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