{"_id":"graph-sequencer","_rev":"269681","name":"graph-sequencer","description":"Sort items in a graph using a topological sort while resolving cycles with priority groups","dist-tags":{"latest":"2.0.0"},"maintainers":[{"name":"thejameskyle","email":"me@thejameskyle.com"}],"time":{"modified":"2021-06-03T17:18:04.000Z","created":"2017-12-05T08:00:49.670Z","2.0.0":"2017-12-07T02:09:30.850Z","1.0.0":"2017-12-05T08:00:49.670Z"},"users":{},"author":{"name":"James Kyle","email":"me@thejameskyle.com"},"repository":{"type":"git","url":"git+https://github.com/thejameskyle/graph-sequencer.git"},"versions":{"2.0.0":{"name":"graph-sequencer","version":"2.0.0","description":"Sort items in a graph using a topological sort while resolving cycles with priority groups","main":"index.js","author":{"name":"James Kyle","email":"me@thejameskyle.com"},"repository":{"type":"git","url":"git+https://github.com/thejameskyle/graph-sequencer.git"},"license":"MIT","keywords":["graph","adjacency","list","tasks","priority","priorities","sort","dependencies","topological","topo","sequencer"],"files":["index.js"],"scripts":{"test":"ava test.js"},"dependencies":{"array-flatten":"^2.1.1","array-includes":"^3.0.3"},"devDependencies":{"ava":"^0.24.0","flow-bin":"^0.60.1"},"gitHead":"565c024a02a1e3b83758149a2fd4eeb24753a898","bugs":{"url":"https://github.com/thejameskyle/graph-sequencer/issues"},"homepage":"https://github.com/thejameskyle/graph-sequencer#readme","_id":"graph-sequencer@2.0.0","_shasum":"bfb809b8af584f6f5287cdce507a30d4aea6ee70","_from":".","_npmVersion":"2.15.11","_nodeVersion":"4.8.4","_npmUser":{"name":"thejameskyle","email":"me@thejameskyle.com"},"dist":{"shasum":"bfb809b8af584f6f5287cdce507a30d4aea6ee70","size":4522,"noattachment":false,"key":"/graph-sequencer/-/graph-sequencer-2.0.0.tgz","tarball":"http://registry.cnpm.dingdandao.com/graph-sequencer/download/graph-sequencer-2.0.0.tgz"},"maintainers":[{"name":"thejameskyle","email":"me@thejameskyle.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/graph-sequencer-2.0.0.tgz_1512612570792_0.28757167397998273"},"directories":{},"publish_time":1512612570850,"_hasShrinkwrap":false,"_cnpm_publish_time":1512612570850},"1.0.0":{"name":"graph-sequencer","version":"1.0.0","description":"Sort items in a graph using a topological sort while resolving cycles with priority groups","main":"index.js","author":{"name":"James Kyle","email":"me@thejameskyle.com"},"repository":{"type":"git","url":"git+https://github.com/thejameskyle/graph-sequencer.git"},"license":"MIT","keywords":["graph","adjacency","list","tasks","priority","priorities","sort","dependencies","topological","topo","sequencer"],"files":["index.js"],"scripts":{"test":"ava test.js"},"dependencies":{"array-flatten":"^2.1.1"},"devDependencies":{"ava":"^0.24.0","flow-bin":"^0.60.1"},"gitHead":"c6c5a786d6308a24c29358c09a3c71b686240407","bugs":{"url":"https://github.com/thejameskyle/graph-sequencer/issues"},"homepage":"https://github.com/thejameskyle/graph-sequencer#readme","_id":"graph-sequencer@1.0.0","_npmVersion":"5.3.0","_nodeVersion":"8.4.0","_npmUser":{"name":"thejameskyle","email":"me@thejameskyle.com"},"dist":{"shasum":"d884ca904aabad776009855bd3b1d1bb4771a2ec","size":4395,"noattachment":false,"key":"/graph-sequencer/-/graph-sequencer-1.0.0.tgz","tarball":"http://registry.cnpm.dingdandao.com/graph-sequencer/download/graph-sequencer-1.0.0.tgz"},"maintainers":[{"name":"thejameskyle","email":"me@thejameskyle.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/graph-sequencer-1.0.0.tgz_1512460849614_0.7366834972053766"},"directories":{},"publish_time":1512460849670,"_hasShrinkwrap":false,"_cnpm_publish_time":1512460849670}},"readme":"# graph-sequencer\n\n> Sort items in a graph using a topological sort while resolving cycles with\n> priority groups.\n\nSay you have some sort of graph of dependencies: (using an adjacency list)\n\n```js\nlet graph = new Map([\n  [\"task-a\", [\"task-d\"]], // task-a depends on task-d\n  [\"task-b\", [\"task-d\", \"task-a\"]],\n  [\"task-c\", [\"task-d\"]],\n  [\"task-d\", [\"task-a\"]],\n]);\n```\n\nYou could run a topological sort on these items, but you'd still end up with\ncycles:\n\n```\ntask-a -> task-d -> task-a\n```\n\nTo resolve this you pass \"priority groups\" to `graph-sequencer`:\n\n```js\nlet groups = [\n  [\"task-d\"], // higher priority\n  [\"task-a\", \"task-b\", \"task-c\"], // lower priority\n];\n```\n\nThe result will be a chunked list of items sorted topologically and by the\npriority groups:\n\n```js\nlet chunks = [\n  [\"task-d\"],\n  [\"task-a\", \"task-c\"],\n  [\"task-b\"]\n];\n```\n\nYou can then run all these items in order with maximum concurrency:\n\n```js\nfor (let chunk of chunks) {\n  await Promise.all(chunk.map(task => exec(task)));\n}\n```\n\nHowever, even with priority groups you can still accidentally create cycles of\ndependencies in your graph.\n\n`graph-sequencer` will return a list of the unresolved cycles:\n\n```js\nlet cycles = [\n  [\"task-a\", \"task-b\"] // task-a depends on task-b which depends on task-a\n];\n```\n\nHowever, `graph-sequencer` will still return an \"unsafe\" set of chunks. When it\ncomes across a cycle, it will add another chunk with the item with the fewest\ndependencies remaining which will often break cycles.\n\n\nAll together that looks like this:\n\n```js\nconst graphSequencer = require('graph-sequencer');\n\ngraphSequencer({\n  graph: new Map([\n    [\"task-a\", [\"task-d\"]], // task-a depends on task-d\n    [\"task-b\", [\"task-d\", \"task-a\"]],\n    [\"task-c\", [\"task-d\"]],\n    [\"task-d\", [\"task-a\"]],\n  ]);\n  groups: [\n    [\"task-d\"], // higher priority\n    [\"task-a\", \"task-b\", \"task-c\"], // lower priority\n  ],\n})\n// {\n//   safe: true,\n//   chunks: [[\"task-d\"], [\"task-a\", \"task-c\"], [\"task-b\"]],\n//   cycles: [],\n// }\n```\n","_attachments":{},"homepage":"https://github.com/thejameskyle/graph-sequencer#readme","bugs":{"url":"https://github.com/thejameskyle/graph-sequencer/issues"},"license":"MIT"}