Back to Repositories

Validating UnionFind Component Operations in Algorithms Repository

This comprehensive test suite validates the UnionFind data structure implementation, focusing on component management, connectivity tracking, and size operations. The tests ensure proper functionality of union-find operations while maintaining data structure integrity and performance.

Test Coverage Overview

The test suite provides extensive coverage of UnionFind operations:

Component counting and size tracking
Element connectivity verification
Dynamic component unification
Size maintenance and validation
Error handling for invalid initializations

Key edge cases include repeated unifications, self-connectivity checks, and boundary conditions.

Implementation Analysis

The testing approach employs JUnit 5 with parameterized tests and Google Truth assertions for enhanced readability and maintainability.

Systematic component size verification
Comprehensive connectivity matrix testing
Parameterized negative test cases
Progressive union operation validation

Technical Details

Testing infrastructure includes:

JUnit Jupiter API for test execution
Google Truth assertion framework
Parameterized test capabilities
Custom test fixtures for UnionFind initialization
Systematic state verification methods

Best Practices Demonstrated

The test suite exemplifies robust testing practices:

Thorough state verification after each operation
Systematic edge case coverage
Clear test method naming conventions
Efficient test organization and modularity
Comprehensive error condition validation

williamfiset/algorithms

src/test/java/com/williamfiset/algorithms/datastructures/unionfind/UnionFindTest.java

            
package com.williamfiset.algorithms.datastructures.unionfind;

// import static org.junit.Assert.*;
import static com.google.common.truth.Truth.assertThat;
import static org.junit.jupiter.api.Assertions.assertThrows;

import org.junit.jupiter.api.Test;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.ValueSource;

public class UnionFindTest {

  @Test
  public void testNumComponents() {

    UnionFind uf = new UnionFind(5);
    assertThat(uf.components()).isEqualTo(5);

    uf.unify(0, 1);
    assertThat(uf.components()).isEqualTo(4);

    uf.unify(1, 0);
    assertThat(uf.components()).isEqualTo(4);

    uf.unify(1, 2);
    assertThat(uf.components()).isEqualTo(3);

    uf.unify(0, 2);
    assertThat(uf.components()).isEqualTo(3);

    uf.unify(2, 1);
    assertThat(uf.components()).isEqualTo(3);

    uf.unify(3, 4);
    assertThat(uf.components()).isEqualTo(2);

    uf.unify(4, 3);
    assertThat(uf.components()).isEqualTo(2);

    uf.unify(1, 3);
    assertThat(uf.components()).isEqualTo(1);

    uf.unify(4, 0);
    assertThat(uf.components()).isEqualTo(1);
  }

  @Test
  public void testComponentSize() {

    UnionFind uf = new UnionFind(5);
    assertThat(uf.componentSize(0)).isEqualTo(1);
    assertThat(uf.componentSize(1)).isEqualTo(1);
    assertThat(uf.componentSize(2)).isEqualTo(1);
    assertThat(uf.componentSize(3)).isEqualTo(1);
    assertThat(uf.componentSize(4)).isEqualTo(1);

    uf.unify(0, 1);
    assertThat(uf.componentSize(0)).isEqualTo(2);
    assertThat(uf.componentSize(1)).isEqualTo(2);
    assertThat(uf.componentSize(2)).isEqualTo(1);
    assertThat(uf.componentSize(3)).isEqualTo(1);
    assertThat(uf.componentSize(4)).isEqualTo(1);

    uf.unify(1, 0);
    assertThat(uf.componentSize(0)).isEqualTo(2);
    assertThat(uf.componentSize(1)).isEqualTo(2);
    assertThat(uf.componentSize(2)).isEqualTo(1);
    assertThat(uf.componentSize(3)).isEqualTo(1);
    assertThat(uf.componentSize(4)).isEqualTo(1);

    uf.unify(1, 2);
    assertThat(uf.componentSize(0)).isEqualTo(3);
    assertThat(uf.componentSize(1)).isEqualTo(3);
    assertThat(uf.componentSize(2)).isEqualTo(3);
    assertThat(uf.componentSize(3)).isEqualTo(1);
    assertThat(uf.componentSize(4)).isEqualTo(1);

    uf.unify(0, 2);
    assertThat(uf.componentSize(0)).isEqualTo(3);
    assertThat(uf.componentSize(1)).isEqualTo(3);
    assertThat(uf.componentSize(2)).isEqualTo(3);
    assertThat(uf.componentSize(3)).isEqualTo(1);
    assertThat(uf.componentSize(4)).isEqualTo(1);

    uf.unify(2, 1);
    assertThat(uf.componentSize(0)).isEqualTo(3);
    assertThat(uf.componentSize(1)).isEqualTo(3);
    assertThat(uf.componentSize(2)).isEqualTo(3);
    assertThat(uf.componentSize(3)).isEqualTo(1);
    assertThat(uf.componentSize(4)).isEqualTo(1);

    uf.unify(3, 4);
    assertThat(uf.componentSize(0)).isEqualTo(3);
    assertThat(uf.componentSize(1)).isEqualTo(3);
    assertThat(uf.componentSize(2)).isEqualTo(3);
    assertThat(uf.componentSize(3)).isEqualTo(2);
    assertThat(uf.componentSize(4)).isEqualTo(2);

    uf.unify(4, 3);
    assertThat(uf.componentSize(0)).isEqualTo(3);
    assertThat(uf.componentSize(1)).isEqualTo(3);
    assertThat(uf.componentSize(2)).isEqualTo(3);
    assertThat(uf.componentSize(3)).isEqualTo(2);
    assertThat(uf.componentSize(4)).isEqualTo(2);

    uf.unify(1, 3);
    assertThat(uf.componentSize(0)).isEqualTo(5);
    assertThat(uf.componentSize(1)).isEqualTo(5);
    assertThat(uf.componentSize(2)).isEqualTo(5);
    assertThat(uf.componentSize(3)).isEqualTo(5);
    assertThat(uf.componentSize(4)).isEqualTo(5);

    uf.unify(4, 0);
    assertThat(uf.componentSize(0)).isEqualTo(5);
    assertThat(uf.componentSize(1)).isEqualTo(5);
    assertThat(uf.componentSize(2)).isEqualTo(5);
    assertThat(uf.componentSize(3)).isEqualTo(5);
    assertThat(uf.componentSize(4)).isEqualTo(5);
  }

