Igraph: Obtenir la plus longue distance géodésique

Question

Ma question est la suivante: Considérons un graphique indirect avec 10000 nœuds et 4800 arêtes. Etant donné ce graphe et étant donné un noeud de ce graphe (par exemple, noeud 1), j'ai besoin d'une commande dans igraph (R) pour obtenir la distance entre ce noeud 1 et le noeud le plus éloigné du graphe. Merci beaucoup pour votre aide! :)

Cordialement, Ignacio.

Answer 1

C'est essentiellement un pathfinder/search.

On suppose que isConnected (a, b) retourne si les deux noeuds sont connectés

(je suis en train d'écrire le code dans Lua, il ne devrait pas être difficile à traduire)

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 est une fonction qui prend des listes et les vérifie. Il trouve la liste soumise la plus longue qui ne contient aucun doublon. Cette liste sera la solution à votre problème.

Oh, une autre chose; mon code ne tient pas compte de quelque chose. Dans le cas où la liste contient des noeuds en double, cette fonction doit se terminer afin qu'elle ne se répète pas indéfiniment.

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 

Faisons un graphique

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

cela trouver les distances au sommet 2

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

Trouver l'indice du sommet le plus (s)

which(s == max(s)) 

Afficher le chemin

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