summaryrefslogtreecommitdiff
path: root/usr.bin/tsort/tsort.1
diff options
context:
space:
mode:
authorMarc Espie <espie@cvs.openbsd.org>2001-03-26 22:53:34 +0000
committerMarc Espie <espie@cvs.openbsd.org>2001-03-26 22:53:34 +0000
commit60ea328912452bb904fc34be01f64367de8fe8b3 (patch)
tree3a4743094e1fef5ac26efb7c9c1b9af4d6a1c1a5 /usr.bin/tsort/tsort.1
parent0ed499a8c4ed0e7ef2f74d6e681f98b82cce5028 (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.148
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.