@algorithm.ts/bellman-ford - npm Package Compare versions

Comparing version 2.0.14 to 3.0.0-alpha.0

lib/cjs/index.js

@@ -5,26 +5,28 @@ 'use strict';
 
-var circularQueue = require('@algorithm.ts/circular-queue');
-var graph = require('@algorithm.ts/graph');
+var queue = require('@algorithm.ts/queue');
 
+const BIGINT_ZERO = BigInt(0);
+BigInt(1);
+
 class BellmanFord {
+    ZERO;
     INF;
-    ZERO;
+    dist;
     bestFrom;
-    dist;
     inq;
     inqTimes;
     Q;
-    constructor(options = {}) {
-        this.INF = options.INF ?? Math.floor(Number.MAX_SAFE_INTEGER / 2);
-        this.ZERO = 0;
-        this.bestFrom = options.bestFrom ?? [];
-        this.dist = options.dist ?? [];
-        this.inq = options.inq ?? [];
-        this.inqTimes = options.inqTimes ?? [];
-        this.Q = circularQueue.createCircularQueue();
+    constructor(props) {
+        this.ZERO = props.ZERO;
+        this.INF = props.INF;
+        this.bestFrom = [];
+        this.dist = [];
+        this.inq = [];
+        this.inqTimes = [];
+        this.Q = new queue.CircularQueue();
     }
-    bellmanFord(graph$1, options = {}, onResolved) {
-        const { ZERO, Q } = this;
-        const { N, source, edges, G } = graph$1;
-        const { INF = this.INF, bestFrom = this.bestFrom, inq = this.inq, inqTimes = this.inqTimes, dist = this.dist, } = options;
+    bellmanFord(graph, options = {}) {
+        const { N, source, edges, G } = graph;
+        const { ZERO, Q, bestFrom, dist, inq, inqTimes } = this;
+        const { INF = this.INF } = options;
         bestFrom.length = N;
@@ -39,18 +41,23 @@ dist.length = N;
         dist[source] = ZERO;
-        Q.init(N + 1);
+        Q.init();
+        Q.resize(N + 1);
         Q.enqueue(source);
-        while (Q.size() > 0) {
+        let edge;
+        let to;
+        let candidate;
+        while (Q.size > 0) {
             const o = Q.dequeue();
             inq[o] = false;
             for (let i = 0, g = G[o], _size = g.length; i < _size; ++i) {
-                const x = g[i];
-                const edge = edges[x];
-                if (dist[edge.to] > dist[o] + edge.cost) {
-                    dist[edge.to] = dist[o] + edge.cost;
-                    bestFrom[edge.to] = o;
-                    if (!inq[edge.to]) {
-                        Q.enqueue(edge.to);
-                        inq[edge.to] = true;
-                        if (++inqTimes[edge.to] > N)
-                            return false;
+                edge = edges[g[i]];
+                to = edge.to;
+                candidate = (dist[o] + edge.cost);
+                if (dist[to] > candidate) {
+                    dist[to] = candidate;
+                    bestFrom[to] = o;
+                    if (!inq[to]) {
+                        Q.enqueue(to);
+                        inq[to] = true;
+                        if (++inqTimes[to] > N)
+                            return { hasNegativeCycle: true };
                     }
@@ -60,23 +67,30 @@ }
         }
-        if (onResolved) {
-            const getShortestPathTo = (target) => graph.getShortestPath(bestFrom, source, target);
-            const context = {
-                INF: this.INF,
-                bestFrom: this.bestFrom,
-                dist: this.dist,
-                getShortestPathTo,
-            };
-            onResolved(context);
-        }
-        return true;
+        return { hasNegativeCycle: false, INF, source, bestFrom, dist };
     }
 }
 
-function bellmanFord(graph, options = {}, onResolved) {
-    return _bellmanFord.bellmanFord(graph, options, onResolved);
-}
-const _bellmanFord = new BellmanFord();
+let _bellmanFord = null;
+const bellmanFord = (graph, options = {}) => {
+    if (_bellmanFord === null) {
+        _bellmanFord = new BellmanFord({
+            ZERO: 0,
+            INF: Math.floor(Number.MAX_SAFE_INTEGER / 2) - 1,
+        });
+    }
+    return _bellmanFord.bellmanFord(graph, options);
+};
+let _bellmanFordBigint = null;
+const bellmanFordBigint = (graph, options = {}) => {
+    if (_bellmanFordBigint === null) {
+        _bellmanFordBigint = new BellmanFord({
+            ZERO: BIGINT_ZERO,
+            INF: BigInt(Number.MAX_SAFE_INTEGER),
+        });
+    }
+    return _bellmanFordBigint.bellmanFord(graph, options);
+};
 
 exports.BellmanFord = BellmanFord;
 exports.bellmanFord = bellmanFord;
+exports.bellmanFordBigint = bellmanFordBigint;
 exports["default"] = bellmanFord;

lib/esm/index.js

@@ -1,25 +0,27 @@
-import { createCircularQueue } from '@algorithm.ts/circular-queue';
-import { getShortestPath } from '@algorithm.ts/graph';
+import { CircularQueue } from '@algorithm.ts/queue';
 
+const BIGINT_ZERO = BigInt(0);
+BigInt(1);
+
 class BellmanFord {
+    ZERO;
     INF;
-    ZERO;
+    dist;
     bestFrom;
-    dist;
     inq;
     inqTimes;
     Q;
-    constructor(options = {}) {
-        this.INF = options.INF ?? Math.floor(Number.MAX_SAFE_INTEGER / 2);
-        this.ZERO = 0;
-        this.bestFrom = options.bestFrom ?? [];
-        this.dist = options.dist ?? [];
-        this.inq = options.inq ?? [];
-        this.inqTimes = options.inqTimes ?? [];
-        this.Q = createCircularQueue();
+    constructor(props) {
+        this.ZERO = props.ZERO;
+        this.INF = props.INF;
+        this.bestFrom = [];
+        this.dist = [];
+        this.inq = [];
+        this.inqTimes = [];
+        this.Q = new CircularQueue();
     }
-    bellmanFord(graph, options = {}, onResolved) {
-        const { ZERO, Q } = this;
+    bellmanFord(graph, options = {}) {
         const { N, source, edges, G } = graph;
-        const { INF = this.INF, bestFrom = this.bestFrom, inq = this.inq, inqTimes = this.inqTimes, dist = this.dist, } = options;
+        const { ZERO, Q, bestFrom, dist, inq, inqTimes } = this;
+        const { INF = this.INF } = options;
         bestFrom.length = N;
@@ -34,18 +36,23 @@ dist.length = N;
         dist[source] = ZERO;
-        Q.init(N + 1);
+        Q.init();
+        Q.resize(N + 1);
         Q.enqueue(source);
-        while (Q.size() > 0) {
+        let edge;
+        let to;
+        let candidate;
+        while (Q.size > 0) {
             const o = Q.dequeue();
             inq[o] = false;
             for (let i = 0, g = G[o], _size = g.length; i < _size; ++i) {
-                const x = g[i];
-                const edge = edges[x];
-                if (dist[edge.to] > dist[o] + edge.cost) {
-                    dist[edge.to] = dist[o] + edge.cost;
-                    bestFrom[edge.to] = o;
-                    if (!inq[edge.to]) {
-                        Q.enqueue(edge.to);
-                        inq[edge.to] = true;
-                        if (++inqTimes[edge.to] > N)
-                            return false;
+                edge = edges[g[i]];
+                to = edge.to;
+                candidate = (dist[o] + edge.cost);
+                if (dist[to] > candidate) {
+                    dist[to] = candidate;
+                    bestFrom[to] = o;
+                    if (!inq[to]) {
+                        Q.enqueue(to);
+                        inq[to] = true;
+                        if (++inqTimes[to] > N)
+                            return { hasNegativeCycle: true };
                     }
@@ -55,21 +62,27 @@ }
         }
-        if (onResolved) {
-            const getShortestPathTo = (target) => getShortestPath(bestFrom, source, target);
-            const context = {
-                INF: this.INF,
-                bestFrom: this.bestFrom,
-                dist: this.dist,
-                getShortestPathTo,
-            };
-            onResolved(context);
-        }
-        return true;
+        return { hasNegativeCycle: false, INF, source, bestFrom, dist };
     }
 }
 
-function bellmanFord(graph, options = {}, onResolved) {
-    return _bellmanFord.bellmanFord(graph, options, onResolved);
-}
-const _bellmanFord = new BellmanFord();
+let _bellmanFord = null;
+const bellmanFord = (graph, options = {}) => {
+    if (_bellmanFord === null) {
+        _bellmanFord = new BellmanFord({
+            ZERO: 0,
+            INF: Math.floor(Number.MAX_SAFE_INTEGER / 2) - 1,
+        });
+    }
+    return _bellmanFord.bellmanFord(graph, options);
+};
+let _bellmanFordBigint = null;
+const bellmanFordBigint = (graph, options = {}) => {
+    if (_bellmanFordBigint === null) {
+        _bellmanFordBigint = new BellmanFord({
+            ZERO: BIGINT_ZERO,
+            INF: BigInt(Number.MAX_SAFE_INTEGER),
+        });
+    }
+    return _bellmanFordBigint.bellmanFord(graph, options);
+};
 
-export { BellmanFord, bellmanFord, bellmanFord as default };
+export { BellmanFord, bellmanFord, bellmanFordBigint, bellmanFord as default };

lib/types/index.d.ts

@@ -1,7 +0,12 @@
-import { ICircularQueue } from '@algorithm.ts/circular-queue';
-import { IEdge, IGraph } from '@algorithm.ts/graph';
+import { IDigraphEdge, IDigraph, DeepReadonly } from '@algorithm.ts/types';
+import { ICircularQueue } from '@algorithm.ts/queue';
 
-declare type IBellmanFordEdge = IEdge;
-interface IBellmanFordGraph extends IGraph {
+interface IBellmanFordEdge<C extends number | bigint> extends IDigraphEdge {
     /**
+     * The cost of walking along this side.
+     */
+    cost: C;
+}
+interface IBellmanFordGraph<C extends number | bigint> extends IDigraph<IBellmanFordEdge<C>> {
+    /**
      * The source node. (0-index)
@@ -11,34 +16,21 @@ */
 }
-
-interface IOptions {
+interface IBellmanFordOptions<C extends number | bigint> {
     /**
-     * A big number, representing the unreachable cost.
+     * A big number / bigint, representing the unreachable cost.
      */
-    INF?: number;
+    INF?: C;
+}
+declare type IBellmanFordResult<C extends number | bigint> = {
+    hasNegativeCycle: true;
+} | {
+    hasNegativeCycle: false;
     /**
-     * Record the shortest path parent source point to the specified point.
-     * For example: bestFrom[x] represents the previous position of x in the shortest path
-     *              parent the source point to x.
+     * A big number, representing the unreachable cost.
      */
-    bestFrom?: number[];
+    INF: C;
     /**
-     * An array recording the shortest distance to the source point.
+     * Source point
      */
-    dist?: number[];
+    source: number;
     /**
-     * Used to check if an element is already in the queue.
-     */
-    inq?: boolean[];
-    /**
-     * Record the number of times an element is enqueued,
-     * used to check whether there is a negative cycle.
-     */
-    inqTimes?: number[];
-}
-interface IContext {
-    /**
-     * A big number, representing the unreachable cost.
-     */
-    INF: number;
-    /**
      * Record the shortest path parent source point to the specified point.
@@ -52,28 +44,30 @@ * For example: bestFrom[x] represents the previous position of x in the shortest path
      */
-    dist: ReadonlyArray<number>;
+    dist: ReadonlyArray<C>;
+};
+
+declare const bellmanFord: (graph: DeepReadonly<IBellmanFordGraph<number>>, options?: IBellmanFordOptions<number>) => IBellmanFordResult<number>;
+declare const bellmanFordBigint: (graph: DeepReadonly<IBellmanFordGraph<bigint>>, options?: IBellmanFordOptions<bigint>) => IBellmanFordResult<bigint>;
+
+interface IBellmanFordProps<C extends number | bigint> {
     /**
-     * Get shortest path from the source point to the given target point.
+     * The value represent the zero cost, 0 for number and 0n for bigint.
      */
-    getShortestPathTo(target: number): number[];
+    ZERO: C;
+    /**
+     * A big number / bigint, representing the unreachable cost.
+     */
+    INF: C;
 }
-declare class BellmanFord {
-    protected readonly INF: number;
-    protected readonly ZERO: number;
+declare class BellmanFord<C extends number | bigint> {
+    protected readonly ZERO: C;
+    protected readonly INF: C;
+    protected readonly dist: C[];
     protected readonly bestFrom: number[];
-    protected readonly dist: number[];
     protected readonly inq: boolean[];
     protected readonly inqTimes: number[];
     protected readonly Q: ICircularQueue<number>;
-    constructor(options?: IOptions);
-    bellmanFord(graph: IBellmanFordGraph, options?: IOptions, onResolved?: (context: IContext) => void): boolean;
+    constructor(props: IBellmanFordProps<C>);
+    bellmanFord(graph: DeepReadonly<IBellmanFordGraph<C>>, options?: IBellmanFordOptions<C>): IBellmanFordResult<C>;
 }
 
-/**
- * The bellman-ford algorithm, optimized with queue.
- *
- * @param graph
- * @param options
- */
-declare function bellmanFord(graph: IBellmanFordGraph, options?: IOptions, onResolved?: (context: IContext) => void): boolean;
-
-export { BellmanFord, IBellmanFordEdge, IBellmanFordGraph, IContext, IOptions, bellmanFord, bellmanFord as default };
+export { BellmanFord, IBellmanFordEdge, IBellmanFordGraph, IBellmanFordOptions, IBellmanFordProps, IBellmanFordResult, bellmanFord, bellmanFordBigint, bellmanFord as default };

package.json

 {
   "name": "@algorithm.ts/bellman-ford",
-  "version": "2.0.14",
+  "version": "3.0.0-alpha.0",
   "description": "Bellman-ford algorithm.",
@@ -11,6 +11,6 @@ "author": {
     "type": "git",
-    "url": "https://github.com/guanghechen/algorithm.ts/tree/release-2.x.x",
+    "url": "https://github.com/guanghechen/algorithm.ts/tree/release-3.x.x",
     "directory": "packages/bellman-ford"
   },
-  "homepage": "https://github.com/guanghechen/algorithm.ts/tree/release-2.x.x/packages/bellman-ford#readme",
+  "homepage": "https://github.com/guanghechen/algorithm.ts/tree/release-3.x.x/packages/bellman-ford#readme",
   "keywords": [
@@ -46,6 +46,7 @@ "algorithm",
   "dependencies": {
-    "@algorithm.ts/circular-queue": "^2.0.14",
-    "@algorithm.ts/graph": "^2.0.14"
+    "@algorithm.ts/constant": "^3.0.0-alpha.0",
+    "@algorithm.ts/queue": "^3.0.0-alpha.0",
+    "@algorithm.ts/types": "^3.0.0-alpha.0"
   },
-  "gitHead": "53a24624195c9f09422c9769c552f9066bc22c70"
+  "gitHead": "7562a908843d63b6b1bf92e7aa2104e7b294eaa0"
 }

README.md

 <header>
   <h1 align="center">
-    <a href="https://github.com/guanghechen/algorithm.ts/tree/release-2.x.x/packages/bellman-ford#readme">@algorithm.ts/bellman-ford</a>
+    <a href="https://github.com/guanghechen/algorithm.ts/tree/release-3.x.x/packages/bellman-ford#readme">@algorithm.ts/bellman-ford</a>
   </h1>
@@ -80,2 +80,3 @@ <div align="center">
 
+
 ## Usage
@@ -89,3 +90,3 @@
 
-  const graph: IGraph = {
+  const graph: IBellmanFordGraph<number> = {
     N: 4,
@@ -101,12 +102,19 @@ source: 0,
   }
-  const dist: number[] = []
-  bellmanFord(graph, { dist }) // => true, which means there is no negative-cycle.
-  dist
-  // => [0, 2, 4, 4]
-  // 
-  //    Which means:
-  //      0 --> 0: cost is 0
-  //      0 --> 1: cost is 2
-  //      0 --> 2: cost is 4
-  //      0 --> 3: cost is 4
+
+  const result = bellmanFord(graph)
+  /**
+   * {
+   *   hasNegativeCycle: false, // there is no negative-cycle.
+   *   INF: 4503599627370494,
+   *   source: 0,
+   *   bestFrom: ,
+   *   dist: [0, 2, 4, 4] 
+   * }
+   * 
+   * For dist:
+   *    0 --> 0: cost is 0
+   *    0 --> 1: cost is 2
+   *    0 --> 2: cost is 4
+   *    0 --> 3: cost is 4
+   */
   ```
@@ -116,9 +124,5 @@
 
-  Name        | Type        | Required  | Description
-  :----------:|:-----------:|:---------:|:----------------
-  `INF`       | `number`    | `false`   | A big number, representing the unreachable cost.
-  `from`      | `number[]`  | `false`   | Record the shortest path parent source point to the specified point.
-  `dist`      | `number[]`  | `false`   | An array recording the shortest distance to the source point.
-  `inq`       | `boolean`   | `false`   | Used to check if an element is already in the queue.
-  `inqTimes`  | `number[]`  | `false`   | Record the number of times an element is enqueued, used to check whether there is a negative cycle.
+  Name        | Type            | Required  | Description
+  :----------:|:---------------:|:---------:|:----------------
+  `INF`       | `number|bigint` | `false`   | A big number, representing the unreachable cost.
 
@@ -132,2 +136,3 @@
   import bellmanFord from '@algorithm.ts/bellman-ford'
+  import { getShortestPath } from '@algorithm.ts/graph'
 
@@ -154,13 +159,9 @@ const A = 0
 
-  const noNegativeCycle: boolean = bellmanFord(graph, undefined, context => {
-    const a2aPath: number[] = context.getShortestPathTo(A)
-    const a2bPath: number[] = context.getShortestPathTo(B)
-    const a2cPath: number[] = context.getShortestPathTo(C)
-    const a2dPath: number[] = context.getShortestPathTo(D)
+  const result = _bellmanFord.bellmanFord(graph)
+  assert(result.negativeCycle === false)
 
-    a2aPath // => [0]
-    a2bPath // => [0, 1]
-    a2cPath // => [0, 1, 2]
-    a2dPath // => [0, 1, 2, 3]
-  })
+  getShortestPath(result.bestFrom, Nodes.A, Nodes.A) // [Nodes.A]
+  getShortestPath(result.bestFrom, Nodes.A, Nodes.B) // [Nodes.A, Nodes.B]
+  getShortestPath(result.bestFrom, Nodes.A, Nodes.C) // [Nodes.A, Nodes.B, Nodes.C]
+  getShortestPath(result.bestFrom, Nodes.A, Nodes.D) // [Nodes.A, Nodes.B, Nodes.C, Nodes.D])
   ```
@@ -172,8 +173,8 @@
   ```typescript
-  import type { IEdge, IGraph } from '@algorithm.ts/bellman-ford'
-  import bellmanFord from '@algorithm.ts/bellman-ford'
+  import type { IBellmanFordEdge, IBellmanFordGraph } from '@algorithm.ts/bellman-ford'
+  import { bellmanFord } from '@algorithm.ts/bellman-ford'
 
   const MOD = 1e9 + 7
   export function countPaths(N: number, roads: number[][]): number {
-    const edges: IEdge[] = []
+    const edges: Array<IBellmanFordEdge<number>> = []
     const G: number[][] = new Array(N)
@@ -191,6 +192,7 @@ for (let i = 0; i < N; ++i) G[i] = []
     const target = N - 1
-    const graph: IGraph = { N, source: target, edges, G }
-    const dist: number[] = customDist ?? []
-    bellmanFord.bellmanFord(graph, { INF: 1e12, dist })
+    const graph: IBellmanFordGraph<number> = { N, source: target, edges, G }
+    const result = bellmanFord(graph, { INF: 1e12 })
+    if (result.hasNegativeCycle) return -1
 
+    const { dist } = result
     const dp: number[] = new Array(N).fill(-1)
@@ -208,3 +210,3 @@ return dfs(source)
       for (const idx of G[o]) {
-        const e: IEdge = edges[idx]
+        const e: IBellmanFordEdge<number> = edges[idx]
         if (dist[e.to] + e.cost === d) {
@@ -230,7 +232,7 @@ const t = dfs(e.to)
 * [bellman-ford | Wikipedia][wikipedia-bellman-ford]
-* [@algorithm.ts/circular-queue][]
+* [@algorithm.ts/queue][]
 
 
-[homepage]: https://github.com/guanghechen/algorithm.ts/tree/release-2.x.x/packages/bellman-ford#readme
+[homepage]: https://github.com/guanghechen/algorithm.ts/tree/release-3.x.x/packages/bellman-ford#readme
 [wikipedia-bellman-ford]: https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
-[@algorithm.ts/circular-queue]: https://github.com/guanghechen/algorithm.ts/tree/release-2.x.x/packages/circular-queue
+[@algorithm.ts/queue]: https://github.com/guanghechen/algorithm.ts/tree/release-3.x.x/packages/queue

New alerts

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

Found 1 instance in 1 package

No v1

Quality

Package is not semver >=1. This means it is not stable and does not support ^ ranges.

Found 1 instance in 1 package

Fixed alerts

No website

Quality

Package does not have a website.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

16818

increased by0.13%

Lines of code

236

increased by8.76%

Number of lines in readme file

229

increased by1.33%

Worsened metrics

Dependency count

3

increased by50%

Number of medium supply chain risk alerts

1

increased byInfinity%

Dependency changes

• + [e-mail]/constant@^3.0.0-alpha.0

• + [e-mail]/queue@^3.0.0-alpha.0

• + [e-mail]/types@^3.0.0-alpha.0

• + [e-mail]/constant@3.0.2(transitive)

• + [e-mail]/queue@3.1.1(transitive)

• + [e-mail]/types@3.1.1(transitive)

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

• - [e-mail]/graph@^2.0.14

• - [e-mail]/circular-queue@2.0.14(transitive)

• - [e-mail]/graph@2.0.14(transitive)