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

[André <akr...@on...>]

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.
> 

-- 
View this message in context: http://n3.nabble.com/Connected-Component-Labeling-with-union-find-datastructure-tp721453p731535.html
Sent from the jgrapht-users mailing list archive at Nabble.com.