R's Shortest Path Problem with Forbidden Subpaths

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) , and Hsu et al. (2009) . The resulting graph is generated in a data-frame format. See rsppfp website for more information, documentation an examples.


CRAN_Status_Badge CRAN Downloads Travis-CI Build Status Coverage Status License: GPL v3 DOI

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:

  • It allows solving the original shortest path problem in G* with algorithms that efficiently manage time and processing resources constraints, having been implemented in a plethora of languages.
  • The resulting G* is highly compatible with existing libraries, and can be used as input data for other, more complex problems and researches.
  • In many cases -i.e. logistics- G and F remain 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.
  • The input data is provided as common data frames, increasing the versatility of this package.

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.

Algorithms

rsppfp implements two different algorithms, each one suited for different situations:

  1. Villeneuve and Desaulniers (2005) proposed the first algorithm. In this case, the set F must 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.
  2. Hsu et al. 'Backward Construction' (2009) solves the restriction of sub-paths in the forbidden paths, and generates smaller graphs 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.

Installation

As from 2018-11-22 you can install rsppfp directly from CRAN, using:

install.packages("rsppfp")

You can also install the development version of rsppfp from GitHub with:

# install.packages("devtools")
devtools::install_github("melvidoni/rsppfp")

References

Available at References

News

RSPPFP 1.0.4

Stable release with minor bug fixes. Released February 2019.

Minor Bug Fixes and Improvements

  • Fixed bugs for missing nodes on both transformation algorithms.
  • The numeric or integer attributes on graphs with multiple attributes are no longer converted to characters. They are parsed to the generic numeric format.
  • Minor wording changes on warnings and error messages.
  • Updates to the get_shortest_path() function, to improve its functionality.

RSPPFP 1.0.3

Stable release of advanced implementation of rsppfp, with minor bug fixes. Released November 2018.

Minor Bug Fixes and Improvements

  • Additional checks have been added to Hsu's and Villeneuve's transformation. The algorithms now stop if certain conditions are not met, such as: columns' names, use of non-existent nodes in forbidden paths, and subpaths inclusions for Villeneuve's algorithms.
  • Additional handling of the weight has been added to the convenience function get_shortest_path(). The user is now required to explicit the weight attribute name. If it does not exist, a standard weight of 1 is added to the graph.
  • All examples and documentation now feature data frames created with data.frame(), instead of using structure() The importance of using stringAsFactors = FALSE has been highlighted.
  • Cluster closing has been moved to on.exit(), so that if the function terminates early, all the connections will still be closed.
  • The benchmark on the website now showcases the results for all the evaluated density types.

RSPPFP 1.0.2

Stable release of advanced implementation of rsppfp, with minor bug fixes. Released October 2018.

Minor Bug Fixes and Improvements

  • Fixed Hsu's transformation: when having more than three columns (from and to, and an undefined number of attributes) the resulting gStar has the attributes in the correct order.
  • Improved Hsu's transformation: previous to working, it deletes empty rows from the set of forbidden paths. Empty rows are those in which all of the cells contain either only blank spaces or NA values.

RSPPFP 1.0.0

First stable release of advanced implementation of rsppfp, released on June 2018.

Major Changes

First stable release of advanced implementation of rsppfp! Includes the following functions:

  • Transformation algorithms (Villeneuve & Desaulniers, and Hsu's et al.).
  • Basic parsing functions: graph-to-digraph, and vpath translation.
  • Integration functions: equivalent nodes selection, and igraph's integration.

Reference manual

It appears you don't have a PDF plugin for this browser. You can click here to download the reference manual.

install.packages("rsppfp")

1.0.4 by Melina Vidoni, 9 months ago


https://github.com/melvidoni/rsppfp


Report a bug at https://github.com/melvidoni/rsppfp/issues


Browse source code at https://github.com/cran/rsppfp


Authors: Melina Vidoni [aut, cre] , Aldo Vecchietti [aut]


Documentation:   PDF Manual  


GPL-3 license


Imports dplyr, foreach, doParallel, igraph, tidyr, stringr

Suggests knitr, rmarkdown, testthat, covr, ggplot2


See at CRAN