4.3BSD - /usr/src/usr.bin/tsort.c

   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: }

Defined functions

Defined variables

Defined struct's

Defined macros