У меня следующий вопрос: рассмотрим непрямой граф с 10000 узлов и 4800 ребер. Учитывая этот граф и заданный узел этого графа (например, узел 1), мне нужна команда в igraph (R), чтобы получить расстояние между этим узлом 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 — это функция, которая принимает списки и проверяет их. Он находит самый длинный представленный список, который не содержит дубликатов. Этот список и будет решением вашей проблемы.
О, еще одна вещь; мой код что-то не учитывает. В случае, если список содержит повторяющиеся узлы, эта функция должна завершиться, чтобы она не повторялась вечно.
> 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)
