giraph-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Yazan Boshmaf <bosh...@ece.ubc.ca>
Subject Re: Giraph examples: SimpleShortestPathsComputation
Date Sun, 02 Jun 2013 03:39:38 GMT
You might want to consider this in your GIRAPH-644 patch :)

On Sat, Jun 1, 2013 at 8:38 PM, Yazan Boshmaf <boshmaf@ece.ubc.ca> 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 <marsty5@gmail.com> 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 <boshmaf@ece.ubc.ca> 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

Mime
View raw message