Overview
Johnson's Cycle Enumeration is a cycle enumeration method for simple cycle enumeration. It works by blocking and unblocking vertices to enumerate elementary directed cycles.
ExtendedSource checked
Johnson's Cycle Enumeration
Johnson's Cycle Enumeration addresses simple cycle enumeration by blocking and unblocking vertices to enumerate elementary directed cycles.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Graph Traversal
- Difficulty
- Intermediate
- Family
- Cycle Enumeration
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
simple cycle enumerationcycle enumerationgraph traversal
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(V + E)
Average
O((V + E) log V)
Worst
O(V^2 + E)
Space
O(V + E)
When to Use
- Use Johnson's Cycle Enumeration when solving simple cycle enumeration and you want to benefit from blocking and unblocking vertices to enumerate elementary directed cycles.
- Choose it when O((V + E) log V) average/worst-case time and O(V + E) memory match your workload profile.
- Prefer it over Fleury's Algorithm or Hierholzer's Algorithm when the problem structure favors simple cycle enumeration.
When Not to Use
- Avoid when the graph model does not match the method's direction, weight, or connectivity assumptions.
- Avoid when a simpler traversal gives the same information with less bookkeeping.
What It Does
- Computes simple cycle enumeration within Cycle Enumeration workloads (O((V + E) log V) time, O(V + E) space).
- Works by blocking and unblocking vertices to enumerate elementary directed cycles.
- Maintains key invariants across simple cycle enumeration, cycle enumeration, graph traversal.
Use Cases
- Production and research workloads requiring simple cycle enumeration via blocking and unblocking vertices to enumerate elementary directed cycles.
- Cycle Enumeration pipelines where O((V + E) log V) time and O(V + E) space fit system constraints.
- Engineering comparisons against Fleury's Algorithm and Hierholzer's Algorithm when tuning simple cycle enumeration.
Inputs
- Directed graph G = (V, E)
Outputs
- Complete list of elementary directed cycles without duplicates
Pseudocode
- 1.Construct the graph representation G = (V, E) and initialize auxiliary structures for simple cycle enumeration (cycle enumeration).
- 2.Seed the initial frontier, partition, or residual capacities according to Johnson's Cycle Enumeration's invariants.
- 3.Iteratively process vertices or edges by blocking and unblocking vertices to enumerate elementary directed cycles.
- 4.Maintain structural invariants (simple cycle enumeration, cycle enumeration, graph traversal) and prune or contract resolved subproblems.
- 5.Extract and return the final simple cycle enumeration structure from the converged graph state.
Canonical Example
- Input
- Directed graph G = (V, E) configured for a representative simple cycle enumeration test case
- Output
- Complete list of elementary directed cycles without duplicates satisfying Johnson's Cycle Enumeration invariants
- Explanation
- Johnson's Cycle Enumeration processes the input by blocking and unblocking vertices to enumerate elementary directed cycles, tracking simple cycle enumeration and cycle enumeration to produce the verified simple cycle enumeration result.
Implementation Notes
- Represent vertices and edges explicitly before optimizing storage.
- Keep graph direction, weights, and multiedges clear in tests.
- Record tie-breaking when multiple valid outputs exist.
Common Pitfalls
- Using the method on the wrong graph type, such as directed versus undirected or weighted versus unweighted.
- Forgetting disconnected components or isolated vertices.
- Letting tie-breaking hide nondeterministic output in tests.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow blocking and unblocking vertices to enumerate elementary directed cycles on a small simple cycle enumeration example.
Step 1 of 5: Construct the graph representation G = (V, E) and initialize auxiliary structures for simple cycle enumeration (cycle enumeration).
graph-traversal-mechanismNotes
Johnson's Cycle Enumeration operates in O((V + E) log V) time and O(V + E) space within the Cycle Enumeration family. Often compared with Fleury's Algorithm and Hierholzer's Algorithm.
Sources (1)
What each reference supports for this entry.
Finding All Elementary Circuits
PaperOriginal Johnson reference for enumerating elementary circuits in directed graphs.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Conceptual neighborEuler Tour
Graph Traversal · Core
Johnson's Cycle Enumeration and Euler Tour share a concrete cycle enumeration mechanism for simple cycle enumeration.
Compare with thisRelationships
View full relationship pageConceptual neighborFleury's Algorithm
Johnson's Cycle Enumeration and Fleury's Algorithm share a concrete cycle enumeration mechanism for simple cycle enumeration.
Conceptual neighborHierholzer's Algorithm
Johnson's Cycle Enumeration and Hierholzer's Algorithm share a concrete cycle enumeration mechanism for simple cycle enumeration.
Conceptual neighborEuler Tour
Johnson's Cycle Enumeration and Euler Tour share a concrete cycle enumeration mechanism for simple cycle enumeration.
Related Algorithms
Tags
GraphTraversal