tsort.1 (1474B)
1 .Dd February 16, 2016 2 .Dt TSORT 1 3 .Os sbase 4 .Sh NAME 5 .Nm tsort 6 .Nd topological sort 7 .Sh SYNOPSIS 8 .Nm 9 .Op Ar file 10 .Sh DESCRIPTION 11 .Nm 12 topologically sorts a graph. 13 The graph is read either from 14 .Ar file 15 or from standard input. 16 The result is not optimized for any particular usage. 17 Loops are detected and reported to standard error, but does not stop the 18 sort. 19 .Pp 20 The input is a list of edges (vertex pairs), where 21 the edge is directed from the first vertex to the 22 second vertex. 23 .Sh OPTIONS 24 None. 25 .Sh EXIT STATUS 26 .Bl -tag -width Ds 27 .It 0 28 The graph as successfully sorted. 29 .It 1 30 The graph as successfully sorted, but contained loops. 31 .It > 1 32 An error occurred. 33 .El 34 .Sh EXAMPLES 35 .Bd -literal -offset left 36 The input 37 38 a a 39 a b 40 a c 41 a c 42 a d 43 b c 44 c b 45 e f 46 47 or equivalently 48 49 a a a b a c a c a d 50 b c c b e f 51 52 represents the graph 53 54 ┌─┐ 55 ↓ │ 56 ┏━━━┓ 57 ┌──────┃ a ┃──────┐ 58 │ ┗━━━┛ │ 59 │ │ │ │ 60 ↓ ↓ ↓ ↓ 61 ┏━━━┓───→┏━━━┓ ┏━━━┓ 62 ┃ b ┃ ┃ c ┃ ┃ d ┃ 63 ┗━━━┛←───┗━━━┛ ┗━━━┛ 64 65 ┏━━━┓ ┏━━━┓ 66 ┃ e ┃───→┃ f ┃ 67 ┗━━━┛ ┗━━━┛ 68 .Ed 69 .Sh STANDARDS 70 The 71 .Nm 72 utility is compliant with the 73 .St -p1003.1-2013 74 specification.