Coding Recipies: Max Spacing for K-order Cluster

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

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

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(" } ");
 }

 
}

Coding Recipies

19 Sept 2013

Max Spacing for K-order Cluster

2 comments: