aboutsummaryrefslogtreecommitdiff
path: root/usr.bin/tsort/tsort.1
diff options
context:
space:
mode:
Diffstat (limited to 'usr.bin/tsort/tsort.1')
-rw-r--r--usr.bin/tsort/tsort.1167
1 files changed, 0 insertions, 167 deletions
diff --git a/usr.bin/tsort/tsort.1 b/usr.bin/tsort/tsort.1
deleted file mode 100644
index 56f5fc3..0000000
--- a/usr.bin/tsort/tsort.1
+++ /dev/null
@@ -1,167 +0,0 @@
-.\" $OpenBSD: tsort.1,v 1.24 2019/04/23 18:13:11 schwarze Exp $
-.\" $NetBSD: tsort.1,v 1.6 1996/01/17 20:37:49 mycroft Exp $
-.\"
-.\" Copyright (c) 1990, 1993, 1994
-.\" The Regents of the University of California. All rights reserved.
-.\"
-.\" This manual is derived from one contributed to Berkeley by
-.\" Michael Rendell of Memorial University of Newfoundland.
-.\"
-.\" 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. Neither the name of the University nor the names of its contributors
-.\" may be used to endorse or promote products derived from this software
-.\" without specific prior written permission.
-.\"
-.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS 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 REGENTS 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.
-.\"
-.\" @(#)tsort.1 8.3 (Berkeley) 4/1/94
-.\"
-.Dd $Mdocdate: April 23 2019 $
-.Dt TSORT 1
-.Os
-.Sh NAME
-.Nm tsort
-.Nd topological sort of a directed graph
-.Sh SYNOPSIS
-.Nm tsort
-.Op Fl flqrvw
-.Op Fl h Ar file
-.Op Ar file
-.Sh DESCRIPTION
-.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.
-That is, the input describes a partial ordering relation, from which
-.Nm
-computes a total order compatible with this partial ordering.
-.Pp
-Input is taken from the named
-.Ar file ,
-or from standard input if no file
-is given.
-.Pp
-Node names in the input are separated by white space and there must
-be an even number of node names.
-.Pp
-Presence of a node in a graph can be represented by an arc from the node
-to itself.
-This is useful when a node is not connected to any other nodes.
-.Pp
-If the graph contains a cycle (and therefore cannot be properly sorted),
-one of the arcs in the cycle is ignored and the sort continues.
-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 appearance
-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.
-In case of duplicates, the first entry is chosen.
-.It Fl l
-Search for and display the longest cycle.
-Can take a very long time, as it may need to solve an NP-complete problem.
-.It Fl q
-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.
-If a hints file was used, inform on seen nodes absent from that file.
-.It Fl w
-Exit with exit code the number of cycles
-.Nm
-had to break.
-.El
-.Sh EXIT STATUS
-.Ex -std tsort
-.Sh EXAMPLES
-Faced with the input:
-.Bd -literal -offset indent
-a b
-b c
-b d
-d f
-c e
-.Ed
-.Pp
-.Nm
-outputs:
-.Bd -literal -offset indent
-a
-b
-c
-e
-d
-f
-.Ed
-.Pp
-which is one total ordering compatible with the individual relations.
-There is no unicity, another compatible total ordering would be:
-.Bd -literal -offset indent
-a
-b
-c
-d
-e
-f
-.Ed
-.Pp
-.Nm
-is commonly used to analyze dependencies and find a correct build order
-in a static way, whereas
-.Xr make 1
-accomplishes the same task in a dynamic way.
-.Sh SEE ALSO
-.Xr ar 1 ,
-.Xr lorder 1 ,
-.Xr make 1
-.Rs
-.%A Donald E. Knuth
-.%B The Art of Computer Programming
-.%V Vol. 1
-.%P pp. 258\(en268
-.%D 1973
-.Re
-.Sh STANDARDS
-The
-.Nm
-utility is compliant with the
-.St -p1003.1-2008
-specification.
-.Pp
-The flags
-.Op Fl fhlqrvw
-are extensions to that specification.
-.Sh HISTORY
-A
-.Nm
-command appeared in
-.At v7 .
-This
-.Nm tsort
-command was completely rewritten by Marc Espie for
-.Ox ,
-to finally use the well-known optimal algorithms for topological sorting.