2014-09-03

Calcular el trayecto recomendado entre dos estaciones con igraph

Title Mi objetivo es calcular el trayecto más corto entre dos estaciones de metro. Como la página para calcular el trayecto recomendado de Metro de Madrid. En este caso entre Quevedo y O'Donnell.

Utilizaremos el paquete igraph para el análisis de redes.

Datos

1. El primer paso es crear un fichero CSV con los nombres de los vértices, las estaciones de metro de Madrid. La primera columna denota desde y la segunda a.

Importación

2. Importamos el CSV y a partir de él creamos el igraph.

require(igraph)
estaciones <- read.csv2("estaciones.csv")
g <- graph.data.frame(estaciones, directed = FALSE)

Cálculos

3. Camino más corto entre dos estaciones

# Listado de paradas (secuencia de vértices)
gsp <- get.shortest.paths(g, from = "Quevedo", to = "O'Donnell") 
V(g)[gsp$vpath[[1]]]
Vertex sequence:
[1] "Quevedo"           "Canal"        "Alonso Cano"    "Gregorio Marañón"  
[5] "Avenida de América" "Diego de León" "Manuel Becerra" "O'Donnell"       
# Número de paradas (distancia)
sp<- shortest.paths(g, v = "Quevedo", to = "O'Donnell") 
        O'Donnell
Quevedo         7
4. Camino más corto entre una estación y el resto

# Número de paradas entre una estación y el resto
sp <- shortest.paths(g, v = "Quevedo")
head(t(sp)) # Para mostrar todas: t(sp) 
                   Quevedo
Pinar de Chamartin       9
Bambú                    8
Chamartín                7
Plaza de Castilla        6
Valdeacederas            6
Tetuán                   5
 # Distancia entre la parada anterior (Quevedo) y Pacífico 
sp[1, which(V(g)$name == 'Pacífico')]
[1] 10
4. Matriz de distancias, con el camino más corto entre todos los nodos

sp <- shortest.paths(g) # Camino más corto entre todos los vértices
write.csv2(sp, "matriz de distancias.csv") # Exportamos la matriz como CSV
El CSV tendrá este aspecto:

Camino más corto entre dos estaciones cualquiera

sp["Quevedo", "Chamartín"]
[1] 7

Notas

En nuestro ejemplo, he elegido a propósito un trayecto entre dos estaciones, Quevedo y O'Donnell, que arroja un resultado diferente si empleamos el trayecto recomendado por la página de Metro de Madrid o igraph.

Metro de Madrid utiliza como criterios, la ruta más rápida, con menores transbordos o menor longitud de recorrido, pero no el menor número de paradas (nodos). En cambio igraph en este caso, como no hemos especificado pesos o distancias entre los nodos, simplemente devuelve la ruta con el menor número de nodos o vértices. Es decir, no tiene en cuenta ni el número de transbordos, dos en este caso, ni la distancia entre las estaciones.

Referencias:

Introducción al paquete igraph para R
Calcular el número de transbordos en una ruta con igraph
igraph

No hay comentarios:

Publicar un comentario

Nube de datos