[HaBo]

public void groupAllElements()
    {
        Integer v1;
        String v2;
        String v3;
        int key;
        
        for(int i=0; i<groupId; i++)
        {
            if(datensatz.containsKey(i))
            {
                ArrayList<Triple<Integer,String,String>> aElem1 = datensatz.get(i);
                
                if(i % 500 == 0)
                {
                    System.out.println("Group ID: " + i);
                }
                
                for(int j=0; j<aElem1.size(); j++)
                {
                    Triple<Integer,String,String> tElem1 = aElem1.get(j);
                    v1 = Tuple.get1(tElem1);
                    v2 = Tuple.get2(tElem1).trim();
                    v3 = Tuple.get3(tElem1).trim();
                    
                    Integer v1comp;
                    String v2comp;
                    String v3comp;
                    
                    for(int k=0; k<groupId; k++)
                    {
                        if(i != k)
                        {
                            if(datensatz.containsKey(k))
                            {
                                ArrayList<Triple<Integer,String,String>> aElem2 = datensatz.get(k);
                                
                                for(int l=0; l<aElem2.size(); l++)
                                {
                                    Triple<Integer,String,String> tElem2 = aElem2.get(l);
                                    v1comp = Tuple.get1(tElem2);
                                    v2comp = Tuple.get2(tElem2).trim();
                                    v3comp = Tuple.get3(tElem2).trim();
                                    
                                    if(v1 == v1comp ||
                                       v2 == v2comp ||
                                       v3 == v3comp)
                                    {
                                        key = k;
                                        
                                        // choose smaller key
                                        if(i<k)
                                        {
                                            datensatz.remove(k);
                                            aElem1.addAll(aElem2);
                                        } else
                                        {
                                            datensatz.remove(i);
                                            aElem2.addAll(aElem1);
                                        }
                                        
                                        System.out.println("Merged keys: " + i + " and " + k);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }        
    }

List meineTripel; // Liste aller Tripel

UnionFind uf = new UnionFind(); // Musst du schauen, wo man eine Implementierung herbekommt...
foreach (meineTripel as tripel) {
  uf.addPartition(tripel); // Zu Begin: Jedes Trupel hat eine eigene Partition
}
Hashtable Namen = new Hashtable();
Hashtable Essen = new Hashtable();
Hashtable Trinken = new Hashtable();

foreach (meineTripel as tripel) {
  if (Namen.get(tripel.name) != null) {
    Tripel otherTripel = Namen.get(tripel.name);
    uf.union(uf.find(tripel), uf.find(otherTripel)); // Finde die Repräsentanten der beiden Tripel und vereinige ihre Partitionen
  } else {
    Namen.put(tripel.name, tripel);
  }

  if (Essen.get(tripel.essen) != null) {
    Tripel otherTripel = Essen.get(tripel.essen);
    uf.union(uf.find(tripel), uf.find(otherTripel));
  } else {
    Essen.put(tripel.essen, tripel);
  }

  if (Trinken.get(tripel.trinken) != null) {
    Tripel otherTripel = Trinken.get(tripel.trinken);
    uf.union(uf.find(tripel), uf.find(otherTripel));
  } else {
    Trinken.put(tripel.trinken, tripel);
  }
}

package partition;

/* ==========================================
 * JGraphT : a free Java graph-theory library
 * ==========================================
 *
 * Project Info:  http://jgrapht.sourceforge.net/
 * Project Creator:  Barak Naveh (http://sourceforge.net/users/barak_naveh)
 *
 * (C) Copyright 2003-2010, by Barak Naveh and Contributors.
 *
 * This library is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or
 * (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
 * License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library; if not, write to the Free Software Foundation,
 * Inc.,
 * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
 */
/* -------------------------
 * UnionFind.java
 * -------------------------
 * (C) Copyright 2010-2010, by Tom Conerly and Contributors.
 *
 * Original Author:  Tom Conerly
 * Contributor(s):
 *
 * Changes
 * -------
 * 02-Feb-2010 : Initial revision (TC);
 *
 */

import java.util.*;


/**
 * An implementation of <a
 * href="http://en.wikipedia.org/wiki/Disjoint-set_data_structure">Union
 * Find</a> data structure. Union Find is a disjoint-set data structure. It
 * supports two operations: finding the set a specific element is in, and
 * merging two sets. The implementation uses union by rank and path compression
 * to achieve an amortized cost of O(a(n)) per operation where a is the inverse
 * Ackermann function. UnionFind uses the hashCode and equals method of the
 * elements it operates on.
 *
 * @author Tom Conerly
 * @since Feb 10, 2010
 */
public class UnionFind<E>
{
    //~ Instance fields --------------------------------------------------------

    protected Map<E, E> parentMap;
    protected Map<E, Integer> rankMap;
    protected int totalBlocks;


    //~ Constructors -----------------------------------------------------------

    /**
     * Creates a UnionFind instance with all of the elements of elements in
     * seperate sets.
     */
    public UnionFind(Set<E> elements)
    {
        parentMap = new HashMap<E, E>();
        rankMap = new HashMap<E, Integer>();
        totalBlocks = 0;
        
        for (E element : elements) {
            parentMap.put(element, element);
            rankMap.put(element, 0);
            totalBlocks++;
        }
    }
   
    /**
     * Creates a UnionFind instance without any initial elements
     */
    public UnionFind()
    {
        parentMap = new HashMap<E, E>();
        rankMap = new HashMap<E, Integer>();
        totalBlocks = 0;
    }

    //~ Methods ----------------------------------------------------------------

    public int getSizeParent()
    {
    	return parentMap.size();
    }
    
    public int getSizeRank()
    {
    	return rankMap.size();
    }
    
    public Map<E, E> getParentMap()
    {
    	return parentMap;
    }
    
    public Map<E, Integer> getRankMap()
    {
    	return rankMap;
    }
    
    /**
     * Adds a new element to the data structure in its own set.
     *
     * @param element The element to add.
     */
    public void addElement(E element)
    {
        parentMap.put(element, element);
        rankMap.put(element, 0);
    }

	/**
	 * Returns the representative element of the set that element is in.
	 *
	 * @param element The element to find.
	 *
	 * @return The element representing the set the element is in.
	 * @throws IllegalArgumentException if the given elements does not exist.
	 */
	public E find(E element)
	{
		if (!parentMap.containsKey(element)) {
			throw new IllegalArgumentException("label does not exist");
		}

		E parent = parentMap.get(element);
		if (parent.equals(element)) {
			return element;
		}

		E newParent = find(parent);
		parentMap.put(element, newParent);
		return newParent;
	}

	/**
	 * Merges the sets which contain label1 and label2.
	 *
	 * @param element1 The first element to union.
	 * @param element2 The second element to union.
	 * @throws IllegalArgumentException if one of the given elements does not exist.
	 */
	public void union(E element1, E element2)
	{
		if (!parentMap.containsKey(element1) || !parentMap.containsKey(element2))
		{
			throw new IllegalArgumentException("both elemtents must exist");
		}

		E parent1 = find(element1);
		E parent2 = find(element2);

		//check if the elements are already in the same set
		if (parent1.equals(parent2)) {
			return;
		}

		int rank1 = rankMap.get(parent1);
		int rank2 = rankMap.get(parent2);
		
		if (rank1 > rank2) {
			parentMap.put(parent2, parent1);
			totalBlocks--;
		} else if (rank1 < rank2) {
			parentMap.put(parent1, parent2);
			totalBlocks--;
		} else {
			parentMap.put(parent2, parent1);
			rankMap.put(parent1, rank1 + 1);
			totalBlocks--;
		}
	}
}

public void mergePartitions()
{
	Iterator<MeinTripel> it=liste.iterator();

	while(it.hasNext())
	{
	    MeinTripel mTripel = it.next();
            
            if(hId.get(mTripel.id) != null)
            {
            	MeinTripel otherTripel = hId.get(mTripel.id);
            	uf.union(uf.find(mTripel), uf.find(otherTripel));
            } else {
            	hId.put(mTripel.id, mTripel);
            }
            
            if(hStr1.get(mTripel.str1) != null)
            {
            	MeinTripel otherTripel = hStr1.get(mTripel.str1);
            	uf.union(uf.find(mTripel), uf.find(otherTripel));
            } else {
            	hStr1.put(mTripel.str1, mTripel);
            }
            
            if(hStr2.get(mTripel.str2) != null)
            {
            	MeinTripel otherTripel = hStr2.get(mTripel.str2);
            	uf.union(uf.find(mTripel), uf.find(otherTripel));
            } else {
            	hStr2.put(mTripel.str2, mTripel);
            }
	}
}