Re: Giraph examples: SimpleShortestPathsComputation

[Maria Stylianou <ma...@gmail.com>]

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 <bo...@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

Re: Giraph examples: SimpleShortestPathsComputation

[Yazan Boshmaf <bo...@ece.ubc.ca>]

You might want to consider this in your GIRAPH-644 patch :)

On Sat, Jun 1, 2013 at 8:38 PM, Yazan Boshmaf <bo...@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 <ma...@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 <bo...@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

Re: Giraph examples: SimpleShortestPathsComputation

[Yazan Boshmaf <bo...@ece.ubc.ca>]

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 <ma...@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 <bo...@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