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

using namespace std;



class Graph {
 public:
  // Constructor just builds an empty graph
  Graph();
  // Destructor 
  ~Graph();

  // These are values returned by graph functions
  enum ErrorCode {OUT_OF_MEMORY, NOT_CONNECTED, INVALID_EDGE, SUCCESS};

  // Init must be called to tell the graph how many vertices it has -- just 
  // the constructor is not enough.  Can return OUT_OF_MEMORY or SUCCESS
  ErrorCode Init (int newNumVertices);
  
  // Build MST puts the MST into the tree passed in by reference.
  // Can return OUT_OF_MEMORY, NOT_CONNECTED, or SUCCESS
  ErrorCode BuildMST (Graph & tree);

  friend istream & operator>>(istream & input, Graph & graph);
  friend ostream & operator<<(ostream & input, const Graph & graph);

 private:

  // the value greater than any allowed weight
  const static int infinity;

  // AddEdge puts an edge into a graph.  weight must be less than infinity
  // and begin must not equal end and begin and end must be not out of bounds
  // Can return INVALID_EDGE, OUT_OF_MEMORY or SUCCESS
  ErrorCode AddEdge (int begin, int end, int weight);

  int **weights;
  int numVertices;
};