disjoint

README

disjoint

Introduction

This fork introduces one new method to allow for re-using the same objects, in an attempt to allow an application using this data structure to reduce memory overhead. For details on the original package, such as how to install it, etc., we refer to the original package.

Author of original package

Scott Pakin, scott+disj@pakin.org

Documentation

Overview

Original package by Scott Pakin, available under https://github.com/spakin/disjoint. This fork introduces one new method to allow for re-using the same objects, in an attempt to allow an application using this data structure to reduce memory overhead

Original description below:

Package disjoint implements a disjoint-set data structure.

A disjoint-set—also called union-find—data structure keeps track of nonoverlapping partitions of a collection of data elements. Initially, each data element belongs to its own, singleton, set. The following operations can then be performed on these sets:

• Union merges two sets into a single set containing the union of their elements.

• Find returns an arbitrary element from a set.

The critical feature is that Find returns the same element when given any element in a set. The implication is that two elements A and B belong to the same set if and only if A.Find() == B.Find().

Both Union and Find take as arguments elements of sets, not the sets themselves. Because sets are mutually disjoint, an element uniquely identifies a set. Ergo, there is no need to pass sets to those functions.

Disjoint sets are more limited in functionality than conventional sets. They support only set union, not set intersection, set difference, or any other set operation. They don't allow an element to reside in more than one set. They don't even provide a way to enumerate the elements in a given set. What makes them useful, though, is that they're extremely fast, especially for large sets; both Union and Find run in amortized near-constant time. See http://en.wikipedia.org/wiki/Disjoint-set_data_structure for more information.

Disjoint sets are often used in graph algorithms, for example to find a minimal spanning tree for a graph or to determine if adding a given edge to a graph would create a cycle.

Example (Maze)

Draw a maze. This is my favorite use of disjoint-set forests. The algorithm works by repeatedly knocking down walls between two sets of rooms that are not part of the same union and merging those rooms into a single union. A union represents connected components—rooms in the maze that are mutually reachable. A single union implies that every room is reachable from every other room.

This is a fairly long example, but note that only half of it relates to generating the maze. The other half renders the maze using Unicode box-drawing characters.

package main

import (
	"fmt"
	"math/rand"

	"github.com/cem-okulmus/disjoint"
)

func main() {
	const width = 50  // Width of maze in rooms (must be > 1)
	const height = 10 // Height of maze in rooms (must be > 1)

	// A room is identified by its walls and by the other rooms it can reach.
	type Room struct {
		N       bool              // North side of room is a wall
		S       bool              // South side of room is a wall
		E       bool              // East side of room is a wall
		W       bool              // West side of room is a wall
		Reaches *disjoint.Element // Element in a set of reachable rooms
	}

	// Initialize the maze data structure.
	maze := make([][]Room, height)
	for y := range maze {
		maze[y] = make([]Room, width)
		for x := range maze[y] {
			// Start with all walls present and no other rooms reachable.
			maze[y][x].N = true
			maze[y][x].S = true
			maze[y][x].E = true
			maze[y][x].W = true
			maze[y][x].Reaches = disjoint.NewElement()
		}
	}

	// Repeatedly remove walls until a single connected component remains.
	rand.Seed(5552368)
	for cc := width * height; cc > 1; {
		// Because of symmetry, we need only connect to the right or
		// down rather than in all four directions.
		x0 := rand.Intn(width)
		y0 := rand.Intn(height)
		x1 := x0
		y1 := y0
		dir := rand.Intn(2)
		if dir == 0 && x0 < width-1 {
			x1++ // Go right.
		} else if dir == 1 && y0 < height-1 {
			y1++ // Go down.
		} else {
			continue // Can't go in the desired direction
		}
		if maze[y0][x0].Reaches.Find() == maze[y1][x1].Reaches.Find() {
			continue // Already connected
		}

		// Tear down the wall.
		if dir == 0 {
			// Right/left
			maze[y0][x0].E = false
			maze[y1][x1].W = false
		} else {
			// Down/up
			maze[y0][x0].S = false
			maze[y1][x1].N = false
		}
		disjoint.Union(maze[y0][x0].Reaches, maze[y1][x1].Reaches)
		cc--
	}

	// Punch holes for an entry (UL) and exit (LR).
	maze[0][0].W = false
	maze[height-1][width-1].E = false

	// Convert the grid of rooms to a grid of walls.  Walls are staggered
	// spatially by half a room vertically and horizontally.
	type Walls struct {
		N bool // Northbound wall from cell center
		S bool // Southbound wall from cell center
		E bool // Eastbound wall from cell center
		W bool // Westbound wall from cell center
	}
	walls := make([][]Walls, height+1)
	for y := range walls {
		walls[y] = make([]Walls, width+1)
	}
	for y := 0; y < height+1; y++ {
		for x := 0; x < width+1; x++ {
			if y < height {
				if x < width {
					walls[y][x].E = maze[y][x].N
					walls[y][x].S = maze[y][x].W
				}
				if x > 0 {
					walls[y][x].W = maze[y][x-1].N
					walls[y][x].S = maze[y][x-1].E
				}
			}
			if y > 0 {
				if x > 0 {
					walls[y][x].W = maze[y-1][x-1].S
					walls[y][x].N = maze[y-1][x-1].E
				}
				if x < width {
					walls[y][x].E = maze[y-1][x].S
					walls[y][x].N = maze[y-1][x].W
				}
			}
		}
	}

	// Define a map from wall types to Unicode box-drawing characters.
	wallsToGlyph := []rune{' ', '╴', '╶', '─', '╷', '┐', '┌', '┬', '╵', '┘', '└', '┴', '│', '┤', '├', '┼'}

	// Define a map from Booleans to integers.
	boolToInt := map[bool]int{false: 0, true: 1}

	// Output the glyph corresponding to each cell of walls.
	for _, row := range walls {
		for _, cell := range row {
			val := boolToInt[cell.N]<<3 | boolToInt[cell.S]<<2 | boolToInt[cell.E]<<1 | boolToInt[cell.W]
			fmt.Printf("%c", wallsToGlyph[val])
		}
		fmt.Println("")
	}

}

