elementary-circuits-directed-graph

WebJar for elementary-circuits-directed-graph

License

License

MIT
GroupId

GroupId

org.webjars.npm
ArtifactId

ArtifactId

elementary-circuits-directed-graph
Last Version

Last Version

1.2.0
Release Date

Release Date

Type

Type

jar
Description

Description

elementary-circuits-directed-graph
WebJar for elementary-circuits-directed-graph
Project URL

Project URL

https://www.webjars.org
Source Code Management

Source Code Management

https://github.com/antoinerg/elementary-circuits-directed-graph

Download elementary-circuits-directed-graph

How to add to project

<!-- https://jarcasting.com/artifacts/org.webjars.npm/elementary-circuits-directed-graph/ -->
<dependency>
    <groupId>org.webjars.npm</groupId>
    <artifactId>elementary-circuits-directed-graph</artifactId>
    <version>1.2.0</version>
</dependency>
// https://jarcasting.com/artifacts/org.webjars.npm/elementary-circuits-directed-graph/
implementation 'org.webjars.npm:elementary-circuits-directed-graph:1.2.0'
// https://jarcasting.com/artifacts/org.webjars.npm/elementary-circuits-directed-graph/
implementation ("org.webjars.npm:elementary-circuits-directed-graph:1.2.0")
'org.webjars.npm:elementary-circuits-directed-graph:jar:1.2.0'
<dependency org="org.webjars.npm" name="elementary-circuits-directed-graph" rev="1.2.0">
  <artifact name="elementary-circuits-directed-graph" type="jar" />
</dependency>
@Grapes(
@Grab(group='org.webjars.npm', module='elementary-circuits-directed-graph', version='1.2.0')
)
libraryDependencies += "org.webjars.npm" % "elementary-circuits-directed-graph" % "1.2.0"
[org.webjars.npm/elementary-circuits-directed-graph "1.2.0"]

Dependencies

compile (1)

Group / Artifact Type Version
org.webjars.npm : strongly-connected-components jar [1.0.1,2)

Project Modules

There are no modules declared in this project.

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

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.

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.

Versions

Version
1.2.0
1.0.4