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

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

.. code-block:: default

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








.. GENERATED FROM PYTHON SOURCE LINES 15-16

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

.. GENERATED FROM PYTHON SOURCE LINES 16-18

.. code-block:: default

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








.. GENERATED FROM PYTHON SOURCE LINES 19-20

We can compute the 2D layout of the graph:

.. GENERATED FROM PYTHON SOURCE LINES 20-22

.. code-block:: default

    layout = g.layout("grid")








.. GENERATED FROM PYTHON SOURCE LINES 23-26

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 26-35

.. code-block:: default

    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[permutation[i]] = layout[i]
    layout = new_layout








.. GENERATED FROM PYTHON SOURCE LINES 36-37

We can now generate a spanning tree:

.. GENERATED FROM PYTHON SOURCE LINES 37-39

.. code-block:: default

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








.. GENERATED FROM PYTHON SOURCE LINES 40-44

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 44-59

.. code-block:: default

    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 60-63

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


.. _sphx_glr_download_tutorials_spanning_trees.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: spanning_trees.py <spanning_trees.py>`



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

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


.. only:: html

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

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