/*
 *  graph.h 
 * 
 *  (c) 2004 Daniel Jackson. 
 *  CIS 11 Data Structures & Algorithms 
 * 
 
This class implements a directional weighted graph that allows loops, but not multiple edges. 
It is a template class, and data of the type of the template Item is stored in each vertex. 
The weights are non-negative integers. Each vertex is numbered, and is accessed by a std::size_t. 
To change the data of a vertex, access its reference via the [] operator, or set it when adding  
the vertex. 
 
Item must have a default constructor. The assignment operator must work correctly, as must the 
copy constructor. 
 
Constructors: 

  graph(std::size_t capacity = 20);
    Postcondition: The graph has been initialized with no vertices and no edges. It has the initial  
      capacity given by capacity, or 20 if none is specified. 
 
  graph& operator=(const graph& source);
    Postcondition: The source has been assigned to the left operand correctly. 
 
  graph(const graph& source);
    Postcondition: Creates a new graph, a correctly copied version of source. 
 
 
Mutators:

  void AddVertex(const Item& label); 
    Postcondition: The size of the graph has been increased by adding one new vertex. The vertex 
      has the specified label, and no edges. 
   
  void AddEdge(std::size_t source, std::size_t target, int newWeight); 
    Precondition: source < size() and target < size() and newWeight >= 0 
    Postcondition: The graph has all the edges it originally had, plus the specified edge from  
      source to target with weight. If that edge already existed, the weight has been changed. 
   
  void RemoveEdge(std::size_t source, std::size_t target); 
    Precondition: source < size() and target < size() 
    Postcondition: The graph has all of the edges it previously had, except the specified edge. 
      If that edge did not exist, the graph is unchanged. 
   
  void Resize(std::size_t newSize); 
    Postcondition: The allocated size is changed to newSize, unless newSize < size(), then newSize=size() 
   
  Item& operator[] (std::size_t vertex); 
    Precondition: vertex < size() 
    Postcondition: The return value is a reference to the data in the specified vertex. 
 
 
Accessors:

  std::size_t size() const 
    Postcondition: The return value is the number of vertices in the graph. 
   
  bool IsEdge(std::size_t source, std::size_t target) const 
    Precondition: source < size() and target < size() 
    Postcondtion: True if the edge exists, False otherwise. 
   
  std::set<std::size_t> Neighbors(std::size_t vertex) const 
    Precondition: vertex < size() 
    Postcondition: The return value is a set containing the vertex numbers of vertices that 
      are the target of an edge whose source is at the specified vertex. 
   
  Item operator[](std::size_t vertex) const 
    Precondition: vertex < size() 
    Postcondition: The return value is a reference to the data of the specified vertex. 
    NOTE: This function differs from the other because it returns a copy of the Item, not 
      a reference to the Item. It is a const function because it does not change the Item. 
   
  int EdgeWeight(std::size_t source, std::size_t target) const 
    Precondition: source < size() and target < size() 
    Postcondition: The return value is the weight of the specified edge. If there is no edge, 
      the return value is -1. 
 
Value semantics:

  Assignments and the copy constructor may be used with graph<Item> objects. 
 
*/ 

#ifndef GRAPH_H
#define GRAPH_H
#include <cstdlib>   // provides size_t
#include <set>       // provides set 

struct weightedEdge {
  bool exists;
  int weight;
};

template <class Item>
class graph {
  public:
    graph(std::size_t capacity = 20);
    graph& operator=(const graph& source);
    graph(const graph& source);
    ~graph();
    void AddVertex(const Item& label);
    void AddEdge(std::size_t source, std::size_t target, int newWeight);
    void RemoveEdge(std::size_t source, std::size_t target);
    void Resize(std::size_t newSize);
    Item& operator[] (std::size_t vertex);
    std::size_t size() const {
      return numVertices; }
    bool IsEdge(std::size_t source, std::size_t target) const;
    std::set<std::size_t> Neighbors(std::size_t vertex) const;
    Item operator[](std::size_t vertex) const;
    int EdgeWeight(std::size_t source, std::size_t target) const;
  private:
    weightedEdge** edges;
    Item* data;
    std::size_t numVertices;
    std::size_t allocated;
};

#include "graph.cpp"
#endif