Socket
Socket
Sign inDemoInstall

@dagrejs/graphlib

Package Overview
Dependencies
Maintainers
3
Versions
11
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

@dagrejs/graphlib - npm Package Compare versions

Comparing version 2.1.4 to 2.1.10

566

dist/graphlib.core.js

@@ -1,2 +0,2 @@

(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 e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);var f=new Error("Cannot find module '"+o+"'");throw f.code="MODULE_NOT_FOUND",f}var l=n[o]={exports:{}};t[o][0].call(l.exports,function(e){var n=t[o][1][e];return s(n?n:e)},l,l.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s})({1:[function(require,module,exports){
(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){
/**

@@ -42,20 +42,18 @@ * Copyright (c) 2014, Chris Pettitt

},{"./lib":17,"./lib/alg":8,"./lib/json":18}],2:[function(require,module,exports){
var _ = require("../lodash");
module.exports = components;
function components(g) {
var visited = {},
cmpts = [],
cmpt;
var visited = {};
var cmpts = [];
var cmpt;
function dfs(v) {
if (_.has(visited, v)) return;
if (visited.hasOwnProperty(v)) return;
visited[v] = true;
cmpt.push(v);
_.each(g.successors(v), dfs);
_.each(g.predecessors(v), dfs);
g.successors(v).forEach(dfs);
g.predecessors(v).forEach(dfs);
}
_.each(g.nodes(), function(v) {
g.nodes().forEach(function(v) {
cmpt = [];

@@ -71,5 +69,3 @@ dfs(v);

},{"../lodash":19}],3:[function(require,module,exports){
var _ = require("../lodash");
},{}],3:[function(require,module,exports){
module.exports = dfs;

@@ -86,3 +82,3 @@

function dfs(g, vs, order) {
if (!_.isArray(vs)) {
if (!Array.isArray(vs)) {
vs = [vs];

@@ -93,5 +89,5 @@ }

var acc = [],
visited = {};
_.each(vs, function(v) {
var acc = [];
var visited = {};
vs.forEach(function(v) {
if (!g.hasNode(v)) {

@@ -107,7 +103,7 @@ throw new Error("Graph does not have node: " + v);

function doDfs(g, v, postorder, visited, navigation, acc) {
if (!_.has(visited, v)) {
if (!visited.hasOwnProperty(v)) {
visited[v] = true;
if (!postorder) { acc.push(v); }
_.each(navigation(v), function(w) {
navigation(v).forEach(function(w) {
doDfs(g, w, postorder, visited, navigation, acc);

@@ -119,5 +115,4 @@ });

},{"../lodash":19}],4:[function(require,module,exports){
var dijkstra = require("./dijkstra"),
_ = require("../lodash");
},{}],4:[function(require,module,exports){
var dijkstra = require("./dijkstra");

@@ -127,31 +122,31 @@ module.exports = dijkstraAll;

function dijkstraAll(g, weightFunc, edgeFunc) {
return _.transform(g.nodes(), function(acc, v) {
return g.nodes().reduce(function(acc, v) {
acc[v] = dijkstra(g, v, weightFunc, edgeFunc);
return acc;
}, {});
}
},{"../lodash":19,"./dijkstra":5}],5:[function(require,module,exports){
var _ = require("../lodash"),
PriorityQueue = require("../data/priority-queue");
},{"./dijkstra":5}],5:[function(require,module,exports){
var PriorityQueue = require("../data/priority-queue");
module.exports = dijkstra;
var DEFAULT_WEIGHT_FUNC = _.constant(1);
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); });
weightFn || DEFAULT_WEIGHT_FUNC,
edgeFn || function(v) { return g.outEdges(v); });
}
function runDijkstra(g, source, weightFn, edgeFn) {
var results = {},
pq = new PriorityQueue(),
v, vEntry;
var results = {};
var pq = new PriorityQueue();
var v, vEntry;
var updateNeighbors = function(edge) {
var w = edge.v !== v ? edge.v : edge.w,
wEntry = results[w],
weight = weightFn(edge),
distance = vEntry.distance + weight;
var w = edge.v !== v ? edge.v : edge.w;
var wEntry = results[w];
var weight = weightFn(edge);
var distance = vEntry.distance + weight;

@@ -189,5 +184,4 @@ if (weight < 0) {

},{"../data/priority-queue":15,"../lodash":19}],6:[function(require,module,exports){
var _ = require("../lodash"),
tarjan = require("./tarjan");
},{"../data/priority-queue":15}],6:[function(require,module,exports){
var tarjan = require("./tarjan");

@@ -197,3 +191,3 @@ module.exports = findCycles;

function findCycles(g) {
return _.filter(tarjan(g), function(cmpt) {
return tarjan(g).filter(function(cmpt) {
return cmpt.length > 1 || (cmpt.length === 1 && g.hasEdge(cmpt[0], cmpt[0]));

@@ -203,18 +197,16 @@ });

},{"../lodash":19,"./tarjan":13}],7:[function(require,module,exports){
var _ = require("../lodash");
},{"./tarjan":13}],7:[function(require,module,exports){
module.exports = floydWarshall;
var DEFAULT_WEIGHT_FUNC = _.constant(1);
var DEFAULT_WEIGHT_FUNC = () => 1;
function floydWarshall(g, weightFn, edgeFn) {
return runFloydWarshall(g,
weightFn || DEFAULT_WEIGHT_FUNC,
edgeFn || function(v) { return g.outEdges(v); });
weightFn || DEFAULT_WEIGHT_FUNC,
edgeFn || function(v) { return g.outEdges(v); });
}
function runFloydWarshall(g, weightFn, edgeFn) {
var results = {},
nodes = g.nodes();
var results = {};
var nodes = g.nodes();

@@ -230,4 +222,4 @@ nodes.forEach(function(v) {

edgeFn(v).forEach(function(edge) {
var w = edge.v === v ? edge.w : edge.v,
d = weightFn(edge);
var w = edge.v === v ? edge.w : edge.v;
var d = weightFn(edge);
results[v][w] = { distance: d, predecessor: v };

@@ -257,3 +249,3 @@ });

},{"../lodash":19}],8:[function(require,module,exports){
},{}],8:[function(require,module,exports){
module.exports = {

@@ -309,5 +301,4 @@ components: require("./components"),

},{"./dfs":3}],12:[function(require,module,exports){
var _ = require("../lodash"),
Graph = require("../graph"),
PriorityQueue = require("../data/priority-queue");
var Graph = require("../graph");
var PriorityQueue = require("../data/priority-queue");

@@ -317,10 +308,10 @@ module.exports = prim;

function prim(g, weightFunc) {
var result = new Graph(),
parents = {},
pq = new PriorityQueue(),
v;
var result = new Graph();
var parents = {};
var pq = new PriorityQueue();
var v;
function updateNeighbors(edge) {
var w = edge.v === v ? edge.w : edge.v,
pri = pq.priority(w);
var w = edge.v === v ? edge.w : edge.v;
var pri = pq.priority(w);
if (pri !== undefined) {

@@ -339,3 +330,3 @@ var edgeWeight = weightFunc(edge);

_.each(g.nodes(), function(v) {
g.nodes().forEach(function(v) {
pq.add(v, Number.POSITIVE_INFINITY);

@@ -351,3 +342,3 @@ result.setNode(v);

v = pq.removeMin();
if (_.has(parents, v)) {
if (parents.hasOwnProperty(v)) {
result.setEdge(v, parents[v]);

@@ -366,12 +357,10 @@ } else if (init) {

},{"../data/priority-queue":15,"../graph":16,"../lodash":19}],13:[function(require,module,exports){
var _ = require("../lodash");
},{"../data/priority-queue":15,"../graph":16}],13:[function(require,module,exports){
module.exports = tarjan;
function tarjan(g) {
var index = 0,
stack = [],
visited = {}, // node id -> { onStack, lowlink, index }
results = [];
var index = 0;
var stack = [];
var visited = {}; // node id -> { onStack, lowlink, index }
var results = [];

@@ -387,3 +376,3 @@ function dfs(v) {

g.successors(v).forEach(function(w) {
if (!_.has(visited, w)) {
if (!visited.hasOwnProperty(w)) {
dfs(w);

@@ -397,4 +386,4 @@ entry.lowlink = Math.min(entry.lowlink, visited[w].lowlink);

if (entry.lowlink === entry.index) {
var cmpt = [],
w;
var cmpt = [];
var w;
do {

@@ -410,3 +399,3 @@ w = stack.pop();

g.nodes().forEach(function(v) {
if (!_.has(visited, v)) {
if (!visited.hasOwnProperty(v)) {
dfs(v);

@@ -419,5 +408,3 @@ }

},{"../lodash":19}],14:[function(require,module,exports){
var _ = require("../lodash");
},{}],14:[function(require,module,exports){
module.exports = topsort;

@@ -427,15 +414,15 @@ topsort.CycleException = CycleException;

function topsort(g) {
var visited = {},
stack = {},
results = [];
var visited = {};
var stack = {};
var results = [];
function visit(node) {
if (_.has(stack, node)) {
if (stack.hasOwnProperty(node)) {
throw new CycleException();
}
if (!_.has(visited, node)) {
if (!visited.hasOwnProperty(node)) {
stack[node] = true;
visited[node] = true;
_.each(g.predecessors(node), visit);
g.predecessors(node).forEach(visit);
delete stack[node];

@@ -446,5 +433,5 @@ results.push(node);

_.each(g.sinks(), visit);
g.sinks().forEach(visit);
if (_.size(visited) !== g.nodeCount()) {
if (Object.keys(visited).length !== g.nodeCount()) {
throw new CycleException();

@@ -457,6 +444,5 @@ }

function CycleException() {}
CycleException.prototype = new Error(); // must be an instance of Error to pass testing
},{"../lodash":19}],15:[function(require,module,exports){
var _ = require("../lodash");
},{}],15:[function(require,module,exports){
module.exports = PriorityQueue;

@@ -494,3 +480,3 @@

PriorityQueue.prototype.has = function(key) {
return _.has(this._keyIndices, key);
return this._keyIndices.hasOwnProperty(key);
};

@@ -533,3 +519,3 @@

key = String(key);
if (!_.has(keyIndices, key)) {
if (!keyIndices.hasOwnProperty(key)) {
var arr = this._arr;

@@ -575,5 +561,5 @@ var index = arr.length;

var arr = this._arr;
var l = 2 * i,
r = l + 1,
largest = i;
var l = 2 * i;
var r = l + 1;
var largest = i;
if (l < arr.length) {

@@ -616,12 +602,10 @@ largest = arr[l].priority < arr[largest].priority ? l : largest;

},{"../lodash":19}],16:[function(require,module,exports){
},{}],16:[function(require,module,exports){
"use strict";
var _ = require("./lodash");
module.exports = Graph;
var DEFAULT_EDGE_NAME = "\x00",
GRAPH_NODE = "\x00",
EDGE_KEY_DELIM = "\x01";
var DEFAULT_EDGE_NAME = "\x00";
var GRAPH_NODE = "\x00";
var EDGE_KEY_DELIM = "\x01";

@@ -639,6 +623,12 @@ // Implementation notes:

function Graph(opts) {
this._isDirected = _.has(opts, "directed") ? opts.directed : true;
this._isMultigraph = _.has(opts, "multigraph") ? opts.multigraph : false;
this._isCompound = _.has(opts, "compound") ? opts.compound : false;
this._isDirected = true;
this._isMultigraph = false;
this._isCompound = false;
if (opts) {
this._isDirected = opts.hasOwnProperty("directed") ? opts.directed : true;
this._isMultigraph = opts.hasOwnProperty("multigraph") ? opts.multigraph : false;
this._isCompound = opts.hasOwnProperty("compound") ? opts.compound : false;
}
// Label for the graph itself

@@ -648,6 +638,6 @@ this._label = undefined;

// Defaults to be set when creating a new node
this._defaultNodeLabelFn = _.constant(undefined);
this._defaultNodeLabelFn = () => undefined;
// Defaults to be set when creating a new edge
this._defaultEdgeLabelFn = _.constant(undefined);
this._defaultEdgeLabelFn = () => undefined;

@@ -694,2 +684,5 @@ // v -> label

/**
* Whether graph was created with 'directed' flag set to true or not.
*/
Graph.prototype.isDirected = function() {

@@ -699,2 +692,5 @@ return this._isDirected;

/**
* Whether graph was created with 'multigraph' flag set to true or not.
*/
Graph.prototype.isMultigraph = function() {

@@ -704,2 +700,5 @@ return this._isMultigraph;

/**
* Whether graph was created with 'compound' flag set to true or not.
*/
Graph.prototype.isCompound = function() {

@@ -709,2 +708,5 @@ return this._isCompound;

/**
* Sets the label of the graph.
*/
Graph.prototype.setGraph = function(label) {

@@ -715,2 +717,5 @@ this._label = label;

/**
* Gets the graph label.
*/
Graph.prototype.graph = function() {

@@ -723,10 +728,22 @@ return this._label;

/**
* Sets the default node label. If newDefault is a function, it will be
* invoked ach time when setting a label for a node. Otherwise, this label
* will be assigned as default label in case if no label was specified while
* setting a node.
* Complexity: O(1).
*/
Graph.prototype.setDefaultNodeLabel = function(newDefault) {
if (!_.isFunction(newDefault)) {
newDefault = _.constant(newDefault);
this._defaultNodeLabelFn = newDefault;
if (typeof newDefault !== 'function') {
this._defaultNodeLabelFn = () => newDefault;
}
this._defaultNodeLabelFn = newDefault;
return this;
};
/**
* Gets the number of nodes in the graph.
* Complexity: O(1).
*/
Graph.prototype.nodeCount = function() {

@@ -736,32 +753,54 @@ return this._nodeCount;

/**
* Gets all nodes of the graph. Note, the in case of compound graph subnodes are
* not included in list.
* Complexity: O(1).
*/
Graph.prototype.nodes = function() {
return _.keys(this._nodes);
return Object.keys(this._nodes);
};
/**
* Gets list of nodes without in-edges.
* Complexity: O(|V|).
*/
Graph.prototype.sources = function() {
return _.filter(this.nodes(), _.bind(function(v) {
return _.isEmpty(this._in[v]);
}, this));
var self = this;
return this.nodes().filter(v => Object.keys(self._in[v]).length === 0);
};
/**
* Gets list of nodes without out-edges.
* Complexity: O(|V|).
*/
Graph.prototype.sinks = function() {
return _.filter(this.nodes(), _.bind(function(v) {
return _.isEmpty(this._out[v]);
}, this));
var self = this;
return this.nodes().filter(v => Object.keys(self._out[v]).length === 0);
};
/**
* Invokes setNode method for each node in names list.
* Complexity: O(|names|).
*/
Graph.prototype.setNodes = function(vs, value) {
var args = arguments;
_.each(vs, _.bind(function(v) {
var self = this;
vs.forEach(function(v) {
if (args.length > 1) {
this.setNode(v, value);
self.setNode(v, value);
} else {
this.setNode(v);
self.setNode(v);
}
}, this));
});
return this;
};
/**
* Creates or updates the value for the node v in the graph. If label is supplied
* it is set as the value for the node. If label is not supplied and the node was
* created by this call then the default node label will be assigned.
* Complexity: O(1).
*/
Graph.prototype.setNode = function(v, value) {
if (_.has(this._nodes, v)) {
if (this._nodes.hasOwnProperty(v)) {
if (arguments.length > 1) {

@@ -787,2 +826,6 @@ this._nodes[v] = value;

/**
* Gets the label of node with specified name.
* Complexity: O(|V|).
*/
Graph.prototype.node = function(v) {

@@ -792,10 +835,19 @@ return this._nodes[v];

/**
* Detects whether graph has a node with specified name or not.
*/
Graph.prototype.hasNode = function(v) {
return _.has(this._nodes, v);
return this._nodes.hasOwnProperty(v);
};
/**
* Remove the node with the name from the graph or do nothing if the node is not in
* the graph. If the node was removed this function also removes any incident
* edges.
* Complexity: O(1).
*/
Graph.prototype.removeNode = function(v) {
var self = this;
if (_.has(this._nodes, v)) {
var removeEdge = function(e) { self.removeEdge(self._edgeObjs[e]); };
if (this._nodes.hasOwnProperty(v)) {
var removeEdge = e => self.removeEdge(self._edgeObjs[e]);
delete this._nodes[v];

@@ -805,11 +857,11 @@ if (this._isCompound) {

delete this._parent[v];
_.each(this.children(v), _.bind(function(child) {
this.setParent(child);
}, this));
this.children(v).forEach(function(child) {
self.setParent(child);
});
delete this._children[v];
}
_.each(_.keys(this._in[v]), removeEdge);
Object.keys(this._in[v]).forEach(removeEdge);
delete this._in[v];
delete this._preds[v];
_.each(_.keys(this._out[v]), removeEdge);
Object.keys(this._out[v]).forEach(removeEdge);
delete this._out[v];

@@ -822,2 +874,8 @@ delete this._sucs[v];

/**
* Sets node p as a parent for node v if it is defined, or removes the
* parent for v if p is undefined. Method throws an exception in case of
* invoking it in context of noncompound graph.
* Average-case complexity: O(1).
*/
Graph.prototype.setParent = function(v, parent) {

@@ -828,3 +886,3 @@ if (!this._isCompound) {

if (_.isUndefined(parent)) {
if (parent === undefined) {
parent = GRAPH_NODE;

@@ -835,7 +893,7 @@ } else {

for (var ancestor = parent;
!_.isUndefined(ancestor);
ancestor = this.parent(ancestor)) {
ancestor !== undefined;
ancestor = this.parent(ancestor)) {
if (ancestor === v) {
throw new Error("Setting " + parent+ " as parent of " + v +
" would create create a cycle");
" would create a cycle");
}

@@ -858,2 +916,6 @@ }

/**
* Gets parent node for node v.
* Complexity: O(1).
*/
Graph.prototype.parent = function(v) {

@@ -868,11 +930,11 @@ if (this._isCompound) {

Graph.prototype.children = function(v) {
if (_.isUndefined(v)) {
v = GRAPH_NODE;
}
/**
* Gets list of direct children of node v.
* Complexity: O(1).
*/
Graph.prototype.children = function(v = GRAPH_NODE) {
if (this._isCompound) {
var children = this._children[v];
if (children) {
return _.keys(children);
return Object.keys(children);
}

@@ -886,20 +948,40 @@ } else if (v === GRAPH_NODE) {

/**
* Return all nodes that are predecessors of the specified node or undefined if node v is not in
* the graph. Behavior is undefined for undirected graphs - use neighbors instead.
* Complexity: O(|V|).
*/
Graph.prototype.predecessors = function(v) {
var predsV = this._preds[v];
if (predsV) {
return _.keys(predsV);
return Object.keys(predsV);
}
};
/**
* Return all nodes that are successors of the specified node or undefined if node v is not in
* the graph. Behavior is undefined for undirected graphs - use neighbors instead.
* Complexity: O(|V|).
*/
Graph.prototype.successors = function(v) {
var sucsV = this._sucs[v];
if (sucsV) {
return _.keys(sucsV);
return Object.keys(sucsV);
}
};
/**
* Return all nodes that are predecessors or successors of the specified node or undefined if
* node v is not in the graph.
* Complexity: O(|V|).
*/
Graph.prototype.neighbors = function(v) {
var preds = this.predecessors(v);
if (preds) {
return _.union(preds, this.successors(v));
const union = new Set(preds);
for (var succ of this.successors(v)) {
union.add(succ);
}
return Array.from(union.values());
}

@@ -918,2 +1000,8 @@ };

/**
* Creates new graph with nodes filtered via filter. Edges incident to rejected node
* are also removed. In case of compound graph, if parent is rejected by filter,
* than all its children are rejected too.
* Average-case complexity: O(|E|+|V|).
*/
Graph.prototype.filterNodes = function(filter) {

@@ -928,15 +1016,15 @@ var copy = new this.constructor({

_.each(this._nodes, _.bind(function(value, v) {
var self = this;
Object.entries(this._nodes).forEach(function([v, value]) {
if (filter(v)) {
copy.setNode(v, value);
}
}, this));
});
_.each(this._edgeObjs, _.bind(function(e) {
Object.values(this._edgeObjs).forEach(function(e) {
if (copy.hasNode(e.v) && copy.hasNode(e.w)) {
copy.setEdge(e, this.edge(e));
copy.setEdge(e, self.edge(e));
}
}, this));
});
var self = this;
var parents = {};

@@ -956,5 +1044,3 @@ function findParent(v) {

if (this._isCompound) {
_.each(copy.nodes(), function(v) {
copy.setParent(v, findParent(v));
});
copy.nodes().forEach(v => copy.setParent(v, findParent(v)));
}

@@ -967,10 +1053,22 @@

/**
* Sets the default edge label or factory function. This label will be
* assigned as default label in case if no label was specified while setting
* an edge or this function will be invoked each time when setting an edge
* with no label specified and returned value * will be used as a label for edge.
* Complexity: O(1).
*/
Graph.prototype.setDefaultEdgeLabel = function(newDefault) {
if (!_.isFunction(newDefault)) {
newDefault = _.constant(newDefault);
this._defaultEdgeLabelFn = newDefault;
if (typeof newDefault !== 'function') {
this._defaultEdgeLabelFn = () => newDefault;
}
this._defaultEdgeLabelFn = newDefault;
return this;
};
/**
* Gets the number of edges in the graph.
* Complexity: O(1).
*/
Graph.prototype.edgeCount = function() {

@@ -980,10 +1078,20 @@ return this._edgeCount;

/**
* Gets edges of the graph. In case of compound graph subgraphs are not considered.
* Complexity: O(|E|).
*/
Graph.prototype.edges = function() {
return _.values(this._edgeObjs);
return Object.values(this._edgeObjs);
};
/**
* Establish an edges path over the nodes in nodes list. If some edge is already
* exists, it will update its label, otherwise it will create an edge between pair
* of nodes with label provided or default label if no label provided.
* Complexity: O(|nodes|).
*/
Graph.prototype.setPath = function(vs, value) {
var self = this,
args = arguments;
_.reduce(vs, function(v, w) {
var self = this;
var args = arguments;
vs.reduce(function(v, w) {
if (args.length > 1) {

@@ -999,10 +1107,12 @@ self.setEdge(v, w, value);

/*
* setEdge(v, w, [value, [name]])
* setEdge({ v, w, [name] }, [value])
/**
* Creates or updates the label for the edge (v, w) with the optionally supplied
* name. If label is supplied it is set as the value for the edge. If label is not
* supplied and the edge was created by this call then the default edge label will
* be assigned. The name parameter is only useful with multigraphs.
*/
Graph.prototype.setEdge = function() {
var v, w, name, value,
valueSpecified = false,
arg0 = arguments[0];
var v, w, name, value;
var valueSpecified = false;
var arg0 = arguments[0];

@@ -1029,3 +1139,3 @@ if (typeof arg0 === "object" && arg0 !== null && "v" in arg0) {

w = "" + w;
if (!_.isUndefined(name)) {
if (name !== undefined) {
name = "" + name;

@@ -1035,3 +1145,3 @@ }

var e = edgeArgsToId(this._isDirected, v, w, name);
if (_.has(this._edgeLabels, e)) {
if (this._edgeLabels.hasOwnProperty(e)) {
if (valueSpecified) {

@@ -1043,3 +1153,3 @@ this._edgeLabels[e] = value;

if (!_.isUndefined(name) && !this._isMultigraph) {
if (name !== undefined && !this._isMultigraph) {
throw new Error("Cannot set a named edge when isMultigraph = false");

@@ -1070,21 +1180,33 @@ }

/**
* Gets the label for the specified edge.
* Complexity: O(1).
*/
Graph.prototype.edge = function(v, w, name) {
var e = (arguments.length === 1
? edgeObjToId(this._isDirected, arguments[0])
: edgeArgsToId(this._isDirected, v, w, name));
? edgeObjToId(this._isDirected, arguments[0])
: edgeArgsToId(this._isDirected, v, w, name));
return this._edgeLabels[e];
};
/**
* Detects whether the graph contains specified edge or not. No subgraphs are considered.
* Complexity: O(1).
*/
Graph.prototype.hasEdge = function(v, w, name) {
var e = (arguments.length === 1
? edgeObjToId(this._isDirected, arguments[0])
: edgeArgsToId(this._isDirected, v, w, name));
return _.has(this._edgeLabels, e);
? edgeObjToId(this._isDirected, arguments[0])
: edgeArgsToId(this._isDirected, v, w, name));
return this._edgeLabels.hasOwnProperty(e);
};
/**
* Removes the specified edge from the graph. No subgraphs are considered.
* Complexity: O(1).
*/
Graph.prototype.removeEdge = function(v, w, name) {
var e = (arguments.length === 1
? edgeObjToId(this._isDirected, arguments[0])
: edgeArgsToId(this._isDirected, v, w, name)),
edge = this._edgeObjs[e];
? edgeObjToId(this._isDirected, arguments[0])
: edgeArgsToId(this._isDirected, v, w, name));
var edge = this._edgeObjs[e];
if (edge) {

@@ -1104,24 +1226,39 @@ v = edge.v;

/**
* Return all edges that point to the node v. Optionally filters those edges down to just those
* coming from node u. Behavior is undefined for undirected graphs - use nodeEdges instead.
* Complexity: O(|E|).
*/
Graph.prototype.inEdges = function(v, u) {
var inV = this._in[v];
if (inV) {
var edges = _.values(inV);
var edges = Object.values(inV);
if (!u) {
return edges;
}
return _.filter(edges, function(edge) { return edge.v === u; });
return edges.filter(edge => edge.v === u);
}
};
/**
* Return all edges that are pointed at by node v. Optionally filters those edges down to just
* those point to w. Behavior is undefined for undirected graphs - use nodeEdges instead.
* Complexity: O(|E|).
*/
Graph.prototype.outEdges = function(v, w) {
var outV = this._out[v];
if (outV) {
var edges = _.values(outV);
var edges = Object.values(outV);
if (!w) {
return edges;
}
return _.filter(edges, function(edge) { return edge.w === w; });
return edges.filter(edge => edge.w === w);
}
};
/**
* Returns all edges to or from node v regardless of direction. Optionally filters those edges
* down to just those between nodes v and w regardless of direction.
* Complexity: O(|E|).
*/
Graph.prototype.nodeEdges = function(v, w) {

@@ -1155,3 +1292,3 @@ var inEdges = this.inEdges(v, w);

return v + EDGE_KEY_DELIM + w + EDGE_KEY_DELIM +
(_.isUndefined(name) ? DEFAULT_EDGE_NAME : name);
(name === undefined ? DEFAULT_EDGE_NAME : name);
}

@@ -1178,3 +1315,3 @@

},{"./lodash":19}],17:[function(require,module,exports){
},{}],17:[function(require,module,exports){
// Includes only the "core" of graphlib

@@ -1186,5 +1323,4 @@ module.exports = {

},{"./graph":16,"./version":20}],18:[function(require,module,exports){
var _ = require("./lodash"),
Graph = require("./graph");
},{"./graph":16,"./version":19}],18:[function(require,module,exports){
var Graph = require("./graph");

@@ -1196,2 +1332,6 @@ module.exports = {

/**
* Creates a JSON representation of the graph that can be serialized to a string with
* JSON.stringify. The graph can later be restored using json.read.
*/
function write(g) {

@@ -1207,4 +1347,5 @@ var json = {

};
if (!_.isUndefined(g.graph())) {
json.value = _.clone(g.graph());
if (g.graph() !== undefined) {
json.value = structuredClone(g.graph());
}

@@ -1215,10 +1356,10 @@ return json;

function writeNodes(g) {
return _.map(g.nodes(), function(v) {
var nodeValue = g.node(v),
parent = g.parent(v),
node = { v: v };
if (!_.isUndefined(nodeValue)) {
return g.nodes().map(function(v) {
var nodeValue = g.node(v);
var parent = g.parent(v);
var node = { v: v };
if (nodeValue !== undefined) {
node.value = nodeValue;
}
if (!_.isUndefined(parent)) {
if (parent !== undefined) {
node.parent = parent;

@@ -1231,9 +1372,9 @@ }

function writeEdges(g) {
return _.map(g.edges(), function(e) {
var edgeValue = g.edge(e),
edge = { v: e.v, w: e.w };
if (!_.isUndefined(e.name)) {
return g.edges().map(function(e) {
var edgeValue = g.edge(e);
var edge = { v: e.v, w: e.w };
if (e.name !== undefined) {
edge.name = e.name;
}
if (!_.isUndefined(edgeValue)) {
if (edgeValue !== undefined) {
edge.value = edgeValue;

@@ -1245,5 +1386,15 @@ }

/**
* Takes JSON as input and returns the graph representation.
*
* @example
* var g2 = graphlib.json.read(JSON.parse(str));
* g2.nodes();
* // ['a', 'b']
* g2.edges()
* // [ { v: 'a', w: 'b' } ]
*/
function read(json) {
var g = new Graph(json.options).setGraph(json.value);
_.each(json.nodes, function(entry) {
json.nodes.forEach(function(entry) {
g.setNode(entry.v, entry.value);

@@ -1254,3 +1405,3 @@ if (entry.parent) {

});
_.each(json.edges, function(entry) {
json.edges.forEach(function(entry) {
g.setEdge({ v: entry.v, w: entry.w, name: entry.name }, entry.value);

@@ -1261,23 +1412,6 @@ });

},{"./graph":16,"./lodash":19}],19:[function(require,module,exports){
/* global window */
},{"./graph":16}],19:[function(require,module,exports){
module.exports = '2.1.9';
var lodash;
if (typeof require === "function") {
try {
lodash = require("lodash");
} catch (e) {}
}
if (!lodash) {
lodash = window._;
}
module.exports = lodash;
},{"lodash":undefined}],20:[function(require,module,exports){
module.exports = '2.1.4';
},{}]},{},[1])(1)
});
});

244

dist/graphlib.core.min.js

@@ -1,2 +0,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 e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);var f=new Error("Cannot find module '"+o+"'");throw f.code="MODULE_NOT_FOUND",f}var l=n[o]={exports:{}};t[o][0].call(l.exports,function(e){var n=t[o][1][e];return s(n?n:e)},l,l.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s}({1:[function(require,module,exports){/**
(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){
/**
* Copyright (c) 2014, Chris Pettitt

@@ -30,3 +31,4 @@ * All rights reserved.

*/
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){var _=require("../lodash");module.exports=components;function components(g){var visited={},cmpts=[],cmpt;function dfs(v){if(_.has(visited,v))return;visited[v]=true;cmpt.push(v);_.each(g.successors(v),dfs);_.each(g.predecessors(v),dfs)}_.each(g.nodes(),function(v){cmpt=[];dfs(v);if(cmpt.length){cmpts.push(cmpt)}});return cmpts}},{"../lodash":19}],3:[function(require,module,exports){var _=require("../lodash");module.exports=dfs;/*
var lib=require("./lib");module.exports={Graph:lib.Graph,json:require("./lib/json"),alg:require("./lib/alg"),version:lib.version}},{"./lib":17,"./lib/alg":8,"./lib/json":18}],2:[function(require,module,exports){module.exports=components;function components(g){var visited={};var cmpts=[];var cmpt;function dfs(v){if(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;
/*
* A helper that preforms a pre- or post-order traversal on the input graph

@@ -38,7 +40,8 @@ * and returns the nodes in the order they were visited. If the graph is

* Order must be one of "pre" or "post".
*/
function dfs(g,vs,order){if(!_.isArray(vs)){vs=[vs]}var navigation=(g.isDirected()?g.successors:g.neighbors).bind(g);var acc=[],visited={};_.each(vs,function(v){if(!g.hasNode(v)){throw new Error("Graph does not have node: "+v)}doDfs(g,v,order==="post",visited,navigation,acc)});return acc}function doDfs(g,v,postorder,visited,navigation,acc){if(!_.has(visited,v)){visited[v]=true;if(!postorder){acc.push(v)}_.each(navigation(v),function(w){doDfs(g,w,postorder,visited,navigation,acc)});if(postorder){acc.push(v)}}}},{"../lodash":19}],4:[function(require,module,exports){var dijkstra=require("./dijkstra"),_=require("../lodash");module.exports=dijkstraAll;function dijkstraAll(g,weightFunc,edgeFunc){return _.transform(g.nodes(),function(acc,v){acc[v]=dijkstra(g,v,weightFunc,edgeFunc)},{})}},{"../lodash":19,"./dijkstra":5}],5:[function(require,module,exports){var _=require("../lodash"),PriorityQueue=require("../data/priority-queue");module.exports=dijkstra;var DEFAULT_WEIGHT_FUNC=_.constant(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={},pq=new PriorityQueue,v,vEntry;var updateNeighbors=function(edge){var w=edge.v!==v?edge.v:edge.w,wEntry=results[w],weight=weightFn(edge),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,"../lodash":19}],6:[function(require,module,exports){var _=require("../lodash"),tarjan=require("./tarjan");module.exports=findCycles;function findCycles(g){return _.filter(tarjan(g),function(cmpt){return cmpt.length>1||cmpt.length===1&&g.hasEdge(cmpt[0],cmpt[0])})}},{"../lodash":19,"./tarjan":13}],7:[function(require,module,exports){var _=require("../lodash");module.exports=floydWarshall;var DEFAULT_WEIGHT_FUNC=_.constant(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={},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,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}},{"../lodash":19}],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 _=require("../lodash"),Graph=require("../graph"),PriorityQueue=require("../data/priority-queue");module.exports=prim;function prim(g,weightFunc){var result=new Graph,parents={},pq=new PriorityQueue,v;function updateNeighbors(edge){var w=edge.v===v?edge.w:edge.v,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}_.each(g.nodes(),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()?g.successors:g.neighbors).bind(g);var acc=[];var visited={};vs.forEach(function(v){if(!g.hasNode(v)){throw new Error("Graph does not have node: "+v)}doDfs(g,v,order==="post",visited,navigation,acc)});return acc}function doDfs(g,v,postorder,visited,navigation,acc){if(!visited.hasOwnProperty(v)){visited[v]=true;if(!postorder){acc.push(v)}navigation(v).forEach(function(w){doDfs(g,w,postorder,visited,navigation,acc)});if(postorder){acc.push(v)}}}},{}],4:[function(require,module,exports){var dijkstra=require("./dijkstra");module.exports=dijkstraAll;function dijkstraAll(g,weightFunc,edgeFunc){return g.nodes().reduce(function(acc,v){acc[v]=dijkstra(g,v,weightFunc,edgeFunc);return acc},{})}},{"./dijkstra":5}],5:[function(require,module,exports){var PriorityQueue=require("../data/priority-queue");module.exports=dijkstra;var DEFAULT_WEIGHT_FUNC=()=>1;function dijkstra(g,source,weightFn,edgeFn){return runDijkstra(g,String(source),weightFn||DEFAULT_WEIGHT_FUNC,edgeFn||function(v){return g.outEdges(v)})}function runDijkstra(g,source,weightFn,edgeFn){var results={};var pq=new PriorityQueue;var v,vEntry;var updateNeighbors=function(edge){var w=edge.v!==v?edge.v:edge.w;var wEntry=results[w];var weight=weightFn(edge);var distance=vEntry.distance+weight;if(weight<0){throw new Error("dijkstra does not allow negative edge weights. "+"Bad edge: "+edge+" Weight: "+weight)}if(distance<wEntry.distance){wEntry.distance=distance;wEntry.predecessor=v;pq.decrease(w,distance)}};g.nodes().forEach(function(v){var distance=v===source?0:Number.POSITIVE_INFINITY;results[v]={distance:distance};pq.add(v,distance)});while(pq.size()>0){v=pq.removeMin();vEntry=results[v];if(vEntry.distance===Number.POSITIVE_INFINITY){break}edgeFn(v).forEach(updateNeighbors)}return results}},{"../data/priority-queue":15}],6:[function(require,module,exports){var tarjan=require("./tarjan");module.exports=findCycles;function findCycles(g){return tarjan(g).filter(function(cmpt){return cmpt.length>1||cmpt.length===1&&g.hasEdge(cmpt[0],cmpt[0])})}},{"./tarjan":13}],7:[function(require,module,exports){module.exports=floydWarshall;var DEFAULT_WEIGHT_FUNC=()=>1;function floydWarshall(g,weightFn,edgeFn){return runFloydWarshall(g,weightFn||DEFAULT_WEIGHT_FUNC,edgeFn||function(v){return g.outEdges(v)})}function runFloydWarshall(g,weightFn,edgeFn){var results={};var nodes=g.nodes();nodes.forEach(function(v){results[v]={};results[v][v]={distance:0};nodes.forEach(function(w){if(v!==w){results[v][w]={distance:Number.POSITIVE_INFINITY}}});edgeFn(v).forEach(function(edge){var w=edge.v===v?edge.w:edge.v;var d=weightFn(edge);results[v][w]={distance:d,predecessor:v}})});nodes.forEach(function(k){var rowK=results[k];nodes.forEach(function(i){var rowI=results[i];nodes.forEach(function(j){var ik=rowI[k];var kj=rowK[j];var ij=rowI[j];var altDistance=ik.distance+kj.distance;if(altDistance<ij.distance){ij.distance=altDistance;ij.predecessor=kj.predecessor}})})});return results}},{}],8:[function(require,module,exports){module.exports={components:require("./components"),dijkstra:require("./dijkstra"),dijkstraAll:require("./dijkstra-all"),findCycles:require("./find-cycles"),floydWarshall:require("./floyd-warshall"),isAcyclic:require("./is-acyclic"),postorder:require("./postorder"),preorder:require("./preorder"),prim:require("./prim"),tarjan:require("./tarjan"),topsort:require("./topsort")}},{"./components":2,"./dijkstra":5,"./dijkstra-all":4,"./find-cycles":6,"./floyd-warshall":7,"./is-acyclic":9,"./postorder":10,"./preorder":11,"./prim":12,"./tarjan":13,"./topsort":14}],9:[function(require,module,exports){var topsort=require("./topsort");module.exports=isAcyclic;function isAcyclic(g){try{topsort(g)}catch(e){if(e instanceof topsort.CycleException){return false}throw e}return true}},{"./topsort":14}],10:[function(require,module,exports){var dfs=require("./dfs");module.exports=postorder;function postorder(g,vs){return dfs(g,vs,"post")}},{"./dfs":3}],11:[function(require,module,exports){var dfs=require("./dfs");module.exports=preorder;function preorder(g,vs){return dfs(g,vs,"pre")}},{"./dfs":3}],12:[function(require,module,exports){var Graph=require("../graph");var PriorityQueue=require("../data/priority-queue");module.exports=prim;function prim(g,weightFunc){var result=new Graph;var parents={};var pq=new PriorityQueue;var v;function updateNeighbors(edge){var w=edge.v===v?edge.w:edge.v;var pri=pq.priority(w);if(pri!==undefined){var edgeWeight=weightFunc(edge);if(edgeWeight<pri){parents[w]=v;pq.decrease(w,edgeWeight)}}}if(g.nodeCount()===0){return result}g.nodes().forEach(function(v){pq.add(v,Number.POSITIVE_INFINITY);result.setNode(v)});
// Start from an arbitrary node
pq.decrease(g.nodes()[0],0);var init=false;while(pq.size()>0){v=pq.removeMin();if(_.has(parents,v)){result.setEdge(v,parents[v])}else if(init){throw new Error("Input graph is not connected: "+g)}else{init=true}g.nodeEdges(v).forEach(updateNeighbors)}return result}},{"../data/priority-queue":15,"../graph":16,"../lodash":19}],13:[function(require,module,exports){var _=require("../lodash");module.exports=tarjan;function tarjan(g){var index=0,stack=[],visited={},// node id -> { onStack, lowlink, index }
results=[];function dfs(v){var entry=visited[v]={onStack:true,lowlink:index,index:index++};stack.push(v);g.successors(v).forEach(function(w){if(!_.has(visited,w)){dfs(w);entry.lowlink=Math.min(entry.lowlink,visited[w].lowlink)}else if(visited[w].onStack){entry.lowlink=Math.min(entry.lowlink,visited[w].index)}});if(entry.lowlink===entry.index){var cmpt=[],w;do{w=stack.pop();visited[w].onStack=false;cmpt.push(w)}while(v!==w);results.push(cmpt)}}g.nodes().forEach(function(v){if(!_.has(visited,v)){dfs(v)}});return results}},{"../lodash":19}],14:[function(require,module,exports){var _=require("../lodash");module.exports=topsort;topsort.CycleException=CycleException;function topsort(g){var visited={},stack={},results=[];function visit(node){if(_.has(stack,node)){throw new CycleException}if(!_.has(visited,node)){stack[node]=true;visited[node]=true;_.each(g.predecessors(node),visit);delete stack[node];results.push(node)}}_.each(g.sinks(),visit);if(_.size(visited)!==g.nodeCount()){throw new CycleException}return results}function CycleException(){}},{"../lodash":19}],15:[function(require,module,exports){var _=require("../lodash");module.exports=PriorityQueue;/**
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){module.exports=topsort;topsort.CycleException=CycleException;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}function CycleException(){}CycleException.prototype=new Error;// must be an instance of Error to pass testing
},{}],15:[function(require,module,exports){module.exports=PriorityQueue;
/**
* A min-priority queue data structure. This algorithm is derived from Cormen,

@@ -49,13 +52,13 @@ * et al., "Introduction to Algorithms". The basic idea of a min-priority

* have its priority decreased in O(log n) time.
*/
function PriorityQueue(){this._arr=[];this._keyIndices={}}/**
*/function PriorityQueue(){this._arr=[];this._keyIndices={}}
/**
* Returns the number of elements in the queue. Takes `O(1)` time.
*/
PriorityQueue.prototype.size=function(){return this._arr.length};/**
*/PriorityQueue.prototype.size=function(){return this._arr.length};
/**
* Returns the keys that are in the queue. Takes `O(n)` time.
*/
PriorityQueue.prototype.keys=function(){return this._arr.map(function(x){return x.key})};/**
*/PriorityQueue.prototype.keys=function(){return this._arr.map(function(x){return x.key})};
/**
* Returns `true` if **key** is in the queue and `false` if not.
*/
PriorityQueue.prototype.has=function(key){return _.has(this._keyIndices,key)};/**
*/PriorityQueue.prototype.has=function(key){return this._keyIndices.hasOwnProperty(key)};
/**
* Returns the priority for **key**. If **key** is not present in the queue

@@ -65,8 +68,8 @@ * then this function returns `undefined`. Takes `O(1)` time.

* @param {Object} key
*/
PriorityQueue.prototype.priority=function(key){var index=this._keyIndices[key];if(index!==undefined){return this._arr[index].priority}};/**
*/PriorityQueue.prototype.priority=function(key){var index=this._keyIndices[key];if(index!==undefined){return this._arr[index].priority}};
/**
* Returns the key for the minimum element in this queue. If the queue is
* empty this function throws an Error. Takes `O(1)` time.
*/
PriorityQueue.prototype.min=function(){if(this.size()===0){throw new Error("Queue underflow")}return this._arr[0].key};/**
*/PriorityQueue.prototype.min=function(){if(this.size()===0){throw new Error("Queue underflow")}return this._arr[0].key};
/**
* Inserts a new key into the priority queue. If the key already exists in

@@ -78,7 +81,7 @@ * the queue this function returns `false`; otherwise it will return `true`.

* @param {Number} priority the initial priority for the key
*/
PriorityQueue.prototype.add=function(key,priority){var keyIndices=this._keyIndices;key=String(key);if(!_.has(keyIndices,key)){var arr=this._arr;var index=arr.length;keyIndices[key]=index;arr.push({key:key,priority:priority});this._decrease(index);return true}return false};/**
*/PriorityQueue.prototype.add=function(key,priority){var keyIndices=this._keyIndices;key=String(key);if(!keyIndices.hasOwnProperty(key)){var arr=this._arr;var index=arr.length;keyIndices[key]=index;arr.push({key:key,priority:priority});this._decrease(index);return true}return false};
/**
* Removes and returns the smallest key in the queue. Takes `O(log n)` time.
*/
PriorityQueue.prototype.removeMin=function(){this._swap(0,this._arr.length-1);var min=this._arr.pop();delete this._keyIndices[min.key];this._heapify(0);return min.key};/**
*/PriorityQueue.prototype.removeMin=function(){this._swap(0,this._arr.length-1);var min=this._arr.pop();delete this._keyIndices[min.key];this._heapify(0);return min.key};
/**
* Decreases the priority for **key** to **priority**. If the new priority is

@@ -89,4 +92,3 @@ * greater than the previous priority, this function will throw an Error.

* @param {Number} priority the new priority for the key
*/
PriorityQueue.prototype.decrease=function(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)};PriorityQueue.prototype._heapify=function(i){var arr=this._arr;var l=2*i,r=l+1,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)}}};PriorityQueue.prototype._decrease=function(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}};PriorityQueue.prototype._swap=function(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}},{"../lodash":19}],16:[function(require,module,exports){"use strict";var _=require("./lodash");module.exports=Graph;var DEFAULT_EDGE_NAME="\0",GRAPH_NODE="\0",EDGE_KEY_DELIM="";
*/PriorityQueue.prototype.decrease=function(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)};PriorityQueue.prototype._heapify=function(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)}}};PriorityQueue.prototype._decrease=function(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}};PriorityQueue.prototype._swap=function(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}},{}],16:[function(require,module,exports){"use strict";module.exports=Graph;var DEFAULT_EDGE_NAME="\0";var GRAPH_NODE="\0";var EDGE_KEY_DELIM="";
// Implementation notes:

@@ -101,9 +103,9 @@ //

// we're going to get to a performant hashtable in JavaScript.
function Graph(opts){this._isDirected=_.has(opts,"directed")?opts.directed:true;this._isMultigraph=_.has(opts,"multigraph")?opts.multigraph:false;this._isCompound=_.has(opts,"compound")?opts.compound:false;
function Graph(opts){this._isDirected=true;this._isMultigraph=false;this._isCompound=false;if(opts){this._isDirected=opts.hasOwnProperty("directed")?opts.directed:true;this._isMultigraph=opts.hasOwnProperty("multigraph")?opts.multigraph:false;this._isCompound=opts.hasOwnProperty("compound")?opts.compound:false}
// Label for the graph itself
this._label=undefined;
// Defaults to be set when creating a new node
this._defaultNodeLabelFn=_.constant(undefined);
this._defaultNodeLabelFn=()=>undefined;
// Defaults to be set when creating a new edge
this._defaultEdgeLabelFn=_.constant(undefined);
this._defaultEdgeLabelFn=()=>undefined;
// v -> label

@@ -126,14 +128,134 @@ this._nodes={};if(this._isCompound){

// e -> label
this._edgeLabels={}}/* Number of nodes in the graph. Should only be changed by the implementation. */
Graph.prototype._nodeCount=0;/* Number of edges in the graph. Should only be changed by the implementation. */
Graph.prototype._edgeCount=0;/* === Graph functions ========= */
Graph.prototype.isDirected=function(){return this._isDirected};Graph.prototype.isMultigraph=function(){return this._isMultigraph};Graph.prototype.isCompound=function(){return this._isCompound};Graph.prototype.setGraph=function(label){this._label=label;return this};Graph.prototype.graph=function(){return this._label};/* === Node functions ========== */
Graph.prototype.setDefaultNodeLabel=function(newDefault){if(!_.isFunction(newDefault)){newDefault=_.constant(newDefault)}this._defaultNodeLabelFn=newDefault;return this};Graph.prototype.nodeCount=function(){return this._nodeCount};Graph.prototype.nodes=function(){return _.keys(this._nodes)};Graph.prototype.sources=function(){return _.filter(this.nodes(),_.bind(function(v){return _.isEmpty(this._in[v])},this))};Graph.prototype.sinks=function(){return _.filter(this.nodes(),_.bind(function(v){return _.isEmpty(this._out[v])},this))};Graph.prototype.setNodes=function(vs,value){var args=arguments;_.each(vs,_.bind(function(v){if(args.length>1){this.setNode(v,value)}else{this.setNode(v)}},this));return this};Graph.prototype.setNode=function(v,value){if(_.has(this._nodes,v)){if(arguments.length>1){this._nodes[v]=value}return this}this._nodes[v]=arguments.length>1?value:this._defaultNodeLabelFn(v);if(this._isCompound){this._parent[v]=GRAPH_NODE;this._children[v]={};this._children[GRAPH_NODE][v]=true}this._in[v]={};this._preds[v]={};this._out[v]={};this._sucs[v]={};++this._nodeCount;return this};Graph.prototype.node=function(v){return this._nodes[v]};Graph.prototype.hasNode=function(v){return _.has(this._nodes,v)};Graph.prototype.removeNode=function(v){var self=this;if(_.has(this._nodes,v)){var removeEdge=function(e){self.removeEdge(self._edgeObjs[e])};delete this._nodes[v];if(this._isCompound){this._removeFromParentsChildList(v);delete this._parent[v];_.each(this.children(v),_.bind(function(child){this.setParent(child)},this));delete this._children[v]}_.each(_.keys(this._in[v]),removeEdge);delete this._in[v];delete this._preds[v];_.each(_.keys(this._out[v]),removeEdge);delete this._out[v];delete this._sucs[v];--this._nodeCount}return this};Graph.prototype.setParent=function(v,parent){if(!this._isCompound){throw new Error("Cannot set parent in a non-compound graph")}if(_.isUndefined(parent)){parent=GRAPH_NODE}else{
this._edgeLabels={}}
/* Number of nodes in the graph. Should only be changed by the implementation. */Graph.prototype._nodeCount=0;
/* Number of edges in the graph. Should only be changed by the implementation. */Graph.prototype._edgeCount=0;
/* === Graph functions ========= */
/**
* Whether graph was created with 'directed' flag set to true or not.
*/Graph.prototype.isDirected=function(){return this._isDirected};
/**
* Whether graph was created with 'multigraph' flag set to true or not.
*/Graph.prototype.isMultigraph=function(){return this._isMultigraph};
/**
* Whether graph was created with 'compound' flag set to true or not.
*/Graph.prototype.isCompound=function(){return this._isCompound};
/**
* Sets the label of the graph.
*/Graph.prototype.setGraph=function(label){this._label=label;return this};
/**
* Gets the graph label.
*/Graph.prototype.graph=function(){return this._label};
/* === Node functions ========== */
/**
* Sets the default node label. If newDefault is a function, it will be
* invoked ach time when setting a label for a node. Otherwise, this label
* will be assigned as default label in case if no label was specified while
* setting a node.
* Complexity: O(1).
*/Graph.prototype.setDefaultNodeLabel=function(newDefault){this._defaultNodeLabelFn=newDefault;if(typeof newDefault!=="function"){this._defaultNodeLabelFn=()=>newDefault}return this};
/**
* Gets the number of nodes in the graph.
* Complexity: O(1).
*/Graph.prototype.nodeCount=function(){return this._nodeCount};
/**
* Gets all nodes of the graph. Note, the in case of compound graph subnodes are
* not included in list.
* Complexity: O(1).
*/Graph.prototype.nodes=function(){return Object.keys(this._nodes)};
/**
* Gets list of nodes without in-edges.
* Complexity: O(|V|).
*/Graph.prototype.sources=function(){var self=this;return this.nodes().filter(v=>Object.keys(self._in[v]).length===0)};
/**
* Gets list of nodes without out-edges.
* Complexity: O(|V|).
*/Graph.prototype.sinks=function(){var self=this;return this.nodes().filter(v=>Object.keys(self._out[v]).length===0)};
/**
* Invokes setNode method for each node in names list.
* Complexity: O(|names|).
*/Graph.prototype.setNodes=function(vs,value){var args=arguments;var self=this;vs.forEach(function(v){if(args.length>1){self.setNode(v,value)}else{self.setNode(v)}});return this};
/**
* Creates or updates the value for the node v in the graph. If label is supplied
* it is set as the value for the node. If label is not supplied and the node was
* created by this call then the default node label will be assigned.
* Complexity: O(1).
*/Graph.prototype.setNode=function(v,value){if(this._nodes.hasOwnProperty(v)){if(arguments.length>1){this._nodes[v]=value}return this}this._nodes[v]=arguments.length>1?value:this._defaultNodeLabelFn(v);if(this._isCompound){this._parent[v]=GRAPH_NODE;this._children[v]={};this._children[GRAPH_NODE][v]=true}this._in[v]={};this._preds[v]={};this._out[v]={};this._sucs[v]={};++this._nodeCount;return this};
/**
* Gets the label of node with specified name.
* Complexity: O(|V|).
*/Graph.prototype.node=function(v){return this._nodes[v]};
/**
* Detects whether graph has a node with specified name or not.
*/Graph.prototype.hasNode=function(v){return this._nodes.hasOwnProperty(v)};
/**
* Remove the node with the name from the graph or do nothing if the node is not in
* the graph. If the node was removed this function also removes any incident
* edges.
* Complexity: O(1).
*/Graph.prototype.removeNode=function(v){var self=this;if(this._nodes.hasOwnProperty(v)){var removeEdge=e=>self.removeEdge(self._edgeObjs[e]);delete this._nodes[v];if(this._isCompound){this._removeFromParentsChildList(v);delete this._parent[v];this.children(v).forEach(function(child){self.setParent(child)});delete this._children[v]}Object.keys(this._in[v]).forEach(removeEdge);delete this._in[v];delete this._preds[v];Object.keys(this._out[v]).forEach(removeEdge);delete this._out[v];delete this._sucs[v];--this._nodeCount}return this};
/**
* Sets node p as a parent for node v if it is defined, or removes the
* parent for v if p is undefined. Method throws an exception in case of
* invoking it in context of noncompound graph.
* Average-case complexity: O(1).
*/Graph.prototype.setParent=function(v,parent){if(!this._isCompound){throw new Error("Cannot set parent in a non-compound graph")}if(parent===undefined){parent=GRAPH_NODE}else{
// Coerce parent to string
parent+="";for(var ancestor=parent;!_.isUndefined(ancestor);ancestor=this.parent(ancestor)){if(ancestor===v){throw new Error("Setting "+parent+" as parent of "+v+" would create create a cycle")}}this.setNode(parent)}this.setNode(v);this._removeFromParentsChildList(v);this._parent[v]=parent;this._children[parent][v]=true;return this};Graph.prototype._removeFromParentsChildList=function(v){delete this._children[this._parent[v]][v]};Graph.prototype.parent=function(v){if(this._isCompound){var parent=this._parent[v];if(parent!==GRAPH_NODE){return parent}}};Graph.prototype.children=function(v){if(_.isUndefined(v)){v=GRAPH_NODE}if(this._isCompound){var children=this._children[v];if(children){return _.keys(children)}}else if(v===GRAPH_NODE){return this.nodes()}else if(this.hasNode(v)){return[]}};Graph.prototype.predecessors=function(v){var predsV=this._preds[v];if(predsV){return _.keys(predsV)}};Graph.prototype.successors=function(v){var sucsV=this._sucs[v];if(sucsV){return _.keys(sucsV)}};Graph.prototype.neighbors=function(v){var preds=this.predecessors(v);if(preds){return _.union(preds,this.successors(v))}};Graph.prototype.isLeaf=function(v){var neighbors;if(this.isDirected()){neighbors=this.successors(v)}else{neighbors=this.neighbors(v)}return neighbors.length===0};Graph.prototype.filterNodes=function(filter){var copy=new this.constructor({directed:this._isDirected,multigraph:this._isMultigraph,compound:this._isCompound});copy.setGraph(this.graph());_.each(this._nodes,_.bind(function(value,v){if(filter(v)){copy.setNode(v,value)}},this));_.each(this._edgeObjs,_.bind(function(e){if(copy.hasNode(e.v)&&copy.hasNode(e.w)){copy.setEdge(e,this.edge(e))}},this));var self=this;var parents={};function findParent(v){var parent=self.parent(v);if(parent===undefined||copy.hasNode(parent)){parents[v]=parent;return parent}else if(parent in parents){return parents[parent]}else{return findParent(parent)}}if(this._isCompound){_.each(copy.nodes(),function(v){copy.setParent(v,findParent(v))})}return copy};/* === Edge functions ========== */
Graph.prototype.setDefaultEdgeLabel=function(newDefault){if(!_.isFunction(newDefault)){newDefault=_.constant(newDefault)}this._defaultEdgeLabelFn=newDefault;return this};Graph.prototype.edgeCount=function(){return this._edgeCount};Graph.prototype.edges=function(){return _.values(this._edgeObjs)};Graph.prototype.setPath=function(vs,value){var self=this,args=arguments;_.reduce(vs,function(v,w){if(args.length>1){self.setEdge(v,w,value)}else{self.setEdge(v,w)}return w});return this};/*
* setEdge(v, w, [value, [name]])
* setEdge({ v, w, [name] }, [value])
*/
Graph.prototype.setEdge=function(){var v,w,name,value,valueSpecified=false,arg0=arguments[0];if(typeof arg0==="object"&&arg0!==null&&"v"in arg0){v=arg0.v;w=arg0.w;name=arg0.name;if(arguments.length===2){value=arguments[1];valueSpecified=true}}else{v=arg0;w=arguments[1];name=arguments[3];if(arguments.length>2){value=arguments[2];valueSpecified=true}}v=""+v;w=""+w;if(!_.isUndefined(name)){name=""+name}var e=edgeArgsToId(this._isDirected,v,w,name);if(_.has(this._edgeLabels,e)){if(valueSpecified){this._edgeLabels[e]=value}return this}if(!_.isUndefined(name)&&!this._isMultigraph){throw new Error("Cannot set a named edge when isMultigraph = false")}
parent+="";for(var ancestor=parent;ancestor!==undefined;ancestor=this.parent(ancestor)){if(ancestor===v){throw new Error("Setting "+parent+" as parent of "+v+" would create a cycle")}}this.setNode(parent)}this.setNode(v);this._removeFromParentsChildList(v);this._parent[v]=parent;this._children[parent][v]=true;return this};Graph.prototype._removeFromParentsChildList=function(v){delete this._children[this._parent[v]][v]};
/**
* Gets parent node for node v.
* Complexity: O(1).
*/Graph.prototype.parent=function(v){if(this._isCompound){var parent=this._parent[v];if(parent!==GRAPH_NODE){return parent}}};
/**
* Gets list of direct children of node v.
* Complexity: O(1).
*/Graph.prototype.children=function(v=GRAPH_NODE){if(this._isCompound){var children=this._children[v];if(children){return Object.keys(children)}}else if(v===GRAPH_NODE){return this.nodes()}else if(this.hasNode(v)){return[]}};
/**
* Return all nodes that are predecessors of the specified node or undefined if node v is not in
* the graph. Behavior is undefined for undirected graphs - use neighbors instead.
* Complexity: O(|V|).
*/Graph.prototype.predecessors=function(v){var predsV=this._preds[v];if(predsV){return Object.keys(predsV)}};
/**
* Return all nodes that are successors of the specified node or undefined if node v is not in
* the graph. Behavior is undefined for undirected graphs - use neighbors instead.
* Complexity: O(|V|).
*/Graph.prototype.successors=function(v){var sucsV=this._sucs[v];if(sucsV){return Object.keys(sucsV)}};
/**
* Return all nodes that are predecessors or successors of the specified node or undefined if
* node v is not in the graph.
* Complexity: O(|V|).
*/Graph.prototype.neighbors=function(v){var preds=this.predecessors(v);if(preds){const union=new Set(preds);for(var succ of this.successors(v)){union.add(succ)}return Array.from(union.values())}};Graph.prototype.isLeaf=function(v){var neighbors;if(this.isDirected()){neighbors=this.successors(v)}else{neighbors=this.neighbors(v)}return neighbors.length===0};
/**
* Creates new graph with nodes filtered via filter. Edges incident to rejected node
* are also removed. In case of compound graph, if parent is rejected by filter,
* than all its children are rejected too.
* Average-case complexity: O(|E|+|V|).
*/Graph.prototype.filterNodes=function(filter){var copy=new this.constructor({directed:this._isDirected,multigraph:this._isMultigraph,compound:this._isCompound});copy.setGraph(this.graph());var self=this;Object.entries(this._nodes).forEach(function([v,value]){if(filter(v)){copy.setNode(v,value)}});Object.values(this._edgeObjs).forEach(function(e){if(copy.hasNode(e.v)&&copy.hasNode(e.w)){copy.setEdge(e,self.edge(e))}});var parents={};function findParent(v){var parent=self.parent(v);if(parent===undefined||copy.hasNode(parent)){parents[v]=parent;return parent}else if(parent in parents){return parents[parent]}else{return findParent(parent)}}if(this._isCompound){copy.nodes().forEach(v=>copy.setParent(v,findParent(v)))}return copy};
/* === Edge functions ========== */
/**
* Sets the default edge label or factory function. This label will be
* assigned as default label in case if no label was specified while setting
* an edge or this function will be invoked each time when setting an edge
* with no label specified and returned value * will be used as a label for edge.
* Complexity: O(1).
*/Graph.prototype.setDefaultEdgeLabel=function(newDefault){this._defaultEdgeLabelFn=newDefault;if(typeof newDefault!=="function"){this._defaultEdgeLabelFn=()=>newDefault}return this};
/**
* Gets the number of edges in the graph.
* Complexity: O(1).
*/Graph.prototype.edgeCount=function(){return this._edgeCount};
/**
* Gets edges of the graph. In case of compound graph subgraphs are not considered.
* Complexity: O(|E|).
*/Graph.prototype.edges=function(){return Object.values(this._edgeObjs)};
/**
* Establish an edges path over the nodes in nodes list. If some edge is already
* exists, it will update its label, otherwise it will create an edge between pair
* of nodes with label provided or default label if no label provided.
* Complexity: O(|nodes|).
*/Graph.prototype.setPath=function(vs,value){var self=this;var args=arguments;vs.reduce(function(v,w){if(args.length>1){self.setEdge(v,w,value)}else{self.setEdge(v,w)}return w});return this};
/**
* Creates or updates the label for the edge (v, w) with the optionally supplied
* name. If label is supplied it is set as the value for the edge. If label is not
* supplied and the edge was created by this call then the default edge label will
* be assigned. The name parameter is only useful with multigraphs.
*/Graph.prototype.setEdge=function(){var v,w,name,value;var valueSpecified=false;var arg0=arguments[0];if(typeof arg0==="object"&&arg0!==null&&"v"in arg0){v=arg0.v;w=arg0.w;name=arg0.name;if(arguments.length===2){value=arguments[1];valueSpecified=true}}else{v=arg0;w=arguments[1];name=arguments[3];if(arguments.length>2){value=arguments[2];valueSpecified=true}}v=""+v;w=""+w;if(name!==undefined){name=""+name}var e=edgeArgsToId(this._isDirected,v,w,name);if(this._edgeLabels.hasOwnProperty(e)){if(valueSpecified){this._edgeLabels[e]=value}return this}if(name!==undefined&&!this._isMultigraph){throw new Error("Cannot set a named edge when isMultigraph = false")}
// It didn't exist, so we need to create it.

@@ -143,5 +265,45 @@ // First ensure the nodes exist.

// Ensure we add undirected edges in a consistent way.
v=edgeObj.v;w=edgeObj.w;Object.freeze(edgeObj);this._edgeObjs[e]=edgeObj;incrementOrInitEntry(this._preds[w],v);incrementOrInitEntry(this._sucs[v],w);this._in[w][e]=edgeObj;this._out[v][e]=edgeObj;this._edgeCount++;return this};Graph.prototype.edge=function(v,w,name){var e=arguments.length===1?edgeObjToId(this._isDirected,arguments[0]):edgeArgsToId(this._isDirected,v,w,name);return this._edgeLabels[e]};Graph.prototype.hasEdge=function(v,w,name){var e=arguments.length===1?edgeObjToId(this._isDirected,arguments[0]):edgeArgsToId(this._isDirected,v,w,name);return _.has(this._edgeLabels,e)};Graph.prototype.removeEdge=function(v,w,name){var e=arguments.length===1?edgeObjToId(this._isDirected,arguments[0]):edgeArgsToId(this._isDirected,v,w,name),edge=this._edgeObjs[e];if(edge){v=edge.v;w=edge.w;delete this._edgeLabels[e];delete this._edgeObjs[e];decrementOrRemoveEntry(this._preds[w],v);decrementOrRemoveEntry(this._sucs[v],w);delete this._in[w][e];delete this._out[v][e];this._edgeCount--}return this};Graph.prototype.inEdges=function(v,u){var inV=this._in[v];if(inV){var edges=_.values(inV);if(!u){return edges}return _.filter(edges,function(edge){return edge.v===u})}};Graph.prototype.outEdges=function(v,w){var outV=this._out[v];if(outV){var edges=_.values(outV);if(!w){return edges}return _.filter(edges,function(edge){return edge.w===w})}};Graph.prototype.nodeEdges=function(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+(_.isUndefined(name)?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)}},{"./lodash":19}],17:[function(require,module,exports){
v=edgeObj.v;w=edgeObj.w;Object.freeze(edgeObj);this._edgeObjs[e]=edgeObj;incrementOrInitEntry(this._preds[w],v);incrementOrInitEntry(this._sucs[v],w);this._in[w][e]=edgeObj;this._out[v][e]=edgeObj;this._edgeCount++;return this};
/**
* Gets the label for the specified edge.
* Complexity: O(1).
*/Graph.prototype.edge=function(v,w,name){var e=arguments.length===1?edgeObjToId(this._isDirected,arguments[0]):edgeArgsToId(this._isDirected,v,w,name);return this._edgeLabels[e]};
/**
* Detects whether the graph contains specified edge or not. No subgraphs are considered.
* Complexity: O(1).
*/Graph.prototype.hasEdge=function(v,w,name){var e=arguments.length===1?edgeObjToId(this._isDirected,arguments[0]):edgeArgsToId(this._isDirected,v,w,name);return this._edgeLabels.hasOwnProperty(e)};
/**
* Removes the specified edge from the graph. No subgraphs are considered.
* Complexity: O(1).
*/Graph.prototype.removeEdge=function(v,w,name){var e=arguments.length===1?edgeObjToId(this._isDirected,arguments[0]):edgeArgsToId(this._isDirected,v,w,name);var edge=this._edgeObjs[e];if(edge){v=edge.v;w=edge.w;delete this._edgeLabels[e];delete this._edgeObjs[e];decrementOrRemoveEntry(this._preds[w],v);decrementOrRemoveEntry(this._sucs[v],w);delete this._in[w][e];delete this._out[v][e];this._edgeCount--}return this};
/**
* Return all edges that point to the node v. Optionally filters those edges down to just those
* coming from node u. Behavior is undefined for undirected graphs - use nodeEdges instead.
* Complexity: O(|E|).
*/Graph.prototype.inEdges=function(v,u){var inV=this._in[v];if(inV){var edges=Object.values(inV);if(!u){return edges}return edges.filter(edge=>edge.v===u)}};
/**
* Return all edges that are pointed at by node v. Optionally filters those edges down to just
* those point to w. Behavior is undefined for undirected graphs - use nodeEdges instead.
* Complexity: O(|E|).
*/Graph.prototype.outEdges=function(v,w){var outV=this._out[v];if(outV){var edges=Object.values(outV);if(!w){return edges}return edges.filter(edge=>edge.w===w)}};
/**
* Returns all edges to or from node v regardless of direction. Optionally filters those edges
* down to just those between nodes v and w regardless of direction.
* Complexity: O(|E|).
*/Graph.prototype.nodeEdges=function(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)}},{}],17:[function(require,module,exports){
// Includes only the "core" of graphlib
module.exports={Graph:require("./graph"),version:require("./version")}},{"./graph":16,"./version":20}],18:[function(require,module,exports){var _=require("./lodash"),Graph=require("./graph");module.exports={write:write,read:read};function write(g){var json={options:{directed:g.isDirected(),multigraph:g.isMultigraph(),compound:g.isCompound()},nodes:writeNodes(g),edges:writeEdges(g)};if(!_.isUndefined(g.graph())){json.value=_.clone(g.graph())}return json}function writeNodes(g){return _.map(g.nodes(),function(v){var nodeValue=g.node(v),parent=g.parent(v),node={v:v};if(!_.isUndefined(nodeValue)){node.value=nodeValue}if(!_.isUndefined(parent)){node.parent=parent}return node})}function writeEdges(g){return _.map(g.edges(),function(e){var edgeValue=g.edge(e),edge={v:e.v,w:e.w};if(!_.isUndefined(e.name)){edge.name=e.name}if(!_.isUndefined(edgeValue)){edge.value=edgeValue}return edge})}function read(json){var g=new Graph(json.options).setGraph(json.value);_.each(json.nodes,function(entry){g.setNode(entry.v,entry.value);if(entry.parent){g.setParent(entry.v,entry.parent)}});_.each(json.edges,function(entry){g.setEdge({v:entry.v,w:entry.w,name:entry.name},entry.value)});return g}},{"./graph":16,"./lodash":19}],19:[function(require,module,exports){/* global window */
var lodash;if(typeof require==="function"){try{lodash=require("lodash")}catch(e){}}if(!lodash){lodash=window._}module.exports=lodash},{lodash:undefined}],20:[function(require,module,exports){module.exports="2.1.4"},{}]},{},[1])(1)});
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};
/**
* Creates a JSON representation of the graph that can be serialized to a string with
* JSON.stringify. The graph can later be restored using json.read.
*/function write(g){var json={options:{directed:g.isDirected(),multigraph:g.isMultigraph(),compound:g.isCompound()},nodes:writeNodes(g),edges:writeEdges(g)};if(g.graph()!==undefined){json.value=structuredClone(g.graph())}return json}function writeNodes(g){return g.nodes().map(function(v){var nodeValue=g.node(v);var parent=g.parent(v);var node={v:v};if(nodeValue!==undefined){node.value=nodeValue}if(parent!==undefined){node.parent=parent}return node})}function writeEdges(g){return g.edges().map(function(e){var edgeValue=g.edge(e);var edge={v:e.v,w:e.w};if(e.name!==undefined){edge.name=e.name}if(edgeValue!==undefined){edge.value=edgeValue}return edge})}
/**
* Takes JSON as input and returns the graph representation.
*
* @example
* var g2 = graphlib.json.read(JSON.parse(str));
* g2.nodes();
* // ['a', 'b']
* g2.edges()
* // [ { v: 'a', w: 'b' } ]
*/function read(json){var g=new Graph(json.options).setGraph(json.value);json.nodes.forEach(function(entry){g.setNode(entry.v,entry.value);if(entry.parent){g.setParent(entry.v,entry.parent)}});json.edges.forEach(function(entry){g.setEdge({v:entry.v,w:entry.w,name:entry.name},entry.value)});return g}},{"./graph":16}],19:[function(require,module,exports){module.exports="2.1.9"},{}]},{},[1])(1)});

16

lib/alg/components.js

@@ -1,19 +0,17 @@

var _ = require("../lodash");
module.exports = components;
function components(g) {
var visited = {},
cmpts = [],
cmpt;
var visited = {};
var cmpts = [];
var cmpt;
function dfs(v) {
if (_.has(visited, v)) return;
if (visited.hasOwnProperty(v)) return;
visited[v] = true;
cmpt.push(v);
_.each(g.successors(v), dfs);
_.each(g.predecessors(v), dfs);
g.successors(v).forEach(dfs);
g.predecessors(v).forEach(dfs);
}
_.each(g.nodes(), function(v) {
g.nodes().forEach(function(v) {
cmpt = [];

@@ -20,0 +18,0 @@ dfs(v);

14

lib/alg/dfs.js

@@ -1,3 +0,1 @@

var _ = require("../lodash");
module.exports = dfs;

@@ -14,3 +12,3 @@

function dfs(g, vs, order) {
if (!_.isArray(vs)) {
if (!Array.isArray(vs)) {
vs = [vs];

@@ -21,5 +19,5 @@ }

var acc = [],
visited = {};
_.each(vs, function(v) {
var acc = [];
var visited = {};
vs.forEach(function(v) {
if (!g.hasNode(v)) {

@@ -35,7 +33,7 @@ throw new Error("Graph does not have node: " + v);

function doDfs(g, v, postorder, visited, navigation, acc) {
if (!_.has(visited, v)) {
if (!visited.hasOwnProperty(v)) {
visited[v] = true;
if (!postorder) { acc.push(v); }
_.each(navigation(v), function(w) {
navigation(v).forEach(function(w) {
doDfs(g, w, postorder, visited, navigation, acc);

@@ -42,0 +40,0 @@ });

6

lib/alg/dijkstra-all.js

@@ -1,3 +0,2 @@

var dijkstra = require("./dijkstra"),
_ = require("../lodash");
var dijkstra = require("./dijkstra");

@@ -7,5 +6,6 @@ module.exports = dijkstraAll;

function dijkstraAll(g, weightFunc, edgeFunc) {
return _.transform(g.nodes(), function(acc, v) {
return g.nodes().reduce(function(acc, v) {
acc[v] = dijkstra(g, v, weightFunc, edgeFunc);
return acc;
}, {});
}

23

lib/alg/dijkstra.js

@@ -1,24 +0,23 @@

var _ = require("../lodash"),
PriorityQueue = require("../data/priority-queue");
var PriorityQueue = require("../data/priority-queue");
module.exports = dijkstra;
var DEFAULT_WEIGHT_FUNC = _.constant(1);
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); });
weightFn || DEFAULT_WEIGHT_FUNC,
edgeFn || function(v) { return g.outEdges(v); });
}
function runDijkstra(g, source, weightFn, edgeFn) {
var results = {},
pq = new PriorityQueue(),
v, vEntry;
var results = {};
var pq = new PriorityQueue();
var v, vEntry;
var updateNeighbors = function(edge) {
var w = edge.v !== v ? edge.v : edge.w,
wEntry = results[w],
weight = weightFn(edge),
distance = vEntry.distance + weight;
var w = edge.v !== v ? edge.v : edge.w;
var wEntry = results[w];
var weight = weightFn(edge);
var distance = vEntry.distance + weight;

@@ -25,0 +24,0 @@ if (weight < 0) {

5

lib/alg/find-cycles.js

@@ -1,3 +0,2 @@

var _ = require("../lodash"),
tarjan = require("./tarjan");
var tarjan = require("./tarjan");

@@ -7,5 +6,5 @@ module.exports = findCycles;

function findCycles(g) {
return _.filter(tarjan(g), function(cmpt) {
return tarjan(g).filter(function(cmpt) {
return cmpt.length > 1 || (cmpt.length === 1 && g.hasEdge(cmpt[0], cmpt[0]));
});
}

16

lib/alg/floyd-warshall.js

@@ -1,16 +0,14 @@

var _ = require("../lodash");
module.exports = floydWarshall;
var DEFAULT_WEIGHT_FUNC = _.constant(1);
var DEFAULT_WEIGHT_FUNC = () => 1;
function floydWarshall(g, weightFn, edgeFn) {
return runFloydWarshall(g,
weightFn || DEFAULT_WEIGHT_FUNC,
edgeFn || function(v) { return g.outEdges(v); });
weightFn || DEFAULT_WEIGHT_FUNC,
edgeFn || function(v) { return g.outEdges(v); });
}
function runFloydWarshall(g, weightFn, edgeFn) {
var results = {},
nodes = g.nodes();
var results = {};
var nodes = g.nodes();

@@ -26,4 +24,4 @@ nodes.forEach(function(v) {

edgeFn(v).forEach(function(edge) {
var w = edge.v === v ? edge.w : edge.v,
d = weightFn(edge);
var w = edge.v === v ? edge.w : edge.v;
var d = weightFn(edge);
results[v][w] = { distance: d, predecessor: v };

@@ -30,0 +28,0 @@ });

21

lib/alg/prim.js

@@ -1,4 +0,3 @@

var _ = require("../lodash"),
Graph = require("../graph"),
PriorityQueue = require("../data/priority-queue");
var Graph = require("../graph");
var PriorityQueue = require("../data/priority-queue");

@@ -8,10 +7,10 @@ module.exports = prim;

function prim(g, weightFunc) {
var result = new Graph(),
parents = {},
pq = new PriorityQueue(),
v;
var result = new Graph();
var parents = {};
var pq = new PriorityQueue();
var v;
function updateNeighbors(edge) {
var w = edge.v === v ? edge.w : edge.v,
pri = pq.priority(w);
var w = edge.v === v ? edge.w : edge.v;
var pri = pq.priority(w);
if (pri !== undefined) {

@@ -30,3 +29,3 @@ var edgeWeight = weightFunc(edge);

_.each(g.nodes(), function(v) {
g.nodes().forEach(function(v) {
pq.add(v, Number.POSITIVE_INFINITY);

@@ -42,3 +41,3 @@ result.setNode(v);

v = pq.removeMin();
if (_.has(parents, v)) {
if (parents.hasOwnProperty(v)) {
result.setEdge(v, parents[v]);

@@ -45,0 +44,0 @@ } else if (init) {

18

lib/alg/tarjan.js

@@ -1,10 +0,8 @@

var _ = require("../lodash");
module.exports = tarjan;
function tarjan(g) {
var index = 0,
stack = [],
visited = {}, // node id -> { onStack, lowlink, index }
results = [];
var index = 0;
var stack = [];
var visited = {}; // node id -> { onStack, lowlink, index }
var results = [];

@@ -20,3 +18,3 @@ function dfs(v) {

g.successors(v).forEach(function(w) {
if (!_.has(visited, w)) {
if (!visited.hasOwnProperty(w)) {
dfs(w);

@@ -30,4 +28,4 @@ entry.lowlink = Math.min(entry.lowlink, visited[w].lowlink);

if (entry.lowlink === entry.index) {
var cmpt = [],
w;
var cmpt = [];
var w;
do {

@@ -43,3 +41,3 @@ w = stack.pop();

g.nodes().forEach(function(v) {
if (!_.has(visited, v)) {
if (!visited.hasOwnProperty(v)) {
dfs(v);

@@ -46,0 +44,0 @@ }

19

lib/alg/topsort.js

@@ -1,3 +0,1 @@

var _ = require("../lodash");
module.exports = topsort;

@@ -7,15 +5,15 @@ topsort.CycleException = CycleException;

function topsort(g) {
var visited = {},
stack = {},
results = [];
var visited = {};
var stack = {};
var results = [];
function visit(node) {
if (_.has(stack, node)) {
if (stack.hasOwnProperty(node)) {
throw new CycleException();
}
if (!_.has(visited, node)) {
if (!visited.hasOwnProperty(node)) {
stack[node] = true;
visited[node] = true;
_.each(g.predecessors(node), visit);
g.predecessors(node).forEach(visit);
delete stack[node];

@@ -26,5 +24,5 @@ results.push(node);

_.each(g.sinks(), visit);
g.sinks().forEach(visit);
if (_.size(visited) !== g.nodeCount()) {
if (Object.keys(visited).length !== g.nodeCount()) {
throw new CycleException();

@@ -37,1 +35,2 @@ }

function CycleException() {}
CycleException.prototype = new Error(); // must be an instance of Error to pass testing

12

lib/data/priority-queue.js

@@ -1,3 +0,1 @@

var _ = require("../lodash");
module.exports = PriorityQueue;

@@ -35,3 +33,3 @@

PriorityQueue.prototype.has = function(key) {
return _.has(this._keyIndices, key);
return this._keyIndices.hasOwnProperty(key);
};

@@ -74,3 +72,3 @@

key = String(key);
if (!_.has(keyIndices, key)) {
if (!keyIndices.hasOwnProperty(key)) {
var arr = this._arr;

@@ -116,5 +114,5 @@ var index = arr.length;

var arr = this._arr;
var l = 2 * i,
r = l + 1,
largest = i;
var l = 2 * i;
var r = l + 1;
var largest = i;
if (l < arr.length) {

@@ -121,0 +119,0 @@ largest = arr[l].priority < arr[largest].priority ? l : largest;

319

lib/graph.js
"use strict";
var _ = require("./lodash");
module.exports = Graph;
var DEFAULT_EDGE_NAME = "\x00",
GRAPH_NODE = "\x00",
EDGE_KEY_DELIM = "\x01";
var DEFAULT_EDGE_NAME = "\x00";
var GRAPH_NODE = "\x00";
var EDGE_KEY_DELIM = "\x01";

@@ -22,6 +20,12 @@ // Implementation notes:

function Graph(opts) {
this._isDirected = _.has(opts, "directed") ? opts.directed : true;
this._isMultigraph = _.has(opts, "multigraph") ? opts.multigraph : false;
this._isCompound = _.has(opts, "compound") ? opts.compound : false;
this._isDirected = true;
this._isMultigraph = false;
this._isCompound = false;
if (opts) {
this._isDirected = opts.hasOwnProperty("directed") ? opts.directed : true;
this._isMultigraph = opts.hasOwnProperty("multigraph") ? opts.multigraph : false;
this._isCompound = opts.hasOwnProperty("compound") ? opts.compound : false;
}
// Label for the graph itself

@@ -31,6 +35,6 @@ this._label = undefined;

// Defaults to be set when creating a new node
this._defaultNodeLabelFn = _.constant(undefined);
this._defaultNodeLabelFn = () => undefined;
// Defaults to be set when creating a new edge
this._defaultEdgeLabelFn = _.constant(undefined);
this._defaultEdgeLabelFn = () => undefined;

@@ -77,2 +81,5 @@ // v -> label

/**
* Whether graph was created with 'directed' flag set to true or not.
*/
Graph.prototype.isDirected = function() {

@@ -82,2 +89,5 @@ return this._isDirected;

/**
* Whether graph was created with 'multigraph' flag set to true or not.
*/
Graph.prototype.isMultigraph = function() {

@@ -87,2 +97,5 @@ return this._isMultigraph;

/**
* Whether graph was created with 'compound' flag set to true or not.
*/
Graph.prototype.isCompound = function() {

@@ -92,2 +105,5 @@ return this._isCompound;

/**
* Sets the label of the graph.
*/
Graph.prototype.setGraph = function(label) {

@@ -98,2 +114,5 @@ this._label = label;

/**
* Gets the graph label.
*/
Graph.prototype.graph = function() {

@@ -106,10 +125,22 @@ return this._label;

/**
* Sets the default node label. If newDefault is a function, it will be
* invoked ach time when setting a label for a node. Otherwise, this label
* will be assigned as default label in case if no label was specified while
* setting a node.
* Complexity: O(1).
*/
Graph.prototype.setDefaultNodeLabel = function(newDefault) {
if (!_.isFunction(newDefault)) {
newDefault = _.constant(newDefault);
this._defaultNodeLabelFn = newDefault;
if (typeof newDefault !== 'function') {
this._defaultNodeLabelFn = () => newDefault;
}
this._defaultNodeLabelFn = newDefault;
return this;
};
/**
* Gets the number of nodes in the graph.
* Complexity: O(1).
*/
Graph.prototype.nodeCount = function() {

@@ -119,32 +150,54 @@ return this._nodeCount;

/**
* Gets all nodes of the graph. Note, the in case of compound graph subnodes are
* not included in list.
* Complexity: O(1).
*/
Graph.prototype.nodes = function() {
return _.keys(this._nodes);
return Object.keys(this._nodes);
};
/**
* Gets list of nodes without in-edges.
* Complexity: O(|V|).
*/
Graph.prototype.sources = function() {
return _.filter(this.nodes(), _.bind(function(v) {
return _.isEmpty(this._in[v]);
}, this));
var self = this;
return this.nodes().filter(v => Object.keys(self._in[v]).length === 0);
};
/**
* Gets list of nodes without out-edges.
* Complexity: O(|V|).
*/
Graph.prototype.sinks = function() {
return _.filter(this.nodes(), _.bind(function(v) {
return _.isEmpty(this._out[v]);
}, this));
var self = this;
return this.nodes().filter(v => Object.keys(self._out[v]).length === 0);
};
/**
* Invokes setNode method for each node in names list.
* Complexity: O(|names|).
*/
Graph.prototype.setNodes = function(vs, value) {
var args = arguments;
_.each(vs, _.bind(function(v) {
var self = this;
vs.forEach(function(v) {
if (args.length > 1) {
this.setNode(v, value);
self.setNode(v, value);
} else {
this.setNode(v);
self.setNode(v);
}
}, this));
});
return this;
};
/**
* Creates or updates the value for the node v in the graph. If label is supplied
* it is set as the value for the node. If label is not supplied and the node was
* created by this call then the default node label will be assigned.
* Complexity: O(1).
*/
Graph.prototype.setNode = function(v, value) {
if (_.has(this._nodes, v)) {
if (this._nodes.hasOwnProperty(v)) {
if (arguments.length > 1) {

@@ -170,2 +223,6 @@ this._nodes[v] = value;

/**
* Gets the label of node with specified name.
* Complexity: O(|V|).
*/
Graph.prototype.node = function(v) {

@@ -175,10 +232,19 @@ return this._nodes[v];

/**
* Detects whether graph has a node with specified name or not.
*/
Graph.prototype.hasNode = function(v) {
return _.has(this._nodes, v);
return this._nodes.hasOwnProperty(v);
};
/**
* Remove the node with the name from the graph or do nothing if the node is not in
* the graph. If the node was removed this function also removes any incident
* edges.
* Complexity: O(1).
*/
Graph.prototype.removeNode = function(v) {
var self = this;
if (_.has(this._nodes, v)) {
var removeEdge = function(e) { self.removeEdge(self._edgeObjs[e]); };
if (this._nodes.hasOwnProperty(v)) {
var removeEdge = e => self.removeEdge(self._edgeObjs[e]);
delete this._nodes[v];

@@ -188,11 +254,11 @@ if (this._isCompound) {

delete this._parent[v];
_.each(this.children(v), _.bind(function(child) {
this.setParent(child);
}, this));
this.children(v).forEach(function(child) {
self.setParent(child);
});
delete this._children[v];
}
_.each(_.keys(this._in[v]), removeEdge);
Object.keys(this._in[v]).forEach(removeEdge);
delete this._in[v];
delete this._preds[v];
_.each(_.keys(this._out[v]), removeEdge);
Object.keys(this._out[v]).forEach(removeEdge);
delete this._out[v];

@@ -205,2 +271,8 @@ delete this._sucs[v];

/**
* Sets node p as a parent for node v if it is defined, or removes the
* parent for v if p is undefined. Method throws an exception in case of
* invoking it in context of noncompound graph.
* Average-case complexity: O(1).
*/
Graph.prototype.setParent = function(v, parent) {

@@ -211,3 +283,3 @@ if (!this._isCompound) {

if (_.isUndefined(parent)) {
if (parent === undefined) {
parent = GRAPH_NODE;

@@ -218,7 +290,7 @@ } else {

for (var ancestor = parent;
!_.isUndefined(ancestor);
ancestor = this.parent(ancestor)) {
ancestor !== undefined;
ancestor = this.parent(ancestor)) {
if (ancestor === v) {
throw new Error("Setting " + parent+ " as parent of " + v +
" would create create a cycle");
" would create a cycle");
}

@@ -241,2 +313,6 @@ }

/**
* Gets parent node for node v.
* Complexity: O(1).
*/
Graph.prototype.parent = function(v) {

@@ -251,11 +327,11 @@ if (this._isCompound) {

Graph.prototype.children = function(v) {
if (_.isUndefined(v)) {
v = GRAPH_NODE;
}
/**
* Gets list of direct children of node v.
* Complexity: O(1).
*/
Graph.prototype.children = function(v = GRAPH_NODE) {
if (this._isCompound) {
var children = this._children[v];
if (children) {
return _.keys(children);
return Object.keys(children);
}

@@ -269,20 +345,40 @@ } else if (v === GRAPH_NODE) {

/**
* Return all nodes that are predecessors of the specified node or undefined if node v is not in
* the graph. Behavior is undefined for undirected graphs - use neighbors instead.
* Complexity: O(|V|).
*/
Graph.prototype.predecessors = function(v) {
var predsV = this._preds[v];
if (predsV) {
return _.keys(predsV);
return Object.keys(predsV);
}
};
/**
* Return all nodes that are successors of the specified node or undefined if node v is not in
* the graph. Behavior is undefined for undirected graphs - use neighbors instead.
* Complexity: O(|V|).
*/
Graph.prototype.successors = function(v) {
var sucsV = this._sucs[v];
if (sucsV) {
return _.keys(sucsV);
return Object.keys(sucsV);
}
};
/**
* Return all nodes that are predecessors or successors of the specified node or undefined if
* node v is not in the graph.
* Complexity: O(|V|).
*/
Graph.prototype.neighbors = function(v) {
var preds = this.predecessors(v);
if (preds) {
return _.union(preds, this.successors(v));
const union = new Set(preds);
for (var succ of this.successors(v)) {
union.add(succ);
}
return Array.from(union.values());
}

@@ -301,2 +397,8 @@ };

/**
* Creates new graph with nodes filtered via filter. Edges incident to rejected node
* are also removed. In case of compound graph, if parent is rejected by filter,
* than all its children are rejected too.
* Average-case complexity: O(|E|+|V|).
*/
Graph.prototype.filterNodes = function(filter) {

@@ -311,15 +413,15 @@ var copy = new this.constructor({

_.each(this._nodes, _.bind(function(value, v) {
var self = this;
Object.entries(this._nodes).forEach(function([v, value]) {
if (filter(v)) {
copy.setNode(v, value);
}
}, this));
});
_.each(this._edgeObjs, _.bind(function(e) {
Object.values(this._edgeObjs).forEach(function(e) {
if (copy.hasNode(e.v) && copy.hasNode(e.w)) {
copy.setEdge(e, this.edge(e));
copy.setEdge(e, self.edge(e));
}
}, this));
});
var self = this;
var parents = {};

@@ -339,5 +441,3 @@ function findParent(v) {

if (this._isCompound) {
_.each(copy.nodes(), function(v) {
copy.setParent(v, findParent(v));
});
copy.nodes().forEach(v => copy.setParent(v, findParent(v)));
}

@@ -350,10 +450,22 @@

/**
* Sets the default edge label or factory function. This label will be
* assigned as default label in case if no label was specified while setting
* an edge or this function will be invoked each time when setting an edge
* with no label specified and returned value * will be used as a label for edge.
* Complexity: O(1).
*/
Graph.prototype.setDefaultEdgeLabel = function(newDefault) {
if (!_.isFunction(newDefault)) {
newDefault = _.constant(newDefault);
this._defaultEdgeLabelFn = newDefault;
if (typeof newDefault !== 'function') {
this._defaultEdgeLabelFn = () => newDefault;
}
this._defaultEdgeLabelFn = newDefault;
return this;
};
/**
* Gets the number of edges in the graph.
* Complexity: O(1).
*/
Graph.prototype.edgeCount = function() {

@@ -363,10 +475,20 @@ return this._edgeCount;

/**
* Gets edges of the graph. In case of compound graph subgraphs are not considered.
* Complexity: O(|E|).
*/
Graph.prototype.edges = function() {
return _.values(this._edgeObjs);
return Object.values(this._edgeObjs);
};
/**
* Establish an edges path over the nodes in nodes list. If some edge is already
* exists, it will update its label, otherwise it will create an edge between pair
* of nodes with label provided or default label if no label provided.
* Complexity: O(|nodes|).
*/
Graph.prototype.setPath = function(vs, value) {
var self = this,
args = arguments;
_.reduce(vs, function(v, w) {
var self = this;
var args = arguments;
vs.reduce(function(v, w) {
if (args.length > 1) {

@@ -382,10 +504,12 @@ self.setEdge(v, w, value);

/*
* setEdge(v, w, [value, [name]])
* setEdge({ v, w, [name] }, [value])
/**
* Creates or updates the label for the edge (v, w) with the optionally supplied
* name. If label is supplied it is set as the value for the edge. If label is not
* supplied and the edge was created by this call then the default edge label will
* be assigned. The name parameter is only useful with multigraphs.
*/
Graph.prototype.setEdge = function() {
var v, w, name, value,
valueSpecified = false,
arg0 = arguments[0];
var v, w, name, value;
var valueSpecified = false;
var arg0 = arguments[0];

@@ -412,3 +536,3 @@ if (typeof arg0 === "object" && arg0 !== null && "v" in arg0) {

w = "" + w;
if (!_.isUndefined(name)) {
if (name !== undefined) {
name = "" + name;

@@ -418,3 +542,3 @@ }

var e = edgeArgsToId(this._isDirected, v, w, name);
if (_.has(this._edgeLabels, e)) {
if (this._edgeLabels.hasOwnProperty(e)) {
if (valueSpecified) {

@@ -426,3 +550,3 @@ this._edgeLabels[e] = value;

if (!_.isUndefined(name) && !this._isMultigraph) {
if (name !== undefined && !this._isMultigraph) {
throw new Error("Cannot set a named edge when isMultigraph = false");

@@ -453,21 +577,33 @@ }

/**
* Gets the label for the specified edge.
* Complexity: O(1).
*/
Graph.prototype.edge = function(v, w, name) {
var e = (arguments.length === 1
? edgeObjToId(this._isDirected, arguments[0])
: edgeArgsToId(this._isDirected, v, w, name));
? edgeObjToId(this._isDirected, arguments[0])
: edgeArgsToId(this._isDirected, v, w, name));
return this._edgeLabels[e];
};
/**
* Detects whether the graph contains specified edge or not. No subgraphs are considered.
* Complexity: O(1).
*/
Graph.prototype.hasEdge = function(v, w, name) {
var e = (arguments.length === 1
? edgeObjToId(this._isDirected, arguments[0])
: edgeArgsToId(this._isDirected, v, w, name));
return _.has(this._edgeLabels, e);
? edgeObjToId(this._isDirected, arguments[0])
: edgeArgsToId(this._isDirected, v, w, name));
return this._edgeLabels.hasOwnProperty(e);
};
/**
* Removes the specified edge from the graph. No subgraphs are considered.
* Complexity: O(1).
*/
Graph.prototype.removeEdge = function(v, w, name) {
var e = (arguments.length === 1
? edgeObjToId(this._isDirected, arguments[0])
: edgeArgsToId(this._isDirected, v, w, name)),
edge = this._edgeObjs[e];
? edgeObjToId(this._isDirected, arguments[0])
: edgeArgsToId(this._isDirected, v, w, name));
var edge = this._edgeObjs[e];
if (edge) {

@@ -487,24 +623,39 @@ v = edge.v;

/**
* Return all edges that point to the node v. Optionally filters those edges down to just those
* coming from node u. Behavior is undefined for undirected graphs - use nodeEdges instead.
* Complexity: O(|E|).
*/
Graph.prototype.inEdges = function(v, u) {
var inV = this._in[v];
if (inV) {
var edges = _.values(inV);
var edges = Object.values(inV);
if (!u) {
return edges;
}
return _.filter(edges, function(edge) { return edge.v === u; });
return edges.filter(edge => edge.v === u);
}
};
/**
* Return all edges that are pointed at by node v. Optionally filters those edges down to just
* those point to w. Behavior is undefined for undirected graphs - use nodeEdges instead.
* Complexity: O(|E|).
*/
Graph.prototype.outEdges = function(v, w) {
var outV = this._out[v];
if (outV) {
var edges = _.values(outV);
var edges = Object.values(outV);
if (!w) {
return edges;
}
return _.filter(edges, function(edge) { return edge.w === w; });
return edges.filter(edge => edge.w === w);
}
};
/**
* Returns all edges to or from node v regardless of direction. Optionally filters those edges
* down to just those between nodes v and w regardless of direction.
* Complexity: O(|E|).
*/
Graph.prototype.nodeEdges = function(v, w) {

@@ -538,3 +689,3 @@ var inEdges = this.inEdges(v, w);

return v + EDGE_KEY_DELIM + w + EDGE_KEY_DELIM +
(_.isUndefined(name) ? DEFAULT_EDGE_NAME : name);
(name === undefined ? DEFAULT_EDGE_NAME : name);
}

@@ -541,0 +692,0 @@

48

lib/json.js

@@ -1,3 +0,2 @@

var _ = require("./lodash"),
Graph = require("./graph");
var Graph = require("./graph");

@@ -9,2 +8,6 @@ module.exports = {

/**
* Creates a JSON representation of the graph that can be serialized to a string with
* JSON.stringify. The graph can later be restored using json.read.
*/
function write(g) {

@@ -20,4 +23,5 @@ var json = {

};
if (!_.isUndefined(g.graph())) {
json.value = _.clone(g.graph());
if (g.graph() !== undefined) {
json.value = structuredClone(g.graph());
}

@@ -28,10 +32,10 @@ return json;

function writeNodes(g) {
return _.map(g.nodes(), function(v) {
var nodeValue = g.node(v),
parent = g.parent(v),
node = { v: v };
if (!_.isUndefined(nodeValue)) {
return g.nodes().map(function(v) {
var nodeValue = g.node(v);
var parent = g.parent(v);
var node = { v: v };
if (nodeValue !== undefined) {
node.value = nodeValue;
}
if (!_.isUndefined(parent)) {
if (parent !== undefined) {
node.parent = parent;

@@ -44,9 +48,9 @@ }

function writeEdges(g) {
return _.map(g.edges(), function(e) {
var edgeValue = g.edge(e),
edge = { v: e.v, w: e.w };
if (!_.isUndefined(e.name)) {
return g.edges().map(function(e) {
var edgeValue = g.edge(e);
var edge = { v: e.v, w: e.w };
if (e.name !== undefined) {
edge.name = e.name;
}
if (!_.isUndefined(edgeValue)) {
if (edgeValue !== undefined) {
edge.value = edgeValue;

@@ -58,5 +62,15 @@ }

/**
* Takes JSON as input and returns the graph representation.
*
* @example
* var g2 = graphlib.json.read(JSON.parse(str));
* g2.nodes();
* // ['a', 'b']
* g2.edges()
* // [ { v: 'a', w: 'b' } ]
*/
function read(json) {
var g = new Graph(json.options).setGraph(json.value);
_.each(json.nodes, function(entry) {
json.nodes.forEach(function(entry) {
g.setNode(entry.v, entry.value);

@@ -67,3 +81,3 @@ if (entry.parent) {

});
_.each(json.edges, function(entry) {
json.edges.forEach(function(entry) {
g.setEdge({ v: entry.v, w: entry.w, name: entry.name }, entry.value);

@@ -70,0 +84,0 @@ });

2

lib/version.js

@@ -1,1 +0,1 @@

module.exports = '2.1.4';
module.exports = '2.1.9';

62

package.json
{
"name": "@dagrejs/graphlib",
"version": "2.1.4",
"version": "2.1.10",
"description": "A directed and undirected multi-graph library",
"author": "Chris Pettitt <cpettitt@gmail.com>",
"license": "MIT",
"main": "index.js",
"scripts": {
"lint": "make lint",
"test": "make test"
},
"files": [
"index.js",
"dist/",
"lib/"
],
"engines": {
"node": ">17.0.0"
},
"keywords": [

@@ -11,27 +24,23 @@ "graph",

],
"dependencies": {
"lodash": "^4.11.1"
},
"dependencies": {},
"devDependencies": {
"benchmark": "^1.0.0",
"browserify": "^13.0.0",
"chai": "^1.9.2",
"istanbul": "^0.3.2",
"jscs": "^1.7.3",
"jshint": "^2.5.6",
"jshint-stylish": "^1.0.0",
"karma": "^0.13.22",
"karma-chrome-launcher": "^0.2.0",
"karma-firefox-launcher": "^0.1.6",
"karma-mocha": "^0.2.0",
"karma-phantomjs-launcher": "^1.0.0",
"karma-requirejs": "^0.2.5",
"karma-safari-launcher": "^0.1.1",
"mocha": "^1.21.5",
"phantomjs-prebuilt": "^2.1.7",
"requirejs": "^2.1.22",
"seedrandom": "^2.4.2",
"semver": "^4.1.0",
"sprintf": "^0.1.4",
"uglify-js": "^2.4.15"
"benchmark": "2.1.4",
"browserify": "16.5.1",
"chai": "^4.3.6",
"eslint": "8.35.0",
"istanbul": "^0.4.5",
"jshint": "2.13.5",
"jshint-stylish": "2.2.1",
"karma": "6.4.1",
"karma-chrome-launcher": "3.1.0",
"karma-firefox-launcher": "1.3.0",
"karma-mocha": "2.0.1",
"karma-requirejs": "1.1.0",
"karma-safari-launcher": "1.0.0",
"mocha": "10.1.0",
"requirejs": "2.3.6",
"seedrandom": "3.0.5",
"semver": "7.3.2",
"sprintf": "0.1.5",
"uglify-js": "3.17.4"
},

@@ -41,4 +50,3 @@ "repository": {

"url": "https://github.com/dagrejs/graphlib.git"
},
"license": "MIT"
}
}

3

README.md

@@ -6,3 +6,4 @@ # Graphlib

[![Build Status](https://secure.travis-ci.org/dagrejs/graphlib.png)](http://travis-ci.org/dagrejs/graphlib)
[![Build Status](https://github.com/dagrejs/graphlib/workflows/Build%20Status/badge.svg?branch=master)](https://github.com/dagrejs/graphlib/actions?query=workflow%3A%22Build+Status%22)
[![npm](https://img.shields.io/npm/v/graphlib.svg)](https://www.npmjs.com/package/graphlib)

@@ -9,0 +10,0 @@ To learn more [see our Wiki](https://github.com/cpettitt/graphlib/wiki).

.jscsrc
.jshintrc
.travis.yml
bower.json
karma.amd.conf.js
karma.conf.js
karma.core.conf.js
lib/lodash.js
dist/graphlib.js

Sorry, the diff of this file is too big to display

dist/graphlib.min.js

Sorry, the diff of this file is too big to display

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc