Trouver efficacement le chemin le plus court dans les grands graphiques

Je suis à la recherche d'un moyen en temps réel, trouver le plus court chemin entre deux nœuds dans un grand graphe. Il a des centaines de milliers de sommets et des millions de bords. Je sais que cette question a été posée et je suppose que la réponse est d'utiliser une largeur de recherche, mais je suis plus intéressé de savoir quels sont les logiciels que vous pouvez utiliser pour la mettre en œuvre. Par exemple, il serait totalement parfait si il existe déjà une bibliothèque (avec des bindings python!) pour la réalisation de la bfs non orienté graphiques.

ajouté:

Les commentaires m'a rendu curieux comme à comment la performance de pygraph était pour un problème sur le bon de commande de l'OP, j'ai donc fait un jouet programme pour trouver. Voici la sortie pour une version légèrement plus petite de la le problème:

$ 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]

Pas trop mal pour les 10k nœuds et 1M de bords. Il est important de noter que la façon de Dijkstra est calculée par pygraph donne un dictionnaire de tous les arbres de recouvrement pour chaque nœud par rapport à une cible (qui a été arbitrairement le nœud 0, et ne détient pas de position privilégiée dans le graphique). Par conséquent, la solution qui a pris de 3,75 minutes pour calculer réellement donné la réponse à "qu'est-ce que le chemin le plus court à partir de tous les nœuds de la cible?". En effet, une fois shortest_path a été fait, la marche, la réponse a été simple dictionnaire des recherches et a pris essentiellement en un rien de temps. Il est également intéressant de noter que l'ajout de la pré-calculées d'arêtes du graphe est plutôt cher à ~1,5 minutes. Ces horaires sont compatibles entre plusieurs pistes.

Je tiens à dire que le processus d'échelles, mais je suis toujours en attente sur biggraph 5 6 sur une autre inactif ordinateur (Athlon 64, 4800 BogoMIPS par processeur, tous en cœur) qui a été en cours d'exécution depuis plus d'un quart d'heure. Au moins l'utilisation de la mémoire est stable à environ 0,5 GO. Et les résultats sont là:

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]

C'est beaucoup de temps, mais c'était aussi un gros calcul (et je souhaite vraiment que j'avais marinés le résultat). Voici le code pour les curieux:

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

9

Pour les grands graphes, essayez le Python interface de igraph. Son noyau est implémenté en C, donc il peut faire face à des graphiques avec des millions de sommets et d'arêtes relativement facilement. Il contient une SECTION de mise en œuvre (entre autres algorithmes), et il comprend aussi de l'algorithme de Dijkstra et de la Bellman-Ford algorithme pour pondérée des graphiques.

Comme pour "realtimeness", j'ai fait quelques tests rapides ainsi:
```
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
```
Selon l'extrait de code ci-dessus, la recherche d'un plus court chemin entre deux sommets dans un petit graphique du monde d'avoir 100K sommets et 10M de bords (10M = 100 * 100) prend environ 0.01003 secondes en moyenne (moyenne de 1000 essais). C'était le premier cas de test et c'est une estimation raisonnable si vous travaillez avec des données de réseau social ou un autre réseau où le diamètre est connu pour être petite par rapport à la taille du réseau. Le deuxième test est un géométriques aléatoires graphique, où 1 million de points sont tombé au hasard sur un plan en 2D et les deux points sont reliés si leur distance est inférieure à 0,002, résultant dans un graphe à environ 1M de sommets et de 6,5 M des bords. Dans ce cas, le chemin le plus court calcul prend plus de temps (comme les chemins sont eux-mêmes plus longtemps), mais il est encore à peu près en temps réel: 0.41357 secondes en moyenne.

Disclaimer: je suis l'un des auteurs de igraph.
3

Pour un graphique que les grandes (et avec votre des contraintes de performance), vous voudrez probablement la Boost Graph Library depuis qu'il est écrit en C++. Il a la Liaisons Python vous êtes à la recherche pour.
3

Eh bien, cela dépend de combien de métadonnées que vous avez connecté à votre nœuds et les arêtes. Si relativement peu, que la taille du graphique de tenir en mémoire, et je voudrais donc recommander l'excellent NetworkX package (voir en particulier les http://networkx.lanl.gov/reference/generated/networkx.shortest_path.html), qui est un pur Python.

Pour une solution plus robuste qui peut gérer plusieurs millions de nœuds, de grandes métadonnées, avec des transactions, disque de stockage, etc., J'ai eu beaucoup de chance avec neo4j (http://www.neo4j.org/). Il est écrit en Java, mais a des bindings Python ou peut être exécuté comme un RESTE du serveur. La traversée est un peu plus difficile mais pas mauvais.
2

BFS dans un graphe non-dirigé est seulement d'environ 25 lignes de code. Vous n'avez pas besoin d'une bibliothèque. Découvrez l'exemple de code dans la Article de Wikipedia.
0

En fonction du type d'information supplémentaire que vous avez, d'Un* peuvent être extrêmement efficaces. En particulier, si un nœud vous pouvez calculer une estimation du coût de ce nœud à l'objectif, Une* est parfaitement efficace.
0

magasin en neo4j

C'est inclure Dijkstra, A*, "plus court chemin" algorithmes.

Vous devez vous connecter pour publier un commentaire.