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 Sun, 13 Apr 2014 17:30:31 GMT
Hi,

I have managed to implement it correctly after re-thinking my approach. The
video described it in an asynchronous algorithm which, as you pointed out
is not a distributed. I followed the BFS algorithm written in this paper:
http://www.cc.gatech.edu/~bader/papers/GraphBSPonXMT-MTAAP2013.pdf. and
managed to get it working.

Thanks for the help,

Ghufran


On Mon, Apr 7, 2014 at 11:00 AM, Lukas Nalezenec <
lukas.nalezenec@firma.seznam.cz> wrote:

>  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:
>
> 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