Todas las rutas posibles de un nodo a otro en un árbol dirigido (igraph)

Utilizo el enlace de python para igraph para representar un árbol dirigido. Me gustaría encontrar todas las rutas posibles de un nodo en ese gráfico a otro. Desafortunadamente, ¿no pude encontrar una función lista para usar en igraph que realice esta tarea?

EDITAR

Las preocupaciones sobre un número infinito de caminos.

el gráfico del que estoy hablando es en realidad un gráfico acíclico dirigido (DAG) con una sola raíz. Representa una cascada unidireccional de eventos que, en varios niveles de la cascada, pueden dividirse o unirse. Como dije, este es un gráfico unidireccional. También se dispone que el gráfico no contiene ningún ciclo. Debido a estas dos razones, una lista infinita de caminos, es imposible.

¿Qué estoy tratando de hacer?

Mi objective es encontrar todas las rutas posibles que conducen desde la parte superior del gráfico (la raíz) al nodo dado.

Está buscando todas las rutas entre un nodo y otro en un gráfico acíclico dirigido (DAG).

Un árbol siempre es un DAG, pero un DAG no siempre es un árbol. La diferencia es que no se permite que las twigs de un árbol se unan, solo se dividen, mientras que las twigs de un DAG pueden fluir juntas, siempre que no se introduzcan ciclos.

Su solución se puede encontrar como find_all_paths() en “Patrones de Python – Implementación de gráficos”. Esto requiere una pequeña adaptación para usar con igraph. No tengo igraph instalado, pero al usar simulacros, esto parece funcionar:

 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) 

De la documentación no estaba claro si la lista adjunta es una lista de listas de índices de vértice o una lista de objetos de vértice en sí mismos. Supuse que las listas contenían índices para simplificar el uso de la lista auxiliar. Como resultado, las rutas devueltas están en términos de índices de vértice. Tendrá que asignarlos de nuevo a los objetos de vértice si los necesita, o adaptar el código para agregar el vértice en lugar de su índice.