// Graph.cpp: implementation of the Graph class. Define the graph using adjacency list
// also define the Dijkstra algorithm for this graph.
//
//////////////////////////////////////////////////////////////////////

#include "Graph.h"

/*
 *construct the graph with user input, user input in the form of "From To Cost"
 */
Graph::~Graph()
{
	clear();
}

Graph::Graph()
{
	cout<<"construct the graph with user input, please input the edges:"
		<<endl
		<<"From To Cost:"
		<<endl;
	istream & is = cin;
	buildGraph(is);
}

/*
 *construct a graph randomly
 *int node_num; number of nodes in the graph
 *density: the edge density in the graph, 10 means 10%
 */
Graph::Graph(int node_num, int density)
{
	/*output to file*/
	//fstream fs;
	//fs.open("output.dat",fstream::out);
	
	/* initialize random generator */
	srand ( time(NULL) );	

	int max_edge = node_num*(node_num-1)*density/100;
	int from, to, cost;
	Edge * e;

	while(true){
		initialize();
		e = new Edge();
		e->node = 0; 
		e->cost = rand()%1000+1; e->next = 0;
		//fs<<0<<" "<<1<<" "<<e->cost<<endl;
		addNewEdge(node_num-1, e);
		for(int i=0; i<node_num-1; i++){
			//from = rand()%i;
			e = new Edge();
			e->node = i+1;
			e->cost = rand()%1000+1; e->next = 0;
			//fs<<i<<" "<<i+1<<" "<<e->cost<<endl;
			addNewEdge(i, e);
		}
		while(edge_num<max_edge){
			from = rand()%node_num;
			//if(from==node_num) from--;
			//do{
			to = rand()%node_num+1;
			if(to==node_num) to--;
			//}
			//while(from==to);
			cost = rand()%1000+1;
			e = new Edge();
			e->node = to; e->cost = cost; e->next = 0;
			if(addNewEdge(from, e)){
				//fs<<from<<" "<<e->node<<" "<<e->cost<<endl;
			}
		}
		if(isConnected()){
			//fs<<"*"<<endl;
			//fs.close();
			return;
		}
		clear();	
	}
}

/*construct a graph from a file*/
Graph::Graph(const char * fileName)
{
	cout<<"construct the graph from an input file:"<<fileName
		<<endl;
	fstream fs;
	fs.open(fileName, fstream::in);
	istream & is = fs;
	buildGraph(is);	
	fs.close();
}

/*
 *if the adj_list is not long enough, extend the list in the step of 20.
 *int newlength: the expected length of the new adj_list
 */
void Graph::extendAdjList(int newlength){
	Node* tmp = new Node [newlength];
	for(int i1=0; i1<newlength; i1++) {
		tmp[i1].degree = -1;
	}
	for(int i=0; i<adj_length; i++){
		tmp[i].degree = adj_list[i].degree;
		tmp[i].e = adj_list[i].e;
	}
	delete [] adj_list;
	adj_list = tmp;
	adj_length = newlength;
}

/*
 *add a new edge into the adj_list of the graph
 *int from: the start node of the edge
 *Edge * e1: the end node and the cost of the edge
 */
bool Graph::addNewEdge(int from, Edge * e1)
{
	int m = from>e1->node?from:e1->node;
	if(m>=adj_length){ //there is no enough length of adjlist
		extendAdjList((m/20+1)*20);
	}
	//if node from never apperars before, add a new node and edge.
	if(adj_list[from].degree<0){
		adj_list[from].degree = 0;
		node_num++;
	}
	if(adj_list[from].degree==0){
		adj_list[from].e = e1;
	}
	else {//if node from already existed, add a new edge
		Edge *tmp = adj_list[from].e;
		Edge * last = tmp;
		for(int i=0; i<adj_list[from].degree; i++){
			if(tmp->node==e1->node){
				return false;
			}
			last = tmp;
			tmp=tmp->next;
		}
		last->next = e1;
	}

	//if node to never apperars before, add a new node.
	if(adj_list[e1->node].degree<0){
		adj_list[e1->node].degree = 0;
		node_num++;
	}
	(adj_list[from].degree)++;
	edge_num++;
	return true;
}

