giraph-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ghufran malik <ghufran1ma...@gmail.com>
Subject Re: Breadth First Search (BFS)
Date Thu, 03 Apr 2014 13:13:52 GMT
Hi,

Lukas, I believe the queue list is essential to the BFS algorithm I am
trying? I am following this explanation given here:

https://www.youtube.com/watch?v=zLZhSSXAwxI

So for my output I want to have the vertex id followed by the number
representing the order in which it was visited so vertex 5 was the start so
it has a value of 0, it has neighbours 4, 8 and 2, the order in which they
would be visited should be 2-4-8 so I want their values to be 1,2,3
respectively.

Nishant, Yes I've seen those implementations before they were done by a
student at my university some time ago, however for the BFSSO, at least, it
give the depth of each vertex and not result as presented in the above
video. Looking back at this algorithm though has brought into question how
I originally understood how the BSP model works in Giraph. I am confused on
how it works based on 1 fact, I thought every vertex was initially active
and run the compute method, so why isit that after superstep 0 in this
algorithm, every other vertex is not set to 1?

I could be flawed in my understanding but It seems to me that this
algorithm for superstep 0 sets the depth (value) for the start vertex to 0,
that's fine, after that it sends a message to all vertices that are its
neighbours to activate them (according to the code comments)? I thought all
vertices where initially active until they vote to halt?

Pregel Paper:
"In superstep 0, every vertex is in the active state; all
active vertices participate in the computation of any given
superstep. A vertex deactivates itself by voting to halt."

He then sets every other vertex value that's not the start vertex to a max
integer. The supersteps after checks if the vertex value is of a max value
and if it is set the value to that superstep number. So superstep 1 all the
remaining vertices should be set to 1? - this assumption of mine I believe
is wrong but I need help in understanding why.

this was my original understanding until I ran the code on the following
graph:

[0,0,[[1,1],[3,3]]]
[1,0,[[0,1],[2,2],[3,1]]]
[2,0,[[1,2],[4,4]]]
[3,0,[[0,3],[1,1],[5,0]]]
[4,0,[[2,4]]]
[5,0,[[3,0]]]

and got the output:

5 2.0
0 1.0
2 1.0
1 0.0
3 1.0
4 2.0

Note that the start vertex id was 1. So 1 is 0 thats done if the first
superstep. then messages are sent to its neighbours and it seems to me that
only these are active in superstep 1 so they are given a value 1 and
messages are sent to their neighbours (4 and 5). Why are 4 and 5 not active
in superstep 1 as well and given a value 1? Only in superstep 2 once these
vertices have received messages are they taken in to consideration and give
a value 2.

So in conclusion why aren't all the vertices given a value 1 in superstep 1
as I thought all vertices should be active? Unless all vertices are ONLY
active in superstep 0 after which ones that do not receive a message vote
to a halt?

Sorry for long read,

Thanks,

Ghufran



On Thu, Apr 3, 2014 at 11:50 AM, nishant gandhi
<nishantgandhi99@gmail.com>wrote:

> Check this out for BFS..
>
>
> http://stackoverflow.com/questions/12253794/breadth-first-implentation-in-giraph-graphchi-or-pregel
>
> Nishant Gandhi
> M.Tech CSE
> IIT Patna
>
>
> On Thu, Apr 3, 2014 at 3:18 PM, Lukas Nalezenec <
> lukas.nalezenec@firma.seznam.cz> wrote:
>
>>  Hi,
>> It looks like you are using wrong algorithm. If you are doing simple BFS
>> you should not need to remember vertex ids.
>>
>> Lukas
>>
>> Lukas
>>
>>
>> On 2.4.2014 20:30, ghufran malik wrote:
>>
>> Hi
>>
>>  I am trying to implement the BFS algorithm using Giraph 1.1.0.
>>
>>  I have partly implemented it and am stuck on just one part. I have a
>> list of vertex ids and I want these ids to be seen in the next superstep.
>> Is it possible for me to just have the list in my BasicComputations class
>> or do I need to send it to an aggregator or master class of some sort to
>> store this list so that in the next superstep I can use this list of vertex
>> ids in my basiccomputations class?
>>
>> kind regards,
>>
>>  Ghufran
>>
>>
>>
>

Mime
View raw message