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

Question

我需要一种算法来在有向图中查找所有并行路径的集合。这是我用于测试的示例的直观表示。

这是我在 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 中：非常欢迎指向任何可以帮助我实现的算法的指针。

Answer 1

如果考虑带有分支的并行路径，则此问题将是 NP 完全问题（参见 vertex-disjoint paths problem）。

但是，由于不考虑分支，问题很简单：

遍历所有顶点。
如果一个顶点有多个出边，跟随它们直到它们收敛。
如果它们收敛到同一个节点，则它们是平行路径。

伪代码：

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)

Answer 2

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

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

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

Get list of parallel paths in a directed graph

python

algorithm

directed-graph

networkx