@algorithm.ts/graph - npm Package Compare versions

Comparing version 2.0.14 to 3.0.0-alpha.0

lib/cjs/index.js

@@ -5,2 +5,21 @@ 'use strict';
 
+const extractAdjacencyList = (graph) => {
+    const { N, G, edges } = graph;
+    const adjList = new Array(N);
+    for (let o = 0; o < N; ++o) {
+        const adj = [];
+        for (const i of G[o])
+            adj.push(edges[i].to);
+        adjList[o] = adj;
+    }
+    return adjList;
+};
+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();
+};
 const buildEdgeMap = (N, edges) => {
@@ -16,12 +35,5 @@ const G = new Array(N);
 };
-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.extractAdjacencyList = extractAdjacencyList;
 exports.getShortestPath = getShortestPath;

lib/esm/index.js

@@ -0,1 +1,20 @@
+const extractAdjacencyList = (graph) => {
+    const { N, G, edges } = graph;
+    const adjList = new Array(N);
+    for (let o = 0; o < N; ++o) {
+        const adj = [];
+        for (const i of G[o])
+            adj.push(edges[i].to);
+        adjList[o] = adj;
+    }
+    return adjList;
+};
+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();
+};
 const buildEdgeMap = (N, edges) => {
@@ -11,11 +30,3 @@ const G = new Array(N);
 };
-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, getShortestPath };
+export { buildEdgeMap, extractAdjacencyList, getShortestPath };

lib/types/index.d.ts

@@ -1,38 +0,11 @@
-interface IEdge {
-    /**
-     * The other end of the edge.
-     */
-    to: number;
-    /**
-     * The cost of walking along this side.
-     */
-    cost: number;
-}
-interface IGraph<E extends IEdge = IEdge> {
-    /**
-     * The number of nodes in the graph. (0-index)
-     */
-    N: number;
-    /**
-     * Graph edges.
-     */
-    edges: ReadonlyArray<E>;
-    /**
-     * Adjacency list. G[i] represent the index list of the edges start from node i.
-     */
-    G: ReadonlyArray<ReadonlyArray<number>>;
-}
+import { DeepReadonly, IDigraph } from '@algorithm.ts/types';
 
 /**
- *
- * @param N     the number of nodes in the graph.
- * @param edges edges in the graph.
- * @returns An adjacency list. G[i] represent the index list of the edges start from node i.
+ * ExtractAdjacencyList from graph.
+ * @param graph
+ * @returns
  */
-declare const buildEdgeMap: (N: number, edges: Array<{
-    from: number;
-}>) => number[][];
+declare const extractAdjacencyList: (graph: DeepReadonly<IDigraph>) => number[][];
 /**
  * List all points on the shortest path from source to target in order.
- *
  * @param bestFrom
@@ -44,3 +17,12 @@ * @param source
 declare const getShortestPath: (bestFrom: ReadonlyArray<number>, source: number, target: number) => number[];
+/**
+ *
+ * @param N     the number of nodes in the graph.
+ * @param edges edges in the graph.
+ * @returns An adjacency list. G[i] represent the index list of the edges start from node i.
+ */
+declare const buildEdgeMap: (N: number, edges: ReadonlyArray<{
+    from: number;
+}>) => number[][];
 
-export { IEdge, IGraph, buildEdgeMap, getShortestPath };
+export { buildEdgeMap, extractAdjacencyList, getShortestPath };

package.json

 {
   "name": "@algorithm.ts/graph",
-  "version": "2.0.14",
+  "version": "3.0.0-alpha.0",
   "description": "Types and utils from solving graph problems.",
@@ -11,9 +11,9 @@ "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/graph"
   },
-  "homepage": "https://github.com/guanghechen/algorithm.ts/tree/release-2.x.x/packages/graph#readme",
+  "homepage": "https://github.com/guanghechen/algorithm.ts/tree/release-3.x.x/packages/graph#readme",
   "keywords": [
     "algorithm",
-    "graph"
+    "graph algorithm utils"
   ],
@@ -44,5 +44,5 @@ "main": "lib/cjs/index.js",
   "dependencies": {
-    "@algorithm.ts/circular-queue": "^2.0.14"
+    "@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/graph#readme">@algorithm.ts/graph</a>
+    <a href="https://github.com/guanghechen/algorithm.ts/tree/release-3.x.x/packages/graph#readme">@algorithm.ts/graph</a>
   </h1>
@@ -69,9 +69,3 @@ <div align="center">
 
-* deno
 
-  ```typescript
-  import type { IEdge, IGraph } from 'https://raw.githubusercontent.com/guanghechen/algorithm.ts/main/packages/graph/src/index.ts'
-  import { buildEdgeMap } from 'https://raw.githubusercontent.com/guanghechen/algorithm.ts/main/packages/graph/src/index.ts'
-  ```
-
 ## Usage
@@ -83,3 +77,9 @@
   import { buildEdgeMap } from '@algorithm.ts/graph'
+  import type { IDigraph, IDigraphEdge } from '@algorithm.ts/types'
 
+  interface IEdge extends IDigraphEdge {
+    from: number
+    cost: number
+  }
+
   const Nodes = {
@@ -92,3 +92,3 @@ A: 0,
   const N: number = Object.keys(Nodes).length
-  const edges: Array<IEdge & { from: number }> = [
+  const edges: IEdge[] = [
     { from: Nodes.A, to: Nodes.B, cost: 1 }, // A-B (1)
@@ -101,6 +101,4 @@ { from: Nodes.B, to: Nodes.A, cost: -1 }, // B-A (-1)
   ]
-
   const G: number[][] = buildEdgeMap(N, edges)
-
-  const graph: IGraph = { N, edges, G }
+  const graph: IDigraph<IEdge> = { N, G, edges }
   ```
@@ -126,8 +124,6 @@
 * [@algorithm.ts/dijkstra][]
-* [@algorithm.ts/dijkstra-bigint][]
 
 
-[homepage]: https://github.com/guanghechen/algorithm.ts/tree/release-2.x.x/packages/graph#readme
-[@algorithm.ts/bellman-ford]: https://github.com/guanghechen/algorithm.ts/tree/release-2.x.x/packages/bellman-ford
-[@algorithm.ts/dijkstra]: https://github.com/guanghechen/algorithm.ts/tree/release-2.x.x/packages/dijkstra
-[@algorithm.ts/dijkstra-bigint]: https://github.com/guanghechen/algorithm.ts/tree/release-2.x.x/packages/dijkstra-bigint
+[homepage]: https://github.com/guanghechen/algorithm.ts/tree/release-3.x.x/packages/graph#readme
+[@algorithm.ts/bellman-ford]: https://github.com/guanghechen/algorithm.ts/tree/release-3.x.x/packages/bellman-ford
+[@algorithm.ts/dijkstra]: https://github.com/guanghechen/algorithm.ts/tree/release-3.x.x/packages/dijkstra

New alerts

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

Improved metrics

Total package byte prevSize

8400

increased by1.07%

Lines of code

89

increased by5.95%

Worsened metrics

Number of low quality alerts

1

increased byInfinity%

Number of lines in readme file

125

decreased by-2.34%

Dependency changes

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

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

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

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