@algorithm.ts/graph - npm Package Compare versions

Comparing version 2.0.11 to 2.0.12

lib/cjs/index.js

@@ -15,3 +15,12 @@ 'use strict';
 };
+const getShortestPath = (bestFrom, source, target) => {
+    const path = [target];
+    for (let x = target, parent; x !== source; x = parent) {
+        parent = bestFrom[x];
+        path.push(parent);
+    }
+    return path.reverse();
+};
 
 exports.buildEdgeMap = buildEdgeMap;
+exports.getShortestPath = getShortestPath;

lib/esm/index.js

@@ -11,3 +11,11 @@ const buildEdgeMap = (N, edges) => {
 };
+const getShortestPath = (bestFrom, source, target) => {
+    const path = [target];
+    for (let x = target, parent; x !== source; x = parent) {
+        parent = bestFrom[x];
+        path.push(parent);
+    }
+    return path.reverse();
+};
 
-export { buildEdgeMap };
+export { buildEdgeMap, getShortestPath };

lib/types/util.d.ts

@@ -10,1 +10,10 @@ /**
 }>) => number[][];
+/**
+ * List all points on the shortest path from source to target in order.
+ *
+ * @param bestFrom
+ * @param source
+ * @param target
+ * @returns
+ */
+export declare const getShortestPath: (bestFrom: ReadonlyArray<number>, source: number, target: number) => number[];

package.json

 {
   "name": "@algorithm.ts/graph",
-  "version": "2.0.11",
+  "version": "2.0.12",
   "description": "Types and utils from solving graph problems.",
@@ -43,5 +43,5 @@ "author": {
   "dependencies": {
-    "@algorithm.ts/circular-queue": "^2.0.11"
+    "@algorithm.ts/circular-queue": "^2.0.12"
   },
-  "gitHead": "42feafd0303f51767aa7e498f6de84d9478c1dca"
+  "gitHead": "cfc415a6e56d76dcf795421d92dd81ac2a39a5fc"
 }

README.md

@@ -81,2 +81,4 @@ <header>
   ```typescript {17}
+  import { buildEdgeMap } from '@algorithm.ts/graph'
+
   const Nodes = {
@@ -103,3 +105,16 @@ A: 0,
 
+* `getShortestPath`
 
+  ```typescript {17}
+  import { getShortestPath } from '@algorithm.ts/graph'
+
+  /**
+   * @param bestFrom  Record the shortest path parent source point to the specified point.
+   * @param source    The source node on the shortest path.
+   * @param target    The target node on the shortest path.
+   */
+  getShortestPath(bestFrom: number[], source: number, target: number): number[] // nodes 
+  ```
+
+
 ## Related
@@ -106,0 +121,0 @@

No alert changes

Improved metrics

Total package byte prevSize

8310

increased by18.07%

Lines of code

85

increased by44.07%

Number of lines in readme file

128

increased by13.27%

Dependency changes

• [e-mail]/circular-queue@^2.0.12