![[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] / 3BSD / cmd|
Return to tsort.c CVS log | Up to [CSRG BSD Unix] / 3BSD / cmd |
1.1 root 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: * states of the "live" field:*/
13: #define DEAD 0 /* already printed*/
14: #define LIVE 1 /* not yet printed*/
15: #define VISITED 2 /*used only in findloop()*/
16:
17: struct nodelist {
18: struct nodelist *nextnode;
19: struct predlist *inedges;
20: char *name;
21: int live;
22: } firstnode = {NULL, NULL, NULL, DEAD};
23:
24: /* a predecessor list tells all the immediate
25: * predecessors of a given node
26: */
27: struct predlist {
28: struct predlist *nextpred;
29: struct nodelist *pred;
30: };
31:
32: struct nodelist *index();
33: struct nodelist *findloop();
34: struct nodelist *mark();
35: char *malloc();
36: char *empty = "";
37:
38: /* the first for loop reads in the graph,
39: * the second prints out the ordering
40: */
41: main(argc,argv)
42: char **argv;
43: {
44: register struct predlist *t;
45: FILE *input = stdin;
46: register struct nodelist *i, *j;
47: int x;
48: char precedes[50], follows[50];
49: if(argc>1) {
50: input = fopen(argv[1],"r");
51: if(input==NULL)
52: error("cannot open ", argv[1]);
53: }
54: for(;;) {
55: x = fscanf(input,"%s%s",precedes, follows);
56: if(x==EOF)
57: break;
58: if(x!=2)
59: error("odd data",empty);
60: i = index(precedes);
61: j = index(follows);
62: if(i==j||present(i,j))
63: continue;
64: t = (struct predlist *)malloc(sizeof(struct predlist));
65: t->nextpred = j->inedges;
66: t->pred = i;
67: j->inedges = t;
68: }
69: for(;;) {
70: x = 0; /*anything LIVE on this sweep?*/
71: for(i= &firstnode; i->nextnode!=NULL; i=i->nextnode) {
72: if(i->live==LIVE) {
73: x = 1;
74: if(!anypred(i))
75: break;
76: }
77: }
78: if(x==0)
79: break;
80: if(i->nextnode==NULL)
81: i = findloop();
82: printf("%s\n",i->name);
83: i->live = DEAD;
84: }
85: }
86:
87: /* is i present on j's predecessor list?
88: */
89: present(i,j)
90: struct nodelist *i, *j;
91: {
92: register struct predlist *t;
93: for(t=j->inedges; t!=NULL; t=t->nextpred)
94: if(t->pred==i)
95: return(1);
96: return(0);
97: }
98:
99: /* is there any live predecessor for i?
100: */
101: anypred(i)
102: struct nodelist *i;
103: {
104: register struct predlist *t;
105: for(t=i->inedges; t!=NULL; t=t->nextpred)
106: if(t->pred->live==LIVE)
107: return(1);
108: return(0);
109: }
110:
111: /* turn a string into a node pointer
112: */
113: struct nodelist *
114: index(s)
115: register char *s;
116: {
117: register struct nodelist *i;
118: register char *t;
119: for(i= &firstnode; i->nextnode!=NULL; i=i->nextnode)
120: if(cmp(s,i->name))
121: return(i);
122: for(t=s; *t; t++) ;
123: t = malloc((unsigned)(t+1-s));
124: i->nextnode = (struct nodelist *)malloc(sizeof(struct nodelist));
125: if(i->nextnode==NULL||t==NULL)
126: error("too many items",empty);
127: i->name = t;
128: i->live = LIVE;
129: i->nextnode->nextnode = NULL;
130: i->nextnode->inedges = NULL;
131: i->nextnode->live = DEAD;
132: while(*t++ = *s++);
133: return(i);
134: }
135:
136: cmp(s,t)
137: register char *s, *t;
138: {
139: while(*s==*t) {
140: if(*s==0)
141: return(1);
142: s++;
143: t++;
144: }
145: return(0);
146: }
147:
148: error(s,t)
149: char *s, *t;
150: {
151: note(s,t);
152: exit(1);
153: }
154:
155: note(s,t)
156: char *s,*t;
157: {
158: fprintf(stderr,"tsort: %s%s\n",s,t);
159: }
160:
161: /* given that there is a cycle, find some
162: * node in it
163: */
164: struct nodelist *
165: findloop()
166: {
167: register struct nodelist *i, *j;
168: for(i= &firstnode; i->nextnode!=NULL; i=i->nextnode)
169: if(i->live==LIVE)
170: break;
171: note("cycle in data",empty);
172: i = mark(i);
173: if(i==NULL)
174: error("program error",empty);
175: for(j= &firstnode; j->nextnode!=NULL; j=j->nextnode)
176: if(j->live==VISITED)
177: j->live = LIVE;
178: return(i);
179: }
180:
181: /* depth-first search of LIVE predecessors
182: * to find some element of a cycle;
183: * VISITED is a temporary state recording the
184: * visits of the search
185: */
186: struct nodelist *
187: mark(i)
188: register struct nodelist *i;
189: {
190: register struct nodelist *j;
191: register struct predlist *t;
192: if(i->live==DEAD)
193: return(NULL);
194: if(i->live==VISITED)
195: return(i);
196: i->live = VISITED;
197: for(t=i->inedges; t!=NULL; t=t->nextpred) {
198: j = mark(t->pred);
199: if(j!=NULL) {
200: note(i->name,empty);
201: return(j);
202: }
203: }
204: return(NULL);
205: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.