{"_id":"find-cycle","_rev":"2-f5a7ff4da4c828df051d743dcf337add","name":"find-cycle","description":"find and identify a cycle in a directed graph","dist-tags":{"latest":"1.1.0"},"versions":{"1.0.0":{"name":"find-cycle","version":"1.0.0","description":"find and identify a cycle in a directed graph","author":{"name":"Andy Edwards"},"license":"MIT","scripts":{"lint":"eslint *.js test --cache","lint:fix":"eslint --fix *.js test --cache","lint:watch":"esw --watch *.js test --cache","flow":"flow","flow:coverage":"for file in *.js test/**.js; do echo $file; flow coverage $file; done","flow:watch":"flow-watch -e js,js.flow,flowconfig --ignore lib/ --ignore node_modules/ --watch .flowconfig --watch *.js --watch test/","test":"NODE_ENV=production BABEL_ENV=test nyc --reporter=lcov --reporter=text mocha $npm_package_config_mocha","test:watch":"mocha --watch $npm_package_config_mocha","codecov":"nyc report --reporter=text-lcov > coverage.lcov; codecov","commitmsg":"commitlint -e $GIT_PARAMS","precommit":"npm run lint && flow","prepush":"npm test","prepublishOnly":"npm run lint && flow && npm test","open:coverage":"open coverage/lcov-report/index.html","semantic-release":"semantic-release","travis-deploy-once":"travis-deploy-once"},"config":{"mocha":"./test/**/*.js","commitizen":{"path":"cz-conventional-changelog"}},"nyc":{"include":["*.js"],"exclude":["commitlint.config.js"]},"repository":{"type":"git","url":"git+https://github.com/jcoreio/find-cycle.git"},"keywords":["cycle","cycles","cyclic","graph","graphs","directed","directed-graph","directed-graphs","find","finder","search","detect","detector","detection"],"bugs":{"url":"https://github.com/jcoreio/find-cycle/issues"},"homepage":"https://github.com/jcoreio/find-cycle#readme","engines":{"node":">=4.0.0"},"devDependencies":{"@commitlint/cli":"^6.0.2","@commitlint/config-conventional":"^6.0.2","@jedwards1211/eslint-config":"^2.0.0","@jedwards1211/eslint-config-flow":"^1.0.0","chai":"^4.1.2","codecov":"^3.0.0","eslint":"^4.16.0","eslint-plugin-flowtype":"^2.42.0","eslint-watch":"^3.1.3","flow-bin":"^0.64.0","flow-watch":"^1.1.1","husky":"^0.14.3","istanbul":"^0.4.5","mocha":"^5.0.0","nyc":"^11.4.1","semantic-release":"^12.4.1","travis-deploy-once":"^4.3.3"},"gitHead":"9a42fb79472b4c93fb42991217936ade1d39923f","_id":"find-cycle@1.0.0","_npmVersion":"5.6.0","_nodeVersion":"8.9.4","_npmUser":{"name":"jedwards1211","email":"jedwards@fastmail.com"},"dist":{"integrity":"sha512-um47oVzW1wGgkEb1Pbhs/Scb1xYP+RErujOAQCpngJDhG9YHXfOh7HV2l4tFwrNs60XawH4kDul3BvG+ZuTKvQ==","shasum":"9d4a84b853540e121fd7a2bd7fbc4a6d425364b9","tarball":"https://registry.npmjs.org/find-cycle/-/find-cycle-1.0.0.tgz","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEQCIGikUOw31+y6HBVmeSvhpq2FgAd7brTy2cWwDo967WUiAiAggR46l1oLAi1pw/AdlwPfSkCVW/NueWorPzvgqTMgFQ=="}]},"maintainers":[{"name":"jedwards1211","email":"jedwards@fastmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/find-cycle-1.0.0.tgz_1517162268483_0.05275615421123803"},"directories":{}},"1.1.0":{"name":"find-cycle","version":"1.1.0","description":"find and identify a cycle in a directed graph","author":{"name":"Andy Edwards"},"license":"MIT","repository":{"type":"git","url":"git+https://github.com/jcoreio/find-cycle.git"},"keywords":["cycle","cycles","cyclic","graph","graphs","directed","directed-graph","directed-graphs","find","finder","search","detect","detector","detection"],"bugs":{"url":"https://github.com/jcoreio/find-cycle/issues"},"homepage":"https://github.com/jcoreio/find-cycle#readme","engines":{"node":">=16"},"exports":{"./package.json":"./package.json","./*":{"types":"./*.d.ts","default":"./*.js"}},"sideEffects":false,"packageManager":"pnpm@8.3.1","gitHead":"31e74978aa39407375d0f5caea502c29b46b75a7","_id":"find-cycle@1.1.0","_nodeVersion":"20.3.0","_npmVersion":"9.6.7","dist":{"integrity":"sha512-1LLF+8rDHJvT0EDu1xWGqLliIfJ3y/L31pcQhgV9OgZN2gJmebHY5ZHPXkhueucV+RPOD+b+yRAN8xndFap5NA==","shasum":"d22405af3f5b835c7f4cc3aac9f3893ca8929b5e","tarball":"https://registry.npmjs.org/find-cycle/-/find-cycle-1.1.0.tgz","fileCount":7,"unpackedSize":9045,"signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEQCIGZtObxieznRCULF7fBzA2zjJ+mK6Aa4mvK0YUcwJ9ZCAiAXUX0f/gyA8iswOkBxyNhPTLd0H95F0i6cGF4eftGNVQ=="}]},"_npmUser":{"name":"jedwards1211","email":"jedwards@fastmail.com"},"directories":{},"maintainers":[{"name":"jedwards1211","email":"jedwards@fastmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/find-cycle_1.1.0_1699395490543_0.36707014097653645"},"_hasShrinkwrap":false}},"readme":"# find-cycle\n\n[![Build Status](https://travis-ci.org/jcoreio/find-cycle.svg?branch=master)](https://travis-ci.org/jcoreio/find-cycle)\n[![Coverage Status](https://codecov.io/gh/jcoreio/find-cycle/branch/master/graph/badge.svg)](https://codecov.io/gh/jcoreio/find-cycle)\n[![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)\n[![Commitizen friendly](https://img.shields.io/badge/commitizen-friendly-brightgreen.svg)](http://commitizen.github.io/cz-cli/)\n\nSearches for a cycle in a directed graph, and tells you the nodes in the\nfirst cycle it finds. Should work on your existing data structures\nwithout conversion, because it operates on `Iterables` and a\n`getConnectedNodes` adapter function that you provide.\n\nThe implementation is a depth-first search using a stack instead of\nrecursion, so it's not limited by the maximum call stack size.\n\n# Compatibility\n\nYour environment must support `Set`, `Map`, and `Symbol.iterator`\nnatively or via a polyfill.\n\n**Node**: 4+\n\n# Installation\n\n```sh\nnpm install --save find-cycle\n```\n\n# API\n\n## `findDirectedCycle(startNodes, getConnectedNodes)`\n\n```js\nconst findDirectedCycle = require('find-cycle/directed')\n```\n\n### Arguments\n\n#### `startNodes: Iterable<Node>`\n\nThe nodes to start the search from. Your nodes may be of any primitive\nor object type besides `null` or `undefined`.\n\n#### `getConnectedNodes: (node: Node) => ?(Iterator<Node> | Iterable<Node>)`\n\nGiven a node in your directed graph, return the nodes connected to it as\nan `Iterator` or `Iterable`. You may return `null` or `undefined` if\nthere are no connected nodes.\n\n### Returns: `?Array<Node>`\n\nAn array of nodes in the first cycle found, if any, including each node\nin the cycle only once.\n\n## Examples\n\n### With Arrays\n\n```js\nconst findCycle = require('find-cycle/directed')\n\nconst edges = {\n  1: [2],\n  2: [3],\n  3: [4],\n  4: [2, 5],\n  5: [3],\n  7: [8, 9],\n  8: [1],\n  9: [10, 11],\n  10: [11],\n  11: [9, 8],\n}\n\nconst startNodes = [1]\nconst getConnectedNodes = (node) => edges[node]\n\nexpect(findCycle(startNodes, getConnectedNodes)).to.deep.equal([2, 3, 4])\n```\n\n### With Sets/Maps\n\n```js\nconst findCycle = require('find-cycle/directed'\nconst edges = new Map([\n  [1, new Set([2])],\n  [2, new Set([3])],\n  [3, new Set([4])],\n  [4, new Set([2, 5])],\n  [5, new Set([3])],\n  [7, new Set([8, 9])],\n  [8, new Set([1])],\n  [9, new Set([10, 11])],\n  [10, new Set([11])],\n  [11, new Set([9, 8])],\n])\n\nconst startNodes = new Set([1])\nconst getConnectedNodes = node => edges.get(node)\n\nexpect(findCycle(startNodes, getConnectedNodes)).to.deep.equal([2, 3, 4])\n```\n","maintainers":[{"name":"jedwards1211","email":"jedwards@fastmail.com"}],"time":{"modified":"2023-11-07T22:18:11.000Z","created":"2018-01-28T17:57:49.541Z","1.0.0":"2018-01-28T17:57:49.541Z","1.1.0":"2023-11-07T22:18:10.806Z"},"homepage":"https://github.com/jcoreio/find-cycle#readme","keywords":["cycle","cycles","cyclic","graph","graphs","directed","directed-graph","directed-graphs","find","finder","search","detect","detector","detection"],"repository":{"type":"git","url":"git+https://github.com/jcoreio/find-cycle.git"},"author":{"name":"Andy Edwards"},"bugs":{"url":"https://github.com/jcoreio/find-cycle/issues"},"license":"MIT","readmeFilename":"README.md"}