giraph-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From yeshwanth kumar <yeshwant...@gmail.com>
Subject Re: understanding tiny_graph.txt
Date Thu, 17 Apr 2014 16:32:42 GMT
that's a detailed explanation.
thanks nishant.




On Thu, Apr 17, 2014 at 7:50 PM, nishant gandhi
<nishantgandhi99@gmail.com>wrote:

> 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