Python igraph：获取有向图中所有可能的路径
Python igraph: get all possible paths in a directed graph
我正在使用 igraph (Python) 并希望获得有向图中两个节点之间的所有可能路径。我知道函数 get_all_shortest_paths，它用于最短路径，但找不到通用函数。
更新：
我的主要目标是获取这些路径中的所有节点，这样我就可以获得这些节点的子图。
我不能确定，但是在 python igraph 文档中查找了几分钟，看起来这样的函数不存在。我不再寻找，因为在我看来，此类信息并不是真正有用，至少如果我是开发人员，我不会创建它。回到问题：
首先你需要明白对于任意一个图，这样的路径的数量是无限的。您只需要一个循环，就可以创建无限数量的路径。所以为了使这个数字是有限的，它应该是 directed acyclic graph.
所以如果你有DAG，可以用DFS and recursively calculate all the paths (note that you will end up with exponential graph and most probably will not be able to find an answer in the reasonable time for even for a reasonably big graph). I was not writing the code by myself, and just googled a little bit and it looks like this guy have done what you want（基本上他是在做DFS）
from igraph import *
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)
我还没有检查它是否产生了正确的结果。
既然你在问题中提到你的最终目标是只获取这些路径中的节点而不是路径本身，我认为你甚至不必计算路径。
igraph 中的 Graph 对象有一个名为 subcomponent 的方法。默认情况下，它会为您提供与给定输入节点位于同一（弱连接）组件中的所有节点。但是，它还有一个 mode 参数。当您将 mode 设置为 "out" 时，它将为您提供从某个节点可达的所有节点。当您将 mode 设置为 "in" 时，它将为您提供可以到达某个节点的所有节点。因此，您可能需要源顶点的可到达节点集与可到达目标顶点的节点集的交集：
s=set(graph.subcomponent(source, mode="out"))
t=set(graph.subcomponent(target, mode="in"))
s.intersection(t)
这可能比计算所有路径要快得多。
In this post igraph 的作者之一 Tamás 提出了一个简单的递归解决方案。此函数 returns 没有重复的路径，因为它从可能的后续步骤集合中减去 set(path)（路径中已有的节点）（adjlist[start]，其中开始是最新添加的节点）。
我修改了这个解决方案，使其具有在两组节点之间搜索长度不超过 maxlen 的所有简单路径的功能。它 returns 路径列表：
def find_all_paths(graph, start, end, mode = 'OUT', maxlen = None):
def find_all_paths_aux(adjlist, start, end, path, maxlen = None):
path = path + [start]
if start == end:
return [path]
paths = []
if maxlen is None or len(path) <= maxlen:
for node in adjlist[start] - set(path):
paths.extend(find_all_paths_aux(adjlist, node, end, path, maxlen))
return paths
adjlist = [set(graph.neighbors(node, mode = mode)) \
for node in xrange(graph.vcount())]
all_paths = []
start = start if type(start) is list else [start]
end = end if type(end) is list else [end]
for s in start:
for e in end:
all_paths.extend(find_all_paths_aux(adjlist, s, e, [], maxlen))
return all_paths
对于此图：
import igraph
G = ig.Graph()
#ring
G.add_vertices(4)
G.add_edges([(0,1), (1,2),(2,3),(3,0)])
G = G.as_directed()
print G.is_directed()
print G
如果我应用上面的函数
喜欢
for p in find_all_paths(G,0,0):
print p
我只得到
结果 [0]，而应该有第二条路径 [0,1,2,3,0] imho
如果图中有这样的环，如何找到所有路径？
在networkx中，可以用all_simple_paths得到想要的结果：
import networkx as nx
G = nx.MultiDiGraph()
G.add_path(['a','b','c','d','a'])
G.add_path(['a','e','f','g'])
G.add_path(['a','a'])
for p in nx.all_simple_paths(G,'a','a'):
print p
结果：
['a', 'a']
['a', 'b', 'c', 'd', 'a']
如上文所述，all_simple_paths函数仅存在于networkx中，由于性能问题不适合处理超大图。有什么方法可以将 all_simple_paths 从 networkx 带到 igraph 吗？
我成功地将以下函数与 python-igraph 结合使用。
由于这是我应用程序的性能瓶颈，我想知道是否有人有想法如何进一步优化它的性能。
def find_all_paths2(G, start, end, vn = []):
""" Finds all paths between nodes start and end in graph.
If any node on such a path is within vn, the path is not returned.
!! start and end node can't be in the vn list !!
Params:
--------
G : igraph graph
start: start node index
end : end node index
vn : list of via- or stop-nodes indices
Returns:
--------
A list of paths (node index lists) between start and end node
"""
vn = vn if type(vn) is list else [vn]
#vn = list(set(vn)-set([start,end]))
path = []
paths = []
queue = [(start, end, path)]
while queue:
start, end, path = queue.pop()
path = path + [start]
if start not in vn:
for node in set(G.neighbors(start,mode='OUT')).difference(path):
queue.append((node, end, path))
if start == end and len(path) > 0:
paths.append(path)
else:
pass
else:
pass
return paths
有一个函数叫做 get_all_simple_paths(v, to=None, mode=OUT)。
也许当问题被问到时，这不是一个功能，但它完全符合你的要求。
你说：
would like to get all possible paths between two nodes in a directed graph
所以，如果图形对象是g，起始节点是source_vertex，结束节点是target_vertex，你可以得到所有可能的路径：
g.get_all_simple_paths(source_vertex, target_vertex)
我正在使用 igraph (Python) 并希望获得有向图中两个节点之间的所有可能路径。我知道函数 get_all_shortest_paths，它用于最短路径，但找不到通用函数。
更新：
我的主要目标是获取这些路径中的所有节点，这样我就可以获得这些节点的子图。
我不能确定，但是在 python igraph 文档中查找了几分钟，看起来这样的函数不存在。我不再寻找，因为在我看来，此类信息并不是真正有用，至少如果我是开发人员，我不会创建它。回到问题：
首先你需要明白对于任意一个图，这样的路径的数量是无限的。您只需要一个循环，就可以创建无限数量的路径。所以为了使这个数字是有限的，它应该是 directed acyclic graph.
所以如果你有DAG，可以用DFS and recursively calculate all the paths (note that you will end up with exponential graph and most probably will not be able to find an answer in the reasonable time for even for a reasonably big graph). I was not writing the code by myself, and just googled a little bit and it looks like this guy have done what you want（基本上他是在做DFS）
from igraph import *
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)
我还没有检查它是否产生了正确的结果。
既然你在问题中提到你的最终目标是只获取这些路径中的节点而不是路径本身，我认为你甚至不必计算路径。
igraph 中的 Graph 对象有一个名为 subcomponent 的方法。默认情况下，它会为您提供与给定输入节点位于同一（弱连接）组件中的所有节点。但是，它还有一个 mode 参数。当您将 mode 设置为 "out" 时，它将为您提供从某个节点可达的所有节点。当您将 mode 设置为 "in" 时，它将为您提供可以到达某个节点的所有节点。因此，您可能需要源顶点的可到达节点集与可到达目标顶点的节点集的交集：
s=set(graph.subcomponent(source, mode="out"))
t=set(graph.subcomponent(target, mode="in"))
s.intersection(t)
这可能比计算所有路径要快得多。
In this post igraph 的作者之一 Tamás 提出了一个简单的递归解决方案。此函数 returns 没有重复的路径，因为它从可能的后续步骤集合中减去 set(path)（路径中已有的节点）（adjlist[start]，其中开始是最新添加的节点）。
我修改了这个解决方案，使其具有在两组节点之间搜索长度不超过 maxlen 的所有简单路径的功能。它 returns 路径列表：
def find_all_paths(graph, start, end, mode = 'OUT', maxlen = None):
def find_all_paths_aux(adjlist, start, end, path, maxlen = None):
path = path + [start]
if start == end:
return [path]
paths = []
if maxlen is None or len(path) <= maxlen:
for node in adjlist[start] - set(path):
paths.extend(find_all_paths_aux(adjlist, node, end, path, maxlen))
return paths
adjlist = [set(graph.neighbors(node, mode = mode)) \
for node in xrange(graph.vcount())]
all_paths = []
start = start if type(start) is list else [start]
end = end if type(end) is list else [end]
for s in start:
for e in end:
all_paths.extend(find_all_paths_aux(adjlist, s, e, [], maxlen))
return all_paths
对于此图：
import igraph
G = ig.Graph()
#ring
G.add_vertices(4)
G.add_edges([(0,1), (1,2),(2,3),(3,0)])
G = G.as_directed()
print G.is_directed()
print G
如果我应用上面的函数
喜欢
for p in find_all_paths(G,0,0):
print p
我只得到
结果[0]，而应该有第二条路径 [0,1,2,3,0] imho
如果图中有这样的环，如何找到所有路径？
在networkx中，可以用all_simple_paths得到想要的结果：
import networkx as nx
G = nx.MultiDiGraph()
G.add_path(['a','b','c','d','a'])
G.add_path(['a','e','f','g'])
G.add_path(['a','a'])
for p in nx.all_simple_paths(G,'a','a'):
print p
结果：
['a', 'a']
['a', 'b', 'c', 'd', 'a']
如上文
我成功地将以下函数与 python-igraph 结合使用。 由于这是我应用程序的性能瓶颈，我想知道是否有人有想法如何进一步优化它的性能。
def find_all_paths2(G, start, end, vn = []):
""" Finds all paths between nodes start and end in graph.
If any node on such a path is within vn, the path is not returned.
!! start and end node can't be in the vn list !!
Params:
--------
G : igraph graph
start: start node index
end : end node index
vn : list of via- or stop-nodes indices
Returns:
--------
A list of paths (node index lists) between start and end node
"""
vn = vn if type(vn) is list else [vn]
#vn = list(set(vn)-set([start,end]))
path = []
paths = []
queue = [(start, end, path)]
while queue:
start, end, path = queue.pop()
path = path + [start]
if start not in vn:
for node in set(G.neighbors(start,mode='OUT')).difference(path):
queue.append((node, end, path))
if start == end and len(path) > 0:
paths.append(path)
else:
pass
else:
pass
return paths
有一个函数叫做 get_all_simple_paths(v, to=None, mode=OUT)。
也许当问题被问到时，这不是一个功能，但它完全符合你的要求。
你说：
would like to get all possible paths between two nodes in a directed graph
所以，如果图形对象是g，起始节点是source_vertex，结束节点是target_vertex，你可以得到所有可能的路径：
g.get_all_simple_paths(source_vertex, target_vertex)