Saturday, March 28, 2015

Diameter of a graph

So after last night's two posts, I decide to practice and write a code to calculate the diameter of a graph.

The graph is an undirected weighted graph (my same old Graph class), so the way I do it is use Dijkstra to calculate and get the maximum shortest distance from one node to all other nodes, and update the max shortest distance each time. The maximum shortest distance among all is the diameter.


public class Diameter {
 private Graph g;
 public Diameter(Graph g){
  this.g = g;
 }
 public double maxShortestDistance(Node n){
  g.chooseSource(n);
  PriorityQueue pq = new PriorityQueue(new NodeComparator());
  //Set visited = new HashSet ();
  pq.offer(n);
  double maxDist = 0.0;
  while(!pq.isEmpty()){
   Node curr = pq.poll();
   for(Node nei : g.neighbors.get(curr)){
    double distance = g.getEdge(curr.label, nei.label).weight + curr.dist;
    if(distance < nei.dist){
     pq.remove(nei);
     nei.dist = distance;
     pq.offer(nei);
     maxDist = Math.max(maxDist, distance);
    }
   }
  }
  return maxDist;
 }
 public double diameter(){
  double diameter = 0.0;
  for(Node v : g.vertices.values()){
   diameter = Math.max(diameter, maxShortestDistance(v));
  }
  return diameter;
 }
 private class NodeComparator implements Comparator{
  
  public int compare(Node a, Node b){
   if(a.dist - b.dist > 0)
    return 1;
   else if (a.dist - b.dist < 0)
    return -1;
   return 0;
  }
 }
}

No comments:

Post a Comment