New Case Study:See how Anthropic automated 95% of dependency reviews with Socket.Learn More
Socket
Sign inDemoInstall
Socket

find-cycle

Package Overview
Dependencies
Maintainers
1
Versions
2
Alerts
File Explorer

Advanced tools

Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

find-cycle

find and identify a cycle in a directed graph

  • 1.1.0
  • latest
  • Source
  • npm
  • Socket score

Version published
Weekly downloads
2.7K
decreased by-21.9%
Maintainers
1
Weekly downloads
 
Created
Source

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(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])

Keywords

FAQs

Package last updated on 07 Nov 2023

Did you know?

Socket

Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.

Install

Related posts

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

Packages

npm

Stay in touch

Get open source security insights delivered straight into your inbox.


  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc