@algorithm.ts/graph

@algorithm.ts/graph

Types and utils from solving graph problems.

Install

• npm

  npm install --save @algorithm.ts/graph
  

• yarn

  yarn add @algorithm.ts/graph
  

• deno

  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

• buildEdgeMap

  import { buildEdgeMap } from '@algorithm.ts/graph'
  
  const Nodes = {
    A: 0,
    B: 1,
    C: 2,
    D: 3,
  }
  const N: number = Object.keys(Nodes).length
  const edges: Array<IEdge & { from: number }> = [
    { 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: IGraph = { N, edges, G }
  

• 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
• @algorithm.ts/dijkstra-bigint