BiDirectional functionality for non-elementary paths

[kevindalmeijer]

Version: 0.1.2 (installed through pip)

In the following example, I expected BiDirectional to return the path Source -> A -> B -> C -> A -> Sink with cost -30. Instead, the path Source -> A -> Sink with cost 0 is returned.

The same behavior occurs with direction="forward" and elementary=False.

My best guess is that something is going on with negative cycles. In Issue #33 it is mentioned that the check was removed, and tests were done on vehicle routing problems. In vehicle routing, you typically try to avoid negative cycles anyways, so that could be a reason why everything seemed ok at that point.

from cspy import BiDirectional
from networkx import DiGraph
from numpy import array
G = DiGraph(directed=True, n_res=2)
G.add_edge("Source", "A", res_cost=array([1, 1]), weight=0)
G.add_edge("A", "B", res_cost=array([1, 1]), weight=-10)
G.add_edge("B", "C", res_cost=array([1, 1]), weight=-10)
G.add_edge("C", "A", res_cost=array([1, 1]), weight=-10)
G.add_edge("A", "Sink", res_cost=array([1, 1]), weight=0)
max_res, min_res = [5, 5], [0, 0]
bidirec = BiDirectional(G, max_res, min_res, direction="both")
bidirec.run()
print(bidirec.path)

[torressa]

Hey @kevindalmeijer, thanks for the issue! Currently the elementary option doesn't do anything as elementary paths are basically hard-coded. I did a fair amount of experiments to do it properly but performance was absolutely terrible for large instances. However, I'm in the process of re-writing the algorithm in C++ and non-elementary paths are definitely a priority. Unfortunately, this means that it might take a while to fix this. I'll commit some initial work on the C++ work soon so feel free to contribute :)

[kevindalmeijer]

Hi @torressa, thank you for putting it on the todo list. I like that this project is defined on top of networkx, which makes it a lot easier to work with. Instead of re-writing in C++, you might be able to utilize https://www.boost.org/doc/libs/1_73_0/libs/graph/doc/r_c_shortest_paths.html, although I don't know how that would work with the dependencies in Python.

[torressa]

Thanks for that I'd forgotten it existed! That's a monodirectional algorithm so I still need to write the bi-directional version but I could still maybe use the same structure/constructs there.

[torressa]

Seems to work on the WIP 3048e8a2948fd28e1debb4155156f1307cef9239. I've added a unit test here