p-graph - npm Package Compare versions

Comparing version 1.0.1 to 1.0.2

CHANGELOG.json

@@ -5,3 +5,18 @@ {
     {
-      "date": "Tue, 14 Jul 2020 21:39:43 GMT",
+      "date": "Mon, 05 Oct 2020 17:07:57 GMT",
+      "tag": "p-graph_v1.0.2",
+      "version": "1.0.2",
+      "comments": {
+        "patch": [
+          {
+            "comment": "perf: Improve perf of graphHasCycles function",
+            "author": "[e-mail]",
+            "commit": "d98b31d8bd9734f9d381361e377a3743fac7ebb3",
+            "package": "p-graph"
+          }
+        ]
+      }
+    },
+    {
+      "date": "Tue, 14 Jul 2020 21:39:50 GMT",
       "tag": "p-graph_v1.0.1",
@@ -8,0 +23,0 @@ "version": "1.0.1",

CHANGELOG.md

 # Change Log - p-graph
 
-This log was last generated on Tue, 14 Jul 2020 21:39:43 GMT and should not be manually modified.
+This log was last generated on Mon, 05 Oct 2020 17:07:57 GMT and should not be manually modified.
 
 <!-- Start content -->
 
+## 1.0.2
+
+Mon, 05 Oct 2020 17:07:57 GMT
+
+### Patches
+
+- perf: Improve perf of graphHasCycles function ([e-mail])
+
 ## 1.0.1
 
-Tue, 14 Jul 2020 21:39:43 GMT
+Tue, 14 Jul 2020 21:39:50 GMT
 
@@ -11,0 +19,0 @@ ### Patches

lib/graphHasCycles.d.ts

@@ -5,2 +5,2 @@ import { PGraphNodeWithDependencies } from "./types";
  */
-export declare function graphHasCycles(pGraphDependencyMap: Map<string, PGraphNodeWithDependencies>, nodesWithNoDependencies: string[]): boolean;
+export declare function graphHasCycles(pGraphDependencyMap: Map<string, PGraphNodeWithDependencies>): boolean;

lib/graphHasCycles.js

@@ -6,14 +6,22 @@ "use strict";
  */
-function graphHasCycles(pGraphDependencyMap, nodesWithNoDependencies) {
-    const stack = [];
-    nodesWithNoDependencies.forEach((root) => stack.push({ nodeId: root, visitedNodes: new Set() }));
-    while (stack.length > 0) {
-        const { nodeId, visitedNodes } = stack.pop();
-        // If we have already seen this node, we've found a cycle
-        if (visitedNodes.has(nodeId)) {
-            return true;
+function graphHasCycles(pGraphDependencyMap) {
+    /**
+     *  A map to keep track of the visited and visiting nodes.
+     * <node, true> entry means it is currently being visited.
+     * <node, false> entry means it's sub graph has been visited and is a DAG.
+     * No entry means the node has not been visited yet.
+     */
+    const visitMap = new Map();
+    for (const [nodeId] of pGraphDependencyMap.entries()) {
+        /**
+         * Test whether this node has already been visited or not.
+         */
+        if (!visitMap.has(nodeId)) {
+            /**
+             * Test whether the sub-graph of this node has cycles.
+             */
+            if (hasCycleDFS(pGraphDependencyMap, visitMap, nodeId)) {
+                return true;
+            }
         }
-        visitedNodes.add(nodeId);
-        const node = pGraphDependencyMap.get(nodeId);
-        [...node.dependedOnBy.keys()].forEach((childId) => stack.push({ nodeId: childId, visitedNodes: new Set(visitedNodes) }));
     }
@@ -23,1 +31,49 @@ return false;
 exports.graphHasCycles = graphHasCycles;
+const hasCycleDFS = (graph, visitMap, nodeId) => {
+    const stack = [{ node: nodeId, traversing: false }];
+    while (stack.length > 0) {
+        const current = stack[stack.length - 1];
+        if (!current.traversing) {
+            if (visitMap.has(current.node)) {
+                if (visitMap.get(current.node)) {
+                    /**
+                     * The current node has already been visited,
+                     * hence there is a cycle.
+                     */
+                    return true;
+                }
+                else {
+                    /**
+                     * The current node has already been fully traversed
+                     */
+                    stack.pop();
+                    continue;
+                }
+            }
+            /**
+             * The current node is starting its traversal
+             */
+            visitMap.set(current.node, true);
+            stack[stack.length - 1] = Object.assign(Object.assign({}, current), { traversing: true });
+            /**
+             * Get the current node in the graph
+             */
+            const node = graph.get(current.node);
+            if (!node) {
+                throw new Error(`Could not find node "${current.node}" in the graph`);
+            }
+            /**
+             * Add the current node's dependencies to the stack
+             */
+            stack.push(...[...node.dependsOn].map((n) => ({ node: n, traversing: false })));
+        }
+        else {
+            /**
+             * The current node has now been fully traversed.
+             */
+            visitMap.set(current.node, false);
+            stack.pop();
+        }
+    }
+    return false;
+};

lib/PGraph.js

@@ -28,3 +28,3 @@ "use strict";
         }
-        if (graphHasCycles_1.graphHasCycles(this.pGraphDependencyMap, this.nodesWithNoDependencies)) {
+        if (graphHasCycles_1.graphHasCycles(this.pGraphDependencyMap)) {
             throw new Error("The dependency graph has a cycle in it");
@@ -31,0 +31,0 @@ }

package.json

 {
   "name": "p-graph",
-  "version": "1.0.1",
+  "version": "1.0.2",
   "license": "MIT",
@@ -5,0 +5,0 @@ "main": "lib/index.js",

New alerts

Long strings

Supply chain risk

Contains long string literals, which may be a sign of obfuscated or packed code.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

50898

4.71%

Lines of code

966

7.93%

Worsened metrics

Number of low supply chain risk alerts

2

100%

No dependency changes