定向树中从一个节点到另一个节点的所有可能路径

Question

我使用python binding到igraph来表示有向树。我想找到从该图中的一个节点到另一个节点的所有可能路径。不幸的是，我在igraph中找不到准备使用的函数来执行这个任务？

EDIT

上的路径

无限数目的关注我说的是该图实际上是一个有向非循环图（DAG）与单个根。它代表了一个单向的级联事件，在级联的各个级别上，可以分裂或连接在一起。正如我所说，这是一个单向图。还规定图形不包含任何循环。由于这两个原因，无限的路径列表是不可能的。

我想要做什么？

我的目标是找到从图的顶部（根部）到给定节点的所有可能路径。

Answer 1

您正在寻找有向无环图（DAG）中的一个节点与另一个节点之间的所有路径。

树总是一个DAG，但一个DAG并不总是一棵树。不同之处在于树的分支不允许加入，只能分割，而DAG的分支可以一起流动，只要不引入循环。

您的解决方案可以在"Python Patterns - Implementing Graphs."中找到find_all_paths()这需要稍微改编才能与igraph一起使用。我没有安装的igraph，但使用嘲笑，这似乎工作：

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) 

这是从文档不清楚adjlist是否是顶点索引列表的列表或列表清单的顶点对象本身。我认为列表中包含索引以简化使用调整列表。结果，返回的路径是按照顶点索引。如果您需要这些对象，则必须将它们映射回顶点对象，或者调整代码以追加顶点而不是索引。