/*
graph_alg.c
Pedro Flynn - pflynn@microsoftsucks.org
*/

#include "graph_alg.h"

int graph_ins_weight_edge(Graph* graph,const PathVertex* v1,const PathVertex* v2,double weight)
{
PathVertex* adjvertex;
	
if(!(adjvertex = (PathVertex*) malloc(sizeof(PathVertex))))
	return -1;

memcpy(adjvertex,v2,sizeof(PathVertex));
adjvertex->weight = weight;

return graph_ins_edge(graph,v1, adjvertex);
}

/* find minimum spaning trees - (Prim's algorithm )*/
List* graph_mst(Graph* graph,MSTVertex* start)
{
MSTVertex *vertex,*adjvertex;
AdjList *adjlist,*adjadjlist;
ListElmt* element;
SetElmt* setelement;
int i=0,found = 0;
double min;	
List* mstlist;
	
for(element=LIST_HEAD(graph->adjlists);element;element=LIST_NEXT(element)){
	 
	vertex = ((AdjList*) LIST_DATA(element))->vertex;
	
	if(graph->match(vertex,start)){
		vertex->parent = NULL;
		vertex->key = 0;
		vertex->color = white;
		found = 1;
		}else{
					vertex->parent = NULL;
		      vertex->key = DBL_MAX;
		      vertex->color = white;
		     }
	}
	
	if(!found)
		return NULL;
	
	while(i < graph->vcount){
		
		min = DBL_MAX;
		for(element=LIST_HEAD(graph->adjlists);element;element=LIST_NEXT(element)){
	     
			 vertex = ((AdjList*) LIST_DATA(element))->vertex;
			 if(vertex->color == white && vertex->key < min){
				 min = vertex->key;
				 adjlist = LIST_DATA(element);
				 }
			
			}
			
			vertex = (MSTVertex*) adjlist->vertex;
		  vertex->color = black;
			
			for(setelement=SET_FIRST(adjlist->adjacent);setelement;setelement=SET_NEXT(setelement)){
				adjvertex = SET_DATA(setelement);
				graph_adjlist(graph,adjvertex,&adjadjlist);
				
				if(((MSTVertex*) adjadjlist->vertex)->color == white 
					&& adjvertex->weight < ((MSTVertex*) adjadjlist->vertex)->key){
						
						((MSTVertex*) adjadjlist->vertex)->key = adjvertex->weight;
						((MSTVertex*) adjadjlist->vertex)->parent = vertex;
						
						}
						
						
				}
		  
			
		i++;
		}
		
		mstlist = list_create(NULL);
		for(element=LIST_HEAD(graph->adjlists);element;element=LIST_NEXT(element)){
	     vertex = ((AdjList*) LIST_DATA(element))->vertex;
		   if(vertex->color == black)
				 list_ins_next(mstlist,NULL,vertex);
			}
		
		
		
	return mstlist;
}


static void relax(PathVertex* u,PathVertex* v,double weight)
{
if(v->d > u->d + weight){
	v->d = u->d + weight;
	v->parent = u;
	}	
return;
}

List* graph_dijkstra(Graph* graph,const PathVertex* start)
{
List* pathlist;
ListElmt *element;
SetElmt *setelement;
PathVertex *vertex,*adjvertex;
AdjList *adjlist,*adjadjlist;
int found = 0,i=0;
double min;
	
for(element=LIST_HEAD(graph->adjlists);element;element=LIST_NEXT(element)){
	vertex = ((AdjList*) LIST_DATA(element))->vertex;
	if(graph->match(vertex,start)){
		vertex->parent = NULL;
		vertex->d = 0;
		vertex->color = white;
		found = 1;
		}else{
			vertex->parent = NULL;
		  vertex->d = DBL_MAX;
		  vertex->color = white;
		}
	}
	
	if(!found)
		return NULL;
	
	while(i < graph->vcount){
		
	min = DBL_MAX;
		
	for(element=LIST_HEAD(graph->adjlists);element;element=LIST_NEXT(element)){
		vertex = ((AdjList*) LIST_DATA(element))->vertex;
		if(vertex->color == white && vertex->d < min){
			min = vertex->d;
			adjlist = LIST_DATA(element);
			}
		}
		
		vertex = (PathVertex*) adjlist->vertex;
		vertex->color = black;
		
		for(setelement=SET_FIRST(adjlist->adjacent);setelement;setelement=SET_NEXT(setelement)){
			adjvertex = SET_DATA(setelement);
			graph_adjlist(graph,adjvertex,&adjadjlist);
			if(((PathVertex*) adjadjlist->vertex)->color == white)
				relax(vertex,(PathVertex*) adjadjlist->vertex,adjvertex->weight);
			}
		
		i++;
		}
		
		pathlist = list_create(NULL);
		
		for(element=LIST_HEAD(graph->adjlists);element;element=LIST_NEXT(element)){
		vertex = ((AdjList*) LIST_DATA(element))->vertex;
		if(vertex->color == black)
			list_ins_next(pathlist,NULL,vertex);
			}
return pathlist;
			}