#include <iostream>
#include "LinkedList.cpp"

using namespace std;

#ifndef GRAPH_CLASS_INCLUDED
#define GRAPH_CLASS_INCLUDED

/*
	Graph Class
	LastModification : 2008. 5. 5
	Version : 0.1.0 Beta
	myllyj(myllyj at myllyj dot com) / http://program.myllyj.com

	Requirements:
		require LinkedList class.

	Comment:
		Graph는 하나의 노드가 여러군데에 연결 될 수 있어야 하며,
		방향성이 존재 할 수도 있다. 또한 각각의 링크는 Weight를
		달리 할 수도 있다.

		이 버전의 그래프는 Link가 방향성을 가지지 않으며, Link의
		Weight가 모두 동일한 경우로 가정한다. 또한 자신이 자신
		스스로를 링크 할 수 없으며, 자신과 다른 인접노드와는 하나의
		연결만 가질 수 있다.

		현재 버전은 아주 낮은 시험버전으로, Vertex, Edge의 수정,
		삭제를 지원하지 않는다.

*/

template <class T>
class Graph
{
private :
	LinkedList<LinkedList<T>*>* linkHolder;

public :
	Graph();
	void AddVertex(T data);
	void AddEdge(T data1, T data2);
	T GetFirstVertex();
	LinkedList<T>* GetVertics(T data);

};

template <class T>
Graph<T>::Graph()
{
	linkHolder = new LinkedList<LinkedList<T>*>;
}

// 그래프에 Vertex를 추가합니다.
template <class T>
void Graph<T>::AddVertex(T data)
{
	LinkedList<T>* newVertex = new LinkedList<T>();
	newVertex->AddFirst(data);
	this->linkHolder->AddLast(newVertex);
}

// 그래프에 Edge를 추가합니다.
template <class T>
void Graph<T>::AddEdge(T data1, T data2)
{
	bool flag = false;
	LinkedList<T>* tmpNode1;
	LinkedList<T>* tmpNode2;

	// data1에 대한
	this->linkHolder->MoveFirst();
	while (!linkHolder->IsHeaderNode())
	{
		tmpNode1 = linkHolder->Get();
		tmpNode1->MoveFirst();
		if (tmpNode1->Get()==data1)
		{
			flag = true;
			break;
		}
		
		linkHolder->MoveNext();
	}

	if (!flag) return;

	// data2에 대한
	this->linkHolder->MoveFirst();
	while (!linkHolder->IsHeaderNode())
	{
		tmpNode2 = linkHolder->Get();
		tmpNode2->MoveFirst();
		if (tmpNode2->Get()==data2)
		{
			flag = true;
			break;
		}
		
		linkHolder->MoveNext();
	}
	if (!flag) return;

	tmpNode2->AddLast(data1);
	tmpNode1->AddLast(data2);
}

// 그래프에서 첫 Vertex를 찾습니다.
template <class T>
T Graph<T>::GetFirstVertex()
{
	LinkedList<T>* tmpNode;

	linkHolder->MoveFirst();
	tmpNode = linkHolder->Get();
	tmpNode->MoveFirst();
	return tmpNode->Get();
}

// 그래프에서 지정한 Vertex와 연결된 Vertex의 List를 반환합니다.
template <class T>
LinkedList<T>* Graph<T>::GetVertics(T data)
{
	LinkedList<T>* tmpNode;

	linkHolder->MoveFirst();
	while (!linkHolder->IsHeaderNode())
	{
		tmpNode = linkHolder->Get();
		tmpNode->MoveFirst();
		if (tmpNode->Get()==data) return tmpNode;
		linkHolder->MoveNext();
	}

	return NULL;

}

#endif