3

グラフ G、ノード n、長さ L が与えられた場合、n から離れた長さ L のすべての (非巡回) パスを収集したいと思います。

これにアプローチする方法について何か考えはありますか？

今では、私のグラフは networkx.Graph インスタンスですが、igraph が推奨されるかどうかはあまり気にしません。

どうもありがとう！

4

5 に答える 5

6

この問題にアプローチする (そして完全に解決する) 非常に簡単な方法は、グラフの隣接行列Aを使用することです。A^Lの(i,j)番目の要素は、長さLのノードiとjの間のパスの数です。したがって、iをnに固定したまますべてのjにわたってこれらを合計すると、長さLのノードnから発せられるすべてのパスが得られます。

残念ながら、これは循環パスもカウントします。幸いなことに、これらは要素から見つけることができるA^L(n,n)ので、それを差し引くだけです。

したがって、最終的な答えは次のとおり Σj{A^L(n,j)} - A^L(n,n)です。

注意点: ノード 1 から長さ 5 のパスを探しているとします。この計算では、 のよう1-2-3-2-4に内側に小さなサイクルがあるパスもカウントされます。その長さは、表示方法に応じて 5 または 4 になります。それ。

于 2012-08-04T16:45:10.007 に答える
2

Lance Helsten の優れた回答を拡張したいと思います。

深さ制限検索は、特定の深さ (長さ L と呼んでいるもの) 内の特定のノードを検索し、それが見つかると停止します。彼の回答のwikiリンクの疑似コードを見ると、次のことがわかります。

DLS(node, goal, depth) {
  if ( depth >= 0 ) {
    if ( node == goal )
      return node

    for each child in expand(node)
      DLS(child, goal, depth-1)
  }
}

ただし、あなたの場合、ノードから長さ L のすべてのパスを探しているので、どこにも止まらないでしょう。したがって、疑似コードを次のように変更する必要があります。

DLS(node, depth) {
    for each child in expand(node) {
      record paths as [node, child]
      DLS(child, depth-1)
    }
}

DLS の連続するネストからすべての単一リンク パスを記録し終わったら、それらの積を取得してパス全体を取得します。これらの数は、ノードから始まる必要な深さのパスの数を示します。

于 2012-08-04T16:29:59.670 に答える
1

このソリューションは効率の面で改善される可能性がありますが、非常に短いようで、networkx 機能を利用しています。

G = nx.complete_graph(4)
n =  0
L = 3
result = []
for paths in (nx.all_simple_paths(G, n, target, L) for target in G.nodes_iter()):
    print(paths)
    result+=paths
于 2012-08-04T16:47:02.800 に答える
1

深さ制限検索 ( http://en.wikipedia.org/wiki/Depth-limited_search ) を使用して、パス上にあるときにサイクルを検出するために訪問したノードのセットを保持します。たとえば、ノード n からすべてのノードと長さ L のツリーを構築し、ツリーを剪定できます。

これを行うためにグラフアルゴリズムを簡単に検索しましたが、何も見つかりませんでした。グラフ アルゴリズムのリスト ( http://en.wikipedia.org/wiki/Category:Graph_algorithms ) には、探しているものが含まれている可能性があります。

于 2012-08-04T16:06:04.940 に答える