connectivity

package
v0.0.0-...-20eb531 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Dec 8, 2015 License: BSD-2-Clause Imports: 2 Imported by: 0

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

func (p *PercolationSimulator) Clear()

clear all states

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

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL