Documentation
¶
Overview ¶
Package sparse provides a generic, map-backed implementation of the Disjoint Set Union (DSU) data structure.
The sparse DSU supports any user-defined type that is comparable, grows dynamically with no fixed capacity, and assigns new elements on demand through Find and Union operations. This makes it ideal for graph algorithms or workloads where element identifiers are not known ahead of time or cannot be restricted to integer ranges.
Example (Point) ¶
Example_point shows constructing a DSU with user-defined struct keys.
type Point struct {
X int
Y int
}
dsu := New[Point]()
a := Point{1, 1}
b := Point{1, 2}
dsu.Union(a, b)
Example (String) ¶
Example demonstrates basic usage of the sparse DSU with strings.
dsu := New[string]()
dsu.Union("apple", "banana")
dsu.Union("banana", "cherry")
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type DSU ¶
type DSU[T comparable] struct { // contains filtered or unexported fields }
DSU is a sparse, map-backed generic implementation of a Disjoint-Set Union.
It does NOT require a fixed capacity or pre-registration of elements. Elements are added lazily when first seen by Find/Union.
func New ¶
func New[T comparable](elems ...T) *DSU[T]
New creates a new DSU initialized with the given elements. Additional elements may still be added later via Find/Union.
Example (Pointempty) ¶
ExampleNewpoint_empty shows constructing an empty sparse DSU of user-defined struct keys.
type Point struct {
X int
Y int
}
_ = New[Point]()
Example (Pointinitialized) ¶
ExampleNew_pointinitialized shows constructing a sparse DSU of user-defined struct keys initialized with a few objects.
type Point struct {
X int
Y int
}
a := Point{1, 1}
b := Point{1, 2}
c := Point{2, 3}
_ = New(a, b, c)
func (*DSU[T]) Connected ¶
Connected reports whether x and y are in the same set. If x or y did not already exist, then singleton sets are created for them.
Example ¶
ExampleDSU_Connected illustrates checking connectedness between members.
dsu := New[int]() var result int var connected bool result = dsu.Find(10) // new element (10) auto-created fmt.Println(result) // expected 10 connected = dsu.Connected(10, 20) // element 20 auto created fmt.Println(connected) // expected false result = dsu.Find(20) fmt.Println(result) // expected 20 _ = dsu.Union(20, 10) connected = dsu.Connected(10, 20) fmt.Println(connected) // expected true
Output: 10 false 20 true
func (*DSU[T]) Find ¶
func (dsu *DSU[T]) Find(x T) T
Find returns the representative element (root) of the set containing x. If x is not present, it is added as a singleton set.
Example ¶
ExampleDSU_Find illustrates that Find grows the structure dynamically, and returns the root after unions.
dsu := New[int]() var result int result = dsu.Find(33) // new element auto-created fmt.Println(result) result = dsu.Find(99) fmt.Println(result) _ = dsu.Union(33, 99) result = dsu.Find(99) fmt.Println(result)
Output: 33 99 33
func (*DSU[T]) Groups ¶
func (dsu *DSU[T]) Groups() map[T][]T
Groups returns a map from root -> slice of elements in that set.
Example ¶
ExampleDSU_Groups illustrates retrieving the connected elements as groups.
dsu := New("mozart", "bach", "gauss", "euler")
dsu.Union("mozart", "bach")
dsu.Union("beethoven", "bach")
dsu.Union("mozart", "barman")
dsu.Union("fermat", "ramanujan")
dsu.Union("gauss", "euler")
dsu.Union("gauss", "fermat")
dsu.Union("gallileo", "newton")
dsu.Union("newton", "einstein")
dsu.Union("einstein", "bose")
groups := dsu.Groups()
for _, elements := range groups {
// Elements in a line needs a predictable order for testing
sort.Strings(elements)
separator := ""
for _, element := range elements {
fmt.Printf("%s%s", separator, element)
separator = ","
}
fmt.Printf("\n")
}
Output: bach,barman,beethoven,mozart euler,fermat,gauss,ramanujan bose,einstein,gallileo,newton
func (*DSU[T]) Union ¶
Union merges the sets containing x and y. Returns true if the sets were separate and are now merged.
Example ¶
ExampleDSU_Union illustrates connecting (union) components, and the return value capturing whether merge was actually necessary or not.
dsu := New[int]() var result int var merged bool result = dsu.Find(10) // new element auto-created fmt.Println(result) // expected 10 result = dsu.Find(20) fmt.Println(result) // expected 20 merged = dsu.Union(10, 20) fmt.Println(merged) // merge necessary, expected true merged = dsu.Union(20, 35) fmt.Println(merged) // merge necessary, expected true merged = dsu.Union(10, 35) fmt.Println(merged) // merge not necessary (due to above), expected false
Output: 10 20 true true false
Source Files