djs

README

Disjoint-set data structure

Disjoint-set for GO. In computing, a disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (nonoverlapping) subsets. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:

1. Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.
2. Union: Join two subsets into a single subset.

Documentation

Overview

A disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (nonoverlapping) subsets.

A union-find algorithm is an algorithm that performs two useful operations on such a data structure:

Find  - determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.
Union - join two subsets into a single subset.

Index

• func Connected(u Interface, a, b interface{}) bool
• func Find(u Interface, a interface{}) interface{}
• func Init(u InitInterface)
• func NewRankUnion(size int) *rankUnion
• func Union(u Interface, a, b interface{})
• type InitInterface
• type Interface
• type RankInterface
• type UnionInt
  • func (m UnionInt) Each(fn func(a interface{}))
  • func (m UnionInt) GetParent(c interface{}) interface{}
  • func (m UnionInt) SetParent(c, p interface{})

Examples

• Init
• NewRankUnion

Functions

func Connected

func Connected(u Interface, a, b interface{}) bool

Connected is a convenient method that compares result of Find for both elements.

func Find

func Find(u Interface, a interface{}) interface{}

Find determines which subset a particular element is in. This can be used for determining if two elements are in the same subset.

func Init

func Init(u InitInterface)

Init sets all elements parent to itself (i.e. 1->1, 2->2, 3->3, ...) via SetParent(...) to achieve proper initial state

Example

package main

import (
	"fmt"
	"github.com/igm/djs"
)

func main() {
	var data djs.UnionInt = make([]int, 20)

	djs.Init(data)
	djs.Union(data, 10, 11)
	djs.Union(data, 1, 2)

	fmt.Println(djs.Connected(data, 10, 11))
	fmt.Println(data)
}

Output:
true
[0 2 2 3 4 5 6 7 8 9 11 11 12 13 14 15 16 17 18 19]

func NewRankUnion

func NewRankUnion(size int) *rankUnion

NewRankUnion creates a convenient structure of specified size containing elements of type int. The structure also supports ranking.

Example

package main

import (
	"fmt"
	"github.com/igm/djs"
)

func main() {
	// create structure with nodes adresses from 0 to 9 (10 in length)
	uf := djs.NewRankUnion(10)
	// join 1 and 2
	djs.Union(uf, 1, 2)
	// join 3 and 4
	djs.Union(uf, 3, 4)
	fmt.Println(djs.Find(uf, 2))
	fmt.Println(djs.Find(uf, 1))
}

Output:
1
1

func Union

func Union(u Interface, a, b interface{})

Union joins two subsets into a single subset.

Types

type InitInterface

type InitInterface interface {
	Interface
	Each(func(a interface{}))
}

InitInterface enables iteration to perform initial state setup

type Interface

type Interface interface {
	// Sets parent p to element c
	SetParent(c, p interface{})
	// Returns back a parent of element
	GetParent(c interface{}) interface{}
}

Interface is the minimum contract any structure needs to conform in order to be used as underlaying data structure for union-find algorithm. Path compression is the only improvement applied in this case.

type RankInterface

type RankInterface interface {
	Interface
	GetRank(a interface{}) int
	SetRank(a interface{}, rank int)
}

RankInterface with more methods to enable "union by rank".

type UnionInt

type UnionInt []int

UnionInt attaches the methods of Interface to []int

func (UnionInt) Each

func (m UnionInt) Each(fn func(a interface{}))

func (UnionInt) GetParent

func (m UnionInt) GetParent(c interface{}) interface{}

func (UnionInt) SetParent

func (m UnionInt) SetParent(c, p interface{})