@algorithm.ts/graph NPM

Types and utils from solving graph problems.

Install

npm
```
npm install --save @algorithm.ts/graph
```
yarn
```
yarn add @algorithm.ts/graph
```

Usage

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