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}