Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
Socket
Sign inDemoInstall
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.2.2 to 0.3.0

dist/src/Algorithm.d.ts
dist/src/Algorithm.js

486

dist/browser.js

@@ -5,17 +5,67 @@ (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/Algorithm"), exports);
tslib_1.__exportStar(require("./src/GenericGraphAdapter"), 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/GenericGraphAdapter":2,"./src/GraphlibAdapter":3,"./src/MultiGraphAdapter":4,"./src/PearceKellyDetector":5,"tslib":7}],2:[function(require,module,exports){
},{"./src/Algorithm":2,"./src/GenericGraphAdapter":3,"./src/GraphlibAdapter":4,"./src/MultiGraphAdapter":5,"./src/PearceKellyDetector":6,"tslib":8}],2:[function(require,module,exports){
"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
var util_1 = require("./util");
var Algorithm = (function () {
function Algorithm() {
}
Algorithm.findWeaklyConnectedComponents = function (graph, setConstructor) {
if (setConstructor === void 0) { setConstructor = Set; }
var visited = new setConstructor();
var components = [];
for (var vertexIterator = graph.getVertices(), vertexResult = vertexIterator.next(); !vertexResult.done; vertexResult = vertexIterator.next()) {
if (visited.has(vertexResult.value)) {
continue;
}
var component = { edges: [], vertices: [vertexResult.value] };
var stack = [vertexResult.value];
visited.add(vertexResult.value);
while (stack.length > 0) {
var vertex = stack.pop();
for (var edgeIterator = graph.getEdgesWithDataTo(vertex), edgeResult = edgeIterator.next(); !edgeResult.done; edgeResult = edgeIterator.next()) {
var v = edgeResult.value[0];
if (visited.has(v)) {
continue;
}
visited.add(v);
component.vertices.push(v);
stack.push(v);
}
for (var edgeIterator = graph.getEdgesWithDataFrom(vertex), edgeResult = edgeIterator.next(); !edgeResult.done; edgeResult = edgeIterator.next()) {
var v = edgeResult.value[0];
component.edges.push([vertex, v, edgeResult.value[1]]);
if (visited.has(v)) {
continue;
}
visited.add(v);
component.vertices.push(v);
stack.push(v);
}
}
components.push(component);
}
return components;
};
Algorithm.getNeighbors = function (graph, vertex) {
return util_1.createChainedIterator(graph.getPredecessorsOf(vertex), graph.getSuccessorsOf(vertex));
};
return Algorithm;
}());
exports.Algorithm = Algorithm;
},{"./util":7}],3:[function(require,module,exports){
"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
var PearceKellyDetector_1 = require("./PearceKellyDetector");
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();
function GenericGraphAdapter(mapConstructor, cycleDetector) {
this.detector = cycleDetector;
this.forward = new mapConstructor();

@@ -32,2 +82,37 @@ this.backward = new mapConstructor();

}
GenericGraphAdapter.create = function (options) {
if (options === void 0) { options = {}; }
var mapConstructor = options.mapConstructor || Map;
var detector = options.cycleDetector || new PearceKellyDetector_1.PearceKellyDetector();
return new GenericGraphAdapter(mapConstructor, detector);
};
GenericGraphAdapter.prototype.map = function (vertexMapper, edgeDataMapper) {
var _this = this;
var clone = new GenericGraphAdapter(this.mapConstructor, util_1.DummyDetector);
var clonedVertexMap = new this.mapConstructor();
this.vertices.forEach(function (vertexData, vertex) {
var clonedVertex = vertexMapper(vertex);
clonedVertexMap.set(vertex, clonedVertex);
clone.vertices.set(clonedVertex, vertexData);
});
this.forward.forEach(function (map, from) {
var clonedMap = new _this.mapConstructor();
var clonedFrom = clonedVertexMap.get(from);
map.forEach(function (edgeData, to) {
var clonedTo = clonedVertexMap.get(to);
var clonedEdgeData = edgeData !== undefined ? edgeDataMapper(edgeData) : undefined;
clonedMap.set(clonedTo, clonedEdgeData);
clone.addToBackwardsMap(clonedFrom, clonedTo, clonedEdgeData);
});
clone.forward.set(clonedFrom, clonedMap);
});
clone.edgeCount = this.edgeCount;
clone.detector = this.detector.map();
return clone;
};
GenericGraphAdapter.prototype.clone = function (vertexCloner, edgeDataCloner) {
var vCloner = vertexCloner !== undefined ? vertexCloner : function (vertex) { return vertex; };
var eCloner = edgeDataCloner !== undefined ? edgeDataCloner : function (data) { return data; };
return this.map(vCloner, eCloner);
};
GenericGraphAdapter.prototype.canContractEdge = function (from, to) {

@@ -66,2 +151,9 @@ return util_1.canContractEdge(this, from, to);

};
GenericGraphAdapter.prototype.getEdgesWithDataTo = function (vertex) {
var b = this.backward.get(vertex);
if (b === undefined) {
return util_1.EmptyIterator;
}
return b.entries();
};
GenericGraphAdapter.prototype.getEdgeDataTo = function (vertex) {

@@ -72,4 +164,11 @@ var b = this.backward.get(vertex);

}
return util_1.createFilteredIterator(b.values(), function (data) { return data !== undefined; });
return util_1.createFilteredIterator(b.values());
};
GenericGraphAdapter.prototype.getEdgesWithDataFrom = function (vertex) {
var f = this.forward.get(vertex);
if (f === undefined) {
return util_1.EmptyIterator;
}
return f.entries();
};
GenericGraphAdapter.prototype.getEdgeDataFrom = function (vertex) {

@@ -80,3 +179,3 @@ var f = this.forward.get(vertex);

}
return util_1.createFilteredIterator(f.values(), function (data) { return data !== undefined; });
return util_1.createFilteredIterator(f.values());
};

@@ -98,2 +197,9 @@ GenericGraphAdapter.prototype.setEdgeData = function (from, to, data) {

};
GenericGraphAdapter.prototype.getEdgesWithData = function () {
return util_1.createFlatMappedIterator(this.forward.entries(), function (entry) {
return util_1.createMappedIterator(entry[1].entries(), function (subEntry) {
return [entry[0], subEntry[0], subEntry[1]];
});
});
};
GenericGraphAdapter.prototype.getEdgeCount = function () {

@@ -169,3 +275,3 @@ return this.edgeCount;

}
this.vertices.set(vertex, this.detector.createVertexData(this.adapter, vertex));
this.vertices.set(vertex, this.detector.createVertexData(this.adapter));
return true;

