`graphlib` --- グラフ構造を操作する機能¶

ソースコード: Lib/graphlib.py

class graphlib.TopologicalSorter(graph=None)¶

ハッシュ可能な頂点のグラフをトポロジカルソートする機能を提供します。

トポロジカル順序はグラフの頂点の線形順序で、頂点 u から頂点 v への有向辺 u-> v 全てについて、頂点 u が頂点 v よりも前にくるような順序です。例えば、グラフの頂点が実行するタスクを表し、その辺があるタスクが別のタスクよりも前に実行されなければならないという制約を表す場合、トポロジカル順序は制約を満たすタスクの実行順序のシーケンスになります。トポロジカル順序が得られるのは、グラフが有向閉路を持たない、つまり有向非巡回グラフである場合でかつその時に限ります。

もしオプションの graph 引数が与えられた場合、その値は有向非巡回グラフを表す辞書でなければならず、辞書はそのキーがノードで、その値はキーのノードの先行ノードのイテラブルとなります（言い換えると、辞書の値はそのキーのノードを指す辺を持つノードのイテラブルです）辺 add() メソッドを使うことで、さらにノードを追加することができます。

一般的に、与えられたグラフのソートの実行に必要なステップは以下のようになります:

TopologicalSorter のインスタンスをオプションの初期グラフで生成します。
さらにノードをグラフに追加します。
prepare() をグラフ上で呼び出します。
is_active() が True の間、 get_ready() によって返されたノード群をイテレートし、それらを処理します。ノードの処理が終わる都度、done() を呼び出します。

すぐにグラフのノードをソートした結果が必要で、並行性が不要な場合、便利なメソッド TopologicalSorter.static_order() を直接呼び出すことができます:

>>> graph = {"D": {"B", "C"}, "C": {"A"}, "B": {"A"}}
>>> ts = TopologicalSorter(graph)
>>> tuple(ts.static_order())
('A', 'C', 'B', 'D')

このクラスは、簡単に準備が整ったノードの並列処理を行えるよう設計されています。例えば:

topological_sorter = TopologicalSorter()

# 'topological_sorter' にノードを追加する...

topological_sorter.prepare()
while topological_sorter.is_active():
    for node in topological_sorter.get_ready():
        # ワーカースレッドやプロセスが 'task_queue' キューから
        # 処理するノードを取り出す。
        task_queue.put(node)

    # ノードの処理が終わると、ワーカーはそのノードを
    # 'finalized_tasks_queue' に入れる。
    # それによって次の処理対象を得られる。
    # 'is_active()' の定義により、この時点で 'task_queue' に入っていて
    # まだ 'done()' に渡されていないノードが少なくとも 1 つある。
    # したがって、ここでブロックする 'get()' は最終的には成功する。
    # 'done()' の呼び出し後はループの先頭に戻り、再び 'get_ready()' を呼ぶ。
    # これにより、新たに処理可能になったノードを論理的に可能な限り早く
    # 'task_queue' に入れられる。
    node = finalized_tasks_queue.get()
    topological_sorter.done(node)

add(node, *predecessors)¶

新しいノードとその先行ノードをグラフに追加します。 node と predecessors のすべての要素はハッシュ可能でなければなりません。

同じ node 引数で複数回呼び出した場合、依存関係の集合は、それまでに指定した依存関係の和集合になります。

依存先のないノードを追加することも (predecessors を指定しない場合)、同じ依存関係を 2 回指定することもできます。 predecessors に、まだ追加していないノードが含まれる場合、そのノードは自身の先行ノードを持たないものとしてグラフに自動的に追加されます。

prepare() を呼び出した後にこのメソッドを呼び出すと、ValueError を送出します。

prepare()¶

グラフの構築を完了したものとして印を付け、閉路がないか調べます。閉路が見つかると CycleError を送出しますが、get_ready() は引き続き使えるため、閉路によってそれ以上進めなくなるまで可能な限りノードを取得できます。この関数を呼び出した後はグラフを変更できず、add() でノードを追加することもできません。

