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)
The rsppfp package implements different algorithms for transforming graphs in the Shortest Path Problem with Forbidden Paths (SPPFP). This problem is an important concept in the field of graph theories, and it is a variant of the traditional shortest path problem. In here, there is an additional constrait that takes the form of a finite set of forbidden paths (arc sequences of at least three nodes) that cannot be part of any solution path.
This problem is solved by transforming the original graph
G and its set of forbidden paths
F, generating a new graph
G* in which traditional shortest path algorithms can be applied, and obtain solutions that abide to the restrictions. This approach has a number of advantages:
G*with algorithms that efficiently manage time and processing resources constraints, having been implemented in a plethora of languages.
G*is highly compatible with existing libraries, and can be used as input data for other, more complex problems and researches.
Fremain unchanged for long periods of time. Thus, the transformation is completed only once, and
G*can be stored along with the original graph. A new conversion is required only on the rare cases where the graph, or its forbidden paths, are modified.
This solving process is illustrated in Figure 1, using a paper notation to indicate input and output data. Even more, rsppfp scope and key functionalities are also highlighted.
rsppfp implements two different algorithms, each one suited for different situations:
Fmust be known beforehand. This transformation is slightly fast, but generates bigger graphs
G*. Each forbidden path can be of different size, but no sub-path (of at least three nodes long) can be part of another forbidden path.
G*, by adding less new nodes and arcs. However, this algorithm is slightly slower.
Both algorithms are analyzed using 27 graphs, randomly generated. The complete benchmark evaluation can be found here.
As from 2018-11-22 you can install rsppfp directly from CRAN, using:
You can also install the development version of rsppfp from GitHub with:
Available at References
Stable release with minor bug fixes. Released February 2019.
get_shortest_path()function, to improve its functionality.
Stable release of advanced implementation of rsppfp, with minor bug fixes. Released November 2018.
get_shortest_path(). The user is now required to explicit the
weightattribute name. If it does not exist, a standard weight of 1 is added to the graph.
data.frame(), instead of using
structure()The importance of using
stringAsFactors = FALSEhas been highlighted.
on.exit(), so that if the function terminates early, all the connections will still be closed.
Stable release of advanced implementation of rsppfp, with minor bug fixes. Released October 2018.
to, and an undefined number of attributes) the resulting
gStarhas the attributes in the correct order.
First stable release of advanced implementation of rsppfp, released on June 2018.
First stable release of advanced implementation of rsppfp! Includes the following functions: