Return to tsort.c CVS log

Up to [local] / src / usr.bin / tsort

Fix cycle detection.
Under some circumstances, trying to find a cycle starting with a given
point can be very time-consuming (probably exponential, as an
implementation of an NP-complete problem), so we lower our expectations,
and just report the first cycle we find, irregardless of which point it
cuts, which is guaranteed to be much faster (quadratic behavior at the
worst--because we won't explore more than a tree out of the graph).

Always find that cycle, even if -q is specified, so that -q is only
`quiet', e.g., does not change the reported result.

Based on a testcase reported by Dragos Ruiu,  okay millert@

/* $OpenBSD: tsort.c,v 1.10 2001/07/14 14:18:50 espie Exp $ */
/* ex:ts=8 sw=4: 
 */

/*
 * Copyright (c) 1999-2001 Marc Espie.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 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 Marc Espie for the OpenBSD
 * Project.
 *
 * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT 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 OPENBSD
 * PROJECT 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 SUCH DAMAGE.
 */

#include <sys/types.h>
#include <assert.h>
#include <ctype.h>
#include <err.h>
#include <limits.h>
#include <stddef.h>
#include <ohash.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sysexits.h>
#include <unistd.h>

/* The complexity of topological sorting is O(e), where e is the 
 * size of input.  While reading input, vertices have to be identified,
 * thus add the complexity of e keys retrieval among v keys using
 * an appropriate data structure.  This program uses open double hashing 
 * for that purpose.  See Knuth for the expected complexity of double 
 * hashing (Brent variation should probably be used if v << e, as a user
 * option).
 *
 * The algorithm used for longest cycle reporting is accurate, but somewhat
 * expensive.  It may need to build all free paths of the graph (a free
 * path is a path that never goes twice through the same node), whose
 * number can be as high as O(2^e).  Usually, the number of free paths is 
 * much smaller though.  This program's author does not believe that a
 * significantly better worst-case complexity algorithm exists.
 *
 * In case of a hints file, the set of minimal nodes is maintained as a
 * heap.  The resulting complexity is O(e+v log v) for the worst case.
 * The average should actually be near O(e).
 *
 * If the hints file is incomplete, there is some extra complexity incurred
 * by make_transparent, which does propagate order values to unmarked
 * nodes. In the worst case, make_transparent is  O(e u),
 * where u is the number of originally unmarked nodes.
 * In practice, it is much faster.
 *
 * The simple topological sort algorithm detects cycles.  This program
 * goes further, breaking cycles through the use of simple heuristics.  
 * Each cycle break checks the whole set of nodes, hence if c cycles break 
 * are needed, this is an extra cost of O(c v).
 *
 * Possible heuristics are as follows:
 * - break cycle at node with lowest number of predecessors (default case),
 * - break longest cycle at node with lowest number of predecessors,
 * - break cycle at next node from the hints file.
 *
 * Except for the hints file case, which sets an explicit constraint on
 * which cycle to break, those heuristics locally result in the smallest 
 * number of broken edges.
 *
 * Those are admittedly greedy strategies, as is the selection of the next
 * node from the hints file amongst equivalent candidates that is used for
 * `stable' topological sorting.
 */

#ifdef __GNUC__
#define UNUSED	__attribute__((unused))
#else
#define UNUSED
#endif

struct node;

/* The set of arcs from a given node is stored as a linked list.  */
struct link {
	struct link *next;
	struct node *node;
};

#define NO_ORDER	UINT_MAX

struct node {
	unsigned int refs;	/* Number of arcs left, coming into this node . 
				 * Note that nodes with a null count can't 
				 * be part of cycles.  */
	struct link  *arcs;	/* List of forward arcs.  */

	unsigned int order; 	/* Order of nodes according to a hint file.  */

	/* Cycle detection algorithms build a free path of nodes.  */
	struct node  *from; 	/* Previous node in the current path.  */

	unsigned int mark;	/* Mark processed nodes in cycle discovery.  */
	struct link  *traverse;	/* Next link to traverse when backtracking.  */
	char         k[1];	/* Name of this node.  */
};

#define HASH_START 9

struct array {
	unsigned int entries;
	struct node  **t;
};

static void nodes_init __P((struct ohash *));
static struct node *node_lookup __P((struct ohash *, const char *, const char *));
static void usage __P((void));
static struct node *new_node __P((const char *, const char *));

static unsigned int read_pairs __P((FILE *, struct ohash *, int, 
    const char *, unsigned int, int));
static void split_nodes __P((struct ohash *, struct array *, struct array *));
static void make_transparent __P((struct ohash *));
static void insert_arc __P((struct node *, struct node *));

#ifdef DEBUG
static void dump_node __P((struct node *));
static void dump_array __P((struct array *));
static void dump_hash __P((struct ohash *));
#endif
static unsigned int read_hints __P((FILE *, struct ohash *, int, 
    const char *, unsigned int));
static struct node *find_smallest_node __P((struct array *));
static struct node *find_good_cycle_break __P((struct array *));
static void print_cycle __P((struct array *));
static struct node *find_cycle_from __P((struct node *, struct array *));
static struct node *find_predecessor __P((struct array *, struct node *));
static unsigned int traverse_node __P((struct node *, unsigned int, struct array *));
static struct node *find_longest_cycle __P((struct array *, struct array *));

static void heap_down __P((struct array *, unsigned int));
static void heapify __P((struct array *, int));
static struct node *dequeue __P((struct array *));
static void enqueue __P((struct array *, struct node *));



#define erealloc(n, s)	emem(realloc(n, s))
static void *hash_alloc __P((size_t, void *));
static void hash_free __P((void *, size_t, void *));
static void* entry_alloc __P((size_t, void *));
static void *emalloc __P((size_t));
static void *emem __P((void *));
#define DEBUG_TRAVERSE 0
static struct ohash_info node_info = { 
	offsetof(struct node, k), NULL, hash_alloc, hash_free, entry_alloc };


int main __P((int, char *[]));


/***
 *** Memory handling. 
 ***/

static void *
emem(p)
	void 		*p;
{
	if (p)
		return p;
	else
		errx(EX_SOFTWARE, "Memory exhausted");
}

static void *
hash_alloc(s, u)
	size_t s;
	void *u		UNUSED;
{
	return emem(calloc(s, 1));
}

static void
hash_free(p, s, u)
	void *p;
	size_t s	UNUSED;
	void *u		UNUSED;
{
	free(p);
}

static void *
entry_alloc(s, u)
	size_t s;
	void *u		UNUSED;
{
	return emalloc(s);
}

static void *
emalloc(s)
	size_t s;
{
	return emem(malloc(s));
}


/*** 
 *** Hash table.
 ***/

/* Inserting and finding nodes in the hash structure.
 * We handle interval strings for efficiency wrt fgetln.  */
static struct node *
new_node(start, end)
	const char 	*start;
	const char 	*end;
{
	struct node 	*n;

	n = ohash_create_entry(&node_info, start, &end);
	n->from = NULL;
	n->arcs = NULL;
	n->refs = 0;
	n->mark = 0;
	n->order = NO_ORDER;
	n->traverse = NULL;
	return n;
}


static void 
nodes_init(h)
	struct ohash 	*h;
{
	ohash_init(h, HASH_START, &node_info);
}

static struct node *
node_lookup(h, start, end)
	struct ohash 	*h;
	const char 	*start;
	const char 	*end;
{
	unsigned int	i;
	struct node *	n;

	i = ohash_qlookupi(h, start, &end);

	n = ohash_find(h, i);
	if (n == NULL)
		n = ohash_insert(h, i, new_node(start, end));
	return n;
}
	
#ifdef DEBUG
static void
dump_node(n)
    struct node 	*n;
{
	struct link 	*l;

	if (n->refs == 0)
		return;
	printf("%s (%u/%u): ", n->k, n->order, n->refs);
	for (l = n->arcs; l != NULL; l = l->next)
		if (n->refs != 0)
		printf("%s(%u/%u) ", l->node->k, l->node->order, l->node->refs);
    	putchar('\n');
}

static void
dump_array(a)
	struct array	*a;
{
	unsigned int 	i;

	for (i = 0; i < a->entries; i++)
		dump_node(a->t[i]);
}
		
static void 
dump_hash(h)
	struct ohash 	*h;
{
	unsigned int 	i;
	struct node 	*n;

	for (n = ohash_first(h, &i); n != NULL; n = ohash_next(h, &i))
		dump_node(n);
}
#endif
		

/***
 *** Reading data.
 ***/

static void 
insert_arc(a, b)
	struct node 	*a, *b;
{
	struct link 	*l;

	/* Check that this arc is not already present.  */
	for (l = a->arcs; l != NULL; l = l->next) {
		if (l->node == b)
			return;
	}
	b->refs++;
	l = emalloc(sizeof(struct link));
	l->node = b;
	l->next = a->arcs;
	a->arcs = l;
}

static unsigned int
read_pairs(f, h, reverse, name, order, hint)
	FILE 		*f;
	struct ohash 	*h;
	int 		reverse;
	const char 	*name;
	unsigned int	order;
	int		hint;
{
	int 		toggle;
	struct node 	*a;
	size_t 		size;
	char 		*str;

	toggle = 1;
	a = NULL;
	
	while ((str = fgetln(f, &size)) != NULL) {
		char *sentinel;

		sentinel = str + size;
		for (;;) {
			char *e;

			while (isspace(*str) && str < sentinel) 
				str++;
			if (str == sentinel)
				break;
			for (e = str; !isspace(*e) && e < sentinel; e++)
				continue;
			if (toggle) {
				a = node_lookup(h, str, e);
				if (a->order == NO_ORDER && hint)
					a->order = order++;
			} else {
				struct node *b;

				b = node_lookup(h, str, e);
				assert(a != NULL);
				if (b != a) {
					if (reverse) 
						insert_arc(b, a);
					else 
						insert_arc(a, b);
				}
			}
			toggle = !toggle;
			str = e;
		}
	}
	if (toggle == 0)
		errx(EX_DATAERR, "odd number of pairs in %s", name);
    	if (!feof(f))
		err(EX_IOERR, "error reading %s", name);
	return order;
}

static unsigned int
read_hints(f, h, quiet, name, order)
	FILE 		*f;
	struct ohash 	*h;
	int 		quiet;
	const char 	*name;
	unsigned int	order;
{
	char 		*str;
	size_t 		size;

	while ((str = fgetln(f, &size)) != NULL) {
		char *sentinel;

		sentinel = str + size;
		for (;;) {
			char *e;
			struct node *a;

			while (isspace(*str) && str < sentinel) 
				str++;
			if (str == sentinel)
				break;
			for (e = str; !isspace(*e) && e < sentinel; e++)
				continue;
			a = node_lookup(h, str, e);
			if (a->order != NO_ORDER) {
				if (!quiet)
				    warnx(
					"duplicate node %s in hints file %s",
					a->k, name);
			} else
				a->order = order++;
			str = e;
		}
	}
	return order;
}


/***
 *** Standard heap handling routines.  
 ***/

static void 
heap_down(h, i)
	struct array 	*h;
	unsigned int 	i;
{
	unsigned int 	j;
	struct node 	*swap;

	for (; (j=2*i+1) < h->entries; i = j) {
		if (j+1 < h->entries && h->t[j+1]->order < h->t[j]->order)
		    	j++;
		if (h->t[i]->order <= h->t[j]->order)
			break;
		swap = h->t[i];
		h->t[i] = h->t[j];
		h->t[j] = swap;
	}
}

static void 
heapify(h, verbose)
	struct array 	*h;
	int		verbose;
{
	unsigned int 	i;

	for (i = h->entries; i != 0;) {
		if (h->t[--i]->order == NO_ORDER && verbose)
			warnx("node %s absent from hints file", h->t[i]->k);
		heap_down(h, i);
	}
}

#define DEQUEUE(h) ( hints_flag ? dequeue(h) : (h)->t[--(h)->entries] )

static struct node *
dequeue(h)
	struct array 	*h;
{
	struct node 	*n;

	if (h->entries == 0)
		n = NULL;
	else {
		n = h->t[0];
		if (--h->entries != 0) {
		    h->t[0] = h->t[h->entries];
		    heap_down(h, 0);
		}
	}
	return n;
}
	
#define ENQUEUE(h, n) do {			\
	if (hints_flag)				\
		enqueue((h), (n));		\
	else					\
		(h)->t[(h)->entries++] = (n);	\
	} while(0);

