
.. 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

        Click :ref:`here <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-13

.. code-block:: default

    import igraph as ig
    import matplotlib.pyplot as plt








.. GENERATED FROM PYTHON SOURCE LINES 14-15

First we generate three different graphs:

.. GENERATED FROM PYTHON SOURCE LINES 15-19

.. code-block:: default

    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 20-21

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

.. GENERATED FROM PYTHON SOURCE LINES 21-36

.. code-block:: default

    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

 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 37-41

.. 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 43-44

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

.. GENERATED FROM PYTHON SOURCE LINES 44-72

.. code-block:: default

    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.265 seconds)


.. _sphx_glr_download_tutorials_isomorphism.py:


.. only :: html

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



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

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



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

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


.. only:: html

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

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