Options
All
  • Public
  • Public/Protected
  • All
Menu

Module "mst"

Index

Functions

Functions

Const mst

  • mst<T>(edges: T[], maxID: number, cost: Fn<T, number>, verts: Fn<T, [number, number]>): T[]
  • Computes the Minimum Spanning Tree from given weighted edges, using Kruskal's algorithm.

    remarks

    Edges can be of any type, but requires unsigned integer vertex IDs. The latter can be extracted via the user supplied verts function. The edge weights are extracted via the cost function.

    The maxID arg should equal or greater than the largest vertex ID referenced by the given edges.

    The function returns a new array of the original edges, satisfying the MST criteria. The result edges will be in ascending order, based on the supplied cost function.

    https://en.wikipedia.org/wiki/Kruskal%27s_algorithm

    example
    // 2D vectors
    verts = [[0,0], [0,1], [1,1], [1,2], [4,2]]
    
    // connections (vertex ID pairs)
    edges = [[0,1], [0,4], [1,2], [1,3], [2,3], [2,4]]
    
    mst(
      edges,
      // max vertex ID
      4,
      // cost function (cartesian distance, from @thi.ng/vectors pkg)
      ([a,b]) => distSq(verts[a], verts[b]),
      // edge vertex IDs
      (e) => e
    )
    
    // [ [ 0, 1 ], [ 1, 2 ], [ 2, 3 ], [ 2, 4 ] ]

    Type parameters

    • T

    Parameters

    • edges: T[]

      edge pairs

    • maxID: number

      max vertex ID (+1)

    • cost: Fn<T, number>

      cost function

    • verts: Fn<T, [number, number]>

      vertices / graph nodes

    Returns T[]

Generated using TypeDoc