org.apache.giraph.examples

Class ConnectedComponentsComputation

java.lang.Object

org.apache.giraph.conf.DefaultImmutableClassesGiraphConfigurable<I,V,E>

org.apache.giraph.worker.WorkerAggregatorDelegator<I,V,E>

org.apache.giraph.graph.AbstractComputation<I,V,E,M,M>

org.apache.giraph.graph.BasicComputation<org.apache.hadoop.io.IntWritable,org.apache.hadoop.io.IntWritable,org.apache.hadoop.io.NullWritable,org.apache.hadoop.io.IntWritable>

org.apache.giraph.examples.ConnectedComponentsComputation

All Implemented Interfaces:

AggregatorUsage, GiraphConfigurationSettable<org.apache.hadoop.io.IntWritable,org.apache.hadoop.io.IntWritable,org.apache.hadoop.io.NullWritable>, ImmutableClassesGiraphConfigurable<org.apache.hadoop.io.IntWritable,org.apache.hadoop.io.IntWritable,org.apache.hadoop.io.NullWritable>, TypesHolder<org.apache.hadoop.io.IntWritable,org.apache.hadoop.io.IntWritable,org.apache.hadoop.io.NullWritable,org.apache.hadoop.io.IntWritable,org.apache.hadoop.io.IntWritable>, Computation<org.apache.hadoop.io.IntWritable,org.apache.hadoop.io.IntWritable,org.apache.hadoop.io.NullWritable,org.apache.hadoop.io.IntWritable,org.apache.hadoop.io.IntWritable>, WorkerAggregatorUsage, WorkerBroadcastUsage, WorkerGlobalCommUsage, WorkerIndexUsage<org.apache.hadoop.io.IntWritable>, WorkerReduceUsage

public class ConnectedComponentsComputation
extends BasicComputation<org.apache.hadoop.io.IntWritable,org.apache.hadoop.io.IntWritable,org.apache.hadoop.io.NullWritable,org.apache.hadoop.io.IntWritable>

Implementation of the HCC algorithm that identifies connected components and assigns each vertex its "component identifier" (the smallest vertex id in the component) The idea behind the algorithm is very simple: propagate the smallest vertex id along the edges to all vertices of a connected component. 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", 2010 http://www.cs.cmu.edu/~ukang/papers/PegasusKAIS.pdf

Constructor Summary

Constructors

Constructor and Description
ConnectedComponentsComputation()

Method Summary

Modifier and Type	Method and Description
void	compute(Vertex<org.apache.hadoop.io.IntWritable,org.apache.hadoop.io.IntWritable,org.apache.hadoop.io.NullWritable> vertex, Iterable<org.apache.hadoop.io.IntWritable> messages) Propagates the smallest vertex id to all neighbors.

Methods inherited from class org.apache.giraph.graph.AbstractComputation

addEdgeRequest, addVertexRequest, addVertexRequest, getContext, getMyWorkerIndex, getSuperstep, getTotalNumEdges, getTotalNumVertices, getWorkerContext, getWorkerCount, getWorkerForVertex, initialize, postSuperstep, preSuperstep, removeEdgesRequest, removeVertexRequest, sendMessage, sendMessageToAllEdges, sendMessageToMultipleEdges

Methods inherited from class org.apache.giraph.worker.WorkerAggregatorDelegator

aggregate, getAggregatedValue, getBroadcast, reduce, reduceMerge, setWorkerGlobalCommUsage

Methods inherited from class org.apache.giraph.conf.DefaultImmutableClassesGiraphConfigurable

getConf, setConf

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface org.apache.giraph.conf.ImmutableClassesGiraphConfigurable

getConf

Methods inherited from interface org.apache.giraph.conf.GiraphConfigurationSettable

setConf

Methods inherited from interface org.apache.giraph.worker.WorkerBroadcastUsage

getBroadcast

Methods inherited from interface org.apache.giraph.worker.WorkerReduceUsage

reduce, reduceMerge

Methods inherited from interface org.apache.giraph.worker.WorkerAggregatorUsage

aggregate

Methods inherited from interface org.apache.giraph.aggregators.AggregatorUsage

getAggregatedValue

Constructor Detail

ConnectedComponentsComputation

public ConnectedComponentsComputation()

Method Detail

compute

public void compute(Vertex<org.apache.hadoop.io.IntWritable,org.apache.hadoop.io.IntWritable,org.apache.hadoop.io.NullWritable> vertex,
                    Iterable<org.apache.hadoop.io.IntWritable> messages)
             throws IOException

Propagates the smallest vertex id to all neighbors. Will always choose to halt and only reactivate if a smaller id has been sent to it.

Specified by:

compute in interface Computation<org.apache.hadoop.io.IntWritable,org.apache.hadoop.io.IntWritable,org.apache.hadoop.io.NullWritable,org.apache.hadoop.io.IntWritable,org.apache.hadoop.io.IntWritable>

Specified by:

compute in class AbstractComputation<org.apache.hadoop.io.IntWritable,org.apache.hadoop.io.IntWritable,org.apache.hadoop.io.NullWritable,org.apache.hadoop.io.IntWritable,org.apache.hadoop.io.IntWritable>

Parameters:

vertex - Vertex

messages - Iterator of messages from the previous superstep.

Throws:

IOException