search

torressa / cspy

A collection of algorithms for the (Resource) Constrained Shortest Path problem in Python / C++ / C#
https://torressa.github.io/cspy/
MIT License
77 stars 24 forks source link

BUG: returning path with edge not in graph #17

Closed torressa closed 4 years ago

torressa commented 4 years ago

The BiDirectional algorithm with direction='both' (default) path join and checking functions are inconsistent, sometimes resulting in invalid paths (final paths with edges not it the graph).

How this can be fixed

The path joining function (https://github.com/torressa/cspy/blob/master/cspy/algorithms/bidirectional.py#L278) and path checking (https://github.com/torressa/cspy/blob/master/cspy/algorithms/bidirectional.py#L290) have to be altered to only join the forward and backward paths if they are not disconnected.

Quick Fix

For a quick fix, specify direction='forward'/'backward' when calling the BiDirectional algorithm.

torressa commented 4 years ago

Wasn't trivial but realised that negative cost cycles make things impossible for the algorithms check out networkx docs

torressa commented 4 years ago

Path joining algorithms still remains. Opened another, more specific issue #21