Ruta entre dos nodos

Estoy usando networkx para trabajar con gráficos. Tengo un gráfico bastante grande (tiene cerca de 200 nodos) e bash encontrar todas las rutas posibles entre dos nodos. Pero, según tengo entendido, networkx solo puede encontrar el camino más corto. ¿Cómo puedo obtener no solo el camino más corto, sino todos los caminos posibles?

UPD: la ruta puede contener cada nodo solo una vez.

UPD2: Necesito algo como la función find_all_paths (), que se describe aquí: python.org/doc/essays/graphs.html Pero esta función no funciona bien con un gran número de nodos y edged = (

igraph , otro módulo de gráficos para Python puede calcular todas las rutas más cortas entre un par de nodos dado. Calcular todos los caminos no tiene sentido ya que tiene infinitos de esos caminos.

Un ejemplo para calcular todas las rutas más cortas del vértice 0:

>>> from igraph import Graph >>> g = Graph.Lattice([10, 10], circular=False) >>> g.get_all_shortest_paths(0) [...a list of 3669 shortest paths starting from vertex 0...] 

Si tiene igraph 0.6 o posterior (esta es la versión de desarrollo en el momento de escribir), también puede restringir el resultado de get_all_shortest_paths a un vértice final dado:

 >>> g.get_all_shortest_paths(0, 15) [[0, 1, 2, 3, 4, 14, 15], [0, 1, 2, 12, 13, 14, 15], [0, 10, 11, 12, 13, 14, 15], [0, 1, 11, 12, 13, 14, 15], [0, 1, 2, 3, 13, 14, 15], [0, 1, 2, 3, 4, 5, 15]] 

Por supuesto hay que tener cuidado; por ejemplo, suponga que tiene un gráfico de cuadrícula de 100 x 100 (que puede generarse fácilmente mediante Graph.Lattice([100, 100], circular=False) en igraph). El número de rutas más cortas que van desde el nodo superior izquierdo al nodo inferior derecho es igual al número de posibilidades para elegir 100 elementos de 200 (prueba: la longitud de la ruta más corta tiene 200 bordes, 100 de los cuales irán “horizontalmente” en la cuadrícula y 100 de los cuales irán “verticalmente”). Es probable que esto no se ajuste a su memoria, por lo que incluso calcular los caminos más cortos entre estos dos nodos no es realmente factible aquí.

Si realmente necesita todas las rutas entre dos nodos, puede volver a escribir la función dada en la página web que mencionó usando igraph, que probablemente sea más rápida que una solución de Python pura, ya que el núcleo de igraph se implementa en C:

 def find_all_paths(graph, start, end, path=[]): path = path + [start] if start == end: return [path] paths = [] for node in set(graph.neighbors(start)) - set(path): paths.extend(find_all_paths(graph, node, end, path)) return paths 

Se puede optimizar más convirtiendo el gráfico en una representación de lista de adyacencia primero, ya que ahorraría llamadas repetidas a graph.neighbors :

 def find_all_paths(graph, start, end): def find_all_paths_aux(adjlist, start, end, path): path = path + [start] if start == end: return [path] paths = [] for node in adjlist[start] - set(path): paths.extend(find_all_paths_aux(adjlist, node, end, path)) return paths adjlist = [set(graph.neighbors(node)) for node in xrange(graph.vcount())] return find_all_paths_aux(adjlist, start, end, []) 

Edición : se corrigió el primer ejemplo para trabajar también en igraph 0.5.3, no solo en igraph 0.6.

Este realmente funciona con networkx, y es no recursivo, lo que puede ser bueno para gráficos grandes.

 def find_all_paths(graph, start, end): path = [] paths = [] queue = [(start, end, path)] while queue: start, end, path = queue.pop() print 'PATH', path path = path + [start] if start == end: paths.append(path) for node in set(graph[start]).difference(path): queue.append((node, end, path)) return paths 

El algoritmo de Dijkstra buscará la ruta más corta de una manera similar a una amplia primera búsqueda (sustituye una cola de prioridad ponderada por profundidad en el gráfico para la cola ingenua de un BFS). Podría extenderlo de forma bastante trivial para producir las rutas más cortas en ‘N’ si necesita un número de alternativas, aunque si necesita que las rutas sean sustancialmente diferentes (por ejemplo, la progtwigción de las rutas de las camionetas de seguridad) es posible que deba ser más inteligente al seleccionar Caminos que son significativamente diferentes entre sí.