PGX 20.1.1

Mutating Graphs

PGX provides several methods for creating a mutated version of a loaded graph instance. Note that PGX always creates a new instance and returns it rather than directly mutating the original instance. This is because the original graph instance is immutable in PGX, since it may be shared among multiple clients. See the related document here.

The following sections explains mutation operators supported by PGX. See PGX API Guide for the APIs.

Altering Partitioned Graphs by Adding or Removing Vertex and Edge Providers

It is possible to add or remove vertex and edge providers of partitioned graphs using the alterGraph mutation APIs. Please read the dedicated documentation available at the graph alteration reference documentation.

Simplifying and Undirecting a Graph

In the literature, simplifying a graph instance can mean multiple things:

  • Removing self-edges (i.e., an edge whose source and destination are the same vertex)
  • Removing duplicated edges (i.e., multiple edges between a source vertex and a destination vertex)
  • Removing trivial vertices (i.e., vertices that are not connected to any other vertices)

PGX provides a method for simplifying a graph by combining any of the above operations.

Simplifying Graph

Figure: Simplifying a Graph

Similarly, PGX allows the users to create an undirected version of the graph. Note that while PGX originally treats graphs as directed (link), an undirected graph can be handled by creating extra edges from the reverse direction.

Simplifying Graph

Figure: Undirecting a Graph

Transposing a Graph

A transpose of a directed graph is another directed graph on the same set of vertices with all of the edges reversed. If source graph contains an edge (u,v) then the transposed graph will contain an edge (v,u) and vice versa.

Transposing Graph

Figure: Transposing a Graph

If graph is undirected, transpose operation has no effect.

Transposing Undirected Graph

Figure: Transposing an Undirected Graph

Creating Subgraphs

In PGX, it is possible to create subgraphs from an existing graph instance, dynamically, with a simple filter expression. For example, in the following figure, a subgraph is created by the original graph by choosing only the edges between the blue vertices.

Simplifying Graph

Figure: Creating a Subgraph

PGX also provides a specialized method for creating bipartite subgraphs. That is, given a set of vertices, PGX creates a bipartite subgraph instance whose left side is composed of the given vertices. The following figure shows an example of creating the bipartite subgraph from the left set of the vertices a,b,e.

Simplifying Graph

Figure: Creating a Bipartite Subgraph


PGX also provides a method called sortByDegree. Technically, this method does not mutate the graph at all. Instead, the method changes the internal representation of the graph so that the vertices are ordered by their (in-/out-)degree. Reordering vertices by their degree can affect the performance of certain algorithms (For instance, it can accelerate triangle counting significantly, as discussed in this paper.)