giraph-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Lukas Nalezenec <lukas.naleze...@firma.seznam.cz>
Subject Re: Breadth First Search (BFS)
Date Mon, 07 Apr 2014 10:00:36 GMT
Hi,
I dont know what problem do you exactly solve and I have never written 
distributed BFS
but I think that sharing queue using agreggator wont scale for larger 
graphs.
The algorithm in video is basic its not distributed version.

Lukas

On 3.4.2014 15:13, ghufran malik wrote:
> 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:
>
> 52.0
> 01.0
> 21.0
> 10.0
> 31.0
> 42.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 <mailto: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
>     <mailto: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