/*********************************************************************
 *
 *  Nathan Balon
 *  Dinesh Thandapani
 *  CIS 350 
 *  Data Structures & Algorithms
 *  Winter 2005
 *  Univeristy of Michigan Dearborn
 *
 *  Save the Planet Problem
 *
 *  The program reads in the points that will be represented as vertices in
 *  a graph.  The program will then compute the minimum distance needed to 
 *  connect the vertices in the graph.  When the program complete the result
 *  will be displayed to the user.
 *
 *  Input:
 *
 *  All input to the program will come from the keyboard.  When the program 
 *  starts, the user will enter the number of vertices that are contained in
 *  the graph.  Then on each line the user will enter the the x and y 
 *  coordinates to be used for that vertex in the graph.  The program will
 *  terminate when the user enters a 0 for the number of vertices in the
 *  graph.
 *
 *  Sample Input:
 *      
 *      4
 *      4.0 4.0
 *      10.0 4.0
 *      4.0 6.0
 *      2.0 4.0
 *
 *  The Output generated by the input of above would be:
 *      
 *      10.0     
 *
 */ 

#include <iostream>
#include <vector>
#include <limits>
#include <iomanip>
#include<math.h>

using namespace std;


const double INF = numeric_limits<double>::max();        // INF used to represent infinity 
                                                         // when calc the spanning tree


/*                Global functions used by main                         */

int getNumberOfVertices();       // get the number of vertices contained in a graph 
                                 // from the user before creating the graph.

void displayHelp();                          // display how to run the program to the user
void validCoordinate(const double & coord);  // checks if the coordinate is valid


/*********************************************************************
 *  
 *  struct point stores the x and y coordinates of a point.
 *
 *********************************************************************/

struct Point{
    double x_;         // the x coordinate
    double y_;         // the y coordinate

    Point(int x, int y);
    Point();
};

Point::Point(){
    x_ = 0;
    y_ = 0;
}

Point::Point(int x, int y){
    x_ = x;
    y_ = y;
}

/**********************************************************************
 *  
 *  struct prim is used to hold the values needed to calculate the
 *  minimum spanning tree for the graph.
 *
 **********************************************************************/

struct Prim{
       int vNo;       // Vertex number 
       bool known;    // If vertex is visited true else false
       double dv;     //minimum  distance from source to destination
       int pv;        // source vertex number
};

/***********************************************************************
 *
 *  Class Graph is used to store all the vertices and edges(distance between
 * the vertices) in a graph using a adjacency Matrix.  The main purpose of the 
 * class is to store a graph of points containing x and y coordinates of
 * the points  and to compute the minimum spanning tree of the graph.  
 *
 * ********************************************************************/

class Graph{
    public:
        typedef vector <double> row;
        Graph(int noVertices);	
        void addVertex(Point p);
        void genAdjacencyMatrix();
        void displayGraph();
        void printAdjacencyMatrix();
        void primAlgorithm();
        void displayPrimTable();

    private:       	
	void displayDistance();
	void initializePrimTable();
	
        vector<Point> vertices_;   // the vertices contained in the graph  
        vector<row> adjMatrix;     // a complete graph of all points
        vector<Prim> primTable;    // table used to calculate the min spanning tree   
};


/**
 * Graph: creates an instance of a graph.
 * 
 * Precondition:  Resources are available to creates the object and
 *                the vertex objects contain in the vector have been
 *                properly initialized.
 * Postcondition: A graph object is created.  The graph will be created with the 
 *                number of vertices specified by the numberOfVertices argument. 
 */

Graph::Graph(int noVertices){
   adjMatrix.resize(noVertices);
   for(int i=0;i<noVertices;i++){
        for(int j=0;j<noVertices;j++)
            adjMatrix[i].push_back(0);
   }
}


/**
* displayGraph : Displays the vector of vertices entered by user
* Precondition : All co-ordinates should be given in the standard input.
* Postcondition : Displays the graph (Coordinates)
**/
void Graph::displayGraph(){
    cout<<"\nThe Generated graph is:";
    cout<<"\n-----------------------\n";
    for(int i=0;i<vertices_.size();i++)
        cout<<vertices_[i].x_<<"\t"<<vertices_[i].y_<<"\n";
}


