// File: graph.cpp
// Solutions to HW6 Fall 2003 CS 112 B by Leo Reyzin
#include"graph.h"
#include<new>

const int Graph::infinity = numeric_limits<int>::max();

Graph::Graph() 
{
  weights=NULL;
  numVertices=0;
}

Graph::~Graph() 
{
  int i;
  if (weights!=NULL) {
    for (i=0; i<numVertices; i++)
      if (weights[i]!=NULL)
        delete [] weights[i];
    delete [] weights;
  }
}

Graph::ErrorCode Graph::Init (int newNumVertices)
{
  int i, j;

  // First free up old memory
  if (weights!=NULL) {
    for (i=0; i<numVertices; i++)
      if (weights[i]!=NULL)
        delete [] weights[i];
    delete [] weights;
  }

  // now allocate new memory
  numVertices = newNumVertices;
  weights = new int* [numVertices];
  if (weights == NULL) {
    numVertices = 0;
    return OUT_OF_MEMORY;
  }

  for (i=0; i<numVertices; i++) {
    weights[i]=new int [numVertices];
 
   if (weights[i] == NULL) {
     for (j=0; j<i; j++)
       delete [] weights[j];
     delete [] weights;
     return OUT_OF_MEMORY;
   }

   for (j=0; j<numVertices; j++)
     weights[i][j]=infinity;
  }
  return SUCCESS;
}

Graph::ErrorCode Graph::BuildMST(Graph& tree)
{
  int * bestDestination, * bestEdgeWeight;
  bool * covered;
  int i, j, minWeight, addedNode, destinationOfAddedNode;

  if (tree.Init(numVertices) != SUCCESS)
    return OUT_OF_MEMORY;

  covered = new (nothrow) bool [numVertices];
  bestDestination = new (nothrow) int [numVertices];
  bestEdgeWeight = new (nothrow) int [numVertices];
  if (covered == NULL || bestDestination == NULL || bestEdgeWeight == NULL) {
    if (covered != NULL)
      delete [] covered;
    if (bestDestination != NULL)
      delete [] bestDestination;
    if (bestEdgeWeight != NULL)
      delete [] bestEdgeWeight;
    return OUT_OF_MEMORY;
  }

  for (i=0; i<numVertices; i++) {
    covered[i] = false;
    bestDestination[i]=-1;
    bestEdgeWeight[i]=infinity;
  }

  covered[0]=true;
  addedNode=0;

  // This is the master loop -- iterates until all vertices are in the
  // graph or we can't find an edge to add -- meaning graph is disconnected
  for (i=1; i<numVertices; i++) {

    // Update all the not yet convered bestEdges: if the distance from
    // the current node to the most recently added node is less that
    // bestEdgeWeight, the replace bestEdge and bestEdgeWeight
    // cout << "updating best links arrays at locations:";
    for (j=1; j<numVertices; j++) {
      if (!covered[j] && bestEdgeWeight[j]>weights[j][addedNode]) {
        bestEdgeWeight[j]=weights[j][addedNode];
        bestDestination[j]=addedNode;
        // cout<<" " << j;
      }
    }

    // cout<<"\nBest edges: ";
    // Find the minimum-weight edge from uncovered to covered part
    minWeight=infinity;
    for (j=1; j<numVertices; j++) {
      //cout << bestDestination[j]<<","<<bestEdgeWeight[j] << " ";
      if (!covered[j] && bestEdgeWeight[j]<minWeight) {
	minWeight=bestEdgeWeight[j];
	addedNode=j;
	destinationOfAddedNode=bestDestination[j];
      }
    }
 
    // The above two loops can easily be combined into one, just left here
    // like this for simplicity.

    if (minWeight == infinity) {
      // The graph is disconnected, since no edge was found into the
      // covered part.  
      delete [] covered;
      delete [] bestDestination;
      delete [] bestEdgeWeight;
      return NOT_CONNECTED;
    }

    // Add the edge to the tree and mark it as covered
    // cout << "\nAdding Edge From " << addedNode << " To " 
    // << destinationOfAddedNode << " Weight " << minWeight;
    tree.AddEdge(addedNode, destinationOfAddedNode, minWeight);
    covered[addedNode]=true;
  }

  delete [] covered;
  delete [] bestDestination;
  delete [] bestEdgeWeight;
  return SUCCESS;
}

Graph::ErrorCode Graph::AddEdge(int begin, int end, int weight) 
{
  if (weight == infinity || begin==end || begin<0 || begin>=numVertices
      || end<0 || end>=numVertices)
    return INVALID_EDGE;
  weights[begin][end]=weights[end][begin]=weight;
  return SUCCESS;
}


ostream & operator<<(ostream & output, const Graph & graph) 
{
  int i, j;

  output << graph.numVertices << endl;

  for (i=0; i<graph.numVertices; i++)
    for (j=i; j<graph.numVertices; j++)
      if (graph.weights[i][j]!=Graph::infinity)
	output << i << " " << j << " " << graph.weights[i][j] << endl;
  return output;
}

istream & operator>>(istream & input, Graph & graph) 
{
  int i, j, w;

  input >> i;
  if (graph.Init(i)) {
    do {
      input >> i;
      input >> j;
      input >> w;
    } while (graph.AddEdge(i, j, w)==Graph::SUCCESS);
  }
  return input;
}