#ifndef WEIGHTED_GRAPH_H
#define WEIGHTED_GRAPH_H

#include <iostream>
#include <limits>
#include "Exception.h"

/*****************************************
 * UW User ID:  pagunnew
 * Submitted for ECE 250
 * Semester of Submission:  Winter 2011
 *
 * By submitting this file, I affirm that
 * I am the author of all modifications to
 * the provided code.
 *****************************************/

class Weighted_graph {
	private:
		static const double INF;
        int N; 		// number of vertices in the graph
        int num_of_edges;

		double **edges;	// 2D array to store the weight of the edges
        int *vertex_degree;
        bool *visited;
        double *distance;

	public:
		Weighted_graph( int = 50 );
		~Weighted_graph();

		int degree( int ) const;
		int edge_count() const;
		double adjacent( int, int ) const;
		double minimum_spanning_tree( int ) const;
		bool is_connected() const;

		void insert( int, int, double );

	// Friends

	friend std::ostream &operator << ( std::ostream &, const Weighted_graph & );
};

Weighted_graph::Weighted_graph( int n ){
    // Set graph size
    N = n;

    // Initalize the number of edges
    num_of_edges = 0;

    // Create arrays to hold the degree of the vertexes, if the verticies have been visited and the min distance
    vertex_degree = new int[N];
    visited = new bool[N];
    distance = new double[N];

    // allocate an array of size N, of type pointer to bool
    edges = new double *[N];

    // allocate and initialize an N-by-N array of type bool
    for ( int i = 0; i < N; i++ ) {
        edges[i] = new double[N];
        vertex_degree[i] = 0;

        for ( int j=0; j < N; j++ ) {
            edges[i][j] = 0;
       }
    }
}

Weighted_graph::~Weighted_graph() {
    // delete each array
    for ( int i = 0; i < N; i++ ) {
        delete [] edges[i];
    }

    // delete the arrays of pointers
    delete [] edges;
    delete [] vertex_degree;
    delete [] visited;
    delete [] distance;
}

int Weighted_graph::degree(int n) const {
    // Returns the degree of the vertex n.
    // Throw an illegal argument exception if the argument does not correspond to an existing vertex.
    if(n < 0 || n >= N)
    {
        throw illegal_argument();
    }
    else
    {
        return vertex_degree[n];
    }
}

int Weighted_graph::edge_count() const {
    // Returns the number of edges in the graph.
	return num_of_edges;
}

double Weighted_graph::adjacent(int m, int n) const {
    // Throw an illegal argument exception if the arguments do not correspond to existing vertices.
	if(m < 0 || m >= N || n < 0 || n >= N)
	{
	    throw illegal_argument();
	}
	//If the vertices are equal, return 0.
	if(m == n)
	{
	    return 0;
	}
	// If the vertices are not adjacent, return infinity.
	if(edges[m][n] == 0)
	{
	    return INF;
	}
	// Returns the weight of the edge connecting vertices m and n.
	else
	{
	    return edges[m][n];
	}
}

bool Weighted_graph::is_connected() const {
    // Determine if the graph is connected
    // Calling mst will update the visited array
	minimum_spanning_tree(0);
	// Make sure each vertex was visited
    for(int i = 0; i < N; i++)
    {
        if(visited[i] == false)
        {
            return false;
        }
    }
    return true;
}

double Weighted_graph::minimum_spanning_tree(int m) const {
    // Return the size of the minimum spanning tree of those nodes which are connected to vertex m.
    // Throw an illegal argument exception if the arguments do not correspond to existing vertices.
    if(m < 0 || m >= N)
    {
        throw illegal_argument();
    }
    else
    {
        // Set all the initial values of the table
        for(int i = 0; i < N; i++)
        {
            visited[i] = false;
            distance[i] = INF;
        }
        distance[m] = 0;
        int i = m;
        double mst = 0;

        // start at node m
        while(i != -1)
        {
            double min_distance = INF;
            visited[i] = true;
            mst = mst + distance[i];

            // Go through each node
            for(int j = 0; j < N; j++)
            {
                // Check to see if that node is connected to i
                if(edges[i][j] > 0)
                {
                    // Update the distance if it is shorter
                    if(edges[i][j] < distance[j])
                    {
                        distance[j] = edges[i][j];
                    }
                }
            }

            i = -1; // If i doesn't get changed below then there are no unvisited nodes
            // Find the path of shortest distance to go to next
            for(int k = 0; k < N; k++)
            {
                // Find the vertex with the shortest distance that hasn't been visited
                if(visited[k] == false && distance[k] < min_distance)
                {
                    min_distance = distance[k];
                    i = k;
                }
            }
        }
        return mst;
    }
}

void Weighted_graph::insert(int m, int n, double w) {
    // If the weight w < 0 or w = ∞, throw an illegal argument exception.
    if(w < 0 || w == INF)
    {
        throw illegal_argument();
    }
    // If the vertices do not exist or are equal, throw an illegal argument exception.
	if(m < 0 || m >= N || n < 0 || n >= N || n == m)
	{
	    throw illegal_argument();
	}
    // If the weight w is 0, remove any edge between m and n (if any).
    if(w == 0)
    {
        if(edges[m][n] != 0)
        {
            edges[m][n] = w;
            edges[n][m] = w;
            num_of_edges--;
            vertex_degree[m]--;
            vertex_degree[n]--;
        }
    }
    // If an edge already exists, just update the weight, not the degree or num of edges
    else if(edges[m][n] != 0)
    {
        edges[m][n] = w;
        edges[n][m] = w;
    }
    // If an edge doesn't exist add the weight as well as update the degree and num of edges
    else
    {
        edges[m][n] = w;
        edges[n][m] = w;
        num_of_edges++;
        vertex_degree[m]++;
        vertex_degree[n]++;
    }
}

std::ostream &operator << (std::ostream &out, const Weighted_graph &wg){
    return out;
}

const double Weighted_graph::INF = std::numeric_limits<double>::infinity();

#endif