{"_id":"edmonds-blossom","_rev":"4-1b8372b1bfc27e523e0b39b0b17880c8","name":"edmonds-blossom","description":"Edmond's weighted maximum matching algorithm (Blossom algorithm) ported from http://jorisvr.nl/maximummatching.html","dist-tags":{"latest":"1.0.0"},"versions":{"0.1.0":{"name":"edmonds-blossom","version":"0.1.0","description":"Edmond's weighted maximum matching algorithm (Blossom algorithm) ported from http://jorisvr.nl/maximummatching.html","main":"blossom.js","scripts":{"test":"echo \"Error: no test specified\" && exit 1"},"repository":{"type":"git","url":"git+https://github.com/mattkrick/EdmondsBlossom.git"},"author":"","license":"MIT","bugs":{"url":"https://github.com/mattkrick/EdmondsBlossom/issues"},"homepage":"https://github.com/mattkrick/EdmondsBlossom#readme","dependencies":{"jasmine-node":"^1.14.5"},"gitHead":"b48be039c61e6fa60e88b886422186707d241f5e","_id":"edmonds-blossom@0.1.0","_shasum":"ea062f13c68414fce5813c2a994cb3c1c2cff483","_from":".","_npmVersion":"2.10.1","_nodeVersion":"0.12.4","_npmUser":{"name":"mattkrick","email":"matt.krick@gmail.com"},"dist":{"shasum":"ea062f13c68414fce5813c2a994cb3c1c2cff483","tarball":"https://registry.npmjs.org/edmonds-blossom/-/edmonds-blossom-0.1.0.tgz","integrity":"sha512-64t6kUEuvjhb6Lg8+mX6KsK1rV8Nyo9uykDq5YXa85LmDPt13plND6H43N9cvT6C4AnOmyYWrgWHaWcQuEobcA==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEQCIBqN/cKlcbBixDyO/Andi/ghnoHDZ6C3ORwfsWLfNi52AiBjM+dOSoAcdD+izrLi8dJwMyyXbGAGZUBFwr7y4lA8Jw=="}]},"maintainers":[{"name":"mattkrick","email":"matt.krick@gmail.com"}]},"1.0.0":{"name":"edmonds-blossom","version":"1.0.0","description":"Edmond's weighted maximum matching algorithm (Blossom algorithm) ported from http://jorisvr.nl/maximummatching.html","main":"app/blossom.js","keywords":["graph","directional graph","edmonds","maximum matching","blossom"],"scripts":{"test":"jasmine-node spec"},"repository":{"type":"git","url":"git+https://github.com/mattkrick/EdmondsBlossom.git"},"author":"","license":"MIT","bugs":{"url":"https://github.com/mattkrick/EdmondsBlossom/issues"},"homepage":"https://github.com/mattkrick/EdmondsBlossom#readme","devDependencies":{"jasmine-node":"^1.14.5"},"gitHead":"908190d2e7dbc86c3a8dd43238e7782a2a25f65f","_id":"edmonds-blossom@1.0.0","_shasum":"e937273bd3cbe12710b66846e1e5b5086bdf1f97","_from":".","_npmVersion":"2.10.1","_nodeVersion":"0.12.4","_npmUser":{"name":"mattkrick","email":"matt.krick@gmail.com"},"dist":{"shasum":"e937273bd3cbe12710b66846e1e5b5086bdf1f97","tarball":"https://registry.npmjs.org/edmonds-blossom/-/edmonds-blossom-1.0.0.tgz","integrity":"sha512-wz18RgLg21nW4afc80d080fZuAjiaePfSoHje56aOiH8mO6O5Mc/VAv7s8bCBJkxsks37e0cYTS0dNirsQ4/rg==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEYCIQCNE97vVBUd0Yhx4uT0QT+ONFqKGnxWZRf4pVxSWkw+yQIhAI3aPgkPe543QKQmiLAjeUhOEy8L+ycI77YnAmUjtDkU"}]},"maintainers":[{"name":"mattkrick","email":"matt.krick@gmail.com"}]}},"readme":"# EdmondsBlossom\nEdmond's maximum weighted matching algorithm (Blossom algorithm) in O(n^3)\n\n##Installation\n`npm install edmonds-blossom --save`\n\n##How to use\n```\nvar blossom = require('./edmonds-blossom');\nvar data = [\n      [0, 1, 6],\n      [0, 2, 10],\n      [1, 2, 5]\n    ];\nvar results = blossom(data);\n//results: [2,-1,0];\n```\nThe results are read as follows: index 0 is matchced up with index 2. Index 1 is not used. Index 2 is matched up with index 0 (redundant information).\n###What's the most basic example of a problem that this solves?\nLet's assume I own a store & only sell items in groups of two.\n\n- If I sell a PENCIL and an ERASER, I earn $3\n- If I sell a PENCIL and a MARBLE , I earn $2\n- If I sell a RULER and an ERASER, I earn $2\n\nEach customer is willing to buy up to 1 item of each & I want to maximize profit. Therefore, selling #1 AND #2 is illegal because that would be 2 pencils. #1 AND #3 would is also illegal due to the erasers. So, legal moves are: only #1, only #2, only #3, or #2 AND #3. Since the last option has a profit of $5, I should do that.\n\n\n","maintainers":[{"name":"mattkrick","email":"matt.krick@gmail.com"}],"time":{"modified":"2022-06-16T05:29:01.707Z","created":"2015-09-02T18:40:32.705Z","0.1.0":"2015-09-02T18:40:32.705Z","1.0.0":"2015-09-13T21:35:38.425Z"},"homepage":"https://github.com/mattkrick/EdmondsBlossom#readme","repository":{"type":"git","url":"git+https://github.com/mattkrick/EdmondsBlossom.git"},"bugs":{"url":"https://github.com/mattkrick/EdmondsBlossom/issues"},"license":"MIT","readmeFilename":"README.md","keywords":["graph","directional graph","edmonds","maximum matching","blossom"]}