1 static char *sccsid = "@(#)tsort.c 4.2 (Berkeley) 10/20/82"; 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 } 87 88 /* is i present on j's predecessor list? 89 */ 90 present(i,j) 91 struct nodelist *i, *j; 92 { 93 register struct predlist *t; 94 for(t=j->inedges; t!=NULL; t=t->nextpred) 95 if(t->pred==i) 96 return(1); 97 return(0); 98 } 99 100 /* is there any live predecessor for i? 101 */ 102 anypred(i) 103 struct nodelist *i; 104 { 105 register struct predlist *t; 106 for(t=i->inedges; t!=NULL; t=t->nextpred) 107 if(t->pred->live==LIVE) 108 return(1); 109 return(0); 110 } 111 112 /* turn a string into a node pointer 113 */ 114 struct nodelist * 115 index(s) 116 register char *s; 117 { 118 register struct nodelist *i; 119 register char *t; 120 for(i= &firstnode; i->nextnode!=NULL; i=i->nextnode) 121 if(cmp(s,i->name)) 122 return(i); 123 for(t=s; *t; t++) ; 124 t = malloc((unsigned)(t+1-s)); 125 i->nextnode = (struct nodelist *)malloc(sizeof(struct nodelist)); 126 if(i->nextnode==NULL||t==NULL) 127 error("too many items",empty); 128 i->name = t; 129 i->live = LIVE; 130 i->nextnode->nextnode = NULL; 131 i->nextnode->inedges = NULL; 132 i->nextnode->live = DEAD; 133 while(*t++ = *s++); 134 return(i); 135 } 136 137 cmp(s,t) 138 register char *s, *t; 139 { 140 while(*s==*t) { 141 if(*s==0) 142 return(1); 143 s++; 144 t++; 145 } 146 return(0); 147 } 148 149 error(s,t) 150 char *s, *t; 151 { 152 note(s,t); 153 exit(1); 154 } 155 156 note(s,t) 157 char *s,*t; 158 { 159 fprintf(stderr,"tsort: %s%s\n",s,t); 160 } 161 162 /* given that there is a cycle, find some 163 * node in it 164 */ 165 struct nodelist * 166 findloop() 167 { 168 register struct nodelist *i, *j; 169 for(i= &firstnode; i->nextnode!=NULL; i=i->nextnode) 170 if(i->live==LIVE) 171 break; 172 note("cycle in data",empty); 173 i = mark(i); 174 if(i==NULL) 175 error("program error",empty); 176 for(j= &firstnode; j->nextnode!=NULL; j=j->nextnode) 177 if(j->live==VISITED) 178 j->live = LIVE; 179 return(i); 180 } 181 182 /* depth-first search of LIVE predecessors 183 * to find some element of a cycle; 184 * VISITED is a temporary state recording the 185 * visits of the search 186 */ 187 struct nodelist * 188 mark(i) 189 register struct nodelist *i; 190 { 191 register struct nodelist *j; 192 register struct predlist *t; 193 if(i->live==DEAD) 194 return(NULL); 195 if(i->live==VISITED) 196 return(i); 197 i->live = VISITED; 198 for(t=i->inedges; t!=NULL; t=t->nextpred) { 199 j = mark(t->pred); 200 if(j!=NULL) { 201 note(i->name,empty); 202 return(j); 203 } 204 } 205 return(NULL); 206 } 207