New Case Study:See how Anthropic automated 95% of dependency reviews with Socket.Learn More →
js-graph - npm Package Compare versions
Comparing version 1.0.0-alpha to 1.1.0-alpha
| 'use strict'; | ||
| // //////////////////////////////////////////////////////////////////////////////////////////////////////////////////// | ||
| // // Utility ///////////////////////////////////////////////////////////////////////////////////////////////////////// | ||
| // //////////////////////////////////////////////////////////////////////////////////////////////////////////////////// | ||
| // //////////////////////////////////////////////////////////////////////////////////////////////// | ||
| // // Utility ///////////////////////////////////////////////////////////////////////////////////// | ||
| // //////////////////////////////////////////////////////////////////////////////////////////////// | ||
@@ -34,5 +34,5 @@ class Callbacks { | ||
| // //////////////////////////////////////////////////////////////////////////////////////////////////////////////////// | ||
| // // JsGraph class /////////////////////////////////////////////////////////////////////////////////////////////////// | ||
| // //////////////////////////////////////////////////////////////////////////////////////////////////////////////////// | ||
| // //////////////////////////////////////////////////////////////////////////////////////////////// | ||
| // // JsGraph class /////////////////////////////////////////////////////////////////////////////// | ||
| // //////////////////////////////////////////////////////////////////////////////////////////////// | ||
@@ -348,33 +348,78 @@ export default class JsGraph { | ||
| /////////////////////////////////////////////// | ||
| // | ||
| //get vertices() { | ||
| // return { | ||
| // _graph: this, | ||
| // get length() { return this._graph._vertexCount }, | ||
| // [Symbol.iterator]: function*() { | ||
| // var keys = Object.keys(this._graph._vertices); | ||
| // for (let i = 0; i < keys.length; ++i) { | ||
| // yield [keys[i], this._graph._vertices[keys[i]]]; | ||
| // } | ||
| // } | ||
| // }; | ||
| //} | ||
| // | ||
| //get edges() { | ||
| // return { | ||
| // _graph: this, | ||
| // get length() { return this._graph._edgeCount }, | ||
| // [Symbol.iterator]: function*() { | ||
| // var fromKeys = Object.keys(this._graph._edges); | ||
| // for (let i = 0; i < fromKeys.length; ++i) { | ||
| // var toKeys = Object.keys(this._graph._edges[fromKeys[i]]); | ||
| // for (let j = 0; j < toKeys.length; ++j) { | ||
| // yield [fromKeys[i], toKeys[j], this._graph._edges[fromKeys[i]][toKeys[j]]]; | ||
| // } | ||
| // } | ||
| // } | ||
| // }; | ||
| //} | ||
| [Symbol.iterator]() { return this.vertices() } | ||
| *vertices() { | ||
| for (let key of Object.keys(this._vertices)) { | ||
| if (this.hasVertex(key)) { | ||
| yield [key, this._vertices[key]]; | ||
| } | ||
| } | ||
| } | ||
| *edges() { | ||
| for (let from of Object.keys(this._edges)) { | ||
| for (let to of Object.keys(this._edges[from])) { | ||
| if (this.hasEdge(from, to)) { | ||
| yield [from, to, this._edges[from][to]]; | ||
| } | ||
| } | ||
| } | ||
| } | ||
| verticesFrom(from) { | ||
| if (!this.hasVertex(from)) { throw new JsGraph.VertexNotExistsError(from) } | ||
| return this._verticesFrom(from); | ||
| } | ||
| *_verticesFrom(from) { | ||
| for (let to of Object.keys(this._edges[from])) { | ||
| if (this.hasEdge(from, to)) { | ||
| yield [to, this._vertices[to], this._edges[from][to]]; | ||
| } | ||
| } | ||
| } | ||
| verticesTo(to) { | ||
| if (!this.hasVertex(to)) { throw new JsGraph.VertexNotExistsError(to) } | ||
| return this._verticesTo(to); | ||
| } | ||
| *_verticesTo(to) { | ||
| for (let from of Object.keys(this._reverseEdges[to])) { | ||
| if (this.hasEdge(from, to)) { | ||
| yield [from, this._vertices[from], this._edges[from][to]]; | ||
| } | ||
| } | ||
| } | ||
| *vertices_topologically() { | ||
| var visited = []; | ||
| var handled = {}; | ||
| var _this = this; | ||
| function *visit(a) { | ||
| visited.push(a); | ||
| var i = visited.indexOf(a); | ||
| if (i !== visited.length - 1) { | ||
| var cycle = visited.slice(i + 1).reverse(); | ||
| throw new JsGraph.CycleError(cycle); | ||
| } | ||
| if (!handled[a]) { | ||
| for (let [b] of _this.verticesTo(a)) { | ||
| yield* visit(b); | ||
| } | ||
| if (_this.hasVertex(a)) { | ||
| yield [a, _this._vertices[a]]; | ||
| } | ||
| handled[a] = true; | ||
| } | ||
| visited.pop(); | ||
| } | ||
| for (let [a] of this.vertices()) { | ||
| if (!handled[a]) { | ||
| yield* visit(a); | ||
| } | ||
| } | ||
| } | ||
| ////////////////////////////// | ||
@@ -492,5 +537,5 @@ ////////// Clearing ////////// | ||
| // //////////////////////////////////////////////////////////////////////////////////////////////////////////////////// | ||
| // // Errors ////////////////////////////////////////////////////////////////////////////////////////////////////////// | ||
| // //////////////////////////////////////////////////////////////////////////////////////////////////////////////////// | ||
| // //////////////////////////////////////////////////////////////////////////////////////////////// | ||
| // // Errors ////////////////////////////////////////////////////////////////////////////////////// | ||
| // //////////////////////////////////////////////////////////////////////////////////////////////// | ||
@@ -497,0 +542,0 @@ JsGraph.VertexExistsError = class VertexExistsError extends Error { |
1438
dist/js-graph.js
@@ -59,2 +59,4 @@ (function webpackUniversalModuleDefinition(root, factory) { | ||
| var _slicedToArray = function (arr, i) { if (Array.isArray(arr)) { return arr; } else if (Symbol.iterator in Object(arr)) { var _arr = []; for (var _iterator = arr[Symbol.iterator](), _step; !(_step = _iterator.next()).done;) { _arr.push(_step.value); if (i && _arr.length === i) break; } return _arr; } else { throw new TypeError("Invalid attempt to destructure non-iterable instance"); } }; | ||
| var _defineProperty = function (obj, key, value) { return Object.defineProperty(obj, key, { value: value, enumerable: true, configurable: true, writable: true }); }; | ||
@@ -64,2 +66,4 @@ | ||
| var _createComputedClass = (function () { function defineProperties(target, props) { for (var i = 0; i < props.length; i++) { var prop = props[i]; prop.configurable = true; if (prop.value) prop.writable = true; Object.defineProperty(target, prop.key, prop); } } return function (Constructor, protoProps, staticProps) { if (protoProps) defineProperties(Constructor.prototype, protoProps); if (staticProps) defineProperties(Constructor, staticProps); return Constructor; }; })(); | ||
| var _createClass = (function () { function defineProperties(target, props) { for (var key in props) { var prop = props[key]; prop.configurable = true; if (prop.value) prop.writable = true; } Object.defineProperties(target, props); } return function (Constructor, protoProps, staticProps) { if (protoProps) defineProperties(Constructor.prototype, protoProps); if (staticProps) defineProperties(Constructor, staticProps); return Constructor; }; })(); | ||
@@ -69,5 +73,5 @@ | ||
| // //////////////////////////////////////////////////////////////////////////////////////////////////////////////////// | ||
| // // Utility ///////////////////////////////////////////////////////////////////////////////////////////////////////// | ||
| // //////////////////////////////////////////////////////////////////////////////////////////////////////////////////// | ||
| // //////////////////////////////////////////////////////////////////////////////////////////////// | ||
| // // Utility ///////////////////////////////////////////////////////////////////////////////////// | ||
| // //////////////////////////////////////////////////////////////////////////////////////////////// | ||
@@ -113,5 +117,5 @@ var Callbacks = (function () { | ||
| // //////////////////////////////////////////////////////////////////////////////////////////////////////////////////// | ||
| // // JsGraph class /////////////////////////////////////////////////////////////////////////////////////////////////// | ||
| // //////////////////////////////////////////////////////////////////////////////////////////////////////////////////// | ||
| // //////////////////////////////////////////////////////////////////////////////////////////////// | ||
| // // JsGraph class /////////////////////////////////////////////////////////////////////////////// | ||
| // //////////////////////////////////////////////////////////////////////////////////////////////// | ||
@@ -133,457 +137,981 @@ var JsGraph = (function () { | ||
| _createClass(JsGraph, { | ||
| onAddVertex: { | ||
| _createComputedClass(JsGraph, [{ | ||
| key: "onAddVertex", | ||
| ////////////////////////////// | ||
| ////////// Vertices ////////// | ||
| ////////////////////////////// | ||
| ////////////////////////////// | ||
| ////////// Vertices ////////// | ||
| ////////////////////////////// | ||
| value: function onAddVertex(fn) { | ||
| return this._addVertexCallbacks.add(fn); | ||
| } | ||
| }, | ||
| onRemoveVertex: { | ||
| value: function onRemoveVertex(fn) { | ||
| return this._removeVertexCallbacks.add(fn); | ||
| } | ||
| }, | ||
| addNewVertex: { | ||
| value: function onAddVertex(fn) { | ||
| return this._addVertexCallbacks.add(fn); | ||
| } | ||
| }, { | ||
| key: "onRemoveVertex", | ||
| value: function onRemoveVertex(fn) { | ||
| return this._removeVertexCallbacks.add(fn); | ||
| } | ||
| }, { | ||
| key: "addNewVertex", | ||
| //// creating them //// | ||
| //// creating them //// | ||
| value: function addNewVertex(key, value) { | ||
| if (this.hasVertex(key)) { | ||
| throw new JsGraph.VertexExistsError(key, this._vertices[key]); | ||
| } | ||
| this._vertices[key] = value; | ||
| this._edges[key] = {}; | ||
| this._reverseEdges[key] = {}; | ||
| this._vertexCount += 1; | ||
| this._addVertexCallbacks.fire(key, value); | ||
| value: function addNewVertex(key, value) { | ||
| if (this.hasVertex(key)) { | ||
| throw new JsGraph.VertexExistsError(key, this._vertices[key]); | ||
| } | ||
| }, | ||
| setVertex: { | ||
| value: function setVertex(key, value) { | ||
| if (!this.hasVertex(key)) { | ||
| throw new JsGraph.VertexNotExistsError(key); | ||
| } | ||
| this._vertices[key] = value; | ||
| this._vertices[key] = value; | ||
| this._edges[key] = {}; | ||
| this._reverseEdges[key] = {}; | ||
| this._vertexCount += 1; | ||
| this._addVertexCallbacks.fire(key, value); | ||
| } | ||
| }, { | ||
| key: "setVertex", | ||
| value: function setVertex(key, value) { | ||
| if (!this.hasVertex(key)) { | ||
| throw new JsGraph.VertexNotExistsError(key); | ||
| } | ||
| }, | ||
| ensureVertex: { | ||
| value: function ensureVertex(key, value) { | ||
| if (!this.hasVertex(key)) { | ||
| this.addNewVertex(key, value); | ||
| } | ||
| this._vertices[key] = value; | ||
| } | ||
| }, { | ||
| key: "ensureVertex", | ||
| value: function ensureVertex(key, value) { | ||
| if (!this.hasVertex(key)) { | ||
| this.addNewVertex(key, value); | ||
| } | ||
| }, | ||
| addVertex: { | ||
| value: function addVertex(key, value) { | ||
| if (this.hasVertex(key)) { | ||
| this.setVertex(key, value); | ||
| } else { | ||
| this.addNewVertex(key, value); | ||
| } | ||
| } | ||
| }, { | ||
| key: "addVertex", | ||
| value: function addVertex(key, value) { | ||
| if (this.hasVertex(key)) { | ||
| this.setVertex(key, value); | ||
| } else { | ||
| this.addNewVertex(key, value); | ||
| } | ||
| }, | ||
| removeExistingVertex: { | ||
| } | ||
| }, { | ||
| key: "removeExistingVertex", | ||
| //// removing them //// | ||
| //// removing them //// | ||
| value: function removeExistingVertex(key) { | ||
| if (!this.hasVertex(key)) { | ||
| throw new JsGraph.VertexNotExistsError(key); | ||
| } | ||
| if (Object.keys(this._edges[key]).length) { | ||
| throw new JsGraph.HasConnectedEdgesError(key); | ||
| } | ||
| if (Object.keys(this._reverseEdges[key]).length) { | ||
| throw new JsGraph.HasConnectedEdgesError(key); | ||
| } | ||
| var valueOfRemovedVertex = this._vertices[key]; | ||
| delete this._vertices[key]; | ||
| this._vertexCount -= 1; | ||
| this._removeVertexCallbacks.fire(key, valueOfRemovedVertex); | ||
| value: function removeExistingVertex(key) { | ||
| if (!this.hasVertex(key)) { | ||
| throw new JsGraph.VertexNotExistsError(key); | ||
| } | ||
| }, | ||
| destroyExistingVertex: { | ||
| value: function destroyExistingVertex(key) { | ||
| var _this = this; | ||
| if (!this.hasVertex(key)) { | ||
| throw new JsGraph.VertexNotExistsError(key); | ||
| } | ||
| this.eachVertexFrom(key, function (to) { | ||
| _this.removeEdge(key, to); | ||
| }); | ||
| this.eachVertexTo(key, function (from) { | ||
| _this.removeEdge(from, key); | ||
| }); | ||
| this.removeExistingVertex(key); | ||
| if (Object.keys(this._edges[key]).length) { | ||
| throw new JsGraph.HasConnectedEdgesError(key); | ||
| } | ||
| }, | ||
| removeVertex: { | ||
| value: function removeVertex(key) { | ||
| if (this.hasVertex(key)) { | ||
| this.removeExistingVertex(key); | ||
| } | ||
| if (Object.keys(this._reverseEdges[key]).length) { | ||
| throw new JsGraph.HasConnectedEdgesError(key); | ||
| } | ||
| }, | ||
| destroyVertex: { | ||
| value: function destroyVertex(key) { | ||
| if (this.hasVertex(key)) { | ||
| this.destroyExistingVertex(key); | ||
| } | ||
| } | ||
| }, | ||
| vertexCount: { | ||
| var valueOfRemovedVertex = this._vertices[key]; | ||
| delete this._vertices[key]; | ||
| this._vertexCount -= 1; | ||
| this._removeVertexCallbacks.fire(key, valueOfRemovedVertex); | ||
| } | ||
| }, { | ||
| key: "destroyExistingVertex", | ||
| value: function destroyExistingVertex(key) { | ||
| var _this = this; | ||
| //// querying them //// | ||
| value: function vertexCount() { | ||
| return this._vertexCount; | ||
| if (!this.hasVertex(key)) { | ||
| throw new JsGraph.VertexNotExistsError(key); | ||
| } | ||
| }, | ||
| hasVertex: { | ||
| value: function hasVertex(key) { | ||
| return key in this._vertices; | ||
| this.eachVertexFrom(key, function (to) { | ||
| _this.removeEdge(key, to); | ||
| }); | ||
| this.eachVertexTo(key, function (from) { | ||
| _this.removeEdge(from, key); | ||
| }); | ||
| this.removeExistingVertex(key); | ||
| } | ||
| }, { | ||
| key: "removeVertex", | ||
| value: function removeVertex(key) { | ||
| if (this.hasVertex(key)) { | ||
| this.removeExistingVertex(key); | ||
| } | ||
| }, | ||
| vertexValue: { | ||
| value: function vertexValue(key) { | ||
| return this._vertices[key]; | ||
| } | ||
| }, { | ||
| key: "destroyVertex", | ||
| value: function destroyVertex(key) { | ||
| if (this.hasVertex(key)) { | ||
| this.destroyExistingVertex(key); | ||
| } | ||
| }, | ||
| onAddEdge: { | ||
| } | ||
| }, { | ||
| key: "vertexCount", | ||
| /////////////////////////// | ||
| ////////// Edges ////////// | ||
| /////////////////////////// | ||
| //// querying them //// | ||
| value: function onAddEdge(fn) { | ||
| return this._addEdgeCallbacks.add(fn); | ||
| value: function vertexCount() { | ||
| return this._vertexCount; | ||
| } | ||
| }, { | ||
| key: "hasVertex", | ||
| value: function hasVertex(key) { | ||
| return key in this._vertices; | ||
| } | ||
| }, { | ||
| key: "vertexValue", | ||
| value: function vertexValue(key) { | ||
| return this._vertices[key]; | ||
| } | ||
| }, { | ||
| key: "onAddEdge", | ||
| /////////////////////////// | ||
| ////////// Edges ////////// | ||
| /////////////////////////// | ||
| value: function onAddEdge(fn) { | ||
| return this._addEdgeCallbacks.add(fn); | ||
| } | ||
| }, { | ||
| key: "onRemoveEdge", | ||
| value: function onRemoveEdge(fn) { | ||
| return this._removeEdgeCallbacks.add(fn); | ||
| } | ||
| }, { | ||
| key: "addNewEdge", | ||
| value: function addNewEdge(from, to, value) { | ||
| if (this.hasEdge(from, to)) { | ||
| throw new JsGraph.EdgeExistsError(from, to, this.edgeValue(from, to)); | ||
| } | ||
| }, | ||
| onRemoveEdge: { | ||
| value: function onRemoveEdge(fn) { | ||
| return this._removeEdgeCallbacks.add(fn); | ||
| } | ||
| }, | ||
| addNewEdge: { | ||
| value: function addNewEdge(from, to, value) { | ||
| if (this.hasEdge(from, to)) { | ||
| throw new JsGraph.EdgeExistsError(from, to, this.edgeValue(from, to)); | ||
| if (!this.hasVertex(from)) { | ||
| if (this.hasVertex(to)) { | ||
| throw new JsGraph.VertexNotExistsError(from); | ||
| } else { | ||
| throw new JsGraph.VertexNotExistsError(from).v(to); | ||
| } | ||
| if (!this.hasVertex(from)) { | ||
| if (this.hasVertex(to)) { | ||
| throw new JsGraph.VertexNotExistsError(from); | ||
| } else { | ||
| throw new JsGraph.VertexNotExistsError(from).v(to); | ||
| } | ||
| } else if (!this.hasVertex(to)) { | ||
| throw new JsGraph.VertexNotExistsError(to); | ||
| } | ||
| this._edges[from][to] = value; | ||
| this._reverseEdges[to][from] = null; | ||
| this._edgeCount += 1; | ||
| this._addEdgeCallbacks.fire(from, to, value); | ||
| } else if (!this.hasVertex(to)) { | ||
| throw new JsGraph.VertexNotExistsError(to); | ||
| } | ||
| }, | ||
| createNewEdge: { | ||
| value: function createNewEdge(from, to, value) { | ||
| if (this.hasEdge(from, to)) { | ||
| throw new JsGraph.EdgeExistsError(from, to, this.edgeValue(from, to)); | ||
| } | ||
| this.ensureVertex(from); | ||
| this.ensureVertex(to); | ||
| this.addNewEdge(from, to, value); | ||
| this._edges[from][to] = value; | ||
| this._reverseEdges[to][from] = null; | ||
| this._edgeCount += 1; | ||
| this._addEdgeCallbacks.fire(from, to, value); | ||
| } | ||
| }, { | ||
| key: "createNewEdge", | ||
| value: function createNewEdge(from, to, value) { | ||
| if (this.hasEdge(from, to)) { | ||
| throw new JsGraph.EdgeExistsError(from, to, this.edgeValue(from, to)); | ||
| } | ||
| }, | ||
| setEdge: { | ||
| value: function setEdge(from, to, value) { | ||
| if (!this.hasEdge(from, to)) { | ||
| throw new JsGraph.EdgeNotExistsError(from, to); | ||
| } | ||
| this._edges[from][to] = value; | ||
| this.ensureVertex(from); | ||
| this.ensureVertex(to); | ||
| this.addNewEdge(from, to, value); | ||
| } | ||
| }, { | ||
| key: "setEdge", | ||
| value: function setEdge(from, to, value) { | ||
| if (!this.hasEdge(from, to)) { | ||
| throw new JsGraph.EdgeNotExistsError(from, to); | ||
| } | ||
| }, | ||
| spanEdge: { | ||
| value: function spanEdge(from, to, value) { | ||
| if (!this.hasVertex(from)) { | ||
| if (this.hasVertex(to)) { | ||
| throw new JsGraph.VertexNotExistsError(from); | ||
| } else { | ||
| throw new JsGraph.VertexNotExistsError(from).v(to); | ||
| } | ||
| } else if (!this.hasVertex(to)) { | ||
| throw new JsGraph.VertexNotExistsError(to); | ||
| } | ||
| if (!this.hasEdge(from, to)) { | ||
| this.addNewEdge(from, to, value); | ||
| } | ||
| } | ||
| }, | ||
| addEdge: { | ||
| value: function addEdge(from, to, value) { | ||
| if (this.hasEdge(from, to)) { | ||
| this.setEdge(from, to, value); | ||
| this._edges[from][to] = value; | ||
| } | ||
| }, { | ||
| key: "spanEdge", | ||
| value: function spanEdge(from, to, value) { | ||
| if (!this.hasVertex(from)) { | ||
| if (this.hasVertex(to)) { | ||
| throw new JsGraph.VertexNotExistsError(from); | ||
| } else { | ||
| this.addNewEdge(from, to, value); | ||
| throw new JsGraph.VertexNotExistsError(from).v(to); | ||
| } | ||
| } else if (!this.hasVertex(to)) { | ||
| throw new JsGraph.VertexNotExistsError(to); | ||
| } | ||
| }, | ||
| ensureEdge: { | ||
| value: function ensureEdge(from, to, value) { | ||
| if (!this.hasEdge(from, to)) { | ||
| this.createNewEdge(from, to, value); | ||
| } | ||
| if (!this.hasEdge(from, to)) { | ||
| this.addNewEdge(from, to, value); | ||
| } | ||
| }, | ||
| createEdge: { | ||
| value: function createEdge(from, to, value) { | ||
| if (this.hasEdge(from, to)) { | ||
| this.setEdge(from, to, value); | ||
| } else { | ||
| this.createNewEdge(from, to, value); | ||
| } | ||
| } | ||
| }, { | ||
| key: "addEdge", | ||
| value: function addEdge(from, to, value) { | ||
| if (this.hasEdge(from, to)) { | ||
| this.setEdge(from, to, value); | ||
| } else { | ||
| this.addNewEdge(from, to, value); | ||
| } | ||
| }, | ||
| removeExistingEdge: { | ||
| } | ||
| }, { | ||
| key: "ensureEdge", | ||
| value: function ensureEdge(from, to, value) { | ||
| if (!this.hasEdge(from, to)) { | ||
| this.createNewEdge(from, to, value); | ||
| } | ||
| } | ||
| }, { | ||
| key: "createEdge", | ||
| value: function createEdge(from, to, value) { | ||
| if (this.hasEdge(from, to)) { | ||
| this.setEdge(from, to, value); | ||
| } else { | ||
| this.createNewEdge(from, to, value); | ||
| } | ||
| } | ||
| }, { | ||
| key: "removeExistingEdge", | ||
| //// removing them //// | ||
| //// removing them //// | ||
| value: function removeExistingEdge(from, to) { | ||
| if (!this.hasEdge(from, to)) { | ||
| throw new JsGraph.EdgeNotExistsError(from, to); | ||
| } | ||
| var valueOfRemovedEdge = this._edges[from][to]; | ||
| delete this._edges[from][to]; | ||
| delete this._reverseEdges[to][from]; | ||
| this._edgeCount -= 1; | ||
| this._removeEdgeCallbacks.fire(from, to, valueOfRemovedEdge); | ||
| value: function removeExistingEdge(from, to) { | ||
| if (!this.hasEdge(from, to)) { | ||
| throw new JsGraph.EdgeNotExistsError(from, to); | ||
| } | ||
| }, | ||
| removeEdge: { | ||
| value: function removeEdge(from, to) { | ||
| if (this.hasEdge(from, to)) { | ||
| this.removeExistingEdge(from, to); | ||
| } | ||
| var valueOfRemovedEdge = this._edges[from][to]; | ||
| delete this._edges[from][to]; | ||
| delete this._reverseEdges[to][from]; | ||
| this._edgeCount -= 1; | ||
| this._removeEdgeCallbacks.fire(from, to, valueOfRemovedEdge); | ||
| } | ||
| }, { | ||
| key: "removeEdge", | ||
| value: function removeEdge(from, to) { | ||
| if (this.hasEdge(from, to)) { | ||
| this.removeExistingEdge(from, to); | ||
| } | ||
| }, | ||
| edgeCount: { | ||
| } | ||
| }, { | ||
| key: "edgeCount", | ||
| //// querying them //// | ||
| //// querying them //// | ||
| value: function edgeCount() { | ||
| return this._edgeCount; | ||
| value: function edgeCount() { | ||
| return this._edgeCount; | ||
| } | ||
| }, { | ||
| key: "hasEdge", | ||
| value: function hasEdge(from, to) { | ||
| return this.hasVertex(from) && this.hasVertex(to) && from in this._edges && to in this._edges[from]; | ||
| } | ||
| }, { | ||
| key: "edgeValue", | ||
| value: function edgeValue(from, to) { | ||
| return this.hasEdge(from, to) ? this._edges[from][to] : undefined; | ||
| } | ||
| }, { | ||
| key: "successors", | ||
| ////////////////////////// | ||
| ////////// More ////////// | ||
| ////////////////////////// | ||
| value: function successors(from) { | ||
| if (!this.hasVertex(from)) { | ||
| throw new JsGraph.VertexNotExistsError(from); | ||
| } | ||
| }, | ||
| hasEdge: { | ||
| value: function hasEdge(from, to) { | ||
| return this.hasVertex(from) && this.hasVertex(to) && from in this._edges && to in this._edges[from]; | ||
| return Object.keys(this._edges[from]); | ||
| } | ||
| }, { | ||
| key: "predecessors", | ||
| value: function predecessors(to) { | ||
| if (!this.hasVertex(to)) { | ||
| throw new JsGraph.VertexNotExistsError(to); | ||
| } | ||
| }, | ||
| edgeValue: { | ||
| value: function edgeValue(from, to) { | ||
| return this.hasEdge(from, to) ? this._edges[from][to] : undefined; | ||
| return Object.keys(this._reverseEdges[to]); | ||
| } | ||
| }, { | ||
| key: "eachVertex", | ||
| /////////////////////////////// | ||
| ////////// Iteration ////////// | ||
| /////////////////////////////// | ||
| value: function eachVertex(handler) { | ||
| var _this = this; | ||
| Object.keys(this._vertices).every(function (key) { | ||
| var r = handler(key, _this._vertices[key]); | ||
| return r !== false; | ||
| }); | ||
| } | ||
| }, { | ||
| key: "eachVertexFrom", | ||
| value: function eachVertexFrom(from, handler) { | ||
| var _this = this; | ||
| if (!this.hasVertex(from)) { | ||
| throw new JsGraph.VertexNotExistsError(from); | ||
| } | ||
| }, | ||
| successors: { | ||
| Object.keys(this._edges[from]).every(function (to) { | ||
| var r = handler(to, _this.vertexValue(to), _this.edgeValue(from, to)); | ||
| return r !== false; | ||
| }); | ||
| } | ||
| }, { | ||
| key: "eachVertexTo", | ||
| value: function eachVertexTo(to, handler) { | ||
| var _this = this; | ||
| ////////////////////////// | ||
| ////////// More ////////// | ||
| ////////////////////////// | ||
| if (!this.hasVertex(to)) { | ||
| throw new JsGraph.VertexNotExistsError(to); | ||
| } | ||
| Object.keys(this._reverseEdges[to]).every(function (from) { | ||
| var r = handler(from, _this.vertexValue(from), _this.edgeValue(from, to)); | ||
| return r !== false; | ||
| }); | ||
| } | ||
| }, { | ||
| key: "eachEdge", | ||
| value: function eachEdge(handler) { | ||
| var _this = this; | ||
| value: function successors(from) { | ||
| if (!this.hasVertex(from)) { | ||
| throw new JsGraph.VertexNotExistsError(from); | ||
| Object.keys(this._edges).every(function (from) { | ||
| return Object.keys(_this._edges[from]).every(function (to) { | ||
| var r = handler(from, to, _this._edges[from][to]); | ||
| return r !== false; | ||
| }); | ||
| }); | ||
| } | ||
| }, { | ||
| key: "topologically", | ||
| value: function topologically(handler) { | ||
| var _this = this; | ||
| var visited = []; | ||
| var handled = {}; | ||
| var visit = function (a) { | ||
| visited.push(a); | ||
| var i = visited.indexOf(a); | ||
| if (i !== visited.length - 1) { | ||
| var cycle = visited.slice(i + 1).reverse(); | ||
| throw new JsGraph.CycleError(cycle); | ||
| } | ||
| return Object.keys(this._edges[from]); | ||
| } | ||
| }, | ||
| predecessors: { | ||
| value: function predecessors(to) { | ||
| if (!this.hasVertex(to)) { | ||
| throw new JsGraph.VertexNotExistsError(to); | ||
| if (!handled[a]) { | ||
| _this.eachVertexTo(a, visit); | ||
| handled[a] = { returned: handler(a, _this.vertexValue(a)) }; | ||
| } | ||
| return Object.keys(this._reverseEdges[to]); | ||
| } | ||
| }, | ||
| eachVertex: { | ||
| visited.pop(); | ||
| }; | ||
| /////////////////////////////// | ||
| ////////// Iteration ////////// | ||
| /////////////////////////////// | ||
| this.eachVertex(function (a) { | ||
| if (!handled[a]) { | ||
| visit(a); | ||
| } | ||
| }); | ||
| } | ||
| }, { | ||
| key: Symbol.iterator, | ||
| value: function eachVertex(handler) { | ||
| var _this = this; | ||
| /////////////////////////////////////////////// | ||
| //////////// ES6 Iterable interfaces ////////// | ||
| /////////////////////////////////////////////// | ||
| Object.keys(this._vertices).every(function (key) { | ||
| var r = handler(key, _this._vertices[key]); | ||
| return r !== false; | ||
| }); | ||
| } | ||
| }, | ||
| eachVertexFrom: { | ||
| value: function eachVertexFrom(from, handler) { | ||
| var _this = this; | ||
| value: function () { | ||
| return this.vertices(); | ||
| } | ||
| }, { | ||
| key: "vertices", | ||
| value: regeneratorRuntime.mark(function vertices() { | ||
| var _this = this; | ||
| if (!this.hasVertex(from)) { | ||
| throw new JsGraph.VertexNotExistsError(from); | ||
| var _iteratorNormalCompletion, _didIteratorError, _iteratorError, _iterator, _step, key; | ||
| return regeneratorRuntime.wrap(function vertices$(context$2$0) { | ||
| while (1) switch (context$2$0.prev = context$2$0.next) { | ||
| case 0: | ||
| _iteratorNormalCompletion = true; | ||
| _didIteratorError = false; | ||
| _iteratorError = undefined; | ||
| context$2$0.prev = 3; | ||
| _iterator = Object.keys(_this._vertices)[Symbol.iterator](); | ||
| case 5: | ||
| if (_iteratorNormalCompletion = (_step = _iterator.next()).done) { | ||
| context$2$0.next = 13; | ||
| break; | ||
| } | ||
| key = _step.value; | ||
| if (!_this.hasVertex(key)) { | ||
| context$2$0.next = 10; | ||
| break; | ||
| } | ||
| context$2$0.next = 10; | ||
| return [key, _this._vertices[key]]; | ||
| case 10: | ||
| _iteratorNormalCompletion = true; | ||
| context$2$0.next = 5; | ||
| break; | ||
| case 13: | ||
| context$2$0.next = 19; | ||
| break; | ||
| case 15: | ||
| context$2$0.prev = 15; | ||
| context$2$0.t0 = context$2$0["catch"](3); | ||
| _didIteratorError = true; | ||
| _iteratorError = context$2$0.t0; | ||
| case 19: | ||
| context$2$0.prev = 19; | ||
| context$2$0.prev = 20; | ||
| if (!_iteratorNormalCompletion && _iterator["return"]) { | ||
| _iterator["return"](); | ||
| } | ||
| case 22: | ||
| context$2$0.prev = 22; | ||
| if (!_didIteratorError) { | ||
| context$2$0.next = 25; | ||
| break; | ||
| } | ||
| throw _iteratorError; | ||
| case 25: | ||
| return context$2$0.finish(22); | ||
| case 26: | ||
| return context$2$0.finish(19); | ||
| case 27: | ||
| case "end": | ||
| return context$2$0.stop(); | ||
| } | ||
| Object.keys(this._edges[from]).every(function (to) { | ||
| var r = handler(to, _this.vertexValue(to), _this.edgeValue(from, to)); | ||
| return r !== false; | ||
| }); | ||
| } | ||
| }, | ||
| eachVertexTo: { | ||
| value: function eachVertexTo(to, handler) { | ||
| var _this = this; | ||
| }, vertices, this, [[3, 15, 19, 27], [20,, 22, 26]]); | ||
| }) | ||
| }, { | ||
| key: "edges", | ||
| value: regeneratorRuntime.mark(function edges() { | ||
| var _this = this; | ||
| if (!this.hasVertex(to)) { | ||
| throw new JsGraph.VertexNotExistsError(to); | ||
| var _iteratorNormalCompletion, _didIteratorError, _iteratorError, _iterator, _step, from, _iteratorNormalCompletion2, _didIteratorError2, _iteratorError2, _iterator2, _step2, to; | ||
| return regeneratorRuntime.wrap(function edges$(context$2$0) { | ||
| while (1) switch (context$2$0.prev = context$2$0.next) { | ||
| case 0: | ||
| _iteratorNormalCompletion = true; | ||
| _didIteratorError = false; | ||
| _iteratorError = undefined; | ||
| context$2$0.prev = 3; | ||
| _iterator = Object.keys(_this._edges)[Symbol.iterator](); | ||
| case 5: | ||
| if (_iteratorNormalCompletion = (_step = _iterator.next()).done) { | ||
| context$2$0.next = 37; | ||
| break; | ||
| } | ||
| from = _step.value; | ||
| _iteratorNormalCompletion2 = true; | ||
| _didIteratorError2 = false; | ||
| _iteratorError2 = undefined; | ||
| context$2$0.prev = 10; | ||
| _iterator2 = Object.keys(_this._edges[from])[Symbol.iterator](); | ||
| case 12: | ||
| if (_iteratorNormalCompletion2 = (_step2 = _iterator2.next()).done) { | ||
| context$2$0.next = 20; | ||
| break; | ||
| } | ||
| to = _step2.value; | ||
| if (!_this.hasEdge(from, to)) { | ||
| context$2$0.next = 17; | ||
| break; | ||
| } | ||
| context$2$0.next = 17; | ||
| return [from, to, _this._edges[from][to]]; | ||
| case 17: | ||
| _iteratorNormalCompletion2 = true; | ||
| context$2$0.next = 12; | ||
| break; | ||
| case 20: | ||
| context$2$0.next = 26; | ||
| break; | ||
| case 22: | ||
| context$2$0.prev = 22; | ||
| context$2$0.t1 = context$2$0["catch"](10); | ||
| _didIteratorError2 = true; | ||
| _iteratorError2 = context$2$0.t1; | ||
| case 26: | ||
| context$2$0.prev = 26; | ||
| context$2$0.prev = 27; | ||
| if (!_iteratorNormalCompletion2 && _iterator2["return"]) { | ||
| _iterator2["return"](); | ||
| } | ||
| case 29: | ||
| context$2$0.prev = 29; | ||
| if (!_didIteratorError2) { | ||
| context$2$0.next = 32; | ||
| break; | ||
| } | ||
| throw _iteratorError2; | ||
| case 32: | ||
| return context$2$0.finish(29); | ||
| case 33: | ||
| return context$2$0.finish(26); | ||
| case 34: | ||
| _iteratorNormalCompletion = true; | ||
| context$2$0.next = 5; | ||
| break; | ||
| case 37: | ||
| context$2$0.next = 43; | ||
| break; | ||
| case 39: | ||
| context$2$0.prev = 39; | ||
| context$2$0.t2 = context$2$0["catch"](3); | ||
| _didIteratorError = true; | ||
| _iteratorError = context$2$0.t2; | ||
| case 43: | ||
| context$2$0.prev = 43; | ||
| context$2$0.prev = 44; | ||
| if (!_iteratorNormalCompletion && _iterator["return"]) { | ||
| _iterator["return"](); | ||
| } | ||
| case 46: | ||
| context$2$0.prev = 46; | ||
| if (!_didIteratorError) { | ||
| context$2$0.next = 49; | ||
| break; | ||
| } | ||
| throw _iteratorError; | ||
| case 49: | ||
| return context$2$0.finish(46); | ||
| case 50: | ||
| return context$2$0.finish(43); | ||
| case 51: | ||
| case "end": | ||
| return context$2$0.stop(); | ||
| } | ||
| Object.keys(this._reverseEdges[to]).every(function (from) { | ||
| var r = handler(from, _this.vertexValue(from), _this.edgeValue(from, to)); | ||
| return r !== false; | ||
| }); | ||
| }, edges, this, [[3, 39, 43, 51], [10, 22, 26, 34], [27,, 29, 33], [44,, 46, 50]]); | ||
| }) | ||
| }, { | ||
| key: "verticesFrom", | ||
| value: function verticesFrom(from) { | ||
| if (!this.hasVertex(from)) { | ||
| throw new JsGraph.VertexNotExistsError(from); | ||
| } | ||
| }, | ||
| eachEdge: { | ||
| value: function eachEdge(handler) { | ||
| var _this = this; | ||
| return this._verticesFrom(from); | ||
| } | ||
| }, { | ||
| key: "_verticesFrom", | ||
| value: regeneratorRuntime.mark(function _verticesFrom(from) { | ||
| var _this = this; | ||
| Object.keys(this._edges).every(function (from) { | ||
| return Object.keys(_this._edges[from]).every(function (to) { | ||
| var r = handler(from, to, _this._edges[from][to]); | ||
| return r !== false; | ||
| }); | ||
| }); | ||
| } | ||
| }, | ||
| topologically: { | ||
| value: function topologically(handler) { | ||
| var _this = this; | ||
| var _iteratorNormalCompletion, _didIteratorError, _iteratorError, _iterator, _step, to; | ||
| var visited = []; | ||
| var handled = {}; | ||
| return regeneratorRuntime.wrap(function _verticesFrom$(context$2$0) { | ||
| while (1) switch (context$2$0.prev = context$2$0.next) { | ||
| case 0: | ||
| _iteratorNormalCompletion = true; | ||
| _didIteratorError = false; | ||
| _iteratorError = undefined; | ||
| context$2$0.prev = 3; | ||
| _iterator = Object.keys(_this._edges[from])[Symbol.iterator](); | ||
| var visit = function (a) { | ||
| visited.push(a); | ||
| var i = visited.indexOf(a); | ||
| if (i !== visited.length - 1) { | ||
| var cycle = visited.slice(i + 1).reverse(); | ||
| throw new JsGraph.CycleError(cycle); | ||
| } | ||
| if (!handled[a]) { | ||
| _this.eachVertexTo(a, visit); | ||
| handled[a] = { returned: handler(a, _this.vertexValue(a)) }; | ||
| } | ||
| visited.pop(); | ||
| }; | ||
| case 5: | ||
| if (_iteratorNormalCompletion = (_step = _iterator.next()).done) { | ||
| context$2$0.next = 13; | ||
| break; | ||
| } | ||
| this.eachVertex(function (a) { | ||
| if (!handled[a]) { | ||
| visit(a); | ||
| } | ||
| }); | ||
| } | ||
| }, | ||
| clearEdges: { | ||
| to = _step.value; | ||
| /////////////////////////////////////////////// | ||
| //////////// ES6 Iterable interfaces ////////// | ||
| /////////////////////////////////////////////// | ||
| // | ||
| //get vertices() { | ||
| // return { | ||
| // _graph: this, | ||
| // get length() { return this._graph._vertexCount }, | ||
| // [Symbol.iterator]: function*() { | ||
| // var keys = Object.keys(this._graph._vertices); | ||
| // for (let i = 0; i < keys.length; ++i) { | ||
| // yield [keys[i], this._graph._vertices[keys[i]]]; | ||
| // } | ||
| // } | ||
| // }; | ||
| //} | ||
| // | ||
| //get edges() { | ||
| // return { | ||
| // _graph: this, | ||
| // get length() { return this._graph._edgeCount }, | ||
| // [Symbol.iterator]: function*() { | ||
| // var fromKeys = Object.keys(this._graph._edges); | ||
| // for (let i = 0; i < fromKeys.length; ++i) { | ||
| // var toKeys = Object.keys(this._graph._edges[fromKeys[i]]); | ||
| // for (let j = 0; j < toKeys.length; ++j) { | ||
| // yield [fromKeys[i], toKeys[j], this._graph._edges[fromKeys[i]][toKeys[j]]]; | ||
| // } | ||
| // } | ||
| // } | ||
| // }; | ||
| //} | ||
| if (!_this.hasEdge(from, to)) { | ||
| context$2$0.next = 10; | ||
| break; | ||
| } | ||
| ////////////////////////////// | ||
| ////////// Clearing ////////// | ||
| ////////////////////////////// | ||
| context$2$0.next = 10; | ||
| return [to, _this._vertices[to], _this._edges[from][to]]; | ||
| value: function clearEdges() { | ||
| var _this = this; | ||
| case 10: | ||
| _iteratorNormalCompletion = true; | ||
| context$2$0.next = 5; | ||
| break; | ||
| this.eachEdge(function (from, to) { | ||
| _this.removeEdge(from, to); | ||
| }); | ||
| } | ||
| }, | ||
| clear: { | ||
| value: function clear() { | ||
| var _this = this; | ||
| case 13: | ||
| context$2$0.next = 19; | ||
| break; | ||
| this.eachVertex(function (v) { | ||
| _this.destroyVertex(v); | ||
| }); | ||
| case 15: | ||
| context$2$0.prev = 15; | ||
| context$2$0.t3 = context$2$0["catch"](3); | ||
| _didIteratorError = true; | ||
| _iteratorError = context$2$0.t3; | ||
| case 19: | ||
| context$2$0.prev = 19; | ||
| context$2$0.prev = 20; | ||
| if (!_iteratorNormalCompletion && _iterator["return"]) { | ||
| _iterator["return"](); | ||
| } | ||
| case 22: | ||
| context$2$0.prev = 22; | ||
| if (!_didIteratorError) { | ||
| context$2$0.next = 25; | ||
| break; | ||
| } | ||
| throw _iteratorError; | ||
| case 25: | ||
| return context$2$0.finish(22); | ||
| case 26: | ||
| return context$2$0.finish(19); | ||
| case 27: | ||
| case "end": | ||
| return context$2$0.stop(); | ||
| } | ||
| }, _verticesFrom, this, [[3, 15, 19, 27], [20,, 22, 26]]); | ||
| }) | ||
| }, { | ||
| key: "verticesTo", | ||
| value: function verticesTo(to) { | ||
| if (!this.hasVertex(to)) { | ||
| throw new JsGraph.VertexNotExistsError(to); | ||
| } | ||
| }, | ||
| hasCycle: { | ||
| return this._verticesTo(to); | ||
| } | ||
| }, { | ||
| key: "_verticesTo", | ||
| value: regeneratorRuntime.mark(function _verticesTo(to) { | ||
| var _this = this; | ||
| ////////////////////////////////////// | ||
| ////////// Advanced Queries ////////// | ||
| ////////////////////////////////////// | ||
| var _iteratorNormalCompletion, _didIteratorError, _iteratorError, _iterator, _step, from; | ||
| value: function hasCycle() { | ||
| var _this = this; | ||
| return regeneratorRuntime.wrap(function _verticesTo$(context$2$0) { | ||
| while (1) switch (context$2$0.prev = context$2$0.next) { | ||
| case 0: | ||
| _iteratorNormalCompletion = true; | ||
| _didIteratorError = false; | ||
| _iteratorError = undefined; | ||
| context$2$0.prev = 3; | ||
| _iterator = Object.keys(_this._reverseEdges[to])[Symbol.iterator](); | ||
| var visited = {}; | ||
| var handled = {}; | ||
| case 5: | ||
| if (_iteratorNormalCompletion = (_step = _iterator.next()).done) { | ||
| context$2$0.next = 13; | ||
| break; | ||
| } | ||
| var cycleFound = false; | ||
| from = _step.value; | ||
| var visit = function (a) { | ||
| /* if a cycle is found, record it and return */ | ||
| if (visited[a]) { | ||
| cycleFound = true; | ||
| return; | ||
| } | ||
| if (!_this.hasEdge(from, to)) { | ||
| context$2$0.next = 10; | ||
| break; | ||
| } | ||
| /* if this vertex was already handled, no cycle can be found here */ | ||
| if (handled[a]) { | ||
| return; | ||
| context$2$0.next = 10; | ||
| return [from, _this._vertices[from], _this._edges[from][to]]; | ||
| case 10: | ||
| _iteratorNormalCompletion = true; | ||
| context$2$0.next = 5; | ||
| break; | ||
| case 13: | ||
| context$2$0.next = 19; | ||
| break; | ||
| case 15: | ||
| context$2$0.prev = 15; | ||
| context$2$0.t4 = context$2$0["catch"](3); | ||
| _didIteratorError = true; | ||
| _iteratorError = context$2$0.t4; | ||
| case 19: | ||
| context$2$0.prev = 19; | ||
| context$2$0.prev = 20; | ||
| if (!_iteratorNormalCompletion && _iterator["return"]) { | ||
| _iterator["return"](); | ||
| } | ||
| case 22: | ||
| context$2$0.prev = 22; | ||
| if (!_didIteratorError) { | ||
| context$2$0.next = 25; | ||
| break; | ||
| } | ||
| throw _iteratorError; | ||
| case 25: | ||
| return context$2$0.finish(22); | ||
| case 26: | ||
| return context$2$0.finish(19); | ||
| case 27: | ||
| case "end": | ||
| return context$2$0.stop(); | ||
| } | ||
| }, _verticesTo, this, [[3, 15, 19, 27], [20,, 22, 26]]); | ||
| }) | ||
| }, { | ||
| key: "vertices_topologically", | ||
| value: regeneratorRuntime.mark(function vertices_topologically() { | ||
| var _this2 = this; | ||
| var visit = regeneratorRuntime.mark(function visit(a) { | ||
| var i, cycle, _iteratorNormalCompletion, _didIteratorError, _iteratorError, _iterator, _step, _step$value, b; | ||
| return regeneratorRuntime.wrap(function visit$(context$3$0) { | ||
| while (1) switch (context$3$0.prev = context$3$0.next) { | ||
| case 0: | ||
| visited.push(a); | ||
| i = visited.indexOf(a); | ||
| if (!(i !== visited.length - 1)) { | ||
| context$3$0.next = 5; | ||
| break; | ||
| } | ||
| cycle = visited.slice(i + 1).reverse(); | ||
| throw new JsGraph.CycleError(cycle); | ||
| case 5: | ||
| if (handled[a]) { | ||
| context$3$0.next = 36; | ||
| break; | ||
| } | ||
| _iteratorNormalCompletion = true; | ||
| _didIteratorError = false; | ||
| _iteratorError = undefined; | ||
| context$3$0.prev = 9; | ||
| _iterator = _this.verticesTo(a)[Symbol.iterator](); | ||
| case 11: | ||
| if (_iteratorNormalCompletion = (_step = _iterator.next()).done) { | ||
| context$3$0.next = 18; | ||
| break; | ||
| } | ||
| _step$value = _slicedToArray(_step.value, 1); | ||
| b = _step$value[0]; | ||
| return context$3$0.delegateYield(visit(b), "t5", 15); | ||
| case 15: | ||
| _iteratorNormalCompletion = true; | ||
| context$3$0.next = 11; | ||
| break; | ||
| case 18: | ||
| context$3$0.next = 24; | ||
| break; | ||
| case 20: | ||
| context$3$0.prev = 20; | ||
| context$3$0.t6 = context$3$0["catch"](9); | ||
| _didIteratorError = true; | ||
| _iteratorError = context$3$0.t6; | ||
| case 24: | ||
| context$3$0.prev = 24; | ||
| context$3$0.prev = 25; | ||
| if (!_iteratorNormalCompletion && _iterator["return"]) { | ||
| _iterator["return"](); | ||
| } | ||
| case 27: | ||
| context$3$0.prev = 27; | ||
| if (!_didIteratorError) { | ||
| context$3$0.next = 30; | ||
| break; | ||
| } | ||
| throw _iteratorError; | ||
| case 30: | ||
| return context$3$0.finish(27); | ||
| case 31: | ||
| return context$3$0.finish(24); | ||
| case 32: | ||
| if (!_this.hasVertex(a)) { | ||
| context$3$0.next = 35; | ||
| break; | ||
| } | ||
| context$3$0.next = 35; | ||
| return [a, _this._vertices[a]]; | ||
| case 35: | ||
| handled[a] = true; | ||
| case 36: | ||
| visited.pop(); | ||
| case 37: | ||
| case "end": | ||
| return context$3$0.stop(); | ||
| } | ||
| handled[a] = true; | ||
| }, visit, this, [[9, 20, 24, 32], [25,, 27, 31]]); | ||
| }); | ||
| /* recursively visit successors to check for cycles */ | ||
| visited[a] = true; | ||
| _this.eachVertexFrom(a, function (b) { | ||
| visit(b); | ||
| if (cycleFound) { | ||
| return false; | ||
| var visited, handled, _this, _iteratorNormalCompletion, _didIteratorError, _iteratorError, _iterator, _step, _step$value, a; | ||
| return regeneratorRuntime.wrap(function vertices_topologically$(context$2$0) { | ||
| while (1) switch (context$2$0.prev = context$2$0.next) { | ||
| case 0: | ||
| visited = []; | ||
| handled = {}; | ||
| _this = _this2; | ||
| _iteratorNormalCompletion = true; | ||
| _didIteratorError = false; | ||
| _iteratorError = undefined; | ||
| context$2$0.prev = 6; | ||
| _iterator = _this2.vertices()[Symbol.iterator](); | ||
| case 8: | ||
| if (_iteratorNormalCompletion = (_step = _iterator.next()).done) { | ||
| context$2$0.next = 16; | ||
| break; | ||
| } | ||
| }); | ||
| visited[a] = false; | ||
| }; | ||
| this.eachVertex(function (a) { | ||
| visit(a); | ||
| _step$value = _slicedToArray(_step.value, 1); | ||
| a = _step$value[0]; | ||
| if (handled[a]) { | ||
| context$2$0.next = 13; | ||
| break; | ||
| } | ||
| return context$2$0.delegateYield(visit(a), "t7", 13); | ||
| case 13: | ||
| _iteratorNormalCompletion = true; | ||
| context$2$0.next = 8; | ||
| break; | ||
| case 16: | ||
| context$2$0.next = 22; | ||
| break; | ||
| case 18: | ||
| context$2$0.prev = 18; | ||
| context$2$0.t8 = context$2$0["catch"](6); | ||
| _didIteratorError = true; | ||
| _iteratorError = context$2$0.t8; | ||
| case 22: | ||
| context$2$0.prev = 22; | ||
| context$2$0.prev = 23; | ||
| if (!_iteratorNormalCompletion && _iterator["return"]) { | ||
| _iterator["return"](); | ||
| } | ||
| case 25: | ||
| context$2$0.prev = 25; | ||
| if (!_didIteratorError) { | ||
| context$2$0.next = 28; | ||
| break; | ||
| } | ||
| throw _iteratorError; | ||
| case 28: | ||
| return context$2$0.finish(25); | ||
| case 29: | ||
| return context$2$0.finish(22); | ||
| case 30: | ||
| case "end": | ||
| return context$2$0.stop(); | ||
| } | ||
| }, vertices_topologically, this, [[6, 18, 22, 30], [23,, 25, 29]]); | ||
| }) | ||
| }, { | ||
| key: "clearEdges", | ||
| ////////////////////////////// | ||
| ////////// Clearing ////////// | ||
| ////////////////////////////// | ||
| value: function clearEdges() { | ||
| var _this = this; | ||
| this.eachEdge(function (from, to) { | ||
| _this.removeEdge(from, to); | ||
| }); | ||
| } | ||
| }, { | ||
| key: "clear", | ||
| value: function clear() { | ||
| var _this = this; | ||
| this.eachVertex(function (v) { | ||
| _this.destroyVertex(v); | ||
| }); | ||
| } | ||
| }, { | ||
| key: "hasCycle", | ||
| ////////////////////////////////////// | ||
| ////////// Advanced Queries ////////// | ||
| ////////////////////////////////////// | ||
| value: function hasCycle() { | ||
| var _this = this; | ||
| var visited = {}; | ||
| var handled = {}; | ||
| var cycleFound = false; | ||
| var visit = function (a) { | ||
| /* if a cycle is found, record it and return */ | ||
| if (visited[a]) { | ||
| cycleFound = true; | ||
| return; | ||
| } | ||
| /* if this vertex was already handled, no cycle can be found here */ | ||
| if (handled[a]) { | ||
| return; | ||
| } | ||
| handled[a] = true; | ||
| /* recursively visit successors to check for cycles */ | ||
| visited[a] = true; | ||
| _this.eachVertexFrom(a, function (b) { | ||
| visit(b); | ||
| if (cycleFound) { | ||
@@ -593,70 +1121,78 @@ return false; | ||
| }); | ||
| visited[a] = false; | ||
| }; | ||
| return cycleFound; | ||
| } | ||
| }, | ||
| hasPath: { | ||
| value: function hasPath(from, to) { | ||
| var _this = this; | ||
| if (!this.hasVertex(from) || !this.hasVertex(to)) { | ||
| this.eachVertex(function (a) { | ||
| visit(a); | ||
| if (cycleFound) { | ||
| return false; | ||
| } | ||
| }); | ||
| var visited = {}; | ||
| return cycleFound; | ||
| } | ||
| }, { | ||
| key: "hasPath", | ||
| value: function hasPath(from, to) { | ||
| var _this = this; | ||
| /* Recursive auxiliary function: Is there a path from 'current' to 'to'? */ | ||
| var hasPathAux = function (current) { | ||
| if (_this.hasEdge(current, to)) { | ||
| return true; | ||
| if (!this.hasVertex(from) || !this.hasVertex(to)) { | ||
| return false; | ||
| } | ||
| var visited = {}; | ||
| /* Recursive auxiliary function: Is there a path from 'current' to 'to'? */ | ||
| var hasPathAux = function (current) { | ||
| if (_this.hasEdge(current, to)) { | ||
| return true; | ||
| } | ||
| visited[current] = true; | ||
| var found = false; | ||
| _this.eachVertexFrom(current, function (next) { | ||
| if (!found && !visited[next] && hasPathAux(next)) { | ||
| found = true; | ||
| } | ||
| visited[current] = true; | ||
| var found = false; | ||
| _this.eachVertexFrom(current, function (next) { | ||
| if (!found && !visited[next] && hasPathAux(next)) { | ||
| found = true; | ||
| } | ||
| }); | ||
| delete visited[current]; | ||
| return found; | ||
| }; | ||
| }); | ||
| delete visited[current]; | ||
| return found; | ||
| }; | ||
| return hasPathAux(from); | ||
| } | ||
| }, | ||
| clone: { | ||
| return hasPathAux(from); | ||
| } | ||
| }, { | ||
| key: "clone", | ||
| ///////////////////////////// | ||
| ////////// Cloning ////////// | ||
| ///////////////////////////// | ||
| ///////////////////////////// | ||
| ////////// Cloning ////////// | ||
| ///////////////////////////// | ||
| value: function clone() { | ||
| var result = new JsGraph(); | ||
| this.eachVertex(function (key, val) { | ||
| result.addVertex(key, val); | ||
| value: function clone() { | ||
| var result = new JsGraph(); | ||
| this.eachVertex(function (key, val) { | ||
| result.addVertex(key, val); | ||
| }); | ||
| this.eachEdge(function (from, to, val) { | ||
| result.addEdge(from, to, val); | ||
| }); | ||
| return result; | ||
| } | ||
| }, { | ||
| key: "transitiveReduction", | ||
| value: function transitiveReduction() { | ||
| var result = this.clone(); | ||
| result.eachVertex(function (x) { | ||
| result.eachVertex(function (y) { | ||
| if (result.hasEdge(x, y)) { | ||
| result.eachVertex(function (z) { | ||
| if (result.hasPath(y, z)) { | ||
| result.removeEdge(x, z); | ||
| } | ||
| }); | ||
| } | ||
| }); | ||
| this.eachEdge(function (from, to, val) { | ||
| result.addEdge(from, to, val); | ||
| }); | ||
| return result; | ||
| } | ||
| }, | ||
| transitiveReduction: { | ||
| value: function transitiveReduction() { | ||
| var result = this.clone(); | ||
| result.eachVertex(function (x) { | ||
| result.eachVertex(function (y) { | ||
| if (result.hasEdge(x, y)) { | ||
| result.eachVertex(function (z) { | ||
| if (result.hasPath(y, z)) { | ||
| result.removeEdge(x, z); | ||
| } | ||
| }); | ||
| } | ||
| }); | ||
| }); | ||
| return result; | ||
| } | ||
| }); | ||
| return result; | ||
| } | ||
| }); | ||
| }]); | ||
@@ -668,5 +1204,5 @@ return JsGraph; | ||
| // //////////////////////////////////////////////////////////////////////////////////////////////////////////////////// | ||
| // // Errors ////////////////////////////////////////////////////////////////////////////////////////////////////////// | ||
| // //////////////////////////////////////////////////////////////////////////////////////////////////////////////////// | ||
| // //////////////////////////////////////////////////////////////////////////////////////////////// | ||
| // // Errors ////////////////////////////////////////////////////////////////////////////////////// | ||
| // //////////////////////////////////////////////////////////////////////////////////////////////// | ||
@@ -673,0 +1209,0 @@ JsGraph.VertexExistsError = (function (_Error) { |
@@ -1,2 +0,2 @@ | ||
| (function e(t,r){if(typeof exports==="object"&&typeof module==="object")module.exports=r();else if(typeof define==="function"&&define.amd)define(r);else if(typeof exports==="object")exports["JsGraph"]=r();else t["JsGraph"]=r()})(this,function(){return function(e){var t={};function r(s){if(t[s])return t[s].exports;var i=t[s]={exports:{},id:s,loaded:false};e[s].call(i.exports,i,i.exports,r);i.loaded=true;return i.exports}r.m=e;r.c=t;r.p="";return r(0)}([function(e,t,r){"use strict";var s=function(e,t,r){return Object.defineProperty(e,t,{value:r,enumerable:true,configurable:true,writable:true})};var i=function(e,t){if(typeof t!=="function"&&t!==null){throw new TypeError("Super expression must either be null or a function, not "+typeof t)}e.prototype=Object.create(t&&t.prototype,{constructor:{value:e,enumerable:false,writable:true,configurable:true}});if(t)e.__proto__=t};var n=function(){function e(e,t){for(var r in t){var s=t[r];s.configurable=true;if(s.value)s.writable=true}Object.defineProperties(e,t)}return function(t,r,s){if(r)e(t.prototype,r);if(s)e(t,s);return t}}();var a=function(e,t){if(!(e instanceof t)){throw new TypeError("Cannot call a class as a function")}};var o=function(){function e(){a(this,e);this._callbacks=[]}n(e,{add:{value:function t(e){var t=this;if(this._callbacks.indexOf(e)===-1){this._callbacks.push(e)}return function(){var r=t._callbacks.indexOf(e);if(r!==-1){t._callbacks.splice(r,1)}}}},fire:{value:function r(){for(var e=arguments.length,t=Array(e),r=0;r<e;r++){t[r]=arguments[r]}this._callbacks.forEach(function(e){e.apply(undefined,t)})}}});return e}();var h=function(){function e(){a(this,e);this._vertices={};this._edges={};this._reverseEdges={};this._vertexCount=0;this._edgeCount=0;this._addVertexCallbacks=new o;this._removeVertexCallbacks=new o;this._addEdgeCallbacks=new o;this._removeEdgeCallbacks=new o}n(e,{onAddVertex:{value:function t(e){return this._addVertexCallbacks.add(e)}},onRemoveVertex:{value:function r(e){return this._removeVertexCallbacks.add(e)}},addNewVertex:{value:function s(t,r){if(this.hasVertex(t)){throw new e.VertexExistsError(t,this._vertices[t])}this._vertices[t]=r;this._edges[t]={};this._reverseEdges[t]={};this._vertexCount+=1;this._addVertexCallbacks.fire(t,r)}},setVertex:{value:function i(t,r){if(!this.hasVertex(t)){throw new e.VertexNotExistsError(t)}this._vertices[t]=r}},ensureVertex:{value:function h(e,t){if(!this.hasVertex(e)){this.addNewVertex(e,t)}}},addVertex:{value:function u(e,t){if(this.hasVertex(e)){this.setVertex(e,t)}else{this.addNewVertex(e,t)}}},removeExistingVertex:{value:function c(t){if(!this.hasVertex(t)){throw new e.VertexNotExistsError(t)}if(Object.keys(this._edges[t]).length){throw new e.HasConnectedEdgesError(t)}if(Object.keys(this._reverseEdges[t]).length){throw new e.HasConnectedEdgesError(t)}var r=this._vertices[t];delete this._vertices[t];this._vertexCount-=1;this._removeVertexCallbacks.fire(t,r)}},destroyExistingVertex:{value:function f(t){var r=this;if(!this.hasVertex(t)){throw new e.VertexNotExistsError(t)}this.eachVertexFrom(t,function(e){r.removeEdge(t,e)});this.eachVertexTo(t,function(e){r.removeEdge(e,t)});this.removeExistingVertex(t)}},removeVertex:{value:function d(e){if(this.hasVertex(e)){this.removeExistingVertex(e)}}},destroyVertex:{value:function v(e){if(this.hasVertex(e)){this.destroyExistingVertex(e)}}},vertexCount:{value:function l(){return this._vertexCount}},hasVertex:{value:function g(e){return e in this._vertices}},vertexValue:{value:function x(e){return this._vertices[e]}},onAddEdge:{value:function E(e){return this._addEdgeCallbacks.add(e)}},onRemoveEdge:{value:function V(e){return this._removeEdgeCallbacks.add(e)}},addNewEdge:{value:function _(t,r,s){if(this.hasEdge(t,r)){throw new e.EdgeExistsError(t,r,this.edgeValue(t,r))}if(!this.hasVertex(t)){if(this.hasVertex(r)){throw new e.VertexNotExistsError(t)}else{throw new e.VertexNotExistsError(t).v(r)}}else if(!this.hasVertex(r)){throw new e.VertexNotExistsError(r)}this._edges[t][r]=s;this._reverseEdges[r][t]=null;this._edgeCount+=1;this._addEdgeCallbacks.fire(t,r,s)}},createNewEdge:{value:function w(t,r,s){if(this.hasEdge(t,r)){throw new e.EdgeExistsError(t,r,this.edgeValue(t,r))}this.ensureVertex(t);this.ensureVertex(r);this.addNewEdge(t,r,s)}},setEdge:{value:function p(t,r,s){if(!this.hasEdge(t,r)){throw new e.EdgeNotExistsError(t,r)}this._edges[t][r]=s}},spanEdge:{value:function b(t,r,s){if(!this.hasVertex(t)){if(this.hasVertex(r)){throw new e.VertexNotExistsError(t)}else{throw new e.VertexNotExistsError(t).v(r)}}else if(!this.hasVertex(r)){throw new e.VertexNotExistsError(r)}if(!this.hasEdge(t,r)){this.addNewEdge(t,r,s)}}},addEdge:{value:function y(e,t,r){if(this.hasEdge(e,t)){this.setEdge(e,t,r)}else{this.addNewEdge(e,t,r)}}},ensureEdge:{value:function m(e,t,r){if(!this.hasEdge(e,t)){this.createNewEdge(e,t,r)}}},createEdge:{value:function k(e,t,r){if(this.hasEdge(e,t)){this.setEdge(e,t,r)}else{this.createNewEdge(e,t,r)}}},removeExistingEdge:{value:function C(t,r){if(!this.hasEdge(t,r)){throw new e.EdgeNotExistsError(t,r)}var s=this._edges[t][r];delete this._edges[t][r];delete this._reverseEdges[r][t];this._edgeCount-=1;this._removeEdgeCallbacks.fire(t,r,s)}},removeEdge:{value:function N(e,t){if(this.hasEdge(e,t)){this.removeExistingEdge(e,t)}}},edgeCount:{value:function j(){return this._edgeCount}},hasEdge:{value:function O(e,t){return this.hasVertex(e)&&this.hasVertex(t)&&e in this._edges&&t in this._edges[e]}},edgeValue:{value:function T(e,t){return this.hasEdge(e,t)?this._edges[e][t]:undefined}},successors:{value:function M(t){if(!this.hasVertex(t)){throw new e.VertexNotExistsError(t)}return Object.keys(this._edges[t])}},predecessors:{value:function F(t){if(!this.hasVertex(t)){throw new e.VertexNotExistsError(t)}return Object.keys(this._reverseEdges[t])}},eachVertex:{value:function P(e){var t=this;Object.keys(this._vertices).every(function(r){var s=e(r,t._vertices[r]);return s!==false})}},eachVertexFrom:{value:function A(t,r){var s=this;if(!this.hasVertex(t)){throw new e.VertexNotExistsError(t)}Object.keys(this._edges[t]).every(function(e){var i=r(e,s.vertexValue(e),s.edgeValue(t,e));return i!==false})}},eachVertexTo:{value:function H(t,r){var s=this;if(!this.hasVertex(t)){throw new e.VertexNotExistsError(t)}Object.keys(this._reverseEdges[t]).every(function(e){var i=r(e,s.vertexValue(e),s.edgeValue(e,t));return i!==false})}},eachEdge:{value:function R(e){var t=this;Object.keys(this._edges).every(function(r){return Object.keys(t._edges[r]).every(function(s){var i=e(r,s,t._edges[r][s]);return i!==false})})}},topologically:{value:function G(t){var r=this;var s=[];var i={};var n=function(a){s.push(a);var o=s.indexOf(a);if(o!==s.length-1){var h=s.slice(o+1).reverse();throw new e.CycleError(h)}if(!i[a]){r.eachVertexTo(a,n);i[a]={returned:t(a,r.vertexValue(a))}}s.pop()};this.eachVertex(function(e){if(!i[e]){n(e)}})}},clearEdges:{value:function J(){var e=this;this.eachEdge(function(t,r){e.removeEdge(t,r)})}},clear:{value:function S(){var e=this;this.eachVertex(function(t){e.destroyVertex(t)})}},hasCycle:{value:function q(){var e=this;var t={};var r={};var s=false;var i=function(n){if(t[n]){s=true;return}if(r[n]){return}r[n]=true;t[n]=true;e.eachVertexFrom(n,function(e){i(e);if(s){return false}});t[n]=false};this.eachVertex(function(e){i(e);if(s){return false}});return s}},hasPath:{value:function z(e,t){var r=this;if(!this.hasVertex(e)||!this.hasVertex(t)){return false}var s={};var i=function(e){if(r.hasEdge(e,t)){return true}s[e]=true;var n=false;r.eachVertexFrom(e,function(e){if(!n&&!s[e]&&i(e)){n=true}});delete s[e];return n};return i(e)}},clone:{value:function B(){var t=new e;this.eachVertex(function(e,r){t.addVertex(e,r)});this.eachEdge(function(e,r,s){t.addEdge(e,r,s)});return t}},transitiveReduction:{value:function D(){var e=this.clone();e.eachVertex(function(t){e.eachVertex(function(r){if(e.hasEdge(t,r)){e.eachVertex(function(s){if(e.hasPath(r,s)){e.removeEdge(t,s)}})}})});return e}}});return e}();e.exports=h;h.VertexExistsError=function(e){function t(e,r){a(this,t);this.vertices={};this.v(e,r)}i(t,e);n(t,{v:{value:function r(e,t){this.vertices[e]=t;this._refreshMessage();return this}},_refreshMessage:{value:function s(){var e=this.vertices===1?"a vertex":"vertices";this.message="This graph has "+e+" '"+Object.keys(this.vertices).join("', '")+"'"}}});return t}(Error);h.VertexNotExistsError=function(e){function t(e){a(this,t);this.vertices={};this.v(e)}i(t,e);n(t,{v:{value:function r(e){this.vertices[e]=undefined;this._refreshMessage();return this}},_refreshMessage:{value:function s(){var e=this.vertices===1?"a vertex":"vertices";this.message="This graph does not have "+e+" '"+Object.keys(this.vertices).join("', '")+"'"}}});return t}(Error);h.EdgeExistsError=function(e){function t(e,r,s){a(this,t);this.edges={};this.e(e,r,s)}i(t,e);n(t,{e:{value:function r(e,t,i){this.edges[e]=s({},t,i);this._refreshMessage();return this}},_refreshMessage:{value:function o(){var e=this;var t=[];Object.keys(this.edges).forEach(function(r){Object.keys(e.edges[r]).forEach(function(e){t.push("('"+r+"', '"+e+"')")})});var r=t.length===1?"an edge":"edges";this.message="This graph has "+r+" "+t.join(", ")}}});return t}(Error);h.EdgeNotExistsError=function(e){function t(e,r){a(this,t);this.edges={};this.e(e,r)}i(t,e);n(t,{e:{value:function r(e,t){this.edges[e]=s({},t,undefined);this._refreshMessage();return this}},_refreshMessage:{value:function o(){var e=this;var t=[];Object.keys(this.edges).forEach(function(r){Object.keys(e.edges[r]).forEach(function(e){t.push("('"+r+"', '"+e+"')")})});var r=t.length===1?"an edge":"edges";this.message="This graph does not have "+r+" "+t.join(", ")}}});return t}(Error);h.HasConnectedEdgesError=function(e){function t(e){a(this,t);this.message="The '"+e+"' vertex has connected edges";this.key=e}i(t,e);return t}(Error);h.CycleError=function(e){function t(e){a(this,t);this.message="This graph contains a cycle: "+e;this.cycle=e}i(t,e);return t}(Error)}])}); | ||
| (function e(t,r){if(typeof exports==="object"&&typeof module==="object")module.exports=r();else if(typeof define==="function"&&define.amd)define(r);else if(typeof exports==="object")exports["JsGraph"]=r();else t["JsGraph"]=r()})(this,function(){return function(e){var t={};function r(s){if(t[s])return t[s].exports;var n=t[s]={exports:{},id:s,loaded:false};e[s].call(n.exports,n,n.exports,r);n.loaded=true;return n.exports}r.m=e;r.c=t;r.p="";return r(0)}([function(e,t,r){"use strict";var s=function(e,t){if(Array.isArray(e)){return e}else if(Symbol.iterator in Object(e)){var r=[];for(var s=e[Symbol.iterator](),n;!(n=s.next()).done;){r.push(n.value);if(t&&r.length===t)break}return r}else{throw new TypeError("Invalid attempt to destructure non-iterable instance")}};var n=function(e,t,r){return Object.defineProperty(e,t,{value:r,enumerable:true,configurable:true,writable:true})};var i=function(e,t){if(typeof t!=="function"&&t!==null){throw new TypeError("Super expression must either be null or a function, not "+typeof t)}e.prototype=Object.create(t&&t.prototype,{constructor:{value:e,enumerable:false,writable:true,configurable:true}});if(t)e.__proto__=t};var a=function(){function e(e,t){for(var r=0;r<t.length;r++){var s=t[r];s.configurable=true;if(s.value)s.writable=true;Object.defineProperty(e,s.key,s)}}return function(t,r,s){if(r)e(t.prototype,r);if(s)e(t,s);return t}}();var u=function(){function e(e,t){for(var r in t){var s=t[r];s.configurable=true;if(s.value)s.writable=true}Object.defineProperties(e,t)}return function(t,r,s){if(r)e(t.prototype,r);if(s)e(t,s);return t}}();var o=function(e,t){if(!(e instanceof t)){throw new TypeError("Cannot call a class as a function")}};var c=function(){function e(){o(this,e);this._callbacks=[]}u(e,{add:{value:function t(e){var t=this;if(this._callbacks.indexOf(e)===-1){this._callbacks.push(e)}return function(){var r=t._callbacks.indexOf(e);if(r!==-1){t._callbacks.splice(r,1)}}}},fire:{value:function r(){for(var e=arguments.length,t=Array(e),r=0;r<e;r++){t[r]=arguments[r]}this._callbacks.forEach(function(e){e.apply(undefined,t)})}}});return e}();var h=function(){function e(){o(this,e);this._vertices={};this._edges={};this._reverseEdges={};this._vertexCount=0;this._edgeCount=0;this._addVertexCallbacks=new c;this._removeVertexCallbacks=new c;this._addEdgeCallbacks=new c;this._removeEdgeCallbacks=new c}a(e,[{key:"onAddVertex",value:function t(e){return this._addVertexCallbacks.add(e)}},{key:"onRemoveVertex",value:function r(e){return this._removeVertexCallbacks.add(e)}},{key:"addNewVertex",value:function n(t,r){if(this.hasVertex(t)){throw new e.VertexExistsError(t,this._vertices[t])}this._vertices[t]=r;this._edges[t]={};this._reverseEdges[t]={};this._vertexCount+=1;this._addVertexCallbacks.fire(t,r)}},{key:"setVertex",value:function i(t,r){if(!this.hasVertex(t)){throw new e.VertexNotExistsError(t)}this._vertices[t]=r}},{key:"ensureVertex",value:function u(e,t){if(!this.hasVertex(e)){this.addNewVertex(e,t)}}},{key:"addVertex",value:function h(e,t){if(this.hasVertex(e)){this.setVertex(e,t)}else{this.addNewVertex(e,t)}}},{key:"removeExistingVertex",value:function f(t){if(!this.hasVertex(t)){throw new e.VertexNotExistsError(t)}if(Object.keys(this._edges[t]).length){throw new e.HasConnectedEdgesError(t)}if(Object.keys(this._reverseEdges[t]).length){throw new e.HasConnectedEdgesError(t)}var r=this._vertices[t];delete this._vertices[t];this._vertexCount-=1;this._removeVertexCallbacks.fire(t,r)}},{key:"destroyExistingVertex",value:function v(t){var r=this;if(!this.hasVertex(t)){throw new e.VertexNotExistsError(t)}this.eachVertexFrom(t,function(e){r.removeEdge(t,e)});this.eachVertexTo(t,function(e){r.removeEdge(e,t)});this.removeExistingVertex(t)}},{key:"removeVertex",value:function d(e){if(this.hasVertex(e)){this.removeExistingVertex(e)}}},{key:"destroyVertex",value:function l(e){if(this.hasVertex(e)){this.destroyExistingVertex(e)}}},{key:"vertexCount",value:function x(){return this._vertexCount}},{key:"hasVertex",value:function g(e){return e in this._vertices}},{key:"vertexValue",value:function E(e){return this._vertices[e]}},{key:"onAddEdge",value:function k(e){return this._addEdgeCallbacks.add(e)}},{key:"onRemoveEdge",value:function y(e){return this._removeEdgeCallbacks.add(e)}},{key:"addNewEdge",value:function p(t,r,s){if(this.hasEdge(t,r)){throw new e.EdgeExistsError(t,r,this.edgeValue(t,r))}if(!this.hasVertex(t)){if(this.hasVertex(r)){throw new e.VertexNotExistsError(t)}else{throw new e.VertexNotExistsError(t).v(r)}}else if(!this.hasVertex(r)){throw new e.VertexNotExistsError(r)}this._edges[t][r]=s;this._reverseEdges[r][t]=null;this._edgeCount+=1;this._addEdgeCallbacks.fire(t,r,s)}},{key:"createNewEdge",value:function b(t,r,s){if(this.hasEdge(t,r)){throw new e.EdgeExistsError(t,r,this.edgeValue(t,r))}this.ensureVertex(t);this.ensureVertex(r);this.addNewEdge(t,r,s)}},{key:"setEdge",value:function w(t,r,s){if(!this.hasEdge(t,r)){throw new e.EdgeNotExistsError(t,r)}this._edges[t][r]=s}},{key:"spanEdge",value:function V(t,r,s){if(!this.hasVertex(t)){if(this.hasVertex(r)){throw new e.VertexNotExistsError(t)}else{throw new e.VertexNotExistsError(t).v(r)}}else if(!this.hasVertex(r)){throw new e.VertexNotExistsError(r)}if(!this.hasEdge(t,r)){this.addNewEdge(t,r,s)}}},{key:"addEdge",value:function _(e,t,r){if(this.hasEdge(e,t)){this.setEdge(e,t,r)}else{this.addNewEdge(e,t,r)}}},{key:"ensureEdge",value:function m(e,t,r){if(!this.hasEdge(e,t)){this.createNewEdge(e,t,r)}}},{key:"createEdge",value:function j(e,t,r){if(this.hasEdge(e,t)){this.setEdge(e,t,r)}else{this.createNewEdge(e,t,r)}}},{key:"removeExistingEdge",value:function C(t,r){if(!this.hasEdge(t,r)){throw new e.EdgeNotExistsError(t,r)}var s=this._edges[t][r];delete this._edges[t][r];delete this._reverseEdges[r][t];this._edgeCount-=1;this._removeEdgeCallbacks.fire(t,r,s)}},{key:"removeEdge",value:function N(e,t){if(this.hasEdge(e,t)){this.removeExistingEdge(e,t)}}},{key:"edgeCount",value:function O(){return this._edgeCount}},{key:"hasEdge",value:function T(e,t){return this.hasVertex(e)&&this.hasVertex(t)&&e in this._edges&&t in this._edges[e]}},{key:"edgeValue",value:function R(e,t){return this.hasEdge(e,t)?this._edges[e][t]:undefined}},{key:"successors",value:function S(t){if(!this.hasVertex(t)){throw new e.VertexNotExistsError(t)}return Object.keys(this._edges[t])}},{key:"predecessors",value:function M(t){if(!this.hasVertex(t)){throw new e.VertexNotExistsError(t)}return Object.keys(this._reverseEdges[t])}},{key:"eachVertex",value:function F(e){var t=this;Object.keys(this._vertices).every(function(r){var s=e(r,t._vertices[r]);return s!==false})}},{key:"eachVertexFrom",value:function A(t,r){var s=this;if(!this.hasVertex(t)){throw new e.VertexNotExistsError(t)}Object.keys(this._edges[t]).every(function(e){var n=r(e,s.vertexValue(e),s.edgeValue(t,e));return n!==false})}},{key:"eachVertexTo",value:function P(t,r){var s=this;if(!this.hasVertex(t)){throw new e.VertexNotExistsError(t)}Object.keys(this._reverseEdges[t]).every(function(e){var n=r(e,s.vertexValue(e),s.edgeValue(e,t));return n!==false})}},{key:"eachEdge",value:function H(e){var t=this;Object.keys(this._edges).every(function(r){return Object.keys(t._edges[r]).every(function(s){var n=e(r,s,t._edges[r][s]);return n!==false})})}},{key:"topologically",value:function G(t){var r=this;var s=[];var n={};var i=function(a){s.push(a);var u=s.indexOf(a);if(u!==s.length-1){var o=s.slice(u+1).reverse();throw new e.CycleError(o)}if(!n[a]){r.eachVertexTo(a,i);n[a]={returned:t(a,r.vertexValue(a))}}s.pop()};this.eachVertex(function(e){if(!n[e]){i(e)}})}},{key:Symbol.iterator,value:function(){return this.vertices()}},{key:"vertices",value:regeneratorRuntime.mark(function J(){var e=this;var t,r,s,n,i,a;return regeneratorRuntime.wrap(function u(o){while(1)switch(o.prev=o.next){case 0:t=true;r=false;s=undefined;o.prev=3;n=Object.keys(e._vertices)[Symbol.iterator]();case 5:if(t=(i=n.next()).done){o.next=13;break}a=i.value;if(!e.hasVertex(a)){o.next=10;break}o.next=10;return[a,e._vertices[a]];case 10:t=true;o.next=5;break;case 13:o.next=19;break;case 15:o.prev=15;o.t0=o["catch"](3);r=true;s=o.t0;case 19:o.prev=19;o.prev=20;if(!t&&n["return"]){n["return"]()}case 22:o.prev=22;if(!r){o.next=25;break}throw s;case 25:return o.finish(22);case 26:return o.finish(19);case 27:case"end":return o.stop()}},J,this,[[3,15,19,27],[20,,22,26]])})},{key:"edges",value:regeneratorRuntime.mark(function Y(){var e=this;var t,r,s,n,i,a,u,o,c,h,f,v;return regeneratorRuntime.wrap(function d(l){while(1)switch(l.prev=l.next){case 0:t=true;r=false;s=undefined;l.prev=3;n=Object.keys(e._edges)[Symbol.iterator]();case 5:if(t=(i=n.next()).done){l.next=37;break}a=i.value;u=true;o=false;c=undefined;l.prev=10;h=Object.keys(e._edges[a])[Symbol.iterator]();case 12:if(u=(f=h.next()).done){l.next=20;break}v=f.value;if(!e.hasEdge(a,v)){l.next=17;break}l.next=17;return[a,v,e._edges[a][v]];case 17:u=true;l.next=12;break;case 20:l.next=26;break;case 22:l.prev=22;l.t1=l["catch"](10);o=true;c=l.t1;case 26:l.prev=26;l.prev=27;if(!u&&h["return"]){h["return"]()}case 29:l.prev=29;if(!o){l.next=32;break}throw c;case 32:return l.finish(29);case 33:return l.finish(26);case 34:t=true;l.next=5;break;case 37:l.next=43;break;case 39:l.prev=39;l.t2=l["catch"](3);r=true;s=l.t2;case 43:l.prev=43;l.prev=44;if(!t&&n["return"]){n["return"]()}case 46:l.prev=46;if(!r){l.next=49;break}throw s;case 49:return l.finish(46);case 50:return l.finish(43);case 51:case"end":return l.stop()}},Y,this,[[3,39,43,51],[10,22,26,34],[27,,29,33],[44,,46,50]])})},{key:"verticesFrom",value:function I(t){if(!this.hasVertex(t)){throw new e.VertexNotExistsError(t)}return this._verticesFrom(t)}},{key:"_verticesFrom",value:regeneratorRuntime.mark(function q(e){var t=this;var r,s,n,i,a,u;return regeneratorRuntime.wrap(function o(c){while(1)switch(c.prev=c.next){case 0:r=true;s=false;n=undefined;c.prev=3;i=Object.keys(t._edges[e])[Symbol.iterator]();case 5:if(r=(a=i.next()).done){c.next=13;break}u=a.value;if(!t.hasEdge(e,u)){c.next=10;break}c.next=10;return[u,t._vertices[u],t._edges[e][u]];case 10:r=true;c.next=5;break;case 13:c.next=19;break;case 15:c.prev=15;c.t3=c["catch"](3);s=true;n=c.t3;case 19:c.prev=19;c.prev=20;if(!r&&i["return"]){i["return"]()}case 22:c.prev=22;if(!s){c.next=25;break}throw n;case 25:return c.finish(22);case 26:return c.finish(19);case 27:case"end":return c.stop()}},q,this,[[3,15,19,27],[20,,22,26]])})},{key:"verticesTo",value:function z(t){if(!this.hasVertex(t)){throw new e.VertexNotExistsError(t)}return this._verticesTo(t)}},{key:"_verticesTo",value:regeneratorRuntime.mark(function B(e){var t=this;var r,s,n,i,a,u;return regeneratorRuntime.wrap(function o(c){while(1)switch(c.prev=c.next){case 0:r=true;s=false;n=undefined;c.prev=3;i=Object.keys(t._reverseEdges[e])[Symbol.iterator]();case 5:if(r=(a=i.next()).done){c.next=13;break}u=a.value;if(!t.hasEdge(u,e)){c.next=10;break}c.next=10;return[u,t._vertices[u],t._edges[u][e]];case 10:r=true;c.next=5;break;case 13:c.next=19;break;case 15:c.prev=15;c.t4=c["catch"](3);s=true;n=c.t4;case 19:c.prev=19;c.prev=20;if(!r&&i["return"]){i["return"]()}case 22:c.prev=22;if(!s){c.next=25;break}throw n;case 25:return c.finish(22);case 26:return c.finish(19);case 27:case"end":return c.stop()}},B,this,[[3,15,19,27],[20,,22,26]])})},{key:"vertices_topologically",value:regeneratorRuntime.mark(function D(){var t=this;var r=regeneratorRuntime.mark(function l(t){var r,u,o,c,h,f,v,d,x;return regeneratorRuntime.wrap(function g(E){while(1)switch(E.prev=E.next){case 0:n.push(t);r=n.indexOf(t);if(!(r!==n.length-1)){E.next=5;break}u=n.slice(r+1).reverse();throw new e.CycleError(u);case 5:if(i[t]){E.next=36;break}o=true;c=false;h=undefined;E.prev=9;f=a.verticesTo(t)[Symbol.iterator]();case 11:if(o=(v=f.next()).done){E.next=18;break}d=s(v.value,1);x=d[0];return E.delegateYield(l(x),"t5",15);case 15:o=true;E.next=11;break;case 18:E.next=24;break;case 20:E.prev=20;E.t6=E["catch"](9);c=true;h=E.t6;case 24:E.prev=24;E.prev=25;if(!o&&f["return"]){f["return"]()}case 27:E.prev=27;if(!c){E.next=30;break}throw h;case 30:return E.finish(27);case 31:return E.finish(24);case 32:if(!a.hasVertex(t)){E.next=35;break}E.next=35;return[t,a._vertices[t]];case 35:i[t]=true;case 36:n.pop();case 37:case"end":return E.stop()}},l,this,[[9,20,24,32],[25,,27,31]])});var n,i,a,u,o,c,h,f,v,d;return regeneratorRuntime.wrap(function x(e){while(1)switch(e.prev=e.next){case 0:n=[];i={};a=t;u=true;o=false;c=undefined;e.prev=6;h=t.vertices()[Symbol.iterator]();case 8:if(u=(f=h.next()).done){e.next=16;break}v=s(f.value,1);d=v[0];if(i[d]){e.next=13;break}return e.delegateYield(r(d),"t7",13);case 13:u=true;e.next=8;break;case 16:e.next=22;break;case 18:e.prev=18;e.t8=e["catch"](6);o=true;c=e.t8;case 22:e.prev=22;e.prev=23;if(!u&&h["return"]){h["return"]()}case 25:e.prev=25;if(!o){e.next=28;break}throw c;case 28:return e.finish(25);case 29:return e.finish(22);case 30:case"end":return e.stop()}},D,this,[[6,18,22,30],[23,,25,29]])})},{key:"clearEdges",value:function K(){var e=this;this.eachEdge(function(t,r){e.removeEdge(t,r)})}},{key:"clear",value:function L(){var e=this;this.eachVertex(function(t){e.destroyVertex(t)})}},{key:"hasCycle",value:function Q(){var e=this;var t={};var r={};var s=false;var n=function(i){if(t[i]){s=true;return}if(r[i]){return}r[i]=true;t[i]=true;e.eachVertexFrom(i,function(e){n(e);if(s){return false}});t[i]=false};this.eachVertex(function(e){n(e);if(s){return false}});return s}},{key:"hasPath",value:function U(e,t){var r=this;if(!this.hasVertex(e)||!this.hasVertex(t)){return false}var s={};var n=function(e){if(r.hasEdge(e,t)){return true}s[e]=true;var i=false;r.eachVertexFrom(e,function(e){if(!i&&!s[e]&&n(e)){i=true}});delete s[e];return i};return n(e)}},{key:"clone",value:function W(){var t=new e;this.eachVertex(function(e,r){t.addVertex(e,r)});this.eachEdge(function(e,r,s){t.addEdge(e,r,s)});return t}},{key:"transitiveReduction",value:function X(){var e=this.clone();e.eachVertex(function(t){e.eachVertex(function(r){if(e.hasEdge(t,r)){e.eachVertex(function(s){if(e.hasPath(r,s)){e.removeEdge(t,s)}})}})});return e}}]);return e}();e.exports=h;h.VertexExistsError=function(e){function t(e,r){o(this,t);this.vertices={};this.v(e,r)}i(t,e);u(t,{v:{value:function r(e,t){this.vertices[e]=t;this._refreshMessage();return this}},_refreshMessage:{value:function s(){var e=this.vertices===1?"a vertex":"vertices";this.message="This graph has "+e+" '"+Object.keys(this.vertices).join("', '")+"'"}}});return t}(Error);h.VertexNotExistsError=function(e){function t(e){o(this,t);this.vertices={};this.v(e)}i(t,e);u(t,{v:{value:function r(e){this.vertices[e]=undefined;this._refreshMessage();return this}},_refreshMessage:{value:function s(){var e=this.vertices===1?"a vertex":"vertices";this.message="This graph does not have "+e+" '"+Object.keys(this.vertices).join("', '")+"'"}}});return t}(Error);h.EdgeExistsError=function(e){function t(e,r,s){o(this,t);this.edges={};this.e(e,r,s)}i(t,e);u(t,{e:{value:function r(e,t,s){this.edges[e]=n({},t,s);this._refreshMessage();return this}},_refreshMessage:{value:function s(){var e=this;var t=[];Object.keys(this.edges).forEach(function(r){Object.keys(e.edges[r]).forEach(function(e){t.push("('"+r+"', '"+e+"')")})});var r=t.length===1?"an edge":"edges";this.message="This graph has "+r+" "+t.join(", ")}}});return t}(Error);h.EdgeNotExistsError=function(e){function t(e,r){o(this,t);this.edges={};this.e(e,r)}i(t,e);u(t,{e:{value:function r(e,t){this.edges[e]=n({},t,undefined);this._refreshMessage();return this}},_refreshMessage:{value:function s(){var e=this;var t=[];Object.keys(this.edges).forEach(function(r){Object.keys(e.edges[r]).forEach(function(e){t.push("('"+r+"', '"+e+"')")})});var r=t.length===1?"an edge":"edges";this.message="This graph does not have "+r+" "+t.join(", ")}}});return t}(Error);h.HasConnectedEdgesError=function(e){function t(e){o(this,t);this.message="The '"+e+"' vertex has connected edges";this.key=e}i(t,e);return t}(Error);h.CycleError=function(e){function t(e){o(this,t);this.message="This graph contains a cycle: "+e;this.cycle=e}i(t,e);return t}(Error)}])}); | ||
| //# sourceMappingURL=dist/js-graph.min.js.map |
| { | ||
| "name": "js-graph", | ||
| "version": "1.0.0-alpha", | ||
| "version": "1.1.0-alpha", | ||
| "title": "Javascript Graph Datastructure", | ||
| "homepage": "https://github.com/mhelvens/js-graph", | ||
| "description": "a javascript library for storing arbitrary data in mathematical (di)graphs, as well as traversing and analyzing them in various ways", | ||
| "description": "a javascript library for storing arbitrary data in mathematical (di)graphs, as well as traversing and analyzing them in various ways (ECMAScript 6 Ready)", | ||
| "main": "dist/js-graph.es6.js", | ||
@@ -8,0 +8,0 @@ "author": { |
@@ -8,3 +8,4 @@ js-graph | ||
| as well as traversing and analyzing them in various ways. It was originally created to | ||
| track dependencies between options and modules. | ||
| track dependencies between options and modules. It is now rewritten in ECMAScript 6, but | ||
| ECMAScript 5 versions are shipped with it, automatically generated with [Babel](https://babeljs.io). | ||
@@ -11,0 +12,0 @@ The library is fully functional and has 100% test-coverage, but the API is not yet |
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Fixed alerts
Major refactor
Supply chain riskPackage has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.
Found 1 instance in 1 package
Improved metrics
- Total package byte prevSize
- increased by21.47%
158078
- Lines of code
- increased by37.71%
1742
- Number of lines in readme file
- increased by6.67%
16
- Number of medium supply chain risk alerts
- decreased by-100%
0
No dependency changes