BiDirectional fails to find feasible paths in small graph

[dvbuntu]

Describe the bug BiDirectional sometimes fails to find a feasible path, even in small graphs when other methods succeed. If BiDirectional is an exact method, it should be able to find the constrained shortest path (given enough time), right?

To Reproduce

from networkx import DiGraph
import numpy as np
from cspy import BiDirectional, GRASP

## make a small graph, only Source->3->6->Sink is feasible
max_res, min_res = [20,30], [1,0]
H = DiGraph(directed=True, n_res=2)
H.add_edge("Source", 3, res_cost=np.array([7,13]), weight=3)
H.add_edge(3, 0, res_cost=np.array([8,10]), weight=4)
H.add_edge(3, 6, res_cost=np.array([8,3]), weight=7)
H.add_edge(3, "Sink", res_cost=np.array([15,12]), weight=1)
H.add_edge(0, "Sink", res_cost=np.array([6,3]), weight=7)
H.add_edge(6, "Sink", res_cost=np.array([3,8]), weight=8)
bidirec = BiDirectional(H, max_res, min_res, seed=42)
bidirec.run()
print(bidirec.path, bidirec.total_cost, bidirec.consumed_resources) ## empty

gr = GRASP(H, max_res, min_res)
res = gr.run()
print(gr.path, gr.total_cost, gr.consumed_resources) # correct

Expected behavior Bidirectional should find the feasible path. In this case, it should print ['Source', 3, 6, 'Sink'] 18 [18. 24.].

Desktop (please complete the following information):

• OS: CentOS
• cspy 1.0.0a0
• numpy 1.19.2
• networkx 2.5
• Python 3.8.5

Additional context This occurs in many small random graphs I tried. Sometimes it seemed like removing extra edges made it able to discover the constrained shortest path. Changing the seed did not change the results of BiDirectional in 100 trials.

[dvbuntu]

Checking a few more cases, in the above example, direction='forward' or direction='backward' work ok. It's just the direction='both' that fails. Any relation to Issue #66 or Issue #38 ?

[dvbuntu]

One can also strip down the example further to a simple chain (Source->3->6>Sink) where it fails under both despite being the only path.

[torressa]

Hey @dvbuntu indeed this is a bug, thanks!

Just added a unittest and the fix for #66 seems to give the right path in all directions. However, there's another problem, the final resource consumption is not inverted correctly for the backward direction (see log below). This should be pretty easy to fix.

I'll fix this for the next release and leave this open until then

Workflow log

1: ======================================================================
1: FAIL: test_bidirectional_backward (tests_issue69.TestsIssue69)
1: ----------------------------------------------------------------------
1: Traceback (most recent call last):
1:   File "/home/runner/work/cspy/cspy/test/python/tests_issue69.py", line 64, in test_bidirectional_backward
1:     self.assertTrue(alg.consumed_resources == self.consumed_resources)
1: AssertionError: False is not true
1: 
1: ----------------------------------------------------------------------
1: Ran 59 tests in 0.675s
1: 
1: FAILED (failures=1)
1: ['Source', 3, 6, 'Sink'] 18.0 [18.0, 24.0]
1: ['Source', 3, 6, 'Sink'] 18.0 [19.0, 24.0]
1: ['Source', 3, 6, 'Sink'] 18.0 [18.0, 24.0]