在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
.它从u
的不包括u
的邻居开始递归地找到长度为n-1的所有路径.然后,它将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
为优化此效果,尤其是在有多个循环的情况下,可能值得发送一组不允许的节点.在每个嵌套调用中,它将知道不包含递归中更高层的任何节点.这将代替if u not in path
检查工作.该代码将更难以理解,但运行速度更快.
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屋!