CSC212 Union Find in Java

From dftwiki3
Revision as of 11:00, 25 November 2014 by Thiebaut (talk | contribs) (→‎Version 2)
Jump to: navigation, search

--D. Thiebaut (talk) 10:58, 25 November 2014 (EST)

Version 1


Source


public class UnionFind {
	static int[] id = null;
	static int noVertices = 0;
	
	public static void initQuickFind( int n ) {
		noVertices = n;
		id = new int[noVertices];		
		for ( int i=0; i<noVertices; i++ )
			id[i] = i;			
	}
	
	/**
	 * return Id of Vertex p (does not modify p)
	 * @param p: id of vertex we're interested in.
	 * @return Id of p
	 */
	public static int idOf( int p ) {
		while ( id[ p ] != p ) p = id[ p ];
		return p;
	}
	
	public static boolean quickFind( int p, int q ) {
		return idOf( p ) == idOf( q );
	}
	
	public static void quickUnite( int p, int q ) {
		int id_p = idOf( p );
		int id_q = idOf( q );
		if ( id_p == id_q ) return;
		id[ id_p ] = id_q;
	}
	
	public static void displayQF( String caption ) {
		System.out.println( "\nId array " + caption );
		for ( int i=0; i<noVertices; i++ )
			System.out.print( String.format( "%3d ", i ) );
		System.out.println();
		for ( int i=0; i<noVertices; i++ )
			System.out.print( String.format( "%3d ", id[i] ) );
		System.out.println();		
	}
	
	public static void displayIds( ) {
		for ( int i=0; i<noVertices; i++ )
			System.out.println( "Id of " + i + " = " + idOf( i ) );
	}
	
	public static void main(String[] args) {
		initQuickFind( 10 );
		
		quickUnite( 3, 5 );
		displayQF( "after adding 3-5" );

		quickUnite( 4, 6 );
		displayQF( "after adding 4-6" );

		quickUnite( 4, 3 );
		displayQF( "after adding 4-3" );
		
		quickUnite( 7, 8 );
		quickUnite( 9, 8 );
		displayQF( "after adding 7-8, 9-8" );
		
		quickUnite( 7, 3 );
		displayQF( "after adding 7-3" );
		displayIds();
	}

}


Output


after adding 3-5
index :   0   1   2   3   4   5   6   7   8   9 
Id    :   0   1   2   3   4   3   6   7   8   9 
Size  :   1   1   1   1   1   2   1   1   1   1 

after adding 4-6
index :   0   1   2   3   4   5   6   7   8   9 
Id    :   0   1   2   3   4   3   4   7   8   9 
Size  :   1   1   1   1   1   2   2   1   1   1 

after adding 4-3
index :   0   1   2   3   4   5   6   7   8   9 
Id    :   0   1   2   4   4   3   4   7   8   9 
Size  :   1   1   1   2   1   2   2   1   1   1 

after adding 7-8, 9-8
index :   0   1   2   3   4   5   6   7   8   9 
Id    :   0   1   2   4   4   3   4   9   7   9 
Size  :   1   1   1   2   1   2   2   2   2   1 

after adding 7-3
index :   0   1   2   3   4   5   6   7   8   9 
Id    :   0   1   2   4   9   3   4   9   7   9 
Size  :   1   1   1   2   2   2   2   2   2   1 

Id of 0 = 0
Id of 1 = 1
Id of 2 = 2
Id of 3 = 9
Id of 4 = 9
Id of 5 = 9
Id of 6 = 9
Id of 7 = 9
Id of 8 = 9
Id of 9 = 9


Version 2: Fast


source


public class UnionFindFast {
	static int[] id = null;
	static int[] size = null;
	static int noVertices = 0;
	
	public static void initQuickFind( int n ) {
		noVertices = n;
		id = new int[noVertices];		
		size = new int[noVertices];		
		for ( int i=0; i<noVertices; i++ ) {
			id[i] = i;			
			size[i] = 1;
		}
	}
	
	/**
	 * return Id of Vertex p (does not modify p)
	 * @param p: id of vertex we're interested in.
	 * @return Id of p
	 */
	public static int idOf( int p ) {
		while ( id[ p ] != p ) p = id[ p ];
		return p;
	}
	
	public static boolean quickFind( int p, int q ) {
		return idOf( p ) == idOf( q );
	}
	
	public static void quickUnite( int p, int q ) {
		int id_p = idOf( p );
		int id_q = idOf( q );

		if ( id_p == id_q )
			return;
		
		if ( size[ id_p ] < size[ id_q ] ) {
			id[id_p] = id_q;
			size[id_p] += size[id_q];
		}
		else {
			id[id_q] = id_p;
			size[id_q] += size[id_p];
		}		
	}
	
	public static void displayQF( String caption ) {
		System.out.println( caption );
		System.out.print( "index : " );
		for ( int i=0; i<noVertices; i++ )
			System.out.print( String.format( "%3d ", i ) );
		System.out.println();
		System.out.print( "Id    : " );
		for ( int i=0; i<noVertices; i++ )
			System.out.print( String.format( "%3d ", id[i] ) );
		System.out.println();		
		System.out.print( "Size  : " );
		for ( int i=0; i<noVertices; i++ )
			System.out.print( String.format( "%3d ", size[i] ) );
		System.out.println( "\n" );

	}
	
	public static void displayIds( ) {
		for ( int i=0; i<noVertices; i++ )
			System.out.println( "Id of " + i + " = " + idOf( i ) );
	}
	
