Búsqueda eficiente de la ruta más corta en gráficos grandes

Question

Estoy buscando encontrar la manera de encontrar en tiempo real la ruta más corta entre nodos en un gráfico enorme. Tiene cientos de miles de vértices y millones de bordes. Sé que esta pregunta ya fue formulada y creo que la respuesta es usar una búsqueda de amplitud, pero estoy más interesado en saber qué software puede usar para implementarla. Por ejemplo, sería totalmente perfecto si ya existe una biblioteca (¡con enlaces de python!) Para realizar bfs en gráficos no dirigidos.

Answer 1

python-graph

añadido:

Los comentarios me hizo curioso en cuanto a cómo el desempeño de pygraph era por un problema en el orden de la OP, así que hice un programa de juguete para averiguar. Aquí está la salida para una versión ligeramente más pequeña del problema:

$ python2.6 biggraph.py 4 6 
biggraph generate 10000 nodes  00:00:00 
biggraph generate 1000000 edges 00:00:00 
biggraph add edges    00:00:05 
biggraph Dijkstra     00:01:32 
biggraph shortest_path done  00:04:15 
step: 1915 2 
step: 0 1 
biggraph walk done    00:04:15 
path: [9999, 1915, 0] 

No está mal para 10k nodos y bordes 1M. Es importante notar que la forma en que Dijkstra es calculada por pygraph produce un diccionario de todos los árboles de expansión para cada nodo relativo a un objetivo (que arbitrariamente era el nodo 0, y no tiene posición privilegiada en el gráfico). Por lo tanto, la solución que tardó 3,75 minutos en computar realmente arrojó la respuesta a "¿cuál es el camino más corto desde todos los nodos hasta el objetivo?". De hecho, una vez que se hizo shortest_path, caminar la respuesta fue meras búsquedas en el diccionario y no llevó esencialmente tiempo. También vale la pena señalar que agregar los bordes precalculados al gráfico fue bastante caro a ~ 1,5 minutos. Estos tiempos son consistentes en varias ejecuciones.

me gustaría decir que el proceso de escala bien, pero todavía estoy esperando en biggraph 5 6 en un equipo de otra manera ociosa (Athlon 64, 4800 BogoMIPS por procesador, todo en el núcleo), que ha estado funcionando durante más de un cuarto hora. Al menos el uso de la memoria es estable a aproximadamente 0.5GB. Y los resultados están en:

biggraph generate 100000 nodes 00:00:00 
biggraph generate 1000000 edges 00:00:00 
biggraph add edges    00:00:07 
biggraph Dijkstra     00:01:27 
biggraph shortest_path done  00:23:44 
step: 48437 4 
step: 66200 3 
step: 83824 2 
step: 0 1 
biggraph walk done    00:23:44 
path: [99999, 48437, 66200, 83824, 0] 

Eso es mucho tiempo, pero también fue un cómputo pesado (y realmente deseo que había en escabeche el resultado). Aquí está el código para los curiosos:

#!/usr/bin/python 

import pygraph.classes.graph 
import pygraph.algorithms 
import pygraph.algorithms.minmax 
import time 
import random 
import sys 

if len(sys.argv) != 3: 
    print ('usage %s: node_exponent edge_exponent' % sys.argv[0]) 
    sys.exit(1) 

nnodes = 10**int(sys.argv[1]) 
nedges = 10**int(sys.argv[2]) 

start_time = time.clock() 
def timestamp(s): 
    t = time.gmtime(time.clock() - start_time) 
    print 'biggraph', s.ljust(24), time.strftime('%H:%M:%S', t) 

timestamp('generate %d nodes' % nnodes) 
bg = pygraph.classes.graph.graph() 
bg.add_nodes(xrange(nnodes)) 

timestamp('generate %d edges' % nedges) 
edges = set() 
while len(edges) < nedges: 
    left, right = random.randrange(nnodes), random.randrange(nnodes) 
    if left == right: 
     continue 
    elif left > right: 
     left, right = right, left 
    edges.add((left, right)) 

timestamp('add edges') 
for edge in edges: 
    bg.add_edge(edge) 

