# graph-sequencer

> Sort items in a graph using a topological sort while resolving cycles with priority groups

Latest version **2.0.0** (published 2017-12-07) · MIT license · 0 weekly downloads

## Install

```sh
npm install graph-sequencer
pnpm add graph-sequencer
yarn add graph-sequencer
bun add graph-sequencer
```

## Health

**Score 15/100 (F)** — status: abandoned.

Positive: no vulnerabilities.

Warnings: low downloads; no types; no esm support.

Negative: abandoned; low maintenance score.

## Facts

| | |
|---|---|
| Version | 2.0.0 |
| Published | 2017-12-07 |
| First published | 2017-12-05 |
| Weekly downloads | 0 |
| License | MIT |
| TypeScript types | none |
| Module format | CommonJS |
| Dependencies | 2 |
| Known vulnerabilities | 0 |
| Install scripts | no |
| Author | James Kyle |
| Maintainers | thejameskyle |
| Keywords | graph, adjacency, list, tasks, priority, priorities, sort, dependencies, topological, topo, sequencer |

## Links

- npm: https://www.npmjs.com/package/graph-sequencer
- Repository: https://github.com/thejameskyle/graph-sequencer
- Homepage: https://github.com/thejameskyle/graph-sequencer#readme
- Issues: https://github.com/thejameskyle/graph-sequencer/issues
- npm.io page: https://npm.io/package/graph-sequencer

## Dependencies (2)

- [array-flatten](https://npm.io/package/array-flatten.md) ^2.1.1
- [array-includes](https://npm.io/package/array-includes.md) ^3.0.3

## Alternatives

- [apollo-link-http-common](https://npm.io/package/apollo-link-http-common.md) — 879.0K weekly downloads
- [react-relay](https://npm.io/package/react-relay.md) — 336.8K weekly downloads
- [relay-test-utils](https://npm.io/package/relay-test-utils.md) — 181.6K weekly downloads
- [@vendure/core](https://npm.io/package/@vendure/core.md) — 14.8K weekly downloads
- [@pnpm/deps.graph-sequencer](https://npm.io/package/@pnpm/deps.graph-sequencer.md) — 13.4K weekly downloads

## Recent versions

- 2.0.0 (latest) — 2017-12-07
- 1.0.0 — 2017-12-05

## README

# graph-sequencer

> Sort items in a graph using a topological sort while resolving cycles with
> priority groups.

Say you have some sort of graph of dependencies: (using an adjacency list)

```js
let graph = new Map([
  ["task-a", ["task-d"]], // task-a depends on task-d
  ["task-b", ["task-d", "task-a"]],
  ["task-c", ["task-d"]],
  ["task-d", ["task-a"]],
]);
```

You could run a topological sort on these items, but you'd still end up with
cycles:

```
task-a -> task-d -> task-a
```

To resolve this you pass "priority groups" to `graph-sequencer`:

```js
let groups = [
  ["task-d"], // higher priority
  ["task-a", "task-b", "task-c"], // lower priority
];
```

The result will be a chunked list of items sorted topologically and by the
priority groups:

```js
let chunks = [
  ["task-d"],
  ["task-a", "task-c"],
  ["task-b"]
];
```

You can then run all these items in order with maximum concurrency:

```js
for (let chunk of chunks) {
  await Promise.all(chunk.map(task => exec(task)));
}
```

However, even with priority groups you can still accidentally create cycles of
dependencies in your graph.

`graph-sequencer` will return a list of the unresolved cycles:

```js
let cycles = [
  ["task-a", "task-b"] // task-a depends on task-b which depends on task-a
];
```

However, `graph-sequencer` will still return an "unsafe" set of chunks. When it
comes across a cycle, it will add another chunk with the item with the fewest
dependencies remaining which will often break cycles.


All together that looks like this:

```js
const graphSequencer = require('graph-sequencer');

graphSequencer({
  graph: new Map([
    ["task-a", ["task-d"]], // task-a depends on task-d
    ["task-b", ["task-d", "task-a"]],
    ["task-c", ["task-d"]],
    ["task-d", ["task-a"]],
  ]);
  groups: [
    ["task-d"], // higher priority
    ["task-a", "task-b", "task-c"], // lower priority
  ],
})
// {
//   safe: true,
//   chunks: [["task-d"], ["task-a", "task-c"], ["task-b"]],
//   cycles: [],
// }
```

---
_Source: https://npm.io/package/graph-sequencer · Machine-readable twin of the npm.io package page. Health data is recomputed on every publish._