gsdset

Documentation

Overview

Package gsdset implements set operations with the package graph/gsd.

Index

• func FindSet(vtx *gsd.Vertex, ds []*DisJointSet) *gsd.Vertex
• func SortEdges(graph *gsd.Graph) *slice.Sequence
• func UnionByRep(rep1, rep2 *gsd.Vertex, ds *[]*DisJointSet) *[]*DisJointSet
• func UnionByVtx(vtx1, vtx2 *gsd.Vertex, ds *[]*DisJointSet) *[]*DisJointSet
• type DisJointSet
  • func GetSet(vtx *gsd.Vertex, ds []*DisJointSet) *DisJointSet
  • func MakeGraphSet(graph *gsd.Graph) []*DisJointSet
  • func MakeSet(vtx *gsd.Vertex) *DisJointSet
  • func NewDisJointSet() *DisJointSet
  • func UnionDisJointSet(s1, s2 *DisJointSet) *DisJointSet
  • func (s DisJointSet) SetContains(vtx *gsd.Vertex) bool
  • func (s DisJointSet) String() string
• type EdgeSlice
  • func (s EdgeSlice) Len() int
  • func (s EdgeSlice) Less(i, j int) bool
  • func (s EdgeSlice) Swap(i, j int)
• type Set
  • func InstantiateSet(vertices ...*gsd.Vertex) Set
  • func NewSet() Set
  • func (s Set) Clone() Set
  • func (s Set) Contains(vtx *gsd.Vertex) bool
  • func (s Set) Delete(vtx *gsd.Vertex) bool
  • func (s Set) GetElements() []*gsd.Vertex
  • func (s Set) Insert(vertices ...*gsd.Vertex)
  • func (s Set) Intersection(a Set) []*gsd.Vertex
  • func (s Set) IsEmpty() bool
  • func (s Set) IsEqual(a Set) bool
  • func (s Set) Size() int
  • func (s Set) String() string
  • func (s Set) Subset(a Set) bool
  • func (s Set) Subtract(a Set) []*gsd.Vertex
  • func (s Set) Union(a Set) []*gsd.Vertex

Functions

func FindSet

func FindSet(vtx *gsd.Vertex, ds []*DisJointSet) *gsd.Vertex

FindSet returns the Rep of the DisJointSet that vtx belongs to.

func SortEdges

func SortEdges(graph *gsd.Graph) *slice.Sequence

SortEdges sorts Edges of graph in an increasing order by its weight and return the sorted Edges in slice.

func UnionByRep

func UnionByRep(rep1, rep2 *gsd.Vertex, ds *[]*DisJointSet) *[]*DisJointSet

UnionByRep joins two subsets each of which is represented by its Rep x and y. We pass pointer to update the input slice.

func UnionByVtx

func UnionByVtx(vtx1, vtx2 *gsd.Vertex, ds *[]*DisJointSet) *[]*DisJointSet

UnionByVtx joins two subsets that contain x and y. It joins two subsets into a single subset and update the slice of DisJointSet.

Types

type DisJointSet

type DisJointSet struct {
	Rep  *gsd.Vertex // Representitive Vertex
	Mems Set         // Set Members

}

func GetSet

func GetSet(vtx *gsd.Vertex, ds []*DisJointSet) *DisJointSet

GetSet returns the DisJointSet that vtx belongs to.

func MakeGraphSet

func MakeGraphSet(graph *gsd.Graph) []*DisJointSet

MakeGraphSet creates a Set of Vertices from the input Graph.

func MakeSet

func MakeSet(vtx *gsd.Vertex) *DisJointSet

MakeSet creates a Set of one input Vertex with the vertex as Rep.

func NewDisJointSet

func NewDisJointSet() *DisJointSet

NewDisJointSet returns a new DisJointSet.

func UnionDisJointSet

func UnionDisJointSet(s1, s2 *DisJointSet) *DisJointSet

UnionDisJointSet creates a Set of Vertices from the input Graph, setting s1's Rep as a new Rep.

func (DisJointSet) SetContains

func (s DisJointSet) SetContains(vtx *gsd.Vertex) bool

SetContains returns true if the value exists in the set.

func (DisJointSet) String

func (s DisJointSet) String() string

String prints out the DisJointSet information.

type EdgeSlice

type EdgeSlice slice.Sequence

(X) type EdgeSlice *slice.Sequence

func (EdgeSlice) Len

func (s EdgeSlice) Len() int

func (EdgeSlice) Less

func (s EdgeSlice) Less(i, j int) bool

func (EdgeSlice) Swap

func (s EdgeSlice) Swap(i, j int)

type Set

type Set map[*gsd.Vertex]*gsd.Vertex

Set maps each Vertex of graph to its Representative of DisJointSet.

func InstantiateSet

func InstantiateSet(vertices ...*gsd.Vertex) Set

InstantiateSet instantiates a set object with initial elements.

func NewSet

func NewSet() Set

NewSet returns a new Set. Map supports the built-in function "make" so we do not have to use "new" and "make" does not return pointer.

func (Set) Clone

func (s Set) Clone() Set

Clone returns a cloned set but does not clone its frequency.

func (Set) Contains

func (s Set) Contains(vtx *gsd.Vertex) bool

Contains returns true if the value exists in the Set.

func (Set) Delete

func (s Set) Delete(vtx *gsd.Vertex) bool

Delete deletes the value, or return false if the value does not exist in the Set.

func (Set) GetElements

func (s Set) GetElements() []*gsd.Vertex

GetElements returns the set elements. It makes another slice to return keys in map. The keys that occur more than one are considered to occur once in this case.

func (Set) Insert

func (s Set) Insert(vertices ...*gsd.Vertex)

Insert insert values to the set.

func (Set) Intersection

func (s Set) Intersection(a Set) []*gsd.Vertex

Intersection returns values common in both sets.

func (Set) IsEmpty

func (s Set) IsEmpty() bool

IsEmpty returns true if the set is empty.

func (Set) IsEqual

func (s Set) IsEqual(a Set) bool

IsEqual returns true if the two sets are same, regardless of its frequency.

func (Set) Size

func (s Set) Size() int

Size returns the size of set.

func (Set) String

func (s Set) String() string

String prints out the Set information.

func (Set) Subset

func (s Set) Subset(a Set) bool

Subset returns true if "a" is a subset of "s".

func (Set) Subtract

func (s Set) Subtract(a Set) []*gsd.Vertex

Subtract returns the set "s" - "a".

func (Set) Union

func (s Set) Union(a Set) []*gsd.Vertex

Union returns the union of two sets.