Re: [jgrapht-users] Connected Component Labeling with union find datastructure

[John V. S. <js...@gm...>]

Thanks Andre.  For connected components specifically of graphs, we 
already have ConnectivityInspector, but if someone needs the generic 
connected component labeling via union-find as a helper algorithm in 
some new class, they can incorporate the code you posted here.

JVS

André wrote:
> I extended the existing UnionFind class to use it for the labeling of
> connected components.
> 
> Therefore I made the two maps visible for subclasses and added an empty
> constructor.
> 
> As I can not decide if such an extension is useful for jgrapht I'll post my
> code here for anybody who might have similar needs:
> 
> /**
>  * Supports the creation of the classical two-pass algorithm for finding
> connected components.
>  * An example of this algorithm for the application in image systems can be
> found here:
>  *  http://en.wikipedia.org/wiki/Connected_Component_Labeling Wikipedia
> Connected Component Labeling 
>  * 
>  * The implementation uses an <code>UnionFind</code> data structure. 
>  * @author André Kreienbring
>  * @since Apr 17, 2010
>  */
> public class ComponentConnector<E> extends UnionFind<E>{
> 
> 	/**
> 	 * Creates an instance with all of the elements in
> 	 * separate sets.
> 	 * @param elements	A <code>Set</code> of elements
> 	 */
> 	public ComponentConnector(Set<E> elements)
> 	{
> 		super(elements);
> 	}
> 	
>     /**
>      * Creates an instance without any initial elements
>      */
> 	public ComponentConnector(){
> 		super();
> 	}
> 
> 	/**
> 	 * Finds the label of the smallest element from the list of given elements
> and then
> 	 * labels the given element with this label.
> 	 * 
> 	 * After that all other elements from the list are united with the minimum
> element.
> 	 * @param element	This element is labeled with the minimum label from the
> connected elements
> 	 * @param connectedElements	A <code>List</code> of elements that are
> connected with the given element.
> 	 */
> 	public void uniteConnected(E element, List<E> connectedElements){
> 		//assign the current pixel to the minimum label
> 		E minElement = getMinimumLabel(connectedElements);
> 		this.setLabel(element, minElement);
> 
> 		//unite the non-minimum labels
> 		for(E label : connectedElements){
> 			if(label != minElement){
> 				super.union(minElement, label);
> 			}
> 		}
> 	}
> 
> 	/**
> 	 * Get an iterator over all elements that were added before.
> 	 * It is intended that find() is called for every key to get it's
> representing element.
> 	 * Keys with the same representing element belong to the same component.
> 	 * @return	An iterator that can be used to iterate over all elements.
> 	 */
> 	public Iterator<E> iterator(){
> 		return super.parentMap.keySet().iterator();
> 	}
> 
> 
> 	/**
> 	 * Associate (connect) element1 with element2.
> 	 * Before the two elements are connected the upmost parent from element2 is
> looked up to keep the tree structure flat.
> 	 * If element1 is not in the internal set, then it is created.
> 	 * @param element1	The element that is connected to element2
> 	 * @param element2	element1 is connected to this element.
> 	 * @throws IllegalArgumentException if element2 does not exist.
> 	 */
> 	private void setLabel(E element1, E element2){
> 		if(!super.parentMap.containsKey(element2)){
> 			throw new IllegalArgumentException("parent label does not exist");
> 		}
> 		
> 		//try to find the parent of the new parent for a flat structure
> 		E parent = find(element2);
> 		
> 		//return if the element equals the actual parent
> 		if(element1.equals(parent) ||
> element1.equals(super.parentMap.get(parent))){
> 			return;
> 		}
> 		
> 		//remove the element if it exists
> 		if(super.parentMap.containsKey(element1)){
> 			super.parentMap.remove(element1);
> 			super.rankMap.remove(element1);
> 		}
> 		
> 		//and put it back in the list while maintaining the rank.
> 		int rank = super.rankMap.get(parent);
> 		super.parentMap.put(element1, parent);
> 		super.rankMap.put(element1, rank + 1);
> 	}
> 
> 	
> 	/**
> 	 * Given a list of elements this method finds the one with the lowest rank
> 	 * @param elements	A <code>List</code> of Elements
> 	 * @return	The element with the lowest rank
> 	 */
> 	private E getMinimumLabel(List<E> elements){
> 		int minimum = Integer.MAX_VALUE;
> 		E minElement = null;
> 		for(E element : elements){
> 			int rank = super.rankMap.get(element);
> 			
> 			if(rank < minimum){
> 				minimum = rank;
> 				minElement = element;
> 			}
> 		}
> 
> 		return minElement;
> 	}
> 
> }
> André wrote:
>> Ok... found it.
>>
>> I just got the latest version from trunk and there it is! 
>>
>> I'll check it out and report if it can be used for that component labeling
>> purpose.
>>
>> Thanks.
>>
>