# find-cycle

> find and identify a cycle in a directed graph

Latest version **1.1.0** (published 2023-11-07) · MIT license · 0 weekly downloads

## Install

```sh
npm install find-cycle
pnpm add find-cycle
yarn add find-cycle
bun add find-cycle
```

## Health

**Score 20/100 (F)** — status: abandoned.

Positive: esm support; no vulnerabilities.

Warnings: low downloads; no types.

Negative: abandoned; low maintenance score.

## Facts

| | |
|---|---|
| Version | 1.1.0 |
| Published | 2023-11-07 |
| First published | 2018-01-28 |
| Weekly downloads | 0 |
| License | MIT |
| TypeScript types | none |
| Module format | ESM + CommonJS |
| Node | >=16 |
| Dependencies | 0 |
| Unpacked size | 8.8 KB |
| Known vulnerabilities | 0 |
| Install scripts | no |
| GitHub stars | 16 |
| Author | Andy Edwards |
| Maintainers | jedwards1211 |
| Keywords | cycle, cycles, cyclic, graph, graphs, directed, directed-graph, directed-graphs, find, finder, search, detect, detector, detection |

## Links

- npm: https://www.npmjs.com/package/find-cycle
- Repository: https://github.com/jcoreio/find-cycle
- Homepage: https://github.com/jcoreio/find-cycle#readme
- Issues: https://github.com/jcoreio/find-cycle/issues
- npm.io page: https://npm.io/package/find-cycle

## Alternatives

- [apollo-link-http-common](https://npm.io/package/apollo-link-http-common.md) — 879.0K weekly downloads
- [react-relay](https://npm.io/package/react-relay.md) — 336.8K weekly downloads
- [relay-test-utils](https://npm.io/package/relay-test-utils.md) — 181.6K weekly downloads
- [@vendure/core](https://npm.io/package/@vendure/core.md) — 14.8K weekly downloads
- [@pnpm/deps.graph-sequencer](https://npm.io/package/@pnpm/deps.graph-sequencer.md) — 13.4K weekly downloads

## Recent versions

- 1.1.0 (latest) — 2023-11-07
- 1.0.0 — 2018-01-28

## README

# find-cycle

[![Build Status](https://travis-ci.org/jcoreio/find-cycle.svg?branch=master)](https://travis-ci.org/jcoreio/find-cycle)
[![Coverage Status](https://codecov.io/gh/jcoreio/find-cycle/branch/master/graph/badge.svg)](https://codecov.io/gh/jcoreio/find-cycle)
[![semantic-release](https://img.shields.io/badge/%20%20%F0%9F%93%A6%F0%9F%9A%80-semantic--release-e10079.svg)](https://github.com/semantic-release/semantic-release)
[![Commitizen friendly](https://img.shields.io/badge/commitizen-friendly-brightgreen.svg)](http://commitizen.github.io/cz-cli/)

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

```sh
npm install --save find-cycle
```

# API

## `findDirectedCycle(startNodes, getConnectedNodes)`

```js
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

```js
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

```js
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])
```

---
_Source: https://npm.io/package/find-cycle · Machine-readable twin of the npm.io package page. Health data is recomputed on every publish._