Hsu et al. (2009) Algorithm

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.

modify_graph_hsu(g, f, cores = 1L)

Arguments

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.

Value

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 (|).

Details

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

See also

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

Other Graph Transformation: modify_graph_vd

Examples

# 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
#>    from to
#> 1     c  u
#> 2     c  p
#> 3     u  e
#> 4     u  t
#> 5     t  a
#> 6     a  r
#> 7     a  i
#> 8     r  u
#> 9     e  r
#> 10    e  i
#> 11    e  p
#> 12    p  n
#> 13    i  n
#> 14    i  o
#> 15    n  o
#> 16    o  m
fpaths
#>   X1 X2 X3   X4   X5
#> 1  u  t  a    r    u
#> 2  p  n  o    m <NA>
#> 3  a  i  n    o <NA>
#> 4  a  r  u <NA> <NA>

# Call the function and store the result
gStar <- modify_graph_hsu(graph, fpaths)
gStar
#>     from      to
#> 1      c       u
#> 2      c       p
#> 3      u       e
#> 4      t       a
#> 5      r       u
#> 6      e       r
#> 7      e       i
#> 8      e       p
#> 9      i       n
#> 10     i       o
#> 11     n       o
#> 12     o       m
#> 25     u     u|t
#> 26   u|t   u|t|a
#> 27 u|t|a u|t|a|r
#> 28     p     p|n
#> 29   p|n   p|n|o
#> 30     a     a|i
#> 31   a|i   a|i|n
#> 32     a     a|r
#> 33 u|t|a     a|i
#> 34   a|i       o