There are three data attached with the graph
1) Vertex Id: Every vertex has ID. It can be anything. number or string or
object
2) Vertex Value: Every vertex can be assign some value to attached with it.
this value can be number or string or object
3) Edge Value: Every edge can be assign some value with it.
now for SSSP,
Initially , we set one parameter for setting source vertex for SSSP with
following code.
Here we are setting it to 1.
public static final LongConfOption SOURCE_ID =
new LongConfOption("SimpleShortestPathsVertex.sourceId", 1);
In superstep=0
----------------------
initially all vertex are in active state.
the source vertex's vertex value is set to 0 and rest all other vertex are
set to maximum possible value(Theoretically Infinite).
source vertex(in our case, it is1) create edge iterator and sends the
messages to all neighbor with (it's own vertex value+ respected edge value).
voteToHalt by all vertex.
in superstep>0
---------------------
all vertex that receive message from previous super steps become active
they check all message and see if they receive any vertexValue less than
their own current vertexValue. If yes than they set their current vertex
value to received vertexValue by message
create edge iterator and sends the messages to all neighbor with (it's own
vertex value+ respected edge value).
voteToHalt by all vertex.
when no vertex pass the message as every one has shortest path cost set in
their VertexValue. so finally no vertex become active in next superstep and
algorithm halt.
Hope that helps.
Nishant Gandhi
M.Tech. CSE
IIT Patna
On Thu, Apr 17, 2014 at 3:50 PM, yeshwanth kumar <yeshwant...@gmail.com>wrote:
> thanks nishant,
>
> everything is clear except that vertex value.
> i am trying to understand the execution flow of shortestpath example
> where it starts and where it ends.
> can you help me with it.
>
>
>
>
> On Thu, Apr 17, 2014 at 3:25 PM, nishant gandhi <nishantgandh...@gmail.com
> > wrote:
>
>> format of this input is
>> [VertexId,VertexValue,[OppositeVertexOfEdge,Edge Value]]
>>
>> so,
>> for
>>
>> [1,0,[[0,1],[2,2],[3,1]]]
>>
>> VertexId=1
>> VertexValue=0
>>
>> there are three edges for VertexId=1
>> with [0,1] means, Edge has opposite vertexId 0, so Edge is (1,0) and
>> second part is Edge Value 1.
>> with [2,2] means, Edge has opposite vertexId 2, so Edge is (1,2) and
>> second part is Edge Value 2.
>> with [3,1] means, Edge has opposite vertexId 3, so Edge is (1,3) and
>> second part is Edge Value 1.
>> Hope that Helps.
>>
>> Nishant Gandhi
>> M.Tech. CSE
>> IIT Patna
>>
>>
>> On Thu, Apr 17, 2014 at 3:10 PM, yeshwanth kumar
>> <yeshwant...@gmail.com>wrote:
>>
>>> hi i just started working on giraph,
>>>
>>> started with shortestpath example.
>>> in tiny_graph.txt graph is represented as
>>>
>>> [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],[4,4]]]
>>> [4,0,[[3,4],[2,4]]]
>>>
>>> from this
>>> image<http://blog.cloudera.com/wp-content/uploads/2014/01/giraph3.png>
>>> somehow
>>> i understood the representation.
>>> but its not clear totally.
>>>
>>> from [0,*0*,[[1,1],[3,3]]]
>>>
>>> it mean it got edges between (0,1) and weight of edge is 1 and (0,3) and
>>> weight of edge is 3. what does second 0 stands for.
>>> does it mean there's no cycle between (0,0)
>>> can someone explain how graph is represented.
>>>
>>> thank you.
>>>
>>>
>>
>
