12

igraphへのpython バインディングを使用して、有向ツリーを表します。そのグラフのあるノードから別のノードへのすべての可能なパスを見つけたいと思います。残念ながら、このタスクを実行する igraph ですぐに使用できる関数を見つけることができませんでしたか?

編集

無数のパスに関する懸念

私が話しているグラフは、実際には単一のルートを持つ有向非巡回グラフ (DAG) です。これは、カスケードのさまざまなレベルで分割または結合できる一方向のイベントのカスケードを表します。先ほど言ったように、これは単方向グラフです。また、グラフにサイクルが含まれていないことも前提です。これらの 2 つの理由により、パスの無限リストは不可能です。

私は何をしようとしていますか？

私の目標は、グラフの上部 (ルート) から特定のノードにつながるすべての可能なパスを見つけることです。

4

1 に答える 1

16

有向非巡回グラフ (DAG) で、あるノードと別のノードの間のすべてのパスを探しています。

ツリーは常に DAG ですが、DAG は必ずしもツリーではありません。違いは、循環が導入されない限り、ツリーのブランチは結合できず、分割のみが許可されるのに対し、DAG のブランチは一緒に流れることができることです。

find_all_paths()あなたのソリューションは、「Python パターン - グラフの実装」のように見つけることができます。これを igraph で使用するには、少し調整が必要です。私は igraph をインストールしていませんが、モックを使用すると、これはうまくいくようです:

def adjlist_find_paths(a, n, m, path=[]):
  "Find paths from node index n to m using adjacency list a."
  path = path + [n]
  if n == m:
    return [path]
  paths = []
  for child in a[n]:
    if child not in path:
      child_paths = adjlist_find_paths(a, child, m, path)
      for child_path in child_paths:
        paths.append(child_path)
  return paths

def paths_from_to(graph, source, dest):
  "Find paths in graph from vertex source to vertex dest."
  a = graph.get_adjlist()
  n = source.index
  m = dest.index
  return adjlist_find_paths(a, n, m)

adjlist が頂点インデックスのリストのリストなのか、頂点オブジェクト自体のリストのリストなのかは、ドキュメントからは不明でした。リストには、adjlist を使用して単純化するためのインデックスが含まれていると想定しました。その結果、返されるパスは頂点インデックスに基づいています。代わりに必要な場合は、これらを頂点オブジェクトにマップし直すか、インデックスではなく頂点を追加するようにコードを調整する必要があります。

于 2010-10-19T22:27:05.107 に答える