Have ideas to improve npm?Join in the discussion! »

    find-cycle

    1.0.0 • Public • Published

    find-cycle

    Build Status Coverage Status semantic-release Commitizen friendly

    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([1], 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])

    Install

    npm i find-cycle

    DownloadsWeekly Downloads

    1,494

    Version

    1.0.0

    License

    MIT

    Last publish

    Collaborators

    • avatar