![[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.