19b50d902SRodney W. Grimes.\" Copyright (c) 1990, 1993, 1994 29b50d902SRodney W. Grimes.\" The Regents of the University of California. All rights reserved. 39b50d902SRodney W. Grimes.\" 49b50d902SRodney W. Grimes.\" This manual is derived from one contributed to Berkeley by 59b50d902SRodney W. Grimes.\" Michael Rendell of Memorial University of Newfoundland. 69b50d902SRodney W. Grimes.\" 79b50d902SRodney W. Grimes.\" Redistribution and use in source and binary forms, with or without 89b50d902SRodney W. Grimes.\" modification, are permitted provided that the following conditions 99b50d902SRodney W. Grimes.\" are met: 109b50d902SRodney W. Grimes.\" 1. Redistributions of source code must retain the above copyright 119b50d902SRodney W. Grimes.\" notice, this list of conditions and the following disclaimer. 129b50d902SRodney W. Grimes.\" 2. Redistributions in binary form must reproduce the above copyright 139b50d902SRodney W. Grimes.\" notice, this list of conditions and the following disclaimer in the 149b50d902SRodney W. Grimes.\" documentation and/or other materials provided with the distribution. 15fbbd9655SWarner Losh.\" 3. Neither the name of the University nor the names of its contributors 169b50d902SRodney W. Grimes.\" may be used to endorse or promote products derived from this software 179b50d902SRodney W. Grimes.\" without specific prior written permission. 189b50d902SRodney W. Grimes.\" 199b50d902SRodney W. Grimes.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 209b50d902SRodney W. Grimes.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 219b50d902SRodney W. Grimes.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 229b50d902SRodney W. Grimes.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 239b50d902SRodney W. Grimes.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 249b50d902SRodney W. Grimes.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 259b50d902SRodney W. Grimes.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 269b50d902SRodney W. Grimes.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 279b50d902SRodney W. Grimes.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 289b50d902SRodney W. Grimes.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 299b50d902SRodney W. Grimes.\" SUCH DAMAGE. 309b50d902SRodney W. Grimes.\" 31*9051d94eSFernando Apesteguía.Dd August 30, 2020 329b50d902SRodney W. Grimes.Dt TSORT 1 339b50d902SRodney W. Grimes.Os 349b50d902SRodney W. Grimes.Sh NAME 359b50d902SRodney W. Grimes.Nm tsort 369b50d902SRodney W. Grimes.Nd topological sort of a directed graph 379b50d902SRodney W. Grimes.Sh SYNOPSIS 380e879078SPhilippe Charnier.Nm 39fa759582STim J. Robbins.Op Fl dlq 409b50d902SRodney W. Grimes.Op Ar file 419b50d902SRodney W. Grimes.Sh DESCRIPTION 42e8937ba0SPhilippe CharnierThe 43e8937ba0SPhilippe Charnier.Nm 44e8937ba0SPhilippe Charnierutility takes a list of pairs of node names representing directed arcs in 459b50d902SRodney W. Grimesa graph and prints the nodes in topological order on standard output. 469b50d902SRodney W. GrimesInput is taken from the named 479b50d902SRodney W. Grimes.Ar file , 489b50d902SRodney W. Grimesor from standard input if no file 499b50d902SRodney W. Grimesis given. 509b50d902SRodney W. Grimes.Pp 51bf42b54cSRuslan ErmilovThere must be an even number of nodes in the input. 52bf42b54cSRuslan ErmilovNode names specified on the same line should be white space separated. 539b50d902SRodney W. Grimes.Pp 549b50d902SRodney W. GrimesPresence of a node in a graph can be represented by an arc from the node 559b50d902SRodney W. Grimesto itself. 569b50d902SRodney W. GrimesThis is useful when a node is not connected to any other nodes. 579b50d902SRodney W. Grimes.Pp 589b50d902SRodney W. GrimesIf the graph contains a cycle (and therefore cannot be properly sorted), 599b50d902SRodney W. Grimesone of the arcs in the cycle is ignored and the sort continues. 609b50d902SRodney W. GrimesCycles are reported on standard error. 619b50d902SRodney W. Grimes.Pp 629b50d902SRodney W. GrimesThe options are as follows: 63bf42b54cSRuslan Ermilov.Bl -tag -width indent 648cd68930SPoul-Henning Kamp.It Fl d 658cd68930SPoul-Henning KampTurn on debugging. 669b50d902SRodney W. Grimes.It Fl l 679b50d902SRodney W. GrimesSearch for and display the longest cycle. 689b50d902SRodney W. GrimesCan take a very long time. 698566830bSJordan K. Hubbard.It Fl q 706a3e8b0aSRuslan ErmilovDo not display informational messages about cycles. 716a3e8b0aSRuslan ErmilovThis is primarily 728566830bSJordan K. Hubbardintended for building libraries, where optimal ordering is not critical, 738566830bSJordan K. Hubbardand cycles occur often. 749b50d902SRodney W. Grimes.El 75*9051d94eSFernando Apesteguía.Sh EXAMPLES 76*9051d94eSFernando ApesteguíaAssuming a file named 77*9051d94eSFernando Apesteguía.Pa dag 78*9051d94eSFernando Apesteguíawith the following contents representing a directed acyclic graph: 79*9051d94eSFernando Apesteguía.Bd -literal -offset indent 80*9051d94eSFernando ApesteguíaA B 81*9051d94eSFernando ApesteguíaA F 82*9051d94eSFernando ApesteguíaB C 83*9051d94eSFernando ApesteguíaB D 84*9051d94eSFernando ApesteguíaD E 85*9051d94eSFernando Apesteguía.Ed 86*9051d94eSFernando Apesteguía.Pp 87*9051d94eSFernando ApesteguíaSort the nodes of the graph: 88*9051d94eSFernando Apesteguía.Bd -literal -offset indent 89*9051d94eSFernando Apesteguía$ tsort dag 90*9051d94eSFernando ApesteguíaA 91*9051d94eSFernando ApesteguíaF 92*9051d94eSFernando ApesteguíaB 93*9051d94eSFernando ApesteguíaD 94*9051d94eSFernando ApesteguíaC 95*9051d94eSFernando ApesteguíaE 96*9051d94eSFernando Apesteguía.Ed 97*9051d94eSFernando Apesteguía.Pp 98*9051d94eSFernando ApesteguíaWhite spaces and new line characters are considered equal. 99*9051d94eSFernando ApesteguíaThis file for example is considered equal to the one we defined before: 100*9051d94eSFernando Apesteguía.Bd -literal -offset indent 101*9051d94eSFernando Apesteguía$ cat dga 102*9051d94eSFernando ApesteguíaA B A F B C B D D E 103*9051d94eSFernando Apesteguía.Ed 104*9051d94eSFernando Apesteguía.Pp 105*9051d94eSFernando ApesteguíaAssume we add a new directed arc from D to A creating a cycle: 106*9051d94eSFernando Apesteguía.Bd -literal -offset indent 107*9051d94eSFernando ApesteguíaA B 108*9051d94eSFernando ApesteguíaA F 109*9051d94eSFernando ApesteguíaB C 110*9051d94eSFernando ApesteguíaB D 111*9051d94eSFernando ApesteguíaD E 112*9051d94eSFernando ApesteguíaD A 113*9051d94eSFernando Apesteguía.Ed 114*9051d94eSFernando Apesteguía.Pp 115*9051d94eSFernando ApesteguíaOrdering the graph detects the cycle: 116*9051d94eSFernando Apesteguía.Bd -literal -offset indent 117*9051d94eSFernando Apesteguía$ tsort dag 118*9051d94eSFernando Apesteguíatsort: cycle in data 119*9051d94eSFernando Apesteguíatsort: A 120*9051d94eSFernando Apesteguíatsort: B 121*9051d94eSFernando Apesteguíatsort: D 122*9051d94eSFernando ApesteguíaD 123*9051d94eSFernando ApesteguíaE 124*9051d94eSFernando ApesteguíaA 125*9051d94eSFernando ApesteguíaF 126*9051d94eSFernando ApesteguíaB 127*9051d94eSFernando ApesteguíaC 128*9051d94eSFernando Apesteguía.Ed 129*9051d94eSFernando Apesteguía.Pp 130*9051d94eSFernando ApesteguíaSame as above but silencing the warning about the cycle: 131*9051d94eSFernando Apesteguía.Bd -literal -offset indent 132*9051d94eSFernando Apesteguía$ tsort -q dag 133*9051d94eSFernando ApesteguíaD 134*9051d94eSFernando ApesteguíaE 135*9051d94eSFernando ApesteguíaA 136*9051d94eSFernando ApesteguíaF 137*9051d94eSFernando ApesteguíaB 138*9051d94eSFernando ApesteguíaC 139*9051d94eSFernando Apesteguía.Ed 1409b50d902SRodney W. Grimes.Sh SEE ALSO 1419b50d902SRodney W. Grimes.Xr ar 1 1429b50d902SRodney W. Grimes.Sh HISTORY 143bf42b54cSRuslan ErmilovThe 1449b50d902SRodney W. Grimes.Nm 1459b50d902SRodney W. Grimescommand appeared in 1469b50d902SRodney W. Grimes.At v7 . 1479b50d902SRodney W. GrimesThis 1480e879078SPhilippe Charnier.Nm 1499b50d902SRodney W. Grimescommand and manual page are derived from sources contributed to Berkeley by 150bf42b54cSRuslan Ermilov.An Michael Rendell 151bf42b54cSRuslan Ermilovof Memorial University of Newfoundland. 1524f45d811STim J. Robbins.Sh BUGS 1534f45d811STim J. RobbinsThe 1544f45d811STim J. Robbins.Nm 1554f45d811STim J. Robbinsutility does not recognize multibyte characters. 156