Weighted Quick Union Find in C#, VB.NET and F#
Weighted Quick Union Find in C#, VB.NET and F#
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:
///////////////////Weiguang Zhou Oct 15, 2015 UCT//////////
/// This class is a translation of the Java class from Princeton University.
/// URL of the original class:
/// http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/WeightedQuickUnionUF.java.html
///////////////////////////////////////////////////////////////////
using System;
namespace TankWorld.Common
{
/// <summary>
/// ///////////////////Weiguang Zhou Oct 15, 2015 UCT//////////
/// This class is a translation of the java class from Princton University.
/// URL of the original class:
/// http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/WeightedQuickUnionUF.java.html
/// </summary>
public class WeightedQuickUnionUF
{
private int[] parent; // parent[i] = parent of i
private int[] size; // size[i] = number of sites in subtree rooted at i
private int count; // number of components
/// <summary>
/// * Initializes an empty union-find data structure with <tt>N</tt> sites
/// * <tt>0</tt> through <tt>N-1</tt>. Each site Is initially in its own
/// * component.
/// </summary>
/// <param name="n">the number of sites</param>
/// <exception cref="ArgumentOutOfRangeException">if n<0</exception>
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;
}
}
/// <summary>
/// Returns the number of components.
/// </summary>
/// <returns>the number of components
/// (between <tt>1</tt> And <tt>N</tt>)</returns>
public int GetCount()
{
return count;
}
/// <summary>
/// Returns the component identifier for the component containing site <tt>p</tt>.
/// </summary>
/// <param name="p">the integer representing one object</param>
/// <returns>the component identifier for the component
/// containing site <tt>p</tt></returns>
/// <exception cref="IndexOutOfRangeException">unless
/// <tt>0 <= p < N</tt></exception>
public int Find(int p)
{
Validate(p);
while (p != parent[p])
p = parent[p];
return p;
}
// validate that p is a valid index
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));
}
}
/// <summary>
/// Returns true if the two sites are in the same component.
/// </summary>
/// <param name="p">the integer representing one site</param>
/// <param name="q">the integer representing the other site</param>
/// <returns>
/// <b>true</b> if the two sites <tt>p</tt>
/// And <tt>q</tt> are in the same component;
/// <tt>false</tt> otherwise
///</returns>
/// <exception cref="IndexOutOfRangeException">unless <tt>0
/// <= p < N</tt> And <tt>0 <= q < N</tt></exception>
public bool Connected(int p, int q)
{
return Find(p) == Find(q);
}
/// <summary>
/// Merges the component containing site <tt>p</tt> with the
/// * the component containing site <tt>q</tt>.
/// </summary>
/// <param name="p">the integer representing one site</param>
/// <param name="q">the integer representing the other site</param>
/// <exception cref="IndexOutOfRangeException">unless both
/// <tt>0 <= p < N</tt>
/// And <tt>0 <= q < N</tt></exception>
public void Union(int p, int q)
{
int rootP = Find(p);
int rootQ = Find(q);
if (rootP == rootQ) return;
// make smaller root point to larger one
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:
'''''''''''''''''''''''''''Weiguang Zhou Oct 15, 2015 UCT'''''''''''''''''''
''' This class Is a translation of the java class from Robert Sedgewick and author Kevin Wayne
''' , Princton University.
''' URL of the original class:
''' http//algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/WeightedQuickUnionUF.java.html
''' ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Public Class VB_WeightedQuickUnionUF
Dim parent() As Integer ' parent[i] = parent Of i
Dim size() As Integer ' size[i] = number Of sites In subtree rooted at i
Dim count As Integer ' number Of components
''' <summary>
''' * Initializes an empty union-find data structure with <tt>N</tt> sites
''' * <tt>0</tt> through <tt>N-1</tt>. Each site Is initially in its own
''' * component.
''' </summary>
''' <param name="n">the number of sites</param>
''' <exception cref="ArgumentOutOfRangeException">if n<0</exception>
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
''' <summary>
''' Returns the number of components.
''' </summary>
''' <returns>the number of components
''' (between <tt>1</tt> And <tt>N</tt>)</returns>
Public Function GetCount() As Integer
Return count
End Function
''' <summary>
''' Returns the component identifier for the component containing site <tt>p</tt>.
''' </summary>
''' <param name="p">the integer representing one object</param>
''' <returns>the component identifier for the component
''' containing site <tt>p</tt></returns>
''' <exception cref="IndexOutOfRangeException">unless
''' <tt>0 <= p < N</tt></exception>
Public Function Find(p As Integer) As Integer
Validate(p)
While (p <> parent(p))
p = parent(p)
End While
Return p
End Function
''' <summary>
''' validate that p Is a valid index
''' </summary>
''' <param name="p"></param>
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
''' <summary>
''' Returns true if the two sites are in the same component.
''' </summary>
''' <param name="p">the integer representing one site</param>
''' <param name="q">the integer representing the other site</param>
''' <returns>
''' <b>true</b> if the two sites <tt>p</tt>
''' And <tt>q</tt> are in the same component;
''' <tt>false</tt> otherwise
'''</returns>
''' <exception cref="IndexOutOfRangeException">unless
''' <tt>0 <= p < N</tt> And <tt>0
''' <= q < N</tt></exception>
Public Function Connected(p As Integer, q As Integer) As Boolean
Validate(p)
Validate(q)
Return Find(p) = Find(q)
End Function
''' <summary>
''' Merges the component containing site <tt>p</tt> with the
''' * the component containing site <tt>q</tt>.
''' </summary>
''' <param name="p">the integer representing one site</param>
''' <param name="q">the integer representing the other site</param>
''' <exception cref="IndexOutOfRangeException">unless both
''' <tt>0 <= p < N</tt> And <tt>0 <= q < N</tt></exception>
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
' make smaller root point to larger one
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
/// <summary>
/// * Initializes an empty union-find data structure with <tt>N</tt> sites
/// * <tt>0</tt> through <tt>N-1</tt>. Each site Is initially in its own
/// * component.
/// </summary>
/// <param name="n">the number of sites</param>
/// <exception cref="ArgumentOutOfRangeException">when things go wrong.</exception>
type WeightedQuickUnion (N) =
//parent.[i] = parent Of i
let parent : int[] = Array.init N (fun i -> i)
//size.[i] = number Of sites In subtree rooted at i
let size : int[] = Array.create N 0
//number Of components
let mutable count=0
let root i =
let mutable q = i
while (q <> parent.[q]) do q <- parent.[q]
q
//validate that p Is a valid index
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
/// <summary>
/// Returns the number of components.
/// </summary>
/// <returns>the number of components (between <tt>1</tt>
/// And <tt>N</tt>)</returns>
member t.GetCount() = count
/// <summary>
/// Returns true if the two sites are in the same component.
/// </summary>
/// <param name="p">the integer representing one site</param>
/// <param name="q">the integer representing the other site</param>
/// <returns>
/// <b>true</b> if the two sites <tt>p</tt>
/// And <tt>q</tt> are in the same component;
/// <tt>false</tt> otherwise
///</returns>
/// <exception cref="IndexOutOfRangeException">unless <tt>0
/// <= p < N</tt> And <tt>0 <= q < N</tt></exception>
member t.Connected(p, q) =
validate(p)
validate(q)
root(p) = root(q)
/// <summary>
/// Merges the component containing site <tt>p</tt> with the
/// * the component containing site <tt>q</tt>.
/// </summary>
/// <param name="p">the integer representing one site</param>
/// <param name="q">the integer representing the other site</param>
/// <exception cref="IndexOutOfRangeException">unless both
/// <tt>0 <= p < N</tt> And <tt>0 <= q < N</tt></exception>
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]