graph-data-structure - npm Package Compare versions

Comparing version 1.8.0 to 1.9.0

graph-data-structure.js

@@ -1,2 +0,2 @@
-(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 e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);var f=new Error("Cannot find module '"+o+"'");throw f.code="MODULE_NOT_FOUND",f}var l=n[o]={exports:{}};t[o][0].call(l.exports,function(e){var n=t[o][1][e];return s(n?n:e)},l,l.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s}return e})()({1:[function(require,module,exports){
+(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){
 // A graph data structure with depth-first search and topological sort.
@@ -18,2 +18,3 @@ module.exports = function Graph(serialized){
     depthFirstSearch: depthFirstSearch,
+    lowestCommonAncestors: lowestCommonAncestors,
     topologicalSort: topologicalSort,
@@ -51,3 +52,3 @@ shortestPath: shortestPath,
   function removeNode(node){
-    
+
     // Remove incoming edges.
@@ -153,3 +154,3 @@ Object.keys(edges).forEach(function (u){
   // Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 604
-  // This variant includes an additional option 
+  // This variant includes an additional option
   // `includeSourceNodes` to specify whether to include or
@@ -194,2 +195,46 @@ // exclude the source nodes from the result (true by default).
 
+  // Least Common Ancestors
+  // Inspired by https://github.com/relaxedws/lca/blob/master/src/LowestCommonAncestor.php code
+  // but uses depth search instead of breadth. Also uses some optimizations
+  function lowestCommonAncestors(node1, node2){
+
+    var node1Ancestors = [];
+    var lcas = [];
+
+    function CA1Visit(visited, node){
+      if(!visited[node]){
+        visited[node] = true;
+        node1Ancestors.push(node);
+        if (node == node2) {
+          lcas.push(node);
+          return false; // found - shortcut
+        }
+        return adjacent(node).every(node => {
+          return CA1Visit(visited, node);
+        });
+      } else {
+        return true;
+      }
+    }
+
+    function CA2Visit(visited, node){
+      if(!visited[node]){
+        visited[node] = true;
+        if (node1Ancestors.indexOf(node) >= 0) {
+          lcas.push(node);
+        } else if (lcas.length == 0) {
+          adjacent(node).forEach(node => {
+            CA2Visit(visited, node);
+          });
+        }
+      }
+    }
+
+    if (CA1Visit({}, node1)) { // No shortcut worked
+      CA2Visit({}, node2);
+    }
+
+    return lcas;
+  }
+
   // The topological sort algorithm yields a list of visited nodes
@@ -334,3 +379,3 @@ // such that for each visited edge (u, v), u comes before v in the list.
   }
-  
+
   return graph;
@@ -340,2 +385,2 @@ }
 },{}]},{},[1])(1)
-});
+});

index.js

@@ -17,2 +17,3 @@ // A graph data structure with depth-first search and topological sort.
     depthFirstSearch: depthFirstSearch,
+    lowestCommonAncestors: lowestCommonAncestors,
     topologicalSort: topologicalSort,
@@ -50,3 +51,3 @@ shortestPath: shortestPath,
   function removeNode(node){
-    
+
     // Remove incoming edges.
@@ -152,3 +153,3 @@ Object.keys(edges).forEach(function (u){
   // Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 604
-  // This variant includes an additional option 
+  // This variant includes an additional option
   // `includeSourceNodes` to specify whether to include or
@@ -193,2 +194,46 @@ // exclude the source nodes from the result (true by default).
 
+  // Least Common Ancestors
+  // Inspired by https://github.com/relaxedws/lca/blob/master/src/LowestCommonAncestor.php code
+  // but uses depth search instead of breadth. Also uses some optimizations
+  function lowestCommonAncestors(node1, node2){
+
+    var node1Ancestors = [];
+    var lcas = [];
+
+    function CA1Visit(visited, node){
+      if(!visited[node]){
+        visited[node] = true;
+        node1Ancestors.push(node);
+        if (node == node2) {
+          lcas.push(node);
+          return false; // found - shortcut
+        }
+        return adjacent(node).every(node => {
+          return CA1Visit(visited, node);
+        });
+      } else {
+        return true;
+      }
+    }
+
+    function CA2Visit(visited, node){
+      if(!visited[node]){
+        visited[node] = true;
+        if (node1Ancestors.indexOf(node) >= 0) {
+          lcas.push(node);
+        } else if (lcas.length == 0) {
+          adjacent(node).forEach(node => {
+            CA2Visit(visited, node);
+          });
+        }
+      }
+    }
+
+    if (CA1Visit({}, node1)) { // No shortcut worked
+      CA2Visit({}, node2);
+    }
+
+    return lcas;
+  }
+
   // The topological sort algorithm yields a list of visited nodes
@@ -333,4 +378,4 @@ // such that for each visited edge (u, v), u comes before v in the list.
   }
-  
+
   return graph;
 }

package.json

 {
   "name": "graph-data-structure",
-  "version": "1.8.0",
+  "version": "1.9.0",
   "description": "A graph data structure with topological sort.",
@@ -30,5 +30,6 @@ "main": "index.js",
   "devDependencies": {
+    "browserify": "^16.5.0",
     "graph-diagrams": "^0.5.0",
-    "mocha": "^3.5.0"
+    "mocha": "^6.2.0"
   }
 }

README.md

@@ -213,2 +213,11 @@ # graph-data-structure
 
+<a name="lca" href="#lca">#</a> <i>graph</i>.<b>lowestCommonAncestors</b>([<i>node1</i>][, <i>node2</i>])
+
+Performs search of [Lowest common ancestors](https://en.wikipedia.org/wiki/Lowest_common_ancestor). Returns an array of node identifier strings.
+
+Arguments:
+
+ * *node1* (required) - First node.
+ * *node2* (required) - Second node.
+
 <a name="topological-sort" href="#topological-sort">#</a> <i>graph</i>.<b>topologicalSort</b>([<i>sourceNodes</i>][, <i>includeSourceNodes</i>])
@@ -215,0 +224,0 @@

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

33878

increased by8.66%

Lines of code

654

increased by13.74%

Number of lines in readme file

238

increased by3.93%

Worsened metrics

Dev dependency count

3

increased by50%

No dependency changes