@algorithm.ts/graph

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

Related

• @algorithm.ts/bellman-ford
• @algorithm.ts/dijkstra