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

.. only:: html

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

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

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

.. _sphx_glr_tutorials_topological_sort.py:


.. _tutorials-topological-sort:

===================
Topological sorting
===================

This example demonstrates how to get a topological sorting on a directed acyclic graph (DAG). A topological sorting of a directed graph is a linear ordering based on the precedence implied by the directed edges. It exists iff the graph doesn't have any cycle. In ``igraph``, we can use :meth:`igraph.GraphBase.topological_sorting` to get a topological ordering of the vertices.

.. GENERATED FROM PYTHON SOURCE LINES 10-15

.. code-block:: Python


    import igraph as ig
    import matplotlib.pyplot as plt









.. GENERATED FROM PYTHON SOURCE LINES 16-17

First off, we generate a directed acyclic graph (DAG):

.. GENERATED FROM PYTHON SOURCE LINES 17-22

.. code-block:: Python

    g = ig.Graph(
        edges=[(0, 1), (0, 2), (1, 3), (2, 4), (4, 3), (3, 5), (4, 5)],
        directed=True,
    )








.. GENERATED FROM PYTHON SOURCE LINES 23-24

We can verify immediately that this is actually a DAG:

.. GENERATED FROM PYTHON SOURCE LINES 24-26

.. code-block:: Python

    assert g.is_dag








.. GENERATED FROM PYTHON SOURCE LINES 27-30

A topological sorting can be computed quite easily by calling
:meth:`igraph.GraphBase.topological_sorting`, which returns a list of vertex IDs.
If the given graph is not DAG, the error will occur.

.. GENERATED FROM PYTHON SOURCE LINES 30-33

.. code-block:: Python

    results = g.topological_sorting(mode="out")
    print("Topological sort of g (out):", *results)





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

 .. code-block:: none

    Topological sort of g (out): 0 1 2 4 3 5




.. GENERATED FROM PYTHON SOURCE LINES 34-38

In fact, there are two modes of :meth:`igraph.GraphBase.topological_sorting`,
``'out'`` ``'in'``. ``'out'`` is the default and starts from a node with
indegree equal to 0. Vice versa, ``'in'`` starts from a node with outdegree
equal to 0. To call the other mode, we can simply use:

.. GENERATED FROM PYTHON SOURCE LINES 38-41

.. code-block:: Python

    results = g.topological_sorting(mode="in")
    print("Topological sort of g (in):", *results)





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

 .. code-block:: none

    Topological sort of g (in): 5 3 1 4 2 0




.. GENERATED FROM PYTHON SOURCE LINES 42-43

We can use :meth:`igraph.Vertex.indegree` to find the indegree of the node.

.. GENERATED FROM PYTHON SOURCE LINES 43-61

.. code-block:: Python

    for i in range(g.vcount()):
        print("degree of {}: {}".format(i, g.vs[i].indegree()))

    # %
    # Finally, we can plot the graph to make the situation a little clearer.
    # Just to change things up a bit, we use the matplotlib visualization mode
    # inspired by `xkcd <https://xkcd.com/>_:
    with plt.xkcd():
        fig, ax = plt.subplots(figsize=(5, 5))
        ig.plot(
            g,
            target=ax,
            layout="kk",
            vertex_size=25,
            edge_width=4,
            vertex_label=range(g.vcount()),
            vertex_color="white",
        )



.. image-sg:: /tutorials/images/sphx_glr_topological_sort_001.png
   :alt: topological sort
   :srcset: /tutorials/images/sphx_glr_topological_sort_001.png
   :class: sphx-glr-single-img


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

 .. code-block:: none

    degree of 0: 0
    degree of 1: 1
    degree of 2: 1
    degree of 3: 2
    degree of 4: 1
    degree of 5: 2





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

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


.. _sphx_glr_download_tutorials_topological_sort.py:

.. only:: html

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

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

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

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

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

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

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


.. only:: html

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

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