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

.. only:: html

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

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

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

.. _sphx_glr_tutorials_spanning_trees.py:


.. _tutorials-spanning-trees:

==============
Spanning Trees
==============

This example shows how to generate a spanning tree from an input graph using :meth:`igraph.Graph.spanning_tree`. For the related idea of finding a *minimum spanning tree*, see :ref:`tutorials-minimum-spanning-trees`.

.. GENERATED FROM PYTHON SOURCE LINES 10-15

.. code-block:: Python


    import igraph as ig
    import matplotlib.pyplot as plt
    import random








.. GENERATED FROM PYTHON SOURCE LINES 16-17

First we create a two-dimensional, 6 by 6 lattice graph:

.. GENERATED FROM PYTHON SOURCE LINES 17-19

.. code-block:: Python

    g = ig.Graph.Lattice([6, 6], circular=False)








.. GENERATED FROM PYTHON SOURCE LINES 20-21

We can compute the 2D layout of the graph:

.. GENERATED FROM PYTHON SOURCE LINES 21-23

.. code-block:: Python

    layout = g.layout("grid")








.. GENERATED FROM PYTHON SOURCE LINES 24-27

To spice things up a little, we rearrange the vertex ids and compute a new
layout. While not terribly useful in this context, it does make for a more
interesting-looking spanning tree ;-)

.. GENERATED FROM PYTHON SOURCE LINES 27-36

.. code-block:: Python

    random.seed(0)
    permutation = list(range(g.vcount()))
    random.shuffle(permutation)
    g = g.permute_vertices(permutation)
    new_layout = g.layout("grid")
    for i in range(36):
        new_layout[i] = layout[permutation[i]]
    layout = new_layout








.. GENERATED FROM PYTHON SOURCE LINES 37-38

We can now generate a spanning tree:

.. GENERATED FROM PYTHON SOURCE LINES 38-40

.. code-block:: Python

    spanning_tree = g.spanning_tree(weights=None, return_tree=False)








.. GENERATED FROM PYTHON SOURCE LINES 41-45

Finally, we can plot the graph with a highlight color for the spanning tree.
We follow the usual recipe: first we set a few aesthetic options and then we
leverage :func:`igraph.plot() <igraph.drawing.plot>` and matplotlib for the
heavy lifting:

.. GENERATED FROM PYTHON SOURCE LINES 45-54

.. code-block:: Python

    g.es["color"] = "lightgray"
    g.es[spanning_tree]["color"] = "midnightblue"
    g.es["width"] = 0.5
    g.es[spanning_tree]["width"] = 3.0

    fig, ax = plt.subplots()
    ig.plot(g, target=ax, layout=layout, vertex_color="lightblue", edge_width=g.es["width"])
    plt.show()




.. image-sg:: /tutorials/images/sphx_glr_spanning_trees_001.png
   :alt: spanning trees
   :srcset: /tutorials/images/sphx_glr_spanning_trees_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 55-58

.. note::
  To invert the y axis such that the root of the tree is on top of the plot,
  you can call `ax.invert_yaxis()` before `plt.show()`.


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

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


.. _sphx_glr_download_tutorials_spanning_trees.py:

.. only:: html

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

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

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

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

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

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

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


.. only:: html

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

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