我需要一种算法来查找有向图中所有并行路径的集合。这是我用于测试的示例的直观表示。
这是我在 Python 中使用 networkx 的示例代码:
import networkx as nx
G = nx.MultiDiGraph()
# relevant part of graph to my question
G.add_edges_from([(1,2),(2,3),(3,4),(2,5),(5,6),(6,4),(4,7)])
# subordinate part of graph to my question
G.add_edges_from([(7,8),(8,9),(7,10),(10,11),(11,13),(11,12),(12,14)])
pp = get_parallel_paths(G) # -> the function I'm looking for
# pp should contain:
# pp = [[[(2,3),(3,4)],[(2,5),(5,6),(6,4)]],[...]]
# the procedure should list all sets of parallel paths
# hence the [...] indicates a possible other set of parallel paths (not in example)
这是我正在寻找的函数“get_parallel_paths”。它不必在 Python 中:非常欢迎指向任何可以帮助我实现的算法的指针。
最佳答案
有一个内置函数可以列出两个顶点之间的所有简单路径。这使用它来列出任意两个顶点之间的所有路径集:
def get_parallel_paths(G):
return [list(nx.all_simple_paths(G, i, j)) for i in G.nodes_iter() for j in G.nodes_iter() if i != j and nx.has_path(G, i, j)]
要过滤掉任何内部顶点度数大于二的路径，我们可以这样做:
def get_parallel_paths(G):
colpaths = []
for i in G.nodes_iter():
for j in G.nodes_iter():
if i == j:
continue
nbp = nobranchpaths(G, i, j)
if len(nbp) > 1:
colpaths += [nbp]
return colpaths
def nobranchpaths(G, u, v):
paths = []
for p in nx.all_simple_paths(G, u, v):
if len(p) == 2 or max(G.degree(i) for i in p[1:-1]) == 2:
paths += [p]
return paths
这仅包括存在多于一条路径的顶点对；要包含具有唯一路径的对，请将 if len(nbp) > 1: 更改为 if len(nbp):
关于python - 获取有向图中的并行路径列表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37633941/