@dagrejs/graphlib
Advanced tools
Comparing version 2.1.13 to 2.2.0
@@ -42,4 +42,8 @@ (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){ | ||
},{"./lib":17,"./lib/alg":8,"./lib/json":18}],2:[function(require,module,exports){ | ||
module.exports = components; | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = components; | ||
function components(g) { | ||
@@ -49,3 +53,2 @@ var visited = {}; | ||
var cmpt; | ||
function dfs(v) { | ||
@@ -58,4 +61,3 @@ if (visited.hasOwnProperty(v)) return; | ||
} | ||
g.nodes().forEach(function(v) { | ||
g.nodes().forEach(function (v) { | ||
cmpt = []; | ||
@@ -67,9 +69,13 @@ dfs(v); | ||
}); | ||
return cmpts; | ||
} | ||
module.exports = exports.default; | ||
},{}],3:[function(require,module,exports){ | ||
module.exports = dfs; | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = dfs; | ||
/* | ||
@@ -87,6 +93,4 @@ * A helper that preforms a pre- or post-order traversal on the input graph | ||
} | ||
var navigation = g.isDirected() ? v => g.successors(v) : v => g.neighbors(v); | ||
var orderFunc = order === "post" ? postOrderDfs : preOrderDfs; | ||
var acc = []; | ||
@@ -98,9 +102,6 @@ var visited = {}; | ||
} | ||
orderFunc(v, navigation, visited, acc); | ||
}); | ||
return acc; | ||
} | ||
function postOrderDfs(v, navigation, visited, acc) { | ||
@@ -121,3 +122,2 @@ var stack = [[v, false]]; | ||
} | ||
function preOrderDfs(v, navigation, visited, acc) { | ||
@@ -134,3 +134,2 @@ var stack = [v]; | ||
} | ||
function forEachRight(array, iteratee) { | ||
@@ -141,37 +140,43 @@ var length = array.length; | ||
} | ||
return array; | ||
} | ||
module.exports = exports.default; | ||
},{}],4:[function(require,module,exports){ | ||
var dijkstra = require("./dijkstra"); | ||
"use strict"; | ||
module.exports = dijkstraAll; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = dijkstraAll; | ||
var _dijkstra = _interopRequireDefault(require("./dijkstra.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
function dijkstraAll(g, weightFunc, edgeFunc) { | ||
return g.nodes().reduce(function(acc, v) { | ||
acc[v] = dijkstra(g, v, weightFunc, edgeFunc); | ||
return g.nodes().reduce(function (acc, v) { | ||
acc[v] = (0, _dijkstra.default)(g, v, weightFunc, edgeFunc); | ||
return acc; | ||
}, {}); | ||
} | ||
module.exports = exports.default; | ||
},{"./dijkstra":5}],5:[function(require,module,exports){ | ||
var PriorityQueue = require("../data/priority-queue"); | ||
},{"./dijkstra.js":5}],5:[function(require,module,exports){ | ||
"use strict"; | ||
module.exports = dijkstra; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = dijkstra; | ||
var _priorityQueue = _interopRequireDefault(require("../data/priority-queue.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
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); }); | ||
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 pq = new _priorityQueue.default(); | ||
var v, vEntry; | ||
var updateNeighbors = function(edge) { | ||
var updateNeighbors = function (edge) { | ||
var w = edge.v !== v ? edge.v : edge.w; | ||
@@ -181,8 +186,5 @@ var wEntry = results[w]; | ||
var distance = vEntry.distance + weight; | ||
if (weight < 0) { | ||
throw new Error("dijkstra does not allow negative edge weights. " + | ||
"Bad edge: " + edge + " Weight: " + weight); | ||
throw new Error("dijkstra does not allow negative edge weights. " + "Bad edge: " + edge + " Weight: " + weight); | ||
} | ||
if (distance < wEntry.distance) { | ||
@@ -194,9 +196,9 @@ wEntry.distance = distance; | ||
}; | ||
g.nodes().forEach(function(v) { | ||
g.nodes().forEach(function (v) { | ||
var distance = v === source ? 0 : Number.POSITIVE_INFINITY; | ||
results[v] = { distance: distance }; | ||
results[v] = { | ||
distance: distance | ||
}; | ||
pq.add(v, distance); | ||
}); | ||
while (pq.size() > 0) { | ||
@@ -208,55 +210,66 @@ v = pq.removeMin(); | ||
} | ||
edgeFn(v).forEach(updateNeighbors); | ||
} | ||
return results; | ||
} | ||
module.exports = exports.default; | ||
},{"../data/priority-queue":15}],6:[function(require,module,exports){ | ||
var tarjan = require("./tarjan"); | ||
},{"../data/priority-queue.js":15}],6:[function(require,module,exports){ | ||
"use strict"; | ||
module.exports = findCycles; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = findCycles; | ||
var _tarjan = _interopRequireDefault(require("./tarjan.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
function findCycles(g) { | ||
return tarjan(g).filter(function(cmpt) { | ||
return cmpt.length > 1 || (cmpt.length === 1 && g.hasEdge(cmpt[0], cmpt[0])); | ||
return (0, _tarjan.default)(g).filter(function (cmpt) { | ||
return cmpt.length > 1 || cmpt.length === 1 && g.hasEdge(cmpt[0], cmpt[0]); | ||
}); | ||
} | ||
module.exports = exports.default; | ||
},{"./tarjan":13}],7:[function(require,module,exports){ | ||
module.exports = floydWarshall; | ||
},{"./tarjan.js":13}],7:[function(require,module,exports){ | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = 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); }); | ||
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) { | ||
nodes.forEach(function (v) { | ||
results[v] = {}; | ||
results[v][v] = { distance: 0 }; | ||
nodes.forEach(function(w) { | ||
results[v][v] = { | ||
distance: 0 | ||
}; | ||
nodes.forEach(function (w) { | ||
if (v !== w) { | ||
results[v][w] = { distance: Number.POSITIVE_INFINITY }; | ||
results[v][w] = { | ||
distance: Number.POSITIVE_INFINITY | ||
}; | ||
} | ||
}); | ||
edgeFn(v).forEach(function(edge) { | ||
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 }; | ||
results[v][w] = { | ||
distance: d, | ||
predecessor: v | ||
}; | ||
}); | ||
}); | ||
nodes.forEach(function(k) { | ||
nodes.forEach(function (k) { | ||
var rowK = results[k]; | ||
nodes.forEach(function(i) { | ||
nodes.forEach(function (i) { | ||
var rowI = results[i]; | ||
nodes.forEach(function(j) { | ||
nodes.forEach(function (j) { | ||
var ik = rowI[k]; | ||
@@ -273,31 +286,105 @@ var kj = rowK[j]; | ||
}); | ||
return results; | ||
} | ||
module.exports = exports.default; | ||
},{}],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") | ||
}; | ||
"use strict"; | ||
},{"./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"); | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
Object.defineProperty(exports, "components", { | ||
enumerable: true, | ||
get: function () { | ||
return _components.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "dijkstra", { | ||
enumerable: true, | ||
get: function () { | ||
return _dijkstra.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "dijkstraAll", { | ||
enumerable: true, | ||
get: function () { | ||
return _dijkstraAll.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "findCycles", { | ||
enumerable: true, | ||
get: function () { | ||
return _findCycles.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "floydWarshall", { | ||
enumerable: true, | ||
get: function () { | ||
return _floydWarshall.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "isAcyclic", { | ||
enumerable: true, | ||
get: function () { | ||
return _isAcyclic.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "postorder", { | ||
enumerable: true, | ||
get: function () { | ||
return _postorder.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "preorder", { | ||
enumerable: true, | ||
get: function () { | ||
return _preorder.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "prim", { | ||
enumerable: true, | ||
get: function () { | ||
return _prim.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "tarjan", { | ||
enumerable: true, | ||
get: function () { | ||
return _tarjan.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "topsort", { | ||
enumerable: true, | ||
get: function () { | ||
return _topsort.default; | ||
} | ||
}); | ||
var _components = _interopRequireDefault(require("./components.js")); | ||
var _dijkstra = _interopRequireDefault(require("./dijkstra.js")); | ||
var _dijkstraAll = _interopRequireDefault(require("./dijkstra-all.js")); | ||
var _findCycles = _interopRequireDefault(require("./find-cycles.js")); | ||
var _floydWarshall = _interopRequireDefault(require("./floyd-warshall.js")); | ||
var _isAcyclic = _interopRequireDefault(require("./is-acyclic.js")); | ||
var _postorder = _interopRequireDefault(require("./postorder.js")); | ||
var _preorder = _interopRequireDefault(require("./preorder.js")); | ||
var _prim = _interopRequireDefault(require("./prim.js")); | ||
var _tarjan = _interopRequireDefault(require("./tarjan.js")); | ||
var _topsort = _interopRequireDefault(require("./topsort.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
module.exports = isAcyclic; | ||
},{"./components.js":2,"./dijkstra-all.js":4,"./dijkstra.js":5,"./find-cycles.js":6,"./floyd-warshall.js":7,"./is-acyclic.js":9,"./postorder.js":10,"./preorder.js":11,"./prim.js":12,"./tarjan.js":13,"./topsort.js":14}],9:[function(require,module,exports){ | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = isAcyclic; | ||
var _topsort = _interopRequireDefault(require("./topsort.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
function isAcyclic(g) { | ||
try { | ||
topsort(g); | ||
(0, _topsort.default)(g); | ||
} catch (e) { | ||
if (e instanceof topsort.CycleException) { | ||
if (e instanceof _topsort.default.CycleException) { | ||
return false; | ||
@@ -309,33 +396,47 @@ } | ||
} | ||
module.exports = exports.default; | ||
},{"./topsort":14}],10:[function(require,module,exports){ | ||
var dfs = require("./dfs"); | ||
},{"./topsort.js":14}],10:[function(require,module,exports){ | ||
"use strict"; | ||
module.exports = postorder; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = postorder; | ||
var _dfs = _interopRequireDefault(require("./dfs.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
function postorder(g, vs) { | ||
return dfs(g, vs, "post"); | ||
return (0, _dfs.default)(g, vs, "post"); | ||
} | ||
module.exports = exports.default; | ||
},{"./dfs":3}],11:[function(require,module,exports){ | ||
var dfs = require("./dfs"); | ||
},{"./dfs.js":3}],11:[function(require,module,exports){ | ||
"use strict"; | ||
module.exports = preorder; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = preorder; | ||
var _dfs = _interopRequireDefault(require("./dfs.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
function preorder(g, vs) { | ||
return dfs(g, vs, "pre"); | ||
return (0, _dfs.default)(g, vs, "pre"); | ||
} | ||
module.exports = exports.default; | ||
},{"./dfs":3}],12:[function(require,module,exports){ | ||
var Graph = require("../graph"); | ||
var PriorityQueue = require("../data/priority-queue"); | ||
},{"./dfs.js":3}],12:[function(require,module,exports){ | ||
"use strict"; | ||
module.exports = prim; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = prim; | ||
var _graph = _interopRequireDefault(require("../graph.js")); | ||
var _priorityQueue = _interopRequireDefault(require("../data/priority-queue.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
function prim(g, weightFunc) { | ||
var result = new Graph(); | ||
var result = new _graph.default(); | ||
var parents = {}; | ||
var pq = new PriorityQueue(); | ||
var pq = new _priorityQueue.default(); | ||
var v; | ||
function updateNeighbors(edge) { | ||
@@ -352,8 +453,6 @@ var w = edge.v === v ? edge.w : edge.v; | ||
} | ||
if (g.nodeCount() === 0) { | ||
return result; | ||
} | ||
g.nodes().forEach(function(v) { | ||
g.nodes().forEach(function (v) { | ||
pq.add(v, Number.POSITIVE_INFINITY); | ||
@@ -365,3 +464,2 @@ result.setNode(v); | ||
pq.decrease(g.nodes()[0], 0); | ||
var init = false; | ||
@@ -377,12 +475,15 @@ while (pq.size() > 0) { | ||
} | ||
g.nodeEdges(v).forEach(updateNeighbors); | ||
} | ||
return result; | ||
} | ||
module.exports = exports.default; | ||
},{"../data/priority-queue":15,"../graph":16}],13:[function(require,module,exports){ | ||
module.exports = tarjan; | ||
},{"../data/priority-queue.js":15,"../graph.js":16}],13:[function(require,module,exports){ | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = tarjan; | ||
function tarjan(g) { | ||
@@ -393,3 +494,2 @@ var index = 0; | ||
var results = []; | ||
function dfs(v) { | ||
@@ -402,4 +502,3 @@ var entry = visited[v] = { | ||
stack.push(v); | ||
g.successors(v).forEach(function(w) { | ||
g.successors(v).forEach(function (w) { | ||
if (!visited.hasOwnProperty(w)) { | ||
@@ -412,3 +511,2 @@ dfs(w); | ||
}); | ||
if (entry.lowlink === entry.index) { | ||
@@ -425,4 +523,3 @@ var cmpt = []; | ||
} | ||
g.nodes().forEach(function(v) { | ||
g.nodes().forEach(function (v) { | ||
if (!visited.hasOwnProperty(v)) { | ||
@@ -432,7 +529,13 @@ dfs(v); | ||
}); | ||
return results; | ||
} | ||
module.exports = exports.default; | ||
},{}],14:[function(require,module,exports){ | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = topsort; | ||
function topsort(g) { | ||
@@ -442,3 +545,2 @@ var visited = {}; | ||
var results = []; | ||
function visit(node) { | ||
@@ -448,3 +550,2 @@ if (stack.hasOwnProperty(node)) { | ||
} | ||
if (!visited.hasOwnProperty(node)) { | ||
@@ -458,12 +559,8 @@ stack[node] = true; | ||
} | ||
g.sinks().forEach(visit); | ||
if (Object.keys(visited).length !== g.nodeCount()) { | ||
throw new CycleException(); | ||
} | ||
return results; | ||
} | ||
class CycleException extends Error { | ||
@@ -474,7 +571,12 @@ constructor() { | ||
} | ||
module.exports = topsort; | ||
topsort.CycleException = CycleException; | ||
module.exports = exports.default; | ||
},{}],15:[function(require,module,exports){ | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = void 0; | ||
/** | ||
@@ -502,3 +604,5 @@ * A min-priority queue data structure. This algorithm is derived from Cormen, | ||
keys() { | ||
return this.#arr.map(function(x) { return x.key; }); | ||
return this.#arr.map(function (x) { | ||
return x.key; | ||
}); | ||
} | ||
@@ -552,3 +656,6 @@ | ||
keyIndices[key] = index; | ||
arr.push({key: key, priority: priority}); | ||
arr.push({ | ||
key: key, | ||
priority: priority | ||
}); | ||
this.#decrease(index); | ||
@@ -581,4 +688,3 @@ return true; | ||
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); | ||
throw new Error("New priority is greater than current priority. " + "Key: " + key + " Old: " + this.#arr[index].priority + " New: " + priority); | ||
} | ||
@@ -588,3 +694,2 @@ this.#arr[index].priority = priority; | ||
} | ||
#heapify(i) { | ||
@@ -606,3 +711,2 @@ var arr = this.#arr; | ||
} | ||
#decrease(index) { | ||
@@ -621,3 +725,2 @@ var arr = this.#arr; | ||
} | ||
#swap(i, j) { | ||
@@ -634,8 +737,12 @@ var arr = this.#arr; | ||
} | ||
exports.default = PriorityQueue; | ||
module.exports = exports.default; | ||
module.exports = PriorityQueue; | ||
},{}],16:[function(require,module,exports){ | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = void 0; | ||
var DEFAULT_EDGE_NAME = "\x00"; | ||
@@ -695,7 +802,4 @@ var GRAPH_NODE = "\x00"; | ||
#edgeCount = 0; | ||
#parent; | ||
#children; | ||
constructor(opts) { | ||
@@ -707,3 +811,2 @@ if (opts) { | ||
} | ||
if (this.#isCompound) { | ||
@@ -757,3 +860,2 @@ // v -> parent | ||
/* === Node functions ========== */ | ||
@@ -773,3 +875,2 @@ | ||
} | ||
return this; | ||
@@ -820,3 +921,3 @@ } | ||
var self = this; | ||
vs.forEach(function(v) { | ||
vs.forEach(function (v) { | ||
if (args.length > 1) { | ||
@@ -844,3 +945,2 @@ self.setNode(v, value); | ||
} | ||
this.#nodes[v] = arguments.length > 1 ? value : this.#defaultNodeLabelFn(v); | ||
@@ -889,3 +989,3 @@ if (this.#isCompound) { | ||
delete this.#parent[v]; | ||
this.children(v).forEach(function(child) { | ||
this.children(v).forEach(function (child) { | ||
self.setParent(child); | ||
@@ -916,3 +1016,2 @@ }); | ||
} | ||
if (parent === undefined) { | ||
@@ -925,10 +1024,7 @@ parent = GRAPH_NODE; | ||
if (ancestor === v) { | ||
throw new Error("Setting " + parent+ " as parent of " + v + | ||
" would create a cycle"); | ||
throw new Error("Setting " + parent + " as parent of " + v + " would create a cycle"); | ||
} | ||
} | ||
this.setNode(parent); | ||
} | ||
this.setNode(v); | ||
@@ -940,3 +1036,2 @@ this.#removeFromParentsChildList(v); | ||
} | ||
#removeFromParentsChildList(v) { | ||
@@ -1012,7 +1107,5 @@ delete this.#children[this.#parent[v]][v]; | ||
} | ||
return Array.from(union.values()); | ||
} | ||
} | ||
isLeaf(v) { | ||
@@ -1040,7 +1133,5 @@ var neighbors; | ||
}); | ||
copy.setGraph(this.graph()); | ||
var self = this; | ||
Object.entries(this.#nodes).forEach(function([v, value]) { | ||
Object.entries(this.#nodes).forEach(function ([v, value]) { | ||
if (filter(v)) { | ||
@@ -1050,4 +1141,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)) { | ||
@@ -1057,3 +1147,2 @@ copy.setEdge(e, self.edge(e)); | ||
}); | ||
var parents = {}; | ||
@@ -1071,7 +1160,5 @@ function findParent(v) { | ||
} | ||
if (this.#isCompound) { | ||
copy.nodes().forEach(v => copy.setParent(v, findParent(v))); | ||
} | ||
return copy; | ||
@@ -1094,3 +1181,2 @@ } | ||
} | ||
return this; | ||
@@ -1124,3 +1210,3 @@ } | ||
var args = arguments; | ||
vs.reduce(function(v, w) { | ||
vs.reduce(function (v, w) { | ||
if (args.length > 1) { | ||
@@ -1146,3 +1232,2 @@ self.setEdge(v, w, value); | ||
var arg0 = arguments[0]; | ||
if (typeof arg0 === "object" && arg0 !== null && "v" in arg0) { | ||
@@ -1165,3 +1250,2 @@ v = arg0.v; | ||
} | ||
v = "" + v; | ||
@@ -1172,3 +1256,2 @@ w = "" + w; | ||
} | ||
var e = edgeArgsToId(this.#isDirected, v, w, name); | ||
@@ -1181,3 +1264,2 @@ if (this.#edgeLabels.hasOwnProperty(e)) { | ||
} | ||
if (name !== undefined && !this.#isMultigraph) { | ||
@@ -1191,5 +1273,3 @@ throw new Error("Cannot set a named edge when isMultigraph = false"); | ||
this.setNode(w); | ||
this.#edgeLabels[e] = valueSpecified ? value : this.#defaultEdgeLabelFn(v, w, name); | ||
var edgeObj = edgeArgsToObj(this.#isDirected, v, w, name); | ||
@@ -1199,3 +1279,2 @@ // Ensure we add undirected edges in a consistent way. | ||
w = edgeObj.w; | ||
Object.freeze(edgeObj); | ||
@@ -1216,5 +1295,3 @@ this.#edgeObjs[e] = edgeObj; | ||
edge(v, w, name) { | ||
var e = (arguments.length === 1 | ||
? edgeObjToId(this.#isDirected, arguments[0]) | ||
: edgeArgsToId(this.#isDirected, v, w, name)); | ||
var e = arguments.length === 1 ? edgeObjToId(this.#isDirected, arguments[0]) : edgeArgsToId(this.#isDirected, v, w, name); | ||
return this.#edgeLabels[e]; | ||
@@ -1230,5 +1307,6 @@ } | ||
if (typeof edge !== "object") { | ||
return {label: edge}; | ||
return { | ||
label: edge | ||
}; | ||
} | ||
return edge; | ||
@@ -1242,5 +1320,3 @@ } | ||
hasEdge(v, w, name) { | ||
var e = (arguments.length === 1 | ||
? edgeObjToId(this.#isDirected, arguments[0]) | ||
: edgeArgsToId(this.#isDirected, v, w, name)); | ||
var e = arguments.length === 1 ? edgeObjToId(this.#isDirected, arguments[0]) : edgeArgsToId(this.#isDirected, v, w, name); | ||
return this.#edgeLabels.hasOwnProperty(e); | ||
@@ -1254,5 +1330,3 @@ } | ||
removeEdge(v, w, name) { | ||
var e = (arguments.length === 1 | ||
? edgeObjToId(this.#isDirected, arguments[0]) | ||
: edgeArgsToId(this.#isDirected, v, w, name)); | ||
var e = arguments.length === 1 ? edgeObjToId(this.#isDirected, arguments[0]) : edgeArgsToId(this.#isDirected, v, w, name); | ||
var edge = this.#edgeObjs[e]; | ||
@@ -1317,3 +1391,3 @@ if (edge) { | ||
} | ||
exports.default = Graph; | ||
function incrementOrInitEntry(map, k) { | ||
@@ -1326,7 +1400,7 @@ if (map[k]) { | ||
} | ||
function decrementOrRemoveEntry(map, k) { | ||
if (!--map[k]) { delete map[k]; } | ||
if (! --map[k]) { | ||
delete map[k]; | ||
} | ||
} | ||
function edgeArgsToId(isDirected, v_, w_, name) { | ||
@@ -1340,6 +1414,4 @@ var v = "" + v_; | ||
} | ||
return v + EDGE_KEY_DELIM + w + EDGE_KEY_DELIM + | ||
(name === undefined ? DEFAULT_EDGE_NAME : name); | ||
return v + EDGE_KEY_DELIM + w + EDGE_KEY_DELIM + (name === undefined ? DEFAULT_EDGE_NAME : name); | ||
} | ||
function edgeArgsToObj(isDirected, v_, w_, name) { | ||
@@ -1353,3 +1425,6 @@ var v = "" + v_; | ||
} | ||
var edgeObj = { v: v, w: w }; | ||
var edgeObj = { | ||
v: v, | ||
w: w | ||
}; | ||
if (name) { | ||
@@ -1360,24 +1435,46 @@ edgeObj.name = name; | ||
} | ||
function edgeObjToId(isDirected, edgeObj) { | ||
return edgeArgsToId(isDirected, edgeObj.v, edgeObj.w, edgeObj.name); | ||
} | ||
module.exports = exports.default; | ||
module.exports = Graph; | ||
},{}],17:[function(require,module,exports){ | ||
// Includes only the "core" of graphlib | ||
module.exports = { | ||
Graph: require("./graph"), | ||
version: require("./version") | ||
}; | ||
"use strict"; | ||
},{"./graph":16,"./version":19}],18:[function(require,module,exports){ | ||
var Graph = require("./graph"); | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
Object.defineProperty(exports, "Graph", { | ||
enumerable: true, | ||
get: function () { | ||
return _graph.default; | ||
} | ||
}); | ||
exports.json = exports.alg = void 0; | ||
Object.defineProperty(exports, "version", { | ||
enumerable: true, | ||
get: function () { | ||
return _version.default; | ||
} | ||
}); | ||
var _graph = _interopRequireDefault(require("./graph.js")); | ||
var _version = _interopRequireDefault(require("./version.js")); | ||
var _json = _interopRequireWildcard(require("./json.js")); | ||
exports.json = _json; | ||
var _alg = _interopRequireWildcard(require("./alg/index.js")); | ||
exports.alg = _alg; | ||
function _getRequireWildcardCache(e) { if ("function" != typeof WeakMap) return null; var r = new WeakMap(), t = new WeakMap(); return (_getRequireWildcardCache = function (e) { return e ? t : r; })(e); } | ||
function _interopRequireWildcard(e, r) { if (!r && e && e.__esModule) return e; if (null === e || "object" != typeof e && "function" != typeof e) return { default: e }; var t = _getRequireWildcardCache(r); if (t && t.has(e)) return t.get(e); var n = { __proto__: null }, a = Object.defineProperty && Object.getOwnPropertyDescriptor; for (var u in e) if ("default" !== u && Object.prototype.hasOwnProperty.call(e, u)) { var i = a ? Object.getOwnPropertyDescriptor(e, u) : null; i && (i.get || i.set) ? Object.defineProperty(n, u, i) : n[u] = e[u]; } return n.default = e, t && t.set(e, n), n; } | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
module.exports = { | ||
write: write, | ||
read: read | ||
}; | ||
},{"./alg/index.js":8,"./graph.js":16,"./json.js":18,"./version.js":19}],18:[function(require,module,exports){ | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.read = read; | ||
exports.write = write; | ||
var _graph = _interopRequireDefault(require("./graph.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
/** | ||
@@ -1397,3 +1494,2 @@ * Creates a JSON representation of the graph that can be serialized to a string with | ||
}; | ||
if (g.graph() !== undefined) { | ||
@@ -1404,8 +1500,9 @@ json.value = structuredClone(g.graph()); | ||
} | ||
function writeNodes(g) { | ||
return g.nodes().map(function(v) { | ||
return g.nodes().map(function (v) { | ||
var nodeValue = g.node(v); | ||
var parent = g.parent(v); | ||
var node = { v: v }; | ||
var node = { | ||
v: v | ||
}; | ||
if (nodeValue !== undefined) { | ||
@@ -1420,7 +1517,9 @@ node.value = nodeValue; | ||
} | ||
function writeEdges(g) { | ||
return g.edges().map(function(e) { | ||
return g.edges().map(function (e) { | ||
var edgeValue = g.edge(e); | ||
var edge = { v: e.v, w: e.w }; | ||
var edge = { | ||
v: e.v, | ||
w: e.w | ||
}; | ||
if (e.name !== undefined) { | ||
@@ -1447,4 +1546,4 @@ edge.name = e.name; | ||
function read(json) { | ||
var g = new Graph(json.options).setGraph(json.value); | ||
json.nodes.forEach(function(entry) { | ||
var g = new _graph.default(json.options).setGraph(json.value); | ||
json.nodes.forEach(function (entry) { | ||
g.setNode(entry.v, entry.value); | ||
@@ -1455,4 +1554,8 @@ if (entry.parent) { | ||
}); | ||
json.edges.forEach(function(entry) { | ||
g.setEdge({ v: entry.v, w: entry.w, name: entry.name }, entry.value); | ||
json.edges.forEach(function (entry) { | ||
g.setEdge({ | ||
v: entry.v, | ||
w: entry.w, | ||
name: entry.name | ||
}, entry.value); | ||
}); | ||
@@ -1462,6 +1565,13 @@ return g; | ||
},{"./graph":16}],19:[function(require,module,exports){ | ||
module.exports = '2.1.13'; | ||
},{"./graph.js":16}],19:[function(require,module,exports){ | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = void 0; | ||
var _default = exports.default = '2.2.0'; | ||
module.exports = exports.default; | ||
},{}]},{},[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){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=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}module.exports=exports.default},{}],3:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=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(!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}module.exports=exports.default},{}],4:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=dijkstraAll;var _dijkstra=_interopRequireDefault(require("./dijkstra.js"));function _interopRequireDefault(obj){return obj&&obj.__esModule?obj:{default:obj}}function dijkstraAll(g,weightFunc,edgeFunc){return g.nodes().reduce(function(acc,v){acc[v]=(0,_dijkstra.default)(g,v,weightFunc,edgeFunc);return acc},{})}module.exports=exports.default},{"./dijkstra.js":5}],5:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=dijkstra;var _priorityQueue=_interopRequireDefault(require("../data/priority-queue.js"));function _interopRequireDefault(obj){return obj&&obj.__esModule?obj:{default:obj}}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.default;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}module.exports=exports.default},{"../data/priority-queue.js":15}],6:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=findCycles;var _tarjan=_interopRequireDefault(require("./tarjan.js"));function _interopRequireDefault(obj){return obj&&obj.__esModule?obj:{default:obj}}function findCycles(g){return(0,_tarjan.default)(g).filter(function(cmpt){return cmpt.length>1||cmpt.length===1&&g.hasEdge(cmpt[0],cmpt[0])})}module.exports=exports.default},{"./tarjan.js":13}],7:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=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}module.exports=exports.default},{}],8:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});Object.defineProperty(exports,"components",{enumerable:true,get:function(){return _components.default}});Object.defineProperty(exports,"dijkstra",{enumerable:true,get:function(){return _dijkstra.default}});Object.defineProperty(exports,"dijkstraAll",{enumerable:true,get:function(){return _dijkstraAll.default}});Object.defineProperty(exports,"findCycles",{enumerable:true,get:function(){return _findCycles.default}});Object.defineProperty(exports,"floydWarshall",{enumerable:true,get:function(){return _floydWarshall.default}});Object.defineProperty(exports,"isAcyclic",{enumerable:true,get:function(){return _isAcyclic.default}});Object.defineProperty(exports,"postorder",{enumerable:true,get:function(){return _postorder.default}});Object.defineProperty(exports,"preorder",{enumerable:true,get:function(){return _preorder.default}});Object.defineProperty(exports,"prim",{enumerable:true,get:function(){return _prim.default}});Object.defineProperty(exports,"tarjan",{enumerable:true,get:function(){return _tarjan.default}});Object.defineProperty(exports,"topsort",{enumerable:true,get:function(){return _topsort.default}});var _components=_interopRequireDefault(require("./components.js"));var _dijkstra=_interopRequireDefault(require("./dijkstra.js"));var _dijkstraAll=_interopRequireDefault(require("./dijkstra-all.js"));var _findCycles=_interopRequireDefault(require("./find-cycles.js"));var _floydWarshall=_interopRequireDefault(require("./floyd-warshall.js"));var _isAcyclic=_interopRequireDefault(require("./is-acyclic.js"));var _postorder=_interopRequireDefault(require("./postorder.js"));var _preorder=_interopRequireDefault(require("./preorder.js"));var _prim=_interopRequireDefault(require("./prim.js"));var _tarjan=_interopRequireDefault(require("./tarjan.js"));var _topsort=_interopRequireDefault(require("./topsort.js"));function _interopRequireDefault(obj){return obj&&obj.__esModule?obj:{default:obj}}},{"./components.js":2,"./dijkstra-all.js":4,"./dijkstra.js":5,"./find-cycles.js":6,"./floyd-warshall.js":7,"./is-acyclic.js":9,"./postorder.js":10,"./preorder.js":11,"./prim.js":12,"./tarjan.js":13,"./topsort.js":14}],9:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=isAcyclic;var _topsort=_interopRequireDefault(require("./topsort.js"));function _interopRequireDefault(obj){return obj&&obj.__esModule?obj:{default:obj}}function isAcyclic(g){try{(0,_topsort.default)(g)}catch(e){if(e instanceof _topsort.default.CycleException){return false}throw e}return true}module.exports=exports.default},{"./topsort.js":14}],10:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=postorder;var _dfs=_interopRequireDefault(require("./dfs.js"));function _interopRequireDefault(obj){return obj&&obj.__esModule?obj:{default:obj}}function postorder(g,vs){return(0,_dfs.default)(g,vs,"post")}module.exports=exports.default},{"./dfs.js":3}],11:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=preorder;var _dfs=_interopRequireDefault(require("./dfs.js"));function _interopRequireDefault(obj){return obj&&obj.__esModule?obj:{default:obj}}function preorder(g,vs){return(0,_dfs.default)(g,vs,"pre")}module.exports=exports.default},{"./dfs.js":3}],12:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=prim;var _graph=_interopRequireDefault(require("../graph.js"));var _priorityQueue=_interopRequireDefault(require("../data/priority-queue.js"));function _interopRequireDefault(obj){return obj&&obj.__esModule?obj:{default:obj}}function prim(g,weightFunc){var result=new _graph.default;var parents={};var pq=new _priorityQueue.default;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(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}module.exports=exports.default},{"../data/priority-queue.js":15,"../graph.js":16}],13:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=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}module.exports=exports.default},{}],14:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=topsort;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)}}topsort.CycleException=CycleException;module.exports=exports.default},{}],15:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=void 0; | ||
/** | ||
@@ -51,4 +51,3 @@ * A min-priority queue data structure. This algorithm is derived from Cormen, | ||
* have its priority decreased in O(log n) time. | ||
*/ | ||
class PriorityQueue{#arr=[];#keyIndices={}; | ||
*/class PriorityQueue{#arr=[];#keyIndices={}; | ||
/** | ||
@@ -90,3 +89,3 @@ * Returns the number of elements in the queue. Takes `O(1)` time. | ||
* @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}}exports.default=PriorityQueue;module.exports=exports.default},{}],16:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=void 0;var DEFAULT_EDGE_NAME="\0";var GRAPH_NODE="\0";var EDGE_KEY_DELIM=""; | ||
// Implementation notes: | ||
@@ -292,5 +291,3 @@ // | ||
* Complexity: O(|E|). | ||
*/nodeEdges(v,w){var inEdges=this.inEdges(v,w);if(inEdges){return inEdges.concat(this.outEdges(v,w))}}}function incrementOrInitEntry(map,k){if(map[k]){map[k]++}else{map[k]=1}}function decrementOrRemoveEntry(map,k){if(!--map[k]){delete map[k]}}function edgeArgsToId(isDirected,v_,w_,name){var v=""+v_;var w=""+w_;if(!isDirected&&v>w){var tmp=v;v=w;w=tmp}return v+EDGE_KEY_DELIM+w+EDGE_KEY_DELIM+(name===undefined?DEFAULT_EDGE_NAME:name)}function edgeArgsToObj(isDirected,v_,w_,name){var v=""+v_;var w=""+w_;if(!isDirected&&v>w){var tmp=v;v=w;w=tmp}var edgeObj={v:v,w:w};if(name){edgeObj.name=name}return edgeObj}function edgeObjToId(isDirected,edgeObj){return edgeArgsToId(isDirected,edgeObj.v,edgeObj.w,edgeObj.name)}module.exports=Graph},{}],17:[function(require,module,exports){ | ||
// Includes only the "core" of graphlib | ||
module.exports={Graph:require("./graph"),version:require("./version")}},{"./graph":16,"./version":19}],18:[function(require,module,exports){var Graph=require("./graph");module.exports={write:write,read:read}; | ||
*/nodeEdges(v,w){var inEdges=this.inEdges(v,w);if(inEdges){return inEdges.concat(this.outEdges(v,w))}}}exports.default=Graph;function incrementOrInitEntry(map,k){if(map[k]){map[k]++}else{map[k]=1}}function decrementOrRemoveEntry(map,k){if(!--map[k]){delete map[k]}}function edgeArgsToId(isDirected,v_,w_,name){var v=""+v_;var w=""+w_;if(!isDirected&&v>w){var tmp=v;v=w;w=tmp}return v+EDGE_KEY_DELIM+w+EDGE_KEY_DELIM+(name===undefined?DEFAULT_EDGE_NAME:name)}function edgeArgsToObj(isDirected,v_,w_,name){var v=""+v_;var w=""+w_;if(!isDirected&&v>w){var tmp=v;v=w;w=tmp}var edgeObj={v:v,w:w};if(name){edgeObj.name=name}return edgeObj}function edgeObjToId(isDirected,edgeObj){return edgeArgsToId(isDirected,edgeObj.v,edgeObj.w,edgeObj.name)}module.exports=exports.default},{}],17:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});Object.defineProperty(exports,"Graph",{enumerable:true,get:function(){return _graph.default}});exports.json=exports.alg=void 0;Object.defineProperty(exports,"version",{enumerable:true,get:function(){return _version.default}});var _graph=_interopRequireDefault(require("./graph.js"));var _version=_interopRequireDefault(require("./version.js"));var _json=_interopRequireWildcard(require("./json.js"));exports.json=_json;var _alg=_interopRequireWildcard(require("./alg/index.js"));exports.alg=_alg;function _getRequireWildcardCache(e){if("function"!=typeof WeakMap)return null;var r=new WeakMap,t=new WeakMap;return(_getRequireWildcardCache=function(e){return e?t:r})(e)}function _interopRequireWildcard(e,r){if(!r&&e&&e.__esModule)return e;if(null===e||"object"!=typeof e&&"function"!=typeof e)return{default:e};var t=_getRequireWildcardCache(r);if(t&&t.has(e))return t.get(e);var n={__proto__:null},a=Object.defineProperty&&Object.getOwnPropertyDescriptor;for(var u in e)if("default"!==u&&Object.prototype.hasOwnProperty.call(e,u)){var i=a?Object.getOwnPropertyDescriptor(e,u):null;i&&(i.get||i.set)?Object.defineProperty(n,u,i):n[u]=e[u]}return n.default=e,t&&t.set(e,n),n}function _interopRequireDefault(obj){return obj&&obj.__esModule?obj:{default:obj}}},{"./alg/index.js":8,"./graph.js":16,"./json.js":18,"./version.js":19}],18:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.read=read;exports.write=write;var _graph=_interopRequireDefault(require("./graph.js"));function _interopRequireDefault(obj){return obj&&obj.__esModule?obj:{default:obj}} | ||
/** | ||
@@ -309,2 +306,2 @@ * Creates a JSON representation of the graph that can be serialized to a string with | ||
* // [ { 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.1.13"},{}]},{},[1])(1)}); | ||
*/function read(json){var g=new _graph.default(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.js":16}],19:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=void 0;var _default=exports.default="2.2.0";module.exports=exports.default},{}]},{},[1])(1)}); |
@@ -42,4 +42,8 @@ (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){ | ||
},{"./lib":17,"./lib/alg":8,"./lib/json":18}],2:[function(require,module,exports){ | ||
module.exports = components; | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = components; | ||
function components(g) { | ||
@@ -49,3 +53,2 @@ var visited = {}; | ||
var cmpt; | ||
function dfs(v) { | ||
@@ -58,4 +61,3 @@ if (visited.hasOwnProperty(v)) return; | ||
} | ||
g.nodes().forEach(function(v) { | ||
g.nodes().forEach(function (v) { | ||
cmpt = []; | ||
@@ -67,9 +69,13 @@ dfs(v); | ||
}); | ||
return cmpts; | ||
} | ||
module.exports = exports.default; | ||
},{}],3:[function(require,module,exports){ | ||
module.exports = dfs; | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = dfs; | ||
/* | ||
@@ -87,6 +93,4 @@ * A helper that preforms a pre- or post-order traversal on the input graph | ||
} | ||
var navigation = g.isDirected() ? v => g.successors(v) : v => g.neighbors(v); | ||
var orderFunc = order === "post" ? postOrderDfs : preOrderDfs; | ||
var acc = []; | ||
@@ -98,9 +102,6 @@ var visited = {}; | ||
} | ||
orderFunc(v, navigation, visited, acc); | ||
}); | ||
return acc; | ||
} | ||
function postOrderDfs(v, navigation, visited, acc) { | ||
@@ -121,3 +122,2 @@ var stack = [[v, false]]; | ||
} | ||
function preOrderDfs(v, navigation, visited, acc) { | ||
@@ -134,3 +134,2 @@ var stack = [v]; | ||
} | ||
function forEachRight(array, iteratee) { | ||
@@ -141,37 +140,43 @@ var length = array.length; | ||
} | ||
return array; | ||
} | ||
module.exports = exports.default; | ||
},{}],4:[function(require,module,exports){ | ||
var dijkstra = require("./dijkstra"); | ||
"use strict"; | ||
module.exports = dijkstraAll; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = dijkstraAll; | ||
var _dijkstra = _interopRequireDefault(require("./dijkstra.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
function dijkstraAll(g, weightFunc, edgeFunc) { | ||
return g.nodes().reduce(function(acc, v) { | ||
acc[v] = dijkstra(g, v, weightFunc, edgeFunc); | ||
return g.nodes().reduce(function (acc, v) { | ||
acc[v] = (0, _dijkstra.default)(g, v, weightFunc, edgeFunc); | ||
return acc; | ||
}, {}); | ||
} | ||
module.exports = exports.default; | ||
},{"./dijkstra":5}],5:[function(require,module,exports){ | ||
var PriorityQueue = require("../data/priority-queue"); | ||
},{"./dijkstra.js":5}],5:[function(require,module,exports){ | ||
"use strict"; | ||
module.exports = dijkstra; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = dijkstra; | ||
var _priorityQueue = _interopRequireDefault(require("../data/priority-queue.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
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); }); | ||
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 pq = new _priorityQueue.default(); | ||
var v, vEntry; | ||
var updateNeighbors = function(edge) { | ||
var updateNeighbors = function (edge) { | ||
var w = edge.v !== v ? edge.v : edge.w; | ||
@@ -181,8 +186,5 @@ var wEntry = results[w]; | ||
var distance = vEntry.distance + weight; | ||
if (weight < 0) { | ||
throw new Error("dijkstra does not allow negative edge weights. " + | ||
"Bad edge: " + edge + " Weight: " + weight); | ||
throw new Error("dijkstra does not allow negative edge weights. " + "Bad edge: " + edge + " Weight: " + weight); | ||
} | ||
if (distance < wEntry.distance) { | ||
@@ -194,9 +196,9 @@ wEntry.distance = distance; | ||
}; | ||
g.nodes().forEach(function(v) { | ||
g.nodes().forEach(function (v) { | ||
var distance = v === source ? 0 : Number.POSITIVE_INFINITY; | ||
results[v] = { distance: distance }; | ||
results[v] = { | ||
distance: distance | ||
}; | ||
pq.add(v, distance); | ||
}); | ||
while (pq.size() > 0) { | ||
@@ -208,55 +210,66 @@ v = pq.removeMin(); | ||
} | ||
edgeFn(v).forEach(updateNeighbors); | ||
} | ||
return results; | ||
} | ||
module.exports = exports.default; | ||
},{"../data/priority-queue":15}],6:[function(require,module,exports){ | ||
var tarjan = require("./tarjan"); | ||
},{"../data/priority-queue.js":15}],6:[function(require,module,exports){ | ||
"use strict"; | ||
module.exports = findCycles; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = findCycles; | ||
var _tarjan = _interopRequireDefault(require("./tarjan.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
function findCycles(g) { | ||
return tarjan(g).filter(function(cmpt) { | ||
return cmpt.length > 1 || (cmpt.length === 1 && g.hasEdge(cmpt[0], cmpt[0])); | ||
return (0, _tarjan.default)(g).filter(function (cmpt) { | ||
return cmpt.length > 1 || cmpt.length === 1 && g.hasEdge(cmpt[0], cmpt[0]); | ||
}); | ||
} | ||
module.exports = exports.default; | ||
},{"./tarjan":13}],7:[function(require,module,exports){ | ||
module.exports = floydWarshall; | ||
},{"./tarjan.js":13}],7:[function(require,module,exports){ | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = 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); }); | ||
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) { | ||
nodes.forEach(function (v) { | ||
results[v] = {}; | ||
results[v][v] = { distance: 0 }; | ||
nodes.forEach(function(w) { | ||
results[v][v] = { | ||
distance: 0 | ||
}; | ||
nodes.forEach(function (w) { | ||
if (v !== w) { | ||
results[v][w] = { distance: Number.POSITIVE_INFINITY }; | ||
results[v][w] = { | ||
distance: Number.POSITIVE_INFINITY | ||
}; | ||
} | ||
}); | ||
edgeFn(v).forEach(function(edge) { | ||
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 }; | ||
results[v][w] = { | ||
distance: d, | ||
predecessor: v | ||
}; | ||
}); | ||
}); | ||
nodes.forEach(function(k) { | ||
nodes.forEach(function (k) { | ||
var rowK = results[k]; | ||
nodes.forEach(function(i) { | ||
nodes.forEach(function (i) { | ||
var rowI = results[i]; | ||
nodes.forEach(function(j) { | ||
nodes.forEach(function (j) { | ||
var ik = rowI[k]; | ||
@@ -273,31 +286,105 @@ var kj = rowK[j]; | ||
}); | ||
return results; | ||
} | ||
module.exports = exports.default; | ||
},{}],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") | ||
}; | ||
"use strict"; | ||
},{"./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"); | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
Object.defineProperty(exports, "components", { | ||
enumerable: true, | ||
get: function () { | ||
return _components.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "dijkstra", { | ||
enumerable: true, | ||
get: function () { | ||
return _dijkstra.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "dijkstraAll", { | ||
enumerable: true, | ||
get: function () { | ||
return _dijkstraAll.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "findCycles", { | ||
enumerable: true, | ||
get: function () { | ||
return _findCycles.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "floydWarshall", { | ||
enumerable: true, | ||
get: function () { | ||
return _floydWarshall.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "isAcyclic", { | ||
enumerable: true, | ||
get: function () { | ||
return _isAcyclic.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "postorder", { | ||
enumerable: true, | ||
get: function () { | ||
return _postorder.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "preorder", { | ||
enumerable: true, | ||
get: function () { | ||
return _preorder.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "prim", { | ||
enumerable: true, | ||
get: function () { | ||
return _prim.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "tarjan", { | ||
enumerable: true, | ||
get: function () { | ||
return _tarjan.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "topsort", { | ||
enumerable: true, | ||
get: function () { | ||
return _topsort.default; | ||
} | ||
}); | ||
var _components = _interopRequireDefault(require("./components.js")); | ||
var _dijkstra = _interopRequireDefault(require("./dijkstra.js")); | ||
var _dijkstraAll = _interopRequireDefault(require("./dijkstra-all.js")); | ||
var _findCycles = _interopRequireDefault(require("./find-cycles.js")); | ||
var _floydWarshall = _interopRequireDefault(require("./floyd-warshall.js")); | ||
var _isAcyclic = _interopRequireDefault(require("./is-acyclic.js")); | ||
var _postorder = _interopRequireDefault(require("./postorder.js")); | ||
var _preorder = _interopRequireDefault(require("./preorder.js")); | ||
var _prim = _interopRequireDefault(require("./prim.js")); | ||
var _tarjan = _interopRequireDefault(require("./tarjan.js")); | ||
var _topsort = _interopRequireDefault(require("./topsort.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
module.exports = isAcyclic; | ||
},{"./components.js":2,"./dijkstra-all.js":4,"./dijkstra.js":5,"./find-cycles.js":6,"./floyd-warshall.js":7,"./is-acyclic.js":9,"./postorder.js":10,"./preorder.js":11,"./prim.js":12,"./tarjan.js":13,"./topsort.js":14}],9:[function(require,module,exports){ | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = isAcyclic; | ||
var _topsort = _interopRequireDefault(require("./topsort.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
function isAcyclic(g) { | ||
try { | ||
topsort(g); | ||
(0, _topsort.default)(g); | ||
} catch (e) { | ||
if (e instanceof topsort.CycleException) { | ||
if (e instanceof _topsort.default.CycleException) { | ||
return false; | ||
@@ -309,33 +396,47 @@ } | ||
} | ||
module.exports = exports.default; | ||
},{"./topsort":14}],10:[function(require,module,exports){ | ||
var dfs = require("./dfs"); | ||
},{"./topsort.js":14}],10:[function(require,module,exports){ | ||
"use strict"; | ||
module.exports = postorder; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = postorder; | ||
var _dfs = _interopRequireDefault(require("./dfs.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
function postorder(g, vs) { | ||
return dfs(g, vs, "post"); | ||
return (0, _dfs.default)(g, vs, "post"); | ||
} | ||
module.exports = exports.default; | ||
},{"./dfs":3}],11:[function(require,module,exports){ | ||
var dfs = require("./dfs"); | ||
},{"./dfs.js":3}],11:[function(require,module,exports){ | ||
"use strict"; | ||
module.exports = preorder; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = preorder; | ||
var _dfs = _interopRequireDefault(require("./dfs.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
function preorder(g, vs) { | ||
return dfs(g, vs, "pre"); | ||
return (0, _dfs.default)(g, vs, "pre"); | ||
} | ||
module.exports = exports.default; | ||
},{"./dfs":3}],12:[function(require,module,exports){ | ||
var Graph = require("../graph"); | ||
var PriorityQueue = require("../data/priority-queue"); | ||
},{"./dfs.js":3}],12:[function(require,module,exports){ | ||
"use strict"; | ||
module.exports = prim; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = prim; | ||
var _graph = _interopRequireDefault(require("../graph.js")); | ||
var _priorityQueue = _interopRequireDefault(require("../data/priority-queue.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
function prim(g, weightFunc) { | ||
var result = new Graph(); | ||
var result = new _graph.default(); | ||
var parents = {}; | ||
var pq = new PriorityQueue(); | ||
var pq = new _priorityQueue.default(); | ||
var v; | ||
function updateNeighbors(edge) { | ||
@@ -352,8 +453,6 @@ var w = edge.v === v ? edge.w : edge.v; | ||
} | ||
if (g.nodeCount() === 0) { | ||
return result; | ||
} | ||
g.nodes().forEach(function(v) { | ||
g.nodes().forEach(function (v) { | ||
pq.add(v, Number.POSITIVE_INFINITY); | ||
@@ -365,3 +464,2 @@ result.setNode(v); | ||
pq.decrease(g.nodes()[0], 0); | ||
var init = false; | ||
@@ -377,12 +475,15 @@ while (pq.size() > 0) { | ||
} | ||
g.nodeEdges(v).forEach(updateNeighbors); | ||
} | ||
return result; | ||
} | ||
module.exports = exports.default; | ||
},{"../data/priority-queue":15,"../graph":16}],13:[function(require,module,exports){ | ||
module.exports = tarjan; | ||
},{"../data/priority-queue.js":15,"../graph.js":16}],13:[function(require,module,exports){ | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = tarjan; | ||
function tarjan(g) { | ||
@@ -393,3 +494,2 @@ var index = 0; | ||
var results = []; | ||
function dfs(v) { | ||
@@ -402,4 +502,3 @@ var entry = visited[v] = { | ||
stack.push(v); | ||
g.successors(v).forEach(function(w) { | ||
g.successors(v).forEach(function (w) { | ||
if (!visited.hasOwnProperty(w)) { | ||
@@ -412,3 +511,2 @@ dfs(w); | ||
}); | ||
if (entry.lowlink === entry.index) { | ||
@@ -425,4 +523,3 @@ var cmpt = []; | ||
} | ||
g.nodes().forEach(function(v) { | ||
g.nodes().forEach(function (v) { | ||
if (!visited.hasOwnProperty(v)) { | ||
@@ -432,7 +529,13 @@ dfs(v); | ||
}); | ||
return results; | ||
} | ||
module.exports = exports.default; | ||
},{}],14:[function(require,module,exports){ | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = topsort; | ||
function topsort(g) { | ||
@@ -442,3 +545,2 @@ var visited = {}; | ||
var results = []; | ||
function visit(node) { | ||
@@ -448,3 +550,2 @@ if (stack.hasOwnProperty(node)) { | ||
} | ||
if (!visited.hasOwnProperty(node)) { | ||
@@ -458,12 +559,8 @@ stack[node] = true; | ||
} | ||
g.sinks().forEach(visit); | ||
if (Object.keys(visited).length !== g.nodeCount()) { | ||
throw new CycleException(); | ||
} | ||
return results; | ||
} | ||
class CycleException extends Error { | ||
@@ -474,7 +571,12 @@ constructor() { | ||
} | ||
module.exports = topsort; | ||
topsort.CycleException = CycleException; | ||
module.exports = exports.default; | ||
},{}],15:[function(require,module,exports){ | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = void 0; | ||
/** | ||
@@ -502,3 +604,5 @@ * A min-priority queue data structure. This algorithm is derived from Cormen, | ||
keys() { | ||
return this.#arr.map(function(x) { return x.key; }); | ||
return this.#arr.map(function (x) { | ||
return x.key; | ||
}); | ||
} | ||
@@ -552,3 +656,6 @@ | ||
keyIndices[key] = index; | ||
arr.push({key: key, priority: priority}); | ||
arr.push({ | ||
key: key, | ||
priority: priority | ||
}); | ||
this.#decrease(index); | ||
@@ -581,4 +688,3 @@ return true; | ||
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); | ||
throw new Error("New priority is greater than current priority. " + "Key: " + key + " Old: " + this.#arr[index].priority + " New: " + priority); | ||
} | ||
@@ -588,3 +694,2 @@ this.#arr[index].priority = priority; | ||
} | ||
#heapify(i) { | ||
@@ -606,3 +711,2 @@ var arr = this.#arr; | ||
} | ||
#decrease(index) { | ||
@@ -621,3 +725,2 @@ var arr = this.#arr; | ||
} | ||
#swap(i, j) { | ||
@@ -634,8 +737,12 @@ var arr = this.#arr; | ||
} | ||
exports.default = PriorityQueue; | ||
module.exports = exports.default; | ||
module.exports = PriorityQueue; | ||
},{}],16:[function(require,module,exports){ | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = void 0; | ||
var DEFAULT_EDGE_NAME = "\x00"; | ||
@@ -695,7 +802,4 @@ var GRAPH_NODE = "\x00"; | ||
#edgeCount = 0; | ||
#parent; | ||
#children; | ||
constructor(opts) { | ||
@@ -707,3 +811,2 @@ if (opts) { | ||
} | ||
if (this.#isCompound) { | ||
@@ -757,3 +860,2 @@ // v -> parent | ||
/* === Node functions ========== */ | ||
@@ -773,3 +875,2 @@ | ||
} | ||
return this; | ||
@@ -820,3 +921,3 @@ } | ||
var self = this; | ||
vs.forEach(function(v) { | ||
vs.forEach(function (v) { | ||
if (args.length > 1) { | ||
@@ -844,3 +945,2 @@ self.setNode(v, value); | ||
} | ||
this.#nodes[v] = arguments.length > 1 ? value : this.#defaultNodeLabelFn(v); | ||
@@ -889,3 +989,3 @@ if (this.#isCompound) { | ||
delete this.#parent[v]; | ||
this.children(v).forEach(function(child) { | ||
this.children(v).forEach(function (child) { | ||
self.setParent(child); | ||
@@ -916,3 +1016,2 @@ }); | ||
} | ||
if (parent === undefined) { | ||
@@ -925,10 +1024,7 @@ parent = GRAPH_NODE; | ||
if (ancestor === v) { | ||
throw new Error("Setting " + parent+ " as parent of " + v + | ||
" would create a cycle"); | ||
throw new Error("Setting " + parent + " as parent of " + v + " would create a cycle"); | ||
} | ||
} | ||
this.setNode(parent); | ||
} | ||
this.setNode(v); | ||
@@ -940,3 +1036,2 @@ this.#removeFromParentsChildList(v); | ||
} | ||
#removeFromParentsChildList(v) { | ||
@@ -1012,7 +1107,5 @@ delete this.#children[this.#parent[v]][v]; | ||
} | ||
return Array.from(union.values()); | ||
} | ||
} | ||
isLeaf(v) { | ||
@@ -1040,7 +1133,5 @@ var neighbors; | ||
}); | ||
copy.setGraph(this.graph()); | ||
var self = this; | ||
Object.entries(this.#nodes).forEach(function([v, value]) { | ||
Object.entries(this.#nodes).forEach(function ([v, value]) { | ||
if (filter(v)) { | ||
@@ -1050,4 +1141,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)) { | ||
@@ -1057,3 +1147,2 @@ copy.setEdge(e, self.edge(e)); | ||
}); | ||
var parents = {}; | ||
@@ -1071,7 +1160,5 @@ function findParent(v) { | ||
} | ||
if (this.#isCompound) { | ||
copy.nodes().forEach(v => copy.setParent(v, findParent(v))); | ||
} | ||
return copy; | ||
@@ -1094,3 +1181,2 @@ } | ||
} | ||
return this; | ||
@@ -1124,3 +1210,3 @@ } | ||
var args = arguments; | ||
vs.reduce(function(v, w) { | ||
vs.reduce(function (v, w) { | ||
if (args.length > 1) { | ||
@@ -1146,3 +1232,2 @@ self.setEdge(v, w, value); | ||
var arg0 = arguments[0]; | ||
if (typeof arg0 === "object" && arg0 !== null && "v" in arg0) { | ||
@@ -1165,3 +1250,2 @@ v = arg0.v; | ||
} | ||
v = "" + v; | ||
@@ -1172,3 +1256,2 @@ w = "" + w; | ||
} | ||
var e = edgeArgsToId(this.#isDirected, v, w, name); | ||
@@ -1181,3 +1264,2 @@ if (this.#edgeLabels.hasOwnProperty(e)) { | ||
} | ||
if (name !== undefined && !this.#isMultigraph) { | ||
@@ -1191,5 +1273,3 @@ throw new Error("Cannot set a named edge when isMultigraph = false"); | ||
this.setNode(w); | ||
this.#edgeLabels[e] = valueSpecified ? value : this.#defaultEdgeLabelFn(v, w, name); | ||
var edgeObj = edgeArgsToObj(this.#isDirected, v, w, name); | ||
@@ -1199,3 +1279,2 @@ // Ensure we add undirected edges in a consistent way. | ||
w = edgeObj.w; | ||
Object.freeze(edgeObj); | ||
@@ -1216,5 +1295,3 @@ this.#edgeObjs[e] = edgeObj; | ||
edge(v, w, name) { | ||
var e = (arguments.length === 1 | ||
? edgeObjToId(this.#isDirected, arguments[0]) | ||
: edgeArgsToId(this.#isDirected, v, w, name)); | ||
var e = arguments.length === 1 ? edgeObjToId(this.#isDirected, arguments[0]) : edgeArgsToId(this.#isDirected, v, w, name); | ||
return this.#edgeLabels[e]; | ||
@@ -1230,5 +1307,6 @@ } | ||
if (typeof edge !== "object") { | ||
return {label: edge}; | ||
return { | ||
label: edge | ||
}; | ||
} | ||
return edge; | ||
@@ -1242,5 +1320,3 @@ } | ||
hasEdge(v, w, name) { | ||
var e = (arguments.length === 1 | ||
? edgeObjToId(this.#isDirected, arguments[0]) | ||
: edgeArgsToId(this.#isDirected, v, w, name)); | ||
var e = arguments.length === 1 ? edgeObjToId(this.#isDirected, arguments[0]) : edgeArgsToId(this.#isDirected, v, w, name); | ||
return this.#edgeLabels.hasOwnProperty(e); | ||
@@ -1254,5 +1330,3 @@ } | ||
removeEdge(v, w, name) { | ||
var e = (arguments.length === 1 | ||
? edgeObjToId(this.#isDirected, arguments[0]) | ||
: edgeArgsToId(this.#isDirected, v, w, name)); | ||
var e = arguments.length === 1 ? edgeObjToId(this.#isDirected, arguments[0]) : edgeArgsToId(this.#isDirected, v, w, name); | ||
var edge = this.#edgeObjs[e]; | ||
@@ -1317,3 +1391,3 @@ if (edge) { | ||
} | ||
exports.default = Graph; | ||
function incrementOrInitEntry(map, k) { | ||
@@ -1326,7 +1400,7 @@ if (map[k]) { | ||
} | ||
function decrementOrRemoveEntry(map, k) { | ||
if (!--map[k]) { delete map[k]; } | ||
if (! --map[k]) { | ||
delete map[k]; | ||
} | ||
} | ||
function edgeArgsToId(isDirected, v_, w_, name) { | ||
@@ -1340,6 +1414,4 @@ var v = "" + v_; | ||
} | ||
return v + EDGE_KEY_DELIM + w + EDGE_KEY_DELIM + | ||
(name === undefined ? DEFAULT_EDGE_NAME : name); | ||
return v + EDGE_KEY_DELIM + w + EDGE_KEY_DELIM + (name === undefined ? DEFAULT_EDGE_NAME : name); | ||
} | ||
function edgeArgsToObj(isDirected, v_, w_, name) { | ||
@@ -1353,3 +1425,6 @@ var v = "" + v_; | ||
} | ||
var edgeObj = { v: v, w: w }; | ||
var edgeObj = { | ||
v: v, | ||
w: w | ||
}; | ||
if (name) { | ||
@@ -1360,24 +1435,46 @@ edgeObj.name = name; | ||
} | ||
function edgeObjToId(isDirected, edgeObj) { | ||
return edgeArgsToId(isDirected, edgeObj.v, edgeObj.w, edgeObj.name); | ||
} | ||
module.exports = exports.default; | ||
module.exports = Graph; | ||
},{}],17:[function(require,module,exports){ | ||
// Includes only the "core" of graphlib | ||
module.exports = { | ||
Graph: require("./graph"), | ||
version: require("./version") | ||
}; | ||
"use strict"; | ||
},{"./graph":16,"./version":19}],18:[function(require,module,exports){ | ||
var Graph = require("./graph"); | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
Object.defineProperty(exports, "Graph", { | ||
enumerable: true, | ||
get: function () { | ||
return _graph.default; | ||
} | ||
}); | ||
exports.json = exports.alg = void 0; | ||
Object.defineProperty(exports, "version", { | ||
enumerable: true, | ||
get: function () { | ||
return _version.default; | ||
} | ||
}); | ||
var _graph = _interopRequireDefault(require("./graph.js")); | ||
var _version = _interopRequireDefault(require("./version.js")); | ||
var _json = _interopRequireWildcard(require("./json.js")); | ||
exports.json = _json; | ||
var _alg = _interopRequireWildcard(require("./alg/index.js")); | ||
exports.alg = _alg; | ||
function _getRequireWildcardCache(e) { if ("function" != typeof WeakMap) return null; var r = new WeakMap(), t = new WeakMap(); return (_getRequireWildcardCache = function (e) { return e ? t : r; })(e); } | ||
function _interopRequireWildcard(e, r) { if (!r && e && e.__esModule) return e; if (null === e || "object" != typeof e && "function" != typeof e) return { default: e }; var t = _getRequireWildcardCache(r); if (t && t.has(e)) return t.get(e); var n = { __proto__: null }, a = Object.defineProperty && Object.getOwnPropertyDescriptor; for (var u in e) if ("default" !== u && Object.prototype.hasOwnProperty.call(e, u)) { var i = a ? Object.getOwnPropertyDescriptor(e, u) : null; i && (i.get || i.set) ? Object.defineProperty(n, u, i) : n[u] = e[u]; } return n.default = e, t && t.set(e, n), n; } | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
module.exports = { | ||
write: write, | ||
read: read | ||
}; | ||
},{"./alg/index.js":8,"./graph.js":16,"./json.js":18,"./version.js":19}],18:[function(require,module,exports){ | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.read = read; | ||
exports.write = write; | ||
var _graph = _interopRequireDefault(require("./graph.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
/** | ||
@@ -1397,3 +1494,2 @@ * Creates a JSON representation of the graph that can be serialized to a string with | ||
}; | ||
if (g.graph() !== undefined) { | ||
@@ -1404,8 +1500,9 @@ json.value = structuredClone(g.graph()); | ||
} | ||
function writeNodes(g) { | ||
return g.nodes().map(function(v) { | ||
return g.nodes().map(function (v) { | ||
var nodeValue = g.node(v); | ||
var parent = g.parent(v); | ||
var node = { v: v }; | ||
var node = { | ||
v: v | ||
}; | ||
if (nodeValue !== undefined) { | ||
@@ -1420,7 +1517,9 @@ node.value = nodeValue; | ||
} | ||
function writeEdges(g) { | ||
return g.edges().map(function(e) { | ||
return g.edges().map(function (e) { | ||
var edgeValue = g.edge(e); | ||
var edge = { v: e.v, w: e.w }; | ||
var edge = { | ||
v: e.v, | ||
w: e.w | ||
}; | ||
if (e.name !== undefined) { | ||
@@ -1447,4 +1546,4 @@ edge.name = e.name; | ||
function read(json) { | ||
var g = new Graph(json.options).setGraph(json.value); | ||
json.nodes.forEach(function(entry) { | ||
var g = new _graph.default(json.options).setGraph(json.value); | ||
json.nodes.forEach(function (entry) { | ||
g.setNode(entry.v, entry.value); | ||
@@ -1455,4 +1554,8 @@ if (entry.parent) { | ||
}); | ||
json.edges.forEach(function(entry) { | ||
g.setEdge({ v: entry.v, w: entry.w, name: entry.name }, entry.value); | ||
json.edges.forEach(function (entry) { | ||
g.setEdge({ | ||
v: entry.v, | ||
w: entry.w, | ||
name: entry.name | ||
}, entry.value); | ||
}); | ||
@@ -1462,6 +1565,13 @@ return g; | ||
},{"./graph":16}],19:[function(require,module,exports){ | ||
module.exports = '2.1.13'; | ||
},{"./graph.js":16}],19:[function(require,module,exports){ | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = void 0; | ||
var _default = exports.default = '2.2.0'; | ||
module.exports = exports.default; | ||
},{}]},{},[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){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=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}module.exports=exports.default},{}],3:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=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(!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}module.exports=exports.default},{}],4:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=dijkstraAll;var _dijkstra=_interopRequireDefault(require("./dijkstra.js"));function _interopRequireDefault(obj){return obj&&obj.__esModule?obj:{default:obj}}function dijkstraAll(g,weightFunc,edgeFunc){return g.nodes().reduce(function(acc,v){acc[v]=(0,_dijkstra.default)(g,v,weightFunc,edgeFunc);return acc},{})}module.exports=exports.default},{"./dijkstra.js":5}],5:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=dijkstra;var _priorityQueue=_interopRequireDefault(require("../data/priority-queue.js"));function _interopRequireDefault(obj){return obj&&obj.__esModule?obj:{default:obj}}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.default;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}module.exports=exports.default},{"../data/priority-queue.js":15}],6:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=findCycles;var _tarjan=_interopRequireDefault(require("./tarjan.js"));function _interopRequireDefault(obj){return obj&&obj.__esModule?obj:{default:obj}}function findCycles(g){return(0,_tarjan.default)(g).filter(function(cmpt){return cmpt.length>1||cmpt.length===1&&g.hasEdge(cmpt[0],cmpt[0])})}module.exports=exports.default},{"./tarjan.js":13}],7:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=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}module.exports=exports.default},{}],8:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});Object.defineProperty(exports,"components",{enumerable:true,get:function(){return _components.default}});Object.defineProperty(exports,"dijkstra",{enumerable:true,get:function(){return _dijkstra.default}});Object.defineProperty(exports,"dijkstraAll",{enumerable:true,get:function(){return _dijkstraAll.default}});Object.defineProperty(exports,"findCycles",{enumerable:true,get:function(){return _findCycles.default}});Object.defineProperty(exports,"floydWarshall",{enumerable:true,get:function(){return _floydWarshall.default}});Object.defineProperty(exports,"isAcyclic",{enumerable:true,get:function(){return _isAcyclic.default}});Object.defineProperty(exports,"postorder",{enumerable:true,get:function(){return _postorder.default}});Object.defineProperty(exports,"preorder",{enumerable:true,get:function(){return _preorder.default}});Object.defineProperty(exports,"prim",{enumerable:true,get:function(){return _prim.default}});Object.defineProperty(exports,"tarjan",{enumerable:true,get:function(){return _tarjan.default}});Object.defineProperty(exports,"topsort",{enumerable:true,get:function(){return _topsort.default}});var _components=_interopRequireDefault(require("./components.js"));var _dijkstra=_interopRequireDefault(require("./dijkstra.js"));var _dijkstraAll=_interopRequireDefault(require("./dijkstra-all.js"));var _findCycles=_interopRequireDefault(require("./find-cycles.js"));var _floydWarshall=_interopRequireDefault(require("./floyd-warshall.js"));var _isAcyclic=_interopRequireDefault(require("./is-acyclic.js"));var _postorder=_interopRequireDefault(require("./postorder.js"));var _preorder=_interopRequireDefault(require("./preorder.js"));var _prim=_interopRequireDefault(require("./prim.js"));var _tarjan=_interopRequireDefault(require("./tarjan.js"));var _topsort=_interopRequireDefault(require("./topsort.js"));function _interopRequireDefault(obj){return obj&&obj.__esModule?obj:{default:obj}}},{"./components.js":2,"./dijkstra-all.js":4,"./dijkstra.js":5,"./find-cycles.js":6,"./floyd-warshall.js":7,"./is-acyclic.js":9,"./postorder.js":10,"./preorder.js":11,"./prim.js":12,"./tarjan.js":13,"./topsort.js":14}],9:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=isAcyclic;var _topsort=_interopRequireDefault(require("./topsort.js"));function _interopRequireDefault(obj){return obj&&obj.__esModule?obj:{default:obj}}function isAcyclic(g){try{(0,_topsort.default)(g)}catch(e){if(e instanceof _topsort.default.CycleException){return false}throw e}return true}module.exports=exports.default},{"./topsort.js":14}],10:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=postorder;var _dfs=_interopRequireDefault(require("./dfs.js"));function _interopRequireDefault(obj){return obj&&obj.__esModule?obj:{default:obj}}function postorder(g,vs){return(0,_dfs.default)(g,vs,"post")}module.exports=exports.default},{"./dfs.js":3}],11:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=preorder;var _dfs=_interopRequireDefault(require("./dfs.js"));function _interopRequireDefault(obj){return obj&&obj.__esModule?obj:{default:obj}}function preorder(g,vs){return(0,_dfs.default)(g,vs,"pre")}module.exports=exports.default},{"./dfs.js":3}],12:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=prim;var _graph=_interopRequireDefault(require("../graph.js"));var _priorityQueue=_interopRequireDefault(require("../data/priority-queue.js"));function _interopRequireDefault(obj){return obj&&obj.__esModule?obj:{default:obj}}function prim(g,weightFunc){var result=new _graph.default;var parents={};var pq=new _priorityQueue.default;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(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}module.exports=exports.default},{"../data/priority-queue.js":15,"../graph.js":16}],13:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=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}module.exports=exports.default},{}],14:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=topsort;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)}}topsort.CycleException=CycleException;module.exports=exports.default},{}],15:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=void 0; | ||
/** | ||
@@ -51,4 +51,3 @@ * A min-priority queue data structure. This algorithm is derived from Cormen, | ||
* have its priority decreased in O(log n) time. | ||
*/ | ||
class PriorityQueue{#arr=[];#keyIndices={}; | ||
*/class PriorityQueue{#arr=[];#keyIndices={}; | ||
/** | ||
@@ -90,3 +89,3 @@ * Returns the number of elements in the queue. Takes `O(1)` time. | ||
* @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}}exports.default=PriorityQueue;module.exports=exports.default},{}],16:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=void 0;var DEFAULT_EDGE_NAME="\0";var GRAPH_NODE="\0";var EDGE_KEY_DELIM=""; | ||
// Implementation notes: | ||
@@ -292,5 +291,3 @@ // | ||
* Complexity: O(|E|). | ||
*/nodeEdges(v,w){var inEdges=this.inEdges(v,w);if(inEdges){return inEdges.concat(this.outEdges(v,w))}}}function incrementOrInitEntry(map,k){if(map[k]){map[k]++}else{map[k]=1}}function decrementOrRemoveEntry(map,k){if(!--map[k]){delete map[k]}}function edgeArgsToId(isDirected,v_,w_,name){var v=""+v_;var w=""+w_;if(!isDirected&&v>w){var tmp=v;v=w;w=tmp}return v+EDGE_KEY_DELIM+w+EDGE_KEY_DELIM+(name===undefined?DEFAULT_EDGE_NAME:name)}function edgeArgsToObj(isDirected,v_,w_,name){var v=""+v_;var w=""+w_;if(!isDirected&&v>w){var tmp=v;v=w;w=tmp}var edgeObj={v:v,w:w};if(name){edgeObj.name=name}return edgeObj}function edgeObjToId(isDirected,edgeObj){return edgeArgsToId(isDirected,edgeObj.v,edgeObj.w,edgeObj.name)}module.exports=Graph},{}],17:[function(require,module,exports){ | ||
// Includes only the "core" of graphlib | ||
module.exports={Graph:require("./graph"),version:require("./version")}},{"./graph":16,"./version":19}],18:[function(require,module,exports){var Graph=require("./graph");module.exports={write:write,read:read}; | ||
*/nodeEdges(v,w){var inEdges=this.inEdges(v,w);if(inEdges){return inEdges.concat(this.outEdges(v,w))}}}exports.default=Graph;function incrementOrInitEntry(map,k){if(map[k]){map[k]++}else{map[k]=1}}function decrementOrRemoveEntry(map,k){if(!--map[k]){delete map[k]}}function edgeArgsToId(isDirected,v_,w_,name){var v=""+v_;var w=""+w_;if(!isDirected&&v>w){var tmp=v;v=w;w=tmp}return v+EDGE_KEY_DELIM+w+EDGE_KEY_DELIM+(name===undefined?DEFAULT_EDGE_NAME:name)}function edgeArgsToObj(isDirected,v_,w_,name){var v=""+v_;var w=""+w_;if(!isDirected&&v>w){var tmp=v;v=w;w=tmp}var edgeObj={v:v,w:w};if(name){edgeObj.name=name}return edgeObj}function edgeObjToId(isDirected,edgeObj){return edgeArgsToId(isDirected,edgeObj.v,edgeObj.w,edgeObj.name)}module.exports=exports.default},{}],17:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});Object.defineProperty(exports,"Graph",{enumerable:true,get:function(){return _graph.default}});exports.json=exports.alg=void 0;Object.defineProperty(exports,"version",{enumerable:true,get:function(){return _version.default}});var _graph=_interopRequireDefault(require("./graph.js"));var _version=_interopRequireDefault(require("./version.js"));var _json=_interopRequireWildcard(require("./json.js"));exports.json=_json;var _alg=_interopRequireWildcard(require("./alg/index.js"));exports.alg=_alg;function _getRequireWildcardCache(e){if("function"!=typeof WeakMap)return null;var r=new WeakMap,t=new WeakMap;return(_getRequireWildcardCache=function(e){return e?t:r})(e)}function _interopRequireWildcard(e,r){if(!r&&e&&e.__esModule)return e;if(null===e||"object"!=typeof e&&"function"!=typeof e)return{default:e};var t=_getRequireWildcardCache(r);if(t&&t.has(e))return t.get(e);var n={__proto__:null},a=Object.defineProperty&&Object.getOwnPropertyDescriptor;for(var u in e)if("default"!==u&&Object.prototype.hasOwnProperty.call(e,u)){var i=a?Object.getOwnPropertyDescriptor(e,u):null;i&&(i.get||i.set)?Object.defineProperty(n,u,i):n[u]=e[u]}return n.default=e,t&&t.set(e,n),n}function _interopRequireDefault(obj){return obj&&obj.__esModule?obj:{default:obj}}},{"./alg/index.js":8,"./graph.js":16,"./json.js":18,"./version.js":19}],18:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.read=read;exports.write=write;var _graph=_interopRequireDefault(require("./graph.js"));function _interopRequireDefault(obj){return obj&&obj.__esModule?obj:{default:obj}} | ||
/** | ||
@@ -309,2 +306,2 @@ * Creates a JSON representation of the graph that can be serialized to a string with | ||
* // [ { 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.1.13"},{}]},{},[1])(1)}); | ||
*/function read(json){var g=new _graph.default(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.js":16}],19:[function(require,module,exports){"use strict";Object.defineProperty(exports,"__esModule",{value:true});exports.default=void 0;var _default=exports.default="2.2.0";module.exports=exports.default},{}]},{},[1])(1)}); |
@@ -1,3 +0,7 @@ | ||
module.exports = components; | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = components; | ||
function components(g) { | ||
@@ -7,3 +11,2 @@ var visited = {}; | ||
var cmpt; | ||
function dfs(v) { | ||
@@ -16,4 +19,3 @@ if (visited.hasOwnProperty(v)) return; | ||
} | ||
g.nodes().forEach(function(v) { | ||
g.nodes().forEach(function (v) { | ||
cmpt = []; | ||
@@ -25,4 +27,4 @@ dfs(v); | ||
}); | ||
return cmpts; | ||
} | ||
module.exports = exports.default; |
@@ -1,3 +0,7 @@ | ||
module.exports = dfs; | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = dfs; | ||
/* | ||
@@ -15,6 +19,4 @@ * A helper that preforms a pre- or post-order traversal on the input graph | ||
} | ||
var navigation = g.isDirected() ? v => g.successors(v) : v => g.neighbors(v); | ||
var orderFunc = order === "post" ? postOrderDfs : preOrderDfs; | ||
var acc = []; | ||
@@ -26,9 +28,6 @@ var visited = {}; | ||
} | ||
orderFunc(v, navigation, visited, acc); | ||
}); | ||
return acc; | ||
} | ||
function postOrderDfs(v, navigation, visited, acc) { | ||
@@ -49,3 +48,2 @@ var stack = [[v, false]]; | ||
} | ||
function preOrderDfs(v, navigation, visited, acc) { | ||
@@ -62,3 +60,2 @@ var stack = [v]; | ||
} | ||
function forEachRight(array, iteratee) { | ||
@@ -69,4 +66,4 @@ var length = array.length; | ||
} | ||
return array; | ||
} | ||
module.exports = exports.default; |
@@ -1,10 +0,15 @@ | ||
var dijkstra = require("./dijkstra"); | ||
"use strict"; | ||
module.exports = dijkstraAll; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = dijkstraAll; | ||
var _dijkstra = _interopRequireDefault(require("./dijkstra.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
function dijkstraAll(g, weightFunc, edgeFunc) { | ||
return g.nodes().reduce(function(acc, v) { | ||
acc[v] = dijkstra(g, v, weightFunc, edgeFunc); | ||
return g.nodes().reduce(function (acc, v) { | ||
acc[v] = (0, _dijkstra.default)(g, v, weightFunc, edgeFunc); | ||
return acc; | ||
}, {}); | ||
} | ||
module.exports = exports.default; |
@@ -1,19 +0,20 @@ | ||
var PriorityQueue = require("../data/priority-queue"); | ||
"use strict"; | ||
module.exports = dijkstra; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = dijkstra; | ||
var _priorityQueue = _interopRequireDefault(require("../data/priority-queue.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
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); }); | ||
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 pq = new _priorityQueue.default(); | ||
var v, vEntry; | ||
var updateNeighbors = function(edge) { | ||
var updateNeighbors = function (edge) { | ||
var w = edge.v !== v ? edge.v : edge.w; | ||
@@ -23,8 +24,5 @@ var wEntry = results[w]; | ||
var distance = vEntry.distance + weight; | ||
if (weight < 0) { | ||
throw new Error("dijkstra does not allow negative edge weights. " + | ||
"Bad edge: " + edge + " Weight: " + weight); | ||
throw new Error("dijkstra does not allow negative edge weights. " + "Bad edge: " + edge + " Weight: " + weight); | ||
} | ||
if (distance < wEntry.distance) { | ||
@@ -36,9 +34,9 @@ wEntry.distance = distance; | ||
}; | ||
g.nodes().forEach(function(v) { | ||
g.nodes().forEach(function (v) { | ||
var distance = v === source ? 0 : Number.POSITIVE_INFINITY; | ||
results[v] = { distance: distance }; | ||
results[v] = { | ||
distance: distance | ||
}; | ||
pq.add(v, distance); | ||
}); | ||
while (pq.size() > 0) { | ||
@@ -50,7 +48,6 @@ v = pq.removeMin(); | ||
} | ||
edgeFn(v).forEach(updateNeighbors); | ||
} | ||
return results; | ||
} | ||
module.exports = exports.default; |
@@ -1,9 +0,14 @@ | ||
var tarjan = require("./tarjan"); | ||
"use strict"; | ||
module.exports = findCycles; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = findCycles; | ||
var _tarjan = _interopRequireDefault(require("./tarjan.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
function findCycles(g) { | ||
return tarjan(g).filter(function(cmpt) { | ||
return cmpt.length > 1 || (cmpt.length === 1 && g.hasEdge(cmpt[0], cmpt[0])); | ||
return (0, _tarjan.default)(g).filter(function (cmpt) { | ||
return cmpt.length > 1 || cmpt.length === 1 && g.hasEdge(cmpt[0], cmpt[0]); | ||
}); | ||
} | ||
module.exports = exports.default; |
@@ -1,35 +0,42 @@ | ||
module.exports = floydWarshall; | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = 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); }); | ||
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) { | ||
nodes.forEach(function (v) { | ||
results[v] = {}; | ||
results[v][v] = { distance: 0 }; | ||
nodes.forEach(function(w) { | ||
results[v][v] = { | ||
distance: 0 | ||
}; | ||
nodes.forEach(function (w) { | ||
if (v !== w) { | ||
results[v][w] = { distance: Number.POSITIVE_INFINITY }; | ||
results[v][w] = { | ||
distance: Number.POSITIVE_INFINITY | ||
}; | ||
} | ||
}); | ||
edgeFn(v).forEach(function(edge) { | ||
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 }; | ||
results[v][w] = { | ||
distance: d, | ||
predecessor: v | ||
}; | ||
}); | ||
}); | ||
nodes.forEach(function(k) { | ||
nodes.forEach(function (k) { | ||
var rowK = results[k]; | ||
nodes.forEach(function(i) { | ||
nodes.forEach(function (i) { | ||
var rowI = results[i]; | ||
nodes.forEach(function(j) { | ||
nodes.forEach(function (j) { | ||
var ik = rowI[k]; | ||
@@ -46,4 +53,4 @@ var kj = rowK[j]; | ||
}); | ||
return results; | ||
} | ||
module.exports = exports.default; |
@@ -1,13 +0,83 @@ | ||
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") | ||
}; | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
Object.defineProperty(exports, "components", { | ||
enumerable: true, | ||
get: function () { | ||
return _components.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "dijkstra", { | ||
enumerable: true, | ||
get: function () { | ||
return _dijkstra.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "dijkstraAll", { | ||
enumerable: true, | ||
get: function () { | ||
return _dijkstraAll.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "findCycles", { | ||
enumerable: true, | ||
get: function () { | ||
return _findCycles.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "floydWarshall", { | ||
enumerable: true, | ||
get: function () { | ||
return _floydWarshall.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "isAcyclic", { | ||
enumerable: true, | ||
get: function () { | ||
return _isAcyclic.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "postorder", { | ||
enumerable: true, | ||
get: function () { | ||
return _postorder.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "preorder", { | ||
enumerable: true, | ||
get: function () { | ||
return _preorder.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "prim", { | ||
enumerable: true, | ||
get: function () { | ||
return _prim.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "tarjan", { | ||
enumerable: true, | ||
get: function () { | ||
return _tarjan.default; | ||
} | ||
}); | ||
Object.defineProperty(exports, "topsort", { | ||
enumerable: true, | ||
get: function () { | ||
return _topsort.default; | ||
} | ||
}); | ||
var _components = _interopRequireDefault(require("./components.js")); | ||
var _dijkstra = _interopRequireDefault(require("./dijkstra.js")); | ||
var _dijkstraAll = _interopRequireDefault(require("./dijkstra-all.js")); | ||
var _findCycles = _interopRequireDefault(require("./find-cycles.js")); | ||
var _floydWarshall = _interopRequireDefault(require("./floyd-warshall.js")); | ||
var _isAcyclic = _interopRequireDefault(require("./is-acyclic.js")); | ||
var _postorder = _interopRequireDefault(require("./postorder.js")); | ||
var _preorder = _interopRequireDefault(require("./preorder.js")); | ||
var _prim = _interopRequireDefault(require("./prim.js")); | ||
var _tarjan = _interopRequireDefault(require("./tarjan.js")); | ||
var _topsort = _interopRequireDefault(require("./topsort.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } |
@@ -1,10 +0,14 @@ | ||
var topsort = require("./topsort"); | ||
"use strict"; | ||
module.exports = isAcyclic; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = isAcyclic; | ||
var _topsort = _interopRequireDefault(require("./topsort.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
function isAcyclic(g) { | ||
try { | ||
topsort(g); | ||
(0, _topsort.default)(g); | ||
} catch (e) { | ||
if (e instanceof topsort.CycleException) { | ||
if (e instanceof _topsort.default.CycleException) { | ||
return false; | ||
@@ -16,1 +20,2 @@ } | ||
} | ||
module.exports = exports.default; |
@@ -1,7 +0,12 @@ | ||
var dfs = require("./dfs"); | ||
"use strict"; | ||
module.exports = postorder; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = postorder; | ||
var _dfs = _interopRequireDefault(require("./dfs.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
function postorder(g, vs) { | ||
return dfs(g, vs, "post"); | ||
return (0, _dfs.default)(g, vs, "post"); | ||
} | ||
module.exports = exports.default; |
@@ -1,7 +0,12 @@ | ||
var dfs = require("./dfs"); | ||
"use strict"; | ||
module.exports = preorder; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = preorder; | ||
var _dfs = _interopRequireDefault(require("./dfs.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
function preorder(g, vs) { | ||
return dfs(g, vs, "pre"); | ||
return (0, _dfs.default)(g, vs, "pre"); | ||
} | ||
module.exports = exports.default; |
@@ -1,12 +0,15 @@ | ||
var Graph = require("../graph"); | ||
var PriorityQueue = require("../data/priority-queue"); | ||
"use strict"; | ||
module.exports = prim; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = prim; | ||
var _graph = _interopRequireDefault(require("../graph.js")); | ||
var _priorityQueue = _interopRequireDefault(require("../data/priority-queue.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
function prim(g, weightFunc) { | ||
var result = new Graph(); | ||
var result = new _graph.default(); | ||
var parents = {}; | ||
var pq = new PriorityQueue(); | ||
var pq = new _priorityQueue.default(); | ||
var v; | ||
function updateNeighbors(edge) { | ||
@@ -23,8 +26,6 @@ var w = edge.v === v ? edge.w : edge.v; | ||
} | ||
if (g.nodeCount() === 0) { | ||
return result; | ||
} | ||
g.nodes().forEach(function(v) { | ||
g.nodes().forEach(function (v) { | ||
pq.add(v, Number.POSITIVE_INFINITY); | ||
@@ -36,3 +37,2 @@ result.setNode(v); | ||
pq.decrease(g.nodes()[0], 0); | ||
var init = false; | ||
@@ -48,7 +48,6 @@ while (pq.size() > 0) { | ||
} | ||
g.nodeEdges(v).forEach(updateNeighbors); | ||
} | ||
return result; | ||
} | ||
module.exports = exports.default; |
@@ -1,3 +0,7 @@ | ||
module.exports = tarjan; | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = tarjan; | ||
function tarjan(g) { | ||
@@ -8,3 +12,2 @@ var index = 0; | ||
var results = []; | ||
function dfs(v) { | ||
@@ -17,4 +20,3 @@ var entry = visited[v] = { | ||
stack.push(v); | ||
g.successors(v).forEach(function(w) { | ||
g.successors(v).forEach(function (w) { | ||
if (!visited.hasOwnProperty(w)) { | ||
@@ -27,3 +29,2 @@ dfs(w); | ||
}); | ||
if (entry.lowlink === entry.index) { | ||
@@ -40,4 +41,3 @@ var cmpt = []; | ||
} | ||
g.nodes().forEach(function(v) { | ||
g.nodes().forEach(function (v) { | ||
if (!visited.hasOwnProperty(v)) { | ||
@@ -47,4 +47,4 @@ dfs(v); | ||
}); | ||
return results; | ||
} | ||
module.exports = exports.default; |
@@ -0,1 +1,7 @@ | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = topsort; | ||
function topsort(g) { | ||
@@ -5,3 +11,2 @@ var visited = {}; | ||
var results = []; | ||
function visit(node) { | ||
@@ -11,3 +16,2 @@ if (stack.hasOwnProperty(node)) { | ||
} | ||
if (!visited.hasOwnProperty(node)) { | ||
@@ -21,12 +25,8 @@ stack[node] = true; | ||
} | ||
g.sinks().forEach(visit); | ||
if (Object.keys(visited).length !== g.nodeCount()) { | ||
throw new CycleException(); | ||
} | ||
return results; | ||
} | ||
class CycleException extends Error { | ||
@@ -37,4 +37,3 @@ constructor() { | ||
} | ||
module.exports = topsort; | ||
topsort.CycleException = CycleException; | ||
module.exports = exports.default; |
@@ -0,1 +1,7 @@ | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = void 0; | ||
/** | ||
@@ -23,3 +29,5 @@ * A min-priority queue data structure. This algorithm is derived from Cormen, | ||
keys() { | ||
return this.#arr.map(function(x) { return x.key; }); | ||
return this.#arr.map(function (x) { | ||
return x.key; | ||
}); | ||
} | ||
@@ -73,3 +81,6 @@ | ||
keyIndices[key] = index; | ||
arr.push({key: key, priority: priority}); | ||
arr.push({ | ||
key: key, | ||
priority: priority | ||
}); | ||
this.#decrease(index); | ||
@@ -102,4 +113,3 @@ return true; | ||
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); | ||
throw new Error("New priority is greater than current priority. " + "Key: " + key + " Old: " + this.#arr[index].priority + " New: " + priority); | ||
} | ||
@@ -109,3 +119,2 @@ this.#arr[index].priority = priority; | ||
} | ||
#heapify(i) { | ||
@@ -127,3 +136,2 @@ var arr = this.#arr; | ||
} | ||
#decrease(index) { | ||
@@ -142,3 +150,2 @@ var arr = this.#arr; | ||
} | ||
#swap(i, j) { | ||
@@ -155,3 +162,3 @@ var arr = this.#arr; | ||
} | ||
module.exports = PriorityQueue; | ||
exports.default = PriorityQueue; | ||
module.exports = exports.default; |
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = void 0; | ||
var DEFAULT_EDGE_NAME = "\x00"; | ||
@@ -57,7 +61,4 @@ var GRAPH_NODE = "\x00"; | ||
#edgeCount = 0; | ||
#parent; | ||
#children; | ||
constructor(opts) { | ||
@@ -69,3 +70,2 @@ if (opts) { | ||
} | ||
if (this.#isCompound) { | ||
@@ -119,3 +119,2 @@ // v -> parent | ||
/* === Node functions ========== */ | ||
@@ -135,3 +134,2 @@ | ||
} | ||
return this; | ||
@@ -182,3 +180,3 @@ } | ||
var self = this; | ||
vs.forEach(function(v) { | ||
vs.forEach(function (v) { | ||
if (args.length > 1) { | ||
@@ -206,3 +204,2 @@ self.setNode(v, value); | ||
} | ||
this.#nodes[v] = arguments.length > 1 ? value : this.#defaultNodeLabelFn(v); | ||
@@ -251,3 +248,3 @@ if (this.#isCompound) { | ||
delete this.#parent[v]; | ||
this.children(v).forEach(function(child) { | ||
this.children(v).forEach(function (child) { | ||
self.setParent(child); | ||
@@ -278,3 +275,2 @@ }); | ||
} | ||
if (parent === undefined) { | ||
@@ -287,10 +283,7 @@ parent = GRAPH_NODE; | ||
if (ancestor === v) { | ||
throw new Error("Setting " + parent+ " as parent of " + v + | ||
" would create a cycle"); | ||
throw new Error("Setting " + parent + " as parent of " + v + " would create a cycle"); | ||
} | ||
} | ||
this.setNode(parent); | ||
} | ||
this.setNode(v); | ||
@@ -302,3 +295,2 @@ this.#removeFromParentsChildList(v); | ||
} | ||
#removeFromParentsChildList(v) { | ||
@@ -374,7 +366,5 @@ delete this.#children[this.#parent[v]][v]; | ||
} | ||
return Array.from(union.values()); | ||
} | ||
} | ||
isLeaf(v) { | ||
@@ -402,7 +392,5 @@ var neighbors; | ||
}); | ||
copy.setGraph(this.graph()); | ||
var self = this; | ||
Object.entries(this.#nodes).forEach(function([v, value]) { | ||
Object.entries(this.#nodes).forEach(function ([v, value]) { | ||
if (filter(v)) { | ||
@@ -412,4 +400,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)) { | ||
@@ -419,3 +406,2 @@ copy.setEdge(e, self.edge(e)); | ||
}); | ||
var parents = {}; | ||
@@ -433,7 +419,5 @@ function findParent(v) { | ||
} | ||
if (this.#isCompound) { | ||
copy.nodes().forEach(v => copy.setParent(v, findParent(v))); | ||
} | ||
return copy; | ||
@@ -456,3 +440,2 @@ } | ||
} | ||
return this; | ||
@@ -486,3 +469,3 @@ } | ||
var args = arguments; | ||
vs.reduce(function(v, w) { | ||
vs.reduce(function (v, w) { | ||
if (args.length > 1) { | ||
@@ -508,3 +491,2 @@ self.setEdge(v, w, value); | ||
var arg0 = arguments[0]; | ||
if (typeof arg0 === "object" && arg0 !== null && "v" in arg0) { | ||
@@ -527,3 +509,2 @@ v = arg0.v; | ||
} | ||
v = "" + v; | ||
@@ -534,3 +515,2 @@ w = "" + w; | ||
} | ||
var e = edgeArgsToId(this.#isDirected, v, w, name); | ||
@@ -543,3 +523,2 @@ if (this.#edgeLabels.hasOwnProperty(e)) { | ||
} | ||
if (name !== undefined && !this.#isMultigraph) { | ||
@@ -553,5 +532,3 @@ throw new Error("Cannot set a named edge when isMultigraph = false"); | ||
this.setNode(w); | ||
this.#edgeLabels[e] = valueSpecified ? value : this.#defaultEdgeLabelFn(v, w, name); | ||
var edgeObj = edgeArgsToObj(this.#isDirected, v, w, name); | ||
@@ -561,3 +538,2 @@ // Ensure we add undirected edges in a consistent way. | ||
w = edgeObj.w; | ||
Object.freeze(edgeObj); | ||
@@ -578,5 +554,3 @@ this.#edgeObjs[e] = edgeObj; | ||
edge(v, w, name) { | ||
var e = (arguments.length === 1 | ||
? edgeObjToId(this.#isDirected, arguments[0]) | ||
: edgeArgsToId(this.#isDirected, v, w, name)); | ||
var e = arguments.length === 1 ? edgeObjToId(this.#isDirected, arguments[0]) : edgeArgsToId(this.#isDirected, v, w, name); | ||
return this.#edgeLabels[e]; | ||
@@ -592,5 +566,6 @@ } | ||
if (typeof edge !== "object") { | ||
return {label: edge}; | ||
return { | ||
label: edge | ||
}; | ||
} | ||
return edge; | ||
@@ -604,5 +579,3 @@ } | ||
hasEdge(v, w, name) { | ||
var e = (arguments.length === 1 | ||
? edgeObjToId(this.#isDirected, arguments[0]) | ||
: edgeArgsToId(this.#isDirected, v, w, name)); | ||
var e = arguments.length === 1 ? edgeObjToId(this.#isDirected, arguments[0]) : edgeArgsToId(this.#isDirected, v, w, name); | ||
return this.#edgeLabels.hasOwnProperty(e); | ||
@@ -616,5 +589,3 @@ } | ||
removeEdge(v, w, name) { | ||
var e = (arguments.length === 1 | ||
? edgeObjToId(this.#isDirected, arguments[0]) | ||
: edgeArgsToId(this.#isDirected, v, w, name)); | ||
var e = arguments.length === 1 ? edgeObjToId(this.#isDirected, arguments[0]) : edgeArgsToId(this.#isDirected, v, w, name); | ||
var edge = this.#edgeObjs[e]; | ||
@@ -679,3 +650,3 @@ if (edge) { | ||
} | ||
exports.default = Graph; | ||
function incrementOrInitEntry(map, k) { | ||
@@ -688,7 +659,7 @@ if (map[k]) { | ||
} | ||
function decrementOrRemoveEntry(map, k) { | ||
if (!--map[k]) { delete map[k]; } | ||
if (! --map[k]) { | ||
delete map[k]; | ||
} | ||
} | ||
function edgeArgsToId(isDirected, v_, w_, name) { | ||
@@ -702,6 +673,4 @@ var v = "" + v_; | ||
} | ||
return v + EDGE_KEY_DELIM + w + EDGE_KEY_DELIM + | ||
(name === undefined ? DEFAULT_EDGE_NAME : name); | ||
return v + EDGE_KEY_DELIM + w + EDGE_KEY_DELIM + (name === undefined ? DEFAULT_EDGE_NAME : name); | ||
} | ||
function edgeArgsToObj(isDirected, v_, w_, name) { | ||
@@ -715,3 +684,6 @@ var v = "" + v_; | ||
} | ||
var edgeObj = { v: v, w: w }; | ||
var edgeObj = { | ||
v: v, | ||
w: w | ||
}; | ||
if (name) { | ||
@@ -722,7 +694,5 @@ edgeObj.name = name; | ||
} | ||
function edgeObjToId(isDirected, edgeObj) { | ||
return edgeArgsToId(isDirected, edgeObj.v, edgeObj.w, edgeObj.name); | ||
} | ||
module.exports = Graph; | ||
module.exports = exports.default; |
@@ -1,5 +0,27 @@ | ||
// Includes only the "core" of graphlib | ||
module.exports = { | ||
Graph: require("./graph"), | ||
version: require("./version") | ||
}; | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
Object.defineProperty(exports, "Graph", { | ||
enumerable: true, | ||
get: function () { | ||
return _graph.default; | ||
} | ||
}); | ||
exports.json = exports.alg = void 0; | ||
Object.defineProperty(exports, "version", { | ||
enumerable: true, | ||
get: function () { | ||
return _version.default; | ||
} | ||
}); | ||
var _graph = _interopRequireDefault(require("./graph.js")); | ||
var _version = _interopRequireDefault(require("./version.js")); | ||
var _json = _interopRequireWildcard(require("./json.js")); | ||
exports.json = _json; | ||
var _alg = _interopRequireWildcard(require("./alg/index.js")); | ||
exports.alg = _alg; | ||
function _getRequireWildcardCache(e) { if ("function" != typeof WeakMap) return null; var r = new WeakMap(), t = new WeakMap(); return (_getRequireWildcardCache = function (e) { return e ? t : r; })(e); } | ||
function _interopRequireWildcard(e, r) { if (!r && e && e.__esModule) return e; if (null === e || "object" != typeof e && "function" != typeof e) return { default: e }; var t = _getRequireWildcardCache(r); if (t && t.has(e)) return t.get(e); var n = { __proto__: null }, a = Object.defineProperty && Object.getOwnPropertyDescriptor; for (var u in e) if ("default" !== u && Object.prototype.hasOwnProperty.call(e, u)) { var i = a ? Object.getOwnPropertyDescriptor(e, u) : null; i && (i.get || i.set) ? Object.defineProperty(n, u, i) : n[u] = e[u]; } return n.default = e, t && t.set(e, n), n; } | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } |
@@ -1,8 +0,10 @@ | ||
var Graph = require("./graph"); | ||
"use strict"; | ||
module.exports = { | ||
write: write, | ||
read: read | ||
}; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.read = read; | ||
exports.write = write; | ||
var _graph = _interopRequireDefault(require("./graph.js")); | ||
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; } | ||
/** | ||
@@ -22,3 +24,2 @@ * Creates a JSON representation of the graph that can be serialized to a string with | ||
}; | ||
if (g.graph() !== undefined) { | ||
@@ -29,8 +30,9 @@ json.value = structuredClone(g.graph()); | ||
} | ||
function writeNodes(g) { | ||
return g.nodes().map(function(v) { | ||
return g.nodes().map(function (v) { | ||
var nodeValue = g.node(v); | ||
var parent = g.parent(v); | ||
var node = { v: v }; | ||
var node = { | ||
v: v | ||
}; | ||
if (nodeValue !== undefined) { | ||
@@ -45,7 +47,9 @@ node.value = nodeValue; | ||
} | ||
function writeEdges(g) { | ||
return g.edges().map(function(e) { | ||
return g.edges().map(function (e) { | ||
var edgeValue = g.edge(e); | ||
var edge = { v: e.v, w: e.w }; | ||
var edge = { | ||
v: e.v, | ||
w: e.w | ||
}; | ||
if (e.name !== undefined) { | ||
@@ -72,4 +76,4 @@ edge.name = e.name; | ||
function read(json) { | ||
var g = new Graph(json.options).setGraph(json.value); | ||
json.nodes.forEach(function(entry) { | ||
var g = new _graph.default(json.options).setGraph(json.value); | ||
json.nodes.forEach(function (entry) { | ||
g.setNode(entry.v, entry.value); | ||
@@ -80,6 +84,10 @@ if (entry.parent) { | ||
}); | ||
json.edges.forEach(function(entry) { | ||
g.setEdge({ v: entry.v, w: entry.w, name: entry.name }, entry.value); | ||
json.edges.forEach(function (entry) { | ||
g.setEdge({ | ||
v: entry.v, | ||
w: entry.w, | ||
name: entry.name | ||
}, entry.value); | ||
}); | ||
return g; | ||
} |
@@ -1,1 +0,8 @@ | ||
module.exports = '2.1.13'; | ||
"use strict"; | ||
Object.defineProperty(exports, "__esModule", { | ||
value: true | ||
}); | ||
exports.default = void 0; | ||
var _default = exports.default = '2.2.0'; | ||
module.exports = exports.default; |
{ | ||
"name": "@dagrejs/graphlib", | ||
"version": "2.1.13", | ||
"version": "2.2.0", | ||
"description": "A directed and undirected multi-graph library", | ||
@@ -12,2 +12,7 @@ "author": "Chris Pettitt <cpettitt@gmail.com>", | ||
}, | ||
"module": "./mjs-lib/index.js", | ||
"exports": { | ||
"import": "./mjs-lib/index.js", | ||
"require": "./index.js" | ||
}, | ||
"files": [ | ||
@@ -17,3 +22,4 @@ "index.js", | ||
"dist/", | ||
"lib/" | ||
"lib/", | ||
"mjs-lib/" | ||
], | ||
@@ -29,2 +35,7 @@ "engines": { | ||
"devDependencies": { | ||
"@babel/cli": "^7.23.9", | ||
"@babel/core": "^7.23.9", | ||
"@babel/plugin-transform-modules-commonjs": "^7.23.3", | ||
"@babel/preset-env": "^7.23.9", | ||
"babel-plugin-add-module-exports": "^1.0.4", | ||
"benchmark": "2.1.4", | ||
@@ -46,3 +57,3 @@ "browserify": "16.5.1", | ||
"seedrandom": "3.0.5", | ||
"semver": "7.3.2", | ||
"semver": "7.5.4", | ||
"sprintf": "0.1.5", | ||
@@ -49,0 +60,0 @@ "uglify-js": "3.17.4" |
@@ -0,1 +1,2 @@ | ||
> English | [中文](README_CN.md) | ||
# Graphlib | ||
@@ -15,6 +16,4 @@ | ||
Graphlib is licensed under the terms of the MIT License. See the | ||
[LICENSE](LICENSE) file | ||
for details. | ||
Graphlib is licensed under the terms of the MIT License. See the [LICENSE](LICENSE) file for details. | ||
[npm package manager]: http://npmjs.org/ |
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
252751
45
6635
24
19