![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to dag_levels.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / dag|
Return to dag_levels.c CVS log | Up to [Research Unix] / researchv10no / cmd / dag |
1.1 root 1: #include "draw_dag.h"
2:
3: #include <sys/types.h>
4: #include <sys/times.h>
5: #define TIC 60
6:
7: /*
8: Assign levels to nodes of an acyclic digraph.
9:
10: Definition: the length of an edge is the difference
11: in the levels of its adjacent nodes.
12:
13: Optimization objective: minimize the total edge length
14: of all edges.
15: */
16: static void setlevels(int,int), balance();
17:
18: #ifdef DEBUG
19: static void verifylevel(), verifytree(), verifycycle(), fatal(),
20: checklevel(int*), checkcycle(), printtree(int);
21: #endif
22:
23: void dag_levels(int source, int sink, int hasequi)
24: {
25: struct tms begtm, endtm;
26:
27: if(Verbose)
28: {
29: #ifndef TIMING
30: fprintf(stderr,"Assign levels\n");
31: #endif
32: times(&begtm);
33: }
34:
35: #ifdef DEBUG
36: verifycycle();
37: #endif
38:
39: // space to store level assignments
40: Level = new int[N_nodes];
41:
42: // solve associated lp problems
43: setlevels(source,sink);
44: #ifdef DEBUG
45: verifylevel();
46: #endif
47:
48: // set levels for stems
49: if(N_flat_edges <= 0)
50: {
51: for(int in = 0; in < 2; ++in)
52: {
53: edge_t **edges = in ? Istems : Ostems;
54: for(int v = 0; v < N_nodes; ++v)
55: {
56: if(!edges[v])
57: continue;
58: int lev = Level[v] + (in ? -1 : 1);
59: for(edge_t *e = edges[v]; e; e = e->next)
60: Level[e->node] = lev;
61: }
62: }
63: }
64:
65: // compute Maxlevel
66: Maxlevel = 0;
67: for(int v = 0; v < N_nodes; v++)
68: if(Level[v] > Maxlevel)
69: Maxlevel = Level[v];
70:
71: // balance lists of nodes
72: if(!hasequi)
73: balance();
74: #ifdef DEBUG
75: verifylevel();
76: #endif
77:
78: if(Verbose)
79: {
80: times(&endtm);
81: int total = (endtm.tms_utime-begtm.tms_utime) +
82: (endtm.tms_stime-begtm.tms_stime);
83: int percent = (total - (total/TIC)*TIC)*100/TIC;
84: #ifdef TIMING
85: fprintf(stderr,"%d.%02d\t",total/TIC,percent);
86: #else
87: fprintf(stderr,"Time in level assignment: %d.%02ds\n",
88: total/TIC, percent);
89: fprintf(stderr,"Number of levels = %d\n",Maxlevel+1);
90: #endif
91: }
92: }
93:
94:
95: static void balance()
96: {
97: int *size = new int[N_nodes];
98: for(int v = 0; v < N_nodes; v++)
99: size[Level[v]] += 1;
100: for (v = 0; v < N_nodes; ++v)
101: {
102: int inweight = 0, outweight = 0;
103: int low = 0, high = N_nodes;
104:
105: for (edge_t *e = Inedges[v]; e; e = e->next)
106: {
107: inweight += e->weight;
108: if (Level[e->node] > low)
109: low = Level[e->node];
110: }
111:
112: for (e = Outedges[v]; e; e = e->next)
113: {
114: outweight += e->weight;
115: if (Level[e->node] < high)
116: high = Level[e->node];
117: }
118:
119: if (inweight && (inweight == outweight) && (low+1 < high-1))
120: {
121: int best = low+1;
122: for(int n = low+2; n < high; ++n)
123: if(size[n] < size[best])
124: best = n;
125: size[Level[v]] -= 1;
126: size[best] += 1;
127: Level[v] = best;
128: }
129: }
130: delete size;
131: }
132:
133:
134:
135: /*
136: Below are data structures and code for the network simplex algorithm.
137: */
138: static struct edge_l
139: {
140: int node; // the other end
141: int weight; // edge weight
142: int minlen; // minimum edge length
143: int cutvalue; // value of cut set if this is a tree edge
144: edge_l *next; // doubly linked for constant time insert/delete
145: edge_l *last;
146: edge_l *link; // links for identifying pairs of out/in edges
147:
148: // this routine assume edge insertions are done at the head of the list
149: edge_l(int innode, int inweight, int inminlen, edge_l *innext)
150: {
151: node = innode;
152: weight = inweight;
153: minlen = inminlen;
154: cutvalue = 0;
155: last = NULL;
156: next = innext;
157: if(innext)
158: innext->last = this;
159: }
160: };
161:
162: static edge_l **Oedges, // static in/out-edge lists. No multiple edges
163: **Iedges, // are in these lists.
164: **Itree, // Edges in a feasible spanning tree
165: **Otree;
166:
167: static int n_nodes, // number of mega-nodes
168: *Merge; // mapping from normal nodes to mega-nodes.
169: // The mega-nodes are nodes resulted from
170: // merging sets of nodes which are specified
171: // to be on the same levels.
172:
173:
174: // add a new edge
175: static void addedge(int tail, int head, int weight, int minlen)
176: {
177: // map real nodes to corresponding mega-nodes
178: head = Merge[head];
179: tail = Merge[tail];
180:
181: // check for multiple edges
182: for(edge_l *e = Oedges[tail]; e; e = e->next)
183: if(e->node == head)
184: {
185: e->weight += weight;
186: e->link->weight += weight;
187: e->minlen = max(e->minlen,minlen);
188: return;
189: }
190:
191: // a new edge
192: Oedges[tail] = new edge_l(head,weight,minlen,Oedges[tail]);
193: Iedges[head] = new edge_l(tail,weight,minlen,Iedges[head]);
194:
195: // link the two versions of the edge
196: Oedges[tail]->link = Iedges[head];
197: Iedges[head]->link = Oedges[tail];
198: }
199:
200:
201: // delete an edge from its linked list
202: static void delete_edge(edge_l *e, edge_l **elist)
203: {
204: if(e->last)
205: e->last->next = e->next;
206: else elist[0] = e->next;
207: if(e->next)
208: e->next->last = e->last;
209: }
210:
211:
212: // insert an edge into a linked list
213: static void insert_edge(edge_l *e, edge_l **elist)
214: {
215: e->last = NULL;
216: e->next = elist[0];
217: if(elist[0])
218: elist[0]->last = e;
219: elist[0] = e;
220: }
221:
222:
223: // breadth-first search for initial level assignment
224: static int bfs(int me,int *level,edge_l **edges,int *queue,int *marked,int iter)
225: {
226: #define ENQUEUE(x) queue[tail] = x; if(++tail >= n_nodes) tail = 0;
227: #define DEQUEUE(x) x = queue[head]; if(++head >= n_nodes) head = 0;
228: #define NOTNULL() head != tail
229:
230: int head = 0, tail = 0;
231: ENQUEUE(me);
232:
233: int level_inc = edges == Oedges ? 1 : -1;
234: int n_bfs = 0;
235: while(NOTNULL())
236: {
237: DEQUEUE(me);
238: for(edge_l *e = edges[me]; e; e = e->next)
239: {
240: int it = e->node;
241: int length = level_inc*(level[it]-level[me]);
242:
243: if(level[it] == Maxint || length < e->minlen)
244: {
245: ENQUEUE(it);
246: marked[it] = iter;
247: n_bfs++;
248: level[it] = level[me] + level_inc*e->minlen;
249: }
250: }
251: }
252: return n_bfs;
253: }
254:
255:
256:
257: // construct an initial level assignment
258: static void initlevel(int me,int *level,int *queue,int *marked)
259: {
260: for(int n = 0; n < n_nodes; ++n)
261: marked[n] = 0;
262: level[me] = 0;
263: marked[me] = 2;
264:
265: // level assignment
266: for(int iter = 1;; ++iter)
267: {
268: // odd iter: search down, even iter: search up
269: edge_l **edges = iter%2 ? Oedges : Iedges;
270:
271: int nextiter = iter+1;
272: int alldone = 1;
273: for(n = 0; n < n_nodes; ++n)
274: if(marked[n] >= iter)
275: {
276: if(bfs(n,level,edges,queue,marked,nextiter) > 0)
277: alldone = 0;
278: if(marked[n] > iter && alldone)
279: alldone = 0;
280: }
281: if(alldone)
282: return;
283: }
284: }
285:
286:
287: // compute a feasible spanning tree
288: static void spantree(int me, int *level, int *queue, int *marked)
289: {
290: for(int v = 0; v < n_nodes; ++v)
291: marked[v] = 0;
292:
293: int head = 0, tail = 0;
294: ENQUEUE(me);
295: marked[me] = 1;
296: while(NOTNULL())
297: {
298: DEQUEUE(me);
299: for(int isdown = 0; isdown < 2; ++isdown)
300: {
301: int dir = isdown ? 1 : -1;
302: edge_l **these_edges = isdown ? Oedges : Iedges;
303: edge_l **those_edges = isdown ? Iedges : Oedges;
304: edge_l **these_tree = isdown ? Otree : Itree;
305: edge_l **those_tree = isdown ? Itree : Otree;
306:
307: edge_l *e, *enext;
308: for(e = these_edges[me]; e; e = enext)
309: {
310: enext = e->next;
311:
312: int it = e->node;
313: if(marked[it])
314: continue;
315:
316: if(dir*(level[it]-level[me]) == e->minlen)
317: {
318: delete_edge(e,these_edges+me);
319: insert_edge(e,these_tree+me);
320: delete_edge(e->link,those_edges+it);
321: insert_edge(e->link,those_tree+it);
322:
323: marked[it] = 1;
324: ENQUEUE(it);
325: }
326: }
327: }
328: }
329: }
330:
331:
332: // compute all nodes on one side of the cutset
333: static void cutset(int me, int *marked, int val)
334: {
335: marked[me] = val;
336: for(int isdown = 0; isdown < 2; ++isdown)
337: for(edge_l *e = isdown ? Otree[me] : Itree[me]; e; e = e->next)
338: if(marked[e->node] == 0)
339: cutset(e->node,marked,val);
340: }
341:
342:
343: // compute the initial values of edges in a spanning forest
344: static void treevalue(int *marked)
345: {
346: for(int i = 0; i < n_nodes; ++i)
347: for(edge_l *e = Otree[i]; e; e = e->next)
348: {
349: // compute the cutset partition
350: for(int n = 0; n < n_nodes; ++n)
351: marked[n] = 0;
352:
353: // break the edge
354: marked[i] = 1;
355: marked[e->node] = -1;
356:
357: // search the two sides
358: cutset(i,marked,1);
359: cutset(e->node,marked,-1);
360:
361: int cutvalue = e->weight;
362: for(n = 0; n < n_nodes; ++n)
363: {
364: if(marked[n] == 0)
365: continue;
366: for(edge_l *f = Oedges[n]; f; f = f->next)
367: {
368: if(marked[n] != marked[f->node])
369: {
370: if(marked[n] > 0)
371: cutvalue += f->weight;
372: else cutvalue -= f->weight;
373: }
374: }
375: }
376:
377: e->cutvalue = e->link->cutvalue = cutvalue;
378: }
379: }
380:
381:
382: // update values of tree edges on a fundamental cycle being altered
383: static int treeupdate(int here, int to_be, int cutvalue, int *marked)
384: {
385: marked[here] = 1;
386:
387: for(int isdown = 0; isdown < 2; ++isdown)
388: {
389: for(edge_l *e = isdown ? Otree[here] : Itree[here]; e; e = e->next)
390: {
391: int found = e->node == to_be ? 1 : 0;
392: if(!found && !marked[e->node])
393: found = treeupdate(e->node,to_be,cutvalue,marked);
394: if(found)
395: {
396: e->cutvalue += isdown ? cutvalue : -cutvalue;
397: e->link->cutvalue = e->cutvalue;
398: return 1;
399: }
400: }
401: }
402: return 0;
403: }
404:
405:
406: // the network simplex algorithm for computing levels
407: static void networksimplex(int *level)
408: {
409: // construct a feasible level assignment
410: int *queue = new int[n_nodes];
411: int *marked = new int[n_nodes];
412: for(int i = 0; i < n_nodes; ++i)
413: {
414: marked[i] = 0;
415: level[i] = Maxint;
416: }
417: for(i = 0; i < n_nodes; ++i)
418: if(level[i] == Maxint)
419: {
420: // assign levels to node in the component containing i
421: initlevel(i,level,queue,marked);
422:
423: // now find a feasible spanning tree
424: spantree(i,level,queue,marked);
425: }
426:
427: // initial values of tree edges
428: treevalue(marked);
429:
430: // network simplex loop
431: for(int iter = 0;; ++iter)
432: {
433: #ifdef DEBUG
434: printtree(iter);
435: verifytree();
436: checklevel(level);
437: #endif
438: // find a negative tree edge
439: int cutvalue = 0, treetail;
440: edge_l *treeedge;
441: for(i = 0; i < n_nodes; ++i)
442: for(edge_l *e = Otree[i]; e; e = e->next)
443: if(e->cutvalue < cutvalue)
444: {
445: cutvalue = e->cutvalue;
446: treetail = i;
447: treeedge = e;
448: }
449: // done; the tree is positive
450: if(cutvalue >= 0)
451: break;
452:
453: // compute the cutset partition for this tree edge
454: for(i = 0; i < n_nodes; ++i)
455: marked[i] = 0;
456:
457: marked[treetail] = 1; // break the edge
458: marked[treeedge->node] = -1;
459: cutset(treetail,marked,1);
460: cutset(treeedge->node,marked,-1);
461:
462: // find a non-tree edge to be switched in
463: int length = Maxint;
464: int nontail;
465: edge_l *nonedge = NULL;
466: for(i = 0; i < n_nodes; ++i)
467: {
468: if(marked[i] >= 0)
469: continue;
470: int level_i = level[i];
471: for(e = Oedges[i]; e; e = e->next)
472: {
473: if(marked[e->node] < 0)
474: continue;
475: int len = (level[e->node] - level_i) - e->minlen;
476: if(len < length)
477: {
478: length = len;
479: nontail = i;
480: nonedge = e;
481: }
482: }
483: }
484:
485: // update the value of edges on the involved basic cycle
486: for(i = 0; i < n_nodes; ++i)
487: queue[i] = 0;
488: (void)treeupdate(nontail,nonedge->node,treeedge->cutvalue,queue);
489:
490: // now switch the edges
491: treeedge->cutvalue = treeedge->link->cutvalue = 0;
492: delete_edge(treeedge,Otree+treetail);
493: delete_edge(treeedge->link,Itree+treeedge->node);
494: insert_edge(treeedge,Oedges+treetail);
495: insert_edge(treeedge->link,Iedges+treeedge->node);
496:
497: nonedge->cutvalue = nonedge->link->cutvalue = -cutvalue;
498: delete_edge(nonedge,Oedges+nontail);
499: delete_edge(nonedge->link,Iedges+nonedge->node);
500: insert_edge(nonedge,Otree+nontail);
501: insert_edge(nonedge->link,Itree+nonedge->node);
502:
503: // update level info
504: if(length > 0)
505: {
506: for(i = 0; i < n_nodes; ++i)
507: if(marked[i] > 0)
508: level[i] -= length;
509: }
510: #ifdef DEBUG
511: printtree(iter);
512: verifytree();
513: checklevel(level);
514: #endif
515: }
516:
517: #ifndef TIMING
518: if(Verbose)
519: fprintf(stderr,"# of network simplex iterations = %d\n",iter);
520: #endif
521:
522: // make the level assignment starts from 0 for each connected component
523: for(i = 0; i < n_nodes; ++i)
524: marked[i] = 0;
525: for(i = 0; i < n_nodes; ++i)
526: {
527: if(marked[i])
528: continue;
529:
530: // use breadth-first search to get all nodes in this component.
531: int n = 0, n_elt = 0;
532: queue[n_elt++] = i;
533: marked[i] = 1;
534: while(n < n_elt)
535: {
536: int me = queue[n++];
537: for(int isdown = 0; isdown < 2; ++isdown)
538: {
539: edge_l *e = isdown ? Otree[me] : Itree[me];
540: for(; e; e = e->next)
541: if(!marked[e->node])
542: {
543: queue[n_elt++] = e->node;
544: marked[e->node] = 1;
545: }
546: }
547: }
548:
549: int minlev = Maxint;
550: for(n = 0; n < n_elt; ++n)
551: if(level[queue[n]] < minlev)
552: minlev = level[queue[n]];
553: if(minlev != 0 && minlev != Maxint)
554: for(n = 0; n < n_elt; ++n)
555: level[queue[n]] -= minlev;
556: }
557:
558: // restore space
559: delete marked;
560: delete queue;
561: }
562:
563:
564: static void setlevels(int source, int sink)
565: {
566: // Merge[] contains new names of the mega-nodes that represent
567: // true nodes that are specified to be at the same levels.
568: Merge = new int[N_nodes];
569: n_nodes = 0;
570: for(int i = 0; i < N_nodes; ++i)
571: if(i == Root[i])
572: Merge[i] = n_nodes++;
573: for(i = 0; i < N_nodes; ++i)
574: Merge[i] = Merge[Root[i]];
575:
576: // construct the new edge lists.
577: // Since no min_edge_length info is kept, this is 1
578: Oedges = new edge_l*[n_nodes];
579: Iedges = new edge_l*[n_nodes];
580: for(i = 0; i < N_nodes; ++i)
581: for(edge_t *e = Outedges[i]; e; e = e->next)
582: addedge(i,e->node,e->weight,e->minlen);
583:
584: // add constraint edges for sources and sinks.
585: // These edges have zero weight and zero min_edge_length
586: if(source >= 0 || sink >= 0)
587: {
588: for(i = 0; i < N_nodes; ++i)
589: if(i == Root[i])
590: {
591: if(source >= 0 && i != source)
592: addedge(source,i,0,0);
593: if(sink >= 0 && i != sink)
594: addedge(i,sink,0,0);
595: }
596: }
597:
598: // get level assignment
599: Otree = new edge_l*[n_nodes];
600: Itree = new edge_l*[n_nodes];
601: int *level = new int[n_nodes];
602: networksimplex(level);
603: #ifdef DEBUG
604: checklevel(level);
605: #endif
606:
607: // now reassign level assignment to real nodes
608: for(i = 0; i < N_nodes; ++i)
609: Level[i] = level[Merge[i]];
610: #ifdef DEBUG
611: verifylevel();
612: #endif
613:
614: // restore space used
615: for(i = 0; i < n_nodes; ++i)
616: {
617: edge_l *enext;
618: for(edge_l *e = Oedges[i]; e; e = enext)
619: {
620: enext = e->next;
621: delete e;
622: }
623: for(e = Iedges[i]; e; e = enext)
624: {
625: enext = e->next;
626: delete e;
627: }
628: for(e = Otree[i]; e; e = enext)
629: {
630: enext = e->next;
631: delete e;
632: }
633: for(e = Itree[i]; e; e = enext)
634: {
635: enext = e->next;
636: delete e;
637: }
638: }
639: delete Iedges;
640: delete Oedges;
641: delete Itree;
642: delete Otree;
643: delete Merge;
644: delete level;
645: }
646:
647:
648: #ifdef DEBUG
649: static void fatal()
650: {
651: (void) abort();
652: }
653:
654: static void printtree(int iter)
655: {
656: fprintf(stderr,"Iteration=%d\n",iter);
657: for(int i = 0; i < n_nodes; ++i)
658: for(edge_l *e = Otree[i]; e; e = e->next)
659: fprintf(stderr,"%d -> %d : cutvalue=%d\n",i,e->node,e->cutvalue);
660: for(i = 0; i < n_nodes; ++i)
661: for(e = Oedges[i]; e; e = e->next)
662: fprintf(stderr,"%d -> %d\n", i,e->node);
663: }
664:
665: static void verifytree()
666: {
667: int *marked = new int[n_nodes];
668:
669: for(int i = 0; i < n_nodes; ++i)
670: for(edge_l *e = Otree[i]; e; e = e->next)
671: {
672: // compute the cutset partition
673: for(int n = 0; n < n_nodes; ++n)
674: marked[n] = 0;
675:
676: // break the edge
677: marked[i] = 1;
678: marked[e->node] = -1;
679: cutset(i,marked,1);
680: cutset(e->node,marked,-1);
681:
682: int cutvalue = e->weight;
683: for(n = 0; n < n_nodes; ++n)
684: {
685: if(marked[n] == 0)
686: continue;
687: for(edge_l *f = Oedges[n]; f; f = f->next)
688: if(marked[n] != marked[f->node])
689: {
690: if(marked[f->node] == 0)
691: fatal();
692: if(marked[n] > 0)
693: cutvalue += f->weight;
694: else cutvalue -= f->weight;
695: }
696: }
697:
698: if(e->cutvalue != cutvalue)
699: fatal();
700: }
701:
702: delete marked;
703: }
704:
705: static void checklevel(int *level)
706: {
707: for(int v = 0; v < n_nodes; ++v)
708: {
709: for(edge_l *e = Oedges[v]; e; e = e->next)
710: if(level[e->node]-level[v] < e->minlen)
711: fatal();
712: for(e = Otree[v]; e; e = e->next)
713: if(level[e->node]-level[v] != e->minlen)
714: fatal();
715: for(e = Iedges[v]; e; e = e->next)
716: if(level[v]-level[e->node] < e->minlen)
717: fatal();
718: for(e = Itree[v]; e; e = e->next)
719: if(level[v]-level[e->node] != e->minlen)
720: fatal();
721: }
722: }
723:
724: static void verifylevel()
725: {
726: for(int v = 0; v < N_nodes; ++v)
727: {
728: for(edge_t *e = Outedges[v]; e; e = e->next)
729: if(Level[v] >= Level[e->node])
730: fatal();
731: for(e = Inedges[v]; e; e = e->next)
732: if(Level[v] <= Level[e->node])
733: fatal();
734: }
735: }
736:
737: static void checksearch(int v, int *marked, int isdown)
738: {
739: marked[v] = 1;
740: for(edge_l *e = isdown ? Oedges[v] : Iedges[v]; e; e = e->next)
741: {
742: if(marked[e->node] == 1)
743: fatal();
744: if(!marked[e->node])
745: checksearch(e->node,marked,isdown);
746: }
747: marked[v] = 2;
748: }
749: static void checkcycle()
750: {
751: int *marked = new int[n_nodes];
752: for(int v = 0; v < n_nodes; ++v)
753: if(!marked[v])
754: checksearch(v,marked,1);
755:
756: for(v = 0; v < n_nodes; ++v)
757: marked[v] = 0;
758: for(v = 0; v < n_nodes; ++v)
759: if(!marked[v])
760: checksearch(v,marked,0);
761:
762: delete marked;
763: }
764:
765: static void verifysearch(int v, int *marked, int isdown)
766: {
767: marked[v] = 1;
768: for(edge_t *e = isdown ? Outedges[v] : Inedges[v]; e; e = e->next)
769: {
770: if(marked[e->node] == 1)
771: fatal();
772: if(!marked[e->node])
773: verifysearch(e->node,marked,isdown);
774: }
775: marked[v] = 2;
776: }
777: static void verifycycle()
778: {
779: int *marked = new int[N_nodes];
780: for(int v = 0; v < N_nodes; ++v)
781: if(!marked[v])
782: verifysearch(v,marked,1);
783:
784: for(v = 0; v < N_nodes; ++v)
785: marked[v] = 0;
786: for(v = 0; v < N_nodes; ++v)
787: if(!marked[v])
788: verifysearch(v,marked,0);
789:
790: for(v = 0; v < N_nodes; ++v)
791: {
792: for(edge_t *e = Outedges[v]; e; e = e->next)
793: if(e->minlen < 1)
794: fatal();
795: for(e = Inedges[v]; e; e = e->next)
796: if(e->minlen < 1)
797: fatal();
798: }
799:
800: delete marked;
801: }
802: #endif
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.