Todas las rutas de longitud L desde el nodo n usando python

Dado un gráfico G, un nodo n y una longitud L, me gustaría recostackr todas las rutas (no cíclicas) de longitud L que salen de n.

¿Tienes alguna idea sobre cómo abordar esto?

Por ahora, mi gráfico es una instancia de networkx.Graph, pero realmente no me importa si, por ejemplo, se recomienda igraph.

¡Muchas gracias!

Solo me gustaría ampliar la excelente respuesta de Lance Helsten:

La búsqueda de profundidad limitada busca un nodo en particular dentro de una cierta profundidad (lo que usted llama la longitud L), y se detiene cuando lo encuentra. Si echa un vistazo al pseudocódigo en el enlace wiki en su respuesta, entenderá esto:

DLS(node, goal, depth) { if ( depth >= 0 ) { if ( node == goal ) return node for each child in expand(node) DLS(child, goal, depth-1) } } 

Sin embargo, en su caso, mientras busca todas las rutas de longitud L desde un nodo, no se detendrá en ninguna parte. Entonces el pseudocódigo debe ser modificado para:

 DLS(node, depth) { for each child in expand(node) { record paths as [node, child] DLS(child, depth-1) } } 

Una vez que haya terminado de grabar todas las rutas de enlace único de nidos sucesivos de DLS, simplemente tome un producto de ellos para obtener la ruta completa. El número de estos le proporciona el número de rutas de la profundidad requerida a partir del nodo.

Una forma muy simple de abordar (y resolver por completo) este problema es usar la matriz de adyacencia A del gráfico. El (i, j) elemento th de A ^ L es el número de rutas entre los nodos i y j de longitud L. Por lo tanto, si los sums sobre todos j manteniendo i fijo en n , obtendrás todas las rutas que emanan del nodo n de longitud L.

Lamentablemente esto también contará los caminos cíclicos. Estos, felizmente, se pueden encontrar en el elemento A^L(n,n) , así que reste eso.

Entonces su respuesta final es: Σj{A^L(n,j)} - A^L(n,n) .

Advertencia: diga que está buscando rutas de longitud 5 desde el nodo 1: este cálculo también contará la ruta con pequeños ciclos en el interior como 1-2-3-2-4 , cuya longitud es 5 o 4, dependiendo de cómo Elige verlo, así que ten cuidado con eso.

Use una búsqueda de profundidad limitada ( http://en.wikipedia.org/wiki/Depth-limited_search ) donde mantiene un conjunto de nodos visitados para la detección de un ciclo cuando se encuentra en una ruta. Por ejemplo, puede construir un árbol desde su nodo n con todos los nodos y la longitud de L y luego podar el árbol.

Hice una búsqueda rápida de algoritmos gráficos para hacer esto, pero no encontré nada. Hay una lista de algoritmos de gráficos ( http://en.wikipedia.org/wiki/Category:Graph_algorithms ) que pueden tener justo lo que está buscando.

Esta solución podría mejorarse en términos de eficiencia, pero parece muy breve y hace uso de la funcionalidad networkx:

 G = nx.complete_graph(4) n = 0 L = 3 result = [] for paths in (nx.all_simple_paths(G, n, target, L) for target in G.nodes_iter()): print(paths) result+=paths 

Aquí hay otra implementación (bastante ingenua) que se me ocurrió después de leer las respuestas aquí:

 def findAllPaths(node, childrenFn, depth, _depth=0, _parents={}): if _depth == depth - 1: # path found with desired length, create path and stop traversing path = [] parent = node for i in xrange(depth): path.insert(0, parent) if not parent in _parents: continue parent = _parents[parent] if parent in path: return # this path is cyclic, forget yield path return for nb in childrenFn(node): _parents[nb] = node # keep track of where we came from for p in findAllPaths(nb, childrenFn, depth, _depth + 1, _parents): yield p graph = { 0: [1, 2], 1: [4, 5], 2: [3, 10], 3: [8, 9], 4: [6], 5: [6], 6: [7], 7: [], 8: [], 9: [], 10: [2] # cycle } for p in findAllPaths(0, lambda n: graph[n], depth=4): print(p) # [0, 1, 4, 6] # [0, 1, 5, 6] # [0, 2, 3, 8] # [0, 2, 3, 9]