rsppfp is a package that enables the transformation of graphs, and their sets of forbidden paths, to use them later with other tools. As it is part of an undergoing project, new functionalities could be added in the future.
rsppfp manipulates input and output in standard R data frame formats, maximizing its compatibility with other packages, and allowing its results to blend in with other networking tools. In the transformation functions, the primary input data consists of two different data frames and an additional parameter for parallel processing.
First, g represents the original graph as a data frame
of arcs. Arcs are mainly represented as origin-destination pairs, with
the column names from and to, respectively.
These two columns need to be in positions 1:2 of the data
frame. Each arc may or not may have additional attributes, and this is
handled internally. The nodes names may be of any simple type, such as
character, integer, double, and others; however, the returned graph
will have nodes of character type.
Second, f represents the data frame of forbidden paths,
where each row of the data frame is a path. The paths may be of
different lengths, but the unused columns must be filled with
NA or "" values. Also, all nodes used in
f must be part of g; they can be of any data
type, but they are internally manipulated as characters. Columns names
are irrelevant on this data frame. It is assumed that forbidden paths
will at least involve three nodes. This is because paths of two nodes
are simple arcs, in which case they should be directly removed from as
they are forbidden.
Third, cores is an optional parameter that enables the
use of parallel processing in these algorithms. It is recommended that
for a computer with n cores, the maximum possible value for
this parameter should be n-1, to allow one core to take
care of the operative system’s functions. If no value is received, cores
defaults to 1L, removing the parallel abilities.
The following are declarations of a graph and its set of forbidden paths.
# Create a new graph and show it.
# Each graph can be read from different sources, but that is not the scope of rsppfp.
g <- 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, 3L, 1L, 1L, 5L, 1L, 6L, 1L, 1L, 1L, 1L, 7L, 8L),
stringsAsFactors = FALSE)
# Create a list of forbidden paths, for the graph g
f <- data.frame(V1 = c("s", "u"), V2 = c("u", "v"), V3 = c("v", "y"), V4 = c("t", "u"),
stringsAsFactors = FALSE)rsppfp core implements two different transformation algorithms. In both cases, the set of forbidden paths must be known beforehand. There are also additional parsin functions. Each function documentation is available in the reference.
The first one is Villeneuve and Desaulniers (2005) transformation.
Though it supports multiple paths of different sizes, it is restricted
by the fact that no f_i ∈ F must be, or contain, a sub-path
of another f_j ∈ F where i <> j. This is
evaluated for sub-paths of at least three nodes. Using the data from
above, it can be called as:
library(rsppfp)
modify_graph_vd(g, f)
#> from to cost
#> 1 s w 3
#> 2 s x 1
#> 3 u w 1
#> 4 w v 1
#> 5 w y 6
#> 6 x w 1
#> 7 x y 1
#> 8 v y 1
#> 9 v t 1
#> 10 y t 7
#> 11 y u 8
#> 12 s s|u 1
#> 13 s|u s|u|v 5
#> 14 u u|v 5
#> 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 7The second transformation algorithm is the one developed by Hsu et al. (2009), and it is named backward construction. This algorithms also supports multiple paths of different sizes. However any forbidden path -or part of it- can be a sub-path of another forbidden path. USing the same data of the previous section, this transformation can be called as follows:
library(rsppfp)
modify_graph_hsu(g, f, cores = 1L)
#> from to cost
#> 1 s w 3
#> 2 s x 1
#> 3 u w 1
#> 4 w v 1
#> 5 w y 6
#> 6 x w 1
#> 7 x y 1
#> 8 v y 1
#> 9 v t 1
#> 10 y t 7
#> 11 y u 8
#> 23 s s|u 1
#> 24 s|u s|u|v 5
#> 25 u u|v 5
#> 26 u|v u|v|y 1
#> 27 s|u w 1
#> 28 s|u|v y 1
#> 29 u|v t 1
#> 30 u|v|y t 7Using the transformations provided implies two limitations. However, rsppfp provides additional functions to overcome them. These are:
The algorithms are only ment to work with digraphs. i.e. graphs where each arc is directed from a specific node to another node, and can only be traveled in one particular direction. There is an additional function named direct_graph(…) that converts an undirected graph to a digraph compatible with the transformation functions. This is done by duplicating each arc and inverting the duplicate’s origin-destination pair. This function also supports parallel processing.
Because the transformations add new nodes to the graphs, any path
calculated in them with be written in terms of the transformed graph.
The translation of the nodes from gStar back to the
original graph can be done using the function parse_vpath(…)
Both types of transformation functions return a graph as a data
frame, in which each row represents an arc. It maintains the main
columns from and to representing the arcs in
terms of origin and destination nodes. Additional columns represent
other arcs’ attributes, if corresponds. However, regardless of the data
type used for them in the original graph, the names of nodes of the
resulting graph are always of type character.
This is because the generation of the new nodes names follows the
proposal made by Villeneuve and Desaulniers’ (2005): as both algorithms
loop through each node on each forbidden path, new nodes names are
generated by incrementally concatenating the original names, split by
pipe. For example, for a given f_1 ∈ F = {f, c, p, t} with
the nodes named as alphabetical vowels, the new nodes are:
f|c, f|c|p, f|c|p|t. In a second
example, for f_2 ∈ F = {1988, 1985, 1958, 1963}, with nodes
as integer values, the new nodes names will be: 1988|1985,
1988|1985|1958 and 1988|1985|1958|1963.
As a result, any paths calculated in a transformed path will make use of the new nodes names.