source: trunk/minix/commands/simple/tsort.c@ 10

Last change on this file since 10 was 9, checked in by Mattia Monga, 13 years ago

Minix 3.1.2a

File size: 8.1 KB
Line 
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
16typedef 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
26typedef 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*/
48void *
49xmalloc(siz)
50size_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*/
63edge *
64new_edge(v)
65vertex *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*/
75char *
76copyupto(name,buf,stop)
77char *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*/
90int
91child_of(parent,child)
92vertex *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*/
105vertex *vset = NULL;
106
107vertex *
108add_v(s)
109char *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*/
147void
148readin()
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*/
175struct name { struct name *next; char *s; }
176*namelist = NULL;
177
178void
179pushname(s)
180char *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
188char *
189popname() {
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*/
204void 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*/
263void
264print_cycle(parent,child)
265vertex *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*/
298void
299dfs(v)
300vertex *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*/
329void
330check_cycles()
331{
332 vertex *v;
333 for(v = vset; v != NULL; v = v->next)
334 dfs(v);
335}
336
337/*
338** main program.
339*/
340int main(argc,argv)
341int argc;
342char **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}
Note: See TracBrowser for help on using the repository browser.