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:

• http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/WeightedQuickUnionUF.java.html

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&lt;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 &lt;= p &lt; 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
        /// &lt;= p &lt; N</tt> And <tt>0 &lt;= q &lt; 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 &lt;= p &lt; N</tt> 
        /// And <tt>0 &lt;= q &lt; 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&lt;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 &lt;= p &lt; 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 &lt;= p &lt; N</tt> And <tt>0 
    ''' &lt;= q &lt; 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 &lt;= p &lt; N</tt> And <tt>0 &lt;= q &lt; 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 
        /// &lt;= p &lt; N</tt> And <tt>0 &lt;= q &lt; 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 &lt;= p &lt; N</tt> And <tt>0 &lt;= q &lt; 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]