Graph Mutation & Subgraphs

Copying and Simplifying Graphs

The following method creates a simplified version of the graph:

 1graph.simplify(
 2    vertex_properties=True,
 3    edge_properties=True,
 4    keep_multi_edges=False,
 5    keep_self_edges=False,
 6    keep_trivial_vertices=False,
 7    in_place=False,
 8    name=None
 9)
10merging_strategy_builder = graph.create_merging_strategy_builder()
11mutation_strategy = merging_strategy_builder.set_copy_mode(False) \
12    .drop_vertex_properties(graph.get_vertex_properties()) \
13    .build()
14graph.simplify_with_strategy(mutation_strategy)

The first two arguments (vertex_properties and edge_properties) list which properties will be copied into the newly created simplified graph instance.

or their blocking variants:

1graph.clone(vertex_properties=True, edge_properties=True, name=None)

As with simplify(), the user can specify optional properties of the graph to copy with vertex_properties and edge_properties. If no properties are specified, all of the original graph’s properties will be copied into the new graph instance. The user can specify the name of the newly created graph instance with newGraphName.

Transposing Graphs

The following method creates a transposed version of the graph:

1graph.transpose(
2    vertex_properties=True,
3    edge_properties=True,
4    edge_label_mapping=None,
5    in_place=False,
6    name=None
7)

The first two arguments (vertex_properties and edge_properties) list which properties will be copied into the newly created simplified graph instance.

Undirecting Graphs

The following methods create the undirected version of a graph instance:

 1graph.undirect(
 2    vertex_properties=True,
 3    edge_properties=True,
 4    keep_multi_edges=True,
 5    keep_self_edges=True,
 6    keep_trivial_vertices=True,
 7    in_place=False,
 8    name=None
 9)
10graph.undirect_with_strategy(mutation_strategy)

The first two methods create an undirected version of the graph while copying all of the vertex properties. newGraphName is an optional argument to specify the name of the newly created graph instance.

In contrast, the third and fourth methods concurrently perform undirecting and simplifying of a graph. For the meaning of each parameter, refer to the steps for simplifying a graph in the above section. All methods return an object of the undirected PgxGraph type.

Note, that an undirected graph has some restrictions. Some algorithms are only supported on directed graphs or are not yet supported for undirected graphs. Further, PGX does not support to store undirected graphs nor reading from undirected formats. Since the edges do not have a direction anymore, the behavior of pgxEdge.source or pgxEdge.destination can be ambiguous. In order to provide deterministic results, PGX will always return the vertex with the smaller internal id as source and the other as destination vertex.

Advanced Multi-Edge Handling

Picking

This strategy can be used to pick an edge out of multi-edges. PGX allows the user to define several picking criteria. One can pick by:

  1. Property

  2. Label

  3. Edge-ID

Every picking criteria has to be combined with a picking_strategy_function. PGX supports either picking_strategy_function.min and picking_strategy_function.max, which picks the edge whose property/label/id is either minimal or maximal. If one does not specify a picking criteria, PGX will non-deterministically pick an edge out of the multi-edges.

A PickingStrategy can be created using a PickingStrategyBuilder, which can be retrieved by calling create_picking_strategy_builder() on the target graph.

One can choose the decided picking criteria by calling one of the following functions:

 1picking_strategy_builder = graph.create_picking_strategy_builder()
 2# Pick by edge
 3picking_strategy_function = "max"
 4picking_strategy_builder.set_pick_by_edge_id(
 5    picking_strategy_function
 6)
 7# Pick by label
 8picking_strategy_function = "max"
 9picking_strategy_builder.set_pick_by_label(
10    picking_strategy_function
11)
12# Pick by property
13prop = "cost"
14picking_strategy_function = "min"
15picking_strategy_builder.set_pick_by_property(
16    prop,
17    picking_strategy_function
18)

The following figure shows how PGX picks the edge with the minimal cost and takes all its properties.

