redes.utf8

Arreola Silva E. Marisol
Garcia Nieto Luis

Introducción: En la Facultad d}e Ciencias, UNAM, los alumnos eligen su horario a conveniencia, de manera que se tiene una forma libre de elegir profesores, sin embargo, esto no sucede con los salones dentro de la facultad y puede suceder que en el cambio de salón de dos clases consecutivas, se tenga la necesidad de recorrer una considerable distancia o tiempo para llegar de un salón a otro. Así, en este proyecto nos interesa encontrar la forma más óptima(en tiempo) de trasladarnos de un lugar a otro. Consideraremos los principales sitios de interés dentro y fuera de la facultad.

Planteamiento.Sea G=[X,A, t] una red donde:

Si X es el conjunto de vértices, representará los sitios de interés, estos son:

Metro C.U (MCU)
Prometeo(enfrente del bebedero) (PROM)
ABC
Intersección pasillo Edificio de Matemáticas- Edificio P y Edificio O, primer piso (PO1)
Intersección pasillo Edificio de Matemáticas- Edificio P y Edificio O, segundo piso (PO2)
Aula Magna I, Tlahuizcalpan (AM1)
Aula Magna II, Tlahuizcalpan (AM2)
Darwin (DARW)
Taller de finanzas, Tlahuizcalpan (T. FIN)
Taller de IdeO, Tlahuizcalpan (T. IDEO)
Copias (enfrente de servicios escolares) (COP)
Yelizcalli(Planta baja, salón 006) (YEL)
Tía Aly (TIA ALY)
Pulpo (PULPO)
Media luna (MLUNA)

Si A representa el conjunto de aristas, éstas determinará un camino directo entre nuestros lugares objetivo.
t es una función que representa el tiempo que nos toma llegar de un lugar a otro. Estos tiempos se medirán un numero considerable de veces para, posteriormente, obtener la media que será está función.

Solución con explicación. En este problema, buscamos la ruta más corta de un lugar a otro, por lo tanto, se utilizará el algoritmo de Floyd programado en R o Python para resolverlo.

Para esto creamos una función que recibe como parámetros dos lugares de los considerados para el proyecto, con el nombre asignado, y regresamos la trayectoria de rutas más cortas, la matriz de adyacencia de floyd y el costo que en este caso es el tiempo

En el siguiente recuadro mostramos la matriz de costos, el tiempo que toma ir direcamente del lugar i al lugar j, donde los lugares están acomodados por renglón y columna de la siguiente manera:

“PROMETEO”, “CU”, “MAGNA 1”, “MAGNA 2”, “COPIAS”, “YEL”, “TALY”, “T.FINANZ”, “T. IDEO”, “PO1”, “PO2”, “DARWIN”, “ABC”, “PULPO”, “MEDIA LUNA”

require(Matrix)
require(dplyr)
library(readxl)
DISTACIAS <- na.omit(read_excel("DISTACIAS.xlsx")) 
View(DISTACIAS)
places<-c("PROMETEO", "CU", "MAGNA 1", "MAGNA 2", "COPIAS", "YEL", "TALY", "T.FINANZ", "T. IDEO", "PO1", "PO2", "DARWIN", "ABC", "PULPO", "OTRO")
DISTANCIAS<-DISTACIAS%>%select(-1)%>% as.matrix()
Costos<-matrix(DISTANCIAS, nrow=15, ncol =15)%>%na.omit() %>% forceSymmetric()
Costos

## 15 x 15 Matrix of class "dsyMatrix"
##            [,1]     [,2]   [,3]  [,4]  [,5] [,6] [,7]  [,8] [,9] [,10]
##  [1,]   0.00000 12.78425  15.90 14.80 14.30   12   12 12.00   12    12
##  [2,]  12.78425  0.00000  12.00 11.00 10.00   13   13 12.00   13    13
##  [3,]  15.90000 12.00000   0.00  0.28 21.00   43   43  1.18  112    12
##  [4,]  14.80000 11.00000   0.28  0.00  0.16   43   43 43.00   43    43
##  [5,]  14.30000 10.00000  21.00  0.16  0.00   43   32 43.00   43    43
##  [6,]  12.00000 13.00000  43.00 43.00 43.00    0    2 43.00   43    43
##  [7,]  12.00000 13.00000  43.00 43.00 32.00    2    0 43.00   43    43
##  [8,]  12.00000 12.00000   1.18 43.00 43.00   43   43  0.00   43    43
##  [9,]  12.00000 13.00000 112.00 43.00 43.00   43   43 43.00    0    43
## [10,]  12.00000 13.00000  12.00 43.00 43.00   43   43 43.00   43     0
## [11,]  12.00000 12.00000  12.00 43.00 43.00   43   43 43.00   23    23
## [12,]  12.00000 12.00000  65.00 65.00 54.00   23    3  3.00   65    65
## [13,]  12.00000 12.00000  34.00 54.00 54.00   34   23 12.00   23    23
## [14,] 213.00000  3.00000   5.00  4.00  6.00    6   34 43.00  343    43
## [15,]  54.00000  5.00000   5.00  5.00  5.00   54    5  5.00  454     5
##       [,11] [,12] [,13] [,14] [,15]
##  [1,]    12    12    12   213    54
##  [2,]    12    12    12     3     5
##  [3,]    12    65    34     5     5
##  [4,]    43    65    54     4     5
##  [5,]    43    54    54     6     5
##  [6,]    43    23    34     6    54
##  [7,]    43     3    23    34     5
##  [8,]    43     3    12    43     5
##  [9,]    23    65    23   343   454
## [10,]    23    65    23    43     5
## [11,]     0    65    12     6    54
## [12,]    65     0    23    87     5
## [13,]    12    23     0    76     5
## [14,]     6    87    76     0    34
## [15,]    54     5     5    34     0

