{"_id":"batching-toposort","_rev":"3-0f8a7e8a3355eb51c70b972f9b05056b","name":"batching-toposort","dist-tags":{"latest":"1.2.0"},"versions":{"1.0.0":{"name":"batching-toposort","version":"1.0.0","description":"Efficiently sort interdependent tasks into a sequence of concurrently-executable batches.","engines":{"node":">=8.0.0"},"main":"dist/index.js","scripts":{"build":"mkdir -p dist && babel src --out-dir dist && npm run prettify","test":"mocha \"./src/**/*.spec.js\"","test-watch":"npm test -- --watch","precommit":"./scripts/precommit && lint-staged","postcommit":"./scripts/postcommit","prepublishOnly":"npm t && npm run build","prettify":"prettier --write \"**/*.{js,jsx,json,css,scss,md}\"","lint":"esw --ext .js,.jsx --ignore-path .gitignore --cache --format node_modules/eslint-formatter-pretty","lint-watch":"npm run lint -- --watch"},"lint-staged":{"*.{js,jsx}":["prettier --write","eslint --fix","git add"],"*.{css,scss,json,md}":["prettier --write","git add"]},"author":{"name":"Gabriel Lebec","email":"glebec@gmail.com","url":"https://github.com/glebec"},"license":"MIT","homepage":"https://github.com/glebec/batching-toposort#readme","repository":{"type":"git","url":"git+https://github.com/glebec/batching-toposort.git"},"bugs":{"url":"https://github.com/glebec/batching-toposort/issues"},"dependencies":{},"devDependencies":{"@babel/cli":"^7.2.3","@babel/core":"^7.3.3","@babel/preset-env":"^7.3.1","babel-eslint":"^8.2.2","chai":"^4.2.0","eslint":"^4.19.1","eslint-config-fullstack":"^5.0.0","eslint-config-prettier":"^2.9.0","eslint-formatter-pretty":"^1.1.0","eslint-plugin-react":"^7.7.0","eslint-watch":"^3.1.0","husky":"^0.13.4","lint-staged":"^7.3.0","mocha":"^6.0.1","prettier":"1.11.1"},"gitHead":"06140011e52293ad7d99447bbf45dc866dc8978f","_id":"batching-toposort@1.0.0","_nodeVersion":"11.6.0","_npmVersion":"6.8.0","_npmUser":{"name":"glebec","email":"glebec@gmail.com"},"dist":{"integrity":"sha512-sVS48Bxft3X6LkK37UtP8VVv8s+/HRvV4S54UWDp3rn8rR+QyO/ujqldiW3Cmg8Q1QHXwaf78jqHq/FD2PJsTQ==","shasum":"6439cb27b31853e09356718f18c86ebe3346f717","tarball":"https://registry.npmjs.org/batching-toposort/-/batching-toposort-1.0.0.tgz","fileCount":7,"unpackedSize":11812,"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v3.0.4\r\nComment: https://openpgpjs.org\r\n\r\nwsFcBAEBCAAQBQJceJ9xCRA9TVsSAnZWagAAnLsQAKLeKbnlKHnaiI9Fw3iF\no/bhdx2yWZGav+/ftUYZaRRdoAUSBSH+L04B7TUmxbG7yKnB2a2fn9qIZUqu\nQvc/2GEPG9rTAHc2KyPaShbn39zxrw+Gg5Kr7RqtGdK/NRccpQ6Zs46O8fBk\ncmCfAIUlGOpBZGEmmpR1j/RXcmWnqQEGPujsuItHpgoZSTDxuZVs9MhODX0I\nU9Gd3ALVYOTfI9bGxWBG9wOlO7Uvkx109rl11cOlZh6/phOjbfI7nNmQJaJq\nkUKEXYisODDAjI+RnzDPH/j+1ratoXvFuobJp9EYO95ye4YDhmRPvoPnxjnT\nkQMDSSwWtmUE1yb9Q44JMb5WGD6ibE26VzXpyCJDmMkly5cP2RkeOGcmbn3b\njmYUoTYS+HuQgANmKbu0+4ntBRAGw0R7ikqs+HupkAYkJnFBawZ1AzDRCe8R\nxCKmi4yu7iVm9NTHkzHInVFAOIOCHJg+XHLravO1+CLB8riq0HbBhNDrIprO\nK5rjvjrp4SClV4xIfZbRDov+SKr/FRIc3EmVM+6mwLxgRFEa++gRLBJlKh1U\nScA7uxL2C14vZcKmMajXvSoMJI/vC1KU9Y/EuBhCPx6K9WwRHrg/5u7RKDcu\n18hsNq4a7RsxBVRO5Uzx3ENeE+AmJg7Yi0uG4v2VE+fPYFIDrkl0Y7dtQtjw\nFHwV\r\n=RrHS\r\n-----END PGP SIGNATURE-----\r\n","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCICrFhteS3F55SzkyUcRZJxjf8Lgsdj065MiFH+fyJD0aAiEAwy1YDcwYguRHDoUYlNpM/2CFvmw5+uFekzyO1b4UR8E="}]},"maintainers":[{"name":"glebec","email":"glebec@gmail.com"}],"directories":{},"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/batching-toposort_1.0.0_1551409009066_0.6834137286642874"},"_hasShrinkwrap":false},"1.1.0":{"name":"batching-toposort","version":"1.1.0","description":"Efficiently sort interdependent tasks into a sequence of concurrently-executable batches.","keywords":["toposort","concurrency","algorithm","dag","digraph","directed acyclic graph","graph","sort"],"engines":{"node":">=8.0.0"},"main":"dist/index.js","scripts":{"build":"mkdir -p dist && babel src --out-dir dist && npm run prettify","test":"mocha \"./src/**/*.spec.js\"","test-watch":"npm test -- --watch","precommit":"./scripts/precommit && lint-staged","postcommit":"./scripts/postcommit","prepublishOnly":"npm t && npm run build","prettify":"prettier --write \"**/*.{js,jsx,json,css,scss,md}\"","lint":"esw --ext .js,.jsx --ignore-path .gitignore --cache --format node_modules/eslint-formatter-pretty","lint-watch":"npm run lint -- --watch"},"lint-staged":{"*.{js,jsx}":["prettier --write","eslint --fix","git add"],"*.{css,scss,json,md}":["prettier --write","git add"]},"author":{"name":"Gabriel Lebec","email":"glebec@gmail.com","url":"https://github.com/glebec"},"license":"MIT","homepage":"https://github.com/glebec/batching-toposort#readme","repository":{"type":"git","url":"git+https://github.com/glebec/batching-toposort.git"},"bugs":{"url":"https://github.com/glebec/batching-toposort/issues"},"dependencies":{},"devDependencies":{"@babel/cli":"^7.2.3","@babel/core":"^7.3.3","@babel/preset-env":"^7.3.1","babel-eslint":"^8.2.2","chai":"^4.2.0","eslint":"^4.19.1","eslint-config-fullstack":"^5.0.0","eslint-config-prettier":"^2.9.0","eslint-formatter-pretty":"^1.1.0","eslint-plugin-react":"^7.7.0","eslint-watch":"^3.1.0","husky":"^0.13.4","lint-staged":"^7.3.0","mocha":"^6.0.1","prettier":"1.11.1"},"gitHead":"339e73cb6216672d9977b02905330053e4fc1d9f","_id":"batching-toposort@1.1.0","_nodeVersion":"11.6.0","_npmVersion":"6.8.0","_npmUser":{"name":"glebec","email":"glebec@gmail.com"},"dist":{"integrity":"sha512-KeyjNbm4nuArmY6dJKa5V5vFOs2BdwwbdLSaCzIVECwapnfgCoqEaH5fHmIS4UKv1Zej+6Qf+Oa3jj+eCA02KA==","shasum":"3e81ca4adf46d79ebe0db9da4416fadd12834736","tarball":"https://registry.npmjs.org/batching-toposort/-/batching-toposort-1.1.0.tgz","fileCount":7,"unpackedSize":12128,"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v3.0.4\r\nComment: https://openpgpjs.org\r\n\r\nwsFcBAEBCAAQBQJceLrRCRA9TVsSAnZWagAAqnUP/2DzrVhMTuo9vTdyGIeE\nCy5lJhk9rwZYrudFZ06Bvw/jHn6HiRJza+McAISLREW7mJjpyZ1UCbdwhHwW\nb724DcnyRBGNgB454/62XBRUNPT01ciG/2EYmxlghiqB5+1uYZFcnN3B0J8C\ni63QOfg+wgnKRVUdsflcNALeVZAhwVeYiId9/DQy2WRNKqZ7l2BokOaRRPmY\n0WZl0D61VxA5AV58EfHWrE98PdUx8HxCIev045Hpx56PPIWp6VHjQ9V9qi1c\noDmvRkU7wrR+X5pDyuFJfT9y8EMMx8dCwuk977jquxXaVyL317gry5F+3Hmc\nUB4TYuiMg+MgcMcLuCs468EdVGe8eqEC1GCUTXkUc8B6VWWFgaC/+SX7I/jK\nR86jbSBHTRXzEGBnml2gEJ8TjH+i4S7+39upOemVPqWQxHhezZBloXf0vQp2\ndoYqD5TSknCZQraWHjxg1tWDX/lEAWuwMCXROkhqmOoCpKhwQMu/W+E6QOFQ\nS0/yss5JBhD9wZdnSzEZfWE2LAyFmLCm76ebWmtw9CLsSn6ijgl4Ojyi4JWd\n3oJ6bd6P+z8V3kleKK/++ju9zR7NSA+PBKqGiuPNFdac9/xYidoAxcV+Coo9\ns3N6vLozxVbqF5jJmWPqX26WphBisHqKjUCZ1T9p444UstmV7PMEq8u62E4H\n97W7\r\n=OoYf\r\n-----END PGP SIGNATURE-----\r\n","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEYCIQDdNEnQlWkNJAWBwcda3E5clpFej9iVS9K1Xq2AGTvwqwIhAISAw00nvJ5P8bALTm66LybZkoEc7KY7cI2wDm4xlcmN"}]},"maintainers":[{"name":"glebec","email":"glebec@gmail.com"}],"directories":{},"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/batching-toposort_1.1.0_1551416016998_0.8418851744701683"},"_hasShrinkwrap":false},"1.2.0":{"name":"batching-toposort","version":"1.2.0","description":"Efficiently sort interdependent tasks into a sequence of concurrently-executable batches.","keywords":["toposort","concurrency","algorithm","dag","digraph","directed acyclic graph","graph","sort"],"engines":{"node":">=8.0.0"},"main":"dist/index.js","scripts":{"build":"mkdir -p dist && babel src --out-dir dist && npm run prettify","test":"mocha \"./src/**/*.spec.js\"","test-watch":"npm test -- --watch","precommit":"./scripts/precommit && lint-staged","postcommit":"./scripts/postcommit","prepublishOnly":"npm t && npm run build","prettify":"prettier --write \"**/*.{js,jsx,json,css,scss,md}\"","lint":"esw --ext .js,.jsx --ignore-path .gitignore --cache --format node_modules/eslint-formatter-pretty","lint-watch":"npm run lint -- --watch"},"lint-staged":{"*.{js,jsx}":["prettier --write","eslint --fix","git add"],"*.{css,scss,json,md}":["prettier --write","git add"]},"author":{"name":"Gabriel Lebec","email":"glebec@gmail.com","url":"https://github.com/glebec"},"license":"MIT","homepage":"https://github.com/glebec/batching-toposort#readme","repository":{"type":"git","url":"git+https://github.com/glebec/batching-toposort.git"},"bugs":{"url":"https://github.com/glebec/batching-toposort/issues"},"dependencies":{},"devDependencies":{"@babel/cli":"^7.2.3","@babel/core":"^7.3.3","@babel/preset-env":"^7.3.1","babel-eslint":"^8.2.2","chai":"^4.2.0","eslint":"^4.19.1","eslint-config-fullstack":"^5.0.0","eslint-config-prettier":"^2.9.0","eslint-formatter-pretty":"^1.1.0","eslint-plugin-react":"^7.7.0","eslint-watch":"^3.1.0","husky":"^0.13.4","jsverify":"^0.8.4","lint-staged":"^7.3.0","mocha":"^6.0.1","prettier":"1.11.1"},"gitHead":"c23f18fdacd2663b686f312047e89e9c40cef424","_id":"batching-toposort@1.2.0","_nodeVersion":"11.6.0","_npmVersion":"6.9.0","_npmUser":{"name":"glebec","email":"glebec@gmail.com"},"dist":{"integrity":"sha512-HDf0OOv00dqYGm+M5tJ121RTzX0sK9fxzBMKXYsuQrY0pKSOJjc5qa0DUtzvCGkgIVf1YON2G1e/MHEdHXVaRQ==","shasum":"3a40e7c31c2e27b950a03ea630d0b8aace4c9821","tarball":"https://registry.npmjs.org/batching-toposort/-/batching-toposort-1.2.0.tgz","fileCount":7,"unpackedSize":16711,"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v3.0.4\r\nComment: https://openpgpjs.org\r\n\r\nwsFcBAEBCAAQBQJcjGN3CRA9TVsSAnZWagAAcNcP/1BZyXuCoBiVT6o92X7k\nRwn0xvyRy0w97Z5DEnAIOG9qRi7iTpaqff5uuU+xBYj3n83nuoXEZc/ZI7DY\n2SAbF8pLmyuoLCU9Hw/F48SwKC3gNFW0Awhi/cYBYrNxSluhOo/BzaFSqN31\n6fsNC6Ipm8xPo0aIsRddwXgZuhVB8Y+MbHlu4pSTTFqicWYOhpC2SmCTTfiu\nx9dYXZ3ohItJcJrivzEYWcfJyHyuqagBy9GeSl58+koPiQe8R6yiA8RbCTO5\n0jq80aoEvHnh0gI/To7QNGngQ660aMycNBHVn/SX7ZWAG3ieuFbBAeO5yovx\nYgCIi0xNnfEMGO7OFolvZXt0Y+MSkj1z2dWmcTsQlbbyQx6ywITk78cZFAgM\nXtOm9kEOgENA5FVqVb1BhIq+6I0Vlt4Up88GJEf0vem/oBB2MPi9dnZJz+R9\nWo55Suf4Ay4jRMSKn0c1Tf0E/IP7Jc3h0j48TswDgZl1nzqq0xHrGY1CdobV\nK+AFuqwm7dV1MEX71+PLG9t4SdH2GE85vYiOXOzGicfB0Dp0HEVNTvbYjqaF\nQOdRKDRdKYG3FmnyPeO0XyU0MOi+0mgciwl9vCpzYk2Orps3KqZoTlqvOU8p\nuJT8G4BGC/mmRJo5TxAz+hm4rGWBzWhzQd1mIuiXgmn0FqxNpMLmsL8jcMrL\n/SDx\r\n=tiZl\r\n-----END PGP SIGNATURE-----\r\n","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIBOf8NfA2p8361yRsQs4NfgqPzLsxrdrHO3AZTYlQIyiAiEAhlpCBpTbwV6tzOkiSEMiBjDpnBG8uLeciQ+JEsSIRSc="}]},"maintainers":[{"name":"glebec","email":"glebec@gmail.com"}],"directories":{},"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/batching-toposort_1.2.0_1552704374749_0.24408078756840723"},"_hasShrinkwrap":false}},"time":{"created":"2019-03-01T02:56:49.065Z","1.0.0":"2019-03-01T02:56:49.201Z","modified":"2022-04-11T17:10:28.904Z","1.1.0":"2019-03-01T04:53:37.152Z","1.2.0":"2019-03-16T02:46:14.906Z"},"maintainers":[{"name":"glebec","email":"glebec@gmail.com"}],"description":"Efficiently sort interdependent tasks into a sequence of concurrently-executable batches.","homepage":"https://github.com/glebec/batching-toposort#readme","repository":{"type":"git","url":"git+https://github.com/glebec/batching-toposort.git"},"author":{"name":"Gabriel Lebec","email":"glebec@gmail.com","url":"https://github.com/glebec"},"bugs":{"url":"https://github.com/glebec/batching-toposort/issues"},"license":"MIT","readme":"# Batching-Toposort\n\n[![npm version](https://img.shields.io/npm/v/batching-toposort.svg?maxAge=3600)](https://www.npmjs.com/package/batching-toposort)\n[![Build Status](https://travis-ci.org/glebec/batching-toposort.svg?branch=master)](https://travis-ci.org/glebec/batching-toposort)\n[![code style: prettier](https://img.shields.io/badge/code_style-prettier-ff69b4.svg)](https://github.com/prettier/prettier)\n\nEfficiently sort interdependent tasks into a sequence of concurrently-executable batches.\n\n```hs\nbatchingToposort :: { DependencyId : [DependentId] } -> [[TaskId]]\n```\n\n*   `O(t + d)` time complexity (for `t` tasks and `d` dependency relationships)\n*   `O(t)` space complexity\n*   Zero package dependencies\n*   Thoroughly tested (including [invariant tests](http://jsverify.github.io/#property-based-testing))\n*   Errors on cyclic graphs\n\n## Motivation\n\nOften one needs to schedule interdependent tasks. In order to determine task order, the classic solution is to use [topological sort](https://en.wikipedia.org/wiki/Topological_sorting). However, toposort typically outputs a list of individual tasks, without grouping those that can be executed concurrently. Batching-Toposort takes this additional consideration into account, producing a list of lists of tasks. The outer list is ordered; each inner list is unordered.\n\n## Usage\n\n```sh\nnpm install batching-toposort\n```\n\n<img width=\"250\" src=\"images/graph.png\">\n\nBatching-Toposort expects a [directed acyclic graph](https://en.wikipedia.org/wiki/Directed_acyclic_graph) (DAG) implemented via [adjacency list](https://en.wikipedia.org/wiki/Adjacency_list). In other words, construct an object whose keys are dependency IDs, and whose values are lists of dependent IDs.\n\n```js\nconst batchingToposort = require('batching-toposort')\n\n// DAG :: { DependencyId : [DependentId] }\nconst DAG = {\n    a: ['c', 'f'], // `a` is a dependency of `c` and `f`\n    b: ['d', 'e'],\n    c: ['f'],\n    d: ['f', 'g'],\n    e: ['h'],\n    f: ['i'],\n    g: ['j'],\n    h: ['j'],\n    i: [],\n    j: [],\n}\n\n// batchingToposort :: DAG -> [[TaskId]]\nconst taskBatches = batchingToposort(DAG)\n// [['a', 'b'], ['c', 'd', 'e'], ['f', 'g', 'h'], ['i', 'j']]\n```\n\n(If there is demand, Batching-Toposort may one day include a small DAG API and/or [DOT](<https://en.wikipedia.org/wiki/DOT_(graph_description_language)>) support for convenience, but as of now it is the developer's role to construct the graph.)\n\n## Implementation\n\nIn short, Batching-Toposort adapts [Kahn's Algorithm](https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm) by inserting each round of root tasks into sublists rather than appending tasks directly to the main output list.\n\nThe classic DAG toposort keeps track of each task's in-degree (number of dependencies). As root tasks (those with no dependencies) are added to the output list, their dependents' in-degree counts are decremented. For a task to become a root, all of its dependencies must have been accounted for. The core algorithm is illustrated below in pseudocode (the actual implementation is in [`src/index.js`](src/index.js)).\n\n```\ngiven G = adjacency list of tasks and dependents (~O(1) lookup):\n\nlet N = map from tasks to in-degree counts (~O(1) lookup / update)\nlet L = [] (empty output list) (~O(1) append)\nlet R1 = list of root tasks (~O(1) addition, ~O(n) iteration)\n\nwhile R1 is nonempty\n    append R1 to L\n    let R2 = [] (empty list for next batch) (~O(1) append)\n    for each task T in R1\n        for each dependent D of T (as per G)\n            decrement in-degree count for D (in N)\n            if D's in-degree (as per N) is 0\n                add D to R2\n    R1 = R2\n\nreturn L\n```\n\n### Performance\n\nThe time complexity is `O(|V| + |E|)` for `V` task vertices and `E` dependency edges.\n\n*   The algorithm loops through rounds of roots, and every task is only a root only once, contributing to `O(|V|)` rounds (worst case is a linked list of tasks).\n*   Each round handles a disjoint set of dependency edges (those rooted in that round's tasks), so the `O(|E|)` handling of all edges is effectively distributed across rounds.\n*   Other operations, e.g. querying a node's in-degree (average case `O(1)`), are carefully managed to preserve the time complexity.\n\nThe space complexity is slightly better at `O(|V|)`.\n\n*   The in-degree map size is proportional to the number of vertices `|V|`, but not edges, as those are folded into an integer count during map construction.\n*   The output by definition contains `|V|` tasks (distributed among as many or fewer lists).\n*   Again, other operations are controlled to keep space complexity low.\n","readmeFilename":"README.md","keywords":["toposort","concurrency","algorithm","dag","digraph","directed acyclic graph","graph","sort"]}