# giraph-user mailing list archives

##### Site index · List index
Message view
Top
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:
>
>
> 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?
>
>
> 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..
>
>
>     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