How to find all simple cycles in an undirected graph efficiently?

Is there an efficient algorithm to enumerate all the cycles within the Strongly Connected Component of a directed graph?

• What is the most efficient algorithm to decompose a Strongly Connected Component of a directed graph into ALL of the constituent cycles? I solved this in a brute-force manner (Do DFS within the SCC from "every" vertex, find cycles by detecting back-edges incident on the start vertex and at the end remove all duplicate cycles).   [Example] Consider this 4-vertex directed graph represented by the adj-list,   a --> {b, d} b --> {c, d} c --> {a} d --> {a, c}   The 5 output cycles should be,   {a, b, c}, {a, b, d}, {a, d}, {a, d, c}, {a, b, d, c}

• Answer:

  D. B. Johnson, "Finding All the Elementary Circuits of a Directed Graph," SIAM Journal of Computing, 4(1), 1975 pp. 77–84.http://dutta.csc.ncsu.edu/csc791_spring07/wrap/circuits_johnson.pdf. C++ demo /* [Input SCC format] vertex indices start from 0 --- N = number of nodes in the SCC v1 OutDeg(v1) <indices of the vertices adj to v1> v2 OutDeg(v2) <indices of the vertices adj to v2> ... vN OutDeg(vN) <indices of the vertices adj to vN> ---- e.g for 3-vertex complete directed graph the input is 3 0 2 1 2 1 2 0 2 2 2 0 1 [Usage] ./a.out < input.txt */ #include <algorithm> #include <iostream> #include <vector> #include <list> using namespace std; typedef vector< list<size_t> > AdjListT; AdjListT A, B; vector<size_t> node_stack; vector<size_t> blocked; size_t s; void UNBLOCK(size_t); bool CIRCUIT(size_t); void OutputCycle(vector<size_t>&); int main(void) { size_t N, copy_of_N; cin >> N; copy_of_N = N; A.resize(N); blocked.resize(N); B.resize(N); while (N--) { size_t u, v, out_degree; cin >> u >> out_degree; while (out_degree--) { cin >> v; A.at(u).push_back(v); } } N = copy_of_N; for (size_t i = 0; i < N; ++i) blocked[i] = false; s = 0; while (s < N) { CIRCUIT(s); A[s].clear(); for (size_t i = 0; i < N; ++i) A[i].remove(s); for (size_t i = 0; i < N; ++i) { blocked[i] = false; B[i].clear(); } ++s; } return 0; } bool CIRCUIT(size_t v) { bool f = false; node_stack.push_back(v); blocked[v] = true; for (list<size_t>::iterator iw = A[v].begin(); iw != A[v].end(); ++iw) { size_t w = *iw; if (w == s) { OutputCycle(node_stack); f = true; } else if (!blocked[w]) { if (CIRCUIT(w)) f = true; } } if (f) UNBLOCK(v); else for (list<size_t>::iterator iw = A[v].begin(); iw != A[v].end(); ++iw) { size_t w = *iw; if (find(B[w].begin(), B[w].end(), v) == B[w].end()) B[w].push_back(v); } node_stack.pop_back(); return f; } void UNBLOCK(size_t u) { blocked[u] = false; for (list<size_t>::iterator iw = B[u].begin(); iw != B[u].end();) { size_t w = *iw; iw = B[u].erase(iw); if (blocked[w]) UNBLOCK(w); } return; } void OutputCycle(vector<size_t>& node_stack) { for (vector<size_t>::iterator i = node_stack.begin(); i != node_stack.end(); ++i) cout << *i << " "; cout << endl; return; }