gnu1987/gnucmds/tsort.c

18-Jul-84 02:10:28-EDT,3724;000000000001
Received: from MIT-MC by MIT-OZ via Chaosnet; 18 Jul 84 02:10-EDT
Received: from ucbernie.ARPA by UCB-VAX.ARPA (4.28/4.31)
	id AA08177; Tue, 17 Jul 84 22:46:34 pdt
Received: by ucbernie.ARPA (4.28/4.30)
	id AA10610; Tue, 17 Jul 84 22:47:11 pdt
Date: Tue, 17 Jul 84 22:47:11 pdt
From: phr%ucbernie@Berkeley (Paul Rubin)
Message-Id: <8407180547.AA10610@ucbernie.ARPA>
To: rms@oz@mc
Subject: I should be able to get this to run faster sometime

#include <stdio.h>
#define MAXLEN 1000
#define HASHSIZE 10007		/* for now, MAX no. of distinct vertices */

/*
 * tsort - topological sort.  Linear time algorithm
 * suggested by Avi Wigderson.
 *		--phr, 16 July 1984
 */

struct node {
	char *name;
	int indegree;			/* number of predecessors */
	struct nodelist *successors;	/* successors in graph */
	struct node *next;
	struct node *back;
};

struct nodelist {
	struct node *id;
	struct nodelist *next;
};

typedef struct node NODE;
typedef struct nodelist NLIST;

NODE *graph = NULL;
int nnodes = 0;

main(argc, argv)
int argc;
char **argv;
{
	int n = 0;
	NODE *lookup();
	register NODE *p, *q;
	NLIST *t;
	FILE *ifile = stdin;
	char from[MAXLEN], to[MAXLEN];

	if (argc > 1 && (ifile = fopen(argv[1], "r")) == NULL) {
		perror(argv[1]);
		exit(1);
	}

	while (fscanf(ifile, "%s %s", from, to) > 0) {
		p = lookup(from);
		q = lookup(to);
		if (p == q)
			continue;

		/* actually this scan might be taking more time than it saves */
		for (t = p->successors; t != NULL; t = t->next)
			if (t->id == q)
				break;

		if (t == NULL) {		/* q not already on successor list */
			t = (NLIST *) malloc(sizeof (NLIST));
			t->id = q;
			t->next = p->successors;
			p->successors = t;
			++q->indegree;
		}
	} /* each node now has a correct predecessor count and
	    	successor list. */

	if (nnodes == 0)
		exit(0);

	/* next, move all the root nodes to the head of the list */
	for (p = graph; p != NULL; p = p->next) {
		q = p->next;
		if (q == NULL)
			break;
		if (q->indegree == 0) {
			p->next = q->next;
			q->next = graph;
			graph = q;
		}
	}

	/* now turn the list into a doubly linked list */
	for (p = graph; p->next != NULL; p = p->next)
		p->next->back = p;
	graph->back = NULL;

	/* output */
	for (p = graph; p != NULL; nnodes--) {
		if (p->indegree != 0) {
			fprintf(stderr, "tsort: graph is circular\n");
			exit (1);
		}
		printf("%s\n", p->name);
		t = p->successors;
		p = p->next;
		for (; t != NULL; t = t->next) {
			q = t->id;
			if (--q->indegree == 0) {
				/* move new root to head of list.  q->back->next will not
					  be null because q had indegree > 0. */
				if (q == p)		/* it's already at head */
					continue;
				q->back->next = q->next;
				if (q->next != NULL)
					q->next->back = q->back;
				q->next = p;
				p->back = q;
				p = q;
				p->back = NULL;
			}
		}
	}

	if (n != 0) {
		fprintf(stderr, "tsort: graph has cycles\n");
		exit (1);
	}
	exit (0);
}

NODE *lookup(name)
char *name;
{
	char *newstring();
	static NODE *hashtab[HASHSIZE];
	register NODE *p;
	register int i;

	for (i = hashf(name); hashtab[i] != NULL; i = (i+1)%HASHSIZE)
		if (strcmp(hashtab[i]->name, name) == 0)
			return hashtab[i];

	p = hashtab[i] = (NODE *) calloc(1, sizeof (NODE));
	p->name = newstring(name);
	p->next = graph;
	graph = p;
	nnodes++;
	return p;
}

static int hashf(s)
register char *s;
{
	register int r = 0;

	while (*s)
		r = (r << 1) + *s++;

	r &= ~0x80000000;	/* make r nonnegative */

	return r % HASHSIZE;
}


char *newstring(s)
char *s;
{
	char *p = (char *) malloc(strlen(s) + 1);
	strcpy(p, s);
	return p;
}