dsu

README

dsu

Disjoint Set Union (Union Find) performance focused 🔥 implementation in Golang.

func ExampleDsu() {
    d := dsu.NewDsu(3)
    d.Union(0, 1)

    if d.Find(0) == d.Find(1) {
        fmt.Println("0 and 1 are in the same set")
    }

    if d.Find(1) != d.Find(2) {
        fmt.Println("1 and 2 are in different sets")
    }

    if d.Size(0) == 2 {
        fmt.Println("Set with the element 0 has 2 elements")
    }

    // Output:
    // 0 and 1 are in the same set
    // 1 and 2 are in different sets
    // Set with the element 0 has 2 elements
}

My benchmarks show a <50ns/op performance for random (non-empty) union operations.

$ go test -bench .
goos: darwin
goarch: arm64
pkg: alon.kr/x/dsu
cpu: Apple M2 Pro
BenchmarkRandomUnions-10        44521050                48.64 ns/op
PASS
ok      alon.kr/x/dsu   6.390s

Documentation

Index

• type Dsu
  • func NewDsu(n uint) Dsu
  • func (d *Dsu) Find(v uint) uint
  • func (d *Dsu) Size(v uint) uint
  • func (d *Dsu) Union(v1, v2 uint)

Examples

• Dsu

Types

type Dsu

type Dsu struct {
	// contains filtered or unexported fields
}

Example

package main

import (
	"fmt"

	"alon.kr/x/dsu"
)

func main() {
	d := dsu.NewDsu(3)
	d.Union(0, 1)

	if d.Find(0) == d.Find(1) {
		fmt.Println("0 and 1 are in the same set")
	}

	if d.Find(1) != d.Find(2) {
		fmt.Println("1 and 2 are in different sets")
	}

	if d.Size(0) == 2 {
		fmt.Println("Set with the element 0 has 2 elements")
	}

}

Output:

0 and 1 are in the same set
1 and 2 are in different sets
Set with the element 0 has 2 elements

func NewDsu

func NewDsu(n uint) Dsu

Create a new Disjoint Set Union data structure with n elements. The elements are referred to by their index in the range [0, n). The element values are not stored explicitly in the data structure, and the user of the data structure is responsible for maintaining a correspondence between the element values and their indices.

func (*Dsu) Find

func (d *Dsu) Find(v uint) uint

func (*Dsu) Size

func (d *Dsu) Size(v uint) uint

func (*Dsu) Union

func (d *Dsu) Union(v1, v2 uint)