In Gelly, a Graph is represented by a DataSet of vertices and a DataSet of edges.
The Graph nodes are represented by the Vertex type. A Vertex is defined by a unique ID and a value. Vertex IDs should implement the Comparable interface. Vertices without value can be represented by setting the value type to NullValue.
The graph edges are represented by the Edge type. An Edge is defined by a source ID (the ID of the source Vertex), a target ID (the ID of the target Vertex) and an optional value. The source and target IDs should be of the same type as the Vertex IDs. Edges with no value have a NullValue value type.
In Gelly an Edge is always directed from the source vertex to the target vertex. A Graph may be undirected if for
every Edge it contains a matching Edge from the target vertex to the source vertex.
from a DataSet of edges and an optional DataSet of vertices:
from a DataSet of Tuple2 representing the edges. Gelly will convert each Tuple2 to an Edge, where the first field will be the source ID and the second field will be the target ID. Both vertex and edge values will be set to NullValue.
from a DataSet of Tuple3 and an optional DataSet of Tuple2. In this case, Gelly will convert each Tuple3 to an Edge, where the first field will be the source ID, the second field will be the target ID and the third field will be the edge value. Equivalently, each Tuple2 will be converted to a Vertex, where the first field will be the vertex ID and the second field will be the vertex value:
from a CSV file of Edge data and an optional CSV file of Vertex data. In this case, Gelly will convert each row from the Edge CSV file to an Edge, where the first field will be the source ID, the second field will be the target ID and the third field (if present) will be the edge value. Equivalently, each row from the optional Vertex CSV file will be converted to a Vertex, where the first field will be the vertex ID and the second field (if present) will be the vertex value. In order to get a Graph from a GraphCsvReader one has to specify the types, using one of the following methods:
types(Class<K> vertexKey, Class<VV> vertexValue,Class<EV> edgeValue): both vertex and edge values are present.
edgeTypes(Class<K> vertexKey, Class<EV> edgeValue): the Graph has edge values, but no vertex values.
vertexTypes(Class<K> vertexKey, Class<VV> vertexValue): the Graph has vertex values, but no edge values.
keyType(Class<K> vertexKey): the Graph has no vertex values and no edge values.
from a CSV file of Edge data and an optional CSV file of Vertex data.
In this case, Gelly will convert each row from the Edge CSV file to an Edge.
The first field of the each row will be the source ID, the second field will be the target ID and the third field (if present) will be the edge value.
If the edges have no associated value, set the edge value type parameter (3rd type argument) to NullValue.
You can also specify that the vertices are initialized with a vertex value.
If you provide a path to a CSV file via pathVertices, each row of this file will be converted to a Vertex.
The first field of each row will be the vertex ID and the second field will be the vertex value.
If you provide a vertex value initializer MapFunction via the vertexValueInitializer parameter, then this function is used to generate the vertex values.
The set of vertices will be created automatically from the edges input.
If the vertices have no associated value, set the vertex value type parameter (2nd type argument) to NullValue.
The vertices will then be automatically created from the edges input with vertex value of type NullValue.
from a Collection of edges and an optional Collection of vertices:
If no vertex input is provided during Graph creation, Gelly will automatically produce the VertexDataSet from the edge input. In this case, the created vertices will have no values. Alternatively, you can provide a MapFunction as an argument to the creation method, in order to initialize the Vertex values:
If no vertex input is provided during Graph creation, Gelly will automatically produce the VertexDataSet from the edge input. In this case, the created vertices will have no values. Alternatively, you can provide a MapFunction as an argument to the creation method, in order to initialize the Vertex values:
Map: Gelly provides specialized methods for applying a map transformation on the vertex values or edge values. mapVertices and mapEdges return a new Graph, where the IDs of the vertices (or edges) remain unchanged, while the values are transformed according to the provided user-defined map function. The map functions also allow changing the type of the vertex or edge values.
Translate: Gelly provides specialized methods for translating the value and/or type of vertex and edge IDs (translateGraphIDs), vertex values (translateVertexValues), or edge values (translateEdgeValues). Translation is performed by the user-defined map function, several of which are provided in the org.apache.flink.graph.asm.translate package. The same MapFunction can be used for all the three translate methods.
Filter: A filter transformation applies a user-defined filter function on the vertices or edges of the Graph. filterOnEdges will create a sub-graph of the original graph, keeping only the edges that satisfy the provided predicate. Note that the vertex dataset will not be modified. Respectively, filterOnVertices applies a filter on the vertices of the graph. Edges whose source and/or target do not satisfy the vertex predicate are removed from the resulting edge dataset. The subgraph method can be used to apply a filter function to the vertices and the edges at the same time.
Join: Gelly provides specialized methods for joining the vertex and edge datasets with other input datasets. joinWithVertices joins the vertices with a Tuple2 input data set. The join is performed using the vertex ID and the first field of the Tuple2 input as the join keys. The method returns a new Graph where the vertex values have been updated according to a provided user-defined transformation function.
Similarly, an input dataset can be joined with the edges, using one of three methods. joinWithEdges expects an input DataSet of Tuple3 and joins on the composite key of both source and target vertex IDs. joinWithEdgesOnSource expects a DataSet of Tuple2 and joins on the source key of the edges and the first attribute of the input dataset and joinWithEdgesOnTarget expects a DataSet of Tuple2 and joins on the target key of the edges and the first attribute of the input dataset. All three methods apply a transformation function on the edge and the input data set values.
Note that if the input dataset contains a key multiple times, all Gelly join methods will only consider the first value encountered.
Reverse: the reverse() method returns a new Graph where the direction of all edges has been reversed.
Undirected: In Gelly, a Graph is always directed. Undirected graphs can be represented by adding all opposite-direction edges to a graph. For this purpose, Gelly provides the getUndirected() method.
Union: Gelly’s union() method performs a union operation on the vertex and edge sets of the specified graph and the current graph. Duplicate vertices are removed from the resulting Graph, while if duplicate edges exist, these will be preserved.
Difference: Gelly’s difference() method performs a difference on the vertex and edge sets of the current graph and the specified graph.
Intersect: Gelly’s intersect() method performs an intersect on the edge
sets of the current graph and the specified graph. The result is a new Graph that contains all
edges that exist in both input graphs. Two edges are considered equal, if they have the same source
identifier, target identifier and edge value. Vertices in the resulting graph have no
value. If vertex values are required, one can for example retrieve them from one of the input graphs using
the joinWithVertices() method.
Depending on the parameter distinct, equal edges are either contained once in the resulting
Graph or as often as there are pairs of equal edges in the input graphs.
Gelly includes the following methods for adding and removing vertices and edges from an input Graph:
Neighborhood Methods
Neighborhood methods allow vertices to perform an aggregation on their first-hop neighborhood.
reduceOnEdges() can be used to compute an aggregation on the values of the neighboring edges of a vertex and reduceOnNeighbors() can be used to compute an aggregation on the values of the neighboring vertices. These methods assume associative and commutative aggregations and exploit combiners internally, significantly improving performance.
The neighborhood scope is defined by the EdgeDirection parameter, which takes the values IN, OUT or ALL. IN will gather all in-coming edges (neighbors) of a vertex, OUT will gather all out-going edges (neighbors), while ALL will gather all edges (neighbors).
For example, assume that you want to select the minimum weight of all out-edges for each vertex in the following graph:
The following code will collect the out-edges for each vertex and apply the SelectMinWeight() user-defined function on each of the resulting neighborhoods:
Similarly, assume that you would like to compute the sum of the values of all in-coming neighbors, for every vertex. The following code will collect the in-coming neighbors for each vertex and apply the SumValues() user-defined function on each neighborhood:
When the aggregation function is not associative and commutative or when it is desirable to return more than one values per vertex, one can use the more general
groupReduceOnEdges() and groupReduceOnNeighbors() methods.
These methods return zero, one or more values per vertex and provide access to the whole neighborhood.
For example, the following code will output all the vertex pairs which are connected with an edge having a weight of 0.5 or more:
When the aggregation computation does not require access to the vertex value (for which the aggregation is performed), it is advised to use the more efficient EdgesFunction and NeighborsFunction for the user-defined functions. When access to the vertex value is required, one should use EdgesFunctionWithVertexValue and NeighborsFunctionWithVertexValue instead.
Gelly provides a simple utility for performing validation checks on input graphs. Depending on the application context, a graph may or may not be valid according to certain criteria. For example, a user might need to validate whether their graph contains duplicate edges or whether its structure is bipartite. In order to validate a graph, one can define a custom GraphValidator and implement its validate() method. InvalidVertexIdsValidator is Gelly’s pre-defined validator. It checks that the edge set contains valid vertex IDs, i.e. that all edge IDs
also exist in the vertex IDs set.