在 networkx 图中查找给定长度的所有路径/步行 [英] Finding all paths/walks of given length in a networkx graph

问题描述

我正在使用 networkx 并试图在图中找到所有长度为 3 的步行，特别是具有三个边的路径.我试图在 networkx 文档中找到一些关于算法的信息，但我只能找到图中最短路径的算法.如果最短路径是 14 -> 15 -> 16，我是否可以找到通过特定节点的路径长度，例如通过节点 14 -> 11 -> 12 -> 16 的路径?以下是示例图的图像:

I'm using networkx and trying to find all the walks with length 3 in the graph, specifically the paths with three edges. I tried to find some information about the algorithms in the networkx documentation but I could only find the algorithms for the shortest path in the graph. Can I find a length of a path trough specific nodes, for example a path trough nodes 14 -> 11 -> 12 -> 16 if the shortest path is 14 -> 15 -> 16? Here's an image of a graph for an example:

推荐答案

最简单的版本(我认为下面的另一个版本更快):

Simplest version (another version is below which I think is faster):

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 粘贴在每个这样的路径的前面，并返回这些路径的列表.

This takes a network G and a node u and a length n. It recursively finds all paths of length n-1 starting from neighbors of u that don't include u. Then it sticks u at the front of each such path and returns a list of those paths.

注意，每个路径都是一个有序列表.它们都从指定的节点开始.所以对于你想要的，只需围绕这个循环:

Note, each path is an ordered list. They all start from the specified node. So for what you want, just wrap a loop around this:

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

请注意，这将具有任何 a-b-c-d 路径以及反向 d-c-b-a 路径.

Note that this will have any a-b-c-d path as well as the reverse d-c-b-a path.

如果您发现列表理解"难以解释，这里有一个等效的选项:

If you find the "list comprehension" to be a challenge to interpret, here's an equivalent option:

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

为了优化这一点，特别是如果有很多周期，可能值得发送一组不允许的节点.在每个嵌套调用中，它会知道在递归中不包含任何来自更高级别的节点.如果您不在路径中 检查，这将代替 工作.代码会更难理解，但它会运行得更快.

For optimizing this, especially if there are many cycles, it may be worth sending in a set of disallowed nodes. At each nested call it would know not to include any nodes from higher up in the recursion. This would work instead of the if u not in path check. The code would be a bit more difficult to understand, but it would run faster.

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 ，然后在返回之前将其删除.

Note that I have to add u to excludeSet before the recursive call and then remove it before returning.

这篇关于在 networkx 图中查找给定长度的所有路径/步行的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！