I'm trying to implement the union find algorithm using Go. I want to implement different strategies like quick find, quick union and weighted quick union using one structure UnionFind see below. I put the code into a package unionfind
package unionfind
type Unionfind struct {
elements []int
}
func makeUnionfind(n int) Unionfind {
elements := make([]int, n)
for idx := range elements {
elements[idx] = idx
}
return Unionfind{elements}
}
Next I create the functions for the different strategies starting with quick find. The example below isn't working. But I have no idea where to put the strategy specific code, how to name the package and how to import the common structure type.
// create a separate package for each strategy?
package quickfind
// import the structure locally?
import ufp "./unionfind"
// prefer methods over functions for convenience?
func (uf *ufp.Unionfind) union(a int, b int) {
aroot := uf.elements[a]
broot := uf.elements[b]
for k, v := range uf.elements {
if v == aroot {
uf.elements[k] = broot
}
}
}
func (uf *ufp.Unionfind) connected(a int, b int) bool {
return uf.elements[a] == uf.elements[b]
}
How should I organize my code the get the quick find algorithm working but have the UnionFindstructure separated?
You won't be able to use the same struct for all union find implementations. For example weighted quick union requires array of tree sizes in addition to the elements.
What you are trying to achieve here is to have the same operations implemented differently. This is what interfaces are for in Go.
Additionally using aliases for package imports to save a few key strokes is not a good practice. Instead it is better to come up with good names such as package name together with its interace/struct/function names makes sense.
I would organize all algorithms in one package with the following structure:
package algorithms
type UnionFind interface {
Union(a int, b int)
Connected(a int, b int) bool
}
func QuickFind(n int) UnionFind {
return &quickFind{......}
}
func QuickUnion(n int) UnionFind {
return &quickUnion{......}
}
type quickUnion struct {
....
}
func (qu *quickUnion) Union(a int, b int) {
...
}
func (qu *quickUnion) Connected(a int, b int) bool {
...
}
type quickFind struct {
....
}
func (qf *quickFind) Union(a int, b int) {
...
}
func (qf *quickFind) Connected(a int, b int) bool {
...
}