Comparator Function for CQYDirectedPath does not provide a strict weak ordering.

[GoogleCodeExporter]

The STL set function requires that the sorting criterion define a "strict 
weak ordering." In other words, the ordering has to be antisymmetric, 
transitive, and irreflexive.

Your Comparator function for CQYDirectedPath violates both the 
antisymmetric and irreflexive properties. Assume x and y are two paths with 
identical costs and lengths. Your implementation will have both x < y and y 
< x. Thus, not antisymmetric. Also, x < x will return true when it should 
return false.

If you add a third parameter, I used the ID, the Comparator function works 
as expected. This assumes that the IDs are unique, but I think that is a 
safe assumption.

I really believe this error should be fixed. Most of the time, the bug has 
no impact upon the results. However, in some cases this bug does lead to 
incorrect results and it may generate a run time error on some compilers.

I have attached my fix to the bug.

Original issue reported on code.google.com by [email protected] on 1 Sep 2009 at 5:05

Attachments:

• QYDirectedPath.h

[GoogleCodeExporter]

Thank you for this. I agree that's a serious bug needing to be fixed. One may 
not 
notice it with arbitrary link weights because of the low probability of having 
more 
than one path with the same cost. But in cases when you use a constant weight 
for each 
hop, this bug makes the code impossible to run.

Original comment by [email protected] on 20 Jan 2010 at 7:05