Igraph: Erhalten Sie die längste geodätische Entfernung

Question

Meine Frage ist die folgende: Betrachten Sie eine indirekte Grafik mit 10000 Knoten und 4800 Kanten. In Anbetracht dieses Graphen und eines Knoten dieses Graphen (zum Beispiel Knoten 1) benötige ich einen Befehl in igraph (R), um den Abstand zwischen diesem Knoten 1 und dem am weitesten entfernten Knoten in der Grafik zu erhalten. Vielen dank für Deine Hilfe! :)

Mit freundlichen Grüßen, Ignacio.

Answer 1

Das ist im Wesentlichen ein Pfadfinder/Suche.

Angenommen, isConnected (a, b) zurückgibt, wenn die beiden Knoten

verbunden sind (ich den Code in Lua schreibe, ist es nicht schwer sein sollte, übersetzen)

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 ist eine Funktion, die Listen aufnimmt und prüft. Es findet die am längsten eingereichte Liste, die keine Duplikate enthält. Diese Liste wird die Lösung für Ihr Problem sein.

Oh, eine andere Sache; Mein Code berücksichtigt nichts. Für den Fall, dass die Liste doppelte Knoten enthält, sollte diese Funktion beendet werden, so dass sie nicht für immer rekursiv ist.

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 

Werfen wir einen Graphen machen

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

dies die Abstände 2 nach Knoten

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

Finden Sie den Index des am weitesten Vertex finden (s)

which(s == max(s)) 

Zeigen Sie den Pfad

an

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