Question about example-sssp-pull-simple: is it assuming directed graph?

[Steamgjk]

I have a confusion point related to the example-sssp-pull-simple program. I feel it cannot work correctly with directed graph.

I can understand the logic of example-sssp-simple and example-sssp-push-simple, and they both work with directed graph. However, when it comes to the pull-style, I feel it assumes using undirected graph, because it is using neighbors' data and edge weight to update the current node's data value. https://github.com/IntelligentSoftwareSystems/Galois/blob/59d5aa54b4a7b6594660bb1b18b83ae6875b954c/lonestar/tutorial_examples/SSSPPullSimple.cpp#L81-L85

However, IIUC, LC_Linear_Graph getEdgeData returns the edges starting from the active_node (i.e. the edge points to the dst node), so we cannot use dst.data + edge_weigth to update the active_node, if the graph is directed. (Of course, the update still makes sense if we consider the graph is undirected)

I hope some staff can explain a bit.

[bozhiyou]

Thanks for your interest in Galois.

As they are tutorial examples, we assume undirected graphs as inputs for both push- and pull-style implementations to keep things simple, though they work with directed graphs as well (undirected graphs are implemented as directed graphs with symmetric edges).

When it comes to directed/asymmetric graphs, the pull-style implementation requires the input graph to have a transposed (i.e., reversing the direction of all edges) or symmetric/undirected version of the original graph - which is not required if the graph implementation provides APIs to access in-edges (unfortunately LC_Linear_Graph does not provide this; MorphGraph does). To make things simple, we don't want this complexity since the goal is to show push vs. pull rather than undirected vs. directed. That being said, we should have made it clear in our tutorial that just think about undirected graphs. Sorry for the confusion.

[bozhiyou]

FYI, if you look at the SSSP implementations in the Lonestar benchmark (not the simple tutorial ones), you'll find that we explicitly require a graphTranspose as a command line argument.

[Steamgjk]

Thanks @bozhiyou BTW: What is the use of numRuns? I understand the concept of "rounds" from the Gluon paper, but it does not mention "numRuns", I feel it is just for a better performance measurement( i.e. "multiple runs and measure the average") and has no relation to the algorithms. Am I right?

[nicelhc13]

Yes you are right.

[Steamgjk]

Thanks