'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 |
|---|
