Introduction
This tip simply translates WeightedQuickUnionUF
class from Java to C#, VB.NET and F#. This tip does not introduce Union Find. However, you can Google it yourself.
Background
The source code can be found from Princeton University at the following link:
Using the Code
The following is the C# code:
using System;
namespace TankWorld.Common
{
public class WeightedQuickUnionUF
{
private int[] parent;
private int[] size;
private int count;
public WeightedQuickUnionUF(int N)
{
count = N;
parent = new int[N];
size = new int[N];
for (int i = 0; i < N; i++)
{
parent[i] = i;
size[i] = 1;
}
}
public int GetCount()
{
return count;
}
public int Find(int p)
{
Validate(p);
while (p != parent[p])
p = parent[p];
return p;
}
private void Validate(int p)
{
int N = parent.Length;
if (p < 0 || p >= N)
{
throw new IndexOutOfRangeException
("index " + p + " is not between 0 and " + (N - 1));
}
}
public bool Connected(int p, int q)
{
return Find(p) == Find(q);
}
public void Union(int p, int q)
{
int rootP = Find(p);
int rootQ = Find(q);
if (rootP == rootQ) return;
if (size[rootP] < size[rootQ])
{
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
}
else
{
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
}
count--;
}
}
}
The following is the VB.NET code:
Public Class VB_WeightedQuickUnionUF
Dim parent() As Integer
Dim size() As Integer
Dim count As Integer
Public Sub New(n As Integer)
If n < 0 Then
Throw New ArgumentOutOfRangeException()
End If
count = n
parent = New Integer(n) {}
size = New Integer(n) {}
For i As Integer = 0 To n - 1
parent(i) = i
size(i) = 1
Next
End Sub
Public Function GetCount() As Integer
Return count
End Function
Public Function Find(p As Integer) As Integer
Validate(p)
While (p <> parent(p))
p = parent(p)
End While
Return p
End Function
Private Sub Validate(p As Integer)
If (p < 0 Or p >= parent.Length) Then
Throw New IndexOutOfRangeException("index " + _
p + " is not between 0 and " + (parent.Length - 1))
End If
End Sub
Public Function Connected(p As Integer, q As Integer) As Boolean
Validate(p)
Validate(q)
Return Find(p) = Find(q)
End Function
Public Sub Union(p As Integer, q As Integer)
Validate(p)
Validate(q)
Dim rootP = Find(p)
Dim rootQ = Find(q)
If (rootP = rootQ) Then Return
If (size(rootP) < size(rootQ)) Then
parent(rootP) = rootQ
size(rootQ) = size(rootQ) + size(rootP)
Else
parent(rootQ) = rootP
size(rootP) = size(rootP) + size(rootQ)
End If
count = count - 1
End Sub
End Class
The following is the F# code:
namespace TankWorld.UnionFind
type WeightedQuickUnion (N) =
let parent : int[] = Array.init N (fun i -> i)
let size : int[] = Array.create N 0
let mutable count=0
let root i =
let mutable q = i
while (q <> parent.[q]) do q <- parent.[q]
q
let validate i=
if i>=N || i<0 then raise(System.IndexOutOfRangeException("index " +
i.ToString() + " is not between 0 and " + (parent.Length - 1).ToString()))
|> ignore
member t.GetCount() = count
member t.Connected(p, q) =
validate(p)
validate(q)
root(p) = root(q)
member t.Union(p, q) =
validate(p)
validate(q)
let i = root(p)
let j = root(q)
if size.[i] < size.[j] then parent.[i] <- j; size.[j] <- size.[j] + size.[i]
else parent.[j] <- i; size.[i] <- size.[i] + size.[j]