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.