maux
Star on GitHub Buy me a coffee

Manual / tsort

tsort(1)

TSORT(1) General Commands Manual TSORT(1)

tsort - topological sort

tsort [ file ]

Tsort reads pairs of whitespace/newline-separated tokens from file (standard input if none is given): a pair “ a b ” means a must precede b in the output. A pair whose two tokens are IDENTICAL (“ a a ”) declares the node a without any ordering edge — the same idiom tsort(1) implementations have always used for an isolated node.

Tsort writes one node per line, in an order consistent with every edge given. Among nodes with no remaining predecessor at a given step, this implementation always picks the one that appeared FIRST in the input (GNU's own tie-break; BSD's is a different, unspecified order — there is no common oracle for this choice, so any row that depends on it is fixed by this tree's own behaviour, not a captured host run).

An odd number of tokens is an error: no ordering can be formed from an unpaired trailing token, so nothing is sorted and tsort exits 1 without printing an order at all.

A cycle (no node ever becomes free) is reported to standard error as “ tsort: cycle in data ” plus the still-unresolved node names, and the sort continues anyway by forcing the output of the first such node in table order — breaking whichever edge pointed into it, the same "one edge of the cycle broken" contract tsort(1) has always had. The exit status is 1 if this ever happened.

/usr/man/TSORT this page

make(1)

Exit status is 0 if every token paired off and no cycle was found; 1 if the input held an odd number of tokens, or a cycle was found (an order is still printed); 2 for a usage error (more than one file operand).

Capacity is fixed at build time (32 distinct tokens, 64 edges, 15 characters per token) — a graph past that silently reuses the last slot rather than growing. A detected cycle's own reported member list is whatever remains UNRESOLVED at the moment of detection, which is not necessarily the minimal cycle in a larger tangled graph.

September 15, 2026 maux