Я надеюсь находить способ в режиме реального времени найти кратчайший путь между узлами в огромном графике. Это имеет сотни тысяч вершин и миллионы краев. Я знаю, что этот вопрос задали, прежде и я предполагаю, что ответ должен использовать поиск в ширину, но я больше интересуюсь знать, какое программное обеспечение можно использовать для реализации его. Например, это было бы полностью прекрасно, если это уже существует библиотека (с привязкой Python!) для выполнения bfs в неориентированных графах.
добавлено:
Комментарии заставили меня полюбопытствовать, какова производительность pygraph для задачи порядка OP, поэтому я сделал игрушечную программу, чтобы выяснить это. Вот результат для немного уменьшенной версии задачи:
$ 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]
Неплохо для 10k узлов и 1M ребер. Важно отметить, что способ, которым pygraph вычисляет метод Дейкстры, дает словарь всех прямых деревьев для каждого узла относительно одной цели (которой произвольно был узел 0, не занимающий никакого привилегированного положения в графе). Таким образом, решение, на вычисление которого ушло 3,75 минуты, фактически дало ответ на вопрос "каков кратчайший путь от всех узлов к цели?". Действительно, как только shortest_path
был выполнен, поиск ответа сводился к просмотру словаря и не занимал практически никакого времени. Стоит также отметить, что добавление предварительно вычисленных ребер в граф было довольно дорогостоящим - ~1,5 минуты. Эти временные показатели совпадают при многократных прогонах.
Я бы хотел сказать, что процесс хорошо масштабируется, но я все еще жду biggraph 5 6
на неработающем компьютере (Athlon 64, 4800 BogoMIPS на процессор, все в ядре), который работает уже более четверти часа. По крайней мере, использование памяти стабильно - около 0,5 ГБ. И вот результаты:
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]
Это долго, но это были и тяжелые вычисления (и я очень жалею, что не замариновал результат). Вот код для любопытных:
#!/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
Для больших графиков попробуйте интерфейс Python igraph . Его ядро реализовано на языке C, поэтому он относительно легко справляется с графами с миллионами вершин и ребер.Он содержит реализацию BFS (среди других алгоритмов), а также алгоритм Дейкстры и алгоритм Беллмана-Форда для взвешенных графов.
Что касается «реального времени», я также провел несколько быстрых тестов:
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
Согласно приведенному выше фрагменту кода, поиск кратчайшего пути между двумя заданными вершинами в графе малого мира, имеющем 100K вершин и 10M ребер (10M = 100K * 100) в среднем занимает около 0,01003 секунды (в среднем по 1000 попыток). Это был первый тестовый пример, и это разумная оценка, если вы работаете с данными социальной сети или какой-либо другой сети, диаметр которой, как известно, мал по сравнению с размером сети. Второй тест представляет собой геометрический случайный граф, в котором 1 миллион точек случайным образом отбрасывается на 2D-плоскости и две точки соединяются, если их расстояние меньше 0,002, в результате получается граф с примерно 1 млн вершин и 6,5 млн ребер. В этом случае вычисление кратчайшего пути занимает больше времени (поскольку сами пути длиннее), но он все еще довольно близок к реальному времени: в среднем 0,41357 секунды.
Заявление об ограничении ответственности: я являюсь одним из авторов графика .
Для такого большого графа (и с вашими ограничениями производительности) вам, вероятно, понадобится Boost Graph Library, поскольку она написана на C++. Она имеет привязку к Python, которую вы ищете.
Ну, это зависит от того, сколько метаданных вы прикрепили к своим узлам и ребрам. Если относительно небольшой, этот размер графа поместится в памяти, и поэтому я бы порекомендовал отличный пакет NetworkX (см. Особенно http://networkx.lanl.gov/reference/generated/networkx.shortest_path.html ]), который является чистым Python.
В поисках более надежного решения, которое может обрабатывать многие миллионы узлов, большие метаданные, транзакции, дисковое хранилище и т. Д., Мне очень повезло с neo4j ( http://www.neo4j.org/ ). Он написан на Java, но имеет привязки к Python или может работать как REST-сервер. Обойти его немного сложнее, но неплохо.
В зависимости от того, какая дополнительная информация у вас есть, A * может быть чрезвычайно эффективным. В частности, если дан узел, вы можете вычислить оценку стоимости от этого узла до цели, A * оптимально эффективен.
BFS в неориентированном графе занимает всего около 25 строк кода. Вам не нужна библиотека. Посмотрите пример кода в статье Википедии .