tsort

The tsort program is a command line utility on Unix and Unix-like platforms, that performs a topological sort on its input. As of 2017, it is part of the POSIX.1 standard.[1]

For the Discworld location, see Discworld (world) § Tsort.

tsort
Initial release1979 (1979)
Operating systemUnix, Unix-like, V, Inferno
TypeCommand

History

According to its info[2] page, this command was initially written for providing an ordering of object files that allowed the linker to process them sequentially (each one exactly once, and in order). The FreeBSD manual page dates its appearance to Version 7 Unix.[3]

Note that the following description is describing the behaviour of the FreeBSD implementation of tsort and mentions GNU features where they may exist. Other implementations or versions may differ.

Syntax

 
tsort [-dlq] [FILE]

Options can be:

-d         turn on debugging
-l         search for and display the longest cycle.
-q         Do not display informational messages about cycles.

GNU provides the following options only:

--help     display help message and exit
--version  display version information and exit

Behavior

tsort reads its input (from the given FILE, or standard input if no input file is given or for a FILE of '-') as pairs of strings, separated by blanks, indicating a partial ordering. The output is a total ordering that corresponds to the given partial ordering.[4]

In other words: for a directed acyclic graph (used as a dependency graph), tsort produces a listing of the vertices so that for all edges 'a->b', 'a' comes before 'b' in the listing.

Examples

tsort lists the vertices of a directed acyclic graph in such an order that all ordering/direction relations are respected:

$ tsort <<EOF
> 3 8
> 3 10
> 5 11
> 7 8
> 7 11
> 8 9
> 11 2
> 11 9
> 11 10
> EOF
3
5
7
11
8
10
2
9
sample DAG

tsort can help rearranging functions in a source file so that as many as possible are defined before they are used (Interpret the following as: main() calls parse_options(), tail_file() and tail_forever(); tail_file() calls pretty_name(), and so on. The result is that dump_remainder() should be defined first, start_lines() second, etc.):

$ cat call-graph
main parse_options
main tail_file
main tail_forever
tail_file pretty_name
tail_file write_header
tail_file tail
tail_forever recheck
tail_forever pretty_name
tail_forever write_header
tail_forever dump_remainder
tail tail_lines
tail tail_bytes
tail_lines start_lines
tail_lines dump_remainder
tail_lines file_lines
tail_lines pipe_lines
tail_bytes xlseek
tail_bytes start_bytes
tail_bytes dump_remainder
tail_bytes pipe_bytes
file_lines dump_remainder
recheck pretty_name

$ # note: 'tac' reverses the order
$ tsort call-graph | tac
dump_remainder
start_lines
file_lines
pipe_lines
xlseek
start_bytes
pipe_bytes
tail_lines
tail_bytes
pretty_name
write_header
tail
recheck
parse_options
tail_file
tail_forever
main

BSD UNIX uses tsort as a common part of the typical ar & ranlib command invocations (from /usr/share/mk/bsd.lib.mk):

 lib${LIB}.a: ${OBJS} ${STATICOBJS}
    @${ECHO} building static ${LIB} library
    @${AR} cq ${.TARGET} `lorder ${OBJS} ${STATICOBJS} | tsort -q` ${ARADD}
    ${RANLIB} ${.TARGET}

Usage notes

Notice the interchangeability of white space separators so the following inputs are equivalent:

a b
b c
 
a b b
c
 
a
b b c
 
a b b c
 
a
b
b
c

Pairs of identical items indicate presence of a vertex, but not ordering (so the following represents one vertex without edges):

a a

Strictly speaking there is no topological ordering of a graph that contains one or more cycles. However tsort prints a warning and GNU tsort prints the detected cycles to standard error (lines beginning with 'tsort:'):

$ tsort <<EOF
> a b
> b c
> c a
> EOF
UX: tsort: INFORM: cycle in data
tsort: a
tsort: b
tsort: c
a
b
c
gollark: You've said so, yes. Or implied so. Said now.
gollark: You're just defining things as public services though.
gollark: Strictly, cost-spread-to-everyone, yes.
gollark: They aren't, they're specific to (some?) food.
gollark: I would prefer "some amount of free money" to "some amount of free food". The former provides me more choice about exactly what I get.

See also

References
  1. "tsort". The Open Group Base Specifications Issue 7, 2018 edition. The Open Group.
  2. https://www.gnu.org/software/coreutils/manual/html_node/tsort-background.html
  3. http://www.freebsd.org/cgi/man.cgi?query=tsort
  4. https://www.gnu.org/software/coreutils/manual/html_node/tsort-invocation.html

Further reading

manual page of tsort on

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.