graphlib - npm Package Compare versions

Comparing version 0.7.4 to 1.0.0-pre1

CHANGELOG.md

@@ -0,1 +1,6 @@
+v1.0.0
+======
+
+* Massive rewrite to the API for 1.0. API TBD on the wiki.
+
 v0.7.4
@@ -2,0 +7,0 @@ ======

index.js

@@ -1,31 +0,53 @@
-exports.Graph = require("./lib/Graph");
-exports.Digraph = require("./lib/Digraph");
-exports.CGraph = require("./lib/CGraph");
-exports.CDigraph = require("./lib/CDigraph");
-require("./lib/graph-converters");
+/**
+ * Copyright (c) 2014, Chris Pettitt
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright notice, this
+ * list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright notice,
+ * this list of conditions and the following disclaimer in the documentation
+ * and/or other materials provided with the distribution.
+ *
+ * 3. Neither the name of the copyright holder nor the names of its contributors
+ * may be used to endorse or promote products derived from this software without
+ * specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+module.exports = {
+  Digraph: require("./lib/digraph"),
+  CDigraph: require("./lib/compound-digraph"),
 
-exports.alg = {
-  isAcyclic: require("./lib/alg/isAcyclic"),
-  components: require("./lib/alg/components"),
-  dijkstra: require("./lib/alg/dijkstra"),
-  dijkstraAll: require("./lib/alg/dijkstraAll"),
-  findCycles: require("./lib/alg/findCycles"),
-  floydWarshall: require("./lib/alg/floydWarshall"),
-  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")
-};
+  Graph: require("./lib/graph"),
+  CGraph: require("./lib/compound-graph"),
 
-exports.converter = {
-  json: require("./lib/converter/json.js")
-};
+  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")
+  },
 
-var filter = require("./lib/filter");
-exports.filter = {
-  all: filter.all,
-  nodesFromList: filter.nodesFromList
+  util: require("./lib/util"),
+  version: require("./lib/version")
 };
-
-exports.version = require("./lib/version");

lib/alg/components.js

@@ -1,35 +0,20 @@
-/* jshint -W079 */
-var Set = require("cp-data").Set;
-/* jshint +W079 */
+var _ = require("lodash");
 
 module.exports = components;
 
