001 /*--------------------------------------------------------------------------+ 002 $Id: UnionFind.java 26283 2010-02-18 11:18:57Z juergens $ 003 | | 004 | Copyright 2005-2010 Technische Universitaet Muenchen | 005 | | 006 | Licensed under the Apache License, Version 2.0 (the "License"); | 007 | you may not use this file except in compliance with the License. | 008 | You may obtain a copy of the License at | 009 | | 010 | http://www.apache.org/licenses/LICENSE-2.0 | 011 | | 012 | Unless required by applicable law or agreed to in writing, software | 013 | distributed under the License is distributed on an "AS IS" BASIS, | 014 | WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | 015 | See the License for the specific language governing permissions and | 016 | limitations under the License. | 017 +--------------------------------------------------------------------------*/ 018 package edu.tum.cs.commons.algo; 019 020 import edu.tum.cs.commons.collections.ManagedIntArray; 021 022 /** 023 * Implementation of a simple union find data structure. It implements the 024 * "partial path compression" heuristic but does not use "union by rank" but 025 * instead uses randomization. 026 * 027 * @author hummelb 028 * @author $Author: juergens $ 029 * @version $Rev: 26283 $ 030 * @levd.rating GREEN Hash: CF81A002CA0755AAD2BB6B1A6C75BA03 031 */ 032 public class UnionFind extends ManagedIntArray { 033 034 /** Finds and returns the representative for the given element. */ 035 public int find(int element) { 036 if (element >= size) { 037 throw new IllegalArgumentException("Unknown element!"); 038 } 039 040 while (element != array[element]) { 041 int next = array[element]; 042 array[element] = array[next]; 043 element = next; 044 } 045 046 return element; 047 } 048 049 /** 050 * Merges the classes in which element1 and element2 are, by giving them the 051 * same representative. 052 */ 053 public void union(int element1, int element2) { 054 if (element1 >= size || element2 >= size) { 055 throw new IllegalArgumentException("Unknown elements!"); 056 } 057 058 // locate representatives 059 element1 = find(element1); 060 element2 = find(element2); 061 062 if (element1 != element2) { 063 if (Math.random() > .5) { 064 connectToRepresentative(element1, element2); 065 } else { 066 connectToRepresentative(element2, element1); 067 } 068 } 069 } 070 071 /** 072 * Connects the given element (must also be representative) to the given 073 * representative. 074 */ 075 protected void connectToRepresentative(int element, int representative) { 076 array[element] = representative; 077 } 078 079 /** Adds a new element to this union find structure and returns its index. */ 080 public int addElement() { 081 int index = size; 082 addArrayElement(); 083 array[index] = index; 084 return index; 085 } 086 }