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