Conflict with the definition of label dominance about cspy HOT 6 CLOSED

Hi @Kuifje02!
Cheers for another bug.
The tabu algorithm doesn't give optimal paths, just resource feasible ones.
I've just quickly checked, the networkx.astar_path (used in tabu) gives the same solution.
The bidirectional algorithm however, should give the result you've stated. I'll dig into it.
Also, contributions are very welcome!

from cspy.

Hey @Kuifje02, just had another thought about this. It's actually an interesting case.
The label containing the Source-2-1-Sink path, say label_1, has a total weight of -10 and a total resource usage of [3,2].
The label containing the Source-1-Sink path, say label_2, has a total weight of 0 and a total resource usage of [1,0].
According to the definition of dominance in

To overcome this, we can add another condition to the if statement saving the final labels:

from cspy.

Yes that makes sense.
I have checked how it is implemented in the pylgrim library (a python library for the elementary constrained shortest path).
I am not sure I understand as I don't see such a criteria in his domination function :
https://github.com/ToonWeyens/pylgrim/blob/45ac035f38c33cba4e55180480316b1a442b15cd/pylgrim/ESPPRC.py#L321.
Maybe I haven't spend enough time thoroughly reading the code !

ps : I would be happy to contribute if I manage to find some time :)

from cspy.

Yeh, they did the same thing, just more elegantly, it's the standard definition for dominance (from Righini and Salani, 2006):

In pylgrim, a label b dominates a label a if and only if not a[0] < b[0] and not any(a[1] < b[1]).
I think index 0 is the cost/weight and index 1 contains an array with resource consumptions.
The converse statement would be, label b dominates a label a if both b[0] <= a[0] and all(b[1] <= a[1]) with at least one of the equalities is strict (for any resource in index 1).
This is what I tried to write in my function, however, with the single return it all seems pretty confusing (and probably misses wrong).
Additionally, when you're traversing the graph backwards the inequalities for resources get flipped.
Anyway, will change to make it less confusing.

from cspy.

Changed the definition of dominance one closer to the one in pylgrim (hence more elegant).
This wasn't enough unfortunately, since the definitions were equivalent neither label dominates.
However, if you flip the direction and check the dominance again, this flips the inequality for resources and you get a solution that has a lower cost with a still-feasible but higher resource consumption.

from cspy.

Closing for now, but needs further testing.

from cspy.