Options
All
  • Public
  • Public/Protected
  • All
Menu

Class DisjointSet

Typed array based Disjoint Set implementation with quick union and path compression, after Sedgewick & Wayne.

remarks

Hierarchy

  • DisjointSet

Index

Constructors

Properties

Methods

Constructors

constructor

Properties

count

count: number

ranks

ranks: Uint8Array

roots

roots: Uint32Array

Methods

canonical

  • canonical(id: number): number

  • Returns canonical ID (tree root) for given id. Unless id already is unified with some other ID, this will always return id itself (since each node is initially its own root).

    Parameters

    • id: number

      node ID

    Returns number

subsets

  • subsets(): Map<number, number[]>

  • Returns a Map of all subsets (connected components) with their canonical tree root IDs as keys and arrays of node IDs as values.

    remarks

    If only the number of subsets is required, use the count property of this class instance instead (O(1), updated with each call to DisjointSet.union).

    Returns Map<number, number[]>

unified

  • unified(a: number, b: number): boolean

  • Returns true, if the given two nodes belong to the same tree / subset.

    Parameters

    • a: number

      node ID

    • b: number

      node ID

    Returns boolean

union

  • union(a: number, b: number): number

  • Connects combines the trees of the given two node IDs and returns the new resulting canonical tree root ID.

    Parameters

    • a: number

      node ID

    • b: number

      node ID

    Returns number

Generated using TypeDoc