W3C SVG

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

  1. まるさんかくしかく　Tech学習と入門ログ
  2. Python
  3. Python標準のライブラリ
  4. Python 標準ライブラリ graphlib 有向エッジのトポロジカルソート
2021-04-02

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

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 <— A かつ C <— Dのノードという事になります。

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

参考