libgraph - npm Package Compare versions

Comparing version 1.2.5 to 1.2.6

dijkstra/index.js

 // Generated by CoffeeScript 1.10.0
 (function() {
-  var dijkstra, trieFactory;
+  var PriorityQueue, dijkstra;
 
-  trieFactory = require("trie-array");
+  PriorityQueue = require("js-priority-queue");
 
   dijkstra = function(graph, weightFn) {
-    var edges, toStrFn;
+    var edges;
     edges = graph.edges;
@@ -15,25 +15,12 @@ if (weightFn == null) {
     }
-    toStrFn = (function() {
-      var e, j, len, maxLen, maxPrec, prec, ref;
-      maxLen = 0;
-      maxPrec = 0;
-      for (j = 0, len = edges.length; j < len; j++) {
-        e = edges[j];
-        prec = ((ref = weightFn(e).toString().split(".")[1]) != null ? ref.length : void 0) || 0;
-        if (prec > maxPrec) {
-          maxPrec = prec;
-        }
-        maxLen = maxLen + weightFn(e);
-      }
-      maxLen = maxLen.toString().split(".")[0].length;
-      return function(x) {
-        return trieFactory.numToStr(maxLen, maxPrec, x.distance);
-      };
-    })();
     return {
       weightFn: weightFn,
       from: function(src) {
-        var dagEdges, data, distance, edgesTo, ee, elem, i, j, k, len, len1, queue, ref, ref1, v;
+        var dagEdges, data, distance, edgesTo, ee, elem, i, j, k, len, len1, pq, ref, ref1, v;
         data = {};
-        queue = trieFactory(toStrFn);
+        pq = new PriorityQueue({
+          comparator: function(a, b) {
+            return a.distance - b.distance;
+          }
+        });
         data[src] = {
@@ -46,3 +33,3 @@ last: [],
           i = ref[j];
-          queue.add({
+          pq.queue({
             i: i,
@@ -52,5 +39,4 @@ distance: weightFn(edges[i])
         }
-        while (queue.size() > 0) {
-          elem = queue.getNth(0);
-          queue.del(elem);
+        while (pq.length > 0) {
+          elem = pq.dequeue();
           i = elem.i, distance = elem.distance;
@@ -66,3 +52,3 @@ v = edges[i].dst;
               ee = ref1[k];
-              queue.add({
+              pq.queue({
                 i: ee,
@@ -77,3 +63,3 @@ distance: distance + weightFn(edges[ee])
         edgesTo = function(dst) {
-          var e, e_src, marker, pathEdges;
+          var e, e_src, marker, pathEdges, queue;
           marker = {};
@@ -80,0 +66,0 @@ if (!data[dst]) {

dijkstra/test.js

@@ -7,3 +7,3 @@ // Generated by CoffeeScript 1.10.0
 
-  dijkstra = require("./");
+  dijkstra = require("./index.coffee");
 
@@ -10,0 +10,0 @@ testGraphEdges = require("./graph.json");

Igp/index.js

 // Generated by CoffeeScript 1.10.0
 (function() {
-  var Graph, Igp, Rat, RatFast, bellmanFord, demandsToDems, dfs, ld, toStrFnGen, topo_order, trieFactory;
+  var Graph, Igp, PriorityQueue, bellmanFord, demandsToDems, dfs, ld, topo_order;
 
   ld = require("underscore");
 
-  Rat = require("rat.js");
+  PriorityQueue = require("js-priority-queue");
 
-  trieFactory = require("trie-array");
-
   Graph = require("../");
@@ -19,25 +17,2 @@
 
-  RatFast = (function() {
-    function RatFast(val) {
-      this.val = val != null ? val : 0;
-    }
-
-    RatFast.prototype.add = function(x) {
-      return new RatFast(this.val + x);
-    };
-
-    RatFast.prototype.divide = function(x) {
-      return new RatFast(this.val / x);
-    };
-
-    RatFast.prototype.valueOf = function() {
-      return this.val;
-    };
-
-    return RatFast;
-
-  })();
-
-  Rat = RatFast;
-
   demandsToDems = function(demands) {
@@ -55,25 +30,7 @@ return ld.reduce(demands, function(res, dem) {
 
-  toStrFnGen = function(edges, weightFn) {
-    var e, i, len, maxLen, maxPrec, prec, ref;
-    maxLen = 0;
-    maxPrec = 0;
-    for (i = 0, len = edges.length; i < len; i++) {
-      e = edges[i];
-      prec = ((ref = weightFn(e).toString().split(".")[1]) != null ? ref.length : void 0) || 0;
-      if (prec > maxPrec) {
-        maxPrec = prec;
-      }
-      maxLen = maxLen + weightFn(e);
-    }
-    maxLen = maxLen.toString().split(".")[0].length;
-    return function(x) {
-      return trieFactory.numToStr(maxLen, maxPrec, x.distance);
-    };
-  };
-
   Igp = (function() {
-    function Igp(graph, demands1, weightFn1) {
+    function Igp(graph, demands1, weightFn) {
       this.graph = graph;
       this.demands = demands1;
-      this.weightFn = weightFn1 != null ? weightFn1 : function() {
+      this.weightFn = weightFn != null ? weightFn : function() {
         return 1;
@@ -105,3 +62,2 @@ };
       this.demandsByName = ld.indexBy(this.demands, "name");
-      this.toStrFn = toStrFnGen(this.graph.edges, this.weightFn);
     }
@@ -115,4 +71,4 @@
     Igp.prototype.nodeIsOnShortestPath = function(src, dst, n) {
-      var ref, ref1, ref2;
-      return ((ref = this.bf[src][dst]) != null ? ref.distance : void 0) === ((ref1 = this.bf[src][n]) != null ? ref1.distance : void 0) + ((ref2 = this.bf[n][dst]) != null ? ref2.distance : void 0);
+      var ref, ref1, ref2, ref3, ref4;
+      return ((ref = this.bf[src]) != null ? (ref1 = ref[dst]) != null ? ref1.distance : void 0 : void 0) === ((ref2 = this.bf[src][n]) != null ? ref2.distance : void 0) + ((ref3 = this.bf[n]) != null ? (ref4 = ref3[dst]) != null ? ref4.distance : void 0 : void 0);
     };
@@ -200,3 +156,3 @@
     Igp.prototype.utilization = function(demands, resultObj) {
-      var base, d, d_load, d_name, dems, demsPerEdge, e_dems, e_dst, e_idx, edgesPerDem, i, j, l, len, len1, load, newNode, ref, ref1, spec, src, trie, x;
+      var base, d, d_load, d_name, dems, demsPerEdge, e_dems, e_dst, e_idx, edgesPerDem, i, j, l, len, len1, load, newNode, pq, ref, ref1, spec, src, x;
       if (demands == null) {
@@ -236,10 +192,13 @@ demands = this.dems;
         })(this), {});
-        trie = trieFactory(this.toStrFn);
-        trie.add({
+        pq = new PriorityQueue({
+          comparator: function(a, b) {
+            return a.distance - b.distance;
+          }
+        });
+        pq.queue({
           node: src,
           distance: 0
         });
-        while (trie.size() > 0) {
-          x = trie.getNth(0);
-          trie.del(x);
+        while (pq.length > 0) {
+          x = pq.dequeue();
           demsPerEdge = {};
@@ -277,3 +236,3 @@ edgesPerDem = {};
                 };
-                trie.add(newNode);
+                pq.queue(newNode);
                 load[e_dst] = {};
@@ -280,0 +239,0 @@ }

Igp/test.js

@@ -63,3 +63,3 @@ // Generated by CoffeeScript 1.10.0
       topo: "grid",
-      args: [10, 6]
+      args: [14, 8]
     }
@@ -66,0 +66,0 @@ ];

Ospf/test.js

@@ -64,4 +64,4 @@ // Generated by CoffeeScript 1.10.0
     }, {
-      topo: "grid",
-      args: [10, 6]
+      topo: "lattice",
+      args: [14, 8]
     }
@@ -68,0 +68,0 @@ ];

package.json

 {
   "name": "libgraph",
-  "version": "1.2.5",
+  "version": "1.2.6",
   "description": "graph lib in js/coffee",
@@ -31,5 +31,5 @@ "main": "Graph.js",
   "dependencies": {
+    "js-priority-queue": "^0.1.3",
     "keep-n-first": "^1.0.0",
     "rat.js": "^1.2.0",
-    "trie-array": "^1.1.3",
     "underscore": "^1.8.3"
@@ -36,0 +36,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

139343

increased by7.11%

Number of package files

69

increased by4.55%

Lines of code

2433

increased by11.2%

Dependency changes

• + Addedjs-priority-queue@^0.1.3

• + Addedjs-priority-queue@0.1.5(transitive)

• - Removedtrie-array@^1.1.3

• - Removedtrie-array@1.1.3(transitive)