home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Trees / V7 / usr / src / cmd / tsort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1979-04-23  |  3.7 KB  |  197 lines
  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. }
  196.  
  197.