#ifndef GRAPH_H
#define GRAPH_H

#include <vector>


// Class is parameterized by the types of structure used to hold
// information associated with vertices and edges.
// Vertices are referenced by an integer index between 0 and n-1;
// edges are referenced by a pair of vertex indices.
// The graph is undirected so (i, j) and (j, i) are the same edge.

template <class Vertex, class Edge>
class graph
{
public:

  graph(int sz = 0)
  {
    std::vector<Edge *> new_row;
    int i;
    for (i=0; i < sz; ++i)
    {
      new_row.push_back(0);
      vertices.push_back(Vertex());
    }
    for (i=0; i < sz; ++i)
      matrix.push_back(new_row);
  }

  int vsize() { return vertices.size(); }

  Vertex & vertex(int i) { return vertices[i]; }

  bool exists(int u, int v) { return matrix[u][v]; }

  Edge & edge(int i, int j) { return *matrix[i][j]; }

  void add_edge(Edge & e, int i, int j) {
    if (!matrix[i][j])
    {
      matrix[i][j] = new Edge();
      matrix[j][i] = new Edge();
    }
    *matrix[i][j] = e;
    *matrix[j][i] = e;
  }

private:
  
  std::vector<std::vector<Edge *> > matrix;
  std::vector<Vertex> vertices;
};


#endif