giraph-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Apostolos Koutras <koutras.aposto...@gmail.com>
Subject Wanting help on completing calculating Betweeness using giraph
Date Wed, 12 Feb 2014 14:04:50 GMT
Hi fellow developers,

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

Mime
View raw message