/**
* genAdjacencyMatrix : Creates  the Adjacency Matrix of distance between the vertices
* Precondition : All the vertice co-ordinates should be entered in the standard input.
* Postcondition : Generates the Adjacency Matrix of Distance between the vertices
**/

void Graph::genAdjacencyMatrix(){
    for(int i=0;i<vertices_.size();i++)
        for(int k=i+1;k<vertices_.size();k++)
           adjMatrix[i][k]=adjMatrix[k][i]=sqrt(pow((vertices_[i].x_-vertices_[k].x_),2)
			                       +pow((vertices_[i].y_-vertices_[k].y_),2));        
}


/**
* printAdjacencyMatrix : Displays the Adjacency Matrix of distance between the vertices
* Precondition  : Adjacency Matrix of distances should be generated using genAdjacency matrix
* Postcondition : Prints the distance adjacency Matrix for checking.
**/

void Graph:: printAdjacencyMatrix(){
     cout<<"\nAdjacency Matrix:";
     cout<<"\n-----------------";
     for(int i=0;i<vertices_.size();i++){
         cout<<"\n";
         cout.precision(2);
         for(int k=0;k<vertices_.size();k++)
             cout<<"\t"<<adjMatrix[i][k];              
     } 
}


/**
 *  primAlgorithm: Determines the minimum spanning tree of the graph.
 *  
 *  precondition:  The method genAdjacencyMatrix must be called on the graph
 *                 object before calling primAlgorithm.
 *  postcondition: The minimum spanning tree of the graph will be determined
 *                 and the total cost of the graph will be displayed.
 */

void Graph::primAlgorithm(){
     bool continuePrimAlgorithm = true; // continue to run prims algorithm
     bool foundDist = false;            // used to indicate if a vertice is found that is unknown
     double dist = 0;                   // the distance between vertices 	  
     int smallestVert = 0;              // the number of the smallest vertice
    
     initializePrimTable();
     while(continuePrimAlgorithm){
	 foundDist = false;
	 dist = 0;
	 smallestVert = 0;
         // find the smallest distance in the table
         for(int i = 0; i < primTable.size(); i++){
            // find the first possible distance to use		 
            if(!foundDist && (primTable[i].known == false) && primTable[i].dv != INF){
	        smallestVert = i;
            dist = primTable[i].dv;
	        foundDist = true;
	     }    
	     // if a shorter distance is found use that distance
	     else if(primTable[i].dv < dist && primTable[i].dv != INF 
			                    && primTable[i].known == false){
                 dist = primTable[i].dv;
	         smallestVert = i;
	     }  
         }
	 continuePrimAlgorithm = foundDist;
	 if(continuePrimAlgorithm){
	     // set smallest dist to true
             primTable[smallestVert].known = true;
             // update the table of adjacent vertices 
             for(int i = 0; i < adjMatrix[smallestVert].size(); i++){
                 if(primTable[i].known == false){
                     if(adjMatrix[smallestVert][i] < primTable[i].dv){
			 primTable[i].dv = adjMatrix[smallestVert][i];
		         primTable[i].pv = smallestVert;
	             }
	         }
             } 
	 }
//       if(foundDist) displayPrimTable();
     }
     displayDistance();
}


/**
 *  intializePrimTable: intializes the data in the table used to determine the
 *  minimum spanning tree.
 *  
 *  Precondition:   None
 *  Postcondition:  The table used to determine the minimum spanning tree will be
 *                  initialized.
 *  Called by:      primAlgorithm
 */

void Graph::initializePrimTable(){
    for(int i = 0; i < vertices_.size(); i++){
	Prim tableEntry;    // entry to be added to the table
        tableEntry.vNo = i;
        tableEntry.known = false;
	if(i == 0){
	    tableEntry.dv = 0;
	} else {
	    tableEntry.dv = INF;
	}
	tableEntry.pv = 0;
	primTable.push_back(tableEntry);
    }
}


/**
 * displayPrimTable: displays the contents of the table used to calculate the
 * minimum spanning tree. Used to debug the program.
 * 
 * Precondition:  The function initializePrimTable must be called first so that
 *                the table contains valid values.
 * Postcondition: The values used to calculate the minimum spanning tree will be
 *                displayed.
 */

