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. 15*fbbd9655SWarner 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.\" 319b50d902SRodney W. Grimes.\" @(#)tsort.1 8.3 (Berkeley) 4/1/94 32c3aac50fSPeter Wemm.\" $FreeBSD$ 339b50d902SRodney W. Grimes.\" 34bf42b54cSRuslan Ermilov.Dd December 27, 2006 359b50d902SRodney W. Grimes.Dt TSORT 1 369b50d902SRodney W. Grimes.Os 379b50d902SRodney W. Grimes.Sh NAME 389b50d902SRodney W. Grimes.Nm tsort 399b50d902SRodney W. Grimes.Nd topological sort of a directed graph 409b50d902SRodney W. Grimes.Sh SYNOPSIS 410e879078SPhilippe Charnier.Nm 42fa759582STim J. Robbins.Op Fl dlq 439b50d902SRodney W. Grimes.Op Ar file 449b50d902SRodney W. Grimes.Sh DESCRIPTION 45e8937ba0SPhilippe CharnierThe 46e8937ba0SPhilippe Charnier.Nm 47e8937ba0SPhilippe Charnierutility takes a list of pairs of node names representing directed arcs in 489b50d902SRodney W. Grimesa graph and prints the nodes in topological order on standard output. 499b50d902SRodney W. GrimesInput is taken from the named 509b50d902SRodney W. Grimes.Ar file , 519b50d902SRodney W. Grimesor from standard input if no file 529b50d902SRodney W. Grimesis given. 539b50d902SRodney W. Grimes.Pp 54bf42b54cSRuslan ErmilovThere must be an even number of nodes in the input. 55bf42b54cSRuslan ErmilovNode names specified on the same line should be white space separated. 569b50d902SRodney W. Grimes.Pp 579b50d902SRodney W. GrimesPresence of a node in a graph can be represented by an arc from the node 589b50d902SRodney W. Grimesto itself. 599b50d902SRodney W. GrimesThis is useful when a node is not connected to any other nodes. 609b50d902SRodney W. Grimes.Pp 619b50d902SRodney W. GrimesIf the graph contains a cycle (and therefore cannot be properly sorted), 629b50d902SRodney W. Grimesone of the arcs in the cycle is ignored and the sort continues. 639b50d902SRodney W. GrimesCycles are reported on standard error. 649b50d902SRodney W. Grimes.Pp 659b50d902SRodney W. GrimesThe options are as follows: 66bf42b54cSRuslan Ermilov.Bl -tag -width indent 678cd68930SPoul-Henning Kamp.It Fl d 688cd68930SPoul-Henning KampTurn on debugging. 699b50d902SRodney W. Grimes.It Fl l 709b50d902SRodney W. GrimesSearch for and display the longest cycle. 719b50d902SRodney W. GrimesCan take a very long time. 728566830bSJordan K. Hubbard.It Fl q 736a3e8b0aSRuslan ErmilovDo not display informational messages about cycles. 746a3e8b0aSRuslan ErmilovThis is primarily 758566830bSJordan K. Hubbardintended for building libraries, where optimal ordering is not critical, 768566830bSJordan K. Hubbardand cycles occur often. 779b50d902SRodney W. Grimes.El 789b50d902SRodney W. Grimes.Sh SEE ALSO 799b50d902SRodney W. Grimes.Xr ar 1 809b50d902SRodney W. Grimes.Sh HISTORY 81bf42b54cSRuslan ErmilovThe 829b50d902SRodney W. Grimes.Nm 839b50d902SRodney W. Grimescommand appeared in 849b50d902SRodney W. Grimes.At v7 . 859b50d902SRodney W. GrimesThis 860e879078SPhilippe Charnier.Nm 879b50d902SRodney W. Grimescommand and manual page are derived from sources contributed to Berkeley by 88bf42b54cSRuslan Ermilov.An Michael Rendell 89bf42b54cSRuslan Ermilovof Memorial University of Newfoundland. 904f45d811STim J. Robbins.Sh BUGS 914f45d811STim J. RobbinsThe 924f45d811STim J. Robbins.Nm 934f45d811STim J. Robbinsutility does not recognize multibyte characters. 94