Villeneuve and Desaulniers (2005) Algorithm

It is an implementation of Villeneuve and Desaulniers' algorithm to transform a digraph and a known set of forbidden paths, into a new graph that does not allow any forbidden path as part of its solutions. This algorithm should only be used when there is certainty that no forbidden path is a sub-path (or contains a sub-path) of another forbidden path.

modify_graph_vd(g, f, cores = 1L)

Arguments

g	The digraph to be transformed, written as a data frame where each row represents a directed arc. The first two columns must be named from and to, and can be of any data type. No cells can be NULL or NA.
f	The set of forbidden paths, written as a data frame. Each row represents a path as a sequence of nodes. Each row may be of different size, filling the empty cells with NA. All nodes involved must be part of g, and no forbidden path can be of size 2. This is because the latter is thought as an arc that should not exist in the first place. Also, no forbidden path can be sub-path (or contain a sub-path) of another forbidden path. The columns names are not relevant.
cores	This algorithm can be run using R's parallel processing functions. This variable represents the number of processing cores you want to assign for the transformation. The default value is one single core. It is suggested to not assign all of your available cores to the function.

Value

A new graph, generated following Villeneuve's prodcedure, in which no path includes one of the forbidden subpaths. The graph is returned in a data frame format, where each row represents a directed arc. However, regardless of the data type of the original graph, nodes on the new graph are of type character. The new nodes names are generated by incrementally concatenating the nodes on a forbidden path, but split by a pipe character (|). The new graph includes all of the additional attributes that the original graph had.

See also

https://doi.org/10.1016/j.ejor.2004.01.032

Other Graph Transformation: modify_graph_hsu

Examples

# Obtain a graph and its forbidden subpaths
graph <- data.frame(from = c("s", "s", "s", "u", "u", "w", "w", "x", "x", "v", "v",
                             "y", "y"),
                    to = c("u", "w", "x", "w", "v", "v", "y", "w", "y", "y", "t", "t", "u"),
                    cost = c(1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L),
                    stringsAsFactors = FALSE)

fpaths <- data.frame(V1 = c("s", "u"), V2 = c("u", "v"), V3 = c("v", "y"), V4 = c("t", "u"),
                     stringsAsFactors = FALSE)

# Show the values
graph
#>    from to cost
#> 1     s  u    1
#> 2     s  w    1
#> 3     s  x    1
#> 4     u  w    1
#> 5     u  v    1
#> 6     w  v    1
#> 7     w  y    1
#> 8     x  w    1
#> 9     x  y    1
#> 10    v  y    1
#> 11    v  t    1
#> 12    y  t    1
#> 13    y  u    1
fpaths
#>   V1 V2 V3 V4
#> 1  s  u  v  t
#> 2  u  v  y  u

# Call the function and store the result
modify_graph_vd(graph, fpaths)
#>     from    to cost
#> 1      s     w    1
#> 2      s     x    1
#> 3      u     w    1
#> 4      w     v    1
#> 5      w     y    1
#> 6      x     w    1
#> 7      x     y    1
#> 8      v     y    1
#> 9      v     t    1
#> 10     y     t    1
#> 11     y     u    1
#> 12     s   s|u    1
#> 13   s|u s|u|v    1
#> 14     u   u|v    1
#> 15   u|v u|v|y    1
#> 16   s|u     w    1
#> 17 s|u|v u|v|y    1
#> 18   u|v u|v|y    1
#> 19   u|v     t    1
#> 20 u|v|y     t    1