/*
 *Initialize the graph
 */
void Graph::initialize()
{
	adj_length = 20;
	node_num = 0;
	edge_num = 0;
	adj_list = new Node[20];
	for(int i=0; i<20; i++){
		adj_list[i].degree = -1;
	}
}

/*
 *For user input mod, take both std::in or a file as a input to construct the graph
 *std::istream & is: input stream, can be either a file or a key board input
 */
void Graph::buildGraph(std::istream & is)
{
	int index=0, from, to, cost;
	Edge * e;
	initialize();
	while(is>>from>>to>>cost){
		e = new Edge();
		e->node = to; e->cost = cost; e->next = 0;
		addNewEdge(from, e);
	}	
}

/*
 *Clear the adj_list of the graph
 */
void Graph::clear()
{
	for(int i=0; i<adj_length; i++){
		Edge * tmp = adj_list[i].e;
		for(int j = 0; j<adj_list[i].degree; j++){
			Edge * tmp1 = tmp;
			tmp = tmp->next;
			delete tmp1;
		}
	}

	delete [] adj_list;
}

/*
 *For random mode, test if the graph is connected using DFS from node 0;
 *If connected, return true, else return false.
 */
bool Graph::isConnected()
{
	int i;
	bool * isVisited = new bool [node_num];
	  
	for(i=0; i<node_num; i++) isVisited[i] = false;

	DFS(0, isVisited);
	  
	for(i=0; i<node_num; i++) {
		if(isVisited[i] == false)
		  return false; 
		}
	return true;
}

/*
 *Depth first search from a start node,find its connected component.
 *int startNode: the node where DFS started
 *bool* isVisited: a boolean array that give a flag of true for each node visited in DFS
 */
void Graph::DFS(int startNode, bool* isVisited)
{
	isVisited[startNode] = true;

	Edge * e = adj_list[startNode].e;
	for(int i=0; i<adj_list[startNode].degree; i++, e=e->next) {
		int node = e->node;
		if(!isVisited[node])
			DFS(node, isVisited);
	} 
}



void Graph::testInput(void)
{
	cout<<"Node num: "<<node_num<<endl;
	cout<<"Edge num: "<<edge_num<<endl;
	for(int i=0; i<adj_length; i++){
		Node n = adj_list[i];
		if(n.degree>=0){
			cout<<"Node "<<i<<endl;
			cout<<"degree:"<<n.degree<<endl;		
			Edge * e1 = n.e;
			for(int j=0; j<n.degree; j++){
				cout<<i<<" to "<<e1->node;
				cout<<" cost: "<<e1->cost<<endl;
				e1 = e1->next;
			}
		}
	}
}

/*
 *Dijkstra's single source shortest path algorithm. compute the shortest path from node 0 to 
 *all the other nodes in the graph.
 *DistSet * dist_set: can be either array, Fibonacci Heap or Pairing Heap
 *Result: store the result of Dijkstra
 */
Result Graph::DijkstraSSP(int source, DistSet * dist_set)
{ 
	bool * found = new bool[node_num];
	Result * r = new Result(node_num);
	int v, i;
	Edge * e;
	for(int i1=0; i1<node_num; i1++){
		found[i1] = false;
		(r->dist)[i1] = INT_MAX;
	}
	(r->dist)[source] = 0;
	dist_set->insert(source, 0);
	found[source] = true;
	
	while(!dist_set->IsEmpty()){
		v = dist_set->deleteMin();
		if((r->dist)[v] == INT_MAX){
			return *r;
		}
		e = adj_list[v].e;
		for(i=0; i<adj_list[v].degree; i++, e=e->next){
			int newDist = r->dist[v] + e->cost;
			if(r->dist[e->node]>newDist){
				r->dist[e->node] = newDist;
				if(found[e->node]) {
					dist_set->decreasDist(e->node, r->dist[e->node]);
				}
				else {
					dist_set->insert(e->node, r->dist[e->node]);
					found[e->node] = true;
				}
			}
		}
	}
		return *r;
}

