Ruta entre dos nodos

Question

Estoy usando networkx para trabajar con gráficos. Tengo un gráfico bastante grande (está cerca de 200 nodos) y trato de encontrar todos los caminos 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 así como find_all_paths() función, se describe aquí: python.org/doc/essays/graphs.html Pero esta función no funciona bien con gran número de nodos y bordeado = (

Answer 1

igraph, otro módulo de gráfico para Python puede calcular todas las rutas más cortas entre un par de nodos determinado. Calcular todas las rutas no tiene sentido ya que tiene infinitas rutas de ese tipo.

Un ejemplo de cálculo de todos los caminos más cortos desde el 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 la escritura), puede restringir el resultado de get_all_shortest_paths a un vértice dado también:

>>> 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, debe tener cuidado; por ejemplo, suponga que tiene un gráfico de cuadrícula de 100 x 100 (que puede ser generado fácilmente por Graph.Lattice([100, 100], circular=False) en igraph). El número de caminos más cortos que van del nodo superior izquierdo al nodo inferior derecho es igual al número de posibilidades para elegir 100 elementos de 200 (prueba: la longitud del camino más corto tiene 200 aristas, 100 de las cuales irán "horizontalmente"). en la grilla y 100 de los cuales irán "verticalmente"). Probablemente esto no se ajuste a su memoria, por lo tanto, incluso el cálculo de todas las rutas más cortas entre estos dos nodos no es realmente factible aquí.

Si realmente necesita todos los caminos entre dos nodos, puede volver a escribir la función dada en la página web que mencionaste usando igraph, que probablemente será más rápido que una solución Python puro como 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 optimizarse más mediante la conversión de la gráfica a una representación de la lista de adyacencia primero ya que las piezas de 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, []) 

Editar: fIX ed primer ejemplo para trabajar en igraph 0.5.3 también, no solo en igraph 0.6.

Answer 2

El algoritmo de Dijkstra encontrará la ruta más corta de manera similar a una búsqueda de amplitud (sustituye una cola de prioridad ponderada por profundidad en el gráfico por la cola ingenua de una BFS). Podría extenderla bastante trivialmente para producir la 'N' más corta rutas si necesita un número de alternativas, aunque si necesita que las rutas sean sustancialmente diferentes (por ejemplo, programar las rutas de las furgonetas de seguridad), puede ser más inteligente seleccionar rutas que sean significativamente diferentes.

Answer 3

Éste realmente funciona con networkx, y no es 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