// Project 4 graph class.

#ifndef GRAPH_H
#define GRAPH_H


// 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);		// Argument is number of vertices in graph.
  int vsize();			// Return number of vertices.

  Vertex & vertex(int v);	// Return the data associated with vertex v.
  Edge & edge(int u, int v);	// Return the data assoc. with edge (u, v).
				// Note that (v, u) should return the same.

  void add_edge(Edge & e, int u, int v); // Add new edge (u, v) to graph.


  // This allows iterating over the vertices adjacent to a given vertex.

  friend class adjacent_iterator;
  class adjacent_iterator
  {
  public:
    friend class graph;
    adjacent_iterator();
    int operator*();		// Return the index of adjacent vertex.
    void operator++();		// Go to next adjacent vertex.
  };

  adjacent_iterator begin(int v); // "Begining" iterator for vertex v.
  adjacent_iterator end(int v);	  // "Ending" iterator for vertex v.

  Edge & edge(adjacent_iterator i); // Return adjacent edge.
};


#endif