diff options
author | Marc Espie <espie@cvs.openbsd.org> | 2001-03-26 22:53:34 +0000 |
---|---|---|
committer | Marc Espie <espie@cvs.openbsd.org> | 2001-03-26 22:53:34 +0000 |
commit | 60ea328912452bb904fc34be01f64367de8fe8b3 (patch) | |
tree | 3a4743094e1fef5ac26efb7c9c1b9af4d6a1c1a5 /usr.bin/tsort/tsort.1 | |
parent | 0ed499a8c4ed0e7ef2f74d6e681f98b82cce5028 (diff) |
Replacement for original tsort.
The old code suffers from a few defects:
- it does not even implement the standard optimal topological sort
algorithm. It's much slower.
- its longest cycle computation is completely bogus.
This is clean-slate code, that does implement the actual standard optimal
topological sort, together with a correct graph traversal to find longest
cycles.
It does also feature a `stable tsort' mode, where it uses a heap to yield
the least disturbed permutation of input nodes that satisfies the ordering
constraints (in particular, try tsort -f).
Thanks to the nature of the problem, the actual output won't exactly match
the old one, but it does pass the regression suite (and it is a topological
sorter).
Ok millert@
Diffstat (limited to 'usr.bin/tsort/tsort.1')
-rw-r--r-- | usr.bin/tsort/tsort.1 | 48 |
1 files changed, 37 insertions, 11 deletions
diff --git a/usr.bin/tsort/tsort.1 b/usr.bin/tsort/tsort.1 index 48132883ff7..971db804316 100644 --- a/usr.bin/tsort/tsort.1 +++ b/usr.bin/tsort/tsort.1 @@ -1,4 +1,4 @@ -.\" $OpenBSD: tsort.1,v 1.6 2000/03/11 21:40:06 aaron Exp $ +.\" $OpenBSD: tsort.1,v 1.7 2001/03/26 22:53:33 espie Exp $ .\" $NetBSD: tsort.1,v 1.6 1996/01/17 20:37:49 mycroft Exp $ .\" .\" Copyright (c) 1990, 1993, 1994 @@ -37,7 +37,7 @@ .\" .\" @(#)tsort.1 8.3 (Berkeley) 4/1/94 .\" -.Dd April 1, 1994 +.Dd November 1, 1999 .Dt TSORT 1 .Os .Sh NAME @@ -45,11 +45,15 @@ .Nd topological sort of a directed graph .Sh SYNOPSIS .Nm tsort +.Op Fl f +.Op Fl h Ar file .Op Fl l .Op Fl q +.Op Fl r +.Op Fl w .Op Ar file .Sh DESCRIPTION -.Nm +.Nm tsort takes a list of pairs of node names representing directed arcs in a graph and prints the nodes in topological order on standard output. Input is taken from the named @@ -57,7 +61,7 @@ Input is taken from the named or from standard input if no file is given. .Pp -Node names in the input are separated by whitespace and there must +Node names in the input are separated by white space and there must be an even number of node pairs. .Pp Presence of a node in a graph can be represented by an arc from the node @@ -70,23 +74,45 @@ Cycles are reported on standard error. .Pp The options are as follows: .Bl -tag -width Ds +.It Fl f +Resolve ambiguities by selecting nodes based on the order of apparition +of the first component of the pairs. +.It Fl h Ar file +Use +.Ar file , +which holds an ordered list of nodes, to resolve ambiguities. .It Fl l Search for and display the longest cycle. -Can take a very long time. .It Fl q -Do not display informational messages about cycles. -This is primarily +Do not display informational messages about cycles. This is primarily intended for building libraries, where optimal ordering is not critical, and cycles occur often. +.It Fl r +Reverse the ordering relation. +.It Fl v +Inform on the exact number of edges broken while breaking cycles. +.It Fl w +Exit with exit code the number of cycles +.Nm +had to break. .El .Sh SEE ALSO -.Xr ar 1 +.Xr ar 1 , +.Xr lorder 1 , +.Rs +.%A Donald E. Knuth +.%B The Art of Computer Programming +.%V Vol. 1 +.%P pp 258-268 +.%D 1973 +.Re .Sh HISTORY A .Nm command appeared in .At v7 . This -.Nm -command and manual page are derived from sources contributed to Berkeley by -Michael Rendell of Memorial University of Newfoundland. +.Nm tsort +command was completely rewritten by Marc Espie for +.Ox , +to finally use the well-known optimal algorithms for topological sorting. |