有效地找到大图中的最短路径

Question

我正在寻找一种方法来实时找到巨大图形中节点之间的最短路径.它有数十万个顶点和数百万个边.我知道之前已经问过这个问题,我想答案是使用广度优先搜索,但我更感兴趣的是知道可以用什么软件来实现它.例如,如果已经存在用于在无向图中执行bfs的库(使用python绑定!),那将是完全完美的.

Answer 1

蟒蛇 - 图

添加:

这些评论让我很好奇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计算Dijkstra的方式产生了每个节点相对于一个目标(任意节点0,并且在图中没有特权位置)的所有生成树的字典.因此,花费3.75分钟进行计算的解决方案实际上得出了"从所有节点到目标的最短路径是什么？"的答案.确实一旦shortest_path完成,走的答案仅仅是字典查找,基本上没有时间.值得注意的是,在图表中添加预先计算的边缘在约1.5分钟时相当昂贵.这些时间在多次运行中是一致的.

我想说这个过程可以很好地扩展,但是我还在等待biggraph 5 6一台闲置的计算机(每台处理器的Athlon 64,48 BogoMIPS,全部是核心),它已经运行了超过四分之一小时.至少内存使用稳定在约0.5GB.结果如下:

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

Answer 2

对于大图,请尝试igraph的Python界面.它的核心是用C实现的,因此它可以相对容易地处理具有数百万个顶点和边缘的图形.它包含BFS实现(以及其他算法),它还包括Dijkstra算法和加权图的Bellman-Ford算法.

至于"实时性",我也进行了一些快速测试:

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次尝试).这是第一个测试案例,如果您正在使用社交网络数据或其他网络,其中已知直径与网络规模相比较小,则这是一个合理的估计.第二个测试是几何随机图,其中在2D平面上随机丢弃100万个点,如果它们的距离小于0.002则连接两个点,从而产生具有大约1M顶点和6.5M边缘的图形.在这种情况下,最短路径计算需要更长时间(因为路径本身更长),但它仍然非常接近实时:平均0.41357秒.

免责声明:我是igraph的作者之一.