.. DO NOT EDIT. .. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY. .. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE: .. "api/gallery/graph_theory/eulerian/plot_02_hierholzer_circuit.py" .. LINE NUMBERS ARE GIVEN BELOW. .. only:: html .. note:: :class: sphx-glr-download-link-note :ref:`Go to the end ` to download the full example code or to run this example in your browser via JupyterLite. .. rst-class:: sphx-glr-example-title .. _sphx_glr_api_gallery_graph_theory_eulerian_plot_02_hierholzer_circuit.py: Hierholzer's algorithm: constructing an Eulerian circuit ======================================================== Euler showed that a closed walk using every edge once forces every vertex to have even degree. Hierholzer (1873) proved the converse for a connected graph, and his proof is an algorithm: walk along unused edges until you are stuck, which can only happen back where you started; then, from any vertex of that closed walk that still has unused edges, walk a second closed tour and splice it in. Repeat until no edge is left. The octahedron below has every vertex of degree 4. A greedy walk from vertex 0 gets stuck back at 0 after 9 of its 12 edges, and the remaining triangle has to be spliced in. .. GENERATED FROM PYTHON SOURCE LINES 19-32 .. code-block:: Python import matplotlib.pyplot as plt import numpy as np from mathematicskit.graph_theory import Graph, eulerian_circuit, odd_degree_vertices opposite = {(0, 3), (1, 4), (2, 5)} octahedron = Graph(6) for u in range(6): for v in range(u + 1, 6): if (u, v) not in opposite: octahedron.add_edge(u, v) print(f"edges: {len(octahedron.edges())}, odd-degree vertices: {odd_degree_vertices(octahedron)}") .. rst-class:: sphx-glr-script-out .. code-block:: none edges: 12, odd-degree vertices: [] .. GENERATED FROM PYTHON SOURCE LINES 33-41 Getting stuck, then splicing ------------------------------ Walking greedily from vertex 0 (always to the lowest-numbered unused neighbour) ends back at 0 with three edges unused. Hierholzer's insight is that this is not a failure: the unused edges still have even degree at every vertex, so they form closed tours, and each one starts at a vertex already on the walk, where it can be inserted. .. GENERATED FROM PYTHON SOURCE LINES 41-64 .. code-block:: Python def greedy_closed_walk(graph, start, used): walk = [start] while True: options = [v for v in sorted(graph.neighbors(walk[-1])) if frozenset((walk[-1], v)) not in used] if not options: return walk used.add(frozenset((walk[-1], options[0]))) walk.append(options[0]) used: set = set() tours = [greedy_closed_walk(octahedron, 0, used)] while len(used) < len(octahedron.edges()): start = next(v for tour in tours for v in tour if any(frozenset((v, w)) not in used for w in octahedron.neighbors(v))) tours.append(greedy_closed_walk(octahedron, start, used)) for k, tour in enumerate(tours): print(f"closed tour {k + 1}: {tour}") circuit = eulerian_circuit(octahedron, start=0) print(f"eulerian_circuit: {circuit} ({len(circuit) - 1} edges)") .. rst-class:: sphx-glr-script-out .. code-block:: none closed tour 1: [0, 1, 2, 0, 4, 2, 3, 1, 5, 0] closed tour 2: [4, 3, 5, 4] eulerian_circuit: [0, 5, 4, 3, 5, 1, 3, 2, 4, 0, 2, 1, 0] (12 edges) .. GENERATED FROM PYTHON SOURCE LINES 65-67 Drawing the tours and the circuit ----------------------------------- .. GENERATED FROM PYTHON SOURCE LINES 67-98 .. code-block:: Python angles = np.pi / 2 + 2 * np.pi * np.arange(3) / 3 outer = np.column_stack([np.cos(angles), np.sin(angles)]) pos = np.vstack([outer, -0.45 * outer]) # vertex k + 3 sits opposite vertex k def draw_edges(ax, walk, color, numbered=False): for k, (u, v) in enumerate(zip(walk, walk[1:], strict=False)): p, q = pos[u], pos[v] ax.annotate("", q, p, arrowprops={"arrowstyle": "-|>", "color": color, "lw": 2, "shrinkA": 12, "shrinkB": 12}) if numbered: ax.annotate(str(k + 1), (p + q) / 2, ha="center", va="center", fontsize=8, bbox={"boxstyle": "circle", "fc": "white", "ec": color}) fig, axes = plt.subplots(1, 2, figsize=(11, 5.2)) colors = plt.cm.tab10.colors for ax in axes: for u, v, _ in octahedron.edges(): ax.plot(*pos[[u, v]].T, color="0.85", lw=4, zorder=0) ax.scatter(*pos.T, s=500, color="white", edgecolors="black", zorder=3) for v, (x, y) in enumerate(pos): ax.annotate(str(v), (x, y), ha="center", va="center", zorder=4) ax.set_aspect("equal") ax.axis("off") for k, tour in enumerate(tours): draw_edges(axes[0], tour, colors[k]) axes[0].set_title(f"Greedy walking leaves {len(tours)} closed tours") draw_edges(axes[1], circuit, "tab:blue", numbered=True) axes[1].set_title("Spliced together: one Eulerian circuit") fig.tight_layout() .. image-sg:: /api/gallery/graph_theory/eulerian/images/sphx_glr_plot_02_hierholzer_circuit_001.png :alt: Greedy walking leaves 2 closed tours, Spliced together: one Eulerian circuit :srcset: /api/gallery/graph_theory/eulerian/images/sphx_glr_plot_02_hierholzer_circuit_001.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 99-106 An application: de Bruijn sequences ------------------------------------- A cyclic binary string in which every 4-bit word appears exactly once is an Eulerian circuit of the de Bruijn graph on 3-bit words, whose edges append one bit. Every vertex there has in-degree equal to out-degree 2. .. GENERATED FROM PYTHON SOURCE LINES 106-116 .. code-block:: Python de_bruijn = Graph(8, directed=True) for word in range(8): for bit in (0, 1): de_bruijn.add_edge(word, ((word << 1) | bit) & 7) sequence = "".join(str(w & 1) for w in eulerian_circuit(de_bruijn)[1:]) words = sorted({(sequence + sequence[:3])[i : i + 4] for i in range(len(sequence))}) print(f"de Bruijn sequence: {sequence} contains {len(words)} distinct 4-bit words") plt.show() .. rst-class:: sphx-glr-script-out .. code-block:: none de Bruijn sequence: 1111011001010000 contains 16 distinct 4-bit words .. rst-class:: sphx-glr-timing **Total running time of the script:** (0 minutes 0.076 seconds) .. _sphx_glr_download_api_gallery_graph_theory_eulerian_plot_02_hierholzer_circuit.py: .. only:: html .. container:: sphx-glr-footer sphx-glr-footer-example .. container:: lite-badge .. image:: images/jupyterlite_badge_logo.svg :target: ../../../../lite/lab/index.html?path=api/gallery/graph_theory/eulerian/plot_02_hierholzer_circuit.ipynb :alt: Launch JupyterLite :width: 150 px .. container:: sphx-glr-download sphx-glr-download-jupyter :download:`Download Jupyter notebook: plot_02_hierholzer_circuit.ipynb ` .. container:: sphx-glr-download sphx-glr-download-python :download:`Download Python source code: plot_02_hierholzer_circuit.py ` .. container:: sphx-glr-download sphx-glr-download-zip :download:`Download zipped: plot_02_hierholzer_circuit.zip ` .. only:: html .. rst-class:: sphx-glr-signature `Gallery generated by Sphinx-Gallery `_