#pragma once

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#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;
			marked = false;
			breadCrumb = nullptr;
		}
	};

	//container/data structure to hold all vertices
	unordered_map<string,vertex*> vertexMap;

public:

	//Add a vertex to the graph
	//run time: O(1) a.c.
	void addVertex(string s)
	{
		vertexMap[s] = new vertex(s);
	}

	//Add a directed edge from a to b
	//run time: O(1) a.c.
	void addDirectedEdge(string a, string b)
	{
		vertex* aptr = vertexMap[a]; //O(1) a.c.
		vertex* bptr = vertexMap[b]; //O(1) a.c.

		aptr->neighbors.push_back(bptr); //O(1)
	}

	//Add a bidirectional edge between a and b
	//run time:
	void addBasicEdge(string a, string b)
	{
		addDirectedEdge(a, b);
		addDirectedEdge(b, a);
	}

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

};