// ===== main.cpp =====

//#include "header dfs.h"
#include "header bfs.h"
int main(){ 
	int target;
	graphSearch G; 
	cout << "Input target: " ; 
	cin >> target; 
	G.buildGraph(); 
	G.search(target); 
	cout << endl;
	return 0; 
}

// ===== header bfs.h =====

#ifndef HEADER_BFS_H
#define HEADER_BFS_H
#include <iostream>
#include <vector>
#include <queue>
#include <windows.h>
using namespace std;
class node{
public:
	node(){
		data = -1;
		next = NULL;
	}
	node(int n){
		data = n;
		next = NULL;
	}
	node(int n, node *ptr){
		data = n;
		next = ptr;
	}
	void setNode(int n){
		data = n;
	}
	int getNode() const{
		return data;
	}
	node* getNext() const{
		return next;
	}
private:
	int data;
	node* next;
}; 
// [|=== SPACER ===|]
class graphSearch{ 
public: 
	graphSearch(){ 
		visitedList.resize(0);
		adj.resize(0);
		searchList.empty();
		searchList.push(0);
	}
	void buildGraph(){
		cout << endl << "Now building a graph for Breadth First Search.";
		int edgeQty, source, sink;
		cout << endl << "How many nodes? ";
		cin >> numNodes;
		visitedList.resize(numNodes);
		adj.resize(numNodes);
		for(int cntra = 0; cntra < numNodes; cntra++){
			adj[cntra].resize(0);
		}
		cout << endl << "How many edges? ";
		cin >> edgeQty;
		cout << endl;
		for(int cntrb = 1; cntrb <= edgeQty; cntrb++){
			cout << "Enter edge set #" << cntrb << " in the format # # :" << endl;
			cin >> source >> sink;
			adj[source].push_back(node(sink));
			adj[sink].push_back(node(source));
		}
		// Here lies the display of the adjacency array
		cout << endl;
		for(int tllya = 0; tllya < int(adj.size()); tllya++){
			SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_RED);
			cout << tllya;
			SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY);
			cout << " | ";
			SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_GREEN);
			for(int tllyb = 0; tllyb < int(adj[tllya].size()); tllyb++){
				cout << adj[tllya][tllyb].getNode() << " ";
			}
			SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY);
			cout << endl;
		}
	}
	void search(const int target){
		int currNodeToCheck = searchList.front(); // .front() in queue, .top() in stack
		searchList.pop();
		if(!visitedList[currNodeToCheck]){
			visitedList[currNodeToCheck] = 1;
			if(currNodeToCheck == target){
				cout << endl << "---Found node at " << currNodeToCheck << "!" << endl;
				system("pause");
				exit(0);
			}
			cout << endl << "Visiting node #" << currNodeToCheck;
			for(int k = 0; k < int(adj[currNodeToCheck].size()); k++){
				//if(!visitedList[adj[currNodeToCheck][k].getNode()])
					searchList.push(adj[currNodeToCheck][k].getNode());
			}
			search(target);
		}
		else{
			cout << endl << "Ignoring node #" << currNodeToCheck;
			search(target);
		}
	}
private:
	vector <bool> visitedList;
	vector <vector <node> > adj;
	queue <int> searchList;
	int numNodes;
};
#endif

// ===== header dfs.h =====

#ifndef HEADER_DFS_H
#define HEADER_DFS_H
#include <iostream>
#include <vector>
#include <stack>
#include <windows.h>
using namespace std;
class node{
public:
	node(){
		data = -1;
		next = NULL;
	}
	node(int n){
		data = n;
		next = NULL;
	}
	node(int n, node *ptr){
		data = n;
		next = ptr;
	}
	void setNode(int n){
		data = n;
	}
	int getNode() const{
		return data;
	}
	node* getNext() const{
		return next;
	}
private:
	int data;
	node* next;
}; 
// [|=== SPACER ===|]
class graphSearch{ 
public: 
	graphSearch(){ 
		visitedList.resize(0);
		adj.resize(0);
		searchList.empty();
		searchList.push(0);
	}
	void buildGraph(){
		cout << endl << "Now building a graph for Depth First Search.";
		int edgeQty, source, sink;
		cout << endl << "How many nodes? ";
		cin >> numNodes;
		visitedList.resize(numNodes);
		adj.resize(numNodes);
		for(int cntra = 0; cntra < numNodes; cntra++){
			adj[cntra].resize(0);
		}
		cout << endl << "How many edges? ";
		cin >> edgeQty;
		cout << endl;
		for(int cntrb = 1; cntrb <= edgeQty; cntrb++){
			cout << "Enter edge set #" << cntrb << " in the format # # :" << endl;
			cin >> source >> sink;
			adj[source].push_back(node(sink));
			adj[sink].push_back(node(source));
		}
		// Here lies the display of the adjacency array
		cout << endl;
		for(int tllya = 0; tllya < int(adj.size()); tllya++){
			SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_RED);
			cout << tllya;
			SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY);
			cout << " | ";
			SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_GREEN);
			for(int tllyb = 0; tllyb < int(adj[tllya].size()); tllyb++){
				cout << adj[tllya][tllyb].getNode() << " ";
			}
			SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY);
			cout << endl;
		}
	}
	void search(const int target){
		int currNodeToCheck = searchList.top(); // .front() in queue, .top() in stack
		searchList.pop();
		if(!visitedList[currNodeToCheck]){
			visitedList[currNodeToCheck] = 1;
			if(currNodeToCheck == target){
				cout << endl << "---Found node at " << currNodeToCheck << "!" << endl;
				system("pause");
				exit(0);
			}
			cout << endl << "Visiting node #" << currNodeToCheck;
			for(int k = 0; k < int(adj[currNodeToCheck].size()); k++){
				//if(!visitedList[adj[currNodeToCheck][k].getNode()])
					searchList.push(adj[currNodeToCheck][k].getNode());
			}
			search(target);
		}
		else{
			cout << endl << "Ignoring node #" << currNodeToCheck;
			search(target);
		}
	}
private:
	vector <bool> visitedList;
	vector <vector <node> > adj;
	stack <int> searchList;
	int numNodes;
};
#endif