1*8e5df35eSLionel Sambuc.\" $NetBSD: tsort.1,v 1.10 2003/08/07 11:16:50 agc Exp $ 2*8e5df35eSLionel Sambuc.\" 3*8e5df35eSLionel Sambuc.\" Copyright (c) 1990, 1993, 1994 4*8e5df35eSLionel Sambuc.\" The Regents of the University of California. All rights reserved. 5*8e5df35eSLionel Sambuc.\" 6*8e5df35eSLionel Sambuc.\" This manual is derived from one contributed to Berkeley by 7*8e5df35eSLionel Sambuc.\" Michael Rendell of Memorial University of Newfoundland. 8*8e5df35eSLionel Sambuc.\" 9*8e5df35eSLionel Sambuc.\" Redistribution and use in source and binary forms, with or without 10*8e5df35eSLionel Sambuc.\" modification, are permitted provided that the following conditions 11*8e5df35eSLionel Sambuc.\" are met: 12*8e5df35eSLionel Sambuc.\" 1. Redistributions of source code must retain the above copyright 13*8e5df35eSLionel Sambuc.\" notice, this list of conditions and the following disclaimer. 14*8e5df35eSLionel Sambuc.\" 2. Redistributions in binary form must reproduce the above copyright 15*8e5df35eSLionel Sambuc.\" notice, this list of conditions and the following disclaimer in the 16*8e5df35eSLionel Sambuc.\" documentation and/or other materials provided with the distribution. 17*8e5df35eSLionel Sambuc.\" 3. Neither the name of the University nor the names of its contributors 18*8e5df35eSLionel Sambuc.\" may be used to endorse or promote products derived from this software 19*8e5df35eSLionel Sambuc.\" without specific prior written permission. 20*8e5df35eSLionel Sambuc.\" 21*8e5df35eSLionel Sambuc.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 22*8e5df35eSLionel Sambuc.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23*8e5df35eSLionel Sambuc.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24*8e5df35eSLionel Sambuc.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 25*8e5df35eSLionel Sambuc.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26*8e5df35eSLionel Sambuc.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27*8e5df35eSLionel Sambuc.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28*8e5df35eSLionel Sambuc.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29*8e5df35eSLionel Sambuc.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30*8e5df35eSLionel Sambuc.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31*8e5df35eSLionel Sambuc.\" SUCH DAMAGE. 32*8e5df35eSLionel Sambuc.\" 33*8e5df35eSLionel Sambuc.\" @(#)tsort.1 8.3 (Berkeley) 4/1/94 34*8e5df35eSLionel Sambuc.\" 35*8e5df35eSLionel Sambuc.Dd April 1, 1994 36*8e5df35eSLionel Sambuc.Dt TSORT 1 37*8e5df35eSLionel Sambuc.Os 38*8e5df35eSLionel Sambuc.Sh NAME 39*8e5df35eSLionel Sambuc.Nm tsort 40*8e5df35eSLionel Sambuc.Nd topological sort of a directed graph 41*8e5df35eSLionel Sambuc.Sh SYNOPSIS 42*8e5df35eSLionel Sambuc.Nm 43*8e5df35eSLionel Sambuc.Op Fl l 44*8e5df35eSLionel Sambuc.Op Fl q 45*8e5df35eSLionel Sambuc.Op Ar file 46*8e5df35eSLionel Sambuc.Sh DESCRIPTION 47*8e5df35eSLionel Sambuc.Nm 48*8e5df35eSLionel Sambuctakes a list of pairs of node names representing directed arcs in 49*8e5df35eSLionel Sambuca graph and prints the nodes in topological order on standard output. 50*8e5df35eSLionel SambucInput is taken from the named 51*8e5df35eSLionel Sambuc.Ar file , 52*8e5df35eSLionel Sambucor from standard input if no file 53*8e5df35eSLionel Sambucis given. 54*8e5df35eSLionel Sambuc.Pp 55*8e5df35eSLionel SambucNode names in the input are separated by white space and there must 56*8e5df35eSLionel Sambucbe an even number of node names. 57*8e5df35eSLionel Sambuc.Pp 58*8e5df35eSLionel SambucPresence of a node in a graph can be represented by an arc from the node 59*8e5df35eSLionel Sambucto itself. 60*8e5df35eSLionel SambucThis is useful when a node is not connected to any other nodes. 61*8e5df35eSLionel Sambuc.Pp 62*8e5df35eSLionel SambucIf the graph contains a cycle (and therefore cannot be properly sorted), 63*8e5df35eSLionel Sambucone of the arcs in the cycle is ignored and the sort continues. 64*8e5df35eSLionel SambucCycles are reported on standard error. 65*8e5df35eSLionel Sambuc.Pp 66*8e5df35eSLionel SambucThe options are as follows: 67*8e5df35eSLionel Sambuc.Bl -tag -width Ds 68*8e5df35eSLionel Sambuc.It Fl l 69*8e5df35eSLionel SambucSearch for and display the longest cycle. 70*8e5df35eSLionel SambucCan take a very long time. 71*8e5df35eSLionel Sambuc.It Fl q 72*8e5df35eSLionel SambucDo not display informational messages about cycles. 73*8e5df35eSLionel SambucThis is primarily 74*8e5df35eSLionel Sambucintended for building libraries, where optimal ordering is not critical, 75*8e5df35eSLionel Sambucand cycles occur often. 76*8e5df35eSLionel Sambuc.El 77*8e5df35eSLionel Sambuc.Sh SEE ALSO 78*8e5df35eSLionel Sambuc.Xr ar 1 79*8e5df35eSLionel Sambuc.Sh HISTORY 80*8e5df35eSLionel SambucA 81*8e5df35eSLionel Sambuc.Nm 82*8e5df35eSLionel Sambuccommand appeared in 83*8e5df35eSLionel Sambuc.At v7 . 84*8e5df35eSLionel SambucThis 85*8e5df35eSLionel Sambuc.Nm 86*8e5df35eSLionel Sambuccommand and manual page are derived from sources contributed to Berkeley by 87*8e5df35eSLionel SambucMichael Rendell of Memorial University of Newfoundland. 88