void Graph::displayPrimTable(){
    cout << "\n\nRPrim's Table\n"
         << "v       known   dv      pv\n"
         << "------------------------------\n";
    for(int i = 0; i < primTable.size(); i++){
        cout << primTable.at(i).vNo << "\t";
        if(primTable.at(i).known == false){
	   cout << "false" << "\t";
	}else{
	   cout << "true" << "\t";
	}
	if(primTable.at(i).dv == INF){
	    cout << "INF" << "\t";
	}else{
	    cout << primTable.at(i).dv << "\t";
	}
        cout << primTable.at(i).pv << endl;
    }
}


/**
 *  displayDistance: Display the total distance of the graph
 *  
 *  precondition:  The minimum spanning tree of the graph must be determined 
 *                 before calling.
 *  Postcondition: The cost of the minimum spanning tree is displayed
 *  called By:     primAlgorithm
 */

void Graph::displayDistance(){
    double totalDistance = 0;        // the total distance need to connect the points
    
    for(int i = 0; i < primTable.size(); i++){
        totalDistance += primTable[i].dv;
    }
    cout << std::showpoint << std::fixed << std::setprecision(1) << totalDistance << endl;
}


/**
*  addVertex: Add vertices to the graph
*  PreCondtion: Graph Object should be created and the Point Input should be got
*  PostCondition: Vertice is added in the Graph.
**/
void Graph::addVertex(Point p){
    vertices_.push_back(p);
}


/*******************************************************************************
 *
 *  Global functions used by main.
 *
 *******************************************************************************/


/**
 * getNumberOfVertices: gets the number of vertices in the graph from
 * standard input and checks that the number of vertices is even.
 * Precondition:  None.
 * Postcondition: Return the number of vertices the user has entered.
 *                If the user enters an odd number of vertices an error
 *                is displayed and the program is exited.
 */

int getNumberOfVertices(){
    int numberOfVertices = 0;         // the number of vertices to be  // contained in the graph
//    cout<<"\n Please enter the Number of vertices \t";                                  
    cin >> numberOfVertices;
    return numberOfVertices;
}


/**
 *  validCoordinate: checks that the coordinate is within a valid range.
 *  Precondition:  none
 *  Postcondition: if an invalid coordinate was entered an error will be
 *                 displayed and the program will terminate.
 */

void validCoordinate(const double & coord){
    if(coord > 100 || coord < 0){
        cerr << "invalid coordinate, the coordinate must be within the range 0.0 - 100.0\n";
	exit(1);
    }    
}


/**
 *  displayHelp: display help to the user to run the program.
 *  Precondition:  None
 *  Postcondition: the user will be display information concerning how
 *                 to run the program.
 */

void displayHelp(){
    cout << "To run the program enter the number of vertices contained in\n"
         << "the graph, followed by the x and y coordinates for each\n"
         << "vertice.  To end the program enter a 0 for the number of\n"
	 << "vertices.\n\nSample Input:\n"
	 << "4\n4.0 4.0\n10.0 4.0\n4.0 6.0\n2.0 4.0\n" << endl;
}


/*******************************************************************************
 *
 *  The main entry point to the program.
 *
 ******************************************************************************/


int main(int argc, char *argv[]){
    int numberOfVertices = 0;   // the number of vertices in the graph,
    double xCoord = 0;          // the x coordinate for the point
    double yCoord = 0;          // the y coordinate for the point
    Point point;                // the x and y coordinate of a point in the graph
    Graph * graph;              // the graph hold all points
    
    // display help to the user how to run the program
    if((argc == 2) && (argv[1][0] == '-') && (argv[1][1] == 'h')){
        displayHelp();
        exit(0);
    }  
    
    // read from standard input till a zero is found for the number of vertices
    while(numberOfVertices = getNumberOfVertices()){
	graph = new Graph(numberOfVertices);   
//  cout<<"\n Please enter the points for the vertices in the format X Y e.g: 1.0 1.1.\n";
	// read in each vertice
        for(int i = 1; i <= numberOfVertices; i++){
            cin >> xCoord;
	    cin >> yCoord;
	    validCoordinate(xCoord);    // check if valid
	    validCoordinate(yCoord);    // check if valid
	    point.x_ = xCoord;
	    point.y_ = yCoord;
	    graph->addVertex(point); 
	}
//	graph->displayGraph();
	graph->genAdjacencyMatrix();
//	graph->printAdjacencyMatrix();
	graph->primAlgorithm();
	delete graph;
    }	    
    return 0;
}