Estoy estudiando el paquete igraph
para resolver un problema. Digamos que tengo la siguiente topología:
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)