.gif)
Tsort (Unix)
Encyclopedia
The tsort program is a command line utility on Unix-like
platforms, that performs a topological sort
on its input.
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).
Note that the following description is describing the behaviour of the GNU
implementation of tsort (namely version 7.4 of GNU coreutils
), other implementations or versions may differ.
Options can be:
--help display help message and exit
--version display version information and exit
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.
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.
in such an order that all ordering/direction relations are respected:
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.):
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}
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 cyclic graph. However the GNU implementation of tsort prints a particular order of vertices and prints the detected cycles to standard error (lines beginning with 'tsort:'):
$ tsort <
> b c
> c a
> EOF
tsort: -: input contains a loop:
tsort: a
tsort: b
tsort: c
a
b
c
Unix-like
A Unix-like operating system is one that behaves in a manner similar to a Unix system, while not necessarily conforming to or being certified to any version of the Single UNIX Specification....
platforms, that performs a topological sort
Topological sorting
In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that, for every edge uv, u comes before v in the ordering...
on its input.
History
According to its infoInfo (Unix)
info is a software utility which forms a hypertextual, multipage documentation and help viewer working on a command line interface, useful when there is no GUI available....
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).
Note that the following description is describing the behaviour of the GNU
GNU
GNU is a Unix-like computer operating system developed by the GNU project, ultimately aiming to be a "complete Unix-compatible software system"...
implementation of tsort (namely version 7.4 of GNU coreutils
GNU Core Utilities
The GNU Core Utilities or coreutils is a package of GNU software containing many of the basic tools, such as cat, ls, and rm, needed for Unix-like operating systems...
), other implementations or versions may differ.
Syntax
tsort [OPTION] [FILE]Options can be:
--help display help message and exit
--version display version information and exit
Behavior
tsort reads its input (from the given FILE, or standard inputStandard streams
In Unix and Unix-like operating systems , as well as certain programming language interfaces, the standard streams are preconnected input and output channels between a computer program and its environment when it begins execution...
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.
In other words: for a directed acyclic graph
Directed acyclic graph
In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...
(used as a dependency graph
Dependency graph
In mathematics, computer science and digital electronics, a dependency graph is a directed graph representing dependencies of several objects towards each other...
), 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 graphDirected acyclic graph
In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...
in such an order that all ordering/direction relations are respected:
$ tsort < > 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 |
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 |
BSD UNIX uses tsort as a common part of the typical ar
Ar (Unix)
The archiver is a Unix utility that maintains groups of files as a single archive file. Today, ar is generally used only to create and update static library files that the link editor or linker uses; it can be used to create archives for any purpose, but has been largely replaced by tar for...
& 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 |
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 cyclic graph. However the GNU implementation of tsort prints a particular order of vertices and prints the detected cycles to standard error (lines beginning with 'tsort:'):
$ tsort <
> b c
> c a
> EOF
tsort: -: input contains a loop:
tsort: a
tsort: b
tsort: c
a
b
c
See also
- Sort (Unix)Sort (Unix)sort is a standard Unix command line program that prints the lines of its input or concatenation of all files listed in its argument list in sorted order. Sorting is done based on one or more sort keys extracted from each line of input. By default, the entire input is taken as sort key...
- Make (software)
- Topological sortingTopological sortingIn computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that, for every edge uv, u comes before v in the ordering...
- List of Unix programs