org.apache.flink.graph.library

Class Summarization<K,VV,EV>

java.lang.Object

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

Type Parameters:

K - vertex identifier type

VV - vertex value type

EV - edge value type

All Implemented Interfaces:

GraphAlgorithm<K,VV,EV,Graph<K,Summarization.VertexValue<VV>,Summarization.EdgeValue<EV>>>

public class Summarization<K,VV,EV>
extends Object
implements GraphAlgorithm<K,VV,EV,Graph<K,Summarization.VertexValue<VV>,Summarization.EdgeValue<EV>>>

The summarization algorithm computes a condensed version of the input graph by grouping vertices and edges based on their values. By doing this, the algorithm helps to uncover insights about patterns and distributions in the graph.

In the resulting graph, each vertex represents a group of vertices that share the same vertex value. An edge, that connects a vertex with itself, represents all edges with the same edge value that connect vertices inside that group. An edge between vertices in the output graph represents all edges with the same edge value between members of those groups in the input graph.

Consider the following example:

Input graph:

 Vertices (id, value):
 (0, "A")
 (1, "A")
 (2, "B")
 (3, "B")

 Edges (source, target, value):
 (0,1, null)
 (1,0, null)
 (1,2, null)
 (2,1, null)
 (2,3, null)
 (3,2, null)
 

Output graph:

Vertices (id, (value, count)):
 (0, ("A", 2)) // 0 and 1
 (2, ("B", 2)) // 2 and 3

 Edges (source, target, (value, count)):
 (0, 0, (null, 2)) // (0,1) and (1,0)
 (2, 2, (null, 2)) // (2,3) and (3,2)
 (0, 2, (null, 1)) // (1,2)
 (2, 0, (null, 1)) // (2,1)
 

Note that this implementation is non-deterministic in the way that it assigns identifiers to summarized vertices. However, it is guaranteed that the identifier is one of the represented vertex identifiers.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	Summarization.EdgeValue<EV> Value that is stored at a summarized edge.
static class	Summarization.VertexGroupItem<K,VGV> Represents a single vertex in a vertex group.
static class	Summarization.VertexValue<VV> Value that is stored at a summarized vertex.
static class	Summarization.VertexWithRepresentative<K> Represents a vertex identifier and its corresponding vertex group identifier.

Constructor Summary

Constructors

Constructor and Description
Summarization()

Method Summary

Modifier and Type	Method and Description
Graph<K,Summarization.VertexValue<VV>,Summarization.EdgeValue<EV>>	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

Summarization

public Summarization()

Method Detail

run

public Graph<K,Summarization.VertexValue<VV>,Summarization.EdgeValue<EV>> run(Graph<K,VV,EV> input)
                                                                       throws Exception

Specified by:

run in interface GraphAlgorithm<K,VV,EV,Graph<K,Summarization.VertexValue<VV>,Summarization.EdgeValue<EV>>>

Throws:

Exception