#include "cGraph.h"
#include "cList.cpp"

cDirectedGraph::cDirectedGraph(const int vertices){
	VertexCount = vertices;
	HeadNodes = new cList<Vertex>[VertexCount];
	// 인접 길이 행렬의 값을 채운다.
	// 99999은 Edge가 없다는 의미이다.
	for(int i = 0; i < MAX_VERTICES; i ++){
		for(int j = 0; j < MAX_VERTICES; j ++){
			if(i == j) length[i][j] = 0;
			else length[i][j] = 99999; // 
		}
	}
}
cDirectedGraph::~cDirectedGraph(){
	// 인접 리스트에 할당되어 있는 메모리를 제거한다.
	if(HeadNodes) delete [] HeadNodes;
}

void cDirectedGraph::InsertEdge(Vertex u, Vertex v){
	// 단순히 인접 리스트에 추가한다.
	HeadNodes[u].Add(v);
}
void cDirectedGraph::InsertEdge(Vertex u, Vertex v, int Distance){
	// 단순이 인접 리스트에 추가하고 길이 정보를 기록한다.
	HeadNodes[u].Add(v);
	length[u][v] = Distance;
}

void cDirectedGraph::DeleteEdge(Vertex u, Vertex v){
	// 단순히 인접 리스트에서 정점을 제거한다.
	HeadNodes[u].Delete(v);
}

bool cDirectedGraph::IsEmpty(){
	return VertexCount > 0;
}

void cDirectedGraph::ShortestPath(const int n, const Vertex v){
// dist [j], 0 <= j < n, is set to the length of the shortest path from vertex v to vertex j
// in a digraph G with n vertices and edge lengths given vy Length[i][j].
	for(int i = 0; i < n; i ++){
		s[i] = false;
		dist[i] = length[v][i];
	}
	s[v] = true;
	dist[v] = 0;
	for(i = 0; i < n - 2; i ++){ // determine n - 1 paths from vertex v
		int u = choose(n);
		// choose returns a value u such that:
		// dist[u] = minimum dist[w], where s[w] = false;
		s[u] = true;
		for(int w = 0; w < n; w ++)
			if(!s[w])
				if(dist[u] + length[u][w] < dist[w])
					dist[w] = dist[u] + length[u][w];
	} // end of for(i = 0;...)
}
							
int cDirectedGraph::GetLength(Vertex u, Vertex v){
	return length[u][v];
}

int cDirectedGraph::choose(int n){
// choose returns a value u such that:
// dist[u] = minimum dist[w], where s[w] = false;
	int u = 0, min = 99999;

	for(int w = 0; w < n; w ++){
		if(s[w] == false && dist[w] < min){
			min = dist[w];
			u = w;
		}
	}
	return u;
}
int *cDirectedGraph::GetDist(){
	return dist;
}
