You might want to consider this in your GIRAPH-644 patch :)
On Sat, Jun 1, 2013 at 8:38 PM, Yazan Boshmaf <[email protected]> wrote: > Maria, it depends whether the SSSP computation is expected to find the > shortest path between the source to itself. Consider a graph of two > nodes {v1,v2} and two edges {(v1,v2),(v2,v1)}. Let v1 be the source > node. The SSSP for v1 are as follows: > > v1 -> (v1,v2,v1), with length 2 > v2 -> (v1,v2), with length 1 > > This might be useful as the length of the path from the source to > itself is the height of the resulting tree rooted at the source (a > spanning tree in undirected graphs, and potentially an arborescence is > directed graphs). > > As far as I know, traditional SSSP algorithms find the shortest path > from a source node to all *other* nodes. It is not expected to output > the shortest path from/to itself. The example, however, does output a > record for the source node, and in this case, it would be better to > actually compute the value to be consistent with the expected output. > > Hope this clarifies it. > > Cheers, > Yazan > > On Sat, Jun 1, 2013 at 2:35 PM, Maria Stylianou <[email protected]> wrote: >> I'm not sure if I follow you. I totally understand zero value for the >> source vertex, since the distance/hops to itself is zero. >> >> >> >> On Fri, May 31, 2013 at 12:25 AM, Yazan Boshmaf <[email protected]> wrote: >> >>> Hi all, >>> >>> For the SimpleShortestPathsComputation example in "giraph-examples" >>> module, I noticed that the distance to the source node is set to 0 by >>> convention. In most applications, however, one actually needs to find >>> the distance from a node to itself. A distance of 1 means a self-loop >>> and a greater value means a cycle consisting of more then one unique >>> node. In my opinion, a distance of 0 does not have a clear meaning: a >>> nodes is either reachable with 1 <= distance < Double.MAX or >>> unreachable with distance = Double.MAX, all from a given source node. >>> >>> Suggestions: >>> >>> As the values of all nodes are set to Double.MAX in seuperstep 0, I >>> would initialize minDist to vertex.getValue().get() in >>> SimpleShortestPathsComputation.java:65 >>> >>> What do you think? >>> >>> All the best, >>> Yazan >>> >>> P.S. Please let me know if such questions should go to the user list. >>> >> >> >> >> -- >> Maria Stylianou >> Intern at Telefonica, Barcelona, Spain >> Master Student of European Master in Distributed >> Computing<http://www.kth.se/en/studies/programmes/master/em/emdc> >> marsty5.wordpress.com
