@dagrejs/graphlib
Advanced tools
Comparing version 2.2.3 to 2.2.4
@@ -50,3 +50,3 @@ (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){ | ||
function dfs(v) { | ||
if (visited.hasOwnProperty(v)) return; | ||
if (Object.hasOwn(visited, v)) return; | ||
visited[v] = true; | ||
@@ -108,3 +108,3 @@ cmpt.push(v); | ||
} else { | ||
if (!visited.hasOwnProperty(curr[0])) { | ||
if (!Object.hasOwn(visited, curr[0])) { | ||
visited[curr[0]] = true; | ||
@@ -122,3 +122,3 @@ stack.push([curr[0], true]); | ||
var curr = stack.pop(); | ||
if (!visited.hasOwnProperty(curr)) { | ||
if (!Object.hasOwn(visited, curr)) { | ||
visited[curr] = true; | ||
@@ -357,3 +357,3 @@ acc.push(curr); | ||
v = pq.removeMin(); | ||
if (parents.hasOwnProperty(v)) { | ||
if (Object.hasOwn(parents, v)) { | ||
result.setEdge(v, parents[v]); | ||
@@ -390,3 +390,3 @@ } else if (init) { | ||
g.successors(v).forEach(function(w) { | ||
if (!visited.hasOwnProperty(w)) { | ||
if (!Object.hasOwn(visited, w)) { | ||
dfs(w); | ||
@@ -412,3 +412,3 @@ entry.lowlink = Math.min(entry.lowlink, visited[w].lowlink); | ||
g.nodes().forEach(function(v) { | ||
if (!visited.hasOwnProperty(v)) { | ||
if (!Object.hasOwn(visited, v)) { | ||
dfs(v); | ||
@@ -428,7 +428,7 @@ } | ||
function visit(node) { | ||
if (stack.hasOwnProperty(node)) { | ||
if (Object.hasOwn(stack, node)) { | ||
throw new CycleException(); | ||
} | ||
if (!visited.hasOwnProperty(node)) { | ||
if (!Object.hasOwn(visited, node)) { | ||
stack[node] = true; | ||
@@ -490,3 +490,3 @@ visited[node] = true; | ||
has(key) { | ||
return this._keyIndices.hasOwnProperty(key); | ||
return Object.hasOwn(this._keyIndices, key); | ||
} | ||
@@ -529,3 +529,3 @@ | ||
key = String(key); | ||
if (!keyIndices.hasOwnProperty(key)) { | ||
if (!Object.hasOwn(keyIndices, key)) { | ||
var arr = this._arr; | ||
@@ -678,5 +678,5 @@ var index = arr.length; | ||
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 = Object.hasOwn(opts, "directed") ? opts.directed : true; | ||
this._isMultigraph = Object.hasOwn(opts, "multigraph") ? opts.multigraph : false; | ||
this._isCompound = Object.hasOwn(opts, "compound") ? opts.compound : false; | ||
} | ||
@@ -810,3 +810,3 @@ | ||
setNode(v, value) { | ||
if (this._nodes.hasOwnProperty(v)) { | ||
if (Object.hasOwn(this._nodes, v)) { | ||
if (arguments.length > 1) { | ||
@@ -844,3 +844,3 @@ this._nodes[v] = value; | ||
hasNode(v) { | ||
return this._nodes.hasOwnProperty(v); | ||
return Object.hasOwn(this._nodes, v); | ||
} | ||
@@ -856,3 +856,3 @@ | ||
var self = this; | ||
if (this._nodes.hasOwnProperty(v)) { | ||
if (Object.hasOwn(this._nodes, v)) { | ||
var removeEdge = e => self.removeEdge(self._edgeObjs[e]); | ||
@@ -1135,3 +1135,3 @@ delete this._nodes[v]; | ||
var e = edgeArgsToId(this._isDirected, v, w, name); | ||
if (this._edgeLabels.hasOwnProperty(e)) { | ||
if (Object.hasOwn(this._edgeLabels, e)) { | ||
if (valueSpecified) { | ||
@@ -1201,3 +1201,3 @@ this._edgeLabels[e] = value; | ||
: edgeArgsToId(this._isDirected, v, w, name)); | ||
return this._edgeLabels.hasOwnProperty(e); | ||
return Object.hasOwn(this._edgeLabels, e); | ||
} | ||
@@ -1408,5 +1408,5 @@ | ||
},{"./graph":16}],19:[function(require,module,exports){ | ||
module.exports = '2.2.3'; | ||
module.exports = '2.2.4'; | ||
},{}]},{},[1])(1) | ||
}); |
@@ -31,3 +31,3 @@ (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){ | ||
*/ | ||
var lib=require("./lib");module.exports={Graph:lib.Graph,json:require("./lib/json"),alg:require("./lib/alg"),version:lib.version}},{"./lib":17,"./lib/alg":8,"./lib/json":18}],2:[function(require,module,exports){module.exports=components;function components(g){var visited={};var cmpts=[];var cmpt;function dfs(v){if(visited.hasOwnProperty(v))return;visited[v]=true;cmpt.push(v);g.successors(v).forEach(dfs);g.predecessors(v).forEach(dfs)}g.nodes().forEach(function(v){cmpt=[];dfs(v);if(cmpt.length){cmpts.push(cmpt)}});return cmpts}},{}],3:[function(require,module,exports){module.exports=dfs; | ||
var lib=require("./lib");module.exports={Graph:lib.Graph,json:require("./lib/json"),alg:require("./lib/alg"),version:lib.version}},{"./lib":17,"./lib/alg":8,"./lib/json":18}],2:[function(require,module,exports){module.exports=components;function components(g){var visited={};var cmpts=[];var cmpt;function dfs(v){if(Object.hasOwn(visited,v))return;visited[v]=true;cmpt.push(v);g.successors(v).forEach(dfs);g.predecessors(v).forEach(dfs)}g.nodes().forEach(function(v){cmpt=[];dfs(v);if(cmpt.length){cmpts.push(cmpt)}});return cmpts}},{}],3:[function(require,module,exports){module.exports=dfs; | ||
/* | ||
@@ -40,6 +40,6 @@ * A helper that preforms a pre- or post-order traversal on the input graph | ||
* If the order is not "post", it will be treated as "pre". | ||
*/function dfs(g,vs,order){if(!Array.isArray(vs)){vs=[vs]}var navigation=g.isDirected()?v=>g.successors(v):v=>g.neighbors(v);var orderFunc=order==="post"?postOrderDfs:preOrderDfs;var acc=[];var visited={};vs.forEach(v=>{if(!g.hasNode(v)){throw new Error("Graph does not have node: "+v)}orderFunc(v,navigation,visited,acc)});return acc}function postOrderDfs(v,navigation,visited,acc){var stack=[[v,false]];while(stack.length>0){var curr=stack.pop();if(curr[1]){acc.push(curr[0])}else{if(!visited.hasOwnProperty(curr[0])){visited[curr[0]]=true;stack.push([curr[0],true]);forEachRight(navigation(curr[0]),w=>stack.push([w,false]))}}}}function preOrderDfs(v,navigation,visited,acc){var stack=[v];while(stack.length>0){var curr=stack.pop();if(!visited.hasOwnProperty(curr)){visited[curr]=true;acc.push(curr);forEachRight(navigation(curr),w=>stack.push(w))}}}function forEachRight(array,iteratee){var length=array.length;while(length--){iteratee(array[length],length,array)}return array}},{}],4:[function(require,module,exports){var dijkstra=require("./dijkstra");module.exports=dijkstraAll;function dijkstraAll(g,weightFunc,edgeFunc){return g.nodes().reduce(function(acc,v){acc[v]=dijkstra(g,v,weightFunc,edgeFunc);return acc},{})}},{"./dijkstra":5}],5:[function(require,module,exports){var PriorityQueue=require("../data/priority-queue");module.exports=dijkstra;var DEFAULT_WEIGHT_FUNC=()=>1;function dijkstra(g,source,weightFn,edgeFn){return runDijkstra(g,String(source),weightFn||DEFAULT_WEIGHT_FUNC,edgeFn||function(v){return g.outEdges(v)})}function runDijkstra(g,source,weightFn,edgeFn){var results={};var pq=new PriorityQueue;var v,vEntry;var updateNeighbors=function(edge){var w=edge.v!==v?edge.v:edge.w;var wEntry=results[w];var weight=weightFn(edge);var distance=vEntry.distance+weight;if(weight<0){throw new Error("dijkstra does not allow negative edge weights. "+"Bad edge: "+edge+" Weight: "+weight)}if(distance<wEntry.distance){wEntry.distance=distance;wEntry.predecessor=v;pq.decrease(w,distance)}};g.nodes().forEach(function(v){var distance=v===source?0:Number.POSITIVE_INFINITY;results[v]={distance:distance};pq.add(v,distance)});while(pq.size()>0){v=pq.removeMin();vEntry=results[v];if(vEntry.distance===Number.POSITIVE_INFINITY){break}edgeFn(v).forEach(updateNeighbors)}return results}},{"../data/priority-queue":15}],6:[function(require,module,exports){var tarjan=require("./tarjan");module.exports=findCycles;function findCycles(g){return tarjan(g).filter(function(cmpt){return cmpt.length>1||cmpt.length===1&&g.hasEdge(cmpt[0],cmpt[0])})}},{"./tarjan":13}],7:[function(require,module,exports){module.exports=floydWarshall;var DEFAULT_WEIGHT_FUNC=()=>1;function floydWarshall(g,weightFn,edgeFn){return runFloydWarshall(g,weightFn||DEFAULT_WEIGHT_FUNC,edgeFn||function(v){return g.outEdges(v)})}function runFloydWarshall(g,weightFn,edgeFn){var results={};var nodes=g.nodes();nodes.forEach(function(v){results[v]={};results[v][v]={distance:0};nodes.forEach(function(w){if(v!==w){results[v][w]={distance:Number.POSITIVE_INFINITY}}});edgeFn(v).forEach(function(edge){var w=edge.v===v?edge.w:edge.v;var d=weightFn(edge);results[v][w]={distance:d,predecessor:v}})});nodes.forEach(function(k){var rowK=results[k];nodes.forEach(function(i){var rowI=results[i];nodes.forEach(function(j){var ik=rowI[k];var kj=rowK[j];var ij=rowI[j];var altDistance=ik.distance+kj.distance;if(altDistance<ij.distance){ij.distance=altDistance;ij.predecessor=kj.predecessor}})})});return results}},{}],8:[function(require,module,exports){module.exports={components:require("./components"),dijkstra:require("./dijkstra"),dijkstraAll:require("./dijkstra-all"),findCycles:require("./find-cycles"),floydWarshall:require("./floyd-warshall"),isAcyclic:require("./is-acyclic"),postorder:require("./postorder"),preorder:require("./preorder"),prim:require("./prim"),tarjan:require("./tarjan"),topsort:require("./topsort")}},{"./components":2,"./dijkstra":5,"./dijkstra-all":4,"./find-cycles":6,"./floyd-warshall":7,"./is-acyclic":9,"./postorder":10,"./preorder":11,"./prim":12,"./tarjan":13,"./topsort":14}],9:[function(require,module,exports){var topsort=require("./topsort");module.exports=isAcyclic;function isAcyclic(g){try{topsort(g)}catch(e){if(e instanceof topsort.CycleException){return false}throw e}return true}},{"./topsort":14}],10:[function(require,module,exports){var dfs=require("./dfs");module.exports=postorder;function postorder(g,vs){return dfs(g,vs,"post")}},{"./dfs":3}],11:[function(require,module,exports){var dfs=require("./dfs");module.exports=preorder;function preorder(g,vs){return dfs(g,vs,"pre")}},{"./dfs":3}],12:[function(require,module,exports){var Graph=require("../graph");var PriorityQueue=require("../data/priority-queue");module.exports=prim;function prim(g,weightFunc){var result=new Graph;var parents={};var pq=new PriorityQueue;var v;function updateNeighbors(edge){var w=edge.v===v?edge.w:edge.v;var pri=pq.priority(w);if(pri!==undefined){var edgeWeight=weightFunc(edge);if(edgeWeight<pri){parents[w]=v;pq.decrease(w,edgeWeight)}}}if(g.nodeCount()===0){return result}g.nodes().forEach(function(v){pq.add(v,Number.POSITIVE_INFINITY);result.setNode(v)}); | ||
*/function dfs(g,vs,order){if(!Array.isArray(vs)){vs=[vs]}var navigation=g.isDirected()?v=>g.successors(v):v=>g.neighbors(v);var orderFunc=order==="post"?postOrderDfs:preOrderDfs;var acc=[];var visited={};vs.forEach(v=>{if(!g.hasNode(v)){throw new Error("Graph does not have node: "+v)}orderFunc(v,navigation,visited,acc)});return acc}function postOrderDfs(v,navigation,visited,acc){var stack=[[v,false]];while(stack.length>0){var curr=stack.pop();if(curr[1]){acc.push(curr[0])}else{if(!Object.hasOwn(visited,curr[0])){visited[curr[0]]=true;stack.push([curr[0],true]);forEachRight(navigation(curr[0]),w=>stack.push([w,false]))}}}}function preOrderDfs(v,navigation,visited,acc){var stack=[v];while(stack.length>0){var curr=stack.pop();if(!Object.hasOwn(visited,curr)){visited[curr]=true;acc.push(curr);forEachRight(navigation(curr),w=>stack.push(w))}}}function forEachRight(array,iteratee){var length=array.length;while(length--){iteratee(array[length],length,array)}return array}},{}],4:[function(require,module,exports){var dijkstra=require("./dijkstra");module.exports=dijkstraAll;function dijkstraAll(g,weightFunc,edgeFunc){return g.nodes().reduce(function(acc,v){acc[v]=dijkstra(g,v,weightFunc,edgeFunc);return acc},{})}},{"./dijkstra":5}],5:[function(require,module,exports){var PriorityQueue=require("../data/priority-queue");module.exports=dijkstra;var DEFAULT_WEIGHT_FUNC=()=>1;function dijkstra(g,source,weightFn,edgeFn){return runDijkstra(g,String(source),weightFn||DEFAULT_WEIGHT_FUNC,edgeFn||function(v){return g.outEdges(v)})}function runDijkstra(g,source,weightFn,edgeFn){var results={};var pq=new PriorityQueue;var v,vEntry;var updateNeighbors=function(edge){var w=edge.v!==v?edge.v:edge.w;var wEntry=results[w];var weight=weightFn(edge);var distance=vEntry.distance+weight;if(weight<0){throw new Error("dijkstra does not allow negative edge weights. "+"Bad edge: "+edge+" Weight: "+weight)}if(distance<wEntry.distance){wEntry.distance=distance;wEntry.predecessor=v;pq.decrease(w,distance)}};g.nodes().forEach(function(v){var distance=v===source?0:Number.POSITIVE_INFINITY;results[v]={distance:distance};pq.add(v,distance)});while(pq.size()>0){v=pq.removeMin();vEntry=results[v];if(vEntry.distance===Number.POSITIVE_INFINITY){break}edgeFn(v).forEach(updateNeighbors)}return results}},{"../data/priority-queue":15}],6:[function(require,module,exports){var tarjan=require("./tarjan");module.exports=findCycles;function findCycles(g){return tarjan(g).filter(function(cmpt){return cmpt.length>1||cmpt.length===1&&g.hasEdge(cmpt[0],cmpt[0])})}},{"./tarjan":13}],7:[function(require,module,exports){module.exports=floydWarshall;var DEFAULT_WEIGHT_FUNC=()=>1;function floydWarshall(g,weightFn,edgeFn){return runFloydWarshall(g,weightFn||DEFAULT_WEIGHT_FUNC,edgeFn||function(v){return g.outEdges(v)})}function runFloydWarshall(g,weightFn,edgeFn){var results={};var nodes=g.nodes();nodes.forEach(function(v){results[v]={};results[v][v]={distance:0};nodes.forEach(function(w){if(v!==w){results[v][w]={distance:Number.POSITIVE_INFINITY}}});edgeFn(v).forEach(function(edge){var w=edge.v===v?edge.w:edge.v;var d=weightFn(edge);results[v][w]={distance:d,predecessor:v}})});nodes.forEach(function(k){var rowK=results[k];nodes.forEach(function(i){var rowI=results[i];nodes.forEach(function(j){var ik=rowI[k];var kj=rowK[j];var ij=rowI[j];var altDistance=ik.distance+kj.distance;if(altDistance<ij.distance){ij.distance=altDistance;ij.predecessor=kj.predecessor}})})});return results}},{}],8:[function(require,module,exports){module.exports={components:require("./components"),dijkstra:require("./dijkstra"),dijkstraAll:require("./dijkstra-all"),findCycles:require("./find-cycles"),floydWarshall:require("./floyd-warshall"),isAcyclic:require("./is-acyclic"),postorder:require("./postorder"),preorder:require("./preorder"),prim:require("./prim"),tarjan:require("./tarjan"),topsort:require("./topsort")}},{"./components":2,"./dijkstra":5,"./dijkstra-all":4,"./find-cycles":6,"./floyd-warshall":7,"./is-acyclic":9,"./postorder":10,"./preorder":11,"./prim":12,"./tarjan":13,"./topsort":14}],9:[function(require,module,exports){var topsort=require("./topsort");module.exports=isAcyclic;function isAcyclic(g){try{topsort(g)}catch(e){if(e instanceof topsort.CycleException){return false}throw e}return true}},{"./topsort":14}],10:[function(require,module,exports){var dfs=require("./dfs");module.exports=postorder;function postorder(g,vs){return dfs(g,vs,"post")}},{"./dfs":3}],11:[function(require,module,exports){var dfs=require("./dfs");module.exports=preorder;function preorder(g,vs){return dfs(g,vs,"pre")}},{"./dfs":3}],12:[function(require,module,exports){var Graph=require("../graph");var PriorityQueue=require("../data/priority-queue");module.exports=prim;function prim(g,weightFunc){var result=new Graph;var parents={};var pq=new PriorityQueue;var v;function updateNeighbors(edge){var w=edge.v===v?edge.w:edge.v;var pri=pq.priority(w);if(pri!==undefined){var edgeWeight=weightFunc(edge);if(edgeWeight<pri){parents[w]=v;pq.decrease(w,edgeWeight)}}}if(g.nodeCount()===0){return result}g.nodes().forEach(function(v){pq.add(v,Number.POSITIVE_INFINITY);result.setNode(v)}); | ||
// Start from an arbitrary node | ||
pq.decrease(g.nodes()[0],0);var init=false;while(pq.size()>0){v=pq.removeMin();if(parents.hasOwnProperty(v)){result.setEdge(v,parents[v])}else if(init){throw new Error("Input graph is not connected: "+g)}else{init=true}g.nodeEdges(v).forEach(updateNeighbors)}return result}},{"../data/priority-queue":15,"../graph":16}],13:[function(require,module,exports){module.exports=tarjan;function tarjan(g){var index=0;var stack=[];var visited={};// node id -> { onStack, lowlink, index } | ||
var results=[];function dfs(v){var entry=visited[v]={onStack:true,lowlink:index,index:index++};stack.push(v);g.successors(v).forEach(function(w){if(!visited.hasOwnProperty(w)){dfs(w);entry.lowlink=Math.min(entry.lowlink,visited[w].lowlink)}else if(visited[w].onStack){entry.lowlink=Math.min(entry.lowlink,visited[w].index)}});if(entry.lowlink===entry.index){var cmpt=[];var w;do{w=stack.pop();visited[w].onStack=false;cmpt.push(w)}while(v!==w);results.push(cmpt)}}g.nodes().forEach(function(v){if(!visited.hasOwnProperty(v)){dfs(v)}});return results}},{}],14:[function(require,module,exports){function topsort(g){var visited={};var stack={};var results=[];function visit(node){if(stack.hasOwnProperty(node)){throw new CycleException}if(!visited.hasOwnProperty(node)){stack[node]=true;visited[node]=true;g.predecessors(node).forEach(visit);delete stack[node];results.push(node)}}g.sinks().forEach(visit);if(Object.keys(visited).length!==g.nodeCount()){throw new CycleException}return results}class CycleException extends Error{constructor(){super(...arguments)}}module.exports=topsort;topsort.CycleException=CycleException},{}],15:[function(require,module,exports){ | ||
pq.decrease(g.nodes()[0],0);var init=false;while(pq.size()>0){v=pq.removeMin();if(Object.hasOwn(parents,v)){result.setEdge(v,parents[v])}else if(init){throw new Error("Input graph is not connected: "+g)}else{init=true}g.nodeEdges(v).forEach(updateNeighbors)}return result}},{"../data/priority-queue":15,"../graph":16}],13:[function(require,module,exports){module.exports=tarjan;function tarjan(g){var index=0;var stack=[];var visited={};// node id -> { onStack, lowlink, index } | ||
var results=[];function dfs(v){var entry=visited[v]={onStack:true,lowlink:index,index:index++};stack.push(v);g.successors(v).forEach(function(w){if(!Object.hasOwn(visited,w)){dfs(w);entry.lowlink=Math.min(entry.lowlink,visited[w].lowlink)}else if(visited[w].onStack){entry.lowlink=Math.min(entry.lowlink,visited[w].index)}});if(entry.lowlink===entry.index){var cmpt=[];var w;do{w=stack.pop();visited[w].onStack=false;cmpt.push(w)}while(v!==w);results.push(cmpt)}}g.nodes().forEach(function(v){if(!Object.hasOwn(visited,v)){dfs(v)}});return results}},{}],14:[function(require,module,exports){function topsort(g){var visited={};var stack={};var results=[];function visit(node){if(Object.hasOwn(stack,node)){throw new CycleException}if(!Object.hasOwn(visited,node)){stack[node]=true;visited[node]=true;g.predecessors(node).forEach(visit);delete stack[node];results.push(node)}}g.sinks().forEach(visit);if(Object.keys(visited).length!==g.nodeCount()){throw new CycleException}return results}class CycleException extends Error{constructor(){super(...arguments)}}module.exports=topsort;topsort.CycleException=CycleException},{}],15:[function(require,module,exports){ | ||
/** | ||
@@ -61,3 +61,3 @@ * A min-priority queue data structure. This algorithm is derived from Cormen, | ||
* Returns `true` if **key** is in the queue and `false` if not. | ||
*/has(key){return this._keyIndices.hasOwnProperty(key)} | ||
*/has(key){return Object.hasOwn(this._keyIndices,key)} | ||
/** | ||
@@ -80,3 +80,3 @@ * Returns the priority for **key**. If **key** is not present in the queue | ||
* @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(!Object.hasOwn(keyIndices,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} | ||
/** | ||
@@ -123,3 +123,3 @@ * Removes and returns the smallest key in the queue. Takes `O(log n)` time. | ||
/* 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){ | ||
/* Number of edges in the graph. Should only be changed by the implementation. */_edgeCount=0;_parent;_children;constructor(opts){if(opts){this._isDirected=Object.hasOwn(opts,"directed")?opts.directed:true;this._isMultigraph=Object.hasOwn(opts,"multigraph")?opts.multigraph:false;this._isCompound=Object.hasOwn(opts,"compound")?opts.compound:false}if(this._isCompound){ | ||
// v -> parent | ||
@@ -179,3 +179,3 @@ this._parent={}; | ||
* 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(Object.hasOwn(this._nodes,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} | ||
/** | ||
@@ -187,3 +187,3 @@ * Gets the label of node with specified name. | ||
* Detects whether graph has a node with specified name or not. | ||
*/hasNode(v){return this._nodes.hasOwnProperty(v)} | ||
*/hasNode(v){return Object.hasOwn(this._nodes,v)} | ||
/** | ||
@@ -194,3 +194,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(Object.hasOwn(this._nodes,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} | ||
/** | ||
@@ -260,3 +260,3 @@ * Sets node p as a parent for node v if it is defined, or removes the | ||
* 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(Object.hasOwn(this._edgeLabels,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. | ||
@@ -278,3 +278,3 @@ // First ensure the nodes exist. | ||
* 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 Object.hasOwn(this._edgeLabels,e)} | ||
/** | ||
@@ -314,2 +314,2 @@ * Removes the specified edge from the graph. No subgraphs are considered. | ||
* // [ { 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.3"},{}]},{},[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.4"},{}]},{},[1])(1)}); |
@@ -50,3 +50,3 @@ (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){ | ||
function dfs(v) { | ||
if (visited.hasOwnProperty(v)) return; | ||
if (Object.hasOwn(visited, v)) return; | ||
visited[v] = true; | ||
@@ -108,3 +108,3 @@ cmpt.push(v); | ||
} else { | ||
if (!visited.hasOwnProperty(curr[0])) { | ||
if (!Object.hasOwn(visited, curr[0])) { | ||
visited[curr[0]] = true; | ||
@@ -122,3 +122,3 @@ stack.push([curr[0], true]); | ||
var curr = stack.pop(); | ||
if (!visited.hasOwnProperty(curr)) { | ||
if (!Object.hasOwn(visited, curr)) { | ||
visited[curr] = true; | ||
@@ -357,3 +357,3 @@ acc.push(curr); | ||
v = pq.removeMin(); | ||
if (parents.hasOwnProperty(v)) { | ||
if (Object.hasOwn(parents, v)) { | ||
result.setEdge(v, parents[v]); | ||
@@ -390,3 +390,3 @@ } else if (init) { | ||
g.successors(v).forEach(function(w) { | ||
if (!visited.hasOwnProperty(w)) { | ||
if (!Object.hasOwn(visited, w)) { | ||
dfs(w); | ||
@@ -412,3 +412,3 @@ entry.lowlink = Math.min(entry.lowlink, visited[w].lowlink); | ||
g.nodes().forEach(function(v) { | ||
if (!visited.hasOwnProperty(v)) { | ||
if (!Object.hasOwn(visited, v)) { | ||
dfs(v); | ||
@@ -428,7 +428,7 @@ } | ||
function visit(node) { | ||
if (stack.hasOwnProperty(node)) { | ||
if (Object.hasOwn(stack, node)) { | ||
throw new CycleException(); | ||
} | ||
if (!visited.hasOwnProperty(node)) { | ||
if (!Object.hasOwn(visited, node)) { | ||
stack[node] = true; | ||
@@ -490,3 +490,3 @@ visited[node] = true; | ||
has(key) { | ||
return this._keyIndices.hasOwnProperty(key); | ||
return Object.hasOwn(this._keyIndices, key); | ||
} | ||
@@ -529,3 +529,3 @@ | ||
key = String(key); | ||
if (!keyIndices.hasOwnProperty(key)) { | ||
if (!Object.hasOwn(keyIndices, key)) { | ||
var arr = this._arr; | ||
@@ -678,5 +678,5 @@ var index = arr.length; | ||
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 = Object.hasOwn(opts, "directed") ? opts.directed : true; | ||
this._isMultigraph = Object.hasOwn(opts, "multigraph") ? opts.multigraph : false; | ||
this._isCompound = Object.hasOwn(opts, "compound") ? opts.compound : false; | ||
} | ||
@@ -810,3 +810,3 @@ | ||
setNode(v, value) { | ||
if (this._nodes.hasOwnProperty(v)) { | ||
if (Object.hasOwn(this._nodes, v)) { | ||
if (arguments.length > 1) { | ||
@@ -844,3 +844,3 @@ this._nodes[v] = value; | ||
hasNode(v) { | ||
return this._nodes.hasOwnProperty(v); | ||
return Object.hasOwn(this._nodes, v); | ||
} | ||
@@ -856,3 +856,3 @@ | ||
var self = this; | ||
if (this._nodes.hasOwnProperty(v)) { | ||
if (Object.hasOwn(this._nodes, v)) { | ||
var removeEdge = e => self.removeEdge(self._edgeObjs[e]); | ||
@@ -1135,3 +1135,3 @@ delete this._nodes[v]; | ||
var e = edgeArgsToId(this._isDirected, v, w, name); | ||
if (this._edgeLabels.hasOwnProperty(e)) { | ||
if (Object.hasOwn(this._edgeLabels, e)) { | ||
if (valueSpecified) { | ||
@@ -1201,3 +1201,3 @@ this._edgeLabels[e] = value; | ||
: edgeArgsToId(this._isDirected, v, w, name)); | ||
return this._edgeLabels.hasOwnProperty(e); | ||
return Object.hasOwn(this._edgeLabels, e); | ||
} | ||
@@ -1408,5 +1408,5 @@ | ||
},{"./graph":16}],19:[function(require,module,exports){ | ||
module.exports = '2.2.3'; | ||
module.exports = '2.2.4'; | ||
},{}]},{},[1])(1) | ||
}); |
@@ -31,3 +31,3 @@ (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){ | ||
*/ | ||
var lib=require("./lib");module.exports={Graph:lib.Graph,json:require("./lib/json"),alg:require("./lib/alg"),version:lib.version}},{"./lib":17,"./lib/alg":8,"./lib/json":18}],2:[function(require,module,exports){module.exports=components;function components(g){var visited={};var cmpts=[];var cmpt;function dfs(v){if(visited.hasOwnProperty(v))return;visited[v]=true;cmpt.push(v);g.successors(v).forEach(dfs);g.predecessors(v).forEach(dfs)}g.nodes().forEach(function(v){cmpt=[];dfs(v);if(cmpt.length){cmpts.push(cmpt)}});return cmpts}},{}],3:[function(require,module,exports){module.exports=dfs; | ||
var lib=require("./lib");module.exports={Graph:lib.Graph,json:require("./lib/json"),alg:require("./lib/alg"),version:lib.version}},{"./lib":17,"./lib/alg":8,"./lib/json":18}],2:[function(require,module,exports){module.exports=components;function components(g){var visited={};var cmpts=[];var cmpt;function dfs(v){if(Object.hasOwn(visited,v))return;visited[v]=true;cmpt.push(v);g.successors(v).forEach(dfs);g.predecessors(v).forEach(dfs)}g.nodes().forEach(function(v){cmpt=[];dfs(v);if(cmpt.length){cmpts.push(cmpt)}});return cmpts}},{}],3:[function(require,module,exports){module.exports=dfs; | ||
/* | ||
@@ -40,6 +40,6 @@ * A helper that preforms a pre- or post-order traversal on the input graph | ||
* If the order is not "post", it will be treated as "pre". | ||
*/function dfs(g,vs,order){if(!Array.isArray(vs)){vs=[vs]}var navigation=g.isDirected()?v=>g.successors(v):v=>g.neighbors(v);var orderFunc=order==="post"?postOrderDfs:preOrderDfs;var acc=[];var visited={};vs.forEach(v=>{if(!g.hasNode(v)){throw new Error("Graph does not have node: "+v)}orderFunc(v,navigation,visited,acc)});return acc}function postOrderDfs(v,navigation,visited,acc){var stack=[[v,false]];while(stack.length>0){var curr=stack.pop();if(curr[1]){acc.push(curr[0])}else{if(!visited.hasOwnProperty(curr[0])){visited[curr[0]]=true;stack.push([curr[0],true]);forEachRight(navigation(curr[0]),w=>stack.push([w,false]))}}}}function preOrderDfs(v,navigation,visited,acc){var stack=[v];while(stack.length>0){var curr=stack.pop();if(!visited.hasOwnProperty(curr)){visited[curr]=true;acc.push(curr);forEachRight(navigation(curr),w=>stack.push(w))}}}function forEachRight(array,iteratee){var length=array.length;while(length--){iteratee(array[length],length,array)}return array}},{}],4:[function(require,module,exports){var dijkstra=require("./dijkstra");module.exports=dijkstraAll;function dijkstraAll(g,weightFunc,edgeFunc){return g.nodes().reduce(function(acc,v){acc[v]=dijkstra(g,v,weightFunc,edgeFunc);return acc},{})}},{"./dijkstra":5}],5:[function(require,module,exports){var PriorityQueue=require("../data/priority-queue");module.exports=dijkstra;var DEFAULT_WEIGHT_FUNC=()=>1;function dijkstra(g,source,weightFn,edgeFn){return runDijkstra(g,String(source),weightFn||DEFAULT_WEIGHT_FUNC,edgeFn||function(v){return g.outEdges(v)})}function runDijkstra(g,source,weightFn,edgeFn){var results={};var pq=new PriorityQueue;var v,vEntry;var updateNeighbors=function(edge){var w=edge.v!==v?edge.v:edge.w;var wEntry=results[w];var weight=weightFn(edge);var distance=vEntry.distance+weight;if(weight<0){throw new Error("dijkstra does not allow negative edge weights. "+"Bad edge: "+edge+" Weight: "+weight)}if(distance<wEntry.distance){wEntry.distance=distance;wEntry.predecessor=v;pq.decrease(w,distance)}};g.nodes().forEach(function(v){var distance=v===source?0:Number.POSITIVE_INFINITY;results[v]={distance:distance};pq.add(v,distance)});while(pq.size()>0){v=pq.removeMin();vEntry=results[v];if(vEntry.distance===Number.POSITIVE_INFINITY){break}edgeFn(v).forEach(updateNeighbors)}return results}},{"../data/priority-queue":15}],6:[function(require,module,exports){var tarjan=require("./tarjan");module.exports=findCycles;function findCycles(g){return tarjan(g).filter(function(cmpt){return cmpt.length>1||cmpt.length===1&&g.hasEdge(cmpt[0],cmpt[0])})}},{"./tarjan":13}],7:[function(require,module,exports){module.exports=floydWarshall;var DEFAULT_WEIGHT_FUNC=()=>1;function floydWarshall(g,weightFn,edgeFn){return runFloydWarshall(g,weightFn||DEFAULT_WEIGHT_FUNC,edgeFn||function(v){return g.outEdges(v)})}function runFloydWarshall(g,weightFn,edgeFn){var results={};var nodes=g.nodes();nodes.forEach(function(v){results[v]={};results[v][v]={distance:0};nodes.forEach(function(w){if(v!==w){results[v][w]={distance:Number.POSITIVE_INFINITY}}});edgeFn(v).forEach(function(edge){var w=edge.v===v?edge.w:edge.v;var d=weightFn(edge);results[v][w]={distance:d,predecessor:v}})});nodes.forEach(function(k){var rowK=results[k];nodes.forEach(function(i){var rowI=results[i];nodes.forEach(function(j){var ik=rowI[k];var kj=rowK[j];var ij=rowI[j];var altDistance=ik.distance+kj.distance;if(altDistance<ij.distance){ij.distance=altDistance;ij.predecessor=kj.predecessor}})})});return results}},{}],8:[function(require,module,exports){module.exports={components:require("./components"),dijkstra:require("./dijkstra"),dijkstraAll:require("./dijkstra-all"),findCycles:require("./find-cycles"),floydWarshall:require("./floyd-warshall"),isAcyclic:require("./is-acyclic"),postorder:require("./postorder"),preorder:require("./preorder"),prim:require("./prim"),tarjan:require("./tarjan"),topsort:require("./topsort")}},{"./components":2,"./dijkstra":5,"./dijkstra-all":4,"./find-cycles":6,"./floyd-warshall":7,"./is-acyclic":9,"./postorder":10,"./preorder":11,"./prim":12,"./tarjan":13,"./topsort":14}],9:[function(require,module,exports){var topsort=require("./topsort");module.exports=isAcyclic;function isAcyclic(g){try{topsort(g)}catch(e){if(e instanceof topsort.CycleException){return false}throw e}return true}},{"./topsort":14}],10:[function(require,module,exports){var dfs=require("./dfs");module.exports=postorder;function postorder(g,vs){return dfs(g,vs,"post")}},{"./dfs":3}],11:[function(require,module,exports){var dfs=require("./dfs");module.exports=preorder;function preorder(g,vs){return dfs(g,vs,"pre")}},{"./dfs":3}],12:[function(require,module,exports){var Graph=require("../graph");var PriorityQueue=require("../data/priority-queue");module.exports=prim;function prim(g,weightFunc){var result=new Graph;var parents={};var pq=new PriorityQueue;var v;function updateNeighbors(edge){var w=edge.v===v?edge.w:edge.v;var pri=pq.priority(w);if(pri!==undefined){var edgeWeight=weightFunc(edge);if(edgeWeight<pri){parents[w]=v;pq.decrease(w,edgeWeight)}}}if(g.nodeCount()===0){return result}g.nodes().forEach(function(v){pq.add(v,Number.POSITIVE_INFINITY);result.setNode(v)}); | ||
*/function dfs(g,vs,order){if(!Array.isArray(vs)){vs=[vs]}var navigation=g.isDirected()?v=>g.successors(v):v=>g.neighbors(v);var orderFunc=order==="post"?postOrderDfs:preOrderDfs;var acc=[];var visited={};vs.forEach(v=>{if(!g.hasNode(v)){throw new Error("Graph does not have node: "+v)}orderFunc(v,navigation,visited,acc)});return acc}function postOrderDfs(v,navigation,visited,acc){var stack=[[v,false]];while(stack.length>0){var curr=stack.pop();if(curr[1]){acc.push(curr[0])}else{if(!Object.hasOwn(visited,curr[0])){visited[curr[0]]=true;stack.push([curr[0],true]);forEachRight(navigation(curr[0]),w=>stack.push([w,false]))}}}}function preOrderDfs(v,navigation,visited,acc){var stack=[v];while(stack.length>0){var curr=stack.pop();if(!Object.hasOwn(visited,curr)){visited[curr]=true;acc.push(curr);forEachRight(navigation(curr),w=>stack.push(w))}}}function forEachRight(array,iteratee){var length=array.length;while(length--){iteratee(array[length],length,array)}return array}},{}],4:[function(require,module,exports){var dijkstra=require("./dijkstra");module.exports=dijkstraAll;function dijkstraAll(g,weightFunc,edgeFunc){return g.nodes().reduce(function(acc,v){acc[v]=dijkstra(g,v,weightFunc,edgeFunc);return acc},{})}},{"./dijkstra":5}],5:[function(require,module,exports){var PriorityQueue=require("../data/priority-queue");module.exports=dijkstra;var DEFAULT_WEIGHT_FUNC=()=>1;function dijkstra(g,source,weightFn,edgeFn){return runDijkstra(g,String(source),weightFn||DEFAULT_WEIGHT_FUNC,edgeFn||function(v){return g.outEdges(v)})}function runDijkstra(g,source,weightFn,edgeFn){var results={};var pq=new PriorityQueue;var v,vEntry;var updateNeighbors=function(edge){var w=edge.v!==v?edge.v:edge.w;var wEntry=results[w];var weight=weightFn(edge);var distance=vEntry.distance+weight;if(weight<0){throw new Error("dijkstra does not allow negative edge weights. "+"Bad edge: "+edge+" Weight: "+weight)}if(distance<wEntry.distance){wEntry.distance=distance;wEntry.predecessor=v;pq.decrease(w,distance)}};g.nodes().forEach(function(v){var distance=v===source?0:Number.POSITIVE_INFINITY;results[v]={distance:distance};pq.add(v,distance)});while(pq.size()>0){v=pq.removeMin();vEntry=results[v];if(vEntry.distance===Number.POSITIVE_INFINITY){break}edgeFn(v).forEach(updateNeighbors)}return results}},{"../data/priority-queue":15}],6:[function(require,module,exports){var tarjan=require("./tarjan");module.exports=findCycles;function findCycles(g){return tarjan(g).filter(function(cmpt){return cmpt.length>1||cmpt.length===1&&g.hasEdge(cmpt[0],cmpt[0])})}},{"./tarjan":13}],7:[function(require,module,exports){module.exports=floydWarshall;var DEFAULT_WEIGHT_FUNC=()=>1;function floydWarshall(g,weightFn,edgeFn){return runFloydWarshall(g,weightFn||DEFAULT_WEIGHT_FUNC,edgeFn||function(v){return g.outEdges(v)})}function runFloydWarshall(g,weightFn,edgeFn){var results={};var nodes=g.nodes();nodes.forEach(function(v){results[v]={};results[v][v]={distance:0};nodes.forEach(function(w){if(v!==w){results[v][w]={distance:Number.POSITIVE_INFINITY}}});edgeFn(v).forEach(function(edge){var w=edge.v===v?edge.w:edge.v;var d=weightFn(edge);results[v][w]={distance:d,predecessor:v}})});nodes.forEach(function(k){var rowK=results[k];nodes.forEach(function(i){var rowI=results[i];nodes.forEach(function(j){var ik=rowI[k];var kj=rowK[j];var ij=rowI[j];var altDistance=ik.distance+kj.distance;if(altDistance<ij.distance){ij.distance=altDistance;ij.predecessor=kj.predecessor}})})});return results}},{}],8:[function(require,module,exports){module.exports={components:require("./components"),dijkstra:require("./dijkstra"),dijkstraAll:require("./dijkstra-all"),findCycles:require("./find-cycles"),floydWarshall:require("./floyd-warshall"),isAcyclic:require("./is-acyclic"),postorder:require("./postorder"),preorder:require("./preorder"),prim:require("./prim"),tarjan:require("./tarjan"),topsort:require("./topsort")}},{"./components":2,"./dijkstra":5,"./dijkstra-all":4,"./find-cycles":6,"./floyd-warshall":7,"./is-acyclic":9,"./postorder":10,"./preorder":11,"./prim":12,"./tarjan":13,"./topsort":14}],9:[function(require,module,exports){var topsort=require("./topsort");module.exports=isAcyclic;function isAcyclic(g){try{topsort(g)}catch(e){if(e instanceof topsort.CycleException){return false}throw e}return true}},{"./topsort":14}],10:[function(require,module,exports){var dfs=require("./dfs");module.exports=postorder;function postorder(g,vs){return dfs(g,vs,"post")}},{"./dfs":3}],11:[function(require,module,exports){var dfs=require("./dfs");module.exports=preorder;function preorder(g,vs){return dfs(g,vs,"pre")}},{"./dfs":3}],12:[function(require,module,exports){var Graph=require("../graph");var PriorityQueue=require("../data/priority-queue");module.exports=prim;function prim(g,weightFunc){var result=new Graph;var parents={};var pq=new PriorityQueue;var v;function updateNeighbors(edge){var w=edge.v===v?edge.w:edge.v;var pri=pq.priority(w);if(pri!==undefined){var edgeWeight=weightFunc(edge);if(edgeWeight<pri){parents[w]=v;pq.decrease(w,edgeWeight)}}}if(g.nodeCount()===0){return result}g.nodes().forEach(function(v){pq.add(v,Number.POSITIVE_INFINITY);result.setNode(v)}); | ||
// Start from an arbitrary node | ||
pq.decrease(g.nodes()[0],0);var init=false;while(pq.size()>0){v=pq.removeMin();if(parents.hasOwnProperty(v)){result.setEdge(v,parents[v])}else if(init){throw new Error("Input graph is not connected: "+g)}else{init=true}g.nodeEdges(v).forEach(updateNeighbors)}return result}},{"../data/priority-queue":15,"../graph":16}],13:[function(require,module,exports){module.exports=tarjan;function tarjan(g){var index=0;var stack=[];var visited={};// node id -> { onStack, lowlink, index } | ||
var results=[];function dfs(v){var entry=visited[v]={onStack:true,lowlink:index,index:index++};stack.push(v);g.successors(v).forEach(function(w){if(!visited.hasOwnProperty(w)){dfs(w);entry.lowlink=Math.min(entry.lowlink,visited[w].lowlink)}else if(visited[w].onStack){entry.lowlink=Math.min(entry.lowlink,visited[w].index)}});if(entry.lowlink===entry.index){var cmpt=[];var w;do{w=stack.pop();visited[w].onStack=false;cmpt.push(w)}while(v!==w);results.push(cmpt)}}g.nodes().forEach(function(v){if(!visited.hasOwnProperty(v)){dfs(v)}});return results}},{}],14:[function(require,module,exports){function topsort(g){var visited={};var stack={};var results=[];function visit(node){if(stack.hasOwnProperty(node)){throw new CycleException}if(!visited.hasOwnProperty(node)){stack[node]=true;visited[node]=true;g.predecessors(node).forEach(visit);delete stack[node];results.push(node)}}g.sinks().forEach(visit);if(Object.keys(visited).length!==g.nodeCount()){throw new CycleException}return results}class CycleException extends Error{constructor(){super(...arguments)}}module.exports=topsort;topsort.CycleException=CycleException},{}],15:[function(require,module,exports){ | ||
pq.decrease(g.nodes()[0],0);var init=false;while(pq.size()>0){v=pq.removeMin();if(Object.hasOwn(parents,v)){result.setEdge(v,parents[v])}else if(init){throw new Error("Input graph is not connected: "+g)}else{init=true}g.nodeEdges(v).forEach(updateNeighbors)}return result}},{"../data/priority-queue":15,"../graph":16}],13:[function(require,module,exports){module.exports=tarjan;function tarjan(g){var index=0;var stack=[];var visited={};// node id -> { onStack, lowlink, index } | ||
var results=[];function dfs(v){var entry=visited[v]={onStack:true,lowlink:index,index:index++};stack.push(v);g.successors(v).forEach(function(w){if(!Object.hasOwn(visited,w)){dfs(w);entry.lowlink=Math.min(entry.lowlink,visited[w].lowlink)}else if(visited[w].onStack){entry.lowlink=Math.min(entry.lowlink,visited[w].index)}});if(entry.lowlink===entry.index){var cmpt=[];var w;do{w=stack.pop();visited[w].onStack=false;cmpt.push(w)}while(v!==w);results.push(cmpt)}}g.nodes().forEach(function(v){if(!Object.hasOwn(visited,v)){dfs(v)}});return results}},{}],14:[function(require,module,exports){function topsort(g){var visited={};var stack={};var results=[];function visit(node){if(Object.hasOwn(stack,node)){throw new CycleException}if(!Object.hasOwn(visited,node)){stack[node]=true;visited[node]=true;g.predecessors(node).forEach(visit);delete stack[node];results.push(node)}}g.sinks().forEach(visit);if(Object.keys(visited).length!==g.nodeCount()){throw new CycleException}return results}class CycleException extends Error{constructor(){super(...arguments)}}module.exports=topsort;topsort.CycleException=CycleException},{}],15:[function(require,module,exports){ | ||
/** | ||
@@ -61,3 +61,3 @@ * A min-priority queue data structure. This algorithm is derived from Cormen, | ||
* Returns `true` if **key** is in the queue and `false` if not. | ||
*/has(key){return this._keyIndices.hasOwnProperty(key)} | ||
*/has(key){return Object.hasOwn(this._keyIndices,key)} | ||
/** | ||
@@ -80,3 +80,3 @@ * Returns the priority for **key**. If **key** is not present in the queue | ||
* @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(!Object.hasOwn(keyIndices,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} | ||
/** | ||
@@ -123,3 +123,3 @@ * Removes and returns the smallest key in the queue. Takes `O(log n)` time. | ||
/* 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){ | ||
/* Number of edges in the graph. Should only be changed by the implementation. */_edgeCount=0;_parent;_children;constructor(opts){if(opts){this._isDirected=Object.hasOwn(opts,"directed")?opts.directed:true;this._isMultigraph=Object.hasOwn(opts,"multigraph")?opts.multigraph:false;this._isCompound=Object.hasOwn(opts,"compound")?opts.compound:false}if(this._isCompound){ | ||
// v -> parent | ||
@@ -179,3 +179,3 @@ this._parent={}; | ||
* 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(Object.hasOwn(this._nodes,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} | ||
/** | ||
@@ -187,3 +187,3 @@ * Gets the label of node with specified name. | ||
* Detects whether graph has a node with specified name or not. | ||
*/hasNode(v){return this._nodes.hasOwnProperty(v)} | ||
*/hasNode(v){return Object.hasOwn(this._nodes,v)} | ||
/** | ||
@@ -194,3 +194,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(Object.hasOwn(this._nodes,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} | ||
/** | ||
@@ -260,3 +260,3 @@ * Sets node p as a parent for node v if it is defined, or removes the | ||
* 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(Object.hasOwn(this._edgeLabels,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. | ||
@@ -278,3 +278,3 @@ // First ensure the nodes exist. | ||
* 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 Object.hasOwn(this._edgeLabels,e)} | ||
/** | ||
@@ -314,2 +314,2 @@ * Removes the specified edge from the graph. No subgraphs are considered. | ||
* // [ { 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.3"},{}]},{},[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.4"},{}]},{},[1])(1)}); |
@@ -9,3 +9,3 @@ module.exports = components; | ||
function dfs(v) { | ||
if (visited.hasOwnProperty(v)) return; | ||
if (Object.hasOwn(visited, v)) return; | ||
visited[v] = true; | ||
@@ -12,0 +12,0 @@ cmpt.push(v); |
@@ -39,3 +39,3 @@ module.exports = dfs; | ||
} else { | ||
if (!visited.hasOwnProperty(curr[0])) { | ||
if (!Object.hasOwn(visited, curr[0])) { | ||
visited[curr[0]] = true; | ||
@@ -53,3 +53,3 @@ stack.push([curr[0], true]); | ||
var curr = stack.pop(); | ||
if (!visited.hasOwnProperty(curr)) { | ||
if (!Object.hasOwn(visited, curr)) { | ||
visited[curr] = true; | ||
@@ -56,0 +56,0 @@ acc.push(curr); |
@@ -39,3 +39,3 @@ var Graph = require("../graph"); | ||
v = pq.removeMin(); | ||
if (parents.hasOwnProperty(v)) { | ||
if (Object.hasOwn(parents, v)) { | ||
result.setEdge(v, parents[v]); | ||
@@ -42,0 +42,0 @@ } else if (init) { |
@@ -18,3 +18,3 @@ module.exports = tarjan; | ||
g.successors(v).forEach(function(w) { | ||
if (!visited.hasOwnProperty(w)) { | ||
if (!Object.hasOwn(visited, w)) { | ||
dfs(w); | ||
@@ -40,3 +40,3 @@ entry.lowlink = Math.min(entry.lowlink, visited[w].lowlink); | ||
g.nodes().forEach(function(v) { | ||
if (!visited.hasOwnProperty(v)) { | ||
if (!Object.hasOwn(visited, v)) { | ||
dfs(v); | ||
@@ -43,0 +43,0 @@ } |
@@ -7,7 +7,7 @@ function topsort(g) { | ||
function visit(node) { | ||
if (stack.hasOwnProperty(node)) { | ||
if (Object.hasOwn(stack, node)) { | ||
throw new CycleException(); | ||
} | ||
if (!visited.hasOwnProperty(node)) { | ||
if (!Object.hasOwn(visited, node)) { | ||
stack[node] = true; | ||
@@ -14,0 +14,0 @@ visited[node] = true; |
@@ -30,3 +30,3 @@ /** | ||
has(key) { | ||
return this._keyIndices.hasOwnProperty(key); | ||
return Object.hasOwn(this._keyIndices, key); | ||
} | ||
@@ -69,3 +69,3 @@ | ||
key = String(key); | ||
if (!keyIndices.hasOwnProperty(key)) { | ||
if (!Object.hasOwn(keyIndices, key)) { | ||
var arr = this._arr; | ||
@@ -72,0 +72,0 @@ var index = arr.length; |
@@ -64,5 +64,5 @@ "use strict"; | ||
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 = Object.hasOwn(opts, "directed") ? opts.directed : true; | ||
this._isMultigraph = Object.hasOwn(opts, "multigraph") ? opts.multigraph : false; | ||
this._isCompound = Object.hasOwn(opts, "compound") ? opts.compound : false; | ||
} | ||
@@ -196,3 +196,3 @@ | ||
setNode(v, value) { | ||
if (this._nodes.hasOwnProperty(v)) { | ||
if (Object.hasOwn(this._nodes, v)) { | ||
if (arguments.length > 1) { | ||
@@ -230,3 +230,3 @@ this._nodes[v] = value; | ||
hasNode(v) { | ||
return this._nodes.hasOwnProperty(v); | ||
return Object.hasOwn(this._nodes, v); | ||
} | ||
@@ -242,3 +242,3 @@ | ||
var self = this; | ||
if (this._nodes.hasOwnProperty(v)) { | ||
if (Object.hasOwn(this._nodes, v)) { | ||
var removeEdge = e => self.removeEdge(self._edgeObjs[e]); | ||
@@ -521,3 +521,3 @@ delete this._nodes[v]; | ||
var e = edgeArgsToId(this._isDirected, v, w, name); | ||
if (this._edgeLabels.hasOwnProperty(e)) { | ||
if (Object.hasOwn(this._edgeLabels, e)) { | ||
if (valueSpecified) { | ||
@@ -587,3 +587,3 @@ this._edgeLabels[e] = value; | ||
: edgeArgsToId(this._isDirected, v, w, name)); | ||
return this._edgeLabels.hasOwnProperty(e); | ||
return Object.hasOwn(this._edgeLabels, e); | ||
} | ||
@@ -590,0 +590,0 @@ |
@@ -1,1 +0,1 @@ | ||
module.exports = '2.2.3'; | ||
module.exports = '2.2.4'; |
{ | ||
"name": "@dagrejs/graphlib", | ||
"version": "2.2.3", | ||
"version": "2.2.4", | ||
"description": "A directed and undirected multi-graph library", | ||
@@ -40,3 +40,3 @@ "author": "Chris Pettitt <cpettitt@gmail.com>", | ||
"nyc": "^15.1.0", | ||
"requirejs": "2.3.6", | ||
"requirejs": "2.3.7", | ||
"seedrandom": "3.0.5", | ||
@@ -43,0 +43,0 @@ "semver": "7.5.4", |
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
190139