tsort

Perform a topological sort consistent with a partial sort per line of input separated by blanks

$ tsort [path/to/file]

$ echo -e "[UI Backend\nBackend Database\nDocs UI]" | tsort

tsort [OPTION]... [FILE]

-h, --help
    Display help information and exit.

-v, --version
    Output version information and exit.

tsort (topological sort) is a command-line utility used to produce a linear ordering of vertices in a directed acyclic graph (DAG). It reads pairs of strings from its input, interpreting each pair as a directed edge from the first string to the second.

For example, "A B" means A must precede B in the output. The command outputs the items in an order such that if item X must precede item Y, then X appears before Y in the output. If the input contains a cycle (meaning it's not a DAG), tsort will detect it and report an error. It's commonly used in dependency management, for example, to determine the correct order for compiling files, linking libraries, or installing software packages where dependencies exist.

Input Format Specificity: tsort strictly expects input as pairs of items, separated by whitespace, with one pair per line (e.g., "A B") or a single item per line. Input must be carefully formatted.

DAG Requirement: It only works correctly on Directed Acyclic Graphs (DAGs). If the input graph contains cycles, tsort will detect them, exit with an error message, and report which elements form the cycle.

Non-Unique Order: For graphs with multiple valid topological sorts (e.g., elements with no dependencies or parallel dependencies), tsort does not guarantee a specific order among those alternatives. The exact output might depend on the implementation details or the order of input lines.

Scalability: While generally efficient for typical use cases, very large graphs might push its limits, though this is rare for simple text-based dependency tasks.

tsort reads items from input, treating whitespace as separators. It expects pairs of items on a line defining a dependency (e.g., "A B" means A must precede B). If a line contains only one item, that item is treated as a node in the graph without any explicit dependencies shown on that line. Blank lines are ignored. Multiple arguments for FILE are not typical; generally, one file or standard input is used.

The output is a list of items, one per line, in topologically sorted order. If an item appears in the output, it means all its prerequisites have already appeared. If multiple valid topological sorts exist, tsort provides one of them.

If tsort detects a cycle in the input graph (meaning a set of dependencies that forms a closed loop, making a linear ordering impossible), it will print an error message to standard error, indicating the elements involved in the cycle, and exit with a non-zero status.

tsort is a standard utility found in most Unix-like operating systems. It is part of the GNU Core Utilities, which provides essential command-line tools for GNU/Linux systems. Its core algorithm, topological sort, has been known and applied in computer science for decades, predating modern operating systems. Its presence in core utilities ensures its availability and consistency across different Linux distributions.

sort(1), make(1), graphviz (conceptual)