Igraph: Obtain the longest geodesic distance.

Question

Hi, everybody!

My question is the following: Consider a undirect graph with 10000 nodes and 4800 edges. Given this graph and given a node of this graph (for example, node 1), I need a command in igraph (R) to obtain the distance between this node 1 and the farest node in the graph, please. Thanks a lot, for your help! :)

Kind regards, Ignacio.

Answer 1

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.

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

Let's make a graph

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

this will find the distances to vertex 2

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

Find the index of the furthest vertex(s)

which(s == max(s))

Display the path

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