/*
 * 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;
	}
}