graphlib - npm Package Compare versions

Comparing version 0.1.1 to 0.2.0

CHANGELOG.md

@@ -0,1 +1,7 @@
+v0.2.0
+======
+
+* Added an undirected multi-graph implementation (`Graph`).
+* Added a Set datatype (`data.Set`).
+
 v0.1.1
@@ -2,0 +8,0 @@ ======

index.js

 exports.Digraph = require("./lib/Digraph");
+exports.Graph = require("./lib/Graph");
 exports.alg = {
@@ -11,4 +12,5 @@ isAcyclic: require("./lib/alg/isAcyclic"),
 exports.data = {
-  PriorityQueue: require("./lib/data/PriorityQueue")
+  PriorityQueue: require("./lib/data/PriorityQueue"),
+  Set: require("./lib/data/Set")
 };
 exports.version = require("./lib/version");

lib/alg/dijkstra.js

@@ -1,2 +0,3 @@
-var PriorityQueue = require("../data/PriorityQueue");
+var PriorityQueue = require("../data/PriorityQueue"),
+    Digraph = require("../Digraph");
 
@@ -21,4 +22,4 @@ module.exports = dijkstra;
  * all edges incident to the node `u` for the purposes of shortest path
- * traversal. By default this function uses the `outEdges` function on the
- * supplied graph.
+ * traversal. By default this function uses the `g.outEdges` for Digraphs and
+ * `g.incidentEdges` for Graphs.
  *
@@ -39,3 +40,5 @@ * This function takes `O((|E| + |V|) * log |V|)` time.
   weightFunc = weightFunc || function() { return 1; };
-  incidentFunc = incidentFunc || function(u) { return g.outEdges(u); };
+  incidentFunc = incidentFunc || (g instanceof Digraph
+      ? function(u) { return g.outEdges(u); }
+      : function(u) { return g.incidentEdges(u); });
 
@@ -57,3 +60,4 @@ g.nodes().forEach(function(u) {
     incidentFunc(u).forEach(function(e) {
-      var v = g.source(e) !== u ? g.source(e) : g.target(e),
+      var incidentNodes = g.incidentNodes(e),
+          v = incidentNodes[0] !== u ? incidentNodes[0] : incidentNodes[1],
           vEntry = results[v],
@@ -60,0 +64,0 @@ weight = weightFunc(e),

lib/alg/dijkstraAll.js

@@ -23,3 +23,3 @@ var dijkstra = require("./dijkstra");
  *
- * [dijkstra]: dijkstra.js.html#dijkstra
+ * [alg.dijkstra]: dijkstra.js.html#dijkstra
  *
@@ -26,0 +26,0 @@ * @param {Graph} g the graph to search for shortest paths from **source**

lib/alg/tarjan.js

@@ -0,1 +1,3 @@
+var Digraph = require("../Digraph");
+
 module.exports = tarjan;
@@ -21,5 +23,9 @@
 function tarjan(g) {
+  if (!(g instanceof Digraph)) {
+    throw new Error("tarjan can only be applied to a Digraph. Bad input: " + g);
+  }
+
   var index = 0,
       stack = [],
-      visited = {}; // node id -> { onStack, lowlink, index }
+      visited = {}, // node id -> { onStack, lowlink, index }
       results = [];
@@ -26,0 +32,0 @@

lib/alg/topsort.js

@@ -0,1 +1,3 @@
+var Digraph = require("../Digraph");
+
 module.exports = topsort;
@@ -16,2 +18,6 @@ topsort.CycleException = CycleException;
 function topsort(g) {
+  if (!(g instanceof Digraph)) {
+    throw new Error("topsort can only be applied to a Digraph. Bad input: " + g);
+  }
+
   var visited = {};
@@ -18,0 +24,0 @@ var stack = {};

lib/data/PriorityQueue.js

@@ -53,3 +53,3 @@ module.exports = PriorityQueue;
  */
-PriorityQueue.prototype.min = function(key) {
+PriorityQueue.prototype.min = function() {
   if (this.size() === 0) {
@@ -56,0 +56,0 @@ throw new Error("Queue underflow");

lib/Digraph.js

@@ -11,3 +11,4 @@ /*!
 
-var util = require("./util");
+var util = require("./util"),
+    Set = require("./data/Set");
 
@@ -26,6 +27,6 @@ module.exports = Digraph;
 
-  /*! Map of sourceId -> {targetId -> {count, edgeId -> true}} */
+  /*! Map of sourceId -> {targetId -> Set of edge ids} */
   this._inEdges = {};
 
-  /*! Map of targetId -> {sourceId -> {count, edgeId -> true}} */
+  /*! Map of targetId -> {sourceId -> Set of edge ids} */
   this._outEdges = {};
@@ -131,3 +132,3 @@
   var nodes = [];
-  this.eachNode(function(id, _) { nodes.push(id); });
+  this.eachNode(function(id) { nodes.push(id); });
   return nodes;
@@ -185,13 +186,3 @@ };
 Digraph.prototype.neighbors = function(u) {
-  this._strictGetNode(u);
-  var vs = {};
-
-  Object.keys(this._outEdges[u])
-        .map(function(v) { vs[v] = true; });
-
-  Object.keys(this._inEdges[u])
-        .map(function(v) { vs[v] = true; });
-
-  return Object.keys(vs)
-               .map(function(v) { return this._nodes[v].id; }, this);
+  return Set.unionAll([this.successors(u), this.predecessors(u)]).keys();
 };
@@ -252,3 +243,3 @@
  */
-Digraph.prototype.edges = function(u) {
+Digraph.prototype.edges = function() {
   if (arguments.length === 1) {
@@ -300,2 +291,11 @@ throw new Error("Digraph.edges() cannot be called with 1 argument. " +
 
+/**
+ * Returns the nodes that are a part of this graph in a 2 element array. The
+ * source is placed in the 0 index and the target in the 1 index.
+ */
+Digraph.prototype.incidentNodes = function(e) {
+  var edge = this._strictGetEdge(e);
+  return [edge.source, edge.target];
+};
+
 /*
@@ -316,4 +316,3 @@ * Returns an array of ids for all edges in the graph that have the node
   this._strictGetNode(target);
-  var results = util.concat(util.values(this._inEdges[target])
-                    .map(function(es) { return Object.keys(es.edges); }, this));
+  var results = Set.unionAll(util.values(this._inEdges[target])).keys();
   if (arguments.length > 1) {
@@ -341,4 +340,3 @@ this._strictGetNode(source);
   this._strictGetNode(source);
-  var results =  util.concat(util.values(this._outEdges[source])
-                     .map(function(es) { return Object.keys(es.edges); }, this));
+  var results = Set.unionAll(util.values(this._outEdges[source])).keys();
   if (arguments.length > 1) {
@@ -366,5 +364,5 @@ this._strictGetNode(target);
   if (arguments.length > 1) {
-    return util.mergeKeys([this.outEdges(u, v), this.outEdges(v, u)]);
+    return Set.unionAll([this.outEdges(u, v), this.outEdges(v, u)]).keys();
   } else {
-    return util.mergeKeys([this.inEdges(u), this.outEdges(u)]);
+    return Set.unionAll([this.inEdges(u), this.outEdges(u)]).keys();
   }
@@ -392,3 +390,3 @@ };
   var self = this;
-  var str = "GRAPH: " + JSON.stringify(self._value) + "\n";
+  var str = "Digraph: " + JSON.stringify(self._value) + "\n";
   str += "    Nodes:\n";
@@ -405,3 +403,3 @@ Object.keys(this._nodes)
           str += "        " + e + " (" + edge.source + " -> " + edge.target + "): " +
-                 JSON.stringify(self._edges[e].value) + "\n";
+                 JSON.stringify(edge.value) + "\n";
         });
@@ -449,3 +447,3 @@
  * Adds a new edge to the graph with the id `e` from a node with the id `source`
- * to a noce with an id `target` and assigns it the value `value`. This graph
+ * to a node with an id `target` and assigns it the value `value`. This graph
  * allows more than one edge from `source` to `target` as long as the id `e`
@@ -510,3 +508,3 @@ * is unique in the set of edges. If `e` is `null` the graph will assign a
   var filtered = [];
-  this.eachNode(function(u, value) {
+  this.eachNode(function(u) {
     if (pred(u)) {
@@ -520,8 +518,3 @@ filtered.push(u);
 function addEdgeToMap(map, v, e) {
-  var vEntry = map[v];
-  if (!vEntry) {
-    vEntry = map[v] = { count: 0, edges: {} };
-  }
-  vEntry.count++;
-  vEntry.edges[e] = true;
+  (map[v] || (map[v] = new Set())).add(e);
 }
@@ -531,8 +524,7 @@
   var vEntry = map[v];
-  if (--vEntry.count === 0) {
+  vEntry.remove(e);
+  if (vEntry.size() === 0) {
     delete map[v];
-  } else {
-    delete vEntry.edges[e];
   }
 }
 

lib/util.js

@@ -9,3 +9,3 @@ // Returns `true` only if `f(x)` is `true` for all `x` in **xs**. Otherwise
   return true;
-}
+};
 
@@ -15,18 +15,2 @@ // Returns an array of all values for properties of **o**.
   return Object.keys(o).map(function(k) { return o[k]; });
-}
-
-// Joins all of the arrays **xs** into a single array.
-exports.concat = function(xs) {
-  return Array.prototype.concat.apply([], xs);
-}
-
-// Similar to **concat**, but all duplicates are removed
-exports.mergeKeys = function(xs) {
-  var obj = {};
-  xs.forEach(function(x) {
-    x.forEach(function(o) {
-      obj[o] = o;
-    });
-  });
-  return exports.values(obj);
-}
+};

lib/version.js

@@ -1,1 +0,1 @@
-module.exports = '0.1.1';
+module.exports = '0.2.0';

package.json

 {
   "name": "graphlib",
-  "version": "0.1.1",
+  "version": "0.2.0",
   "description": "A  multi-graph library",
@@ -9,3 +9,10 @@ "main": "index.js",
   ],
+  "scripts": {
+    "blanket": {
+      "pattern": "lib",
+      "data-cover-never": "node_modules"
+    }
+  },
   "devDependencies": {
+    "blanket": "1.x.x",
     "browserify": "2.28.x",
@@ -12,0 +19,0 @@ "chai": "1.7.x",

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

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

Improved metrics

Total package byte prevSize

50899

increased by39.59%

Number of package files

19

increased by11.76%

Lines of code

1344

increased by52.55%

Worsened metrics

Dev dependency count

7

increased by16.67%

No dependency changes