#ifndef GRAPH_H 
#define GRAPH_H

#include "apvector.h"
#include "listNode2.h"

using namespace main_savitch_6B;

template <class T> class graph{
public:
	graph();
   	void addVertex(const T & name);
  	void addEdge(const T & name1, const T & name2);
  	node < T > * getNeighbors(const T & name) const;
  	int numVertices() const;
   	int numEdges() const; 
	T getItem(int) const ;
	void bfs(const T &, apvector<int> &, apvector<int> &)  ;
	void dfs(const T &, apvector<int> &, apvector<int> &)  ;
	void dfsNonRecursive(const T &, apvector<int> &, apvector<int> &)  ;
	void print() ;
	
	int getIndex(const T & name) const;

private:
	apvector < node < T > > myVertices;
	int myNumVertices;
	int myNumEdges;	

	void dfsHelper(const T &, apvector<int> &, apvector<int> &,apvector<bool>&)  ;
};

#include "graph.cxx"
#endif