disjointset

Documentation

Overview

*

• Package disjointset implements a DisjointSet (Union-Find) datastructure
• and an alternative linked list based version.

Index

• type DisjointSet
  • func New(size int) *DisjointSet
  • func (set *DisjointSet) Components() int
  • func (set *DisjointSet) Connected(p, q int) bool
  • func (set *DisjointSet) Find(i int) int
  • func (set *DisjointSet) Size(p int) int
  • func (set *DisjointSet) TotalElements() int
  • func (set *DisjointSet) Union(p, q int) int
• type DisjointSetLL
  • func NewDisjointSetLL(size int) *DisjointSetLL
  • func (set *DisjointSetLL) Connected(a, b int) bool
  • func (set *DisjointSetLL) Elements(v int) chan int
  • func (set *DisjointSetLL) Find(v int) int
  • func (set *DisjointSetLL) Print()
  • func (set *DisjointSetLL) Size(v int) int
  • func (set *DisjointSetLL) TotalComponents() int
  • func (set *DisjointSetLL) TotalElements() int
  • func (set *DisjointSetLL) Union(a, b int)
• type DisjointSetLLNode
• type DisjointSetLLRegion
• type DisjointSetNode

Types

type DisjointSet

type DisjointSet struct {
	// contains filtered or unexported fields
}

*

• DisjointSet type, contains the elements (nodes) that
• the disjoint set has and the number of components that
• it's representing

func New

func New(size int) *DisjointSet

*

• Instantiates a new DisjointSet with 'size' elements

func (*DisjointSet) Components

func (set *DisjointSet) Components() int

*

• Returns the total number of components that the DisjointSet set has

func (*DisjointSet) Connected

func (set *DisjointSet) Connected(p, q int) bool

*

• Returns true if both nodes p and q belong to the same component

func (*DisjointSet) Find

func (set *DisjointSet) Find(i int) int

*

• Returns the id of the component to which the node i belongs

func (*DisjointSet) Size

func (set *DisjointSet) Size(p int) int

*

• Returns the size of the component to which the node p belongs

func (*DisjointSet) TotalElements

func (set *DisjointSet) TotalElements() int

*

• Returns the total number of elements that the DisjointSet set has

func (*DisjointSet) Union

func (set *DisjointSet) Union(p, q int) int

*

• Merges the two components to which p and q belong. It does nothing
• if they belong to the same component

type DisjointSetLL

type DisjointSetLL struct {
	// contains filtered or unexported fields
}

*

• DisjointSetLL datatype, it contains a list of all the regions and
• the number of components that it's storing

func NewDisjointSetLL

func NewDisjointSetLL(size int) *DisjointSetLL

*

• Instantiates a new DisjointSetLL with 'size' elements

func (*DisjointSetLL) Connected

func (set *DisjointSetLL) Connected(a, b int) bool

*

• Returns true if a and b belong to the same region

func (*DisjointSetLL) Elements

func (set *DisjointSetLL) Elements(v int) chan int

*

• Returns all the elements that belong too the region that v belongs to

func (*DisjointSetLL) Find

func (set *DisjointSetLL) Find(v int) int

*

• Returns the id of the component to which the node v belongs

func (*DisjointSetLL) Print

func (set *DisjointSetLL) Print()

*

• Print the dijsointset linked list

func (*DisjointSetLL) Size

func (set *DisjointSetLL) Size(v int) int

*

• Return the size of the region that v belongs to

func (*DisjointSetLL) TotalComponents

func (set *DisjointSetLL) TotalComponents() int

*

• Return the number of components that are stored

func (*DisjointSetLL) TotalElements

func (set *DisjointSetLL) TotalElements() int

*

• Return the number of elements that are stored

func (*DisjointSetLL) Union

func (set *DisjointSetLL) Union(a, b int)

* Merge the regions that a and b belong to

type DisjointSetLLNode

type DisjointSetLLNode struct {
	// contains filtered or unexported fields
}

*

• Node for the linked list

type DisjointSetLLRegion

type DisjointSetLLRegion struct {
	// contains filtered or unexported fields
}

*

• Each component of the disjoint set.
• Contains the id of the region, its parent (if the parent has the same
• address, it means that it's the root), a pointer to the last element of the
• LL, a pointer to the first element of the LL and the size of the region

type DisjointSetNode

type DisjointSetNode struct {
	// contains filtered or unexported fields
}

*

• Node for DisjointSet datastructure.
• Contains the parent id, the node rank and the number
• of components in the tree (only useful for root nodes)