Problem Statement:
Find maximum spacing of a K-clustering of the given Graph (in the given below eg. K=4)
Resultant Graph after K Clusters are formed:
Solution:
For solving this problem Kruskal Algorithm will be applied , which picks the minimum edges to connect to every vertex and finally in the end generates a MST , but in the process of picking up edges we need to ensure that no cycles are formed , and that we would use the UNION-FIND data structure. Here in this problem we will terminate the process of connecting vertices as soon as out K clusters are formed. Max space between the cluster will be given by the edge that would have actully
decreased the number of clusters to K-1.
File Name: KCluster.java
The UNION-FIND data structure Template class being used to avoid cycles in the MST.
The Union(int v1,v2) Operation merges two clusters keeping in mind that height of the tree is minimum.
The Find(int x) operation returns the Leader of the cluster in which ''x" resides.
File Name: UnionFind.java
Find maximum spacing of a K-clustering of the given Graph (in the given below eg. K=4)
Resultant Graph after K Clusters are formed:
Solution:
For solving this problem Kruskal Algorithm will be applied , which picks the minimum edges to connect to every vertex and finally in the end generates a MST , but in the process of picking up edges we need to ensure that no cycles are formed , and that we would use the UNION-FIND data structure. Here in this problem we will terminate the process of connecting vertices as soon as out K clusters are formed. Max space between the cluster will be given by the edge that would have actully
decreased the number of clusters to K-1.
File Name: KCluster.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 | import java.util.ArrayList; import java.util.Collections; import java.util.List; /** * Kruskal's Edge definition * @author Prateek * */ class Edge implements Comparable<Edge>{ int src; int dest; int weight; public Edge(int src,int dest,int weight) { this.src=src; this.dest=dest; this.weight=weight; } @Override public String toString() { return "Edge: "+src+ " - " + dest + " | " +" Weight: "+ weight; } @Override public int compareTo(Edge another) { return this.weight - another.weight; } } /** * problem statement: What is the maximum spacing of a K-clustering * @author r.prateek * */ public class KCluster { private int mNumVertices; // Number of vertices in the graph private int mNumEdges; // Number of edges in the graph private int maxClusterDistance; // for K cluster // Input Edge List private List<Edge> mEdgeList; public KCluster(int numVertices,int numEdges) { this.mNumVertices=numVertices; this.mNumEdges=numEdges; this.mEdgeList=new ArrayList<Edge>(mNumEdges); } public int getMaxSpacing(int clusterCount) { Collections.sort(mEdgeList); UnionFind uf=new UnionFind(mNumVertices); if(clusterCount > uf.getCount()) { try { throw new Exception("Cluster counter is lesser than input"); } catch (Exception e) { System.out.println(e.getMessage()); } } else { for(int i=0;i<mNumVertices;i++) { Edge edge=mEdgeList.get(i); // if parents do not match, consider edge list for MST and , union the two vertex if(!uf.isConnected(edge.src, edge.dest)) { if(uf.getCount()==clusterCount) { uf.printCluster1(); return maxClusterDistance=edge.weight; } int v1 = uf.Find(edge.src); //parent vertex for source int v2 = uf.Find(edge.dest); //parent vertex for destinition uf.Union(v1, v2); } } } return -1; } public static void main(String[] args) { KCluster graph=new KCluster(9, 13); graph.helper(); } public void helper() { mEdgeList.add(new Edge(1 ,2 ,4)); mEdgeList.add(new Edge(2 ,3 ,8)); mEdgeList.add(new Edge(3 ,4 ,7)); mEdgeList.add(new Edge(4 ,5 ,9)); mEdgeList.add(new Edge(5 ,6 ,10)); mEdgeList.add(new Edge(6 ,3 ,4)); mEdgeList.add(new Edge(6,7, 2)); mEdgeList.add(new Edge(7,8 ,1)); mEdgeList.add(new Edge(8 ,1, 8)); mEdgeList.add(new Edge(8 ,2 ,11)); mEdgeList.add(new Edge(8 ,0 ,7)); mEdgeList.add(new Edge(0 ,3 ,2)); mEdgeList.add(new Edge(0, 7 ,6)); int k=4; maxClusterDistance=getMaxSpacing(k); if(maxClusterDistance!=-1) System.out.println("Maximum Cluster Spacing for "+k + " cluster is "+maxClusterDistance); else System.out.println("Something went Wrong"); } } |
The UNION-FIND data structure Template class being used to avoid cycles in the MST.
The Union(int v1,v2) Operation merges two clusters keeping in mind that height of the tree is minimum.
The Find(int x) operation returns the Leader of the cluster in which ''x" resides.
File Name: UnionFind.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 | import java.util.ArrayList; import java.util.HashMap; import java.util.Iterator; import java.util.Map; import java.util.Map.Entry; import java.util.Set; /** * Union-Find DS node * @author Prateek * */ class UFNode { int parent; // parent of Vertex at i in the nodeHolder int rank; // Number of object present in the tree/ Cluster UFNode(int parent, int rank) { this.parent = parent; this.rank = rank; } } /** * Union-Find Data structure * @author Prateek * */ public class UnionFind { // Node Holder haveing UFNode private UFNode[] nodeHolder; int numVertices; // number of node (Cluster Count) private int count; public UnionFind(int size) { if (size < 0) throw new IllegalArgumentException(); count = size; numVertices=size; nodeHolder = new UFNode[size]; for (int i = 0; i < size; i++) { nodeHolder[i] = new UFNode(i, 1); // default values, node points to // itself and rank is 1 } } /** * Finds the parent of a given vertex, using recursion * * @param vertex * @return */ public int Find(int vertex) { if (vertex < 0 || vertex >= nodeHolder.length) throw new IndexOutOfBoundsException(); if (nodeHolder[vertex].parent != vertex) nodeHolder[vertex].parent = Find(nodeHolder[vertex].parent); return nodeHolder[vertex].parent; } /** * @return the cluster count */ public int getCount() { return count; } /** * @param v1 * : vertex 1 of some cluster * @param v2 * : vertex 2 of some cluster * @return true if both vertex have same parent */ public boolean isConnected(int v1, int v2) { return Find(v1) == Find(v2); } /** * unions two cluster of two vertices * @param v1 * @param v2 */ public void Union(int v1, int v2) { int i = Find(v1); int j = Find(v2); if (i == j) return; if (nodeHolder[i].rank < nodeHolder[j].rank) { nodeHolder[i].parent = j; nodeHolder[j].rank = nodeHolder[j].rank + nodeHolder[i].rank; } else { nodeHolder[j].parent = i; nodeHolder[i].rank = nodeHolder[i].rank + nodeHolder[j].rank; } count--; } public void printCluster1() { Map<Integer,ArrayList<Integer>> leaders=new HashMap<Integer, ArrayList<Integer>>(); for(int i=0;i<nodeHolder.length;i++) { leaders.put(nodeHolder[i].parent, null); } for(int i=0;i<numVertices;i++) { int leader=Find(i); ArrayList<Integer> leaderList=leaders.get(Find(i)); if(leaderList==null) { leaderList=new ArrayList<Integer>(); } leaderList.add(i); leaders.put(leader, leaderList); } Set<Map.Entry<Integer, ArrayList<Integer>>> set=leaders.entrySet(); printCluster2(set); } private void printCluster2(Set<Entry<Integer, ArrayList<Integer>>> set) { System.out.println("Following is the cluster"); System.out.println(" { "); for(Map.Entry<Integer, ArrayList<Integer>> entry: set) { int key=entry.getKey(); System.out.print(key + " :[ "); ArrayList<Integer> val=entry.getValue(); for(int i:val) { System.out.print(i + " ,"); } System.out.println( " ] "); } System.out.println(" } "); } } |
Nice Explaination !! Much Thanks !!
ReplyDeleteThis is great. Thank you.
ReplyDelete