static void 
enqueue(h, n)
	struct array 	*h;
	struct node 	*n;
{
	unsigned int 	i, j;
	struct node 	*swap;

	h->t[h->entries++] = n;
	for (i = h->entries-1; i > 0; i = j) {
		j = (i-1)/2;
		if (h->t[j]->order < h->t[i]->order)
			break;
		swap = h->t[j];
		h->t[j] = h->t[i];
		h->t[i] = swap;
	}
}

/* Nodes without order should not hinder direct dependencies.
 * Iterate until no nodes are left. 
 */
static void
make_transparent(hash)
	struct ohash	*hash;
{
	struct node 	*n;
	unsigned int 	i;
	struct link 	*l;
	int		adjusted;
	int		bad;
	unsigned int	min;

	/* first try to solve complete nodes */
	do {
		adjusted = 0;
		bad = 0;
		for (n = ohash_first(hash, &i); n != NULL; 
		    n = ohash_next(hash, &i)) {
			if (n->order == NO_ORDER) {
				min = NO_ORDER;

				for (l = n->arcs; l != NULL; l = l->next) {
					/* unsolved node -> delay resolution */
					if (l->node->order == NO_ORDER) {
						bad = 1;
						break;
					} else if (l->node->order < min)
						min = l->node->order;
				}
				if (min < NO_ORDER && l == NULL) {
					n->order = min;
					adjusted = 1;
				}
			}
		}

	} while (adjusted);

