{"_id":"tarjan-graph","_rev":"11-6a067d90e08926d1262e6eaf04c3985e","name":"tarjan-graph","description":"[![Build Status](https://travis-ci.org/tmont/tarjan-graph.png)](https://travis-ci.org/tmont/tarjan-graph) [![NPM version](https://img.shields.io/npm/v/tarjan-graph.svg)](https://www.npmjs.com/package/tarjan-graph)","dist-tags":{"latest":"3.0.0"},"versions":{"0.1.0":{"name":"tarjan-graph","version":"0.1.0","scripts":{"test":"mocha -R spec tests"},"devDependencies":{"mocha":"2.3.3","should":"7.1.1"},"gitHead":"31b11b6496b0e72143f7b2534f5ae7a71fbb7858","description":"[![Build Status](https://travis-ci.org/tmont/tarjan-graph.png)](https://travis-ci.org/tmont/tarjan-graph)","_id":"tarjan-graph@0.1.0","_shasum":"5f6327effe6d2fae343226740a2a5c727c794628","_from":".","_npmVersion":"2.14.7","_nodeVersion":"4.2.1","_npmUser":{"name":"tmont","email":"tommy.mont@gmail.com"},"maintainers":[{"name":"tmont","email":"tommy.mont@gmail.com"}],"dist":{"shasum":"5f6327effe6d2fae343226740a2a5c727c794628","tarball":"https://registry.npmjs.org/tarjan-graph/-/tarjan-graph-0.1.0.tgz","integrity":"sha512-P63lCOWQi81CAmgPRHcynY4ltJv7HScSW1CE2d7Qopv1DxmdHgtpDYsynjHVy0WPJaFm4biMmwftptGvO+478g==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIHslTsOzpOV8JAiavfP4Mfxj2DYr2Z3y5iTBS6lHu+H8AiEA7wV5H4F05K14YR868AzkBDzCqNdr1RfbyFnpOHBZ0hE="}]},"directories":{}},"0.1.1":{"name":"tarjan-graph","version":"0.1.1","license":"MIT","scripts":{"test":"mocha -R spec tests"},"files":["index.js"],"devDependencies":{"mocha":"2.3.3","should":"7.1.1"},"gitHead":"53138797c96ea89406fdf232b9de85860e608909","description":"[![Build Status](https://travis-ci.org/tmont/tarjan-graph.png)](https://travis-ci.org/tmont/tarjan-graph)","_id":"tarjan-graph@0.1.1","_shasum":"635d56229d672845c168340142fcfbb6421de409","_from":".","_npmVersion":"2.14.7","_nodeVersion":"4.2.1","_npmUser":{"name":"tmont","email":"tommy.mont@gmail.com"},"maintainers":[{"name":"tmont","email":"tommy.mont@gmail.com"}],"dist":{"shasum":"635d56229d672845c168340142fcfbb6421de409","tarball":"https://registry.npmjs.org/tarjan-graph/-/tarjan-graph-0.1.1.tgz","integrity":"sha512-W+zP9B+lmDcaY7YpVThFt/C1vSia6AIJD6785c8WADZZwtZS/G6aVpI/uuNelzXKZYns/OSk7FLSyXP2X1fkLg==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIE6LR31y2TDdHJEGuULRWkyE43VOWT7RqoxJSJ0SFFEVAiEA+njSioOKy7vr1LaXjkVk5pqIvjZlVA/NB6LZZoOEPtI="}]},"directories":{}},"0.2.0":{"name":"tarjan-graph","version":"0.2.0","license":"MIT","scripts":{"test":"mocha -R spec tests"},"files":["index.js"],"devDependencies":{"mocha":"2.3.3","should":"7.1.1"},"gitHead":"1547059b40d671ea6615663c6213f4bf914303fc","description":"[![Build Status](https://travis-ci.org/tmont/tarjan-graph.png)](https://travis-ci.org/tmont/tarjan-graph)","_id":"tarjan-graph@0.2.0","_shasum":"5110cab0c6342d7023ba1aa4437b0d0ca8a12df5","_from":".","_npmVersion":"2.14.7","_nodeVersion":"4.2.1","_npmUser":{"name":"tmont","email":"tommy.mont@gmail.com"},"maintainers":[{"name":"tmont","email":"tommy.mont@gmail.com"}],"dist":{"shasum":"5110cab0c6342d7023ba1aa4437b0d0ca8a12df5","tarball":"https://registry.npmjs.org/tarjan-graph/-/tarjan-graph-0.2.0.tgz","integrity":"sha512-rP1mpa6SJyzxguKlTf9Np6QrEjIKmDgS4SU1a+7cJxbK+3Z+rXh4q6x+OvENtn2Ve3MF7egtHrtLPJ7eA17j8Q==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEYCIQC4vof88GmqD5hevIha0EnXSjHXEUw0Z4YO4TWXkO05nwIhAKihaeCuYhfnnfl4tvDSdwPPLEzS6A1anCYwPXg0xTVJ"}]},"directories":{}},"0.3.0":{"name":"tarjan-graph","version":"0.3.0","license":"MIT","scripts":{"test":"mocha -R spec tests"},"repository":{"type":"git","url":"git+https://github.com/tmont/tarjan-graph.git"},"files":["index.js"],"devDependencies":{"mocha":"2.3.4","should":"7.1.1"},"gitHead":"ddc05d7eb7952200d4ad73a368443e7746bce9b2","description":"[![Build Status](https://travis-ci.org/tmont/tarjan-graph.png)](https://travis-ci.org/tmont/tarjan-graph)","bugs":{"url":"https://github.com/tmont/tarjan-graph/issues"},"homepage":"https://github.com/tmont/tarjan-graph#readme","_id":"tarjan-graph@0.3.0","_shasum":"cedb7c103500724ec46e6e22f4aba39fd379bb20","_from":".","_npmVersion":"3.3.12","_nodeVersion":"5.1.1","_npmUser":{"name":"tmont","email":"tommy.mont@gmail.com"},"maintainers":[{"name":"tmont","email":"tommy.mont@gmail.com"}],"dist":{"shasum":"cedb7c103500724ec46e6e22f4aba39fd379bb20","tarball":"https://registry.npmjs.org/tarjan-graph/-/tarjan-graph-0.3.0.tgz","integrity":"sha512-ug+53ujkErGHaLK/P5bRV7wxLfl088aXlWwTP+B2P+dVbIUsWiu1gS928m4ml6mxm6cW3LLsey3sc5RKrxdWxA==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIQD6crWDlfn0eofSpRruYNvgD3QDDVuCZ3pr+5/z1B98/AIgH90zBFhquoP6fturyQOTq3VX+eHZua4rSx2aA5pujTM="}]},"directories":{}},"1.0.0":{"name":"tarjan-graph","version":"1.0.0","license":"MIT","scripts":{"test":"mocha -R spec tests"},"repository":{"type":"git","url":"git+https://github.com/tmont/tarjan-graph.git"},"files":["index.js","index.d.ts"],"devDependencies":{"mocha":"4.0.1","should":"13.1.2","typescript":"2.5.3"},"types":"./index.d.ts","gitHead":"0f2045bc89094e61a940cf0ecc822db69ae79d82","description":"[![Build Status](https://travis-ci.org/tmont/tarjan-graph.png)](https://travis-ci.org/tmont/tarjan-graph)","bugs":{"url":"https://github.com/tmont/tarjan-graph/issues"},"homepage":"https://github.com/tmont/tarjan-graph#readme","_id":"tarjan-graph@1.0.0","_npmVersion":"5.3.0","_nodeVersion":"8.6.0","_npmUser":{"name":"tmont","email":"tommy.mont@gmail.com"},"dist":{"integrity":"sha512-ubo0VUODT+QPLFs4WCbTX6/vjymj1SFhp8JOk+HK0oWW5fpK29O0ch9q6JscSPmzTvbbNUEgauoSNjy6WoPm4A==","shasum":"906a69c6e9a916e4b1ee7e2160aba4c3e8d138b3","tarball":"https://registry.npmjs.org/tarjan-graph/-/tarjan-graph-1.0.0.tgz","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIQDz3OV/2G/hvAmK9wTc9czf2ElYWJjXAjab6waZvepNygIgGhFY3jqy4QIiKKQF1lnvu5wszL0u1ywGxBKkEB9ZSac="}]},"maintainers":[{"name":"tmont","email":"tommy.mont@gmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/tarjan-graph-1.0.0.tgz_1508658750954_0.18898554099723697"},"directories":{}},"1.0.1":{"name":"tarjan-graph","version":"1.0.1","license":"MIT","scripts":{"test":"mocha -R spec tests"},"repository":{"type":"git","url":"git+https://github.com/tmont/tarjan-graph.git"},"files":["index.js","index.d.ts"],"devDependencies":{"mocha":"4.0.1","should":"13.1.2","typescript":"2.5.3"},"types":"./index.d.ts","gitHead":"16722ccc01118c2c9fc472e55f190dbb41a89a85","description":"[![Build Status](https://travis-ci.org/tmont/tarjan-graph.png)](https://travis-ci.org/tmont/tarjan-graph) [![NPM version](https://img.shields.io/npm/v/tarjan-graph.svg)](https://www.npmjs.com/package/tarjan-graph)","bugs":{"url":"https://github.com/tmont/tarjan-graph/issues"},"homepage":"https://github.com/tmont/tarjan-graph#readme","_id":"tarjan-graph@1.0.1","_npmVersion":"5.0.3","_nodeVersion":"8.1.4","_npmUser":{"name":"tmont","email":"tommy.mont@gmail.com"},"dist":{"integrity":"sha512-ZoAE3C6+JtwV/aKPAGMNorR3jPj4Ol1raxaNNPVP1jvuM8+rm82KKOUWXSqxsnU5GtLRGVI1rZuttzd/UxLlcg==","shasum":"e80ec1060fe2676aee18877637537b85e40534c3","tarball":"https://registry.npmjs.org/tarjan-graph/-/tarjan-graph-1.0.1.tgz","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIQCaqzVhjZmFI9QWKwyPpt4Cw8P5UgWaLbd9NAgbM3jCnAIganUP+gZOlXWePsA55iW3TaYRLnnxMeHwqB56ZqOPdXs="}]},"maintainers":[{"name":"tmont","email":"tommy.mont@gmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/tarjan-graph-1.0.1.tgz_1513010361476_0.8082521623000503"},"directories":{}},"2.0.0":{"name":"tarjan-graph","version":"2.0.0","license":"MIT","scripts":{"test":"mocha -R spec tests"},"repository":{"type":"git","url":"git+https://github.com/tmont/tarjan-graph.git"},"files":["index.js","index.d.ts"],"devDependencies":{"mocha":"5.2.0","should":"13.2.3","typescript":"3.0.1"},"types":"./index.d.ts","gitHead":"bf8b8e7330efbc6d409b5360f0a300ad921186bb","description":"[![Build Status](https://travis-ci.org/tmont/tarjan-graph.png)](https://travis-ci.org/tmont/tarjan-graph) [![NPM version](https://img.shields.io/npm/v/tarjan-graph.svg)](https://www.npmjs.com/package/tarjan-graph)","bugs":{"url":"https://github.com/tmont/tarjan-graph/issues"},"homepage":"https://github.com/tmont/tarjan-graph#readme","_id":"tarjan-graph@2.0.0","_npmVersion":"5.6.0","_nodeVersion":"8.11.3","_npmUser":{"name":"tmont","email":"tommy.mont@gmail.com"},"dist":{"integrity":"sha512-fDe57nO2Ukw2A/jHwVeiEgERGrGHukf3aHmR/YZ9BrveOtHVlFs289AnVeb1wD2aj9g01ZZ6f7VyMJ2QxI2NBQ==","shasum":"8d8e991f170600982f9b8081984112ea8390b4a3","tarball":"https://registry.npmjs.org/tarjan-graph/-/tarjan-graph-2.0.0.tgz","fileCount":4,"unpackedSize":7207,"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v3.0.4\r\nComment: https://openpgpjs.org\r\n\r\nwsFcBAEBCAAQBQJba7NbCRA9TVsSAnZWagAAQisP/j3C24+sVhgfSwEP5C8A\nxa1KM2y395w7Af2fwC4QxcY9L2iI2VlbvVry0jtmk3bqnZ8rE92g15PaEp9g\nnbWTD9tkgEOkO/9PJATi4dMME4KO9QIWagLEZqvFj5dCZBFNZBubK25SyW3E\nUm+r78CtrwAp91pad2eLsIQ5Yxebg2463RStOvL6VealsRDq3BkObxpr9v1O\nqvqf3Mv2tEq853GhydFe3c4n0mR3EM6KJFJhlg/SmnRl9ktsfbJ9jttlKbO8\n72Gc/ms7o7b5Bwn5bMEwk9zM/1Cpi6Nvb6EtM9GCyxlt9Ntt7KFZoJALcIgn\nHxZTUEQS0nMBudVDytoUWsAzx8oGBvOCEpBvCXV3XffZMcHnruqjg14dXdnE\nSE03T+yBDMJpLJvLGsLN5qsrtAGTtXsvg90mz12cQb8s1AbskhdYb17cNw62\n7ivMI+IEEw9fCDWOsmKTaADpVKLFXSp/wNFXBT0kOh3UfPy5HUYq8k/RCGz7\nhZYN049mtZWwjP+HJW3WwvGtymeWh/Mov6MaEvL36GshktJJHhzuQy1jOW2S\n3/QBX6T6MQC+w6zJP6A0if8uFB7BIM8oH43qB+4mjmKl7Oau2DjPBw8UAXNs\nfLtMg85NETElzMPV0z3om5eAtnyu0x8vqKQKRU5EYVPPOMmKIEHbGgTgXUJs\n1DX1\r\n=yHWI\r\n-----END PGP SIGNATURE-----\r\n","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEQCIDI0qagBkhMbjJRqwkuzAe1Sx+eVzpBYdeNUBZys7EOGAiAr0Lk6eWe7RMobcpe9YHk7cZgyga9ufmu1REucHMzROg=="}]},"maintainers":[{"name":"tmont","email":"tommy.mont@gmail.com"}],"directories":{},"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/tarjan-graph_2.0.0_1533784923003_0.3004692337373964"},"_hasShrinkwrap":false},"3.0.0":{"name":"tarjan-graph","version":"3.0.0","license":"MIT","scripts":{"build":"tsc --project .","test":"mocha -R spec tests"},"repository":{"type":"git","url":"git+https://github.com/tmont/tarjan-graph.git"},"devDependencies":{"@types/node":"16.11.7","mocha":"9.2.0","should":"13.2.3","typescript":"4.5.5"},"types":"./index.d.ts","gitHead":"60cf3280976b19af858d85fd3696ba05274fc3f3","description":"[![Build Status](https://travis-ci.org/tmont/tarjan-graph.png)](https://travis-ci.org/tmont/tarjan-graph) [![NPM version](https://img.shields.io/npm/v/tarjan-graph.svg)](https://www.npmjs.com/package/tarjan-graph)","bugs":{"url":"https://github.com/tmont/tarjan-graph/issues"},"homepage":"https://github.com/tmont/tarjan-graph#readme","_id":"tarjan-graph@3.0.0","_nodeVersion":"16.13.2","_npmVersion":"8.1.2","dist":{"integrity":"sha512-sM1+1ZKnnCtTP9W0DHTMHTlej9buusVHaKiBVecc6tZpBffBeEpE4XdFz7WNs9H1zaYkcgm6MzfyXFxSV2S1rA==","shasum":"6126076d8f83779cbc1594ef25c4bab3ff8b7a28","tarball":"https://registry.npmjs.org/tarjan-graph/-/tarjan-graph-3.0.0.tgz","fileCount":4,"unpackedSize":9729,"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v3.0.13\r\nComment: https://openpgpjs.org\r\n\r\nwsFcBAEBCAAQBQJh+E0JCRA9TVsSAnZWagAAECoQAImijNhqQ4/dOVn9Ggq9\n6zpGE5cyDBpHAEB8g0dwIz53Lhob+ugQV5xfwfRzYspj9H+B7tz4oOU6QmH8\ny9QP0k1kXOOw9zQvIigmHjYSaNCQpMhAbM9lfIfrNXPkM4oH4vAL9tEnll3k\ntsxyqygzrcWWy+XbZ2vYjiH9PBdKL6Ve/3jlNlL82k2hoXL5i0LHd3cSxMsy\nsjE2fPbcb+ddCCzl4GojJ7oUawJikIZ8MJbdRhgkc/E/A5C4vWWnPHpekDI5\nvQmjoQ3+3RotbmTBBUiTTpdXBNjGFUs3iRA4s0RRGTNuBWTjtEBcYq6rpog2\nh4edHQAenKWuxgRGFI2FrV2kufjD8QQgfSqyk13nveLD0R6BoZBcanlf8C7k\nvSETgATWYBUQIWni6+8ZotKv8P6300uBQfYqbRg5weDWjyibOBaSkYBzpquH\nDAUgBMfvsz8XZTwy5IYCxOAtNRxd2eAMOMom6e+5jyxv6K+itmc7aKFWD2+t\nI2QWMfa6Tgf61wg/9J5TNuwEYCAYo/XmjJb0SaKt8rFFyP7pIrXm921lBktS\nbwsku2hJYTLOCMjSIGVYhE1FH2gXhmP4fycYURWtHz0MGpi9/aYhKU4oSwhy\nbqbY6QZ0Nb6NzeV+eVQPQT80G86mX3FNGLu6SF8C0TldLukU/l2D5rTjE5OS\nUPYP\r\n=ujzl\r\n-----END PGP SIGNATURE-----\r\n","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEQCIB4Rcr9VTHzilMxgxuAWah4O1KBk12yxHAvcJmaQNlDtAiBkD3WufcruEOPC2m+8QwKvnbEqD1EnmOIdinZ52xMzGQ=="}]},"_npmUser":{"name":"tmont","email":"accountnpm@tmonticle.com"},"directories":{},"maintainers":[{"name":"tmont","email":"accountnpm@tmonticle.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/tarjan-graph_3.0.0_1643662601215_0.025975894082657547"},"_hasShrinkwrap":false}},"readme":"# tarjan-graph\n\n[![Build Status](https://travis-ci.org/tmont/tarjan-graph.png)](https://travis-ci.org/tmont/tarjan-graph)\n[![NPM version](https://img.shields.io/npm/v/tarjan-graph.svg)](https://www.npmjs.com/package/tarjan-graph)\n\nThis is a simple directed graph lib, mostly just for checking if a\ndirected graph contains a cycle. It uses \n[Tarjan's algorithm](https://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm)\nfor checking if the graph contains a cycle.\n\nThis library also has some very basic [Graphviz](http://www.graphviz.org/) support\nfor visualizing graphs using the [DOT language](http://www.graphviz.org/doc/info/lang.html).\n\n## Installation\nInstall using `npm`:\n\n```\nnpm install tarjan-graph\n```\n\n* Note: as of v1.0.0 this library requires node >= v8.0.0.\n  Use v0.3.0 for node < v8.0.0. \n* Note: as of v3.0.0 this library was ported to TypeScript and the default\n  export changed to get with the times. So now instead of this:\n  ```typescript\n  const Graph = require('tarjan-graph');  // js\n  import Graph = require('tarjan-graph'); // ts\n  ```\n  you now do this:\n  ```typescript\n  const Graph = require('tarjan-graph').default; // js\n  import Graph from 'tarjan-graph';              // ts\n  ```\n\n## Usage\n\nJavaScript:\n```javascript\nconst Graph = require('tarjan-graph').default;\n```\n\nTypeScript:\n```typescript\nimport Graph from 'tarjan-graph';\n```\n\nAll examples use the following graph:\n\n```bash\nnode -e \"\nconst Graph = require('tarjan-graph').default;\n\nconst graph = new Graph()\n  .add('a', ['b', 'c'])\n  .add('b', ['d', 'e'])\n  .add('c', ['b'])\n  .add('d', ['e'])\n  .add('e', ['c'])\n  .add('f', ['c', 'a', 'g'])\n  .add('g', ['h', 'i'])\n  .add('h', ['j'])\n  .add('i', ['j'])\n  .add('j', ['f', 'k'])\n  .add('k', ['k']);\n\nconsole.log(graph.toDot());\n\" | dot -o docs/example-graph.png -Tpng`\n```\n![Dat Graph](./docs/example-graph.png)\n\nDoing stuff with cycles:\n\n```javascript\nconsole.log(graph.hasCycle()); \n//true\nconsole.log(graph.getCycles());\n// [ \n//   [ { name: 'b', successors: [...] }, { name: 'e', ... }, ... ], \n//   ... \n// ]\n\n//use addAndVerify() instead of add() to throw an error when adding\n//an edge would create a cycle\n```\n\nDoing stuff with SCCs:\n\n```javascript\n//same as graph.getCycles() except includes single vertices\nconsole.log(graph.getStronglyConnectedComponents());\n```\n\nSearching:\n\n```javascript\n//depth-first search (pre-order)\ngraph.dfs('g', (v) => {\n  console.log(v.name + ': ' + v.successors.map(w => w.name).join(', '));\n});\n/*\ng: i, h\nh: j\nj: k, f\nf: g, a, c\nc: b\nb: e, d\nd: e\ne: c\na: c, b\nk: k\ni: j\n*/\n\n//retrieve descendants\nconsole.log(graph.getDescendants('a'));\n//[ 'b', 'd', 'e', 'c' ]\n```\n\nAnd of course, dat dot:\n\n```javascript\nconsole.log(graph.toDot());\n/*\ndigraph {\n  subgraph cluster0 {\n    color=red;\n    d; c; e; b;\n  }\n  subgraph cluster1 {\n    color=red;\n    k;\n  }\n  subgraph cluster2 {\n    color=red;\n    h; f; j; i; g;\n  }\n  b -> e\n  b -> d\n  c -> b\n  a -> c\n  a -> b\n  d -> e\n  e -> c\n  g -> i\n  g -> h\n  f -> g\n  f -> a\n  f -> c\n  h -> j\n  i -> j\n  j -> k\n  j -> f\n  k -> k\n}\n*/\n```\n","maintainers":[{"name":"tmont","email":"accountnpm@tmonticle.com"}],"time":{"modified":"2022-06-27T03:56:46.263Z","created":"2015-11-09T00:52:18.613Z","0.1.0":"2015-11-09T00:52:18.613Z","0.1.1":"2015-11-09T00:58:32.361Z","0.2.0":"2015-11-11T06:17:23.885Z","0.3.0":"2015-12-08T04:31:59.153Z","1.0.0":"2017-10-22T07:52:31.014Z","1.0.1":"2017-12-11T16:39:21.538Z","2.0.0":"2018-08-09T03:22:03.136Z","3.0.0":"2022-01-31T20:56:41.347Z"},"readmeFilename":"README.md","license":"MIT","homepage":"https://github.com/tmont/tarjan-graph#readme","repository":{"type":"git","url":"git+https://github.com/tmont/tarjan-graph.git"},"bugs":{"url":"https://github.com/tmont/tarjan-graph/issues"}}