/**

 * @brief Calcola le componenti fortemente connesse di un grafo graph con l'algoritmo di Kosaraju

 * Nota: per comodita', restituiamo la foresta delle cfc. Quando la stampate pero' fate capire che e' un multiinsieme e non una foresta

 *

 * @param graph il grafo da esaminare

 * @return la foresta delle componenti fortemente connesse restituita dall'algoritmo di Kosaraju

 *

 */

upo_list_t ordine_dec(upo_list_t f)

{

	upo_list_t f_ord=upo_create_list(sizeof(struct finevertice), NULL);

	struct finevertice *tmp;

	int max, i, c=-1;

	while(upo_list_size(f)!=0)

	{

		max=-1;

		for(i=0; i<upo_list_size(f); i++)

		{

			if(((struct finevertice *)upo_get(f, i))->tempofine>max)

			{

				max=((struct finevertice *)upo_get(f, i))->tempofine;

				tmp=(struct finevertice *)upo_get(f, i);

				c=i;

			}

		}

		upo_add_last(f_ord, tmp);

		upo_remove(f, c);

	}

	return f_ord;

}



void DFS_ric_cfc(upo_dirgraph_t graph, upo_list_t f, int* cfc, int* color, int u, int* t, int* k)

{

	int i;

	(*t)++;

	cfc[*k]=u;

	(*k)++;

	color[u]=GRAY;

	for(i=0; i<graph->n; i++)

	{

		if(graph->adj[u][i]!=0)

		{

			if(color[i]==WHITE)

			{

				DFS_ric_cfc(graph, f, cfc, color, i, t, k);

			}

		}

	}

	color[u]=BLACK;

	struct finevertice *tmp;

	tmp=upo_get(f, u);

	tmp->tempofine=*t;

}



int** upo_DFS_tot_cfc(upo_dirgraph_t graph, upo_list_t f) {

	int color[graph->n];

	int i, j, *t=malloc(sizeof(int)), *k=malloc(sizeof(int));



	/*ho usato il metodo come per graph->adj*/

	int **cfc=malloc(graph->n*sizeof(int**));

	if(cfc==NULL)

	{

		perror("Matrice di cfc non creata");

		abort();

	}

	for(i=0; i<graph->n; i++)

		cfc[i]=malloc(graph->n*sizeof(int*));

	for(i=0; i<graph->n; i++)

		for(j=0; j<graph->n; j++)

			cfc[i][j]=-1;



	/*visita dfs. l'inizializza l'ho dovuta mettere ad ogni vertice o non ottenevo le cfc complete ma temo sia sbagliato*/

	*t=0;

	for(i=0; i<graph->n; i++)

	{

		*k=0;

		inizializza(color, NULL, graph->n);

		DFS_ric_cfc(graph, f, cfc[i], color, ((struct finevertice *)upo_get(f, i))->vertice, t, k);

	}

	return cfc;

}



int* insiemecfc(int** matrix, int n)

{

	int i, j, d=1;

	int* cfc=malloc(sizeof(int));

	if(cfc==NULL)

	{

		perror("Insieme di cfc non creata");

		abort();

	}

	for(i=0; i<n; i++)

	{

		for(j=0; j<n; j++)

		{

			if(matrix[i][j]!=-1)

			{

				cfc[d-1]=matrix[i][j];

				d++;

				cfc=realloc(cfc, d*sizeof(int));

			}

		}

		cfc[d-1]=-1;

		d++;

		cfc=realloc(cfc, d*sizeof(int));

	}

	cfc[d-1]=-2;

	return cfc;

}



int* upo_strongly_connected_components(upo_dirgraph_t graph) {

    	if(graph==NULL)

		return NULL;

	int* cfc;

	int** matrix, matrix2;

	upo_list_t f=upo_create_list(sizeof(struct finevertice), NULL);

	int i, j;



	/*vettore delle struct*/

	struct finevertice *tmp;

	for(i=0; i<graph->n; i++)

	{

		tmp=malloc(sizeof(struct finevertice));

		tmp->tempofine=-1;

		tmp->vertice=i;

		upo_add_last(f, tmp);

	}



	/*dfs sulla prima matrice con ritorno di cfc per ogni vertice*/

	matrix=upo_DFS_tot_cfc(graph, f);


	upo_list_t f_ord=ordine_dec(f);



	/*grafo trasposto*/

	upo_dirgraph_t grapht=upo_dirgraph_create(graph->n);

	for(i=0; i<graph->n; i++)

		for(j=0; j<graph->n; j++)

			grapht->adj[i][j]=graph->adj[j][i];



	/*dfs sulla seconda matrice con ritorno di cfc per ogni vertice*/

	matrix2=upo_DFS_tot_cfc(grapht, f_ord);

	for(i=0; i<graph->n; i++)

	{

		printf("\n");

		for(j=0; j<graph->n; j++)

			printf(" %d", matrix[i][j]);

	}



	cfc=insiemecfc(matrix2, graph->n);



	/*implementare l'intersezione tra le matrici e inserirle nel vettore da ritornare*/

	return cfc;

}