	/* then, if incomplete nodes are left, do them */
	if (bad) do {
		adjusted = 0;
		for (n = ohash_first(hash, &i); n != NULL; 
		    n = ohash_next(hash, &i))
			if (n->order == NO_ORDER)
				for (l = n->arcs; l != NULL; l = l->next)
					if (l->node->order < n->order) {
						n->order = l->node->order;
						adjusted = 1;
					}
	} while (adjusted);
}


/***
 *** Search through hash array for nodes.
 ***/

/* Split nodes into unrefed nodes/live nodes.  */
static void
split_nodes(hash, heap, remaining)
	struct ohash 	*hash;
	struct array 	*heap;
	struct array	*remaining;
{

	struct node *n;
	unsigned int i;

	heap->t = emalloc(sizeof(struct node *) * ohash_entries(hash));
	remaining->t = emalloc(sizeof(struct node *) * ohash_entries(hash));
	heap->entries = 0;
	remaining->entries = 0;

	for (n = ohash_first(hash, &i); n != NULL; n = ohash_next(hash, &i)) {
		if (n->refs == 0) 
			heap->t[heap->entries++] = n;
		else
			remaining->t[remaining->entries++] = n;
	}
}

/* Good point to break a cycle: live node with as few refs as possible. */
static struct node *
find_good_cycle_break(h)
	struct array 	*h;
{
	unsigned int 	i;
	unsigned int 	best; 
	struct node 	*u; 

