如何加快 all_pairs_dijkstra_path_length 的速度

Question

我有一个很大的osmnx（networkx）图，并且nx.all_pairs_dijkstra_path_length需要很长时间才能计算。

有哪些可能性可以加快计算速度？

Answer 1

import osmnx as ox\nimport networkx as nx\n

\n

让我们占领这个区域

\n

coords, dist = (51.5178, 9.9601), 9000\nG = ox.graph.graph_from_point( coords, dist=dist, network_type=\'drive\', simplify=True)\nG = ox.add_edge_speeds(G)\nG = ox.add_edge_travel_times(G)\n

\n

以nx.all_pairs_dijkstra_path_length作为基线。

\n

为此，让我们创建简写bench_nx：

\n

bench_nx = lambda G, weight=\'travel_time\': sum((l:=[ d for t in nx.all_pairs_dijkstra_path_length(G, weight=weight) for d in t[1].values() ])) / len(l)\n

\n

bench_nx(G)\n582.2692172953298\n

\n

%timeit -n 3 -r 2 bench_nx(G)\n53.7 s \xc2\xb1 101 ms per loop (mean \xc2\xb1 std. dev. of 2 runs, 3 loops each)\n

\n

并行化

\n

def mp_all_pairs_dijkstra_path_length(G, cutoff=None, weight=\'weight\'):\n    """\n    Multi-core version of\n    nx.all_pairs_dijkstra_path_length\n    """\n\n    import multiprocessing as mp\n    from functools import partial\n\n    f = partial(nx.single_source_dijkstra_path_length,\n                G, cutoff=cutoff, weight=weight)\n\n    with mp.Pool(mp.cpu_count()) as p:\n        \n        lengths = p.map(f, G)\n        for n, l in zip(G, lengths):\n            yield n, l\n

\n

bench_mp = lambda G, weight=\'travel_time\': sum((l:=[ d for t in mp_all_pairs_dijkstra_path_length(G, weight=weight) for d in t[1].values() ])) / len(l)\n

\n

bench_mp(G)\n582.2692172953298\n

\n

%timeit -n 3 -r 2 bench_mp(G)\n20.2 s \xc2\xb1 754 ms per loop (mean \xc2\xb1 std. dev. of 2 runs, 3 loops each)\n

\n

图表越大，这里的优势似乎就越大。

\n

图形工具

\n

使用图形工具我们可以加快速度。

\n

图形工具使用整数索引顶点和边。因此我在这里创建两个字典

\n

\n
1. nx_node->gt_idx
\n
2. u,v,k（边缘）->gt_idx
\n

\n

能够映射从nx到gt。

\n

import graph_tool.all as gt\nfrom collections import defaultdict\n\nG_gt = gt.Graph(directed=G.is_directed())\n\n# "Dict" [idx] = weight\nG_gt_weights = G_gt.new_edge_property("double")\n\n# mapping of nx vertices to gt indices\nvertices = {}\nfor node in G.nodes:\n    \n    v = G_gt.add_vertex()\n    vertices[node] = v\n\n# mapping of nx edges to gt edge indices\nedges = defaultdict(lambda: defaultdict(dict))\n\nfor src, dst, k, data in G.edges(data=True, keys=True):\n    \n    # Look up the vertex idxs from our vertices mapping and add edge.\n    e = G_gt.add_edge(vertices[src], vertices[dst])\n    edges[src][dst][k] = e\n    \n    # Save weights in property map\n    G_gt_weights[e] = data[\'travel_time\']\n

\n

注意：我添加了截止点，1e50因为gt将不可到达的目的地设置为 distance 1.79e308。

\n

bench_gt = lambda G, weights: sum((l:=[ d for l in gt.shortest_distance(G, weights=weights) for d in l if 0 < d <= 1e50 ])) / len(l)\n

\n

bench_gt(G_gt, G_gt_weights)\n582.4092142257183\n

\n

%timeit -n 3 -r 2 bench_gt(G_gt, G_gt_weights)\n4.76 s \xc2\xb1 27.4 ms per loop (mean \xc2\xb1 std. dev. of 2 runs, 3 loops each)\n

\n

这至少提高了 11 倍。

\n

二次抽样

\n

事实证明distance_histogram()，如果在编译时启用，则能够进行二次采样并并行运行！

\n

import osmnx as ox\nimport networkx as nx\n

\n

coords, dist = (51.5178, 9.9601), 9000\nG = ox.graph.graph_from_point( coords, dist=dist, network_type=\'drive\', simplify=True)\nG = ox.add_edge_speeds(G)\nG = ox.add_edge_travel_times(G)\n

\n

注：由于第一个 bin 内的差异，存在小偏差。如果有人知道原因，我很高兴知道！\n编辑这似乎是graph-tools 中的一个错误。

\n

bench_nx = lambda G, weight=\'travel_time\': sum((l:=[ d for t in nx.all_pairs_dijkstra_path_length(G, weight=weight) for d in t[1].values() ])) / len(l)\n

\n

这又是 50 倍，总加速为 241 倍！

\n\n

附录

\n

\nX 轴是涉及的顶点总数占顶点总数的分数。

\n