-/**
- * Finds all [connected components][] in a graph and returns an array of these
- * components. Each component is itself an array that contains the ids of nodes
- * in the component.
- *
- * This function only works with undirected Graphs.
- *
- * [connected components]: http://en.wikipedia.org/wiki/Connected_component_(graph_theory)
- *
- * @param {Graph} g the graph to search for components
- */
 function components(g) {
   var results = [];
-  var visited = new Set();
+  var visited = {};
 
-  function dfs(v, component) {
-    if (!visited.has(v)) {
-      visited.add(v);
+  function dfs(component, v) {
+    if (!_.has(visited, v)) {
+      visited[v] = true;
       component.push(v);
-      g.neighbors(v).forEach(function(w) {
-        dfs(w, component);
-      });
+      _.each(g.neighbors(v), _.partial(dfs, component));
     }
   }
 
-  g.nodes().forEach(function(v) {
+  _.each(g.nodeIds(), function(v) {
     var component = [];
-    dfs(v, component);
+    dfs(component, v);
     if (component.length > 0) {
@@ -36,0 +21,0 @@ results.push(component);

lib/alg/dijkstra.js

@@ -1,75 +0,51 @@
-var PriorityQueue = require("cp-data").PriorityQueue;
+var PriorityQueue = require("cp-data").PriorityQueue,
+    _ = require("lodash");
 
 module.exports = dijkstra;
 
-/**
- * This function is an implementation of [Dijkstra's algorithm][] which finds
- * the shortest path from **source** to all other nodes in **g**. This
- * function returns a map of `u -> { distance, predecessor }`. The distance
- * property holds the sum of the weights from **source** to `u` along the
- * shortest path or `Number.POSITIVE_INFINITY` if there is no path from
- * **source**. The predecessor property can be used to walk the individual
- * elements of the path from **source** to **u** in reverse order.
- *
- * This function takes an optional `weightFunc(e)` which returns the
- * weight of the edge `e`. If no weightFunc is supplied then each edge is
- * assumed to have a weight of 1. This function throws an Error if any of
- * the traversed edges have a negative edge weight.
- *
- * This function takes an optional `incidentFunc(u)` which returns the ids of
- * all edges incident to the node `u` for the purposes of shortest path
- * traversal. By default this function uses the `g.outEdges` for Digraphs and
- * `g.incidentEdges` for Graphs.
- *
- * This function takes `O((|E| + |V|) * log |V|)` time.
- *
- * [Dijkstra's algorithm]: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
- *
- * @param {Graph} g the graph to search for shortest paths from **source**
- * @param {Object} source the source from which to start the search
- * @param {Function} [weightFunc] optional weight function
- * @param {Function} [incidentFunc] optional incident function
- */
-function dijkstra(g, source, weightFunc, incidentFunc) {
+var DEFAULT_WEIGHT_FUNC = _.constant(1);
+
+function dijkstra(g, source, weightFunc, edgeFunc) {
+  return runDijkstra(g, String(source),
+                     weightFunc || DEFAULT_WEIGHT_FUNC,
+                     edgeFunc || function(v) { return g.outEdges(v); });
+}
+
+function runDijkstra(g, source, weightFunc, edgeFunc) {
   var results = {},
-      pq = new PriorityQueue();
+      pq = new PriorityQueue(),
+      v, vEntry;
 
-  function updateNeighbors(e) {
-    var incidentNodes = g.incidentNodes(e),
-        v = incidentNodes[0] !== u ? incidentNodes[0] : incidentNodes[1],
-        vEntry = results[v],
-        weight = weightFunc(e),
-        distance = uEntry.distance + weight;
+  var updateNeighbors = function(edge) {
+    var w = edge.v !== v ? edge.v : edge.w,
+        wEntry = results[w],
+        weight = weightFunc(edge),
+        distance = vEntry.distance + weight;
 
     if (weight < 0) {
-      throw new Error("dijkstra does not allow negative edge weights. Bad edge: " + e + " Weight: " + weight);
+      throw new Error("dijkstra does not allow negative edge weights. " +
+                      "Bad edge: " + edge + " Weight: " + weight);
     }
 
-    if (distance < vEntry.distance) {
-      vEntry.distance = distance;
-      vEntry.predecessor = u;
-      pq.decrease(v, distance);
+    if (distance < wEntry.distance) {
+      wEntry.distance = distance;
+      wEntry.predecessor = v;
+      pq.decrease(w, distance);
     }
-  }
+  };
 
-  weightFunc = weightFunc || function() { return 1; };
-  incidentFunc = incidentFunc || (g.isDirected()
-      ? function(u) { return g.outEdges(u); }
-      : function(u) { return g.incidentEdges(u); });
-
-  g.eachNode(function(u) {
-    var distance = u === source ? 0 : Number.POSITIVE_INFINITY;
-    results[u] = { distance: distance };
-    pq.add(u, distance);
+  g.nodeIds().forEach(function(v) {
+    var distance = v === source ? 0 : Number.POSITIVE_INFINITY;
+    results[v] = { distance: distance };
+    pq.add(v, distance);
   });
 
-  var u, uEntry;
   while (pq.size() > 0) {
-    u = pq.removeMin();
-    uEntry = results[u];
-    if (uEntry.distance === Number.POSITIVE_INFINITY) {
+    v = pq.removeMin();
+    vEntry = results[v];
+    if (vEntry.distance === Number.POSITIVE_INFINITY) {
       break;
     }
 
-    incidentFunc(u).forEach(updateNeighbors);
+    edgeFunc(v).forEach(updateNeighbors);
   }
@@ -76,0 +52,0 @@

lib/alg/postorder.js

@@ -1,25 +0,25 @@
-/* jshint -W079 */
-var Set = require("cp-data").Set;
-/* jshint +W079 */
+var _ = require("lodash");
 
 module.exports = postorder;
 
-// Postorder traversal of g, calling f for each visited node. Assumes the graph
-// is a tree.
-function postorder(g, root, f) {
-  var visited = new Set();
-  if (g.isDirected()) {
-    throw new Error("This function only works for undirected graphs");
+function postorder(g, root) {
+  var visited = {},
+      results = [];
+
+  dfs(g, root, undefined, visited, results);
+
+  return results;
+}
+
+function dfs(g, v, prev, visited, results) {
+  if (_.has(visited, v)) {
+    throw new Error("The input graph is not a tree: " + g);
   }
-  function dfs(u, prev) {
-    if (visited.has(u)) {
-      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);
     }
-    visited.add(u);
-    g.neighbors(u).forEach(function(v) {
-      if (v !== prev) dfs(v, u);
-    });
-    f(u);
-  }
-  dfs(root);
+  });
+  results.push(v);
 }

lib/alg/preorder.js

@@ -1,25 +0,25 @@
-/* jshint -W079 */
-var Set = require("cp-data").Set;
-/* jshint +W079 */
+var _ = require("lodash");
 
 module.exports = preorder;
 
-// Preorder traversal of g, calling f for each visited node. Assumes the graph
-// is a tree.
-function preorder(g, root, f) {
-  var visited = new Set();
-  if (g.isDirected()) {
-    throw new Error("This function only works for undirected graphs");
+function preorder(g, root) {
+  var visited = {},
+      results = [];
+
+  dfs(g, root, undefined, visited, results);
+
+  return results;
+}
+
+function dfs(g, v, prev, visited, results) {
+  if (_.has(visited, v)) {
+    throw new Error("The input graph is not a tree: " + g);
   }
-  function dfs(u, prev) {
-    if (visited.has(u)) {
-      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);
     }
-    visited.add(u);
-    f(u);
-    g.neighbors(u).forEach(function(v) {
-      if (v !== prev) dfs(v, u);
-    });
-  }
-  dfs(root);
+  });
 }

lib/alg/prim.js

@@ -1,2 +0,3 @@
-var Graph = require("../Graph"),
+var _ = require("lodash"),
+    Graph = require("../Graph"),
     PriorityQueue = require("cp-data").PriorityQueue;
@@ -6,19 +7,2 @@
 
-/**
- * [Prim's algorithm][] takes a connected undirected graph and generates a
- * [minimum spanning tree][]. This function returns the minimum spanning
- * tree as an undirected graph. This algorithm is derived from the description
- * in "Introduction to Algorithms", Third Edition, Cormen, et al., Pg 634.
- *
- * This function takes a `weightFunc(e)` which returns the weight of the edge
- * `e`. It throws an Error if the graph is not connected.
- *
- * This function takes `O(|E| log |V|)` time.
- *
- * [Prim's algorithm]: https://en.wikipedia.org/wiki/Prim's_algorithm
- * [minimum spanning tree]: https://en.wikipedia.org/wiki/Minimum_spanning_tree
- *
- * @param {Graph} g the graph used to generate the minimum spanning tree
- * @param {Function} weightFunc the weight function to use
- */
 function prim(g, weightFunc) {
@@ -28,13 +12,12 @@ var result = new Graph(),
       pq = new PriorityQueue(),
-      u;
+      v;
 
-  function updateNeighbors(e) {
-    var incidentNodes = g.incidentNodes(e),
-        v = incidentNodes[0] !== u ? incidentNodes[0] : incidentNodes[1],
-        pri = pq.priority(v);
+  function updateNeighbors(edge) {
+    var w = edge.v === v ? edge.w : edge.v,
+        pri = pq.priority(w);
     if (pri !== undefined) {
-      var edgeWeight = weightFunc(e);
+      var edgeWeight = weightFunc(edge);
       if (edgeWeight < pri) {
-        parents[v] = u;
-        pq.decrease(v, edgeWeight);
+        parents[w] = v;
+        pq.decrease(w, edgeWeight);
       }
@@ -44,19 +27,19 @@ }
 
-  if (g.order() === 0) {
+  if (g.nodeCount() === 0) {
     return result;
   }
 
-  g.eachNode(function(u) {
-    pq.add(u, Number.POSITIVE_INFINITY);
-    result.addNode(u);
+  _.each(g.nodeIds(), function(v) {
+    pq.add(v, Number.POSITIVE_INFINITY);
+    result.setNode(v);
   });
 
   // Start from an arbitrary node
-  pq.decrease(g.nodes()[0], 0);
+  pq.decrease(g.nodeIds()[0], 0);
 
   var init = false;
   while (pq.size() > 0) {
-    u = pq.removeMin();
-    if (u in parents) {
-      result.addEdge(null, u, parents[u]);
+    v = pq.removeMin();
+    if (_.has(parents, v)) {
+      result.setEdge(v, parents[v]);
     } else if (init) {
@@ -68,3 +51,3 @@ throw new Error("Input graph is not connected: " + g);
 
-    g.incidentEdges(u).forEach(updateNeighbors);
+    g.nodeEdges(v).forEach(updateNeighbors);
   }
@@ -71,0 +54,0 @@

lib/alg/tarjan.js

@@ -0,25 +1,6 @@
+var _ = require("lodash");
+
 module.exports = tarjan;
 
-/**
- * This function is an implementation of [Tarjan's algorithm][] which finds
- * all [strongly connected components][] in the directed graph **g**. Each
- * strongly connected component is composed of nodes that can reach all other
- * nodes in the component via directed edges. A strongly connected component
- * can consist of a single node if that node cannot both reach and be reached
- * by any other specific node in the graph. Components of more than one node
- * are guaranteed to have at least one cycle.
- *
- * This function returns an array of components. Each component is itself an
- * array that contains the ids of all nodes in the component.
- *
- * [Tarjan's algorithm]: http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm
- * [strongly connected components]: http://en.wikipedia.org/wiki/Strongly_connected_component
- *
- * @param {Digraph} g the graph to search for strongly connected components
- */
 function tarjan(g) {
-  if (!g.isDirected()) {
-    throw new Error("tarjan can only be applied to a directed graph. Bad input: " + g);
-  }
-
   var index = 0,
@@ -30,4 +11,4 @@ stack = [],
 
-  function dfs(u) {
-    var entry = visited[u] = {
+  function dfs(v) {
+    var entry = visited[v] = {
       onStack: true,
@@ -37,10 +18,10 @@ lowlink: index,
     };
-    stack.push(u);
+    stack.push(v);
 
-    g.successors(u).forEach(function(v) {
-      if (!(v in visited)) {
-        dfs(v);
-        entry.lowlink = Math.min(entry.lowlink, visited[v].lowlink);
-      } else if (visited[v].onStack) {
-        entry.lowlink = Math.min(entry.lowlink, visited[v].index);
+    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);
       }
@@ -51,8 +32,8 @@ });
       var cmpt = [],
-          v;
+          w;
       do {
-        v = stack.pop();
-        visited[v].onStack = false;
-        cmpt.push(v);
-      } while (u !== v);
+        w = stack.pop();
+        visited[w].onStack = false;
+        cmpt.push(w);
+      } while (v !== w);
       results.push(cmpt);
@@ -62,5 +43,5 @@ }
 
-  g.nodes().forEach(function(u) {
-    if (!(u in visited)) {
-      dfs(u);
+  g.nodeIds().forEach(function(v) {
+    if (!_.has(visited, v)) {
+      dfs(v);
     }
@@ -67,0 +48,0 @@ });

lib/alg/topsort.js

@@ -0,35 +1,20 @@
+var _ = require("lodash");
+
 module.exports = topsort;
 topsort.CycleException = CycleException;
 
-/*
- * Given a graph **g**, this function returns an ordered list of nodes such
- * that for each edge `u -> v`, `u` appears before `v` in the list. If the
- * graph has a cycle it is impossible to generate such a list and
- * **CycleException** is thrown.
- *
- * See [topological sorting](https://en.wikipedia.org/wiki/Topological_sorting)
- * for more details about how this algorithm works.
- *
- * @param {Digraph} g the graph to sort
- */
 function topsort(g) {
-  if (!g.isDirected()) {
-    throw new Error("topsort can only be applied to a directed graph. Bad input: " + g);
-  }
+  var visited = {},
+      stack = {},
+      results = [];
 
-  var visited = {};
-  var stack = {};
-  var results = [];
-
   function visit(node) {
-    if (node in stack) {
+    if (_.has(stack, node)) {
       throw new CycleException();
     }
 
-    if (!(node in visited)) {
+    if (!_.has(visited, node)) {
       stack[node] = true;
       visited[node] = true;
-      g.predecessors(node).forEach(function(pred) {
-        visit(pred);
-      });
+      _.each(g.predecessors(node), visit);
       delete stack[node];
@@ -40,11 +25,8 @@ results.push(node);
 
-  var sinks = g.sinks();
-  if (g.order() !== 0 && sinks.length === 0) {
+  _.each(g.sinks(), visit);
+
+  if (_.size(visited) !== g.nodeCount()) {
     throw new CycleException();
   }
 
-  g.sinks().forEach(function(sink) {
-    visit(sink);
-  });
-
   return results;
@@ -54,5 +36,1 @@ }
 function CycleException() {}
-
-CycleException.prototype.toString = function() {
-  return "Graph has at least one cycle";
-};

lib/util.js

@@ -1,11 +0,1 @@
-// Returns an array of all values for properties of **o**.
-exports.values = function(o) {
-  var ks = Object.keys(o),
-      len = ks.length,
-      result = new Array(len),
-      i;
-  for (i = 0; i < len; ++i) {
-    result[i] = o[ks[i]];
-  }
-  return result;
-};
+exports.LABEL_WEIGHT_FUNC = function(edge) { return edge.label; };

lib/version.js

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

package.json

 {
   "name": "graphlib",
-  "version": "0.7.4",
+  "version": "1.0.0-pre1",
   "description": "A directed and undirected multi-graph library",
+  "author": "Chris Pettitt <[e-mail]>",
   "main": "index.js",
@@ -11,17 +12,19 @@ "keywords": [
   "dependencies": {
-    "cp-data": "1.1.3"
+    "lodash": "^2.4.1",
+    "cp-data": "^1.1.3"
   },
   "devDependencies": {
-    "benchmark": "~1.0.0",
-    "browserify": "~2.35.1",
-    "chai": "1.8.x",
-    "jade": "0.35.x",
-    "jshint": "2.1.x",
-    "istanbul": "~0.1.44",
-    "marked": "0.2.x",
-    "mocha": "1.12.x",
-    "semver": "2.1.x",
-    "uglify-js": "1.2.3"
+    "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",
+    "sprintf": "^0.1.4",
+    "uglify-js": "^2.4.15"
   },
-  "author": "Chris Pettitt <[e-mail]>",
   "repository": {
@@ -28,0 +31,0 @@ "type": "git",

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

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

Worsened metrics

Total package byte prevSize

32020

decreased by-39.01%

Dependency count

2

increased by100%

Dev dependency count

12

increased by20%

Number of package files

28

decreased by-6.67%

Lines of code

690

decreased by-46.39%

Number of medium supply chain risk alerts

1

increased byInfinity%

Dependency changes

• + Addedlodash@^2.4.1

• + Addedlodash@2.4.2(transitive)

• Updatedcp-data@^1.1.3