modify_graph_hsu: Hsu et al. (2009) Algorithm
In rsppfp: R's Shortest Path Problem with Forbidden Subpaths

Description Usage Arguments Details Value See Also Examples

It is an implementation of Hsu et al. 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.

1	modify_graph_hsu(g, f, cores = 1L)

`g`	The digraph to be transformed, written as a data frame where each row represents a directed arc. The columns must be named `from` and `to`, and can be of any data type. On each row 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.
`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.

This version of the algorithm produce smaller graphs, with less new nodes and arcs.

A new graph, generated following Hsu's backward construction, 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, with or without additional attributes (if corresponds). 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 (|).

https://doi.org/10.1007/978-3-642-03095-6_60

Other Graph Transformation: modify_graph_vd

# Obtain a graph and its forbidden subpaths
graph <- data.frame(from = c("c", "c", "u", "u", "t", "a", "a", "r", "e", "e", "e", 
                             "p", "i", "i", "n", "o"),
                    to = c("u", "p", "e", "t", "a", "r", "i", "u", "r", "i", "p", 
                           "n", "n", "o", "o", "m"),
                    stringsAsFactors = FALSE)
fpaths <- data.frame(X1 = c("u", "p", "a", "a"), X2 = c("t", "n", "i", "r"), 
                     X3 = c("a", "o", "n", "u"), X4 = c("r", "m", "o", NA),  
                     X5 = c("u", NA, NA, NA), stringsAsFactors = FALSE)

# Show the input
graph
fpaths

# Call the function and store the result
gStar <- modify_graph_hsu(graph, fpaths)
gStar