# simplify-dag

> given a directed acyclic graph, contract straight-line runs to single vertices

Latest version **2.0.1** (published 2015-05-03) · MIT license · 0 weekly downloads

## Install

```sh
npm install simplify-dag
pnpm add simplify-dag
yarn add simplify-dag
bun add simplify-dag
```

## 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.1 |
| Published | 2015-05-03 |
| First published | 2015-04-05 |
| Weekly downloads | 0 |
| License | MIT |
| TypeScript types | none |
| Module format | CommonJS |
| Dependencies | 0 |
| Known vulnerabilities | 0 |
| Install scripts | no |
| Author | Chris Dickinson |
| Maintainers | chrisdickinson |
| Keywords | graph-theory, graph, contract, edges, simplify |

## Links

- npm: https://www.npmjs.com/package/simplify-dag
- Repository: https://github.com/chrisdickinson/contract-graph-edges
- Issues: https://github.com/chrisdickinson/contract-graph-edges/issues
- npm.io page: https://npm.io/package/simplify-dag

## 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.1 (latest) — 2015-05-03
- 2.0.0 — 2015-05-02
- 1.0.3 — 2015-05-02
- 1.0.2 — 2015-04-07
- 1.0.1 — 2015-04-05
- 0.0.0 — 2015-04-05

## README

# simplify-dag

Given a directed acyclic graph, simplify straight-line runs into single vertices.

```javascript
const simplify = require('simplify-dag')
const digraph = require('digraph-tag')

let graph = digraph`
  A -> B
  B -> C
  C -> D
  X -> Y
  Y -> Z
  Z -> D
  D -> U
  U -> V
`

let simplified = simplify(graph) 
/*
   A   X
   ↓   ↓
   B   Y
   ↓   ↓       [A, B, C]   [X, Y, Z]
   C   Z            \___   ___/
    \ /                 \ /
     Y     --->          Y
     ↓                   ↓
     D               [D, U, V]
     ↓
     U
     ↓
     V
*/
```

**Note:** passing a graph with cycles to this module will mostly likely result
in an infinite loop. Be sure to remove cycles from your graph before applying
this module.

## API

##### `Map<Vertex → Set<Edge>> → Edges`

A `Map` from `Vertex` (whatever type you provide) to `Edge` will be defined as `Edges`.

##### `{vertices: Set<Vertex>, outgoing: Edges, incoming: Edges} → Graph`

An object with the properties `vertices`, `outgoing`, and `incoming`, whose types are
`Set<Vertex>` and `Edges` respectively will be known as a `Graph`. Incoming `Edges` will
map a given `Vertex` instance to every incoming `Edge`, and outgoing `Edges` will map `Vertex`
instances to every outgoing `Edge`. `Edge` and `Vertex` types are *user-defined* – that is,
you should provide instructions to this module on how to treat these types.

##### `Array<Vertex> → DerivedVertex`

`DerivedVertex` instances represent straight-line runs of `Vertex` instances from the original
graph. This module will *only* produce `DerivedVertex` instances.

##### `{copyEdge: Function?, {s,g}et{From,To}: Function?}? → Interface`

An `Interface` is defined as an object that optionally defines `copyEdge`, `getFrom`, and
`getTo` properties. 

* `copyEdge` takes the original `Edge` object, and should return a new copy of it.
* `getFrom` takes an `Edge` and returns the source of the edge. If not defined it will treat
edges as 2-element arrays, and attempt to take the first element as the source.
* `getTo` takes an `Edge` and returns the destination of the edge. As above, if not defined
it will treat edges as a 2-element array and return the second element as the destination.
* `setFrom` takes an `Edge` and a `Vertex` and should mutate the `Edge` such
that it originates from the vertex.
* `setTo` takes an `Edge` and a `Vertex` and should mutate the `Edge` such
that it terminates in the vertex.

##### `simplify(vertices: Set<Vertex>, incoming: Edges, `
##### `         outgoing: Edges, interface: Interface) → Graph`

Given a set of vertices, a map from vertex to incoming edges, a map from vertex to outgoing
edges, and optionally an interface for `Vertex` and `Edge` interaction, return a new `Graph`
instance representing a simplified DAG.

## License

MIT

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