如何在有向无环图中有效地找到由k个节点构成的所有路径？

Question

我有一个DAG，看起来像这样： Example DAG

我想提取在该图中4个节点构成的所有路径。

我期望的结果应该是这样的：

N1 - > N2 - > N3 - > N4

N1 - > N2 - > N3 - > N5

N1 - > N3 - > N4 - > N5

N2 - > N3 - > N4 - > N5

我当前的尝试看起来像这样

def path_finder(n1): 
    paths = [] 
    if DAG.has_node(n1): 
     for n2 in DAG.successors(n1): 
      for n3 in DAG.successors(n2): 
       for n4 in DAG.successors(n3): 
        paths.append([n1, n2, n3, n4]) 
    return paths 

我为每个节点调用这个函数。 DAG是一个全局变量，更具体地说它是一个networkx对象（DAG = networkx.DiGraph()）这个天真的函数很慢。有没有更有效的策略来做到这一点？

我看了一下问题20262712，但问题的作者用自己的方式自我解决。

感谢

UPDATE：

因为我无法得到任何满意的算法来解决这个问题，我结束了用我的天真功能作为一个工人，而所有的数据卸入队列并行工作。我使用pool.imap_unordered启动工作人员功能并汇总队列中的结果。它仍然很慢（5M节点需要几个小时）。我还应该提供我正在处理的平均节点度数据，因为这会影响我的工作人员运行速度。但是，我现在就把它留在外面。

Answer 1

你的问题的一部分可能是，如果你遇到一个节点u作为路径中的第二个节点，那么你做所有的计算找到所有的长度为3的路径。但是，如果你遇到u再次作为第二个节点，你重复所有这些计算。

所以尽量避免这种情况。我们会做的递归第一计算所有长度为3点的路径（这需要计算长度2个路径）

def get_paths(G, n): 
    '''returns a dict, paths, such that paths[u] is a list of all paths 
     of length n that start from u''' 
    if n == 1: #base case, return a dict so that D[u] is a 
       #list of all length 1 paths starting from u. 
       #it's a boring list. 
     return {u: [[u]] for u in G.nodes()} 
    #if we get to here n>1 (unless input was bad) 
    subpath_dict = get_paths(G,n-1) #contains all length n-1 paths, 
            #indexed by first node 
    path_dict = {} 
    for u in G: 
     path_dict[u] = [] 
     for v in G.successors(u): 
      path_dict[u].extend([[u]+subpath for subpath in subpath_dict[v]]) 
    return(path_dict) 

G=nx.DiGraph() 
G.add_path([1,2,3,4,5,6]) 
G.add_path([1,3,6,8,10]) 

path_dict = get_paths(G,4) 
path_list = [] 
for paths in path_dict.values(): 
    path_list.extend(paths) 

Answer 2

这里是返回图中的所有节点之间的给定长度的路径的功能。它在所有节点集之间进行迭代，并使用networkx.all_simple_paths来获取路径。

import networkx as nx 

g = nx.DiGraph() 

g.add_nodes_from(['A','B','C','D','E']) 

g.add_path(['A','B','C','D']) 
g.add_path(['A','B','C','E']) 
g.add_path(['A','C','D','E']) 
g.add_path(['B','C','D','D']) 

def find_paths(graph, number_nodes=4): 
    paths = [] 
    for source in graph.nodes_iter(): 
     for target in graph.nodes_iter(): 
      if not source==target: 
       p_source_target = nx.all_simple_paths(graph, 
                 source, 
                 target, 
                 cutoff=number_nodes-1) 
       paths.extend([p for p in p_source_target if len(p)==number_nodes]) 
    return paths 

find_paths(g) 
# output: 
[['B', 'C', 'D', 'E'], 
['A', 'C', 'D', 'E'], 
['A', 'B', 'C', 'E'], 
['A', 'B', 'C', 'D']] 

Answer 3

序列数的阶数为| V | * d^3，其中d是平均节点输出度。从创建图的方式来看，d是有界的。我想d不是很小（如< 5）。这意味着，对于5M节点图，有> 1G路径。

由于找到一条路径很快（它们很短），因此不确定DP类似算法是否可以提供帮助。 DP像算法一样尝试利用部分计算的数据，所以存储和检索该数据会有开销，并且可能比计算所需的部分数据的开销更大。

一个想法是算法遍历DAG在后面拓扑顺序，做两件事情：

• 节点保持从长度为3的节点开始的所有路径，
• 使用长度3打印的接班人路径所有路径的长度为4.

该方法可以使用大量内存，但可以释放一部分内存用于不是任何遍历边界节点的后继节点。

其他的想法是让简单的算法更优化。在你的解决方案中，每个节点有三个for循环。这意味着四个for循环的所有路径。请注意，每个循环都是通过节点。可能 通过遍历边来加入前两个循环。这是因为每条路径都必须以一条边开始。算法是这样的：

for n1, n2 in DAG.edges(): 
    for n3 in DAG.successors(n2): 
    for n4 in DAG.successors(n3): 
     paths.append([n1, n2, n3, n4]) 

或者也可以简单通过首先选择中间边缘：

for n2, n3 in DAG.edges(): 
    for n1, n4 in itertools.product(DAG.predecessors(n2), DAG.successors(n3)): 
    paths.append([n1, n2, n3, n4]) 

外环可以通过不选择该源节点上启动或目标节点上结束中间边缘被优化。但是在product（）方法中检测速度非常快。也许这种优化可以通过不向其他进程发送不需要的数据来提供帮助。