*************************************
Creating Subgraphs from Loaded Graphs
*************************************

The goal of this guide is to help you understand how to create a subgraph, based on an already loaded graph. First, we will introduce filter expressions, which are two different ways to create a subgraph in PGX. Then we will show how to create a bipartite subgraph based on a vertex collection that specifies the left set of the bipartite graph.

Recap: load a graph into memory
-------------------------------

To load a graph, you need a graph config stored in an accessible location that points to a graph that is accessible by PGX. If your graph is not stored on the same machine as the one where PGX runs, make sure that you can access it.

You can read a graph like this:

.. code-block:: python
   :linenos:

    session = pypgx.get_session(session_name="my-session")
    graph = session.read_graph_with_properties(self.graph_path)

Once the graph is loaded, you can become familiar with the semantics of our filter expressions  following the below introduction to understand the concept of filter expressions in PGX.

An introduction to filter expressions
-------------------------------------

Filter expressions in PGX are expressions that are evaluated for either each vertex or each edge. 
The expression can define some predicates that a vertex or edge has to fulfill in order to be contained in the result, in this case a subgraph.

This graph is based on the sample graph that is also used for other tutorials and it is part of the PGX download package.

.. image:: /_static/images/pgx-sample-graph.jpg
   :alt: pgx sample graph

The edge filter expression

.. code-block:: python

   src.prop1 == 10

conveys that each edge where the source vertex's property ``prop1`` equals the value 10 will match the expression. The following edges will be matched by this expression:

.. image:: /_static/images/pgx-sample-graph_highlight1.jpg
   :alt: pgx sample graph highlight 1

which results in the following subgraph:

.. image:: /_static/images/pgx-sample-graph_subgraph1.jpg
   :alt: pgx sample graph subgraph 1

The vertex filter expression

.. code-block:: python
   :linenos:

   vertex.prop1 < 10

expresses that each vertex where the property ``prop1`` is less than 10 will match the expression. The following vertices will be matched by this expression:

.. image:: /_static/images/pgx-sample-graph_vertex_highlight.png
   :alt: pgx sample graph vertex highlight

which results in the following subgraph:

.. image:: /_static/images/pgx-sample-graph_vertex_subgraph.png
   :alt: pgx sample graph vertex subgraph

Creating a subgraph based on a filter in PGX
--------------------------------------------

Example for creating and using an edge filter
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

.. code-block:: python
   :linenos:

    subgraph = graph.filter(EdgeFilter("src.prop1 == 10"))

Example for creating and using a vertex filter
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

.. code-block:: python
   :linenos:

    subgraph = graph.filter(VertexFilter("vertex.prop1 < 10"))

Create a subgraph based on a more complex filter
------------------------------------------------

This example focuses on a slightly more complex filter, which uses some special features of our filter expressions. One such feature is the :attr:`out_degree` function. It calculates the number of outgoing edges for an identifier (``src`` or ``dst``). The following filter expression matches all edges where the destination vertex has an outDegree higher than 1 and an edge property ``cost`` higher than 50.

.. code-block:: python
   :linenos:

   dst.out_degree > 1 && edge.cost > 50

There is only one edge in the sample graph which matches this filter expression:

.. image:: /_static/images/pgx-sample-graph_highlight2.jpg
   :alt: pgx sample graph highlight 2

The resulting subgraph looks like this:

.. image:: /_static/images/pgx-sample-graph_subgraph2.jpg
   :alt: pgx sample graph subgraph2

Combining filters
-----------------

It is also possible to combine vertex filters with edge filters.
Both filters are evaluated separately and afterwards merged by either creating a union of the results or by intersecting the results.

Creating a union of two filters
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Creating the union of the edge filter:

.. code-block:: python

   src.prop1 == 10

and the vertex filter:

.. code-block:: python
   :linenos:

   vertex.prop1 < 10

will result in the following graph:

.. image:: /_static/images/pgx-sample-graph_union.png
   :alt: pgx sample graph union

.. code-block:: python
   :linenos:

    edge_filter = EdgeFilter("src.prop1 == 10")
    vertex_filter = VertexFilter("vertex.prop1 < 10")
    filter = edge_filter.union(vertex_filter)
    subgraph = graph.filter(filter)

Creating an intersection of two filters
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Creating the intersection of the filters mentioned above will result in the following graph, that only consists of a single vertex:

.. image:: /_static/images/pgx-sample-graph_intersection.png
   :alt: pgx sample graph intersection

.. code-block:: python
   :linenos:

    edge_filter = EdgeFilter("src.prop1 == 10")
    vertex_filter = VertexFilter("vertex.prop1 < 10")
    filter = edge_filter.intersect(vertex_filter)
    subgraph = graph.filter(filter)


Creating a set of vertices or edges using a filter
--------------------------------------------------

Instead of using filters to create a subgraph they can also be used to only select a set of vertices or edges from a graph.
Creating a vertex set on the sample graph using the vertex filter expression

.. code-block:: python
   :linenos:

   vertex.prop1 < 10

will yield the following set: 

.. code-block:: none

   PgxVertex with ID 99
   PgxVertex with ID 333

These sets can for example be used to create a bipartite subgraph.

Example for creating a vertex set
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

.. code-block:: python
   :linenos:

    vertices = graph.get_vertices(filter_expr=VertexFilter("vertex.prop1 < 10"))

.. code-block:: python
   :linenos:

    edge_set = graph.get_edges(filter_expr=EdgeFilter("src.prop1 == 10"))

Create a bipartite subgraph based on a vertex list
--------------------------------------------------

The second way to create a subgraph is to specify a set of vertices and create a bipartite subgraph based on those vertices. The specified vertices will be used as the left-hand side of the bipartite subgraph. A bipartite subgraph only has edges between the left set and the other vertices (essentially the right-hand side), but not in between those groups (e.g. no edges from a left set vertex to another left set vertex and no edges between a right-hand side vertex to another right-hand side vertex). In PGX, vertices that are isolated because all the edges leading to and from it were deleted will not be part of the bipartite subgraph.

This is an example of a bipartite subgraph, without any properties shown:

.. image:: /_static/images/bipartite-sample-graph.jpg
   :alt: bipartite sample graph

Given the simple graph example from earlier, we can use PGX to create a bipartite subgraph based on a couple of vertices. Before creating the bipartite subgraph, however, we first need to create a new vertex collection and then fill it with the vertices we want to have on the left-hand side.

.. code-block:: python
   :linenos:

    s = graph.create_vertex_set()
    s.add_all([128, 99])
    bipartite = graph.bipartite_sub_graph_from_left_set(s)

When you create the subgraph PGX will automatically create a new boolean vertex property that stores whether a vertex is on the left side or not. You can then specify what the new vertex property should be called. The name must not have been previously used for another vertex property on this graph.

The resulting bipartite subgraph looks like this:

.. image:: /_static/images/pgx-sample-graph-bipartite.jpg
   :alt: pgx sample graph bipartite

As you may have noticed, the vertex with the ID ``1908`` is not in the bipartite subgraph. Since the only edge connecting that vertex to the graph was the one from ``128`` to ``1908`` that edge would violate the bipartite properties of the subgraph, the edge was removed. The ``1908`` vertex had no other connection to the graph and was removed as well.
Moreover, the edge from the vertex with the ID ``128`` to the vertex with ID ``99`` is not present in the bipartite subgraph, because edges are only allowed to go from left to right (and not from right to left).