testing: improving test coverage DisjointSetUnionTest

TheAlgorithms · DenizAltunkapan · Jul 19, 2025 · Jul 16, 2025 · Jul 16, 2025 · Jul 18, 2025
commit 2e83877200fa35e7a7a577b05675ddae97062f29
@@ -1,8 +1,9 @@
 package com.thealgorithms.datastructures.disjointsetunion;
 
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertNotEquals;
 import static org.junit.jupiter.api.Assertions.assertNotNull;
 
-import org.junit.jupiter.api.Assertions;
 import org.junit.jupiter.api.Test;
 
 public class DisjointSetUnionTest {
@@ -12,7 +13,7 @@ public void testMakeSet() {
         DisjointSetUnion<Integer> dsu = new DisjointSetUnion<>();
         Node<Integer> node = dsu.makeSet(1);
         assertNotNull(node);
-        Assertions.assertEquals(node, node.parent);
+        assertEquals(node, node.parent);
     }
 
     @Test
@@ -33,19 +34,96 @@ public void testUnionFindSet() {
         Node<Integer> root3 = dsu.findSet(node3);
         Node<Integer> root4 = dsu.findSet(node4);
 
-        Assertions.assertEquals(node1, node1.parent);
-        Assertions.assertEquals(node1, node2.parent);
-        Assertions.assertEquals(node1, node3.parent);
-        Assertions.assertEquals(node1, node4.parent);
+        assertEquals(node1, node1.parent);
+        assertEquals(node1, node2.parent);
+        assertEquals(node1, node3.parent);
+        assertEquals(node1, node4.parent);
 
-        Assertions.assertEquals(node1, root1);
-        Assertions.assertEquals(node1, root2);
-        Assertions.assertEquals(node1, root3);
-        Assertions.assertEquals(node1, root4);
+        assertEquals(node1, root1);
+        assertEquals(node1, root2);
+        assertEquals(node1, root3);
+        assertEquals(node1, root4);
 
-        Assertions.assertEquals(1, node1.rank);
-        Assertions.assertEquals(0, node2.rank);
-        Assertions.assertEquals(0, node3.rank);
-        Assertions.assertEquals(0, node4.rank);
+        assertEquals(1, node1.rank);
+        assertEquals(0, node2.rank);
+        assertEquals(0, node3.rank);
+        assertEquals(0, node4.rank);
+    }
+
+    @Test
+    public void testFindSetOnSingleNode() {
+        DisjointSetUnion<String> dsu = new DisjointSetUnion<>();
+        Node<String> node = dsu.makeSet("A");
+        assertEquals(node, dsu.findSet(node));
+    }
+
+    @Test
+    public void testUnionAlreadyConnectedNodes() {
+        DisjointSetUnion<Integer> dsu = new DisjointSetUnion<>();
+        Node<Integer> node1 = dsu.makeSet(1);
+        Node<Integer> node2 = dsu.makeSet(2);
+        Node<Integer> node3 = dsu.makeSet(3);
+
+        dsu.unionSets(node1, node2);
+        dsu.unionSets(node2, node3);
+
+        // Union nodes that are already connected
+        dsu.unionSets(node1, node3);
+
+        // All should have the same root
+        Node<Integer> root = dsu.findSet(node1);
+        assertEquals(root, dsu.findSet(node2));
+        assertEquals(root, dsu.findSet(node3));
+    }
+
+    @Test
+    public void testRankIncrease() {
+        DisjointSetUnion<Integer> dsu = new DisjointSetUnion<>();
+        Node<Integer> node1 = dsu.makeSet(1);
+        Node<Integer> node2 = dsu.makeSet(2);
+        Node<Integer> node3 = dsu.makeSet(3);
+        Node<Integer> node4 = dsu.makeSet(4);
+
+        dsu.unionSets(node1, node2); // rank of node1 should increase
+        dsu.unionSets(node3, node4); // rank of node3 should increase
+        dsu.unionSets(node1, node3); // union two trees of same rank -> rank increases
+
+        assertEquals(2, dsu.findSet(node1).rank);
+    }
+
+    @Test
+    public void testMultipleMakeSets() {
+        DisjointSetUnion<Integer> dsu = new DisjointSetUnion<>();
+        Node<Integer> node1 = dsu.makeSet(1);
+        Node<Integer> node2 = dsu.makeSet(2);
+        Node<Integer> node3 = dsu.makeSet(3);
+
+        assertNotEquals(node1, node2);
+        assertNotEquals(node2, node3);
+        assertNotEquals(node1, node3);
+
+        assertEquals(node1, node1.parent);
+        assertEquals(node2, node2.parent);
+        assertEquals(node3, node3.parent);
+    }
+
+    @Test
+    public void testPathCompression() {
+        DisjointSetUnion<Integer> dsu = new DisjointSetUnion<>();
+        Node<Integer> node1 = dsu.makeSet(1);
+        Node<Integer> node2 = dsu.makeSet(2);
+        Node<Integer> node3 = dsu.makeSet(3);
+
+        dsu.unionSets(node1, node2);
+        dsu.unionSets(node2, node3);
+
+        // Before path compression, parent of node3 might not be node1 directly
+        Node<Integer> parentBefore = node3.parent;
+
+        // After findSet, path compression should update parent to root directly
+        Node<Integer> root = dsu.findSet(node3);
+        assertEquals(root, node1);
+        assertEquals(node1, node3.parent);
+        //assertNotEquals(parentBefore, node3.parent);
     }
 }