r - R igraph：仅计算所有顶点对的子集的最短路径

Question

我有一个非常大的 igraph 对象，因此计算最短路径需要很长时间。我只对一组非常小的顶点对之间的最短路径的长度感兴趣。假设（无向）图由 10,000 个顶点和 500,000 条边组成，顶点对有最短路径10,000 * 10,000 / 2，但我只需要 10,000 对顶点之间的路径。

是否有可能不仅定义顶点，还定义顶点对（意思是：要计算的路径的起点和终点）？

标签： rsubsetigraphshortest-path

Answer 1

由于您有偶数个顶点来配对，您可以将所有顶点分成两组，即偶数或奇数，如下所示

v_even <- subset(V(g), !V(g) %% 2)
v_odd <- subset(V(g), !!V(g) %% 2)

然后你运行shortest_paht以mapply产生最短路径

> mapply(function(x, y) shortest_paths(g, x, y)$vpath, v_even, v_odd)
[[1]]
+ 3/10 vertices, from 7125d30:
[1] 2 6 1

[[2]]
+ 2/10 vertices, from 7125d30:
[1] 4 3

[[3]]
+ 2/10 vertices, from 7125d30:
[1] 6 5

[[4]]
+ 5/10 vertices, from 7125d30:
[1] 8 5 6 2 7

[[5]]
+ 3/10 vertice

数据

set.seed(1)
g <- sample_gnm(10, 15)