Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Java application to list all cycles in an undirected and directed graph

Sharing is caring!

Problem Statement
Given a graph G = (V, E), list all cycles within G.

Graph

Graph

Algorithm
1. Compute a cycle basis of graph G = (V, E)
* Find a minimal spanning tree (V, E') of G, using Depth-first search (DFS) and its associated set of back edges
* If e in B is a back edge, insert it into the minimal spanning tree’s edges E' to form a set E'' = E' + {e}. The resulting graph (V, E'') has exactly one cycle, which may be constructed by applying a DFS
2. Generate the incidence vector of each cycle in the cycle basis
3. Create all possible combinations of the computed incidence vectors. Let the set of all combinations be C
4. Generate a cycle from each incidence vector in C

The below described algorithm is implemented in CycleUtil.java

Full code
https://github.com/lucaslouca/graph-cycles

References
* Algorithmic Approaches To Circuit Enumeration and Applications
* Cycle basis