Return to tsort.1 CVS log

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

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

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