// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): Elizabeth Johnson (Indiana University)

// This software is copyrighted by the DIMACS Center at Rutgers, The State
// University of New Jersey.  IT IS PROVIDED AS IS, AND THE AUTHORS, DIMACS, AND
// RUTGERS, THE STATE UNIVERSITY OF NEW JERSEY  DISCLAIM
// ALL LIABILITY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
// DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY
// DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.

// THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT.  THIS SOFTWARE
// IS PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE
// NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
// MODIFICATIONS.

// The authors hereby grant permission to use, copy, modify, distribute,
// and license this software and its documentation for any purpose, provided
// that existing copyright notices are retained in all copies and that this
// notice is included verbatim in any distributions. No written agreement,
// license, or royalty fee is required for any of the authorized uses.
// Modifications to this software may be copyrighted by their authors
// and need not follow the licensing terms described here, provided that
// the new terms are clearly indicated on the first page of each file where
// they apply.

// Last File Update: 31-Jul-1996
// 

#include <stdio.h>
#include <assert.h>
#include <LINK/graph/Graph.h>
#include <LINK/graph/Vertex.h>
#include <LINK/graph/Edge.h>
#include <LINK/graph/Attribute.h>
#include <LINK/basic/Matrix.h>

void 
initializeDistanceMatrix(Graph* graph, AsymMatrix<double>& distance_matrix)
{
    double weight;
    int i, j;
    int num_vertices = graph->order();
    for (i=0; i < num_vertices; i++) { 
        for (j=0; j < num_vertices; j++) { 
            if (i == j)
	        distance_matrix(i,j) = 0.0;
            else
	        distance_matrix(i,j) = LARGE_INT;
        }
    }

    Vertex** vertices = graph->vertexStart();
    for (int v=0; v < num_vertices; v++) {
        getAttribute((GraphObject*) vertices[v], "index", i);

	Set<Edge*> incident_edges = graph->outIncidentEdges(vertices[v]);
        Iterator<Edge*> getedge(&incident_edges);
        Edge* edge;
        while (getedge(edge)) {
            Vertex* otherVertex = edge->otherVertices(vertices[v]).first();
            getAttribute((GraphObject*) otherVertex, "index", j);
            int attOkay = getAttribute((GraphObject*) edge, "weight", weight);
            distance_matrix(i,j) = attOkay == LINK_OK ? weight:DEFAULT_WEIGHT;
        }
    }
    return;
}


void 
computeDistances(int num_vertices, AsymMatrix<double>& distance_matrix)
{
    for (int k=0; k < num_vertices; k++)
        for (int i=0; i < num_vertices; i++)
            for (int j=0; j < num_vertices; j++) {
	        double mindist = distance_matrix(i,k)+ distance_matrix(k,j);
	        if (mindist < distance_matrix(i,j)) 
	            distance_matrix(i,j) = mindist;
            }
}


AsymMatrix<double> 
FloydWarshall(Graph* graph, char *graph_view=0)
{
    // associate each vertex with a unique integer so we can index the matrices 
    Attribute<int> index_attr(graph, "index", 0);
    Vertex** vertices = graph->vertexStart();
    int num_vertices = graph->order();
    for (int i=0; i < num_vertices; i++)
        setAttribute((GraphObject*) vertices[i], "index", i);

    // distance matrix
    AsymMatrix<double> distance_matrix(num_vertices, num_vertices);
    initializeDistanceMatrix(graph, distance_matrix);

    computeDistances(num_vertices, distance_matrix);

    return distance_matrix;
}

// reusable distance matrix (pass-by-reference)
//
void FloydWarshall(Graph* graph, AsymMatrix<double> &D)
{
    int num_vertices = graph->order();

    assert(D.numRows()==num_vertices && D.numCols()==num_vertices);

    // associate each vertex with a unique integer so we can index the matrices 
    Attribute<int> index_attr(graph, "index", 0);
    Vertex** vertices = graph->vertexStart();
    for (int i=0; i < num_vertices; i++)
        setAttribute((GraphObject*) vertices[i], "index", i);

    initializeDistanceMatrix(graph, D);

    computeDistances(num_vertices, D);
}