1 /* Copyright (C) 2012 Gilleain Torrance <gilleain.torrance@gmail.com> 2 * 3 * Contact: cdk-devel@lists.sourceforge.net 4 * 5 * This program is free software; you can redistribute it and/or 6 * modify it under the terms of the GNU Lesser General Public License 7 * as published by the Free Software Foundation; either version 2.1 8 * of the License, or (at your option) any later version. 9 * All we ask is that proper credit is given for our work, which includes 10 * - but is not limited to - adding the above copyright notice to the beginning 11 * of your source code files, and to any copyright notice that you may distribute 12 * with programs based on this work. 13 * 14 * This program is distributed in the hope that it will be useful, 15 * but WITHOUT ANY WARRANTY; without even the implied warranty of 16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 * GNU Lesser General Public License for more details. 18 * 19 * You should have received a copy of the GNU Lesser General Public License 20 * along with this program; if not, write to the Free Software 21 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 22 */ 23 package org.openscience.cdk.group; 24 25 import java.util.Arrays; 26 27 28 /** 29 * Implementation of a union-find data structure, largely copied from 30 * code due to Derrick Stolee. 31 * 32 * @author maclean 33 * @cdk.module standard 34 * @cdk.keyword union-find 35 */ 36 public class DisjointSetForest { 37 38 /** 39 * The sets stored as pointers to their parents. The root of each 40 * set is stored as the negated size of the set - ie a set of size 41 * 5 with a root element 2 will mean forest[2] = -5. 42 */ 43 private int[] forest; 44 45 /** 46 * Initialize a disjoint set forest with a number of elements. 47 * 48 * @param numberOfElements the number of elements in the forest 49 */ DisjointSetForest(int numberOfElements)50 public DisjointSetForest(int numberOfElements) { 51 forest = new int[numberOfElements]; 52 for (int i = 0; i < numberOfElements; i++) { 53 forest[i] = -1; 54 } 55 } 56 57 /** 58 * Get the value of the forest at this index - note that this will <i>not</i> 59 * necessarily give the set for that element : use {@link #getSets} after 60 * union-ing elements. 61 * 62 * @param i the index in the forest 63 * @return the value at this index 64 */ get(int i)65 public int get(int i) { 66 return forest[i]; 67 } 68 69 /** 70 * Travel up the tree that this element is in, until the root of the set 71 * is found, and return that root. 72 * 73 * @param element the starting point 74 * @return the root of the set containing element 75 */ getRoot(int element)76 public int getRoot(int element) { 77 if (forest[element] < 0) { 78 return element; 79 } else { 80 return getRoot(forest[element]); 81 } 82 } 83 84 /** 85 * Union these two elements - in other words, put them in the same set. 86 * 87 * @param elementX an element 88 * @param elementY an element 89 */ makeUnion(int elementX, int elementY)90 public void makeUnion(int elementX, int elementY) { 91 int xRoot = getRoot(elementX); 92 int yRoot = getRoot(elementY); 93 94 if (xRoot == yRoot) { 95 return; 96 } 97 98 if (forest[xRoot] < forest[yRoot]) { 99 forest[yRoot] = forest[yRoot] + forest[xRoot]; 100 forest[xRoot] = yRoot; 101 } else { 102 forest[xRoot] = forest[xRoot] + forest[yRoot]; 103 forest[yRoot] = xRoot; 104 } 105 } 106 107 /** 108 * Retrieve the sets as 2D-array of ints. 109 * 110 * @return the sets 111 */ getSets()112 public int[][] getSets() { 113 int n = 0; 114 for (int i = 0; i < forest.length; i++) { 115 if (forest[i] < 0) { 116 n++; 117 } 118 } 119 int[][] sets = new int[n][]; 120 int currentSet = 0; 121 for (int i = 0; i < forest.length; i++) { 122 if (forest[i] < 0) { 123 int setSize = 1 - forest[i] - 1; 124 sets[currentSet] = new int[setSize]; 125 int currentIndex = 0; 126 for (int element = 0; element < forest.length; element++) { 127 if (getRoot(element) == i) { 128 sets[currentSet][currentIndex] = element; 129 currentIndex++; 130 } 131 } 132 currentSet++; 133 } 134 } 135 return sets; 136 } 137 138 @Override toString()139 public String toString() { 140 return Arrays.toString(forest); 141 } 142 143 } 144