k-shortest-path

k-shortest-path implements various algorithms for the K shortest path problem. Currently, the only implementation is for the deviation path algorithm by Martins, Pascoals and Santos (see 1 and 2) to generate all simple paths from from (any) source to a fixed target.

Installation

pip3 install pipenv
git clone git@github.com:datagovsg/k-shortest-path.git
cd k-shortest-path
pipenv install

Usage

Create one kspath.deviation_path.mps.SingleTargetDeviationPathAlgorithm object for all source-target pairs with a fixed target as this will reduce the number of calls to Dijkstra's algorithm

1. kspath.deviation_path.mps.SingleTargetDeviationPathAlgorithm.create_from_graph(G, target, weight, max_consecutive_cycles=500)

Parameters

• G (NetworkX graph)
• target (node) – Ending node for path
• weight (string) – Name of the edge attribute to be used as a weight. If None all edges are considered to have unit weight.
• max_consecutive_cycles (int) – Maximum number of deviation paths to search before switching to Yen's algorithm

Returns

• kspath.deviation_path.mps.SingleTargetDeviationPathAlgorithm object

Raises

• NodeNotFound – If target does not exist in G

2. kspath.deviation_path.mps.SingleTargetDeviationPathAlgorithm.shortest_simple_paths(source)

Parameters

• source (node) – Starting node for path

Returns

• generator

Raises

• NodeNotFound – If source does not exist in G

from kspath.deviation_path.mps import SingleTargetDeviationPathAlgorithm

dpa_mps = SingleTargetDeviationPathAlgorithm.create_from_graph(G=G, target=6, weight='weight')
paths = []
for path_count, path in enumerate(dpa_mps.shortest_simple_paths(source=1), 1):
    paths.append(path)
    if path_count == 100:
        break

Tests

For simple test cases, install pytest and run in the top level directory.

pipenv install pytest --dev
pytest -m fast

For a larger test, run

pytest -m slow

This takes a couple of minutes to complete.

For more comprehensive test cases, run

pytest -m comprehensive

This takes approximately fifteen days to complete.

*Both slow and comprehensive tests requires the right credentials to download the data from a private repo.