graphlib - npm Package Compare versions

Comparing version 0.0.6 to 0.1.0

CHANGELOG.md

@@ -0,1 +1,24 @@
+v0.1.0
+======
+
+This release introduces **backwards incompatible** changes.
+
+* `Graph` was renamed to `Digraph` in v0.0.4. This release removes `Graph`.
+  Please use `Digraph` in its place.
+* `Digraph.edges` no longer takes any arguments. It always returns all edges in
+  the graph.
+    * The equivalent of `Digraph.edges(u)` is now `Digraph.incidentEdges(u)`.
+    * The equivalent of `Digraph.edges(u, v)` is now `Digraph.outEdges(u, v)`
+      or `Digraph.inEdges(v, u)`.
+
+The following are backwards compatible changes:
+
+* Added a new optional parameter to `Digraph.outEdges` to filter the results by
+  the source node. See API documentation for details.
+* Added a new optional parameter to `Digraph.inEdges` to filter the results by
+  the target node. See API documentation for details.
+* Added a new method, `Digraph.incidentEdges`, that returns all edges incident
+  on a node `u` with `Digraph.incidentEdges(u)` or all edges between two nodes
+  - regardless of direction - with `Digraph.incidentEdges(u, v)`.
+
 v0.0.6
@@ -2,0 +25,0 @@ ======

index.js

 exports.Digraph = require("./lib/Digraph");
