SSSP results correctness

[yzhwang]

Hi @farkhor ,

We're running some experiments for SSSP in CuSha. And the results is different from BGL's CPU results. Did you have any verification code in CuSha to verify the correctness of your SSSP? Here are some details:

1. We are compiling CuSha using CUDA 8.0.
2. We are using 0-based vertex node ID, providing an edge list with no header line. We are using --undirected to specify an undirected graph. Our graph has random weights [1,64) in int.
3. our command line is like this:
   ./cusha-sssp --input edgelist_file --method CW --undirected

We are suspicious about the results because we verified that the weights have been successfully read in, but the iteration number is similar to a BFS on the same dataset, which usually isn't the case. Because for SSSP with various edge weights, it usually has more iterations as BFS. Also the results distances have a lot of repeating values in small ints, they look like wrong results. We just want to provide this info to you and see if we have done something wrong during our comparison.

Look forward to your reply! Thank you so much!

[farkhor]

Hi @yzhwang,

Thank you for your interest. There are a few points which might explain the results you’re observing:

• The reason why the number of iterations in SSSP and BFS come out similar or close-to-each-other in CuSha is probably due to the fact that all the vertices and their edges are being visited at every iteration. Basically, a portion of the redundant work in BFS becomes useful in SSSP.
• I should have made it clear that the undirected flag in CuSha does nothing but creating two edges per every line of the input edge-list. For every line “m n w” (3rd argument is arbitrary), it creates two edges, one from m to n with weight w and the other from n to m again with weight w. Now if an edge appears twice in the input edge-list (which can be the case in some undirected ones), the graph ends up with two edges from every source to every destination that may have different weights. Therefore, in this scenario, if the user wants to express an edge from m to n with weight w1 and from n to m with weight w2 and w1<w2, during the SSSP the w2 weight from n to m is masked by undesired w1 resulted from edge mirroring. This basically changes the computation outcome; so the correct way would have been excluding the undirected flag.
• If a vertex index is less than the maximum vertex index appearing in the input edge-list but has never appeared as a source or a destination index in it (basically an isolated vertex), it will never be initialized and its final value is random in the output file. This can cause a discrepancy that should be ignored.

I hope above explanations help. If the problems you are seeing persist, please let me know your input graph and a deterministic way to initialize the weights (or maybe uploading the weighted graph somewhere) so I can recreate the results.

Best,
Farzad