#include <iostream>
#include <fstream>
#include <unordered_map>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

unordered_map<string,vector<string>> G; // the adjacency list
unordered_map<string,bool> visited;
unordered_map<string,string> parent;

void Tokenize(string line, vector<string> & tokens, string delimiters){
        string token = "";
        string OneCharString = " ";
        for (int i=0; i<line.size(); i++)
                if (find(delimiters.begin(), delimiters.end(), line[i])!=delimiters.end()) // line[i] is one of the delimiter characters
                {
                        if (token != "")
                                tokens.push_back(token);
                        token = "";
                }
                else
                {
                        OneCharString[0] = line[i];
                        token +=OneCharString;
                }

        if (token != "")
                tokens.push_back(token);
}

void readGreaph(char* file_name){
	fstream inf;
	inf.open(file_name);

	string line;
	while (getline(inf,line).good()){
		vector<string> tokens;
		Tokenize(line, tokens, " \t");	
		if (tokens.size()!=2)
			continue;
		G[tokens[0]].push_back(tokens[1]);
		G[tokens[1]].push_back(tokens[0]);
	}
	inf.close();
}

// assuming that nodes have unique string identifiers
void DFS(string v, vector<string>& ret){
	visited[v] = true;
	ret.push_back(v);
	for (int i=0; i< G[v].size(); i++){
		if (!visited[G[v][i]]){
			parent[G[v][i]] = v;
			DFS(G[v][i], ret);

		}
	}	
}

vector<string> BFS(string v){
        vector<string> ret;

	queue<string> q;
	q.push(v);	
        visited[v] = true;
	while (!q.empty()){
	        string u = q.front();
		q.pop();

		ret.push_back(u);
        	for (int i=0; i< G[u].size(); i++){
			if (visited[G[u][i]])
				continue;
			q.push(G[u][i]);
			visited[G[u][i]] = true;
        	}
	}
        return ret;
}

vector<string> get_reverse_path(string u, string v){
	vector<string> ret;
	ret.push_back(v);
	while (v!=u){
		v = parent[v];
		ret.push_back(v);
	}
	return ret;
}

int main(int argc, char** argv){
	if (argc!=4){
		cout <<"Parameters: graph u v" << endl;
		return 1;
	}
	
	readGreaph(argv[1]);

	string u = argv[2];
	string v = argv[3];
	
	cout << "Path found by DFS:" << endl;
        vector<string> output; 
	DFS(u, output);
	vector<string> path = get_reverse_path(u, v);
        for (int i=path.size()-1; i>=0; i--)
                cout << path[i] << "\t";
	cout << endl;

	visited.clear();
	parent.clear();

	cout << "Path found by BFS:" << endl;
	output = BFS(argv[2]);
	path = get_reverse_path(u, v);
        for (int i=path.size()-1; i>=0; i--)
                cout << path[i] << "\t";
        cout << endl;

	cout << "All done!\n";

	return 0;
}