rommel@Informatik.TU-Muenchen.DE (Kai-Uwe Rommel) (06/04/91)
After complaining about tsort, here is a working one.
It is the BSD tsort which is small enough to work under Minix-PC.
I had to add a strdup() function missing in the Minix C library
and a typedef for u_int. Also there was a bug in this tsort (yeah, in
BSD code!). The ninth line in main() was originally:
else if (argc == 2) {
instead of:
else if (argc > 2) {
which is correct. This made tsort not accepting an optional input file.
The ordering in the output of this tsort is different from that of the
standard tsort but seems to be ok.
Kai Uwe Rommel
/* Kai Uwe Rommel, Munich ----- rommel@lan.informatik.tu-muenchen.dbp.de */
DOS ... is still a real mode only non-reentrant interrupt
handler, and always will be. -Russell Williams
echo x - strdup.c
sed '/^X/s///' > strdup.c << '/'
X#include <stdlib.h>
X#include <stdio.h>
X
Xchar *strdup(str)
Xchar *str;
X{
X char *ptr = (char *) malloc(strlen(str) + 1);
X
X if ( ptr == NULL )
X return NULL;
X
X strcpy(ptr, str);
X return ptr;
X}
/
echo x - tsort.c
sed '/^X/s///' > tsort.c << '/'
X/*
X * Copyright (c) 1989 The Regents of the University of California.
X * All rights reserved.
X *
X * This code is derived from software contributed to Berkeley by
X * Michael Rendell of Memorial University of Newfoundland.
X *
X * Redistribution and use in source and binary forms are permitted provided
X * that: (1) source distributions retain this entire copyright notice and
X * comment, and (2) distributions including binaries display the following
X * acknowledgement: ``This product includes software developed by the
X * University of California, Berkeley and its contributors'' in the
X * documentation or other materials provided with the distribution and in
X * all advertising materials mentioning features or use of this software.
X * Neither the name of the University nor the names of its contributors may
X * be used to endorse or promote products derived from this software without
X * specific prior written permission.
X * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
X * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
X * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
X */
X
X#ifndef lint
Xchar copyright[] =
X"@(#) Copyright (c) 1989 The Regents of the University of California.\n\
X All rights reserved.\n";
X#endif /* not lint */
X
X#ifndef lint
Xstatic char sccsid[] = "@(#)tsort.c 5.3 (Berkeley) 6/1/90";
X#endif /* not lint */
X
X#include <sys/types.h>
X#include <errno.h>
X#include <stdio.h>
X#include <ctype.h>
X#include <string.h>
X
X#ifdef _MINIX
Xtypedef unsigned int u_int;
Xextern char *strdup();
X#endif
X
X/*
X * Topological sort. Input is a list of pairs of strings seperated by
X * white space (spaces, tabs, and/or newlines); strings are written to
X * standard output in sorted order, one per line.
X *
X * usage:
X * tsort [inputfile]
X * If no input file is specified, standard input is read.
X *
X * Should be compatable with AT&T tsort HOWEVER the output is not identical
X * (i.e. for most graphs there is more than one sorted order, and this tsort
X * usually generates a different one then the AT&T tsort). Also, cycle
X * reporting seems to be more accurate in this version (the AT&T tsort
X * sometimes says a node is in a cycle when it isn't).
X *
X * Michael Rendell, michael@stretch.cs.mun.ca - Feb 26, '90
X */
X#define HASHSIZE 53 /* doesn't need to be big */
X#define NF_MARK 0x1 /* marker for cycle detection */
X#define NF_ACYCLIC 0x2 /* this node is cycle free */
X
Xtypedef struct node_str NODE;
X
Xstruct node_str {
X char *n_name; /* name of this node */
X NODE **n_prevp; /* pointer to previous node's n_next */
X NODE *n_next; /* next node in graph */
X NODE *n_hash; /* next node in hash table */
X int n_narcs; /* number of arcs in n_arcs[] */
X int n_arcsize; /* size of n_arcs[] array */
X NODE **n_arcs; /* array of arcs to other nodes */
X int n_refcnt; /* # of arcs pointing to this node */
X int n_flags; /* NF_* */
X};
X
Xtypedef struct _buf {
X char *b_buf;
X int b_bsize;
X} BUF;
X
XNODE *add_node(), *find_node();
Xvoid add_arc(), no_memory(), remove_node(), tsort();
Xchar *grow_buf(), *malloc();
X
Xextern int errno;
XNODE *graph;
XNODE *hashtable[HASHSIZE];
XNODE **cycle_buf;
XNODE **longest_cycle;
X
Xmain(argc, argv)
X int argc;
X char **argv;
X{
X register BUF *b;
X register int c, n;
X FILE *fp;
X int bsize, nused;
X BUF bufs[2];
X
X if (argc < 2)
X fp = stdin;
X else if (argc > 2) {
X (void)fprintf(stderr, "usage: tsort [ inputfile ]\n");
X exit(1);
X } else if (!(fp = fopen(argv[1], "r"))) {
X (void)fprintf(stderr, "tsort: %s.\n", strerror(errno));
X exit(1);
X }
X
X for (b = bufs, n = 2; --n >= 0; b++)
X b->b_buf = grow_buf((char *)NULL, b->b_bsize = 1024);
X
X /* parse input and build the graph */
X for (n = 0, c = getc(fp);;) {
X while (c != EOF && isspace(c))
X c = getc(fp);
X if (c == EOF)
X break;
X
X nused = 0;
X b = &bufs[n];
X bsize = b->b_bsize;
X do {
X b->b_buf[nused++] = c;
X if (nused == bsize) {
X bsize *= 2;
X b->b_buf = grow_buf(b->b_buf, bsize);
X }
X c = getc(fp);
X } while (c != EOF && !isspace(c));
X
X b->b_buf[nused] = '\0';
X b->b_bsize = bsize;
X if (n)
X add_arc(bufs[0].b_buf, bufs[1].b_buf);
X n = !n;
X }
X (void)fclose(fp);
X if (n) {
X (void)fprintf(stderr, "tsort: odd data count.\n");
X exit(1);
X }
X
X /* do the sort */
X tsort();
X exit(0);
X}
X
X/* double the size of oldbuf and return a pointer to the new buffer. */
Xchar *
Xgrow_buf(bp, size)
X char *bp;
X int size;
X{
X char *realloc();
X if ( !bp )
X bp = malloc((u_int)size);
X else
X bp = realloc(bp, (u_int)size);
X if (!bp)
X no_memory();
X return(bp);
X}
X
X/*
X * add an arc from node s1 to node s2 in the graph. If s1 or s2 are not in
X * the graph, then add them.
X */
Xvoid
Xadd_arc(s1, s2)
X char *s1, *s2;
X{
X register NODE *n1;
X NODE *n2;
X int bsize;
X
X n1 = find_node(s1);
X if (!n1)
X n1 = add_node(s1);
X
X if (!strcmp(s1, s2))
X return;
X
X n2 = find_node(s2);
X if (!n2)
X n2 = add_node(s2);
X
X /*
X * could check to see if this arc is here already, but it isn't
X * worth the bother -- there usually isn't and it doesn't hurt if
X * there is (I think :-).
X */
X if (n1->n_narcs == n1->n_arcsize) {
X if (!n1->n_arcsize)
X n1->n_arcsize = 10;
X bsize = n1->n_arcsize * sizeof(*n1->n_arcs) * 2;
X n1->n_arcs = (NODE **)grow_buf((char *)n1->n_arcs, bsize);
X n1->n_arcsize = bsize / sizeof(*n1->n_arcs);
X }
X n1->n_arcs[n1->n_narcs++] = n2;
X ++n2->n_refcnt;
X}
X
Xhash_string(s)
X char *s;
X{
X register int hash, i;
X
X for (hash = 0, i = 1; *s; s++, i++)
X hash += *s * i;
X return(hash % HASHSIZE);
X}
X
X/*
X * find a node in the graph and return a pointer to it - returns null if not
X * found.
X */
XNODE *
Xfind_node(name)
X char *name;
X{
X register NODE *n;
X
X for (n = hashtable[hash_string(name)]; n; n = n->n_hash)
X if (!strcmp(n->n_name, name))
X return(n);
X return((NODE *)NULL);
X}
X
X/* Add a node to the graph and return a pointer to it. */
XNODE *
Xadd_node(name)
X char *name;
X{
X register NODE *n;
X int hash;
X
X if (!(n = (NODE *)malloc(sizeof(NODE))) || !(n->n_name = strdup(name)))
X no_memory();
X
X n->n_narcs = 0;
X n->n_arcsize = 0;
X n->n_arcs = (NODE **)NULL;
X n->n_refcnt = 0;
X n->n_flags = 0;
X
X /* add to linked list */
X if (n->n_next = graph)
X graph->n_prevp = &n->n_next;
X n->n_prevp = &graph;
X graph = n;
X
X /* add to hash table */
X hash = hash_string(name);
X n->n_hash = hashtable[hash];
X hashtable[hash] = n;
X return(n);
X}
X
X/* do topological sort on graph */
Xvoid
Xtsort()
X{
X register NODE *n, *next;
X register int cnt;
X
X while (graph) {
X /*
X * keep getting rid of simple cases until there are none left,
X * if there are any nodes still in the graph, then there is
X * a cycle in it.
X */
X do {
X for (cnt = 0, n = graph; n; n = next) {
X next = n->n_next;
X if (n->n_refcnt == 0) {
X remove_node(n);
X ++cnt;
X }
X }
X } while (graph && cnt);
X
X if (!graph)
X break;
X
X if (!cycle_buf) {
X /*
X * allocate space for two cycle logs - one to be used
X * as scratch space, the other to save the longest
X * cycle.
X */
X for (cnt = 0, n = graph; n; n = n->n_next)
X ++cnt;
X cycle_buf =
X (NODE **)malloc((u_int)sizeof(NODE *) * cnt);
X longest_cycle =
X (NODE **)malloc((u_int)sizeof(NODE *) * cnt);
X if (!cycle_buf || !longest_cycle)
X no_memory();
X }
X for (n = graph; n; n = n->n_next)
X if (!(n->n_flags & NF_ACYCLIC)) {
X if (cnt = find_cycle(n, n, 0, 0)) {
X register int i;
X
X (void)fprintf(stderr,
X "tsort: cycle in data.\n");
X for (i = 0; i < cnt; i++)
X (void)fprintf(stderr,
X "tsort: %s.\n", longest_cycle[i]->n_name);
X remove_node(n);
X break;
X } else
X /* to avoid further checks */
X n->n_flags = NF_ACYCLIC;
X }
X
X if (!n) {
X (void)fprintf(stderr,
X "tsort: internal error -- could not find cycle.\n");
X exit(1);
X }
X }
X}
X
X/* print node and remove from graph (does not actually free node) */
Xvoid
Xremove_node(n)
X register NODE *n;
X{
X register NODE **np;
X register int i;
X
X (void)printf("%s\n", n->n_name);
X for (np = n->n_arcs, i = n->n_narcs; --i >= 0; np++)
X --(*np)->n_refcnt;
X n->n_narcs = 0;
X *n->n_prevp = n->n_next;
X if (n->n_next)
X n->n_next->n_prevp = n->n_prevp;
X}
X
X/* look for the longest cycle from node from to node to. */
Xfind_cycle(from, to, longest_len, depth)
X NODE *from, *to;
X int depth, longest_len;
X{
X register NODE **np;
X register int i, len;
X
X /*
X * avoid infinite loops and ignore portions of the graph known
X * to be acyclic
X */
X if (from->n_flags & (NF_MARK|NF_ACYCLIC))
X return(0);
X from->n_flags = NF_MARK;
X
X for (np = from->n_arcs, i = from->n_narcs; --i >= 0; np++) {
X cycle_buf[depth] = *np;
X if (*np == to) {
X if (depth + 1 > longest_len) {
X longest_len = depth + 1;
X (void)memcpy((char *)longest_cycle,
X (char *)cycle_buf,
X longest_len * sizeof(NODE *));
X }
X } else {
X len = find_cycle(*np, to, longest_len, depth + 1);
X if (len > longest_len)
X longest_len = len;
X }
X }
X from->n_flags &= ~NF_MARK;
X return(longest_len);
X}
X
Xvoid
Xno_memory()
X{
X (void)fprintf(stderr, "tsort: %s.\n", strerror(ENOMEM));
X exit(1);
X}
/
echo x - tsort.man
sed '/^X/s///' > tsort.man << '/'
XNAME
X tsort - topological sort of a directed graph
X
XSYNOPSIS
X tsort [ file ]
X
XDESCRIPTION
X Tsort takes a list of pairs of node names representing
X directed arcs in a graph and prints the nodes in topological
X order on standard output. Input is taken from the named
X file, or from standard input if no file is given.
X
X Node names in the input are separated by white space and
X there must be an even number of nodes.
X
X Presence of a node in a graph can be represented by an arc
X from the node to itself. This is useful when a node is not
X connected to any other nodes.
X
X If the graph contains a cycle (and therefore cannot be prop-
X erly sorted), one of the arcs in the cycle is ignored and
X the sort continues. Cycles are reported on standard error.
/
------------
EOF