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.
The parent slice is widened to the platform int (64-bit on every 64-bit target) so the element-ID domain matches the int domain of the graph NodeID / MaxNodeID callers feed into NewSlice (search.WCC, search.KruskalMST). An earlier int32 backing silently truncated element IDs once the universe exceeded math.MaxInt32, wrapping high IDs to negative slice indices and corrupting set membership (rmp #1476); the int backing removes that ceiling entirely. Correctness is preferred over the ~2x density int32 would save, and only on universes already near the 2^31 boundary.
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.
n is the universe size in the platform int domain; the parent slice is indexed by int throughout, so any n that a Go slice can hold is supported without truncation. Passing a negative n panics in make, matching every other slice constructor in the standard library.
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