ts-structures - npm Package Compare versions

Comparing version 0.5.5 to 0.5.6

graph/list-graph.d.ts

@@ -1,2 +0,2 @@
-import type { ReduceFunction, TraverseCallback } from '../_shared/types';
+import type { FilterFunction, ReduceFunction, TraverseCallback } from '../_shared/types';
 import type { Graph, GraphOptions } from '.';
@@ -165,2 +165,8 @@ /**
     /**
+     * Adds new vertices from given tuples [id, data]
+     *
+     * @param vertices - The tuples separated by a comma
+     */
+    addVertices(...vertices: [string, T][]): void;
+    /**
      * Removes vertex qith given id and its related edges.
@@ -261,2 +267,14 @@ *
     reduce<R>(reduce: ReduceFunction<Vertex<T>, R>, initialValue: R): R;
+    /**
+     * Returns an array of `Vertex<T>` representing the steps of
+     * the shortest path from position `from` to position `to`.
+     * It uses Dijktsra's algorithm.
+     *
+     * @param from - The starting vertex id.
+     * @param to - The destination vertex id.
+     * @param filter - An optional filter function applied on vertices
+     * to restrict or not their usage.
+     * @returns An array of {@link Vertex | Vertex\<T\>}
+     */
+    shortestPath(from: string, to: string, filter?: FilterFunction<Vertex<T>>): Vertex<T>[];
     traverseDFSRecursive(rootId: string, callback: TraverseCallback<Vertex<T>>): void;
@@ -263,0 +281,0 @@ traverseBFS(rootId: string, callback: TraverseCallback<Vertex<T>>): void;

graph/list-graph.js

@@ -216,2 +216,10 @@ "use strict";
     /**
+     * Adds new vertices from given tuples [id, data]
+     *
+     * @param vertices - The tuples separated by a comma
+     */
+    addVertices(...vertices) {
+        vertices.forEach(([id, data]) => this.addVertex(id, data));
+    }
+    /**
      * Removes vertex qith given id and its related edges.
@@ -373,2 +381,68 @@ *
     }
+    // TODO: find a correct way to also restitute distance between
+    // each step. That implies not returning a true Vertex<T>[]
+    // because of that additionnal info not carried by a Vertex.
+    //
+    // A linked list seems well suited for the task
+    // -> return DoublyLinkedList<Vertex<T>>
+    // each DLLNode: { value: { vertex: Vertex<T>, dist: number }, (...) }
+    // `dist` would represent the distance from either the previous
+    // vertex or from the start.
+    //
+    // Or an array of tuples [[Vertex<T>, number], [Vertex<T>, number], ...]
+    /**
+     * Returns an array of `Vertex<T>` representing the steps of
+     * the shortest path from position `from` to position `to`.
+     * It uses Dijktsra's algorithm.
+     *
+     * @param from - The starting vertex id.
+     * @param to - The destination vertex id.
+     * @param filter - An optional filter function applied on vertices
+     * to restrict or not their usage.
+     * @returns An array of {@link Vertex | Vertex\<T\>}
+     */
+    shortestPath(from, to, filter) {
+        var _a;
+        const pqueue = new queue_1.PriorityQueue();
+        const distances = new Map();
+        const previous = new Map();
+        const path = [];
+        if (!this.get(from) || !this.get(to))
+            return path;
+        // initialize
+        this.data.forEach((_, id) => {
+            if (id === from) {
+                distances.set(id, 0);
+                pqueue.enqueue(id, 0);
+            }
+            else {
+                distances.set(id, Infinity);
+                pqueue.enqueue(id, Infinity);
+            }
+            previous.set(id, null);
+        });
+        let current;
+        while (current = pqueue.dequeue()) { // eslint-disable-line no-cond-assign
+            let smallest = current.value;
+            // Path calculations over, render the final array
+            if (smallest === to) {
+                while (previous.get(smallest) !== undefined) { // explicit undefined or 0 would break
+                    path.push(this.get(smallest));
+                    smallest = previous.get(smallest);
+                }
+                break;
+            }
+            (_a = this.get(smallest)) === null || _a === void 0 ? void 0 : _a.forEachEdge(({ to, weight }) => {
+                if (filter && !filter(this.get(to)))
+                    return;
+                const candidate = distances.get(smallest) + weight;
+                if (candidate < distances.get(to)) {
+                    distances.set(to, candidate);
+                    previous.set(to, smallest);
+                    pqueue.enqueue(to, candidate);
+                }
+            });
+        }
+        return path.reverse();
+    }
     // CHECKPOINT REFACTO
@@ -375,0 +449,0 @@ traverseDFSRecursive(rootId, callback) {

index.d.ts

 import type { CompareFunction, FilterFunction, MapFunction, ReduceFunction, TraverseCallback } from './_shared';
+import type { PriorityQueueNode } from './queue';
+import type { Vertex } from './graph';
 import { TraverseMethod } from './_shared';
@@ -9,3 +11,3 @@ import { DoublyLinkedList } from './list';
 import { ListGraph } from './graph';
-export type { CompareFunction, FilterFunction, MapFunction, ReduceFunction, TraverseCallback, };
+export type { CompareFunction, FilterFunction, MapFunction, ReduceFunction, TraverseCallback, PriorityQueueNode, Vertex, };
 export { DoublyLinkedList, Queue, PriorityQueue, Stack, BinarySearchTree, TraverseMethod, BinaryHeap, ListGraph, };

package.json

 {
   "name": "ts-structures",
-  "version": "0.5.5",
+  "version": "0.5.6",
   "description": "TypeScript implementation of common data structures",
@@ -5,0 +5,0 @@ "main": "index.js",

queue/index.d.ts

@@ -0,3 +1,5 @@
+import type { PriorityQueueNode } from './priority-queue';
 import { Queue } from './queue';
 import { PriorityQueue } from './priority-queue';
+export type { PriorityQueueNode, };
 export { Queue, PriorityQueue, };

queue/priority-queue.d.ts

@@ -52,2 +52,3 @@ import { CappedStructure } from '../_shared';
 }
-export { PriorityQueue };
+export type { PriorityQueueNode, };
+export { PriorityQueue, };

No alert changes

Improved metrics

Total package byte prevSize

99799

increased by4.08%

Lines of code

2655

increased by3.79%

No dependency changes