DEV Community

loading...

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

maru3kaku4kaku profile image maru3kaku4kaku Originally published at marusankakusikaku.jp ・2 min read

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

graphlibの定義

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

graph LR
    A --> C
    B --> C
    B --> D
    C --> E
    D --> E
Enter fullscreen mode Exit fullscreen mode

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

import graphlib

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

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

ts = graphlib.TopologicalSorter()

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

辞書{'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()
Enter fullscreen mode Exit fullscreen mode
graph LR
    A --> C
    B --> C
    B --> D
    C --> E
    D --> E
Enter fullscreen mode Exit fullscreen mode

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

ts.is_active() #= > True
ts.get_ready() # => ('B', 'A')
ts.get_ready() # => () 1回取得すると同じノードは2回は取得されない
ts.is_active() #= > True
Enter fullscreen mode Exit fullscreen mode
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;
Enter fullscreen mode Exit fullscreen mode

Aにマークを行う。

ts.done('A')
ts.get_ready() # => ()
ts.is_active() #= > True
Enter fullscreen mode Exit fullscreen mode
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;
Enter fullscreen mode Exit fullscreen mode

Bにマークを行う。

ts.done('B')
ts.get_ready() # => ('D', 'C')
ts.is_active() #= > True
Enter fullscreen mode Exit fullscreen mode
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;
Enter fullscreen mode Exit fullscreen mode

Cにマークを行う。

ts.done('C')
ts.get_ready() # => ()
ts.is_active() #= > True
Enter fullscreen mode Exit fullscreen mode
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;
Enter fullscreen mode Exit fullscreen mode

Dにマークを行う。

ts.done('D')
ts.get_ready() # => ('E',)
ts.is_active() #= > True
Enter fullscreen mode Exit fullscreen mode
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;
Enter fullscreen mode Exit fullscreen mode

Eにマークを行う。

ts.done('E')
ts.get_ready() # => ()
ts.is_active() #= > False マーク終了
Enter fullscreen mode Exit fullscreen mode
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;
Enter fullscreen mode Exit fullscreen mode

より一般的な流れ

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',)
Enter fullscreen mode Exit fullscreen mode

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

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

Discussion (0)

pic
Editor guide