r - Igraph：获取最长测地线距离

Question

我的问题如下：考虑一个具有 10000 个节点和 4800 条边的无向图。给定这个图和给定这个图的一个节点（例如节点 1），我需要 igraph (R) 中的一个命令来获取这个节点 1 和图中最远节点之间的距离。非常感谢你的帮助！:)

亲切的问候，伊格纳西奥。

Answer 1

这本质上是一个探路者/搜索。

假设 isConnected(a,b) 返回两个节点是否连接

（我是用 Lua 写代码，应该不难翻译）

function search(list)

local i = 0

while i < 10000 do

i = i + 1

if isConnected(i,list[#list]) then

--This expression refers to the last member

search(list ++ i)  

--Although not technically a proper operator, ++ adds the element to the end of the list

end

end


submit_list(list)
end

submit_list是一个接受列表并检查它们的函数。它找到最长的不包含重复项的提交列表。该列表将解决您的问题。

哦，另一件事；我的代码没有说明什么。如果列表包含重复节点，则该函数应终止，以便它不会永远递归。

Answer 2

> g <- erdos.renyi.game(100,1/20)
> s <- c(shortest.paths(g,2))
> s
  [1] 3 2 0 3 3 3 3 3 3 3 3 3 3 2 1 2 3 1 3 3 3 4 2 4 3 2 3 2 2 3 3 2 3 2 4 4 3
 [38] 3 3 2 2 3 3 4 2 3 3 2 2 4 3 2 3 3 2 1 2 4 2 2 2 2 1 2 4 3 2 2 2 4 3 4 3 3
 [75] 3 3 3 3 3 2 1 3 2 4 2 1 3 1 3 3 3 3 4 3 2 3 2 2 3 3
> which(s == max(s))
 [1] 22 24 35 36 44 50 58 65 70 72 84 93
> get.shortest.paths(g,2,21)
[[1]]
[1]  2 55 33 50 21

让我们做一个图表

g <- erdos.renyi.game(100,1/20)

这将找到到顶点 2 的距离

s <- c(shortest.paths(g,2))

查找最远顶点的索引

which(s == max(s))

显示路径

get.shortest.paths(g,2,21)