	best = UINT_MAX;
	u = NULL;

	assert(h->entries != 0);
	for (i = 0; i < h->entries; i++) {
		struct node *n = h->t[i];
		/* No need to look further. */		
		if (n->refs == 1)
			return n;
		if (n->refs != 0 && n->refs < best) {
			best = n->refs;
			u = n;
		}
	}
	assert(u != NULL);
	return u;
}
			
/*  Retrieve the node with the smallest order.  */
static struct node * 
find_smallest_node(h)
	struct array 	*h;
{
	unsigned int 	i;
	unsigned int 	best;
	struct node 	*u;

	best = UINT_MAX;
	u = NULL;

	assert(h->entries != 0);
	for (i = 0; i < h->entries; i++) {
		struct node *n = h->t[i];
		if (n->refs != 0 && n->order < best) {
			best = n->order;
			u = n;
		}
	}
	assert(u != NULL);
	return u;
}


/***
 *** Graph algorithms.
 ***/

/* Explore the nodes reachable from i to find a cycle, store it in c.  
 * This may fail.  */
static struct node * 
find_cycle_from(i, c)
	struct node 	*i;
	struct array 	*c;
{
	struct node 	*n;

	n = i;
	/* XXX Previous cycle findings may have left this pointer non-null.  */
	i->from = NULL;

	for (;;) {
		/* Note that all marks are reversed before this code exits.  */
		n->mark = 1;
		if (n->traverse) 
			n->traverse = n->traverse->next;
		else
			n->traverse = n->arcs;
		/* Skip over dead nodes.  */
		while (n->traverse && n->traverse->node->refs == 0)
			n->traverse = n->traverse->next;
		if (n->traverse) {
			struct node *go = n->traverse->node;

			if (go->mark) {
				c->entries = 0;
				for (; n != NULL && n != go; n = n->from) {
					c->t[c->entries++] = n;
					n->mark = 0;
				}
				for (; n != NULL; n = n->from)
					n->mark = 0;
				c->t[c->entries++] = go;
				return go;
			} else {
			    go->from = n;
			    n = go;
			}
		} else {
			n->mark = 0;
			n = n->from;
			if (n == NULL) 
				return NULL;
		}
	}
}

