/* Graphs.java
 * =========================================================================
 * This file is part of the GrInvIn project - http://www.grinvin.org
 * 
 * Copyright (C) 2005-2008 Universiteit Gent
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or (at
 * your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 * 
 * A copy of the GNU General Public License can be found in the file
 * LICENSE.txt provided with the source distribution of this program (see
 * the META-INF directory in the source jar). This license can also be
 * found on the GNU website at http://www.gnu.org/licenses/gpl.html.
 * 
 * If you did not receive a copy of the GNU General Public License along
 * with this program, contact the lead developer, or write to the Free
 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
 * 02110-1301, USA.
 */

package org.grinvin.graphs;

import java.util.logging.Logger;

import org.grinvin.util.Tridiagonal;

/**
 * Provides some basic helper methods for graphs.<p>
 * Note that adjacency matrix, adjacency list and distance matrix can
 * also be obtained from the graph bundle directory, which may cache
 * their values.
 */
public final class Graphs {
    
    // do not instantiate this class
    private Graphs() {
    }
    
    
    /**
     * Returns a boolean adjacency matrix for the given graph. Row and column
     * indices correspond to vertex indices. Entries are {@code true}
     * when the corresponding vertices are adjacent (and different) and {@code false}
     * otherwise.
     * Note that the contents of this matrix are valid only for as long as the graph
     * given as a parameter remains unaltered.
     */
    public static boolean[][] booleanAdjacencyMatrix(GraphView graph) {
        int n = graph.getNumberOfVertices();
        boolean [][] adj = new boolean [n][n];
        for (Edge edge: graph.edges()) {
            int from = edge.getFirstEndpoint().getIndex();
            int to = edge.getSecondEndpoint().getIndex();
            adj[from][to] = true;
            adj[to][from] = true;
        }
        return adj;
    }
    
    /**
     * Returns the adjacency list representation for the given graph. The resulting array
     * contains an array of neighbour indices for every vertex. The length of each array is exactly
     * the valency of the corresponding vertex.
     */
    public static int[][] adjacencyList(GraphView graph) {
        // TODO: can this be done in a more memory efficient way?
        int n = graph.getNumberOfVertices();
        int[][] list = new int[n][n];
        int[] valency = new int[n];
        
        // compute
        for (Edge edge:  graph.edges()) {
            int from = edge.getFirstEndpoint().getIndex();
            int to = edge.getSecondEndpoint().getIndex();
            list[to][valency[to]++] = from;
            if (from != to)
                list[from][valency[from]++] = to;
        }
        // normalize
        for (int i = 0; i < n; i++) {
            int v = valency[i];
            int[] dest = new int[v];
            System.arraycopy(list[i], 0, dest, 0, v);
            list[i] =dest;
        }
        return list;
    }
    
    /**
     * Returns the distance matrix for the given graph. Row and column
     * indices correspond to vertex indices. Entries contains the distance
     * between corresponding vertices or 0 when vertices are equal or
     * belong to different components of the graph.
     */
    public static int[][] distanceMatrix(GraphView graph) {
        int n = graph.getNumberOfVertices();
        int[][] dist = new int[n][n];
        
        // compute the adjacency matrix
        for (Edge edge: graph.edges()) {
            int from = edge.getFirstEndpoint().getIndex();
            int to = edge.getSecondEndpoint().getIndex();
            dist[from][to] = 1;
            dist[to][from] = 1;
        }
        
        int d = 1;
        int count;
        do {
            int d1 = d++;
            count = 0;
            for (int i = 0; i < n; i++)
                for (int j = i + 1; j < n; j++)
                    if (dist[i][j] == 0)
                        for (int k = 0; k < n; k++)
                            if (dist[i][k] == 1 && dist[j][k] == d1) {
                dist[i][j] = d;
                dist[j][i] = d;
                count++;
                break;
                            }
        } while (count > 0);
        return dist;
    }
    
    /**
     * Returns the list of eigenvalues of the given graph. These are the eigenvalues
     * of the adjacency matrix of the graph. The resulting array contains the
     * eigenvalues in descending order.
     * If an error occurs during the calculation an array with length 0 is returned.
     */
    public static double[] eigenValues(GraphView graph) {
        int n = graph.getNumberOfVertices();
        if(n==0)
            return new double[0];
        double [][] adjMatrix = new double [n][n];
        for (Edge edge: graph.edges()) {
            int from = edge.getFirstEndpoint().getIndex();
            int to = edge.getSecondEndpoint().getIndex();
            adjMatrix[from][to]++;
            adjMatrix[to][from]++;
        }
        
        //compute
        Tridiagonal matrix = new Tridiagonal(adjMatrix);
        double[] eigenValues;
        try {
            eigenValues = matrix.eigenvalues();
        } catch(RuntimeException ex){
            Logger.getLogger("org.grinvin").warning("Error while computing the eigenvalues");
            eigenValues = new double[0];
        }
        
        // round
        // TODO: is this necessary?
        int precision = 10;
        for(int i=0; i < eigenValues.length; i++){
            for(int j=0; j < precision; j++)
                eigenValues[i] *= 10;
            eigenValues[i] = Math.round(eigenValues[i]);
            for(int j=0; j < precision; j++)
                eigenValues[i] /= 10;
        }
        
        //sort
        for(int i=0; i < eigenValues.length; i++)
            for(int j=eigenValues.length-1; j>i; j--)
                if(eigenValues[j] > eigenValues[j-1]){
            double tmp = eigenValues[j];
            eigenValues[j] = eigenValues[j-1];
            eigenValues[j-1] = tmp;
                }
        
        return eigenValues;
    }
    
    //
    private static final int[] DUMMY = new int[0];
    
    //
    private static final int[] DUMMY0 = new int[] {0};
    
    /**
     * Returns the list with eccentricities for the given graph. The resulting array
     * contains an integer for every vertex. If the graph is disconnected the array will
     * contain Integer.MAX_VALUE for every vertex.
     */
    public static int[] eccentricityList(GraphView graph) {
        int[][] distanceMatrix = distanceMatrix(graph);
        int n = graph.getNumberOfVertices();
        if (n == 0)
            return DUMMY;
        else if (n==1)
            return DUMMY0;
        
        int[] ecc = new int[n];
        for (int i=0; i < n; i++) {
            int eccentricity = 0;
            for (int j=0; j < n; j++) {
                int d = distanceMatrix[i][j];
                if (d == 0 && i!=j)
                    eccentricity=Integer.MAX_VALUE;
                if ( d > eccentricity)
                    eccentricity = d;
            }
            ecc[i]=eccentricity;
        }
        return ecc;
    }
}