Return to tsort.1 CVS log

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

Annotation of src/usr.bin/tsort/tsort.1, Revision 1.13

1.13    ! millert     1: .\"    $OpenBSD: tsort.1,v 1.12 2002/11/18 20:20:56 millert Exp $
1.2       deraadt     2: .\"    $NetBSD: tsort.1,v 1.6 1996/01/17 20:37:49 mycroft Exp $
1.1       deraadt     3: .\"
                      4: .\" Copyright (c) 1990, 1993, 1994
                      5: .\"    The Regents of the University of California.  All rights reserved.
                      6: .\"
                      7: .\" This manual is derived from one contributed to Berkeley by
                      8: .\" Michael Rendell of Memorial University of Newfoundland.
                      9: .\"
                     10: .\" Redistribution and use in source and binary forms, with or without
                     11: .\" modification, are permitted provided that the following conditions
                     12: .\" are met:
                     13: .\" 1. Redistributions of source code must retain the above copyright
                     14: .\"    notice, this list of conditions and the following disclaimer.
                     15: .\" 2. Redistributions in binary form must reproduce the above copyright
                     16: .\"    notice, this list of conditions and the following disclaimer in the
                     17: .\"    documentation and/or other materials provided with the distribution.
1.13    ! millert    18: .\" 3. Neither the name of the University nor the names of its contributors
1.1       deraadt    19: .\"    may be used to endorse or promote products derived from this software
                     20: .\"    without specific prior written permission.
                     21: .\"
                     22: .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
                     23: .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
                     24: .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
                     25: .\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
                     26: .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
                     27: .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
                     28: .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
                     29: .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
                     30: .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
                     31: .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
                     32: .\" SUCH DAMAGE.
                     33: .\"
                     34: .\"     @(#)tsort.1    8.3 (Berkeley) 4/1/94
                     35: .\"
1.7       espie      36: .Dd November 1, 1999
1.1       deraadt    37: .Dt TSORT 1
                     38: .Os
                     39: .Sh NAME
                     40: .Nm tsort
                     41: .Nd topological sort of a directed graph
                     42: .Sh SYNOPSIS
                     43: .Nm tsort
1.7       espie      44: .Op Fl f
                     45: .Op Fl h Ar file
1.1       deraadt    46: .Op Fl l
1.2       deraadt    47: .Op Fl q
1.7       espie      48: .Op Fl r
1.9       pvalchev   49: .Op Fl v
1.7       espie      50: .Op Fl w
1.1       deraadt    51: .Op Ar file
                     52: .Sh DESCRIPTION
1.7       espie      53: .Nm tsort
1.1       deraadt    54: takes a list of pairs of node names representing directed arcs in
                     55: a graph and prints the nodes in topological order on standard output.
                     56: Input is taken from the named
                     57: .Ar file ,
                     58: or from standard input if no file
                     59: is given.
                     60: .Pp
1.7       espie      61: Node names in the input are separated by white space and there must
1.1       deraadt    62: be an even number of node pairs.
                     63: .Pp
                     64: Presence of a node in a graph can be represented by an arc from the node
                     65: to itself.
                     66: This is useful when a node is not connected to any other nodes.
                     67: .Pp
                     68: If the graph contains a cycle (and therefore cannot be properly sorted),
                     69: one of the arcs in the cycle is ignored and the sort continues.
                     70: Cycles are reported on standard error.
                     71: .Pp
                     72: The options are as follows:
                     73: .Bl -tag -width Ds
1.7       espie      74: .It Fl f
1.12      millert    75: Resolve ambiguities by selecting nodes based on the order of appearance
1.7       espie      76: of the first component of the pairs.
                     77: .It Fl h Ar file
                     78: Use
                     79: .Ar file ,
                     80: which holds an ordered list of nodes, to resolve ambiguities.
1.8       espie      81: In case of duplicates, the first entry is chosen.
1.2       deraadt    82: .It Fl l
1.1       deraadt    83: Search for and display the longest cycle.
1.10      espie      84: Can take a very long time, as it may need to solve an NP-complete problem.
1.2       deraadt    85: .It Fl q
1.8       espie      86: Do not display informational messages about cycles.
                     87: This is primarily intended for building libraries, where optimal ordering
                     88: is not critical, and cycles occur often.
1.7       espie      89: .It Fl r
                     90: Reverse the ordering relation.
                     91: .It Fl v
                     92: Inform on the exact number of edges broken while breaking cycles.
1.8       espie      93: If a hints file was used, inform on seen nodes absent from that file.
1.7       espie      94: .It Fl w
                     95: Exit with exit code the number of cycles
                     96: .Nm
                     97: had to break.
1.1       deraadt    98: .El
                     99: .Sh SEE ALSO
1.7       espie     100: .Xr ar 1 ,
1.11      mpech     101: .Xr lorder 1
1.7       espie     102: .Rs
                    103: .%A Donald E. Knuth
                    104: .%B The Art of Computer Programming
                    105: .%V Vol. 1
                    106: .%P pp 258-268
                    107: .%D 1973
                    108: .Re
1.1       deraadt   109: .Sh HISTORY
                    110: A
                    111: .Nm
                    112: command appeared in
                    113: .At v7 .
                    114: This
1.7       espie     115: .Nm tsort
                    116: command was completely rewritten by Marc Espie for
                    117: .Ox ,
                    118: to finally use the well-known optimal algorithms for topological sorting.