Wszystkie możliwe ścieżki z jednego węzła do drugiego w drzewie skierowanym (igraph)

Question

Używam python binding do igraph do reprezentowania skierowanego drzewa. Chciałbym znaleźć wszystkie możliwe ścieżki z jednego węzła na tym wykresie do innego. Niestety, nie mogłem znaleźć funkcji gotowej do użycia w pracy, która wykonuje to zadanie?

EDIT

Obawy o nieskończonej liczbie ścieżek

wykres mówię jest w rzeczywistości skierowany graf acykliczny (DAG) z jednego korzenia. Reprezentuje jednokierunkową kaskadę zdarzeń, które na różnych poziomach kaskady mogą się dzielić lub łączyć. Jak już powiedziałem, jest to wykres jednokierunkowy. Przewiduje się również, że wykres nie zawiera żadnych cykli. Z tych dwóch powodów nieskończona lista ścieżek jest niemożliwa.

Co ja próbuję zrobić?

Moim celem jest znalezienie wszystkich możliwych ścieżek prowadzących od wierzchołka wykresu (korzenia) do danego węzła.

Answer 1

Poszukujesz wszystkich ścieżek między węzłem a innym w ukierunkowanym wykresie acyklicznym (DAG).

Drzewo jest zawsze DAG, ale DAG nie zawsze jest drzewem. Różnica polega na tym, że gałęzie drzewa nie mogą się łączyć, a jedynie dzielić, podczas gdy gałęzie DAG mogą płynąć razem, o ile nie wprowadzono żadnych cykli.

Twój roztwór można znaleźć pod numerem find_all_paths() w "Python Patterns - Implementing Graphs." Wymaga to niewielkiej adaptacji do użycia z igraph. Nie mam zainstalowane igraph, ale używając mocks, to wydaje się działać:

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) 

To było jasne od dokumentacji czy adjlist jest lista list indeksów wierzchołków lub listę liście z wierzchołków obiektów siebie . Zakładałem, że listy zawierają indeksy, aby uprościć korzystanie z listy kontrolnej. W rezultacie zwrócone ścieżki są pod względem indeksów wierzchołków. Będziesz musiał odwzorować te z powrotem na obiekty wierzchołków, jeśli potrzebujesz ich zamiast tego, lub dostosuj kod, aby dodać wierzchołek zamiast indeksu.