--- title: "Example: Other Packages" output: rmarkdown::html_vignette resource_files: - fig2.png vignette: > %\VignetteIndexEntry{Example: Other Packages} %\VignetteEngine{knitr::rmarkdown} %\VignetteEncoding{UTF-8} --- ```{r setup, include = FALSE} knitr::opts_chunk$set( collapse = TRUE, comment = "#>" ) library(rsppfp) library(igraph) library(foreach) library(doParallel) library(dplyr) ``` 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. ```{r} # 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. ```{r} # Run the algorithm and transform the graph gStar <- modify_graph_hsu(graph, fpaths) gStar ``` ## 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. ```{r} # 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. ```{r, fig.show='hold'} # 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: ```{r} # This can be used to plot the graph get_all_nodes(gStar, "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`](reference/get_shortest_path.html). 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: ```{r, eval=FALSE} 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: ```{r, warning=FALSE} # Obtain the shortest path using the simplified function shortestPath <- get_shortest_path(gStar, "u", "t", "cost") shortestPath ``` 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.