find-cycle
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.
Compatibility
Your environment must support Set
, Map
, and Symbol.iterator
natively or via a polyfill.
Node: 4+
Installation
npm install --save find-cycle
API
findDirectedCycle(startNodes, getConnectedNodes)
const findDirectedCycle =
Arguments
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>
Returns: An array of nodes in the first cycle found, if any, including each node in the cycle only once.
Examples
With Arrays
const findCycle = 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 startNodes = 1const getConnectedNodes = edgesnode todeep
With Sets/Maps
const findCycle =