"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 番目の要素か
   らアクセスできます。 これはノードのリストで、各ノードはグラフ上でリ
   ストの次のノードの直接の先行ノードになっています。 閉路であることが
   分かるように、報告されるリストの最初と最後のノードは同じです。
