“Tsort”的意思、由来-开放百科全书

词条

Tsort

释义

History
Syntax
Behavior
Examples
Usage notes
See also
References
Further reading
External links

{{lowercase|tsort}}{{Infobox Software
| name = tsort
| logo =
| screenshot =
| screenshot size =
| caption =
| developer =
| released = {{Start date and age|1979}}
| latest release version =
| latest release date =
| operating system = Unix and Unix-like
| genre = Command
| license =
| website =
}}

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

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

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 < > 3 8 > 3 10 > 5 11 > 7 8 > 7 11 > 8 9 > 11 2 > 11 9 > 11 10 > EOF 7 5 3 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: {{code|main()}} calls {{code|parse_options(), tail_file()}} and {{code|tail_forever()}}; {{code|tail_file()}} calls {{code|pretty_name()}}, and so on. The result is that {{code|dump_remainder()}} should be defined first, {{code|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

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

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 <

> a b

> b c

> c a

> EOF

UX: tsort: INFORM: cycle in data

tsort: a

tsort: b

tsort: c

References

1. ^{{cite web|title=tsort|url=http://pubs.opengroup.org/onlinepubs/9699919799/utilities/tsort.html|publisher=The Open Group|work=The Open Group Base Specifications Issue 7, 2018 edition}}
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

External links

manual page of tsort on

FreeBSD,
OpenBSD,
NetBSD,
AIX,
Solaris,
HP-UX

1 : Unix SUS2008 utilities

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。