graphology-shortest-path - npm Package Compare versions

Comparing version 1.0.4 to 1.1.0-alpha1

dijkstra.js

@@ -60,15 +60,2 @@ /**
 
-var GET_NEIGHBORS = [
-  function(graph, node) {
-    return graph
-      .undirectedEdges(node)
-      .concat(graph.outEdges(node));
-  },
-  function(graph, node) {
-    return graph
-      .undirectedEdges(node)
-      .concat(graph.inEdges(node));
-  }
-];
-
 /**
@@ -155,3 +142,5 @@ * Bidirectional Dijkstra shortest path between source & target node abstract.
 
-    edges = GET_NEIGHBORS[dir](graph, v);
+    edges = dir === 1 ?
+      graph.inboundEdges(v) :
+      graph.outboundEdges(v);
 
@@ -264,5 +253,3 @@ for (i = 0, l = edges.length; i < l; i++) {
 
-    edges = graph
-      .undirectedEdges(v)
-      .concat(graph.outEdges(v));
+    edges = graph.outboundEdges(v);
 
@@ -386,5 +373,3 @@ for (j = 0, m = edges.length; j < m; j++) {
 
-    edges = graph
-      .undirectedEdges(v)
-      .concat(graph.outEdges(v));
+    edges = graph.outboundEdges(v);
 
@@ -391,0 +376,0 @@ for (i = 0, l = edges.length; i < l; i++) {

package.json

 {
   "name": "graphology-shortest-path",
-  "version": "1.0.4",
+  "version": "1.1.0-alpha1",
   "description": "Shortest path functions for graphology.",
   "main": "index.js",
   "files": [
+    "*.d.ts",
     "dijkstra.js",
@@ -38,5 +39,5 @@ "index.js",
     "@yomguithereal/eslint-config": "^4.0.0",
-    "eslint": "^5.9.0",
-    "graphology": "0.14.0",
-    "mocha": "^5.2.0"
+    "eslint": "^6.8.0",
+    "graphology": "0.16.0",
+    "mocha": "^7.1.0"
   },
@@ -47,5 +48,6 @@ "eslintConfig": {
   "dependencies": {
-    "graphology-utils": "^1.3.1",
-    "mnemonist": "^0.25.1"
+    "graphology-types": "^0.16.0",
+    "graphology-utils": "^1.7.0",
+    "mnemonist": "^0.32.0"
   }
 }

unweighted.js

@@ -9,3 +9,6 @@ /**
 var isGraph = require('graphology-utils/is-graph'),
-    Queue = require('mnemonist/queue');
+    Queue = require('mnemonist/queue'),
+    PointerVector = require('mnemonist/vector').PointerVector,
+    typed = require('mnemonist/utils/typed-arrays'),
+    FixedStack = require('mnemonist/fixed-stack');
 
@@ -43,29 +46,5 @@ /**
   // Binding functions
-  var getPredecessors,
-      getSuccessors;
+  var getPredecessors = graph.inboundNeighbors.bind(graph),
+      getSuccessors = graph.outboundNeighbors.bind(graph);
 
-  // TODO: move outside this function
-  if (graph.type === 'mixed') {
-    getPredecessors = function(node) {
-      var result = graph.inNeighbors(node);
-
-      result.push.apply(result, graph.undirectedNeighbors(node));
-      return result;
-    };
-
-    getSuccessors = function(node) {
-      var result = graph.outNeighbors(node);
-
-      result.push.apply(result, graph.undirectedNeighbors(node));
-      return result;
-    };
-  }
-  else if (graph.type === 'directed') {
-    getPredecessors = graph.inNeighbors.bind(graph);
-    getSuccessors = graph.outNeighbors.bind(graph);
-  }
-  else {
-    getPredecessors = getSuccessors = graph.undirectedNeighbors.bind(graph);
-  }
-
   var predecessor = {},
@@ -205,4 +184,3 @@ successor = {};
     for (v in currentLevel) {
-      neighbors = graph.outNeighbors(v);
-      neighbors.push.apply(neighbors, graph.undirectedNeighbors(v));
+      neighbors = graph.outboundNeighbors(v);
 
@@ -289,5 +267,3 @@ for (i = 0, l = neighbors.length; i < l; i++) {
 
-    neighbors = graph
-      .undirectedNeighbors(v)
-      .concat(graph.outNeighbors(v));
+    neighbors = graph.outboundNeighbors(v);
 
@@ -312,2 +288,122 @@ for (j = 0, m = neighbors.length; j < m; j++) {
 
+function OutboundNeighborhoodIndex(graph) {
+  var PointerArray = typed.getPointerArray(graph.order);
+
+  this.neighborhood = new PointerVector(graph.directedSize + graph.undirectedSize * 2);
+  this.starts = new PointerArray(graph.order);
+  this.lengths = new PointerArray(graph.order);
+  this.nodes = graph.nodes();
+
+  // TODO: it may be possible to drop this index
+  this.ids = {};
+
+  var i, l, j, m, node, neighbors, neighbor;
+
+  for (i = 0, l = graph.order; i < l; i++)
+    this.ids[this.nodes[i]] = i;
+
+  for (i = 0, l = graph.order; i < l; i++) {
+    node = this.nodes[i];
+    neighbors = graph.outboundNeighbors(node);
+
+    this.starts[i] = this.neighborhood.length;
+    this.lengths[i] = neighbors.length;
+
+    for (j = 0, m = neighbors.length; j < m; j++) {
+      neighbor = neighbors[j];
+      this.neighborhood.push(this.ids[neighbor]);
+    }
+  }
+}
+
+OutboundNeighborhoodIndex.prototype.bounds = function(node) {
+  var idx = this.ids[node];
+
+  return [this.starts[idx], this.lengths[idx]];
+};
+
+// var Graph = require('graphology');
+// var graph = new Graph();
+// graph.mergeEdge(1, 2);
+// graph.mergeEdge(2, 3);
+// graph.mergeEdge(2, 1);
+// graph.mergeEdge(4, 5);
+
+// var index = new OutboundNeighborhoodIndex(graph);
+// console.log(index);
+
+// graph.forEachNode(node => {
+//   var bounds = index.bounds(node);
+
+//   console.log(node, bounds);
+//   var A = index.neighborhood.array;
+//   var neighbors = A.slice(bounds[0], bounds[0] + bounds[1]);
+//   console.log(neighbors);
+// });
+
+function createIndexedBrandes(graph) {
+  var neighborhoodIndex = new OutboundNeighborhoodIndex(graph);
+  var N = neighborhoodIndex.neighborhood.array;
+
+  var S = new FixedStack(Array, graph.order),
+      sigma = {},
+      P = {};
+
+  // TODO: more aggressive indexation relying on indices without objects
+
+  return function(source) {
+    source = '' + source;
+
+    var Dv,
+        sigmav,
+        bounds,
+        start,
+        length,
+        v,
+        w,
+        j,
+        m;
+
+    for (v in neighborhoodIndex.ids) {
+      P[v] = [];
+      sigma[v] = 0;
+    }
+
+    var D = {};
+
+    sigma[source] = 1;
+    D[source] = 0;
+
+    var queue = Queue.of(source);
+
+    while (queue.size) {
+      v = queue.dequeue();
+      S.push(v);
+
+      Dv = D[v];
+      sigmav = sigma[v];
+
+      bounds = neighborhoodIndex.bounds(v);
+      start = bounds[0];
+      length = bounds[1];
+
+      for (j = start, m = start + length; j < m; j++) {
+        w = neighborhoodIndex.nodes[N[j]];
+
+        if (!(w in D)) {
+          queue.enqueue(w);
+          D[w] = Dv + 1;
+        }
+
+        if (D[w] === Dv + 1) {
+          sigma[w] += sigmav;
+          P[w].push(v);
+        }
+      }
+    }
+
+    return [S, P, sigma];
+  };
+}
+
 /**
@@ -319,3 +415,4 @@ * Exporting.
 shortestPath.brandes = brandes;
+shortestPath.createIndexedBrandes = createIndexedBrandes;
 
 module.exports = shortestPath;

New alerts

No v1

Quality

Package is not semver >=1. This means it is not stable and does not support ^ ranges.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

27587

increased by11.24%

Number of package files

8

increased by33.33%

Lines of code

678

increased by12.62%

Worsened metrics

Dependency count

3

increased by50%

Number of low quality alerts

2

increased by100%

Dependency changes

• + Addedgraphology-types@^0.16.0

• + Addedgraphology-types@0.16.0(transitive)

• + Addedmnemonist@0.32.0(transitive)

• - Removedmnemonist@0.25.1(transitive)

• Updatedgraphology-utils@^1.7.0

• Updatedmnemonist@^0.32.0