An implementation of the Johnson's circuit finding algorithm [1].
[1] Donald B. Johnson, Finding all the elementary circuits of a directed graph, SIAM Journal on Computing, 1975.
var findCircuits = require("elementary-circuits-directed-graph");
// V4 V2
// +-<---o---<---o---<--+
// | | |
// o V0 ^ o V3
// | V1| |
// +------>------o--->--+
var adjacencyList = [
[1],
[2, 3],
[4],
[2],
[0]
]
console.log(findCircuits(adjacencyList))
// returns [[0, 1, 2, 4, 0], [0, 1, 3, 2, 4, 0]]
Optionally, one can define a callback to manage the result.
// reusing the same adjacencyList as before
var counter = 0;
function increment() {
counter += 1;
}
findCircuits(adjacencyList, increment);
console.log(counter)
// return 2
This is especially useful if there are too many elementary circuits to store in memory. Using a callback, they can be saved to disk instead.
npm install elementary-circuits-directed-graph
Finds all the elementary circuits of a directed graph using
adjacencyList
is an array of lists representing the directed edges of the graphcallback
is an optional function that will be called each time an elementary circuit is found.
Returns An array of arrays representing the elementary circuits if no callback was defined.
(c) 2018 Antoine Roy-Gobeil. MIT License.