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

#include "bfs.h"
#include "queue.h"


List* bfs(Graph* graph,BFSVertex* start)
{
Queue* queue;
ListElmt* element;
BFSVertex *vertex,*adjvertex;	
AdjList *adjlist = NULL,*adjadjlist = NULL;
SetElmt* setelmt;


	
for(element=LIST_HEAD(graph->adjlists);element;element=LIST_NEXT(element)){
	adjlist = (AdjList*) LIST_DATA(element);
	if(graph->match((void*) start,adjlist->vertex)){
		((BFSVertex*) adjlist->vertex)->color = gray;
		((BFSVertex*) adjlist->vertex)->hops = 0;
		}else{
		((BFSVertex*) adjlist->vertex)->color = white;
		((BFSVertex*) adjlist->vertex)->hops = -1;
			}
	}
	
	
	if(!(queue = queue_create()))
		return NULL;
	
	graph_adjlist(graph,(void*) start,&adjlist);
	queue_enqueue(queue,(void*) adjlist);
	
	while(QUEUE_SIZE(queue)){
    		
		adjlist = (AdjList*) QUEUE_DATA(QUEUE_PEEK(queue));
		
		for(setelmt=SET_FIRST(adjlist->adjacent);setelmt;setelmt=SET_NEXT(setelmt)){
	  			adjvertex = (BFSVertex*) SET_DATA(setelmt);
			    if(adjvertex->color == white){
			      adjvertex->color = gray;
						graph_adjlist(graph,(void*) adjvertex,&adjadjlist);
						adjvertex->hops = ((BFSVertex*) adjlist->vertex)->hops + 1;
						queue_enqueue(queue,(void*) adjadjlist);
						}
			}
	queue_dequeue(queue,(void**) &adjlist);
	((BFSVertex*) adjlist->vertex)->color = black;
	}
	
	queue_destroy(queue);
	return NULL;
}