sbase/tsort.1

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.