#ifndef _GRAPH_H
#define _GRAPH_H


#include <string>

#include "hmap.h"
#include "tvector.h"

/**
 * This Graph class uses an adjacency list representation
 * of a graph.  The lists of edges for a vertex are returned
 * to client programs in vectors rather than as linked lists
 *
 * All vertices are represented as strings.  Each string has
 * a corresponding number, and the relationship between
 * strings and numbers is obtained via functions:
 *
 *  o getNum(string) -- the number associated with a vertex string
 *  o getName(int)   -- the string associated with a number
 *
 *    Note: getName(getNum(s)) == s
 *    Time: getName and getNum are O(1) operations
 *
 * A list of vertices is accessible via getVertices
 * a copy of the names of all vertices is returned in a vector
 *
 * Similarly getAdjacent returns a list of vertices adjacent to
 * a named vertex. The names are returned, edges can be formed
 * in client programs from the names of 'to' vertices
 *
 * Edges are added using addEdge(from,to)  which adds a directed edge.
 * Similarly, addUndirectedEdge adds an undirected edge which is
 * simulated in this class by adding two edges from-&gt;to and
 * to-gt;from.
 *
 * Edges can be removed by calling removeEdge(from,to).
 *
 * All edges can be removed by calling clear() [which doesn't remove
 * vertices, but does remove all edges]
 *
 */

class Graph
{
  public:
    Graph();
    ~Graph();

    int  addVertex(const string& s);
    void addEdge(const string& from, const string& to);
    void addEdge(const string& from, const string& to, double weight);    
    void addUndirectedEdge(const string& from, const string& to);
    void addUndirectedEdge(const string& from,
			   const string& to, double weight);
    
    void removeEdge(const string& from, const string& to);
    
    int    getNum(const string& s) const;
    string getName(int index)      const;
    int    vertexSize()            const;
    int    edgeSize()            const;
    double getWeight(const string& from, const string& to) const;
    double getWeight(int from, int to)      const;
    bool hasEdge(const string& from, const string& to) const;
    
    void getVertices(tvector<string>& list) const;
    void getAdjacent(const string& vertex, tvector<string>& list) const;

    void clear();
    
    struct Vertex
    {
	string name;
	double weight;
	explicit Vertex(const string& s="")   // default
	    : name(s), weight(1.0)
	{ }
	Vertex(const string& s, double w)
	    : name(s), weight(w)
	{ }
	bool operator < (const Vertex& rhs) const
	{
	    return weight < rhs.weight;
	}
    };
    
  private:

    tvector<tvector<Vertex> > myAlist;
    HMap<int>                  myMap;
    int myVertexCount;
    int myEdgeCount;

    // disable copy/assignment
    Graph(const Graph& g);
    const Graph& operator = (const Graph& g);
};


#endif