Output:

╶───┬─────┬┬──┬────┬────┬─┬──┬┬─┬───┬─┬─┬───┬───┬─┐
╷╷╶┐├┐┌┐╷╶┤│╶─┤╷╶┬─┘╶┐╷╷│╶┴─┐╵╵╶┴─╴╷│╷└╴├┬─╴│╷╶┬┴╴│
├┴╴├┤╵│└┘┌┘╵╶┬┼┘╶┴┬╴╷│├┤├─╴┌┴┐╶┐╶──┤└┤╶┬┘├╴┌┴┤╷└╴┌┤
├╴╷│└┬┼┐┌┤╷╶┬┘│╷╷╷╵╶┼┴┘╵├╴╶┼╴╵╷├─╴┌┘╶┤╷│┌┘╷│┌┤│╶┐╵│
│┌┘╵╶┤╵╵│││┌┴╴│││└┐╷├╴╷╶┴╴┌┼─╴│└┐╶┼─┐││╵├╴│╵╵└┘╶┼┬┤
├┼┬╴╷└─┐╵│├┘╷╶┴┴┤╷││├─┴╴┌┐│╵╶┬┴┐├─┤┌┘└┘╶┤┌┘╶┐┌─╴╵╵│
│╵│╶┴┐╷╵╷╵╵┌┴┐╶┐╵└┼┼┤┌┐╷│││╶─┼╴└┘┌┘├┬┐┌┐└┘╶┐├┘╶┬┐╶┤
├╴├┐┌┴┤╷├╴╶┴┐╵╶┤╷┌┘╵├┘╵├┤│╵╷┌┼┐┌┐├┐╵│└┤╵╷┌╴└┴┐╶┤│╷│
│╷╵╵│╶┘├┼╴┌─┴──┼┼┤╷╷├╴╶┘││╶┤╵│╵╵││╵╶┘╷│╷├┴┐╶┬┼╴│└┴┤
├┴╴┌┴╴╷│╵╷╵╷╷┌╴│╵╵│└┘╶┐╶┘│╶┴─┘╷╷├┴╴╷╶┤╵└┤╶┴╴╵└┐╵╶┐╵
└──┴──┴┴─┴─┴┴┴─┴──┴───┴──┴────┴┴┴──┴─┴──┴─────┴──┴╴

Index

• func Union(e1, e2 *Element)
• type Element
  • func NewElement() *Element
  • func (e *Element) Find() *Element
  • func (e *Element) Reset()

Examples

• Package (Maze)

Functions

func Union

func Union(e1, e2 *Element)

Union establishes the union of two sets when given an element from each set. Afterwards, the original sets no longer exist as separate entities.

Types

type Element

type Element struct {
	Data interface{} // Arbitrary user-provided payload
	// contains filtered or unexported fields
}

An Element represents a single element of a set.

Note that, perhaps surprisingly, the package does not expose a corresponding Set data type. Sets exist only implicitly based on the sequence of Union operations performed on their elements.

The Data field lets a program store arbitrary data within an Element. This can be used, for example, to keep track of the total number of elements in the associated set, the set's maximum-valued element, a map of attributes associated with the set's elements, or even a map or slice of all elements in the set. (That last possibility would associate a linear-time cost with each Union operation but would not affect Find's near-constant running time.)

func NewElement

func NewElement() *Element

NewElement creates a singleton set and returns its sole element.

func (*Element) Find

func (e *Element) Find() *Element

Find returns an arbitrary element of a set when invoked on any element of the set, The important feature is that it returns the same value when invoked on any element of the set. Consequently, it can be used to test if two elements belong to the same set.

func (*Element) Reset

func (e *Element) Reset()

Reset simply rests an element to its initial state, allowing for re-use of the same set of Elements. Needs to be manually called for all relevant Element objects.