Disjoint

Disjoint package is a implementation of a UnionFind (Disjoint-set). Each element in the Disjoint-set is part of exactly one (non-overlapping) set.

The DSet supports two methods

• Find: Which returns which subset the element is a part of.
• Union: Which joins two subset sets together into a single subset.

API

Create new DSet

A new DSet is created using the NewDSet function, passing the elements to populate the set.

NewDSet returns a error if the elements set contains duplicates.

import "disjoint"

dset, err := disjoint.NewDSet([]interface{}{1, 2, 3, 4})

Add a new element Adds a new element to the the set.

import "disjoint"

dset, err := disjoint.NewDSet([]interface{}{1, 2, 3, 4})
dset.Add(5)

Find partition for element Returns the identifier the passed in element is part of.

import (
    "disjoint"
)

dset, err := disjoint.NewDSet([]interface{}{1, 2, 3, 4})
p1, ok  := dset.FindPartition(1)
p2, ok := dset.FindPartition(2)

Merge two sets Merges the sets the two elements are part of.

import (
    "disjoint"
)

dset, err := disjoint.NewDSet([]interface{}{1, 2, 3, 4})
p1, ok  := dset.Merge(1,2)

Check if disjoint Checks if two elements are part of the same set or not.

import (
    "disjoint"
)

dset, err := disjoint.NewDSet([]interface{}{1, 2, 3, 4})
p1, ok  := dset.AreDisjoint(1,2)

Tests

The tests can be invoked with go test

License

MIT © Oliver Daff