Cesko.wiki Tsort (Unix)
Author
Albert FloresProgram tsort je nástroj příkazového řádku na platformách Unix, který provádí topologické řazení. Je součástí standardu POSIX.1 asi od roku 2017 .
Historie
Podle manuálové stránky byl tento příkaz původně napsán pro topologické řazení objektových souborů. Toto pořadí mělo umožnit linkeru je sekvenčně zpracovávat (každý přesně jednou a v přesně daném pořadí). +more Manuálová stránka FreeBSD má vzhled verze 7 Unix .
V následujícím odstavci je popsáno chování implementace tsort v distribuci FreeBSD a jsou zde zmíněny také funkce GNU. Jiné implementace nebo verze se mohou lišit.
Syntaxe
tsort [-dlq] [SOUBOR]
Přepínače podporované programem tsort v distribuci FreeBSD: -d zapnout ladění (debugging) -l vyhledat a zobrazit nejdelší cyklus. -q nezobrazovat informační zprávy o cyklech.
V implementaci GNU existují pouze následující přepínače: --help zobrazí zprávu nápovědy a skončí --version zobrazí informace o verzi a skončí
Standard POSIX nepředepisuje žádné přepínače.
Chování
tsort čte vstup buď z textového souboru nebo ze standardního vstupu (to v případě, pokud příkazu není předán žádný název souboru nebo speciální soubor pojmenovaný -). Vstup tvoří dvojice řetězců oddělených mezerami, které značí částečné uspořádání určité množiny. +more Výstupem je některé úplné uspořádání, které odpovídá podmínkám určeným zadaným částečným uspořádání.
Jinými slovy: tsort vypíše pro zadaný orientovaný acyklický graf takové pořadí vrcholů, že po zakreslení vrcholů v tomto pořadí povedou hrany jen jedním směrem. Je-li například v grafu přítomná hrana a → b, ve výstupu příkazu tsort musí být t před a.
Příklady
tsort vypisuje vrcholy orientovaného acyklického grafu v topologickém pořadí. Jednotlivé prvky grafu budou vypsány tak, že prvky budou seřazeny za sebou podle toho, v jakém pořadí je třeba je projít tak, aby byly splněny všechny závislosti:
| $ tsort 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 | +moresvg|vpravo|rám'>orientovaný acyklický graf, který tsort topologicky řadí v příkladu vlevo |
|---|
Pořadí definice funkcí
tsort je možné použít k vytvoření pořadí, ve kterém mají být funkce definovány ve zdrojovém souboru tak, aby bylo co nejvíce funkcí (ideálně všechny) deklarováno před jejich prvním použitím. V následujícím příkladu interpretujte dvojici jako volá , dvojici jako volá atd.
Z výsledku je poté zřejmé, že funkce by měla být definována jako první, druhá, atd.
| $ 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 |
|---|
Poznámka k užití tsortu
Jako oddělovač je možné použít jakoukoliv posloupnost bílých znaků. To znamená, že následující vstupy programu jsou ekvivalentní:
| a b b c | a b b c | a b b c | a b b c | a b b c |
|---|
Páry identických písmem značí přítomnost vrcholu, ale ne jeho řazení (následující vstup značí jeden vrchol bez jakékoliv hrany):
a a
V případě, kdy není možné topologické uspořádání sestrojit (proto, že existuje jeden nebo více cyklů), tsort vytiskne chybovou hlášku. GNU varianta utility tsort vytiskne seznam zjištěných cyklů v grafu (viz řádky s prefixem tsort:).
$ tsort a b > b c > c a > EOF UX: tsort: INFORM: cycle in data tsort: a tsort: b tsort: c a b c
Odkazy
Reference
Související články
Seřadit (Unix) * Make (software) * Seznam unixových příkazů * Call graph
Externí odkazy
[url=http://www. freebsd. +moreorg/cgi/man. cgi. query=tsort]FreeBSD[/url] * [url=http://man. openbsd. org/tsort. 1]OpenBSD[/url] * [url=http://netbsd. gw. com/cgi-bin/man-cgi. tsort]NetBSD[/url] * [url=http://publib. boulder. ibm. com/infocenter/pseries/v5r3/topic/com. ibm. aix. cmds/doc/aixcmds5/tsort. htm]AIX[/url] * [url=http://download. oracle. com/docs/cd/E19963-01/html/821-1461/tsort-1. html]Solaris[/url] * [url=http://h20000. www2. hp. com/bc/docs/support/SupportManual/c02280845/c02280845. pdf]HP-UX[/url] * [url=http://sourceforge. net/projects/dep-trace/]dep-trace[/url] Uspořádá základní závislosti a rozbalí vnořené. (základní: bez 2D grafického předpokladu).