#pragma once
#include <string>
#include <map>
#include <vector>
#include <queue>
using namespace std;

class directedGraph
{
private:

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

		//BFS variables
		bool marked;
		vertex* breadCrumb;

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

	map<string, vertex*> vertexMap;

	void clearData()
	{
		for (auto x : vertexMap)
		{
			x.second->marked = false;
			x.second->breadCrumb = nullptr;
		}
	}

	void breadthFirstSearch(vertex* s)
	{
		//stepup:
		clearData();
		queue<vertex*> Q;

		//Step 0: Mark s, put s into queue
		s->marked = true;
		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 unmarked neighbors
			for (auto y : x->neighbors)
			{
				if (!y->marked)
				{
					y->marked = true;
					Q.push(y);

					//augmentation
					y->breadCrumb = x;
				}
			}
		}

	}

public:

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

	void addDirectedEdge(string a, string b)
	{
		vertex* aptr = vertexMap[a];
		vertex* bptr = vertexMap[b];

		aptr->neighbors.push_back(bptr);
	}

	void addBasicEdge(string a, string b)
	{
		addDirectedEdge(a, b);
		addDirectedEdge(b, a);
	}

	string shortestPath(string start, string end)
	{
		//setup:
		vertex* startPtr = vertexMap[start];
		vertex* endPtr = vertexMap[end];

		//Call BFS on source vertex (the vertex containing a)
		//It will set all the breadcrumb pointers to encode
		//all shortest paths starting from startPtr.
		breadthFirstSearch(startPtr);

		//Trace breadCrumb trail from end to start
		//to get shortest path
		string output = "";

		vertex* finger = endPtr;
		while (finger != startPtr && finger != nullptr)
		{
			output = finger->data + ", " + output;
			finger = finger->breadCrumb;
		}

		output = startPtr->data + ", " + output;

		if (finger != nullptr)
			return output;
		else
			return "NO PATH EXISTS";
	}
};