Tsort (Unix)

tsort
První vydání1979 ; 43 před lety ( 1979 )
Operační systémUnix, Unix-like, V, Inferno
Platformavíceplatformní
Typ softwarustandardní UNIXová utilita či příkaz a topologický řadící algoritmus
Některá data mohou pocházet z datové položky.

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].

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.

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
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

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

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Tsort na anglické Wikipedii.

  1. Dostupné online. 
  2. Tsort background (GNU Coreutils 9.0) [online]. Dostupné online. 
  3. Dostupné online. 
  4. Dostupné online. 
  5. Kružnice (graf)

Související články

Externí odkazy