This is an example to showcase how **rsppfp** can be used along with other existing packages.

The first step is to define the graph and its forbidden paths. This is done in the following snippet, with a set of forbidden paths defined as `F = {f_1, f_2, f_3, f_4}`

, where `f_1 = {u, v, y, u}`

, `f_2 = {w, u, y, u}`

, `f_3 = {w, v, y}`

and `f_4 = {x, w, v, y, t}`

. Though this example is defined arbitrarily, and the input data is hard-coded, it is worth noting that the input can be obtained from different sources such as databases, spreadsheet files, and others. However, that process is outside of **rsppfp**’s scope.

```
# Load the sample graph
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, 4L, 1L, 2L, 7L, 1L, 2L, 5L, 1L, 4L, 1L, 3L, 9L),
stringsAsFactors = FALSE)
# Load the forbidden paths
fpaths <- data.frame(V1 = c("u", "u", "w", "x"), V2 = c("v", "w", "v","w"), V3 = c("y", "y", "y", "v"),
V4 = c("u", "u", NA, "y"), V5 = c(NA, NA, NA, "t"), stringsAsFactors = FALSE)
```

After this, it is possible to use **rsppfp**’s functions to transform the original graph, into `G*`

. In this case, some forbidden paths have sub-paths that are part of others; particular examples are `f_3`

and `f_4`

. As a result, the example makes use of Hsu’s backward construction function.

```
# Run the algorithm and transform the graph
gStar <- modify_graph_hsu(graph, fpaths)
gStar
#> from to cost
#> 1 s u 1
#> 2 s w 4
#> 3 s x 1
#> 4 w y 2
#> 5 x y 1
#> 6 v y 4
#> 7 v t 1
#> 8 y t 3
#> 9 y u 9
#> 10 u u|v 7
#> 11 u|v u|v|y 4
#> 12 u u|w 2
#> 13 u|w u|v|y 2
#> 23 w w|v 1
#> 24 x x|w 5
#> 25 x|w x|w|v 1
#> 26 w|v t 1
#> 27 x|w y 2
#> 28 x|w|v t 1
#> 29 u|v t 1
#> 30 u|v|y t 3
#> 31 u|w w|v 1
```

The resulting data frame (named in the code as `gStar`

) can be transformed to other data types, specific of particular libraries. For example, it is possible to use the function `graph_from_data_frame(...)`

provided by igraph (Csárdi & Nepusz, 2006), to convert `gStar`

in order to use iGraph shortest-path functionalities.

```
# Transform gStar to igraph's data format
gStar.igraph <- graph_from_data_frame(gStar)
```

Even more, both graphs can be plotted using `tkplot(…)`

or `plot(...)`

function. The following code shows an example of visualization using igraphs functions.

```
# This can be used to plot the graph
plot(gStar.igraph, edge.arrow.size = 0.5, vertex.size = 20, xlab = "Graph",
vertex.color = "#F1F1F1", vertex.label.color = "#050505")
```

As any path calculated in `gStar`

will be given in terms of its nodes. Hence, as a result of the transformation process, `gStar`

nodes `nStar`

are equivalences of the original nodes. For example, a node labeled `Argo123`

in the original graph `G`

can be divided into several new `nStar_i`

, resulting in: `Troya789|Argo123`

, `Paris456|Troya789|Argo123`

and `Polux852|Argo123`

, besides the original node. Therefore, when searching for a path from a node to another node `n_i`

, the algorithm must consider all of the `nStar_i`

.

The package **rsppfp** provides an additional function to obtain this equivalences. A code example can be seen below:

```
# This can be used to plot the graph
get_all_nodes(gStar, "v")
#> [1] "v" "u|v" "w|v" "x|w|v"
```

With this, the flow to obtain a *shortest path* with any algorithm, can be summarized as follows: 1. Obtain all of the target node’s equivalences. 2. For each target node found in (1): - Get the shortest path and its weight/cost from the origin node to it. 3. The less costly path is the solution.

This algorithm has been implemented for igraph in an example function, named `get_shortest_path`

. However, although it can be used to simplify solving the shortest path, its aim is to provide guidance on how to impliment the previous logic.

Its code is the following:

```
get_shortest_path <- function(g, origin, dest, weightColName = NULL) {
#If there is no weight column specified, assume equal weights
if(is.null(weightColName)) {
g$weight <- 1
weightColName <- "weight"
# If the column could not be found...
} else if(!weightColName %in% colnames(g)) {
#Show an error
stop(weightColName, " is not a variable in `g`.")
}
# Convert the graph
g.i <- graph_from_data_frame(g)
# Get all nodes where for the destination is the destination
destEq <- get_all_nodes(g, dest)
# Find shortest paths from `origin` to all N* corresponding to `dest`
# - suppress warning if not all destinations reachable
sp <- suppressWarnings(shortest_paths(g.i, from = origin, to = destEq,
weights = edge_attr(g.i, weightColName),
output = "both"))
# Filter out zero-length paths (return if nothing left)
zero_length <- lengths(sp$epath) == 0
if (all(zero_length)) {
warning("There is no path from ", origin, " to ", dest, ".\n")
return (character(0))
} else {
sp <- lapply(sp, function(element) element[!zero_length])
}
# Find shortest of remaining paths
dist <- vapply(sp$epath,
function(path) sum(edge_attr(g.i, weightColName, path)),
numeric(1))
shortestPath <- sp$vpath[[which.min(dist)]]
# Convert path with nodes from N* to path with nodes from N
return( parse_vpath(names(shortestPath)) )
}
```

And it can be used as in the following example:

```
# Obtain the shortest path using the simplified function
shortestPath <- get_shortest_path(gStar, "u", "t", "cost")
shortestPath
#> [1] "u" "w" "v" "t"
```

Also, it is worth pointing out that a path can only be translated if it is presented as a list or vector of nodes, written sequentially. In igraph, this is known as `vpaths`

(vertexes paths). However, this step is done inside the convenience function.