graph-data-structure - npm Package Compare versions

Comparing version 1.13.0 to 1.14.0

graph-data-structure.js

 (function(f){if(typeof exports==="object"&&typeof module!=="undefined"){module.exports=f()}else if(typeof define==="function"&&define.amd){define([],f)}else{var g;if(typeof window!=="undefined"){g=window}else if(typeof global!=="undefined"){g=global}else if(typeof self!=="undefined"){g=self}else{g=this}g.GraphDataStructure = f()}})(function(){var define,module,exports;return (function(){function r(e,n,t){function o(i,f){if(!n[i]){if(!e[i]){var c="function"==typeof require&&require;if(!f&&c)return c(i,!0);if(u)return u(i,!0);var a=new Error("Cannot find module '"+i+"'");throw a.code="MODULE_NOT_FOUND",a}var p=n[i]={exports:{}};e[i][0].call(p.exports,function(r){var n=e[i][1][r];return o(n||r)},p,p.exports,r,e,n,t)}return n[i].exports}for(var u="function"==typeof require&&require,i=0;i<t.length;i++)o(t[i]);return o}return r})()({1:[function(require,module,exports){
 "use strict";
+var __extends = (this && this.__extends) || (function () {
+    var extendStatics = function (d, b) {
+        extendStatics = Object.setPrototypeOf ||
+            ({ __proto__: [] } instanceof Array && function (d, b) { d.__proto__ = b; }) ||
+            function (d, b) { for (var p in b) if (Object.prototype.hasOwnProperty.call(b, p)) d[p] = b[p]; };
+        return extendStatics(d, b);
+    };
+    return function (d, b) {
+        if (typeof b !== "function" && b !== null)
+            throw new TypeError("Class extends value " + String(b) + " is not a constructor or null");
+        extendStatics(d, b);
+        function __() { this.constructor = d; }
+        d.prototype = b === null ? Object.create(b) : (__.prototype = b.prototype, new __());
+    };
+})();
+var CycleError = /** @class */ (function (_super) {
+    __extends(CycleError, _super);
+    function CycleError(message) {
+        var _this = _super.call(this, message) || this;
+        Object.setPrototypeOf(_this, CycleError.prototype);
+        return _this;
+    }
+    return CycleError;
+}(Error));
 // A graph data structure with depth-first search and topological sort.
@@ -13,2 +37,3 @@ function Graph(serialized) {
         removeEdge: removeEdge,
+        hasEdge: hasEdge,
         setEdgeWeight: setEdgeWeight,
@@ -19,2 +44,3 @@ getEdgeWeight: getEdgeWeight,
         depthFirstSearch: depthFirstSearch,
+        hasCycle: hasCycle,
         lowestCommonAncestors: lowestCommonAncestors,
@@ -115,2 +141,14 @@ topologicalSort: topologicalSort,
     }
+    // Returns true if there is an edge from node u to node v.
+    function hasEdge(u, v) {
+        var has = false;
+        if (edges[u]) {
+            adjacent(u).forEach(function (_v) {
+                if (_v === v) {
+                    has = true;
+                }
+            });
+        }
+        return has;
+    }
     // Computes the indegree for the given node.
@@ -140,4 +178,5 @@ // Not very efficient, costs O(E) where E = number of edges.
     // are used as source nodes.
-    function depthFirstSearch(sourceNodes, includeSourceNodes) {
+    function depthFirstSearch(sourceNodes, includeSourceNodes, errorOnCycle) {
         if (includeSourceNodes === void 0) { includeSourceNodes = true; }
+        if (errorOnCycle === void 0) { errorOnCycle = false; }
         if (!sourceNodes) {
@@ -150,7 +189,13 @@ sourceNodes = nodes();
         var visited = {};
+        var visiting = {};
         var nodeList = [];
         function DFSVisit(node) {
+            if (visiting[node] && errorOnCycle) {
+                throw new CycleError("Cycle found");
+            }
             if (!visited[node]) {
                 visited[node] = true;
+                visiting[node] = true; // temporary flag while visiting
                 adjacent(node).forEach(DFSVisit);
+                visiting[node] = false;
                 nodeList.push(node);
@@ -172,2 +217,18 @@ }
     }
+    // Returns true if the graph has one or more cycles and false otherwise
+    function hasCycle() {
+        try {
+            depthFirstSearch(undefined, true, true);
+            // No error thrown -> no cycles
+            return false;
+        }
+        catch (error) {
+            if (error instanceof CycleError) {
+                return true;
+            }
+            else {
+                throw error;
+            }
+        }
+    }
     // Least Common Ancestors
@@ -220,3 +281,3 @@ // Inspired by https://github.com/relaxedws/lca/blob/master/src/LowestCommonAncestor.php code
         if (includeSourceNodes === void 0) { includeSourceNodes = true; }
-        return depthFirstSearch(sourceNodes, includeSourceNodes).reverse();
+        return depthFirstSearch(sourceNodes, includeSourceNodes, true).reverse();
     }
@@ -223,0 +284,0 @@ // Dijkstra's Shortest Path Algorithm.

index.d.ts

@@ -20,2 +20,3 @@ declare type NodeId = string;
     removeEdge: (u: NodeId, v: NodeId) => any;
+    hasEdge: (u: NodeId, v: NodeId) => boolean;
     setEdgeWeight: (u: NodeId, v: NodeId, weight: EdgeWeight) => any;
@@ -25,3 +26,4 @@ getEdgeWeight: (u: NodeId, v: NodeId) => EdgeWeight;
     outdegree: (node: NodeId) => number;
-    depthFirstSearch: (sourceNodes?: string[] | undefined, includeSourceNodes?: boolean) => string[];
+    depthFirstSearch: (sourceNodes?: string[] | undefined, includeSourceNodes?: boolean, errorOnCycle?: boolean) => string[];
+    hasCycle: () => boolean;
     lowestCommonAncestors: (node1: NodeId, node2: NodeId) => string[];
@@ -28,0 +30,0 @@ topologicalSort: (sourceNodes: NodeId[], includeSourceNodes?: boolean) => string[];

index.js

 "use strict";
+var __extends = (this && this.__extends) || (function () {
+    var extendStatics = function (d, b) {
+        extendStatics = Object.setPrototypeOf ||
+            ({ __proto__: [] } instanceof Array && function (d, b) { d.__proto__ = b; }) ||
+            function (d, b) { for (var p in b) if (Object.prototype.hasOwnProperty.call(b, p)) d[p] = b[p]; };
+        return extendStatics(d, b);
+    };
+    return function (d, b) {
+        if (typeof b !== "function" && b !== null)
+            throw new TypeError("Class extends value " + String(b) + " is not a constructor or null");
+        extendStatics(d, b);
+        function __() { this.constructor = d; }
+        d.prototype = b === null ? Object.create(b) : (__.prototype = b.prototype, new __());
+    };
+})();
+var CycleError = /** @class */ (function (_super) {
+    __extends(CycleError, _super);
+    function CycleError(message) {
+        var _this = _super.call(this, message) || this;
+        Object.setPrototypeOf(_this, CycleError.prototype);
+        return _this;
+    }
+    return CycleError;
+}(Error));
 // A graph data structure with depth-first search and topological sort.
@@ -12,2 +36,3 @@ function Graph(serialized) {
         removeEdge: removeEdge,
+        hasEdge: hasEdge,
         setEdgeWeight: setEdgeWeight,
@@ -18,2 +43,3 @@ getEdgeWeight: getEdgeWeight,
         depthFirstSearch: depthFirstSearch,
+        hasCycle: hasCycle,
         lowestCommonAncestors: lowestCommonAncestors,
@@ -114,2 +140,14 @@ topologicalSort: topologicalSort,
     }
+    // Returns true if there is an edge from node u to node v.
+    function hasEdge(u, v) {
+        var has = false;
+        if (edges[u]) {
+            adjacent(u).forEach(function (_v) {
+                if (_v === v) {
+                    has = true;
+                }
+            });
+        }
+        return has;
+    }
     // Computes the indegree for the given node.
@@ -139,4 +177,5 @@ // Not very efficient, costs O(E) where E = number of edges.
     // are used as source nodes.
-    function depthFirstSearch(sourceNodes, includeSourceNodes) {
+    function depthFirstSearch(sourceNodes, includeSourceNodes, errorOnCycle) {
         if (includeSourceNodes === void 0) { includeSourceNodes = true; }
+        if (errorOnCycle === void 0) { errorOnCycle = false; }
         if (!sourceNodes) {
@@ -149,7 +188,13 @@ sourceNodes = nodes();
         var visited = {};
+        var visiting = {};
         var nodeList = [];
         function DFSVisit(node) {
+            if (visiting[node] && errorOnCycle) {
+                throw new CycleError("Cycle found");
+            }
             if (!visited[node]) {
                 visited[node] = true;
+                visiting[node] = true; // temporary flag while visiting
                 adjacent(node).forEach(DFSVisit);
+                visiting[node] = false;
                 nodeList.push(node);
@@ -171,2 +216,18 @@ }
     }
+    // Returns true if the graph has one or more cycles and false otherwise
+    function hasCycle() {
+        try {
+            depthFirstSearch(undefined, true, true);
+            // No error thrown -> no cycles
+            return false;
+        }
+        catch (error) {
+            if (error instanceof CycleError) {
+                return true;
+            }
+            else {
+                throw error;
+            }
+        }
+    }
     // Least Common Ancestors
@@ -219,3 +280,3 @@ // Inspired by https://github.com/relaxedws/lca/blob/master/src/LowestCommonAncestor.php code
         if (includeSourceNodes === void 0) { includeSourceNodes = true; }
-        return depthFirstSearch(sourceNodes, includeSourceNodes).reverse();
+        return depthFirstSearch(sourceNodes, includeSourceNodes, true).reverse();
     }
@@ -222,0 +283,0 @@ // Dijkstra's Shortest Path Algorithm.

package.json

 {
     "name": "graph-data-structure",
-    "version": "1.13.0",
+    "version": "1.14.0",
     "description": "A graph data structure with topological sort.",
@@ -33,8 +33,8 @@ "main": "index.js",
     "devDependencies": {
-        "@types/node": "^14.11.2",
-        "browserify": "^16.5.2",
+        "@types/node": "^15.3.1",
+        "browserify": "^17.0.0",
         "graph-diagrams": "^0.5.0",
-        "mocha": "^8.1.3",
-        "typescript": "^4.0.3"
+        "mocha": "^8.4.0",
+        "typescript": "^4.2.4"
     }
 }

README.md

@@ -129,2 +129,6 @@ # graph-data-structure
 
+<a name="has-edge" href="#has-edge">#</a> <i>graph</i>.<b>hasEdge</b>(<i>u</i>, <i>v</i>)
+
+Returns `true` if there exists an edge from node *u* to node *v*. Returns `false` otherwise.
+
 ### Working with Edge Weights
@@ -205,3 +209,3 @@
 
-<a name="dfs" href="#dfs">#</a> <i>graph</i>.<b>depthFirstSearch</b>([<i>sourceNodes</i>][, <i>includeSourceNodes</i>])
+<a name="dfs" href="#dfs">#</a> <i>graph</i>.<b>depthFirstSearch</b>([<i>sourceNodes</i>][, <i>includeSourceNodes</i>][, <i>errorOnCycle</i>])
 
@@ -214,3 +218,9 @@ Performs [Depth-first Search](https://en.wikipedia.org/wiki/Depth-first_search). Returns an array of node identifier strings. The returned array includes nodes visited by the algorithm in the order in which they were visited. Implementation inspired by pseudocode from Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 604.
  * *includeSourceNodes* (optional) - A boolean specifying whether or not to include the source nodes in the returned array. If *includeSourceNodes* is not specified, it is treated as `true` (all source nodes are included in the returned array).
+ * *errorOnCycle* (optional) - A boolean indicating that a `CycleError` should be thrown whenever a cycle is first encountered. Defaults to `false`.
 
+
+<a name="has-cycle" href="#has-cycle">#</a> <i>graph</i>.<b>hasCycle</b>()
+
+Checks if the graph has any cycles. Returns `true` if it does and `false` otherwise.
+
 <a name="lca" href="#lca">#</a> <i>graph</i>.<b>lowestCommonAncestors</b>([<i>node1</i>][, <i>node2</i>])
@@ -231,2 +241,4 @@
 
+Note: this function raises a `CycleError` when the input is not a DAG.
+
 <a name="shortest-path" href="#shortest-path">#</a> <i>graph</i>.<b>shortestPath</b>(<i>sourceNode</i>, <i>destinationNode</i>)
@@ -241,2 +253,1 @@
 </p>
-

No alert changes

Improved metrics

Total package byte prevSize

44758

12.95%

Lines of code

851

17.06%

Number of lines in readme file

249

4.62%

No dependency changes