Also as to my original question I understand that I need to register an agg to a master class to store a persistent list.
On Thu, Apr 3, 2014 at 2:13 PM, ghufran malik <ghufran1ma...@gmail.com>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 <nishantgandh...@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.naleze...@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 >>> >>> >>> >> >
