static char *sccsid
= "@(#)tsort.c 4.2 (Berkeley) %G%";
* input is sequence of pairs of items (blank-free strings)
* nonidentical pair is a directed edge in graph
* identical pair merely indicates presence of node
* output is ordered list of items consistent with
* the partial ordering specified by the graph
/* the nodelist always has an empty element at the end to
* make it easy to grow in natural order
* states of the "live" field:*/
#define DEAD 0 /* already printed*/
#define LIVE 1 /* not yet printed*/
#define VISITED 2 /*used only in findloop()*/
struct nodelist
*nextnode
;
struct predlist
*inedges
;
} firstnode
= {NULL
, NULL
, NULL
, DEAD
};
/* a predecessor list tells all the immediate
* predecessors of a given node
struct predlist
*nextpred
;
struct nodelist
*index();
struct nodelist
*findloop();
/* the first for loop reads in the graph,
* the second prints out the ordering
register struct predlist
*t
;
register struct nodelist
*i
, *j
;
char precedes
[50], follows
[50];
input
= fopen(argv
[1],"r");
error("cannot open ", argv
[1]);
x
= fscanf(input
,"%s%s",precedes
, follows
);
t
= (struct predlist
*)malloc(sizeof(struct predlist
));
t
->nextpred
= j
->inedges
;
x
= 0; /*anything LIVE on this sweep?*/
for(i
= &firstnode
; i
->nextnode
!=NULL
; i
=i
->nextnode
) {
/* is i present on j's predecessor list?
register struct predlist
*t
;
for(t
=j
->inedges
; t
!=NULL
; t
=t
->nextpred
)
/* is there any live predecessor for i?
register struct predlist
*t
;
for(t
=i
->inedges
; t
!=NULL
; t
=t
->nextpred
)
/* turn a string into a node pointer
register struct nodelist
*i
;
for(i
= &firstnode
; i
->nextnode
!=NULL
; i
=i
->nextnode
)
t
= malloc((unsigned)(t
+1-s
));
i
->nextnode
= (struct nodelist
*)malloc(sizeof(struct nodelist
));
if(i
->nextnode
==NULL
||t
==NULL
)
error("too many items",empty
);
i
->nextnode
->nextnode
= NULL
;
i
->nextnode
->inedges
= NULL
;
i
->nextnode
->live
= DEAD
;
fprintf(stderr
,"tsort: %s%s\n",s
,t
);
/* given that there is a cycle, find some
register struct nodelist
*i
, *j
;
for(i
= &firstnode
; i
->nextnode
!=NULL
; i
=i
->nextnode
)
note("cycle in data",empty
);
error("program error",empty
);
for(j
= &firstnode
; j
->nextnode
!=NULL
; j
=j
->nextnode
)
/* depth-first search of LIVE predecessors
* to find some element of a cycle;
* VISITED is a temporary state recording the
register struct nodelist
*i
;
register struct nodelist
*j
;
register struct predlist
*t
;
for(t
=i
->inedges
; t
!=NULL
; t
=t
->nextpred
) {