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

#include "graph_dfs.h"



static int graph_dfs_main(Graph* graph,AdjList* adjlist,List* dfslist);

List* graph_dfs(Graph* graph)
{
List* dfslist;
ListElmt* element;	
DFSVertex* vertex;

	
for(element = LIST_HEAD(graph->adjlists);element;element = LIST_NEXT(element)){
	vertex = ((AdjList*) LIST_DATA(element))->vertex;
	vertex->color = white;
	}

 dfslist = list_create(NULL);
	
 for(element = LIST_HEAD(graph->adjlists);element;element = LIST_NEXT(element)){
	vertex = ((AdjList*) LIST_DATA(element))->vertex;
  if(vertex->color == white)
		if(graph_dfs_main(graph,(AdjList*) LIST_DATA(element),dfslist)){
		 	list_destroy(dfslist);
		 	return NULL;
		 }
	 }	 
		 return dfslist;
}


static int graph_dfs_main(Graph* graph,AdjList* adjlist,List* dfslist)
{
AdjList* adjadjlist;
DFSVertex *vertex,*adjvertex;
SetElmt* setelement;
int res;
	
vertex = (DFSVertex*) adjlist->vertex;
vertex->color = gray;
	
for(setelement=SET_FIRST(adjlist->adjacent);setelement;setelement=SET_NEXT(setelement)){
	adjvertex = (DFSVertex*) SET_DATA(setelement);
	if(adjvertex->color == white){
		
		if(graph_adjlist(graph,(void*) adjvertex,&adjadjlist)){
			list_destroy(dfslist);
			dfslist = NULL;
			return -1;
			}
			
		if(res = graph_dfs_main(graph,(AdjList*) adjadjlist,dfslist))
			return res;
	}
	}
	
	vertex->color = black;
	
	list_ins_next(dfslist,NULL,(void*) vertex);


return 0;	
}