Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
@dagrejs/graphlib
Advanced tools
@dagrejs/graphlib - npm Package Compare versions
Comparing version 2.2.1 to 2.2.2
@@ -462,4 +462,4 @@ (function(f){if(typeof exports==="object"&&typeof module!=="undefined"){module.exports=f()}else if(typeof define==="function"&&define.amd){define([],f)}else{var g;if(typeof window!=="undefined"){g=window}else if(typeof global!=="undefined"){g=global}else if(typeof self!=="undefined"){g=self}else{g=this}g.graphlib = f()}})(function(){var define,module,exports;return (function(){function r(e,n,t){function o(i,f){if(!n[i]){if(!e[i]){var c="function"==typeof require&&require;if(!f&&c)return c(i,!0);if(u)return u(i,!0);var a=new Error("Cannot find module '"+i+"'");throw a.code="MODULE_NOT_FOUND",a}var p=n[i]={exports:{}};e[i][0].call(p.exports,function(r){var n=e[i][1][r];return o(n||r)},p,p.exports,r,e,n,t)}return n[i].exports}for(var u="function"==typeof require&&require,i=0;i<t.length;i++)o(t[i]);return o}return r})()({1:[function(require,module,exports){ | ||
| class PriorityQueue { | ||
| #arr = []; | ||
| #keyIndices = {}; | ||
| _arr = []; | ||
| _keyIndices = {}; | ||
@@ -470,3 +470,3 @@ /** | ||
| size() { | ||
| return this.#arr.length; | ||
| return this._arr.length; | ||
| } | ||
@@ -478,3 +478,3 @@ | ||
| keys() { | ||
| return this.#arr.map(function(x) { return x.key; }); | ||
| return this._arr.map(function(x) { return x.key; }); | ||
| } | ||
@@ -486,3 +486,3 @@ | ||
| has(key) { | ||
| return this.#keyIndices.hasOwnProperty(key); | ||
| return this._keyIndices.hasOwnProperty(key); | ||
| } | ||
@@ -497,5 +497,5 @@ | ||
| priority(key) { | ||
| var index = this.#keyIndices[key]; | ||
| var index = this._keyIndices[key]; | ||
| if (index !== undefined) { | ||
| return this.#arr[index].priority; | ||
| return this._arr[index].priority; | ||
| } | ||
@@ -512,3 +512,3 @@ } | ||
| } | ||
| return this.#arr[0].key; | ||
| return this._arr[0].key; | ||
| } | ||
@@ -525,10 +525,10 @@ | ||
| add(key, priority) { | ||
| var keyIndices = this.#keyIndices; | ||
| var keyIndices = this._keyIndices; | ||
| key = String(key); | ||
| if (!keyIndices.hasOwnProperty(key)) { | ||
| var arr = this.#arr; | ||
| var arr = this._arr; | ||
| var index = arr.length; | ||
| keyIndices[key] = index; | ||
| arr.push({key: key, priority: priority}); | ||
| this.#decrease(index); | ||
| this._decrease(index); | ||
| return true; | ||
@@ -543,6 +543,6 @@ } | ||
| removeMin() { | ||
| this.#swap(0, this.#arr.length - 1); | ||
| var min = this.#arr.pop(); | ||
| delete this.#keyIndices[min.key]; | ||
| this.#heapify(0); | ||
| this._swap(0, this._arr.length - 1); | ||
| var min = this._arr.pop(); | ||
| delete this._keyIndices[min.key]; | ||
| this._heapify(0); | ||
| return min.key; | ||
@@ -559,13 +559,13 @@ } | ||
| decrease(key, priority) { | ||
| var index = this.#keyIndices[key]; | ||
| if (priority > this.#arr[index].priority) { | ||
| var index = this._keyIndices[key]; | ||
| if (priority > this._arr[index].priority) { | ||
| throw new Error("New priority is greater than current priority. " + | ||
| "Key: " + key + " Old: " + this.#arr[index].priority + " New: " + priority); | ||
| "Key: " + key + " Old: " + this._arr[index].priority + " New: " + priority); | ||
| } | ||
| this.#arr[index].priority = priority; | ||
| this.#decrease(index); | ||
| this._arr[index].priority = priority; | ||
| this._decrease(index); | ||
| } | ||
| #heapify(i) { | ||
| var arr = this.#arr; | ||
| _heapify(i) { | ||
| var arr = this._arr; | ||
| var l = 2 * i; | ||
@@ -580,4 +580,4 @@ var r = l + 1; | ||
| if (largest !== i) { | ||
| this.#swap(i, largest); | ||
| this.#heapify(largest); | ||
| this._swap(i, largest); | ||
| this._heapify(largest); | ||
| } | ||
@@ -587,4 +587,4 @@ } | ||
| #decrease(index) { | ||
| var arr = this.#arr; | ||
| _decrease(index) { | ||
| var arr = this._arr; | ||
| var priority = arr[index].priority; | ||
@@ -597,3 +597,3 @@ var parent; | ||
| } | ||
| this.#swap(index, parent); | ||
| this._swap(index, parent); | ||
| index = parent; | ||
@@ -603,5 +603,5 @@ } | ||
| #swap(i, j) { | ||
| var arr = this.#arr; | ||
| var keyIndices = this.#keyIndices; | ||
| _swap(i, j) { | ||
| var arr = this._arr; | ||
| var keyIndices = this._keyIndices; | ||
| var origArrI = arr[i]; | ||
@@ -636,60 +636,60 @@ var origArrJ = arr[j]; | ||
| class Graph { | ||
| #isDirected = true; | ||
| #isMultigraph = false; | ||
| #isCompound = false; | ||
| _isDirected = true; | ||
| _isMultigraph = false; | ||
| _isCompound = false; | ||
| // Label for the graph itself | ||
| #label; | ||
| _label; | ||
| // Defaults to be set when creating a new node | ||
| #defaultNodeLabelFn = () => undefined; | ||
| _defaultNodeLabelFn = () => undefined; | ||
| // Defaults to be set when creating a new edge | ||
| #defaultEdgeLabelFn = () => undefined; | ||
| _defaultEdgeLabelFn = () => undefined; | ||
| // v -> label | ||
| #nodes = {}; | ||
| _nodes = {}; | ||
| // v -> edgeObj | ||
| #in = {}; | ||
| _in = {}; | ||
| // u -> v -> Number | ||
| #preds = {}; | ||
| _preds = {}; | ||
| // v -> edgeObj | ||
| #out = {}; | ||
| _out = {}; | ||
| // v -> w -> Number | ||
| #sucs = {}; | ||
| _sucs = {}; | ||
| // e -> edgeObj | ||
| #edgeObjs = {}; | ||
| _edgeObjs = {}; | ||
| // e -> label | ||
| #edgeLabels = {}; | ||
| _edgeLabels = {}; | ||
| /* Number of nodes in the graph. Should only be changed by the implementation. */ | ||
| #nodeCount = 0; | ||
| _nodeCount = 0; | ||
| /* Number of edges in the graph. Should only be changed by the implementation. */ | ||
| #edgeCount = 0; | ||
| _edgeCount = 0; | ||
| #parent; | ||
| _parent; | ||
| #children; | ||
| _children; | ||
| constructor(opts) { | ||
| if (opts) { | ||
| this.#isDirected = opts.hasOwnProperty("directed") ? opts.directed : true; | ||
| this.#isMultigraph = opts.hasOwnProperty("multigraph") ? opts.multigraph : false; | ||
| this.#isCompound = opts.hasOwnProperty("compound") ? opts.compound : false; | ||
| this._isDirected = opts.hasOwnProperty("directed") ? opts.directed : true; | ||
| this._isMultigraph = opts.hasOwnProperty("multigraph") ? opts.multigraph : false; | ||
| this._isCompound = opts.hasOwnProperty("compound") ? opts.compound : false; | ||
| } | ||
| if (this.#isCompound) { | ||
| if (this._isCompound) { | ||
| // v -> parent | ||
| this.#parent = {}; | ||
| this._parent = {}; | ||
| // v -> children | ||
| this.#children = {}; | ||
| this.#children[GRAPH_NODE] = {}; | ||
| this._children = {}; | ||
| this._children[GRAPH_NODE] = {}; | ||
| } | ||
@@ -704,3 +704,3 @@ } | ||
| isDirected() { | ||
| return this.#isDirected; | ||
| return this._isDirected; | ||
| } | ||
@@ -712,3 +712,3 @@ | ||
| isMultigraph() { | ||
| return this.#isMultigraph; | ||
| return this._isMultigraph; | ||
| } | ||
@@ -720,3 +720,3 @@ | ||
| isCompound() { | ||
| return this.#isCompound; | ||
| return this._isCompound; | ||
| } | ||
@@ -728,3 +728,3 @@ | ||
| setGraph(label) { | ||
| this.#label = label; | ||
| this._label = label; | ||
| return this; | ||
@@ -737,3 +737,3 @@ } | ||
| graph() { | ||
| return this.#label; | ||
| return this._label; | ||
| } | ||
@@ -752,5 +752,5 @@ | ||
| setDefaultNodeLabel(newDefault) { | ||
| this.#defaultNodeLabelFn = newDefault; | ||
| this._defaultNodeLabelFn = newDefault; | ||
| if (typeof newDefault !== 'function') { | ||
| this.#defaultNodeLabelFn = () => newDefault; | ||
| this._defaultNodeLabelFn = () => newDefault; | ||
| } | ||
@@ -766,3 +766,3 @@ | ||
| nodeCount() { | ||
| return this.#nodeCount; | ||
| return this._nodeCount; | ||
| } | ||
@@ -776,3 +776,3 @@ | ||
| nodes() { | ||
| return Object.keys(this.#nodes); | ||
| return Object.keys(this._nodes); | ||
| } | ||
@@ -786,3 +786,3 @@ | ||
| var self = this; | ||
| return this.nodes().filter(v => Object.keys(self.#in[v]).length === 0); | ||
| return this.nodes().filter(v => Object.keys(self._in[v]).length === 0); | ||
| } | ||
@@ -796,3 +796,3 @@ | ||
| var self = this; | ||
| return this.nodes().filter(v => Object.keys(self.#out[v]).length === 0); | ||
| return this.nodes().filter(v => Object.keys(self._out[v]).length === 0); | ||
| } | ||
@@ -824,5 +824,5 @@ | ||
| setNode(v, value) { | ||
| if (this.#nodes.hasOwnProperty(v)) { | ||
| if (this._nodes.hasOwnProperty(v)) { | ||
| if (arguments.length > 1) { | ||
| this.#nodes[v] = value; | ||
| this._nodes[v] = value; | ||
| } | ||
@@ -832,13 +832,13 @@ return this; | ||
| this.#nodes[v] = arguments.length > 1 ? value : this.#defaultNodeLabelFn(v); | ||
| if (this.#isCompound) { | ||
| this.#parent[v] = GRAPH_NODE; | ||
| this.#children[v] = {}; | ||
| this.#children[GRAPH_NODE][v] = true; | ||
| this._nodes[v] = arguments.length > 1 ? value : this._defaultNodeLabelFn(v); | ||
| if (this._isCompound) { | ||
| this._parent[v] = GRAPH_NODE; | ||
| this._children[v] = {}; | ||
| this._children[GRAPH_NODE][v] = true; | ||
| } | ||
| this.#in[v] = {}; | ||
| this.#preds[v] = {}; | ||
| this.#out[v] = {}; | ||
| this.#sucs[v] = {}; | ||
| ++this.#nodeCount; | ||
| this._in[v] = {}; | ||
| this._preds[v] = {}; | ||
| this._out[v] = {}; | ||
| this._sucs[v] = {}; | ||
| ++this._nodeCount; | ||
| return this; | ||
@@ -852,3 +852,3 @@ } | ||
| node(v) { | ||
| return this.#nodes[v]; | ||
| return this._nodes[v]; | ||
| } | ||
@@ -860,3 +860,3 @@ | ||
| hasNode(v) { | ||
| return this.#nodes.hasOwnProperty(v); | ||
| return this._nodes.hasOwnProperty(v); | ||
| } | ||
@@ -872,20 +872,20 @@ | ||
| var self = this; | ||
| if (this.#nodes.hasOwnProperty(v)) { | ||
| var removeEdge = e => self.removeEdge(self.#edgeObjs[e]); | ||
| delete this.#nodes[v]; | ||
| if (this.#isCompound) { | ||
| this.#removeFromParentsChildList(v); | ||
| delete this.#parent[v]; | ||
| if (this._nodes.hasOwnProperty(v)) { | ||
| var removeEdge = e => self.removeEdge(self._edgeObjs[e]); | ||
| delete this._nodes[v]; | ||
| if (this._isCompound) { | ||
| this._removeFromParentsChildList(v); | ||
| delete this._parent[v]; | ||
| this.children(v).forEach(function(child) { | ||
| self.setParent(child); | ||
| }); | ||
| delete this.#children[v]; | ||
| delete this._children[v]; | ||
| } | ||
| Object.keys(this.#in[v]).forEach(removeEdge); | ||
| delete this.#in[v]; | ||
| delete this.#preds[v]; | ||
| Object.keys(this.#out[v]).forEach(removeEdge); | ||
| delete this.#out[v]; | ||
| delete this.#sucs[v]; | ||
| --this.#nodeCount; | ||
| Object.keys(this._in[v]).forEach(removeEdge); | ||
| delete this._in[v]; | ||
| delete this._preds[v]; | ||
| Object.keys(this._out[v]).forEach(removeEdge); | ||
| delete this._out[v]; | ||
| delete this._sucs[v]; | ||
| --this._nodeCount; | ||
| } | ||
@@ -902,3 +902,3 @@ return this; | ||
| setParent(v, parent) { | ||
| if (!this.#isCompound) { | ||
| if (!this._isCompound) { | ||
| throw new Error("Cannot set parent in a non-compound graph"); | ||
@@ -923,10 +923,10 @@ } | ||
| this.setNode(v); | ||
| this.#removeFromParentsChildList(v); | ||
| this.#parent[v] = parent; | ||
| this.#children[parent][v] = true; | ||
| this._removeFromParentsChildList(v); | ||
| this._parent[v] = parent; | ||
| this._children[parent][v] = true; | ||
| return this; | ||
| } | ||
| #removeFromParentsChildList(v) { | ||
| delete this.#children[this.#parent[v]][v]; | ||
| _removeFromParentsChildList(v) { | ||
| delete this._children[this._parent[v]][v]; | ||
| } | ||
@@ -939,4 +939,4 @@ | ||
| parent(v) { | ||
| if (this.#isCompound) { | ||
| var parent = this.#parent[v]; | ||
| if (this._isCompound) { | ||
| var parent = this._parent[v]; | ||
| if (parent !== GRAPH_NODE) { | ||
@@ -953,4 +953,4 @@ return parent; | ||
| children(v = GRAPH_NODE) { | ||
| if (this.#isCompound) { | ||
| var children = this.#children[v]; | ||
| if (this._isCompound) { | ||
| var children = this._children[v]; | ||
| if (children) { | ||
@@ -972,3 +972,3 @@ return Object.keys(children); | ||
| predecessors(v) { | ||
| var predsV = this.#preds[v]; | ||
| var predsV = this._preds[v]; | ||
| if (predsV) { | ||
@@ -985,3 +985,3 @@ return Object.keys(predsV); | ||
| successors(v) { | ||
| var sucsV = this.#sucs[v]; | ||
| var sucsV = this._sucs[v]; | ||
| if (sucsV) { | ||
@@ -1027,5 +1027,5 @@ return Object.keys(sucsV); | ||
| var copy = new this.constructor({ | ||
| directed: this.#isDirected, | ||
| multigraph: this.#isMultigraph, | ||
| compound: this.#isCompound | ||
| directed: this._isDirected, | ||
| multigraph: this._isMultigraph, | ||
| compound: this._isCompound | ||
| }); | ||
@@ -1036,3 +1036,3 @@ | ||
| var self = this; | ||
| Object.entries(this.#nodes).forEach(function([v, value]) { | ||
| Object.entries(this._nodes).forEach(function([v, value]) { | ||
| if (filter(v)) { | ||
@@ -1043,3 +1043,3 @@ copy.setNode(v, value); | ||
| Object.values(this.#edgeObjs).forEach(function(e) { | ||
| Object.values(this._edgeObjs).forEach(function(e) { | ||
| if (copy.hasNode(e.v) && copy.hasNode(e.w)) { | ||
@@ -1063,3 +1063,3 @@ copy.setEdge(e, self.edge(e)); | ||
| if (this.#isCompound) { | ||
| if (this._isCompound) { | ||
| copy.nodes().forEach(v => copy.setParent(v, findParent(v))); | ||
@@ -1081,5 +1081,5 @@ } | ||
| setDefaultEdgeLabel(newDefault) { | ||
| this.#defaultEdgeLabelFn = newDefault; | ||
| this._defaultEdgeLabelFn = newDefault; | ||
| if (typeof newDefault !== 'function') { | ||
| this.#defaultEdgeLabelFn = () => newDefault; | ||
| this._defaultEdgeLabelFn = () => newDefault; | ||
| } | ||
@@ -1095,3 +1095,3 @@ | ||
| edgeCount() { | ||
| return this.#edgeCount; | ||
| return this._edgeCount; | ||
| } | ||
@@ -1104,3 +1104,3 @@ | ||
| edges() { | ||
| return Object.values(this.#edgeObjs); | ||
| return Object.values(this._edgeObjs); | ||
| } | ||
@@ -1163,6 +1163,6 @@ | ||
| var e = edgeArgsToId(this.#isDirected, v, w, name); | ||
| if (this.#edgeLabels.hasOwnProperty(e)) { | ||
| var e = edgeArgsToId(this._isDirected, v, w, name); | ||
| if (this._edgeLabels.hasOwnProperty(e)) { | ||
| if (valueSpecified) { | ||
| this.#edgeLabels[e] = value; | ||
| this._edgeLabels[e] = value; | ||
| } | ||
@@ -1172,3 +1172,3 @@ return this; | ||
| if (name !== undefined && !this.#isMultigraph) { | ||
| if (name !== undefined && !this._isMultigraph) { | ||
| throw new Error("Cannot set a named edge when isMultigraph = false"); | ||
@@ -1182,5 +1182,5 @@ } | ||
| this.#edgeLabels[e] = valueSpecified ? value : this.#defaultEdgeLabelFn(v, w, name); | ||
| this._edgeLabels[e] = valueSpecified ? value : this._defaultEdgeLabelFn(v, w, name); | ||
| var edgeObj = edgeArgsToObj(this.#isDirected, v, w, name); | ||
| var edgeObj = edgeArgsToObj(this._isDirected, v, w, name); | ||
| // Ensure we add undirected edges in a consistent way. | ||
@@ -1191,8 +1191,8 @@ v = edgeObj.v; | ||
| Object.freeze(edgeObj); | ||
| this.#edgeObjs[e] = edgeObj; | ||
| incrementOrInitEntry(this.#preds[w], v); | ||
| incrementOrInitEntry(this.#sucs[v], w); | ||
| this.#in[w][e] = edgeObj; | ||
| this.#out[v][e] = edgeObj; | ||
| this.#edgeCount++; | ||
| this._edgeObjs[e] = edgeObj; | ||
| incrementOrInitEntry(this._preds[w], v); | ||
| incrementOrInitEntry(this._sucs[v], w); | ||
| this._in[w][e] = edgeObj; | ||
| this._out[v][e] = edgeObj; | ||
| this._edgeCount++; | ||
| return this; | ||
@@ -1207,5 +1207,5 @@ } | ||
| var e = (arguments.length === 1 | ||
| ? edgeObjToId(this.#isDirected, arguments[0]) | ||
| : edgeArgsToId(this.#isDirected, v, w, name)); | ||
| return this.#edgeLabels[e]; | ||
| ? edgeObjToId(this._isDirected, arguments[0]) | ||
| : edgeArgsToId(this._isDirected, v, w, name)); | ||
| return this._edgeLabels[e]; | ||
| } | ||
@@ -1232,5 +1232,5 @@ | ||
| var e = (arguments.length === 1 | ||
| ? edgeObjToId(this.#isDirected, arguments[0]) | ||
| : edgeArgsToId(this.#isDirected, v, w, name)); | ||
| return this.#edgeLabels.hasOwnProperty(e); | ||
| ? edgeObjToId(this._isDirected, arguments[0]) | ||
| : edgeArgsToId(this._isDirected, v, w, name)); | ||
| return this._edgeLabels.hasOwnProperty(e); | ||
| } | ||
@@ -1244,15 +1244,15 @@ | ||
| var e = (arguments.length === 1 | ||
| ? edgeObjToId(this.#isDirected, arguments[0]) | ||
| : edgeArgsToId(this.#isDirected, v, w, name)); | ||
| var edge = this.#edgeObjs[e]; | ||
| ? edgeObjToId(this._isDirected, arguments[0]) | ||
| : edgeArgsToId(this._isDirected, v, w, name)); | ||
| var edge = this._edgeObjs[e]; | ||
| if (edge) { | ||
| v = edge.v; | ||
| w = edge.w; | ||
| delete this.#edgeLabels[e]; | ||
| delete this.#edgeObjs[e]; | ||
| decrementOrRemoveEntry(this.#preds[w], v); | ||
| decrementOrRemoveEntry(this.#sucs[v], w); | ||
| delete this.#in[w][e]; | ||
| delete this.#out[v][e]; | ||
| this.#edgeCount--; | ||
| delete this._edgeLabels[e]; | ||
| delete this._edgeObjs[e]; | ||
| decrementOrRemoveEntry(this._preds[w], v); | ||
| decrementOrRemoveEntry(this._sucs[v], w); | ||
| delete this._in[w][e]; | ||
| delete this._out[v][e]; | ||
| this._edgeCount--; | ||
| } | ||
@@ -1268,3 +1268,3 @@ return this; | ||
| inEdges(v, u) { | ||
| var inV = this.#in[v]; | ||
| var inV = this._in[v]; | ||
| if (inV) { | ||
@@ -1285,3 +1285,3 @@ var edges = Object.values(inV); | ||
| outEdges(v, w) { | ||
| var outV = this.#out[v]; | ||
| var outV = this._out[v]; | ||
| if (outV) { | ||
@@ -1444,5 +1444,5 @@ var edges = Object.values(outV); | ||
| },{"./graph":16}],19:[function(require,module,exports){ | ||
| module.exports = '2.2.1'; | ||
| module.exports = '2.2.2'; | ||
| },{}]},{},[1])(1) | ||
| }); |
@@ -50,12 +50,12 @@ (function(f){if(typeof exports==="object"&&typeof module!=="undefined"){module.exports=f()}else if(typeof define==="function"&&define.amd){define([],f)}else{var g;if(typeof window!=="undefined"){g=window}else if(typeof global!=="undefined"){g=global}else if(typeof self!=="undefined"){g=self}else{g=this}g.graphlib=f()}})(function(){var define,module,exports;return function(){function r(e,n,t){function o(i,f){if(!n[i]){if(!e[i]){var c="function"==typeof require&&require;if(!f&&c)return c(i,!0);if(u)return u(i,!0);var a=new Error("Cannot find module '"+i+"'");throw a.code="MODULE_NOT_FOUND",a}var p=n[i]={exports:{}};e[i][0].call(p.exports,function(r){var n=e[i][1][r];return o(n||r)},p,p.exports,r,e,n,t)}return n[i].exports}for(var u="function"==typeof require&&require,i=0;i<t.length;i++)o(t[i]);return o}return r}()({1:[function(require,module,exports){ | ||
| */ | ||
| class PriorityQueue{#arr=[];#keyIndices={}; | ||
| class PriorityQueue{_arr=[];_keyIndices={}; | ||
| /** | ||
| * Returns the number of elements in the queue. Takes `O(1)` time. | ||
| */size(){return this.#arr.length} | ||
| */size(){return this._arr.length} | ||
| /** | ||
| * Returns the keys that are in the queue. Takes `O(n)` time. | ||
| */keys(){return this.#arr.map(function(x){return x.key})} | ||
| */keys(){return this._arr.map(function(x){return x.key})} | ||
| /** | ||
| * Returns `true` if **key** is in the queue and `false` if not. | ||
| */has(key){return this.#keyIndices.hasOwnProperty(key)} | ||
| */has(key){return this._keyIndices.hasOwnProperty(key)} | ||
| /** | ||
@@ -66,7 +66,7 @@ * Returns the priority for **key**. If **key** is not present in the queue | ||
| * @param {Object} key | ||
| */priority(key){var index=this.#keyIndices[key];if(index!==undefined){return this.#arr[index].priority}} | ||
| */priority(key){var index=this._keyIndices[key];if(index!==undefined){return this._arr[index].priority}} | ||
| /** | ||
| * Returns the key for the minimum element in this queue. If the queue is | ||
| * empty this function throws an Error. Takes `O(1)` time. | ||
| */min(){if(this.size()===0){throw new Error("Queue underflow")}return this.#arr[0].key} | ||
| */min(){if(this.size()===0){throw new Error("Queue underflow")}return this._arr[0].key} | ||
| /** | ||
@@ -79,6 +79,6 @@ * Inserts a new key into the priority queue. If the key already exists in | ||
| * @param {Number} priority the initial priority for the key | ||
| */add(key,priority){var keyIndices=this.#keyIndices;key=String(key);if(!keyIndices.hasOwnProperty(key)){var arr=this.#arr;var index=arr.length;keyIndices[key]=index;arr.push({key:key,priority:priority});this.#decrease(index);return true}return false} | ||
| */add(key,priority){var keyIndices=this._keyIndices;key=String(key);if(!keyIndices.hasOwnProperty(key)){var arr=this._arr;var index=arr.length;keyIndices[key]=index;arr.push({key:key,priority:priority});this._decrease(index);return true}return false} | ||
| /** | ||
| * Removes and returns the smallest key in the queue. Takes `O(log n)` time. | ||
| */removeMin(){this.#swap(0,this.#arr.length-1);var min=this.#arr.pop();delete this.#keyIndices[min.key];this.#heapify(0);return min.key} | ||
| */removeMin(){this._swap(0,this._arr.length-1);var min=this._arr.pop();delete this._keyIndices[min.key];this._heapify(0);return min.key} | ||
| /** | ||
@@ -90,3 +90,3 @@ * Decreases the priority for **key** to **priority**. If the new priority is | ||
| * @param {Number} priority the new priority for the key | ||
| */decrease(key,priority){var index=this.#keyIndices[key];if(priority>this.#arr[index].priority){throw new Error("New priority is greater than current priority. "+"Key: "+key+" Old: "+this.#arr[index].priority+" New: "+priority)}this.#arr[index].priority=priority;this.#decrease(index)}#heapify(i){var arr=this.#arr;var l=2*i;var r=l+1;var largest=i;if(l<arr.length){largest=arr[l].priority<arr[largest].priority?l:largest;if(r<arr.length){largest=arr[r].priority<arr[largest].priority?r:largest}if(largest!==i){this.#swap(i,largest);this.#heapify(largest)}}}#decrease(index){var arr=this.#arr;var priority=arr[index].priority;var parent;while(index!==0){parent=index>>1;if(arr[parent].priority<priority){break}this.#swap(index,parent);index=parent}}#swap(i,j){var arr=this.#arr;var keyIndices=this.#keyIndices;var origArrI=arr[i];var origArrJ=arr[j];arr[i]=origArrJ;arr[j]=origArrI;keyIndices[origArrJ.key]=i;keyIndices[origArrI.key]=j}}module.exports=PriorityQueue},{}],16:[function(require,module,exports){"use strict";var DEFAULT_EDGE_NAME="\0";var GRAPH_NODE="\0";var EDGE_KEY_DELIM=""; | ||
| */decrease(key,priority){var index=this._keyIndices[key];if(priority>this._arr[index].priority){throw new Error("New priority is greater than current priority. "+"Key: "+key+" Old: "+this._arr[index].priority+" New: "+priority)}this._arr[index].priority=priority;this._decrease(index)}_heapify(i){var arr=this._arr;var l=2*i;var r=l+1;var largest=i;if(l<arr.length){largest=arr[l].priority<arr[largest].priority?l:largest;if(r<arr.length){largest=arr[r].priority<arr[largest].priority?r:largest}if(largest!==i){this._swap(i,largest);this._heapify(largest)}}}_decrease(index){var arr=this._arr;var priority=arr[index].priority;var parent;while(index!==0){parent=index>>1;if(arr[parent].priority<priority){break}this._swap(index,parent);index=parent}}_swap(i,j){var arr=this._arr;var keyIndices=this._keyIndices;var origArrI=arr[i];var origArrJ=arr[j];arr[i]=origArrJ;arr[j]=origArrI;keyIndices[origArrJ.key]=i;keyIndices[origArrI.key]=j}}module.exports=PriorityQueue},{}],16:[function(require,module,exports){"use strict";var DEFAULT_EDGE_NAME="\0";var GRAPH_NODE="\0";var EDGE_KEY_DELIM=""; | ||
| // Implementation notes: | ||
@@ -101,45 +101,45 @@ // | ||
| // we're going to get to a performant hashtable in JavaScript. | ||
| class Graph{#isDirected=true;#isMultigraph=false;#isCompound=false; | ||
| class Graph{_isDirected=true;_isMultigraph=false;_isCompound=false; | ||
| // Label for the graph itself | ||
| #label; | ||
| _label; | ||
| // Defaults to be set when creating a new node | ||
| #defaultNodeLabelFn=()=>undefined; | ||
| _defaultNodeLabelFn=()=>undefined; | ||
| // Defaults to be set when creating a new edge | ||
| #defaultEdgeLabelFn=()=>undefined; | ||
| _defaultEdgeLabelFn=()=>undefined; | ||
| // v -> label | ||
| #nodes={}; | ||
| _nodes={}; | ||
| // v -> edgeObj | ||
| #in={}; | ||
| _in={}; | ||
| // u -> v -> Number | ||
| #preds={}; | ||
| _preds={}; | ||
| // v -> edgeObj | ||
| #out={}; | ||
| _out={}; | ||
| // v -> w -> Number | ||
| #sucs={}; | ||
| _sucs={}; | ||
| // e -> edgeObj | ||
| #edgeObjs={}; | ||
| _edgeObjs={}; | ||
| // e -> label | ||
| #edgeLabels={}; | ||
| /* Number of nodes in the graph. Should only be changed by the implementation. */#nodeCount=0; | ||
| /* Number of edges in the graph. Should only be changed by the implementation. */#edgeCount=0;#parent;#children;constructor(opts){if(opts){this.#isDirected=opts.hasOwnProperty("directed")?opts.directed:true;this.#isMultigraph=opts.hasOwnProperty("multigraph")?opts.multigraph:false;this.#isCompound=opts.hasOwnProperty("compound")?opts.compound:false}if(this.#isCompound){ | ||
| _edgeLabels={}; | ||
| /* Number of nodes in the graph. Should only be changed by the implementation. */_nodeCount=0; | ||
| /* Number of edges in the graph. Should only be changed by the implementation. */_edgeCount=0;_parent;_children;constructor(opts){if(opts){this._isDirected=opts.hasOwnProperty("directed")?opts.directed:true;this._isMultigraph=opts.hasOwnProperty("multigraph")?opts.multigraph:false;this._isCompound=opts.hasOwnProperty("compound")?opts.compound:false}if(this._isCompound){ | ||
| // v -> parent | ||
| this.#parent={}; | ||
| this._parent={}; | ||
| // v -> children | ||
| this.#children={};this.#children[GRAPH_NODE]={}}} | ||
| this._children={};this._children[GRAPH_NODE]={}}} | ||
| /* === Graph functions ========= */ | ||
| /** | ||
| * Whether graph was created with 'directed' flag set to true or not. | ||
| */isDirected(){return this.#isDirected} | ||
| */isDirected(){return this._isDirected} | ||
| /** | ||
| * Whether graph was created with 'multigraph' flag set to true or not. | ||
| */isMultigraph(){return this.#isMultigraph} | ||
| */isMultigraph(){return this._isMultigraph} | ||
| /** | ||
| * Whether graph was created with 'compound' flag set to true or not. | ||
| */isCompound(){return this.#isCompound} | ||
| */isCompound(){return this._isCompound} | ||
| /** | ||
| * Sets the label of the graph. | ||
| */setGraph(label){this.#label=label;return this} | ||
| */setGraph(label){this._label=label;return this} | ||
| /** | ||
| * Gets the graph label. | ||
| */graph(){return this.#label} | ||
| */graph(){return this._label} | ||
| /* === Node functions ========== */ | ||
@@ -152,7 +152,7 @@ /** | ||
| * Complexity: O(1). | ||
| */setDefaultNodeLabel(newDefault){this.#defaultNodeLabelFn=newDefault;if(typeof newDefault!=="function"){this.#defaultNodeLabelFn=()=>newDefault}return this} | ||
| */setDefaultNodeLabel(newDefault){this._defaultNodeLabelFn=newDefault;if(typeof newDefault!=="function"){this._defaultNodeLabelFn=()=>newDefault}return this} | ||
| /** | ||
| * Gets the number of nodes in the graph. | ||
| * Complexity: O(1). | ||
| */nodeCount(){return this.#nodeCount} | ||
| */nodeCount(){return this._nodeCount} | ||
| /** | ||
@@ -162,11 +162,11 @@ * Gets all nodes of the graph. Note, the in case of compound graph subnodes are | ||
| * Complexity: O(1). | ||
| */nodes(){return Object.keys(this.#nodes)} | ||
| */nodes(){return Object.keys(this._nodes)} | ||
| /** | ||
| * Gets list of nodes without in-edges. | ||
| * Complexity: O(|V|). | ||
| */sources(){var self=this;return this.nodes().filter(v=>Object.keys(self.#in[v]).length===0)} | ||
| */sources(){var self=this;return this.nodes().filter(v=>Object.keys(self._in[v]).length===0)} | ||
| /** | ||
| * Gets list of nodes without out-edges. | ||
| * Complexity: O(|V|). | ||
| */sinks(){var self=this;return this.nodes().filter(v=>Object.keys(self.#out[v]).length===0)} | ||
| */sinks(){var self=this;return this.nodes().filter(v=>Object.keys(self._out[v]).length===0)} | ||
| /** | ||
@@ -181,10 +181,10 @@ * Invokes setNode method for each node in names list. | ||
| * Complexity: O(1). | ||
| */setNode(v,value){if(this.#nodes.hasOwnProperty(v)){if(arguments.length>1){this.#nodes[v]=value}return this}this.#nodes[v]=arguments.length>1?value:this.#defaultNodeLabelFn(v);if(this.#isCompound){this.#parent[v]=GRAPH_NODE;this.#children[v]={};this.#children[GRAPH_NODE][v]=true}this.#in[v]={};this.#preds[v]={};this.#out[v]={};this.#sucs[v]={};++this.#nodeCount;return this} | ||
| */setNode(v,value){if(this._nodes.hasOwnProperty(v)){if(arguments.length>1){this._nodes[v]=value}return this}this._nodes[v]=arguments.length>1?value:this._defaultNodeLabelFn(v);if(this._isCompound){this._parent[v]=GRAPH_NODE;this._children[v]={};this._children[GRAPH_NODE][v]=true}this._in[v]={};this._preds[v]={};this._out[v]={};this._sucs[v]={};++this._nodeCount;return this} | ||
| /** | ||
| * Gets the label of node with specified name. | ||
| * Complexity: O(|V|). | ||
| */node(v){return this.#nodes[v]} | ||
| */node(v){return this._nodes[v]} | ||
| /** | ||
| * Detects whether graph has a node with specified name or not. | ||
| */hasNode(v){return this.#nodes.hasOwnProperty(v)} | ||
| */hasNode(v){return this._nodes.hasOwnProperty(v)} | ||
| /** | ||
@@ -195,3 +195,3 @@ * Remove the node with the name from the graph or do nothing if the node is not in | ||
| * Complexity: O(1). | ||
| */removeNode(v){var self=this;if(this.#nodes.hasOwnProperty(v)){var removeEdge=e=>self.removeEdge(self.#edgeObjs[e]);delete this.#nodes[v];if(this.#isCompound){this.#removeFromParentsChildList(v);delete this.#parent[v];this.children(v).forEach(function(child){self.setParent(child)});delete this.#children[v]}Object.keys(this.#in[v]).forEach(removeEdge);delete this.#in[v];delete this.#preds[v];Object.keys(this.#out[v]).forEach(removeEdge);delete this.#out[v];delete this.#sucs[v];--this.#nodeCount}return this} | ||
| */removeNode(v){var self=this;if(this._nodes.hasOwnProperty(v)){var removeEdge=e=>self.removeEdge(self._edgeObjs[e]);delete this._nodes[v];if(this._isCompound){this._removeFromParentsChildList(v);delete this._parent[v];this.children(v).forEach(function(child){self.setParent(child)});delete this._children[v]}Object.keys(this._in[v]).forEach(removeEdge);delete this._in[v];delete this._preds[v];Object.keys(this._out[v]).forEach(removeEdge);delete this._out[v];delete this._sucs[v];--this._nodeCount}return this} | ||
| /** | ||
@@ -202,13 +202,13 @@ * Sets node p as a parent for node v if it is defined, or removes the | ||
| * Average-case complexity: O(1). | ||
| */setParent(v,parent){if(!this.#isCompound){throw new Error("Cannot set parent in a non-compound graph")}if(parent===undefined){parent=GRAPH_NODE}else{ | ||
| */setParent(v,parent){if(!this._isCompound){throw new Error("Cannot set parent in a non-compound graph")}if(parent===undefined){parent=GRAPH_NODE}else{ | ||
| // Coerce parent to string | ||
| parent+="";for(var ancestor=parent;ancestor!==undefined;ancestor=this.parent(ancestor)){if(ancestor===v){throw new Error("Setting "+parent+" as parent of "+v+" would create a cycle")}}this.setNode(parent)}this.setNode(v);this.#removeFromParentsChildList(v);this.#parent[v]=parent;this.#children[parent][v]=true;return this}#removeFromParentsChildList(v){delete this.#children[this.#parent[v]][v]} | ||
| parent+="";for(var ancestor=parent;ancestor!==undefined;ancestor=this.parent(ancestor)){if(ancestor===v){throw new Error("Setting "+parent+" as parent of "+v+" would create a cycle")}}this.setNode(parent)}this.setNode(v);this._removeFromParentsChildList(v);this._parent[v]=parent;this._children[parent][v]=true;return this}_removeFromParentsChildList(v){delete this._children[this._parent[v]][v]} | ||
| /** | ||
| * Gets parent node for node v. | ||
| * Complexity: O(1). | ||
| */parent(v){if(this.#isCompound){var parent=this.#parent[v];if(parent!==GRAPH_NODE){return parent}}} | ||
| */parent(v){if(this._isCompound){var parent=this._parent[v];if(parent!==GRAPH_NODE){return parent}}} | ||
| /** | ||
| * Gets list of direct children of node v. | ||
| * Complexity: O(1). | ||
| */children(v=GRAPH_NODE){if(this.#isCompound){var children=this.#children[v];if(children){return Object.keys(children)}}else if(v===GRAPH_NODE){return this.nodes()}else if(this.hasNode(v)){return[]}} | ||
| */children(v=GRAPH_NODE){if(this._isCompound){var children=this._children[v];if(children){return Object.keys(children)}}else if(v===GRAPH_NODE){return this.nodes()}else if(this.hasNode(v)){return[]}} | ||
| /** | ||
@@ -218,3 +218,3 @@ * Return all nodes that are predecessors of the specified node or undefined if node v is not in | ||
| * Complexity: O(|V|). | ||
| */predecessors(v){var predsV=this.#preds[v];if(predsV){return Object.keys(predsV)}} | ||
| */predecessors(v){var predsV=this._preds[v];if(predsV){return Object.keys(predsV)}} | ||
| /** | ||
@@ -224,3 +224,3 @@ * Return all nodes that are successors of the specified node or undefined if node v is not in | ||
| * Complexity: O(|V|). | ||
| */successors(v){var sucsV=this.#sucs[v];if(sucsV){return Object.keys(sucsV)}} | ||
| */successors(v){var sucsV=this._sucs[v];if(sucsV){return Object.keys(sucsV)}} | ||
| /** | ||
@@ -236,3 +236,3 @@ * Return all nodes that are predecessors or successors of the specified node or undefined if | ||
| * Average-case complexity: O(|E|+|V|). | ||
| */filterNodes(filter){var copy=new this.constructor({directed:this.#isDirected,multigraph:this.#isMultigraph,compound:this.#isCompound});copy.setGraph(this.graph());var self=this;Object.entries(this.#nodes).forEach(function([v,value]){if(filter(v)){copy.setNode(v,value)}});Object.values(this.#edgeObjs).forEach(function(e){if(copy.hasNode(e.v)&©.hasNode(e.w)){copy.setEdge(e,self.edge(e))}});var parents={};function findParent(v){var parent=self.parent(v);if(parent===undefined||copy.hasNode(parent)){parents[v]=parent;return parent}else if(parent in parents){return parents[parent]}else{return findParent(parent)}}if(this.#isCompound){copy.nodes().forEach(v=>copy.setParent(v,findParent(v)))}return copy} | ||
| */filterNodes(filter){var copy=new this.constructor({directed:this._isDirected,multigraph:this._isMultigraph,compound:this._isCompound});copy.setGraph(this.graph());var self=this;Object.entries(this._nodes).forEach(function([v,value]){if(filter(v)){copy.setNode(v,value)}});Object.values(this._edgeObjs).forEach(function(e){if(copy.hasNode(e.v)&©.hasNode(e.w)){copy.setEdge(e,self.edge(e))}});var parents={};function findParent(v){var parent=self.parent(v);if(parent===undefined||copy.hasNode(parent)){parents[v]=parent;return parent}else if(parent in parents){return parents[parent]}else{return findParent(parent)}}if(this._isCompound){copy.nodes().forEach(v=>copy.setParent(v,findParent(v)))}return copy} | ||
| /* === Edge functions ========== */ | ||
@@ -245,11 +245,11 @@ /** | ||
| * Complexity: O(1). | ||
| */setDefaultEdgeLabel(newDefault){this.#defaultEdgeLabelFn=newDefault;if(typeof newDefault!=="function"){this.#defaultEdgeLabelFn=()=>newDefault}return this} | ||
| */setDefaultEdgeLabel(newDefault){this._defaultEdgeLabelFn=newDefault;if(typeof newDefault!=="function"){this._defaultEdgeLabelFn=()=>newDefault}return this} | ||
| /** | ||
| * Gets the number of edges in the graph. | ||
| * Complexity: O(1). | ||
| */edgeCount(){return this.#edgeCount} | ||
| */edgeCount(){return this._edgeCount} | ||
| /** | ||
| * Gets edges of the graph. In case of compound graph subgraphs are not considered. | ||
| * Complexity: O(|E|). | ||
| */edges(){return Object.values(this.#edgeObjs)} | ||
| */edges(){return Object.values(this._edgeObjs)} | ||
| /** | ||
@@ -266,12 +266,12 @@ * Establish an edges path over the nodes in nodes list. If some edge is already | ||
| * be assigned. The name parameter is only useful with multigraphs. | ||
| */setEdge(){var v,w,name,value;var valueSpecified=false;var arg0=arguments[0];if(typeof arg0==="object"&&arg0!==null&&"v"in arg0){v=arg0.v;w=arg0.w;name=arg0.name;if(arguments.length===2){value=arguments[1];valueSpecified=true}}else{v=arg0;w=arguments[1];name=arguments[3];if(arguments.length>2){value=arguments[2];valueSpecified=true}}v=""+v;w=""+w;if(name!==undefined){name=""+name}var e=edgeArgsToId(this.#isDirected,v,w,name);if(this.#edgeLabels.hasOwnProperty(e)){if(valueSpecified){this.#edgeLabels[e]=value}return this}if(name!==undefined&&!this.#isMultigraph){throw new Error("Cannot set a named edge when isMultigraph = false")} | ||
| */setEdge(){var v,w,name,value;var valueSpecified=false;var arg0=arguments[0];if(typeof arg0==="object"&&arg0!==null&&"v"in arg0){v=arg0.v;w=arg0.w;name=arg0.name;if(arguments.length===2){value=arguments[1];valueSpecified=true}}else{v=arg0;w=arguments[1];name=arguments[3];if(arguments.length>2){value=arguments[2];valueSpecified=true}}v=""+v;w=""+w;if(name!==undefined){name=""+name}var e=edgeArgsToId(this._isDirected,v,w,name);if(this._edgeLabels.hasOwnProperty(e)){if(valueSpecified){this._edgeLabels[e]=value}return this}if(name!==undefined&&!this._isMultigraph){throw new Error("Cannot set a named edge when isMultigraph = false")} | ||
| // It didn't exist, so we need to create it. | ||
| // First ensure the nodes exist. | ||
| this.setNode(v);this.setNode(w);this.#edgeLabels[e]=valueSpecified?value:this.#defaultEdgeLabelFn(v,w,name);var edgeObj=edgeArgsToObj(this.#isDirected,v,w,name); | ||
| this.setNode(v);this.setNode(w);this._edgeLabels[e]=valueSpecified?value:this._defaultEdgeLabelFn(v,w,name);var edgeObj=edgeArgsToObj(this._isDirected,v,w,name); | ||
| // Ensure we add undirected edges in a consistent way. | ||
| v=edgeObj.v;w=edgeObj.w;Object.freeze(edgeObj);this.#edgeObjs[e]=edgeObj;incrementOrInitEntry(this.#preds[w],v);incrementOrInitEntry(this.#sucs[v],w);this.#in[w][e]=edgeObj;this.#out[v][e]=edgeObj;this.#edgeCount++;return this} | ||
| v=edgeObj.v;w=edgeObj.w;Object.freeze(edgeObj);this._edgeObjs[e]=edgeObj;incrementOrInitEntry(this._preds[w],v);incrementOrInitEntry(this._sucs[v],w);this._in[w][e]=edgeObj;this._out[v][e]=edgeObj;this._edgeCount++;return this} | ||
| /** | ||
| * Gets the label for the specified edge. | ||
| * Complexity: O(1). | ||
| */edge(v,w,name){var e=arguments.length===1?edgeObjToId(this.#isDirected,arguments[0]):edgeArgsToId(this.#isDirected,v,w,name);return this.#edgeLabels[e]} | ||
| */edge(v,w,name){var e=arguments.length===1?edgeObjToId(this._isDirected,arguments[0]):edgeArgsToId(this._isDirected,v,w,name);return this._edgeLabels[e]} | ||
| /** | ||
@@ -284,7 +284,7 @@ * Gets the label for the specified edge and converts it to an object. | ||
| * Complexity: O(1). | ||
| */hasEdge(v,w,name){var e=arguments.length===1?edgeObjToId(this.#isDirected,arguments[0]):edgeArgsToId(this.#isDirected,v,w,name);return this.#edgeLabels.hasOwnProperty(e)} | ||
| */hasEdge(v,w,name){var e=arguments.length===1?edgeObjToId(this._isDirected,arguments[0]):edgeArgsToId(this._isDirected,v,w,name);return this._edgeLabels.hasOwnProperty(e)} | ||
| /** | ||
| * Removes the specified edge from the graph. No subgraphs are considered. | ||
| * Complexity: O(1). | ||
| */removeEdge(v,w,name){var e=arguments.length===1?edgeObjToId(this.#isDirected,arguments[0]):edgeArgsToId(this.#isDirected,v,w,name);var edge=this.#edgeObjs[e];if(edge){v=edge.v;w=edge.w;delete this.#edgeLabels[e];delete this.#edgeObjs[e];decrementOrRemoveEntry(this.#preds[w],v);decrementOrRemoveEntry(this.#sucs[v],w);delete this.#in[w][e];delete this.#out[v][e];this.#edgeCount--}return this} | ||
| */removeEdge(v,w,name){var e=arguments.length===1?edgeObjToId(this._isDirected,arguments[0]):edgeArgsToId(this._isDirected,v,w,name);var edge=this._edgeObjs[e];if(edge){v=edge.v;w=edge.w;delete this._edgeLabels[e];delete this._edgeObjs[e];decrementOrRemoveEntry(this._preds[w],v);decrementOrRemoveEntry(this._sucs[v],w);delete this._in[w][e];delete this._out[v][e];this._edgeCount--}return this} | ||
| /** | ||
@@ -294,3 +294,3 @@ * Return all edges that point to the node v. Optionally filters those edges down to just those | ||
| * Complexity: O(|E|). | ||
| */inEdges(v,u){var inV=this.#in[v];if(inV){var edges=Object.values(inV);if(!u){return edges}return edges.filter(edge=>edge.v===u)}} | ||
| */inEdges(v,u){var inV=this._in[v];if(inV){var edges=Object.values(inV);if(!u){return edges}return edges.filter(edge=>edge.v===u)}} | ||
| /** | ||
@@ -300,3 +300,3 @@ * Return all edges that are pointed at by node v. Optionally filters those edges down to just | ||
| * Complexity: O(|E|). | ||
| */outEdges(v,w){var outV=this.#out[v];if(outV){var edges=Object.values(outV);if(!w){return edges}return edges.filter(edge=>edge.w===w)}} | ||
| */outEdges(v,w){var outV=this._out[v];if(outV){var edges=Object.values(outV);if(!w){return edges}return edges.filter(edge=>edge.w===w)}} | ||
| /** | ||
@@ -322,2 +322,2 @@ * Returns all edges to or from node v regardless of direction. Optionally filters those edges | ||
| * // [ { v: 'a', w: 'b' } ] | ||
| */function read(json){var g=new Graph(json.options).setGraph(json.value);json.nodes.forEach(function(entry){g.setNode(entry.v,entry.value);if(entry.parent){g.setParent(entry.v,entry.parent)}});json.edges.forEach(function(entry){g.setEdge({v:entry.v,w:entry.w,name:entry.name},entry.value)});return g}},{"./graph":16}],19:[function(require,module,exports){module.exports="2.2.1"},{}]},{},[1])(1)}); | ||
| */function read(json){var g=new Graph(json.options).setGraph(json.value);json.nodes.forEach(function(entry){g.setNode(entry.v,entry.value);if(entry.parent){g.setParent(entry.v,entry.parent)}});json.edges.forEach(function(entry){g.setEdge({v:entry.v,w:entry.w,name:entry.name},entry.value)});return g}},{"./graph":16}],19:[function(require,module,exports){module.exports="2.2.2"},{}]},{},[1])(1)}); |
@@ -462,4 +462,4 @@ (function(f){if(typeof exports==="object"&&typeof module!=="undefined"){module.exports=f()}else if(typeof define==="function"&&define.amd){define([],f)}else{var g;if(typeof window!=="undefined"){g=window}else if(typeof global!=="undefined"){g=global}else if(typeof self!=="undefined"){g=self}else{g=this}g.graphlib = f()}})(function(){var define,module,exports;return (function(){function r(e,n,t){function o(i,f){if(!n[i]){if(!e[i]){var c="function"==typeof require&&require;if(!f&&c)return c(i,!0);if(u)return u(i,!0);var a=new Error("Cannot find module '"+i+"'");throw a.code="MODULE_NOT_FOUND",a}var p=n[i]={exports:{}};e[i][0].call(p.exports,function(r){var n=e[i][1][r];return o(n||r)},p,p.exports,r,e,n,t)}return n[i].exports}for(var u="function"==typeof require&&require,i=0;i<t.length;i++)o(t[i]);return o}return r})()({1:[function(require,module,exports){ | ||
| class PriorityQueue { | ||
| #arr = []; | ||
| #keyIndices = {}; | ||
| _arr = []; | ||
| _keyIndices = {}; | ||
@@ -470,3 +470,3 @@ /** | ||
| size() { | ||
| return this.#arr.length; | ||
| return this._arr.length; | ||
| } | ||
@@ -478,3 +478,3 @@ | ||
| keys() { | ||
| return this.#arr.map(function(x) { return x.key; }); | ||
| return this._arr.map(function(x) { return x.key; }); | ||
| } | ||
@@ -486,3 +486,3 @@ | ||
| has(key) { | ||
| return this.#keyIndices.hasOwnProperty(key); | ||
| return this._keyIndices.hasOwnProperty(key); | ||
| } | ||
@@ -497,5 +497,5 @@ | ||
| priority(key) { | ||
| var index = this.#keyIndices[key]; | ||
| var index = this._keyIndices[key]; | ||
| if (index !== undefined) { | ||
| return this.#arr[index].priority; | ||
| return this._arr[index].priority; | ||
| } | ||
@@ -512,3 +512,3 @@ } | ||
| } | ||
| return this.#arr[0].key; | ||
| return this._arr[0].key; | ||
| } | ||
@@ -525,10 +525,10 @@ | ||
| add(key, priority) { | ||
| var keyIndices = this.#keyIndices; | ||
| var keyIndices = this._keyIndices; | ||
| key = String(key); | ||
| if (!keyIndices.hasOwnProperty(key)) { | ||
| var arr = this.#arr; | ||
| var arr = this._arr; | ||
| var index = arr.length; | ||
| keyIndices[key] = index; | ||
| arr.push({key: key, priority: priority}); | ||
| this.#decrease(index); | ||
| this._decrease(index); | ||
| return true; | ||
@@ -543,6 +543,6 @@ } | ||
| removeMin() { | ||
| this.#swap(0, this.#arr.length - 1); | ||
| var min = this.#arr.pop(); | ||
| delete this.#keyIndices[min.key]; | ||
| this.#heapify(0); | ||
| this._swap(0, this._arr.length - 1); | ||
| var min = this._arr.pop(); | ||
| delete this._keyIndices[min.key]; | ||
| this._heapify(0); | ||
| return min.key; | ||
@@ -559,13 +559,13 @@ } | ||
| decrease(key, priority) { | ||
| var index = this.#keyIndices[key]; | ||
| if (priority > this.#arr[index].priority) { | ||
| var index = this._keyIndices[key]; | ||
| if (priority > this._arr[index].priority) { | ||
| throw new Error("New priority is greater than current priority. " + | ||
| "Key: " + key + " Old: " + this.#arr[index].priority + " New: " + priority); | ||
| "Key: " + key + " Old: " + this._arr[index].priority + " New: " + priority); | ||
| } | ||
| this.#arr[index].priority = priority; | ||
| this.#decrease(index); | ||
| this._arr[index].priority = priority; | ||
| this._decrease(index); | ||
| } | ||
| #heapify(i) { | ||
| var arr = this.#arr; | ||
| _heapify(i) { | ||
| var arr = this._arr; | ||
| var l = 2 * i; | ||
@@ -580,4 +580,4 @@ var r = l + 1; | ||
| if (largest !== i) { | ||
| this.#swap(i, largest); | ||
| this.#heapify(largest); | ||
| this._swap(i, largest); | ||
| this._heapify(largest); | ||
| } | ||
@@ -587,4 +587,4 @@ } | ||
| #decrease(index) { | ||
| var arr = this.#arr; | ||
| _decrease(index) { | ||
| var arr = this._arr; | ||
| var priority = arr[index].priority; | ||
@@ -597,3 +597,3 @@ var parent; | ||
| } | ||
| this.#swap(index, parent); | ||
| this._swap(index, parent); | ||
| index = parent; | ||
@@ -603,5 +603,5 @@ } | ||
| #swap(i, j) { | ||
| var arr = this.#arr; | ||
| var keyIndices = this.#keyIndices; | ||
| _swap(i, j) { | ||
| var arr = this._arr; | ||
| var keyIndices = this._keyIndices; | ||
| var origArrI = arr[i]; | ||
@@ -636,60 +636,60 @@ var origArrJ = arr[j]; | ||
| class Graph { | ||
| #isDirected = true; | ||
| #isMultigraph = false; | ||
| #isCompound = false; | ||
| _isDirected = true; | ||
| _isMultigraph = false; | ||
| _isCompound = false; | ||
| // Label for the graph itself | ||
| #label; | ||
| _label; | ||
| // Defaults to be set when creating a new node | ||
| #defaultNodeLabelFn = () => undefined; | ||
| _defaultNodeLabelFn = () => undefined; | ||
| // Defaults to be set when creating a new edge | ||
| #defaultEdgeLabelFn = () => undefined; | ||
| _defaultEdgeLabelFn = () => undefined; | ||
| // v -> label | ||
| #nodes = {}; | ||
| _nodes = {}; | ||
| // v -> edgeObj | ||
| #in = {}; | ||
| _in = {}; | ||
| // u -> v -> Number | ||
| #preds = {}; | ||
| _preds = {}; | ||
| // v -> edgeObj | ||
| #out = {}; | ||
| _out = {}; | ||
| // v -> w -> Number | ||
| #sucs = {}; | ||
| _sucs = {}; | ||
| // e -> edgeObj | ||
| #edgeObjs = {}; | ||
| _edgeObjs = {}; | ||
| // e -> label | ||
| #edgeLabels = {}; | ||
| _edgeLabels = {}; | ||
| /* Number of nodes in the graph. Should only be changed by the implementation. */ | ||
| #nodeCount = 0; | ||
| _nodeCount = 0; | ||
| /* Number of edges in the graph. Should only be changed by the implementation. */ | ||
| #edgeCount = 0; | ||
| _edgeCount = 0; | ||
| #parent; | ||
| _parent; | ||
| #children; | ||
| _children; | ||
| constructor(opts) { | ||
| if (opts) { | ||
| this.#isDirected = opts.hasOwnProperty("directed") ? opts.directed : true; | ||
| this.#isMultigraph = opts.hasOwnProperty("multigraph") ? opts.multigraph : false; | ||
| this.#isCompound = opts.hasOwnProperty("compound") ? opts.compound : false; | ||
| this._isDirected = opts.hasOwnProperty("directed") ? opts.directed : true; | ||
| this._isMultigraph = opts.hasOwnProperty("multigraph") ? opts.multigraph : false; | ||
| this._isCompound = opts.hasOwnProperty("compound") ? opts.compound : false; | ||
| } | ||
| if (this.#isCompound) { | ||
| if (this._isCompound) { | ||
| // v -> parent | ||
| this.#parent = {}; | ||
| this._parent = {}; | ||
| // v -> children | ||
| this.#children = {}; | ||
| this.#children[GRAPH_NODE] = {}; | ||
| this._children = {}; | ||
| this._children[GRAPH_NODE] = {}; | ||
| } | ||
@@ -704,3 +704,3 @@ } | ||
| isDirected() { | ||
| return this.#isDirected; | ||
| return this._isDirected; | ||
| } | ||
@@ -712,3 +712,3 @@ | ||
| isMultigraph() { | ||
| return this.#isMultigraph; | ||
| return this._isMultigraph; | ||
| } | ||
@@ -720,3 +720,3 @@ | ||
| isCompound() { | ||
| return this.#isCompound; | ||
| return this._isCompound; | ||
| } | ||
@@ -728,3 +728,3 @@ | ||
| setGraph(label) { | ||
| this.#label = label; | ||
| this._label = label; | ||
| return this; | ||
@@ -737,3 +737,3 @@ } | ||
| graph() { | ||
| return this.#label; | ||
| return this._label; | ||
| } | ||
@@ -752,5 +752,5 @@ | ||
| setDefaultNodeLabel(newDefault) { | ||
| this.#defaultNodeLabelFn = newDefault; | ||
| this._defaultNodeLabelFn = newDefault; | ||
| if (typeof newDefault !== 'function') { | ||
| this.#defaultNodeLabelFn = () => newDefault; | ||
| this._defaultNodeLabelFn = () => newDefault; | ||
| } | ||
@@ -766,3 +766,3 @@ | ||
| nodeCount() { | ||
| return this.#nodeCount; | ||
| return this._nodeCount; | ||
| } | ||
@@ -776,3 +776,3 @@ | ||
| nodes() { | ||
| return Object.keys(this.#nodes); | ||
| return Object.keys(this._nodes); | ||
| } | ||
@@ -786,3 +786,3 @@ | ||
| var self = this; | ||
| return this.nodes().filter(v => Object.keys(self.#in[v]).length === 0); | ||
| return this.nodes().filter(v => Object.keys(self._in[v]).length === 0); | ||
| } | ||
@@ -796,3 +796,3 @@ | ||
| var self = this; | ||
| return this.nodes().filter(v => Object.keys(self.#out[v]).length === 0); | ||
| return this.nodes().filter(v => Object.keys(self._out[v]).length === 0); | ||
| } | ||
@@ -824,5 +824,5 @@ | ||
| setNode(v, value) { | ||
| if (this.#nodes.hasOwnProperty(v)) { | ||
| if (this._nodes.hasOwnProperty(v)) { | ||
| if (arguments.length > 1) { | ||
| this.#nodes[v] = value; | ||
| this._nodes[v] = value; | ||
| } | ||
@@ -832,13 +832,13 @@ return this; | ||
| this.#nodes[v] = arguments.length > 1 ? value : this.#defaultNodeLabelFn(v); | ||
| if (this.#isCompound) { | ||
| this.#parent[v] = GRAPH_NODE; | ||
| this.#children[v] = {}; | ||
| this.#children[GRAPH_NODE][v] = true; | ||
| this._nodes[v] = arguments.length > 1 ? value : this._defaultNodeLabelFn(v); | ||
| if (this._isCompound) { | ||
| this._parent[v] = GRAPH_NODE; | ||
| this._children[v] = {}; | ||
| this._children[GRAPH_NODE][v] = true; | ||
| } | ||
| this.#in[v] = {}; | ||
| this.#preds[v] = {}; | ||
| this.#out[v] = {}; | ||
| this.#sucs[v] = {}; | ||
| ++this.#nodeCount; | ||
| this._in[v] = {}; | ||
| this._preds[v] = {}; | ||
| this._out[v] = {}; | ||
| this._sucs[v] = {}; | ||
| ++this._nodeCount; | ||
| return this; | ||
@@ -852,3 +852,3 @@ } | ||
| node(v) { | ||
| return this.#nodes[v]; | ||
| return this._nodes[v]; | ||
| } | ||
@@ -860,3 +860,3 @@ | ||
| hasNode(v) { | ||
| return this.#nodes.hasOwnProperty(v); | ||
| return this._nodes.hasOwnProperty(v); | ||
| } | ||
@@ -872,20 +872,20 @@ | ||
| var self = this; | ||
| if (this.#nodes.hasOwnProperty(v)) { | ||
| var removeEdge = e => self.removeEdge(self.#edgeObjs[e]); | ||
| delete this.#nodes[v]; | ||
| if (this.#isCompound) { | ||
| this.#removeFromParentsChildList(v); | ||
| delete this.#parent[v]; | ||
| if (this._nodes.hasOwnProperty(v)) { | ||
| var removeEdge = e => self.removeEdge(self._edgeObjs[e]); | ||
| delete this._nodes[v]; | ||
| if (this._isCompound) { | ||
| this._removeFromParentsChildList(v); | ||
| delete this._parent[v]; | ||
| this.children(v).forEach(function(child) { | ||
| self.setParent(child); | ||
| }); | ||
| delete this.#children[v]; | ||
| delete this._children[v]; | ||
| } | ||
| Object.keys(this.#in[v]).forEach(removeEdge); | ||
| delete this.#in[v]; | ||
| delete this.#preds[v]; | ||
| Object.keys(this.#out[v]).forEach(removeEdge); | ||
| delete this.#out[v]; | ||
| delete this.#sucs[v]; | ||
| --this.#nodeCount; | ||
| Object.keys(this._in[v]).forEach(removeEdge); | ||
| delete this._in[v]; | ||
| delete this._preds[v]; | ||
| Object.keys(this._out[v]).forEach(removeEdge); | ||
| delete this._out[v]; | ||
| delete this._sucs[v]; | ||
| --this._nodeCount; | ||
| } | ||
@@ -902,3 +902,3 @@ return this; | ||
| setParent(v, parent) { | ||
| if (!this.#isCompound) { | ||
| if (!this._isCompound) { | ||
| throw new Error("Cannot set parent in a non-compound graph"); | ||
@@ -923,10 +923,10 @@ } | ||
| this.setNode(v); | ||
| this.#removeFromParentsChildList(v); | ||
| this.#parent[v] = parent; | ||
| this.#children[parent][v] = true; | ||
| this._removeFromParentsChildList(v); | ||
| this._parent[v] = parent; | ||
| this._children[parent][v] = true; | ||
| return this; | ||
| } | ||
| #removeFromParentsChildList(v) { | ||
| delete this.#children[this.#parent[v]][v]; | ||
| _removeFromParentsChildList(v) { | ||
| delete this._children[this._parent[v]][v]; | ||
| } | ||
@@ -939,4 +939,4 @@ | ||
| parent(v) { | ||
| if (this.#isCompound) { | ||
| var parent = this.#parent[v]; | ||
| if (this._isCompound) { | ||
| var parent = this._parent[v]; | ||
| if (parent !== GRAPH_NODE) { | ||
@@ -953,4 +953,4 @@ return parent; | ||
| children(v = GRAPH_NODE) { | ||
| if (this.#isCompound) { | ||
| var children = this.#children[v]; | ||
| if (this._isCompound) { | ||
| var children = this._children[v]; | ||
| if (children) { | ||
@@ -972,3 +972,3 @@ return Object.keys(children); | ||
| predecessors(v) { | ||
| var predsV = this.#preds[v]; | ||
| var predsV = this._preds[v]; | ||
| if (predsV) { | ||
@@ -985,3 +985,3 @@ return Object.keys(predsV); | ||
| successors(v) { | ||
| var sucsV = this.#sucs[v]; | ||
| var sucsV = this._sucs[v]; | ||
| if (sucsV) { | ||
@@ -1027,5 +1027,5 @@ return Object.keys(sucsV); | ||
| var copy = new this.constructor({ | ||
| directed: this.#isDirected, | ||
| multigraph: this.#isMultigraph, | ||
| compound: this.#isCompound | ||
| directed: this._isDirected, | ||
| multigraph: this._isMultigraph, | ||
| compound: this._isCompound | ||
| }); | ||
@@ -1036,3 +1036,3 @@ | ||
| var self = this; | ||
| Object.entries(this.#nodes).forEach(function([v, value]) { | ||
| Object.entries(this._nodes).forEach(function([v, value]) { | ||
| if (filter(v)) { | ||
@@ -1043,3 +1043,3 @@ copy.setNode(v, value); | ||
| Object.values(this.#edgeObjs).forEach(function(e) { | ||
| Object.values(this._edgeObjs).forEach(function(e) { | ||
| if (copy.hasNode(e.v) && copy.hasNode(e.w)) { | ||
@@ -1063,3 +1063,3 @@ copy.setEdge(e, self.edge(e)); | ||
| if (this.#isCompound) { | ||
| if (this._isCompound) { | ||
| copy.nodes().forEach(v => copy.setParent(v, findParent(v))); | ||
@@ -1081,5 +1081,5 @@ } | ||
| setDefaultEdgeLabel(newDefault) { | ||
| this.#defaultEdgeLabelFn = newDefault; | ||
| this._defaultEdgeLabelFn = newDefault; | ||
| if (typeof newDefault !== 'function') { | ||
| this.#defaultEdgeLabelFn = () => newDefault; | ||
| this._defaultEdgeLabelFn = () => newDefault; | ||
| } | ||
@@ -1095,3 +1095,3 @@ | ||
| edgeCount() { | ||
| return this.#edgeCount; | ||
| return this._edgeCount; | ||
| } | ||
@@ -1104,3 +1104,3 @@ | ||
| edges() { | ||
| return Object.values(this.#edgeObjs); | ||
| return Object.values(this._edgeObjs); | ||
| } | ||
@@ -1163,6 +1163,6 @@ | ||
| var e = edgeArgsToId(this.#isDirected, v, w, name); | ||
| if (this.#edgeLabels.hasOwnProperty(e)) { | ||
| var e = edgeArgsToId(this._isDirected, v, w, name); | ||
| if (this._edgeLabels.hasOwnProperty(e)) { | ||
| if (valueSpecified) { | ||
| this.#edgeLabels[e] = value; | ||
| this._edgeLabels[e] = value; | ||
| } | ||
@@ -1172,3 +1172,3 @@ return this; | ||
| if (name !== undefined && !this.#isMultigraph) { | ||
| if (name !== undefined && !this._isMultigraph) { | ||
| throw new Error("Cannot set a named edge when isMultigraph = false"); | ||
@@ -1182,5 +1182,5 @@ } | ||
| this.#edgeLabels[e] = valueSpecified ? value : this.#defaultEdgeLabelFn(v, w, name); | ||
| this._edgeLabels[e] = valueSpecified ? value : this._defaultEdgeLabelFn(v, w, name); | ||
| var edgeObj = edgeArgsToObj(this.#isDirected, v, w, name); | ||
| var edgeObj = edgeArgsToObj(this._isDirected, v, w, name); | ||
| // Ensure we add undirected edges in a consistent way. | ||
@@ -1191,8 +1191,8 @@ v = edgeObj.v; | ||
| Object.freeze(edgeObj); | ||
| this.#edgeObjs[e] = edgeObj; | ||
| incrementOrInitEntry(this.#preds[w], v); | ||
| incrementOrInitEntry(this.#sucs[v], w); | ||
| this.#in[w][e] = edgeObj; | ||
| this.#out[v][e] = edgeObj; | ||
| this.#edgeCount++; | ||
| this._edgeObjs[e] = edgeObj; | ||
| incrementOrInitEntry(this._preds[w], v); | ||
| incrementOrInitEntry(this._sucs[v], w); | ||
| this._in[w][e] = edgeObj; | ||
| this._out[v][e] = edgeObj; | ||
| this._edgeCount++; | ||
| return this; | ||
@@ -1207,5 +1207,5 @@ } | ||
| var e = (arguments.length === 1 | ||
| ? edgeObjToId(this.#isDirected, arguments[0]) | ||
| : edgeArgsToId(this.#isDirected, v, w, name)); | ||
| return this.#edgeLabels[e]; | ||
| ? edgeObjToId(this._isDirected, arguments[0]) | ||
| : edgeArgsToId(this._isDirected, v, w, name)); | ||
| return this._edgeLabels[e]; | ||
| } | ||
@@ -1232,5 +1232,5 @@ | ||
| var e = (arguments.length === 1 | ||
| ? edgeObjToId(this.#isDirected, arguments[0]) | ||
| : edgeArgsToId(this.#isDirected, v, w, name)); | ||
| return this.#edgeLabels.hasOwnProperty(e); | ||
| ? edgeObjToId(this._isDirected, arguments[0]) | ||
| : edgeArgsToId(this._isDirected, v, w, name)); | ||
| return this._edgeLabels.hasOwnProperty(e); | ||
| } | ||
@@ -1244,15 +1244,15 @@ | ||
| var e = (arguments.length === 1 | ||
| ? edgeObjToId(this.#isDirected, arguments[0]) | ||
| : edgeArgsToId(this.#isDirected, v, w, name)); | ||
| var edge = this.#edgeObjs[e]; | ||
| ? edgeObjToId(this._isDirected, arguments[0]) | ||
| : edgeArgsToId(this._isDirected, v, w, name)); | ||
| var edge = this._edgeObjs[e]; | ||
| if (edge) { | ||
| v = edge.v; | ||
| w = edge.w; | ||
| delete this.#edgeLabels[e]; | ||
| delete this.#edgeObjs[e]; | ||
| decrementOrRemoveEntry(this.#preds[w], v); | ||
| decrementOrRemoveEntry(this.#sucs[v], w); | ||
| delete this.#in[w][e]; | ||
| delete this.#out[v][e]; | ||
| this.#edgeCount--; | ||
| delete this._edgeLabels[e]; | ||
| delete this._edgeObjs[e]; | ||
| decrementOrRemoveEntry(this._preds[w], v); | ||
| decrementOrRemoveEntry(this._sucs[v], w); | ||
| delete this._in[w][e]; | ||
| delete this._out[v][e]; | ||
| this._edgeCount--; | ||
| } | ||
@@ -1268,3 +1268,3 @@ return this; | ||
| inEdges(v, u) { | ||
| var inV = this.#in[v]; | ||
| var inV = this._in[v]; | ||
| if (inV) { | ||
@@ -1285,3 +1285,3 @@ var edges = Object.values(inV); | ||
| outEdges(v, w) { | ||
| var outV = this.#out[v]; | ||
| var outV = this._out[v]; | ||
| if (outV) { | ||
@@ -1444,5 +1444,5 @@ var edges = Object.values(outV); | ||
| },{"./graph":16}],19:[function(require,module,exports){ | ||
| module.exports = '2.2.1'; | ||
| module.exports = '2.2.2'; | ||
| },{}]},{},[1])(1) | ||
| }); |
@@ -50,12 +50,12 @@ (function(f){if(typeof exports==="object"&&typeof module!=="undefined"){module.exports=f()}else if(typeof define==="function"&&define.amd){define([],f)}else{var g;if(typeof window!=="undefined"){g=window}else if(typeof global!=="undefined"){g=global}else if(typeof self!=="undefined"){g=self}else{g=this}g.graphlib=f()}})(function(){var define,module,exports;return function(){function r(e,n,t){function o(i,f){if(!n[i]){if(!e[i]){var c="function"==typeof require&&require;if(!f&&c)return c(i,!0);if(u)return u(i,!0);var a=new Error("Cannot find module '"+i+"'");throw a.code="MODULE_NOT_FOUND",a}var p=n[i]={exports:{}};e[i][0].call(p.exports,function(r){var n=e[i][1][r];return o(n||r)},p,p.exports,r,e,n,t)}return n[i].exports}for(var u="function"==typeof require&&require,i=0;i<t.length;i++)o(t[i]);return o}return r}()({1:[function(require,module,exports){ | ||
| */ | ||
| class PriorityQueue{#arr=[];#keyIndices={}; | ||
| class PriorityQueue{_arr=[];_keyIndices={}; | ||
| /** | ||
| * Returns the number of elements in the queue. Takes `O(1)` time. | ||
| */size(){return this.#arr.length} | ||
| */size(){return this._arr.length} | ||
| /** | ||
| * Returns the keys that are in the queue. Takes `O(n)` time. | ||
| */keys(){return this.#arr.map(function(x){return x.key})} | ||
| */keys(){return this._arr.map(function(x){return x.key})} | ||
| /** | ||
| * Returns `true` if **key** is in the queue and `false` if not. | ||
| */has(key){return this.#keyIndices.hasOwnProperty(key)} | ||
| */has(key){return this._keyIndices.hasOwnProperty(key)} | ||
| /** | ||
@@ -66,7 +66,7 @@ * Returns the priority for **key**. If **key** is not present in the queue | ||
| * @param {Object} key | ||
| */priority(key){var index=this.#keyIndices[key];if(index!==undefined){return this.#arr[index].priority}} | ||
| */priority(key){var index=this._keyIndices[key];if(index!==undefined){return this._arr[index].priority}} | ||
| /** | ||
| * Returns the key for the minimum element in this queue. If the queue is | ||
| * empty this function throws an Error. Takes `O(1)` time. | ||
| */min(){if(this.size()===0){throw new Error("Queue underflow")}return this.#arr[0].key} | ||
| */min(){if(this.size()===0){throw new Error("Queue underflow")}return this._arr[0].key} | ||
| /** | ||
@@ -79,6 +79,6 @@ * Inserts a new key into the priority queue. If the key already exists in | ||
| * @param {Number} priority the initial priority for the key | ||
| */add(key,priority){var keyIndices=this.#keyIndices;key=String(key);if(!keyIndices.hasOwnProperty(key)){var arr=this.#arr;var index=arr.length;keyIndices[key]=index;arr.push({key:key,priority:priority});this.#decrease(index);return true}return false} | ||
| */add(key,priority){var keyIndices=this._keyIndices;key=String(key);if(!keyIndices.hasOwnProperty(key)){var arr=this._arr;var index=arr.length;keyIndices[key]=index;arr.push({key:key,priority:priority});this._decrease(index);return true}return false} | ||
| /** | ||
| * Removes and returns the smallest key in the queue. Takes `O(log n)` time. | ||
| */removeMin(){this.#swap(0,this.#arr.length-1);var min=this.#arr.pop();delete this.#keyIndices[min.key];this.#heapify(0);return min.key} | ||
| */removeMin(){this._swap(0,this._arr.length-1);var min=this._arr.pop();delete this._keyIndices[min.key];this._heapify(0);return min.key} | ||
| /** | ||
@@ -90,3 +90,3 @@ * Decreases the priority for **key** to **priority**. If the new priority is | ||
| * @param {Number} priority the new priority for the key | ||
| */decrease(key,priority){var index=this.#keyIndices[key];if(priority>this.#arr[index].priority){throw new Error("New priority is greater than current priority. "+"Key: "+key+" Old: "+this.#arr[index].priority+" New: "+priority)}this.#arr[index].priority=priority;this.#decrease(index)}#heapify(i){var arr=this.#arr;var l=2*i;var r=l+1;var largest=i;if(l<arr.length){largest=arr[l].priority<arr[largest].priority?l:largest;if(r<arr.length){largest=arr[r].priority<arr[largest].priority?r:largest}if(largest!==i){this.#swap(i,largest);this.#heapify(largest)}}}#decrease(index){var arr=this.#arr;var priority=arr[index].priority;var parent;while(index!==0){parent=index>>1;if(arr[parent].priority<priority){break}this.#swap(index,parent);index=parent}}#swap(i,j){var arr=this.#arr;var keyIndices=this.#keyIndices;var origArrI=arr[i];var origArrJ=arr[j];arr[i]=origArrJ;arr[j]=origArrI;keyIndices[origArrJ.key]=i;keyIndices[origArrI.key]=j}}module.exports=PriorityQueue},{}],16:[function(require,module,exports){"use strict";var DEFAULT_EDGE_NAME="\0";var GRAPH_NODE="\0";var EDGE_KEY_DELIM=""; | ||
| */decrease(key,priority){var index=this._keyIndices[key];if(priority>this._arr[index].priority){throw new Error("New priority is greater than current priority. "+"Key: "+key+" Old: "+this._arr[index].priority+" New: "+priority)}this._arr[index].priority=priority;this._decrease(index)}_heapify(i){var arr=this._arr;var l=2*i;var r=l+1;var largest=i;if(l<arr.length){largest=arr[l].priority<arr[largest].priority?l:largest;if(r<arr.length){largest=arr[r].priority<arr[largest].priority?r:largest}if(largest!==i){this._swap(i,largest);this._heapify(largest)}}}_decrease(index){var arr=this._arr;var priority=arr[index].priority;var parent;while(index!==0){parent=index>>1;if(arr[parent].priority<priority){break}this._swap(index,parent);index=parent}}_swap(i,j){var arr=this._arr;var keyIndices=this._keyIndices;var origArrI=arr[i];var origArrJ=arr[j];arr[i]=origArrJ;arr[j]=origArrI;keyIndices[origArrJ.key]=i;keyIndices[origArrI.key]=j}}module.exports=PriorityQueue},{}],16:[function(require,module,exports){"use strict";var DEFAULT_EDGE_NAME="\0";var GRAPH_NODE="\0";var EDGE_KEY_DELIM=""; | ||
| // Implementation notes: | ||
@@ -101,45 +101,45 @@ // | ||
| // we're going to get to a performant hashtable in JavaScript. | ||
| class Graph{#isDirected=true;#isMultigraph=false;#isCompound=false; | ||
| class Graph{_isDirected=true;_isMultigraph=false;_isCompound=false; | ||
| // Label for the graph itself | ||
| #label; | ||
| _label; | ||
| // Defaults to be set when creating a new node | ||
| #defaultNodeLabelFn=()=>undefined; | ||
| _defaultNodeLabelFn=()=>undefined; | ||
| // Defaults to be set when creating a new edge | ||
| #defaultEdgeLabelFn=()=>undefined; | ||
| _defaultEdgeLabelFn=()=>undefined; | ||
| // v -> label | ||
| #nodes={}; | ||
| _nodes={}; | ||
| // v -> edgeObj | ||
| #in={}; | ||
| _in={}; | ||
| // u -> v -> Number | ||
| #preds={}; | ||
| _preds={}; | ||
| // v -> edgeObj | ||
| #out={}; | ||
| _out={}; | ||
| // v -> w -> Number | ||
| #sucs={}; | ||
| _sucs={}; | ||
| // e -> edgeObj | ||
| #edgeObjs={}; | ||
| _edgeObjs={}; | ||
| // e -> label | ||
| #edgeLabels={}; | ||
| /* Number of nodes in the graph. Should only be changed by the implementation. */#nodeCount=0; | ||
| /* Number of edges in the graph. Should only be changed by the implementation. */#edgeCount=0;#parent;#children;constructor(opts){if(opts){this.#isDirected=opts.hasOwnProperty("directed")?opts.directed:true;this.#isMultigraph=opts.hasOwnProperty("multigraph")?opts.multigraph:false;this.#isCompound=opts.hasOwnProperty("compound")?opts.compound:false}if(this.#isCompound){ | ||
| _edgeLabels={}; | ||
| /* Number of nodes in the graph. Should only be changed by the implementation. */_nodeCount=0; | ||
| /* Number of edges in the graph. Should only be changed by the implementation. */_edgeCount=0;_parent;_children;constructor(opts){if(opts){this._isDirected=opts.hasOwnProperty("directed")?opts.directed:true;this._isMultigraph=opts.hasOwnProperty("multigraph")?opts.multigraph:false;this._isCompound=opts.hasOwnProperty("compound")?opts.compound:false}if(this._isCompound){ | ||
| // v -> parent | ||
| this.#parent={}; | ||
| this._parent={}; | ||
| // v -> children | ||
| this.#children={};this.#children[GRAPH_NODE]={}}} | ||
| this._children={};this._children[GRAPH_NODE]={}}} | ||
| /* === Graph functions ========= */ | ||
| /** | ||
| * Whether graph was created with 'directed' flag set to true or not. | ||
| */isDirected(){return this.#isDirected} | ||
| */isDirected(){return this._isDirected} | ||
| /** | ||
| * Whether graph was created with 'multigraph' flag set to true or not. | ||
| */isMultigraph(){return this.#isMultigraph} | ||
| */isMultigraph(){return this._isMultigraph} | ||
| /** | ||
| * Whether graph was created with 'compound' flag set to true or not. | ||
| */isCompound(){return this.#isCompound} | ||
| */isCompound(){return this._isCompound} | ||
| /** | ||
| * Sets the label of the graph. | ||
| */setGraph(label){this.#label=label;return this} | ||
| */setGraph(label){this._label=label;return this} | ||
| /** | ||
| * Gets the graph label. | ||
| */graph(){return this.#label} | ||
| */graph(){return this._label} | ||
| /* === Node functions ========== */ | ||
@@ -152,7 +152,7 @@ /** | ||
| * Complexity: O(1). | ||
| */setDefaultNodeLabel(newDefault){this.#defaultNodeLabelFn=newDefault;if(typeof newDefault!=="function"){this.#defaultNodeLabelFn=()=>newDefault}return this} | ||
| */setDefaultNodeLabel(newDefault){this._defaultNodeLabelFn=newDefault;if(typeof newDefault!=="function"){this._defaultNodeLabelFn=()=>newDefault}return this} | ||
| /** | ||
| * Gets the number of nodes in the graph. | ||
| * Complexity: O(1). | ||
| */nodeCount(){return this.#nodeCount} | ||
| */nodeCount(){return this._nodeCount} | ||
| /** | ||
@@ -162,11 +162,11 @@ * Gets all nodes of the graph. Note, the in case of compound graph subnodes are | ||
| * Complexity: O(1). | ||
| */nodes(){return Object.keys(this.#nodes)} | ||
| */nodes(){return Object.keys(this._nodes)} | ||
| /** | ||
| * Gets list of nodes without in-edges. | ||
| * Complexity: O(|V|). | ||
| */sources(){var self=this;return this.nodes().filter(v=>Object.keys(self.#in[v]).length===0)} | ||
| */sources(){var self=this;return this.nodes().filter(v=>Object.keys(self._in[v]).length===0)} | ||
| /** | ||
| * Gets list of nodes without out-edges. | ||
| * Complexity: O(|V|). | ||
| */sinks(){var self=this;return this.nodes().filter(v=>Object.keys(self.#out[v]).length===0)} | ||
| */sinks(){var self=this;return this.nodes().filter(v=>Object.keys(self._out[v]).length===0)} | ||
| /** | ||
@@ -181,10 +181,10 @@ * Invokes setNode method for each node in names list. | ||
| * Complexity: O(1). | ||
| */setNode(v,value){if(this.#nodes.hasOwnProperty(v)){if(arguments.length>1){this.#nodes[v]=value}return this}this.#nodes[v]=arguments.length>1?value:this.#defaultNodeLabelFn(v);if(this.#isCompound){this.#parent[v]=GRAPH_NODE;this.#children[v]={};this.#children[GRAPH_NODE][v]=true}this.#in[v]={};this.#preds[v]={};this.#out[v]={};this.#sucs[v]={};++this.#nodeCount;return this} | ||
| */setNode(v,value){if(this._nodes.hasOwnProperty(v)){if(arguments.length>1){this._nodes[v]=value}return this}this._nodes[v]=arguments.length>1?value:this._defaultNodeLabelFn(v);if(this._isCompound){this._parent[v]=GRAPH_NODE;this._children[v]={};this._children[GRAPH_NODE][v]=true}this._in[v]={};this._preds[v]={};this._out[v]={};this._sucs[v]={};++this._nodeCount;return this} | ||
| /** | ||
| * Gets the label of node with specified name. | ||
| * Complexity: O(|V|). | ||
| */node(v){return this.#nodes[v]} | ||
| */node(v){return this._nodes[v]} | ||
| /** | ||
| * Detects whether graph has a node with specified name or not. | ||
| */hasNode(v){return this.#nodes.hasOwnProperty(v)} | ||
| */hasNode(v){return this._nodes.hasOwnProperty(v)} | ||
| /** | ||
@@ -195,3 +195,3 @@ * Remove the node with the name from the graph or do nothing if the node is not in | ||
| * Complexity: O(1). | ||
| */removeNode(v){var self=this;if(this.#nodes.hasOwnProperty(v)){var removeEdge=e=>self.removeEdge(self.#edgeObjs[e]);delete this.#nodes[v];if(this.#isCompound){this.#removeFromParentsChildList(v);delete this.#parent[v];this.children(v).forEach(function(child){self.setParent(child)});delete this.#children[v]}Object.keys(this.#in[v]).forEach(removeEdge);delete this.#in[v];delete this.#preds[v];Object.keys(this.#out[v]).forEach(removeEdge);delete this.#out[v];delete this.#sucs[v];--this.#nodeCount}return this} | ||
| */removeNode(v){var self=this;if(this._nodes.hasOwnProperty(v)){var removeEdge=e=>self.removeEdge(self._edgeObjs[e]);delete this._nodes[v];if(this._isCompound){this._removeFromParentsChildList(v);delete this._parent[v];this.children(v).forEach(function(child){self.setParent(child)});delete this._children[v]}Object.keys(this._in[v]).forEach(removeEdge);delete this._in[v];delete this._preds[v];Object.keys(this._out[v]).forEach(removeEdge);delete this._out[v];delete this._sucs[v];--this._nodeCount}return this} | ||
| /** | ||
@@ -202,13 +202,13 @@ * Sets node p as a parent for node v if it is defined, or removes the | ||
| * Average-case complexity: O(1). | ||
| */setParent(v,parent){if(!this.#isCompound){throw new Error("Cannot set parent in a non-compound graph")}if(parent===undefined){parent=GRAPH_NODE}else{ | ||
| */setParent(v,parent){if(!this._isCompound){throw new Error("Cannot set parent in a non-compound graph")}if(parent===undefined){parent=GRAPH_NODE}else{ | ||
| // Coerce parent to string | ||
| parent+="";for(var ancestor=parent;ancestor!==undefined;ancestor=this.parent(ancestor)){if(ancestor===v){throw new Error("Setting "+parent+" as parent of "+v+" would create a cycle")}}this.setNode(parent)}this.setNode(v);this.#removeFromParentsChildList(v);this.#parent[v]=parent;this.#children[parent][v]=true;return this}#removeFromParentsChildList(v){delete this.#children[this.#parent[v]][v]} | ||
| parent+="";for(var ancestor=parent;ancestor!==undefined;ancestor=this.parent(ancestor)){if(ancestor===v){throw new Error("Setting "+parent+" as parent of "+v+" would create a cycle")}}this.setNode(parent)}this.setNode(v);this._removeFromParentsChildList(v);this._parent[v]=parent;this._children[parent][v]=true;return this}_removeFromParentsChildList(v){delete this._children[this._parent[v]][v]} | ||
| /** | ||
| * Gets parent node for node v. | ||
| * Complexity: O(1). | ||
| */parent(v){if(this.#isCompound){var parent=this.#parent[v];if(parent!==GRAPH_NODE){return parent}}} | ||
| */parent(v){if(this._isCompound){var parent=this._parent[v];if(parent!==GRAPH_NODE){return parent}}} | ||
| /** | ||
| * Gets list of direct children of node v. | ||
| * Complexity: O(1). | ||
| */children(v=GRAPH_NODE){if(this.#isCompound){var children=this.#children[v];if(children){return Object.keys(children)}}else if(v===GRAPH_NODE){return this.nodes()}else if(this.hasNode(v)){return[]}} | ||
| */children(v=GRAPH_NODE){if(this._isCompound){var children=this._children[v];if(children){return Object.keys(children)}}else if(v===GRAPH_NODE){return this.nodes()}else if(this.hasNode(v)){return[]}} | ||
| /** | ||
@@ -218,3 +218,3 @@ * Return all nodes that are predecessors of the specified node or undefined if node v is not in | ||
| * Complexity: O(|V|). | ||
| */predecessors(v){var predsV=this.#preds[v];if(predsV){return Object.keys(predsV)}} | ||
| */predecessors(v){var predsV=this._preds[v];if(predsV){return Object.keys(predsV)}} | ||
| /** | ||
@@ -224,3 +224,3 @@ * Return all nodes that are successors of the specified node or undefined if node v is not in | ||
| * Complexity: O(|V|). | ||
| */successors(v){var sucsV=this.#sucs[v];if(sucsV){return Object.keys(sucsV)}} | ||
| */successors(v){var sucsV=this._sucs[v];if(sucsV){return Object.keys(sucsV)}} | ||
| /** | ||
@@ -236,3 +236,3 @@ * Return all nodes that are predecessors or successors of the specified node or undefined if | ||
| * Average-case complexity: O(|E|+|V|). | ||
| */filterNodes(filter){var copy=new this.constructor({directed:this.#isDirected,multigraph:this.#isMultigraph,compound:this.#isCompound});copy.setGraph(this.graph());var self=this;Object.entries(this.#nodes).forEach(function([v,value]){if(filter(v)){copy.setNode(v,value)}});Object.values(this.#edgeObjs).forEach(function(e){if(copy.hasNode(e.v)&©.hasNode(e.w)){copy.setEdge(e,self.edge(e))}});var parents={};function findParent(v){var parent=self.parent(v);if(parent===undefined||copy.hasNode(parent)){parents[v]=parent;return parent}else if(parent in parents){return parents[parent]}else{return findParent(parent)}}if(this.#isCompound){copy.nodes().forEach(v=>copy.setParent(v,findParent(v)))}return copy} | ||
| */filterNodes(filter){var copy=new this.constructor({directed:this._isDirected,multigraph:this._isMultigraph,compound:this._isCompound});copy.setGraph(this.graph());var self=this;Object.entries(this._nodes).forEach(function([v,value]){if(filter(v)){copy.setNode(v,value)}});Object.values(this._edgeObjs).forEach(function(e){if(copy.hasNode(e.v)&©.hasNode(e.w)){copy.setEdge(e,self.edge(e))}});var parents={};function findParent(v){var parent=self.parent(v);if(parent===undefined||copy.hasNode(parent)){parents[v]=parent;return parent}else if(parent in parents){return parents[parent]}else{return findParent(parent)}}if(this._isCompound){copy.nodes().forEach(v=>copy.setParent(v,findParent(v)))}return copy} | ||
| /* === Edge functions ========== */ | ||
@@ -245,11 +245,11 @@ /** | ||
| * Complexity: O(1). | ||
| */setDefaultEdgeLabel(newDefault){this.#defaultEdgeLabelFn=newDefault;if(typeof newDefault!=="function"){this.#defaultEdgeLabelFn=()=>newDefault}return this} | ||
| */setDefaultEdgeLabel(newDefault){this._defaultEdgeLabelFn=newDefault;if(typeof newDefault!=="function"){this._defaultEdgeLabelFn=()=>newDefault}return this} | ||
| /** | ||
| * Gets the number of edges in the graph. | ||
| * Complexity: O(1). | ||
| */edgeCount(){return this.#edgeCount} | ||
| */edgeCount(){return this._edgeCount} | ||
| /** | ||
| * Gets edges of the graph. In case of compound graph subgraphs are not considered. | ||
| * Complexity: O(|E|). | ||
| */edges(){return Object.values(this.#edgeObjs)} | ||
| */edges(){return Object.values(this._edgeObjs)} | ||
| /** | ||
@@ -266,12 +266,12 @@ * Establish an edges path over the nodes in nodes list. If some edge is already | ||
| * be assigned. The name parameter is only useful with multigraphs. | ||
| */setEdge(){var v,w,name,value;var valueSpecified=false;var arg0=arguments[0];if(typeof arg0==="object"&&arg0!==null&&"v"in arg0){v=arg0.v;w=arg0.w;name=arg0.name;if(arguments.length===2){value=arguments[1];valueSpecified=true}}else{v=arg0;w=arguments[1];name=arguments[3];if(arguments.length>2){value=arguments[2];valueSpecified=true}}v=""+v;w=""+w;if(name!==undefined){name=""+name}var e=edgeArgsToId(this.#isDirected,v,w,name);if(this.#edgeLabels.hasOwnProperty(e)){if(valueSpecified){this.#edgeLabels[e]=value}return this}if(name!==undefined&&!this.#isMultigraph){throw new Error("Cannot set a named edge when isMultigraph = false")} | ||
| */setEdge(){var v,w,name,value;var valueSpecified=false;var arg0=arguments[0];if(typeof arg0==="object"&&arg0!==null&&"v"in arg0){v=arg0.v;w=arg0.w;name=arg0.name;if(arguments.length===2){value=arguments[1];valueSpecified=true}}else{v=arg0;w=arguments[1];name=arguments[3];if(arguments.length>2){value=arguments[2];valueSpecified=true}}v=""+v;w=""+w;if(name!==undefined){name=""+name}var e=edgeArgsToId(this._isDirected,v,w,name);if(this._edgeLabels.hasOwnProperty(e)){if(valueSpecified){this._edgeLabels[e]=value}return this}if(name!==undefined&&!this._isMultigraph){throw new Error("Cannot set a named edge when isMultigraph = false")} | ||
| // It didn't exist, so we need to create it. | ||
| // First ensure the nodes exist. | ||
| this.setNode(v);this.setNode(w);this.#edgeLabels[e]=valueSpecified?value:this.#defaultEdgeLabelFn(v,w,name);var edgeObj=edgeArgsToObj(this.#isDirected,v,w,name); | ||
| this.setNode(v);this.setNode(w);this._edgeLabels[e]=valueSpecified?value:this._defaultEdgeLabelFn(v,w,name);var edgeObj=edgeArgsToObj(this._isDirected,v,w,name); | ||
| // Ensure we add undirected edges in a consistent way. | ||
| v=edgeObj.v;w=edgeObj.w;Object.freeze(edgeObj);this.#edgeObjs[e]=edgeObj;incrementOrInitEntry(this.#preds[w],v);incrementOrInitEntry(this.#sucs[v],w);this.#in[w][e]=edgeObj;this.#out[v][e]=edgeObj;this.#edgeCount++;return this} | ||
| v=edgeObj.v;w=edgeObj.w;Object.freeze(edgeObj);this._edgeObjs[e]=edgeObj;incrementOrInitEntry(this._preds[w],v);incrementOrInitEntry(this._sucs[v],w);this._in[w][e]=edgeObj;this._out[v][e]=edgeObj;this._edgeCount++;return this} | ||
| /** | ||
| * Gets the label for the specified edge. | ||
| * Complexity: O(1). | ||
| */edge(v,w,name){var e=arguments.length===1?edgeObjToId(this.#isDirected,arguments[0]):edgeArgsToId(this.#isDirected,v,w,name);return this.#edgeLabels[e]} | ||
| */edge(v,w,name){var e=arguments.length===1?edgeObjToId(this._isDirected,arguments[0]):edgeArgsToId(this._isDirected,v,w,name);return this._edgeLabels[e]} | ||
| /** | ||
@@ -284,7 +284,7 @@ * Gets the label for the specified edge and converts it to an object. | ||
| * Complexity: O(1). | ||
| */hasEdge(v,w,name){var e=arguments.length===1?edgeObjToId(this.#isDirected,arguments[0]):edgeArgsToId(this.#isDirected,v,w,name);return this.#edgeLabels.hasOwnProperty(e)} | ||
| */hasEdge(v,w,name){var e=arguments.length===1?edgeObjToId(this._isDirected,arguments[0]):edgeArgsToId(this._isDirected,v,w,name);return this._edgeLabels.hasOwnProperty(e)} | ||
| /** | ||
| * Removes the specified edge from the graph. No subgraphs are considered. | ||
| * Complexity: O(1). | ||
| */removeEdge(v,w,name){var e=arguments.length===1?edgeObjToId(this.#isDirected,arguments[0]):edgeArgsToId(this.#isDirected,v,w,name);var edge=this.#edgeObjs[e];if(edge){v=edge.v;w=edge.w;delete this.#edgeLabels[e];delete this.#edgeObjs[e];decrementOrRemoveEntry(this.#preds[w],v);decrementOrRemoveEntry(this.#sucs[v],w);delete this.#in[w][e];delete this.#out[v][e];this.#edgeCount--}return this} | ||
| */removeEdge(v,w,name){var e=arguments.length===1?edgeObjToId(this._isDirected,arguments[0]):edgeArgsToId(this._isDirected,v,w,name);var edge=this._edgeObjs[e];if(edge){v=edge.v;w=edge.w;delete this._edgeLabels[e];delete this._edgeObjs[e];decrementOrRemoveEntry(this._preds[w],v);decrementOrRemoveEntry(this._sucs[v],w);delete this._in[w][e];delete this._out[v][e];this._edgeCount--}return this} | ||
| /** | ||
@@ -294,3 +294,3 @@ * Return all edges that point to the node v. Optionally filters those edges down to just those | ||
| * Complexity: O(|E|). | ||
| */inEdges(v,u){var inV=this.#in[v];if(inV){var edges=Object.values(inV);if(!u){return edges}return edges.filter(edge=>edge.v===u)}} | ||
| */inEdges(v,u){var inV=this._in[v];if(inV){var edges=Object.values(inV);if(!u){return edges}return edges.filter(edge=>edge.v===u)}} | ||
| /** | ||
@@ -300,3 +300,3 @@ * Return all edges that are pointed at by node v. Optionally filters those edges down to just | ||
| * Complexity: O(|E|). | ||
| */outEdges(v,w){var outV=this.#out[v];if(outV){var edges=Object.values(outV);if(!w){return edges}return edges.filter(edge=>edge.w===w)}} | ||
| */outEdges(v,w){var outV=this._out[v];if(outV){var edges=Object.values(outV);if(!w){return edges}return edges.filter(edge=>edge.w===w)}} | ||
| /** | ||
@@ -322,2 +322,2 @@ * Returns all edges to or from node v regardless of direction. Optionally filters those edges | ||
| * // [ { v: 'a', w: 'b' } ] | ||
| */function read(json){var g=new Graph(json.options).setGraph(json.value);json.nodes.forEach(function(entry){g.setNode(entry.v,entry.value);if(entry.parent){g.setParent(entry.v,entry.parent)}});json.edges.forEach(function(entry){g.setEdge({v:entry.v,w:entry.w,name:entry.name},entry.value)});return g}},{"./graph":16}],19:[function(require,module,exports){module.exports="2.2.1"},{}]},{},[1])(1)}); | ||
| */function read(json){var g=new Graph(json.options).setGraph(json.value);json.nodes.forEach(function(entry){g.setNode(entry.v,entry.value);if(entry.parent){g.setParent(entry.v,entry.parent)}});json.edges.forEach(function(entry){g.setEdge({v:entry.v,w:entry.w,name:entry.name},entry.value)});return g}},{"./graph":16}],19:[function(require,module,exports){module.exports="2.2.2"},{}]},{},[1])(1)}); |
@@ -9,4 +9,4 @@ /** | ||
| class PriorityQueue { | ||
| #arr = []; | ||
| #keyIndices = {}; | ||
| _arr = []; | ||
| _keyIndices = {}; | ||
@@ -17,3 +17,3 @@ /** | ||
| size() { | ||
| return this.#arr.length; | ||
| return this._arr.length; | ||
| } | ||
@@ -25,3 +25,3 @@ | ||
| keys() { | ||
| return this.#arr.map(function(x) { return x.key; }); | ||
| return this._arr.map(function(x) { return x.key; }); | ||
| } | ||
@@ -33,3 +33,3 @@ | ||
| has(key) { | ||
| return this.#keyIndices.hasOwnProperty(key); | ||
| return this._keyIndices.hasOwnProperty(key); | ||
| } | ||
@@ -44,5 +44,5 @@ | ||
| priority(key) { | ||
| var index = this.#keyIndices[key]; | ||
| var index = this._keyIndices[key]; | ||
| if (index !== undefined) { | ||
| return this.#arr[index].priority; | ||
| return this._arr[index].priority; | ||
| } | ||
@@ -59,3 +59,3 @@ } | ||
| } | ||
| return this.#arr[0].key; | ||
| return this._arr[0].key; | ||
| } | ||
@@ -72,10 +72,10 @@ | ||
| add(key, priority) { | ||
| var keyIndices = this.#keyIndices; | ||
| var keyIndices = this._keyIndices; | ||
| key = String(key); | ||
| if (!keyIndices.hasOwnProperty(key)) { | ||
| var arr = this.#arr; | ||
| var arr = this._arr; | ||
| var index = arr.length; | ||
| keyIndices[key] = index; | ||
| arr.push({key: key, priority: priority}); | ||
| this.#decrease(index); | ||
| this._decrease(index); | ||
| return true; | ||
@@ -90,6 +90,6 @@ } | ||
| removeMin() { | ||
| this.#swap(0, this.#arr.length - 1); | ||
| var min = this.#arr.pop(); | ||
| delete this.#keyIndices[min.key]; | ||
| this.#heapify(0); | ||
| this._swap(0, this._arr.length - 1); | ||
| var min = this._arr.pop(); | ||
| delete this._keyIndices[min.key]; | ||
| this._heapify(0); | ||
| return min.key; | ||
@@ -106,13 +106,13 @@ } | ||
| decrease(key, priority) { | ||
| var index = this.#keyIndices[key]; | ||
| if (priority > this.#arr[index].priority) { | ||
| var index = this._keyIndices[key]; | ||
| if (priority > this._arr[index].priority) { | ||
| throw new Error("New priority is greater than current priority. " + | ||
| "Key: " + key + " Old: " + this.#arr[index].priority + " New: " + priority); | ||
| "Key: " + key + " Old: " + this._arr[index].priority + " New: " + priority); | ||
| } | ||
| this.#arr[index].priority = priority; | ||
| this.#decrease(index); | ||
| this._arr[index].priority = priority; | ||
| this._decrease(index); | ||
| } | ||
| #heapify(i) { | ||
| var arr = this.#arr; | ||
| _heapify(i) { | ||
| var arr = this._arr; | ||
| var l = 2 * i; | ||
@@ -127,4 +127,4 @@ var r = l + 1; | ||
| if (largest !== i) { | ||
| this.#swap(i, largest); | ||
| this.#heapify(largest); | ||
| this._swap(i, largest); | ||
| this._heapify(largest); | ||
| } | ||
@@ -134,4 +134,4 @@ } | ||
| #decrease(index) { | ||
| var arr = this.#arr; | ||
| _decrease(index) { | ||
| var arr = this._arr; | ||
| var priority = arr[index].priority; | ||
@@ -144,3 +144,3 @@ var parent; | ||
| } | ||
| this.#swap(index, parent); | ||
| this._swap(index, parent); | ||
| index = parent; | ||
@@ -150,5 +150,5 @@ } | ||
| #swap(i, j) { | ||
| var arr = this.#arr; | ||
| var keyIndices = this.#keyIndices; | ||
| _swap(i, j) { | ||
| var arr = this._arr; | ||
| var keyIndices = this._keyIndices; | ||
| var origArrI = arr[i]; | ||
@@ -155,0 +155,0 @@ var origArrJ = arr[j]; |
230
lib/graph.js
@@ -18,60 +18,60 @@ "use strict"; | ||
| class Graph { | ||
| #isDirected = true; | ||
| #isMultigraph = false; | ||
| #isCompound = false; | ||
| _isDirected = true; | ||
| _isMultigraph = false; | ||
| _isCompound = false; | ||
| // Label for the graph itself | ||
| #label; | ||
| _label; | ||
| // Defaults to be set when creating a new node | ||
| #defaultNodeLabelFn = () => undefined; | ||
| _defaultNodeLabelFn = () => undefined; | ||
| // Defaults to be set when creating a new edge | ||
| #defaultEdgeLabelFn = () => undefined; | ||
| _defaultEdgeLabelFn = () => undefined; | ||
| // v -> label | ||
| #nodes = {}; | ||
| _nodes = {}; | ||
| // v -> edgeObj | ||
| #in = {}; | ||
| _in = {}; | ||
| // u -> v -> Number | ||
| #preds = {}; | ||
| _preds = {}; | ||
| // v -> edgeObj | ||
| #out = {}; | ||
| _out = {}; | ||
| // v -> w -> Number | ||
| #sucs = {}; | ||
| _sucs = {}; | ||
| // e -> edgeObj | ||
| #edgeObjs = {}; | ||
| _edgeObjs = {}; | ||
| // e -> label | ||
| #edgeLabels = {}; | ||
| _edgeLabels = {}; | ||
| /* Number of nodes in the graph. Should only be changed by the implementation. */ | ||
| #nodeCount = 0; | ||
| _nodeCount = 0; | ||
| /* Number of edges in the graph. Should only be changed by the implementation. */ | ||
| #edgeCount = 0; | ||
| _edgeCount = 0; | ||
| #parent; | ||
| _parent; | ||
| #children; | ||
| _children; | ||
| constructor(opts) { | ||
| if (opts) { | ||
| this.#isDirected = opts.hasOwnProperty("directed") ? opts.directed : true; | ||
| this.#isMultigraph = opts.hasOwnProperty("multigraph") ? opts.multigraph : false; | ||
| this.#isCompound = opts.hasOwnProperty("compound") ? opts.compound : false; | ||
| this._isDirected = opts.hasOwnProperty("directed") ? opts.directed : true; | ||
| this._isMultigraph = opts.hasOwnProperty("multigraph") ? opts.multigraph : false; | ||
| this._isCompound = opts.hasOwnProperty("compound") ? opts.compound : false; | ||
| } | ||
| if (this.#isCompound) { | ||
| if (this._isCompound) { | ||
| // v -> parent | ||
| this.#parent = {}; | ||
| this._parent = {}; | ||
| // v -> children | ||
| this.#children = {}; | ||
| this.#children[GRAPH_NODE] = {}; | ||
| this._children = {}; | ||
| this._children[GRAPH_NODE] = {}; | ||
| } | ||
@@ -86,3 +86,3 @@ } | ||
| isDirected() { | ||
| return this.#isDirected; | ||
| return this._isDirected; | ||
| } | ||
@@ -94,3 +94,3 @@ | ||
| isMultigraph() { | ||
| return this.#isMultigraph; | ||
| return this._isMultigraph; | ||
| } | ||
@@ -102,3 +102,3 @@ | ||
| isCompound() { | ||
| return this.#isCompound; | ||
| return this._isCompound; | ||
| } | ||
@@ -110,3 +110,3 @@ | ||
| setGraph(label) { | ||
| this.#label = label; | ||
| this._label = label; | ||
| return this; | ||
@@ -119,3 +119,3 @@ } | ||
| graph() { | ||
| return this.#label; | ||
| return this._label; | ||
| } | ||
@@ -134,5 +134,5 @@ | ||
| setDefaultNodeLabel(newDefault) { | ||
| this.#defaultNodeLabelFn = newDefault; | ||
| this._defaultNodeLabelFn = newDefault; | ||
| if (typeof newDefault !== 'function') { | ||
| this.#defaultNodeLabelFn = () => newDefault; | ||
| this._defaultNodeLabelFn = () => newDefault; | ||
| } | ||
@@ -148,3 +148,3 @@ | ||
| nodeCount() { | ||
| return this.#nodeCount; | ||
| return this._nodeCount; | ||
| } | ||
@@ -158,3 +158,3 @@ | ||
| nodes() { | ||
| return Object.keys(this.#nodes); | ||
| return Object.keys(this._nodes); | ||
| } | ||
@@ -168,3 +168,3 @@ | ||
| var self = this; | ||
| return this.nodes().filter(v => Object.keys(self.#in[v]).length === 0); | ||
| return this.nodes().filter(v => Object.keys(self._in[v]).length === 0); | ||
| } | ||
@@ -178,3 +178,3 @@ | ||
| var self = this; | ||
| return this.nodes().filter(v => Object.keys(self.#out[v]).length === 0); | ||
| return this.nodes().filter(v => Object.keys(self._out[v]).length === 0); | ||
| } | ||
@@ -206,5 +206,5 @@ | ||
| setNode(v, value) { | ||
| if (this.#nodes.hasOwnProperty(v)) { | ||
| if (this._nodes.hasOwnProperty(v)) { | ||
| if (arguments.length > 1) { | ||
| this.#nodes[v] = value; | ||
| this._nodes[v] = value; | ||
| } | ||
@@ -214,13 +214,13 @@ return this; | ||
| this.#nodes[v] = arguments.length > 1 ? value : this.#defaultNodeLabelFn(v); | ||
| if (this.#isCompound) { | ||
| this.#parent[v] = GRAPH_NODE; | ||
| this.#children[v] = {}; | ||
| this.#children[GRAPH_NODE][v] = true; | ||
| this._nodes[v] = arguments.length > 1 ? value : this._defaultNodeLabelFn(v); | ||
| if (this._isCompound) { | ||
| this._parent[v] = GRAPH_NODE; | ||
| this._children[v] = {}; | ||
| this._children[GRAPH_NODE][v] = true; | ||
| } | ||
| this.#in[v] = {}; | ||
| this.#preds[v] = {}; | ||
| this.#out[v] = {}; | ||
| this.#sucs[v] = {}; | ||
| ++this.#nodeCount; | ||
| this._in[v] = {}; | ||
| this._preds[v] = {}; | ||
| this._out[v] = {}; | ||
| this._sucs[v] = {}; | ||
| ++this._nodeCount; | ||
| return this; | ||
@@ -234,3 +234,3 @@ } | ||
| node(v) { | ||
| return this.#nodes[v]; | ||
| return this._nodes[v]; | ||
| } | ||
@@ -242,3 +242,3 @@ | ||
| hasNode(v) { | ||
| return this.#nodes.hasOwnProperty(v); | ||
| return this._nodes.hasOwnProperty(v); | ||
| } | ||
@@ -254,20 +254,20 @@ | ||
| var self = this; | ||
| if (this.#nodes.hasOwnProperty(v)) { | ||
| var removeEdge = e => self.removeEdge(self.#edgeObjs[e]); | ||
| delete this.#nodes[v]; | ||
| if (this.#isCompound) { | ||
| this.#removeFromParentsChildList(v); | ||
| delete this.#parent[v]; | ||
| if (this._nodes.hasOwnProperty(v)) { | ||
| var removeEdge = e => self.removeEdge(self._edgeObjs[e]); | ||
| delete this._nodes[v]; | ||
| if (this._isCompound) { | ||
| this._removeFromParentsChildList(v); | ||
| delete this._parent[v]; | ||
| this.children(v).forEach(function(child) { | ||
| self.setParent(child); | ||
| }); | ||
| delete this.#children[v]; | ||
| delete this._children[v]; | ||
| } | ||
| Object.keys(this.#in[v]).forEach(removeEdge); | ||
| delete this.#in[v]; | ||
| delete this.#preds[v]; | ||
| Object.keys(this.#out[v]).forEach(removeEdge); | ||
| delete this.#out[v]; | ||
| delete this.#sucs[v]; | ||
| --this.#nodeCount; | ||
| Object.keys(this._in[v]).forEach(removeEdge); | ||
| delete this._in[v]; | ||
| delete this._preds[v]; | ||
| Object.keys(this._out[v]).forEach(removeEdge); | ||
| delete this._out[v]; | ||
| delete this._sucs[v]; | ||
| --this._nodeCount; | ||
| } | ||
@@ -284,3 +284,3 @@ return this; | ||
| setParent(v, parent) { | ||
| if (!this.#isCompound) { | ||
| if (!this._isCompound) { | ||
| throw new Error("Cannot set parent in a non-compound graph"); | ||
@@ -305,10 +305,10 @@ } | ||
| this.setNode(v); | ||
| this.#removeFromParentsChildList(v); | ||
| this.#parent[v] = parent; | ||
| this.#children[parent][v] = true; | ||
| this._removeFromParentsChildList(v); | ||
| this._parent[v] = parent; | ||
| this._children[parent][v] = true; | ||
| return this; | ||
| } | ||
| #removeFromParentsChildList(v) { | ||
| delete this.#children[this.#parent[v]][v]; | ||
| _removeFromParentsChildList(v) { | ||
| delete this._children[this._parent[v]][v]; | ||
| } | ||
@@ -321,4 +321,4 @@ | ||
| parent(v) { | ||
| if (this.#isCompound) { | ||
| var parent = this.#parent[v]; | ||
| if (this._isCompound) { | ||
| var parent = this._parent[v]; | ||
| if (parent !== GRAPH_NODE) { | ||
@@ -335,4 +335,4 @@ return parent; | ||
| children(v = GRAPH_NODE) { | ||
| if (this.#isCompound) { | ||
| var children = this.#children[v]; | ||
| if (this._isCompound) { | ||
| var children = this._children[v]; | ||
| if (children) { | ||
@@ -354,3 +354,3 @@ return Object.keys(children); | ||
| predecessors(v) { | ||
| var predsV = this.#preds[v]; | ||
| var predsV = this._preds[v]; | ||
| if (predsV) { | ||
@@ -367,3 +367,3 @@ return Object.keys(predsV); | ||
| successors(v) { | ||
| var sucsV = this.#sucs[v]; | ||
| var sucsV = this._sucs[v]; | ||
| if (sucsV) { | ||
@@ -409,5 +409,5 @@ return Object.keys(sucsV); | ||
| var copy = new this.constructor({ | ||
| directed: this.#isDirected, | ||
| multigraph: this.#isMultigraph, | ||
| compound: this.#isCompound | ||
| directed: this._isDirected, | ||
| multigraph: this._isMultigraph, | ||
| compound: this._isCompound | ||
| }); | ||
@@ -418,3 +418,3 @@ | ||
| var self = this; | ||
| Object.entries(this.#nodes).forEach(function([v, value]) { | ||
| Object.entries(this._nodes).forEach(function([v, value]) { | ||
| if (filter(v)) { | ||
@@ -425,3 +425,3 @@ copy.setNode(v, value); | ||
| Object.values(this.#edgeObjs).forEach(function(e) { | ||
| Object.values(this._edgeObjs).forEach(function(e) { | ||
| if (copy.hasNode(e.v) && copy.hasNode(e.w)) { | ||
@@ -445,3 +445,3 @@ copy.setEdge(e, self.edge(e)); | ||
| if (this.#isCompound) { | ||
| if (this._isCompound) { | ||
| copy.nodes().forEach(v => copy.setParent(v, findParent(v))); | ||
@@ -463,5 +463,5 @@ } | ||
| setDefaultEdgeLabel(newDefault) { | ||
| this.#defaultEdgeLabelFn = newDefault; | ||
| this._defaultEdgeLabelFn = newDefault; | ||
| if (typeof newDefault !== 'function') { | ||
| this.#defaultEdgeLabelFn = () => newDefault; | ||
| this._defaultEdgeLabelFn = () => newDefault; | ||
| } | ||
@@ -477,3 +477,3 @@ | ||
| edgeCount() { | ||
| return this.#edgeCount; | ||
| return this._edgeCount; | ||
| } | ||
@@ -486,3 +486,3 @@ | ||
| edges() { | ||
| return Object.values(this.#edgeObjs); | ||
| return Object.values(this._edgeObjs); | ||
| } | ||
@@ -545,6 +545,6 @@ | ||
| var e = edgeArgsToId(this.#isDirected, v, w, name); | ||
| if (this.#edgeLabels.hasOwnProperty(e)) { | ||
| var e = edgeArgsToId(this._isDirected, v, w, name); | ||
| if (this._edgeLabels.hasOwnProperty(e)) { | ||
| if (valueSpecified) { | ||
| this.#edgeLabels[e] = value; | ||
| this._edgeLabels[e] = value; | ||
| } | ||
@@ -554,3 +554,3 @@ return this; | ||
| if (name !== undefined && !this.#isMultigraph) { | ||
| if (name !== undefined && !this._isMultigraph) { | ||
| throw new Error("Cannot set a named edge when isMultigraph = false"); | ||
@@ -564,5 +564,5 @@ } | ||
| this.#edgeLabels[e] = valueSpecified ? value : this.#defaultEdgeLabelFn(v, w, name); | ||
| this._edgeLabels[e] = valueSpecified ? value : this._defaultEdgeLabelFn(v, w, name); | ||
| var edgeObj = edgeArgsToObj(this.#isDirected, v, w, name); | ||
| var edgeObj = edgeArgsToObj(this._isDirected, v, w, name); | ||
| // Ensure we add undirected edges in a consistent way. | ||
@@ -573,8 +573,8 @@ v = edgeObj.v; | ||
| Object.freeze(edgeObj); | ||
| this.#edgeObjs[e] = edgeObj; | ||
| incrementOrInitEntry(this.#preds[w], v); | ||
| incrementOrInitEntry(this.#sucs[v], w); | ||
| this.#in[w][e] = edgeObj; | ||
| this.#out[v][e] = edgeObj; | ||
| this.#edgeCount++; | ||
| this._edgeObjs[e] = edgeObj; | ||
| incrementOrInitEntry(this._preds[w], v); | ||
| incrementOrInitEntry(this._sucs[v], w); | ||
| this._in[w][e] = edgeObj; | ||
| this._out[v][e] = edgeObj; | ||
| this._edgeCount++; | ||
| return this; | ||
@@ -589,5 +589,5 @@ } | ||
| var e = (arguments.length === 1 | ||
| ? edgeObjToId(this.#isDirected, arguments[0]) | ||
| : edgeArgsToId(this.#isDirected, v, w, name)); | ||
| return this.#edgeLabels[e]; | ||
| ? edgeObjToId(this._isDirected, arguments[0]) | ||
| : edgeArgsToId(this._isDirected, v, w, name)); | ||
| return this._edgeLabels[e]; | ||
| } | ||
@@ -614,5 +614,5 @@ | ||
| var e = (arguments.length === 1 | ||
| ? edgeObjToId(this.#isDirected, arguments[0]) | ||
| : edgeArgsToId(this.#isDirected, v, w, name)); | ||
| return this.#edgeLabels.hasOwnProperty(e); | ||
| ? edgeObjToId(this._isDirected, arguments[0]) | ||
| : edgeArgsToId(this._isDirected, v, w, name)); | ||
| return this._edgeLabels.hasOwnProperty(e); | ||
| } | ||
@@ -626,15 +626,15 @@ | ||
| var e = (arguments.length === 1 | ||
| ? edgeObjToId(this.#isDirected, arguments[0]) | ||
| : edgeArgsToId(this.#isDirected, v, w, name)); | ||
| var edge = this.#edgeObjs[e]; | ||
| ? edgeObjToId(this._isDirected, arguments[0]) | ||
| : edgeArgsToId(this._isDirected, v, w, name)); | ||
| var edge = this._edgeObjs[e]; | ||
| if (edge) { | ||
| v = edge.v; | ||
| w = edge.w; | ||
| delete this.#edgeLabels[e]; | ||
| delete this.#edgeObjs[e]; | ||
| decrementOrRemoveEntry(this.#preds[w], v); | ||
| decrementOrRemoveEntry(this.#sucs[v], w); | ||
| delete this.#in[w][e]; | ||
| delete this.#out[v][e]; | ||
| this.#edgeCount--; | ||
| delete this._edgeLabels[e]; | ||
| delete this._edgeObjs[e]; | ||
| decrementOrRemoveEntry(this._preds[w], v); | ||
| decrementOrRemoveEntry(this._sucs[v], w); | ||
| delete this._in[w][e]; | ||
| delete this._out[v][e]; | ||
| this._edgeCount--; | ||
| } | ||
@@ -650,3 +650,3 @@ return this; | ||
| inEdges(v, u) { | ||
| var inV = this.#in[v]; | ||
| var inV = this._in[v]; | ||
| if (inV) { | ||
@@ -667,3 +667,3 @@ var edges = Object.values(inV); | ||
| outEdges(v, w) { | ||
| var outV = this.#out[v]; | ||
| var outV = this._out[v]; | ||
| if (outV) { | ||
@@ -670,0 +670,0 @@ var edges = Object.values(outV); |
@@ -1,1 +0,1 @@ | ||
| module.exports = '2.2.1'; | ||
| module.exports = '2.2.2'; |
| { | ||
| "name": "@dagrejs/graphlib", | ||
| "version": "2.2.1", | ||
| "version": "2.2.2", | ||
| "description": "A directed and undirected multi-graph library", | ||
@@ -5,0 +5,0 @@ "author": "Chris Pettitt <cpettitt@gmail.com>", |
New alerts
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
Fixed alerts
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
No metric changes
No dependency changes