定向樹中從一個節點到另一個節點的所有可能路徑

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是否是頂點索引列表的列表或列表清單的頂點對象本身。我認爲列表中包含索引以簡化使用調整列表。結果，返回的路徑是按照頂點索引。如果您需要這些對象，則必須將它們映射回頂點對象，或者調整代碼以追加頂點而不是索引。