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
<[email protected] <mailto:[email protected]>> 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
<[email protected]
<mailto:[email protected]>> 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
