r - Igraph：最長の測地線距離を取得します

Question

私の質問は次のとおりです。10000ノードと4800エッジのある間接グラフを考えてみましょう。このグラフとこのグラフのノード（たとえば、ノード1）が与えられた場合、このノード1とグラフの最も遠いノードとの間の距離を取得するためにigraph（R）のコマンドが必要です。どうもありがとうございました！:)

よろしく、イグナシオ。

Answer 1

それは本質的にパスファインダー/検索です。

2 つのノードが接続されている場合、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 つ。私のコードは何かを説明していません。リストに重複ノードが含まれている場合、その関数は永久に再帰しないように終了する必要があります。

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)