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.\" 389b50d902SRodney W. Grimes.Dd April 1, 1994 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 468cd68930SPoul-Henning Kamp.Op Fl d 479b50d902SRodney W. Grimes.Op Fl l 488566830bSJordan K. Hubbard.Op Fl q 499b50d902SRodney W. Grimes.Op Ar file 509b50d902SRodney W. Grimes.Sh DESCRIPTION 51e8937ba0SPhilippe CharnierThe 52e8937ba0SPhilippe Charnier.Nm 53e8937ba0SPhilippe Charnierutility takes a list of pairs of node names representing directed arcs in 549b50d902SRodney W. Grimesa graph and prints the nodes in topological order on standard output. 559b50d902SRodney W. GrimesInput is taken from the named 569b50d902SRodney W. Grimes.Ar file , 579b50d902SRodney W. Grimesor from standard input if no file 589b50d902SRodney W. Grimesis given. 599b50d902SRodney W. Grimes.Pp 609b50d902SRodney W. GrimesNode names in the input are separated by white space and there must 61bc47530cSBill Fumerolabe an even number of nodes. 629b50d902SRodney W. Grimes.Pp 639b50d902SRodney W. GrimesPresence of a node in a graph can be represented by an arc from the node 649b50d902SRodney W. Grimesto itself. 659b50d902SRodney W. GrimesThis is useful when a node is not connected to any other nodes. 669b50d902SRodney W. Grimes.Pp 679b50d902SRodney W. GrimesIf the graph contains a cycle (and therefore cannot be properly sorted), 689b50d902SRodney W. Grimesone of the arcs in the cycle is ignored and the sort continues. 699b50d902SRodney W. GrimesCycles are reported on standard error. 709b50d902SRodney W. Grimes.Pp 719b50d902SRodney W. GrimesThe options are as follows: 729b50d902SRodney W. Grimes.Bl -tag -width Ds 738cd68930SPoul-Henning Kamp.It Fl d 748cd68930SPoul-Henning KampTurn on debugging. 759b50d902SRodney W. Grimes.It Fl l 769b50d902SRodney W. GrimesSearch for and display the longest cycle. 779b50d902SRodney W. GrimesCan take a very long time. 788566830bSJordan K. Hubbard.It Fl q 798566830bSJordan K. HubbardDo not display informational messages about cycles. This is primarily 808566830bSJordan K. Hubbardintended for building libraries, where optimal ordering is not critical, 818566830bSJordan K. Hubbardand cycles occur often. 829b50d902SRodney W. Grimes.El 839b50d902SRodney W. Grimes.Sh SEE ALSO 849b50d902SRodney W. Grimes.Xr ar 1 859b50d902SRodney W. Grimes.Sh HISTORY 869b50d902SRodney W. GrimesA 879b50d902SRodney W. Grimes.Nm 889b50d902SRodney W. Grimescommand appeared in 899b50d902SRodney W. Grimes.At v7 . 909b50d902SRodney W. GrimesThis 910e879078SPhilippe Charnier.Nm 929b50d902SRodney W. Grimescommand and manual page are derived from sources contributed to Berkeley by 939b50d902SRodney W. GrimesMichael Rendell of Memorial University of Newfoundland. 94