giraph-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Claudio Martella <>
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, AFAIK
user-help@ does not exist.

On Wed, Feb 12, 2014 at 3:34 PM, Apostolos Koutras <> 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
> 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
>        Overriding the Serialization functions for my implementation
> according to
>        BrachaTouegDeadlockVertexValue.
> 2) overriding the message that a node is passing to another with
>      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

View raw message