Example: Other Packages

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

Preparing the Input

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

Integration with igraph

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.