package
find and identify a cycle in a directed graph
npm install find-cycleGitHub-flavored package documentation.
Across all versions.
Download trend unavailable.
Runtime metadata.
Tagged topics.
Estimated unpacked size across 1 packages.
8.8 kB
Includes dependencies.
Searches for a cycle in a directed graph, and tells you the nodes in the
first cycle it finds. Should work on your existing data structures
without conversion, because it operates on Iterables and a
getConnectedNodes adapter function that you provide.
The implementation is a depth-first search using a stack instead of recursion, so it's not limited by the maximum call stack size.
Your environment must support Set, Map, and Symbol.iterator
natively or via a polyfill.
Node: 4+
npm install --save find-cyclefindDirectedCycle(startNodes, getConnectedNodes)const findDirectedCycle = require('find-cycle/directed')startNodes: Iterable<Node>The nodes to start the search from. Your nodes may be of any primitive
or object type besides null or undefined.
getConnectedNodes: (node: Node) => ?(Iterator<Node> | Iterable<Node>)Given a node in your directed graph, return the nodes connected to it as
an Iterator or Iterable. You may return null or undefined if
there are no connected nodes.
?Array<Node>An array of nodes in the first cycle found, if any, including each node in the cycle only once.
const findCycle = require('find-cycle/directed')
const edges = {
1: [2],
2: [3],
3: [4],
4: [2, 5],
5: [3],
7: [8, 9],
8: [1],
9: [10, 11],
10: [11],
11: [9, 8],
}
const findCycle = require('find-cycle/directed'
const edges = new Map([
[1, new Set([2])],
[2, new Set([3])],
[3, new Set([4])],
[4, new Set([2, 5])],
[5, new Set([3])],
[7, new Set([8, 9])],
[8