,
Aldo Vecchietti [aut]| Title: | R's Shortest Path Problem with Forbidden Subpaths |
|---|---|
| Description: | An implementation of functionalities to transform directed graphs that are bound to a set of known forbidden paths. There are several transformations, following the rules provided by Villeneuve and Desaulniers (2005) <doi: 10.1016/j.ejor.2004.01.032>, and Hsu et al. (2009) <doi: 10.1007/978-3-642-03095-6_60>. The resulting graph is generated in a data-frame format. See rsppfp website for more information, documentation an examples. |
| Authors: | Melina Vidoni [aut, cre] ,
Aldo Vecchietti [aut] |
| Maintainer: | Melina Vidoni <[email protected]> |
| License: | GPL-3 |
| Version: | 1.0.4 |
| Built: | 2024-10-06 03:18:46 UTC |
| Source: | https://github.com/melvidoni/rsppfp |
The SPPFP transformation functions only work with digraphs -i.e. directed graphs.
Because in a digraph arcs can only be traveled in one direction, from the origin node to the
destination arc, if undirected graphs are used as-is, the resultng G* will not be accurate.
Therefore, this functions translates an undirected graph to a
digraph by duplicating each arc and swapping the duplicate's from and to nodes.
direct_graph(graph, cores = 1L)direct_graph(graph, cores = 1L)
graph |
An undirected graph written as a data frame, in which each rows represent an arc.
The columns must be named |
cores |
This algorithm can be run using R's parallel processing functions. This variable represents the number of processing cores you want to assign for the transformation. The default value is one single core. It is suggested to not assign all of your available cores to the function. |
A new graph, with the same columns and data types of the original graph. This new graph is twice as big as the original, as new arcs are added to represent that each arc can be traveled in both directions.
Other Parsers: get_all_nodes,
parse_vpath
# Obtain the graph from any way 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, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L), stringsAsFactors = FALSE) graph # Translate it digraph <- direct_graph(graph) digraph# Obtain the graph from any way 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, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L), stringsAsFactors = FALSE) graph # Translate it digraph <- direct_graph(graph) digraph
A original node N_i can appear on a transformed G* as different nodes. This is the result of the creation of nodes in the transformation processes. Therefore, it is possible that the original node N does not exists on G*, or that multiple N_i* exist. Hence, as all new nodes are generated using a specific structure for the name -compiling all previous nodes names, split by pipe-, this function allows searching for all the N_i* nodes that are equivalente to N_i. This can be used to find shortest paths to all of them.
get_all_nodes(g, originalNode)get_all_nodes(g, originalNode)
g |
A graph in data frame format, translated using one of the available functions. |
originalNode |
The name of the original node from G, that needs to be searched within G*. It is preferable to use a character format, but this can also be of any simple type. No lists or vectors are allowed. |
A new vector of character type, whose elements are all the N_i* equivalent to the original N node. This also includes the original node.
Other Parsers: direct_graph,
parse_vpath
# Given a specific gStar graph: gStar <- data.frame(from = c("u|v", "s|u|v", "s|u", "s", "s", "u", "w", "w", "x", "x", "v", "v", "y", "y", "s", "s|u", "u", "u|v"), to = c("t", "u|v|y", "w", "w", "x", "w", "v", "y", "w", "y", "y", "t", "t", "u", "s|u", "s|u|v", "u|v", "u|v|y"), weight = c(12L, 3L, 5L, 9L, 7L, 5L, 11L, 10L, 1L, 2L, 3L, 12L, 13L, 0L, 8L, 4L, 4L, 3L), stringsAsFactors = FALSE) gStar # Obtain all the nodes equivalent to N_i = "v" get_all_nodes(gStar, "v")# Given a specific gStar graph: gStar <- data.frame(from = c("u|v", "s|u|v", "s|u", "s", "s", "u", "w", "w", "x", "x", "v", "v", "y", "y", "s", "s|u", "u", "u|v"), to = c("t", "u|v|y", "w", "w", "x", "w", "v", "y", "w", "y", "y", "t", "t", "u", "s|u", "s|u|v", "u|v", "u|v|y"), weight = c(12L, 3L, 5L, 9L, 7L, 5L, 11L, 10L, 1L, 2L, 3L, 12L, 13L, 0L, 8L, 4L, 4L, 3L), stringsAsFactors = FALSE) gStar # Obtain all the nodes equivalent to N_i = "v" get_all_nodes(gStar, "v")
A original node N_i can appear on a transformed gStar as different N_i* equivalent nodes. Therefore, this becomes a limitation when searching for a shortest path inside gStar. As a result: all N_i* need to be considered as possible destination nodes when looking for the shortest path. This function is a wrapper for this behavior, providing a straightforward implementation using igraph capabilities. However, it aims to provide guidance on how to build a similar algorithm for different path-finding algorithms.
It is important to mention that new nodes are only considered as destination nodes, and they
are not search for origin nodes. This is because N* nodes can only be reached after traveling
through gStar nodes. For example, a node "f|e|r" is actually indicating that "r"
has been reached after traveling through the nodes "f" and "e".
get_shortest_path(g, origin, dest, weightColName = NULL)get_shortest_path(g, origin, dest, weightColName = NULL)
g |
A gStar digraph in data frame format, translated using one of the available functions.
The weight or cost attribute of each arc of the graph must be stored in a specific column
named |
origin |
The name of the starting node from G for the path. It must be written as it appears in G, and it is preferable to use a character format, but this can also be of any simple type. No lists or vectors are allowed. |
dest |
The name of the destination node from G for the path. It must be written as it appears in G, and it is preferable to use a character format, but this can also be of any simple type. No lists or vectors are allowed. |
weightColName |
The name of the weight column used in the dataframe. If the column does not exist, a name _must_ be provided so that a new weight column is generated. |
The shortest path from origin node to dest node, calculated in G*, to
include the forbidden paths. It uses igraph's functionalities.
# Given a specific gStar graph: gStar <- data.frame(from = c("u|v", "s|u|v", "s|u", "s", "s", "u", "w", "w", "x", "x", "v", "v", "y", "y", "s", "s|u", "u", "u|v"), to = c("t", "u|v|y", "w", "w", "x", "w", "v", "y", "w", "y", "y", "t", "t", "u", "s|u", "s|u|v", "u|v", "u|v|y"), weight = c(12L, 3L, 5L, 9L, 7L, 5L, 11L, 10L, 1L, 2L, 3L, 12L, 13L, 0L, 8L, 4L, 4L, 3L), stringsAsFactors = FALSE) gStar # Obtain the shortest path get_shortest_path(gStar, "s", "v", "weight")# Given a specific gStar graph: gStar <- data.frame(from = c("u|v", "s|u|v", "s|u", "s", "s", "u", "w", "w", "x", "x", "v", "v", "y", "y", "s", "s|u", "u", "u|v"), to = c("t", "u|v|y", "w", "w", "x", "w", "v", "y", "w", "y", "y", "t", "t", "u", "s|u", "s|u|v", "u|v", "u|v|y"), weight = c(12L, 3L, 5L, 9L, 7L, 5L, 11L, 10L, 1L, 2L, 3L, 12L, 13L, 0L, 8L, 4L, 4L, 3L), stringsAsFactors = FALSE) gStar # Obtain the shortest path get_shortest_path(gStar, "s", "v", "weight")
It is an implementation of Hsu et al. algorithm to transform a digraph and a known set of forbidden paths, into a new graph that does not allow any forbidden path as part of its solutions.
modify_graph_hsu(g, f, cores = 1L)modify_graph_hsu(g, f, cores = 1L)
g |
The digraph to be transformed, written as a data frame where each row represents a
directed arc. The columns must be named |
f |
The set of forbidden paths, written as a data frame. Each row represents a path
as a sequence of nodes. Each row may be of different size, filling the empty cells with
|
cores |
This algorithm can be run using R's parallel processing functions. This variable represents the number of processing cores you want to assign for the transformation. The default value is one single core. It is suggested to not assign all of your available cores to the function. |
This version of the algorithm produce smaller graphs, with less new nodes and arcs.
A new graph, generated following Hsu's backward construction, in which no path
includes one of the forbidden subpaths. The graph is returned in a data frame format,
where each row represents a directed arc, with or without additional attributes (if
corresponds). However, regardless of the data type of the original graph, nodes on the
new graph are of type character. The new nodes names are generated by incrementally
concatenating the nodes on a forbidden path, but split by a pipe character (|).
https://doi.org/10.1007/978-3-642-03095-6_60
Other Graph Transformation: modify_graph_vd
# Obtain a graph and its forbidden subpaths graph <- data.frame(from = c("c", "c", "u", "u", "t", "a", "a", "r", "e", "e", "e", "p", "i", "i", "n", "o"), to = c("u", "p", "e", "t", "a", "r", "i", "u", "r", "i", "p", "n", "n", "o", "o", "m"), stringsAsFactors = FALSE) fpaths <- data.frame(X1 = c("u", "p", "a", "a"), X2 = c("t", "n", "i", "r"), X3 = c("a", "o", "n", "u"), X4 = c("r", "m", "o", NA), X5 = c("u", NA, NA, NA), stringsAsFactors = FALSE) # Show the input graph fpaths # Call the function and store the result gStar <- modify_graph_hsu(graph, fpaths) gStar# Obtain a graph and its forbidden subpaths graph <- data.frame(from = c("c", "c", "u", "u", "t", "a", "a", "r", "e", "e", "e", "p", "i", "i", "n", "o"), to = c("u", "p", "e", "t", "a", "r", "i", "u", "r", "i", "p", "n", "n", "o", "o", "m"), stringsAsFactors = FALSE) fpaths <- data.frame(X1 = c("u", "p", "a", "a"), X2 = c("t", "n", "i", "r"), X3 = c("a", "o", "n", "u"), X4 = c("r", "m", "o", NA), X5 = c("u", NA, NA, NA), stringsAsFactors = FALSE) # Show the input graph fpaths # Call the function and store the result gStar <- modify_graph_hsu(graph, fpaths) gStar
It is an implementation of Villeneuve and Desaulniers' algorithm to transform a digraph and a known set of forbidden paths, into a new graph that does not allow any forbidden path as part of its solutions. This algorithm should only be used when there is certainty that no forbidden path is a sub-path (or contains a sub-path) of another forbidden path.
modify_graph_vd(g, f, cores = 1L)modify_graph_vd(g, f, cores = 1L)
g |
The digraph to be transformed, written as a data frame where each row represents
a directed arc. The first two columns must be named |
f |
The set of forbidden paths, written as a data frame. Each row represents a path as
a sequence of nodes. Each row may be of different size, filling the empty cells with
|
cores |
This algorithm can be run using R's parallel processing functions. This variable represents the number of processing cores you want to assign for the transformation. The default value is one single core. It is suggested to not assign all of your available cores to the function. |
A new graph, generated following Villeneuve's prodcedure, in which no path
includes one of the forbidden subpaths. The graph is returned in a data frame format,
where each row represents a directed arc. However, regardless of the data type of the
original graph, nodes on the new graph are of type character. The new nodes names are
generated by incrementally concatenating the nodes on a forbidden path, but split by a
pipe character (|). The new graph includes all of the additional attributes
that the original graph had.
https://doi.org/10.1016/j.ejor.2004.01.032
Other Graph Transformation: modify_graph_hsu
# Obtain a graph and its forbidden subpaths 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, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L), stringsAsFactors = FALSE) fpaths <- data.frame(V1 = c("s", "u"), V2 = c("u", "v"), V3 = c("v", "y"), V4 = c("t", "u"), stringsAsFactors = FALSE) # Show the values graph fpaths # Call the function and store the result modify_graph_vd(graph, fpaths)# Obtain a graph and its forbidden subpaths 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, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L), stringsAsFactors = FALSE) fpaths <- data.frame(V1 = c("s", "u"), V2 = c("u", "v"), V3 = c("v", "y"), V4 = c("t", "u"), stringsAsFactors = FALSE) # Show the values graph fpaths # Call the function and store the result modify_graph_vd(graph, fpaths)
Translates a sequence of nodes from a G* graph, generated with any of the available transformations, to a sequence of nodes in terms of the original G.
parse_vpath(vpath)parse_vpath(vpath)
vpath |
A vector of character type, representing a path as a sequence of nodes. The nodes are supposed to belong to an original graph G, but be written in terms of G*. |
A new vector of character type, representing the same path as vpath but with
the nodes names translated to the original graph G's names.
Other Parsers: direct_graph,
get_all_nodes
# Obtain the vpath from any way, an algorithm or random walk. # Call the parsing function translated_vpath <- parse_vpath( c("s|u", "s|u|v", "u|v|y", "t") ) # Print the result translated_vpath# Obtain the vpath from any way, an algorithm or random walk. # Call the parsing function translated_vpath <- parse_vpath( c("s|u", "s|u|v", "u|v|y", "t") ) # Print the result translated_vpath
Transformation algorithms to translate the SPPFP (Shortest Path Problem with Forbidden Paths) to a traditional shortest-path problem that includes the forbidden paths.
The SPPFP is a variant of the traditional shortest path problem, in which no solution can include any path listed on a known set of forbidden paths. The current approach to solve this is to translate the existing graph, and its set of forbidden paths, to a graph in which no path will include any forbidden sequence. This package provides straightforward parallel processing capabilities, as well as translation functions to use the algorithms on undirected graphs. It is highly compatible with other network research packages, as it only uses native R data types.