tree-multiset-typed - npm Package Compare versions

Comparing version 1.41.8 to 1.41.9

dist/data-structures/graph/abstract-graph.d.ts

@@ -117,5 +117,6 @@ import type { DijkstraResult, VertexKey } from '../../types';
      * @param {VO | VertexKey} v2 - The parameter `v2` represents either a vertex object (`VO`) or a vertex ID (`VertexKey`).
+     * @param limit - The count of limitation of result array.
      * @returns The function `getAllPathsBetween` returns an array of arrays of vertices (`VO[][]`).
      */
-    getAllPathsBetween(v1: VO | VertexKey, v2: VO | VertexKey): VO[][];
+    getAllPathsBetween(v1: VO | VertexKey, v2: VO | VertexKey, limit?: number): VO[][];
     /**
@@ -152,6 +153,9 @@ * The function calculates the sum of weights along a given path.
      * to false, the function will use breadth-first search (BFS) to find the minimum path.
+     * @param isDFS - If set to true, it enforces the use of getAllPathsBetween to first obtain all possible paths,
+     * followed by iterative computation of the shortest path. This approach may result in exponential time complexity,
+     * so the default method is to use the Dijkstra algorithm to obtain the shortest weighted path.
      * @returns The function `getMinPathBetween` returns an array of vertices (`VO[]`) representing the minimum path between
      * two vertices (`v1` and `v2`). If there is no path between the vertices, it returns `null`.
      */
-    getMinPathBetween(v1: VO | VertexKey, v2: VO | VertexKey, isWeight?: boolean): VO[] | null;
+    getMinPathBetween(v1: VO | VertexKey, v2: VO | VertexKey, isWeight?: boolean, isDFS?: boolean): VO[] | null;
     /**
@@ -158,0 +162,0 @@ * Dijkstra algorithm time: O(VE) space: O(VO + EO)

dist/data-structures/graph/abstract-graph.js

@@ -7,4 +7,4 @@ "use strict";
  *
- * @author Kirk Qi
- * @copyright Copyright (c) 2022 Kirk Qi <[e-mail]>
+ * @author Tyler Zeng
+ * @copyright Copyright (c) 2022 Tyler Zeng <[e-mail]>
  * @license MIT License
@@ -166,5 +166,6 @@ */
      * @param {VO | VertexKey} v2 - The parameter `v2` represents either a vertex object (`VO`) or a vertex ID (`VertexKey`).
+     * @param limit - The count of limitation of result array.
      * @returns The function `getAllPathsBetween` returns an array of arrays of vertices (`VO[][]`).
      */
