はじめに
2020年10月にリリースが予定されているPython3.9で新たに加わる変更をPython3.9の新機能 (まとめ)という記事でまとめています。少し分量のありそうな話題を別記事にしていますが、これはその第二弾で、有向非巡回グラフのソートについてです。
有向非巡回グラフとトポロジカルソート
まず、ここでいうグラフは折れ線グラフとか棒グラフとかデータを視覚的に表す図表のことではなく、グラフ理論のグラフです。グラフはデータ構造の一種で、ノード（頂点）とそれらを繋ぐエッジ（枝）で構成されています。ノードやエッジに何かしらの意味をもたせることによって、関連性を持つ情報を表すことができます。
グラフにもいくつか種類があり、その最初の分かれ道がエッジに方向があるかないか。方向があるものを有向グラフ（左側）、無いものを無向グラフ（右側）といいます。
エッジはノードを繋ぐものですが、繋がれたノードの間に何かしらの主従関係的なものがあれば有向グラフを、そうではなく対等な関係であれば無向グラフを使うことができます。
そして、巡回グラフであるかどうかもポイントになります。エッジをたどっていくことで自分に戻ってくるノードがある場合は巡回グラフ、そうではないものを非巡回グラフと言います。有向でかつ非巡回の2つの特徴を持ち合わせたのが、有向非巡回グラフ (Directed Acyclic Graph: DAG)で、これが今回取り扱うグラフになります。
この有向非巡回グラフ（DAG）は色々な情報を表現するのに用いることができます。変わった例だと暗号資産のIOTAがDAGを使っています。通常の暗号資産はブロックチェーンを使っていて、一本道のDAGということができると思いますが、IOTAはそれを複数のエッジを持つDAGで繋げていく。面白いですね。
もう少し普通の応用だと依存関係のあるタスクのスケジュール問題があります。一つ一つのタスクがノードで、タスクの依存関係がエッジで表現され、例えば A → BとなっていたらAが終わるまでBは始められないという風に表していく。込み入った依存関係をもつタスクのリストがあったとしてもタスクとタスクの関係に分解していけばDAGで表現できることがわかると思います。
例えば BとCはAが終わるまで始められない。そしてDはBとCが終わるまで始められない、そういう依存関係は以下のように表されます。
より複雑な例だと、例えばこの様になります。
話が少し脱線してしまいますが、DAGを視覚化するためのツールに Graphvizというものがあります。これは、DAGをdot形式という独自のフォーマットで記述し、それを描画してPNGなどの画像形式に変換してくれるものです。面白いのは、描画のアルゴリズムがいくつか用意されていて同じ入力でもぜんぜん違う出力が得られます。
例えば上の2つ目の例をdot形式で記述するとこうなります。
digraph example {
graph [
labeljust = "c"
];
7, 5, 3, 11, 8, 2, 9, 10;
7 -> 11;
7 -> 8;
5 -> 11;
3 -> 8;
3 -> 10;
11 -> 2;
11 -> 9;
11 -> 10;
8 -> 9;
}
これをGraphvizの描画ツールで出力してみるとこれだけバリエーションができます。
面白いですね。とても同じDAGには見えませんが、全て同じdotファイルから描画されたものです。
さて、DAGで表現されたタスクの間には順序関係があるので、どの順番で片付けていけば良いのかを知りたくなります。それがスケジュール問題ですね。そのためには、依存関係が満たしながら一次元上に並べるという操作が必要で、それをトポロジカルソートと呼びます。
前置きが長くなりましたが、Python3.9では graphlibモジュールが新設されて TopologicalSorterというクラスが提供されています。これを使って、このトポロジカルソートを標準機能で行えるようになります。
TopologicalSorterを使ってみる
一番最初に示した、A,B,C,Dのノードを持つ例で試してみましょう。
>>> from graphlib import TopologicalSorter
>>> ts = TopologicalSorter()
>>> ts.add('B', 'A')
>>> ts.add('C', 'A')
>>> ts.add('D', 'B', 'C')
>>> tuple(ts.static_order())
('A', 'B', 'C', 'D')
空のソーターをTopologySorter()で作った後にノードを一つずつ追加しています。TopologySorter.add()は第一引数に登録するノード、それ以降の引数に依存関係のあるノードを羅列します。依存するノードのないノード（この場合はA）は登録を省略することができます（他のノードの登録時に依存するものとして出てくるので）。そして、TopologySorter.static_order()でソートされた結果をgeneratorで返してきます。そのままだと見にくいのでタプルに変換して表示しています。
グラフが最初から決まっている場合はコンストラクターにそれを与えて一気に作ることもできます。
>>> from graphlib import TopologicalSorter
>>> graph = {'B': {'A'}, 'C': {'A'}, 'D': {'B', 'C'}}
>>> ts = TopologicalSorter(graph)
>>> tuple(ts.static_order())
('A', 'B', 'C', 'D')
ここで、コンストラクターに与えるのは辞書型のデータで、キーがノード、値が依存するノード（の集合）になっています。複数指定するときにはここではset型を使っていますが、タプルでもリストでも良いようです。
ソートするだけならこれだけで良いのですが、もう少し細かく制御したい時のメソッドもいくつか用意されています。まずは「今現時点で実行可能なもの」。依存関係が満たされているタスクのリストになりますが、これにはget_ready()を用います。
例として先ほどの少し複雑な例を使います。
>>> from graphlib import TopologicalSorter
>>> graph = {
... 2: {11},
... 8: {7, 3},
... 9: {11, 8},
... 10: {11, 3},
... 11: {7, 5},
... }
>>> ts = TopologicalSorter(graph)
>>> ts.prepare()
>>> ts.get_ready()
(3, 7, 5)
コンストラクターでグラフの依存関係データを与えてTopologySorterを作った後に、まずは prepare()します。これはこの後の処理を行う上での前処理を行うメソッドです。ここで登録したグラフが巡回になっていないかのチェックも行っていて、巡回になっている場合には CycleErrorがでます。上の例ではこのprepare()を呼んでいませんでしたが、static_order()の中で自動で呼ばれています（実際にはgeneratorの最初の値を取り出すときに呼ばれる）。
その後にget_ready()を呼び出すと(3, 7, 5)が返ってきます。これは、グラフに含まれるノードの中で依存関係の無いものが「実行可能」としてリストアップされています。もう一度 prepare()を呼んでみると今度は ()が返ってきます。「（今の所）これ以外には無いよ」ということですね。
先ほどのグラフに色を付けて行きます。薄緑色はそのノードが実行可能であることを示します。
では、実行可能なタスクのうち5と7が終わったとしたらどうなるか？それをソーターに教えるのがdone()メソッドです。終わったタスクを引数に並べて呼び出すと内部の状態が変わります。それで再度 get_ready()を実行すると今度は (11,)が返ってきます。
>>> ts.done(5,7)
>>> ts.get_ready()
(11,)
図の方は5と7が完了したことを示すために濃い色に変更します。そして11は依存していたタスクが全て完了したので実行可能になります。上記のts.get_ready()の結果と一致しますね。
これを繰り返していくわけですが、11→3→8の順で完了にしていきましょう。
>>> ts.done(11)
>>> ts.get_ready()
(2,)
>>> ts.done(3)
>>> ts.get_ready()
(8, 10)
>>> ts.done(8)
>>> ts.get_ready()
(9,)
なおグラフの中に未実行のタスクがあるかどうかは、is_active()で調べることができます。上の状態だとまだ 2, 9, 10が未実行なので、それらを done()にする前後で is_active()の返り値が変わることがわかります。
>>> ts.is_active()
True
>>> ts.done(2, 9 ,10)
>>> ts.is_active()
False
まとめ
Python 3.9に新規追加されるgraphlibモジュールで提供されるToplogicalSorterの機能を調べて使ってみました。依存関係のあるバッチ処理とかの順番を決めたりするのに使えるかもしれないなと思いました。