I am studying the package igraph
to solve a problem. Let's say I have the following topology:
Each node has possible paths, you always have to follow the direction of the arrows, you cannot go in the opposite direction, the nodes have an order, you can go from h4
to h5
but not to h3
, anyway this is only informative, because the topology already takes this into account. Nodes have an attribute, in this example, it is represented by color.
Finally, what I am looking for is to be able to find at least one path (ideally all of them), as short as possible, in such a way that, starting at any point, I can make sure I go through the three "colors" (or attributes) at least once. ).
Example: h1 -> h6 -> h9
, it is ideal since I go through the three colors in 3 steps, but it could also be valid if h1 -> h3 -> h4 -> h6
I repeat one of the colors but go through all three.
To reproduce this topology:
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)
For this I have found very useful the function
all_simple_paths()
that builds a list from a node to which we say, for example, fromh1
toh5
we have the following possible paths:With this in mind we can go visiting node by node and see which paths lead us to the last one.
In
l
we have the list of all the paths that we have found, what remains is to verify in each case if we go through the three expected attributes and also try to locate those paths that are shorter:Finally, we got an ideal list of the 8 shortest paths in which we go through all the colors.