Tsort (Unix)

From Wikipedia, the free encyclopedia

Remove ads

Program 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 [1].

Stručná fakta První vydání, Operační systém ...
Remove ads

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í).[2]. Manuálová stránka FreeBSD má vzhled verze 7 Unix [3].

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.

Remove ads

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. 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í. [4]

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 <<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
Thumb
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 main parse_options jako main() volá parse_options(), dvojici tail_file pretty_name jako tail_file() volá pretty_name() atd.

Z výsledku je poté zřejmé, že funkce dump_remainder() by měla být definována jako první, start_lines() 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
Remove ads

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ů[5]), tsort vytiskne chybovou hlášku. GNU varianta utility tsort vytiskne seznam zjištěných cyklů v grafu (viz řádky s prefixem 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
Remove ads

Odkazy

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads