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

.. only:: html

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

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

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

.. _sphx_glr_api_gallery_graph_theory_matching_plot_01_konig_hopcroft_karp.py:


König's theorem and Hopcroft-Karp matching
================================================

Finds a maximum matching in a random bipartite graph with the
Hopcroft-Karp algorithm and builds a vertex cover of exactly the same
size, as König's theorem guarantees.

.. GENERATED FROM PYTHON SOURCE LINES 11-16

.. code-block:: Python

    import matplotlib.pyplot as plt
    import numpy as np

    from mathematicskit.graph_theory import Graph, bipartite_matching








.. GENERATED FROM PYTHON SOURCE LINES 17-19

A random bipartite graph
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 19-39

.. code-block:: Python


    rng = np.random.default_rng(5)
    n_left, n_right = 8, 7
    g = Graph(n_left + n_right)
    for u in range(n_left):
        for v in rng.choice(n_right, size=rng.integers(1, 3), replace=False):
            g.add_edge(u, n_left + int(v))
    result = bipartite_matching(g, left=range(n_left))
    print(f"maximum matching size {result.size}: {result.pairs}")
    print(f"minimum vertex cover size {len(result.vertex_cover)}: {result.vertex_cover}")

    pos = {u: (0, -u) for u in range(n_left)} | {n_left + v: (2, -v - 0.5) for v in range(n_right)}
    fig, ax = plt.subplots(figsize=(5, 6))
    for u, v, _ in g.edges():
        matched = result.pairs.get(min(u, v)) == max(u, v)
        ax.plot(*zip(pos[u], pos[v]), color="tab:red" if matched else "0.8", lw=3 if matched else 1)
    for v, (x, y) in pos.items():
        ax.plot(x, y, "s" if v in result.vertex_cover else "o", color="tab:blue" if v in result.vertex_cover else "k", ms=10)
    ax.axis("off")
    ax.set_title("matching (red) and vertex cover (blue squares)")



.. image-sg:: /api/gallery/graph_theory/matching/images/sphx_glr_plot_01_konig_hopcroft_karp_001.png
   :alt: matching (red) and vertex cover (blue squares)
   :srcset: /api/gallery/graph_theory/matching/images/sphx_glr_plot_01_konig_hopcroft_karp_001.png
   :class: sphx-glr-single-img


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

 .. code-block:: none

    maximum matching size 6: {0: 8, 1: 11, 2: 9, 3: 10, 6: 14, 7: 12}
    minimum vertex cover size 6: [1, 2, 6, 8, 10, 12]

    Text(0.5, 1.0, 'matching (red) and vertex cover (blue squares)')




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

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


.. _sphx_glr_download_api_gallery_graph_theory_matching_plot_01_konig_hopcroft_karp.py:

.. only:: html

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

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

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

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

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

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

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


.. only:: html

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

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