flex-algo - npm Package Compare versions

Comparing version 0.1.19 to 0.1.20

lib/graph.d.ts

 declare class Graph {
     _adjList: number[][];
+    _indegrees: number[];
+    _nodes: number;
     constructor();
     create(vectors: number[][], nodes: number): void;
     createInformTimeGraph(manager: number[], nodes: number): void;
+    createCourseGraph(courses: number[][], numCourses: number): void;
     _dfsInformTime(vertex: number, informTime: number[]): number;
@@ -12,3 +15,4 @@ informTime(headID: number, informTime: number[]): number;
     bfs(vertex: number): number[];
+    isAcyclic(): boolean;
 }
 export { Graph };

lib/graph.js

@@ -7,2 +7,4 @@ "use strict";
         this._adjList = [];
+        this._indegrees = [];
+        this._nodes = 0;
     }
@@ -26,2 +28,14 @@ Graph.prototype.create = function (vectors, nodes) {
     };
+    Graph.prototype.createCourseGraph = function (courses, numCourses) {
+        this._nodes = numCourses;
+        this._adjList = new Array(numCourses).fill(0).map(function () { return []; });
+        this._indegrees = new Array(numCourses).fill(0);
+        for (var i = 0; i < courses.length; i++) {
+            var vector = courses[i];
+            var target = vector[0];
+            var source = vector[1];
+            this._adjList[source].push(target);
+            this._indegrees[target] += 1;
+        }
+    };
     Graph.prototype._dfsInformTime = function (vertex, informTime) {
@@ -85,4 +99,29 @@ var neighbors = this._adjList[vertex];
     };
+    Graph.prototype.isAcyclic = function () {
+        var queue = [];
+        for (var i = 0; i < this._indegrees.length; i++) {
+            if (this._indegrees[i] === 0) {
+                queue.push(i);
+            }
+        }
+        var count = 0;
+        while (queue.length > 0) {
+            var vertex = queue.shift();
+            count += 1;
+            if (vertex === undefined) {
+                continue;
+            }
+            var neighbors = this._adjList[vertex];
+            for (var i = 0; i < neighbors.length; i++) {
+                var neighbor = neighbors[i];
+                this._indegrees[neighbor] -= 1;
+                if (this._indegrees[neighbor] === 0) {
+                    queue.push(neighbor);
+                }
+            }
+        }
+        return count === this._nodes;
+    };
     return Graph;
 }());
 exports.Graph = Graph;

package.json

 {
   "name": "flex-algo",
-  "version": "0.1.19",
+  "version": "0.1.20",
   "description": "\"SDK for commonly used data structure and algorithms\"",
@@ -5,0 +5,0 @@ "main": "lib/index.js",

No alert changes

Improved metrics

Total package byte prevSize

29369

5.5%

Lines of code

790

5.76%

No dependency changes