incremental-cycle-detect
Advanced tools
Comparing version 0.3.0 to 0.4.0
@@ -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/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)}); | ||
(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){var f=0,g=this.g.getEdgeData(a,b);void 0!==g&&(f=g.size);var h=this.g.contractEdge(a,b,c,d(e,this.mapConstructor));return h&&(this.edgeCount-=f),h},a.prototype.contractLabeledEdge=function(a,b,c,d,e){return 1===this.getEdgeCountBetween(a,b)&&!!this.hasLabeledEdge(a,b,c)&&this.contractEdge(a,b,d,e)},a.prototype.canContractLabeledEdge=function(a,b,c){return 1===this.getEdgeCountBetween(a,b)&&!!this.hasLabeledEdge(a,b,c)&&this.canContractEdge(a,b)},a.prototype.canContractOneEdge=function(a,b){return 1===this.getEdgeCountBetween(a,b)&&this.canContractEdge(a,b)},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){var b=this;return f.forEach(function(a){var c=a[1];void 0!==c&&(b.edgeCount-=c.size)},this.g.getEdgesWithDataFrom(a),this.g.getEdgesWithDataTo(a)),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.forEach=function(a){for(var b=[],c=1;c<arguments.length;c++)b[c-1]=arguments[c];for(var d=0,e=b.length;d<e;++d)for(var f=b[d],g=f.next();!g.done;g=f.next())a(g.value)},c.combineIterators=function(){for(var a=[],b=0;b<arguments.length;b++)a[b]=arguments[b];var d=0;return{next:function(){if(d>=a.length)return c.DoneIteratorResult;var b=a[d].next();if(b.done){if(d+=1,d>=a.length)return c.DoneIteratorResult;b=a[d].next()}return b.done?c.DoneIteratorResult:{done:!1,value:b.value}}}},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)}); |
@@ -1,3 +0,4 @@ | ||
import { BinaryOperator, Maybe, Omit, Pair, Triple, TypedFunction, UnaryOperator } from "andross"; | ||
import { BinaryOperator, Maybe, Omit, Pair, Triple, TypedFunction, TypedTriFunction, UnaryOperator } from "andross"; | ||
import { Graph, GraphOptions } from "graphlib"; | ||
export declare type LabelGenerator<TVertex, TEdgeData, TEdgeLabel> = TypedTriFunction<TVertex, TVertex, TEdgeData, Maybe<TEdgeLabel>>; | ||
export interface VertexData { | ||
@@ -4,0 +5,0 @@ order: number; |
@@ -5,5 +5,5 @@ import { BinaryOperator, Maybe, Pair, Quadruple, Triple, TypedFunction, UnaryOperator } from "andross"; | ||
static create<TVertex = any, TEdgeData = any, TEdgeLabel = any>(options?: Partial<MultiGraphAdapterOptions<TVertex, TEdgeData, TEdgeLabel>>): MultiGraphAdapter<TVertex, TEdgeData, TEdgeLabel>; | ||
private g; | ||
private edgeCount; | ||
private mapConstructor; | ||
private readonly g; | ||
private readonly mapConstructor; | ||
private constructor(); | ||
@@ -14,3 +14,2 @@ mapLabeled<TClonedVertex, TClonedEdgeData, TClonedEdgeLabel>(vertexMapper: TypedFunction<TVertex, TClonedVertex>, edgeDataMapper: TypedFunction<TEdgeData, TClonedEdgeData>, labelMapper: TypedFunction<TEdgeLabel, TClonedEdgeLabel>): MultiGraphAdapter<TClonedVertex, TClonedEdgeData, TClonedEdgeLabel>; | ||
addLabeledEdge(from: TVertex, to: TVertex, label: Maybe<TEdgeLabel>, data?: TEdgeData): boolean; | ||
addLabeledEdge(from: TVertex, to: TVertex, label?: TEdgeLabel, data?: TEdgeData): boolean; | ||
canAddEdge(from: TVertex, to: TVertex, label?: TEdgeLabel): boolean; | ||
@@ -24,2 +23,5 @@ addEdge(from: TVertex, to: TVertex, data?: TEdgeData, label?: TEdgeLabel): boolean; | ||
contractEdge(from: TVertex, to: TVertex, vertexMerger?: BinaryOperator<TVertex>, edgeMerger?: BinaryOperator<TEdgeData>): boolean; | ||
contractLabeledEdge(from: TVertex, to: TVertex, label?: TEdgeLabel, vertexMerger?: BinaryOperator<TVertex>, edgeMerger?: BinaryOperator<TEdgeData>): boolean; | ||
canContractLabeledEdge(from: TVertex, to: TVertex, label?: TEdgeLabel): boolean; | ||
canContractOneEdge(from: TVertex, to: TVertex): boolean; | ||
canContractEdge(from: TVertex, to: TVertex): boolean; | ||
@@ -26,0 +28,0 @@ deleteLabeledEdge(from: TVertex, to: TVertex, label: Maybe<TEdgeLabel>): boolean; |
@@ -130,4 +130,37 @@ "use strict"; | ||
MultiGraphAdapter.prototype.contractEdge = function (from, to, vertexMerger, edgeMerger) { | ||
return this.g.contractEdge(from, to, vertexMerger, createMerger(edgeMerger, this.mapConstructor)); | ||
var deletionCount = 0; | ||
var data = this.g.getEdgeData(from, to); | ||
if (data !== undefined) { | ||
deletionCount = data.size; | ||
} | ||
var wasContracted = this.g.contractEdge(from, to, vertexMerger, createMerger(edgeMerger, this.mapConstructor)); | ||
if (wasContracted) { | ||
this.edgeCount -= deletionCount; | ||
} | ||
return wasContracted; | ||
}; | ||
MultiGraphAdapter.prototype.contractLabeledEdge = function (from, to, label, vertexMerger, edgeMerger) { | ||
if (this.getEdgeCountBetween(from, to) !== 1) { | ||
return false; | ||
} | ||
if (!this.hasLabeledEdge(from, to, label)) { | ||
return false; | ||
} | ||
return this.contractEdge(from, to, vertexMerger, edgeMerger); | ||
}; | ||
MultiGraphAdapter.prototype.canContractLabeledEdge = function (from, to, label) { | ||
if (this.getEdgeCountBetween(from, to) !== 1) { | ||
return false; | ||
} | ||
if (!this.hasLabeledEdge(from, to, label)) { | ||
return false; | ||
} | ||
return this.canContractEdge(from, to); | ||
}; | ||
MultiGraphAdapter.prototype.canContractOneEdge = function (from, to) { | ||
if (this.getEdgeCountBetween(from, to) !== 1) { | ||
return false; | ||
} | ||
return this.canContractEdge(from, to); | ||
}; | ||
MultiGraphAdapter.prototype.canContractEdge = function (from, to) { | ||
@@ -158,2 +191,9 @@ return this.g.canContractEdge(from, to); | ||
MultiGraphAdapter.prototype.deleteVertex = function (vertex) { | ||
var _this = this; | ||
util_1.forEach(function (data) { | ||
var edges = data[1]; | ||
if (edges !== undefined) { | ||
_this.edgeCount -= edges.size; | ||
} | ||
}, this.g.getEdgesWithDataFrom(vertex), this.g.getEdgesWithDataTo(vertex)); | ||
return this.g.deleteVertex(vertex); | ||
@@ -160,0 +200,0 @@ }; |
@@ -1,2 +0,2 @@ | ||
import { BinaryOperator, Maybe, Predicate, TypedFunction } from "andross"; | ||
import { BinaryOperator, Consumer, Maybe, Predicate, TypedFunction } from "andross"; | ||
import { CommonAdapter, CycleDetector, GraphAdapter, VertexData } from "./Header"; | ||
@@ -8,2 +8,4 @@ export declare function takeFirst<T>(first: T, second: T): T; | ||
export declare function toArray<T>(it: Iterator<T>): T[]; | ||
export declare function forEach<T>(callback: Consumer<T>, ...iterators: Iterator<T>[]): void; | ||
export declare function combineIterators<T>(...iterators: Iterator<T>[]): Iterator<T>; | ||
export declare function createMappedIterator<T, V>(it: Iterator<T>, mapper: TypedFunction<T, V>): Iterator<V>; | ||
@@ -10,0 +12,0 @@ export declare function createFilteredIterator<T>(it: Iterator<Maybe<T>>): Iterator<T>; |
@@ -37,2 +37,44 @@ "use strict"; | ||
exports.toArray = toArray; | ||
function forEach(callback) { | ||
var iterators = []; | ||
for (var _i = 1; _i < arguments.length; _i++) { | ||
iterators[_i - 1] = arguments[_i]; | ||
} | ||
for (var i = 0, j = iterators.length; i < j; ++i) { | ||
for (var it_1 = iterators[i], next = it_1.next(); !next.done; next = it_1.next()) { | ||
callback(next.value); | ||
} | ||
} | ||
} | ||
exports.forEach = forEach; | ||
function combineIterators() { | ||
var iterators = []; | ||
for (var _i = 0; _i < arguments.length; _i++) { | ||
iterators[_i] = arguments[_i]; | ||
} | ||
var iteratorIndex = 0; | ||
return { | ||
next: function () { | ||
if (iteratorIndex >= iterators.length) { | ||
return exports.DoneIteratorResult; | ||
} | ||
var res = iterators[iteratorIndex].next(); | ||
if (res.done) { | ||
iteratorIndex += 1; | ||
if (iteratorIndex >= iterators.length) { | ||
return exports.DoneIteratorResult; | ||
} | ||
res = iterators[iteratorIndex].next(); | ||
} | ||
if (res.done) { | ||
return exports.DoneIteratorResult; | ||
} | ||
return { | ||
done: false, | ||
value: res.value, | ||
}; | ||
} | ||
}; | ||
} | ||
exports.combineIterators = combineIterators; | ||
function createMappedIterator(it, mapper) { | ||
@@ -77,7 +119,7 @@ return { | ||
while (currentNext.done) { | ||
var it_1 = its[++i]; | ||
if (it_1 === undefined) { | ||
var it_2 = its[++i]; | ||
if (it_2 === undefined) { | ||
return exports.DoneIteratorResult; | ||
} | ||
currentIterator = it_1; | ||
currentIterator = it_2; | ||
currentNext = currentIterator.next(); | ||
@@ -187,3 +229,3 @@ } | ||
if (newVertex !== from) { | ||
for (var it_2 = adapter.getSuccessorsOf(from), res = it_2.next(); !res.done; res = it_2.next()) { | ||
for (var it_3 = adapter.getSuccessorsOf(from), res = it_3.next(); !res.done; res = it_3.next()) { | ||
var data = adapter.getEdgeData(from, res.value); | ||
@@ -193,3 +235,3 @@ adapter.deleteEdge(from, res.value); | ||
} | ||
for (var it_3 = adapter.getPredecessorsOf(from), res = it_3.next(); !res.done; res = it_3.next()) { | ||
for (var it_4 = adapter.getPredecessorsOf(from), res = it_4.next(); !res.done; res = it_4.next()) { | ||
var data = adapter.getEdgeData(res.value, from); | ||
@@ -201,3 +243,3 @@ adapter.deleteEdge(res.value, from); | ||
if (newVertex !== to) { | ||
for (var it_4 = adapter.getSuccessorsOf(to), res = it_4.next(); !res.done; res = it_4.next()) { | ||
for (var it_5 = adapter.getSuccessorsOf(to), res = it_5.next(); !res.done; res = it_5.next()) { | ||
var data = adapter.getEdgeData(to, res.value); | ||
@@ -207,3 +249,3 @@ adapter.deleteEdge(to, res.value); | ||
} | ||
for (var it_5 = adapter.getPredecessorsOf(to), res = it_5.next(); !res.done; res = it_5.next()) { | ||
for (var it_6 = adapter.getPredecessorsOf(to), res = it_6.next(); !res.done; res = it_6.next()) { | ||
var data = adapter.getEdgeData(res.value, to); | ||
@@ -210,0 +252,0 @@ adapter.deleteEdge(res.value, to); |
{ | ||
"name": "incremental-cycle-detect", | ||
"version": "0.3.0", | ||
"version": "0.4.0", | ||
"description": "Keeps a directed acyclic graph topologically sorted each time you add an edge or vertex to check for cycles.", | ||
@@ -45,6 +45,6 @@ "main": "dist/index.js", | ||
"@types/benchmark": "^1.0.31", | ||
"@types/chai": "^4.1.3", | ||
"@types/chai": "^4.1.5", | ||
"@types/graphlib": "^2.1.4", | ||
"@types/random-js": "^1.0.30", | ||
"andross": "^0.3.3", | ||
"@types/random-js": "^1.0.31", | ||
"andross": "^0.3.5", | ||
"babel-minify": "^0.4.3", | ||
@@ -54,16 +54,16 @@ "benchmark": "^2.1.4", | ||
"chai": "^4.1.2", | ||
"elbe": "^0.4.1", | ||
"elbe": "^0.4.2", | ||
"graphlib": "^2.1.5", | ||
"jsperf": "^0.2.1", | ||
"mocha": "^5.2.0", | ||
"mocha-typescript": "^1.1.14", | ||
"nyc": "^12.0.2", | ||
"mocha-typescript": "^1.1.17", | ||
"nyc": "^13.0.1", | ||
"random-js": "^1.0.8", | ||
"ts-mocha": "^1.2.0", | ||
"ts-node": "^6.1.0", | ||
"tslib": "^1.9.2", | ||
"tslint": "^5.10.0", | ||
"ts-mocha": "^2.0.0", | ||
"ts-node": "^7.0.1", | ||
"tslib": "^1.9.3", | ||
"tslint": "^5.11.0", | ||
"tslint-strict-null-checks": "^1.0.1", | ||
"typedoc": "^0.11.1", | ||
"typescript": "^2.9.1" | ||
"typedoc": "^0.12.0", | ||
"typescript": "^3.0.3" | ||
}, | ||
@@ -70,0 +70,0 @@ "homepage": "https://github.com/blutorange/js-incremental-cycle-detect#readme", |
@@ -148,2 +148,7 @@ Lets you add edges to a [directed acyclic graph](https://en.wikipedia.org/wiki/Directed_acyclic_graph) and be told whether this edge | ||
# 0.4.0 | ||
- Fixed bug with `MultiGraphAdapter`: `#getLabelledEdge()` updated incorrectly. | ||
- Added an additional method `#contractLabeledEdge`, While `#contractEdge` contract all edges (irrespective of their label) between two vertices, `#contractEdge` contracts just one particular edge with a specific label. Note that since cycle are forbidden, a certain labeled edge between two vertices can only be contracted if it is the only edge between those two vertices. `#contractLabeled` refuses two contract in such a case, while `#contractVertices` contract all edges. You can check with `#canContractEdge` and `#canContractLabeledEdge`. | ||
- Removed deprecated `MultiGraphAdapter#addLabeledEdge(from: TVertex, to: TVertex, label?: TEdgeLabel, data?: TEdgeData): boolean` | ||
# 0.3.0 | ||
@@ -150,0 +155,0 @@ - Added `Algorithm#findWeaklyConnectedComponents`. |
Sorry, the diff of this file is too big to display
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
175894
3165
177
119