Bidirectional algorithm is not finding valid paths when using non-zero minimum resource values

[steveharenberg]

Describe the bug Bidirectional is not finding valid paths when using non-zero minimum resource values.

To Reproduce

from networkx import *
from cspy import BiDirectional

max_res = [10, 100]
min_res = [0, 1]
rc = [1,0]

# Example 1
# Source -> 0 -> Sink is valid, but not returned.
H = DiGraph(directed=True, n_res=2)
H.add_nodes_from([0,1,2,3,4,5,6,7])

H.add_edge(0, 3, res_cost=rc, weight=1)
H.add_edge(0, 5, res_cost=rc, weight=1)
H.add_edge(0, 'Sink', res_cost=rc, weight=1)
H.add_edge(1, 3, res_cost=rc, weight=1)
H.add_edge(1, 5, res_cost=rc, weight=1)
H.add_edge(1, 'Sink', res_cost=rc, weight=1)
H.add_edge(2, 1, res_cost=rc, weight=1)
H.add_edge(2, 4, res_cost=rc, weight=1)
H.add_edge(2, 'Sink', res_cost=rc, weight=1)
H.add_edge(3, 1, res_cost=rc, weight=1)
H.add_edge(3, 4, res_cost=rc, weight=1)
H.add_edge(3, 'Sink', res_cost=rc, weight=1)
H.add_edge(4, 0, res_cost=rc, weight=1)
H.add_edge(4, 2, res_cost=rc, weight=1)
H.add_edge(4, 'Sink', res_cost=rc, weight=1)
H.add_edge(5, 0, res_cost=rc, weight=1)
H.add_edge(5, 2, res_cost=rc, weight=1)
H.add_edge(5, 'Sink', res_cost=rc, weight=1)
H.add_edge('Source', 0, res_cost=[1,1], weight=1)
H.add_edge('Source', 1, res_cost=rc, weight=1)
H.add_edge('Source', 2, res_cost=rc, weight=1)
H.add_edge('Source', 3, res_cost=rc, weight=1)
H.add_edge('Source', 4, res_cost=rc, weight=1)
H.add_edge('Source', 5, res_cost=rc, weight=1)

bidirec = BiDirectional(H, max_res, min_res, elementary=True, direction="forward")
bidirec.run()
print(bidirec.path)

# Example 2 (subgraph of example 1)
# Source -> 0 -> Sink is valid, and is correctly returned.
H2 = DiGraph(directed=True, n_res=2)
H2.add_nodes_from([0,1,2,3,4,5,6,7])

H2.add_edge(0, 'Sink', res_cost=rc, weight=1)
H2.add_edge(1, 'Sink', res_cost=rc, weight=1)
H2.add_edge('Source', 0, res_cost=[1,1], weight=1)
H2.add_edge('Source', 1, res_cost=rc, weight=1)

bidirec = BiDirectional(H2, max_res, min_res, elementary=True, direction="forward")
bidirec.run()
print(bidirec.path)

Expected behavior First example if failing to find Source->0->Sink path, which is valid. Using a subgraph, the second example is able to find this path.

Desktop (please complete the following information):

• OS: Linux
• Version 1.0.1

Suggestions TBD

[torressa]

Thanks for the report! I've pushed a unit test for this on the branch I'm using for development. It seems to work there (see here). Need to investigate why the previous release doesn't work but haven't managed to replicate it.

[steveharenberg]

Thanks! That patch seems to have fixed it. At least, this test case is working.

[torressa]

The fix discussed in #90 should be generic enough for this too. Let me know if you have any suggestions.

[steveharenberg]

The fix discussed in #90 should be generic enough for this too. Let me know if you have any suggestions.

Hey, thanks for looking at this and sorry for the delay in my response. I saw the changes from #90 on the patch90 branch, and I think the min_res changes make sense. I am not sure I fully understand checkFeasibility, but I do think the changes make it better.

I am still learning the algorithm/code, but a couple comments regarding:

https://github.com/torressa/cspy/blob/8d3cc366a5054df1b4e0b4760cd4bb53a18abc5f/src/cc/labelling.cc#L131-L137

1. Should c_res be included in that conditional? Suppose min_res[c_res] is greater than 0. Can't this prune labels too early, since resource_consumption[c_res] will be increasing?
2. More broadly, should this feasibility step only be applied to resources that have monotonic resource consumption? If not, couldn't this prune labels prematurely?

[torressa]

No worries at all!

1. Should c_res be included in that conditional? Suppose min_res[c_res] is greater than 0. Can't this prune labels too early, since resource_consumption[c_res] will be increasing?

2. More broadly, should this feasibility step only be applied to resources that have monotonic resource consumption? If not, couldn't this prune labels prematurely?

Yep both of these points are totally correct. For 2 we can probably have a preprocessing routine that detects which resources are monotonic. And/or maybe let the user input this information.

[steveharenberg]

Yeah sounds good. On the cspy side, I guess this belongs in preprocessing. I also think we must let the user specify this (I guess a simple setter method), because we don't know what the REFs are doing and that may change things (or the REFs may do everything and rc values are dummy values).

Of course, if it's not required to be specified, it may not be as clear to the user that it needs to be specified if their REFs cause non-montonicity...

I'd be happy to do a PR adding monotonicity checks, but if you want to handle it that's fine. I also don't know what branch I should be working out of, there seem to be a couple branches that are ahead of master.

[torressa]

Yeah sounds good. On the cspy side, I guess this belongs in preprocessing.

Yep.

I also think we must let the user specify this (I guess a simple setter method), because we don't know what the REFs are doing and that may change things (or the REFs may do everything and rc values are dummy values).

Yeh that's probably safest.

I'd be happy to do a PR adding monotonicity checks, but if you want to handle it that's fine.

That'd be grand, really happy for you to do it!

I also don't know what branch I should be working out of, there seem to be a couple branches that are ahead of master.

Yeh, sorry thought I'd cleared things up for the patch90 branch.. Let me clean out the unrelated stuff and set up a new branch for this. You can just send a PR to the new branch, which can then easily be merged to master for release.

[torressa]

New branch monotonic-resource-checks.

Removed the irrelevant bits (the pickup delivery stuff) and fixed some workflows (macos-11 still not building on python but I think it's cause of https://github.com/actions/setup-python/issues/279). Python tests build and test (not on macos-11 but OK everywhere else), just fail due to the test mentioned at https://github.com/torressa/cspy/issues/90#issuecomment-1008342994.