incubator-giraph-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Sebastian Schelter" <...@apache.org>
Subject Review Request: Port of the HCC algorithm for identifying all connected components of a graph
Date Sat, 24 Dec 2011 09:32:15 GMT

-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/3313/
-----------------------------------------------------------

Review request for giraph.


Summary
-------

Port of the HCC algorithm to Giraph. Each vertex needs to find the smallest vertex id in its
component.

I created a very memory-efficient abstract vertex in org.apache.giraph.graph.IntIntNullIntVertex
and had org.apache.giraph.examples.ConnectedComponentsVertex extend that. org.apache.giraph.examples.ConnectedComponentsVertexTest
contains an "integration" test on toy data.

I had to patch org.apache.giraph.utils.InternalVertexRunner to allow the use of combiners
and to shutdown() the local zookeeper instance in the tests.

Local and pseudo-distributed unit tests were passed. I also tested the algorithm on a 6-machine
hadoop cluster using the wikipedia pagelink graph (5.7M vertices, 130M edges).


This addresses bug GIRAPH-115.
    https://issues.apache.org/jira/browse/GIRAPH-115


Diffs
-----

  /trunk/src/main/java/org/apache/giraph/examples/ConnectedComponentsVertex.java PRE-CREATION

  /trunk/src/main/java/org/apache/giraph/examples/IntIntNullIntTextInputFormat.java PRE-CREATION

  /trunk/src/main/java/org/apache/giraph/examples/MinimumIntCombiner.java PRE-CREATION 
  /trunk/src/main/java/org/apache/giraph/examples/VertexWithComponentTextOutputFormat.java
PRE-CREATION 
  /trunk/src/main/java/org/apache/giraph/graph/IntIntNullIntVertex.java PRE-CREATION 
  /trunk/src/main/java/org/apache/giraph/utils/InternalVertexRunner.java 1222837 
  /trunk/src/main/java/org/apache/giraph/utils/UnmodifiableIntArrayIterator.java PRE-CREATION

  /trunk/src/test/java/org/apache/giraph/examples/ConnectedComponentsVertexTest.java PRE-CREATION

  /trunk/src/test/java/org/apache/giraph/examples/MinimumIntCombinerTest.java PRE-CREATION


Diff: https://reviews.apache.org/r/3313/diff


Testing
-------


Thanks,

Sebastian


Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message