{"_id":"union-find","_rev":"21-11031570bd632f74b5aad7285e26cb93","name":"union-find","description":"A union-find data structure for maintaining disjoint sets.","dist-tags":{"latest":"1.0.2"},"versions":{"0.0.0":{"name":"union-find","version":"0.0.0","description":"A union-find data structure for maintaining disjoint sets.","main":"index.js","repository":{"type":"git","url":"git://github.com/mikolalysenko/union-find.git"},"keywords":["union","find","link","disjoint","set","connected","component","graph"],"author":{"name":"Mikola Lysenko"},"license":"MIT","gitHead":"8fbd75feecd9d7154f4c2ff21754f483ad07ccab","_id":"union-find@0.0.0","dist":{"shasum":"cfb72b5d6fec79485b4b7d88436f15ff4f9f6a95","tarball":"https://registry.npmjs.org/union-find/-/union-find-0.0.0.tgz","integrity":"sha512-OIfUqXLhgsOhEDWRUykWLaL4BSLt8zPVr0/YusAoahrs33hV4/1d3Dpva5d6P6ma0qSsTBbyxd3pIUIhrHK/2A==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIQDSli+mV3hjT9Lw2RQcx1gP1AmyVeUGyJqiSUCyod1rdwIgT4a9PsXSBwklwZvkxM8z6dtdTLgrZP+huh+OktSVXUY="}]},"_npmVersion":"1.1.70","_npmUser":{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"},"maintainers":[{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"}]},"0.0.1":{"name":"union-find","version":"0.0.1","description":"A union-find data structure for maintaining disjoint sets.","main":"index.js","repository":{"type":"git","url":"git://github.com/mikolalysenko/union-find.git"},"keywords":["union","find","link","disjoint","set","connected","component","graph"],"author":{"name":"Mikola Lysenko"},"license":"MIT","gitHead":"8fbd75feecd9d7154f4c2ff21754f483ad07ccab","_id":"union-find@0.0.1","dist":{"shasum":"bc6435721244abb7013fb56745d42eab7d5e9115","tarball":"https://registry.npmjs.org/union-find/-/union-find-0.0.1.tgz","integrity":"sha512-s31tUNjr4ROBLv9WrgwnPTC0bLZqvfKVUVxndrTFl8We1rvgI/VJ4SsqAn7kQO8+t0qoXYwx3KH4Ue+yLeibVA==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEYCIQCdQko/fFWkDQ6z05T4CpSKzclnyXV3xxF92NOGVpu9OQIhAOsQHODb7gttAak0m7dgCqzlkLVWu1XrSy+A/L9r3Poh"}]},"_npmVersion":"1.1.70","_npmUser":{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"},"maintainers":[{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"}]},"0.0.2":{"name":"union-find","version":"0.0.2","description":"A union-find data structure for maintaining disjoint sets.","main":"index.js","repository":{"type":"git","url":"git://github.com/mikolalysenko/union-find.git"},"keywords":["union","find","link","disjoint","set","connected","component","graph"],"author":{"name":"Mikola Lysenko"},"license":"MIT","gitHead":"8fbd75feecd9d7154f4c2ff21754f483ad07ccab","_id":"union-find@0.0.2","dist":{"shasum":"ce72eb4bb4e83b5ca88acdc19325931e70f236e1","tarball":"https://registry.npmjs.org/union-find/-/union-find-0.0.2.tgz","integrity":"sha512-VEX6mBb4aOtAMeRDf6LZp9gDyh6b9/UPB558H4yhXiYl5ZqYvuuKDNZO4mwtzOmSPfei8r3JXCNz5o+prVkmWA==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEMCIGrxn/lYCLLN+yb2vHvRqKX15v2OfJ9v5OMF8BdFyGzNAh9dKrUdJsFtswu/heJKgvvslD6vMUyMljquVi6tnvHc"}]},"_npmVersion":"1.1.70","_npmUser":{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"},"maintainers":[{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"}]},"0.0.3":{"name":"union-find","version":"0.0.3","description":"A union-find data structure for maintaining disjoint sets.","main":"index.js","repository":{"type":"git","url":"git://github.com/mikolalysenko/union-find.git"},"keywords":["union","find","link","disjoint","set","connected","component","graph"],"author":{"name":"Mikola Lysenko"},"license":"MIT","gitHead":"8fbd75feecd9d7154f4c2ff21754f483ad07ccab","_id":"union-find@0.0.3","dist":{"shasum":"c103cbe156050e88dd3c35b32b4d8049be622c74","tarball":"https://registry.npmjs.org/union-find/-/union-find-0.0.3.tgz","integrity":"sha512-cPrg5bpK5BzhMI5HRg0AlEd7b26wVmHiH0LDhIe2S82TUKMcYWBavFIE3em6T4jlKcaj3dmiG67O8CK4QpUYuQ==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIG0FAwpTPxsg6m1/L1fLzQLjtN1q3U7Tw3moxKqarkTWAiEAiKkCF7g6NHt+ELVBMAKVwhcEjewIJm6pTaVhe7KYJi0="}]},"_npmVersion":"1.1.70","_npmUser":{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"},"maintainers":[{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"}]},"0.0.4":{"name":"union-find","version":"0.0.4","description":"A union-find data structure for maintaining disjoint sets.","main":"index.js","repository":{"type":"git","url":"git://github.com/mikolalysenko/union-find.git"},"keywords":["union","find","link","disjoint","set","connected","component","graph"],"author":{"name":"Mikola Lysenko"},"license":"MIT","gitHead":"8fbd75feecd9d7154f4c2ff21754f483ad07ccab","_id":"union-find@0.0.4","dist":{"shasum":"b854b3301619bdad144b0014c78f96eac0d2f0f6","tarball":"https://registry.npmjs.org/union-find/-/union-find-0.0.4.tgz","integrity":"sha512-207oken6EyGDCBK5l/LTPsWfgy8N8s6idwRK2TG0ssWhzPlxEDdBA8nIV+eLbkEMdA8pAwE8F7/xwv2sCESVjQ==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIQDclW/E43amwZT7pk7ZVCDCn93xkr2aM9m1aZbKvcKUOgIgUszmMm1xGwD0SCY0ln8Z1wTrECBzWrdlsZ126cavGU4="}]},"_from":".","_npmVersion":"1.2.14","_npmUser":{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"},"maintainers":[{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"}]},"1.0.0":{"name":"union-find","version":"1.0.0","description":"A union-find data structure for maintaining disjoint sets.","main":"index.js","repository":{"type":"git","url":"git://github.com/mikolalysenko/union-find.git"},"keywords":["union","find","link","disjoint","set","connected","component","graph"],"author":{"name":"Mikola Lysenko"},"license":"MIT","gitHead":"8fbd75feecd9d7154f4c2ff21754f483ad07ccab","bugs":{"url":"https://github.com/mikolalysenko/union-find/issues"},"homepage":"https://github.com/mikolalysenko/union-find","_id":"union-find@1.0.0","dist":{"shasum":"33ef5627fa340c451d000981adfc3391ab613823","tarball":"https://registry.npmjs.org/union-find/-/union-find-1.0.0.tgz","integrity":"sha512-2iQlQlfYCdUtQMvKGOIzVwgD04u/1Ri2HYFFIzpjmQvBdULoEY4ypReLWFU4kEdilnL0prn7lCzFIvnB9mISzA==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIQCCTc0vhn9sebcV+dQFR8iIYOIb1uZcvoQSURJIHqWnDQIgEUVyQSzQp/FT19i8fUOQnLqbZZAo7x4FhYpJu/hR9iA="}]},"_from":".","_npmVersion":"1.4.3","_npmUser":{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"},"maintainers":[{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"}]},"1.0.1":{"name":"union-find","version":"1.0.1","description":"A union-find data structure for maintaining disjoint sets.","main":"index.js","repository":{"type":"git","url":"git://github.com/mikolalysenko/union-find.git"},"keywords":["union","find","link","disjoint","set","connected","component","graph"],"scripts":{"test":"tape test/*.js"},"author":{"name":"Mikola Lysenko"},"license":"MIT","gitHead":"8fbd75feecd9d7154f4c2ff21754f483ad07ccab","devDependencies":{"tape":"^2.12.3"},"bugs":{"url":"https://github.com/mikolalysenko/union-find/issues"},"homepage":"https://github.com/mikolalysenko/union-find","_id":"union-find@1.0.1","dist":{"shasum":"4a5acc669527af6a4fc63af0c73fa7113eb379ca","tarball":"https://registry.npmjs.org/union-find/-/union-find-1.0.1.tgz","integrity":"sha512-cCgOZEoQatLVbCjVluYxHJrYqk7skO4xFi1juJGEZXVCFw8utJc2I5N93J7jXzmLVMizAk3y9bj3VJen4nJV1g==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEQCIFJDyId63Mf+NQARIaNVcw05TWQZ2y/9FcOEyoa8SWHdAiBe42cJKdluVozACQMI+8x08DwmGpCtp0W74INRBGZThw=="}]},"_from":".","_npmVersion":"1.4.3","_npmUser":{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"},"maintainers":[{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"}]},"1.0.2":{"name":"union-find","version":"1.0.2","description":"A union-find data structure for maintaining disjoint sets.","main":"index.js","repository":{"type":"git","url":"git://github.com/mikolalysenko/union-find.git"},"keywords":["union","find","link","disjoint","set","connected","component","graph"],"scripts":{"test":"tape test/*.js"},"author":{"name":"Mikola Lysenko"},"license":"MIT","gitHead":"8fbd75feecd9d7154f4c2ff21754f483ad07ccab","devDependencies":{"tape":"^3.5.0"},"bugs":{"url":"https://github.com/mikolalysenko/union-find/issues"},"homepage":"https://github.com/mikolalysenko/union-find","_id":"union-find@1.0.2","_shasum":"292bac415e6ad3a89535d237010db4a536284e58","_from":".","_npmVersion":"2.1.4","_nodeVersion":"0.10.26","_npmUser":{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"},"maintainers":[{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"}],"dist":{"shasum":"292bac415e6ad3a89535d237010db4a536284e58","tarball":"https://registry.npmjs.org/union-find/-/union-find-1.0.2.tgz","integrity":"sha512-wFA9bMD/40k7ZcpKVXfu6X1qD3ri5ryO8HUsuA1RnxPCQl66Mu6DgkxyR+XNnd+osD0aLENixcJVFj+uf+O4gw==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEQCIC5/nXRbE+0gJioE8tDixDlCiEfjhAu3ksmwzsXYMgFKAiB784+Xpa44uwx5Ouw1K18AiV+OEb8cFKkZLk/pw8HR6A=="}]}}},"readme":"union-find\n==========\n\nA basic union-find data structure for node.js.  For more information, see wikipdia:\n\n[Disjoint Set Datastructures](http://en.wikipedia.org/wiki/Disjoint-set_data_structure)\n\nUnion find data structures solve the incremental connectivity problem. (That is maintaining a spanning forest under incremental insertions of edges.)  To handle fully dynamic connectivity, you can use a [dynamic forest](https://www.npmjs.org/package/dynamic-forest) data structure.\n\nUsage\n=====\nHere is an example showing how to do connected component labelling.  Assume we are given a graph with `VERTEX_COUNT` vertices and a list of edges stored in array represented by pairs of vertex indices:\n\n```javascript\n//Import data structure\nvar UnionFind = require('union-find')\n\nvar VERTEX_COUNT = 8\nvar edges = [\n    [0,1],\n    [1,2],\n    [2,3],\n    [5,6],\n    [7,1]\n]\n\n//Link all the nodes together\nvar forest = new UnionFind(VERTEX_COUNT)\nfor(var i=0; i<edges.length; ++i) {\n  forest.link(edges[i][0], edges[i][1])\n}\n\n//Label components\nvar labels = new Array(VERTEX_COUNT)\nfor(var i=0; i<VERTEX_COUNT; ++i) {\n  labels[i] = forest.find(i)\n}\n```\n\nInstallation\n============\n\n```\nnpm install union-find\n```\n\n# API\n\n```javascript\nvar UnionFind = require('union-find')\n```\n\n## Constructor\n\n### `var forest = new UnionFind(numVertices)`\nCreates a new union-find data structure.\n\n* `numVertices` is the number of vertices in the graph\n\n**Returns** A new union-find data structure\n\n## Methods\n\n### `forest.length`\nReturns the number of vertices in the forest\n\n### `forest.makeSet()`\nCreates a new vertex\n\n**Returns** An integer id for the new vertex\n\n### `forest.find(v)`\nReturns an identifier representing the connected component of any given vertex\n\n**Returns** An integer id representing the connected component of `v`\n\n### `forest.link(s, t)`\nLinks a pair of connected components together\n\n* `s` and `t` are both vertices\n    \nCredits\n=======\n(c) 2013-2014 Mikola Lysenko.  MIT License","maintainers":[{"name":"mikolalysenko","email":"mikolalysenko@gmail.com"}],"time":{"modified":"2022-06-28T04:37:35.172Z","created":"2013-01-12T22:33:09.719Z","0.0.0":"2013-01-12T22:33:10.418Z","0.0.1":"2013-01-18T18:08:49.455Z","0.0.2":"2013-01-21T03:05:56.927Z","0.0.3":"2013-01-21T03:10:44.950Z","0.0.4":"2013-04-01T02:06:13.884Z","1.0.0":"2014-04-29T00:05:14.809Z","1.0.1":"2014-04-29T00:41:55.353Z","1.0.2":"2015-03-12T05:00:10.029Z"},"author":{"name":"Mikola Lysenko"},"repository":{"type":"git","url":"git://github.com/mikolalysenko/union-find.git"},"users":{"luk":true,"denji":true},"homepage":"https://github.com/mikolalysenko/union-find","keywords":["union","find","link","disjoint","set","connected","component","graph"],"bugs":{"url":"https://github.com/mikolalysenko/union-find/issues"},"license":"MIT","readmeFilename":"README.md"}