Documentation
¶
Overview ¶
Dynamic Connectivity and its Union Find implementation are inspired by Algorithms Lecture Slide by ROBERT SEDGEWICK & KEVIN WAYNE.
The package implements compatible Union-Find API as illustrated in the lecture slides.
Package contains Weighted Quick-Union with Path Compression implementation and the Percolation API.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type PercolationSimulator ¶
type PercolationSimulator struct {
Size int
Marked []bool
// contains filtered or unexported fields
}
percolation simulator
func NewPercolationSimulator ¶
func NewPercolationSimulator(N int) *PercolationSimulator
ctor for percolation simulator eats a integer representing the side length of the square. e.g. N -> NxN sqaure the square is initially completely black or blocked.
func (*PercolationSimulator) Simulate ¶
func (p *PercolationSimulator) Simulate() int64
every call to the simulate will generate a random order of how the blocks will be marked, and they will be marked according to that order utill we found the percolation returns the steps taken to find the percolation
type Simulator ¶
type Simulator interface {
// run simulation til a percolation is found
// return the used steps to produce a percolation
Simulate() int64
// clear states of the last simulation, init all values.
// size of the grid and side length stay the same
Clear()
// contains filtered or unexported methods
}
monte carlo simulator for percolation once initiated, the simulator fills up blocks randomly and check for percolation on each step. the simulation stops when a percolation is found and the simulation will return the used steps that produced the percolation
type UnionFind ¶
type UnionFind interface {
// Find also known as connected -> bool in literature, check if the 2 notes
// are in the same component
Find(a, b int) bool
// Union connect the 2 notes, make them belong to the same component
Union(a, b int)
}
UnionFind interface defines 2 public operations for the algorithm
type WeightedCompressed ¶
type WeightedCompressed struct {
// contains filtered or unexported fields
}
WeightedCompressed holds a parent array to track parent of each note, and a size array for weights in terms of number of notes in that component.
func NewWeightedCompression ¶
func NewWeightedCompression(n int) *WeightedCompressed
NewWeightedCompression initialize an empty WeightedCompressed struct
func (*WeightedCompressed) Find ¶
func (w *WeightedCompressed) Find(a, b int) bool
Find delivers the check by comparing roots
func (*WeightedCompressed) Union ¶
func (w *WeightedCompressed) Union(a, b int)
Union applies weighted union by balancing based on the size of components
Source Files