commands/simple/tsort.c

   1 /* topo - topological sort              Author: Kent Williams */
   2
   3 /*
   4 ** topo - perform a topological sort of the output of lorder.
   5 **
   6 ** Usage : topo [infile] [outfile]
   7 **
   8 ** Author: Kent Williams (williams@umaxc.weeg.uiowa.edu)
   9 */
  10
  11 #include <ctype.h>
  12 #include <stdlib.h>
  13 #include <string.h>
  14 #include <stdio.h>
  15
  16 typedef struct __v {
  17     struct __v *next;   /* link list node                   */
  18     int indegree,       /* number of edges into this vertex */
  19         visited,        /* depth-first search visited flag  */
  20         on_the_path,    /* used to find cycles              */
  21         has_a_cycle;    /* true if a cycle at this vertex   */
  22     struct __e *out;    /* outgoing edges from this vertex  */
  23     char key[1];        /* name of this vertex              */
  24 } vertex;
  25
  26 typedef struct __e {
  27     struct __e *next;   /* link list node                   */
  28     vertex *v;          /* vertex to which this edge goes   */
  29 } edge;
  30
  31 _PROTOTYPE(int main, (int argc, char **argv));
  32 _PROTOTYPE(void *xmalloc, (size_t siz));
  33 _PROTOTYPE(edge *new_edge, (vertex *v));
  34 _PROTOTYPE(char *copyupto, (char *name, char *buf, int stop));
  35 _PROTOTYPE(int child_of, (vertex *parent, vertex *child));
  36 _PROTOTYPE(vertex *add_v, (char *s));
  37 _PROTOTYPE(void readin, (void));
  38 _PROTOTYPE(void pushname, (char *s));
  39 _PROTOTYPE(char *popname, (void));
  40 _PROTOTYPE(void topo, (void));
  41 _PROTOTYPE(void print_cycle, (vertex *parent, vertex *child));
  42 _PROTOTYPE(void dfs, (vertex *v));
  43 _PROTOTYPE(void check_cycles, (void));
  44
  45 /*
  46 ** xmalloc -- standard do or die malloc front end.
  47 */
  48 void *
  49 xmalloc(siz)
  50 size_t siz;
  51 {
  52     void *rval = (void *)malloc(siz);
  53     if(rval == NULL) {
  54         fputs("Out of memory.\n",stderr);
  55         exit(1);
  56     }
  57     return rval;
  58 }
  59
  60 /*
  61 ** edge allocater.
  62 */
  63 edge *
  64 new_edge(v)
  65 vertex *v;
  66 {
  67     edge *rval;
  68     rval = (edge *)xmalloc(sizeof(edge));
  69     rval->v = v; return rval;
  70 }
  71
  72 /*
  73 ** copyupto - copy until you see the stop character.
  74 */
  75 char *
  76 copyupto(name,buf,stop)
  77 char *name,*buf,stop;
  78 {
  79     while(*buf != '\0' && *buf != stop)
  80         *name++ = *buf++;
  81     *name = '\0';
  82     while(*buf != '\0' && isspace(*buf))
  83         buf++;
  84     return buf;
  85 }
  86
  87 /*
  88 ** find out if the vertex child is a child of the vertex parent.
  89 */
  90 int
  91 child_of(parent,child)
  92 vertex *parent,*child;
  93 {
  94     edge *e;
  95     for(e = parent->out; e != NULL && e->v != child; e = e->next)
  96         ;
  97     return e == NULL ? 0 : 1;
  98 }
  99
 100 /*
 101 ** the vertex set.
 102 **
 103 ** add_v adds a vertex to the set if it's not already there.
 104 */
 105 vertex *vset = NULL;
 106
 107 vertex *
 108 add_v(s)
 109 char *s;
 110 {
 111     vertex *v,*last;
 112     /*
 113     ** go looking for this key in the vertex set.
 114     */
 115     for(last = v = vset; v != NULL && strcmp(v->key,s) != 0;
 116         last = v, v = v->next)
 117         ;
 118     if(v != NULL) {
 119         /*
 120         ** use the move-to-front heuristic to keep this from being
 121         ** an O(N^2) algorithm.
 122         */
 123         if(last != vset) {
 124             last->next = v->next;
 125             v->next = vset;
 126             vset = v;
 127         }
 128         return v;
 129     }
 130
 131     v = (vertex *)xmalloc(sizeof(vertex) + strlen(s));
 132
 133     v->out = NULL;
 134     strcpy(v->key,s);
 135     v->indegree =
 136     v->on_the_path =
 137     v->has_a_cycle =
 138     v->visited = 0;
 139     v->next = vset;
 140     vset = v;
 141     return v;
 142 }
 143
 144 /*
 145 ** readin -- read in the dependency pairs.
 146 */
 147 void
 148 readin()
 149 {
 150     static char buf[128];
 151     static char name[64];
 152     char *bp;
 153     vertex *child,*parent;
 154     edge *e;
 155     while(fgets(buf,sizeof(buf),stdin) != NULL) {
 156         bp = buf + strlen(buf);
 157         if (bp > buf && bp[-1] == '\n') *--bp = 0;
 158         bp = copyupto(name,buf,' ');
 159         child = add_v(name);
 160         parent = add_v(bp);
 161         if(child != parent && !child_of(parent,child)) {
 162             e = new_edge(child);
 163             e->next = parent->out;
 164             parent->out = e;
 165             child->indegree++;
 166         }
 167     }
 168 }
 169
 170 /*
 171 ** the topological sort produces names of modules in reverse of
 172 ** the order we want them in, so use a stack to hold the names
 173 ** until we get them all, then pop them off to print them.
 174 */
 175 struct name { struct name *next; char *s; }
 176 *namelist = NULL;
 177
 178 void
 179 pushname(s)
 180 char *s;
 181 {
 182     struct name *x = (struct name *)xmalloc(sizeof(struct name));
 183     x->s = s;
 184     x->next = namelist;
 185     namelist = x;
 186 }
 187
 188 char *
 189 popname() {
 190     char *rval;
 191     struct name *tmp;
 192     if(namelist == NULL)
 193         return NULL;
 194     tmp = namelist;
 195     rval = namelist->s;
 196     namelist = namelist->next;
 197     free(tmp);
 198     return rval;
 199 }
 200
 201 /*
 202 ** topo - do a topological sort of the dependency graph.
 203 */
 204 void topo() {
 205     vertex *x = vset,*n;
 206     edge *e;
 207     vertex *outq = NULL,*tmp;
 208 #define insq(x) ((x->next = outq),(outq = x))
 209 #define deq() ((tmp = outq),(outq = outq->next),tmp)
 210
 211     /*
 212     ** find all vertices that don't depend on any other vertices
 213     ** Since it breaks the "next" links to insert x into the queue,
 214     ** x->next is saved before insq, to resume the list traversal.
 215     */
 216     while (x != NULL) {
 217         n = x->next;
 218         if(x->indegree == 0) {
 219             insq(x);
 220             pushname(x->key);
 221         }
 222         x = n;
 223     }
 224
 225     /*
 226     ** for each vertex V with indegree of zero,
 227     **     for each edge E from vertex V
 228     **        subtract one from the indegree of the vertex V'
 229     **        pointed to by E.  If V' now has an indegree of zero,
 230     **        add it to the set of vertices with indegree zero, and
 231     **        push its name on the output stack.
 232     */
 233     while(outq != NULL) {
 234         x = deq();
 235         e = x->out;
 236         while(e != NULL) {
 237             if(--(e->v->indegree) == 0) {
 238                 insq(e->v);
 239                 pushname(e->v->key);
 240             }
 241             e = e->next;
 242         }
 243     }
 244
 245     /*
 246     ** print the vertex names in opposite of the order they were
 247     ** encountered.
 248     */
 249     while(namelist != NULL)
 250         puts(popname());
 251 }
 252
 253 /*
 254 ** print_cycle --
 255 ** A cycle has been detected between parent and child.
 256 ** Start with the child, and look at each of its edges for
 257 ** the parent.
 258 **
 259 ** We know a vertex is on the path from the child to the parent
 260 ** because the depth-first search sets on_the_path true for each
 261 ** vertex it visits.
 262 */
 263 void
 264 print_cycle(parent,child)
 265 vertex *parent, *child;
 266 {
 267     char *s;
 268     vertex *x;
 269     edge *e;
 270     for(x = child; x != parent; ) {
 271         pushname(x->key);
 272         for(e = x->out; e != NULL; e = e->next) {
 273             /*
 274             ** stop looking for the path at the first node found
 275             ** that's on the path.  Watch out for cycles already
 276             ** detected, because if you follow an edge into a cycle,
 277             ** you're stuck in an infinite loop!
 278             */
 279             if(e->v->on_the_path && !e->v->has_a_cycle) {
 280                 x = e->v;
 281                 break;
 282             }
 283         }
 284     }
 285     /*
 286     ** print the name of the parent, and then names of each of the
 287     ** vertices on the path from the child to the parent.
 288     */
 289     fprintf(stderr,"%s\n",x->key);
 290     while((s = popname()) != NULL)
 291         fprintf(stderr,"%s\n",s);
 292 }
 293
 294 /*
 295 ** depth first search for cycles in the dependency graph.
 296 ** See "Introduction to Algorithms" by Udi Manber Addison-Wesley 1989
 297 */
 298 void
 299 dfs(v)
 300 vertex *v;
 301 {
 302     edge *e;
 303
 304     if(v->visited)      /* If you've been here before, don't go again! */
 305         return;
 306     v->visited++;
 307     v->on_the_path++;   /* this node is on the path from the root. */
 308
 309     /*
 310     ** depth-first search all outgoing edges.
 311     */
 312     for(e = v->out; e != NULL; e = e->next) {
 313         if(!e->v->visited)
 314             dfs(e->v);
 315         if(e->v->on_the_path) {
 316             fprintf(stderr,"cycle found between %s and %s\n",
 317                 v->key,e->v->key);
 318             print_cycle(v,e->v);
 319             v->has_a_cycle++;
 320         }
 321     }
 322     v->on_the_path = 0;
 323 }
 324
 325 /*
 326 ** check cycles starts the recursive depth-first search from
 327 ** each vertex in vset.
 328 */
 329 void
 330 check_cycles()
 331 {
 332     vertex *v;
 333     for(v = vset; v != NULL; v = v->next)
 334         dfs(v);
 335 }
 336
 337 /*
 338 ** main program.
 339 */
 340 int main(argc,argv)
 341 int argc;
 342 char **argv;
 343 {
 344     if(argc > 1 && freopen(argv[1],"r",stdin) == NULL) {
 345         perror(argv[1]);
 346         exit(0);
 347     }
 348     if(argc > 2 && freopen(argv[2],"w",stdout) == NULL) {
 349         perror(argv[2]);
 350         exit(0);
 351     }
 352     readin();
 353     check_cycles();
 354     topo();
 355     return(0);
 356 }