Difference between revisions of "CSC212 Union Find in Java"

From dftwiki3
Jump to: navigation, search
(Created page with "--~~~~ ---- =Version 1= <br /> ==Source== <br /> ::<source lang="java"> public class UnionFind { static int[] id = null; static int noVertices = 0; public static void in...")
 
(→‎Version 3)
 
(2 intermediate revisions by the same user not shown)
Line 105: Line 105:
 
index :  0  1  2  3  4  5  6  7  8  9  
 
index :  0  1  2  3  4  5  6  7  8  9  
 
Id    :  0  1  2  4  9  3  4  9  7  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
 +
 +
</source>
 +
<br />
 +
=Version 2: Fast=
 +
<br />
 +
==source ==
 +
<br />
 +
<source lang="java">
 +
 +
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();
 +
}
 +
 +
}
 +
 +
</source>
 +
<br />
 +
==Output==
 +
<br />
 +
<source lang="text">
 +
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
 +
 +
</source>
 +
<br />
 +
 +
=Version 3: Faster=
 +
<br />
 +
==source ==
 +
<br />
 +
<source lang="java">
 +
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();
 +
}
 +
 +
}
 +
 +
</source>
 +
<br />
 +
==Output==
 +
<br />
 +
<source lang="text">
 +
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  
 
Size  :  1  1  1  2  2  2  2  2  2  1  
  

Latest revision as of 11:01, 25 November 2014

--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: Faster


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=24504"