Incorrect distance matrix with the slow algorithm

[neumannjan]

The fast algorithm produces correct results, whereas the slow algorithm produces incorrect results.

For the provided adjacency matrix, the first 10 values of the very first row of the distance matrix are:

• 0, 5465, 766658, 765271, 762264, 756299, 749390, 748017, 861825, 870365 for the fast algorithm
• 0, 5465, 462406, 461019, 458012, 452047, 445138, 443765, 861825, 870365 for the slow algorithm

:( I have yet to figure out why.

[F-I-D-O]

Ok, first question, how do you know which version is correct?

[neumannjan]

@F-I-D-O I compared the output of the fast version with the expected result (dm.csv file) you provided me via ownCloud. Also, the result for the slow algorithm contains lots of strangely repeated values, so I expect it to be a memory issue somewhere? Or maybe the algorithm itself is somehow broken

[neumannjan]

It works for smaller graphs, the results are identical for both algorithms

[F-I-D-O]

Ok, then please find the bug int the slow alg. and fix it. The slow algorithm is used inside other preprocessing algorithms, so we cannot discard it right now, can we?

[neumannjan]

Just found out that the slow algorithm operates correctly in c72bbd8. Edit: also newer b4b2f30 Edit: 8a88735 is the commit to blame

Ok, then please find the bug int the slow alg. and fix it. The slow algorithm is used inside other preprocessing algorithms, so we cannot discard it right now, can we?

We could probably replace the slow algorithm with the fast one in many places, but I'm not sure if all, since a very similar (basically identical) Dijkstra algorithm is also implemented separately elsewhere for other purposes.

[F-I-D-O]

Ok, so if it worked correctly before, please just fix it :)

[neumannjan]

FINALLY fixed in dfb43d3. This took me really long to figure out.

The issue was with the CSV reader. It was the following:

• nan values in CSV files were checked for being exactly nan using a custom implementation of istrcmp
• the CSV reader preserved \n with each nan that was last on every line
• this resulted in istrcmp("nan\n", "nan") returning false, which in turn returned 0 for the edge weight
• edge weight == 0 was interpreted as "this is an edge with weight equal to 0", instead of "this is not an edge"
• this only affected the slow algorithm because it uses the Graph class, for which the "free" edge was always explicitly added.

My solution:

• std::stof actually returns a valid number (NaN). For this value, isnan() returns true. Therefore:
• std::stof is used directly (and wrapped with appropriate exception handling in case of unexpected values -> UINF is returned in such cases (representing "no edge") )
• the result of stof is checked using isnan. If true, UINF is returned.
• The result is rounded and returned as unsigned int.

[F-I-D-O]

Nice, interpreting text input is always tricky. I think that interpreting unexpected values as no edge is better than as zero weight edges. But it should be reported as a warning in log at least.

[neumannjan]

I think that interpreting unexpected values as no edge is better than as zero weight edges. But it should be reported as a warning in log at least.

I agree. If you look at my new solution though, it is done so.

• nan is checked by isnan (which returns true) and converted to UINF_MAX, which represents "no edge"
• unexpected value throws an exception, which is resolved by returning UINF_MAX (no edge)
• I will add a check for negative values as well, which will throw a warning and return UINF_MAX.

[F-I-D-O]

I agree. If you look at my new solution though, it is done so.

No, it's not. The exception handling is correct. But there is no reporting. The incorrect input file format should be reported to the standard output.

[neumannjan]

Fixed in a7d57df.

[F-I-D-O]

solved