find-cycle

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 = require('find-cycle/directed')

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.

Returns: ?Array<Node>

An array of nodes in the first cycle found, if any, including each node in the cycle only once.

Examples

With Arrays

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 startNodes = [1]
const getConnectedNodes = (node) => edges[node]

expect(findCycle(startNodes, getConnectedNodes)).to.deep.equal([2, 3, 4])

With Sets/Maps

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, new Set([1])],
  [9, new Set([10, 11])],
  [10, new Set([11])],
  [11, new Set([9, 8])],
])

const startNodes = new Set([1])
const getConnectedNodes = node => edges.get(node)

expect(findCycle(startNodes, getConnectedNodes)).to.deep.equal([2, 3, 4])