In modo efficiente trovare il percorso più breve in grandi grafici

Question

Sto cercando di trovare un modo per in tempo reale trovare il percorso più breve tra i nodi di un grafo enorme. Ha centinaia di migliaia di vertici e milioni di spigoli. So che questo problema è stato fatto prima e credo che la risposta è quella di utilizzare una ricerca in ampiezza, ma io sono più interessato a sapere quale software è possibile utilizzare per la sua attuazione. Ad esempio, sarebbe del tutto perfetto se esiste già una libreria (con binding Python!) Per l'esecuzione di BFS in grafi non orientati.

Answer 1

python-grafico

ha aggiunto:

I commenti mi ha fatto curioso di vedere come le prestazioni di pygraph era per un problema dell'ordine del PO, così ho fatto un programma di giocattoli per scoprirlo. Ecco l'output per una versione leggermente più piccola 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]

Non male per 10k nodi e spigoli 1M. È importante notare che il modo Dijkstra vengono calcolate da pygraph produce un dizionario di tutte spanning tree per ogni nodo rispetto a un target (che era arbitrariamente nodo 0, e detiene alcuna posizione privilegiata nel grafico). Pertanto, la soluzione che ha preso 3,75 minuti per calcolare effettivamente ceduto la risposta alla domanda "qual è il percorso più breve da tutti i nodi al bersaglio?". Infatti una volta shortest_path è stato fatto, a piedi la risposta è stata mere ricerche del dizionario e ha preso essenzialmente nessun tempo. È anche interessante notare che l'aggiunta di bordi pre-calcolate al grafico era piuttosto costoso a ~ 1,5 minuti. Questi tempi sono coerenti su più piste.

Mi piacerebbe dire che le scale di processo bene, ma sto ancora aspettando biggraph 5 6 su un computer altrimenti idled (Athlon 64, 4800 BogoMIPS per processore, il tutto in core) che è attivo da più di un quarto d'ora. Almeno l'utilizzo della memoria è stabile a circa 0,5 GB. E i risultati sono in:

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]

Questo è un lungo periodo di tempo, ma era anche un calcolo pesante (e mi auguro che avevo in salamoia il risultato). Ecco il codice per i curiosi:

#!/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

Per i grandi grafici, provare l'interfaccia di Python di IGRAPH . Il suo nucleo è implementato in C, quindi si può far fronte con grafici con milioni di vertici e spigoli relativamente facilmente. Esso contiene un'implementazione BFS (tra gli altri algoritmi) e comprende anche l'algoritmo di Dijkstra e l'algoritmo di Bellman-Ford per grafi pesati.

Per quanto riguarda "realtimeness", ho fatto alcuni test rapidi così:

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

Secondo il frammento di codice di cui sopra, trovare un percorso più breve tra due dati vertici in un grafico piccolo mondo avente 100K vertici e spigoli 10 M (10M = 100K * 100) prende circa 0.01003 secondi in media (media da 1000 tentativi). Questo è stato il primo banco di prova, ed è una stima ragionevole se si lavora con i dati di rete sociale o qualche altra rete in cui il diametro è noto per essere piccolo rispetto alle dimensioni della rete. La seconda prova è un grafico casuale geometrico dove 1 milione di punti vengono eliminati in modo casuale su un piano 2D e due punti sono collegati se la loro distanza è inferiore a 0,002, risultando in un grafico con circa vertici 1M e 6,5 milioni bordi. In questo caso, il calcolo percorso più breve richiede più tempo (come i sentieri stessi sono più lunghi), ma è ancora abbastanza vicino al tempo reale:. 0.41357 secondi in media

. Disclaimer: io sono uno degli autori IGRAPH

Answer 3

Per un grafico che di grandi dimensioni (e con i vostri vincoli di prestazioni), probabilmente desidera che il Boost Graph Library dal momento che è scritto in C ++. Ha le Python binding state cercando.

Answer 4

Beh, dipende da quanto i metadati è stato collegato ai vostri nodi e spigoli. Se relativamente poco, che le dimensioni del grafico si adatterebbe nella memoria, e mi consiglia quindi l'eccellente pacchetto di NetworkX (si veda in particolare http://networkx.lanl.gov/reference/generated/networkx.shortest_path.html ), che è puro Python.

Per una soluzione più robusta in grado di gestire molti milioni di nodi, grandi metadati, con le transazioni, storage su disco, ecc, ho avuto grande fortuna con Neo4j ( http://www.neo4j.org/ ). E 'scritto in Java, ma ha binding Python oppure può essere eseguito come un server REST. Traversal con esso è un po 'Tricker, ma non male.

Answer 5

UST in un grafo non orientato è soltanto circa 25 righe di codice. Non hai bisogno di una biblioteca. Controlla il codice di esempio nella Wikipedia articolo .

Answer 6

A seconda del tipo di informazioni aggiuntive che hai, A * può essere estremamente efficiente. In particolare, se dato un nodo si può calcolare una stima del costo da quel nodo alla meta, A * è ottimamente efficiente.

Answer 7

Neo4j

E 'includere Dijkstra, A *, "più breve percorso" algoritmi.