![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to tsort.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDTahoe / usr.bin|
Return to tsort.c CVS log | Up to [CSRG BSD Unix] / 43BSDTahoe / usr.bin |
1.1 root 1: static char *sccsid = "@(#)tsort.c 4.3 (Berkeley) 9/14/87";
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: exit(0);
87: }
88:
89: /* is i present on j's predecessor list?
90: */
91: present(i,j)
92: struct nodelist *i, *j;
93: {
94: register struct predlist *t;
95: for(t=j->inedges; t!=NULL; t=t->nextpred)
96: if(t->pred==i)
97: return(1);
98: return(0);
99: }
100:
101: /* is there any live predecessor for i?
102: */
103: anypred(i)
104: struct nodelist *i;
105: {
106: register struct predlist *t;
107: for(t=i->inedges; t!=NULL; t=t->nextpred)
108: if(t->pred->live==LIVE)
109: return(1);
110: return(0);
111: }
112:
113: /* turn a string into a node pointer
114: */
115: struct nodelist *
116: index(s)
117: register char *s;
118: {
119: register struct nodelist *i;
120: register char *t;
121: for(i= &firstnode; i->nextnode!=NULL; i=i->nextnode)
122: if(cmp(s,i->name))
123: return(i);
124: for(t=s; *t; t++) ;
125: t = malloc((unsigned)(t+1-s));
126: i->nextnode = (struct nodelist *)malloc(sizeof(struct nodelist));
127: if(i->nextnode==NULL||t==NULL)
128: error("too many items",empty);
129: i->name = t;
130: i->live = LIVE;
131: i->nextnode->nextnode = NULL;
132: i->nextnode->inedges = NULL;
133: i->nextnode->live = DEAD;
134: while(*t++ = *s++);
135: return(i);
136: }
137:
138: cmp(s,t)
139: register char *s, *t;
140: {
141: while(*s==*t) {
142: if(*s==0)
143: return(1);
144: s++;
145: t++;
146: }
147: return(0);
148: }
149:
150: error(s,t)
151: char *s, *t;
152: {
153: note(s,t);
154: exit(1);
155: }
156:
157: note(s,t)
158: char *s,*t;
159: {
160: fprintf(stderr,"tsort: %s%s\n",s,t);
161: }
162:
163: /* given that there is a cycle, find some
164: * node in it
165: */
166: struct nodelist *
167: findloop()
168: {
169: register struct nodelist *i, *j;
170: for(i= &firstnode; i->nextnode!=NULL; i=i->nextnode)
171: if(i->live==LIVE)
172: break;
173: note("cycle in data",empty);
174: i = mark(i);
175: if(i==NULL)
176: error("program error",empty);
177: for(j= &firstnode; j->nextnode!=NULL; j=j->nextnode)
178: if(j->live==VISITED)
179: j->live = LIVE;
180: return(i);
181: }
182:
183: /* depth-first search of LIVE predecessors
184: * to find some element of a cycle;
185: * VISITED is a temporary state recording the
186: * visits of the search
187: */
188: struct nodelist *
189: mark(i)
190: register struct nodelist *i;
191: {
192: register struct nodelist *j;
193: register struct predlist *t;
194: if(i->live==DEAD)
195: return(NULL);
196: if(i->live==VISITED)
197: return(i);
198: i->live = VISITED;
199: for(t=i->inedges; t!=NULL; t=t->nextpred) {
200: j = mark(t->pred);
201: if(j!=NULL) {
202: note(i->name,empty);
203: return(j);
204: }
205: }
206: return(NULL);
207: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.