/*
    * Copyright (c) 2003, the JUNG Project and the Regents of the University 
    * of California
    * All rights reserved.
    *
    * This software is open-source under the BSD license; see either
    * "license.txt" or
    * http://jung.sourceforge.net/license.txt for a description.
    */
  package edu.uci.ics.jung.algorithms.layout;
  /*
   * This source is under the same license with JUNG.
   * http://jung.sourceforge.net/license.txt for a description.
   */
  
  import java.awt.Dimension;
  import java.awt.geom.Point2D;
  import java.util.ConcurrentModificationException;
  
  import edu.uci.ics.jung.algorithms.layout.util.RandomLocationTransformer;
  import edu.uci.ics.jung.algorithms.shortestpath.Distance;
  import edu.uci.ics.jung.algorithms.shortestpath.DistanceStatistics;
  import edu.uci.ics.jung.algorithms.shortestpath.UnweightedShortestPath;
  import edu.uci.ics.jung.algorithms.util.IterativeContext;
  import edu.uci.ics.jung.graph.Graph;
  
  /**
   * Implements the Kamada-Kawai algorithm for node layout.
   * Does not respect filter calls, and sometimes crashes when the view changes to it.
   *
   * @see "Tomihisa Kamada and Satoru Kawai: An algorithm for drawing general indirect graphs. Information Processing Letters 31(1):7-15, 1989" 
   * @see "Tomihisa Kamada: On visualization of abstract objects and relations. Ph.D. dissertation, Dept. of Information Science, Univ. of Tokyo, Dec. 1988."
   *
   * @author Masanori Harada
   */
  public class KKLayout<V,E> extends AbstractLayout<V,E> implements IterativeContext {
  
  	private double EPSILON = 0.1d;
  
  	private int currentIteration;
      private int maxIterations = 2000;
  	private String status = "KKLayout";
  
  	private double L;			// the ideal length of an edge
  	private double K = 1;		// arbitrary const number
  	private double[][] dm;     // distance matrix
  
  	private boolean adjustForGravity = true;
  	private boolean exchangeVertices = true;
  
  	private V[] vertices;
  	private Point2D[] xydata;
  
      /**
       * Retrieves graph distances between vertices of the visible graph
       */
      protected Distance<V> distance;
  
      /**
       * The diameter of the visible graph. In other words, the maximum over all pairs
       * of vertices of the length of the shortest path between a and bf the visible graph.
       */
  	protected double diameter;
  
      /**
       * A multiplicative factor which partly specifies the "preferred" length of an edge (L).
       */
      private double length_factor = 0.9;
  
      /**
       * A multiplicative factor which specifies the fraction of the graph's diameter to be 
       * used as the inter-vertex distance between disconnected vertices.
       */
      private double disconnected_multiplier = 0.5;
      
  	/**
  	 * Creates an instance for the specified graph.
  	 */
  	public KKLayout(Graph<V,E> g) 
      {
          this(g, new UnweightedShortestPath<V,E>(g));
  	}
  
  	/**
  	 * Creates an instance for the specified graph and distance metric.
  	 */
      public KKLayout(Graph<V,E> g, Distance<V> distance){
          super(g);
          this.distance = distance;
      }
  
      /**
       * Sets a multiplicative factor which 
       * partly specifies the "preferred" length of an edge (L).
       */
      public void setLengthFactor(double length_factor){
          this.length_factor = length_factor;
      }
      
     /**
      * Sets a multiplicative factor that specifies the fraction of the graph's diameter to be 
      * used as the inter-vertex distance between disconnected vertices.
      */
     public void setDisconnectedDistanceMultiplier(double disconnected_multiplier){
         this.disconnected_multiplier = disconnected_multiplier;
     }
     
     /**
      * Returns a string with information about the current status of the algorithm.
      */
 	public String getStatus() {
 		return status + this.getSize();
 	}
 
 	/**
 	 * Sets the maximum number of iterations.
 	 */
     public void setMaxIterations(int maxIterations) {
         this.maxIterations = maxIterations;
     }
 
 	/**
 	 * This one is an incremental visualization.
 	 */
 	public boolean isIncremental() {
 		return true;
 	}
 
 	/**
 	 * Returns true once the current iteration has passed the maximum count.
 	 */
 	public boolean done() {
 		if (currentIteration > maxIterations) {
 			return true;
 		}
 		return false;
 	}
 
 	@SuppressWarnings("unchecked")
     public void initialize() {
     	currentIteration = 0;
 
     	if(graph != null && size != null) {
 
         	double height = size.getHeight();
     		double width = size.getWidth();
 
     		int n = graph.getVertexCount();
     		dm = new double[n][n];
     		vertices = (V[])graph.getVertices().toArray();
     		xydata = new Point2D[n];
 
     		// assign IDs to all visible vertices
     		while(true) {
     			try {
     				int index = 0;
     				for(V v : graph.getVertices()) {
     					Point2D xyd = transform(v);
     					vertices[index] = v;
     					xydata[index] = xyd;
     					index++;
     				}
     				break;
     			} catch(ConcurrentModificationException cme) {}
     		}
 
     		diameter = DistanceStatistics.<V,E>diameter(graph, distance, true);
 
     		double L0 = Math.min(height, width);
     		L = (L0 / diameter) * length_factor;  // length_factor used to be hardcoded to 0.9
     		//L = 0.75 * Math.sqrt(height * width / n);
 
     		for (int i = 0; i < n - 1; i++) {
     			for (int j = i + 1; j < n; j++) {
     				Number d_ij = distance.getDistance(vertices[i], vertices[j]);
     				Number d_ji = distance.getDistance(vertices[j], vertices[i]);
     				double dist = diameter * disconnected_multiplier;
     				if (d_ij != null)
     					dist = Math.min(d_ij.doubleValue(), dist);
     				if (d_ji != null)
     					dist = Math.min(d_ji.doubleValue(), dist);
     				dm[i][j] = dm[j][i] = dist;
     			}
     		}
     	}
 	}
 
 	public void step() {
 		try {
 			currentIteration++;
 			double energy = calcEnergy();
 			status = "Kamada-Kawai V=" + getGraph().getVertexCount()
 			+ "(" + getGraph().getVertexCount() + ")"
 			+ " IT: " + currentIteration
 			+ " E=" + energy
 			;
 
 			int n = getGraph().getVertexCount();
 			if (n == 0)
 				return;
 
 			double maxDeltaM = 0;
 			int pm = -1;            // the node having max deltaM
 			for (int i = 0; i < n; i++) {
 				if (isLocked(vertices[i]))
 					continue;
 				double deltam = calcDeltaM(i);
 
 				if (maxDeltaM < deltam) {
 					maxDeltaM = deltam;
 					pm = i;
 				}
 			}
 			if (pm == -1)
 				return;
 
 			for (int i = 0; i < 100; i++) {
 				double[] dxy = calcDeltaXY(pm);
 				xydata[pm].setLocation(xydata[pm].getX()+dxy[0], xydata[pm].getY()+dxy[1]);
 
 				double deltam = calcDeltaM(pm);
 				if (deltam < EPSILON)
 					break;
 			}
 
 			if (adjustForGravity)
 				adjustForGravity();
 
 			if (exchangeVertices && maxDeltaM < EPSILON) {
 				energy = calcEnergy();
 				for (int i = 0; i < n - 1; i++) {
 					if (isLocked(vertices[i]))
 						continue;
 					for (int j = i + 1; j < n; j++) {
 						if (isLocked(vertices[j]))
 							continue;
 						double xenergy = calcEnergyIfExchanged(i, j);
 						if (energy > xenergy) {
 							double sx = xydata[i].getX();
 							double sy = xydata[i].getY();
 							xydata[i].setLocation(xydata[j]);
 							xydata[j].setLocation(sx, sy);
 							return;
 						}
 					}
 				}
 			}
 		}
 		finally {
 //			fireStateChanged();
 		}
 	}
 
 	/**
 	 * Shift all vertices so that the center of gravity is located at
 	 * the center of the screen.
 	 */
 	public void adjustForGravity() {
 		Dimension d = getSize();
 		double height = d.getHeight();
 		double width = d.getWidth();
 		double gx = 0;
 		double gy = 0;
 		for (int i = 0; i < xydata.length; i++) {
 			gx += xydata[i].getX();
 			gy += xydata[i].getY();
 		}
 		gx /= xydata.length;
 		gy /= xydata.length;
 		double diffx = width / 2 - gx;
 		double diffy = height / 2 - gy;
 		for (int i = 0; i < xydata.length; i++) {
             xydata[i].setLocation(xydata[i].getX()+diffx, xydata[i].getY()+diffy);
 		}
 	}
 
     /* (non-Javadoc)
 	 * @see edu.uci.ics.jung.visualization.layout.AbstractLayout#setSize(java.awt.Dimension)
 	 */
 	@Override
 	public void setSize(Dimension size) {
 		if(initialized == false)
 			setInitializer(new RandomLocationTransformer<V>(size));
 		super.setSize(size);
 	}
 
 	/**
 	 * Enable or disable gravity point adjusting.
 	 */
 	public void setAdjustForGravity(boolean on) {
 		adjustForGravity = on;
 	}
 
 	/**
 	 * Returns true if gravity point adjusting is enabled.
 	 */
 	public boolean getAdjustForGravity() {
 		return adjustForGravity;
 	}
 
 	/**
 	 * Enable or disable the local minimum escape technique by
 	 * exchanging vertices.
 	 */
 	public void setExchangeVertices(boolean on) {
 		exchangeVertices = on;
 	}
 
 	/**
 	 * Returns true if the local minimum escape technique by
 	 * exchanging vertices is enabled.
 	 */
 	public boolean getExchangeVertices() {
 		return exchangeVertices;
 	}
 
 	/**
 	 * Determines a step to new position of the vertex m.
 	 */
 	private double[] calcDeltaXY(int m) {
 		double dE_dxm = 0;
 		double dE_dym = 0;
 		double d2E_d2xm = 0;
 		double d2E_dxmdym = 0;
 		double d2E_dymdxm = 0;
 		double d2E_d2ym = 0;
 
 		for (int i = 0; i < vertices.length; i++) {
 			if (i != m) {
                 
                 double dist = dm[m][i];
 				double l_mi = L * dist;
 				double k_mi = K / (dist * dist);
 				double dx = xydata[m].getX() - xydata[i].getX();
 				double dy = xydata[m].getY() - xydata[i].getY();
 				double d = Math.sqrt(dx * dx + dy * dy);
 				double ddd = d * d * d;
 
 				dE_dxm += k_mi * (1 - l_mi / d) * dx;
 				dE_dym += k_mi * (1 - l_mi / d) * dy;
 				d2E_d2xm += k_mi * (1 - l_mi * dy * dy / ddd);
 				d2E_dxmdym += k_mi * l_mi * dx * dy / ddd;
 				d2E_d2ym += k_mi * (1 - l_mi * dx * dx / ddd);
 			}
 		}
 		// d2E_dymdxm equals to d2E_dxmdym.
 		d2E_dymdxm = d2E_dxmdym;
 
 		double denomi = d2E_d2xm * d2E_d2ym - d2E_dxmdym * d2E_dymdxm;
 		double deltaX = (d2E_dxmdym * dE_dym - d2E_d2ym * dE_dxm) / denomi;
 		double deltaY = (d2E_dymdxm * dE_dxm - d2E_d2xm * dE_dym) / denomi;
 		return new double[]{deltaX, deltaY};
 	}
 
 	/**
 	 * Calculates the gradient of energy function at the vertex m.
 	 */
 	private double calcDeltaM(int m) {
 		double dEdxm = 0;
 		double dEdym = 0;
 		for (int i = 0; i < vertices.length; i++) {
 			if (i != m) {
                 double dist = dm[m][i];
 				double l_mi = L * dist;
 				double k_mi = K / (dist * dist);
 
 				double dx = xydata[m].getX() - xydata[i].getX();
 				double dy = xydata[m].getY() - xydata[i].getY();
 				double d = Math.sqrt(dx * dx + dy * dy);
 
 				double common = k_mi * (1 - l_mi / d);
 				dEdxm += common * dx;
 				dEdym += common * dy;
 			}
 		}
 		return Math.sqrt(dEdxm * dEdxm + dEdym * dEdym);
 	}
 
 	/**
 	 * Calculates the energy function E.
 	 */
 	private double calcEnergy() {
 		double energy = 0;
 		for (int i = 0; i < vertices.length - 1; i++) {
 			for (int j = i + 1; j < vertices.length; j++) {
                 double dist = dm[i][j];
 				double l_ij = L * dist;
 				double k_ij = K / (dist * dist);
 				double dx = xydata[i].getX() - xydata[j].getX();
 				double dy = xydata[i].getY() - xydata[j].getY();
 				double d = Math.sqrt(dx * dx + dy * dy);
 
 
 				energy += k_ij / 2 * (dx * dx + dy * dy + l_ij * l_ij -
 									  2 * l_ij * d);
 			}
 		}
 		return energy;
 	}
 
 	/**
 	 * Calculates the energy function E as if positions of the
 	 * specified vertices are exchanged.
 	 */
 	private double calcEnergyIfExchanged(int p, int q) {
 		if (p >= q)
 			throw new RuntimeException("p should be < q");
 		double energy = 0;		// < 0
 		for (int i = 0; i < vertices.length - 1; i++) {
 			for (int j = i + 1; j < vertices.length; j++) {
 				int ii = i;
 				int jj = j;
 				if (i == p) ii = q;
 				if (j == q) jj = p;
 
                 double dist = dm[i][j];
 				double l_ij = L * dist;
 				double k_ij = K / (dist * dist);
 				double dx = xydata[ii].getX() - xydata[jj].getX();
 				double dy = xydata[ii].getY() - xydata[jj].getY();
 				double d = Math.sqrt(dx * dx + dy * dy);
 				
 				energy += k_ij / 2 * (dx * dx + dy * dy + l_ij * l_ij -
 									  2 * l_ij * d);
 			}
 		}
 		return energy;
 	}
 
 	public void reset() {
 		currentIteration = 0;
 	}
 }