001/*
002 * Copyright 2006 - 2013
003 *     Stefan Balev     <stefan.balev@graphstream-project.org>
004 *     Julien Baudry    <julien.baudry@graphstream-project.org>
005 *     Antoine Dutot    <antoine.dutot@graphstream-project.org>
006 *     Yoann Pigné      <yoann.pigne@graphstream-project.org>
007 *     Guilhelm Savin   <guilhelm.savin@graphstream-project.org>
008 * 
009 * This file is part of GraphStream <http://graphstream-project.org>.
010 * 
011 * GraphStream is a library whose purpose is to handle static or dynamic
012 * graph, create them from scratch, file or any source and display them.
013 * 
014 * This program is free software distributed under the terms of two licenses, the
015 * CeCILL-C license that fits European law, and the GNU Lesser General Public
016 * License. You can  use, modify and/ or redistribute the software under the terms
017 * of the CeCILL-C license as circulated by CEA, CNRS and INRIA at the following
018 * URL <http://www.cecill.info> or under the terms of the GNU LGPL as published by
019 * the Free Software Foundation, either version 3 of the License, or (at your
020 * option) any later version.
021 * 
022 * This program is distributed in the hope that it will be useful, but WITHOUT ANY
023 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
024 * PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more details.
025 * 
026 * You should have received a copy of the GNU Lesser General Public License
027 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
028 * 
029 * The fact that you are presently reading this means that you have had
030 * knowledge of the CeCILL-C and LGPL licenses and that you accept their terms.
031 */
032package org.graphstream.algorithm.util;
033
034import java.util.HashMap;
035import java.util.Map;
036
037/**
038 * <p>
039 * This data structure is used to maintain disjoint sets. It supports limited
040 * number of operations, but they are all executed in constant amortized time.
041 * The supported operations are:
042 * </p>
043 * <ul>
044 * <li>Adding a new set containing a single element</li>
045 * <li>Determining if two elements belong to the same set</li>
046 * <li>Union of the sets containing two elements</li>
047 * </ul>
048 * 
049 * <p>
050 * The space taken by this structure is O(n), where n is the number of elements.
051 * </p>
052 * 
053 * @param <E>
054 *            the type of the elements
055 */
056public class DisjointSets<E> {
057
058        /**
059         * Disjoint sets are represented as a forest. This class presents the tree
060         * node associated to each element.
061         */
062        protected static class Node {
063                Node parent;
064                int rank;
065
066                protected Node() {
067                        parent = this;
068                        rank = 0;
069                }
070
071                protected Node root() {
072                        if (this != parent)
073                                parent = parent.root();
074                        return parent;
075                }
076
077                protected boolean join(Node node) {
078                        Node x = root();
079                        Node y = node.root();
080                        if (x == y)
081                                return false;
082                        if (x.rank > y.rank)
083                                y.parent = x;
084                        else {
085                                x.parent = y;
086                                if (x.rank == y.rank)
087                                        y.rank++;
088                        }
089                        return true;
090                }
091        }
092
093        /**
094         * Correspondence between elements and nodes.
095         */
096        protected Map<E, Node> map;
097
098        /**
099         * Creates a new instance containing no sets and no elements
100         */
101        public DisjointSets() {
102                map = new HashMap<E, Node>();
103        }
104
105        /**
106         * Creates a new instance containing no sets and no elements. If the total
107         * number of elements to add is known in advance, this constructor is more
108         * efficient than the default.
109         * 
110         * @param initialCapacity
111         *            Initial capacity (in number of elements) of the structure. The
112         *            structure grows dynamically and new elements can be added even
113         *            if this capacity is exceeded.
114         */
115        public DisjointSets(int initialCapacity) {
116                map = new HashMap<E, Node>(4 * initialCapacity / 3 + 1);
117        }
118
119        /**
120         * Adds a new set containing only {@code e} to the structure. If {@code e}
121         * already belongs to some of the disjoint sets, nothing happens.
122         * 
123         * @param e
124         *            The element to add as a singleton
125         * @return True if the new set is added and false if {@code e} already
126         *         belongs to some set.
127         */
128        public boolean add(E e) {
129                Node x = map.get(e);
130                if (x != null)
131                        return false;
132                map.put(e, new Node());
133                return true;
134        }
135
136        /**
137         * Checks if two elements belong to the same set.
138         * 
139         * @param e1
140         *            An element
141         * @param e2
142         *            An element
143         * @return True if and only if belong to the same set. Note that if
144         *         {@code e1} or {@code e2} do not belong to any set, false is
145         *         returned.
146         */
147        public boolean inSameSet(Object e1, Object e2) {
148                Node x1 = map.get(e1);
149                if (x1 == null)
150                        return false;
151                Node x2 = map.get(e2);
152                if (x2 == null)
153                        return false;
154                return x1.root() == x2.root();
155        }
156
157        /**
158         * Union of the set containing {@code e1} and the set containing {@code e2}.
159         * After this operation {@code inSameSet(e1, e2)} will return true. If
160         * {@code e1} or {@code e2} do not belong to any set or if they already
161         * belong to the same set, nothing happens.
162         * 
163         * @param e1
164         *            An element
165         * @param e2
166         *            An element
167         * @return {@code true} if and only if {@code e1} and {@code e2} belong to different sets at the beginning
168         */
169        public boolean union(Object e1, Object e2) {
170                Node x1 = map.get(e1);
171                if (x1 == null)
172                        return false;
173                Node x2 = map.get(e2);
174                if (x2 == null)
175                        return false;
176                return x1.join(x2);
177        }
178
179        /**
180         * Checks if an element belongs to some of the disjoint sets.
181         * 
182         * @param e
183         *            An element
184         * @return True if {@code e} belongs to some set.
185         */
186        public boolean contains(Object e) {
187                return map.get(e) != null;
188        }
189
190        /**
191         * Reinitializes the structure. After this operation the structure contains
192         * no sets.
193         */
194        public void clear() {
195                for (Node node : map.values())
196                        node.parent = null;
197                map.clear();
198        }
199}