Socket
Socket
Sign inDemoInstall

incremental-cycle-detect

Package Overview
Dependencies
Maintainers
1
Versions
7
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

incremental-cycle-detect - npm Package Compare versions

Comparing version 0.1.1 to 0.2.0

dist/index.js
dist/src/GenericGraphAdapter.js
dist/src/GraphlibAdapter.js
dist/src/MultiGraphAdapter.js
dist/src/util.js

763

dist/browser.js

@@ -5,94 +5,166 @@ (function(f){if(typeof exports==="object"&&typeof module!=="undefined"){module.exports=f()}else if(typeof define==="function"&&define.amd){define([],f)}else{var g;if(typeof window!=="undefined"){g=window}else if(typeof global!=="undefined"){g=global}else if(typeof self!=="undefined"){g=self}else{g=this}g.IncrementalCycleDetect = f()}})(function(){var define,module,exports;return (function(){function r(e,n,t){function o(i,f){if(!n[i]){if(!e[i]){var c="function"==typeof require&&require;if(!f&&c)return c(i,!0);if(u)return u(i,!0);var a=new Error("Cannot find module '"+i+"'");throw a.code="MODULE_NOT_FOUND",a}var p=n[i]={exports:{}};e[i][0].call(p.exports,function(r){var n=e[i][1][r];return o(n||r)},p,p.exports,r,e,n,t)}return n[i].exports}for(var u="function"==typeof require&&require,i=0;i<t.length;i++)o(t[i]);return o}return r})()({1:[function(require,module,exports){

var tslib_1 = require("tslib");
tslib_1.__exportStar(require("./src/GraphAdapter"), exports);
tslib_1.__exportStar(require("./src/GraphlibAdapter"), exports);
tslib_1.__exportStar(require("./src/GenericGraphAdapter"), exports);
tslib_1.__exportStar(require("./src/MultiGraphAdapter"), exports);
tslib_1.__exportStar(require("./src/PearceKellyDetector"), exports);
},{"./src/GraphAdapter":2,"./src/PearceKellyDetector":3,"tslib":4}],2:[function(require,module,exports){
},{"./src/GenericGraphAdapter":2,"./src/GraphlibAdapter":3,"./src/MultiGraphAdapter":4,"./src/PearceKellyDetector":5,"tslib":7}],2:[function(require,module,exports){
"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
var PearceKellyDetector_1 = require("./PearceKellyDetector");
var DoneIteratorResult = {
done: true,
value: undefined,
};
var EmptyIterator = {
next: function () {
return DoneIteratorResult;
var util_1 = require("./util");
var GenericGraphAdapter = (function () {
function GenericGraphAdapter(options) {
if (options === void 0) { options = {}; }
var mapConstructor = options.mapConstructor || Map;
this.detector = options.cycleDetector || new PearceKellyDetector_1.PearceKellyDetector();
this.forward = new mapConstructor();
this.backward = new mapConstructor();
this.mapConstructor = mapConstructor;
this.vertices = new mapConstructor();
this.edgeCount = 0;
this.adapter = {
getData: this.getData.bind(this),
getPredecessorsOf: this.getPredecessorsOf.bind(this),
getSuccessorsOf: this.getSuccessorsOf.bind(this),
};
}
};
var hasOwnProperty = Object.prototype.hasOwnProperty;
function assign(target, source) {
for (var key in source) {
if (hasOwnProperty.call(source, key)) {
target[key] = source[key];
GenericGraphAdapter.prototype.canContractEdge = function (from, to) {
return util_1.canContractEdge(this, from, to);
};
GenericGraphAdapter.prototype.contractEdge = function (from, to, vertexMerger, edgeMerger) {
return util_1.contractEdge(this, from, to, vertexMerger, edgeMerger);
};
GenericGraphAdapter.prototype.isReachable = function (source, target) {
return this.detector.isReachable(this.adapter, source, target);
};
GenericGraphAdapter.prototype.getSuccessorsOf = function (vertex) {
var f = this.forward.get(vertex);
if (f === undefined) {
return util_1.EmptyIterator;
}
}
return target;
}
function createArrayIterator(arr) {
var i = 0;
return {
next: function () {
while (arr[i] === undefined) {
if (i > arr.length) {
return DoneIteratorResult;
}
i += 1;
}
return {
done: false,
value: arr[i++],
};
return f.keys();
};
GenericGraphAdapter.prototype.getPredecessorsOf = function (vertex) {
var b = this.backward.get(vertex);
if (b === undefined) {
return util_1.EmptyIterator;
}
return b.keys();
};
}
function createMappedArrayIterator(arr, mapFn) {
var i = 0;
return {
next: function () {
while (arr[i] === undefined) {
if (i > arr.length) {
return DoneIteratorResult;
}
i += 1;
GenericGraphAdapter.prototype.getVertices = function () {
return this.vertices.keys();
};
GenericGraphAdapter.prototype.getEdgeData = function (from, to) {
var map = this.forward.get(from);
if (!map) {
return undefined;
}
return map.get(to);
};
GenericGraphAdapter.prototype.setEdgeData = function (from, to, data) {
var map = this.forward.get(from);
if (!map || !map.has(to)) {
return false;
}
map.set(to, data);
return true;
};
GenericGraphAdapter.prototype.getEdges = function () {
return util_1.createFlatMappedIterator(this.forward.entries(), function (entry) {
return util_1.createMappedIterator(entry[1].keys(), function (key) { return [entry[0], key]; });
});
};
GenericGraphAdapter.prototype.getEdgeCount = function () {
return this.edgeCount;
};
GenericGraphAdapter.prototype.supportsOrder = function () {
return this.detector.supportsOrder();
};
GenericGraphAdapter.prototype.getOrder = function (vertex) {
return this.detector.getOrder(this.adapter, vertex);
};
GenericGraphAdapter.prototype.getVertexCount = function () {
return this.vertices.size;
};
GenericGraphAdapter.prototype.hasEdge = function (from, to) {
var f = this.forward.get(from);
return f ? f.has(to) : false;
};
GenericGraphAdapter.prototype.hasVertex = function (vertex) {
return this.vertices.has(vertex);
};
GenericGraphAdapter.prototype.addEdge = function (from, to, edgeData) {
var f = this.forward.get(from);
var b = this.backward.get(to);
var didNotHaveFrom = this.addVertex(from);
var didNotHaveTo = this.addVertex(to);
if (!f) {
this.forward.set(from, f = new this.mapConstructor());
}
if (!b) {
this.backward.set(to, b = new this.mapConstructor());
}
if (f.has(to) || !this.detector.canAddEdge(this.adapter, from, to)) {
if (didNotHaveFrom) {
this.deleteVertex(from);
}
return {
done: false,
value: mapFn(arr[i++]),
};
if (didNotHaveTo) {
this.deleteVertex(to);
}
return false;
}
f.set(to, edgeData);
b.set(from, true);
this.edgeCount += 1;
return true;
};
}
function contractEdge(adapter, from, to) {
if (!adapter.hasEdge(from, to)) {
return false;
}
adapter.deleteEdge(from, to);
if (adapter.isReachable(from, to)) {
adapter.addEdge(from, to);
return false;
}
var succ = [];
var pred = [];
for (var it_1 = adapter.getSuccessorsOf(to), res = it_1.next(); !res.done; res = it_1.next()) {
adapter.deleteEdge(to, res.value);
succ.push(res.value);
}
for (var it_2 = adapter.getPredecessorsOf(to), res = it_2.next(); !res.done; res = it_2.next()) {
adapter.deleteEdge(res.value, to);
pred.push(res.value);
}
for (var _i = 0, succ_1 = succ; _i < succ_1.length; _i++) {
var node = succ_1[_i];
adapter.addEdge(from, node);
}
for (var _a = 0, pred_1 = pred; _a < pred_1.length; _a++) {
var node = pred_1[_a];
adapter.addEdge(node, from);
}
adapter.deleteVertex(to);
return true;
}
GenericGraphAdapter.prototype.addVertex = function (vertex) {
if (this.vertices.has(vertex)) {
return false;
}
this.vertices.set(vertex, this.detector.createVertexData(this.adapter, vertex));
return true;
};
GenericGraphAdapter.prototype.deleteEdge = function (from, to) {
var f = this.forward.get(from);
var b = this.backward.get(to);
if (!f || !b) {
return false;
}
if (!f.delete(to) || !b.delete(from)) {
return false;
}
this.edgeCount -= 1;
return true;
};
GenericGraphAdapter.prototype.deleteVertex = function (vertex) {
if (!this.vertices.has(vertex)) {
return false;
}
this.detector.onVertexDeletion(this.adapter, vertex);
for (var it_1 = this.getSuccessorsOf(vertex), res = it_1.next(); !res.done; res = it_1.next()) {
this.deleteEdge(vertex, res.value);
}
for (var it_2 = this.getPredecessorsOf(vertex), res = it_2.next(); !res.done; res = it_2.next()) {
this.deleteEdge(res.value, vertex);
}
this.vertices.delete(vertex);
return true;
};
GenericGraphAdapter.prototype.getData = function (key) {
return this.vertices.get(key);
};
return GenericGraphAdapter;
}());
exports.GenericGraphAdapter = GenericGraphAdapter;
},{"./PearceKellyDetector":5,"./util":6}],3:[function(require,module,exports){
"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
var PearceKellyDetector_1 = require("./PearceKellyDetector");
var util_1 = require("./util");
var GraphlibAdapter = (function () {
function GraphlibAdapter(options) {
this.g = new options.graphlib(assign({ directed: true }, options.graphOptions));
this.g = new options.graphlib(util_1.assign({ directed: true }, options.graphOptions));
this.detector = options.cycleDetector || new PearceKellyDetector_1.PearceKellyDetector();

@@ -105,5 +177,8 @@ this.adapter = {

}
GraphlibAdapter.prototype.contractEdge = function (from, to) {
return contractEdge(this, from, to);
GraphlibAdapter.prototype.canContractEdge = function (from, to) {
return util_1.canContractEdge(this, from, to);
};
GraphlibAdapter.prototype.contractEdge = function (from, to, vertexMerger, edgeMerger) {
return util_1.contractEdge(this, from, to, vertexMerger, edgeMerger);
};
GraphlibAdapter.prototype.isReachable = function (source, target) {

@@ -115,5 +190,5 @@ return this.detector.isReachable(this.adapter, source, target);

if (!edges) {
return EmptyIterator;
return util_1.EmptyIterator;
}
return createArrayIterator(edges);
return util_1.createArrayIterator(edges);
};

@@ -123,5 +198,5 @@ GraphlibAdapter.prototype.getPredecessorsOf = function (vertex) {

if (!edges) {
return EmptyIterator;
return util_1.EmptyIterator;
}
return createArrayIterator(edges);
return util_1.createArrayIterator(edges);
};

@@ -143,8 +218,24 @@ GraphlibAdapter.prototype.hasEdge = function (from, to) {

};
GraphlibAdapter.prototype.getEdgeData = function (from, to) {
return this.g.edge(from, to);
};
GraphlibAdapter.prototype.setEdgeData = function (from, to, data) {
if (!this.g.hasEdge(from, to)) {
return false;
}
this.g.setEdge(from, to, data);
return true;
};
GraphlibAdapter.prototype.getVertices = function () {
return createArrayIterator(this.g.nodes());
return util_1.createArrayIterator(this.g.nodes());
};
GraphlibAdapter.prototype.getEdges = function () {
return createMappedArrayIterator(this.g.edges(), function (edge) { return [edge.v, edge.w]; });
return util_1.createMappedArrayIterator(this.g.edges(), function (edge) { return [edge.v, edge.w]; });
};
GraphlibAdapter.prototype.supportsOrder = function () {
return this.detector.supportsOrder();
};
GraphlibAdapter.prototype.getOrder = function (vertex) {
return this.detector.getOrder(this.adapter, vertex);
};
Object.defineProperty(GraphlibAdapter.prototype, "graph", {

@@ -157,4 +248,4 @@ get: function () {

});
GraphlibAdapter.prototype.addEdge = function (from, to, label, name) {
if (this.g.hasEdge(from, to, name)) {
GraphlibAdapter.prototype.addEdge = function (from, to, data) {
if (this.g.hasEdge(from, to)) {
return false;

@@ -173,3 +264,3 @@ }

}
this.g.setEdge(from, to, label, name);
this.g.setEdge(from, to, data);
return true;

@@ -182,3 +273,3 @@ };

var vertexData = this.detector.createVertexData(this.adapter, vertex);
this.g.setNode(vertex, label !== undefined ? assign(vertexData, label) : vertexData);
this.g.setNode(vertex, label !== undefined ? util_1.assign(vertexData, label) : vertexData);
return true;

@@ -207,147 +298,178 @@ };

exports.GraphlibAdapter = GraphlibAdapter;
var GenericGraphAdapter = (function () {
function GenericGraphAdapter(options) {
},{"./PearceKellyDetector":5,"./util":6}],4:[function(require,module,exports){
"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
var GenericGraphAdapter_1 = require("./GenericGraphAdapter");
var util_1 = require("./util");
function createMerger(edgeMerger) {
if (edgeMerger === void 0) { edgeMerger = util_1.takeFirst; }
return function (first, second) {
if (first === undefined) {
return second;
}
if (second === undefined) {
return first;
}
for (var it_1 = second.entries(), res = it_1.next(); !res.done; res = it_1.next()) {
var data = first.get(res.value[0]);
data = data === undefined ? res.value[1] : edgeMerger(data, res.value[1]);
first.set(res.value[0], data);
}
return first;
};
}
var MultiGraphAdapter = (function () {
function MultiGraphAdapter(options) {
if (options === void 0) { options = {}; }
var mapConstructor = options.mapConstructor || Map;
this.detector = options.cycleDetector || new PearceKellyDetector_1.PearceKellyDetector();
this.forward = new mapConstructor();
this.backward = new mapConstructor();
this.mapConstructor = mapConstructor;
this.vertices = new mapConstructor();
this.g = new GenericGraphAdapter_1.GenericGraphAdapter(options);
this.edgeCount = 0;
this.adapter = {
getData: this.getData.bind(this),
getPredecessorsOf: this.getPredecessorsOf.bind(this),
getSuccessorsOf: this.getSuccessorsOf.bind(this),
};
}
GenericGraphAdapter.prototype.contractEdge = function (from, to) {
return contractEdge(this, from, to);
MultiGraphAdapter.prototype.addLabeledEdge = function (from, to, label, data) {
return this.addEdge(from, to, data, label);
};
GenericGraphAdapter.prototype.isReachable = function (source, target) {
return this.detector.isReachable(this.adapter, source, target);
};
GenericGraphAdapter.prototype.getSuccessorsOf = function (vertex) {
var f = this.forward.get(vertex);
if (f === undefined) {
return EmptyIterator;
MultiGraphAdapter.prototype.addEdge = function (from, to, data, label) {
var srcData = this.g.getEdgeData(from, to);
if (srcData !== undefined) {
if (srcData.has(label)) {
return false;
}
srcData.set(label, data);
this.edgeCount += 1;
return true;
}
return f.keys();
this.edgeCount += 1;
var newData = new Map();
newData.set(label, data);
return this.g.addEdge(from, to, newData);
};
GenericGraphAdapter.prototype.getPredecessorsOf = function (vertex) {
var b = this.backward.get(vertex);
if (b === undefined) {
return EmptyIterator;
}
return b.keys();
MultiGraphAdapter.prototype.addVertex = function (vertex) {
return this.g.addVertex(vertex);
};
GenericGraphAdapter.prototype.getVertices = function () {
return this.vertices.keys();
MultiGraphAdapter.prototype.contractEdge = function (from, to, vertexMerger, edgeMerger) {
return this.g.contractEdge(from, to, vertexMerger, createMerger(edgeMerger));
};
GenericGraphAdapter.prototype.getEdgeSourceData = function (from, to) {
var map = this.backward.get(to);
if (!map) {
return undefined;
}
return map.get(from);
MultiGraphAdapter.prototype.canContractEdge = function (from, to) {
return this.g.canContractEdge(from, to);
};
GenericGraphAdapter.prototype.getEdgeTargetData = function (from, to) {
var map = this.forward.get(from);
if (!map) {
return undefined;
MultiGraphAdapter.prototype.deleteEdge = function (from, to, label) {
if (label === undefined) {
this.edgeCount -= this.getEdgeCountBetween(from, to);
return this.g.deleteEdge(from, to);
}
return map.get(to);
};
GenericGraphAdapter.prototype.getEdges = function () {
var edges = [];
for (var it_3 = this.forward.entries(), res = it_3.next(); !res.done; res = it_3.next()) {
for (var it2 = res.value[1].keys(), res2 = it2.next(); !res2.done; res2 = it2.next()) {
edges.push([res.value[0], res2.value]);
}
var srcData = this.g.getEdgeData(from, to);
if (srcData === undefined) {
return false;
}
return createArrayIterator(edges);
var wasDeleted = srcData.delete(label);
if (wasDeleted) {
this.edgeCount -= 1;
}
if (srcData.size === 0) {
this.g.deleteEdge(from, to);
}
return wasDeleted;
};
GenericGraphAdapter.prototype.getEdgeCount = function () {
MultiGraphAdapter.prototype.deleteVertex = function (vertex) {
return this.g.deleteVertex(vertex);
};
MultiGraphAdapter.prototype.getLabeledEdgeCount = function () {
return this.edgeCount;
};
GenericGraphAdapter.prototype.getVertexCount = function () {
return this.vertices.size;
MultiGraphAdapter.prototype.getEdgeCount = function () {
return this.g.getEdgeCount();
};
GenericGraphAdapter.prototype.hasEdge = function (from, to) {
var f = this.forward.get(from);
return f ? f.has(to) : false;
MultiGraphAdapter.prototype.getEdgeData = function (from, to, label) {
var data = this.g.getEdgeData(from, to);
if (data === undefined) {
return undefined;
}
return data.get(label);
};
GenericGraphAdapter.prototype.hasVertex = function (vertex) {
return this.vertices.has(vertex);
};
GenericGraphAdapter.prototype.addEdge = function (from, to, edgeSourceData, edgeTargetData) {
var f = this.forward.get(from);
var b = this.backward.get(to);
var didNotHaveFrom = this.addVertex(from);
var didNotHaveTo = this.addVertex(to);
if (!f) {
this.forward.set(from, f = new this.mapConstructor());
}
if (!b) {
this.backward.set(to, b = new this.mapConstructor());
}
if (!this.detector.canAddEdge(this.adapter, from, to)) {
if (didNotHaveFrom) {
this.deleteVertex(from);
}
if (didNotHaveTo) {
this.deleteVertex(to);
}
MultiGraphAdapter.prototype.setEdgeData = function (from, to, data, label) {
var d = this.g.getEdgeData(from, to);
if (d === undefined || !d.has(label)) {
return false;
}
var sizeBefore = f.size;
f.set(to, edgeTargetData);
b.set(from, edgeSourceData);
if (sizeBefore === f.size) {
return false;
}
this.edgeCount += 1;
d.set(label, data);
return true;
};
GenericGraphAdapter.prototype.addVertex = function (vertex) {
if (this.vertices.has(vertex)) {
return false;
MultiGraphAdapter.prototype.getEdges = function () {
return this.g.getEdges();
};
MultiGraphAdapter.prototype.getEdgeCountBetween = function (from, to) {
var data = this.g.getEdgeData(from, to);
if (data === undefined) {
return 0;
}
this.vertices.set(vertex, this.detector.createVertexData(this.adapter, vertex));
return true;
return data.size;
};
GenericGraphAdapter.prototype.deleteEdge = function (from, to) {
var f = this.forward.get(from);
var b = this.backward.get(to);
if (!f || !b) {
return false;
MultiGraphAdapter.prototype.getEdgeLabels = function (from, to) {
var data = this.g.getEdgeData(from, to);
if (data === undefined) {
return util_1.EmptyIterator;
}
if (!f.delete(to) || !b.delete(from)) {
return false;
return data.keys();
};
MultiGraphAdapter.prototype.getLabeledEdges = function () {
var _this = this;
return util_1.createFlatMappedIterator(this.g.getEdges(), function (edge) {
var data = _this.g.getEdgeData(edge[0], edge[1]);
if (data === undefined) {
return util_1.EmptyIterator;
}
return util_1.createMappedIterator(data.keys(), function (key) { return [edge[0], edge[1], key]; });
});
};
MultiGraphAdapter.prototype.getPredecessorsOf = function (vertex, label) {
var _this = this;
if (label === undefined) {
return this.g.getPredecessorsOf(vertex);
}
this.edgeCount -= 1;
return true;
return util_1.createFilteredIterator(this.g.getPredecessorsOf(vertex), function (from) {
var data = _this.g.getEdgeData(from, vertex);
return data !== undefined && data.has(label);
});
};
GenericGraphAdapter.prototype.deleteVertex = function (vertex) {
if (!this.vertices.has(vertex)) {
return false;
MultiGraphAdapter.prototype.getSuccessorsOf = function (vertex, label) {
var _this = this;
if (label === undefined) {
return this.g.getSuccessorsOf(vertex);
}
this.detector.onVertexDeletion(this.adapter, vertex);
for (var it_4 = this.getSuccessorsOf(vertex), res = it_4.next(); !res.done; res = it_4.next()) {
this.deleteEdge(vertex, res.value);
}
for (var it_5 = this.getPredecessorsOf(vertex), res = it_5.next(); !res.done; res = it_5.next()) {
this.deleteEdge(res.value, vertex);
}
this.vertices.delete(vertex);
return true;
return util_1.createFilteredIterator(this.g.getSuccessorsOf(vertex), function (to) {
var data = _this.g.getEdgeData(vertex, to);
return data !== undefined && data.has(label);
});
};
GenericGraphAdapter.prototype.getData = function (key) {
return this.vertices.get(key);
MultiGraphAdapter.prototype.getOrder = function (vertex) {
return this.g.getOrder(vertex);
};
return GenericGraphAdapter;
MultiGraphAdapter.prototype.supportsOrder = function () {
return this.g.supportsOrder();
};
MultiGraphAdapter.prototype.getVertexCount = function () {
return this.g.getVertexCount();
};
MultiGraphAdapter.prototype.getVertices = function () {
return this.g.getVertices();
};
MultiGraphAdapter.prototype.hasEdge = function (from, to, label) {
var data = this.g.getEdgeData(from, to);
return data !== undefined && (label === undefined || data.has(label));
};
MultiGraphAdapter.prototype.hasLabeledEdge = function (from, to, label) {
var data = this.g.getEdgeData(from, to);
return data !== undefined && data.has(label);
};
MultiGraphAdapter.prototype.hasVertex = function (vertex) {
return this.g.hasVertex(vertex);
};
MultiGraphAdapter.prototype.isReachable = function (source, target) {
return this.g.isReachable(source, target);
};
return MultiGraphAdapter;
}());
exports.GenericGraphAdapter = GenericGraphAdapter;
exports.MultiGraphAdapter = MultiGraphAdapter;
},{"./PearceKellyDetector":3}],3:[function(require,module,exports){
},{"./GenericGraphAdapter":2,"./util":6}],5:[function(require,module,exports){
"use strict";

@@ -400,10 +522,8 @@ Object.defineProperty(exports, "__esModule", { value: true });

}
var tOrder = adapter.getData(target).order;
if (adapter.getData(source).order > tOrder) {
var targetOrder = adapter.getData(target).order;
if (adapter.getData(source).order > targetOrder) {
return false;
}
var reachable = !this.dfs_f(source, adapter, tOrder);
if (reachable) {
this.cleanAfterCycle(adapter);
}
var reachable = !this.dfs_f(source, adapter, targetOrder);
this.cleanAfterCycle(adapter);
return reachable;

@@ -428,2 +548,8 @@ };

};
PearceKellyDetector.prototype.supportsOrder = function () {
return true;
};
PearceKellyDetector.prototype.getOrder = function (g, vertex) {
return g.getData(vertex).order;
};
PearceKellyDetector.prototype.checkCycle = function (adapter, x, y) {

@@ -507,3 +633,212 @@ var lb = adapter.getData(y).order;

},{}],4:[function(require,module,exports){
},{}],6:[function(require,module,exports){
"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
function takeFirst(first, second) {
return first;
}
exports.takeFirst = takeFirst;
exports.DoneIteratorResult = {
done: true,
value: undefined,
};
exports.EmptyIterator = {
next: function () {
return exports.DoneIteratorResult;
}
};
var hasOwnProperty = Object.prototype.hasOwnProperty;
function assign(target, source) {
for (var key in source) {
if (hasOwnProperty.call(source, key)) {
target[key] = source[key];
}
}
return target;
}
exports.assign = assign;
function toArray(it) {
var arr = [];
for (var res = it.next(); !res.done; res = it.next()) {
arr.push(res.value);
}
return arr;
}
exports.toArray = toArray;
function createMappedIterator(it, mapper) {
return {
next: function () {
var res = it.next();
if (res.done) {
return exports.DoneIteratorResult;
}
return {
done: false,
value: mapper(res.value),
};
}
};
}
exports.createMappedIterator = createMappedIterator;
function createFilteredIterator(it, filter) {
return {
next: function () {
var res = it.next();
while (!res.done && !filter(res.value)) {
res = it.next();
}
return res;
}
};
}
exports.createFilteredIterator = createFilteredIterator;
function createFlatMappedIterator(iterator, mapper) {
var subIterator = exports.EmptyIterator;
return {
next: function () {
var subNext = subIterator.next();
while (subNext.done) {
var next = iterator.next();
if (next.done) {
return exports.DoneIteratorResult;
}
subIterator = mapper(next.value);
subNext = subIterator.next();
}
return {
done: false,
value: subNext.value,
};
}
};
}
exports.createFlatMappedIterator = createFlatMappedIterator;
function createArrayIterator(array) {
var i = 0;
return {
array: array,
next: function () {
while (array[i] === undefined) {
if (i > array.length) {
return exports.DoneIteratorResult;
}
i += 1;
}
return {
done: false,
value: array[i++],
};
}
};
}
exports.createArrayIterator = createArrayIterator;
function createMappedArrayIterator(arr, mapFn) {
var i = 0;
return {
next: function () {
while (arr[i] === undefined) {
if (i > arr.length) {
return exports.DoneIteratorResult;
}
i += 1;
}
return {
done: false,
value: mapFn(arr[i++]),
};
}
};
}
exports.createMappedArrayIterator = createMappedArrayIterator;
function canContractEdge(adapter, from, to) {
if (!adapter.hasEdge(from, to)) {
return false;
}
var data = adapter.getEdgeData(from, to);
adapter.deleteEdge(from, to);
var result = !adapter.isReachable(from, to);
adapter.addEdge(from, to, data);
return result;
}
exports.canContractEdge = canContractEdge;
function contractEdge(adapter, from, to, vertexMerger, edgeMerger) {
if (vertexMerger === void 0) { vertexMerger = takeFirst; }
if (!adapter.hasEdge(from, to)) {
return false;
}
var data = adapter.getEdgeData(from, to);
adapter.deleteEdge(from, to);
if (adapter.isReachable(from, to)) {
adapter.addEdge(from, to, data);
return false;
}
var newVertex = vertexMerger(from, to);
if (newVertex !== from && newVertex !== to && adapter.hasVertex(newVertex)) {
adapter.addEdge(from, to, data);
throw new Error("Cannot use existing vertex for edge contraction: " + newVertex);
}
performEdgeContraction(adapter, from, to, edgeMerger, newVertex);
return true;
}
exports.contractEdge = contractEdge;
function performEdgeContraction(adapter, from, to, dataMerger, newVertex) {
if (dataMerger === void 0) { dataMerger = takeFirst; }
var succ = [];
var pred = [];
if (newVertex !== from) {
for (var it_1 = adapter.getSuccessorsOf(from), res = it_1.next(); !res.done; res = it_1.next()) {
var data = adapter.getEdgeData(from, res.value);
adapter.deleteEdge(from, res.value);
succ.push([res.value, data]);
}
for (var it_2 = adapter.getPredecessorsOf(from), res = it_2.next(); !res.done; res = it_2.next()) {
var data = adapter.getEdgeData(res.value, from);
adapter.deleteEdge(res.value, from);
pred.push([res.value, data]);
}
}
if (newVertex !== to) {
for (var it_3 = adapter.getSuccessorsOf(to), res = it_3.next(); !res.done; res = it_3.next()) {
var data = adapter.getEdgeData(to, res.value);
adapter.deleteEdge(to, res.value);
succ.push([res.value, data]);
}
for (var it_4 = adapter.getPredecessorsOf(to), res = it_4.next(); !res.done; res = it_4.next()) {
var data = adapter.getEdgeData(res.value, to);
adapter.deleteEdge(res.value, to);
pred.push([res.value, data]);
}
}
if (newVertex !== from && newVertex !== to) {
adapter.addVertex(newVertex);
}
for (var _i = 0, succ_1 = succ; _i < succ_1.length; _i++) {
var node = succ_1[_i];
var data = adapter.getEdgeData(newVertex, node[0]);
if (data === undefined) {
adapter.addEdge(newVertex, node[0], node[1]);
}
else {
adapter.setEdgeData(newVertex, node[0], dataMerger(data, node[1]));
}
}
for (var _a = 0, pred_1 = pred; _a < pred_1.length; _a++) {
var node = pred_1[_a];
var data = adapter.getEdgeData(node[0], newVertex);
if (data === undefined) {
adapter.addEdge(node[0], newVertex, node[1]);
}
else {
adapter.setEdgeData(node[0], newVertex, dataMerger(data, node[1]));
}
}
if (newVertex !== to) {
adapter.deleteVertex(to);
}
if (newVertex !== from) {
adapter.deleteVertex(from);
}
}
},{}],7:[function(require,module,exports){
(function (global){

@@ -627,4 +962,4 @@ /*! *****************************************************************************

while (_) try {
if (f = 1, y && (t = y[op[0] & 2 ? "return" : op[0] ? "throw" : "next"]) && !(t = t.call(y, op[1])).done) return t;
if (y = 0, t) op = [0, t.value];
if (f = 1, y && (t = op[0] & 2 ? y["return"] : op[0] ? y["throw"] || ((t = y["return"]) && t.call(y), 0) : y.next) && !(t = t.call(y, op[1])).done) return t;
if (y = 0, t) op = [op[0] & 2, t.value];
switch (op[0]) {

@@ -631,0 +966,0 @@ case 0: case 1: t = op; break;

2

dist/browser.min.js

@@ -1,1 +0,1 @@

(function(a){if("object"==typeof exports&&"undefined"!=typeof module)module.exports=a();else if("function"==typeof define&&define.amd)define([],a);else{var b;b="undefined"==typeof window?"undefined"==typeof global?"undefined"==typeof self?this:self:global:window,b.IncrementalCycleDetect=a()}})(function(){var a;return function(){function b(d,e,g){function a(j,i){if(!e[j]){if(!d[j]){var f="function"==typeof require&&require;if(!i&&f)return f(j,!0);if(h)return h(j,!0);var c=new Error("Cannot find module '"+j+"'");throw c.code="MODULE_NOT_FOUND",c}var k=e[j]={exports:{}};d[j][0].call(k.exports,function(b){var c=d[j][1][b];return a(c||b)},k,k.exports,b,d,e,g)}return e[j].exports}for(var h="function"==typeof require&&require,c=0;c<g.length;c++)a(g[c]);return a}return b}()({1:[function(a,b,c){"use strict";Object.defineProperty(c,"__esModule",{value:!0});var d=a("tslib");d.__exportStar(a("./src/GraphAdapter"),c),d.__exportStar(a("./src/PearceKellyDetector"),c)},{"./src/GraphAdapter":2,"./src/PearceKellyDetector":3,tslib:4}],2:[function(a,b,c){"use strict";function d(a,b){for(var c in b)k.call(b,c)&&(a[c]=b[c]);return a}function e(a){var b=0;return{next:function(){for(;a[b]===void 0;){if(b>a.length)return j;b+=1}return{done:!1,value:a[b++]}}}}function f(a,b){var c=0;return{next:function(){for(;a[c]===void 0;){if(c>a.length)return j;c+=1}return{done:!1,value:b(a[c++])}}}}function g(a,b,c){if(!a.hasEdge(b,c))return!1;if(a.deleteEdge(b,c),a.isReachable(b,c))return a.addEdge(b,c),!1;for(var d=[],e=[],f=a.getSuccessorsOf(c),g=f.next();!g.done;g=f.next())a.deleteEdge(c,g.value),d.push(g.value);for(var h=a.getPredecessorsOf(c),g=h.next();!g.done;g=h.next())a.deleteEdge(g.value,c),e.push(g.value);for(var i,j=0,k=d;j<k.length;j++)i=k[j],a.addEdge(b,i);for(var i,l=0,m=e;l<m.length;l++)i=m[l],a.addEdge(i,b);return a.deleteVertex(c),!0}Object.defineProperty(c,"__esModule",{value:!0});var h=a("./PearceKellyDetector"),j={done:!0,value:void 0},i={next:function(){return j}},k=Object.prototype.hasOwnProperty,l=function(){function a(a){this.g=new a.graphlib(d({directed:!0},a.graphOptions)),this.detector=a.cycleDetector||new h.PearceKellyDetector,this.adapter={getData:this.getData.bind(this),getPredecessorsOf:this.getPredecessorsOf.bind(this),getSuccessorsOf:this.getSuccessorsOf.bind(this)}}return a.prototype.contractEdge=function(a,b){return g(this,a,b)},a.prototype.isReachable=function(a,b){return this.detector.isReachable(this.adapter,a,b)},a.prototype.getSuccessorsOf=function(a){var b=this.g.successors(a);return b?e(b):i},a.prototype.getPredecessorsOf=function(a){var b=this.g.predecessors(a);return b?e(b):i},a.prototype.hasEdge=function(a,b){return this.g.hasEdge(a,b)},a.prototype.hasVertex=function(a){return this.g.hasNode(a)},a.prototype.getVertexCount=function(){return this.g.nodeCount()},a.prototype.getEdgeCount=function(){return this.g.edgeCount()},a.prototype.getVertexData=function(a){return this.g.node(a)},a.prototype.getVertices=function(){return e(this.g.nodes())},a.prototype.getEdges=function(){return f(this.g.edges(),function(a){return[a.v,a.w]})},Object.defineProperty(a.prototype,"graph",{get:function(){return this.g},enumerable:!0,configurable:!0}),a.prototype.addEdge=function(a,b,c,d){if(this.g.hasEdge(a,b,d))return!1;var e=this.addVertex(a),f=this.addVertex(b);return this.detector.canAddEdge(this.adapter,a,b)?(this.g.setEdge(a,b,c,d),!0):(e&&this.deleteVertex(a),f&&this.deleteVertex(b),!1)},a.prototype.addVertex=function(a,b){if(this.hasVertex(a))return!1;var c=this.detector.createVertexData(this.adapter,a);return this.g.setNode(a,void 0===b?c:d(c,b)),!0},a.prototype.deleteEdge=function(a,b,c){return!!this.g.hasEdge(a,b,c)&&(this.g.removeEdge(a,b),!0)},a.prototype.deleteVertex=function(a){return!!this.g.hasNode(a)&&(this.detector.onVertexDeletion(this.adapter,a),this.g.removeNode(a),!0)},a.prototype.getData=function(a){return this.g.node(a)},a}();c.GraphlibAdapter=l;var m=function(){function a(a){void 0===a&&(a={});var b=a.mapConstructor||Map;this.detector=a.cycleDetector||new h.PearceKellyDetector,this.forward=new b,this.backward=new b,this.mapConstructor=b,this.vertices=new b,this.edgeCount=0,this.adapter={getData:this.getData.bind(this),getPredecessorsOf:this.getPredecessorsOf.bind(this),getSuccessorsOf:this.getSuccessorsOf.bind(this)}}return a.prototype.contractEdge=function(a,b){return g(this,a,b)},a.prototype.isReachable=function(a,b){return this.detector.isReachable(this.adapter,a,b)},a.prototype.getSuccessorsOf=function(a){var b=this.forward.get(a);return void 0===b?i:b.keys()},a.prototype.getPredecessorsOf=function(a){var c=this.backward.get(a);return void 0===c?i:c.keys()},a.prototype.getVertices=function(){return this.vertices.keys()},a.prototype.getEdgeSourceData=function(a,b){var c=this.backward.get(b);return c?c.get(a):void 0},a.prototype.getEdgeTargetData=function(a,b){var c=this.forward.get(a);return c?c.get(b):void 0},a.prototype.getEdges=function(){for(var a=[],b=this.forward.entries(),c=b.next();!c.done;c=b.next())for(var d=c.value[1].keys(),f=d.next();!f.done;f=d.next())a.push([c.value[0],f.value]);return e(a)},a.prototype.getEdgeCount=function(){return this.edgeCount},a.prototype.getVertexCount=function(){return this.vertices.size},a.prototype.hasEdge=function(a,b){var c=this.forward.get(a);return!!c&&c.has(b)},a.prototype.hasVertex=function(a){return this.vertices.has(a)},a.prototype.addEdge=function(a,c,d,e){var g=this.forward.get(a),h=this.backward.get(c),i=this.addVertex(a),j=this.addVertex(c);if(g||this.forward.set(a,g=new this.mapConstructor),h||this.backward.set(c,h=new this.mapConstructor),!this.detector.canAddEdge(this.adapter,a,c))return i&&this.deleteVertex(a),j&&this.deleteVertex(c),!1;var k=g.size;return(g.set(c,e),h.set(a,d),k!==g.size)&&(this.edgeCount+=1,!0)},a.prototype.addVertex=function(a){return!this.vertices.has(a)&&(this.vertices.set(a,this.detector.createVertexData(this.adapter,a)),!0)},a.prototype.deleteEdge=function(a,c){var d=this.forward.get(a),e=this.backward.get(c);return!!(d&&e)&&!!(d.delete(c)&&e.delete(a))&&(this.edgeCount-=1,!0)},a.prototype.deleteVertex=function(a){if(!this.vertices.has(a))return!1;this.detector.onVertexDeletion(this.adapter,a);for(var b=this.getSuccessorsOf(a),c=b.next();!c.done;c=b.next())this.deleteEdge(a,c.value);for(var d=this.getPredecessorsOf(a),c=d.next();!c.done;c=d.next())this.deleteEdge(c.value,a);return this.vertices.delete(a),!0},a.prototype.getData=function(a){return this.vertices.get(a)},a}();c.GenericGraphAdapter=m},{"./PearceKellyDetector":3}],3:[function(a,b,c){"use strict";function d(a,b,c){for(var d=[],e=b.length,f=c.length,g=0,h=0;g<e&&h<f;){var i=a.getData(b[g]).order,j=a.getData(c[h]).order;i<j?(g+=1,d.push(i)):(h+=1,d.push(j))}for(;g<e;){var i=a.getData(b[g]);g+=1,d.push(i.order)}for(;h<f;){var j=a.getData(c[h]);h+=1,d.push(j.order)}return d}function e(a,b){return b.map(function(b){return{key:a.getData(b).order,val:b}}).sort(function(a,b){return a.key-b.key}).map(function(a){return a.val})}Object.defineProperty(c,"__esModule",{value:!0});var f=function(){function a(){this.id=0,this.stack=[],this.deltaXyB=[],this.deltaXyF=[],this.freeStack=[]}return a.prototype.isReachable=function(a,b,c){if(b===c)return!0;var d=a.getData(c).order;if(a.getData(b).order>d)return!1;var e=!this.dfs_f(b,a,d);return e&&this.cleanAfterCycle(a),e},a.prototype.createVertexData=function(){var a=this.freeStack.pop();return{order:void 0===a?this.id++:a,visited:!1}},a.prototype.onVertexDeletion=function(a,b){var c=a.getData(b);this.freeStack.push(c.order)},a.prototype.canAddEdge=function(a,b,c){return b!==c&&this.checkCycle(a,b,c)},a.prototype.checkCycle=function(a,b,c){var d=a.getData(c).order,e=a.getData(b).order;if(this.deltaXyB=[],this.deltaXyF=[],d<e){if(!this.dfs_f(c,a,e))return this.cleanAfterCycle(a),!1;this.dfs_b(b,a,d),this.reorder(a)}return!0},a.prototype.cleanAfterCycle=function(a){this.stack=[];for(var b=this.deltaXyF.pop();void 0!==b;b=this.deltaXyF.pop())a.getData(b).visited=!1},a.prototype.dfs_f=function(a,b,c){for(this.stack.push(a);0<this.stack.length;){var d=this.stack.pop(),e=b.getData(d);if(!e.visited){e.visited=!0,this.deltaXyF.push(d);for(var f,g=b.getSuccessorsOf(d),h=g.next();!h.done;h=g.next()){if(f=b.getData(h.value),f.order===c)return!1;!f.visited&&f.order<c&&this.stack.push(h.value)}}}return!0},a.prototype.dfs_b=function(a,b,c){for(this.stack.push(a);0<this.stack.length;){var d=this.stack.pop(),e=b.getData(d);if(!e.visited){e.visited=!0,this.deltaXyB.push(d);for(var f,g=b.getPredecessorsOf(d),h=g.next();!h.done;h=g.next())f=b.getData(h.value),!f.visited&&c<f.order&&this.stack.push(h.value)}}},a.prototype.reorder=function(a){this.deltaXyB=e(a,this.deltaXyB),this.deltaXyF=e(a,this.deltaXyF);for(var b,c=this.deltaXyB.concat(this.deltaXyF),f=0,g=c;f<g.length;f++)b=g[f],a.getData(b).visited=!1;for(var h=d(a,this.deltaXyB,this.deltaXyF),k=0,l=c.length;k<l;++k)a.getData(c[k]).order=h[k]},a}();c.PearceKellyDetector=f},{}],4:[function(b,c){(function(b){var d,e,f,g,h,i,j,k,l,n,m,o,s,p,q,r,t,u,v;(function(d){function e(a,b){return a!==f&&("function"==typeof Object.create?Object.defineProperty(a,"__esModule",{value:!0}):a.__esModule=!0),function(c,d){return a[c]=b?b(c,d):d}}var f="object"==typeof b?b:"object"==typeof self?self:"object"==typeof this?this:{};"function"==typeof a&&a.amd?a("tslib",["exports"],function(a){d(e(f,e(a)))}):"object"==typeof c&&"object"==typeof c.exports?d(e(f,e(c.exports))):d(e(f))})(function(a){var c=Object.setPrototypeOf||{__proto__:[]}instanceof Array&&function(a,c){a.__proto__=c}||function(a,c){for(var b in c)c.hasOwnProperty(b)&&(a[b]=c[b])};d=function(a,d){function b(){this.constructor=a}c(a,d),a.prototype=null===d?Object.create(d):(b.prototype=d.prototype,new b)},e=Object.assign||function(a){for(var b,c=1,d=arguments.length;c<d;c++)for(var e in b=arguments[c],b)Object.prototype.hasOwnProperty.call(b,e)&&(a[e]=b[e]);return a},f=function(a,b){var c={};for(var d in a)Object.prototype.hasOwnProperty.call(a,d)&&0>b.indexOf(d)&&(c[d]=a[d]);if(null!=a&&"function"==typeof Object.getOwnPropertySymbols)for(var e=0,d=Object.getOwnPropertySymbols(a);e<d.length;e++)0>b.indexOf(d[e])&&(c[d[e]]=a[d[e]]);return c},g=function(a,b,e,f){var g,h=arguments.length,c=3>h?b:null===f?f=Object.getOwnPropertyDescriptor(b,e):f;if("object"==typeof Reflect&&"function"==typeof Reflect.decorate)c=Reflect.decorate(a,b,e,f);else for(var j=a.length-1;0<=j;j--)(g=a[j])&&(c=(3>h?g(c):3<h?g(b,e,c):g(b,e))||c);return 3<h&&c&&Object.defineProperty(b,e,c),c},h=function(a,b){return function(c,d){b(c,d,a)}},i=function(a,b){if("object"==typeof Reflect&&"function"==typeof Reflect.metadata)return Reflect.metadata(a,b)},j=function(a,b,c,d){return new(c||(c=Promise))(function(e,f){function g(a){try{i(d.next(a))}catch(a){f(a)}}function h(a){try{i(d["throw"](a))}catch(a){f(a)}}function i(a){a.done?e(a.value):new c(function(b){b(a.value)}).then(g,h)}i((d=d.apply(a,b||[])).next())})},k=function(a,b){function c(a){return function(b){return d([a,b])}}function d(c){if(e)throw new TypeError("Generator is already executing.");for(;k;)try{if(e=1,h&&(i=h[2&c[0]?"return":c[0]?"throw":"next"])&&!(i=i.call(h,c[1])).done)return i;switch((h=0,i)&&(c=[0,i.value]),c[0]){case 0:case 1:i=c;break;case 4:return k.label++,{value:c[1],done:!1};case 5:k.label++,h=c[1],c=[0];continue;case 7:c=k.ops.pop(),k.trys.pop();continue;default:if((i=k.trys,!(i=0<i.length&&i[i.length-1]))&&(6===c[0]||2===c[0])){k=0;continue}if(3===c[0]&&(!i||c[1]>i[0]&&c[1]<i[3])){k.label=c[1];break}if(6===c[0]&&k.label<i[1]){k.label=i[1],i=c;break}if(i&&k.label<i[2]){k.label=i[2],k.ops.push(c);break}i[2]&&k.ops.pop(),k.trys.pop();continue;}c=b.call(a,k)}catch(a){c=[6,a],h=0}finally{e=i=0}if(5&c[0])throw c[1];return{value:c[0]?c[1]:void 0,done:!0}}var e,h,i,j,k={label:0,sent:function(){if(1&i[0])throw i[1];return i[1]},trys:[],ops:[]};return j={next:c(0),throw:c(1),return:c(2)},"function"==typeof Symbol&&(j[Symbol.iterator]=function(){return this}),j},l=function(a,b){for(var c in a)b.hasOwnProperty(c)||(b[c]=a[c])},n=function(a){var b="function"==typeof Symbol&&a[Symbol.iterator],c=0;return b?b.call(a):{next:function(){return a&&c>=a.length&&(a=void 0),{value:a&&a[c++],done:!a}}}},m=function(a,b){var c="function"==typeof Symbol&&a[Symbol.iterator];if(!c)return a;var d,f,g=c.call(a),h=[];try{for(;(void 0===b||0<b--)&&!(d=g.next()).done;)h.push(d.value)}catch(a){f={error:a}}finally{try{d&&!d.done&&(c=g["return"])&&c.call(g)}finally{if(f)throw f.error}}return h},o=function(){for(var a=[],b=0;b<arguments.length;b++)a=a.concat(m(arguments[b]));return a},s=function(a){return this instanceof s?(this.v=a,this):new s(a)},p=function(a,b,c){function d(c){m[c]&&(l[c]=function(d){return new Promise(function(f,a){1<g.push([c,d,f,a])||e(c,d)})})}function e(a,b){try{f(m[a](b))}catch(a){k(g[0][3],a)}}function f(a){a.value instanceof s?Promise.resolve(a.value.v).then(h,j):k(g[0][2],a)}function h(a){e("next",a)}function j(a){e("throw",a)}function k(a,b){(a(b),g.shift(),g.length)&&e(g[0][0],g[0][1])}if(!Symbol.asyncIterator)throw new TypeError("Symbol.asyncIterator is not defined.");var l,m=c.apply(a,b||[]),g=[];return l={},d("next"),d("throw"),d("return"),l[Symbol.asyncIterator]=function(){return this},l},q=function(a){function b(b,e){c[b]=a[b]?function(c){return(d=!d)?{value:s(a[b](c)),done:"return"===b}:e?e(c):c}:e}var c,d;return c={},b("next"),b("throw",function(a){throw a}),b("return"),c[Symbol.iterator]=function(){return this},c},r=function(a){function b(b){d[b]=a[b]&&function(d){return new Promise(function(e,f){d=a[b](d),c(e,f,d.done,d.value)})}}function c(a,b,c,d){Promise.resolve(d).then(function(b){a({value:b,done:c})},b)}if(!Symbol.asyncIterator)throw new TypeError("Symbol.asyncIterator is not defined.");var d,e=a[Symbol.asyncIterator];return e?e.call(a):(a="function"==typeof n?n(a):a[Symbol.iterator](),d={},b("next"),b("throw"),b("return"),d[Symbol.asyncIterator]=function(){return this},d)},t=function(a,b){return Object.defineProperty?Object.defineProperty(a,"raw",{value:b}):a.raw=b,a},u=function(a){if(a&&a.__esModule)return a;var b={};if(null!=a)for(var c in a)Object.hasOwnProperty.call(a,c)&&(b[c]=a[c]);return b["default"]=a,b},v=function(a){return a&&a.__esModule?a:{default:a}},a("__extends",d),a("__assign",e),a("__rest",f),a("__decorate",g),a("__param",h),a("__metadata",i),a("__awaiter",j),a("__generator",k),a("__exportStar",l),a("__values",n),a("__read",m),a("__spread",o),a("__await",s),a("__asyncGenerator",p),a("__asyncDelegator",q),a("__asyncValues",r),a("__makeTemplateObject",t),a("__importStar",u),a("__importDefault",v)})}).call(this,"undefined"==typeof global?"undefined"==typeof self?"undefined"==typeof window?{}:window:self:global)},{}]},{},[1])(1)});
(function(a){if("object"==typeof exports&&"undefined"!=typeof module)module.exports=a();else if("function"==typeof define&&define.amd)define([],a);else{var b;b="undefined"==typeof window?"undefined"==typeof global?"undefined"==typeof self?this:self:global:window,b.IncrementalCycleDetect=a()}})(function(){var a;return function(){function b(d,e,g){function a(j,i){if(!e[j]){if(!d[j]){var f="function"==typeof require&&require;if(!i&&f)return f(j,!0);if(h)return h(j,!0);var c=new Error("Cannot find module '"+j+"'");throw c.code="MODULE_NOT_FOUND",c}var k=e[j]={exports:{}};d[j][0].call(k.exports,function(b){var c=d[j][1][b];return a(c||b)},k,k.exports,b,d,e,g)}return e[j].exports}for(var h="function"==typeof require&&require,c=0;c<g.length;c++)a(g[c]);return a}return b}()({1:[function(a,b,c){"use strict";Object.defineProperty(c,"__esModule",{value:!0});var d=a("tslib");d.__exportStar(a("./src/GraphlibAdapter"),c),d.__exportStar(a("./src/GenericGraphAdapter"),c),d.__exportStar(a("./src/MultiGraphAdapter"),c),d.__exportStar(a("./src/PearceKellyDetector"),c)},{"./src/GenericGraphAdapter":2,"./src/GraphlibAdapter":3,"./src/MultiGraphAdapter":4,"./src/PearceKellyDetector":5,tslib:7}],2:[function(a,b,c){"use strict";Object.defineProperty(c,"__esModule",{value:!0});var d=a("./PearceKellyDetector"),e=a("./util"),f=function(){function a(a){void 0===a&&(a={});var b=a.mapConstructor||Map;this.detector=a.cycleDetector||new d.PearceKellyDetector,this.forward=new b,this.backward=new b,this.mapConstructor=b,this.vertices=new b,this.edgeCount=0,this.adapter={getData:this.getData.bind(this),getPredecessorsOf:this.getPredecessorsOf.bind(this),getSuccessorsOf:this.getSuccessorsOf.bind(this)}}return a.prototype.canContractEdge=function(a,b){return e.canContractEdge(this,a,b)},a.prototype.contractEdge=function(a,b,c,d){return e.contractEdge(this,a,b,c,d)},a.prototype.isReachable=function(a,b){return this.detector.isReachable(this.adapter,a,b)},a.prototype.getSuccessorsOf=function(a){var b=this.forward.get(a);return void 0===b?e.EmptyIterator:b.keys()},a.prototype.getPredecessorsOf=function(a){var c=this.backward.get(a);return void 0===c?e.EmptyIterator:c.keys()},a.prototype.getVertices=function(){return this.vertices.keys()},a.prototype.getEdgeData=function(a,b){var c=this.forward.get(a);return c?c.get(b):void 0},a.prototype.setEdgeData=function(a,b,c){var d=this.forward.get(a);return!!(d&&d.has(b))&&(d.set(b,c),!0)},a.prototype.getEdges=function(){return e.createFlatMappedIterator(this.forward.entries(),function(a){return e.createMappedIterator(a[1].keys(),function(b){return[a[0],b]})})},a.prototype.getEdgeCount=function(){return this.edgeCount},a.prototype.supportsOrder=function(){return this.detector.supportsOrder()},a.prototype.getOrder=function(a){return this.detector.getOrder(this.adapter,a)},a.prototype.getVertexCount=function(){return this.vertices.size},a.prototype.hasEdge=function(a,b){var c=this.forward.get(a);return!!c&&c.has(b)},a.prototype.hasVertex=function(a){return this.vertices.has(a)},a.prototype.addEdge=function(a,c,d){var e=this.forward.get(a),g=this.backward.get(c),h=this.addVertex(a),i=this.addVertex(c);return(e||this.forward.set(a,e=new this.mapConstructor),g||this.backward.set(c,g=new this.mapConstructor),e.has(c)||!this.detector.canAddEdge(this.adapter,a,c))?(h&&this.deleteVertex(a),i&&this.deleteVertex(c),!1):(e.set(c,d),g.set(a,!0),this.edgeCount+=1,!0)},a.prototype.addVertex=function(a){return!this.vertices.has(a)&&(this.vertices.set(a,this.detector.createVertexData(this.adapter,a)),!0)},a.prototype.deleteEdge=function(a,c){var d=this.forward.get(a),e=this.backward.get(c);return!!(d&&e)&&!!(d.delete(c)&&e.delete(a))&&(this.edgeCount-=1,!0)},a.prototype.deleteVertex=function(a){if(!this.vertices.has(a))return!1;this.detector.onVertexDeletion(this.adapter,a);for(var b=this.getSuccessorsOf(a),c=b.next();!c.done;c=b.next())this.deleteEdge(a,c.value);for(var d=this.getPredecessorsOf(a),c=d.next();!c.done;c=d.next())this.deleteEdge(c.value,a);return this.vertices.delete(a),!0},a.prototype.getData=function(a){return this.vertices.get(a)},a}();c.GenericGraphAdapter=f},{"./PearceKellyDetector":5,"./util":6}],3:[function(a,b,c){"use strict";Object.defineProperty(c,"__esModule",{value:!0});var d=a("./PearceKellyDetector"),e=a("./util"),f=function(){function a(a){this.g=new a.graphlib(e.assign({directed:!0},a.graphOptions)),this.detector=a.cycleDetector||new d.PearceKellyDetector,this.adapter={getData:this.getData.bind(this),getPredecessorsOf:this.getPredecessorsOf.bind(this),getSuccessorsOf:this.getSuccessorsOf.bind(this)}}return a.prototype.canContractEdge=function(a,b){return e.canContractEdge(this,a,b)},a.prototype.contractEdge=function(a,b,c,d){return e.contractEdge(this,a,b,c,d)},a.prototype.isReachable=function(a,b){return this.detector.isReachable(this.adapter,a,b)},a.prototype.getSuccessorsOf=function(a){var b=this.g.successors(a);return b?e.createArrayIterator(b):e.EmptyIterator},a.prototype.getPredecessorsOf=function(a){var b=this.g.predecessors(a);return b?e.createArrayIterator(b):e.EmptyIterator},a.prototype.hasEdge=function(a,b){return this.g.hasEdge(a,b)},a.prototype.hasVertex=function(a){return this.g.hasNode(a)},a.prototype.getVertexCount=function(){return this.g.nodeCount()},a.prototype.getEdgeCount=function(){return this.g.edgeCount()},a.prototype.getVertexData=function(a){return this.g.node(a)},a.prototype.getEdgeData=function(a,b){return this.g.edge(a,b)},a.prototype.setEdgeData=function(a,b,c){return!!this.g.hasEdge(a,b)&&(this.g.setEdge(a,b,c),!0)},a.prototype.getVertices=function(){return e.createArrayIterator(this.g.nodes())},a.prototype.getEdges=function(){return e.createMappedArrayIterator(this.g.edges(),function(a){return[a.v,a.w]})},a.prototype.supportsOrder=function(){return this.detector.supportsOrder()},a.prototype.getOrder=function(a){return this.detector.getOrder(this.adapter,a)},Object.defineProperty(a.prototype,"graph",{get:function(){return this.g},enumerable:!0,configurable:!0}),a.prototype.addEdge=function(a,b,c){if(this.g.hasEdge(a,b))return!1;var d=this.addVertex(a),e=this.addVertex(b);return this.detector.canAddEdge(this.adapter,a,b)?(this.g.setEdge(a,b,c),!0):(d&&this.deleteVertex(a),e&&this.deleteVertex(b),!1)},a.prototype.addVertex=function(a,b){if(this.hasVertex(a))return!1;var c=this.detector.createVertexData(this.adapter,a);return this.g.setNode(a,void 0===b?c:e.assign(c,b)),!0},a.prototype.deleteEdge=function(a,b,c){return!!this.g.hasEdge(a,b,c)&&(this.g.removeEdge(a,b),!0)},a.prototype.deleteVertex=function(a){return!!this.g.hasNode(a)&&(this.detector.onVertexDeletion(this.adapter,a),this.g.removeNode(a),!0)},a.prototype.getData=function(a){return this.g.node(a)},a}();c.GraphlibAdapter=f},{"./PearceKellyDetector":5,"./util":6}],4:[function(a,b,c){"use strict";function d(a){return void 0===a&&(a=f.takeFirst),function(b,c){if(void 0===b)return c;if(void 0===c)return b;for(var d,e=c.entries(),f=e.next();!f.done;f=e.next())d=b.get(f.value[0]),d=void 0===d?f.value[1]:a(d,f.value[1]),b.set(f.value[0],d);return b}}Object.defineProperty(c,"__esModule",{value:!0});var e=a("./GenericGraphAdapter"),f=a("./util"),g=function(){function a(a){void 0===a&&(a={}),this.g=new e.GenericGraphAdapter(a),this.edgeCount=0}return a.prototype.addLabeledEdge=function(a,b,c,d){return this.addEdge(a,b,d,c)},a.prototype.addEdge=function(a,b,c,d){var e=this.g.getEdgeData(a,b);if(void 0!==e)return!e.has(d)&&(e.set(d,c),this.edgeCount+=1,!0);this.edgeCount+=1;var f=new Map;return f.set(d,c),this.g.addEdge(a,b,f)},a.prototype.addVertex=function(a){return this.g.addVertex(a)},a.prototype.contractEdge=function(a,b,c,e){return this.g.contractEdge(a,b,c,d(e))},a.prototype.canContractEdge=function(a,b){return this.g.canContractEdge(a,b)},a.prototype.deleteEdge=function(a,b,c){if(void 0===c)return this.edgeCount-=this.getEdgeCountBetween(a,b),this.g.deleteEdge(a,b);var d=this.g.getEdgeData(a,b);if(void 0===d)return!1;var e=d.delete(c);return e&&(this.edgeCount-=1),0===d.size&&this.g.deleteEdge(a,b),e},a.prototype.deleteVertex=function(a){return this.g.deleteVertex(a)},a.prototype.getLabeledEdgeCount=function(){return this.edgeCount},a.prototype.getEdgeCount=function(){return this.g.getEdgeCount()},a.prototype.getEdgeData=function(a,b,c){var d=this.g.getEdgeData(a,b);return void 0===d?void 0:d.get(c)},a.prototype.setEdgeData=function(a,b,c,e){var f=this.g.getEdgeData(a,b);return!!(void 0!==f&&f.has(e))&&(f.set(e,c),!0)},a.prototype.getEdges=function(){return this.g.getEdges()},a.prototype.getEdgeCountBetween=function(a,b){var c=this.g.getEdgeData(a,b);return void 0===c?0:c.size},a.prototype.getEdgeLabels=function(a,b){var c=this.g.getEdgeData(a,b);return void 0===c?f.EmptyIterator:c.keys()},a.prototype.getLabeledEdges=function(){var a=this;return f.createFlatMappedIterator(this.g.getEdges(),function(b){var c=a.g.getEdgeData(b[0],b[1]);return void 0===c?f.EmptyIterator:f.createMappedIterator(c.keys(),function(a){return[b[0],b[1],a]})})},a.prototype.getPredecessorsOf=function(a,b){var c=this;return void 0===b?this.g.getPredecessorsOf(a):f.createFilteredIterator(this.g.getPredecessorsOf(a),function(d){var e=c.g.getEdgeData(d,a);return void 0!==e&&e.has(b)})},a.prototype.getSuccessorsOf=function(a,b){var c=this;return void 0===b?this.g.getSuccessorsOf(a):f.createFilteredIterator(this.g.getSuccessorsOf(a),function(d){var e=c.g.getEdgeData(a,d);return void 0!==e&&e.has(b)})},a.prototype.getOrder=function(a){return this.g.getOrder(a)},a.prototype.supportsOrder=function(){return this.g.supportsOrder()},a.prototype.getVertexCount=function(){return this.g.getVertexCount()},a.prototype.getVertices=function(){return this.g.getVertices()},a.prototype.hasEdge=function(a,b,c){var d=this.g.getEdgeData(a,b);return void 0!==d&&(void 0===c||d.has(c))},a.prototype.hasLabeledEdge=function(a,b,c){var d=this.g.getEdgeData(a,b);return void 0!==d&&d.has(c)},a.prototype.hasVertex=function(a){return this.g.hasVertex(a)},a.prototype.isReachable=function(a,b){return this.g.isReachable(a,b)},a}();c.MultiGraphAdapter=g},{"./GenericGraphAdapter":2,"./util":6}],5:[function(a,b,c){"use strict";function d(a,b,c){for(var d=[],e=b.length,f=c.length,g=0,h=0;g<e&&h<f;){var i=a.getData(b[g]).order,j=a.getData(c[h]).order;i<j?(g+=1,d.push(i)):(h+=1,d.push(j))}for(;g<e;){var i=a.getData(b[g]);g+=1,d.push(i.order)}for(;h<f;){var j=a.getData(c[h]);h+=1,d.push(j.order)}return d}function e(a,b){return b.map(function(b){return{key:a.getData(b).order,val:b}}).sort(function(a,b){return a.key-b.key}).map(function(a){return a.val})}Object.defineProperty(c,"__esModule",{value:!0});var f=function(){function a(){this.id=0,this.stack=[],this.deltaXyB=[],this.deltaXyF=[],this.freeStack=[]}return a.prototype.isReachable=function(a,b,c){if(b===c)return!0;var d=a.getData(c).order;if(a.getData(b).order>d)return!1;var e=!this.dfs_f(b,a,d);return this.cleanAfterCycle(a),e},a.prototype.createVertexData=function(){var a=this.freeStack.pop();return{order:void 0===a?this.id++:a,visited:!1}},a.prototype.onVertexDeletion=function(a,b){var c=a.getData(b);this.freeStack.push(c.order)},a.prototype.canAddEdge=function(a,b,c){return b!==c&&this.checkCycle(a,b,c)},a.prototype.supportsOrder=function(){return!0},a.prototype.getOrder=function(a,b){return a.getData(b).order},a.prototype.checkCycle=function(a,b,c){var d=a.getData(c).order,e=a.getData(b).order;if(this.deltaXyB=[],this.deltaXyF=[],d<e){if(!this.dfs_f(c,a,e))return this.cleanAfterCycle(a),!1;this.dfs_b(b,a,d),this.reorder(a)}return!0},a.prototype.cleanAfterCycle=function(a){this.stack=[];for(var b=this.deltaXyF.pop();void 0!==b;b=this.deltaXyF.pop())a.getData(b).visited=!1},a.prototype.dfs_f=function(a,b,c){for(this.stack.push(a);0<this.stack.length;){var d=this.stack.pop(),e=b.getData(d);if(!e.visited){e.visited=!0,this.deltaXyF.push(d);for(var f,g=b.getSuccessorsOf(d),h=g.next();!h.done;h=g.next()){if(f=b.getData(h.value),f.order===c)return!1;!f.visited&&f.order<c&&this.stack.push(h.value)}}}return!0},a.prototype.dfs_b=function(a,b,c){for(this.stack.push(a);0<this.stack.length;){var d=this.stack.pop(),e=b.getData(d);if(!e.visited){e.visited=!0,this.deltaXyB.push(d);for(var f,g=b.getPredecessorsOf(d),h=g.next();!h.done;h=g.next())f=b.getData(h.value),!f.visited&&c<f.order&&this.stack.push(h.value)}}},a.prototype.reorder=function(a){this.deltaXyB=e(a,this.deltaXyB),this.deltaXyF=e(a,this.deltaXyF);for(var b,c=this.deltaXyB.concat(this.deltaXyF),f=0,g=c;f<g.length;f++)b=g[f],a.getData(b).visited=!1;for(var h=d(a,this.deltaXyB,this.deltaXyF),k=0,l=c.length;k<l;++k)a.getData(c[k]).order=h[k]},a}();c.PearceKellyDetector=f},{}],6:[function(a,b,c){"use strict";function d(a){return a}function e(a,b,c,e,f){void 0===e&&(e=d);var g=[],h=[];if(f!==b){for(var i,j=a.getSuccessorsOf(b),k=j.next();!k.done;k=j.next())i=a.getEdgeData(b,k.value),a.deleteEdge(b,k.value),g.push([k.value,i]);for(var i,l=a.getPredecessorsOf(b),k=l.next();!k.done;k=l.next())i=a.getEdgeData(k.value,b),a.deleteEdge(k.value,b),h.push([k.value,i])}if(f!==c){for(var i,m=a.getSuccessorsOf(c),k=m.next();!k.done;k=m.next())i=a.getEdgeData(c,k.value),a.deleteEdge(c,k.value),g.push([k.value,i]);for(var i,n=a.getPredecessorsOf(c),k=n.next();!k.done;k=n.next())i=a.getEdgeData(k.value,c),a.deleteEdge(k.value,c),h.push([k.value,i])}f!==b&&f!==c&&a.addVertex(f);for(var o=0,p=g;o<p.length;o++){var q=p[o],i=a.getEdgeData(f,q[0]);i===void 0?a.addEdge(f,q[0],q[1]):a.setEdgeData(f,q[0],e(i,q[1]))}for(var r=0,s=h;r<s.length;r++){var q=s[r],i=a.getEdgeData(q[0],f);i===void 0?a.addEdge(q[0],f,q[1]):a.setEdgeData(q[0],f,e(i,q[1]))}f!==c&&a.deleteVertex(c),f!==b&&a.deleteVertex(b)}Object.defineProperty(c,"__esModule",{value:!0}),c.takeFirst=d,c.DoneIteratorResult={done:!0,value:void 0},c.EmptyIterator={next:function(){return c.DoneIteratorResult}};var f=Object.prototype.hasOwnProperty;c.assign=function(a,b){for(var c in b)f.call(b,c)&&(a[c]=b[c]);return a},c.toArray=function(a){for(var b=[],c=a.next();!c.done;c=a.next())b.push(c.value);return b},c.createMappedIterator=function(a,b){return{next:function(){var d=a.next();return d.done?c.DoneIteratorResult:{done:!1,value:b(d.value)}}}},c.createFilteredIterator=function(a,b){return{next:function(){for(var c=a.next();!c.done&&!b(c.value);)c=a.next();return c}}},c.createFlatMappedIterator=function(a,b){var d=c.EmptyIterator;return{next:function(){for(var e=d.next();e.done;){var f=a.next();if(f.done)return c.DoneIteratorResult;d=b(f.value),e=d.next()}return{done:!1,value:e.value}}}},c.createArrayIterator=function(a){var b=0;return{array:a,next:function(){for(;a[b]===void 0;){if(b>a.length)return c.DoneIteratorResult;b+=1}return{done:!1,value:a[b++]}}}},c.createMappedArrayIterator=function(a,b){var d=0;return{next:function(){for(;a[d]===void 0;){if(d>a.length)return c.DoneIteratorResult;d+=1}return{done:!1,value:b(a[d++])}}}},c.canContractEdge=function(a,b,c){if(!a.hasEdge(b,c))return!1;var d=a.getEdgeData(b,c);a.deleteEdge(b,c);var e=!a.isReachable(b,c);return a.addEdge(b,c,d),e},c.contractEdge=function(a,b,c,f,g){if(void 0===f&&(f=d),!a.hasEdge(b,c))return!1;var h=a.getEdgeData(b,c);if(a.deleteEdge(b,c),a.isReachable(b,c))return a.addEdge(b,c,h),!1;var i=f(b,c);if(i!==b&&i!==c&&a.hasVertex(i))throw a.addEdge(b,c,h),new Error("Cannot use existing vertex for edge contraction: "+i);return e(a,b,c,g,i),!0}},{}],7:[function(b,c){(function(b){var d,e,f,g,h,i,j,k,l,n,m,o,s,p,q,r,t,u,v;(function(d){function e(a,b){return a!==f&&("function"==typeof Object.create?Object.defineProperty(a,"__esModule",{value:!0}):a.__esModule=!0),function(c,d){return a[c]=b?b(c,d):d}}var f="object"==typeof b?b:"object"==typeof self?self:"object"==typeof this?this:{};"function"==typeof a&&a.amd?a("tslib",["exports"],function(a){d(e(f,e(a)))}):"object"==typeof c&&"object"==typeof c.exports?d(e(f,e(c.exports))):d(e(f))})(function(a){var c=Object.setPrototypeOf||{__proto__:[]}instanceof Array&&function(a,c){a.__proto__=c}||function(a,c){for(var b in c)c.hasOwnProperty(b)&&(a[b]=c[b])};d=function(a,d){function b(){this.constructor=a}c(a,d),a.prototype=null===d?Object.create(d):(b.prototype=d.prototype,new b)},e=Object.assign||function(a){for(var b,c=1,d=arguments.length;c<d;c++)for(var e in b=arguments[c],b)Object.prototype.hasOwnProperty.call(b,e)&&(a[e]=b[e]);return a},f=function(a,b){var c={};for(var d in a)Object.prototype.hasOwnProperty.call(a,d)&&0>b.indexOf(d)&&(c[d]=a[d]);if(null!=a&&"function"==typeof Object.getOwnPropertySymbols)for(var e=0,d=Object.getOwnPropertySymbols(a);e<d.length;e++)0>b.indexOf(d[e])&&(c[d[e]]=a[d[e]]);return c},g=function(a,b,e,f){var g,h=arguments.length,c=3>h?b:null===f?f=Object.getOwnPropertyDescriptor(b,e):f;if("object"==typeof Reflect&&"function"==typeof Reflect.decorate)c=Reflect.decorate(a,b,e,f);else for(var j=a.length-1;0<=j;j--)(g=a[j])&&(c=(3>h?g(c):3<h?g(b,e,c):g(b,e))||c);return 3<h&&c&&Object.defineProperty(b,e,c),c},h=function(a,b){return function(c,d){b(c,d,a)}},i=function(a,b){if("object"==typeof Reflect&&"function"==typeof Reflect.metadata)return Reflect.metadata(a,b)},j=function(a,b,c,d){return new(c||(c=Promise))(function(e,f){function g(a){try{i(d.next(a))}catch(a){f(a)}}function h(a){try{i(d["throw"](a))}catch(a){f(a)}}function i(a){a.done?e(a.value):new c(function(b){b(a.value)}).then(g,h)}i((d=d.apply(a,b||[])).next())})},k=function(a,b){function c(a){return function(b){return d([a,b])}}function d(c){if(e)throw new TypeError("Generator is already executing.");for(;k;)try{if(e=1,h&&(i=2&c[0]?h["return"]:c[0]?h["throw"]||((i=h["return"])&&i.call(h),0):h.next)&&!(i=i.call(h,c[1])).done)return i;switch((h=0,i)&&(c=[2&c[0],i.value]),c[0]){case 0:case 1:i=c;break;case 4:return k.label++,{value:c[1],done:!1};case 5:k.label++,h=c[1],c=[0];continue;case 7:c=k.ops.pop(),k.trys.pop();continue;default:if((i=k.trys,!(i=0<i.length&&i[i.length-1]))&&(6===c[0]||2===c[0])){k=0;continue}if(3===c[0]&&(!i||c[1]>i[0]&&c[1]<i[3])){k.label=c[1];break}if(6===c[0]&&k.label<i[1]){k.label=i[1],i=c;break}if(i&&k.label<i[2]){k.label=i[2],k.ops.push(c);break}i[2]&&k.ops.pop(),k.trys.pop();continue;}c=b.call(a,k)}catch(a){c=[6,a],h=0}finally{e=i=0}if(5&c[0])throw c[1];return{value:c[0]?c[1]:void 0,done:!0}}var e,h,i,j,k={label:0,sent:function(){if(1&i[0])throw i[1];return i[1]},trys:[],ops:[]};return j={next:c(0),throw:c(1),return:c(2)},"function"==typeof Symbol&&(j[Symbol.iterator]=function(){return this}),j},l=function(a,b){for(var c in a)b.hasOwnProperty(c)||(b[c]=a[c])},n=function(a){var b="function"==typeof Symbol&&a[Symbol.iterator],c=0;return b?b.call(a):{next:function(){return a&&c>=a.length&&(a=void 0),{value:a&&a[c++],done:!a}}}},m=function(a,b){var c="function"==typeof Symbol&&a[Symbol.iterator];if(!c)return a;var d,f,g=c.call(a),h=[];try{for(;(void 0===b||0<b--)&&!(d=g.next()).done;)h.push(d.value)}catch(a){f={error:a}}finally{try{d&&!d.done&&(c=g["return"])&&c.call(g)}finally{if(f)throw f.error}}return h},o=function(){for(var a=[],b=0;b<arguments.length;b++)a=a.concat(m(arguments[b]));return a},s=function(a){return this instanceof s?(this.v=a,this):new s(a)},p=function(a,b,c){function d(c){m[c]&&(l[c]=function(d){return new Promise(function(f,a){1<g.push([c,d,f,a])||e(c,d)})})}function e(a,b){try{f(m[a](b))}catch(a){k(g[0][3],a)}}function f(a){a.value instanceof s?Promise.resolve(a.value.v).then(h,j):k(g[0][2],a)}function h(a){e("next",a)}function j(a){e("throw",a)}function k(a,b){(a(b),g.shift(),g.length)&&e(g[0][0],g[0][1])}if(!Symbol.asyncIterator)throw new TypeError("Symbol.asyncIterator is not defined.");var l,m=c.apply(a,b||[]),g=[];return l={},d("next"),d("throw"),d("return"),l[Symbol.asyncIterator]=function(){return this},l},q=function(a){function b(b,e){c[b]=a[b]?function(c){return(d=!d)?{value:s(a[b](c)),done:"return"===b}:e?e(c):c}:e}var c,d;return c={},b("next"),b("throw",function(a){throw a}),b("return"),c[Symbol.iterator]=function(){return this},c},r=function(a){function b(b){d[b]=a[b]&&function(d){return new Promise(function(e,f){d=a[b](d),c(e,f,d.done,d.value)})}}function c(a,b,c,d){Promise.resolve(d).then(function(b){a({value:b,done:c})},b)}if(!Symbol.asyncIterator)throw new TypeError("Symbol.asyncIterator is not defined.");var d,e=a[Symbol.asyncIterator];return e?e.call(a):(a="function"==typeof n?n(a):a[Symbol.iterator](),d={},b("next"),b("throw"),b("return"),d[Symbol.asyncIterator]=function(){return this},d)},t=function(a,b){return Object.defineProperty?Object.defineProperty(a,"raw",{value:b}):a.raw=b,a},u=function(a){if(a&&a.__esModule)return a;var b={};if(null!=a)for(var c in a)Object.hasOwnProperty.call(a,c)&&(b[c]=a[c]);return b["default"]=a,b},v=function(a){return a&&a.__esModule?a:{default:a}},a("__extends",d),a("__assign",e),a("__rest",f),a("__decorate",g),a("__param",h),a("__metadata",i),a("__awaiter",j),a("__generator",k),a("__exportStar",l),a("__values",n),a("__read",m),a("__spread",o),a("__await",s),a("__asyncGenerator",p),a("__asyncDelegator",q),a("__asyncValues",r),a("__makeTemplateObject",t),a("__importStar",u),a("__importDefault",v)})}).call(this,"undefined"==typeof global?"undefined"==typeof self?"undefined"==typeof window?{}:window:self:global)},{}]},{},[1])(1)});

16

dist/src/PearceKellyDetector.js

@@ -48,10 +48,8 @@ "use strict";

}
var tOrder = adapter.getData(target).order;
if (adapter.getData(source).order > tOrder) {
var targetOrder = adapter.getData(target).order;
if (adapter.getData(source).order > targetOrder) {
return false;
}
var reachable = !this.dfs_f(source, adapter, tOrder);
if (reachable) {
this.cleanAfterCycle(adapter);
}
var reachable = !this.dfs_f(source, adapter, targetOrder);
this.cleanAfterCycle(adapter);
return reachable;

@@ -76,2 +74,8 @@ };

};
PearceKellyDetector.prototype.supportsOrder = function () {
return true;
};
PearceKellyDetector.prototype.getOrder = function (g, vertex) {
return g.getData(vertex).order;
};
PearceKellyDetector.prototype.checkCycle = function (adapter, x, y) {

@@ -78,0 +82,0 @@ var lb = adapter.getData(y).order;

32

package.json
{
"name": "incremental-cycle-detect",
"version": "0.1.1",
"version": "0.2.0",
"description": "Keeps a directed acyclic graph topologically sorted each time you add an edge or vertex to check for cycles.",
"main": "dist/main.js",
"main": "dist/index.js",
"scripts": {

@@ -13,6 +13,6 @@ "perf": "npx ts-node perf/insert",

"doc-create": "npx typedoc --mode file --name js-incremental-cycle-detect --readme README.md --out docs --excludeExternals --excludePrivate --excludeNotExported --excludeProtected --ignoreCompilerErrors --theme minimal src",
"clean": "rm -rf main.js main.d.ts docs coverage dist",
"clean": "rm -rf index.js index.d.ts docs coverage dist",
"transpile": "npx tsc -p tsconfig.json",
"lint": "npx tslint -c tslint.json main.ts",
"browserify": "npx browserify dist/main.js --standalone IncrementalCycleDetect -o dist/browser.js",
"lint": "npx tslint -c tslint.json index.ts",
"browserify": "npx browserify dist/index.js --standalone IncrementalCycleDetect -o dist/browser.js",
"minify": "npx minify dist/browser.js --out-file dist/browser.min.js",

@@ -24,3 +24,3 @@ "prepublishOnly": "npm run build",

},
"types": "./main.d.ts",
"types": "./index.d.ts",
"repository": {

@@ -31,3 +31,10 @@ "type": "git",

"keywords": [
"graph,directed graph,acyclic graph,dag,cycle,cycle detection"
"graph",
"graphs",
"directed",
"acyclic",
"dag",
"cycle",
"cyclic",
"cycle detection"
],

@@ -54,15 +61,14 @@ "author": "Andre Wachsmuth",

"mocha-typescript": "^1.1.14",
"nyc": "^11.8.0",
"nyc": "^12.0.2",
"random-js": "^1.0.8",
"ts-mocha": "^1.2.0",
"ts-node": "^6.0.5",
"ts-node": "^6.1.0",
"tslib": "^1.9.2",
"tslint": "^5.10.0",
"tslint-strict-null-checks": "^1.0.1",
"typedoc": "^0.11.1",
"typescript": "^2.8.3"
"typescript": "^2.9.1"
},
"homepage": "https://github.com/blutorange/js-incremental-cycle-detect#readme",
"dependencies": {
"tslib": "^1.9.1"
}
"dependencies": {}
}

59

README.md

@@ -27,3 +27,3 @@ Lets you add edges to a [directed acyclic graph](https://en.wikipedia.org/wiki/Directed_acyclic_graph) and be told whether this edge

Typings for [Typescript](https://www.typescriptlang.org/) are available (this is written in typescript!).
Typings for [Typescript](https://www.typescriptlang.org/) are available (this is written in typescript).

@@ -41,3 +41,3 @@ Use the `dist.js` or `dist.min.js` for [browser usage](http://browserify.org/) if you must.

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

@@ -57,9 +57,15 @@ ```javascript

The main algorithm is implemented by `CycleDetectorImpl`. To allow for this lib to work with different graph
data structures, it is subclassed. The subclass is called `...Adapter` responsible for storing the vertex and edge data.
For convenience, the following adapters are provided and all implement [CommonAdapter](https://blutorange.github.io/js-incremental-cycle-detect/interfaces/commonadapter.html)
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](https://blutorange.github.io/js-incremental-cycle-detect/interfaces/graphadapter.html) 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](https://blutorange.github.io/js-incremental-cycle-detect/interfaces/commonadapter.html):
- [GenericGraphAdapter](https://blutorange.github.io/js-incremental-cycle-detect/classes/genericgraphadapter.html): 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.
- [GraphlibAdapter](https://blutorange.github.io/js-incremental-cycle-detect/classes/graphlibadapter.html): For the npm module [graphlib](https://www.npmjs.com/package/graphlib). Vertices are strings.
- [MultiGraphAdapter](https://blutorange.github.io/js-incremental-cycle-detect/classes/multigraphadapter.html) Similar to `GenericGraphAdapter`, but allows for multiple edges between two vertices. Edges are identified by an additional label.
- [GraphlibAdapter](https://blutorange.github.io/js-incremental-cycle-detect/classes/graphlibadapter.html): For the npm module [graphlib](https://www.npmjs.com/package/graphlib). Vertices are strings. Does not support multigraphs currently.
Example for using the GraphlibAdapter:
```javascript

@@ -82,8 +88,10 @@ const { Graph } = require("graphlib");

```
// 200 vertices, 15000 random (same for each algorithm) edges added
incremental-cycle-detection(insert 15000, RandomSource) x 36.51 ops/sec ±4.53% (59 runs sampled)
graphlib(insert15000, RandomSource) x 0.18 ops/sec ±2.78% (5 runs sampled)
```
> **incremental-cycle-detection**(insert 15000, RandomSource) x **36.43** ops/sec ±0.79% (58 runs sampled)
>
> **incremental-cycle-detection-multi**(insert 15000, RandomSource) x **25.71** ops/sec ±10.12% (45 runs sampled)
>
> **graphlib**(insert15000, RandomSource) x **0.17** ops/sec ±1.63% (5 runs sampled)
(200 vertices, 15000 random (same for each algorithm) edges added)
# JavaScript environment

@@ -95,3 +103,3 @@

- [polyfill](https://en.wikipedia.org/wiki/Polyfill_%28programming%29) [Map](https://www.npmjs.com/package/core-js)
- pass an implementation of Mapt to the constructor of the graph adapter. This way you don't have to [monkey patch](https://stackoverflow.com/questions/5741877/is-monkey-patching-really-that-bad):
- pass an implementation of `Map` to the constructor of the graph adapter. This way you don't have to [monkey patch](https://stackoverflow.com/questions/5741877/is-monkey-patching-really-that-bad):

@@ -105,7 +113,8 @@ ```javascript

You can also use the CycleDetector (implemented by `PearceKellyDetector`) directly and
As mentioned above, You can also use the CycleDetector (implemented by `PearceKellyDetector`) directly and
roll your own graph data structure. See the [docs](https://blutorange.github.io/js-incremental-cycle-detect/classes/pearcekellydetector.html).
Basically, you need to call the `CycleDetector` every time you add an edge or delete a vertex. Then it tells you
whether adding an edge is allowed. You can also use an existing `GraphAdapter` as the starting point.
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

@@ -122,2 +131,11 @@

# Test
```sh
git clone https://github.com/blutorange/js-incremental-cycle-detect
cd js-incremental-cycle-detection
npm install
npm run test
```
# Change log

@@ -133,3 +151,12 @@

# 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 Initial version.
# 0.1.0
- 0.1.0 Initial version.
.babelrc
dist/main.js
dist/src/GraphAdapter.js
SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc