Packages
inplace
0.7.11
0.7.12
0.7.11
0.7.10
0.7.9
0.7.8
0.7.7
0.7.6
0.7.5
0.7.4
0.7.3
0.7.2
0.7.1
0.7.0
0.6.8
0.6.7
0.6.6
0.6.5
0.6.4
0.6.3
0.6.2
0.6.1
0.6.0
0.5.4
0.5.3
0.5.2
0.5.1
0.5.0
0.4.4
0.4.3
0.4.2
0.4.1
0.4.0
0.3.3
0.3.2
0.3.1
0.3.0
0.2.3
0.2.2
0.2.1
0.2.0
0.1.9
0.1.8
0.1.7
0.1.6
0.1.5
0.1.4
0.1.3
0.1.2
0.1.1
0.1.0
Mutable data structures
Current section
Files
Jump to
Current section
Files
lib/adt/union_find.ex
defmodule InPlace.UnionFind do
@moduledoc """
Union-find (a.k.a. DSU)
https://en.wikipedia.org/wiki/Disjoint-set_data_structure
The (fixed-length) set is represented by the set of integer indices.
"""
alias InPlace.Array
def new(size) when is_integer(size) and size > 0 do
parent = Array.new(size)
Enum.each(1..size, fn idx -> Array.put(parent, idx, idx) end)
set_size = Array.new(size, 1)
%{
parent: parent,
set_size: set_size,
size: size
}
end
def find(%{parent: parent, size: size} = uf, v) when is_integer(v) and v <= size and v > 0 do
case Array.get(parent, v) do
p when p == v ->
p
p ->
find(uf, p)
|> tap(fn leader -> Array.put(parent, v, leader) end)
end
end
def union(%{parent: parent, set_size: set_size} = uf, a, b)
when is_integer(a) and is_integer(b) and a > 0 and b > 0 do
a = find(uf, a)
b = find(uf, b)
if a != b do
size_a = Array.get(set_size, a)
size_b = Array.get(set_size, b)
{a, b, size_a, size_b} =
if size_a < size_b do
{b, a, size_b, size_a}
else
{a, b, size_a, size_b}
end
Array.put(parent, b, a)
Array.put(set_size, a, size_a + size_b)
end
end
def set_size(%{parent: parent, set_size: set_size}, el) do
p = Array.get(parent, el)
Array.get(set_size, p)
end
end