在有向图中获取并行路径列表

Question

在有向图中获取并行路径列表

3

我需要一个算法来查找有向图中所有平行路径的集合。这里是一个我用于测试的示例的可视化表示。

这是我使用networkx编写的Python示例代码：

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 的：任何能帮助我实现的算法指针都非常欢迎。

- user6423856

我改变了我的问题：我正在寻找并行路径（每个路径由一个或多个边组成）。 - user6423856

进一步澄清：如果在您的示例中，“9”和“14”是同一个顶点，那么“[7,10,11,12,9]”和“[7,8,9]”是否被认为是“平行”的？也就是说，分支会打断您的“平行”定义吗？ - Kittsil

@Kittsil 考虑到无法出现分支，因此如果9和14是相同的节点，则您提到的路径不被视为平行路径。顺便说一下：这个学科是电力网络，平行路径是为了增加网络段的功率容量而添加的。在这些平行路径上不应该出现分支。 - user6423856

这里的“parallel”一词是否有任何意义，还是你只是在寻找两个顶点之间的路径集？ - Nick Matteo

因此，对于每一对顶点 u 和 v，您想要一个从 u 到 v 的所有路径列表。单词“parallel”在这里通常不使用。 - Nick Matteo

显示剩余2条评论

2个回答

3

有一个内置函数可以列出两个顶点之间的所有简单路径。使用它来列出任意两个顶点之间所有路径的集合：

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):

- Nick Matteo

这确实可能是解决方案的一部分。正如Kittsil在原问题的最后一条评论中写到的那样：我将不得不过滤输出，仅包含两个顶点之间不同分支的路径（在示例中为2和4）。我也会研究这个问题。 - user6423856

要获取两个给定顶点之间的路径，可以使用 nx.all_simple_paths(G, 2, 4)。如果您想强制所有内部顶点具有度数为二，则需要像Kittsil那样的方法；没有内置函数具有这样的约束条件。 - Nick Matteo

@theej 或者说，现在我想起来了，只需过滤掉任何具有内部分支顶点的路径即可。我更新了我的答案。 - Nick Matteo

你做得很好。非常感谢。 - user6423856

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Kittsil · Accepted Answer

如果考虑到并行且有分支的路径，则此问题将是NP完全问题 (参见顶点不相交路径问题)。

然而，由于没有考虑支流，因此这个问题很简单：

循环所有顶点。
如果一个顶点有多个出边，请跟随它们直到汇合。
如果它们汇合到同一节点，则它们是平行路径。

伪代码：

allParallelPaths = []

#loop over all vertices to find ones that split
foreach(vertices as v)
  if(out-degree(v) > 1) 

    #store every eventual target and the paths that got there
    destinations = new Map()
    foreach(v.out as e)
      path = [e]

      #stop at any vertex that has non-one in- or out-degree
      while(in-degree(e.target) == 1 && out-degree(e.target) == 1)
        e = e.target.out[0]
        path.push(e)

      #make a list of paths that reached the destination
      if(empty(destinations[e.target]))
        destinations[e.target] = []
      destinations[e.target].push(path)

    foreach(destinations as dest)
      if(dest.size > 1)
        allParallelPaths.push(dest)