1.\" $OpenBSD: tsort.1,v 1.11 2001/09/06 15:04:34 mpech Exp $ 2.\" $NetBSD: tsort.1,v 1.6 1996/01/17 20:37:49 mycroft Exp $ 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.\" 40.Dd November 1, 1999 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 48.Op Fl f 49.Op Fl h Ar file 50.Op Fl l 51.Op Fl q 52.Op Fl r 53.Op Fl v 54.Op Fl w 55.Op Ar file 56.Sh DESCRIPTION 57.Nm tsort 58takes a list of pairs of node names representing directed arcs in 59a graph and prints the nodes in topological order on standard output. 60Input is taken from the named 61.Ar file , 62or from standard input if no file 63is given. 64.Pp 65Node names in the input are separated by white space and there must 66be an even number of node pairs. 67.Pp 68Presence of a node in a graph can be represented by an arc from the node 69to itself. 70This is useful when a node is not connected to any other nodes. 71.Pp 72If the graph contains a cycle (and therefore cannot be properly sorted), 73one of the arcs in the cycle is ignored and the sort continues. 74Cycles are reported on standard error. 75.Pp 76The options are as follows: 77.Bl -tag -width Ds 78.It Fl f 79Resolve ambiguities by selecting nodes based on the order of apparition 80of the first component of the pairs. 81.It Fl h Ar file 82Use 83.Ar file , 84which holds an ordered list of nodes, to resolve ambiguities. 85In case of duplicates, the first entry is chosen. 86.It Fl l 87Search for and display the longest cycle. 88Can take a very long time, as it may need to solve an NP-complete problem. 89.It Fl q 90Do not display informational messages about cycles. 91This is primarily intended for building libraries, where optimal ordering 92is not critical, and cycles occur often. 93.It Fl r 94Reverse the ordering relation. 95.It Fl v 96Inform on the exact number of edges broken while breaking cycles. 97If a hints file was used, inform on seen nodes absent from that file. 98.It Fl w 99Exit with exit code the number of cycles 100.Nm 101had to break. 102.El 103.Sh SEE ALSO 104.Xr ar 1 , 105.Xr lorder 1 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 113.Sh HISTORY 114A 115.Nm 116command appeared in 117.At v7 . 118This 119.Nm tsort 120command was completely rewritten by Marc Espie for 121.Ox , 122to finally use the well-known optimal algorithms for topological sorting. 123