unipg.gila.partitioning

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<org.apache.hadoop.io.LongWritable,PartitioningVertexValue,EdgeValue,org.apache.hadoop.io.LongWritable,org.apache.hadoop.io.LongWritable>

unipg.gila.partitioning.ConnectedComponentsComputation

All Implemented Interfaces:

org.apache.giraph.aggregators.AggregatorUsage, org.apache.giraph.conf.GiraphConfigurationSettable<org.apache.hadoop.io.LongWritable,PartitioningVertexValue,EdgeValue>, org.apache.giraph.conf.ImmutableClassesGiraphConfigurable<org.apache.hadoop.io.LongWritable,PartitioningVertexValue,EdgeValue>, org.apache.giraph.conf.TypesHolder<org.apache.hadoop.io.LongWritable,PartitioningVertexValue,EdgeValue,org.apache.hadoop.io.LongWritable,org.apache.hadoop.io.LongWritable>, org.apache.giraph.graph.Computation<org.apache.hadoop.io.LongWritable,PartitioningVertexValue,EdgeValue,org.apache.hadoop.io.LongWritable,org.apache.hadoop.io.LongWritable>, org.apache.giraph.worker.WorkerAggregatorUsage, org.apache.giraph.worker.WorkerBroadcastUsage, org.apache.giraph.worker.WorkerGlobalCommUsage, org.apache.giraph.worker.WorkerReduceUsage

public class ConnectedComponentsComputation
extends org.apache.giraph.graph.AbstractComputation<org.apache.hadoop.io.LongWritable,PartitioningVertexValue,EdgeValue,org.apache.hadoop.io.LongWritable,org.apache.hadoop.io.LongWritable>

This class contains the code for the connected components discovery. It has been slightly modified to adapt to Dafne's framework but it has been left untouched for the most part. What follows is the description taken from the original class. ################################################################## 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 ####################################################################

Author:

Alessio Arleo

Field Summary

Fields

Modifier and Type	Field and Description
static java.lang.String	activityAggr

Constructor Summary

Constructors

Constructor and Description
ConnectedComponentsComputation()

Method Summary

Methods

Modifier and Type	Method and Description
void	compute(org.apache.giraph.graph.Vertex<org.apache.hadoop.io.LongWritable,PartitioningVertexValue,EdgeValue> vertex, java.lang.Iterable<org.apache.hadoop.io.LongWritable> messages) Propagates the smallest vertex id to all neighbors.

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

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

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

aggregate, getAggregatedValue, getBroadcast, reduce, 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

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

aggregate

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

getAggregatedValue

Field Detail

activityAggr

public static final java.lang.String activityAggr

See Also:

Constant Field Values

Constructor Detail

ConnectedComponentsComputation

public ConnectedComponentsComputation()

Method Detail

compute

public void compute(org.apache.giraph.graph.Vertex<org.apache.hadoop.io.LongWritable,PartitioningVertexValue,EdgeValue> vertex,
           java.lang.Iterable<org.apache.hadoop.io.LongWritable> messages)
             throws java.io.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 org.apache.giraph.graph.Computation<org.apache.hadoop.io.LongWritable,PartitioningVertexValue,EdgeValue,org.apache.hadoop.io.LongWritable,org.apache.hadoop.io.LongWritable>

Specified by:

compute in class org.apache.giraph.graph.AbstractComputation<org.apache.hadoop.io.LongWritable,PartitioningVertexValue,EdgeValue,org.apache.hadoop.io.LongWritable,org.apache.hadoop.io.LongWritable>

Parameters:

vertex - Vertex

messages - Iterator of messages from the previous superstep.

Throws:

java.io.IOException