Lets you add edges to a directed acyclic graph and be told whether this edge introduces a cycle. If it would, it is not added. Useful when trying to build an acyclic graph.

Based on the paper:

`A Dynamic Topological Sort Algorithm for Directed Acyclic Graphs DAVID J. PEARCE / PAUL H. J. KELLY Journal of Experimental Algorithmics (JEA) Volume 11, 2006, Article No. 1.7 ACM New York, NY, USA`

# Documentation

# Install

The drill:

`npm install --save incremental-cycle-detect`

Typings for Typescript are available (this is written in typescript).

Use the `dist.js`

or `dist.min.js`

for browser usage if you must.

Exposes a global object `window.IncrementalCycleDetect`

with the same methods you can when importing this lib:

`;`

# Usage

The main purpose of this library is to add edges to a directed acyclic graph and be told when that makes the graph cyclic.

`const GenericGraphAdapter = ;const graph = GenericGraphAdapter;graph // => truegraph // => truegraph // => truegraph // => false because this edge introduces a cycle// The edge (3,0) was not added. graph;graph // => true, no cycle because we deleted edge (2,3)`

The main algorithm is implemented by `CycleDetectorImpl`

. To allow for this lib to work with different
graph data structures, its methods take a `GraphAdapter`

object for accessing the graph. You must
called it every time an edge is added or removed, see the docs for GraphAdapter for more details.

For convenience this library also provide a few graph data structures that ready to be used. The following all implement the methods from CommonAdapter:

- GenericGraphAdapter: Uses
`Map`

s to associate data with a vertex, allowing any type of vertex. In the above example, you could use strings, booleans, objects etc. instead of numbers. Seems to perform pretty well. - MultiGraphAdapter Similar to
`GenericGraphAdapter`

, but allows for multiple edges between two vertices. Edges are identified by an additional label. - GraphlibAdapter: For the npm module graphlib. Vertices are strings. Does not support multigraphs currently.

Example for using the GraphlibAdapter:

`const Graph = ;const graph = GraphlibAdapter;graph // => true`

You can add vertices explicitly, but it is not required. They are added if they do not exist.

See the documentation linked above for all methods available.

# Performance

Incremental cycle detection performs better than checking for cycles from scratch every time you add an edge.
Tests done with benchmark. Compared with running a full topological
sort with `graphlib`

(via `alg.isAcyclic(graph)`

) each time a vertex is added. Measured time is the time that
was needed for creating a new graph and adding `n`

vertices, checking for a cycle after each edge insertion.

incremental-cycle-detection(insert 15000, RandomSource) x38.21ops/sec ±1.78% (47 runs sampled)

incremental-cycle-detection-multi(insert 15000, RandomSource) x31.58ops/sec ±2.77% (52 runs sampled)

graphlib(insert15000, RandomSource) x0.19ops/sec ±1.83% (5 runs sampled)

(node v8.9.4, graph with 200 vertices, 15000 random -- same for each algorithm -- edges added)

Also, even inserting into graphlib without checking for cycles seems to be slower:

graphlib-no-cycle-check(insert 15000, RandomSource) x21.59ops/sec ±6.63% (37 runs sampled)

# JavaScript environment

Some parts need `Map`

. You can either

- use this lib in an enviroment that supports these
- polyfill Map
- pass an implementation of
`Map`

to the constructor of the graph adapter. This way you don't have to monkey patch:

`;const graph = GenericGraphAdapter:`

# Use your own graph data structure

As mentioned above, You can also use the CycleDetector (implemented by `PearceKellyDetector`

) directly and
roll your own graph data structure. See the docs.

Essentially, you need to call the `CycleDetector`

every time you add modify the graph. Then it tells you
whether adding an edge is allowed. You can also use an existing `GraphAdapter`

(see above) as the starting point.

# Build

May not to work on Windows.

`git clone https://github.com/blutorange/js-incremental-cycle-detectcd js-incremental-cycle-detectionnpm installnpm run build`

# Test

`git clone https://github.com/blutorange/js-incremental-cycle-detectcd js-incremental-cycle-detectionnpm installnpm run test`

# Change log

I use the following keywords:

`Added`

A new feature that is backwards-compatible.`Changed`

A change that is not backwards-compatible.`Fixed`

A bug or error that was fixed.

From newest to oldest:

# 0.4.0

- Fixed bug with
`MultiGraphAdapter`

:`#getLabelledEdge()`

updated incorrectly. - Added an additional method
`#contractLabeledEdge`

, While`#contractEdge`

contract all edges (irrespective of their label) between two vertices,`#contractEdge`

contracts just one particular edge with a specific label. Note that since cycle are forbidden, a certain labeled edge between two vertices can only be contracted if it is the only edge between those two vertices.`#contractLabeled`

refuses two contract in such a case, while`#contractVertices`

contract all edges. You can check with`#canContractEdge`

and`#canContractLabeledEdge`

. - Removed deprecated
`MultiGraphAdapter#addLabeledEdge(from: TVertex, to: TVertex, label?: TEdgeLabel, data?: TEdgeData): boolean`

# 0.3.0

- Added
`Algorithm#findWeaklyConnectedComponents`

. - Added a
`getEdgesWithData`

,`getEdgesWithDataFrom`

,`getEdgesWithDataTo`

method when both the edge and its data are needed. - Added a
`clone`

and`map`

method for creating a copy of a graph. - Changed the graph adapter implementations so that instances are now created with the factory method
`create`

instead of the constructor. This was necessary for the`clone`

method.

# 0.2.2

- Added two methods for accessing edge data of incoming / outgoing edges:
`getEdgeDataFrom`

,`getEdgeDataTo`

- Added a method for checking whether an edge can be added:
`canAddEdge`

.

# 0.2.1

- Fixed typings for typescript.

# 0.2.0

- Added the method
`getOrder`

to the graph adapters. It allows you to access the topological order of each vertex. - Added a
`MultiGraphAdapter`

data structure that allows for multiple edges between two vertices. - Changed
`GenericGraphAdapter`

, it now only allows for one kind of edge data to be compatible with the`CommonAdapter`

interface. You can use objects if you need to store more data. - Added more test cases for the
`MultiGraphAdapter`

and fixed some bugs, updated dependencies.

# 0.1.1

- 0.1.1 Fixed package.json and dependencies (was missing tslib).

# 0.1.0

- 0.1.0 Initial version.