algo.go: github.com/nilbot/algo.go/connectivity Index | Files

package connectivity

import "github.com/nilbot/algo.go/connectivity"

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

Package Files

doc.go percolation.go unionfind.go

type PercolationSimulator Uses

type PercolationSimulator struct {
    Size   int
    Marked []bool
    // contains filtered or unexported fields
}

percolation simulator

func NewPercolationSimulator Uses

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) Clear Uses

func (p *PercolationSimulator) Clear()

clear all states

func (*PercolationSimulator) Simulate Uses

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 Uses

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 Uses

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 Uses

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 Uses

func NewWeightedCompression(n int) *WeightedCompressed

NewWeightedCompression initialize an empty WeightedCompressed struct

func (*WeightedCompressed) Find Uses

func (w *WeightedCompressed) Find(a, b int) bool

Find delivers the check by comparing roots

func (*WeightedCompressed) Union Uses

func (w *WeightedCompressed) Union(a, b int)

Union applies weighted union by balancing based on the size of components

Package connectivity imports 2 packages (graph). Updated 2016-07-30. Refresh now. Tools for package owners.