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. 159b50d902SRodney W. Grimes.\" 3. All advertising materials mentioning features or use of this software 169b50d902SRodney W. Grimes.\" must display the following acknowledgement: 179b50d902SRodney W. Grimes.\" This product includes software developed by the University of 189b50d902SRodney W. Grimes.\" California, Berkeley and its contributors. 199b50d902SRodney W. Grimes.\" 4. Neither the name of the University nor the names of its contributors 209b50d902SRodney W. Grimes.\" may be used to endorse or promote products derived from this software 219b50d902SRodney W. Grimes.\" without specific prior written permission. 229b50d902SRodney W. Grimes.\" 239b50d902SRodney W. Grimes.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 249b50d902SRodney W. Grimes.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 259b50d902SRodney W. Grimes.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 269b50d902SRodney W. Grimes.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 279b50d902SRodney W. Grimes.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 289b50d902SRodney W. Grimes.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 299b50d902SRodney W. Grimes.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 309b50d902SRodney W. Grimes.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 319b50d902SRodney W. Grimes.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 329b50d902SRodney W. Grimes.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 339b50d902SRodney W. Grimes.\" SUCH DAMAGE. 349b50d902SRodney W. Grimes.\" 359b50d902SRodney W. Grimes.\" @(#)tsort.1 8.3 (Berkeley) 4/1/94 36c3aac50fSPeter Wemm.\" $FreeBSD$ 379b50d902SRodney W. Grimes.\" 38bf42b54cSRuslan Ermilov.Dd December 27, 2006 399b50d902SRodney W. Grimes.Dt TSORT 1 409b50d902SRodney W. Grimes.Os 419b50d902SRodney W. Grimes.Sh NAME 429b50d902SRodney W. Grimes.Nm tsort 439b50d902SRodney W. Grimes.Nd topological sort of a directed graph 449b50d902SRodney W. Grimes.Sh SYNOPSIS 450e879078SPhilippe Charnier.Nm 46fa759582STim J. Robbins.Op Fl dlq 479b50d902SRodney W. Grimes.Op Ar file 489b50d902SRodney W. Grimes.Sh DESCRIPTION 49e8937ba0SPhilippe CharnierThe 50e8937ba0SPhilippe Charnier.Nm 51e8937ba0SPhilippe Charnierutility takes a list of pairs of node names representing directed arcs in 529b50d902SRodney W. Grimesa graph and prints the nodes in topological order on standard output. 539b50d902SRodney W. GrimesInput is taken from the named 549b50d902SRodney W. Grimes.Ar file , 559b50d902SRodney W. Grimesor from standard input if no file 569b50d902SRodney W. Grimesis given. 579b50d902SRodney W. Grimes.Pp 58bf42b54cSRuslan ErmilovThere must be an even number of nodes in the input. 59bf42b54cSRuslan ErmilovNode names specified on the same line should be white space separated. 609b50d902SRodney W. Grimes.Pp 619b50d902SRodney W. GrimesPresence of a node in a graph can be represented by an arc from the node 629b50d902SRodney W. Grimesto itself. 639b50d902SRodney W. GrimesThis is useful when a node is not connected to any other nodes. 649b50d902SRodney W. Grimes.Pp 659b50d902SRodney W. GrimesIf the graph contains a cycle (and therefore cannot be properly sorted), 669b50d902SRodney W. Grimesone of the arcs in the cycle is ignored and the sort continues. 679b50d902SRodney W. GrimesCycles are reported on standard error. 689b50d902SRodney W. Grimes.Pp 699b50d902SRodney W. GrimesThe options are as follows: 70bf42b54cSRuslan Ermilov.Bl -tag -width indent 718cd68930SPoul-Henning Kamp.It Fl d 728cd68930SPoul-Henning KampTurn on debugging. 739b50d902SRodney W. Grimes.It Fl l 749b50d902SRodney W. GrimesSearch for and display the longest cycle. 759b50d902SRodney W. GrimesCan take a very long time. 768566830bSJordan K. Hubbard.It Fl q 776a3e8b0aSRuslan ErmilovDo not display informational messages about cycles. 786a3e8b0aSRuslan ErmilovThis is primarily 798566830bSJordan K. Hubbardintended for building libraries, where optimal ordering is not critical, 808566830bSJordan K. Hubbardand cycles occur often. 819b50d902SRodney W. Grimes.El 829b50d902SRodney W. Grimes.Sh SEE ALSO 839b50d902SRodney W. Grimes.Xr ar 1 849b50d902SRodney W. Grimes.Sh HISTORY 85bf42b54cSRuslan ErmilovThe 869b50d902SRodney W. Grimes.Nm 879b50d902SRodney W. Grimescommand appeared in 889b50d902SRodney W. Grimes.At v7 . 899b50d902SRodney W. GrimesThis 900e879078SPhilippe Charnier.Nm 919b50d902SRodney W. Grimescommand and manual page are derived from sources contributed to Berkeley by 92bf42b54cSRuslan Ermilov.An Michael Rendell 93bf42b54cSRuslan Ermilovof Memorial University of Newfoundland. 944f45d811STim J. Robbins.Sh BUGS 954f45d811STim J. RobbinsThe 964f45d811STim J. Robbins.Nm 974f45d811STim J. Robbinsutility does not recognize multibyte characters. 98