tsort.1 - sbase - suckless unix tools
(HTM) git clone git://git.suckless.org/sbase
(DIR) Log
(DIR) Files
(DIR) Refs
(DIR) README
(DIR) LICENSE
---
tsort.1 (1417B)
---
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 POSIX.1-2013.