  @Test
  public void testConnectivity() {

    int sz = 7;
    UnionFind uf = new UnionFind(sz);

    for (int i = 0; i < sz; i++) assertThat(uf.connected(i, i)).isTrue();

    uf.unify(0, 2);

    assertThat(uf.connected(0, 2)).isTrue();
    assertThat(uf.connected(2, 0)).isTrue();

    assertThat(uf.connected(0, 1)).isFalse();
    assertThat(uf.connected(3, 1)).isFalse();
    assertThat(uf.connected(6, 4)).isFalse();
    assertThat(uf.connected(5, 0)).isFalse();

    for (int i = 0; i < sz; i++) assertThat(uf.connected(i, i)).isTrue();

    uf.unify(3, 1);

    assertThat(uf.connected(0, 2)).isTrue();
    assertThat(uf.connected(2, 0)).isTrue();
    assertThat(uf.connected(1, 3)).isTrue();
    assertThat(uf.connected(3, 1)).isTrue();

    assertThat(uf.connected(0, 1)).isFalse();
    assertThat(uf.connected(1, 2)).isFalse();
    assertThat(uf.connected(2, 3)).isFalse();
    assertThat(uf.connected(1, 0)).isFalse();
    assertThat(uf.connected(2, 1)).isFalse();
    assertThat(uf.connected(3, 2)).isFalse();

    assertThat(uf.connected(1, 4)).isFalse();
    assertThat(uf.connected(2, 5)).isFalse();
    assertThat(uf.connected(3, 6)).isFalse();

    for (int i = 0; i < sz; i++) assertThat(uf.connected(i, i)).isTrue();

    uf.unify(2, 5);
    assertThat(uf.connected(0, 2)).isTrue();
    assertThat(uf.connected(2, 0)).isTrue();
    assertThat(uf.connected(1, 3)).isTrue();
    assertThat(uf.connected(3, 1)).isTrue();
    assertThat(uf.connected(0, 5)).isTrue();
    assertThat(uf.connected(5, 0)).isTrue();
    assertThat(uf.connected(5, 2)).isTrue();
    assertThat(uf.connected(2, 5)).isTrue();

    assertThat(uf.connected(0, 1)).isFalse();
    assertThat(uf.connected(1, 2)).isFalse();
    assertThat(uf.connected(2, 3)).isFalse();
    assertThat(uf.connected(1, 0)).isFalse();
    assertThat(uf.connected(2, 1)).isFalse();
    assertThat(uf.connected(3, 2)).isFalse();

    assertThat(uf.connected(4, 6)).isFalse();
    assertThat(uf.connected(4, 5)).isFalse();
    assertThat(uf.connected(1, 6)).isFalse();

    for (int i = 0; i < sz; i++) assertThat(uf.connected(i, i)).isTrue();

    // Connect everything
    uf.unify(1, 2);
    uf.unify(3, 4);
    uf.unify(4, 6);

    for (int i = 0; i < sz; i++) {
      for (int j = 0; j < sz; j++) {
        assertThat(uf.connected(i, j)).isTrue();
      }
    }
  }

  @Test
  public void testSize() {

    UnionFind uf = new UnionFind(5);
    assertThat(uf.size()).isEqualTo(5);
    uf.unify(0, 1);
    uf.find(3);
    assertThat(uf.size()).isEqualTo(5);
    uf.unify(1, 2);
    assertThat(uf.size()).isEqualTo(5);
    uf.unify(0, 2);
    uf.find(1);
    assertThat(uf.size()).isEqualTo(5);
    uf.unify(2, 1);
    assertThat(uf.size()).isEqualTo(5);
    uf.unify(3, 4);
    uf.find(0);
    assertThat(uf.size()).isEqualTo(5);
    uf.unify(4, 3);
    uf.find(3);
    assertThat(uf.size()).isEqualTo(5);
    uf.unify(1, 3);
    assertThat(uf.size()).isEqualTo(5);
    uf.find(2);
    uf.unify(4, 0);
    assertThat(uf.size()).isEqualTo(5);
  }

  @ParameterizedTest(name = "Size: {0}")
  @ValueSource(ints = {-1, -3463, 0})
  public void testBadUnionFindCreation(int size) {
    assertThrows(IllegalArgumentException.class, () -> new UnionFind(size));
  }
}