-    getAllPathsBetween(v1, v2) {
+    getAllPathsBetween(v1, v2, limit = 1000) {
         const paths = [];
@@ -176,18 +177,19 @@ const vertex1 = this._getVertex(v1);
         }
-        const dfs = (cur, dest, visiting, path) => {
-            visiting.add(cur);
-            if (cur === dest) {
-                paths.push([vertex1, ...path]);
+        const stack = [];
+        stack.push({ vertex: vertex1, path: [vertex1] });
+        while (stack.length > 0) {
+            const { vertex, path } = stack.pop();
+            if (vertex === vertex2) {
+                paths.push(path);
+                if (paths.length >= limit)
+                    return paths;
             }
-            const neighbors = this.getNeighbors(cur);
+            const neighbors = this.getNeighbors(vertex);
             for (const neighbor of neighbors) {
-                if (!visiting.has(neighbor)) {
-                    path.push(neighbor);
-                    dfs(neighbor, dest, visiting, path);
-                    path.pop();
+                if (!path.includes(neighbor)) {
+                    const newPath = [...path, neighbor];
+                    stack.push({ vertex: neighbor, path: newPath });
                 }
             }
-            visiting.delete(cur);
-        };
-        dfs(vertex1, vertex2, new Set(), []);
+        }
         return paths;
@@ -276,33 +278,41 @@ }
      * to false, the function will use breadth-first search (BFS) to find the minimum path.
+     * @param isDFS - If set to true, it enforces the use of getAllPathsBetween to first obtain all possible paths,
+     * followed by iterative computation of the shortest path. This approach may result in exponential time complexity,
+     * so the default method is to use the Dijkstra algorithm to obtain the shortest weighted path.
      * @returns The function `getMinPathBetween` returns an array of vertices (`VO[]`) representing the minimum path between
      * two vertices (`v1` and `v2`). If there is no path between the vertices, it returns `null`.
      */
-    getMinPathBetween(v1, v2, isWeight) {
+    getMinPathBetween(v1, v2, isWeight, isDFS = false) {
+        var _a, _b;
         if (isWeight === undefined)
             isWeight = false;
         if (isWeight) {
-            const allPaths = this.getAllPathsBetween(v1, v2);
-            let min = Infinity;
-            let minIndex = -1;
-            let index = 0;
-            for (const path of allPaths) {
-                const pathSumWeight = this.getPathSumWeight(path);
-                if (pathSumWeight < min) {
-                    min = pathSumWeight;
-                    minIndex = index;
+            if (isDFS) {
+                const allPaths = this.getAllPathsBetween(v1, v2, 10000);
+                let min = Infinity;
+                let minIndex = -1;
+                let index = 0;
+                for (const path of allPaths) {
+                    const pathSumWeight = this.getPathSumWeight(path);
+                    if (pathSumWeight < min) {
+                        min = pathSumWeight;
+                        minIndex = index;
+                    }
+                    index++;
                 }
-                index++;
+                return allPaths[minIndex] || null;
             }
-            return allPaths[minIndex] || null;
+            else {
+                return (_b = (_a = this.dijkstra(v1, v2, true, true)) === null || _a === void 0 ? void 0 : _a.minPath) !== null && _b !== void 0 ? _b : [];
+            }
         }
         else {
-            // BFS
+            // DFS
             let minPath = [];
             const vertex1 = this._getVertex(v1);
             const vertex2 = this._getVertex(v2);
-            if (!(vertex1 && vertex2)) {
+            if (!(vertex1 && vertex2))
                 return [];
-            }
             const dfs = (cur, dest, visiting, path) => {
-                visiting.set(cur, true);
+                visiting.add(cur);
                 if (cur === dest) {
@@ -314,11 +324,11 @@ minPath = [vertex1, ...path];
                 for (const neighbor of neighbors) {
-                    if (!visiting.get(neighbor)) {
+                    if (!visiting.has(neighbor)) {
                         path.push(neighbor);
                         dfs(neighbor, dest, visiting, path);
-                        (0, utils_1.arrayRemove)(path, (vertex) => vertex === neighbor);
+                        path.pop();
                     }
                 }
-                visiting.set(cur, false);
+                visiting.delete(cur);
             };
-            dfs(vertex1, vertex2, new Map(), []);
+            dfs(vertex1, vertex2, new Set(), []);
             return minPath;
@@ -325,0 +335,0 @@ }

package.json

 {
   "name": "tree-multiset-typed",
-  "version": "1.41.8",
+  "version": "1.41.9",
   "description": "Tree Multiset, AVLTree, BST, Binary Tree. Javascript & Typescript Data Structure.",
@@ -182,4 +182,4 @@ "main": "dist/index.js",
   "dependencies": {
-    "data-structure-typed": "^1.41.8"
+    "data-structure-typed": "^1.41.9"
   }
 }

src/data-structures/graph/abstract-graph.ts

 /**
  * data-structure-typed
  *
- * @author Kirk Qi
- * @copyright Copyright (c) 2022 Kirk Qi <[e-mail]>
+ * @author Tyler Zeng
+ * @copyright Copyright (c) 2022 Tyler Zeng <[e-mail]>
  * @license MIT License
  */
-import {arrayRemove, uuidV4} from '../../utils';
+import {uuidV4} from '../../utils';
 import {PriorityQueue} from '../priority-queue';
@@ -226,8 +226,10 @@ import type {DijkstraResult, VertexKey} from '../../types';
    * @param {VO | VertexKey} v2 - The parameter `v2` represents either a vertex object (`VO`) or a vertex ID (`VertexKey`).
+   * @param limit - The count of limitation of result array.
    * @returns The function `getAllPathsBetween` returns an array of arrays of vertices (`VO[][]`).
    */
-  getAllPathsBetween(v1: VO | VertexKey, v2: VO | VertexKey): VO[][] {
+  getAllPathsBetween(v1: VO | VertexKey, v2: VO | VertexKey, limit = 1000): VO[][] {
     const paths: VO[][] = [];
     const vertex1 = this._getVertex(v1);
     const vertex2 = this._getVertex(v2);
+
     if (!(vertex1 && vertex2)) {
@@ -237,25 +239,27 @@ return [];
 
-    const dfs = (cur: VO, dest: VO, visiting: Set<VO>, path: VO[]) => {
-      visiting.add(cur);
+    const stack: { vertex: VO, path: VO[] }[] = [];
+    stack.push({ vertex: vertex1, path: [vertex1] });
 
-      if (cur === dest) {
-        paths.push([vertex1, ...path]);
+    while (stack.length > 0) {
+      const { vertex, path } = stack.pop()!;
+
+      if (vertex === vertex2) {
+        paths.push(path);
+        if (paths.length >= limit) return paths;
       }
 
-      const neighbors = this.getNeighbors(cur);
+      const neighbors = this.getNeighbors(vertex);
       for (const neighbor of neighbors) {
-        if (!visiting.has(neighbor)) {
-          path.push(neighbor);
-          dfs(neighbor, dest, visiting, path);
-          path.pop();
+        if (!path.includes(neighbor)) {
+          const newPath = [...path, neighbor];
+          stack.push({ vertex: neighbor, path: newPath });
         }
       }
-
-      visiting.delete(cur);
-    };
-
-    dfs(vertex1, vertex2, new Set<VO>(), []);
+    }
     return paths;
   }
 
+
+
+
   /**
@@ -343,34 +347,39 @@ * The function calculates the sum of weights along a given path.
    * to false, the function will use breadth-first search (BFS) to find the minimum path.
+   * @param isDFS - If set to true, it enforces the use of getAllPathsBetween to first obtain all possible paths,
+   * followed by iterative computation of the shortest path. This approach may result in exponential time complexity,
+   * so the default method is to use the Dijkstra algorithm to obtain the shortest weighted path.
    * @returns The function `getMinPathBetween` returns an array of vertices (`VO[]`) representing the minimum path between
    * two vertices (`v1` and `v2`). If there is no path between the vertices, it returns `null`.
    */
-  getMinPathBetween(v1: VO | VertexKey, v2: VO | VertexKey, isWeight?: boolean): VO[] | null {
+  getMinPathBetween(v1: VO | VertexKey, v2: VO | VertexKey, isWeight?: boolean, isDFS = false): VO[] | null {
     if (isWeight === undefined) isWeight = false;
 
     if (isWeight) {
-      const allPaths = this.getAllPathsBetween(v1, v2);
-      let min = Infinity;
-      let minIndex = -1;
-      let index = 0;
-      for (const path of allPaths) {
-        const pathSumWeight = this.getPathSumWeight(path);
-        if (pathSumWeight < min) {
-          min = pathSumWeight;
-          minIndex = index;
+      if (isDFS) {
+        const allPaths = this.getAllPathsBetween(v1, v2, 10000);
+        let min = Infinity;
+        let minIndex = -1;
+        let index = 0;
+        for (const path of allPaths) {
+          const pathSumWeight = this.getPathSumWeight(path);
+          if (pathSumWeight < min) {
+            min = pathSumWeight;
+            minIndex = index;
+          }
+          index++;
         }
-        index++;
+        return allPaths[minIndex] || null;
+      } else {
+        return this.dijkstra(v1, v2, true, true)?.minPath ?? [];
       }
-      return allPaths[minIndex] || null;
+
     } else {
-      // BFS
+      // DFS
       let minPath: VO[] = [];
       const vertex1 = this._getVertex(v1);
       const vertex2 = this._getVertex(v2);
-      if (!(vertex1 && vertex2)) {
-        return [];
-      }
+      if (!(vertex1 && vertex2)) return [];
 
-      const dfs = (cur: VO, dest: VO, visiting: Map<VO, boolean>, path: VO[]) => {
-        visiting.set(cur, true);
-
+      const dfs = (cur: VO, dest: VO, visiting: Set<VO>, path: VO[]) => {
+        visiting.add(cur);
         if (cur === dest) {
@@ -383,13 +392,13 @@ minPath = [vertex1, ...path];
         for (const neighbor of neighbors) {
-          if (!visiting.get(neighbor)) {
+          if (!visiting.has(neighbor)) {
             path.push(neighbor);
             dfs(neighbor, dest, visiting, path);
-            arrayRemove(path, (vertex: VO) => vertex === neighbor);
+            path.pop();
           }
         }
 
-        visiting.set(cur, false);
+        visiting.delete(cur);
       };
 
-      dfs(vertex1, vertex2, new Map<VO, boolean>(), []);
+      dfs(vertex1, vertex2, new Set<VO>(), []);
       return minPath;
@@ -396,0 +405,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

1550020

increased by0.11%

Lines of code

25852

increased by0.08%

Dependency changes

• Updateddata-structure-typed@^1.41.9