#pragma once
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
using namespace std;

class directedGraph
{
private:
	class vertex
	{
	public:
		string data;
		vector<vertex*> neighbors;

		vertex(string x)
		{
			data = x;
		}
	};

	//need a container to hold all the
	//vertices in the graph.  Array? Linked list? something else?
	//We chose a hash table for O(1) a.c insert,
	//and O(1) a.c. find.
	unordered_map<string, vertex*> vertexMap;

	void breadthFirstSearch(vertex* s, unordered_map<vertex*, vertex*>& breadCrumbs)
	{
		//step -1: declare some stuff we need
		queue<vertex*> Q;
		unordered_set<vertex*> marked;

		//step 0: Mark s, put in Q
		marked.insert(s);
		Q.push(s);

		//step 1: The BFS loop
		while (!Q.empty())
		{
			//step 1.1: get item from Q
			vertex* x = Q.front();
			Q.pop();

			//Step 1.2: visit all of x's
			//unvisited neigjhbors
			for (int i = 0; i < x->neighbors.size(); i++)
			{
				vertex* y = x->neighbors[i];
				if (marked.find(y) == marked.end())
				{
					marked.insert(y);
					Q.push(y);

					//shortest-path augmentation:
					breadCrumbs[y] = x;
				}
			}
		}

	}


public:

	void addVertex(string s)
	{
		vertexMap[s] = new vertex(s);
	}

	void addDirectedEdge(string s, string t)
	{
		vertex* Sptr = vertexMap[s];
		vertex* Tptr = vertexMap[t];

		Sptr->neighbors.push_back(Tptr);
	}

	void addBasicEdge(string s, string t)
	{
		addDirectedEdge(s, t);
		addDirectedEdge(t, s);
	}


	string shortestPath(string start, string dest)
	{
		//Locate vertices of start and dest
		vertex* source = vertexMap[start];
		vertex* destVert = vertexMap[dest];

		//breadcrumbs mapping to encode shortest paths
		unordered_map<vertex*, vertex*> breadCrumbs;

		//compute shortest paths with bfs
		breadthFirstSearch(source, breadCrumbs);

		//use breadcrumbs trail computed by BFS
		//to trace back shortest path from dest to source.
		string path = "";
		vertex* current = destVert;
		while (current != source)
		{
			path = current->data + path;
			current = breadCrumbs[current];
		}
		path = source->data + path;
		return path;
	}

	void test()
	{
		for (auto x : vertexMap)
		{
			cout << x.first << ": ";
			for (auto y : x.second->neighbors)
				cout << y->data << ", ";
			cout << endl;
		}
	}
};