Cycle Detection

Find or enumerate cycles in a graph.

Algorithm Complexity When to use

Algorithm	Complexity	When to use
Hawick Circuits	Exponential (use `max_length` to bound)	Enumerate all elementary circuits in a directed multigraph. Handles self-loops and parallel edges. A `hawick_unique_circuits` variant suppresses duplicates induced by parallel edges.
Tiernan All Cycles	Exponential	Earlier algorithm (1970) for enumerating elementary cycles. Companion helpers `tiernan_girth`, `tiernan_circumference`, and `tiernan_girth_and_circumference` return the shortest / longest / both cycle lengths without enumerating every cycle explicitly.
Cycle Ratio / Cycle Mean	Empirical O(\|E\|); no tight worst-case bound	Find the cycle with the minimum or maximum ratio of two edge weight sums (`maximum_cycle_ratio` / `minimum_cycle_ratio`). The `…_cycle_mean` variants are the common special case where the denominator is the cycle length. Used in performance analysis and scheduling.

Exponential (use max_length to bound)

Enumerate all elementary circuits in a directed multigraph. Handles self-loops and parallel edges. A hawick_unique_circuits variant suppresses duplicates induced by parallel edges.

Tiernan All Cycles

Exponential

Earlier algorithm (1970) for enumerating elementary cycles. Companion helpers tiernan_girth, tiernan_circumference, and tiernan_girth_and_circumference return the shortest / longest / both cycle lengths without enumerating every cycle explicitly.

Cycle Ratio / Cycle Mean

Empirical O(|E|); no tight worst-case bound

Find the cycle with the minimum or maximum ratio of two edge weight sums (maximum_cycle_ratio / minimum_cycle_ratio). The …_cycle_mean variants are the common special case where the denominator is the cycle length. Used in performance analysis and scheduling.

To simply detect whether a cycle exists (without enumerating all of them), use depth_first_search with a visitor that checks for back edges. This is O(V + E) and much faster than full enumeration.

Edit this Page