shortestpaths 0.3.0

Bidirectional replacement paths and k-shortest paths search with dynamic programming

ShortestPaths

Bidirectional replacement-paths and k-shortest paths search with dynamic programming

requirements
python3
click>=7.1.2
networkx>=2.5
numpy>=1.19.2
matplotlib>=3.3.2

Overview

ShortestPaths constitutes thesis source code. It examines the optimization of the bidirectional replacement-paths and k-shortest paths search, using dynamic programming. The algorithm proposed memoizes the states of the search of the parent path and retrieves them upon searching the consequent paths. The optimization was validated experimentally in a parametric analysis of tree parameters, the order, the density and the topology of the graph. The replacement paths problem is solved on both edge-exclusive and node-exlusive variations, as well as both online and offline versions. Regarding the k-shortest paths problem, k online replacement-paths searches are executed, following Yen's algorithm with Lawler's modification, while utilizing the developed bidirectional search with dynamic programming. Dijkstra's algorihtm is used for the shortest path search and a modified Erdős-Rényi random graph model is introduced, controling the density and the topology of the graph. More specifically, the small world property is captured by the topology of the graph, resulting to more realistic representations.

The four supported methods for the k-shortest paths search are:

1. Yen + Dijkstra
2. Lawler + Dijkstra
3. Lawler + Bid. Dijkstra
4. Lawler + Bid. Dijkstra + DP

A PriorityQueue class is implemented as a wrapper around heapq, using the <priority, entry_counter, entry> triple, as suggested here.

Thesis supervisor: Prof. Kostas Siozios

Install

$ conda install -c mattasa shortestpaths

$ pip install shortestpaths

Usage

$ ksp [OPTIONS] N COMMAND [OPTIONS]

Options:
  -k INTEGER                      number of shortest paths to be generated
                                  [default: 1]
  --weighted / --no-weighted      [default: True]
  --directed
  --weights-on [edges|nodes|edges-and-nodes]
                                  [default: edges-and-nodes]
  --max-edge-weight INTEGER       [default: 1000]
  --max-node-weight INTEGER       [default: 50]
  -y, --yen
  -l, --lawler
  -b, --bidirectional             use bidirectional shortest path search
  -p, --parallel                  use multiprocessing
  -d, --dynamic                   use dynamic programming
  -s, --seed INTEGER              for random graph
  --layout-seed INTEGER           fixes the random initialization of the
                                  spirng_layout.  [default: 1]
  --show-graph                    plots up to 8 paths
  --save-graph                    format: png
  -v, --verbose                   prints the generated paths

replacement-paths Options:
  -f, --failing [edges|nodes]  Setting what to fail, path edges or path nodes,
                               in order to produce the replacement paths.
                               [default: nodes]

  --online                     When online, the path up until the failure is
                               kept as it is (the algorithm is getting
                               informed upon meeting the failed node or edge),
                               whereas when not online, a new search starts
                               from the source, ignoring the parent-path (the
                               algorithm is a priori informed about the
                               failure).

Examples

$ ksp -v 100
$ ksp --show-graph -k 5 100
$ ksp -v -d -k 20 1000
$ ksp -v --show-graph 200 replacement-paths --failing edges
$ ksp -v --show-graph 200 replacement-paths --failing edges --online

Test

$ pytest --cov=shortestpaths shortestpaths

State retrieval | Replacement-paths offline

State retrieval | Replacement-paths online

License

GNU General Public License v3.0

(C) 2020, Athanasios Mattas
[e-mail]