22921a859f
Fix "new sentence, new line" warnings throughout so that formatters can produce correct spacing between sentences. join.1 Remove unnecessary Ns macros. These are not necessary for delimeters, which get special treatment. xinstall.1 Fix date in manual. The contents were last modified on 2016-12-03, so use that instead of the invalid date. grep.1 Fix escape sequence for `\<` and `\>`. ed.1 Remove spurious `\\n` escape for the null-command.
75 lines
1.4 KiB
Groff
75 lines
1.4 KiB
Groff
.Dd 2016-02-16
|
|
.Dt TSORT 1
|
|
.Os sbase
|
|
.Sh NAME
|
|
.Nm tsort
|
|
.Nd topological sort
|
|
.Sh SYNOPSIS
|
|
.Nm
|
|
.Op Ar file
|
|
.Sh DESCRIPTION
|
|
.Nm
|
|
topologically sorts a graph.
|
|
The graph is read either from
|
|
.Ar file
|
|
or from standard input.
|
|
The result is not optimized for any particular usage.
|
|
Loops are detected and reported to standard error, but does not stop the
|
|
sort.
|
|
.Pp
|
|
The input is a list of edges (vertex pairs), where
|
|
the edge is directed from the first vertex to the
|
|
second vertex.
|
|
.Sh OPTIONS
|
|
None.
|
|
.Sh EXIT STATUS
|
|
.Bl -tag -width Ds
|
|
.It 0
|
|
The graph as successfully sorted.
|
|
.It 1
|
|
The graph as successfully sorted, but contained loops.
|
|
.It > 1
|
|
An error occurred.
|
|
.El
|
|
.Sh EXAMPLES
|
|
.Bd -literal -offset left
|
|
The input
|
|
|
|
a a
|
|
a b
|
|
a c
|
|
a c
|
|
a d
|
|
b c
|
|
c b
|
|
e f
|
|
|
|
or equivalently
|
|
|
|
a a a b a c a c a d
|
|
b c c b e f
|
|
|
|
represents the graph
|
|
|
|
┌─┐
|
|
↓ │
|
|
┏━━━┓
|
|
┌──────┃ a ┃──────┐
|
|
│ ┗━━━┛ │
|
|
│ │ │ │
|
|
↓ ↓ ↓ ↓
|
|
┏━━━┓───→┏━━━┓ ┏━━━┓
|
|
┃ b ┃ ┃ c ┃ ┃ d ┃
|
|
┗━━━┛←───┗━━━┛ ┗━━━┛
|
|
|
|
┏━━━┓ ┏━━━┓
|
|
┃ e ┃───→┃ f ┃
|
|
┗━━━┛ ┗━━━┛
|
|
.Ed
|
|
.Sh STANDARDS
|
|
The
|
|
.Nm
|
|
utility is compliant with the
|
|
.St -p1003.1-2013
|
|
specification.
|