-exports.alg = require("./lib/alg");
+exports.alg = {
+  isAcyclic: require("./lib/alg/isAcyclic"),
+  findCycles: require("./lib/alg/findCycles"),
+  tarjan: require("./lib/alg/tarjan"),
+  topsort: require("./lib/alg/topsort")
+};
 exports.data = {
@@ -7,4 +12,1 @@ PriorityQueue: require("./lib/data/PriorityQueue")
 exports.version = require("./lib/version");
-
-// Backwards compatibility - to remove at next minor version bump
-exports.Graph = exports.Digraph;

lib/alg/topsort.js

@@ -13,3 +13,3 @@ module.exports = topsort;
  *
- * @param {Graph} g the graph to sort
+ * @param {Digraph} g the graph to sort
  */
@@ -16,0 +16,0 @@ function topsort(g) {

lib/Digraph.js

@@ -246,24 +246,16 @@ /*!
 /*
- * Return all edges with no arguments,
- * the ones that are incident on a node (one argument),
- * or all edges from a source to a target (two arguments)
- *
- * @param {String} [u] an optional node id
- * @param {String} [v] an optional node id
+ * Returns the ids of all edges in the graph.
  */
-Digraph.prototype.edges = function(u, v) {
-  var es, sourceEdges;
-  if (!arguments.length) {
-    es = [];
-    this.eachEdge(function(id) { es.push(id); });
-    return es;
-  } else if (arguments.length === 1) {
-    return util.mergeKeys([this.inEdges(u), this.outEdges(u)]);
-  } else if (arguments.length === 2) {
-    this._strictGetNode(u);
-    this._strictGetNode(v);
-    sourceEdges = this._outEdges[u];
-    es = (v in sourceEdges) ? Object.keys(sourceEdges[v].edges) : [];
-    return es.map(function(e) { return this._edges[e].id; }, this);
+Digraph.prototype.edges = function(u) {
+  if (arguments.length === 1) {
+    throw new Error("Digraph.edges() cannot be called with 1 argument. " +
+                    "Use Digraph.incidentEdges() instead.");
+  } else if (arguments.length > 1) {
+    throw new Error("Digraph.edges() cannot be called with more than 1 argument. " +
+                    "Use Digraph.outEdges() instead.");
   }
+
+  var es = [];
+  this.eachEdge(function(id) { es.push(id); });
+  return es;
 };
@@ -305,28 +297,71 @@
 /*
- * Returns the ids of all edges in the graph that have the node `target` as
- * their target. If the node `target` is not in the graph this function raises
- * an Error.
+ * Returns an array of ids for all edges in the graph that have the node
+ * `target` as their target. If the node `target` is not in the graph this
+ * function raises an Error.
  *
+ * Optionally a `source` node can also be specified. This causes the results
+ * to be filtered such that only edges from `source` to `target` are included.
+ * If the node `source` is specified but is not in the graph then this function
+ * raises an Error.
+ *
  * @param {String} target the target node id
+ * @param {String} [source] an optional source node id
  */
-Digraph.prototype.inEdges = function(target) {
+Digraph.prototype.inEdges = function(target, source) {
   this._strictGetNode(target);
-  return util.concat(util.values(this._inEdges[target])
-             .map(function(es) { return Object.keys(es.edges); }, this));
+  var results = util.concat(util.values(this._inEdges[target])
+                    .map(function(es) { return Object.keys(es.edges); }, this));
+  if (arguments.length > 1) {
+    this._strictGetNode(source);
+    results = results.filter(function(e) { return this.source(e) === source; }, this);
+  }
+  return results;
 };
 
 /*
- * Returns the ids of all nodes in the graph that have the node `source` as
- * their source. If the node `source` is not in the graph this function raises
- * an Error.
+ * Returns an array of ids for all edges in the graph that have the node
+ * `source` as their source. If the node `source` is not in the graph this
+ * function raises an Error.
  *
+ * Optionally a `target` node may also be specified. This causes the results
+ * to be filtered such that only edges from `source` to `target` are included.
+ * If the node `target` is specified but is not in the graph then this function
+ * raises an Error.
+ *
  * @param {String} source the source node id
+ * @param {String} [target] an optional target node id
  */
-Digraph.prototype.outEdges = function(source) {
+Digraph.prototype.outEdges = function(source, target) {
   this._strictGetNode(source);
-  return util.concat(util.values(this._outEdges[source])
-             .map(function(es) { return Object.keys(es.edges); }, this));
+  var results =  util.concat(util.values(this._outEdges[source])
+                     .map(function(es) { return Object.keys(es.edges); }, this));
+  if (arguments.length > 1) {
+    this._strictGetNode(target);
+    results = results.filter(function(e) { return this.target(e) === target; }, this);
+  }
+  return results;
 };
 
 /*
+ * Returns an array of ids for all edges in the graph that have the `u` as
+ * their source or their target. If the node `u` is not in the graph this
+ * function raises an Error.
+ *
+ * Optionally a `v` node may also be specified. This causes the results to be
+ * filtered such that only edges between `u` and `v` - in either direction -
+ * are included. IF the node `v` is specified but not in the graph then this
+ * function raises an Error.
+ *
+ * @param {String} u the node for which to find incident edges
+ * @param {String} [v] option node that must be adjacent to `u`
+ */
+Digraph.prototype.incidentEdges = function(u, v) {
+  if (arguments.length > 1) {
+    return util.mergeKeys([this.outEdges(u, v), this.outEdges(v, u)]);
+  } else {
+    return util.mergeKeys([this.inEdges(u), this.outEdges(u)]);
+  }
+};
+
+/*
  * Returns `true` if the values of all nodes and all edges are equal (===)
@@ -396,3 +431,3 @@ *
   var self = this;
-  this.edges(u).forEach(function(e) { self.delEdge(e); });
+  this.incidentEdges(u).forEach(function(e) { self.delEdge(e); });
 
@@ -399,0 +434,0 @@ delete this._inEdges[u];

lib/version.js

@@ -1,1 +0,1 @@
-module.exports = '0.0.6';
+module.exports = '0.1.0';

package.json

 {
   "name": "graphlib",
-  "version": "0.0.6",
+  "version": "0.1.0",
   "description": "A  multi-graph library",
@@ -5,0 +5,0 @@ "main": "index.js",

README.md

@@ -89,6 +89,6 @@ # Graphlib
 // Which edges go from "A" to "B"? This prints `[ 'AB', 'AB2' ]`
-console.log(g.edges("A", "B"));
+console.log(g.outEdges("A", "B"));
 
 // Which edges are incident on "D"? This prints `[ 'CD' ]`
-console.log(g.edges("D"));
+console.log(g.incidentEdges("D"));
 
@@ -95,0 +95,0 @@ // How about a subgraph?

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

32172

increased by8.37%

Lines of code

782

increased by3.99%

Worsened metrics

Number of package files

15

decreased by-6.25%

No dependency changes