// 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++)
	{
 
}

Graph::Graph(int num) : numV(num), vertices(new VertexNode[num]){
 
      memset (vertices, 0, sizeof(VertexNode) * num);
}

struct VertexNode									// Structure representing a vertex
{
  string		vname;								// Name of vertex
  bool			mark;								// Marked flag
  EdgeNode*		edgePtr;							// Pointer to list of edges
};
 

Your main function must perform all of the following tasks.
(1) Declare a string variable and initialize it with the value argv[1].
(2) Invoke the Load function to input graph data from file along with the search start and end vertices.
Since Load may throw an exception, you should use a try-catch pair to trap the exception.
(3) Once the graph loads, use the Graph class Print function to print out the graph
(4) Perform a Depth-First Search using the start and end vertices input from the file by the Load
function. The path, if found, is stored in a queue (whose address is returned by the DFS function) so
use the Queue class Print function to print out the path. If no path is found, a NULL pointer is
returned by the DFS function.
(5) Compute the weight of the path found by DFS and output to monitor.
Your program must also contain appropriate comments in order to receive full credit.
Your goal is to EXACTLY match the output of your program to that of the sample solution.
Fall 2008 CPE212 Project Assignment Project 8
Page 4 of 5
<Project08 Input File Format>
Use the extraction operator for all inputs!!!
First line of file contains an integer specifying the total number of vertices in the graph.
Use this value when you call the constructor to create the graph.
‘v’  followed by vertex_name (vertex names are always single-word strings)
‘u’  an UNDIRECTED EDGE followed by vertex1 vertex2 edge_weight
‘d’  a DIRECTED EDGE followed by source_vertex destination_vertex edge_weight
‘s‘  name of dfs_start_vertex
‘e’  name of dfs_end_vertex
Hints:
- Use the extraction operator for all inputs!!!
- An UNDIRECTED EDGE may be simulated by two DIRECTED EDGES going in
opposite directions with the same weights
<Project 8 Graph Class Description>
The Graph class uses an Adjacency List Representation to store the graph information.
 Inline functions are not allowed in this course and will result in no credit (0) 
[Note: An inline function is a function whose definition appears within the class declaration]
Attribute Name Data Type Purpose
vertices VertexNode* Stores address of dynamically allocated array of VertexNodes
numV int Number of vertices
Function Name Return
Type
Purpose
Graph N/A Constructor that allocates an array of VertexNodes just large
enough to hold incoming graph
DeleteAllEdges void Deallocates all EdgeNodes connected to all vertices
IsEmpty bool Returns true if Graph is empty, false otherwise
IsFull bool Returns true if Graph is full, false otherwise
AddVertex void Adds vertex name V to vertex array
AddEdge void Adds edge from Source to Destination with specified Weight
IndexIs int Scans vertex array to locate named vertex and returns array index
WeightIs int Returns weight of edge from Source to Destination
GetToVertices void Returns a queue of vertices adjacent to specified vertex
ClearMarks void Sets all vertex marks to false
Fall 2008 CPE212 Project Assignment Project 8
Page 5 of 5
MarkVertex void Sets mark of specified vertex to true
IsMarked bool Returns mark status of specified vertex
Print void Prints Graph contents in specified format (see sample solution)
DepthFirstSearch Queue* Returns pointer to a queue containing the path if found. If not
found, returns NULL pointer
~Graph N/A Deallocates all edge nodes and the vertex array
Note: Load function described in “graph.h”
 See the file graph.h for additional details regarding the function interfaces 