Igraph: Obtener la distancia geodésica más larga

Question

Mi pregunta es la siguiente: Considere un gráfico indirecto con 10000 nodos y 4800 bordes. Dado este gráfico y dado un nodo de este gráfico (por ejemplo, nodo 1), necesito un comando en igraph (R) para obtener la distancia entre este nodo 1 y el nodo más frágil en el gráfico, por favor. ¡Muchas gracias por tu ayuda! :)

Saludos cordiales, Ignacio.

Answer 1

Básicamente es una búsqueda/buscador de caminos.

Supongamos que isConnected (a, b) devuelve si los dos nodos están conectados

(estoy escribiendo el código en Lua, no debería ser difícil de traducir)

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 es una función que toma listas y las verifica. Encuentra la lista enviada más larga que no contiene duplicados. Esa lista será la solución a su problema.

Oh, una cosa más; mi código no explica nada. En el caso de que la lista contenga nodos duplicados, esa función debe terminar para que no se repita para siempre.

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 

Vamos a hacer un gráfico

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

esto encontrará las distancias al vértice 2

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

Encontrar el índice del vértice más alejado (s)

which(s == max(s)) 

Muestra la ruta

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