graphology-dag - npm Package Compare versions

Comparing version 0.0.1 to 0.1.0

has-cycle.d.ts

+import Graph from 'graphology-types';
+
+export default function hasCycle(graph: Graph): boolean;

has-cycle.js

+/**
+ * Graphology Cycle Creation Checker
+ * ==================================
+ *
+ * Function returning whether the given graph contains at least one cycle.
+ *
+ * This function also works on disconnected graphs.
+ *
+ * [Reference]:
+ * https://newbedev.com/how-to-detect-cycles-in-a-directed-graph-using-the-iterative-version-of-dfs
+ */
+const isGraph = require('graphology-utils/is-graph');
+
+const WHITE = undefined;
+const GREY = 0;
+const BLACK = 1;
+
+module.exports = function hasCycle(graph) {
+  if (!isGraph(graph))
+    throw new Error(
+      'graphology-dag/has-cycle: the given graph is not a valid graphology instance.'
+    );
+
+  // Early exit
+  if (graph.size === 0) return false;
+
+  // If the graph has a self loop, it contains a cycle by definition
+  if (graph.selfLoopCount !== 0) return true;
+
+  const labels = {};
+  const stack = [];
+
+  function neighborCallback(neighbor) {
+    const neighborLabel = labels[neighbor];
+
+    if (neighborLabel === WHITE) stack.push(neighbor);
+    else if (neighborLabel === GREY) return true;
+
+    return false;
+  }
+
+  // We iterate over all nodes to be able to handle disconnected graphs
+  // NOTE: possibility to early exit when we know that all nodes have already
+  // been traversed
+  return graph.someNode(node => {
+    // Node was already seen
+    if (labels[node] === BLACK) return false;
+
+    stack.push(node);
+
+    while (stack.length !== 0) {
+      const current = stack[stack.length - 1]; // peek
+      const currentLabel = labels[current];
+
+      if (currentLabel !== GREY) {
+        labels[current] = GREY;
+
+        const shouldStop = graph.someOutboundNeighbor(
+          current,
+          neighborCallback
+        );
+
+        if (shouldStop) return true;
+      } else if (currentLabel === GREY) {
+        stack.pop();
+        labels[current] = BLACK;
+      }
+    }
+
+    return false;
+  });
+};

index.d.ts

@@ -0,1 +1,2 @@
+export {default as hasCycle} from './has-cycle';
 export {default as willCreateCycle} from './will-create-cycle';

index.js

@@ -0,1 +1,2 @@
+exports.hasCycle = require('./has-cycle.js');
 exports.willCreateCycle = require('./will-create-cycle.js');

package.json

 {
   "name": "graphology-dag",
-  "version": "0.0.1",
+  "version": "0.1.0",
   "description": "Directed acyclic graph functions for graphology.",
   "main": "index.js",
   "files": [
+    "has-cycle.js",
     "index.js",
@@ -8,0 +9,0 @@ "will-create-cycle.js",

README.md

@@ -13,4 +13,30 @@ # Graphology DAG
 
+- [hasCycle](#hascycle)
 - [willCreateCycle](#willcreatecycle)
 
+### hasCycle
+
+Function returning whether the given directed graph contains at least one cycle.
+
+Note that this function will also work with a disconnected graph.
+
+```js
+import {hasCycle} from 'graphology-dag';
+// Alternatively, to load only the relevant code:
+import hasCycle from 'graphology-dag/has-cycle';
+
+const graph = new DirectedGraph();
+graph.mergeEdge(0, 1);
+graph.mergeEdge(1, 2);
+graph.mergeEdge(2, 3);
+
+hasCycle(graph);
+>>> false
+
+graph.mergeEdge(3, 0);
+
+hasCycle(graph);
+>>> true
+```
+
 ### willCreateCycle
@@ -22,2 +48,4 @@
 
+Note finally that this function will also work with DAG forests (sets of disconnected DAGs living in the same graph instance).
+
 ```js
@@ -24,0 +52,0 @@ import {willCreateCycle} from 'graphology-dag';

No alert changes

Improved metrics

Total package byte prevSize

7695

54.39%

Number of package files

9

28.57%

Lines of code

113

117.31%

Number of lines in readme file

64

77.78%

No dependency changes