giraph-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From nishant gandhi <nishantgandh...@gmail.com>
Subject Re: understanding tiny_graph.txt
Date Thu, 17 Apr 2014 14:20:23 GMT
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 <yeshwanth43@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 <nishantgandhi99@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 <yeshwanth43@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.
>>>
>>>
>>
>

Mime
View raw message