picking strategy

StrategyBuilder in General

Both StrategyBuilders allow the same configurations. By default, they use the same values as in the convenience methods of simplify() and undirect(). This includes that all properties are kept by default. If one wants to drop specific properties, one can either use the drop_vertex_property() or drop_edge_property() functions.

 1merging_strategy_builder = graph.create_merging_strategy_builder()
 2mode = False
 3trivial_vertices = False
 4self_edges = False
 5multi_edges = False
 6merging_strategy_builder \
 7    .set_new_graph_name(new_graph_name="graph") \
 8    .set_copy_mode(mode) \
 9    .set_trivial_vertices(trivial_vertices) \
10    .set_self_edges(self_edges) \
11    .set_multi_edges(multi_edges) \
12    .set_kept_vertex_properties(props_to_keep=[]) \
13    .set_kept_edge_properties(props_to_keep=[]) \
14    .drop_vertex_properties(vertex_properties=graph.get_vertex_properties()) \
15    .drop_edge_properties(edge_properties=graph.get_edge_properties()) \
16    .drop_vertex_property(vertex_property=graph.get_vertex_property("price")) \
17    .drop_edge_property(edge_property=graph.get_edge_property("cost")) \
18    .build()

simplify() and undirect() can be called using a MutationStrategy as follows:

1merging_strategy_builder = graph.create_merging_strategy_builder()
2strategy = merging_strategy_builder.build()
3simplified_graph = graph.simplify_with_strategy(strategy)
4undirected_graph = graph.undirect_with_strategy(strategy)

Creating Subgraphs

PGX provides the following method for creating subgraphs via a filter expression:

1from pypgx.api.filters import EdgeFilter
2graph_filter = EdgeFilter("true")
3graph.filter(
4    graph_filter,
5    vertex_properties=True,
6    edge_properties=True,
7    name=None
8)

As in the other graph mutating methods, the user has the option to specify the name of the subgraph with the newGraphName parameter and of choosing the vertex/edge properties to be copied into the subgraph (vertex_properties and edge_properties). the above method returns a PgxGraph object which represents the created subgraph.

The filter method requires a GraphFilter argument containing a PGX filter expression. Fundamentally, the filter expression is a Boolean expression that is evaluated for every vertex/edge in the original, graph (in parallel). If the expression is evaluated as true for the vertex/edge, then the vertex/edge is included in the subgraph.

Creating a Bipartite Subgraph

PGX enables the client to create a bipartite subgraph with the following method:

1vset = graph.create_vertex_set()
2vset.add_all([graph.get_vertex(900), graph.get_vertex(42)])
3graph.bipartite_sub_graph_from_left_set(
4    vset,
5    vertex_properties=True,
6    edge_properties=True,
7    name=None,
8    is_left_name=None
9)

Noticeably, the methods require an additional argument vset, which points to a set of vertices whose elements (vertices) would contain the left vertices (i.e. vertices on the left side of the bipartite graph that have only edges to vertices on the right side) in the resulting bipartite graph.

Note: When creating the bipartite subgraph, PGX automatically inserts an additional boolean vertex property is_left. The value of this property is set true for the left vertices and false for the right vertices in the bipartite subgraph. The name of the is_left vertex property can be obtained with get_is_left_property() on the returned BipartiteGraph object.

The method returns the created BipartiteGraph instance.

Creating a Sparsified Subgraph

PGX supports creating a sparsified subgraph of a graph:

1graph.sparsify(
2    sparsification=0.5,
3    vertex_properties=True,
4    edge_properties=True,
5    name=None
6)

The sparsification argument is the sparsification coefficient with a value between 0.0 and 1.0.

The user again has the option to specify the name for the newly created graph (newGraphName) as well as the vertex/edge properties to be copied into the newly created graph instance (vertex_properties and edge_properties).

The returned PgxGraph object represents a sparsified subgraph which has fewer edges than the original graph.