int main(int argc,char *argv[])
{
	
	//PHeap::testPHeap();
/*	Graph * g = new Graph("input.dat");
	cout<<"Node";
	for(int i=0; i<4; i++){
		cout<<"\t"<<i;
	}
	cout<<endl;
	for(int i=0; i<4; i++){
		DistSet * ph = new PHeap(g->getNodeNum());
		Result r3 = g->DijkstraSSP(i, ph);
		cout<<i;
		r3.printResult();
	}*/
	
	clock_t start;
	double s_time, f_time, p_time;
	DistSet * ds;
	Graph * g;

	if(argc==1){
		cout<<"too few parameters!";
		return 1;
	}

	char * pchar = argv[1];

	fstream fs;
	fs.open("output.dat",fstream::out);
	
	switch(pchar[1])
	{
		case 'r':
		{
			fs<<"|V|\t"<<"Density\t"<<"Simple\t"<<"FHeap\t"<<"PHeap\t"<<endl;
			cout<<"|V|\t"<<"Density\t"<<"Simple\t"<<"FHeap\t"<<"PHeap\t"<<endl;
			for(int i=1; i<=1; i++){//|V| from 100 to 500
				for(int j=1; j<=10; j++){//density from 10% to 100%
					s_time = 0; f_time = 0; p_time = 0;
					for(int l=0; l<5; l++){//run 5 times
						g = new Graph(i*100, j*10);
						start = clock();
						for(int k1=0; k1<i*100; k1++){
							DistSet * ph = new PHeap(g->getNodeNum());
							Result r3 = g->DijkstraSSP(k1, ph);
							delete ph;
						}
						p_time += (double)(clock()-start);
					
						start = clock();
						for(int k2=0; k2<i*100; k2++){
							DistSet * fh = new FHeap(g->getNodeNum());
							Result r2 = g->DijkstraSSP(k2, fh);
							delete fh;
						}
						f_time += (double)(clock()-start);
						
						start = clock();
						for(int k=0; k<i*100; k++){
							DistSet * as = new ArraySet(g->getNodeNum());
							Result r1 = g->DijkstraSSP(k, as);
							delete as;
						}
						s_time += (double)(clock()-start);
						delete g;
					}
					fs<<i*100<<"\t"<<j*10<<"%\t"<<s_time/5<<"\t"<<f_time/5<<"\t"<<p_time/5<<endl;
					cout<<i*100<<"\t"<<j*10<<"%\t"<<s_time/5<<"\t"<<f_time/5<<"\t"<<p_time/5<<endl;
				}
			}	
			fs.close();
			break;
		}
		case 'i': //user input model
		{
			if(argc==3){//from file
				g = new Graph(argv[2]);
			}
			else{//from screen input
				g = new Graph();
			}
			if(g->adj_list[0].degree<=0){
				cout<<"Invalid Graph!"<<endl;
				return 0;
			}
			switch(pchar[2])
			{
				case 's': //simple scheme
					ds = new ArraySet(g->getNodeNum());
					break;
				case 'f': //fibonacci heap scheme
					ds = new FHeap(g->getNodeNum());
					break;
				case 'p': //pairing heap scheme
					ds = new PHeap(g->getNodeNum());
					break;
			}
			cout<<"Node";
			for(int i1=0; i1<g->getNodeNum(); i1++){
				cout<<"\t"<<i1;
			}
			cout<<endl;
			for(int i=0; i<g->getNodeNum(); i++){
				Result r = g->DijkstraSSP(i, ds);
				cout<<i;
				r.printResult();
				ds->initial();
			}
			delete g;
			delete ds;
		}
	}
	char blah;
	cout << "Press q to exit"<<endl;
	cin >> blah;
	return 1;
}