3

Estoy estudiando el paquete igraph para resolver un problema. Digamos que tengo la siguiente topología:

introducir la descripción de la imagen aquí

Cada nodo tiene posibles caminos, siempre hay que seguir la dirección de las flechas, no se puede ir en dirección contraria, los nodos tienen un orden, se puede ir de h4 a h5 pero no a h3, de todas formas esto es solo informativo, por que la topología ya tiene en cuenta esto. Los nodos tienen un atributo, en este ejemplo, está representado por el color.

Finalmente, lo que busco es poder encontrar, al menos un camino (ideal sería todos), lo más corto posible, de modo tal, que iniciando en cualquier punto, pueda asegurarme pasar al menos una vez por los tres "colores" (o atributo).

Ejemplo: h1 -> h6 -> h9, es ideal ya que paso por los tres colores en 3 pasos, pero también podría ser válido h1 -> h3 -> h4 -> h6 repito uno de los colores pero pase por los tres.

Para reproducir esta topología:

library(igraph)

nodos <- structure(list(Hito = structure(1:9, .Label = c("h1", "h2", "h3", 
                                                         "h4", "h5", "h6", "h7", "h8", "h9"), class = "factor"), tipo = structure(c(1L, 
                                                                                                                                    2L, 3L, 1L, 3L, 2L, 1L, 2L, 3L), .Label = c("A", "B", "C"), class = "factor")), class = "data.frame", row.names = c(NA, 
                                                                                                                                                                                                                                                        -9L))
topology <- structure(list(Node.1 = structure(c(1L, 1L, 1L, 1L, 1L, 2L, 2L, 
                                                2L, 2L, 2L, 3L, 3L, 3L, 4L, 4L, 4L, 4L, 5L, 5L, 5L, 6L, 6L, 7L, 
                                                7L, 8L), .Label = c("h1", "h2", "h3", "h4", "h5", "h6", "h7", 
                                                                    "h8"), class = "factor"), Node.2 = structure(c(1L, 3L, 4L, 6L, 
                                                                                                                   7L, 1L, 2L, 3L, 5L, 7L, 2L, 4L, 6L, 4L, 3L, 6L, 7L, 4L, 5L, 6L, 
                                                                                                                   5L, 7L, 6L, 7L, 7L), .Label = c("h3", "h4", "h5", "h6", "h7", 
                                                                                                                                                   "h8", "h9"), class = "factor")), class = "data.frame", row.names = c(NA, 
                                                                                                                                                                                                                        -25L))
g <- graph.data.frame(topology, vertices=nodos, directed=TRUE)
V(g)$color <- c("#006699", "#CC0000", "#009933")[as.numeric(factor(V(g)$tipo))]
plot.igraph(g, 
            vertex.size = 20, 
            edge.arrow.size = 0.5,
            vertex.label.font=2, 
            vertex.label.color="gray85",
            vertex.label.cex=1.4, 
            edge.color="gray45",
            layout=layout.kamada.kawai)

1 respuesta 1

3

Para esto he encontrado muy útil la función all_simple_paths() que construye una lista desde un nodo hasta el que le digamos, por ejemplo, desde h1 hasta h5 tenemos los siguientes caminos posibles:

all_simple_paths(g, 1, 5)
[[1]]
+ 4/9 vertices, named, from 3e33596:
[1] h1 h3 h4 h5

[[2]]
+ 2/9 vertices, named, from 3e33596:
[1] h1 h5

Con esto en mente podemos ir visitando nodo a nodo y ver que caminos nos conducen al último.

cant.nodos <- nrow(nodos)
cant.tipos <- length(unique(nodos$tipo))
to <- 1:(cant.nodos-cant.tipos+1)
l <- list(to)
for (n in 1:(cant.nodos-cant.tipos+1)) {
  l[n] <- list(all_simple_paths(g, n, cant.nodos))
}
l <- do.call(c,l)

En l tenemos la lista de todos los caminos que hemos encontrado, lo que restaría es verificar en cada caso si pasamos por los tres atributos esperados y además tratar de ubicar aquellos caminos que sean más cortos:

tipos_path <- 1:length(l)
len_path <- 1:length(l)
for (i in 1:length(l)) {
  tt <- vertex_attr(g, name="tipo", index = l[[i]])
  tipos_path[i] <- length(unique(tt))
  len_path[i] <- length(tt)
}

posibles <- max(tipos_path)
mas_corto <- min(len_path[which(tipos_path == posibles)])
l[which(tipos_path == posibles & len_path == mas_corto)]

[[1]]
+ 3/9 vertices, named, from 33df9be:
[1] h1 h6 h9

[[2]]
+ 3/9 vertices, named, from 33df9be:
[1] h1 h8 h9

[[3]]
+ 3/9 vertices, named, from 33df9be:
[1] h2 h4 h9

[[4]]
+ 3/9 vertices, named, from 33df9be:
[1] h2 h7 h9

[[5]]
+ 3/9 vertices, named, from 33df9be:
[1] h4 h6 h9

[[6]]
+ 3/9 vertices, named, from 33df9be:
[1] h4 h8 h9

[[7]]
+ 3/9 vertices, named, from 33df9be:
[1] h6 h7 h9

[[8]]
+ 3/9 vertices, named, from 33df9be:
[1] h7 h8 h9

Finalmente, obtuvimos una lista ideal de los 8 caminos más cortos en los que pasamos por todos los colores.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.