# toposort

> Topological sort of directed ascyclic graphs (like dependecy lists)

Latest version **2.0.2** (published 2018-04-28) · MIT license · 0 weekly downloads

## Install

```sh
npm install toposort
pnpm add toposort
yarn add toposort
bun add toposort
```

## Health

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

Positive: has types package; no vulnerabilities; high quality score.

Warnings: low downloads; no esm support.

Negative: abandoned; low maintenance score.

## Facts

| | |
|---|---|
| Version | 2.0.2 |
| Published | 2018-04-28 |
| First published | 2012-11-02 |
| Weekly downloads | 0 |
| License | MIT |
| TypeScript types | separate (@types/toposort) |
| Module format | CommonJS |
| Dependencies | 0 |
| Unpacked size | 16.3 KB |
| Known vulnerabilities | 0 |
| Install scripts | no |
| GitHub stars | 310 |
| Author | Marcel Klehr |
| Maintainers | marcelklehr |
| Keywords | topological, sort, sorting, graphs, graph, dependency, list, dependencies, acyclic |

## Links

- npm: https://www.npmjs.com/package/toposort
- Repository: https://github.com/marcelklehr/toposort
- Homepage: https://github.com/marcelklehr/toposort#readme
- Issues: https://github.com/marcelklehr/toposort/issues
- npm.io page: https://npm.io/package/toposort

## 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.2 (latest) — 2018-04-28
- 2.0.1 — 2018-04-28
- 1.0.7 — 2018-04-28
- 1.0.6 — 2017-10-02
- 1.0.5 — 2017-10-02
- 1.0.4 — 2017-09-26
- 1.0.3 — 2017-02-14
- 1.0.2 — 2017-01-28
- 1.0.1 — 2017-01-28
- 1.0.0 — 2016-05-13
- 0.2.12 — 2015-08-24
- 0.2.10 — 2013-09-15
- 0.2.9 — 2013-04-10
- 0.2.8 — 2013-02-19
- 0.2.7 — 2013-02-17
- … 7 more at https://npm.io/package/toposort/versions

## README

# Toposort

Sort directed acyclic graphs

[![Build Status](https://travis-ci.org/marcelklehr/toposort.png)](https://travis-ci.org/marcelklehr/toposort)

## Installation

`npm install toposort` or `component install marcelklehr/toposort`  

then in your code:

```js
toposort = require('toposort')
```

## Usage
We want to sort the following graph.

![graph](https://cdn.rawgit.com/marcelklehr/toposort/8b14e9fd/graph.svg)

```js
// First, we define our edges.
var graph = [
  ['put on your shoes', 'tie your shoes']
, ['put on your shirt', 'put on your jacket']
, ['put on your shorts', 'put on your jacket']
, ['put on your shorts', 'put on your shoes']
]


// Now, sort the vertices topologically, to reveal a legal execution order.
toposort(graph)
// [ 'put on your shirt'
// , 'put on your shorts'
// , 'put on your jacket'
// , 'put on your shoes'
// , 'tie your shoes' ]
```

(Note that there is no defined order for graph parts that are not connected
 -- you could also put on your jacket after having tied your shoes...)

### Sorting dependencies
It is usually more convenient to specify *dependencies* instead of "sequences".
```js
// This time, edges represent dependencies.
var graph = [
  ['tie your shoes', 'put on your shoes']
, ['put on your jacket', 'put on your shirt']
, ['put on your shoes', 'put on your shorts']
, ['put on your jacket', 'put on your shorts']
]

toposort(graph) 
// [ 'tie your shoes'
// , 'put on your shoes'
// , 'put on your jacket'
// , 'put on your shirt'
// , 'put on your shorts' ]

// Now, reversing the list will reveal a legal execution order.
toposort(graph).reverse() 
// [ 'put on your shorts'
// , 'put on your shirt'
// , 'put on your jacket'
// , 'put on your shoes'
// , 'tie your shoes' ]
```

## API

### toposort(edges)

+ edges {Array} An array of directed edges describing a graph. An edge looks like this: `[node1, node2]` (vertices needn't be strings but can be of any type).

Returns: {Array} a list of vertices, sorted from "start" to "end"

Throws an error if there are any cycles in the graph.

### toposort.array(nodes, edges)

+ nodes {Array} An array of nodes
+ edges {Array} An array of directed edges. You don't need to mention all `nodes` here.

This is a convenience method that allows you to define nodes that may or may not be connected to any other nodes. The ordering of unconnected nodes is not defined.

Returns: {Array} a list of vertices, sorted from "start" to "end"

Throws an error if there are any cycles in the graph.

## Tests

Run the tests with `node test.js`.

## Legal

MIT License

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