Skip to main content
 首页 » 编程设计

python之使用 igraph 有效计算具有 23000000 个节点的图的最短路径数

2024年10月25日9arxive

我正在尝试计算包含 23000000 个顶点和大约 9 X 23000000 边的稀疏图中彼此距离为 2 的 2 个节点之间的最短路径数。现在我正在使用

for v,d,parent in graph.bfsiter(source.index, advanced=True): 
        if (0 < d < 3): 

循环遍历距离源节点 2 以内的节点(我需要距离 1 的节点,但我不需要为它们计算所有最短路径)。然后我使用:

len (graph.get_all_shortest_paths(source,v)); 

获取从源到 v 的所有最短路径的数量(其中 v 是 bfsiter 给我的节点,它距源的最短距离为 2)。

但是这花费的时间太长了。例如,对于上述图表,计算每个 (source,v) 的最短距离大约需要 1 秒。

我想知道是否有人可以建议一种更有效的方法来使用 igraph 计算所有最短路径的数量

请您参考如下方法:

这是评论中建议的答案的实现。此代码的耗时部分是图形生成。在已经生成的/内存中的图上运行只需要很少的时间。

from igraph import * 
import random 
 
# Generate a graph 
numnodes = int(1e6) 
thegraph = Graph.GRG(numnodes, 0.003) 
 
print("Graph Generated") 
 
# Choose one node randomly and another a distance of 2 away 
node1 = random.randint(0, numnodes-1) 
node2 = random.sample(set(Graph.neighborhood(thegraph, node1, 2)).difference( 
                      set(Graph.neighborhood(thegraph, node1, 1))),1)[0] 
 
# Find the number of nodes in the intersection of the neighborhood 
# of order 1. 
result = len(set(Graph.neighbors(thegraph, node1)).intersection( 
    Graph.neighbors(thegraph, node2))) 
 
print(result) 

两个邻域的交集就是唯一路径的数量。长度为 2 的路径访问 3 个节点。由于我们知道起点和终点,唯一可能变化的是中间点。由于中间节点必须与两个端点的距离为 1,因此唯一中间点的数量是节点之间长度为 2 的路径的数量。