Pythonの標準ライブラリでトポロジカルソートをする

Pythonでグラフの操作をしたい場合は、たいていnetworkxをインストールして使えば事足りる。(フローや最短路、最小全域木など)

ただし、なぜかトポロジカルソートは以下の標準ライブラリとして使用可能である。

from graphlib import TopologicalSorter

使い勝手も非常に独特である。TopologicalSorter.add("a", "b", "c")とすると、b → aとc → aのエッジがはられる。(ノードがなければ追加される。)
ts.static_order()で、トポロジカルソートの結果のジェネレータが得られる。

ts = TopologicalSorter()
ts.add("a", "b", "c")
ts.add("b", "c")
print(list(ts.static_order()))  # => ["c", "b", "a"]

辞書でグラフを構築することもできるが、この場合でも、それぞれのノードへの入力辺を持つノードを指定することになる。

graph = {"a": {"b", "c"}, "b": {"c"}}
ts = TopologicalSorter(graph)
print(list(ts.static_order()))  # => ["c", "b", "a"]

おそらくこのライブラリは、タスク関係の管理に重点を置いているのだと思われる。
実際、実行済みタスクを登録して、現在実行可能なタスクを取得するようなメソッドも実装されている。

なお、graphlibという大層な名前になっているが、現状実装されているのはTopologicalSorterのみであるため、基本的にはnetworkxを使うことになるだろう。
今後拡充されていく予定などがあるのだろうか。