org.apache.flink.graph.pregel

Class VertexCentricIteration<K,VV,EV,Message>

java.lang.Object

org.apache.flink.graph.pregel.VertexCentricIteration<K,VV,EV,Message>

Type Parameters:

K - The type of the vertex key (the vertex identifier).

VV - The type of the vertex value (the state of the vertex).

Message - The type of the message sent between vertices along the edges.

EV - The type of the values that are associated with the edges.

All Implemented Interfaces:

CustomUnaryOperation<Vertex<K,VV>,Vertex<K,VV>>

public class VertexCentricIteration<K,VV,EV,Message>
extends Object
implements CustomUnaryOperation<Vertex<K,VV>,Vertex<K,VV>>

This class represents iterative graph computations, programmed in a vertex-centric perspective. It is a special case of Bulk Synchronous Parallel computation. The paradigm has also been implemented by Google's Pregel system and by Apache Giraph.

Vertex centric algorithms operate on graphs, which are defined through vertices and edges. The algorithms send messages along the edges and update the state of vertices based on the old state and the incoming messages. All vertices have an initial state. The computation terminates once no vertex receives any message anymore. Additionally, a maximum number of iterations (supersteps) may be specified.

The computation is here represented by one function:

• The ComputeFunction receives incoming messages, may update the state for the vertex, and sends messages along the edges of the vertex.

Vertex-centric graph iterations are run by calling Graph.runVertexCentricIteration(ComputeFunction, MessageCombiner, int).

Method Summary

Modifier and Type	Method and Description
void	configure(VertexCentricConfiguration parameters) Configures this vertex-centric iteration with the provided parameters.
DataSet<Vertex<K,VV>>	createResult() Creates the operator that represents this vertex-centric graph computation.
VertexCentricConfiguration	getIterationConfiguration()
void	setInput(DataSet<Vertex<K,VV>> inputData) Sets the input data set for this operator.
static <K,VV,EV,Message> VertexCentricIteration<K,VV,EV,Message>	withEdges(DataSet<Edge<K,EV>> edgesWithValue, ComputeFunction<K,VV,EV,Message> cf, int maximumNumberOfIterations) Creates a new vertex-centric iteration operator.
static <K,VV,EV,Message> VertexCentricIteration<K,VV,EV,Message>	withEdges(DataSet<Edge<K,EV>> edgesWithValue, ComputeFunction<K,VV,EV,Message> cf, MessageCombiner<K,Message> mc, int maximumNumberOfIterations) Creates a new vertex-centric iteration operator for graphs where the edges are associated with a value (such as a weight or distance).

Methods inherited from class java.lang.Object

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

Method Detail

setInput

public void setInput(DataSet<Vertex<K,VV>> inputData)

Sets the input data set for this operator. In the case of this operator this input data set represents the set of vertices with their initial state.

Specified by:

setInput in interface CustomUnaryOperation<Vertex<K,VV>,Vertex<K,VV>>

Parameters:

inputData - The input data set, which in the case of this operator represents the set of vertices with their initial state.

See Also:

CustomUnaryOperation.setInput(org.apache.flink.api.java.DataSet)

createResult

public DataSet<Vertex<K,VV>> createResult()

Creates the operator that represents this vertex-centric graph computation.

The Pregel iteration is mapped to delta iteration as follows. The solution set consists of the set of active vertices and the workset contains the set of messages send to vertices during the previous superstep. Initially, the workset contains a null message for each vertex. In the beginning of a superstep, the solution set is joined with the workset to produce a dataset containing tuples of vertex state and messages (vertex inbox). The superstep compute UDF is realized with a coGroup between the vertices with inbox and the graph edges. The output of the compute UDF contains both the new vertex values and the new messages produced. These are directed to the solution set delta and new workset, respectively, with subsequent flatMaps.

Specified by:

createResult in interface CustomUnaryOperation<Vertex<K,VV>,Vertex<K,VV>>

Returns:

The operator that represents this vertex-centric graph computation.

withEdges

public static <K,VV,EV,Message> VertexCentricIteration<K,VV,EV,Message> withEdges(DataSet<Edge<K,EV>> edgesWithValue,
                                                                                  ComputeFunction<K,VV,EV,Message> cf,
                                                                                  int maximumNumberOfIterations)

Creates a new vertex-centric iteration operator.

Type Parameters:

K - The type of the vertex key (the vertex identifier).

VV - The type of the vertex value (the state of the vertex).

Message - The type of the message sent between vertices along the edges.

EV - The type of the values that are associated with the edges.

Parameters:

edgesWithValue - The data set containing edges.

cf - The compute function

Returns:

An instance of the vertex-centric graph computation operator.

withEdges

public static <K,VV,EV,Message> VertexCentricIteration<K,VV,EV,Message> withEdges(DataSet<Edge<K,EV>> edgesWithValue,
                                                                                  ComputeFunction<K,VV,EV,Message> cf,
                                                                                  MessageCombiner<K,Message> mc,
                                                                                  int maximumNumberOfIterations)

Creates a new vertex-centric iteration operator for graphs where the edges are associated with a value (such as a weight or distance).

Type Parameters:

K - The type of the vertex key (the vertex identifier).

VV - The type of the vertex value (the state of the vertex).

Message - The type of the message sent between vertices along the edges.

EV - The type of the values that are associated with the edges.

Parameters:

edgesWithValue - The data set containing edges.

cf - The compute function.

mc - The function that combines messages sent to a vertex during a superstep.

Returns:

An instance of the vertex-centric graph computation operator.

configure

public void configure(VertexCentricConfiguration parameters)

Configures this vertex-centric iteration with the provided parameters.

Parameters:

parameters - the configuration parameters

getIterationConfiguration

public VertexCentricConfiguration getIterationConfiguration()

Returns:

the configuration parameters of this vertex-centric iteration