Igraph: Получить наибольшее геодезическое расстояние

Question

Мой вопрос: Рассмотрим непрямой граф с 10000 узлами и 4800 ребрами. Учитывая этот график и заданный узел этого графа (например, узел 1), мне нужна команда в igraph (R), чтобы получить расстояние между этим узлом 1 и самым узким узлом на графике. Большое спасибо за вашу помощь! :)

С уважением, Игнасио.

Answer 1

Это по существу путь к поиску.

Предположим, что IsConnected (а, б) возвращает, если два узла соединены

(я пишу код в 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)