	public static void main(String[] args) {
		initQuickFind( 10 );
		
		quickUnite( 3, 5 );
		displayQF( "after adding 3-5" );

		quickUnite( 4, 6 );
		displayQF( "after adding 4-6" );

		quickUnite( 4, 3 );
		displayQF( "after adding 4-3" );
		
		quickUnite( 7, 8 );
		quickUnite( 9, 8 );
		displayQF( "after adding 7-8, 9-8" );
		
		quickUnite( 7, 3 );
		displayQF( "after adding 7-3" );
		displayIds();
	}

}


Output


after adding 3-5
index :   0   1   2   3   4   5   6   7   8   9 
Id    :   0   1   2   3   4   3   6   7   8   9 
Size  :   1   1   1   1   1   2   1   1   1   1 

after adding 4-6
index :   0   1   2   3   4   5   6   7   8   9 
Id    :   0   1   2   3   4   3   4   7   8   9 
Size  :   1   1   1   1   1   2   2   1   1   1 

after adding 4-3
index :   0   1   2   3   4   5   6   7   8   9 
Id    :   0   1   2   4   4   3   4   7   8   9 
Size  :   1   1   1   2   1   2   2   1   1   1 

after adding 7-8, 9-8
index :   0   1   2   3   4   5   6   7   8   9 
Id    :   0   1   2   4   4   3   4   9   7   9 
Size  :   1   1   1   2   1   2   2   2   2   1 

after adding 7-3
index :   0   1   2   3   4   5   6   7   8   9 
Id    :   0   1   2   4   9   3   4   9   7   9 
Size  :   1   1   1   2   2   2   2   2   2   1 

Id of 0 = 0
Id of 1 = 1
Id of 2 = 2
Id of 3 = 9
Id of 4 = 9
Id of 5 = 9
Id of 6 = 9
Id of 7 = 9
Id of 8 = 9
Id of 9 = 9


Version 3


source


public class UnionFindFaster {
	static int[] id = null;
	static int[] size = null;
	static int noVertices = 0;

	public static void initQuickFind(int n) {
		noVertices = n;
		id = new int[noVertices];
		size = new int[noVertices];
		for (int i = 0; i < noVertices; i++) {
			id[i] = i;
			size[i] = 1;
		}
	}

	/**
	 * return Id of Vertex p (does not modify p)
	 * 
	 * @param p
	 *            : id of vertex we're interested in.
	 * @return Id of p
	 */
	public static int idOf(int p) {
		if (id[p] == p)
			return p;

		int root = idOf(id[p]);
		id[p] = root;
		return root;
	}

	public static boolean quickFind(int p, int q) {
		return idOf(p) == idOf(q);
	}

	public static void quickUnite(int p, int q) {
		int id_p = idOf(p);
		int id_q = idOf(q);

		if (id_p == id_q)
			return;

		if (size[id_p] < size[id_q]) {
			id[id_p] = id_q;
			size[id_p] += size[id_q];
		} else {
			id[id_q] = id_p;
			size[id_q] += size[id_p];
		}
	}

	public static void displayQF(String caption) {
		System.out.println(caption);
		System.out.print("index : ");
		for (int i = 0; i < noVertices; i++)
			System.out.print(String.format("%3d ", i));
		System.out.println();
		System.out.print("Id    : ");
		for (int i = 0; i < noVertices; i++)
			System.out.print(String.format("%3d ", id[i]));
		System.out.println();
		System.out.print("Size  : ");
		for (int i = 0; i < noVertices; i++)
			System.out.print(String.format("%3d ", size[i]));
		System.out.println("\n");

	}

	public static void displayIds() {
		for (int i = 0; i < noVertices; i++)
			System.out.println("Id of " + i + " = " + idOf(i));
	}

	public static void main(String[] args) {
		initQuickFind(10);

		quickUnite(3, 5);
		displayQF("after adding 3-5");

		quickUnite(4, 6);
		displayQF("after adding 4-6");

		quickUnite(4, 3);
		displayQF("after adding 4-3");

		quickUnite(7, 8);
		quickUnite(9, 8);
		displayQF("after adding 7-8, 9-8");

		quickUnite(7, 3);
		displayQF("after adding 7-3");
		
		idOf( 5 );
		displayQF("after id(5)");
		displayIds();
	}

}


Output


after adding 3-5
index :   0   1   2   3   4   5   6   7   8   9 
Id    :   0   1   2   3   4   3   6   7   8   9 
Size  :   1   1   1   1   1   2   1   1   1   1 

after adding 4-6
index :   0   1   2   3   4   5   6   7   8   9 
Id    :   0   1   2   3   4   3   4   7   8   9 
Size  :   1   1   1   1   1   2   2   1   1   1 

after adding 4-3
index :   0   1   2   3   4   5   6   7   8   9 
Id    :   0   1   2   4   4   3   4   7   8   9 
Size  :   1   1   1   2   1   2   2   1   1   1 

after adding 7-8, 9-8
index :   0   1   2   3   4   5   6   7   8   9 
Id    :   0   1   2   4   4   3   4   9   7   9 
Size  :   1   1   1   2   1   2   2   2   2   1 

after adding 7-3
index :   0   1   2   3   4   5   6   7   8   9 
Id    :   0   1   2   4   9   3   4   9   7   9 
Size  :   1   1   1   2   2   2   2   2   2   1 

after id(5)
index :   0   1   2   3   4   5   6   7   8   9 
Id    :   0   1   2   9   9   9   4   9   7   9 
Size  :   1   1   1   2   2   2   2   2   2   1 

Id of 0 = 0
Id of 1 = 1
Id of 2 = 2
Id of 3 = 9
Id of 4 = 9
Id of 5 = 9
Id of 6 = 9
Id of 7 = 9
Id of 8 = 9
Id of 9 = 9


Retrieved from "http://dominiquethiebaut.com/dftwiki3/index.php?title=CSC212_Union_Find_in_Java&oldid=24503"