/* Find a live predecessor of node n.  This is a slow routine, as it needs
 * to go through the whole array, but it is not needed often.
 */
static struct node *
find_predecessor(a, n)
	struct array *a;
	struct node *n;
{
	unsigned int i;

	for (i = 0; i < a->entries; i++) {
		struct node *m;

		m = a->t[i];
		if (m->refs != 0) {
			struct link *l;

			for (l = m->arcs; l != NULL; l = l->next)
				if (l->node == n)
					return m;
		}
	}
	assert(1 == 0);
	return NULL;
}

/* Traverse all strongly connected components reachable from node n.
   Start numbering them at o. Return the maximum order reached.
   Update the largest cycle found so far.
 */
static unsigned int 
traverse_node(n, o, c)
	struct node 	*n;
	unsigned int 	o;
	struct array 	*c;
{
	unsigned int 	min, max;

	n->from = NULL;
	min = o;
	max = ++o;

	for (;;) {
		n->mark = o;
		if (DEBUG_TRAVERSE)
			printf("%s(%d) ", n->k, n->mark);
		/* Find next arc to explore.  */
		if (n->traverse) 
			n->traverse = n->traverse->next;
		else
			n->traverse = n->arcs;
		/* Skip over dead nodes.  */
		while (n->traverse && n->traverse->node->refs == 0)
			n->traverse = n->traverse->next;
		/* If arc left.  */
		if (n->traverse) {
			struct node 	*go;

			go = n->traverse->node;
			/* Optimisation: if go->mark < min, we already 
			 * visited this strongly-connected component in
			 * a previous pass.  Hence, this can yield no new
			 * cycle.  */

			/* Not part of the current path: go for it.  */
			if (go->mark == 0 || go->mark == min) {
				go->from = n;
				n = go;
				o++;
				if (o > max)
					max = o;
			/* Part of the current path: check cycle length.  */
			} else if (go->mark > min) {
				if (DEBUG_TRAVERSE)
					printf("%d\n", o - go->mark + 1);
				if (o - go->mark + 1 > c->entries) {
					struct node *t;
					unsigned int i;

					c->entries = o - go->mark + 1;
					i = 0;
					c->t[i++] = go;
					for (t = n; t != go; t = t->from)
						c->t[i++] = t;
				}
			}

		/* No arc left: backtrack.  */
		} else {
			n->mark = min;
			n = n->from;
			if (!n)
				return max;
			o--;	
		}
	}
}

static void
print_cycle(c)
	struct array 	*c;
{
	unsigned int 	i;

	/* Printing in reverse order, since cycle discoveries finds reverse
	 * edges.  */
	for (i = c->entries; i != 0;) {
		i--;
		warnx("%s", c->t[i]->k);
	}
}

static struct node *
find_longest_cycle(h, c)
	struct array 	*h;
	struct array 	*c;
{
	unsigned int 	i;
	unsigned int 	o;
	unsigned int 	best;
	struct node 	*n;
	static int 	notfirst = 0;

	assert(h->entries != 0);

	/* No cycle found yet.  */
	c->entries = 0;

	/* Reset the set of marks, except the first time around.  */
	if (notfirst) {
		for (i = 0; i < h->entries; i++) 
			h->t[i]->mark = 0;
	} else
		notfirst = 1;

	o = 0;

	/* Traverse the array.  Each unmarked, live node heralds a
	 * new set of strongly connected components.  */
	for (i = 0; i < h->entries; i++) {
		n = h->t[i];
		if (n->refs != 0 && n->mark == 0) {
			/* Each call to traverse_node uses a separate
			 * interval of numbers to mark nodes.  */
			o++;
			o = traverse_node(n, o, c);
		}
	}
	
	assert(c->entries != 0);
	n = c->t[0];
	best = n->refs;
	for (i = 0; i < c->entries; i++) {
		if (c->t[i]->refs < best) {
			n = c->t[i];
			best = n->refs;
		}
	}
	return n;
}


#define plural(n) ((n) > 1 ? "s" : "")

