tsort - トポロジカルソートを行う

tsortコマンドはトポロジカルソートを行うコマンドです。

トポロジカルソートはジョブのスケジューリング問題に利用されます。

トポロジカルソートとは

トポロジカルソートは、Aのジョブが終わった後にBのジョブを行うといった依存関係があるジョブを行う際に使用されます。

有向非巡回グラフ(directed acyclic graph, DAG)の各ノードを順序付けて、AがBを指すような辺がある場合、Aが先になるように並び替えていきます。
トポロジカルソートは、問題によって、解が一つではない可能性もあります。

tsortコマンドの利用例

トポロジカルソートの例

tsortコマンドは、ファイルまたは標準入力からグラフを示すファイルを読み取り、標準出力にトポロジカルソートの結果を表示します。

文字列は、要素がペアになるように書く必要があり、1つ目の要素が２つ目の要素を指すように記述します。

コマンド例

a.txt

実行結果

graph.txtの図

参考

Gnu Coreutils

Gnu Coreutils日本語版