graphlib - npm Package Compare versions

Comparing version 1.0.0-pre1 to 1.0.0

CHANGELOG.md

@@ -1,6 +0,37 @@
-v1.0.0
+v0.9.1
 ======
 
-* Massive rewrite to the API for 1.0. API TBD on the wiki.
+* bower packaging changes - eliminatea lot of unnecessary files.
 
+v0.9.0
+======
+
+* dist scripts now included in the repo
+* repo now supports direct bower install
+* This is effectively 1.0 RC1
+
+v0.8.3
+======
+
+* Fix bug where undefined name was stringified
+
+v0.8.2
+======
+
+* Bug fix: node ids / name in edge are now stringified
+
+v0.8.1
+======
+
+* Release process changes only
+
+v0.8.0
+======
+
+* Massive rewrite to the graph API for a simpler implementation and API, and
+  better performance. This rewrite is to prepare for a v1.0.0 release where
+  subsequent minor releases will be backwards compatible. Please see the wiki
+  for the API reference and file issues for any suggests before we move this
+  to v1.0.0.
+
 v0.7.4
@@ -7,0 +38,0 @@ ======

index.js

@@ -30,25 +30,10 @@ /**
  */
-module.exports = {
-  Digraph: require("./lib/digraph"),
-  CDigraph: require("./lib/compound-digraph"),
 
-  Graph: require("./lib/graph"),
-  CGraph: require("./lib/compound-graph"),
+var lib = require("./lib");
 
-  alg: {
-    components: require("./lib/alg/components"),
-    dijkstra: require("./lib/alg/dijkstra"),
-    dijkstraAll: require("./lib/alg/dijkstra-all"),
-    findCycles: require("./lib/alg/find-cycles"),
-    floydWarshall: require("./lib/alg/floyd-warshall"),
-    isAcyclic: require("./lib/alg/is-acyclic"),
-    postorder: require("./lib/alg/postorder"),
-    preorder: require("./lib/alg/preorder"),
-    prim: require("./lib/alg/prim"),
-    tarjan: require("./lib/alg/tarjan"),
-    topsort: require("./lib/alg/topsort")
-  },
-
-  util: require("./lib/util"),
-  version: require("./lib/version")
+module.exports = {
+  Graph: lib.Graph,
+  json: require("./lib/json"),
+  alg: require("./lib/alg"),
+  version: lib.version
 };

lib/alg/components.js

@@ -1,2 +0,2 @@
-var _ = require("lodash");
+var _ = require("../lodash");
 
@@ -6,22 +6,23 @@ module.exports = components;
 function components(g) {
-  var results = [];
-  var visited = {};
+  var visited = {},
+      cmpts = [],
+      cmpt;
 
-  function dfs(component, v) {
-    if (!_.has(visited, v)) {
-      visited[v] = true;
-      component.push(v);
-      _.each(g.neighbors(v), _.partial(dfs, component));
-    }
+  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.nodeIds(), function(v) {
-    var component = [];
-    dfs(component, v);
-    if (component.length > 0) {
-      results.push(component);
+  _.each(g.nodes(), function(v) {
+    cmpt = [];
+    dfs(v);
+    if (cmpt.length) {
+      cmpts.push(cmpt);
     }
   });
 
-  return results;
+  return cmpts;
 }

lib/alg/dijkstra-all.js

 var dijkstra = require("./dijkstra"),
-    _ = require("lodash");
+    _ = require("../lodash");
 
@@ -7,5 +7,5 @@ module.exports = dijkstraAll;
 function dijkstraAll(g, weightFunc, edgeFunc) {
-  return _.transform(g.nodeIds(), function(acc, v) {
+  return _.transform(g.nodes(), function(acc, v) {
     acc[v] = dijkstra(g, v, weightFunc, edgeFunc);
   }, {});
 }

lib/alg/dijkstra.js

@@ -1,3 +0,3 @@
-var PriorityQueue = require("cp-data").PriorityQueue,
-    _ = require("lodash");
+var _ = require("../lodash"),
+    PriorityQueue = require("../data/priority-queue");
 
@@ -8,9 +8,9 @@ module.exports = dijkstra;
 
-function dijkstra(g, source, weightFunc, edgeFunc) {
+function dijkstra(g, source, weightFn, edgeFn) {
   return runDijkstra(g, String(source),
-                     weightFunc || DEFAULT_WEIGHT_FUNC,
-                     edgeFunc || function(v) { return g.outEdges(v); });
+                     weightFn || DEFAULT_WEIGHT_FUNC,
+                     edgeFn || function(v) { return g.outEdges(v); });
 }
 
-function runDijkstra(g, source, weightFunc, edgeFunc) {
+function runDijkstra(g, source, weightFn, edgeFn) {
   var results = {},
@@ -23,3 +23,3 @@ pq = new PriorityQueue(),
         wEntry = results[w],
-        weight = weightFunc(edge),
+        weight = weightFn(edge),
         distance = vEntry.distance + weight;
@@ -39,3 +39,3 @@
 
-  g.nodeIds().forEach(function(v) {
+  g.nodes().forEach(function(v) {
     var distance = v === source ? 0 : Number.POSITIVE_INFINITY;
@@ -53,3 +53,3 @@ results[v] = { distance: distance };
 
-    edgeFunc(v).forEach(updateNeighbors);
+    edgeFn(v).forEach(updateNeighbors);
   }
@@ -56,0 +56,0 @@

lib/alg/find-cycles.js

@@ -1,2 +0,2 @@
-var _ = require("lodash"),
+var _ = require("../lodash"),
     tarjan = require("./tarjan");
@@ -3,0 +3,0 @@

lib/alg/floyd-warshall.js

@@ -1,2 +0,2 @@
-var _ = require("lodash");
+var _ = require("../lodash");
 
@@ -7,11 +7,11 @@ module.exports = floydWarshall;
 
-function floydWarshall(g, weightFunc, edgeFunc) {
+function floydWarshall(g, weightFn, edgeFn) {
   return runFloydWarshall(g,
-                          weightFunc || DEFAULT_WEIGHT_FUNC,
-                          edgeFunc || function(v) { return g.outEdges(v); });
+                          weightFn || DEFAULT_WEIGHT_FUNC,
+                          edgeFn || function(v) { return g.outEdges(v); });
 }
 
-function runFloydWarshall(g, weightFunc, edgeFunc) {
+function runFloydWarshall(g, weightFn, edgeFn) {
   var results = {},
-      nodes = g.nodeIds();
+      nodes = g.nodes();
 
@@ -26,5 +26,5 @@ nodes.forEach(function(v) {
     });
-    edgeFunc(v).forEach(function(edge) {
+    edgeFn(v).forEach(function(edge) {
       var w = edge.v === v ? edge.w : edge.v,
-          d = weightFunc(edge);
+          d = weightFn(edge);
       results[v][w] = { distance: d, predecessor: v };
@@ -31,0 +31,0 @@ });

lib/alg/postorder.js

@@ -1,25 +0,7 @@
-var _ = require("lodash");
+var dfs = require("./dfs");
 
 module.exports = postorder;
 
-function postorder(g, root) {
-  var visited = {},
-      results = [];
-
-  dfs(g, root, undefined, visited, results);
-
-  return results;
+function postorder(g, vs) {
+  return dfs(g, vs, "post");
 }
-
-function dfs(g, v, prev, visited, results) {
-  if (_.has(visited, v)) {
-    throw new Error("The input graph is not a tree: " + g);
-  }
-  visited[v] = true;
-  g.successors(v).forEach(function(w) {
-    if (g.isDirected() || w !== prev) {
-      dfs(g, w, v, visited, results);
-    }
-  });
-  results.push(v);
-}

lib/alg/preorder.js

@@ -1,25 +0,7 @@
-var _ = require("lodash");
+var dfs = require("./dfs");
 
 module.exports = preorder;
 
-function preorder(g, root) {
-  var visited = {},
-      results = [];
-
-  dfs(g, root, undefined, visited, results);
-
-  return results;
+function preorder(g, vs) {
+  return dfs(g, vs, "pre");
 }
-
-function dfs(g, v, prev, visited, results) {
-  if (_.has(visited, v)) {
-    throw new Error("The input graph is not a tree: " + g);
-  }
-  visited[v] = true;
-  results.push(v);
-  g.successors(v).forEach(function(w) {
-    if (g.isDirected() || w !== prev) {
-      dfs(g, w, v, visited, results);
-    }
-  });
-}

lib/alg/prim.js

@@ -1,4 +0,4 @@
-var _ = require("lodash"),
-    Graph = require("../Graph"),
-    PriorityQueue = require("cp-data").PriorityQueue;
+var _ = require("../lodash"),
+    Graph = require("../graph"),
+    PriorityQueue = require("../data/priority-queue");
 
@@ -29,3 +29,3 @@ module.exports = prim;
 
-  _.each(g.nodeIds(), function(v) {
+  _.each(g.nodes(), function(v) {
     pq.add(v, Number.POSITIVE_INFINITY);
@@ -36,3 +36,3 @@ result.setNode(v);
   // Start from an arbitrary node
-  pq.decrease(g.nodeIds()[0], 0);
+  pq.decrease(g.nodes()[0], 0);
 
@@ -39,0 +39,0 @@ var init = false;

lib/alg/tarjan.js

@@ -1,2 +0,2 @@
-var _ = require("lodash");
+var _ = require("../lodash");
 
@@ -40,3 +40,3 @@ module.exports = tarjan;
 
-  g.nodeIds().forEach(function(v) {
+  g.nodes().forEach(function(v) {
     if (!_.has(visited, v)) {
@@ -43,0 +43,0 @@ dfs(v);

lib/alg/topsort.js

@@ -1,2 +0,2 @@
-var _ = require("lodash");
+var _ = require("../lodash");
 
@@ -3,0 +3,0 @@ module.exports = topsort;

lib/graph.js

@@ -1,51 +0,459 @@
-var _ = require("lodash"),
-    BaseGraph = require("./base-graph");
+"use strict";
 
+var _ = require("./lodash");
+
 module.exports = Graph;
 
-function Graph() {
-  var edges = {},
-      sourceSinks = {};
-  BaseGraph.call(this, edges, edges, sourceSinks, sourceSinks);
+var DEFAULT_EDGE_NAME = "\x00",
+    GRAPH_NODE = "\x00",
+    EDGE_KEY_DELIM = "\x01";
+
+// Implementation notes:
+//
+//  * Node id query functions should return string ids for the nodes
+//  * Edge id query functions should return an "edgeObj", edge object, that is
+//    composed of enough information to uniquely identify an edge: {v, w, name}.
+//  * Internally we use an "edgeId", a stringified form of the edgeObj, to
+//    reference edges. This is because we need a performant way to look these
+//    edges up and, object properties, which have string keys, are the closest
+//    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;
+
+  // Label for the graph itself
+  this._label = undefined;
+
+  // Defaults to be set when creating a new node
+  this._defaultNodeLabelFn = _.constant(undefined);
+
+  // Defaults to be set when creating a new edge
+  this._defaultEdgeLabelFn = _.constant(undefined);
+
+  // v -> label
+  this._nodes = {};
+
+  if (this._isCompound) {
+    // v -> parent
+    this._parent = {};
+
+    // v -> children
+    this._children = {};
+    this._children[GRAPH_NODE] = {};
+  }
+
+  // v -> edgeObj
+  this._in = {};
+
+  // u -> v -> Number
+  this._preds = {};
+
+  // v -> edgeObj
+  this._out = {};
+
+  // v -> w -> Number
+  this._sucs = {};
+
+  // e -> edgeObj
+  this._edgeObjs = {};
+
+  // e -> label
+  this._edgeLabels = {};
 }
 
-Graph.prototype = new BaseGraph();
-Graph.prototype.constructor = Graph;
+/* Number of nodes in the graph. Should only be changed by the implementation. */
+Graph.prototype._nodeCount = 0;
 
-/* === Graph-level functions ========== */
+/* Number of edges in the graph. Should only be changed by the implementation. */
+Graph.prototype._edgeCount = 0;
 
+
+/* === Graph functions ========= */
+
 Graph.prototype.isDirected = function() {
-  return false;
+  return this._isDirected;
 };
 
-Graph.prototype.edges = function() {
-  // Our edges are undirected, which is represented by two edges point in
-  // opposite directions. Here we need to filer one of those edges out.
-  var i = 0;
-  return _.transform(this._outEdges, function(acc, vOut, v) {
-    return _.each(vOut, function(edge) {
-      if (v === edge.v) {
-        acc[i++] = edge;
-      }
-    });
-  }, new Array(this._edgeCount));
+Graph.prototype.isMultigraph = function() {
+  return this._isMultigraph;
 };
 
-/* === Node-level functions ========== */
+Graph.prototype.isCompound = function() {
+  return this._isCompound;
+};
 
-Graph.prototype.neighbors = BaseGraph.prototype.successors;
+Graph.prototype.setGraph = function(label) {
+  this._label = label;
+  return this;
+};
 
-Graph.prototype.nodeEdges = BaseGraph.prototype.outEdges;
+Graph.prototype.graph = function() {
+  return this._label;
+};
 
-Graph.prototype._onRemoveNode = function(v) {
-  _.forIn(this._inEdges[v], function(_, u) {
-    --this._edgeCount;
-    delete this._outEdges[u][v];
+
+/* === 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(), function(v) {
+    return _.isEmpty(this._in[v]);
   }, this);
+};
 
-  // On the second pass we do not decrement the graph count. These are the
-  // inverse elements of the edges already deleted.
-  _.forIn(this._outEdges[v], function(_, w) {
-    delete this._inEdges[w][v];
+Graph.prototype.sinks = function() {
+  return _.filter(this.nodes(), function(v) {
+    return _.isEmpty(this._out[v]);
   }, this);
 };
+
+Graph.prototype.setNodes = function(vs, value) {
+  var args = arguments;
+  _.each(vs, 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), 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 {
+    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));
+  }
+};
+
+/* === 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(v, w, value, name) {
+  var valueSpecified = arguments.length > 2;
+
+  v = String(v);
+  w = String(w);
+  if (!_.isUndefined(name)) {
+    name = String(name);
+  }
+
+  if (_.isPlainObject(arguments[0])) {
+    v = arguments[0].v;
+    w = arguments[0].w;
+    name = arguments[0].name;
+    if (arguments.length === 2) {
+      value = arguments[1];
+      valueSpecified = true;
+    }
+  }
+
+  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");
+  }
+
+  // It didn't exist, so we need to create it.
+  // First ensure the nodes exist.
+  this.setNode(v);
+  this.setNode(w);
+
+  this._edgeLabels[e] = valueSpecified ? value : this._defaultEdgeLabelFn(v, w, name);
+
+  var edgeObj = edgeArgsToObj(this._isDirected, v, w, name);
+  // 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 (_.has(map, k)) {
+    map[k]++;
+  } else {
+    map[k] = 1;
+  }
+}
+
+function decrementOrRemoveEntry(map, k) {
+  if (!--map[k]) { delete map[k]; }
+}
+
+function edgeArgsToId(isDirected, v, w, name) {
+  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) {
+  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);
+}

lib/version.js

@@ -1,1 +0,1 @@
-module.exports = '1.0.0-pre1';
+module.exports = '1.0.0';

package.json

 {
   "name": "graphlib",
-  "version": "1.0.0-pre1",
+  "version": "1.0.0",
   "description": "A directed and undirected multi-graph library",
@@ -12,16 +12,20 @@ "author": "Chris Pettitt <[e-mail]>",
   "dependencies": {
-    "lodash": "^2.4.1",
-    "cp-data": "^1.1.3"
+    "lodash": "^2.4.1"
   },
   "devDependencies": {
     "benchmark": "^1.0.0",
-    "browserify": "^5.10.0",
-    "chai": "^1.9.1",
-    "gaze": "^0.6.4",
-    "istanbul": "^0.3.0",
-    "jscs": "^1.5.9",
-    "jshint": "^2.5.3",
-    "jshint-stylish": "^0.4.0",
-    "mocha": "^1.21.4",
-    "semver": "^3.0.1",
+    "browserify": "^6.1.0",
+    "chai": "^1.9.2",
+    "istanbul": "^0.3.2",
+    "jscs": "^1.7.3",
+    "jshint": "^2.5.6",
+    "jshint-stylish": "^1.0.0",
+    "karma": "^0.12.24",
+    "karma-chrome-launcher": "^0.1.5",
+    "karma-firefox-launcher": "^0.1.3",
+    "karma-mocha": "^0.1.9",
+    "karma-phantomjs-launcher": "^0.1.4",
+    "karma-safari-launcher": "^0.1.1",
+    "mocha": "^1.21.5",
+    "semver": "^4.1.0",
     "sprintf": "^0.1.4",
@@ -28,0 +32,0 @@ "uglify-js": "^2.4.15"

README.md

@@ -8,120 +8,10 @@ # Graphlib
 
-Note that graphlib is current a pre-1.0.0 library. We will do our best to
-maintain backwards compatibility for patch level increases (e.g. 0.0.1 to
-0.0.2) but make no claim to backwards compatibility across minor releases (e.g.
-0.0.1 to 0.1.0). Watch our [CHANGELOG](CHANGELOG.md) for details on changes.
+To learn more [see our Wiki](https://github.com/cpettitt/graphlib/wiki).
 
-# Getting Graphlib
-
-## NPM Install
-
-Before installing this library you need to install the [npm package manager].
-
-To get graphlib from npm, use:
-
-    $ npm install graphlib
-
-## Browser Scripts
-
-You can get the latest browser-ready scripts:
-
-* [graphlib.js](http://cpettitt.github.io/project/graphlib/latest/graphlib.js)
-* [graphlib.min.js](http://cpettitt.github.io/project/graphlib/latest/graphlib.min.js)
-
-## Build From Source
-
-Before building this library you need to install the [npm package manager].
-
-Check out this project and run this command from the root of the project:
-
-    $ make
-
-This will generate `graphlib.js` and `graphlib.min.js` in the `out/dist` directory
-of the project.
-
-# Example
-
-```js
-var Digraph = require("graphlib").Digraph;
-
-// Create a new empty graph
-var g = new Digraph();
-
-// Add node "A" to the graph with no value
-g.addNode("A");
-
-// This returns true
-g.hasNode("A");
-
-// Add node "B" to the graph with a String value
-g.addNode("B", "B's value");
-
-// Prints `B's value`
-console.log(g.node("B"));
-
-// Add node "C" to the graph with an Object value
-g.addNode("C", { k: 123 });
-g.addNode("D");
-
-// Prints `[ 'A', 'B', 'C', 'D' ]`
-console.log(g.nodes());
-
-// Add a directed edge with the ID "AB" from "A" to "B", but assign no value
-g.addEdge("AB", "A", "B");
-
-// Add a directed edge with no ID (Diraph will assign one) from "B" to "C"
-g.addEdge(null, "B", "C");
-
-// Add a directed edge from "C" to "D" with an Object value
-g.addEdge("CD", "C", "D", { k: 456 });
-
-// Since Digraph is a multi-graph, we can have multiple edges incident on the
-// same source and target nodes.
-g.addEdge("AB2", "A", "B");
-
-// Prints `[ 'AB', '_ANON-1', 'CD', 'AB2' ]`. `_ANON-1` is the edge from "B" to "C"
-console.log(g.edges());
-
-// Which edges go from "A" to "B"? This prints `[ 'AB', 'AB2' ]`
-console.log(g.outEdges("A", "B"));
-
-// Which edges are incident on "D"? This prints `[ 'CD' ]`
-console.log(g.incidentEdges("D"));
-
-// How about a subgraph?
-var g2 = g.subgraph(["A", "B", "C"]);
-
-// Prints `[ 'A', 'B', 'C' ]`
-console.log(g2.nodes());
-
-// Prints `[ 'AB', '_ANON-1', 'AB2' ]`. Note that edges that have both their
-// source and target nodes in the graph are also included in the subgraph.
-console.log(g2.edges());
-```
-
-# API
-
-[API documentation](http://cpettitt.github.io/project/graphlib/latest/doc/index.html)
-
-# Contributing
-
-We welcome contributions under the MIT license! Here are a few ways you can
-help:
-
-* Bug reports
-* Bug fixes
-* New algorithms
-* More test cases
-* Documentation improvements
-* Imrpovements to the core Graph API
-
-If your change involves change to the core Graph API, we recommend discussing
-the idea via a [GitHub issue](https://github.com/cpettitt/graphlib/issues)
-first.
-
 # License
 
-Graphlib is licensed under the terms of the MIT License. See the LICENSE file
-for details.
+Graphlib is licensed under the terms of the MIT License. See the
+[LICENSE](LICENSE) file
+aor details.
 
 [npm package manager]: http://npmjs.org/

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

Found 1 instance in 1 package

Uses eval

Supply chain risk

Package uses dynamic code execution (e.g., eval()), which is a dangerous practice. This can prevent the code from running in certain environments and increases the risk that the code may contain exploits or malicious behavior.

Found 1 instance in 1 package

Dynamic require

Supply chain risk

Dynamic require can indicate the package is performing dangerous or unsafe dynamic code execution.

Found 1 instance in 1 package

Minified code

Quality

This package contains minified code. This may be harmless in some cases where minified code is included in packaged libraries, however packages on npm should not minify code.

Found 2 instances in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

Found 1 instance in 1 package

No v1

Quality

Package is not semver >=1. This means it is not stable and does not support ^ ranges.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

425701

increased by1229.48%

Dependency count

1

decreased by-50%

Number of package files

35

increased by25%

Lines of code

9746

increased by1312.46%

Worsened metrics

Dev dependency count

17

increased by41.67%

Number of low quality alerts

3

increased by50%

Number of lines in readme file

17

decreased by-86.61%

Number of low supply chain risk alerts

13

increased byInfinity%

Number of medium supply chain risk alerts

3

increased by200%

Dependency changes

• - Removedcp-data@^1.1.3

• - Removedcp-data@1.1.3(transitive)