Annotation of src/usr.bin/tsort/tsort.1, Revision 1.23
1.23 ! jmc 1: .\" $OpenBSD: tsort.1,v 1.22 2010/09/03 11:09:29 jmc 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.23 ! jmc 36: .Dd $Mdocdate: September 3 2010 $
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.16 espie 44: .Op Fl flqrvw
1.7 espie 45: .Op Fl h Ar file
1.1 deraadt 46: .Op Ar file
47: .Sh DESCRIPTION
1.7 espie 48: .Nm tsort
1.1 deraadt 49: takes a list of pairs of node names representing directed arcs in
50: a graph and prints the nodes in topological order on standard output.
1.16 espie 51: That is, the input describes a partial ordering relation, from which
1.15 espie 52: .Nm
53: computes a total order compatible with this partial ordering.
54: .Pp
1.1 deraadt 55: Input is taken from the named
56: .Ar file ,
57: or from standard input if no file
58: is given.
59: .Pp
1.7 espie 60: Node names in the input are separated by white space and there must
1.23 ! jmc 61: be an even number of node names.
1.1 deraadt 62: .Pp
63: Presence of a node in a graph can be represented by an arc from the node
64: to itself.
65: This is useful when a node is not connected to any other nodes.
66: .Pp
67: If the graph contains a cycle (and therefore cannot be properly sorted),
68: one of the arcs in the cycle is ignored and the sort continues.
69: Cycles are reported on standard error.
70: .Pp
71: The options are as follows:
72: .Bl -tag -width Ds
1.7 espie 73: .It Fl f
1.12 millert 74: Resolve ambiguities by selecting nodes based on the order of appearance
1.7 espie 75: of the first component of the pairs.
76: .It Fl h Ar file
77: Use
78: .Ar file ,
79: which holds an ordered list of nodes, to resolve ambiguities.
1.8 espie 80: In case of duplicates, the first entry is chosen.
1.2 deraadt 81: .It Fl l
1.1 deraadt 82: Search for and display the longest cycle.
1.10 espie 83: Can take a very long time, as it may need to solve an NP-complete problem.
1.2 deraadt 84: .It Fl q
1.14 jmc 85: Do not display informational messages about cycles.
86: This is primarily intended for building libraries, where optimal ordering
1.8 espie 87: is not critical, and cycles occur often.
1.7 espie 88: .It Fl r
89: Reverse the ordering relation.
90: .It Fl v
91: Inform on the exact number of edges broken while breaking cycles.
1.8 espie 92: If a hints file was used, inform on seen nodes absent from that file.
1.7 espie 93: .It Fl w
94: Exit with exit code the number of cycles
95: .Nm
96: had to break.
1.1 deraadt 97: .El
1.22 jmc 98: .Sh EXIT STATUS
1.21 jmc 99: .Ex -std tsort
1.15 espie 100: .Sh EXAMPLES
101: Faced with the input:
1.16 espie 102: .Bd -literal -offset indent
1.15 espie 103: a b
104: b c
105: b d
106: d f
107: c e
108: .Ed
109: .Pp
110: .Nm
111: outputs:
1.16 espie 112: .Bd -literal -offset indent
1.15 espie 113: a
114: b
115: c
116: e
117: d
118: f
119: .Ed
120: .Pp
121: which is one total ordering compatible with the individual relations.
122: There is no unicity, another compatible total ordering would be:
1.16 espie 123: .Bd -literal -offset indent
1.15 espie 124: a
125: b
126: c
127: d
128: e
129: f
130: .Ed
131: .Pp
132: .Nm
133: is commonly used to analyze dependencies and find a correct build order
134: in a static way, whereas
135: .Xr make 1
136: accomplishes the same task in a dynamic way.
1.1 deraadt 137: .Sh SEE ALSO
1.7 espie 138: .Xr ar 1 ,
1.15 espie 139: .Xr lorder 1 ,
140: .Xr make 1
1.7 espie 141: .Rs
142: .%A Donald E. Knuth
143: .%B The Art of Computer Programming
144: .%V Vol. 1
145: .%P pp 258-268
146: .%D 1973
147: .Re
1.17 jmc 148: .Sh STANDARDS
149: The
150: .Nm
151: utility is compliant with the
1.20 jmc 152: .St -p1003.1-2008
1.17 jmc 153: specification.
154: .Pp
1.18 jmc 155: The flags
156: .Op Fl fhlqrvw
157: are extensions to that specification.
1.1 deraadt 158: .Sh HISTORY
159: A
160: .Nm
161: command appeared in
162: .At v7 .
163: This
1.7 espie 164: .Nm tsort
165: command was completely rewritten by Marc Espie for
166: .Ox ,
167: to finally use the well-known optimal algorithms for topological sorting.
![[BACK]](/icons/back.gif){kind=icon}
Return to tsort.1 CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / tsort