js-graph - npm Package Compare versions

Comparing version 0.2.0 to 0.3.0

bower.json

 {
 	"name": "js-graph",
-	"version": "0.2.0",
+	"version": "0.3.0",
 	"description": "a javascript library for storing arbitrary data in mathematical (di)graphs, as well as traversing and analyzing them in various ways",
@@ -5,0 +5,0 @@ "ignore": [

dist/js-graph.js

@@ -324,4 +324,5 @@ 'use strict';
 		that.eachVertex = function (handler) {
-			Object.keys(_vertices).forEach(function (key) {
-				handler(key, _vertices[key]);
+			Object.keys(_vertices).every(function (key) {
+				var r = handler(key, _vertices[key]);
+				return (r !== false);
 			});
@@ -336,4 +337,5 @@ };
 
-			Object.keys(_edges[from]).forEach(function (to) {
-				handler(to, that.vertexValue(to), that.edgeValue(from, to));
+			Object.keys(_edges[from]).every(function (to) {
+				var r = handler(to, that.vertexValue(to), that.edgeValue(from, to));
+				return (r !== false);
 			});
@@ -348,4 +350,5 @@ };
 
-			Object.keys(_reverseEdges[to]).forEach(function (from) {
-				handler(from, that.vertexValue(from), that.edgeValue(from, to));
+			Object.keys(_reverseEdges[to]).every(function (from) {
+				var r = handler(from, that.vertexValue(from), that.edgeValue(from, to));
+				return (r !== false);
 			});
@@ -356,5 +359,6 @@ };
 		that.eachEdge = function (handler) {
-			Object.keys(_edges).forEach(function (from) {
-				Object.keys(_edges[from]).forEach(function (to) {
-					handler(from, to, _edges[from][to]);
+			Object.keys(_edges).every(function (from) {
+				return Object.keys(_edges[from]).every(function (to) {
+					var r = handler(from, to, _edges[from][to]);
+					return (r !== false);
 				});
@@ -374,3 +378,40 @@ });
 
+		that.hasCycle = function () {
+			var visited = {};
+			var handled = {};
 
+			var cycleFound = false;
+
+			function visit(a) {
+				//// if a cycle is found, record it and return
+				//
+				if (visited[a]) {
+					cycleFound = true;
+					return;
+				}
+
+				//// if this vertex was already handled, no cycle can be found here
+				//
+				if (handled[a]) { return }
+				handled[a] = true;
+
+				//// recursively visit successors to check for cycles
+				//
+				visited[a] = true;
+				that.eachVertexFrom(a, function (b) {
+					visit(b);
+					if (cycleFound) { return false }
+				});
+				visited[a] = false;
+			}
+
+			that.eachVertex(function (a) {
+				visit(a);
+				if (cycleFound) { return false }
+			});
+
+			return cycleFound;
+		};
+
+
 		that.hasPath = function (from, to) {
@@ -377,0 +418,0 @@ if (!that.hasVertex(from) || !that.hasVertex(to)) {

dist/js-graph.min.js

@@ -1,3 +0,3 @@
-/* js-graph - v0.1.0 - 2014-09-23 */
-"use strict";!function(a,b,c){"function"==typeof define&&define.amd?define([],c):"object"==typeof exports?module.exports=c():a[b]=c()}(this,"JsGraph",function(){function a(){var b=this,d={},e={},f={},g=0,h=0,i=new c,j=new c;b.onAddVertex=i.add,b.onRemoveVertex=j.add,b.addNewVertex=function(c,h){if(b.hasVertex(c))throw new a.VertexExistsError(c,d[c]);d[c]=h,e[c]={},f[c]={},g+=1,i.fire(c,h)},b.setVertex=function(c,e){if(!b.hasVertex(c))throw new a.VertexNotExistsError(c);d[c]=e},b.ensureVertex=function(a,c){b.hasVertex(a)||b.addNewVertex(a,c)},b.addVertex=function(a,c){b.hasVertex(a)?b.setVertex(a,c):b.addNewVertex(a,c)},b.removeExistingVertex=function(c){if(!b.hasVertex(c))throw new a.VertexNotExistsError(c);if(Object.keys(e[c]).length)throw new a.HasConnectedEdgesError(c);if(Object.keys(f[c]).length)throw new a.HasConnectedEdgesError(c);var h=d[c];delete d[c],g-=1,j.fire(c,h)},b.destroyExistingVertex=function(c){if(!b.hasVertex(c))throw new a.VertexNotExistsError(c);b.eachVertexFrom(c,function(a){b.removeEdge(c,a)}),b.eachVertexTo(c,function(a){b.removeEdge(a,c)}),b.removeExistingVertex(c)},b.removeVertex=function(a){b.hasVertex(a)&&b.removeExistingVertex(a)},b.destroyVertex=function(a){b.hasVertex(a)&&b.destroyExistingVertex(a)};var k=new c,l=new c;b.onAddEdge=k.add,b.onRemoveEdge=l.add,b.addNewEdge=function(c,d,g){if(b.hasEdge(c,d))throw new a.EdgeExistsError(c,d,b.edgeValue(c,d));if(!b.hasVertex(c))throw b.hasVertex(d)?new a.VertexNotExistsError(c):new a.VertexNotExistsError(c).v(d);if(!b.hasVertex(d))throw new a.VertexNotExistsError(d);e[c][d]=g,f[d][c]=null,h+=1,k.fire(c,d,g)},b.createNewEdge=function(c,d,e){if(b.hasEdge(c,d))throw new a.EdgeExistsError(c,d,b.edgeValue(c,d));b.ensureVertex(c),b.ensureVertex(d),b.addNewEdge(c,d,e)},b.setEdge=function(c,d,f){if(!b.hasEdge(c,d))throw new a.EdgeNotExistsError(c,d);e[c][d]=f},b.spanEdge=function(c,d,e){if(!b.hasVertex(c))throw b.hasVertex(d)?new a.VertexNotExistsError(c):new a.VertexNotExistsError(c).v(d);if(!b.hasVertex(d))throw new a.VertexNotExistsError(d);b.hasEdge(c,d)||b.addNewEdge(c,d,e)},b.addEdge=function(a,c,d){b.hasEdge(a,c)?b.setEdge(a,c,d):b.addNewEdge(a,c,d)},b.ensureEdge=function(a,c,d){b.hasEdge(a,c)||b.createNewEdge(a,c,d)},b.createEdge=function(a,c,d){b.hasEdge(a,c)?b.setEdge(a,c,d):b.createNewEdge(a,c,d)},b.removeExistingEdge=function(c,d){if(!b.hasEdge(c,d))throw new a.EdgeNotExistsError(c,d);var g=e[c][d];delete e[c][d],delete f[d][c],h-=1,l.fire(c,d,g)},b.removeEdge=function(a,c){b.hasEdge(a,c)&&b.removeExistingEdge(a,c)},b.vertexCount=function(){return g},b.hasVertex=function(a){return a in d},b.vertexValue=function(a){return d[a]},b.edgeCount=function(){return h},b.hasEdge=function(a,c){return b.hasVertex(a)&&b.hasVertex(c)&&a in e&&c in e[a]},b.edgeValue=function(a,c){return b.hasEdge(a,c)?e[a][c]:void 0},b.successors=function(c){if(!b.hasVertex(c))throw new a.VertexNotExistsError(c);return Object.keys(e[c])},b.predecessors=function(c){if(!b.hasVertex(c))throw new a.VertexNotExistsError(c);return Object.keys(f[c])},b.eachVertex=function(a){Object.keys(d).forEach(function(b){a(b,d[b])})},b.eachVertexFrom=function(c,d){if(!b.hasVertex(c))throw new a.VertexNotExistsError(c);Object.keys(e[c]).forEach(function(a){d(a,b.vertexValue(a),b.edgeValue(c,a))})},b.eachVertexTo=function(c,d){if(!b.hasVertex(c))throw new a.VertexNotExistsError(c);Object.keys(f[c]).forEach(function(a){d(a,b.vertexValue(a),b.edgeValue(a,c))})},b.eachEdge=function(a){Object.keys(e).forEach(function(b){Object.keys(e[b]).forEach(function(c){a(b,c,e[b][c])})})},b.clearEdges=function(){b.eachEdge(b.removeEdge)},b.clear=function(){b.eachVertex(b.destroyVertex)},b.hasPath=function(a,c){function d(a){if(b.hasEdge(a,c))return!0;e[a]=!0;var f=!1;return b.eachVertexFrom(a,function(a){f||e[a]||!d(a)||(f=!0)}),delete e[a],f}if(!b.hasVertex(a)||!b.hasVertex(c))return!1;var e={};return d(a)},b.topologically=function(c){function d(g){e.push(g);var h=e.indexOf(g);if(h!==e.length-1){var i=e.slice(h+1).reverse();throw new a.CycleError(i)}f[g]||(b.eachVertexTo(g,d),f[g]={returned:c(g,b.vertexValue(g))}),e.pop()}var e=[],f={};b.eachVertex(function(a){f[a]||d(a)})}}function b(a,b,c,d){"undefined"==typeof a[b]&&(a[b]={}),a[b][c]=d}function c(){var a=[];this.add=function(b){return-1===a.indexOf(b)&&a.push(b),function(){var c=a.indexOf(b);-1!==c&&a.splice(c,1)}},this.fire=function(){var b=arguments;a.forEach(function(a){a.apply(null,b)})}}function d(a,b){return b.prototype.__proto__=Error.prototype,b.prototype.constructor=b,b.prototype.name=a,b}return a.VertexExistsError=d("VertexExistsError",function(a,b){function c(){d.message="This graph has "+(1===d.vertices?"a vertex":"vertices")+" '"+Object.keys(d.vertices).join("', '")+"'"}var d=this;d.v=function(a,b){return d.vertices[a]=b,c(),d},d.vertices={},d.v(a,b),c()}),a.VertexNotExistsError=d("VertexNotExistError",function(a){function b(){c.message="This graph does not have "+(1===c.vertices?"a vertex":"vertices")+" '"+Object.keys(c.vertices).join("', '")+"'"}var c=this;c.v=function(a){return c.vertices[a]=void 0,b(),c},c.vertices={},c.v(a),b()}),a.EdgeExistsError=d("EdgeExistsError",function(a,c,d){function e(){var a=[];Object.keys(f.edges).forEach(function(b){Object.keys(f.edges[b]).forEach(function(c){a.push("('"+b+"', '"+c+"')")})}),f.message="This graph has "+(1===a.length?"an edge ":"edges ")+a.join(", ")}var f=this;f.e=function(a,c,d){return b(f.edges,a,c,d),e(),f},f.edges={},f.e(a,c,d),e()}),a.EdgeNotExistsError=d("EdgeNotExistError",function(a,c){function d(){var a=[];Object.keys(e.edges).forEach(function(b){Object.keys(e.edges[b]).forEach(function(c){a.push("('"+b+"', '"+c+"')")})}),e.message="This graph does not have "+(1===a.length?"an edge ":"edges ")+a.join(", ")}var e=this;e.e=function(a,c){return b(e.edges,a,c,void 0),d(),e},e.edges={},e.e(a,c),d()}),a.HasConnectedEdgesError=d("HasConnectedEdgesError",function(a){this.message="The '"+a+"' vertex has connected edges",this.key=a}),a.CycleError=d("CycleError",function(a){this.message="This graph contains a cycle: "+a,this.cycle=a}),a});
-//# sourceMappingURL=js-graph.min.js.map
+/* js-graph - v0.2.0 - 2014-10-10 */
+"use strict";!function(a,b,c){"function"==typeof define&&define.amd?define([],c):"object"==typeof exports?module.exports=c():a[b]=c()}(this,"JsGraph",function(){function a(){var b=this,d={},e={},f={},g=0,h=0,i=new c,j=new c;b.onAddVertex=i.add,b.onRemoveVertex=j.add,b.addNewVertex=function(c,h){if(b.hasVertex(c))throw new a.VertexExistsError(c,d[c]);d[c]=h,e[c]={},f[c]={},g+=1,i.fire(c,h)},b.setVertex=function(c,e){if(!b.hasVertex(c))throw new a.VertexNotExistsError(c);d[c]=e},b.ensureVertex=function(a,c){b.hasVertex(a)||b.addNewVertex(a,c)},b.addVertex=function(a,c){b.hasVertex(a)?b.setVertex(a,c):b.addNewVertex(a,c)},b.removeExistingVertex=function(c){if(!b.hasVertex(c))throw new a.VertexNotExistsError(c);if(Object.keys(e[c]).length)throw new a.HasConnectedEdgesError(c);if(Object.keys(f[c]).length)throw new a.HasConnectedEdgesError(c);var h=d[c];delete d[c],g-=1,j.fire(c,h)},b.destroyExistingVertex=function(c){if(!b.hasVertex(c))throw new a.VertexNotExistsError(c);b.eachVertexFrom(c,function(a){b.removeEdge(c,a)}),b.eachVertexTo(c,function(a){b.removeEdge(a,c)}),b.removeExistingVertex(c)},b.removeVertex=function(a){b.hasVertex(a)&&b.removeExistingVertex(a)},b.destroyVertex=function(a){b.hasVertex(a)&&b.destroyExistingVertex(a)};var k=new c,l=new c;b.onAddEdge=k.add,b.onRemoveEdge=l.add,b.addNewEdge=function(c,d,g){if(b.hasEdge(c,d))throw new a.EdgeExistsError(c,d,b.edgeValue(c,d));if(!b.hasVertex(c))throw b.hasVertex(d)?new a.VertexNotExistsError(c):new a.VertexNotExistsError(c).v(d);if(!b.hasVertex(d))throw new a.VertexNotExistsError(d);e[c][d]=g,f[d][c]=null,h+=1,k.fire(c,d,g)},b.createNewEdge=function(c,d,e){if(b.hasEdge(c,d))throw new a.EdgeExistsError(c,d,b.edgeValue(c,d));b.ensureVertex(c),b.ensureVertex(d),b.addNewEdge(c,d,e)},b.setEdge=function(c,d,f){if(!b.hasEdge(c,d))throw new a.EdgeNotExistsError(c,d);e[c][d]=f},b.spanEdge=function(c,d,e){if(!b.hasVertex(c))throw b.hasVertex(d)?new a.VertexNotExistsError(c):new a.VertexNotExistsError(c).v(d);if(!b.hasVertex(d))throw new a.VertexNotExistsError(d);b.hasEdge(c,d)||b.addNewEdge(c,d,e)},b.addEdge=function(a,c,d){b.hasEdge(a,c)?b.setEdge(a,c,d):b.addNewEdge(a,c,d)},b.ensureEdge=function(a,c,d){b.hasEdge(a,c)||b.createNewEdge(a,c,d)},b.createEdge=function(a,c,d){b.hasEdge(a,c)?b.setEdge(a,c,d):b.createNewEdge(a,c,d)},b.removeExistingEdge=function(c,d){if(!b.hasEdge(c,d))throw new a.EdgeNotExistsError(c,d);var g=e[c][d];delete e[c][d],delete f[d][c],h-=1,l.fire(c,d,g)},b.removeEdge=function(a,c){b.hasEdge(a,c)&&b.removeExistingEdge(a,c)},b.vertexCount=function(){return g},b.hasVertex=function(a){return a in d},b.vertexValue=function(a){return d[a]},b.edgeCount=function(){return h},b.hasEdge=function(a,c){return b.hasVertex(a)&&b.hasVertex(c)&&a in e&&c in e[a]},b.edgeValue=function(a,c){return b.hasEdge(a,c)?e[a][c]:void 0},b.successors=function(c){if(!b.hasVertex(c))throw new a.VertexNotExistsError(c);return Object.keys(e[c])},b.predecessors=function(c){if(!b.hasVertex(c))throw new a.VertexNotExistsError(c);return Object.keys(f[c])},b.eachVertex=function(a){Object.keys(d).every(function(b){var c=a(b,d[b]);return c!==!1})},b.eachVertexFrom=function(c,d){if(!b.hasVertex(c))throw new a.VertexNotExistsError(c);Object.keys(e[c]).every(function(a){var e=d(a,b.vertexValue(a),b.edgeValue(c,a));return e!==!1})},b.eachVertexTo=function(c,d){if(!b.hasVertex(c))throw new a.VertexNotExistsError(c);Object.keys(f[c]).every(function(a){var e=d(a,b.vertexValue(a),b.edgeValue(a,c));return e!==!1})},b.eachEdge=function(a){Object.keys(e).every(function(b){return Object.keys(e[b]).every(function(c){var d=a(b,c,e[b][c]);return d!==!1})})},b.clearEdges=function(){b.eachEdge(b.removeEdge)},b.clear=function(){b.eachVertex(b.destroyVertex)},b.hasCycle=function(){function a(f){return c[f]?void(e=!0):void(d[f]||(d[f]=!0,c[f]=!0,b.eachVertexFrom(f,function(b){return a(b),e?!1:void 0}),c[f]=!1))}var c={},d={},e=!1;return b.eachVertex(function(b){return a(b),e?!1:void 0}),e},b.hasPath=function(a,c){function d(a){if(b.hasEdge(a,c))return!0;e[a]=!0;var f=!1;return b.eachVertexFrom(a,function(a){f||e[a]||!d(a)||(f=!0)}),delete e[a],f}if(!b.hasVertex(a)||!b.hasVertex(c))return!1;var e={};return d(a)},b.topologically=function(c){function d(g){e.push(g);var h=e.indexOf(g);if(h!==e.length-1){var i=e.slice(h+1).reverse();throw new a.CycleError(i)}f[g]||(b.eachVertexTo(g,d),f[g]={returned:c(g,b.vertexValue(g))}),e.pop()}var e=[],f={};b.eachVertex(function(a){f[a]||d(a)})}}function b(a,b,c,d){"undefined"==typeof a[b]&&(a[b]={}),a[b][c]=d}function c(){var a=[];this.add=function(b){return-1===a.indexOf(b)&&a.push(b),function(){var c=a.indexOf(b);-1!==c&&a.splice(c,1)}},this.fire=function(){var b=arguments;a.forEach(function(a){a.apply(null,b)})}}function d(a,b){return b.prototype.__proto__=Error.prototype,b.prototype.constructor=b,b.prototype.name=a,b}return a.VertexExistsError=d("VertexExistsError",function(a,b){function c(){d.message="This graph has "+(1===d.vertices?"a vertex":"vertices")+" '"+Object.keys(d.vertices).join("', '")+"'"}var d=this;d.v=function(a,b){return d.vertices[a]=b,c(),d},d.vertices={},d.v(a,b),c()}),a.VertexNotExistsError=d("VertexNotExistError",function(a){function b(){c.message="This graph does not have "+(1===c.vertices?"a vertex":"vertices")+" '"+Object.keys(c.vertices).join("', '")+"'"}var c=this;c.v=function(a){return c.vertices[a]=void 0,b(),c},c.vertices={},c.v(a),b()}),a.EdgeExistsError=d("EdgeExistsError",function(a,c,d){function e(){var a=[];Object.keys(f.edges).forEach(function(b){Object.keys(f.edges[b]).forEach(function(c){a.push("('"+b+"', '"+c+"')")})}),f.message="This graph has "+(1===a.length?"an edge ":"edges ")+a.join(", ")}var f=this;f.e=function(a,c,d){return b(f.edges,a,c,d),e(),f},f.edges={},f.e(a,c,d),e()}),a.EdgeNotExistsError=d("EdgeNotExistError",function(a,c){function d(){var a=[];Object.keys(e.edges).forEach(function(b){Object.keys(e.edges[b]).forEach(function(c){a.push("('"+b+"', '"+c+"')")})}),e.message="This graph does not have "+(1===a.length?"an edge ":"edges ")+a.join(", ")}var e=this;e.e=function(a,c){return b(e.edges,a,c,void 0),d(),e},e.edges={},e.e(a,c),d()}),a.HasConnectedEdgesError=d("HasConnectedEdgesError",function(a){this.message="The '"+a+"' vertex has connected edges",this.key=a}),a.CycleError=d("CycleError",function(a){this.message="This graph contains a cycle: "+a,this.cycle=a}),a});
+//# sourceMappingURL=js-graph.min.map

package.json

 {
-	"name": "js-graph",
-	"version": "0.2.0",
-	"title": "Javascript Graph Datastructure",
-	"homepage": "http://mhelvens.net",
-	"description": "a javascript library for storing arbitrary data in mathematical (di)graphs, as well as traversing and analyzing them in various ways",
-	"main": "dist/js-graph.js",
-	"author": {
-		"name": "Michiel Helvensteijn",
-		"url": "http://mhelvens.net",
-		"email": "[e-mail]"
-	},
-	"repository": {
-		"type": "git",
-		"url": "https://github.com/mhelvens/js-graph.git"
-	},
-	"keywords": [
-		"datastructure",
-		"graph",
-		"directed graph",
-		"traversal",
-		"dependencies"
-	],
-	"bugs": {
-		"url": "https://github.com/mhelvens/js-graph/issues"
-	},
-	"licenses": [
-		{
-			"type": "MIT",
-			"url": "https://github.com/mhelvens/js-graph/blob/master/LICENSE"
-		}
-	],
-	"dependencies": {},
-	"devDependencies": {
-		"bower": "^1.3.8",
-		"grunt": "~0.4.1",
-		"grunt-contrib-copy": "^0.5.0",
-		"grunt-contrib-uglify": "^0.4.1",
-		"grunt-contrib-watch": "~0.6.1",
-		"grunt-coveralls": "^0.3.0",
-		"grunt-karma": "^0.8.3",
-		"karma": "^0.12.9",
-		"karma-coverage": "~0.2.1",
-		"karma-jasmine": "~0.2.2",
-		"karma-phantomjs-launcher": "^0.1.4",
-		"phantomjs": "^1.9.7-3"
-	},
-	"engines": {
-		"node": ">=0.10.17",
-		"npm": ">=1.3.8"
-	}
+  "name": "js-graph",
+  "version": "0.3.0",
+  "title": "Javascript Graph Datastructure",
+  "homepage": "https://github.com/mhelvens/js-graph",
+  "description": "a javascript library for storing arbitrary data in mathematical (di)graphs, as well as traversing and analyzing them in various ways",
+  "main": "dist/js-graph.js",
+  "author": {
+    "name": "Michiel Helvensteijn",
+    "url": "http://mhelvens.net",
+    "email": "[e-mail]"
+  },
+  "repository": {
+    "type": "git",
+    "url": "https://github.com/mhelvens/js-graph.git"
+  },
+  "keywords": [
+    "datastructure",
+    "graph",
+    "directed graph",
+    "traversal",
+    "dependencies"
+  ],
+  "bugs": {
+    "url": "https://github.com/mhelvens/js-graph/issues"
+  },
+  "licenses": [
+    {
+      "type": "MIT",
+      "url": "https://github.com/mhelvens/js-graph/blob/master/LICENSE"
+    }
+  ],
+  "dependencies": {},
+  "devDependencies": {
+    "bower": "^1.3.8",
+    "grunt": "~0.4.1",
+    "grunt-contrib-copy": "^0.5.0",
+    "grunt-contrib-uglify": "^0.4.1",
+    "grunt-contrib-watch": "~0.6.1",
+    "grunt-coveralls": "^0.3.0",
+    "grunt-karma": "^0.8.3",
+    "karma": "^0.12.9",
+    "karma-coverage": "~0.2.1",
+    "karma-jasmine": "^0.2.2",
+    "karma-phantomjs-launcher": "^0.1.4",
+    "phantomjs": "^1.9.7-3"
+  },
+  "engines": {
+    "node": ">=0.10.17",
+    "npm": ">=1.3.8"
+  }
 }

spec/instance-methods-spec.js

@@ -284,2 +284,25 @@ 'use strict';
 
+		it("stops iteration if and when the callback returns false", function () {
+			var counter = 0;
+			callItWith(function (/*key, value*/) {
+				counter += 1;
+				if (counter === 3) { return false }
+			});
+			expect(counter).toEqual(3);
+		});
+
+		it("does not stop iteration when the callback returns a non-false falsey value", function () {
+			var counter;
+
+			[undefined, null, 0, "", NaN].forEach
+			(function (falsey) {
+				counter = 0;
+				callItWith(function (/*key, value*/) {
+					counter += 1;
+					if (counter === 1) { return falsey }
+				});
+				expect(counter).toEqual(5);
+			});
+		});
+
 	});
@@ -318,2 +341,25 @@
 
+		it("stops iteration if and when the callback returns false", function () {
+			var counter = 0;
+			callItWith('k2', function (/*key, value*/) {
+				counter += 1;
+				if (counter === 1) { return false }
+			});
+			expect(counter).toEqual(1);
+		});
+
+		it("does not stop iteration when the callback returns a non-false falsey value", function () {
+			var counter;
+
+			[undefined, null, 0, "", NaN].forEach
+			(function (falsey) {
+				counter = 0;
+				callItWith('k2', function (/*key, value*/) {
+					counter += 1;
+					if (counter === 1) { return falsey }
+				});
+				expect(counter).toEqual(2);
+			});
+		});
+
 	});
@@ -352,2 +398,25 @@
 
+		it("stops iteration if and when the callback returns false", function () {
+			var counter = 0;
+			callItWith('k3', function (/*key, value*/) {
+				counter += 1;
+				if (counter === 1) { return false }
+			});
+			expect(counter).toEqual(1);
+		});
+
+		it("does not stop iteration when the callback returns a non-false falsey value", function () {
+			var counter;
+
+			[undefined, null, 0, "", NaN].forEach
+			(function (falsey) {
+				counter = 0;
+				callItWith('k3', function (/*key, value*/) {
+					counter += 1;
+					if (counter === 1) { return falsey }
+				});
+				expect(counter).toEqual(2);
+			});
+		});
+
 	});
@@ -379,2 +448,25 @@
 
+		it("stops iteration if and when the callback returns false", function () {
+			var counter = 0;
+			callItWith(function (/*key, value*/) {
+				counter += 1;
+				if (counter === 3) { return false }
+			});
+			expect(counter).toEqual(3);
+		});
+
+		it("does not stop iteration when the callback returns a non-false falsey value", function () {
+			var counter;
+
+			[undefined, null, 0, "", NaN].forEach
+			(function (falsey) {
+				counter = 0;
+				callItWith(function (/*key, value*/) {
+					counter += 1;
+					if (counter === 1) { return falsey }
+				});
+				expect(counter).toEqual(4);
+			});
+		});
+
 	});
@@ -1183,3 +1275,42 @@
 
+	describeMethod('hasCycle', function () {
 
+		it("returns true if the graph contains a cycle (1)", function () {
+			graph.clear();
+
+			graph.createEdge('n1', 'n2');
+			graph.createEdge('n2', 'n3');
+			graph.createEdge('n3', 'n4');
+			graph.createEdge('n4', 'n5');
+			graph.createEdge('n3', 'n23');
+			graph.createEdge('n23', 'n2');
+
+			// n1 --> n2 --> n3 --> n4 --> n5
+			//        ^      |
+			//        |      ;
+			//        |     /
+			//       n23 <-"
+
+			expectItWhenCalledWith().toBe(true);
+		});
+
+		it("returns true if the graph contains a cycle (2)", function () {
+			graph.clear();
+
+			graph.createEdge('n1', 'n1');
+
+			expectItWhenCalledWith().toBe(true);
+		});
+
+		it("returns false if the graph contains no cycle (1)", function () {
+			expectItWhenCalledWith().toBe(false);
+		});
+
+		it("returns false if the graph contains no cycle (2)", function () {
+			graph.clear();
+			expectItWhenCalledWith().toBe(false);
+		});
+
+	});
+
 	describeMethod('hasPath', function () {
@@ -1311,11 +1442,11 @@
 				expect(err.cycle).toEqualOneOf(
-					  ['n23', 'n2', 'n3'],
-					  ['n3', 'n23', 'n2'],
-					  ['n2', 'n3', 'n23']
+					['n23', 'n2', 'n3'],
+					['n3', 'n23', 'n2'],
+					['n2', 'n3', 'n23']
 				);
-				var cycleInMessage = err.message.substring(err.message.indexOf(':')+1).trim();
+				var cycleInMessage = err.message.substring(err.message.indexOf(':') + 1).trim();
 				expect(cycleInMessage).toEqualOneOf(
-					  'n23,n2,n3',
-					  'n3,n23,n2',
-					  'n2,n3,n23'
+					'n23,n2,n3',
+					'n3,n23,n2',
+					'n2,n3,n23'
 				);
@@ -1337,3 +1468,3 @@ }
 				expect(err.cycle).toEqual(['n1']);
-				var cycleInMessage = err.message.substring(err.message.indexOf(':')+1).trim();
+				var cycleInMessage = err.message.substring(err.message.indexOf(':') + 1).trim();
 				expect(cycleInMessage).toEqual('n1');
@@ -1388,3 +1519,2 @@ }
 
-
 	});
@@ -1391,0 +1521,0 @@

src/js-graph.js

@@ -324,4 +324,5 @@ 'use strict';
 		that.eachVertex = function (handler) {
-			Object.keys(_vertices).forEach(function (key) {
-				handler(key, _vertices[key]);
+			Object.keys(_vertices).every(function (key) {
+				var r = handler(key, _vertices[key]);
+				return (r !== false);
 			});
@@ -336,4 +337,5 @@ };
 
-			Object.keys(_edges[from]).forEach(function (to) {
-				handler(to, that.vertexValue(to), that.edgeValue(from, to));
+			Object.keys(_edges[from]).every(function (to) {
+				var r = handler(to, that.vertexValue(to), that.edgeValue(from, to));
+				return (r !== false);
 			});
@@ -348,4 +350,5 @@ };
 
-			Object.keys(_reverseEdges[to]).forEach(function (from) {
-				handler(from, that.vertexValue(from), that.edgeValue(from, to));
+			Object.keys(_reverseEdges[to]).every(function (from) {
+				var r = handler(from, that.vertexValue(from), that.edgeValue(from, to));
+				return (r !== false);
 			});
@@ -356,5 +359,6 @@ };
 		that.eachEdge = function (handler) {
-			Object.keys(_edges).forEach(function (from) {
-				Object.keys(_edges[from]).forEach(function (to) {
-					handler(from, to, _edges[from][to]);
+			Object.keys(_edges).every(function (from) {
+				return Object.keys(_edges[from]).every(function (to) {
+					var r = handler(from, to, _edges[from][to]);
+					return (r !== false);
 				});
@@ -374,3 +378,40 @@ });
 
+		that.hasCycle = function () {
+			var visited = {};
+			var handled = {};
 
+			var cycleFound = false;
+
+			function visit(a) {
+				//// if a cycle is found, record it and return
+				//
+				if (visited[a]) {
+					cycleFound = true;
+					return;
+				}
+
+				//// if this vertex was already handled, no cycle can be found here
+				//
+				if (handled[a]) { return }
+				handled[a] = true;
+
+				//// recursively visit successors to check for cycles
+				//
+				visited[a] = true;
+				that.eachVertexFrom(a, function (b) {
+					visit(b);
+					if (cycleFound) { return false }
+				});
+				visited[a] = false;
+			}
+
+			that.eachVertex(function (a) {
+				visit(a);
+				if (cycleFound) { return false }
+			});
+
+			return cycleFound;
+		};
+
+
 		that.hasPath = function (from, to) {
@@ -377,0 +418,0 @@ if (!that.hasVertex(from) || !that.hasVertex(to)) {

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

No website

Quality

Package does not have a website.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

105342

increased by16.35%

Number of package files

17

increased by6.25%

Lines of code

2453

increased by7.82%

Number of low quality alerts

1

decreased by-50%

No dependency changes