Merge pull request TheAlgorithms#716 from MrYangxf/Development

yanglbme · web-flow · commit 822c91c13c78 · 2019-03-15T14:52:46.000+08:00
Add an implementation of disjoint-set
diff --git a/src/main/java/com/dataStructures/DisjointSet.java b/src/main/java/com/dataStructures/DisjointSet.java
@@ -0,0 +1,136 @@
+package src.main.java.com.dataStructures;
+
+import java.io.Serializable;
+import java.util.*;
+
+/**
+ * An implementation of disjoint-set, represented by rooted trees.
+ * <p>
+ * Actually, the instance of {@link DisjointSet} is a disjoint-set forests.
+ *
+ * <p>
+ * Disjoint-set operations:
+ * <p>
+ * 1. quickly unites two sets into a new set, requiring O(1) time.
+ * <p>
+ * 2. quickly query two elements whether contained in the same set, requiring about O(1) time.
+ *
+ * @author yangxf
+ */
+public class DisjointSet<T> implements Serializable {
+    private static final long serialVersionUID = 3134700471905625636L;
+
+    private Map<T, Node<T>> nodeMap = new HashMap<>();
+
+    /**
+     * Add an element to the disjoint-set forests as a set.
+     */
+    public void makeSet(T element) {
+        checkNotNull(element, "element");
+        nodeMap.putIfAbsent(element, new Node<>());
+    }
+
+    /**
+     * Unites the set that contains left and the set that contains right
+     * into a new set with the union-by-rank heuristic.
+     * <p>
+     * Rank is an upper bound on the height of node.
+     */
+    public void union(T left, T right) {
+        checkNotNull(left, "element");
+        checkNotNull(right, "element");
+
+        Node<T> leftNode = nodeMap.get(left),
+                rightNode = nodeMap.get(right);
+
+        if (leftNode == null) {
+            throw new NoSuchElementException(left.toString());
+        }
+
+        if (rightNode == null) {
+            throw new NoSuchElementException(right.toString());
+        }
+
+        Node<T> leftSet = findSet(leftNode),
+                rightSet = findSet(rightNode);
+
+        if (leftSet == rightSet) {
+            return;
+        }
+
+        if (leftSet.rank < rightSet.rank) {
+            leftSet.parent = rightSet;
+        } else {
+            rightSet.parent = leftSet;
+            if (leftSet.rank == rightSet.rank) {
+                leftSet.rank++;
+            }
+        }
+    }
+
+    /**
+     * Query two elements whether contained in the same set.
+     */
+    public boolean isConnected(T left, T right) {
+        if (left == null || right == null) {
+            return false;
+        }
+
+        Node<T> leftNode = nodeMap.get(left);
+        if (leftNode == null) {
+            return false;
+        }
+
+        Node<T> rightNode = nodeMap.get(right);
+        if (rightNode == null) {
+            return false;
+        }
+
+        if (leftNode == rightNode) {
+            return true;
+        }
+
+        return findSet(leftNode) == findSet(rightNode);
+    }
+
+    public Collection<Set<T>> toSets() {
+        Map<Node<T>, Set<T>> setMap = new HashMap<>();
+        for (Map.Entry<T, Node<T>> entry : nodeMap.entrySet()) {
+            setMap.computeIfAbsent(findSet(entry.getValue()), k -> new HashSet<>())
+                  .add(entry.getKey());
+        }
+        return setMap.values();
+    }
+
+    public void show() {
+        toSets().forEach(System.out::println);
+    }
+
+    /**
+     * Find the set that contains the node, actual is the first node of the set.
+     * <p>
+     * Backtracking with path compression.
+     */
+    private Node<T> findSet(Node<T> node) {
+        if (node != node.parent) {
+            node.parent = findSet(node.parent);
+        }
+        return node.parent;
+    }
+
+    private static void checkNotNull(Object obj, String msg) {
+        if (obj == null) {
+            throw new NullPointerException(msg + " must be not null");
+        }
+    }
+
+    static class Node<T> {
+        int rank;
+        Node<T> parent;
+
+        Node() {
+            parent = this;
+        }
+    }
+
+}
diff --git a/src/test/java/com/dataStructures/DisjointSetTest.java b/src/test/java/com/dataStructures/DisjointSetTest.java
@@ -0,0 +1,34 @@
+package src.test.java.com.dataStructures;
+
+import org.junit.Test;
+import src.main.java.com.dataStructures.DisjointSet;
+
+import static org.junit.Assert.*;
+
+public class DisjointSetTest {
+    @Test
+    public void test() {
+        DisjointSet<Object> set = new DisjointSet<>();
+
+        set.makeSet("flink");
+        set.makeSet("c++");
+        set.makeSet("java");
+        set.makeSet("py");
+        set.makeSet("spark");
+
+        set.union("java", "c++");
+
+        assertTrue(set.isConnected("java", "c++"));
+        assertFalse(set.isConnected("java", "py"));
+
+        set.union("c++", "py");
+        assertTrue(set.isConnected("java", "py"));
+
+        set.makeSet("lisp");
+        set.union("lisp", "py");
+
+        assertTrue(set.isConnected("c++", "lisp"));
+
+        set.show();
+    }
+}
