Igraph: получить наибольшее геодезическое расстояние - PullRequest
Новая
       17

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

5 голосов
/ 07 августа 2010

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

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

Ответы [ 2 ]

2 голосов
/ 07 августа 2010

По сути это указатель пути / поиск.

Предположим, что 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 - это функция, которая берет списки и проверяет их.Он находит самый длинный отправленный список, который не содержит дубликатов.Этот список будет решением вашей проблемы.

О, еще одна вещь;мой код не учитывает что-либо.В случае, если список содержит дубликаты узлов, эта функция должна завершаться, чтобы она не повторялась вечно.

1 голос
/ 07 августа 2010 
> 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)
...