NAME

ptsort — Prioritized topological sort

SYNOPSIS

DESCRIPTION

The ptsort utility takes a directed acyclic graph of nodes as input and outputs the nodes in topological order. Unlike tsort(1), the ptsort utility allows nodes to be given a numeric priority. Priorities are propagated along edges so that each node's priority is greater than the priority of all its successors. Thus, it is possible to boost a specific node so that it, and all its predecessors, will be listed ahead of other unrelated nodes.

The following options are available:

-D

Sort the output by depth first instead of priority first.

-d

Include each node's depth in the output.

-P

Print all nodes with the same priority (or the same depth if -D was specified) on the same line. Can be combined with -d if and only if -D is also specified, and with -p if and only if it is not.

-p

Include each node's priority in the output.

-q

Quiet mode. Do not warn about cycles in the input.

-s

Strict mode. Cycles in the input will cause ptsort to terminate with an exit code of 3.

-v

Verbose mode. Show detailed information while building and traversing the graph.

The ptsort utility takes its input either from the files listed on the command line or, if no files were specified, from the standard input. All input is read into the same graph before processing.

Each input line contains either two names or a name and a decimal integer, separated by any amount of whitespace. Any amount of leading or trailing whitespace is permitted. Names are arbitrary non-empty sequences of up to 255 printable, non-whitespace ASCII characters. It is strictly speaking possible, but not a good idea, for a node's name to consist entirely of digits.

If the line contains two names, the effect is to insert a directed edge into the graph going from the first (predecessor) node to the second (successor) node. Either or both nodes are created if they do not already exist. If both names are identical, no edge is inserted, but the node is still created unless it already exists.

If the line contains a name and a number, the effect is to raise the priority of that node to the given number, unless it is already higher. The node will be created if it does not already exist.

Blank lines in the input are ignored.

Any error in the input will cause ptsort to print an error message which includes the offending line and terminate with an exit code of 2.

If no error occurred, the ptsort utility ouputs one line for each node in the graph, consisting of the node's name optionally preceded by its depth (if the -d option was specified) and / or priority (if the -p option was specified). By default, the list is sorted in decreasing order of priority, then depth, then name. If the -D option was specified, it is sorted in decreasing order of depth, then priority, then name.

DIAGNOSTICS

If an error occurred, the ptsort utility exits with one of the following codes:

1

An error occurred while opening or reading from an input file or while trying to allocate memory.

2

A syntax error was encountered in the input.

3

A cycle was detected while running in strict mode.

Otherwise, it exits with code 0.

SEE ALSO

tsort(1)

AUTHORS

The ptsort utility and this manual page were written by Dag-Erling Smørgrav <des@des.no>.

BUGS

The ptsort utility uses a completely different algorithm than the similar tsort(1) and may therefore produce different (but topologically equivalent) output when given the same input.

The ptsort utility should probably have been named klatch, but the author has no imagination or appreciation for the literary arts.