A original node N_i can appear on a transformed gStar as different N_i* equivalent nodes. Therefore, this becomes a limitation when searching for a shortest path inside gStar. As a result: all N_i* need to be considered as possible destination nodes when looking for the shortest path. This function is a wrapper for this behavior, providing a straightforward implementation using igraph capabilities. However, it aims to provide guidance on how to build a similar algorithm for different path-finding algorithms.
It is important to mention that new nodes are only considered as destination nodes, and they
are not search for origin nodes. This is because N* nodes can only be reached after traveling
through gStar nodes. For example, a node "f|e|r" is actually indicating that "r"
has been reached after traveling through the nodes "f" and "e".
get_shortest_path(g, origin, dest, weightColName = NULL)
| g | A gStar digraph in data frame format, translated using one of the available functions.
The weight or cost attribute of each arc of the graph must be stored in a specific column
named |
|---|---|
| origin | The name of the starting node from G for the path. It must be written as it appears in G, and it is preferable to use a character format, but this can also be of any simple type. No lists or vectors are allowed. |
| dest | The name of the destination node from G for the path. It must be written as it appears in G, and it is preferable to use a character format, but this can also be of any simple type. No lists or vectors are allowed. |
| weightColName | The name of the weight column used in the dataframe. If the column does not exist, a name _must_ be provided so that a new weight column is generated. |
The shortest path from origin node to dest node, calculated in G*, to
include the forbidden paths. It uses igraph's functionalities.
# Given a specific gStar graph: gStar <- data.frame(from = c("u|v", "s|u|v", "s|u", "s", "s", "u", "w", "w", "x", "x", "v", "v", "y", "y", "s", "s|u", "u", "u|v"), to = c("t", "u|v|y", "w", "w", "x", "w", "v", "y", "w", "y", "y", "t", "t", "u", "s|u", "s|u|v", "u|v", "u|v|y"), weight = c(12L, 3L, 5L, 9L, 7L, 5L, 11L, 10L, 1L, 2L, 3L, 12L, 13L, 0L, 8L, 4L, 4L, 3L), stringsAsFactors = FALSE) gStar#> from to weight #> 1 u|v t 12 #> 2 s|u|v u|v|y 3 #> 3 s|u w 5 #> 4 s w 9 #> 5 s x 7 #> 6 u w 5 #> 7 w v 11 #> 8 w y 10 #> 9 x w 1 #> 10 x y 2 #> 11 v y 3 #> 12 v t 12 #> 13 y t 13 #> 14 y u 0 #> 15 s s|u 8 #> 16 s|u s|u|v 4 #> 17 u u|v 4 #> 18 u|v u|v|y 3# Obtain the shortest path get_shortest_path(gStar, "s", "v", "weight")#> [1] "s" "u" "v"