int 
main(argc, argv)
    int 		argc;
    char 		*argv[];
{
	struct ohash 	pairs;
	int 		reverse_flag, quiet_flag, long_flag, 
			    warn_flag, hints_flag, verbose_flag;
	unsigned int	order;

	order = 0;

	reverse_flag = quiet_flag = long_flag = 
		warn_flag = hints_flag = verbose_flag = 0;
	nodes_init(&pairs);

	{
	    int c;

	    while ((c = getopt(argc, argv, "h:flqrvw")) != -1) {
		    switch(c) {
		    case 'h': {
			    FILE *f;

			    f = fopen(optarg, "r");
			    if (f == NULL)
				    err(EX_NOINPUT, "Can't open hint file %s",
					optarg);
			    order = read_hints(f, &pairs, quiet_flag,
				optarg, order);
			    fclose(f);
		    }
			    hints_flag = 1;
			    break;
			    /*FALLTHRU*/
		    case 'f':
			    hints_flag = 2;
			    break;
		    case 'l':
			    long_flag = 1;
			    break;
		    case 'q':
			    quiet_flag = 1;
			    break;
		    case 'r':
			    reverse_flag = 1;
			    break;
		    case 'v':
			    verbose_flag = 1;
			    break;
		    case 'w':
			    warn_flag = 1;
			    break;
		    default:
			    usage();
		    }
	    }

	    argc -= optind;
	    argv += optind;
	}

	switch(argc) {
	case 1: {
		FILE *f;

		f = fopen(argv[0], "r");
		if (f == NULL)
			err(EX_NOINPUT, "Can't open file %s", argv[1]);
		order = read_pairs(f, &pairs, reverse_flag, argv[1], order,
		    hints_flag == 2);
		fclose(f);
		break;
	}
	case 0:
		order = read_pairs(stdin, &pairs, reverse_flag, "stdin",
		    order, hints_flag == 2);
		break;
	default:
		usage();
	}

	{
	    struct array 	aux;	/* Unrefed nodes/cycle reporting.  */
	    struct array	remaining;
	    unsigned int	broken_arcs, broken_cycles;
	    unsigned int	left;

	    broken_arcs = 0;
	    broken_cycles = 0;

	    if (hints_flag)
	    	make_transparent(&pairs);
	    split_nodes(&pairs, &aux, &remaining);
	    ohash_delete(&pairs);

	    if (hints_flag)
		    heapify(&aux, verbose_flag);

	    left = remaining.entries + aux.entries;
	    while (left != 0) {

		    /* Standard topological sort.  */
		    while (aux.entries) {
			    struct link *l;
			    struct node *n;

			    n = DEQUEUE(&aux);
			    printf("%s\n", n->k);
			    left--;
			    /* We can't free nodes, as we don't know which
			     * entry we can remove in the hash table.  We
			     * rely on refs == 0 to recognize live nodes.  
			     * Decrease ref count of live nodes, enter new
			     * candidates into the unrefed list.  */
			    for (l = n->arcs; l != NULL; l = l->next) 
				    if (l->node->refs != 0 && 
					--l->node->refs == 0) {
					    ENQUEUE(&aux, l->node);
				    }
		    }
		    /* There are still cycles to break.  */
		    if (left != 0) {
			    struct node *n;

			    broken_cycles++;
			    /* XXX Simple cycle detection and long cycle
			     * detection are mutually exclusive.  */

			    if (long_flag) {
				    n = find_longest_cycle(&remaining, &aux);
			    } else {
				    struct node *b;

				    if (hints_flag) 
					    n = find_smallest_node(&remaining);
				    else 
					    n = find_good_cycle_break(&remaining);
				    while ((b = find_cycle_from(n, &aux)) == NULL)
					    n = find_predecessor(&remaining, n);
				    n = b;
			    }

			    if (!quiet_flag) {
				    warnx("cycle in data");
				    print_cycle(&aux);
			    }

			    if (verbose_flag)
				    warnx("%u edge%s broken", n->refs,
					plural(n->refs));
			    broken_arcs += n->refs;
			    n->refs = 0;
			    /* Reinitialization, cycle reporting uses aux.  */
			    aux.t[0] = n;
			    aux.entries = 1;
		    }
	    }
	    if (verbose_flag && broken_cycles != 0)
		    warnx("%u cycle%s broken, for a total of %u edge%s",
			broken_cycles, plural(broken_cycles),
			broken_arcs, plural(broken_arcs));
	    if (warn_flag) 
		    exit(broken_cycles < 256 ? broken_cycles : 255);
	    else
		    exit(EX_OK);
	}
}


extern char *__progname;

static void
usage()
{
	fprintf(stderr, "Usage: %s [-h file] [-flqrvw] [file]\n", __progname);
	exit(EX_USAGE);
}