A simple Graph API with DFS and BFS Implementation

graphAPI.cpp

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <stdexcept>
#include <iterator>
#include <queue>
#include <stack>

using namespace std;

template <typename T>
class VertexIterator: public std::iterator<std::forward_iterator_tag,T>
{

public:
	VertexIterator( unordered_set<T> &s): vertex_list(s), vertex_list_iter(s.cbegin()){}
	VertexIterator( unordered_set<T> &s, typename unordered_set<T>::const_iterator iter): vertex_list(s), vertex_list_iter(iter){}

	VertexIterator& operator++()
	{
		vertex_list_iter++;
		return *this;
	}

	T operator*()
	{
		return *vertex_list_iter;
	}


	bool operator==(const VertexIterator<T>& rhs)
	{
		return (vertex_list == rhs.vertex_list) && (vertex_list_iter == rhs.vertex_list_iter);
	}

	bool operator!=(const VertexIterator<T>& rhs)
	{
		return (vertex_list != rhs.vertex_list) || (vertex_list_iter != rhs.vertex_list_iter);
	}

	VertexIterator<T> & begin()
	{
		return *this;
	}

	VertexIterator<T> & end()
	{
		return *new VertexIterator<T>(vertex_list, vertex_list.cend());
	}

private:
	unordered_set<T> &vertex_list;
	typename unordered_set<T>::const_iterator vertex_list_iter;
};

template <typename T>
class Graph
{
	public:
		// Create an empty graph with V vertices
		Graph(int V){};

		Graph(Graph<T> &g)
		{

			for(auto v: g.vertices())
			{
				for(auto adjelem: g.adj(v))
				{
					addEdge(v,adjelem);
				}
			}
		}

		Graph(Graph<T>&&g):vertex(move(g.vertex)), adjlist(move(g.adjlist))
		{
		}
		//		Graph(istream in);

		// Add an edge between v and w
		void addEdge(T v, T w)
		{
			vertex.insert(v);
			vertex.insert(w);
			adjlist[v].insert(w);
			adjlist[w].insert(v);
		}

		 VertexIterator<T>& adj(T v)
		{
			return *new VertexIterator<T>(adjlist[v]);
		}

		 VertexIterator<T>& vertices()
		{
			return * new VertexIterator<T>(vertex);
		}

		int V()
		{
			return vertex.size();
		}

		int E()
		{
			return edge_count;
		}

		void print()
		{
				for(auto vert: adjlist)
				{
					for(auto adj_vert: vert.second )
					{
						cout << vert.first << " - " << adj_vert << endl;
					}
				}
		}

private:
		unordered_set<T> vertex;
		unordered_map<T, unordered_set<T> >  adjlist;
		int edge_count;
};

template <typename T>
class BreadthFirstSearch
{
public:
	BreadthFirstSearch(Graph<T> &G, T v): graph(G),vertex(v)
	{
		bfs(v);
	}

	void bfs(T v)
	{
		queue<T> q;
		q.push(vertex);
		visited[v] = true;
		edgeTo[v] = v;
		while(!q.empty())
		{
			v = q.front();
			q.pop();
			for(auto adj: graph.adj(v))
			{
				if (!visited[adj])
				{
					q.push(adj);
					visited[adj] = true;
					edgeTo[adj] = v;
				}
			}
		}
	}
	void printPath(T v)
	{
		T dest = v;
		while(vertex != dest)
		{
			cout << dest << " - ";
			dest = edgeTo[dest];
		}
		cout << vertex << endl;
	}
private:
	Graph<T>& graph;
	unordered_map<T,bool> visited;
	unordered_map<T,T> edgeTo;
	T vertex;
};

template <typename T>
class DepthFirstSearch
{
public:
	DepthFirstSearch(Graph<T>G, T v):graph(G), vertex(v)
	{
		dfs_nr(v);
	}

	void dfs(T v)
	{
		visited[v] = true;
		for(auto adj: graph.adj(v))
		{
			if (!visited[adj])
			{
				edgeTo[adj] = v;
				dfs(adj);
			}
		}
	}

	void dfs_nr(T v)
	{
		stack<T> s;
		s.push(v);
		edgeTo[v] = v;
		while(!s.empty())
		{
			T temp = s.top();
			s.pop();
			visited[temp] = true;
			for(auto n: graph.adj(temp))
			{
				if (!visited[n])
				{
					s.push(n);
					edgeTo[n] = temp;
				}
			}
		}
	}

	void printPath(T v)
	{
		T dest = v;
		while(vertex != dest)
		{
			cout << dest << " - ";
			dest = edgeTo[dest];
		}
		cout << vertex << endl;
	}
private:
	Graph<T>& graph;
	unordered_map<T, bool> visited;
	unordered_map<T, T> edgeTo;
	T vertex;
};


int main()
{
	Graph<int> g(10);
	g.addEdge(0,1);
	g.addEdge(0,2);
	g.addEdge(0,5);
	g.addEdge(0,6);
	g.addEdge(5,3);
	g.addEdge(5,4);
	g.addEdge(3,4);
	g.addEdge(6,4);

	BreadthFirstSearch<int> d(g,0);
	d.printPath(3);
	DepthFirstSearch<int> e(g,0);
	e.printPath(3);
	return 0;
}