File EulerianCycle.h

↰ Parent directory (ADS/graph)

The Eulerian cycle of an oriented graph (exercise 15.3), a closed path that uses each edge exactly once: by the theorem of Euler it exists if and only if each node has as many edges entering as leaving and all the edges are in one component, the orientation ignored.

Definition (ADS/graph/EulerianCycle.h)

Detailed Description

The book finds it by a local search on the partitions of the edges into closed paths, each edge choosing its successor and a swap of two successors merging two paths; here the algorithm of Hierholzer follows unused edges from a node until it comes back, and splices in the closed paths found from the nodes along the way, in O( n + m ) time.

The contracts [see File Contract.h]: the graph is oriented; at the level of the audits, the cycle found is closed and uses each edge exactly once, which isEulerianCycle() checks. The functions are defined in EulerianCycle.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, exercise 15.3, https://algoritmicamente.it/materiali/libro/capitoli/cap15.pdf

  1. Hierholzer, C. Wiener, Ueber die Moeglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren, Mathematische Annalen 6(1), 30-32, 1873, doi:10.1007/BF01442866

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions