当前位置：文江博客话题详情

igraph：获取最长测地距离

发布于 2024-09-13 02:49:20 字数 145 浏览 5 评论 0原文

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

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

初熏 2024-09-20 02:49:20

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

假设如果两个节点已连接，则 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 是一个接受列表并检查的函数他们。它找到最长且不包含重复项的提交列表。该列表将解决您的问题。

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

That's essentially a pathfinder/search.

Assume that isConnected(a,b) returns if the two nodes are connected

(I am writing the code in Lua, it shouldn't be hard to translate)

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 is a function which takes lists, and checks them. It finds the longest submitted list that contains no duplicates. That list will be the solution to your problem.

Oh, one other thing; my code doesn't account for something. In the event that the list contains duplicates nodes, that function should terminate so that it doesn't recurse forever.

回复收藏 0 原文

尘世孤行 2024-09-20 02:49:20

> 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)

> 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

Let's make a graph