Ответ 1
добавлено:
В комментариях мне было любопытно узнать, как производительность пигграфа была связана с проблемой порядка 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. Важно отметить, что метод Dijkstra, вычисляемый pygraph, дает словарь всех связующих деревьев для каждого node относительно одной цели (которая была произвольно node 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