.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "tutorials/bipartite_matching_maxflow.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

    .. note::
        :class: sphx-glr-download-link-note

        :ref:`Go to the end <sphx_glr_download_tutorials_bipartite_matching_maxflow.py>`
        to download the full example code.

.. rst-class:: sphx-glr-example-title

.. _sphx_glr_tutorials_bipartite_matching_maxflow.py:


.. _tutorials-bipartite-matching-maxflow:

==========================================
Maximum Bipartite Matching by Maximum Flow
==========================================

This example presents how to visualise bipartite matching using maximum flow (see :meth:`igraph.Graph.maxflow`).

.. note::  :meth:`igraph.Graph.maximum_bipartite_matching` is usually a better way to find the maximum bipartite matching. For a demonstration on how to use that method instead, check out :ref:`tutorials-bipartite-matching`.

.. GENERATED FROM PYTHON SOURCE LINES 12-16

.. code-block:: Python


    import igraph as ig
    import matplotlib.pyplot as plt








.. GENERATED FROM PYTHON SOURCE LINES 17-18

We start by creating the bipartite directed graph.

.. GENERATED FROM PYTHON SOURCE LINES 18-24

.. code-block:: Python

    g = ig.Graph(
        9,
        [(0, 4), (0, 5), (1, 4), (1, 6), (1, 7), (2, 5), (2, 7), (2, 8), (3, 6), (3, 7)],
        directed=True,
    )








.. GENERATED FROM PYTHON SOURCE LINES 25-28

We assign:
 - nodes 0-3 to one side
 - nodes 4-8 to the other side

.. GENERATED FROM PYTHON SOURCE LINES 28-31

.. code-block:: Python

    g.vs[range(4)]["type"] = True
    g.vs[range(4, 9)]["type"] = False








.. GENERATED FROM PYTHON SOURCE LINES 32-33

Then we add a source (vertex 9) and a sink (vertex 10)

.. GENERATED FROM PYTHON SOURCE LINES 33-40

.. code-block:: Python

    g.add_vertices(2)
    g.add_edges([(9, 0), (9, 1), (9, 2), (9, 3)])  # connect source to one side
    g.add_edges([(4, 10), (5, 10), (6, 10), (7, 10), (8, 10)])  # ... and sinks to the other

    flow = g.maxflow(9, 10)
    print("Size of maximum matching (maxflow) is:", flow.value)





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    Size of maximum matching (maxflow) is: 4.0




.. GENERATED FROM PYTHON SOURCE LINES 41-42

Let's compare the output against :meth:`igraph.Graph.maximum_bipartite_matching`:

.. GENERATED FROM PYTHON SOURCE LINES 42-50

.. code-block:: Python


    # delete the source and sink, which are unneeded for this function.
    g2 = g.copy()
    g2.delete_vertices([9, 10])
    matching = g2.maximum_bipartite_matching()
    matching_size = sum(1 for i in range(4) if matching.is_matched(i))
    print("Size of maximum matching (maximum_bipartite_matching) is:", matching_size)





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    Size of maximum matching (maximum_bipartite_matching) is: 4




.. GENERATED FROM PYTHON SOURCE LINES 51-54

Last, we can display the original flow graph nicely with the matchings added.
To achieve a pleasant visual effect, we set the positions of source and sink
manually:

.. GENERATED FROM PYTHON SOURCE LINES 54-69

.. code-block:: Python

    layout = g.layout_bipartite()
    layout[9] = (2, -1)
    layout[10] = (2, 2)

    fig, ax = plt.subplots()
    ig.plot(
        g,
        target=ax,
        layout=layout,
        vertex_size=30,
        vertex_label=range(g.vcount()),
        vertex_color=["lightblue" if i < 9 else "orange" for i in range(11)],
        edge_width=[1.0 + flow.flow[i] for i in range(g.ecount())],
    )
    plt.show()



.. image-sg:: /tutorials/images/sphx_glr_bipartite_matching_maxflow_001.png
   :alt: bipartite matching maxflow
   :srcset: /tutorials/images/sphx_glr_bipartite_matching_maxflow_001.png
   :class: sphx-glr-single-img






.. rst-class:: sphx-glr-timing

   **Total running time of the script:** (0 minutes 0.097 seconds)


.. _sphx_glr_download_tutorials_bipartite_matching_maxflow.py:

.. only:: html

  .. container:: sphx-glr-footer sphx-glr-footer-example

    .. container:: sphx-glr-download sphx-glr-download-jupyter

      :download:`Download Jupyter notebook: bipartite_matching_maxflow.ipynb <bipartite_matching_maxflow.ipynb>`

    .. container:: sphx-glr-download sphx-glr-download-python

      :download:`Download Python source code: bipartite_matching_maxflow.py <bipartite_matching_maxflow.py>`

    .. container:: sphx-glr-download sphx-glr-download-zip

      :download:`Download zipped: bipartite_matching_maxflow.zip <bipartite_matching_maxflow.zip>`


.. only:: html

 .. rst-class:: sphx-glr-signature

    `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_