Why does min_res impact the output

[ZwYu-uu]

Hi! I am Zw, and I am using your cspy library in my research project. Thanks for your nice work!

I have got a problem: The following code is from your example.

# Imports
from cspy import BiDirectional
from networkx import DiGraph
from numpy import array

max_res, min_res = [4, 20], [1, 0]
# Create a DiGraph
G = DiGraph(directed=True, n_res=2)
G.add_edge("Source", "A", res_cost=[1, 2], weight=0)
G.add_edge("A", "B", res_cost=[1, 0.3], weight=0)
G.add_edge("A", "C", res_cost=[1, 0.1], weight=0)
G.add_edge("B", "C", res_cost=[1, 3], weight=-10)
G.add_edge("B", "Sink", res_cost=[1, 2], weight=10)
G.add_edge("C", "Sink", res_cost=[1, 10], weight=0)

# init algorithm
bidirec = BiDirectional(G, max_res, min_res)

# Call and query attributes
bidirec.run()
print(bidirec.path)
print(bidirec.total_cost)
print(bidirec.consumed_resources)

The output is

['Source', 'A', 'B', 'C', 'Sink']
-10.0
[4.0, 15.3]

However, when I change the code: max_res, min_res = [4, 20], [1, 0] -> max_res, min_res = [4, 20], [2, 0], the output also changes:

['Source', 'A', 'C', 'Sink']
0.0
[3.0, 12.1]

If I understand the meaning of min_res correctly, I think that the previous solution still meets the changed min_res because the consumed resource is 4.0 > 2.0. I am confused why the optimal solution changed.

Could you explain this case? Thanks very much!

[torressa]

Looks like a bug! What version are you using?

[ZwYu-uu]

Looks like a bug! What version are you using?

The version is 1.0.3.

[torressa]

The "critical" resource (default at index 0 and requires some properties such as strictly increasing) is always checked wrt resource feasibility in resource extensions see:

https://github.com/torressa/cspy/blob/bfe0b105d91a0eb0247aef98f3105953fff99277/src/cc/labelling.cc#L122-L127

You can either flip the resource definition around or change the critical resource to the resource at index 1:

bidirec = BiDirectional(G, max_res, min_res, critical_res=1)

I think this is kind off expected, I don't know about the correctness of the algorithm using the non-zero minimum resource for the "critical" resource.