graph-data-structure - npm Package Compare versions

Comparing version 1.15.0 to 2.0.0

graph-data-structure.js

 (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){
 "use strict";
-var __extends = (this && this.__extends) || (function () {
-    var extendStatics = function (d, b) {
-        extendStatics = Object.setPrototypeOf ||
-            ({ __proto__: [] } instanceof Array && function (d, b) { d.__proto__ = b; }) ||
-            function (d, b) { for (var p in b) if (Object.prototype.hasOwnProperty.call(b, p)) d[p] = b[p]; };
-        return extendStatics(d, b);
-    };
-    return function (d, b) {
-        if (typeof b !== "function" && b !== null)
-            throw new TypeError("Class extends value " + String(b) + " is not a constructor or null");
-        extendStatics(d, b);
-        function __() { this.constructor = d; }
-        d.prototype = b === null ? Object.create(b) : (__.prototype = b.prototype, new __());
-    };
-})();
-var CycleError = /** @class */ (function (_super) {
-    __extends(CycleError, _super);
-    function CycleError(message) {
-        var _this = _super.call(this, message) || this;
-        Object.setPrototypeOf(_this, CycleError.prototype);
-        return _this;
+class CycleError extends Error {
+    constructor(message) {
+        super(message);
+        Object.setPrototypeOf(this, CycleError.prototype);
     }
-    return CycleError;
-}(Error));
+}
 // A graph data structure with depth-first search and topological sort.
 function Graph(serialized) {
     // Returned graph instance
-    var graph = {
-        addNode: addNode,
-        removeNode: removeNode,
-        nodes: nodes,
-        adjacent: adjacent,
-        addEdge: addEdge,
-        removeEdge: removeEdge,
-        hasEdge: hasEdge,
-        setEdgeWeight: setEdgeWeight,
-        getEdgeWeight: getEdgeWeight,
-        indegree: indegree,
-        outdegree: outdegree,
-        depthFirstSearch: depthFirstSearch,
-        hasCycle: hasCycle,
-        lowestCommonAncestors: lowestCommonAncestors,
-        topologicalSort: topologicalSort,
-        shortestPath: shortestPath,
-        serialize: serialize,
-        deserialize: deserialize
+    const graph = {
+        addNode,
+        removeNode,
+        nodes,
+        adjacent,
+        addEdge,
+        removeEdge,
+        hasEdge,
+        setEdgeWeight,
+        getEdgeWeight,
+        indegree,
+        outdegree,
+        depthFirstSearch,
+        hasCycle,
+        lowestCommonAncestors,
+        topologicalSort,
+        shortestPath,
+        serialize,
+        deserialize
     };
@@ -53,7 +35,7 @@ // The adjacency list of the graph.
     // Values are adjacent node id arrays.
-    var edges = {};
+    const edges = {};
     // The weights of edges.
     // Keys are string encodings of edges.
     // Values are weights (numbers).
-    var edgeWeights = {};
+    const edgeWeights = {};
     // If a serialized graph was passed into the constructor, deserialize it.
@@ -88,3 +70,3 @@ if (serialized) {
         // TODO: Better implementation with set data structure
-        var nodeSet = {};
+        const nodeSet = {};
         Object.keys(edges).forEach(function (u) {
@@ -116,3 +98,3 @@ nodeSet[u] = true;
     function getEdgeWeight(u, v) {
-        var weight = edgeWeights[encodeEdge(u, v)];
+        const weight = edgeWeights[encodeEdge(u, v)];
         return weight === undefined ? 1 : weight;
@@ -149,3 +131,3 @@ }
     function indegree(node) {
-        var degree = 0;
+        let degree = 0;
         function check(v) {
@@ -171,5 +153,3 @@ if (v === node) {
     // are used as source nodes.
-    function depthFirstSearch(sourceNodes, includeSourceNodes, errorOnCycle) {
-        if (includeSourceNodes === void 0) { includeSourceNodes = true; }
-        if (errorOnCycle === void 0) { errorOnCycle = false; }
+    function depthFirstSearch(sourceNodes, includeSourceNodes = true, errorOnCycle = false) {
         if (!sourceNodes) {
@@ -181,5 +161,5 @@ sourceNodes = nodes();
         }
-        var visited = {};
-        var visiting = {};
-        var nodeList = [];
+        const visited = {};
+        const visiting = {};
+        const nodeList = [];
         function DFSVisit(node) {
@@ -230,4 +210,4 @@ if (visiting[node] && errorOnCycle) {
     function lowestCommonAncestors(node1, node2) {
-        var node1Ancestors = [];
-        var lcas = [];
+        const node1Ancestors = [];
+        const lcas = [];
         function CA1Visit(visited, node) {
@@ -241,3 +221,3 @@ if (!visited[node]) {
                 }
-                return adjacent(node).every(function (node) {
+                return adjacent(node).every(node => {
                     return CA1Visit(visited, node);
@@ -257,3 +237,3 @@ });
                 else if (lcas.length == 0) {
-                    adjacent(node).forEach(function (node) {
+                    adjacent(node).forEach(node => {
                         CA2Visit(visited, node);
@@ -274,4 +254,3 @@ });
     // Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 613
-    function topologicalSort(sourceNodes, includeSourceNodes) {
-        if (includeSourceNodes === void 0) { includeSourceNodes = true; }
+    function topologicalSort(sourceNodes, includeSourceNodes = true) {
         return depthFirstSearch(sourceNodes, includeSourceNodes, true).reverse();
@@ -284,7 +263,7 @@ }
         // Upper bounds for shortest path weights from source.
-        var d = {};
+        const d = {};
         // Predecessors.
-        var p = {};
+        const p = {};
         // Poor man's priority queue, keyed on d.
-        var q = {};
+        let q = {};
         function initializeSingleSource() {
@@ -314,4 +293,4 @@ nodes().forEach(function (node) {
         function extractMin() {
-            var min = Infinity;
-            var minNode;
+            let min = Infinity;
+            let minNode;
             Object.keys(q).forEach(function (node) {
@@ -332,3 +311,3 @@ if (d[node] < min) {
         function relax(u, v) {
-            var w = getEdgeWeight(u, v);
+            const w = getEdgeWeight(u, v);
             if (d[v] > d[u] + w) {
@@ -342,14 +321,9 @@ d[v] = d[u] + w;
             initializePriorityQueue();
-            var _loop_1 = function () {
-                var u = extractMin();
+            while (!priorityQueueEmpty()) {
+                const u = extractMin();
                 if (u === null)
-                    return { value: void 0 };
+                    return;
                 adjacent(u).forEach(function (v) {
                     relax(u, v);
                 });
-            };
-            while (!priorityQueueEmpty()) {
-                var state_1 = _loop_1();
-                if (typeof state_1 === "object")
-                    return state_1.value;
             }
@@ -360,5 +334,5 @@ }
         function path() {
-            var nodeList = [];
-            var weight = 0;
-            var node = destination;
+            const nodeList = [];
+            let weight = 0;
+            let node = destination;
             while (p[node]) {
@@ -382,3 +356,3 @@ nodeList.push(node);
     function serialize() {
-        var serialized = {
+        const serialized = {
             nodes: nodes().map(function (id) {
@@ -390,3 +364,3 @@ return { id: id };
         serialized.nodes.forEach(function (node) {
-            var source = node.id;
+            const source = node.id;
             adjacent(source).forEach(function (target) {
@@ -393,0 +367,0 @@ serialized.links.push({

index.d.ts

@@ -28,3 +28,3 @@ declare type NodeId = string;
     lowestCommonAncestors: (node1: NodeId, node2: NodeId) => string[];
-    topologicalSort: (sourceNodes: NodeId[], includeSourceNodes?: boolean) => string[];
+    topologicalSort: (sourceNodes?: string[] | undefined, includeSourceNodes?: boolean) => string[];
     shortestPath: (source: NodeId, destination: NodeId) => string[] & {
@@ -31,0 +31,0 @@ weight?: number | undefined;

index.js

 "use strict";
-var __extends = (this && this.__extends) || (function () {
-    var extendStatics = function (d, b) {
-        extendStatics = Object.setPrototypeOf ||
-            ({ __proto__: [] } instanceof Array && function (d, b) { d.__proto__ = b; }) ||
-            function (d, b) { for (var p in b) if (Object.prototype.hasOwnProperty.call(b, p)) d[p] = b[p]; };
-        return extendStatics(d, b);
-    };
-    return function (d, b) {
-        if (typeof b !== "function" && b !== null)
-            throw new TypeError("Class extends value " + String(b) + " is not a constructor or null");
-        extendStatics(d, b);
-        function __() { this.constructor = d; }
-        d.prototype = b === null ? Object.create(b) : (__.prototype = b.prototype, new __());
-    };
-})();
-var CycleError = /** @class */ (function (_super) {
-    __extends(CycleError, _super);
-    function CycleError(message) {
-        var _this = _super.call(this, message) || this;
-        Object.setPrototypeOf(_this, CycleError.prototype);
-        return _this;
+class CycleError extends Error {
+    constructor(message) {
+        super(message);
+        Object.setPrototypeOf(this, CycleError.prototype);
     }
-    return CycleError;
-}(Error));
+}
 // A graph data structure with depth-first search and topological sort.
 function Graph(serialized) {
     // Returned graph instance
-    var graph = {
-        addNode: addNode,
-        removeNode: removeNode,
-        nodes: nodes,
-        adjacent: adjacent,
-        addEdge: addEdge,
-        removeEdge: removeEdge,
-        hasEdge: hasEdge,
-        setEdgeWeight: setEdgeWeight,
-        getEdgeWeight: getEdgeWeight,
-        indegree: indegree,
-        outdegree: outdegree,
-        depthFirstSearch: depthFirstSearch,
-        hasCycle: hasCycle,
-        lowestCommonAncestors: lowestCommonAncestors,
-        topologicalSort: topologicalSort,
-        shortestPath: shortestPath,
-        serialize: serialize,
-        deserialize: deserialize
+    const graph = {
+        addNode,
+        removeNode,
+        nodes,
+        adjacent,
+        addEdge,
+        removeEdge,
+        hasEdge,
+        setEdgeWeight,
+        getEdgeWeight,
+        indegree,
+        outdegree,
+        depthFirstSearch,
+        hasCycle,
+        lowestCommonAncestors,
+        topologicalSort,
+        shortestPath,
+        serialize,
+        deserialize
     };
@@ -52,7 +34,7 @@ // The adjacency list of the graph.
     // Values are adjacent node id arrays.
-    var edges = {};
+    const edges = {};
     // The weights of edges.
     // Keys are string encodings of edges.
     // Values are weights (numbers).
-    var edgeWeights = {};
+    const edgeWeights = {};
     // If a serialized graph was passed into the constructor, deserialize it.
@@ -87,3 +69,3 @@ if (serialized) {
         // TODO: Better implementation with set data structure
-        var nodeSet = {};
+        const nodeSet = {};
         Object.keys(edges).forEach(function (u) {
@@ -115,3 +97,3 @@ nodeSet[u] = true;
     function getEdgeWeight(u, v) {
-        var weight = edgeWeights[encodeEdge(u, v)];
+        const weight = edgeWeights[encodeEdge(u, v)];
         return weight === undefined ? 1 : weight;
@@ -148,3 +130,3 @@ }
     function indegree(node) {
-        var degree = 0;
+        let degree = 0;
         function check(v) {
@@ -170,5 +152,3 @@ if (v === node) {
     // are used as source nodes.
-    function depthFirstSearch(sourceNodes, includeSourceNodes, errorOnCycle) {
-        if (includeSourceNodes === void 0) { includeSourceNodes = true; }
-        if (errorOnCycle === void 0) { errorOnCycle = false; }
+    function depthFirstSearch(sourceNodes, includeSourceNodes = true, errorOnCycle = false) {
         if (!sourceNodes) {
@@ -180,5 +160,5 @@ sourceNodes = nodes();
         }
-        var visited = {};
-        var visiting = {};
-        var nodeList = [];
+        const visited = {};
+        const visiting = {};
+        const nodeList = [];
         function DFSVisit(node) {
@@ -229,4 +209,4 @@ if (visiting[node] && errorOnCycle) {
     function lowestCommonAncestors(node1, node2) {
-        var node1Ancestors = [];
-        var lcas = [];
+        const node1Ancestors = [];
+        const lcas = [];
         function CA1Visit(visited, node) {
@@ -240,3 +220,3 @@ if (!visited[node]) {
                 }
-                return adjacent(node).every(function (node) {
+                return adjacent(node).every(node => {
                     return CA1Visit(visited, node);
@@ -256,3 +236,3 @@ });
                 else if (lcas.length == 0) {
-                    adjacent(node).forEach(function (node) {
+                    adjacent(node).forEach(node => {
                         CA2Visit(visited, node);
@@ -273,4 +253,3 @@ });
     // Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 613
-    function topologicalSort(sourceNodes, includeSourceNodes) {
-        if (includeSourceNodes === void 0) { includeSourceNodes = true; }
+    function topologicalSort(sourceNodes, includeSourceNodes = true) {
         return depthFirstSearch(sourceNodes, includeSourceNodes, true).reverse();
@@ -283,7 +262,7 @@ }
         // Upper bounds for shortest path weights from source.
-        var d = {};
+        const d = {};
         // Predecessors.
-        var p = {};
+        const p = {};
         // Poor man's priority queue, keyed on d.
-        var q = {};
+        let q = {};
         function initializeSingleSource() {
@@ -313,4 +292,4 @@ nodes().forEach(function (node) {
         function extractMin() {
-            var min = Infinity;
-            var minNode;
+            let min = Infinity;
+            let minNode;
             Object.keys(q).forEach(function (node) {
@@ -331,3 +310,3 @@ if (d[node] < min) {
         function relax(u, v) {
-            var w = getEdgeWeight(u, v);
+            const w = getEdgeWeight(u, v);
             if (d[v] > d[u] + w) {
@@ -341,14 +320,9 @@ d[v] = d[u] + w;
             initializePriorityQueue();
-            var _loop_1 = function () {
-                var u = extractMin();
+            while (!priorityQueueEmpty()) {
+                const u = extractMin();
                 if (u === null)
-                    return { value: void 0 };
+                    return;
                 adjacent(u).forEach(function (v) {
                     relax(u, v);
                 });
-            };
-            while (!priorityQueueEmpty()) {
-                var state_1 = _loop_1();
-                if (typeof state_1 === "object")
-                    return state_1.value;
             }
@@ -359,5 +333,5 @@ }
         function path() {
-            var nodeList = [];
-            var weight = 0;
-            var node = destination;
+            const nodeList = [];
+            let weight = 0;
+            let node = destination;
             while (p[node]) {
@@ -381,3 +355,3 @@ nodeList.push(node);
     function serialize() {
-        var serialized = {
+        const serialized = {
             nodes: nodes().map(function (id) {
@@ -389,3 +363,3 @@ return { id: id };
         serialized.nodes.forEach(function (node) {
-            var source = node.id;
+            const source = node.id;
             adjacent(source).forEach(function (target) {
@@ -392,0 +366,0 @@ serialized.links.push({

package.json

 {
     "name": "graph-data-structure",
-    "version": "1.15.0",
+    "version": "2.0.0",
     "description": "A graph data structure with topological sort.",
@@ -5,0 +5,0 @@ "main": "index.js",

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

Worsened metrics

Total package byte prevSize

41003

decreased by-6.85%

Lines of code

783

decreased by-6.23%

No dependency changes