Port of the HCC algorithm for identifying all connected components of a graph

                 Key: GIRAPH-115
                 URL: https://issues.apache.org/jira/browse/GIRAPH-115
             Project: Giraph
          Issue Type: New Feature
    Affects Versions: 0.70.0
            Reporter: Sebastian Schelter

Port of the HCC algorithm that identifies connected components and assigns a 
componented id (the smallest vertex id in the component) to each vertex.

The idea behind the algorithm is very simple: propagate the smallest vertex id 
along the edges to all vertices of a connected component until convergence. The 
number of supersteps necessary is equal to the length of the maximum diameter 
of all components + 1

The original Hadoop-based variant of this algorithm was proposed by Kang, 
Charalampos, Tsourakakis and Faloutsos in "PEGASUS: Mining Peta-Scale Graphs", 


This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: 
For more information on JIRA, see: http://www.atlassian.com/software/jira


Reply via email to