![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to tsort.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 3BSD / cmd|
Return to tsort.c CVS log | Up to [CSRG BSD Unix] / 3BSD / cmd |
1.1 ! root 1: /* topological sort ! 2: * input is sequence of pairs of items (blank-free strings) ! 3: * nonidentical pair is a directed edge in graph ! 4: * identical pair merely indicates presence of node ! 5: * output is ordered list of items consistent with ! 6: * the partial ordering specified by the graph ! 7: */ ! 8: #include "stdio.h" ! 9: ! 10: /* the nodelist always has an empty element at the end to ! 11: * make it easy to grow in natural order ! 12: * states of the "live" field:*/ ! 13: #define DEAD 0 /* already printed*/ ! 14: #define LIVE 1 /* not yet printed*/ ! 15: #define VISITED 2 /*used only in findloop()*/ ! 16: ! 17: struct nodelist { ! 18: struct nodelist *nextnode; ! 19: struct predlist *inedges; ! 20: char *name; ! 21: int live; ! 22: } firstnode = {NULL, NULL, NULL, DEAD}; ! 23: ! 24: /* a predecessor list tells all the immediate ! 25: * predecessors of a given node ! 26: */ ! 27: struct predlist { ! 28: struct predlist *nextpred; ! 29: struct nodelist *pred; ! 30: }; ! 31: ! 32: struct nodelist *index(); ! 33: struct nodelist *findloop(); ! 34: struct nodelist *mark(); ! 35: char *malloc(); ! 36: char *empty = ""; ! 37: ! 38: /* the first for loop reads in the graph, ! 39: * the second prints out the ordering ! 40: */ ! 41: main(argc,argv) ! 42: char **argv; ! 43: { ! 44: register struct predlist *t; ! 45: FILE *input = stdin; ! 46: register struct nodelist *i, *j; ! 47: int x; ! 48: char precedes[50], follows[50]; ! 49: if(argc>1) { ! 50: input = fopen(argv[1],"r"); ! 51: if(input==NULL) ! 52: error("cannot open ", argv[1]); ! 53: } ! 54: for(;;) { ! 55: x = fscanf(input,"%s%s",precedes, follows); ! 56: if(x==EOF) ! 57: break; ! 58: if(x!=2) ! 59: error("odd data",empty); ! 60: i = index(precedes); ! 61: j = index(follows); ! 62: if(i==j||present(i,j)) ! 63: continue; ! 64: t = (struct predlist *)malloc(sizeof(struct predlist)); ! 65: t->nextpred = j->inedges; ! 66: t->pred = i; ! 67: j->inedges = t; ! 68: } ! 69: for(;;) { ! 70: x = 0; /*anything LIVE on this sweep?*/ ! 71: for(i= &firstnode; i->nextnode!=NULL; i=i->nextnode) { ! 72: if(i->live==LIVE) { ! 73: x = 1; ! 74: if(!anypred(i)) ! 75: break; ! 76: } ! 77: } ! 78: if(x==0) ! 79: break; ! 80: if(i->nextnode==NULL) ! 81: i = findloop(); ! 82: printf("%s\n",i->name); ! 83: i->live = DEAD; ! 84: } ! 85: } ! 86: ! 87: /* is i present on j's predecessor list? ! 88: */ ! 89: present(i,j) ! 90: struct nodelist *i, *j; ! 91: { ! 92: register struct predlist *t; ! 93: for(t=j->inedges; t!=NULL; t=t->nextpred) ! 94: if(t->pred==i) ! 95: return(1); ! 96: return(0); ! 97: } ! 98: ! 99: /* is there any live predecessor for i? ! 100: */ ! 101: anypred(i) ! 102: struct nodelist *i; ! 103: { ! 104: register struct predlist *t; ! 105: for(t=i->inedges; t!=NULL; t=t->nextpred) ! 106: if(t->pred->live==LIVE) ! 107: return(1); ! 108: return(0); ! 109: } ! 110: ! 111: /* turn a string into a node pointer ! 112: */ ! 113: struct nodelist * ! 114: index(s) ! 115: register char *s; ! 116: { ! 117: register struct nodelist *i; ! 118: register char *t; ! 119: for(i= &firstnode; i->nextnode!=NULL; i=i->nextnode) ! 120: if(cmp(s,i->name)) ! 121: return(i); ! 122: for(t=s; *t; t++) ; ! 123: t = malloc((unsigned)(t+1-s)); ! 124: i->nextnode = (struct nodelist *)malloc(sizeof(struct nodelist)); ! 125: if(i->nextnode==NULL||t==NULL) ! 126: error("too many items",empty); ! 127: i->name = t; ! 128: i->live = LIVE; ! 129: i->nextnode->nextnode = NULL; ! 130: i->nextnode->inedges = NULL; ! 131: i->nextnode->live = DEAD; ! 132: while(*t++ = *s++); ! 133: return(i); ! 134: } ! 135: ! 136: cmp(s,t) ! 137: register char *s, *t; ! 138: { ! 139: while(*s==*t) { ! 140: if(*s==0) ! 141: return(1); ! 142: s++; ! 143: t++; ! 144: } ! 145: return(0); ! 146: } ! 147: ! 148: error(s,t) ! 149: char *s, *t; ! 150: { ! 151: note(s,t); ! 152: exit(1); ! 153: } ! 154: ! 155: note(s,t) ! 156: char *s,*t; ! 157: { ! 158: fprintf(stderr,"tsort: %s%s\n",s,t); ! 159: } ! 160: ! 161: /* given that there is a cycle, find some ! 162: * node in it ! 163: */ ! 164: struct nodelist * ! 165: findloop() ! 166: { ! 167: register struct nodelist *i, *j; ! 168: for(i= &firstnode; i->nextnode!=NULL; i=i->nextnode) ! 169: if(i->live==LIVE) ! 170: break; ! 171: note("cycle in data",empty); ! 172: i = mark(i); ! 173: if(i==NULL) ! 174: error("program error",empty); ! 175: for(j= &firstnode; j->nextnode!=NULL; j=j->nextnode) ! 176: if(j->live==VISITED) ! 177: j->live = LIVE; ! 178: return(i); ! 179: } ! 180: ! 181: /* depth-first search of LIVE predecessors ! 182: * to find some element of a cycle; ! 183: * VISITED is a temporary state recording the ! 184: * visits of the search ! 185: */ ! 186: struct nodelist * ! 187: mark(i) ! 188: register struct nodelist *i; ! 189: { ! 190: register struct nodelist *j; ! 191: register struct predlist *t; ! 192: if(i->live==DEAD) ! 193: return(NULL); ! 194: if(i->live==VISITED) ! 195: return(i); ! 196: i->live = VISITED; ! 197: for(t=i->inedges; t!=NULL; t=t->nextpred) { ! 198: j = mark(t->pred); ! 199: if(j!=NULL) { ! 200: note(i->name,empty); ! 201: return(j); ! 202: } ! 203: } ! 204: return(NULL); ! 205: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.