timestamp("Dijkstra") 
target = 0 
span, dist = pygraph.algorithms.minmax.shortest_path(bg, target) 
timestamp('shortest_path done') 

# the paths from any node to target is in dict span, let's 
# pick any arbitrary node (the last one) and walk to the 
# target from there, the associated distance will decrease 
# monotonically 
lastnode = nnodes - 1 
path = [] 
while lastnode != target: 
    nextnode = span[lastnode] 
    print 'step:', nextnode, dist[lastnode] 
    assert nextnode in bg.neighbors(lastnode) 
    path.append(lastnode) 
    lastnode = nextnode 
path.append(target) 
timestamp('walk done') 
print 'path:', path 

Answer 2

BFS en un gráfico no dirigido es sólo alrededor de 25 líneas de código. No necesitas una biblioteca. Consulte el código de ejemplo en el Wikipedia article.

Answer 3

Para un gráfico tan grande (y con sus limitaciones de rendimiento), es probable que desee el Boost Graph Library ya que está escrito en C++. Tiene el Python bindings que está buscando.

Answer 4

Bueno, depende de la cantidad de metadatos que haya adjuntado a sus nodos y bordes. Si es relativamente poco, ese tamaño de gráfico cabría en la memoria, por lo que recomendaría el excelente paquete de NetworkX (consulte especialmente http://networkx.lanl.gov/reference/generated/networkx.shortest_path.html), que es puro Python.

Para una solución más robusta que puede manejar muchos millones de nodos, grandes metadatos, transacciones, almacenamiento en disco, etc., he tenido una gran suerte con neo4j (http://www.neo4j.org/). Está escrito en Java pero tiene enlaces de Python o puede ejecutarse como un servidor REST. Atravesarlo es un poco complicado, pero no está mal.

Answer 5

Para gráficos grandes, pruebe la interfaz de Python igraph. Su núcleo está implementado en C, por lo tanto, puede hacer frente a los gráficos con millones de vértices y bordes con relativa facilidad. Contiene una implementación BFS (entre otros algoritmos) y también incluye el algoritmo de Dijkstra y el algoritmo Bellman-Ford para gráficos ponderados.

En cuanto a "realtimeness", hice algunas pruebas rápidas, así:

from igraph import * 
from random import randint 
import time 

def test_shortest_path(graph, tries=1000): 
    t1 = time.time() 
    for _ in xrange(tries): 
     v1 = randint(0, graph.vcount()-1) 
     v2 = randint(0, graph.vcount()-1) 
     sp = graph.get_shortest_paths(v1, v2) 
    t2 = time.time() 
    return (t2-t1)/tries 

>>> print test_shortest_path(Graph.Barabasi(100000, 100))  
0.010035698396 
>>> print test_shortest_path(Graph.GRG(1000000, 0.002)) 
0.413572219742 

Según el fragmento de código anterior, la búsqueda de un camino más corto entre dos vértices dados en un gráfico del mundo pequeño que tiene 100K vértices y Los bordes de 10M (10M = 100K * 100) demoran alrededor de 0.01003 segundos en promedio (un promedio de 1000 intentos). Este fue el primer caso de prueba y es una estimación razonable si está trabajando con datos de redes sociales o alguna otra red donde se sabe que el diámetro es pequeño en comparación con el tamaño de la red. La segunda prueba es un gráfico geométrico aleatorio donde 1 millón de puntos se eliminan aleatoriamente en un plano 2D y dos puntos se conectan si su distancia es menor que 0,002, lo que da como resultado un gráfico con aproximadamente 1M de vértices y 6.5M de bordes. En este caso, el cálculo del camino más corto lleva más tiempo (ya que las rutas en sí mismas son más largas), pero todavía está bastante cerca del tiempo real: 0.41357 segundos en promedio.

Descargo de responsabilidad: soy uno de los autores de igraph.

Answer 6

Dependiendo del tipo de información adicional que tenga, A * puede ser extremadamente eficiente. En particular, si se le da un nodo, puede calcular una estimación del costo desde ese nodo hasta la meta, A * es óptimamente eficiente.

Answer 7

tienda en neo4j

Es incluir Dijkstra, A *, algoritmos "camino más corto".