'How to collect all Eulerian cycles/circuits in a directed graph?

According to this post, we have a pseudo-function which can check if a Eulerian circuit exists in a directed graph.

// @flow

const { Edge, Graph, Path, Node } = require("./Graph.js");

/**
* Given a graph, returns any circuit from it, remove the edges from it.
*/
function find_circuit(graph: Graph, initialVertex: number) {
  let vertex = initialVertex;
  const path = new Path();
  path.append(vertex);

  while (true) {
    // Get the next vertex
    const edge = graph.getNextEdgeForVertex(vertex);

    if (edge == null) {
      throw new Error("This graph is not Eulerian");
    }
    const nextVertex = edge.getTheOtherVertex(vertex);

    graph.deleteEdge(edge);
    vertex = nextVertex;

    path.append(vertex);

    // Circuit closed
    if (nextVertex === initialVertex) {
      break;
    }
  }

  // Search for sub-circuits
  for (vertex of path.getContentAsArray()) {
    // Since the vertex was added, its edges could have been removed
    if (graph.getDegree(vertex) === 0) {
      continue;
    }
    let subPath = find_circuit(graph, vertex);
    // Merge sub-path into path
    path.insertAtVertex(vertex, subPath);
  }

  return path;
}

function eulerian_circuit(initialGraph: Graph): Path {
  // Clone because we'll mutate it
  const graph = initialGraph.clone();
  return find_circuit(graph, 0);
}

It seems to find and return just one arbitrary cycle. How do you find all Eulerian circuits/cycles in a directed graph? It is said to use the BEST theorem, but I am not sure how to apply that.

Basically I would like to use the Eulerian cycles to find all de Bruijn sequences of a certain size, so I would construct a directed graph out of binary numbers by taking a_{1}..a_{n} to b_{0}..b_{n-1} and checking if they are equal, to build the directed edges. All I am asking for here is how to find and return all Eulerian cycles in a directed graph, from there I can plug it into this to find the de Bruijn sequences. Ideally the algorithm would be non-recursive (i.e. iterative), and be somewhat efficient, though definitely doesn't need to be perfect. Just something that actually runs and doesn't hang at small number of cycles.



Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source