Collections.DisjointSet (collections v0.2.0) View Source

Disjoint set implementation in Elixir

Examples

  iex> ds = DisjointSet.new()
  iex> {x, ds} = DisjointSet.find(ds, 10)
  iex> x
  10
  iex> ds = ds |> DisjointSet.union(10, 20) |> DisjointSet.union(20, 30)
  iex> x = DisjointSet.find(ds, 10) |> elem(0)
  iex> y = DisjointSet.find(ds, 30) |> elem(0)
  iex> x == y
  true

Link to this section Summary

The Find operation follows the chain of parent from a specified query node x until it reaches a root element. This root element represents the set to which x belongs and may be x itself. Find returns the root element it reaches.

new()

Create an empty disjoint set.

union(disjoint_set, x, y)

The Union replaces the set containing x and the set containing y with their union.

Link to this section Types

t()

Specs

t() :: %Collections.DisjointSet{
  rank: %{optional(any()) => integer()},
  root: map()
}

Link to this section Functions

find(disjoint_set, x)

Specs

find(t(), any()) :: {any(), t()}

Examples

iex> DisjointSet.new()
...>   |> DisjointSet.find(10)
...>   |> elem(0)
10

new()

Specs

new() :: t()

Create an empty disjoint set.

Examples

iex> DisjointSet.new()
%DisjointSet{root: Map.new([]), rank: Map.new([])}

union(disjoint_set, x, y)

Specs

union(t(), any(), any()) :: t()

The Union replaces the set containing x and the set containing y with their union.

Examples

iex> ds = DisjointSet.new() |> DisjointSet.union(20, 30)
iex> x = ds |> DisjointSet.find(20) |> elem(0)
iex> y = ds |> DisjointSet.find(30) |> elem(0)
iex> x == y
true
iex> x == 40
false