/************************************************************/
/* ADAPTED FROM:                                            */
/* http://www.cs.colorado.edu/~main/chapter15/graph.h       */
/*                                                          */
/* Main and Savitch, "Data Structures and Other Objects     */
/*    using C++", 2nd edition, Addison-Wesley, Ch.15,       */
/*    pp. 711-713                                           */
/************************************************************/

//-----------------------------------------------------------
// File: graph.h
// Name: Michael Main, Walter Savitch
//       (adapted by Sharon M. Tuttle)
// last modified: 4-27-05
//
// Template Class: graph<Item> (a graph where each vertex has
//                 a label of type Item; this label may be
//                 any of the C++ built-in types or any class
//                 with a default constructor and an assignment
//                 operator. The graph may not have multiple
//                 edges between two vertices.
//
// VALUE SEMANTICS for the graph<Item> template class:
//    Assignments and the copy constructor may be used 
//       with graph<Item> objects.
//
// DYNAMIC MEMORY USAGE by the graph<Item> template class:
//    If there is insufficient dynamic memory, then the
//       following functions throw bad_alloc:
//       constructor, the copy constructor, add_edge,
//       add_vertex, and the assignment operator. [I THINK]
//-----------------------------------------------------------

#ifndef GRAPH_H
#define GRAPH_H

#include <cstdlib>  // Provides NULL and  size_t
#include "node.h"  
#include "set.h"   
using namespace std;

template <typename Item>
class graph
{
    public:

        /******************************************************/
        /* TYPEDEFS and MEMBER CONSTANTS for the graph        */
        /*    class                                           */
        /******************************************************/

        // graph<Item>::MAXIMUM is the maximum number of
        //    vertices that a graph can have.
        //
        static const size_t MAXIMUM = 20;

        /****************************************************/
        /* CONSTRUCTORS and DESTRUCTOR                      */
        /****************************************************/

        // postcondition: initializes a graph with no vertices
        //    and no edges.
        //
        graph( );

        // copy constructor
        //
        graph(const graph<Item>& source);

        // destructor
        //
        ~graph( );

        /*******************************************************/
        /* ACCESSORS and other constant member functions       */
	/*    (observers)                                      */
        /*******************************************************/

        // postcondition: returns the number of vertices in
        //    the graph.
        //
        size_t get_num_vertices( ) const;

        // postcondition: returns the number of edges in the
        //    graph.
        //
        size_t get_num_edges( ) const;

        // postcondition: returns true if vert is the label of
        //    a vertex in this graph; returns false otherwise.
        //
        bool is_vertex(Item vert) const;

        // preconditions: is_vertex(source) == true,
        //                is_vertex(target) == true
        // postconditions: returns true if (source, target) is
        //    an edge in this graph, and returns false otherwise.
        //
        bool is_edge(Item source, Item target) const;

        // precondition: is_vertex(vert) == true
        // postcondition: returns a set containing all of the
        //    labels of vertices that are the target of an edge
        //    whose source is vert.
        //
        set<Item> get_neighbors(Item vert) const;

        // postcondition: prints the graph in the following
        //    form: first the set of vertices, then the edges
        //    between the vertices.
        //
        void print_graph( ) const;

        /****************************************************/
        /* MODIFIERS and other modifying member functions   */
        /****************************************************/

        // preconditions: num_vertices( ) < MAXIMUM,
        //                is_vertex(new_vert) == false
        // postconditions: the number of vertices in the graph 
        //    has been increased by adding vertex new_vert, which
        //    currently has no edges.
        //
        void add_vertex(const Item& new_vert);

        // preconditions: is_vertex(source) == true,
        //                is_vertex(target) == true
        // postconditions: if there was not an edge from
        //    source to target before, then there is, now
	//    (and the number of edges has been increased).
        //    (If there was an edge from source to target
        //    before, then the graph is unchanged.)
        //
        void add_edge(Item source, Item target);
        
        // preconditions: is_vertex(source) == true,
        //                is_vertex(target) == true
        // postconditions: if there was an edge from source
        //    target before, then it has now been removed
        //    (and the numberof edges has been decreased).
        //    (If there had not been an edge from source to
        //    target before, then the graph is unchanged.)
        //
        void remove_edge(Item source, Item target);

        /****************************************************/
        /* OVERLOADED OPERATORS                             */
        /****************************************************/
   
        // postcondition: the graph that activated this
        //    will be made to have the same vertices and
        //    edges as source
        //
        void operator =(const graph<Item>& source);

    private:
        node<Item> *adj_to_vertex[MAXIMUM]; // linked list of
                                            //    vertices adjacent
                                            //    to each vertex
        Item vertices[MAXIMUM];       // maps vertices to  
                                      //    adj_to_vertex indices 
        size_t total_vertices;        // current # of vertices
        size_t total_edges;           // current # of edges

        /****************************************************/
        /* PRIVATE HELPER MEMBER FUNCTIONS                  */
        /****************************************************/

        // precondition: is_vertex(vert) == true
        // postconditions: returns the index into adj_to_vert
        //    for vertex vert.
        //
        size_t get_vert_index(Item vert) const;

};

#include "graph.template" // Include the implementation 
#endif