* Copyright (c) 1989 The Regents of the University of California.
* This code is derived from software contributed to Berkeley by
* Michael Rendell of Memorial University of Newfoundland.
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. All advertising materials mentioning features or use of this software
* must display the following acknowledgement:
* This product includes software developed by the University of
* California, Berkeley and its contributors.
* 4. Neither the name of the University nor the names of its contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
"@(#) Copyright (c) 1989 The Regents of the University of California.\n\
static char sccsid
[] = "@(#)tsort.c 5.3 (Berkeley) 6/1/90";
* Topological sort. Input is a list of pairs of strings seperated by
* white space (spaces, tabs, and/or newlines); strings are written to
* standard output in sorted order, one per line.
* If no input file is specified, standard input is read.
* Should be compatable with AT&T tsort HOWEVER the output is not identical
* (i.e. for most graphs there is more than one sorted order, and this tsort
* usually generates a different one then the AT&T tsort). Also, cycle
* reporting seems to be more accurate in this version (the AT&T tsort
* sometimes says a node is in a cycle when it isn't).
* Michael Rendell, michael@stretch.cs.mun.ca - Feb 26, '90
#define HASHSIZE 53 /* doesn't need to be big */
#define NF_MARK 0x1 /* marker for cycle detection */
#define NF_ACYCLIC 0x2 /* this node is cycle free */
typedef struct node_str NODE
;
char *n_name
; /* name of this node */
NODE
**n_prevp
; /* pointer to previous node's n_next */
NODE
*n_next
; /* next node in graph */
NODE
*n_hash
; /* next node in hash table */
int n_narcs
; /* number of arcs in n_arcs[] */
int n_arcsize
; /* size of n_arcs[] array */
NODE
**n_arcs
; /* array of arcs to other nodes */
int n_refcnt
; /* # of arcs pointing to this node */
NODE
*add_node(), *find_node();
void add_arc(), no_memory(), remove_node(), tsort();
char *grow_buf(), *malloc();
NODE
*hashtable
[HASHSIZE
];
(void)fprintf(stderr
, "usage: tsort [ inputfile ]\n");
} else if (!(fp
= fopen(argv
[1], "r"))) {
(void)fprintf(stderr
, "tsort: %s.\n", strerror(errno
));
for (b
= bufs
, n
= 2; --n
>= 0; b
++)
b
->b_buf
= grow_buf((char *)NULL
, b
->b_bsize
= 1024);
/* parse input and build the graph */
for (n
= 0, c
= getc(fp
);;) {
while (c
!= EOF
&& isspace(c
))
b
->b_buf
= grow_buf(b
->b_buf
, bsize
);
} while (c
!= EOF
&& !isspace(c
));
add_arc(bufs
[0].b_buf
, bufs
[1].b_buf
);
(void)fprintf(stderr
, "tsort: odd data count.\n");
/* double the size of oldbuf and return a pointer to the new buffer. */
if (!(bp
= realloc(bp
, (u_int
)size
)))
* add an arc from node s1 to node s2 in the graph. If s1 or s2 are not in
* the graph, then add them.
* could check to see if this arc is here already, but it isn't
* worth the bother -- there usually isn't and it doesn't hurt if
if (n1
->n_narcs
== n1
->n_arcsize
) {
bsize
= n1
->n_arcsize
* sizeof(*n1
->n_arcs
) * 2;
n1
->n_arcs
= (NODE
**)grow_buf((char *)n1
->n_arcs
, bsize
);
n1
->n_arcsize
= bsize
/ sizeof(*n1
->n_arcs
);
n1
->n_arcs
[n1
->n_narcs
++] = n2
;
for (hash
= 0, i
= 1; *s
; s
++, i
++)
* find a node in the graph and return a pointer to it - returns null if not
for (n
= hashtable
[hash_string(name
)]; n
; n
= n
->n_hash
)
if (!strcmp(n
->n_name
, name
))
/* Add a node to the graph and return a pointer to it. */
if (!(n
= (NODE
*)malloc(sizeof(NODE
))) || !(n
->n_name
= strdup(name
)))
n
->n_arcs
= (NODE
**)NULL
;
graph
->n_prevp
= &n
->n_next
;
hash
= hash_string(name
);
n
->n_hash
= hashtable
[hash
];
/* do topological sort on graph */
* keep getting rid of simple cases until there are none left,
* if there are any nodes still in the graph, then there is
for (cnt
= 0, n
= graph
; n
; n
= next
) {
* allocate space for two cycle logs - one to be used
* as scratch space, the other to save the longest
for (cnt
= 0, n
= graph
; n
; n
= n
->n_next
)
(NODE
**)malloc((u_int
)sizeof(NODE
*) * cnt
);
(NODE
**)malloc((u_int
)sizeof(NODE
*) * cnt
);
if (!cycle_buf
|| !longest_cycle
)
for (n
= graph
; n
; n
= n
->n_next
)
if (!(n
->n_flags
& NF_ACYCLIC
)) {
if (cnt
= find_cycle(n
, n
, 0, 0)) {
"tsort: cycle in data.\n");
for (i
= 0; i
< cnt
; i
++)
"tsort: %s.\n", longest_cycle
[i
]->n_name
);
/* to avoid further checks */
"tsort: internal error -- could not find cycle.\n");
/* print node and remove from graph (does not actually free node) */
(void)printf("%s\n", n
->n_name
);
for (np
= n
->n_arcs
, i
= n
->n_narcs
; --i
>= 0; np
++)
n
->n_next
->n_prevp
= n
->n_prevp
;
/* look for the longest cycle from node from to node to. */
find_cycle(from
, to
, longest_len
, depth
)
* avoid infinite loops and ignore portions of the graph known
if (from
->n_flags
& (NF_MARK
|NF_ACYCLIC
))
for (np
= from
->n_arcs
, i
= from
->n_narcs
; --i
>= 0; np
++) {
if (depth
+ 1 > longest_len
) {
(void)memcpy((char *)longest_cycle
,
longest_len
* sizeof(NODE
*));
len
= find_cycle(*np
, to
, longest_len
, depth
+ 1);
from
->n_flags
&= ~NF_MARK
;
(void)fprintf(stderr
, "tsort: %s.\n", strerror(ENOMEM
));