Documentation
¶
Overview ¶
Package ds provides small generic data-structure primitives that support gograph's algorithms but do not themselves model a graph.
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type UnionFind ¶
type UnionFind[T comparable] struct { // contains filtered or unexported fields }
UnionFind is a disjoint-set (union-find) data structure with path compression and union by rank. Both operations run in O(alpha(n)) amortised time — effectively constant for any practical input size.
UnionFind is generic over a comparable element type T. Elements are added implicitly on first reference; the structure grows as needed.
UnionFind is not safe for concurrent use; callers that need concurrent access must guard it externally.
Example ¶
ExampleUnionFind shows the disjoint-set workflow: elements start in their own singleton sets, Union merges the sets containing two elements, and Connected reports whether two elements share a set.
package main
import (
"fmt"
"github.com/FlavioCFOliveira/GoGraph/ds"
)
func main() {
uf := ds.New[string]()
// Elements are added implicitly on first reference; MakeSet is an
// explicit way to introduce one as its own singleton set.
uf.MakeSet("alice")
// Merge the sets of the given elements.
uf.Union("alice", "bob")
uf.Union("carol", "dave")
fmt.Println("alice~bob:", uf.Connected("alice", "bob"))
fmt.Println("alice~carol:", uf.Connected("alice", "carol"))
fmt.Println("elements:", uf.Len())
}
Output: alice~bob: true alice~carol: false elements: 4
func (*UnionFind[T]) Connected ¶
Connected reports whether a and b are in the same set. Elements not yet known are treated as singletons.
func (*UnionFind[T]) Find ¶
func (u *UnionFind[T]) Find(x T) T
Find returns the representative of the set containing x, adding x as its own singleton set if it is not already known. The lookup path is compressed so subsequent Find calls run in near-constant time.
Example ¶
ExampleUnionFind_Find shows that Find returns each set's canonical representative: two elements are in the same set exactly when their Find results are equal.
package main
import (
"fmt"
"github.com/FlavioCFOliveira/GoGraph/ds"
)
func main() {
uf := ds.New[int]()
uf.Union(1, 2)
uf.Union(2, 3)
// 1, 2 and 3 are now one set, so they share a representative.
sameRep := uf.Find(1) == uf.Find(3)
fmt.Println("1 and 3 share a representative:", sameRep)
}
Output: 1 and 3 share a representative: true
func (*UnionFind[T]) MakeSet ¶
func (u *UnionFind[T]) MakeSet(x T)
MakeSet records x as a singleton set if it is not already known. It is idempotent.
func (*UnionFind[T]) Reset ¶
func (u *UnionFind[T]) Reset()
Reset returns the structure to its empty state, retaining the backing maps so callers that pool *UnionFind across many short queries (kruskal MST, connected-components, Tarjan SCC under a soak load) can avoid the per-call map allocation. The two maps are cleared with Go 1.21's builtin clear() which preserves the underlying bucket array — subsequent inserts reuse capacity.
After Reset, the UnionFind behaves identically to a freshly constructed instance via New.
Example ¶
ExampleUnionFind_Reset clears every set, returning the structure to the empty state so it can be reused without a fresh allocation.
package main
import (
"fmt"
"github.com/FlavioCFOliveira/GoGraph/ds"
)
func main() {
uf := ds.New[int]()
uf.Union(1, 2)
uf.Reset()
fmt.Println("elements after reset:", uf.Len())
fmt.Println("1~2 after reset:", uf.Connected(1, 2))
}
Output: elements after reset: 0 1~2 after reset: false
type UnionFindSlice ¶
type UnionFindSlice struct {
// contains filtered or unexported fields
}
UnionFindSlice is a slice-backed disjoint-set structure for a bounded integer ID space [0, n). It offers the same amortised O(alpha(n)) Find/Union complexity as UnionFind but trades the generic map storage for two contiguous slices, gaining ~5-10x faster operations on typical Kruskal-MST workloads where the element set is densely packed in a known range.
UnionFindSlice is not safe for concurrent use; callers that need concurrent access must guard it externally.
func NewSlice ¶
func NewSlice(n int) *UnionFindSlice
NewSlice returns a UnionFindSlice covering elements [0, n). Each element starts in its own singleton set.
func (*UnionFindSlice) Connected ¶
func (u *UnionFindSlice) Connected(a, b int) bool
Connected reports whether a and b are in the same set.
func (*UnionFindSlice) Find ¶
func (u *UnionFindSlice) Find(x int) int
Find returns the representative of the set containing x with two-pass path compression. x must be in [0, len(parent)).
func (*UnionFindSlice) Len ¶
func (u *UnionFindSlice) Len() int
Len returns the size of the universe (n at construction time).
func (*UnionFindSlice) Reset ¶
func (u *UnionFindSlice) Reset()
Reset returns every element of u to its own singleton set, preserving the slice capacity for callers that pool *UnionFindSlice across many short queries. The new universe size stays at len(parent); use NewSlice when the universe size must change. Rank is zeroed via a single clear() call.
func (*UnionFindSlice) Union ¶
func (u *UnionFindSlice) Union(a, b int) bool
Union merges the sets containing a and b. Returns true when the two were in distinct sets (i.e., a merge actually occurred).
Source Files