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

.. only:: html

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

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

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

.. _sphx_glr_tutorials_isomorphism.py:


.. _tutorials-isomorphism:

===========
Isomorphism
===========

This example shows how to check for `isomorphism <https://en.wikipedia.org/wiki/Graph_isomorphism>`_ between small graphs using :meth:`igraph.GraphBase.isomorphic`.

.. GENERATED FROM PYTHON SOURCE LINES 10-14

.. code-block:: Python


    import igraph as ig
    import matplotlib.pyplot as plt








.. GENERATED FROM PYTHON SOURCE LINES 15-16

First we generate three different graphs:

.. GENERATED FROM PYTHON SOURCE LINES 16-20

.. code-block:: Python

    g1 = ig.Graph([(0, 1), (0, 2), (0, 4), (1, 2), (1, 3), (2, 3), (2, 4), (3, 4)])
    g2 = ig.Graph([(4, 2), (4, 3), (4, 0), (2, 3), (2, 1), (3, 1), (3, 0), (1, 0)])
    g3 = ig.Graph([(4, 1), (4, 3), (4, 0), (2, 3), (2, 1), (3, 1), (3, 0), (1, 0)])








.. GENERATED FROM PYTHON SOURCE LINES 21-22

To check whether they are isomorphic, we can use a simple method:

.. GENERATED FROM PYTHON SOURCE LINES 22-37

.. code-block:: Python

    print("Are the graphs g1 and g2 isomorphic?")
    print(g1.isomorphic(g2))
    print("Are the graphs g1 and g3 isomorphic?")
    print(g1.isomorphic(g3))
    print("Are the graphs g2 and g3 isomorphic?")
    print(g2.isomorphic(g3))

    # Output:
    # Are the graphs g1 and g2 isomorphic?
    # True
    # Are the graphs g1 and g3 isomorphic?
    # False
    # Are the graphs g2 and g3 isomorphic?
    # False





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

 .. code-block:: none

    Are the graphs g1 and g2 isomorphic?
    True
    Are the graphs g1 and g3 isomorphic?
    False
    Are the graphs g2 and g3 isomorphic?
    False




.. GENERATED FROM PYTHON SOURCE LINES 38-42

.. note::
   `Graph isomorphism <https://en.wikipedia.org/wiki/Graph_isomorphism>`_ is an equivalence
   relationship, i.e. if `g1 ~ g2` and `g2 ~ g3`, then automatically `g1 ~ g3`. Therefore,
   we could have skipped the last check.

.. GENERATED FROM PYTHON SOURCE LINES 44-45

We can plot the graphs to get an idea about the problem:

.. GENERATED FROM PYTHON SOURCE LINES 45-87

.. code-block:: Python

    visual_style = {
        "vertex_color": "lightblue",
        "vertex_label": [0, 1, 2, 3, 4],
        "vertex_size": 25,
    }

    fig, axs = plt.subplots(1, 3)
    ig.plot(
        g1,
        layout=g1.layout("circle"),
        target=axs[0],
        **visual_style,
    )
    ig.plot(
        g2,
        layout=g1.layout("circle"),
        target=axs[1],
        **visual_style,
    )
    ig.plot(
        g3,
        layout=g1.layout("circle"),
        target=axs[2],
        **visual_style,
    )
    fig.text(
        0.38,
        0.5,
        "$\\simeq$" if g1.isomorphic(g2) else "$\\neq$",
        fontsize=15,
        ha="center",
        va="center",
    )
    fig.text(
        0.65,
        0.5,
        "$\\simeq$" if g2.isomorphic(g3) else "$\\neq$",
        fontsize=15,
        ha="center",
        va="center",
    )
    plt.show()



.. image-sg:: /tutorials/images/sphx_glr_isomorphism_001.png
   :alt: isomorphism
   :srcset: /tutorials/images/sphx_glr_isomorphism_001.png
   :class: sphx-glr-single-img






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

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


.. _sphx_glr_download_tutorials_isomorphism.py:

.. only:: html

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

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

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

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

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

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

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


.. only:: html

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

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