# elementary-circuits-directed-graph

Finds all elementary circuits of a directed graph using Johnson's algorithm (1975)

## Stats

StarsIssuesVersionUpdatedCreatedSize
elementary-circuits-directed-graph
1.3.13 years ago5 years ago

elementary-circuits-directed-graph
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.``

## Example

``````var findCircuits = require("elementary-circuits-directed-graph");

//       V4      V2
// +-<---o---<---o---<--+
// |             |      |
// o V0          ^      o V3
// |           V1|      |
// +------>------o--->--+

[1],
[2, 3],
[4],
[2],
[0]
]

// 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;
}
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.

## Install

npm install elementary-circuits-directed-graph

## API

### `require("elementary-circuits-directed-graph")(adjacencyList, callback)`

Finds all the elementary circuits of a directed graph using
• `adjacencyList` is an array of lists representing the directed edges of the graph
• `callback` 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.

## Credits

(c) 2018 Antoine Roy-Gobeil. MIT License.