@@ -199,2 +305,9 @@ };

};
GenericGraphAdapter.prototype.addToBackwardsMap = function (from, to, edgeData) {
var map = this.backward.get(to);
if (map === undefined) {
this.backward.set(to, map = new this.mapConstructor());
}
map.set(from, edgeData);
};
GenericGraphAdapter.prototype.getData = function (key) {

@@ -207,3 +320,3 @@ return this.vertices.get(key);

},{"./PearceKellyDetector":5,"./util":6}],3:[function(require,module,exports){
},{"./PearceKellyDetector":6,"./util":7}],4:[function(require,module,exports){
"use strict";

@@ -213,12 +326,51 @@ Object.defineProperty(exports, "__esModule", { value: true });

var util_1 = require("./util");
function bind(fn, context) {
return fn.bind(context);
}
var GraphlibAdapter = (function () {
function GraphlibAdapter(options) {
this.g = new options.graphlib(util_1.assign({ directed: true }, options.graphOptions));
this.detector = options.cycleDetector || new PearceKellyDetector_1.PearceKellyDetector();
function GraphlibAdapter(g, detector, graphlib) {
this.graphlib = graphlib;
this.g = g;
this.detector = detector;
this.adapter = {
getData: this.getData.bind(this),
getPredecessorsOf: this.getPredecessorsOf.bind(this),
getSuccessorsOf: this.getSuccessorsOf.bind(this),
getData: bind(this.getData, this),
getPredecessorsOf: bind(this.getPredecessorsOf, this),
getSuccessorsOf: bind(this.getSuccessorsOf, this),
};
}
GraphlibAdapter.create = function (options) {
var g = new options.graphlib(util_1.assign(options.graphOptions || {}, { directed: true }));
var detector = options.cycleDetector || new PearceKellyDetector_1.PearceKellyDetector();
return new GraphlibAdapter(g, detector, options.graphlib);
};
GraphlibAdapter.prototype.map = function (vertexDataMapper, edgeDataMapper) {
var clonedG = new this.graphlib({
compound: this.g.isCompound(),
directed: this.g.isDirected(),
multigraph: this.g.isMultigraph(),
});
for (var _i = 0, _a = this.g.nodes(); _i < _a.length; _i++) {
var node = _a[_i];
var vertexData = this.g.node(node);
var partialVertexData = vertexDataMapper(vertexData);
if (partialVertexData.gid === undefined) {
partialVertexData.gid = vertexData.gid;
}
partialVertexData.order = vertexData.order;
partialVertexData.visited = vertexData.visited;
clonedG.setNode(partialVertexData.gid, partialVertexData);
}
for (var _b = 0, _c = this.g.edges(); _b < _c.length; _b++) {
var edge = _c[_b];
var edgeData = this.g.edge(edge);
clonedG.setEdge(edge.v, edge.w, edgeData !== undefined ? edgeDataMapper(edgeData) : undefined, edge.name);
}
var clonedDetector = this.detector.map();
return new GraphlibAdapter(clonedG, clonedDetector, this.graphlib);
};
GraphlibAdapter.prototype.clone = function (vertexDataCloner, edgeDataCloner) {
var vCloner = vertexDataCloner !== undefined ? vertexDataCloner : function (vertex) { return vertex; };
var eCloner = edgeDataCloner !== undefined ? edgeDataCloner : function (data) { return data; };
return this.map(vCloner, eCloner);
};
GraphlibAdapter.prototype.canContractEdge = function (from, to) {

@@ -234,20 +386,22 @@ return util_1.canContractEdge(this, from, to);

GraphlibAdapter.prototype.getSuccessorsOf = function (vertex) {
var edges = this.g.successors(vertex);
if (!edges) {
var _this = this;
var nodes = this.g.successors(vertex.gid);
if (!nodes) {
return util_1.EmptyIterator;
}
return util_1.createArrayIterator(edges);
return util_1.createMappedArrayIterator(nodes, function (node) { return _this.g.node(node); });
};
GraphlibAdapter.prototype.getPredecessorsOf = function (vertex) {
var edges = this.g.predecessors(vertex);
if (!edges) {
var _this = this;
var nodes = this.g.predecessors(vertex.gid);
if (!nodes) {
return util_1.EmptyIterator;
}
return util_1.createArrayIterator(edges);
return util_1.createMappedArrayIterator(nodes, function (node) { return _this.g.node(node); });
};
GraphlibAdapter.prototype.hasEdge = function (from, to) {
return this.g.hasEdge(from, to);
return this.g.hasEdge(from.gid, to.gid);
};
GraphlibAdapter.prototype.hasVertex = function (vertex) {
return this.g.hasNode(vertex);
return this.g.hasNode(vertex.gid);
};

@@ -260,37 +414,70 @@ GraphlibAdapter.prototype.getVertexCount = function () {

};
GraphlibAdapter.prototype.getVertexData = function (vertex) {
return this.g.node(vertex);
GraphlibAdapter.prototype.getEdgesWithDataFrom = function (vertex) {
var _this = this;
var edges = this.g.outEdges(vertex.gid);
if (edges === undefined) {
return util_1.EmptyIterator;
}
return util_1.createMappedArrayIterator(edges, function (edge) { return [
_this.g.node(edge.w),
_this.g.edge(edge.v, edge.w)
]; });
};
GraphlibAdapter.prototype.getEdgeDataFrom = function (vertex) {
var _this = this;
var edges = this.g.outEdges(vertex);
var edges = this.g.outEdges(vertex.gid);
if (edges === undefined) {
return util_1.EmptyIterator;
}
return util_1.createFilteredIterator(util_1.createMappedArrayIterator(edges, function (edge) { return _this.g.edge(edge.v, edge.w); }), function (data) { return data !== undefined; });
return util_1.createFilteredIterator(util_1.createMappedArrayIterator(edges, function (edge) { return _this.g.edge(edge.v, edge.w); }));
};
GraphlibAdapter.prototype.getEdgesWithDataTo = function (vertex) {
var _this = this;
var edges = this.g.inEdges(vertex.gid);
if (edges === undefined) {
return util_1.EmptyIterator;
}
return util_1.createMappedArrayIterator(edges, function (edge) { return [
_this.g.node(edge.v),
_this.g.edge(edge.v, edge.w)
]; });
};
GraphlibAdapter.prototype.getEdgeDataTo = function (vertex) {
var _this = this;
var edges = this.g.inEdges(vertex);
var edges = this.g.inEdges(vertex.gid);
if (edges === undefined) {
return util_1.EmptyIterator;
}
return util_1.createFilteredIterator(util_1.createMappedArrayIterator(edges, function (edge) { return _this.g.edge(edge.v, edge.w); }), function (data) { return data !== undefined; });
return util_1.createFilteredIterator(util_1.createMappedArrayIterator(edges, function (edge) { return _this.g.edge(edge.v, edge.w); }));
};
GraphlibAdapter.prototype.getEdgeData = function (from, to) {
return this.g.edge(from, to);
return this.g.edge(from.gid, to.gid);
};
GraphlibAdapter.prototype.setEdgeData = function (from, to, data) {
if (!this.g.hasEdge(from, to)) {
if (!this.g.hasEdge(from.gid, to.gid)) {
return false;
}
this.g.setEdge(from, to, data);
this.g.setEdge(from.gid, to.gid, data);
return true;
};
GraphlibAdapter.prototype.getVertices = function () {
return util_1.createArrayIterator(this.g.nodes());
var _this = this;
return util_1.createMappedArrayIterator(this.g.nodes(), function (node) { return _this.g.node(node); });
};
GraphlibAdapter.prototype.getEdges = function () {
return util_1.createMappedArrayIterator(this.g.edges(), function (edge) { return [edge.v, edge.w]; });
var _this = this;
return util_1.createMappedArrayIterator(this.g.edges(), function (edge) {
return [_this.g.node(edge.v), _this.g.node(edge.w)];
});
};
GraphlibAdapter.prototype.getEdgesWithData = function () {
var _this = this;
return util_1.createMappedArrayIterator(this.g.edges(), function (edge) {
return [
_this.g.node(edge.v),
_this.g.node(edge.w),
_this.g.edge(edge.v, edge.w)
];
});
};
GraphlibAdapter.prototype.supportsOrder = function () {

@@ -310,3 +497,3 @@ return this.detector.supportsOrder();

GraphlibAdapter.prototype.canAddEdge = function (from, to) {
if (this.g.hasEdge(from, to)) {
if (this.g.hasEdge(from.gid, to.gid)) {
return false;

@@ -328,3 +515,3 @@ }

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

@@ -343,30 +530,33 @@ }

}
this.g.setEdge(from, to, data);
this.g.setEdge(from.gid, to.gid, data);
return true;
};
GraphlibAdapter.prototype.addVertex = function (vertex, label) {
GraphlibAdapter.prototype.createVertex = function (data) {
var vertexData = this.detector.createVertexData(this.adapter);
return util_1.assign(vertexData, data);
};
GraphlibAdapter.prototype.addVertex = function (vertex) {
if (this.hasVertex(vertex)) {
return false;
}
var vertexData = this.detector.createVertexData(this.adapter, vertex);
this.g.setNode(vertex, label !== undefined ? util_1.assign(vertexData, label) : vertexData);
this.g.setNode(vertex.gid, vertex);
return true;
};
GraphlibAdapter.prototype.deleteEdge = function (from, to, name) {
if (!this.g.hasEdge(from, to, name)) {
GraphlibAdapter.prototype.deleteEdge = function (from, to) {
if (!this.g.hasEdge(from.gid, to.gid)) {
return false;
}
this.g.removeEdge(from, to);
this.g.removeEdge(from.gid, to.gid);
return true;
};
GraphlibAdapter.prototype.deleteVertex = function (vertex) {
if (!this.g.hasNode(vertex)) {
if (!this.g.hasNode(vertex.gid)) {
return false;
}
this.detector.onVertexDeletion(this.adapter, vertex);
this.g.removeNode(vertex);
this.g.removeNode(vertex.gid);
return true;
};
GraphlibAdapter.prototype.getData = function (key) {
return this.g.node(key);
GraphlibAdapter.prototype.getData = function (vertex) {
return this.g.node(vertex.gid);
};

@@ -377,3 +567,3 @@ return GraphlibAdapter;

},{"./PearceKellyDetector":5,"./util":6}],4:[function(require,module,exports){
},{"./PearceKellyDetector":6,"./util":7}],5:[function(require,module,exports){
"use strict";

@@ -383,7 +573,7 @@ Object.defineProperty(exports, "__esModule", { value: true });

var util_1 = require("./util");
function createMerger(edgeMerger) {
function createMerger(edgeMerger, mapConstructor) {
if (edgeMerger === void 0) { edgeMerger = util_1.takeFirst; }
return function (first, second) {
if (first === undefined) {
return second;
return second || new mapConstructor();
}

@@ -395,3 +585,9 @@ if (second === undefined) {

var data = first.get(res.value[0]);
data = data === undefined ? res.value[1] : edgeMerger(data, res.value[1]);
if (data === undefined) {
data = res.value[1];
}
else {
var other = res.value[1];
data = other !== undefined ? edgeMerger(data, other) : data;
}
first.set(res.value[0], data);

@@ -403,7 +599,35 @@ }

var MultiGraphAdapter = (function () {
function MultiGraphAdapter(options) {
function MultiGraphAdapter(graphFactory, edgeCount, mapConstructor) {
this.g = graphFactory();
this.edgeCount = edgeCount;
this.mapConstructor = mapConstructor;
}
MultiGraphAdapter.create = function (options) {
if (options === void 0) { options = {}; }
this.g = new GenericGraphAdapter_1.GenericGraphAdapter(options);
this.edgeCount = 0;
}
var graphFactory = options.graphFactory || GenericGraphAdapter_1.GenericGraphAdapter.create;
var mapConstructor = options.mapConstructor || Map;
return new MultiGraphAdapter(graphFactory, 0, mapConstructor);
};
MultiGraphAdapter.prototype.mapLabeled = function (vertexMapper, edgeDataMapper, labelMapper) {
var _this = this;
var g = this.g.map(vertexMapper, function (edgeLabelToEdgeDataMap) {
var clonedEdgeLabelToEdgeDataMap = new _this.mapConstructor();
edgeLabelToEdgeDataMap.forEach(function (edgeData, edgeLabel) {
var clonedEdgeData = edgeData !== undefined ? edgeDataMapper(edgeData) : undefined;
var clonedEdgeLabel = edgeLabel !== undefined ? labelMapper(edgeLabel) : undefined;
clonedEdgeLabelToEdgeDataMap.set(clonedEdgeLabel, clonedEdgeData);
});
return clonedEdgeLabelToEdgeDataMap;
});
return new MultiGraphAdapter(function () { return g; }, this.edgeCount, this.mapConstructor);
};
MultiGraphAdapter.prototype.map = function (vertexMapper, edgeDataMapper) {
return this.mapLabeled(vertexMapper, edgeDataMapper, function (label) { return label; });
};
MultiGraphAdapter.prototype.clone = function (vertexCloner, edgeDataCloner, labelCloner) {
var vCloner = vertexCloner !== undefined ? vertexCloner : function (vertex) { return vertex; };
var eCloner = edgeDataCloner !== undefined ? edgeDataCloner : function (data) { return data; };
var lCloner = labelCloner !== undefined ? labelCloner : function (label) { return label; };
return this.mapLabeled(vCloner, eCloner, lCloner);
};
MultiGraphAdapter.prototype.addLabeledEdge = function (from, to, label, data) {

@@ -440,11 +664,35 @@ return this.addEdge(from, to, data, label);

};
MultiGraphAdapter.prototype.getEdgesWithDataTo = function (vertex, label) {
return util_1.createFlatMappedIterator(this.g.getEdgesWithDataTo(vertex), function (pair) {
var map = pair[1];
if (map === undefined) {
return util_1.EmptyIterator;
}
if (label === undefined) {
return util_1.createMappedIterator(map.values(), function (edgeData) { return [pair[0], edgeData]; });
}
return util_1.createMappedIterator(util_1.createFilteredIterator(map.entries(), function (entry) { return entry[0] === label; }), function (entry) { return [pair[0], entry[1]]; });
});
};
MultiGraphAdapter.prototype.getEdgesWithDataFrom = function (vertex, label) {
return util_1.createFlatMappedIterator(this.g.getEdgesWithDataFrom(vertex), function (pair) {
var map = pair[1];
if (map === undefined) {
return util_1.EmptyIterator;
}
if (label === undefined) {
return util_1.createMappedIterator(map.values(), function (edgeData) { return [pair[0], edgeData]; });
}
return util_1.createMappedIterator(util_1.createFilteredIterator(map.entries(), function (entry) { return entry[0] === label; }), function (entry) { return [pair[0], entry[1]]; });
});
};
MultiGraphAdapter.prototype.getEdgeDataTo = function (vertex, label) {
if (label === undefined) {
return util_1.createFilteredIterator(util_1.createFlatMappedIterator(this.g.getEdgeDataTo(vertex), function (data) { return data.values(); }), function (data) { return data !== undefined; });
return util_1.createFilteredIterator(util_1.createFlatMappedIterator(this.g.getEdgeDataTo(vertex), function (data) { return data ? data.values() : util_1.EmptyIterator; }), function (data) { return data !== undefined; });
}
return util_1.createMappedIterator(util_1.createFilteredIterator(util_1.createFlatMappedIterator(this.g.getEdgeDataTo(vertex), function (data) { return data.entries(); }), function (entry) { return entry[1] !== undefined && entry[0] === label; }), function (entry) { return entry[1]; });
return util_1.createMappedIterator(util_1.createFilteredIterator(util_1.createFlatMappedIterator(this.g.getEdgeDataTo(vertex), function (data) { return data ? data.entries() : util_1.EmptyIterator; }), function (entry) { return entry[1] !== undefined && entry[0] === label; }), function (entry) { return entry[1]; });
};
MultiGraphAdapter.prototype.getEdgeDataFrom = function (vertex, label) {
if (label === undefined) {
return util_1.createFilteredIterator(util_1.createFlatMappedIterator(this.g.getEdgeDataFrom(vertex), function (data) { return data.values(); }), function (data) { return data !== undefined; });
return util_1.createFilteredIterator(util_1.createFlatMappedIterator(this.g.getEdgeDataFrom(vertex), function (data) { return data ? data.values() : util_1.EmptyIterator; }), function (data) { return data !== undefined; });
}

@@ -454,3 +702,3 @@ return util_1.createMappedIterator(util_1.createFilteredIterator(util_1.createFlatMappedIterator(this.g.getEdgeDataFrom(vertex), function (data) { return data.entries(); }), function (entry) { return entry[1] !== undefined && entry[0] === label; }), function (entry) { return entry[1]; });

MultiGraphAdapter.prototype.contractEdge = function (from, to, vertexMerger, edgeMerger) {
return this.g.contractEdge(from, to, vertexMerger, createMerger(edgeMerger));
return this.g.contractEdge(from, to, vertexMerger, createMerger(edgeMerger, this.mapConstructor));
};

@@ -460,7 +708,3 @@ MultiGraphAdapter.prototype.canContractEdge = function (from, to) {

};
MultiGraphAdapter.prototype.deleteEdge = function (from, to, label) {
if (label === undefined) {
this.edgeCount -= this.getEdgeCountBetween(from, to);
return this.g.deleteEdge(from, to);
}
MultiGraphAdapter.prototype.deleteLabeledEdge = function (from, to, label) {
var srcData = this.g.getEdgeData(from, to);

@@ -479,2 +723,9 @@ if (srcData === undefined) {

};
MultiGraphAdapter.prototype.deleteEdge = function (from, to, label) {
if (label === undefined) {
this.edgeCount -= this.getEdgeCountBetween(from, to);
return this.g.deleteEdge(from, to);
}
return this.deleteLabeledEdge(from, to, label);
};
MultiGraphAdapter.prototype.deleteVertex = function (vertex) {

@@ -507,2 +758,21 @@ return this.g.deleteVertex(vertex);

};
MultiGraphAdapter.prototype.getEdgesWithData = function () {
return util_1.createFlatMappedIterator(this.g.getEdgesWithData(), function (entry) {
return util_1.createMappedIterator(entry[2].values(), function (data) { return [
entry[0],
entry[1],
data
]; });
});
};
MultiGraphAdapter.prototype.getLabeledEdgesWithData = function () {
return util_1.createFlatMappedIterator(this.g.getEdgesWithData(), function (entry) {
return util_1.createMappedIterator(entry[2].entries(), function (subEntry) { return [
entry[0],
entry[1],
subEntry[1],
subEntry[0]
]; });
});
};
MultiGraphAdapter.prototype.getEdgeCountBetween = function (from, to) {

@@ -582,3 +852,3 @@ var data = this.g.getEdgeData(from, to);

},{"./GenericGraphAdapter":2,"./util":6}],5:[function(require,module,exports){
},{"./GenericGraphAdapter":3,"./util":7}],6:[function(require,module,exports){
"use strict";

@@ -627,2 +897,11 @@ Object.defineProperty(exports, "__esModule", { value: true });

}
PearceKellyDetector.prototype.map = function () {
var clone = new PearceKellyDetector();
clone.id = this.id;
for (var _i = 0, _a = this.freeStack; _i < _a.length; _i++) {
var item = _a[_i];
clone.freeStack.push(item);
}
return clone;
};
PearceKellyDetector.prototype.isReachable = function (adapter, source, target) {

@@ -640,3 +919,3 @@ if (source === target) {

};
PearceKellyDetector.prototype.createVertexData = function (g, vertex) {
PearceKellyDetector.prototype.createVertexData = function (g) {
var id = this.freeStack.pop();

@@ -742,5 +1021,8 @@ return {

},{}],6:[function(require,module,exports){
},{}],7:[function(require,module,exports){
"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
function filterUndefined(value) {
return value !== undefined;
}
function takeFirst(first, second) {

@@ -793,2 +1075,3 @@ return first;

function createFilteredIterator(it, filter) {
if (filter === void 0) { filter = filterUndefined; }
return {

@@ -805,2 +1088,28 @@ next: function () {

exports.createFilteredIterator = createFilteredIterator;
function createChainedIterator() {
var its = [];
for (var _i = 0; _i < arguments.length; _i++) {
its[_i] = arguments[_i];
}
var i = -1;
var currentIterator = exports.EmptyIterator;
return {
next: function () {
var currentNext = currentIterator.next();
while (currentNext.done) {
var it_1 = its[++i];
if (it_1 === undefined) {
return exports.DoneIteratorResult;
}
currentIterator = it_1;
currentNext = currentIterator.next();
}
return {
done: false,
value: currentNext.value,
};
}
};
}
exports.createChainedIterator = createChainedIterator;
function createFlatMappedIterator(iterator, mapper) {

@@ -900,3 +1209,3 @@ var subIterator = exports.EmptyIterator;

if (newVertex !== from) {
for (var it_1 = adapter.getSuccessorsOf(from), res = it_1.next(); !res.done; res = it_1.next()) {
for (var it_2 = adapter.getSuccessorsOf(from), res = it_2.next(); !res.done; res = it_2.next()) {
var data = adapter.getEdgeData(from, res.value);

@@ -906,3 +1215,3 @@ adapter.deleteEdge(from, res.value);

}
for (var it_2 = adapter.getPredecessorsOf(from), res = it_2.next(); !res.done; res = it_2.next()) {
for (var it_3 = adapter.getPredecessorsOf(from), res = it_3.next(); !res.done; res = it_3.next()) {
var data = adapter.getEdgeData(res.value, from);

@@ -914,3 +1223,3 @@ adapter.deleteEdge(res.value, from);

if (newVertex !== to) {
for (var it_3 = adapter.getSuccessorsOf(to), res = it_3.next(); !res.done; res = it_3.next()) {
for (var it_4 = adapter.getSuccessorsOf(to), res = it_4.next(); !res.done; res = it_4.next()) {
var data = adapter.getEdgeData(to, res.value);

@@ -920,3 +1229,3 @@ adapter.deleteEdge(to, res.value);

}
for (var it_4 = adapter.getPredecessorsOf(to), res = it_4.next(); !res.done; res = it_4.next()) {
for (var it_5 = adapter.getPredecessorsOf(to), res = it_5.next(); !res.done; res = it_5.next()) {
var data = adapter.getEdgeData(res.value, to);

@@ -937,3 +1246,4 @@ adapter.deleteEdge(res.value, to);

else {
adapter.setEdgeData(newVertex, node[0], dataMerger(data, node[1]));
var other = node[1];
adapter.setEdgeData(newVertex, node[0], other !== undefined ? dataMerger(data, other) : data);
}

@@ -948,3 +1258,4 @@ }

else {
adapter.setEdgeData(node[0], newVertex, dataMerger(data, node[1]));
var other = node[1];
adapter.setEdgeData(node[0], newVertex, other !== undefined ? dataMerger(data, other) : data);
}

@@ -959,4 +1270,29 @@ }

}
var DummyVertexData = { order: 0, visited: false };
exports.DummyDetector = new (function () {
function class_1() {
}
class_1.prototype.map = function () {
return exports.DummyDetector;
};
class_1.prototype.createVertexData = function (g) {
return DummyVertexData;
};
class_1.prototype.canAddEdge = function (g, from, to) {
return true;
};
class_1.prototype.isReachable = function (g, source, target) {
return false;
};
class_1.prototype.onVertexDeletion = function (g, vertex) { };
class_1.prototype.supportsOrder = function () {
return false;
};
class_1.prototype.getOrder = function (g, vertex) {
return -1;
};
return class_1;
}())();
},{}],7:[function(require,module,exports){
},{}],8:[function(require,module,exports){
(function (global){

@@ -963,0 +1299,0 @@ /*! *****************************************************************************

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/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.getEdgeDataTo=function(a){var c=this.backward.get(a);return void 0===c?e.EmptyIterator:e.createFilteredIterator(c.values(),function(a){return void 0!==a})},a.prototype.getEdgeDataFrom=function(a){var b=this.forward.get(a);return void 0===b?e.EmptyIterator:e.createFilteredIterator(b.values(),function(a){return void 0!==a})},a.prototype.setEdgeData=function(a,c,d){var e=this.forward.get(a),f=this.backward.get(c);return!!(e&&f&&e.has(c)&&f.has(a))&&(e.set(c,d),f.set(a,d),!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.canAddEdge=function(a,c){var d=this.forward.get(a),e=this.backward.get(c),g=this.addVertex(a),h=this.addVertex(c);return d||this.forward.set(a,d=new this.mapConstructor),e||this.backward.set(c,e=new this.mapConstructor),!d.has(c)&&this.detector.canAddEdge(this.adapter,a,c)||(g&&this.deleteVertex(a),h&&this.deleteVertex(c),!1)},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,d),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.getEdgeDataFrom=function(a){var b=this,c=this.g.outEdges(a);return void 0===c?e.EmptyIterator:e.createFilteredIterator(e.createMappedArrayIterator(c,function(a){return b.g.edge(a.v,a.w)}),function(a){return void 0!==a})},a.prototype.getEdgeDataTo=function(a){var b=this,c=this.g.inEdges(a);return void 0===c?e.EmptyIterator:e.createFilteredIterator(e.createMappedArrayIterator(c,function(a){return b.g.edge(a.v,a.w)}),function(a){return void 0!==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.canAddEdge=function(a,b){if(this.g.hasEdge(a,b))return!1;var c=this.addVertex(a),d=this.addVertex(b);return!!this.detector.canAddEdge(this.adapter,a,b)||(c&&this.deleteVertex(a),d&&this.deleteVertex(b),!1)},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.canAddEdge=function(a,b,c){var d=this.g.getEdgeData(a,b);return void 0===d?this.g.canAddEdge(a,b):!d.has(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.getEdgeDataTo=function(a,b){return void 0===b?f.createFilteredIterator(f.createFlatMappedIterator(this.g.getEdgeDataTo(a),function(a){return a.values()}),function(a){return void 0!==a}):f.createMappedIterator(f.createFilteredIterator(f.createFlatMappedIterator(this.g.getEdgeDataTo(a),function(a){return a.entries()}),function(a){return void 0!==a[1]&&a[0]===b}),function(a){return a[1]})},a.prototype.getEdgeDataFrom=function(a,b){return void 0===b?f.createFilteredIterator(f.createFlatMappedIterator(this.g.getEdgeDataFrom(a),function(a){return a.values()}),function(a){return void 0!==a}):f.createMappedIterator(f.createFilteredIterator(f.createFlatMappedIterator(this.g.getEdgeDataFrom(a),function(a){return a.entries()}),function(a){return void 0!==a[1]&&a[0]===b}),function(a){return a[1]})},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)});
(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/Algorithm"),c),d.__exportStar(a("./src/GenericGraphAdapter"),c),d.__exportStar(a("./src/GraphlibAdapter"),c),d.__exportStar(a("./src/MultiGraphAdapter"),c),d.__exportStar(a("./src/PearceKellyDetector"),c)},{"./src/Algorithm":2,"./src/GenericGraphAdapter":3,"./src/GraphlibAdapter":4,"./src/MultiGraphAdapter":5,"./src/PearceKellyDetector":6,tslib:8}],2:[function(a,b,c){"use strict";Object.defineProperty(c,"__esModule",{value:!0});var d=a("./util"),e=function(){function a(){}return a.findWeaklyConnectedComponents=function(a,b){void 0===b&&(b=Set);for(var c=new b,d=[],e=a.getVertices(),f=e.next();!f.done;f=e.next())if(!c.has(f.value)){var g={edges:[],vertices:[f.value]},h=[f.value];for(c.add(f.value);0<h.length;){for(var i,j=h.pop(),k=a.getEdgesWithDataTo(j),l=k.next();!l.done;l=k.next())(i=l.value[0],!c.has(i))&&(c.add(i),g.vertices.push(i),h.push(i));for(var i,k=a.getEdgesWithDataFrom(j),l=k.next();!l.done;l=k.next())(i=l.value[0],g.edges.push([j,i,l.value[1]]),!c.has(i))&&(c.add(i),g.vertices.push(i),h.push(i))}d.push(g)}return d},a.getNeighbors=function(a,b){return d.createChainedIterator(a.getPredecessorsOf(b),a.getSuccessorsOf(b))},a}();c.Algorithm=e},{"./util":7}],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,b){this.detector=b,this.forward=new a,this.backward=new a,this.mapConstructor=a,this.vertices=new a,this.edgeCount=0,this.adapter={getData:this.getData.bind(this),getPredecessorsOf:this.getPredecessorsOf.bind(this),getSuccessorsOf:this.getSuccessorsOf.bind(this)}}return a.create=function(b){void 0===b&&(b={});var c=b.mapConstructor||Map,e=b.cycleDetector||new d.PearceKellyDetector;return new a(c,e)},a.prototype.map=function(b,c){var d=this,f=new a(this.mapConstructor,e.DummyDetector),g=new this.mapConstructor;return this.vertices.forEach(function(a,c){var d=b(c);g.set(c,d),f.vertices.set(d,a)}),this.forward.forEach(function(a,b){var e=new d.mapConstructor,h=g.get(b);a.forEach(function(a,b){var d=g.get(b),i=void 0===a?void 0:c(a);e.set(d,i),f.addToBackwardsMap(h,d,i)}),f.forward.set(h,e)}),f.edgeCount=this.edgeCount,f.detector=this.detector.map(),f},a.prototype.clone=function(a,b){var c=void 0===a?function(a){return a}:a,d=void 0===b?function(a){return a}:b;return this.map(c,d)},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.getEdgesWithDataTo=function(a){var c=this.backward.get(a);return void 0===c?e.EmptyIterator:c.entries()},a.prototype.getEdgeDataTo=function(a){var c=this.backward.get(a);return void 0===c?e.EmptyIterator:e.createFilteredIterator(c.values())},a.prototype.getEdgesWithDataFrom=function(a){var b=this.forward.get(a);return void 0===b?e.EmptyIterator:b.entries()},a.prototype.getEdgeDataFrom=function(a){var b=this.forward.get(a);return void 0===b?e.EmptyIterator:e.createFilteredIterator(b.values())},a.prototype.setEdgeData=function(a,c,d){var e=this.forward.get(a),f=this.backward.get(c);return!!(e&&f&&e.has(c)&&f.has(a))&&(e.set(c,d),f.set(a,d),!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.getEdgesWithData=function(){return e.createFlatMappedIterator(this.forward.entries(),function(a){return e.createMappedIterator(a[1].entries(),function(b){return[a[0],b[0],b[1]]})})},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.canAddEdge=function(a,c){var d=this.forward.get(a),e=this.backward.get(c),g=this.addVertex(a),h=this.addVertex(c);return d||this.forward.set(a,d=new this.mapConstructor),e||this.backward.set(c,e=new this.mapConstructor),!d.has(c)&&this.detector.canAddEdge(this.adapter,a,c)||(g&&this.deleteVertex(a),h&&this.deleteVertex(c),!1)},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,d),this.edgeCount+=1,!0)},a.prototype.addVertex=function(a){return!this.vertices.has(a)&&(this.vertices.set(a,this.detector.createVertexData(this.adapter)),!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.addToBackwardsMap=function(a,b,c){var d=this.backward.get(b);void 0===d&&this.backward.set(b,d=new this.mapConstructor),d.set(a,c)},a.prototype.getData=function(a){return this.vertices.get(a)},a}();c.GenericGraphAdapter=f},{"./PearceKellyDetector":6,"./util":7}],4:[function(a,b,c){"use strict";function d(a,b){return a.bind(b)}Object.defineProperty(c,"__esModule",{value:!0});var e=a("./PearceKellyDetector"),f=a("./util"),g=function(){function a(a,b,c){this.graphlib=c,this.g=a,this.detector=b,this.adapter={getData:d(this.getData,this),getPredecessorsOf:d(this.getPredecessorsOf,this),getSuccessorsOf:d(this.getSuccessorsOf,this)}}return a.create=function(b){var c=new b.graphlib(f.assign(b.graphOptions||{},{directed:!0})),d=b.cycleDetector||new e.PearceKellyDetector;return new a(c,d,b.graphlib)},a.prototype.map=function(b,c){for(var d=new this.graphlib({compound:this.g.isCompound(),directed:this.g.isDirected(),multigraph:this.g.isMultigraph()}),e=0,f=this.g.nodes();e<f.length;e++){var g=f[e],h=this.g.node(g),i=b(h);void 0===i.gid&&(i.gid=h.gid),i.order=h.order,i.visited=h.visited,d.setNode(i.gid,i)}for(var j=0,k=this.g.edges();j<k.length;j++){var l=k[j],m=this.g.edge(l);d.setEdge(l.v,l.w,void 0===m?void 0:c(m),l.name)}var n=this.detector.map();return new a(d,n,this.graphlib)},a.prototype.clone=function(a,b){var c=void 0===a?function(a){return a}:a,d=void 0===b?function(a){return a}:b;return this.map(c,d)},a.prototype.canContractEdge=function(a,b){return f.canContractEdge(this,a,b)},a.prototype.contractEdge=function(a,b,c,d){return f.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,c=this.g.successors(a.gid);return c?f.createMappedArrayIterator(c,function(a){return b.g.node(a)}):f.EmptyIterator},a.prototype.getPredecessorsOf=function(a){var b=this,c=this.g.predecessors(a.gid);return c?f.createMappedArrayIterator(c,function(a){return b.g.node(a)}):f.EmptyIterator},a.prototype.hasEdge=function(a,b){return this.g.hasEdge(a.gid,b.gid)},a.prototype.hasVertex=function(a){return this.g.hasNode(a.gid)},a.prototype.getVertexCount=function(){return this.g.nodeCount()},a.prototype.getEdgeCount=function(){return this.g.edgeCount()},a.prototype.getEdgesWithDataFrom=function(a){var b=this,c=this.g.outEdges(a.gid);return void 0===c?f.EmptyIterator:f.createMappedArrayIterator(c,function(a){return[b.g.node(a.w),b.g.edge(a.v,a.w)]})},a.prototype.getEdgeDataFrom=function(a){var b=this,c=this.g.outEdges(a.gid);return void 0===c?f.EmptyIterator:f.createFilteredIterator(f.createMappedArrayIterator(c,function(a){return b.g.edge(a.v,a.w)}))},a.prototype.getEdgesWithDataTo=function(a){var b=this,c=this.g.inEdges(a.gid);return void 0===c?f.EmptyIterator:f.createMappedArrayIterator(c,function(a){return[b.g.node(a.v),b.g.edge(a.v,a.w)]})},a.prototype.getEdgeDataTo=function(a){var b=this,c=this.g.inEdges(a.gid);return void 0===c?f.EmptyIterator:f.createFilteredIterator(f.createMappedArrayIterator(c,function(a){return b.g.edge(a.v,a.w)}))},a.prototype.getEdgeData=function(a,b){return this.g.edge(a.gid,b.gid)},a.prototype.setEdgeData=function(a,b,c){return!!this.g.hasEdge(a.gid,b.gid)&&(this.g.setEdge(a.gid,b.gid,c),!0)},a.prototype.getVertices=function(){var a=this;return f.createMappedArrayIterator(this.g.nodes(),function(b){return a.g.node(b)})},a.prototype.getEdges=function(){var a=this;return f.createMappedArrayIterator(this.g.edges(),function(b){return[a.g.node(b.v),a.g.node(b.w)]})},a.prototype.getEdgesWithData=function(){var a=this;return f.createMappedArrayIterator(this.g.edges(),function(b){return[a.g.node(b.v),a.g.node(b.w),a.g.edge(b.v,b.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.canAddEdge=function(a,b){if(this.g.hasEdge(a.gid,b.gid))return!1;var c=this.addVertex(a),d=this.addVertex(b);return!!this.detector.canAddEdge(this.adapter,a,b)||(c&&this.deleteVertex(a),d&&this.deleteVertex(b),!1)},a.prototype.addEdge=function(a,b,c){if(this.g.hasEdge(a.gid,b.gid))return!1;var d=this.addVertex(a),e=this.addVertex(b);return this.detector.canAddEdge(this.adapter,a,b)?(this.g.setEdge(a.gid,b.gid,c),!0):(d&&this.deleteVertex(a),e&&this.deleteVertex(b),!1)},a.prototype.createVertex=function(a){var b=this.detector.createVertexData(this.adapter);return f.assign(b,a)},a.prototype.addVertex=function(a){return!this.hasVertex(a)&&(this.g.setNode(a.gid,a),!0)},a.prototype.deleteEdge=function(a,b){return!!this.g.hasEdge(a.gid,b.gid)&&(this.g.removeEdge(a.gid,b.gid),!0)},a.prototype.deleteVertex=function(a){return!!this.g.hasNode(a.gid)&&(this.detector.onVertexDeletion(this.adapter,a),this.g.removeNode(a.gid),!0)},a.prototype.getData=function(a){return this.g.node(a.gid)},a}();c.GraphlibAdapter=g},{"./PearceKellyDetector":6,"./util":7}],5:[function(a,b,c){"use strict";function d(a,b){return void 0===a&&(a=f.takeFirst),function(c,d){if(void 0===c)return d||new b;if(void 0===d)return c;for(var e,f=d.entries(),g=f.next();!g.done;g=f.next()){if(e=c.get(g.value[0]),void 0===e)e=g.value[1];else{var h=g.value[1];e=void 0===h?e:a(e,h)}c.set(g.value[0],e)}return c}}Object.defineProperty(c,"__esModule",{value:!0});var e=a("./GenericGraphAdapter"),f=a("./util"),g=function(){function a(a,b,c){this.g=a(),this.edgeCount=b,this.mapConstructor=c}return a.create=function(b){void 0===b&&(b={});var c=b.graphFactory||e.GenericGraphAdapter.create,d=b.mapConstructor||Map;return new a(c,0,d)},a.prototype.mapLabeled=function(b,c,d){var e=this,f=this.g.map(b,function(a){var b=new e.mapConstructor;return a.forEach(function(a,e){var f=void 0===a?void 0:c(a),g=void 0===e?void 0:d(e);b.set(g,f)}),b});return new a(function(){return f},this.edgeCount,this.mapConstructor)},a.prototype.map=function(a,b){return this.mapLabeled(a,b,function(a){return a})},a.prototype.clone=function(a,b,c){var d=void 0===a?function(a){return a}:a,e=void 0===b?function(a){return a}:b,f=void 0===c?function(a){return a}:c;return this.mapLabeled(d,e,f)},a.prototype.addLabeledEdge=function(a,b,c,d){return this.addEdge(a,b,d,c)},a.prototype.canAddEdge=function(a,b,c){var d=this.g.getEdgeData(a,b);return void 0===d?this.g.canAddEdge(a,b):!d.has(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.getEdgesWithDataTo=function(a,b){return f.createFlatMappedIterator(this.g.getEdgesWithDataTo(a),function(a){var c=a[1];return void 0===c?f.EmptyIterator:void 0===b?f.createMappedIterator(c.values(),function(b){return[a[0],b]}):f.createMappedIterator(f.createFilteredIterator(c.entries(),function(a){return a[0]===b}),function(b){return[a[0],b[1]]})})},a.prototype.getEdgesWithDataFrom=function(a,b){return f.createFlatMappedIterator(this.g.getEdgesWithDataFrom(a),function(a){var c=a[1];return void 0===c?f.EmptyIterator:void 0===b?f.createMappedIterator(c.values(),function(b){return[a[0],b]}):f.createMappedIterator(f.createFilteredIterator(c.entries(),function(a){return a[0]===b}),function(b){return[a[0],b[1]]})})},a.prototype.getEdgeDataTo=function(a,b){return void 0===b?f.createFilteredIterator(f.createFlatMappedIterator(this.g.getEdgeDataTo(a),function(a){return a?a.values():f.EmptyIterator}),function(a){return void 0!==a}):f.createMappedIterator(f.createFilteredIterator(f.createFlatMappedIterator(this.g.getEdgeDataTo(a),function(a){return a?a.entries():f.EmptyIterator}),function(a){return void 0!==a[1]&&a[0]===b}),function(a){return a[1]})},a.prototype.getEdgeDataFrom=function(a,b){return void 0===b?f.createFilteredIterator(f.createFlatMappedIterator(this.g.getEdgeDataFrom(a),function(a){return a?a.values():f.EmptyIterator}),function(a){return void 0!==a}):f.createMappedIterator(f.createFilteredIterator(f.createFlatMappedIterator(this.g.getEdgeDataFrom(a),function(a){return a.entries()}),function(a){return void 0!==a[1]&&a[0]===b}),function(a){return a[1]})},a.prototype.contractEdge=function(a,b,c,e){return this.g.contractEdge(a,b,c,d(e,this.mapConstructor))},a.prototype.canContractEdge=function(a,b){return this.g.canContractEdge(a,b)},a.prototype.deleteLabeledEdge=function(a,b,c){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.deleteEdge=function(a,b,c){return void 0===c?(this.edgeCount-=this.getEdgeCountBetween(a,b),this.g.deleteEdge(a,b)):this.deleteLabeledEdge(a,b,c)},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.getEdgesWithData=function(){return f.createFlatMappedIterator(this.g.getEdgesWithData(),function(a){return f.createMappedIterator(a[2].values(),function(b){return[a[0],a[1],b]})})},a.prototype.getLabeledEdgesWithData=function(){return f.createFlatMappedIterator(this.g.getEdgesWithData(),function(a){return f.createMappedIterator(a[2].entries(),function(b){return[a[0],a[1],b[1],b[0]]})})},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":3,"./util":7}],6:[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.map=function(){var b=new a;b.id=this.id;for(var c,d=0,e=this.freeStack;d<e.length;d++)c=e[d],b.freeStack.push(c);return b},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},{}],7:[function(a,b,c){"use strict";function d(a){return a!==void 0}function e(a){return a}function f(a,b,c,d,f){void 0===d&&(d=e);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]);if(i===void 0)a.addEdge(f,q[0],q[1]);else{var r=q[1];a.setEdgeData(f,q[0],r===void 0?i:d(i,r))}}for(var s=0,t=h;s<t.length;s++){var q=t[s],i=a.getEdgeData(q[0],f);if(i===void 0)a.addEdge(q[0],f,q[1]);else{var r=q[1];a.setEdgeData(q[0],f,r===void 0?i:d(i,r))}}f!==c&&a.deleteVertex(c),f!==b&&a.deleteVertex(b)}Object.defineProperty(c,"__esModule",{value:!0}),c.takeFirst=e,c.DoneIteratorResult={done:!0,value:void 0},c.EmptyIterator={next:function(){return c.DoneIteratorResult}};var g=Object.prototype.hasOwnProperty;c.assign=function(a,b){for(var c in b)g.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 void 0===b&&(b=d),{next:function(){for(var c=a.next();!c.done&&!b(c.value);)c=a.next();return c}}},c.createChainedIterator=function(){for(var a=[],b=0;b<arguments.length;b++)a[b]=arguments[b];var d=-1,e=c.EmptyIterator;return{next:function(){for(var b=e.next();b.done;){var f=a[++d];if(f===void 0)return c.DoneIteratorResult;e=f,b=e.next()}return{done:!1,value:b.value}}}},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,d,g){if(void 0===d&&(d=e),!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=d(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 f(a,b,c,g,i),!0};var h={order:0,visited:!1};c.DummyDetector=new(function(){function a(){}return a.prototype.map=function(){return c.DummyDetector},a.prototype.createVertexData=function(){return h},a.prototype.canAddEdge=function(){return!0},a.prototype.isReachable=function(){return!1},a.prototype.onVertexDeletion=function(){},a.prototype.supportsOrder=function(){return!1},a.prototype.getOrder=function(){return-1},a}())},{}],8:[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)});

5

dist/index.d.ts

@@ -0,5 +1,6 @@

export * from "./src/Algorithm";
export * from "./src/GenericGraphAdapter";
export * from "./src/GraphlibAdapter";
export * from "./src/GenericGraphAdapter";
export * from "./src/Header";
export * from "./src/MultiGraphAdapter";
export * from "./src/Header";
export * from "./src/PearceKellyDetector";

3

dist/index.js
"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
var tslib_1 = require("tslib");
tslib_1.__exportStar(require("./src/Algorithm"), exports);
tslib_1.__exportStar(require("./src/GenericGraphAdapter"), 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);

19

dist/src/GenericGraphAdapter.d.ts

@@ -1,4 +0,5 @@

import { BinaryOperator, Pair } from "andross";
import { CommonAdapter, GenericGraphAdapterOptions } from "./Header";
export declare class GenericGraphAdapter<TVertex = any, TEdgeData = any> implements CommonAdapter<TVertex, TEdgeData | undefined> {
import { BinaryOperator, Maybe, Pair, Triple, TypedFunction, UnaryOperator } from "andross";
import { ClonableAdapter, CommonAdapter, GenericGraphAdapterOptions } from "./Header";
export declare class GenericGraphAdapter<TVertex = any, TEdgeData = any> implements CommonAdapter<TVertex, TEdgeData>, ClonableAdapter<TVertex, TEdgeData> {
static create<TVertex = any, TEdgeData = any>(options?: Partial<GenericGraphAdapterOptions<TVertex>>): GenericGraphAdapter<TVertex, TEdgeData>;
private detector;

@@ -9,7 +10,9 @@ private adapter;

private backward;
private mapConstructor;
private edgeCount;
private mapConstructor;
constructor(options?: Partial<GenericGraphAdapterOptions<TVertex>>);
private constructor();
map<TClonedVertex, TClonedEdgeData>(vertexMapper: TypedFunction<TVertex, TClonedVertex>, edgeDataMapper: TypedFunction<TEdgeData, TClonedEdgeData>): GenericGraphAdapter<TClonedVertex, TClonedEdgeData>;
clone(vertexCloner?: UnaryOperator<TVertex>, edgeDataCloner?: UnaryOperator<TEdgeData>): GenericGraphAdapter<TVertex, TEdgeData>;
canContractEdge(from: TVertex, to: TVertex): boolean;
contractEdge(from: TVertex, to: TVertex, vertexMerger?: BinaryOperator<TVertex>, edgeMerger?: BinaryOperator<TEdgeData | undefined>): boolean;
contractEdge(from: TVertex, to: TVertex, vertexMerger?: BinaryOperator<TVertex>, edgeMerger?: BinaryOperator<TEdgeData>): boolean;
isReachable(source: TVertex, target: TVertex): boolean;

@@ -20,6 +23,9 @@ getSuccessorsOf(vertex: TVertex): Iterator<TVertex>;

getEdgeData(from: TVertex, to: TVertex): TEdgeData | undefined;
getEdgesWithDataTo(vertex: TVertex): Iterator<Pair<TVertex, Maybe<TEdgeData>>>;
getEdgeDataTo(vertex: TVertex): Iterator<TEdgeData>;
getEdgesWithDataFrom(vertex: TVertex): Iterator<Pair<TVertex, Maybe<TEdgeData>>>;
getEdgeDataFrom(vertex: TVertex): Iterator<TEdgeData>;
setEdgeData(from: TVertex, to: TVertex, data: TEdgeData | undefined): boolean;
getEdges(): Iterator<Pair<TVertex>>;
getEdgesWithData(): Iterator<Triple<TVertex, TVertex, Maybe<TEdgeData>>>;
getEdgeCount(): number;

@@ -36,3 +42,4 @@ supportsOrder(): boolean;

deleteVertex(vertex: TVertex): boolean;
private addToBackwardsMap;
private getData;
}

75

dist/src/GenericGraphAdapter.js

@@ -6,6 +6,4 @@ "use strict";

var GenericGraphAdapter = (function () {
function GenericGraphAdapter(options) {
if (options === void 0) { options = {}; }
var mapConstructor = options.mapConstructor || Map;
this.detector = options.cycleDetector || new PearceKellyDetector_1.PearceKellyDetector();
function GenericGraphAdapter(mapConstructor, cycleDetector) {
this.detector = cycleDetector;
this.forward = new mapConstructor();

@@ -22,2 +20,37 @@ this.backward = new mapConstructor();

}
GenericGraphAdapter.create = function (options) {
if (options === void 0) { options = {}; }
var mapConstructor = options.mapConstructor || Map;
var detector = options.cycleDetector || new PearceKellyDetector_1.PearceKellyDetector();
return new GenericGraphAdapter(mapConstructor, detector);
};
GenericGraphAdapter.prototype.map = function (vertexMapper, edgeDataMapper) {
var _this = this;
var clone = new GenericGraphAdapter(this.mapConstructor, util_1.DummyDetector);
var clonedVertexMap = new this.mapConstructor();
this.vertices.forEach(function (vertexData, vertex) {
var clonedVertex = vertexMapper(vertex);
clonedVertexMap.set(vertex, clonedVertex);
clone.vertices.set(clonedVertex, vertexData);
});
this.forward.forEach(function (map, from) {
var clonedMap = new _this.mapConstructor();
var clonedFrom = clonedVertexMap.get(from);
map.forEach(function (edgeData, to) {
var clonedTo = clonedVertexMap.get(to);
var clonedEdgeData = edgeData !== undefined ? edgeDataMapper(edgeData) : undefined;
clonedMap.set(clonedTo, clonedEdgeData);
clone.addToBackwardsMap(clonedFrom, clonedTo, clonedEdgeData);
});
clone.forward.set(clonedFrom, clonedMap);
});
clone.edgeCount = this.edgeCount;
clone.detector = this.detector.map();
return clone;
};
GenericGraphAdapter.prototype.clone = function (vertexCloner, edgeDataCloner) {
var vCloner = vertexCloner !== undefined ? vertexCloner : function (vertex) { return vertex; };
var eCloner = edgeDataCloner !== undefined ? edgeDataCloner : function (data) { return data; };
return this.map(vCloner, eCloner);
};
GenericGraphAdapter.prototype.canContractEdge = function (from, to) {

@@ -56,2 +89,9 @@ return util_1.canContractEdge(this, from, to);

};
GenericGraphAdapter.prototype.getEdgesWithDataTo = function (vertex) {
var b = this.backward.get(vertex);
if (b === undefined) {
return util_1.EmptyIterator;
}
return b.entries();
};
GenericGraphAdapter.prototype.getEdgeDataTo = function (vertex) {

@@ -62,4 +102,11 @@ var b = this.backward.get(vertex);

}
return util_1.createFilteredIterator(b.values(), function (data) { return data !== undefined; });
return util_1.createFilteredIterator(b.values());
};
GenericGraphAdapter.prototype.getEdgesWithDataFrom = function (vertex) {
var f = this.forward.get(vertex);
if (f === undefined) {
return util_1.EmptyIterator;
}
return f.entries();
};
GenericGraphAdapter.prototype.getEdgeDataFrom = function (vertex) {

@@ -70,3 +117,3 @@ var f = this.forward.get(vertex);

}
return util_1.createFilteredIterator(f.values(), function (data) { return data !== undefined; });
return util_1.createFilteredIterator(f.values());
};

@@ -88,2 +135,9 @@ GenericGraphAdapter.prototype.setEdgeData = function (from, to, data) {

};
GenericGraphAdapter.prototype.getEdgesWithData = function () {
return util_1.createFlatMappedIterator(this.forward.entries(), function (entry) {
return util_1.createMappedIterator(entry[1].entries(), function (subEntry) {
return [entry[0], subEntry[0], subEntry[1]];
});
});
};
GenericGraphAdapter.prototype.getEdgeCount = function () {

@@ -159,3 +213,3 @@ return this.edgeCount;

}
this.vertices.set(vertex, this.detector.createVertexData(this.adapter, vertex));
this.vertices.set(vertex, this.detector.createVertexData(this.adapter));
return true;

@@ -189,2 +243,9 @@ };

};
GenericGraphAdapter.prototype.addToBackwardsMap = function (from, to, edgeData) {
var map = this.backward.get(to);
if (map === undefined) {
this.backward.set(to, map = new this.mapConstructor());
}
map.set(from, edgeData);
};
GenericGraphAdapter.prototype.getData = function (key) {

@@ -191,0 +252,0 @@ return this.vertices.get(key);

56

dist/src/GraphlibAdapter.d.ts

@@ -1,35 +0,41 @@

import { BinaryOperator, Pair, RemoveFrom } from "andross";
import { BinaryOperator, Maybe, Pair, PartialExcept, PartialFor, RemoveFrom, Triple, TypedFunction, UnaryOperator } from "andross";
import { Graph } from "graphlib";
import { CommonAdapter, CustomVertexData, GraphlibAdapterOptions, VertexData } from "./Header";
import { PartialExcept } from "./InternalHeader";
export declare class GraphlibAdapter<TVertexData extends VertexData = any, TEdgeData = any> implements CommonAdapter<string, TEdgeData> {
import { CommonAdapter, GraphlibAdapterOptions, GraphlibVertexData, VertexData } from "./Header";
export declare class GraphlibAdapter<TVertex extends GraphlibVertexData = any, TEdgeData = any> implements CommonAdapter<TVertex, TEdgeData> {
static create<TVertex extends GraphlibVertexData = any, TEdgeData = any>(options: PartialExcept<GraphlibAdapterOptions<TVertex>, "graphlib">): GraphlibAdapter<TVertex, TEdgeData>;
private g;
private graphlib;
private detector;
private adapter;
constructor(options: PartialExcept<GraphlibAdapterOptions<string>, "graphlib">);
canContractEdge(from: string, to: string): boolean;
contractEdge(from: string, to: string, vertexMerger?: BinaryOperator<string>, edgeMerger?: BinaryOperator<TEdgeData>): boolean;
isReachable(source: string, target: string): boolean;
getSuccessorsOf(vertex: string): Iterator<string>;
getPredecessorsOf(vertex: string): Iterator<string>;
hasEdge(from: string, to: string): boolean;
hasVertex(vertex: string): boolean;
private constructor();
map<TClonedVertexData extends TVertex, TClonedEdgeData>(vertexDataMapper: TypedFunction<TVertex, PartialFor<TClonedVertexData, keyof GraphlibVertexData>>, edgeDataMapper: TypedFunction<TEdgeData, TClonedEdgeData>): GraphlibAdapter<TClonedVertexData, TClonedEdgeData>;
clone(vertexDataCloner?: UnaryOperator<TVertex>, edgeDataCloner?: UnaryOperator<TEdgeData>): GraphlibAdapter<TVertex, TEdgeData>;
canContractEdge(from: TVertex, to: TVertex): boolean;
contractEdge(from: TVertex, to: TVertex, vertexMerger?: BinaryOperator<TVertex>, edgeMerger?: BinaryOperator<TEdgeData>): boolean;
isReachable(source: TVertex, target: TVertex): boolean;
getSuccessorsOf(vertex: TVertex): Iterator<TVertex>;
getPredecessorsOf(vertex: TVertex): Iterator<TVertex>;
hasEdge(from: TVertex, to: TVertex): boolean;
hasVertex(vertex: TVertex): boolean;
getVertexCount(): number;
getEdgeCount(): number;
getVertexData(vertex: string): RemoveFrom<TVertexData, VertexData>;
getEdgeDataFrom(vertex: string): Iterator<TEdgeData>;
getEdgeDataTo(vertex: string): Iterator<TEdgeData>;
getEdgeData(from: string, to: string): TEdgeData;
setEdgeData(from: string, to: string, data: TEdgeData): boolean;
getVertices(): Iterator<string>;
getEdges(): Iterator<Pair<string>>;
getEdgesWithDataFrom(vertex: TVertex): Iterator<Pair<TVertex, Maybe<TEdgeData>>>;
getEdgeDataFrom(vertex: TVertex): Iterator<TEdgeData>;
getEdgesWithDataTo(vertex: TVertex): Iterator<Pair<TVertex, Maybe<TEdgeData>>>;
getEdgeDataTo(vertex: TVertex): Iterator<TEdgeData>;
getEdgeData(from: TVertex, to: TVertex): TEdgeData;
setEdgeData(from: TVertex, to: TVertex, data: TEdgeData): boolean;
getVertices(): Iterator<TVertex>;
getEdges(): Iterator<Pair<TVertex>>;
getEdgesWithData(): Iterator<Triple<TVertex, TVertex, Maybe<TEdgeData>>>;
supportsOrder(): boolean;
getOrder(vertex: string): number;
getOrder(vertex: TVertex): number;
readonly graph: Graph;
canAddEdge(from: string, to: string): boolean;
addEdge(from: string, to: string, data?: TEdgeData): boolean;
addVertex(vertex: string, label?: CustomVertexData<TVertexData>): boolean;
deleteEdge(from: string, to: string, name?: string): boolean;
deleteVertex(vertex: string): boolean;
canAddEdge(from: TVertex, to: TVertex): boolean;
addEdge(from: TVertex, to: TVertex, data?: TEdgeData): boolean;
createVertex(data: RemoveFrom<TVertex & GraphlibVertexData, VertexData>): TVertex;
addVertex(vertex: TVertex): boolean;
deleteEdge(from: TVertex, to: TVertex): boolean;
deleteVertex(vertex: TVertex): boolean;
private getData;
}

153

dist/src/GraphlibAdapter.js

@@ -5,12 +5,51 @@ "use strict";

var util_1 = require("./util");
function bind(fn, context) {
return fn.bind(context);
}
var GraphlibAdapter = (function () {
function GraphlibAdapter(options) {
this.g = new options.graphlib(util_1.assign({ directed: true }, options.graphOptions));
this.detector = options.cycleDetector || new PearceKellyDetector_1.PearceKellyDetector();
function GraphlibAdapter(g, detector, graphlib) {
this.graphlib = graphlib;
this.g = g;
this.detector = detector;
this.adapter = {
getData: this.getData.bind(this),
getPredecessorsOf: this.getPredecessorsOf.bind(this),
getSuccessorsOf: this.getSuccessorsOf.bind(this),
getData: bind(this.getData, this),
getPredecessorsOf: bind(this.getPredecessorsOf, this),
getSuccessorsOf: bind(this.getSuccessorsOf, this),
};
}
GraphlibAdapter.create = function (options) {
var g = new options.graphlib(util_1.assign(options.graphOptions || {}, { directed: true }));
var detector = options.cycleDetector || new PearceKellyDetector_1.PearceKellyDetector();
return new GraphlibAdapter(g, detector, options.graphlib);
};
GraphlibAdapter.prototype.map = function (vertexDataMapper, edgeDataMapper) {
var clonedG = new this.graphlib({
compound: this.g.isCompound(),
directed: this.g.isDirected(),
multigraph: this.g.isMultigraph(),
});
for (var _i = 0, _a = this.g.nodes(); _i < _a.length; _i++) {
var node = _a[_i];
var vertexData = this.g.node(node);
var partialVertexData = vertexDataMapper(vertexData);
if (partialVertexData.gid === undefined) {
partialVertexData.gid = vertexData.gid;
}
partialVertexData.order = vertexData.order;
partialVertexData.visited = vertexData.visited;
clonedG.setNode(partialVertexData.gid, partialVertexData);
}
for (var _b = 0, _c = this.g.edges(); _b < _c.length; _b++) {
var edge = _c[_b];
var edgeData = this.g.edge(edge);
clonedG.setEdge(edge.v, edge.w, edgeData !== undefined ? edgeDataMapper(edgeData) : undefined, edge.name);
}
var clonedDetector = this.detector.map();
return new GraphlibAdapter(clonedG, clonedDetector, this.graphlib);
};
GraphlibAdapter.prototype.clone = function (vertexDataCloner, edgeDataCloner) {
var vCloner = vertexDataCloner !== undefined ? vertexDataCloner : function (vertex) { return vertex; };
var eCloner = edgeDataCloner !== undefined ? edgeDataCloner : function (data) { return data; };
return this.map(vCloner, eCloner);
};
GraphlibAdapter.prototype.canContractEdge = function (from, to) {

@@ -26,20 +65,22 @@ return util_1.canContractEdge(this, from, to);

GraphlibAdapter.prototype.getSuccessorsOf = function (vertex) {
var edges = this.g.successors(vertex);
if (!edges) {
var _this = this;
var nodes = this.g.successors(vertex.gid);
if (!nodes) {
return util_1.EmptyIterator;
}
return util_1.createArrayIterator(edges);
return util_1.createMappedArrayIterator(nodes, function (node) { return _this.g.node(node); });
};
GraphlibAdapter.prototype.getPredecessorsOf = function (vertex) {
var edges = this.g.predecessors(vertex);
if (!edges) {
var _this = this;
var nodes = this.g.predecessors(vertex.gid);
if (!nodes) {
return util_1.EmptyIterator;
}
return util_1.createArrayIterator(edges);
return util_1.createMappedArrayIterator(nodes, function (node) { return _this.g.node(node); });
};
GraphlibAdapter.prototype.hasEdge = function (from, to) {
return this.g.hasEdge(from, to);
return this.g.hasEdge(from.gid, to.gid);
};
GraphlibAdapter.prototype.hasVertex = function (vertex) {
return this.g.hasNode(vertex);
return this.g.hasNode(vertex.gid);
};

@@ -52,37 +93,70 @@ GraphlibAdapter.prototype.getVertexCount = function () {

};
GraphlibAdapter.prototype.getVertexData = function (vertex) {
return this.g.node(vertex);
GraphlibAdapter.prototype.getEdgesWithDataFrom = function (vertex) {
var _this = this;
var edges = this.g.outEdges(vertex.gid);
if (edges === undefined) {
return util_1.EmptyIterator;
}
return util_1.createMappedArrayIterator(edges, function (edge) { return [
_this.g.node(edge.w),
_this.g.edge(edge.v, edge.w)
]; });
};
GraphlibAdapter.prototype.getEdgeDataFrom = function (vertex) {
var _this = this;
var edges = this.g.outEdges(vertex);
var edges = this.g.outEdges(vertex.gid);
if (edges === undefined) {
return util_1.EmptyIterator;
}
return util_1.createFilteredIterator(util_1.createMappedArrayIterator(edges, function (edge) { return _this.g.edge(edge.v, edge.w); }), function (data) { return data !== undefined; });
return util_1.createFilteredIterator(util_1.createMappedArrayIterator(edges, function (edge) { return _this.g.edge(edge.v, edge.w); }));
};
GraphlibAdapter.prototype.getEdgesWithDataTo = function (vertex) {
var _this = this;
var edges = this.g.inEdges(vertex.gid);
if (edges === undefined) {
return util_1.EmptyIterator;
}
return util_1.createMappedArrayIterator(edges, function (edge) { return [
_this.g.node(edge.v),
_this.g.edge(edge.v, edge.w)
]; });
};
GraphlibAdapter.prototype.getEdgeDataTo = function (vertex) {
var _this = this;
var edges = this.g.inEdges(vertex);
var edges = this.g.inEdges(vertex.gid);
if (edges === undefined) {
return util_1.EmptyIterator;
}
return util_1.createFilteredIterator(util_1.createMappedArrayIterator(edges, function (edge) { return _this.g.edge(edge.v, edge.w); }), function (data) { return data !== undefined; });
return util_1.createFilteredIterator(util_1.createMappedArrayIterator(edges, function (edge) { return _this.g.edge(edge.v, edge.w); }));
};
GraphlibAdapter.prototype.getEdgeData = function (from, to) {
return this.g.edge(from, to);
return this.g.edge(from.gid, to.gid);
};
GraphlibAdapter.prototype.setEdgeData = function (from, to, data) {
if (!this.g.hasEdge(from, to)) {
if (!this.g.hasEdge(from.gid, to.gid)) {
return false;
}
this.g.setEdge(from, to, data);
this.g.setEdge(from.gid, to.gid, data);
return true;
};
GraphlibAdapter.prototype.getVertices = function () {
return util_1.createArrayIterator(this.g.nodes());
var _this = this;
return util_1.createMappedArrayIterator(this.g.nodes(), function (node) { return _this.g.node(node); });
};
GraphlibAdapter.prototype.getEdges = function () {
return util_1.createMappedArrayIterator(this.g.edges(), function (edge) { return [edge.v, edge.w]; });
var _this = this;
return util_1.createMappedArrayIterator(this.g.edges(), function (edge) {
return [_this.g.node(edge.v), _this.g.node(edge.w)];
});
};
GraphlibAdapter.prototype.getEdgesWithData = function () {
var _this = this;
return util_1.createMappedArrayIterator(this.g.edges(), function (edge) {
return [
_this.g.node(edge.v),
_this.g.node(edge.w),
_this.g.edge(edge.v, edge.w)
];
});
};
GraphlibAdapter.prototype.supportsOrder = function () {

@@ -102,3 +176,3 @@ return this.detector.supportsOrder();

GraphlibAdapter.prototype.canAddEdge = function (from, to) {
if (this.g.hasEdge(from, to)) {
if (this.g.hasEdge(from.gid, to.gid)) {
return false;

@@ -120,3 +194,3 @@ }

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

@@ -135,30 +209,33 @@ }

}
this.g.setEdge(from, to, data);
this.g.setEdge(from.gid, to.gid, data);
return true;
};
GraphlibAdapter.prototype.addVertex = function (vertex, label) {
GraphlibAdapter.prototype.createVertex = function (data) {
var vertexData = this.detector.createVertexData(this.adapter);
return util_1.assign(vertexData, data);
};
GraphlibAdapter.prototype.addVertex = function (vertex) {
if (this.hasVertex(vertex)) {
return false;
}
var vertexData = this.detector.createVertexData(this.adapter, vertex);
this.g.setNode(vertex, label !== undefined ? util_1.assign(vertexData, label) : vertexData);
this.g.setNode(vertex.gid, vertex);
return true;
};
GraphlibAdapter.prototype.deleteEdge = function (from, to, name) {
if (!this.g.hasEdge(from, to, name)) {
GraphlibAdapter.prototype.deleteEdge = function (from, to) {
if (!this.g.hasEdge(from.gid, to.gid)) {
return false;
}
this.g.removeEdge(from, to);
this.g.removeEdge(from.gid, to.gid);
return true;
};
GraphlibAdapter.prototype.deleteVertex = function (vertex) {
if (!this.g.hasNode(vertex)) {
if (!this.g.hasNode(vertex.gid)) {
return false;
}
this.detector.onVertexDeletion(this.adapter, vertex);
this.g.removeNode(vertex);
this.g.removeNode(vertex.gid);
return true;
};
GraphlibAdapter.prototype.getData = function (key) {
return this.g.node(key);
GraphlibAdapter.prototype.getData = function (vertex) {
return this.g.node(vertex.gid);
};

@@ -165,0 +242,0 @@ return GraphlibAdapter;

36

dist/src/Header.d.ts

@@ -1,4 +0,3 @@

import { BinaryOperator, Omit, Pair } from "andross";
import { BinaryOperator, Maybe, Omit, Pair, Triple, TypedFunction, UnaryOperator } from "andross";
import { Graph, GraphOptions } from "graphlib";
export declare type CustomVertexData<TVertexData extends VertexData> = Omit<TVertexData, keyof VertexData>;
export interface VertexData {

@@ -12,2 +11,11 @@ order: number;

}
export declare type MultiGraphEdgeData<TEdgeData, TEdgeLabel> = Map<Maybe<TEdgeLabel>, Maybe<TEdgeData>>;
export declare type GraphFactory<TVertex, TEdgeData, TEdgeLabel> = () => CommonAdapter<TVertex, MultiGraphEdgeData<TEdgeData, TEdgeLabel>> & ClonableAdapter<TVertex, MultiGraphEdgeData<TEdgeData, TEdgeLabel>>;
export interface MultiGraphAdapterOptions<TVertex, TEdgeData, TEdgeLabel> {
graphFactory: GraphFactory<TVertex, TEdgeData, TEdgeLabel>;
mapConstructor: MapConstructor;
}
export interface GraphlibVertexData extends VertexData {
gid: string;
}
export declare type GraphlibConstructor = new (options?: GraphOptions) => Graph;

@@ -25,10 +33,15 @@ export interface GraphlibAdapterOptions<TVertex> {

export interface CycleDetector<TVertex> {
createVertexData(g: GraphAdapter<TVertex>, vertex: TVertex): VertexData;
canAddEdge(g: GraphAdapter<TVertex>, from: TVertex, to: TVertex): boolean;
createVertexData(g: GraphAdapter<TVertex>): VertexData;
getOrder(g: GraphAdapter<TVertex>, vertex: TVertex): number;
isReachable(g: GraphAdapter<TVertex>, source: TVertex, target: TVertex): boolean;
map<TClonedVertex>(): CycleDetector<TClonedVertex>;
onVertexDeletion(g: GraphAdapter<TVertex>, vertex: TVertex): void;
supportsOrder(): boolean;
getOrder(g: GraphAdapter<TVertex>, vertex: TVertex): number;
}
export interface CommonAdapter<TVertex, TEdgeData = any> {
export interface ClonableAdapter<TVertex, TEdgeData> {
clone(vertexCloner?: UnaryOperator<TVertex>, edgeDataCloner?: UnaryOperator<TEdgeData>): CommonAdapter<TVertex, TEdgeData> & ClonableAdapter<TVertex, TEdgeData>;
map<TClonedVertex, TClonedEdgeData>(vertexMapper: TypedFunction<TVertex, TClonedVertex>, edgeDataMapper: TypedFunction<TEdgeData, TClonedEdgeData>): CommonAdapter<TClonedVertex, TClonedEdgeData> & ClonableAdapter<TClonedVertex, TClonedEdgeData>;
}
export interface CommonAdapter<TVertex = any, TEdgeData = any> {
addEdge(from: TVertex, to: TVertex, data?: TEdgeData): boolean;

@@ -42,6 +55,9 @@ addVertex(vertex: TVertex): boolean;

getEdgeCount(): number;
getEdgeData(from: TVertex, to: TVertex): TEdgeData;
getEdgeData(from: TVertex, to: TVertex): Maybe<TEdgeData>;
getEdgeDataTo(vertex: TVertex): Iterator<TEdgeData>;
getEdgeDataFrom(vertex: TVertex): Iterator<TEdgeData>;
getEdges(): Iterator<Pair<TVertex, TVertex>>;
getEdgesWithDataTo(vertex: TVertex): Iterator<Pair<TVertex, Maybe<TEdgeData>>>;
getEdgesWithDataFrom(vertex: TVertex): Iterator<Pair<TVertex, Maybe<TEdgeData>>>;
getEdges(): Iterator<Pair<TVertex>>;
getEdgesWithData(): Iterator<Triple<TVertex, TVertex, Maybe<TEdgeData>>>;
getOrder(vertex: TVertex): number;

@@ -55,4 +71,8 @@ getPredecessorsOf(vertex: TVertex): Iterator<TVertex>;

isReachable(source: TVertex, target: TVertex): boolean;
setEdgeData(from: TVertex, to: TVertex, data: TEdgeData): boolean;
setEdgeData(from: TVertex, to: TVertex, data: Maybe<TEdgeData>): boolean;
supportsOrder(): boolean;
}
export interface WeaklyConnectedComponent<TVertex, TEdgeData> {
edges: Triple<TVertex, TVertex, Maybe<TEdgeData>>[];
vertices: TVertex[];
}

21

dist/src/MultiGraphAdapter.d.ts

@@ -1,7 +0,13 @@

import { BinaryOperator, Maybe, Pair, Triple } from "andross";
import { CommonAdapter, GenericGraphAdapterOptions } from "./Header";
export declare class MultiGraphAdapter<TVertex = any, TEdgeData = any, TEdgeLabel = any> implements CommonAdapter<TVertex, TEdgeData | undefined> {
import { BinaryOperator, Maybe, Pair, Quadruple, Triple, TypedFunction, UnaryOperator } from "andross";
import { ClonableAdapter, CommonAdapter, MultiGraphAdapterOptions } from "./Header";
export declare class MultiGraphAdapter<TVertex = any, TEdgeData = any, TEdgeLabel = any> implements CommonAdapter<TVertex, TEdgeData>, ClonableAdapter<TVertex, TEdgeData> {
static create<TVertex = any, TEdgeData = any, TEdgeLabel = any>(options?: Partial<MultiGraphAdapterOptions<TVertex, TEdgeData, TEdgeLabel>>): MultiGraphAdapter<TVertex, TEdgeData, TEdgeLabel>;
private g;
private edgeCount;
constructor(options?: Partial<GenericGraphAdapterOptions<TVertex>>);
private mapConstructor;
private constructor();
mapLabeled<TClonedVertex, TClonedEdgeData, TClonedEdgeLabel>(vertexMapper: TypedFunction<TVertex, TClonedVertex>, edgeDataMapper: TypedFunction<TEdgeData, TClonedEdgeData>, labelMapper: TypedFunction<TEdgeLabel, TClonedEdgeLabel>): MultiGraphAdapter<TClonedVertex, TClonedEdgeData, TClonedEdgeLabel>;
map<TClonedVertex, TClonedEdgeData>(vertexMapper: TypedFunction<TVertex, TClonedVertex>, edgeDataMapper: TypedFunction<TEdgeData, TClonedEdgeData>): MultiGraphAdapter<TClonedVertex, TClonedEdgeData, TEdgeLabel>;
clone(vertexCloner?: UnaryOperator<TVertex>, edgeDataCloner?: UnaryOperator<TEdgeData>, labelCloner?: UnaryOperator<TEdgeLabel>): MultiGraphAdapter<TVertex, TEdgeData, TEdgeLabel>;
addLabeledEdge(from: TVertex, to: TVertex, label: Maybe<TEdgeLabel>, data?: TEdgeData): boolean;
addLabeledEdge(from: TVertex, to: TVertex, label?: TEdgeLabel, data?: TEdgeData): boolean;

@@ -11,6 +17,9 @@ canAddEdge(from: TVertex, to: TVertex, label?: TEdgeLabel): boolean;

addVertex(vertex: TVertex): boolean;
getEdgesWithDataTo(vertex: TVertex, label?: TEdgeLabel): Iterator<Pair<TVertex, Maybe<TEdgeData>>>;
getEdgesWithDataFrom(vertex: TVertex, label?: TEdgeLabel): Iterator<Pair<TVertex, Maybe<TEdgeData>>>;
getEdgeDataTo(vertex: TVertex, label?: TEdgeLabel): Iterator<TEdgeData>;
getEdgeDataFrom(vertex: TVertex, label?: TEdgeLabel): Iterator<TEdgeData>;
contractEdge(from: TVertex, to: TVertex, vertexMerger?: BinaryOperator<TVertex>, edgeMerger?: BinaryOperator<Maybe<TEdgeData>>): boolean;
contractEdge(from: TVertex, to: TVertex, vertexMerger?: BinaryOperator<TVertex>, edgeMerger?: BinaryOperator<TEdgeData>): boolean;
canContractEdge(from: TVertex, to: TVertex): boolean;
deleteLabeledEdge(from: TVertex, to: TVertex, label: Maybe<TEdgeLabel>): boolean;
deleteEdge(from: TVertex, to: TVertex, label?: TEdgeLabel): boolean;

@@ -23,2 +32,4 @@ deleteVertex(vertex: TVertex): boolean;

getEdges(): Iterator<Pair<TVertex>>;
getEdgesWithData(): Iterator<Triple<TVertex, TVertex, Maybe<TEdgeData>>>;
getLabeledEdgesWithData(): Iterator<Quadruple<TVertex, TVertex, Maybe<TEdgeData>, Maybe<TEdgeLabel>>>;
getEdgeCountBetween(from: TVertex, to: TVertex): number;

@@ -25,0 +36,0 @@ getEdgeLabels(from: TVertex, to: TVertex): Iterator<TEdgeLabel | undefined>;

112

dist/src/MultiGraphAdapter.js

@@ -5,7 +5,7 @@ "use strict";

var util_1 = require("./util");
function createMerger(edgeMerger) {
function createMerger(edgeMerger, mapConstructor) {
if (edgeMerger === void 0) { edgeMerger = util_1.takeFirst; }
return function (first, second) {
if (first === undefined) {
return second;
return second || new mapConstructor();
}

@@ -17,3 +17,9 @@ if (second === undefined) {

var data = first.get(res.value[0]);
data = data === undefined ? res.value[1] : edgeMerger(data, res.value[1]);
if (data === undefined) {
data = res.value[1];
}
else {
var other = res.value[1];
data = other !== undefined ? edgeMerger(data, other) : data;
}
first.set(res.value[0], data);

@@ -25,7 +31,35 @@ }

var MultiGraphAdapter = (function () {
function MultiGraphAdapter(options) {
function MultiGraphAdapter(graphFactory, edgeCount, mapConstructor) {
this.g = graphFactory();
this.edgeCount = edgeCount;
this.mapConstructor = mapConstructor;
}
MultiGraphAdapter.create = function (options) {
if (options === void 0) { options = {}; }
this.g = new GenericGraphAdapter_1.GenericGraphAdapter(options);
this.edgeCount = 0;
}
var graphFactory = options.graphFactory || GenericGraphAdapter_1.GenericGraphAdapter.create;
var mapConstructor = options.mapConstructor || Map;
return new MultiGraphAdapter(graphFactory, 0, mapConstructor);
};
MultiGraphAdapter.prototype.mapLabeled = function (vertexMapper, edgeDataMapper, labelMapper) {
var _this = this;
var g = this.g.map(vertexMapper, function (edgeLabelToEdgeDataMap) {
var clonedEdgeLabelToEdgeDataMap = new _this.mapConstructor();
edgeLabelToEdgeDataMap.forEach(function (edgeData, edgeLabel) {
var clonedEdgeData = edgeData !== undefined ? edgeDataMapper(edgeData) : undefined;
var clonedEdgeLabel = edgeLabel !== undefined ? labelMapper(edgeLabel) : undefined;
clonedEdgeLabelToEdgeDataMap.set(clonedEdgeLabel, clonedEdgeData);
});
return clonedEdgeLabelToEdgeDataMap;
});
return new MultiGraphAdapter(function () { return g; }, this.edgeCount, this.mapConstructor);
};
MultiGraphAdapter.prototype.map = function (vertexMapper, edgeDataMapper) {
return this.mapLabeled(vertexMapper, edgeDataMapper, function (label) { return label; });
};
MultiGraphAdapter.prototype.clone = function (vertexCloner, edgeDataCloner, labelCloner) {
var vCloner = vertexCloner !== undefined ? vertexCloner : function (vertex) { return vertex; };
var eCloner = edgeDataCloner !== undefined ? edgeDataCloner : function (data) { return data; };
var lCloner = labelCloner !== undefined ? labelCloner : function (label) { return label; };
return this.mapLabeled(vCloner, eCloner, lCloner);
};
MultiGraphAdapter.prototype.addLabeledEdge = function (from, to, label, data) {

@@ -62,11 +96,35 @@ return this.addEdge(from, to, data, label);

};
MultiGraphAdapter.prototype.getEdgesWithDataTo = function (vertex, label) {
return util_1.createFlatMappedIterator(this.g.getEdgesWithDataTo(vertex), function (pair) {
var map = pair[1];
if (map === undefined) {
return util_1.EmptyIterator;
}
if (label === undefined) {
return util_1.createMappedIterator(map.values(), function (edgeData) { return [pair[0], edgeData]; });
}
return util_1.createMappedIterator(util_1.createFilteredIterator(map.entries(), function (entry) { return entry[0] === label; }), function (entry) { return [pair[0], entry[1]]; });
});
};
MultiGraphAdapter.prototype.getEdgesWithDataFrom = function (vertex, label) {
return util_1.createFlatMappedIterator(this.g.getEdgesWithDataFrom(vertex), function (pair) {
var map = pair[1];
if (map === undefined) {
return util_1.EmptyIterator;
}
if (label === undefined) {
return util_1.createMappedIterator(map.values(), function (edgeData) { return [pair[0], edgeData]; });
}
return util_1.createMappedIterator(util_1.createFilteredIterator(map.entries(), function (entry) { return entry[0] === label; }), function (entry) { return [pair[0], entry[1]]; });
});
};
MultiGraphAdapter.prototype.getEdgeDataTo = function (vertex, label) {
if (label === undefined) {
return util_1.createFilteredIterator(util_1.createFlatMappedIterator(this.g.getEdgeDataTo(vertex), function (data) { return data.values(); }), function (data) { return data !== undefined; });
return util_1.createFilteredIterator(util_1.createFlatMappedIterator(this.g.getEdgeDataTo(vertex), function (data) { return data ? data.values() : util_1.EmptyIterator; }), function (data) { return data !== undefined; });
}
return util_1.createMappedIterator(util_1.createFilteredIterator(util_1.createFlatMappedIterator(this.g.getEdgeDataTo(vertex), function (data) { return data.entries(); }), function (entry) { return entry[1] !== undefined && entry[0] === label; }), function (entry) { return entry[1]; });
return util_1.createMappedIterator(util_1.createFilteredIterator(util_1.createFlatMappedIterator(this.g.getEdgeDataTo(vertex), function (data) { return data ? data.entries() : util_1.EmptyIterator; }), function (entry) { return entry[1] !== undefined && entry[0] === label; }), function (entry) { return entry[1]; });
};
MultiGraphAdapter.prototype.getEdgeDataFrom = function (vertex, label) {
if (label === undefined) {
return util_1.createFilteredIterator(util_1.createFlatMappedIterator(this.g.getEdgeDataFrom(vertex), function (data) { return data.values(); }), function (data) { return data !== undefined; });
return util_1.createFilteredIterator(util_1.createFlatMappedIterator(this.g.getEdgeDataFrom(vertex), function (data) { return data ? data.values() : util_1.EmptyIterator; }), function (data) { return data !== undefined; });
}

@@ -76,3 +134,3 @@ return util_1.createMappedIterator(util_1.createFilteredIterator(util_1.createFlatMappedIterator(this.g.getEdgeDataFrom(vertex), function (data) { return data.entries(); }), function (entry) { return entry[1] !== undefined && entry[0] === label; }), function (entry) { return entry[1]; });

MultiGraphAdapter.prototype.contractEdge = function (from, to, vertexMerger, edgeMerger) {
return this.g.contractEdge(from, to, vertexMerger, createMerger(edgeMerger));
return this.g.contractEdge(from, to, vertexMerger, createMerger(edgeMerger, this.mapConstructor));
};

@@ -82,7 +140,3 @@ MultiGraphAdapter.prototype.canContractEdge = function (from, to) {

};
MultiGraphAdapter.prototype.deleteEdge = function (from, to, label) {
if (label === undefined) {
this.edgeCount -= this.getEdgeCountBetween(from, to);
return this.g.deleteEdge(from, to);
}
MultiGraphAdapter.prototype.deleteLabeledEdge = function (from, to, label) {
var srcData = this.g.getEdgeData(from, to);

@@ -101,2 +155,9 @@ if (srcData === undefined) {

};
MultiGraphAdapter.prototype.deleteEdge = function (from, to, label) {
if (label === undefined) {
this.edgeCount -= this.getEdgeCountBetween(from, to);
return this.g.deleteEdge(from, to);
}
return this.deleteLabeledEdge(from, to, label);
};
MultiGraphAdapter.prototype.deleteVertex = function (vertex) {

@@ -129,2 +190,21 @@ return this.g.deleteVertex(vertex);

};
MultiGraphAdapter.prototype.getEdgesWithData = function () {
return util_1.createFlatMappedIterator(this.g.getEdgesWithData(), function (entry) {
return util_1.createMappedIterator(entry[2].values(), function (data) { return [
entry[0],
entry[1],
data
]; });
});
};
MultiGraphAdapter.prototype.getLabeledEdgesWithData = function () {
return util_1.createFlatMappedIterator(this.g.getEdgesWithData(), function (entry) {
return util_1.createMappedIterator(entry[2].entries(), function (subEntry) { return [
entry[0],
entry[1],
subEntry[1],
subEntry[0]
]; });
});
};
MultiGraphAdapter.prototype.getEdgeCountBetween = function (from, to) {

@@ -131,0 +211,0 @@ var data = this.g.getEdgeData(from, to);

3

dist/src/PearceKellyDetector.d.ts

@@ -9,4 +9,5 @@ import { CycleDetector, GraphAdapter, VertexData } from "./Header";

constructor();
map<TClonedVertex>(): PearceKellyDetector<TClonedVertex>;
isReachable(adapter: GraphAdapter<TVertex>, source: TVertex, target: TVertex): boolean;
createVertexData(g: GraphAdapter<TVertex>, vertex: TVertex): VertexData;
createVertexData(g: GraphAdapter<TVertex>): VertexData;
onVertexDeletion(g: GraphAdapter<TVertex>, vertex: TVertex): void;

@@ -13,0 +14,0 @@ canAddEdge(g: GraphAdapter<TVertex>, from: TVertex, to: TVertex): boolean;

11

dist/src/PearceKellyDetector.js

@@ -44,2 +44,11 @@ "use strict";

}
PearceKellyDetector.prototype.map = function () {
var clone = new PearceKellyDetector();
clone.id = this.id;
for (var _i = 0, _a = this.freeStack; _i < _a.length; _i++) {
var item = _a[_i];
clone.freeStack.push(item);
}
return clone;
};
PearceKellyDetector.prototype.isReachable = function (adapter, source, target) {

@@ -57,3 +66,3 @@ if (source === target) {

};
PearceKellyDetector.prototype.createVertexData = function (g, vertex) {
PearceKellyDetector.prototype.createVertexData = function (g) {
var id = this.freeStack.pop();

@@ -60,0 +69,0 @@ return {

15

dist/src/util.d.ts

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

import { BinaryOperator, Predicate, TypedFunction } from "andross";
import { CommonAdapter } from "./Header";
import { BinaryOperator, Maybe, Predicate, TypedFunction } from "andross";
import { CommonAdapter, CycleDetector, GraphAdapter, VertexData } from "./Header";
export declare function takeFirst<T>(first: T, second: T): T;

@@ -9,3 +9,5 @@ export declare const DoneIteratorResult: IteratorResult<any>;

export declare function createMappedIterator<T, V>(it: Iterator<T>, mapper: TypedFunction<T, V>): Iterator<V>;
export declare function createFilteredIterator<T>(it: Iterator<Maybe<T>>): Iterator<T>;
export declare function createFilteredIterator<T>(it: Iterator<T>, filter: Predicate<T>): Iterator<T>;
export declare function createChainedIterator<T>(...its: Iterator<T>[]): Iterator<T>;
export declare function createFlatMappedIterator<T, S>(iterator: Iterator<T>, mapper: TypedFunction<T, Iterator<S>>): Iterator<S>;

@@ -18,1 +20,10 @@ export declare function createArrayIterator<T>(array: (T | undefined)[]): Iterator<T> & {

export declare function contractEdge<TVertex, TEdgeData>(adapter: CommonAdapter<TVertex, TEdgeData>, from: TVertex, to: TVertex, vertexMerger?: BinaryOperator<TVertex>, edgeMerger?: BinaryOperator<TEdgeData>): boolean;
export declare const DummyDetector: {
map<TAnotherClonedVertex>(): CycleDetector<TAnotherClonedVertex>;
createVertexData(g: GraphAdapter<any>): VertexData;
canAddEdge(g: GraphAdapter<any>, from: any, to: any): boolean;
isReachable(g: GraphAdapter<any>, source: any, target: any): boolean;
onVertexDeletion(g: GraphAdapter<any>, vertex: any): void;
supportsOrder(): boolean;
getOrder(g: GraphAdapter<any>, vertex: any): number;
};

69

dist/src/util.js
"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
function filterUndefined(value) {
return value !== undefined;
}
function takeFirst(first, second) {

@@ -50,2 +53,3 @@ return first;

function createFilteredIterator(it, filter) {
if (filter === void 0) { filter = filterUndefined; }
return {

@@ -62,2 +66,28 @@ next: function () {

exports.createFilteredIterator = createFilteredIterator;
function createChainedIterator() {
var its = [];
for (var _i = 0; _i < arguments.length; _i++) {
its[_i] = arguments[_i];
}
var i = -1;
var currentIterator = exports.EmptyIterator;
return {
next: function () {
var currentNext = currentIterator.next();
while (currentNext.done) {
var it_1 = its[++i];
if (it_1 === undefined) {
return exports.DoneIteratorResult;
}
currentIterator = it_1;
currentNext = currentIterator.next();
}
return {
done: false,
value: currentNext.value,
};
}
};
}
exports.createChainedIterator = createChainedIterator;
function createFlatMappedIterator(iterator, mapper) {

@@ -157,3 +187,3 @@ var subIterator = exports.EmptyIterator;

if (newVertex !== from) {
for (var it_1 = adapter.getSuccessorsOf(from), res = it_1.next(); !res.done; res = it_1.next()) {
for (var it_2 = adapter.getSuccessorsOf(from), res = it_2.next(); !res.done; res = it_2.next()) {
var data = adapter.getEdgeData(from, res.value);

@@ -163,3 +193,3 @@ adapter.deleteEdge(from, res.value);

}
for (var it_2 = adapter.getPredecessorsOf(from), res = it_2.next(); !res.done; res = it_2.next()) {
for (var it_3 = adapter.getPredecessorsOf(from), res = it_3.next(); !res.done; res = it_3.next()) {
var data = adapter.getEdgeData(res.value, from);

@@ -171,3 +201,3 @@ adapter.deleteEdge(res.value, from);

if (newVertex !== to) {
for (var it_3 = adapter.getSuccessorsOf(to), res = it_3.next(); !res.done; res = it_3.next()) {
for (var it_4 = adapter.getSuccessorsOf(to), res = it_4.next(); !res.done; res = it_4.next()) {
var data = adapter.getEdgeData(to, res.value);

@@ -177,3 +207,3 @@ adapter.deleteEdge(to, res.value);

}
for (var it_4 = adapter.getPredecessorsOf(to), res = it_4.next(); !res.done; res = it_4.next()) {
for (var it_5 = adapter.getPredecessorsOf(to), res = it_5.next(); !res.done; res = it_5.next()) {
var data = adapter.getEdgeData(res.value, to);

@@ -194,3 +224,4 @@ adapter.deleteEdge(res.value, to);

else {
adapter.setEdgeData(newVertex, node[0], dataMerger(data, node[1]));
var other = node[1];
adapter.setEdgeData(newVertex, node[0], other !== undefined ? dataMerger(data, other) : data);
}

@@ -205,3 +236,4 @@ }

else {
adapter.setEdgeData(node[0], newVertex, dataMerger(data, node[1]));
var other = node[1];
adapter.setEdgeData(node[0], newVertex, other !== undefined ? dataMerger(data, other) : data);
}

@@ -216,1 +248,26 @@ }

}
var DummyVertexData = { order: 0, visited: false };
exports.DummyDetector = new (function () {
function class_1() {
}
class_1.prototype.map = function () {
return exports.DummyDetector;
};
class_1.prototype.createVertexData = function (g) {
return DummyVertexData;
};
class_1.prototype.canAddEdge = function (g, from, to) {
return true;
};
class_1.prototype.isReachable = function (g, source, target) {
return false;
};
class_1.prototype.onVertexDeletion = function (g, vertex) { };
class_1.prototype.supportsOrder = function () {
return false;
};
class_1.prototype.getOrder = function (g, vertex) {
return -1;
};
return class_1;
}())();

4

package.json
{
"name": "incremental-cycle-detect",
"version": "0.2.2",
"version": "0.3.0",
"description": "Keeps a directed acyclic graph topologically sorted each time you add an edge or vertex to check for cycles.",

@@ -48,3 +48,3 @@ "main": "dist/index.js",

"@types/random-js": "^1.0.30",
"andross": "^0.3.2",
"andross": "^0.3.3",
"babel-minify": "^0.4.3",

@@ -51,0 +51,0 @@ "benchmark": "^2.1.4",

24

README.md

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

const { GenericGraphAdapter } = require("incremental-cycle-detect");
const graph = new GenericGraphAdapter();
const graph = GenericGraphAdapter.create();
graph.addEdge(0, 1) // => true

@@ -71,3 +71,3 @@ graph.addEdge(1, 2) // => true

const { Graph } = require("graphlib");
const graph = new GraphlibAdapter({graphlib: Graph});
const graph = GraphlibAdapter.create({graphlib: Graph});
graph.addEdge(0, 1) // => true

@@ -87,10 +87,14 @@ ```

> **incremental-cycle-detection**(insert 15000, RandomSource) x **36.43** ops/sec ±0.79% (58 runs sampled)
> **incremental-cycle-detection**(insert 15000, RandomSource) x **38.21** ops/sec ±1.78% (47 runs sampled)
>
> **incremental-cycle-detection-multi**(insert 15000, RandomSource) x **25.71** ops/sec ±10.12% (45 runs sampled)
> **incremental-cycle-detection-multi**(insert 15000, RandomSource) x **31.58** ops/sec ±2.77% (52 runs sampled)
>
> **graphlib**(insert15000, RandomSource) x **0.17** ops/sec ±1.63% (5 runs sampled)
> **graphlib**(insert15000, RandomSource) x **0.19** ops/sec ±1.83% (5 runs sampled)
(200 vertices, 15000 random (same for each algorithm) edges added)
(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)
# JavaScript environment

@@ -106,3 +110,3 @@

import * as Map from "core-js/es6/map";
const graph = new GenericGraphAdapter({mapConstructor: Map}):
const graph = GenericGraphAdapter.create({mapConstructor: Map}):
```

@@ -148,2 +152,8 @@

# 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

@@ -150,0 +160,0 @@ - Added two methods for accessing edge data of incoming / outgoing edges: `getEdgeDataFrom`, `getEdgeDataTo`

.babelrc
dist/src/InternalHeader.d.ts
dist/src/InternalHeader.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