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.
En general, no se puede hacer. Si hay ciclos en su gráfico, hay un número infinito de caminos, por ej. A-> B-> A-> B -> ...-> B-> C Necesitará agregar más restricciones a su pregunta (por ejemplo, no ciclos, o cómo planea manejar los ciclos). –
Aunque puede detectar ciclos en rutas usando un algoritmo de tortuga y liebre. Puede obtener una aproximación aceptable combinando eso con una búsqueda amplia, aunque me atrevo a decir que sería algo ineficiente. – ConcernedOfTunbridgeWells
Necesito algo así como la función find_all_paths(), que se describe aquí: http://www.python.org/doc/essays/graphs.html Pero esta función no funciona bien con una gran cantidad de nodos y filo = ( – user285070