![[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] / researchv10dc / cmd / dag|
Return to dag_ranks.c CVS log | Up to [Research Unix] / researchv10dc / 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.