NAME

tsort — stable total ordering

SYNOPSIS

DESCRIPTION

Constructs a directed graph from the pairs of whitespace-separated node relationships provided in file (standard input stream if "-", the default), then writes all unique nodes to the standard output stream, one per line, sorted according to the total ordering described by that graph, consistently with the partial ordering of the final occurrence of nodes in the input.

An input pair in the form "a a" indicates presence of node a. An input pair in the form "a b" indicates an a → b relationship: a sorts earlier than b; this is transitive: another "b c" node means that a → b → c, i.e. a sorts earlier than b sorts earlier than c (indeed, a node sorts earlier than a different node if the latter can be reached from the former).

Edges that would cause a cycle are removed, as they can interfere with preserving the input's partial ordering.

EXIT STATUS

1 if file (the standard input stream) couldn't be read, or contained an odd amount of tokens.

EXAMPLES

The simple case

$ cat nodes
A B
A F
B C
B D
D E
$ tsort nodes
A
F
B
C
D
E

A → F
↓
B → C
↓
D
↓
E

By adding a D → A relationship, an A → B → D → A loop is created:

$ echo A B A F B C B D D E D A | tsort
tsort: -: breaking D -> A link
A
F
B
C
D
E

A → F
↑ ↓
| B → C
| ↓
|←D
  ↓
  E

This input:

$ tsort
a b c c d e
g g
f g e f
h h
^D
a
b
c
d
e
f
g
h

a  c  d  h
↓     ↓
b     e
      ↓
      f
      ↓
      g

SEE ALSO

lorder(1)

STANDARDS

Conforms to IEEE Std 1003.1-2008 (“POSIX.1”).

HISTORY

Appeared in Version 7 AT&T UNIX, fully formed, as

X/Open Portability Guide Issue 2 (“XPG2”) includes it verbatim.