COP 3530 Section U03 Spring 2017 THE DISJOINT UNION CLASS ======================== I. The Problem -------------- Write the method public static boolean path( boolean c[][], int i, int j) that takes as input the adjacency matrix of an undirected graph with $n$ nodes, 0, 1, \ldots , n-1, and two nodes i, j in the graph. The method returns true if there is a path between i and j and false if there is no such path. We assume that always there is a path from a node to itself. You may use any data structure in the book. Try to write an efficient program. II. The Disjoint Set Class ------------------------- // The disjSets class from Data Structures and Algorithm Analysis // 3rd Edition by Mark Weiss. pp 335- public class DisjSets { // intitialize the discrete equivalence on s public DisjSets(int numElements) { s = new int[ numElements]; for (int i = 0; i < s.length; i++) s[i] = -1; } // return the representative of x public int find(int x) { if (s[x] < 0) return x; else return find(s[x]); } // the union of two sets using the height heuristic // we assume that roo1 != root2 // @param root1 is the root of set1 // @param root2 is the root of set2 public void union(int root1, int root2) { if (s[root2] < s[root1]) s[root1] = root2; // root 2 is deeper, make it the new root else { if (s[root1] == s[root2]) s[root1]--; // update height if the same s[root2] = root1; // make root1 the new root } } private int[] s; // the sets } III. The Driver and Several Methods ----------------------------------- import java.util.LinkedList; public class TestDisjointSets { /** * @param args the command line arguments */ public static void main(String[] args) { System.out.println("Test path"); System.out.println("=========\n\n"); boolean[][] m = new boolean[6][6]; m[2][3] = true; m[4][5] = true; m[0][1] = true; m[0][4] = true; System.out.println("0 is connected 5 is " + path(m,0,5)); System.out.println("1 is connected 5 is " + path(m,1,5)); System.out.println("0 is connected 3 is " + path(m,0,3)); System.out.println("0 is connected 0 is " + path(m,0,0)); // System.out.println("Now test the matrix connectivity"); for (int i = 0; i < m.length; i++) m[i][i] = true; m[3][2] = true; m[5][4] = true; m[1][0] = true; m[4][0] = true; System.out.println("0 is connected 5 is " + path2(m,0,5)); System.out.println("1 is connected 5 is " + path2(m,1,5)); System.out.println("0 is connected 3 is " + path2(m,0,3)); System.out.println("0 is connected 0 is " + path2(m,0,0)); // System.out.println("Now we test the 3rd approach"); System.out.println("0 is connected 5 is " + path3(m,0,5)); System.out.println("1 is connected 5 is " + path3(m,1,5)); System.out.println("0 is connected 3 is " + path3(m,0,3)); System.out.println("0 is connected 0 is " + path3(m,0,0)); System.out.println("Now we test the 4th approach"); System.out.println("0 is connected 5 is " + path4(m,0,5)); System.out.println("1 is connected 5 is " + path4(m,1,5)); System.out.println("0 is connected 3 is " + path4(m,0,3)); System.out.println("0 is connected 0 is " + path4(m,0,0)); } // print the connective componenets of a graph given by its connectivity matrix public static boolean path(boolean c[][], int i, int j) { int n = c.length; DisjSets components = new DisjSets(n); for (int k = 0; k < n-1; k++) for (int l = k+1; l < n; l++) if (c[k][l]) { int r1 = components.find(k); int r2 = components.find(l); if (r1 != r2) components.union(r1,r2); } // see if i and j are in the same class return components.find(i) == components.find(j); } // the path predicate public static boolean path2(boolean[][] c, int i, int j) { // compute the connectivity matrix boolean[][] connect = new boolean[c.length][c.length]; copy(c,connect); for (int k = 2; k < c.length; k++) connect = multiply(connect,c); return connect[i][j]; } // copy two tables private static void copy( boolean[][] a, boolean[][] b) { for (int i = 0; i < a.length; i++ ) for (int j = 0; j < a[i].length; j++) b[i][j] = a[i][j]; } // multiply 2 square boolean matrices private static boolean[][] multiply(boolean[][] a, boolean[][] b) { boolean c[][] = new boolean[a.length][a.length]; for (int i = 0; i < a.length; i++) for (int j = 0; j < a.length; j++) { c[i][j] = false; for (int k = 0; k < a.length; k++) c[i][j] = c[i][j] || a[i][k] && b[k][j]; } return c; } // the 3rd approach public static boolean path3( boolean[][] c, int i, int j) { // d is the set of nodes reachable from i // copy line i in c boolean[] d = new boolean[c.length]; for (int k = 0; k < c.length; k++) d[k] = c[i][k]; int l = 2; while (l < c.length && !d[j]) // the path < c.length { for (int n = 0; n < c.length; n++) if ( !d[n]) // compute it { for (int m =0; m < d.length; m++) { if ( d[m] && c[m][n]) { d[n] = true; break; } } } l++; } return d[j]; } // use 2 inked lists, one for live nodes, the other for // dead ones public static boolean path4(boolean[][] c, int i, int j) { LinkedList dead = new LinkedList<>(); LinkedList live = new LinkedList<>(); // put i in the live nodes live.add(new Integer(i)); while ( ! live.isEmpty()) { int cur = live.removeFirst(); dead.add(new Integer(cur)); if (cur == j) return true; // find all children of i for (int k = 0; k < c.length; k++) { // generate all children of cur if (c[cur][k]) { // see if the child is dead Integer child = new Integer(k); if ( !dead.contains(child) && !live.contains(child)) live.add(child); } } } return false; // j was not found } // print a matrix private static void print(boolean[][] c) { for (int i =0; i < c.length; i++) { for (int j = 0; j < c.length; j++) System.out.print(c[i][j] + " "); System.out.println("\n"); } } IV. The Output: --------------- run: Test path ========= 0 is connected 5 is true 1 is connected 5 is true 0 is connected 3 is false 0 is connected 0 is true Now test the matrix connectivity 0 is connected 5 is true 1 is connected 5 is true 0 is connected 3 is false 0 is connected 0 is true Now we test the 3rd approach 0 is connected 5 is true 1 is connected 5 is true 0 is connected 3 is false 0 is connected 0 is true Now we test the 4th approach 0 is connected 5 is true 1 is connected 5 is true 0 is connected 3 is false 0 is connected 0 is true BUILD SUCCESSFUL (total time: 1 second)