2.9BSD - /usr/src/cmd/tsort.c

   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: */
  13: 
  14: struct nodelist {
  15:     struct nodelist *nextnode;
  16:     struct predlist *inedges;
  17:     char *name;
  18:     enum {DEAD, LIVE, ONCE, TWICE} live;
  19: } firstnode = {NULL, NULL, NULL, DEAD};
  20: 
  21: /*	a predecessor list tells all the immediate
  22:  *	predecessors of a given node
  23: */
  24: struct predlist {
  25:     struct predlist *nextpred;
  26:     struct nodelist *pred;
  27: };
  28: 
  29: struct nodelist *index();
  30: struct nodelist *findloop();
  31: struct nodelist *mark();
  32: char *malloc();
  33: char *empty = "";
  34: 
  35: /*	the first for loop reads in the graph,
  36:  *	the second prints out the ordering
  37: */
  38: main(argc,argv)
  39: char **argv;
  40: {
  41:     register struct predlist *t;
  42:     FILE *input = stdin;
  43:     register struct nodelist *i, *j;
  44:     int x;
  45:     char precedes[50], follows[50];
  46:     if(argc>1) {
  47:         input = fopen(argv[1],"r");
  48:         if(input==NULL)
  49:             error("cannot open ", argv[1]);
  50:     }
  51:     for(;;) {
  52:         x = fscanf(input,"%s%s",precedes, follows);
  53:         if(x==EOF)
  54:             break;
  55:         if(x!=2)
  56:             error("odd data",empty);
  57:         i = index(precedes);
  58:         j = index(follows);
  59:         if(i==j||present(i,j))
  60:             continue;
  61:         t = (struct predlist *)malloc(sizeof(struct predlist));
  62:         t->nextpred = j->inedges;
  63:         t->pred = i;
  64:         j->inedges = t;
  65:     }
  66:     for(;;) {
  67:         x = 0;  /*anything LIVE on this sweep?*/
  68:         for(i= &firstnode; i->nextnode!=NULL; i=i->nextnode) {
  69:             if(i->live==LIVE) {
  70:                 x = 1;
  71:                 if(!anypred(i))
  72:                     break;
  73:             }
  74:         }
  75:         if(x==0)
  76:             break;
  77:         if(i->nextnode==NULL)
  78:             i = findloop();
  79:         printf("%s\n",i->name);
  80:         i->live = DEAD;
  81:     }
  82: }
  83: 
  84: /*	is i present on j's predecessor list?
  85: */
  86: present(i,j)
  87: struct nodelist *i, *j;
  88: {
  89:     register struct predlist *t;
  90:     for(t=j->inedges; t!=NULL; t=t->nextpred)
  91:         if(t->pred==i)
  92:             return(1);
  93:     return(0);
  94: }
  95: 
  96: /*	is there any live predecessor for i?
  97: */
  98: anypred(i)
  99: struct nodelist *i;
 100: {
 101:     register struct predlist *t;
 102:     for(t=i->inedges; t!=NULL; t=t->nextpred)
 103:         if(t->pred->live==LIVE)
 104:             return(1);
 105:     return(0);
 106: }
 107: 
 108: /*	turn a string into a node pointer
 109: */
 110: struct nodelist *
 111: index(s)
 112: register char *s;
 113: {
 114:     register struct nodelist *i;
 115:     register char *t;
 116:     for(i= &firstnode; i->nextnode!=NULL; i=i->nextnode)
 117:         if(cmp(s,i->name))
 118:             return(i);
 119:     for(t=s; *t; t++) ;
 120:     t = malloc((unsigned)(t+1-s));
 121:     i->nextnode = (struct nodelist *)malloc(sizeof(struct nodelist));
 122:     if(i->nextnode==NULL||t==NULL)
 123:         error("too many items",empty);
 124:     i->name = t;
 125:     i->live = LIVE;
 126:     i->nextnode->nextnode = NULL;
 127:     i->nextnode->inedges = NULL;
 128:     i->nextnode->live = DEAD;
 129:     while(*t++ = *s++);
 130:     return(i);
 131: }
 132: 
 133: cmp(s,t)
 134: register char *s, *t;
 135: {
 136:     while(*s==*t) {
 137:         if(*s==0)
 138:             return(1);
 139:         s++;
 140:         t++;
 141:     }
 142:     return(0);
 143: }
 144: 
 145: error(s,t)
 146: char *s, *t;
 147: {
 148:     note(s,t);
 149:     exit(1);
 150: }
 151: 
 152: note(s,t)
 153: char *s,*t;
 154: {
 155:     fprintf(stderr,"tsort: %s%s\n",s,t);
 156: }
 157: 
 158: /*	given that there is a cycle, find some
 159:  *	node in it
 160: */
 161: struct nodelist *
 162: findloop()
 163: {
 164:     register struct nodelist *i, *j;
 165:     register struct predlist *p;
 166:     for(i= &firstnode; i->nextnode!=NULL; i=i->nextnode)
 167:         if(i->live==LIVE)
 168:             break;
 169:     note("cycle in reverse order",empty);
 170:     while(i->live==LIVE) {
 171:         i->live = ONCE;
 172:         for(p=i->inedges; ; p=p->nextpred) {
 173:             if(p==NULL)
 174:                 error("error 1");
 175:             i = p->pred;
 176:             if(i->live!=DEAD)
 177:                 break;
 178:         }
 179:     }
 180:     while(i->live==ONCE) {
 181:         i->live = TWICE;
 182:         note(i->name,empty);
 183:         for(p=i->inedges; ; p=p->nextpred) {
 184:             if(p==NULL)
 185:                 error("error 2");
 186:             i = p->pred;
 187:             if(i->live!=DEAD)
 188:                 break;
 189:         }
 190:     }
 191:     for(j= &firstnode; j->nextnode!=NULL; j=j->nextnode)
 192:         if(j->live!=DEAD)
 193:             j->live = LIVE;
 194:     return(i);
 195: }

Defined functions

Defined variables

Defined struct's