11

私は networkx を使用しており、グラフ内の長さ 3 のすべてのウォーク、特に 3 つのエッジを持つパスを見つけようとしています。networkx のドキュメントでアルゴリズムに関する情報を見つけようとしましたが、グラフ内の最短パスのアルゴリズムしか見つけることができませんでした。最短パスが 14 -> 15 -> 16 の場合、特定のノードを通過するパスの長さを見つけることはできますか? たとえば、ノード 14 -> 11 -> 12 -> 16 を通過するパスは? 例のグラフのイメージを次に示します。

グラフの例

4

1 に答える 1

15

最も単純なバージョン（別のバージョンはそれ以下で、より高速だと思います）：

def findPaths(G,u,n):
    if n==0:
        return [[u]]
    paths = [[u]+path for neighbor in G.neighbors(u) for path in findPaths(G,neighbor,n-1) if u not in path]
    return paths

これはネットワークGとノードuと長さを取りますn。長さ n-1 のすべてのパスを、 をu含まない隣接パスから開始して再帰的に検索しますu。次に、そのような各パスの先頭に固執uし、それらのパスのリストを返します。

各パスは順序付きリストであることに注意してください。それらはすべて指定されたノードから始まります。したがって、必要に応じて、これをループでラップするだけです。

allpaths = []
for node in G:
    allpaths.extend(findPaths(G,node,3))

これには、任意のa-b-c-dパスと逆のd-c-b-aパスがあることに注意してください。

「リスト内包表記」を解釈するのが難しい場合は、同等のオプションを次に示します。

def findPathsNoLC(G,u,n):
    if n==0:
        return [[u]]
    paths = []
    for neighbor in G.neighbors(u):
        for path in findPathsNoLC(G,neighbor,n-1):
            if u not in path:
                paths.append([u]+path)
    return paths

これを最適化するために、特にサイクルが多い場合は、許可されていないノードのセットを送信する価値があるかもしれません。ネストされた呼び出しごとに、再帰に上位のノードを含めないことがわかります。これはif u not in pathチェックの代わりに機能します。コードを理解するのは少し難しくなりますが、実行速度は速くなります。

def findPaths2(G,u,n,excludeSet = None):
    if excludeSet == None:
        excludeSet = set([u])
    else:
        excludeSet.add(u)
    if n==0:
        return [[u]]
    paths = [[u]+path for neighbor in G.neighbors(u) if neighbor not in excludeSet for path in findPaths2(G,neighbor,n-1,excludeSet)]
    excludeSet.remove(u)
    return paths

再帰呼び出しの前に追加uしてから、戻る前に削除する必要があることに注意してください。excludeSet

于 2015-01-23T05:41:24.437 に答える