#include <iostream>
#include "Graph.cpp"
#include "Stack.cpp"
#include "Queue.cpp"

using namespace std;

#ifndef GRAPHTRAVERSAL_CLASS_INCLUDED
#define GRAPHTRAVERSAL_CLASS_INCLUDED

/*
	Graph Traversal Class
	LastModification : 2008. 5. 5
	Version : 1.0.0
	myllyj(myllyj at myllyj dot com) / http://program.myllyj.com

	Requirements:
		require Graph class
		require Stack class
		require Queue class

	Comment:
		BFS와 DFS를 할 때 여러개의 Child가 있을경우, 고르는 우선 순위는
		그저 먼저 edge를 연결한 것으로 한다.
		특정 연결이 어떤 다른 연결보다 우선시 한다는 강한 연결 같은
		기능은 없다.
		반대로 이야기 하면, 강한 연결이라면 그보다 약한 연결 보다
		먼저 연결 하면 된다.

*/

template <class T>
class GraphTraversal
{

private:
	Queue<T>* queue;
	Stack<T>* stack;
	LinkedList<T>* visited;

public:
	GraphTraversal();
	void DepthFirstSearch(Graph<T>* graph);
	void BreadthFirstSearch(Graph<T>* graph);
	void PrintVisited();

};

template <class T>
GraphTraversal<T>::GraphTraversal()
{
	queue = new Queue<T>();
	stack = new Stack<T>();
	visited = new LinkedList<T>();
}

// 지정한 그래프에 대해서 깊이 우선 탐색(DFS)를 실시합니다.
template <class T>
void GraphTraversal<T>::DepthFirstSearch(Graph<T>* graph)
{
	stack->Clear();
	visited->Clear();
	// 첫번째 노드 넣어줌
	stack->Push(graph->GetFirstVertex());

	while(stack->Count() > 0)
	{
		bool flag = false;

		// 작업 vertex 뽑고
		T nowVertex = stack->Top();
		// 스택에 있는 것 중에서 이미 방문한 것도 있는데,
		// 방문한거 또 추가 하면 안된다.
		if (!visited->Contains(nowVertex)) visited->AddLast(nowVertex);

		//child가 있는지 검사한다
		LinkedList<T>* tmpList = graph->GetVertics(nowVertex);
		tmpList->MoveFirst();
		tmpList->MoveNext();
		while(!tmpList->IsHeaderNode())
		{
			// 방문 안한 노드 중 하나만 찾아서 추가하고
			// 그 노드에 대한 탐색 시작.
			if (!visited->Contains(tmpList->Get()))
			{
				stack->Push(tmpList->Get());
				flag = true;
				break;
			}
			tmpList->MoveNext();
		}

		if (!flag) stack->Pop();
	}

	// visited 에 기록된거 순서대로 다 집어 끄낸다.
	this->PrintVisited();

}

// 지정한 그래프에 대해서 공간 우선 탐색(BFS)를 실시합니다.
template <class T>
void GraphTraversal<T>::BreadthFirstSearch(Graph<T>* graph)
{
	queue->Clear();
	visited->Clear();
	// 첫번째 노드 넣어줌
	queue->Enqueue(graph->GetFirstVertex());
	visited->AddLast(graph->GetFirstVertex());

	while(queue->Count() > 0)
	{
		T nowVertex = queue->Dequeue();

		//child가 있는지 검사한다
		LinkedList<T>* tmpList = graph->GetVertics(nowVertex);
		tmpList->MoveFirst();
		tmpList->MoveNext();
		while(!tmpList->IsHeaderNode())
		{
			if (!visited->Contains(tmpList->Get()))
			{
				queue->Enqueue(tmpList->Get());
				visited->AddLast(tmpList->Get());
			}
			tmpList->MoveNext();
		}

	}

	// visited 에 기록된거 순서대로 다 집어 끄낸다.
	this->PrintVisited();

}

// 그래프 탐색의 결과를 출력합니다.
template <class T>
void GraphTraversal<T>::PrintVisited()
{
	visited->MoveFirst();
	while (!visited->IsHeaderNode())
	{
		cout << visited->Get() << " ";
		visited->MoveNext();
	}
}

#endif