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, USAThe drill:
npm install --save incremental-cycle-detectTypings 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:
import * as IncrementalCycleDetect from "incremental-cycle-detect";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 } = require("incremental-cycle-detect");
const graph = GenericGraphAdapter.create();
graph.addEdge(0, 1) // => true
graph.addEdge(1, 2) // => true
graph.addEdge(2, 3) // => true
graph.addEdge(3, 0) // => false because this edge introduces a cycle
// The edge (3,0) was not added.
graph.deleteEdge(2, 3);
graph.addEdge(3, 0) // => 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:
Maps 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.GenericGraphAdapter, but allows for multiple edges between two vertices. Edges are identified by an additional label.Example for using the GraphlibAdapter:
const { Graph } = require("graphlib");
const graph = GraphlibAdapter.create({graphlib: Graph});
graph.addEdge(0, 1) // => trueYou 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.
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) x 38.21 ops/sec ±1.78% (47 runs sampled)
incremental-cycle-detection-multi(insert 15000, RandomSource) x 31.58 ops/sec ±2.77% (52 runs sampled)
graphlib(insert15000, RandomSource) x 0.19 ops/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) x 21.59 ops/sec ±6.63% (37 runs sampled)
Some parts need Map. You can either
Map to the constructor of the graph adapter. This way you don't have to monkey patch:import * as Map from "core-js/es6/map";
const graph = GenericGraphAdapter.create({mapConstructor: Map}):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.
May not to work on Windows.
git clone https://github.com/blutorange/js-incremental-cycle-detect
cd js-incremental-cycle-detection
npm install
npm run buildgit clone https://github.com/blutorange/js-incremental-cycle-detect
cd js-incremental-cycle-detection
npm install
npm run testI 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:
MultiGraphAdapter: #getLabelledEdge() updated incorrectly.#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.MultiGraphAdapter#addLabeledEdge(from: TVertex, to: TVertex, label?: TEdgeLabel, data?: TEdgeData): booleanAlgorithm#findWeaklyConnectedComponents.getEdgesWithData, getEdgesWithDataFrom, getEdgesWithDataTo method when both the edge and its data are needed.clone and map method for creating a copy of a graph.create instead of the constructor. This was necessary for the clone method.getEdgeDataFrom, getEdgeDataTocanAddEdge.getOrder to the graph adapters. It allows you to access the topological order of each vertex.MultiGraphAdapter data structure that allows for multiple edges between two vertices.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.MultiGraphAdapter and fixed some bugs, updated dependencies.Maps each item with the provided mapper function to an iterator, and iterates over all items of these iterators.
Base iterator.
Mapper that maps an item to an iterator.
Generated using TypeDoc
MultiGraphAdapterOptions