org.apache.flink.graph.library

Class TriangleEnumerator<K extends Comparable<K>,VV,EV>

java.lang.Object

org.apache.flink.graph.library.TriangleEnumerator<K,VV,EV>

All Implemented Interfaces:

GraphAlgorithm<K,VV,EV,DataSet<Tuple3<K,K,K>>>

public class TriangleEnumerator<K extends Comparable<K>,VV,EV>
extends Object
implements GraphAlgorithm<K,VV,EV,DataSet<Tuple3<K,K,K>>>

This library method enumerates unique triangles present in the input graph. A triangle consists of three edges that connect three vertices with each other. Edge directions are ignored here. The method returns a DataSet of Tuple3, where the fields of each Tuple3 contain the Vertex IDs of a triangle.

The basic algorithm works as follows: It groups all edges that share a common vertex and builds triads, i.e., triples of vertices that are connected by two edges. Finally, all triads are filtered for which no third edge exists that closes the triangle.

For a group of n edges that share a common vertex, the number of built triads is quadratic ((n*(n-1))/2). Therefore, an optimization of the algorithm is to group edges on the vertex with the smaller output degree to reduce the number of triads. This implementation extends the basic algorithm by computing output degrees of edge vertices and grouping on edges on the vertex with the smaller degree.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	TriangleEnumerator.EdgeWithDegrees<K>
static class	TriangleEnumerator.Triad<K>

Constructor Summary

Constructors

Constructor and Description
TriangleEnumerator()

Method Summary

Modifier and Type	Method and Description
DataSet<Tuple3<K,K,K>>	run(Graph<K,VV,EV> input)

Methods inherited from class java.lang.Object

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

Constructor Detail

TriangleEnumerator

public TriangleEnumerator()

Method Detail

run

public DataSet<Tuple3<K,K,K>> run(Graph<K,VV,EV> input)
                           throws Exception

Specified by:

run in interface GraphAlgorithm<K extends Comparable<K>,VV,EV,DataSet<Tuple3<K extends Comparable<K>,K extends Comparable<K>,K extends Comparable<K>>>>

Throws:

Exception