En el siguiente código implementamos el algoritmo de Floyd y mostramos una gráfica interactiva de la red (Deslizar algún nodo).

for(k in 1:15){
  for(i in 1:15){
    for(j in 1:15){
      if((k != i)&(k != j)){
        if((Costos[i,k]+ Costos[k,j]) <= (Costos[i,j])){
          A[i,j]=A[k,j]
          Costos[i,j]=min(Costos[i,j], Costos[i,k]+Costos[k,j])
        }
      }
    }
  }
}

library(igraph) 
library('visNetwork') 
library(networkD3)
library(tidyverse)
# create a dataset:
data <- data.frame(
  from=rep(c("PROMETEO", "CU", "MAGNA 1", "MAGNA 2", "COPIAS", "YEL", "TIA ALY", "T.FINANZ", "T. IDEO", "PO1", "PO2", "DARWIN", "ABC", "PULPO", "MEDIA LUNA"),15),
  to=c(rep("PROMETEO", 15), rep("CU",15),rep("MAGNA 1",15),rep("MAGNA 2",15),rep("COPIAS",15),rep("YEL",15),rep("TIA ALY",15),rep("T.FINANZ",15),rep("T. IDEO",15),rep("PO1",15),rep("PO2",15),rep("DARWIN",15), rep("ABC",15),rep("PULPO",15), rep("MEDIA LUNA",15)))

# Plot
p <- simpleNetwork(data, height="100px", width="100px",        
        Source = 1,                 # column number of source
        Target = 2,                 # column number of target
        linkDistance = 10,          # distance between node. Increase this value to have more space between nodes
        charge = -900,                # numeric value indicating either the strength of the node repulsion (negative value) or attraction (positive value)
        fontSize = 14,               # size of the node names
        fontFamily = "serif",       # font og node names
        linkColour = "blue",        # colour of edges, MUST be a common colour for the whole graph
        nodeColour = "lightblue",     # colour of nodes, MUST be a common colour for the whole graph
        opacity = 0.99,              # opacity of nodes. 0=transparent. 1=no transparency
        zoom = T                    # Can you zoom on the figure?
        )
p

La siguiente función recibe como parámetros dos lugares (de acuerdo al indice en la matriz) de los considerados para el proyecto, y regresamos la trayectoria de rutas más cortas, la matriz de adyacencia de floyd y el costo que en este caso es el tiempo

floyd_us<-function(origen, destino){
  ant<-A[origen,destino]
  trayectoria<-c(destino)
  while(origen!=ant){
      trayectoria<-c(trayectoria, ant)
      ant<-A[origen,ant]
  }
  trayectoria<-c(trayectoria, origen)
  trayectoria=trayectoria%>%rev()
  Costo=0
  n=length(places[trayectoria])
  for(i in 1:(n-1)){
    Costo=Costo+ Costos[trayectoria[i],trayectoria[i+1]]
  }
  print("Trayectoria:")
  print(places[trayectoria])
  print("Tiempo:")
  print(Costo)
  
  
  df<-data.frame(from=places[trayectoria][-n], to=places[trayectoria][-1])
  p <- simpleNetwork(df, height="100px", width="100px",        
        Source = 1,                 # column number of source
        Target = 2,                 # column number of target
        linkDistance = 10,          # distance between node. Increase this value to have more space between nodes
        charge = -900,                # numeric value indicating either the strength of the node repulsion (negative value) or attraction (positive value)
        fontSize = 14,               # size of the node names
        fontFamily = "serif",       # font og node names
        linkColour = "red",        # colour of edges, MUST be a common colour for the whole graph
        nodeColour = "white",     # colour of nodes, MUST be a common colour for the whole graph
        opacity = 0.99,              # opacity of nodes. 0=transparent. 1=no transparency
        zoom = T                    # Can you zoom on the figure?
        )
p
  
}

Ejemplo 1.

floyd_us(3,5)

## [1] "Trayectoria:"
## [1] "MAGNA 1" "MAGNA 2" "COPIAS" 
## [1] "Tiempo:"
## [1] 0.4440729

Ejemplo 2

floyd_us(7,13)

## [1] "Trayectoria:"
## [1] "TALY" "OTRO" "ABC" 
## [1] "Tiempo:"
## [1] 10.24034

Ejemplo 3

floyd_us(9,10)

## [1] "Trayectoria:"
## [1] "T. IDEO" "CU"      "OTRO"    "PO1"    
## [1] "Tiempo:"
## [1] 21.95992

UNIVERSIDAD NACIONAL AUTONOMA DE MEXICO

UNIVERSIDAD NACIONAL AUTONOMA DE MEXICO

Teoria de redes

Teoria de redes