Python 標準ライブラリ graphlib 有向エッジのトポロジカルソート

前後順序のある有向エッジのトポロジカルソート
(例えば、前工程のあるタスクの順序の解決等)を行えるライブラリです。

graphlibの定義

次のような矢印のあるグラフ

graph LR
    A --> C
    B --> C
    B --> D
    C --> E
    D --> E

に対応するTopologicalSorterのインスタンスは以下で定義できます。

import graphlib

# TopologicalSorter(graph=None) graph:はノードとその先行ノードの辞書
graph = {'E': {'C', 'D'}, 'D': {'B'}, 'C': {'A', 'D'}}
ts = graphlib.TopologicalSorter(graph)

あるいはaddでも指定できます。

ts = graphlib.TopologicalSorter()

# add(node, *predecessors) node:ノード, predecessors:先行ノード
ts.add('C', 'A', 'D')
ts.add('D', 'B')
ts.add('E', 'C', 'D')

辞書{'C': {'A', 'D'}や引数('C', 'A', 'D')は
C

graphlibのメソッド

graphlibのメソッドは以下があります。

• add(node, *predecessors) ノードnodeと先行ノードpredecessorsをグラフに追加
• prepare() グラフの定義を終了し、循環がないかチェック
• is_active() ノードが全てマークされているかの判定
• done(*nodes) ノードnodesにマーク
• get_ready() マーク可能なノードを取得
• static_order() マーク可能な順序でノードを取得

これらを使って矢印で先行しているノードから順番にマーキングを行うことができます。

graphlibメソッドの使用例

以下ノードを順番にマークする流れです。

まずグラフを準備します。

graph = {'E': {'C', 'D'}, 'D': {'B'}, 'C': {'A', 'B'}}
ts = graphlib.TopologicalSorter(graph)

ts.prepare()

graph LR
    A --> C
    B --> C
    B --> D
    C --> E
    D --> E

最初にマークできるのは'A'と'B'のノード。(※以降マーク可能なノードを薄い黄色、マークしたノードを濃い黄色にします)

ts.is_active() #= > True
ts.get_ready() # => ('B', 'A')
ts.get_ready() # => () 1回取得すると同じノードは2回は取得されない
ts.is_active() #= > True

graph LR
    A:::mark --> C
    B:::mark --> C
    B --> D
    C --> E
    D --> E
    classDef mark fill:lightyellow,stroke:black,stroke-width:1px,color:black,background-color:lightyellow;

Aにマークを行う。

ts.done('A')
ts.get_ready() # => ()
ts.is_active() #= > True

graph LR
    A:::done --> C
    B:::mark --> C
    B --> D
    C --> E
    D --> E
    classDef mark fill:lightyellow,stroke:black,stroke-width:1px,color:black,background-color:lightyellow;
    classDef done fill:gold,stroke:black,stroke-width:1px,color:black,background-color:gold;

Bにマークを行う。

ts.done('B')
ts.get_ready() # => ('D', 'C')
ts.is_active() #= > True

graph LR
    A:::done --> C
    B:::done --> C
    B --> D
    C:::mark --> E
    D:::mark --> E
    classDef mark fill:lightyellow,stroke:black,stroke-width:1px,color:black,background-color:lightyellow;
    classDef done fill:gold,stroke:black,stroke-width:1px,color:black,background-color:gold;

Cにマークを行う。

ts.done('C')
ts.get_ready() # => ()
ts.is_active() #= > True

graph LR
    A:::done --> C
    B:::done --> C
    B --> D
    C:::done --> E
    D:::mark --> E
    classDef mark fill:lightyellow,stroke:black,stroke-width:1px,color:black,background-color:lightyellow;
    classDef done fill:gold,stroke:black,stroke-width:1px,color:black,background-color:gold;

Dにマークを行う。

ts.done('D')
ts.get_ready() # => ('E',)
ts.is_active() #= > True

graph LR
    A:::done --> C
    B:::done --> C
    B --> D
    C:::done --> E:::mark
    D:::done --> E
    classDef mark fill:lightyellow,stroke:black,stroke-width:1px,color:black,background-color:lightyellow;
    classDef done fill:gold,stroke:black,stroke-width:1px,color:black,background-color:gold;

Eにマークを行う。

ts.done('E')
ts.get_ready() # => ()
ts.is_active() #= > False マーク終了

graph LR
    A:::done --> C
    B:::done --> C
    B --> D
    C:::done --> E:::done
    D:::done --> E
    classDef done fill:gold,stroke:black,stroke-width:1px,color:black,background-color:gold;

より一般的な流れ

graph = {'E': {'C', 'D'}, 'D': {'B'}, 'C': {'A', 'B'}}
ts = graphlib.TopologicalSorter(graph)

ts.prepare()
while ts.is_active():
    ready_nodes = ts.get_ready()
    ts.done(*ready_nodes)
    print(ready_nodes)

#=>
# ('B', 'A')
# ('D', 'C')
# ('E',)

static_orderで実行可能な順序を取得

graph = {'E': {'C', 'D'}, 'D': {'B'}, 'C': {'A', 'B'}}
ts = graphlib.TopologicalSorter(graph)
list(ts.static_order())
# => ['B', 'A', 'D', 'C', 'E']