// graph.h
// -- adjacency list representation of a weighted graph
//
 
#ifndef GRAPH_H
 
#define GRAPH_H
 
#include <string>
#include "queue.h"
using namespace std;
 
 
class FileOpenError                                 // Exception class -- cannot open input file
{
};
 
struct EdgeNode										// Structure representing an edge
{
  int			destination;						// Index of destination vertex
  int			weight;								// Edge weight
  EdgeNode*		nextPtr;							// Next edge pointer
};
 
struct VertexNode									// Structure representing a vertex
{
  string		vname;								// Name of vertex
  bool			mark;								// Marked flag
  EdgeNode*		edgePtr;							// Pointer to list of edges
};
 
 
class Graph											// Graph ADT using adjacency list representation
{
 private:		//***** Private class members below *****//
  VertexNode*	vertices;							// Array of vertex nodes
  int			numV;								// Number of vertices
 
 public:		//***** Public members below *****//
  Graph(int num);									// Constructor - creates graph with num vertices
  ~Graph();											// Destructor - deallocates all edge nodes and the vertex list
  void DeleteAllEdges();							// Deallocates all edge nodes from all vertices
  bool IsEmpty();									// Returns true if graph empty, false otherwise
  bool IsFull();									// Returns true if graph full, false otherwise
  void AddVertex(string v);							// Adds vertex to graph assuming vertex not already present
  void AddEdge(string s, string d, int w);	        // Adds edge from source S  to destination D with specified weight W
  int IndexIs(string v);							// Returns index of edge from S to D; -1 if not present
  int WeightIs(string s, string d);					// Returns weight of vertex V -- assumes V is in graph
  void GetToVertices(string s, Queue& q);			// Returns a queue Q of vertices adjacent to vertex V
  void ClearMarks();								// Clears vertex marks
  void MarkVertex(string v);						// Marks vertex V
  bool IsMarked(string v);							// Returns true if vertex V is marked, false otherwise
  void Print();										// Write graph to stdout
  Queue* DepthFirstSearch(string startVertex, string endVertex);  // Returns ptr to queue containing path or NULL if none
}; 
 
  void Load(string filename, Graph*& g, string& startVertex, string& endVertex);  	
  // Load graph from named file and values of start and end vertices
  // Note: this file attempts to open the named file for input and input all information.  
  // If the file fails to open, Load throws the FileOpenError exception
 
#endif

#include <iostream>
#include <new>
#include <cstddef>
#include <string>
#include "graph.h"
 
using namespace std;
 
Graph::Graph(int num)
{
	numV = 0;
	vertices[num];
}
 
Graph::~Graph()
{
	delete [] vertices;
}
 
bool Graph::IsEmpty()
{
	return (numV == 0);
}
 
bool Graph::IsFull()
{
	EdgeNode* tempPtr;
	try
	{
		tempPtr = new EdgeNode;
	}
	catch (bad_alloc)
	{
		return true;
	}
    delete tempPtr;
	return false;
}
 
void Graph::AddVertex(string v)
{
	verticies[numV] = v;
 
	for(int index = 0; index < numV; index++)
	{
 
}