3
\$\begingroup\$

I've created an integer index based union find implementation in C#, and am looking for some feedback. Unit tests have been written with NUnit. Some questions I am considering:

  1. Can the implementation be made more performant?
  2. Can the (C#) language be used more elegantly?
  3. Are there any general style guidelines being violated?
  4. Could the design of the classes in the implementation or unit tests be done better?
  5. Are there any bugs that have been missed?
  6. Is there a better way to leverage the NUnit framework for clearer code?
using System;

namespace DataStructures
{
    /// <summary>
    /// An integer based implementation of the union find data structure
    /// </summary>
    /// <remarks>
    /// It is expected that the integer indices stored internally in this <see cref="UnionFind"/> class are correlated to actual objects via a bijection of integer indices 
    /// to objects
    /// </remarks>
    public class UnionFind
    {
        private int[] elements;
        private int[] componentSizes;

        /// <summary>
        /// The number of components that elements have been grouped into
        /// </summary>
        public int ComponentCount { get; private set; }

        /// <summary>
        /// Creates an instance of an integer based <see cref="UnionFind"/> data structure
        /// </summary>
        /// <param name="size">The number of elements to initialize the <see cref="UnionFind"/> instance with</param>
        /// <exception cref="ArgumentOutOfRangeException">Thrown if the inputted <paramref name="size"/> is less than 0 or above <see cref="int.MaxValue"/></exception>
        public UnionFind(int size)
        {
            if (size < 0 || size > int.MaxValue)
            {
                throw new ArgumentOutOfRangeException(nameof(size), Resource.SizeMustBeWithinValidRange);
            }

            this.elements = new int[size];
            this.componentSizes = new int[size];

            for (var i = 0; i < size; i++)
            {
                this.elements[i] = i;
                this.componentSizes[i] = 1;
            }

            this.ComponentCount = size;
        }

        /// <summary>
        /// Checks by index whether two elements are in the same group
        /// </summary>
        /// <param name="firstIndex">The index of the first element to check</param>
        /// <param name="secondIndex">The index of the second element to check</param>
        /// <returns>True if the elements are in the same group, otherwise false</returns>
        public bool Connected(int firstIndex, int secondIndex)
        {
            return this.Find(firstIndex) == this.Find(secondIndex);
        }

        /// <summary>
        /// Finds the index of the root parent to an element
        /// </summary>
        /// <param name="index">The index of the child element</param>
        /// <returns>The index of the root parent element, or the inputted index if the element has no parents</returns>
        /// <exception cref="ArgumentOutOfRangeException">Thrown if the inputted <paramref name="index"/> is less than 0 or above <see cref="int.MaxValue"/></exception>
        /// <remarks>
        /// This method has the side-effect of compressing the path from child to root parent such that all elements between, including the child, directly
        /// point to the root parent after <see cref="Find(int)"/> has executed. As a result of path compression, <see cref="Find(int)"/> runs in amortized 
        /// constant time.
        /// </remarks>
        public int Find(int index)
        {
            if (index < 0 || index > this.elements.Length - 1)
            {
                throw new ArgumentOutOfRangeException(nameof(index), Resource.IndexMustBeWithinValidRange);
            }

            int nextIndex = index;

            while (this.HasParent(nextIndex))
            {
                nextIndex = this.elements[nextIndex];
            }

            new PathCompressor(this.elements).Compress(index, nextIndex);

            return nextIndex;
        }

        /// <summary>
        /// Gets the size of the component an element belongs to
        /// </summary>
        /// <param name="index">The index of the element</param>
        /// <returns>The size of the component the element belongs to</returns>
        public int GetComponentSize(int index)
        {
            return this.componentSizes[this.Find(index)];
        }

        /// <summary>
        /// Merges two elements' groups together
        /// </summary>
        /// <param name="firstIndex">The index of the first element to merge</param>
        /// <param name="secondIndex">The index of the second element to merge</param>
        /// <exception cref="ArgumentOutOfRangeException">
        /// Thrown if either the inputted <paramref name="firstIndex"/> or <paramref name="secondIndex"/> is less than 0 or above <see cref="int.MaxValue"/>
        /// </exception>
        public void Unify(int firstIndex, int secondIndex)
        {
            if (firstIndex < 0 || firstIndex > this.elements.Length - 1)
            {
                throw new ArgumentOutOfRangeException(nameof(firstIndex), Resource.IndexMustBeWithinValidRange);
            }

            if (secondIndex < 0 || secondIndex > this.elements.Length - 1)
            {
                throw new ArgumentOutOfRangeException(nameof(secondIndex), Resource.IndexMustBeWithinValidRange);
            }

            if (firstIndex == secondIndex)
            {
                return;
            }

            var firstParentIndex = this.Find(firstIndex);
            var secondParentIndex = this.Find(secondIndex);

            if (firstParentIndex == secondParentIndex)
            {
                return;
            }

            this.UpdateComponentState(firstParentIndex, secondParentIndex);
        }

        private void UpdateComponentState(int firstParentIndex, int secondParentIndex)
        {
            if (this.componentSizes[firstParentIndex] >= this.componentSizes[secondParentIndex])
            {
                this.elements[secondParentIndex] = firstParentIndex;
                this.componentSizes[firstParentIndex] += this.componentSizes[secondParentIndex];
            }
            else
            {
                this.elements[firstParentIndex] = secondParentIndex;
                this.componentSizes[secondParentIndex] += this.componentSizes[firstParentIndex];
            }

            this.ComponentCount--;
        }

        private bool HasParent(int nextIndex)
        {
            return this.elements[nextIndex] != nextIndex;
        }
    }
}
namespace DataStructures
{
    /// <summary>
    /// A path compression strategy class for the <see cref="UnionFind"/> data structure. 
    /// </summary>
    internal class PathCompressor
    {
        private readonly int[] elements;

        /// <summary>
        /// Creates an instance of a <see cref="PathCompressor"/>
        /// </summary>
        /// <param name="elements">An array of all elements that could undergo path compression</param>
        public PathCompressor(int[] elements)
        {
            this.elements = elements;
        }

        /// <summary>
        /// Compresses the path from a child element to its root parent element.
        /// </summary>
        /// <param name="fromIndex">The index of the child element from which path compression will start. Path compression includes the child element.</param>
        /// <param name="toIndex">The index of the root parent element where path compression will end.</param>
        public void Compress(int fromIndex, int toIndex)
        {
            var next = fromIndex;

            while (this.elements[next] != toIndex)
            {
                var temp = this.elements[next];
                this.elements[next] = toIndex;
                next = temp;
            }
        }
    }
}

Unit Tests:

using DataStructures;
using NUnit.Framework;
using System.Collections.Generic;

namespace UnitTests
{
    /// <summary>
    /// Unit tests for the <see cref="UnionFind"/> class
    /// </summary>
    public class UnionFindTests
    {
        /// <summary>
        /// Tests that <see cref="UnionFind.Connected(int, int)"/> successfully identifies elements which are in the same group
        /// </summary>
        /// <param name="parameters">An instance encapsulating the inputs and expected outputs from this test</param>
        [TestCaseSource(nameof(UnionFindTests.ConnectedTestCaseSource))]
        public void TestConnected(Parameters<IndexPair, bool> parameters)
        {
            var unionFind = new UnionFind(parameters.InitialSize);

            foreach (var pair in parameters.PairsToMerge)
            {
                unionFind.Unify(pair.FirstIndex, pair.SecondIndex);
            }

            foreach (var inputOutput in parameters.InputOutput)
            {
                Assert.That(unionFind.Connected(inputOutput.Input.FirstIndex, inputOutput.Input.SecondIndex), Is.EqualTo(inputOutput.ExpectedOutput));
            }
        }

        /// <summary>
        /// Tests that <see cref="UnionFind.Find(int)"/> finds an elements root parent as expected
        /// </summary>
        /// <param name="initialSize">The size of the <see cref="UnionFind"/> to initialize</param>
        /// <param name="indexToFind">The element index to input into the <see cref="UnionFind.Find(int)"/> method</param>
        /// <param name="expectedRootIndex">The expected output index from <see cref="UnionFind.Find(int)"/></param>
        [TestCase(1, 0, 0)]
        [TestCase(2, 1, 1)]
        [TestCase(4, 3, 3)]
        [TestCase(10, 9, 9)]
        public void TestFind(int initialSize, int indexToFind, int expectedRootIndex)
        {
            var unionFind = new UnionFind(initialSize);
            Assert.That(unionFind.Find(indexToFind), Is.EqualTo(expectedRootIndex));
        }

        /// <summary>
        /// Tests that <see cref="UnionFind.Unify(int, int)"/> merges elements/groups as expected
        /// </summary>
        /// <param name="parameters">An instance encapsulating the inputs and expected outputs from this test</param>
        [TestCaseSource(nameof(UnionFindTests.UnifyTestCaseSource))]
        public void TestUnify(Parameters<int, int> parameters)
        {
            var unionFind = new UnionFind(parameters.InitialSize);

            foreach (var pair in parameters.PairsToMerge)
            {
                unionFind.Unify(pair.FirstIndex, pair.SecondIndex);
            }

            foreach (var inputOutput in parameters.InputOutput)
            {
                Assert.That(unionFind.Find(inputOutput.Input), Is.EqualTo(inputOutput.ExpectedOutput));
            }
        }

        /// <summary>
        /// Tests that the <see cref="UnionFind.GetComponentSize(int)"/> returns the queried component size as expected
        /// </summary>
        /// <param name="parameters"></param>
        [TestCaseSource(nameof(UnionFindTests.GetComponentSizeTestCaseSource))]
        public void TestGetComponentSize(Parameters<int, int> parameters)
        {
            var unionFind = new UnionFind(parameters.InitialSize);

            foreach (var pair in parameters.PairsToMerge)
            {
                unionFind.Unify(pair.FirstIndex, pair.SecondIndex);
            }

            foreach (var inputOutput in parameters.InputOutput)
            {
                Assert.That(unionFind.GetComponentSize(inputOutput.Input), Is.EqualTo(inputOutput.ExpectedOutput));
            }
        }

        private static IEnumerable<TestCaseData> ConnectedTestCaseSource()
        {
            yield return new TestCaseData(new Parameters<IndexPair, bool>
            {
                InitialSize = 4,
                PairsToMerge = new[] { new IndexPair(1, 1), new IndexPair(2, 2), new IndexPair(3, 3) },
                InputOutput = new[]
                { 
                    new InputOutput<IndexPair, bool>(new IndexPair(1, 2), false),
                    new InputOutput<IndexPair, bool>(new IndexPair(1, 3), false),
                    new InputOutput<IndexPair, bool>(new IndexPair(2, 3), false),
                    new InputOutput<IndexPair, bool>(new IndexPair(1, 1), true),
                    new InputOutput<IndexPair, bool>(new IndexPair(2, 2), true),
                    new InputOutput<IndexPair, bool>(new IndexPair(3, 3), true),
                }
            }).SetName("Unify each element to itself, then ensure no elements are in the same group");

            yield return new TestCaseData(new Parameters<IndexPair, bool>
            {
                InitialSize = 11,
                PairsToMerge = new[] { new IndexPair(1, 5), new IndexPair(6, 3), new IndexPair(3, 1), new IndexPair(7, 3) },
                InputOutput = new[]
                {
                    new InputOutput<IndexPair, bool>(new IndexPair(1, 2), false),
                    new InputOutput<IndexPair, bool>(new IndexPair(1, 3), true),
                    new InputOutput<IndexPair, bool>(new IndexPair(1, 4), false),
                    new InputOutput<IndexPair, bool>(new IndexPair(1, 5), true),
                    new InputOutput<IndexPair, bool>(new IndexPair(1, 6), true),
                    new InputOutput<IndexPair, bool>(new IndexPair(1, 7), true),
                    new InputOutput<IndexPair, bool>(new IndexPair(6, 7), true),
                    new InputOutput<IndexPair, bool>(new IndexPair(6, 10), false)
                }
            }).SetName("Unify some elements, then ensure only these elements are in the same group");
        }

        private static IEnumerable<TestCaseData> UnifyTestCaseSource()
        {
            yield return new TestCaseData(new Parameters<int, int>
            {
                InitialSize = 4,
                PairsToMerge = new[] { new IndexPair(1, 1), new IndexPair(2, 2), new IndexPair(3, 3) },
                InputOutput = new[] { new InputOutput<int, int>(1, 1), new InputOutput<int, int>(2, 2), new InputOutput<int, int>(3, 3) }
            }).SetName("Unify each element to itself, then ensure each element points to itself");

            yield return new TestCaseData(new Parameters<int, int>
            {
                InitialSize = 6,
                PairsToMerge = new[] { new IndexPair(1, 2), new IndexPair(2, 3), new IndexPair(3, 4), new IndexPair(4, 5) },
                InputOutput = new[] 
                { 
                    new InputOutput<int, int>(1, 1),
                    new InputOutput<int, int>(2, 1),
                    new InputOutput<int, int>(3, 1),
                    new InputOutput<int, int>(4, 1),
                    new InputOutput<int, int>(5, 1) 
                }
            }).SetName("Unify all elements into the same component, then ensure all elements have the same parent");

            yield return new TestCaseData(new Parameters<int, int>
            {
                InitialSize = 101,
                PairsToMerge = new[] { new IndexPair(5, 100), new IndexPair(3, 50), new IndexPair(2, 50), new IndexPair(50, 6), new IndexPair(100, 6) },
                InputOutput = new[] 
                { 
                    new InputOutput<int, int>(5, 3),
                    new InputOutput<int, int>(100, 3),
                    new InputOutput<int, int>(3, 3),
                    new InputOutput<int, int>(50, 3),
                    new InputOutput<int, int>(2, 3),
                    new InputOutput<int, int>(6, 3) 
                }
            }).SetName("Unify two components together, then ensure all elements have the same parent");

            yield return new TestCaseData(new Parameters<int, int>
            {
                InitialSize = 501,
                PairsToMerge = new[] { new IndexPair(500, 400), new IndexPair(20, 60), new IndexPair(33, 67), new IndexPair(33, 6), new IndexPair(500, 20), new IndexPair(500, 6) },
                InputOutput = new[] 
                { 
                    new InputOutput<int, int>(500, 500),
                    new InputOutput<int, int>(400, 500),
                    new InputOutput<int, int>(20, 500),
                    new InputOutput<int, int>(60, 500),
                    new InputOutput<int, int>(33, 500),
                    new InputOutput<int, int>(6, 500) 
                }
            }).SetName("Unify three components together, then ensure all elements have the same parent");

            yield return new TestCaseData(new Parameters<int, int>
            {
                InitialSize = 11,
                PairsToMerge = new[]
                {
                    new IndexPair(10, 0),
                    new IndexPair(1, 9),
                    new IndexPair(2, 8),
                    new IndexPair(3, 7),
                    new IndexPair(4, 6),
                    new IndexPair(5, 10),
                    new IndexPair(5, 1),
                    new IndexPair(8, 5),
                    new IndexPair(3, 4)
                },
                InputOutput = new[]
                {
                    new InputOutput<int, int>(0, 10),
                    new InputOutput<int, int>(1, 10),
                    new InputOutput<int, int>(2, 10),
                    new InputOutput<int, int>(3, 3),
                    new InputOutput<int, int>(4, 3),
                    new InputOutput<int, int>(5, 10),
                    new InputOutput<int, int>(6, 3),
                    new InputOutput<int, int>(7, 3),
                    new InputOutput<int, int>(8, 10),
                    new InputOutput<int, int>(9, 10),
                    new InputOutput<int, int>(10, 10)
                }
            }).SetName("Unify elements into two different compoents, then ensure that they each have the correct parent");
        }

        private static IEnumerable<TestCaseData> GetComponentSizeTestCaseSource()
        {
            yield return new TestCaseData(new Parameters<int, int>
            {
                InitialSize = 4,
                PairsToMerge = new[] { new IndexPair(1, 1), new IndexPair(2, 2), new IndexPair(3, 3) },
                InputOutput = new[] { new InputOutput<int, int>(1, 1), new InputOutput<int, int>(2, 1), new InputOutput<int, int>(3, 1) }
            }).SetName("Get the component size of elements that have not yet been grouped");

            yield return new TestCaseData(new Parameters<int, int>
            {
                InitialSize = 6,
                PairsToMerge = new[] { new IndexPair(1, 2), new IndexPair(2, 3), new IndexPair(3, 4), new IndexPair(4, 5) },
                InputOutput = new[] 
                { 
                    new InputOutput<int, int>(1, 5),
                    new InputOutput<int, int>(2, 5),
                    new InputOutput<int, int>(3, 5),
                    new InputOutput<int, int>(4, 5),
                    new InputOutput<int, int>(5, 5) 
                }
            }).SetName("Get the component size of elements that are all in the same component");

            yield return new TestCaseData(new Parameters<int, int>
            {
                InitialSize = 11,
                PairsToMerge = new[]
                { 
                    new IndexPair(10, 0),
                    new IndexPair(1, 9),
                    new IndexPair(2, 8),
                    new IndexPair(3, 7),
                    new IndexPair(4, 6),

                    new IndexPair(5, 10),
                    new IndexPair(5, 1),
                    new IndexPair(8, 5),
                    new IndexPair(3, 4)
                },
                InputOutput = new[]
                {
                    new InputOutput<int, int>(0, 7),
                    new InputOutput<int, int>(1, 7),
                    new InputOutput<int, int>(2, 7),
                    new InputOutput<int, int>(3, 4),
                    new InputOutput<int, int>(4, 4),
                    new InputOutput<int, int>(5, 7),
                    new InputOutput<int, int>(6, 4),
                    new InputOutput<int, int>(7, 4),
                    new InputOutput<int, int>(8, 7),
                    new InputOutput<int, int>(9, 7),
                    new InputOutput<int, int>(10, 7)
                }
            }).SetName("Get the component size of elements that are in different components");
        }

        /// <summary>
        /// Parameters for testing the <see cref="UnionFind"/> data structure
        /// </summary>
        public class Parameters<T, U>
        {
            /// <summary>
            /// The initial size of the <see cref="UnionFind"/> instance under test
            /// </summary>
            public int InitialSize { get; set; }

            /// <summary>
            /// The index pairs to merge before the target method is tested
            /// </summary>
            public IndexPair[] PairsToMerge { get; set; }

            public InputOutput<T,U>[] InputOutput { get; set; }
        }

        /// <summary>
        /// A pair of indices that should be processed together, such as for merging
        /// </summary>
        public class IndexPair
        {
            /// <summary>
            /// The index of the first element to process
            /// </summary>
            public int FirstIndex { get; }

            /// <summary>
            /// The index of the second element to process
            /// </summary>
            public int SecondIndex { get; }

            /// <summary>
            /// Creates an instance of an <see cref="IndexPair"/> for grouping pairs of indices together
            /// </summary>
            /// <param name="firstIndex">The index of the first element to process</param>
            /// <param name="secondIndex">The index of the second element to process</param>
            public IndexPair(int firstIndex, int secondIndex)
            {
                this.FirstIndex = firstIndex;
                this.SecondIndex = secondIndex;
            }
        }

        /// <summary>
        /// Encapsulated input and expected output for the method under test
        /// </summary>
        /// <typeparam name="T">The type of <see cref="Input"/></typeparam>
        /// <typeparam name="U">The type of <see cref="ExpectedOutput"/></typeparam>
        public class InputOutput<T, U>
        {
            /// <summary>
            /// The value to input into the method under test
            /// </summary>
            public T Input { get; }

            /// <summary>
            /// The expected output value of the method under test
            /// </summary>
            public U ExpectedOutput { get; }

            /// <summary>
            /// Creates an instance for encapsulating input into a method under test, and the expected output
            /// </summary>
            /// <param name="input">The value that will be inputted into the method under test</param>
            /// <param name="expectedOutput">The expected output value from the method under test</param>
            public InputOutput(T input, U expectedOutput)
            {
                this.Input = input;
                this.ExpectedOutput = expectedOutput;
            }
        }
    }
}
using DataStructures;
using NUnit.Framework;
using System.Collections.Generic;
using System.Linq;

namespace UnitTests
{
    /// <summary>
    /// Unit tests for the <see cref="PathCompressor"/> class
    /// </summary>
    internal class PathCompressorTests
    {
        /// <summary>
        /// Tests that the <see cref="PathCompressor.Compress(int, int)"/> method behaves as expected
        /// </summary>
        /// <param name="parameters">An instance encapsulating the inputs and expected outputs from this test</param>
        [TestCaseSource(nameof(PathCompressorTestCaseSource))]
        public void TestPathCompressor(CompressParameters parameters)
        {
            var elements = parameters.InitialIndices;
            var compressor = new PathCompressor(elements);

            compressor.Compress(parameters.StartIndex, parameters.RootIndex);
            Assert.That(elements, Is.EqualTo(parameters.ExpectedIndices));
        }

        private static IEnumerable<TestCaseData> PathCompressorTestCaseSource()
        {
            yield return new TestCaseData(new CompressParameters
            {
                InitialIndices = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10 },
                StartIndex = 0,
                RootIndex = 10,
                ExpectedIndices = Enumerable.Repeat(10, 11).ToArray()
            }).SetName("Compress elements in series");

            yield return new TestCaseData(new CompressParameters
            {
                InitialIndices = new[] { 1, 10, 3, 6, 5, 2, 8, 9, 7, 9, 4 },
                StartIndex = 0,
                RootIndex = 9,
                ExpectedIndices = Enumerable.Repeat(9, 11).ToArray()
            }).SetName("Compress elements in mixed array order");
        }

        /// <summary>
        /// Parameters for testing the <see cref="PathCompressor.Compress(int, int)"/> method
        /// </summary>
        public class CompressParameters
        {
            /// <summary>
            /// An array of element indices to initialize the <see cref="PathCompressor"/> instance under test with
            /// </summary>
            public int[] InitialIndices { get; set; }

            /// <summary>
            /// The index of the child element where path compression will begin
            /// </summary>
            public int StartIndex { get; set; }

            /// <summary>
            /// The index of the root parent element where path compression will end
            /// </summary>
            public int RootIndex { get; set; }

            /// <summary>
            /// The expected element indices after path compression
            /// </summary>
            public int[] ExpectedIndices { get; set; }
        }
    }
}

