![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to dag_ranks.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_ranks.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: Create an ordering of nodes on each level.
9: The ordering attempts to minimize edge crossing
10: */
11: static float Convergence = .005; // convergence rate
12: static int Maxiter = 24; // max number of iterations
13: static int Minquit = 10; // quit after this many iterations
14: // if not improved
15: static int **List; // temp space for rank construction
16: static int *Count, // to aid rcross()
17: *Cross, // current numbers of crossings between levels
18: *Levelmarked; // used in transpose()
19: static edge_t **Flatedges; // transitive closure of flat edges
20: static int *Flatindeg; // in-degree of nodes using Flatedges
21:
22: static long *Median;
23: static int *Medadj;
24:
25: static void decompose(),
26: flatclosure(),
27: removestem(),
28: installstem(int**,int);
29: static int cross_stat(int**), rcross(int*,int*),
30: buildrank(int**,int**,int);
31: extern void inversion(int**);
32:
33: void dag_ranks()
34: {
35: struct tms begtm, endtm;
36: int startcross = 0;
37:
38: if(Verbose)
39: {
40: #ifndef TIMING
41: fprintf(stderr,"Minimize edge crossing\n");
42: #endif
43: times(&begtm);
44: }
45: #ifdef TIMING
46: Maxiter = 20;
47: Minquit = 20;
48: Convergence = .0001;
49: #else
50: // reset parameters for speed
51: if(N_real_nodes > 500)
52: {
53: float density = ((float) N_edges)/N_nodes;
54: if(density >= 2.)
55: {
56: Maxiter = N_real_nodes <= 1000 ? 8 : 4;
57: Minquit = N_real_nodes <= 1000 ? 4 : 2;
58: Convergence = N_real_nodes <= 1000 ? .01 : .1;
59: }
60: }
61: #endif
62:
63: // number of nodes in each level
64: N_level = new int[Maxlevel+1];
65: for(int i = 0; i < N_nodes; i++)
66: N_level[Level[i]] += 1;
67:
68: // create space for node lists
69: List = new int*[Maxlevel+1];
70: Rank = new int*[Maxlevel+1];
71: int **tryout = new int*[Maxlevel+1];
72: int **target = new int*[Maxlevel+1];
73: for(i = 0; i <= Maxlevel; ++i)
74: {
75: List[i] = new int[N_level[i]+1];
76: tryout[i] = new int[N_level[i]+1];
77: Rank[i] = new int[N_level[i]+1];
78: Rank[i][0] = -1;
79: }
80:
81: // space for intermediate calculations
82: Invert = new int[N_nodes];
83: Count = new int[N_nodes];
84: Cross = new int[Maxlevel];
85: Levelmarked = new int[Maxlevel+1];
86: Median = new long[N_nodes];
87: Medadj = new int[N_nodes+N_repeat_edges];
88:
89: // compute the transitive closure of the set of flat edges
90: if(N_flat_edges > 0)
91: {
92: Flatedges = new edge_t*[N_real_nodes];
93: Flatindeg = new int[N_real_nodes];
94: flatclosure();
95: }
96:
97: // detect connected components
98: Component = new int[N_nodes];
99: decompose();
100:
101: // build up the ordering component by component
102: for(int component = 1; component <= N_component; ++component)
103: {
104: for(i = 0; i <= Maxlevel; ++i)
105: {
106: for(int k = 0; ; ++k)
107: if(Rank[i][k] == -1)
108: break;
109: target[i] = Rank[i]+k;
110: }
111: startcross += buildrank(target,tryout,component);
112: }
113: inversion(Rank);
114:
115: if(Verbose)
116: {
117: times(&endtm);
118: int total = (endtm.tms_utime - begtm.tms_utime)+
119: (endtm.tms_stime - begtm.tms_stime);
120: int percent = (total - (total/TIC)*TIC)*100/TIC;
121: int bestcross = cross_stat(Rank);
122: #ifdef TIMING
123: fprintf(stderr,"%d\t%d\t%d.%02d\t",
124: startcross,bestcross,total/TIC,percent);
125: #else
126: fprintf(stderr,"Starting crossing number = %d\n",startcross);
127: fprintf(stderr,"Crossings between ranks:\n");
128: for(i = 0; i < Maxlevel; ++i)
129: fprintf(stderr,"(%2d,%2d):\tx=%d\n",i,i+1,Cross[i]);
130: fprintf(stderr,"Ending crossing number = %d\n",bestcross);
131: fprintf(stderr,"Time in minimizing crossing: %d.%02ds\n",
132: total/TIC, percent);
133: #endif
134: }
135:
136: // release temp space
137: delete Median;
138: delete Medadj;
139: delete Levelmarked;
140: delete Cross;
141: delete Count;
142: for(i = 0; i <= Maxlevel; ++i)
143: {
144: delete List[i];
145: delete tryout[i];
146: }
147: delete List;
148: delete tryout;
149: delete target;
150: if(N_flat_edges > 0)
151: deledges(N_real_nodes,Flatedges);
152: }
153:
154: // compute the transitive closure of flat edges
155: // and remove resulting bidirectional edges.
156: // The final graph defines a partial order on the nodes.
157: static void flatedges(int root, int here, int *marked)
158: {
159: marked[here] = 1;
160:
161: for(edge_t *e = Noedges[here]; e; e = e->next)
162: if(e->weight > 0 && !marked[e->node])
163: {
164: // check for bi-directional edges
165: edge_t *lastf = NULL, *f = Flatedges[e->node];
166: for(; f != NULL; lastf = f, f = f->next)
167: if(f->node == root)
168: break;
169:
170: // remove bidirectional edges
171: if(f != NULL)
172: {
173: if(lastf)
174: lastf->next = f->next;
175: else Flatedges[e->node] = f->next;
176: delete f;
177: }
178: // add a new edge
179: else Flatedges[root] =
180: new edge_t(e->node,0,0,0,Flatedges[root]);
181:
182: flatedges(root,e->node,marked);
183: }
184: }
185:
186: static void flatclosure()
187: {
188: int *marked = Count;
189: for(int v = 0; v < N_real_nodes; ++v)
190: {
191: for(int i = 0; i < N_real_nodes; ++i)
192: marked[i] = 0;
193: flatedges(v,v,marked);
194: }
195:
196: for(v = 0; v < N_real_nodes; ++v)
197: for(edge_t *e = Flatedges[v]; e; e = e->next)
198: Flatindeg[e->node]++;
199: }
200:
201: // assign component numbers to nodes so that nodes in the same
202: // connected component get the same number.
203: static void decompose()
204: {
205: // make a reverse flat edge list
206: edge_t **noedges = NULL;
207: if(N_flat_edges > 0)
208: {
209: noedges = new edge_t*[N_real_nodes];
210: for(int v = 0; v < N_real_nodes; ++v)
211: for(edge_t *e = Noedges[v]; e; e = e->next)
212: {
213: int w = e->node;
214: if(w != v)
215: noedges[w] = new edge_t(v,0,0,0,noedges[w]);
216: }
217: }
218:
219: // all adjacent edge lists
220: edge_t **adjlist[5];
221: adjlist[0] = Outedges;
222: adjlist[1] = Inedges;
223: adjlist[2] = N_flat_edges > 0 ? Noedges : NULL;
224: adjlist[3] = N_flat_edges > 0 ? noedges : NULL;
225: adjlist[4] = NULL;
226:
227: // space for the breadth-first search
228: int *queue = new int[N_nodes];
229:
230: N_component = 0;
231: for(int n = 0; n < N_nodes; ++n)
232: {
233: if(Component[n] > 0)
234: continue;
235:
236: // initialize for component search
237: N_component += 1;
238: Component[n] = N_component;
239:
240: // breadth-first search
241: int first = 0, last = 1;
242: queue[0] = n;
243: while(first < last)
244: {
245: int v = queue[first++];
246: for(int i = 0; adjlist[i] != NULL; ++i)
247: {
248: if(v >= N_real_nodes && i >= 2)
249: continue;
250: for(edge_t *e = adjlist[i][v]; e; e = e->next)
251: {
252: int w = e->node;
253: if(Component[w] != 0)
254: continue;
255: Component[w] = N_component;
256: queue[last++] = w;
257: }
258: }
259: }
260: }
261:
262: delete queue;
263: if(N_flat_edges > 0)
264: deledges(N_real_nodes,noedges);
265: }
266:
267: // copy a ranking to another
268: static void copyrank(int **from, int **to)
269: {
270: for(int i = 0; i <= Maxlevel; ++i)
271: {
272: register int *frp = from[i], *top = to[i];
273: while(*frp != -1)
274: *top++ = *frp++;
275: *top = -1;
276: }
277: }
278:
279: // see if one vertex must be left of another
280: static int left2right(int v, int w)
281: {
282: if(v >= N_real_nodes || w >= N_real_nodes)
283: return 0;
284:
285: for(edge_t *e = Flatedges[v]; e; e = e->next)
286: if(e->node == w)
287: return 1;
288: return 0;
289: }
290:
291: // construct nodes reachable from 'here' in post-order.
292: // This is the same as doing a topological sort in reverse order.
293: static void postorder(int here,int *marked,int *list, int &n_search)
294: {
295: marked[here] = 1;
296: for(edge_t *e = Flatedges[here]; e; e = e->next)
297: if(!marked[e->node])
298: postorder(e->node,marked,list,n_search);
299: list[n_search++] = here;
300: }
301:
302: static void reorder(int *list, int *marked, int *temp)
303: {
304: for(int i = 0; list[i] >= 0; ++i)
305: marked[list[i]] = 0;
306:
307: int n_temp = 0;
308: for(i = 0; list[i] >= 0; ++i)
309: {
310: // dummy nodes
311: if(list[i] >= N_real_nodes)
312: temp[n_temp++] = list[i];
313: // real nodes
314: else if(!marked[list[i]] && Flatindeg[list[i]] == 0)
315: {
316: int n_search = 0;
317: postorder(list[i],marked,temp+n_temp,n_search);
318: int *left = temp+n_temp, *right = left+n_search-1;
319: for(; left < right; ++left, --right)
320: {
321: int t = *left;
322: *left = *right;
323: *right = t;
324: }
325: n_temp += n_search;
326: }
327: }
328:
329: // recopy the list
330: for(i = 0; list[i] >= 0; ++i)
331: list[i] = temp[i];
332: }
333:
334: // Compute an initial ordering of nodes belonging to some connected component.
335: static void initrank(int *rank[], int component, int isdown)
336: {
337: // use breadth-first search to build the list
338: int *marked = new int[N_nodes];
339: int *queue = new int[N_nodes];
340: int *n_lev = new int[Maxlevel+1];
341:
342: // now do the rank partitioning by components
343: edge_t **those = isdown ? Inedges : Outedges;
344: edge_t **these = isdown ? Outedges : Inedges;
345: for(int n = 0; n < N_nodes; ++n)
346: {
347: if(marked[n] || those[n] || Component[n] != component ||
348: (n < N_real_nodes && N_flat_edges <= 0 && Stems[n]))
349: continue;
350:
351: marked[n] = 1;
352: queue[0] = n;
353: int first = 0, last = 1;
354: while(first < last)
355: {
356: int node = queue[first++];
357: rank[Level[node]][n_lev[Level[node]]++] = node;
358: for(edge_t *e = these[node]; e; e = e->next)
359: {
360: if(!marked[e->node])
361: {
362: marked[e->node] = 1;
363: queue[last++] = e->node;
364: }
365: }
366: }
367: }
368:
369: for(n = 0; n <= Maxlevel; ++n)
370: {
371: rank[n][n_lev[n]] = -1;
372:
373: // make sure that implicit left-to-right orders are satisfied
374: if(N_flat_edges > 0)
375: reorder(rank[n],marked,queue);
376: }
377:
378: delete marked;
379: delete queue;
380: delete n_lev;
381: }
382:
383: // Compute the crossing of two levels.
384: // We'll assume that edges point from top to bot.
385: static int rcross(int *top, int *bot)
386: {
387: // clear up work space
388: for (int i = 0; bot[i] != -1; i++)
389: Count[i] = 0;
390:
391: register int cross = 0; // the crossing count
392: int max = 0; // index we have to sum to during counting
393: for (i = 0; top[i] != -1; i++)
394: {
395: register edge_t *e;
396:
397: if (max > 0)
398: {
399: /* iterate over each edge */
400: for (e = Outedges[top[i]]; e; e = e->next)
401: for(int k = Invert[e->node]+1; k <= max; k++)
402: cross += Count[k]*e->count;
403: }
404:
405: /* update the counts */
406: for (e = Outedges[top[i]]; e; e = e->next)
407: {
408: register int inv = Invert[e->node];
409: if (inv > max)
410: max = inv;
411: Count[inv] += e->count;
412: }
413: }
414: return cross;
415: }
416:
417: // compute the inverted indices of all vertices in their rank lists
418: // and the crossing statistics between ranks.
419: static void inversion(int **ranks)
420: {
421: for(int i = 0; i <= Maxlevel; ++i)
422: {
423: int *rank = ranks[i];
424: for(int k = 0; rank[k] != -1; ++k)
425: Invert[rank[k]] = k;
426: }
427: }
428:
429: static int cross_stat(int **ranks)
430: {
431: int cross = 0;
432: for(int i = 0; i < Maxlevel; ++i)
433: cross += (Cross[i] = rcross(ranks[i],ranks[i+1]));
434: return cross;
435: }
436:
437: // Compute the crossing of incident edges of two vertices
438: static int vcross(edge_t *adj1, edge_t *adj2)
439: {
440: register int cross = 0;
441: for (register edge_t *e2 = adj2; e2; e2 = e2->next)
442: {
443: register int inv = Invert[e2->node];
444: register int cnt = e2->count;
445: for(register edge_t *e1 = adj1; e1; e1 = e1->next)
446: if(Invert[e1->node] > inv)
447: cross += e1->count * cnt;
448: }
449: return cross;
450: }
451:
452: // Reduce crossings by adjacent tranpositions of vertices
453: static void transpose(int **ranks, int revert)
454: {
455: // current number of crossings
456: int curcross = 0;
457: for(int l = 0; l < Maxlevel; ++l)
458: {
459: curcross += Cross[l];
460: Levelmarked[l] = 1;
461: }
462: if(curcross == 0)
463: return;
464: else Levelmarked[l] = 1;
465:
466: while(1)
467: {
468: int delta = 0;
469: for (int lev = 0; lev <= Maxlevel; lev++)
470: if(Levelmarked[lev])
471: {
472: int *rank = ranks[lev];
473: if(rank[0] == -1 || rank[1] == -1)
474: {
475: Levelmarked[lev] = 0;
476: continue;
477: }
478: for(; rank[1] != -1; ++rank)
479: {
480: register int c0 = 0, c1 = 0;
481: int v = rank[0], w = rank[1];
482:
483: if(N_flat_edges > 0 && left2right(v,w) != 0)
484: continue;
485:
486: if(lev > 0)
487: {
488: edge_t *vadj = Inedges[v], *wadj = Inedges[w];
489: c0 += vcross(vadj,wadj);
490: c1 += vcross(wadj,vadj);
491: }
492: if(lev < Maxlevel)
493: {
494: edge_t *vadj = Outedges[v], *wadj = Outedges[w];
495: c0 += vcross(vadj,wadj);
496: c1 += vcross(wadj,vadj);
497: }
498:
499: if (c1 < c0 || (c1 > 0 && c1 == c0 && revert))
500: {
501: Levelmarked[lev] = 2;
502: Invert[v]++;
503: Invert[w]--;
504: rank[0] = w;
505: rank[1] = v;
506: delta += c0-c1;
507: }
508: }
509:
510: if(Levelmarked[lev] == 2)
511: {
512: Levelmarked[lev] = 1;
513: if(lev > 0)
514: {
515: Levelmarked[lev-1] = 1;
516: Cross[lev-1] = -1;
517: }
518: if(lev < Maxlevel)
519: {
520: Levelmarked[lev+1] = 1;
521: Cross[lev] = -1;
522: }
523: }
524: else Levelmarked[lev] = 0;
525: }
526:
527: curcross -= delta;
528: float reduce = curcross <= 0 ? 0. : ((float)delta)/curcross;
529: if(curcross == 0 || reduce <= Convergence)
530: break;
531: }
532:
533: // restore crossing statistics
534: for(l = 0; l < Maxlevel; ++l)
535: if(Cross[l] < 0)
536: Cross[l] = rcross(ranks[l],ranks[l+1]);
537: }
538:
539: // sort nodes by their median values.
540: // This is basically a bubble sort that respects fixed points
541: static int mediansort(int *array, int nelt, int revert, int hasfixed)
542: {
543: int changed = 0;
544:
545: register int *ep = array+nelt, *lp, *rp;
546: for(nelt -= 1; nelt > 0; --nelt)
547: {
548: lp = array;
549: while(lp < ep)
550: {
551: // -1 nodes are FIXED points
552: if(Median[*lp] < 0)
553: for(; lp < ep; lp++)
554: if(Median[*lp] >= 0)
555: break;
556: if(lp >= ep)
557: break;
558:
559: // find the one that can be compared with
560: int muststay = 0;
561: for(rp = lp+1; rp < ep; ++rp)
562: {
563: if(N_flat_edges > 0 && left2right(*lp,*rp))
564: {
565: muststay = 1;
566: break;
567: }
568: if(Median[*rp] >= 0)
569: break;
570: }
571: if(rp >= ep)
572: break;
573:
574: // switch if appropriate
575: if(!muststay &&
576: (Median[*lp] > Median[*rp] ||
577: (Median[*lp] == Median[*rp] && revert)))
578: {
579: register int t = *lp;
580: *lp = *rp;
581: *rp = t;
582: changed++;
583: }
584: lp = rp;
585: }
586:
587: if(!hasfixed && !revert)
588: --ep;
589: }
590: return changed;
591: }
592:
593:
594: // reduce crossing using weighted median sorting
595: static int intcmp(register int *i1, register int *i2)
596: {
597: return *i1 - *i2;
598: }
599: static void median(int **ranks, int revert, int isup)
600: {
601: #define SCALE 16
602: for (int lev = 1; lev <= Maxlevel; lev++)
603: {
604: int thislev = isup ? Maxlevel-lev : lev;
605: int thatlev = isup ? thislev+1 : thislev-1;
606: edge_t **edges = isup ? Outedges : Inedges;
607: int *thislist = ranks[thislev];
608: int *thatlist = ranks[thatlev];
609:
610: // compute medians of thislist
611: int hasfixed = 0;
612: for(int n_this = 0; thislist[n_this] != -1; n_this++)
613: {
614: register int node = thislist[n_this];
615: register int *endadj = Medadj;
616: for(register edge_t *e = edges[node]; e; e = e->next)
617: for(int k = e->count; k > 0; --k)
618: *endadj++ = Invert[e->node];
619: register int cnt = endadj-Medadj;
620: #ifdef BCENTER
621: // barycenter method
622: if(cnt > 0)
623: {
624: int ave = 0;
625: for(int m = 0; m < cnt; ++m)
626: ave += Medadj[m];
627: Median[node] = (SCALE*ave)/cnt;
628: }
629: else
630: {
631: Median[node] = -1;
632: hasfixed = 1;
633: }
634: #else /* a right median method */
635: #ifdef RMEDIAN
636: if(cnt > 1)
637: qsort((char*)Medadj,cnt,sizeof(Medadj[0]),(qsortcmpfun)intcmp);
638: if(cnt == 0)
639: {
640: Median[node] = -1;
641: hasfixed = 1;
642: }
643: else Median[node] = SCALE*Medadj[cnt/2];
644: #else /* weighted median */
645: switch(cnt)
646: {
647: case 0 :
648: Median[node] = -1;
649: hasfixed = 1;
650: break;
651: case 1 :
652: Median[node] = SCALE*Medadj[0];
653: break;
654: case 2 :
655: Median[node] = (Medadj[0]+Medadj[1])*(SCALE/2);
656: break;
657: default :
658: qsort((char*)Medadj,cnt,sizeof(Medadj[0]),(qsortcmpfun)intcmp);
659: if(cnt%2)
660: {
661: Median[node] = SCALE*Medadj[cnt/2];
662: break;
663: }
664:
665: register int r = cnt/2;
666: register int l = r-1;
667:
668: // compute left/right spans
669: int lspan = 0, rspan = 0;
670: int curinv = Medadj[l];
671: int nextinv;
672: for(k = l-1; k >= 0; --k)
673: {
674: nextinv = Medadj[k];
675: lspan += curinv-nextinv;
676: curinv = nextinv;
677: }
678: curinv = Medadj[r];
679: for(k = r+1; k < cnt; ++k)
680: {
681: nextinv = Medadj[k];
682: rspan += nextinv-curinv;
683: curinv = nextinv;
684: }
685: if(lspan == rspan)
686: Median[node] = (Medadj[l]+Medadj[r])*(SCALE/2);
687: else
688: {
689: int w = Medadj[l]*rspan+ Medadj[r]*lspan;
690: Median[node] = (w*SCALE)/(lspan+rspan);
691: }
692: break;
693: }
694: #endif /* RMEDIAN */
695: #endif /* BCENTER */
696: }
697:
698: // sort by medians
699: if(mediansort(thislist,n_this,revert,hasfixed))
700: {
701: for(int i = 0; *thislist != -1; ++i)
702: Invert[*thislist++] = i;
703: if(thislev > 0)
704: Cross[thislev-1] = -1;
705: if(thislev < Maxlevel)
706: Cross[thislev] = -1;
707: }
708: }
709: for(lev = 0; lev < Maxlevel; ++lev)
710: if(Cross[lev] < 0)
711: Cross[lev] = rcross(ranks[lev],ranks[lev+1]);
712: }
713:
714: // minimizing crossing using the median and transpose heuristics
715: static int mincross(int **ranks, int bestcross)
716: {
717: // copy current rank to List to start the process
718: copyrank(ranks,List);
719:
720: inversion(List);
721: int curcross = cross_stat(List);
722: if(curcross < bestcross)
723: bestcross = curcross;
724:
725: int counter = 1;
726: for (int iter = 0; iter < Maxiter; iter++)
727: {
728: median(List,iter%4 < 2 ? 1 : 0,iter%2 ? 1 : 0);
729: #ifndef NOTRANSPOSE
730: transpose(List,iter%4 < 2 ? 0 : 1);
731: #endif
732: curcross = 0;
733: for(int i = 0; i < Maxlevel; ++i)
734: curcross += Cross[i];
735: #ifdef BIGGRAPH
736: if(Verbose)
737: fprintf(stderr,"Iteration %d, curcross=%d bestcross=%d\n",
738: iter,curcross,bestcross);
739: #endif
740: if(curcross < bestcross)
741: {
742: float reduce = curcross <= 0 ? 0. :
743: ((float)(bestcross-curcross))/curcross;
744:
745: copyrank(List,ranks);
746: bestcross = curcross;
747:
748: if(bestcross == 0 || reduce < Convergence)
749: break;
750:
751: counter = 1;
752: }
753: else
754: {
755: if(counter > Minquit)
756: break;
757: ++counter;
758: }
759: }
760:
761: return bestcross;
762: }
763:
764: // compute edge crossings
765: static int scross(int iw, int count, edge_t *adj, int dir)
766: {
767: int cross = 0;
768: if(dir > 0)
769: {
770: for(register edge_t *e = adj; e; e = e->next)
771: if(Invert[e->node] < iw)
772: cross += e->count*count;
773: }
774: else
775: {
776: for(register edge_t *e = adj; e; e = e->next)
777: if(Invert[e->node] > iw)
778: cross += e->count*count;
779: }
780: return cross;
781: }
782:
783: // put stems in place where they'll be close to their adjacent nodes
784: static void fixstem(int **ranks, int *stem)
785: {
786: for(int dir = 1; dir >= -1; dir -= 2)
787: for(int l = dir > 0 ? 1 : Maxlevel-1; l >= 0 && l <= Maxlevel; l += dir)
788: {
789: edge_t **these = dir > 0 ? Inedges : Outedges;
790: edge_t **those = dir > 0 ? Outedges : Inedges;
791: int *rank = ranks[l];
792:
793: // count the list size
794: int n_rank = 0;
795: int n_stem = 0;
796: for(int k = 0; rank[k] >= 0; ++k, ++n_rank)
797: {
798: int v = rank[k];
799: if(these[v] && !these[v]->next && !those[v])
800: stem[n_stem++] = v;
801: }
802: if(n_stem <= 0)
803: continue;
804:
805: for(k = 0; k < n_stem; ++k)
806: {
807: int v = stem[k], iv = Invert[v];
808: int w = these[v]->node, iw = Invert[w];
809: int count = these[v]->count;
810:
811: // find the left and right medians and bounds
812: int n = 0;
813: for(edge_t *e = those[w]; e; e = e->next)
814: if(e->node != v)
815: Medadj[n++] = Invert[e->node];
816: if(n == 0)
817: continue;
818: if(n > 2)
819: qsort((char*)Medadj,n,sizeof(Medadj[0]),(qsortcmpfun)intcmp);
820: int rmed = Medadj[n/2];
821: int lmed = n%2 ? rmed : Medadj[n/2-1];
822:
823: // check each position
824: int best = iv, cross = 0;
825: int dist = iabs(2*iv - (rmed+lmed));
826: for(int d = -1; d <= 1; d += 2)
827: {
828: int c = 0, lm = lmed, rm = rmed;
829: for(int p = iv+d; p >= 0 && p < n_rank; p += d)
830: {
831: int x = rank[p];
832: if(p == lm)
833: lm -= d;
834: if(p == rm)
835: rm -= d;
836:
837: int c0 = scross(iw,count,these[x],d);
838: int c1 = scross(iw,count,these[x],-d);
839: c += c1-c0;
840: if(c == cross)
841: {
842: int di = iabs(2*p -(lm+rm));
843: if(di < dist)
844: {
845: best = p;
846: dist = di;
847: }
848: }
849: else if(c < cross)
850: {
851: cross = c;
852: best = p;
853: dist = iabs(2*p - (lm+rm));
854: }
855: }
856: }
857: if(best == iv)
858: continue;
859:
860: // move v to its best place
861: d = best < iv ? -1 : 1;
862: for(register int p = iv; p != best; p += d)
863: {
864: rank[p] = rank[p+d];
865: Invert[rank[p]] = p;
866: }
867: rank[p] = v;
868: Invert[v] = p;
869:
870: }
871: }
872: }
873:
874: // make node orderings for a connected component
875: static int buildrank(int **target, int **tryout, int component)
876: {
877: // build order using downward depth-first search
878: int start_target, start_tryout, bestcross, curcross;
879: initrank(target,component,1);
880: inversion(target);
881: start_target = bestcross = cross_stat(target);
882: start_tryout = 0;
883:
884: if(bestcross > 0)
885: {
886: #ifndef NOTRANSPOSE
887: transpose(target,0);
888: bestcross = 0;
889: for(int i = 0; i < Maxlevel; ++i)
890: bestcross += Cross[i];
891: #endif
892: }
893:
894: // rebuild order using upward depth-first search
895: if(bestcross > 0)
896: {
897: initrank(tryout,component,0);
898: inversion(tryout);
899: start_tryout = curcross = cross_stat(tryout);
900:
901: if(curcross > 0)
902: {
903: #ifndef NOTRANSPOSE
904: transpose(tryout,0);
905: curcross = 0;
906: for(int i = 0; i < Maxlevel; ++i)
907: curcross += Cross[i];
908: #endif
909: }
910: if(curcross == 0)
911: {
912: copyrank(tryout,target);
913: bestcross = curcross;
914: }
915: }
916:
917: // iterations to improve crossing
918: if(bestcross > 0)
919: bestcross = mincross(target,Maxint);
920: if(bestcross > 0 && (curcross = mincross(tryout,bestcross)) < bestcross)
921: copyrank(tryout,target);
922:
923: // fix dangling stems
924: if(N_flat_edges <= 0)
925: {
926: inversion(target);
927: fixstem(target,Count);
928: }
929:
930: return max(start_target,start_tryout);
931: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.