1 /*
  2  * keyPath.c
  3  *
  4  *  Created on: 2017年5月17日
  5  *      Author: ygh
  6  */
  7 
  8 #include <stdio.h>
  9 #include <stdlib.h>
 10 
 11 #define MAX_VERTEX_NUM 100 /*define the max number of the vertex*/
 12 #define INFINITY 65535     /*define double byte no negitive integer max number is 65535*/
 13 #define ERROR -1
 14 
 15 typedef int vertex; /*define the data type of the vertex*/
 16 typedef int weightType; /*define the data type of the weight*/
 17 typedef char dataType; /*define the data type of the vertex value*/
 18 
 19 vertex inputOrder[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
 20 /*define the data structure of the Edge*/
 21 typedef struct eNode *ptrToENode;
 22 typedef struct eNode {
 23     vertex v1, v2; /*two vertex between the edge <v1,v2>*/
 24     weightType weight; /*the value of the edge‘s weight */
 25 };
 26 typedef ptrToENode edge;
 27 
 28 /*==================A adjacent link to describe a graph=========================================*/
 29 /*define the data structure adjacent table node*/
 30 typedef struct adjNode *ptrToAdjNode;
 31 typedef struct adjNode {
 32     vertex adjVerx; /*the index of the vertex*/
 33     weightType weight; /*the value of the weight*/
 34     ptrToAdjNode next; /*the point to point the next node*/
 35 };
 36 
 37 /*define the data structure of the adjacent head*/
 38 typedef struct vNode *ptrToVNode;
 39 typedef struct vNode {
 40     ptrToAdjNode head; /*the point to point the adjacent table node*/
 41     dataType data; /*the space to store the name of the vertex,but some time the vertex has no names*/
 42     weightType earliest; /*The earliest data of the project*/
 43     weightType latest; /*The latest time*/
 44 } adjList[MAX_VERTEX_NUM];
 45 
 46 /*define the data structure of graph*/
 47 typedef struct gLNode *ptrTogLNode;
 48 typedef struct gLNode {
 49     int vertex_number; /*the number of the vertex*/
 50     int edge_nunber; /*the number of the edge*/
 51     adjList g; /*adjacent table*/
 52 };
 53 typedef ptrTogLNode adjacentTableGraph; /*a graph show by adjacent table*/
 54 
 55 /*
 56  create a graph given the vertex number.
 57  @param vertexNum The verter number of the graph
 58  @return a graph with vertex but no any egdgs
 59  */
 60 adjacentTableGraph createLGraph(int vertexNum) {
 61     adjacentTableGraph graph;
 62 
 63     vertex v;
 64     graph = (adjacentTableGraph) malloc(sizeof(struct gLNode));
 65     graph->vertex_number = vertexNum;
 66     graph->edge_nunber = 0;
 67     /*initialize the adjacent table*/
 68     for (v = 0; v < graph->vertex_number; v++) {
 69         graph->g[v].head = NULL;
 70         graph->g[v].earliest = 0;
 71         graph->g[v].latest = INFINITY;
 72     }
 73     return graph;
 74 }
 75 
 76 /*
 77  insert a edge to graph.We will distinct oriented graph and undirected graph
 78  The e->v1 and e->v2 are the vertexs‘ indexs in the adjacent table
 79  @param graph The graph you want to insert edge
 80  @param e The edge you want to insert the graph
 81  @param isOriented Whether the graph is oriented graph.If the graph is oriented
 82  we will set adjacent table graph[v1]->head=v2 and set graph[v1].head=v2
 83  otherwise we only set graph[v1].head=v2
 84  */
 85 void insertEdgeToLink(adjacentTableGraph graph, edge e, int isOriented) {
 86     /*build node<v1,v2>*/
 87     ptrToAdjNode newNode;
 88     newNode = (ptrToAdjNode) malloc(sizeof(struct adjNode));
 89     newNode->adjVerx = e->v2;
 90     newNode->weight = e->weight;
 91     newNode->next = graph->g[e->v1].head;
 92     graph->g[e->v1].head = newNode;
 93     /*if the graph is directed graph*/
 94     if (!isOriented) {
 95         newNode = (ptrToAdjNode) malloc(sizeof(struct adjNode));
 96         newNode->adjVerx = e->v1;
 97         newNode->weight = e->weight;
 98         newNode->next = graph->g[e->v2].head;
 99         graph->g[e->v2].head = newNode;
100     }
101 }
102 
103 /*
104  build a graph stored by adjacent table
105  */
106 adjacentTableGraph buildLGraph(int isOrdered) {
107     adjacentTableGraph graph;
108     edge e;
109     vertex i;
110     int vertex_num;
111 
112     scanf("%d", &vertex_num);
113     graph = createLGraph(vertex_num);
114     scanf("%d", &(graph->edge_nunber));
115     if (graph->edge_nunber) {
116         e = (edge) malloc(sizeof(struct eNode));
117         for (i = 0; i < graph->edge_nunber; i++) {
118             scanf("%d %d %d", &e->v1, &e->v2, &e->weight);
119             e->v1--;
120             e->v2--;
121             insertEdgeToLink(graph, e, isOrdered);
122         }
123     }
124 
125     return graph;
126 }
127 
128 /*==============================define a queue=====================================================*/
129 /*define a list to store the element in the queue*/
130 typedef vertex elementType;
131 typedef struct node3 *pList;
132 typedef struct node3 {
133     elementType element;
134     struct node3 *next;
135 };
136 
137 /*define a queue to point the list*/
138 typedef struct node4 *pQueue;
139 typedef struct node4 {
140     pList front; /*the front point to point the head of the list*/
141     pList rear; /*the rear point to point the rear of of the list*/
142 };
143 
144 /*create a empty list to store the queue element*/
145 pList createEmptyList() {
146     pList list;
147     list = (pList) malloc(sizeof(struct node3));
148     list->next = NULL;
149     return list;
150 }
151 /*create a empty queye*/
152 pQueue createEmptyQueue() {
153     pQueue queue = (pQueue) malloc(sizeof(struct node4));
154     queue->front = NULL;
155     queue->rear = NULL;
156     return queue;
157 }
158 
159 /*
160  Wether the queue is empty
161  @param queue The queue need to adjust
162  @return If the queue is null,return 1 otherwise return 0
163  */
164 int isQueueEmpty(pQueue queue) {
165     return (queue->front == NULL);
166 }
167 
168 /*
169  Add a element to a queue,If the queue is null,we will create a new queue
170  @parama queue The queue we will add elememt to
171  @prama element The element we will add to queue
172  */
173 void addQueue(pQueue queue, elementType element) {
174     if (isQueueEmpty(queue)) {
175         pList list = createEmptyList();
176         list->element = element;
177         queue->front = queue->rear = list;
178     } else {
179         pList newNode = (pList) malloc(sizeof(struct node3));
180         newNode->element = element;
181         newNode->next = queue->rear->next;
182         queue->rear->next = newNode;
183         queue->rear = newNode;
184     }
185 }
186 
187 /*
188  delete a element from a queue
189  @param queue The queue will be deleted a element
190  @return The element has been deleted
191  */
192 elementType deleteEleFromQueue(pQueue queue) {
193     if (isQueueEmpty(queue)) {
194         printf("the queue is empty,don‘t allow to delete elemet from it!");
195         return -1;
196     } else {
197         pList oldNode = queue->front;
198         elementType element = oldNode->element;
199         if (queue->front == queue->rear) {
200             queue->rear = queue->front = NULL;
201         } else {
202             queue->front = queue->front->next;
203         }
204         free(oldNode);
205         return element;
206     }
207 }
208 
209 /*
210  * We solve this problem by top sort,but we need to update the adjacent
211  * vertex earliest value at decreasing the adjacent vertex in-degree,the
212  * earliest the max value of parent‘s earliest value add the weight(last time).
213  * The vertex which has no in-degree will set earliest to 0 at first time
214  *
215  * Top sort algorithms thoughts:
216  * 1.we first initialize all vertex in-degree is zero,then we according to
217  * the graph to set the each vertex in-degree.
218  * 2.find zero in-degree vertex and put it in queue.
219  * 3.get a vertex from a queue and record its index
220  * 4.get the all adjacent vertex of the vertex and let them in-degree decrement,at this moment,if
221  * some vertex has decrease into zero,we put them into queue.
222  * 5.Execute this operation until the queue is empty
223  *
224  * @param grap A graph which use adjacent list is used to store the vertex
225  * @param topOrder A <code>vertex</code> array to store the index of the
226  *             vertex about the top queue
227  * @return If the graph is no circle,indicate the top sort is correct 1 will be return
228  * otherwise will return 0
229  */
230 int getEarliestDate(adjacentTableGraph graph, vertex topOrder[]) {
231     vertex v;
232     ptrToAdjNode w;
233     int indegree[MAX_VERTEX_NUM], vertexConter = 0;
234     /*
235      * Create a queue to store the vertex whose in-degree is zero
236      */
237     pQueue queue = createEmptyQueue();
238     /*
239      * Initialize topOrder
240      */
241     for (v = 0; v < graph->vertex_number; v++) {
242         indegree[v] = 0;
243     }
244     for (v = 0; v < graph->vertex_number; v++) {
245         for (w = graph->g[v].head; w; w = w->next) {
246             indegree[w->adjVerx]++;
247         }
248     }
249 
250     /*
251      * Add in-degree vertex to queue
252      */
253     for (v = 0; v < graph->vertex_number; v++) {
254         if (indegree[v] == 0) {
255             addQueue(queue, v);
256             graph->g[v].earliest = 0;
257         }
258     }
259     while (!isQueueEmpty(queue)) {
260         v = deleteEleFromQueue(queue);
261         /*
262          * Record the vertex of top sort
263          */
264         topOrder[vertexConter++] = v;
265         for (w = graph->g[v].head; w; w = w->next) {
266             if ((graph->g[v].earliest + w->weight)
267                     > (graph->g[w->adjVerx].earliest)) {
268                 graph->g[w->adjVerx].earliest = graph->g[v].earliest
269                         + w->weight;
270             }
271             if (--indegree[w->adjVerx] == 0) {
272                 addQueue(queue, w->adjVerx);
273             }
274         }
275     }
276 
277     /*
278      *Adjust whether all vertexes have been recorded
279      */
280     if (vertexConter == graph->vertex_number) {
281         return 1;
282     } else {
283         return 0;
284     }
285 }
286 
287 /*
288  * You know ,we need to let these vertex whose out-degree is zero
289  * latest equal earliest.These whose out-degree is zero is the vertex which
290  * the project‘s finish vertex
291  * @param grap A graph which use adjacent list is used to store the vertex
292  */
293 void initLatest(adjacentTableGraph graph) {
294     vertex v;
295     ptrToAdjNode w;
296     vertex outdegree[graph->vertex_number];
297     for (v = 0; v < graph->vertex_number; v++) {
298         outdegree[v] = 0;
299     }
300     for (v = 0; v < graph->vertex_number; v++) {
301         for (w = graph->g[v].head; w; w = w->next) {
302             outdegree[v]++;
303         }
304     }
305     /*
306      *find out-degree vertex and set them latest equal earliest
307      */
308     for (v = 0; v < graph->vertex_number; v++) {
309         if (outdegree[v] == 0) {
310             graph->g[v].latest = graph->g[v].earliest;
311         }
312     }
313 }
314 
315 /*
316  * Calculate the the latest by the earliest and the top sort result
317  * From the class,we can know the latest value is minimal value amount the child vertex‘s latest
318  * minus the weight(we use the weight as the lasting time).Before caller this method,we have
319  * initialize the terminal vertex latest value.You can see the method above.
320  *@param grap A graph which use adjacent list is used to store the vertex
321  *@param topOrder a <code>vertex</code> array to store the top sort result
322  *
323  */
324 void calculateTheLatest(adjacentTableGraph graph, vertex topOrder[]) {
325     int length = graph->vertex_number, i;
326     ptrToAdjNode w;
327     vertex v;
328     for (i = length - 1; i >= 0; i--) {
329         for (v = 0; v < graph->vertex_number; v++) {
330             for (w = graph->g[v].head; w; w = w->next) {
331                 if (w->adjVerx == topOrder[i]) {
332                     if (graph->g[v].latest
333                             > (graph->g[topOrder[i]].latest - w->weight)) {
334                         graph->g[v].latest = graph->g[topOrder[i]].latest
335                                 - w->weight;
336                     }
337 
338                 }
339             }
340         }
341     }
342 }
343 
344 /*
345  * Print the key path,we know when child vertex‘s latest minus parent vertex‘s earliest
346  * and minus the weight(we use the weight as the lasting time),if the result is  equal zero
347  * indicating this is key path.we print them.
348  *@param grap A graph which use adjacent list is used to store the vertex
349  */
350 void recordKeyActivity(adjacentTableGraph graph) {
351     vertex v;
352     ptrToAdjNode w;
353     for (v = 0; v < graph->vertex_number; v++) {
354         for (w = graph->g[v].head; w; w = w->next) {
355             if (graph->g[w->adjVerx].latest - graph->g[v].earliest
356                     == w->weight) {
357                 printf("%d->%d\n", v + 1, w->adjVerx + 1);
358             }
359         }
360     }
361 }
362 
363 /*
364  * Get the earliest max value from all vertex.we search each vertex and find the max earliest
365  * and return
366  * @param grap A graph which use adjacent list is used to store the vertex
367  */
368 int getEarliestTime(adjacentTableGraph graph) {
369     weightType maxTime = -1;
370     vertex v;
371     for (v = 0; v < graph->vertex_number; v++) {
372         if (graph->g[v].earliest > maxTime) {
373             maxTime = graph->g[v].earliest;
374         }
375     }
376     return maxTime;
377 }
378 
379 /*
380  * Access graph vertex by the index of the vertex
381  */
382 void visit(adjacentTableGraph graph, vertex v) {
383     printf("%d %d %d\n", v, graph->g[v].earliest, graph->g[v].latest);
384 }
385 
386 /*
387  Depth first search a graph
388  @param graph The graph need to search
389  @param startPoint The fisrt point we start search the graph
390  @paran int *visited The array we use to tag the vertex we has accessed.
391  */
392 void DFS(adjacentTableGraph graph, vertex startPoint, int *visited) {
393     ptrToAdjNode p;
394     visit(graph, startPoint);
395     visited[startPoint] = 1;
396     for (p = graph->g[startPoint].head; p; p = p->next) {
397         if (visited[p->adjVerx] == 0) {
398             DFS(graph, p->adjVerx, visited);
399         }
400     }
401 }
402 
403 /*
404  * Fill a array with value
405  * @param arr The array need to be filled
406  * @param length The length of the array
407  * @param filledValue The value the array will be filled
408  */
409 void fullArray(int *arr, int length, int filledValue) {
410     int i;
411     for (i = 0; i < length; i++) {
412         arr[i] = filledValue;
413     }
414 }
415 
416 int main() {
417     adjacentTableGraph graph = buildLGraph(1);
418     vertex topOrder[graph->vertex_number];
419     vertex keyActivities[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
420     int bool = getEarliestDate(graph, topOrder);
421     if (bool) {
422         printf("%d\n", getEarliestTime(graph));
423     } else {
424         printf("0\n");
425     }
426     initLatest(graph);
427     calculateTheLatest(graph, topOrder);
428     recordKeyActivity(graph);
429     return 0;
430 }