1.\" Copyright (c) 1990, 1993, 1994 2.\" The Regents of the University of California. All rights reserved. 3.\" 4.\" This manual is derived from one contributed to Berkeley by 5.\" Michael Rendell of Memorial University of Newfoundland. 6.\" 7.\" Redistribution and use in source and binary forms, with or without 8.\" modification, are permitted provided that the following conditions 9.\" are met: 10.\" 1. Redistributions of source code must retain the above copyright 11.\" notice, this list of conditions and the following disclaimer. 12.\" 2. Redistributions in binary form must reproduce the above copyright 13.\" notice, this list of conditions and the following disclaimer in the 14.\" documentation and/or other materials provided with the distribution. 15.\" 3. Neither the name of the University nor the names of its contributors 16.\" may be used to endorse or promote products derived from this software 17.\" without specific prior written permission. 18.\" 19.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 20.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 23.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 25.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 26.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 27.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 28.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 29.\" SUCH DAMAGE. 30.\" 31.Dd August 30, 2020 32.Dt TSORT 1 33.Os 34.Sh NAME 35.Nm tsort 36.Nd topological sort of a directed graph 37.Sh SYNOPSIS 38.Nm 39.Op Fl dlq 40.Op Ar file 41.Sh DESCRIPTION 42The 43.Nm 44utility takes a list of pairs of node names representing directed arcs in 45a graph and prints the nodes in topological order on standard output. 46Input is taken from the named 47.Ar file , 48or from standard input if no file 49is given. 50.Pp 51There must be an even number of nodes in the input. 52Node names specified on the same line should be white space separated. 53.Pp 54Presence of a node in a graph can be represented by an arc from the node 55to itself. 56This is useful when a node is not connected to any other nodes. 57.Pp 58If the graph contains a cycle (and therefore cannot be properly sorted), 59one of the arcs in the cycle is ignored and the sort continues. 60Cycles are reported on standard error. 61.Pp 62The options are as follows: 63.Bl -tag -width indent 64.It Fl d 65Turn on debugging. 66.It Fl l 67Search for and display the longest cycle. 68Can take a very long time. 69.It Fl q 70Do not display informational messages about cycles. 71This is primarily 72intended for building libraries, where optimal ordering is not critical, 73and cycles occur often. 74.El 75.Sh EXAMPLES 76Assuming a file named 77.Pa dag 78with the following contents representing a directed acyclic graph: 79.Bd -literal -offset indent 80A B 81A F 82B C 83B D 84D E 85.Ed 86.Pp 87Sort the nodes of the graph: 88.Bd -literal -offset indent 89$ tsort dag 90A 91F 92B 93D 94C 95E 96.Ed 97.Pp 98White spaces and new line characters are considered equal. 99This file for example is considered equal to the one we defined before: 100.Bd -literal -offset indent 101$ cat dga 102A B A F B C B D D E 103.Ed 104.Pp 105Assume we add a new directed arc from D to A creating a cycle: 106.Bd -literal -offset indent 107A B 108A F 109B C 110B D 111D E 112D A 113.Ed 114.Pp 115Ordering the graph detects the cycle: 116.Bd -literal -offset indent 117$ tsort dag 118tsort: cycle in data 119tsort: A 120tsort: B 121tsort: D 122D 123E 124A 125F 126B 127C 128.Ed 129.Pp 130Same as above but silencing the warning about the cycle: 131.Bd -literal -offset indent 132$ tsort -q dag 133D 134E 135A 136F 137B 138C 139.Ed 140.Sh SEE ALSO 141.Xr ar 1 142.Sh HISTORY 143The 144.Nm 145command appeared in 146.At v7 . 147This 148.Nm 149command and manual page are derived from sources contributed to Berkeley by 150.An Michael Rendell 151of Memorial University of Newfoundland. 152.Sh BUGS 153The 154.Nm 155utility does not recognize multibyte characters. 156