static_order() または get_ready() によってソートが開始されている場合は ValueError を送出します。

バージョン 3.14 で変更: ソートが開始されていなければ、prepare() を複数回呼び出せるようになりました。以前は ValueError が送出されていました。

is_active()¶

処理を進められる場合は True、そうでなければ False を返します。閉路によって処理が妨げられておらず、TopologicalSorter.get_ready() がまだ返していない処理可能なノードがあるか、TopologicalSorter.done() で処理済みとしたノード数が TopologicalSorter.get_ready() の返したノード数より少ない場合に、処理を進められます。

このクラスの __bool__() メソッドはこの関数に処理を委ねます。そのため、次の書き方は置き換えられます。

if ts.is_active():
    ...

次のように簡単に書けます。

if ts:
    ...

前もって prepare() を呼び出さずにこの関数を呼び出すと ValueError を送出します。

done(*nodes)¶

TopologicalSorter.get_ready() が返した一連のノードを処理済みとします。これにより、nodes の各ノードの後続ノードが、それ以降の TopologicalSorter.get_ready() の呼び出しで返されるための依存条件が解消されます。

nodes のいずれかのノードが、このメソッドの以前の呼び出しですでに処理済みになっている場合や、TopologicalSorter.add() でグラフに追加されていない場合は ValueError を送出します。 prepare() を呼び出す前に呼び出した場合や、ノードがまだ get_ready() から返されていない場合も同様です。

get_ready()¶

処理の準備が整ったすべてのノードを tuple で返します。最初は先行ノードのないすべてのノードを返します。それらを TopologicalSorter.done() で処理済みとすると、以降の呼び出しでは、すべての先行ノードの処理が終わった新たなノードをすべて返します。それ以上処理を進められなくなると、空のタプルを返します。

前もって prepare() を呼び出さずにこの関数を呼び出すと ValueError を送出します。

static_order()¶

ノードをトポロジカル順序でたどるイテレータオブジェクトを返します。このメソッドを使う場合は、prepare() と done() を呼び出さないでください。このメソッドは次と等価です。

def static_order(self):
    self.prepare()
    while self.is_active():
        node_group = self.get_ready()
        yield from node_group
        self.done(*node_group)

返される具体的な順序は、グラフに要素を挿入した順序に依存する場合があります。例えば次のようになります。

>>> ts = TopologicalSorter()
>>> ts.add(3, 2, 1)
>>> ts.add(1, 0)
>>> print([*ts.static_order()])
[2, 0, 1, 3]

>>> ts2 = TopologicalSorter()
>>> ts2.add(1, 0)
>>> ts2.add(3, 2, 1)
>>> print([*ts2.static_order()])
[0, 2, 1, 3]

これは、"0" と "2" がグラフの同じ階層にあり (同じ get_ready() の呼び出しで返される)、両者の間の順序が挿入順で決まるためです。

閉路が見つかると CycleError を送出します。

Added in version 3.9.

例外¶

graphlib モジュールは次の例外クラスを定義しています。

exception graphlib.CycleError¶

処理対象のグラフに閉路がある場合に TopologicalSorter.prepare() が送出する、ValueError のサブクラスです。閉路が複数ある場合は、そのうち 1 つだけが選ばれて報告され、例外に含まれます。どれが選ばれるかは未定義です。

検出された閉路には、例外インスタンスの args 属性の 2 番目の要素からアクセスできます。これはノードのリストで、各ノードはグラフ上でリストの次のノードの直接の先行ノードになっています。閉路であることが分かるように、報告されるリストの最初と最後のノードは同じです。

`graphlib` --- グラフ構造を操作する機能¶

例外¶

目次

前のトピックへ

次のトピックへ

このページ

graphlib --- グラフ構造を操作する機能¶

例外¶

`graphlib` --- グラフ構造を操作する機能¶