giraph-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Claudio Martella <claudio.marte...@gmail.com>
Subject Re: Completing betweeness on giraph
Date Wed, 12 Feb 2014 15:54:01 GMT
i don't think the point is whether following your approach, which is a
concatenation of SSSP, this is possible, but whether given the the sizes of
graphs your approach is actually feasible.

About your questions, you have to implement a type for your Vertex Value
and one for the Message, and make sure they implement Writable correctly,
to ensure serializability.

P.S.= you should post (and subscribe) to user@giraph.apache.org, AFAIK
user-help@ does not exist.


On Wed, Feb 12, 2014 at 3:34 PM, Apostolos Koutras <
koutras.apostolos@gmail.com> wrote:

>
>
>
>
>
> Hi fellow developer Semih Salihoglu,
>
> In the past day, I am struggling on completing calculating Betweeness for
> a graph.
> Browsing in some forums, some stated that this cannot be done.
>
> This point of view is simply put WRONG!.
>
> I have uploaded my work in https://github.com/koutras/gb
> where everyone with an interest can browse and provide insight, as I have
> been developing
> for about 12 straight hours and I have not the right experience yet.
>
> The main algorithm is based on SimpleShortestPathsComputation  for the
> main algorithm (brande's algorithm) but I needed to store extra values in
> each node, and as an effect override
> the message also.
>
> The trick I've thought about for the algorithm to work is provide the
> input of nodes in ascending
> value, starting from 1 to number of nodes, and as such, to complete a bfs
> each time I have to
> wait for number of nodes supersteps each time. This can easily be done by
>  mod(superstep,nodes_num).
>
> After the end of that phase I do some calculations in each node, and I
> clear the distance value,
> in order to continue running the SimpleShortestPaths algorithm but with
> the next vertex
> as a source in ascending order.
>
>  I was also based
> on BrachaTouegDeadlockComputation for overriding message and vertex value,
>
>
> (message is based on BrachaTouegDeadlockMessage and vertex value on
>  BrachaTouegDeadlockVertexValue located in utils
> on respect.)
>
> The things I had found difficulty so far is not the algorithm by itself
> that is the brande's algorithm,
> but integrating the following things.
>
>  1) overriding the value of vertex with mine using myVertex.java
>        Overriding the Serialization functions for my implementation
> according to
>        BrachaTouegDeadlockVertexValue.
>
>
>
> 2) overriding the message that a node is passing to another with
> myMessage.java
>      I've added the accessors that I wanted but I dont now what to do with
> readFields, and write,
>      that the BrachaTouegDeadlockMessage has, for my implementation
>
>
> Any help on the above matters is very appreciated. Thank you all, and
> sorry for the long post
> So this CAN be done! If this algorithm is effective is another topic of
> conversation.
> Thanks for your time, and once again sorry for the long post
>
>


-- 
   Claudio Martella

Mime
View raw message