Types and utils from solving graph problems.
-
npm
npm install --save @algorithm.ts/graph
-
yarn
yarn add @algorithm.ts/graph
-
buildEdgeMap
import { buildEdgeMap } from '@algorithm.ts/graph' import type { IDigraph, IDigraphEdge } from '@algorithm.ts/graph.types' interface IEdge extends IDigraphEdge { from: number cost: number } const Nodes = { A: 0, B: 1, C: 2, D: 3, } const N: number = Object.keys(Nodes).length const edges: IEdge[] = [ { from: Nodes.A, to: Nodes.B, cost: 1 }, // A-B (1) { from: Nodes.B, to: Nodes.A, cost: -1 }, // B-A (-1) { from: Nodes.B, to: Nodes.C, cost: 0.87 }, // B-C (0.87) { from: Nodes.C, to: Nodes.B, cost: -0.87 }, // C-B (-0.87) { from: Nodes.C, to: Nodes.D, cost: 5 }, // C-D (5) { from: Nodes.D, to: Nodes.C, cost: -5 }, // D-C (-5) ] const G: number[][] = buildEdgeMap(N, edges) const graph: IDigraph<IEdge> = { N, G, edges }
-
getShortestPath
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