```
\$\endgroup\$
3
\$\begingroup\$

Using two arrays of int

That's nice. There is a tendency to use Node objects that refer to each other by address, which still requires an array to initially find a node by index anyway, and then the nodes become a pointless extra step. Trap avoided.

PathCompressor

This class is a bit dubious, it works by "stealing" (temporarily, so maybe "borrowing") the private data of the main data structure and modifying it (resulting in a kind of action-at-a-distance type of modification). Strangely, it holds state at all, its main job is encapsulating the path compression function as an object. It could have been a private method of UnionFind as well, or even just inlined directly into its call-site. There are no other places where it would be used .. well, except in the tests.

Describing it as a path compression strategy class suggests that it's part of a strategy pattern, where different strategies might be supplied, but there is no facility to supply them. The other major strategies, path splitting, and path halving are specifically meant to be performed during the initial pass - their point is sacrificing some amount of path-shortening to avoid a second pass. If they were implemented as a drop-in replacement strategy, the way it is now, their point would be missed.

So in total, in my opinion, there should not be a PathCompressor class.

Naming of elements

elements is very generic. That's no big deal, but you could emphasize their nature more, for example, parents or links.

Performance?

You could try path splitting/halving, they were invented to be faster in practice than full path compression. I've never benchmarked them though.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for the awesome feedback! Did not know about path splitting or halving. Based on your comments, if a set of strategy classes were to be implemented, it seems it would be better to implement them as Find strategy classes instead of Path Compression/Splitting/Halving strategy classes. For example, classes could be something like FindWithPathCompression, FindWithPathSplitting, FindWithPathHalving. These could then be injected into the UnionFind via constructor or property. Anyone have a better design pattern for doing this? \$\endgroup\$ – MiniWalrus Mar 22 at 20:57
2
\$\begingroup\$

As for the primary code I think it's very well written, with good documentation, naming and general structure.

Some minor comments:

Avoid the use of this.-prefix - it is rather un-C#-ish, unless it's absolutely necessary:

public PathCompressor(int[] elements)
{
  this.elements = elements;
}

if (size < 0 || size > int.MaxValue)

An int can never be larger than int.MaxValue - if so int.MaxValue wouldn't be int.MaxValue.


if (index < 0 || index > elements.Length - 1)

I would prefer index >= elements.Length for the second condition.


| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.