/*
	Name: Kruskal.cpp
	Copyright: Cesar A. Rodriguez C.
	Author: Cesar A. Rodriguez C.
	Date: 09/10/16 21:11
	Description: Programa para la solución al problema correspondiente al objetivo 5 del Trabajo Practico de la Materia (324) 2016-1
*/

#include <stdlib.h>
#include <conio.h>
#include <iostream>
#include <time.h>

   	const int N = 800;
   	const int Ar = (N*N)/2;

	int N_maquinas, N_aristas;
	int i, j, k, n = 1;
   	int comp_u, comp_v;
   	int aux;
   	int contador;

   	int T[N];
   	int Maquinas[N][N];
	int Conecta[N][N];
	int Adyacente[N][N];
	int componente[N][N];

	struct edge{
   		int a, u, v;
	};

	edge arista[Ar];
   	edge Aux[Ar];



void Matriz_Incidencia(int M){
//  Genera una matriz de 1 y 0 de dimensiones N_maquinas asignando la conexion entre vertices (Conectividad).
//  La matriz conectividad debe proporcionar una diagonal de ceros ya que los vertices en estos grafos no tiene bucles.
//  La matriz debe ser piramidal y es simetrica respecto a su diagonal.

system("cls");
printf( "\n\n");

	// Cabecera de la matriz
	printf("  Matriz de Incidencia \n\n");
	printf("      ");
   	for(i = 1; i <= M; i++)
    	printf( "%4d", i);
	printf("\n      ");
	for(i = 1; i <= M; i++)
    	   printf(" _ _");
   	printf( "\n\n");

	for(i = 0; i < M; i++){
		if (i >= 9)
		   printf(" %d  \b| ", i+1);
		else
		   printf(" %d  | ", i+1);
		for(j = 0; j < M; j++){
			if(i==j){
				Conecta[i][j] = 0;
				printf("%4d", Conecta[i][j]);
			}
			else if (i < j){
				Conecta[i][j] = rand() %2;
				printf("%4d", Conecta[i][j]);
			}
			else if(i > j){
				Conecta[i][j] = Conecta[j][i];
				printf("%4d", Conecta[i][j]);
			}
		}
	printf( "  | ");
	printf( "\n");
	};
}


int Verificar_Conexion(void){
// Verifica si la matriz de incidencia posee vertices aislados. En tal caso genera una nueva matriz de incidencia.
	for(j = 0; j < N_maquinas; j++){
		for(i = 0; i < N_maquinas; i++){
			if(Conecta[i][j] == 1)
				break;
			else if(i == N_maquinas-1)
				return 1;
		}
	}
}


void Matriz_Ponderada(int M){
// Crea una matriz con numeros aleatorios entre [1, 100] correspondiente a las distancia en kilometros.
printf(" \n\n");

	printf("  Matriz de Ponderacion (Kms.) \n\n");

	for(i = 0; i < M; i++){
		if (i >= 9)
		   printf(" %d  \b| ", i+1);
		else
		   printf(" %d  | ", i+1);

		for(j = 0; j < M; j++){
    		if(i==j){
			Maquinas[i][j] = 0;
			printf("%4d", Maquinas[i][j]);
			}
			else if (i < j){
			Maquinas[i][j] = rand() %100 +1;
			printf("%4d", Maquinas[i][j]);

			}
			else if(i > j){
			Maquinas[i][j] = Maquinas[j][i];
			printf("%4d", Maquinas[i][j]);
			}
		}
     	printf( "  | ");
		printf("\n");
	};
}


void Matriz_Adyacente(int M){
// Genera una matriz la cual representa grafo no dirigido particular compuesto por la multiplicacion de las matrices de incidencia y distancia.
	printf(" \n\n");
	printf("  Matriz Adyacente \n\n");

    for(i = 0; i < M; i++){
   		if (i >= 9)
		   printf(" %d  \b| ", i+1);
		else
		   printf(" %d  | ", i+1);

		for (j = 0; j < M; j++){
			Adyacente[i][j] =  Maquinas[i][j] * Conecta[i][j];
			printf("%4d", Adyacente[i][j]);
		}
	printf( "  | ");
	printf("\n");
	};
}


void Aristas(int M){
//Registra todas las aristas del grafo (Matriz Adyacente)
// aristas.a = peso de la arista;  arista.u = vertice de origen; arista.v= vertice de llegada;

	N_aristas=0;
	for(i = 0; i < M; i++){
		for(j = 0; j < M; j++){
		 	if(i < j){
		 		if(Adyacente[i][j] != 0){
		 			N_aristas++;
					arista[N_aristas].a = Adyacente[i][j];
		 			arista[N_aristas].u = i+1;
		 			arista[N_aristas].v = j+1;
				 }
			 }
		}
	}
}


void Ver_Aristas(void){
// Imprime la Matriz de Aristas
printf("\n\n");

	for(i = 1; i <= N_aristas; i++)
		printf("  arista[%d] = (%d , %d) = %d \n", i, arista[i].u, arista[i].v, arista[i].a);
}


void Heapsort(void){
//Ordenamos las aristas utilizando el metodo Heapsort

	edge H[N_aristas];
	int  temp, ult=0, x;
	arista[0].a=0;
	H[0].a=0;

	for(k = 1; k <= N_aristas; k++){

		ult = ult + 1;
		H[ult].a = arista[k].a;
		x = ult;
		while((x > 1) and (H[x].a < H[x/2].a)){
			temp = H[x].a;
			H[x].a = H[x/2].a;
			H[x/2].a = temp;
			x = x/2;
		}
	}

	int Heapsort[N_aristas];
	int r;
	int ultimo;

	for(k = 0; k <= N_aristas; k++){

		Heapsort[k]=H[1].a;         // Alamcenamos el dato que resulta ser el de menor valor entre todos.
		H[1].a = H[ult-k].a; 		// Reemplazamos la raiz por la hoja mas a la izquierda del ultimo nivel quebrando la propiedad de los arboles parcialmente ordenados
		H[ult-k].a = 0;
		ultimo = ult-k-1;

		r = 1;
		while(r <= (ultimo/2)){
		if(ultimo == 2*r){
			if( H[r].a > H[2*r].a){
				aux = H[r].a;
				H[r].a = H[2*r].a;
				H[2*r].a = aux;
				r = ultimo;
			}
			else
			r = ultimo;
		}
		else
			if(H[r].a > H[2*r].a and H[2*r].a <= H[2*r+1].a){
				aux = H[r].a;
				H[r].a = H[2*r].a;
				H[2*r].a = aux;
				r = 2*r;
			}
		else if(H[r].a > H[2*r+1].a and H[2*r+1].a < H[2*r].a){
				aux = H[r].a;
				H[r].a = H[2*r+1].a;
				H[2*r+1].a = aux;
				r = 2*r+1;
		}
		else
			r = ultimo;
		}
	}

//Asignamos el orden a las aristas

	for(k = 0; k < N_aristas; k++){
		contador = 1;
		for(i = 1; i <= N_aristas; i++){
			if(Heapsort[k] == arista[i].a){
				Aux[k+1].a = arista[i].a;
				Aux[k+1].u = arista[i].u;
				Aux[k+1].v = arista[i].v;
				arista[i].a = 0;
				contador++;
				break;
			}
		}
	}

	for(i = 1; i <= N_aristas; i++){
		arista[i].a = Aux[i].a;
		arista[i].u = Aux[i].u;
		arista[i].v = Aux[i].v;
	}


 	printf("\n\n Ordenando las Aristas: \n\n");
	for(i = 1; i <= N_aristas; i++)
		printf("  arista[%d] = (%d , %d) = %d \n", i, arista[i].u, arista[i].v, arista[i].a);
	printf("\n\n");

}


void Iniciar_Componentes(void){
// Inicio de las Componentes[] con los vertices
	for(i = 0; i <= N_maquinas; i++){
		for(j = 0; j <= N_maquinas; j++){

			if(i == 1)
				componente[i][j]= j;
			else
				componente[i][j]= 0;
		}
	}
}



void Iniciar_Ruta(void){
	// Inicio de las variables
	for(i = 0; i <= N_maquinas; i++)
		T[i]=0;
}

void Ver_Ruta(int M){
printf("\n\n");

	for(i = 1; i <= M; i++)
		printf(" Trayecto[%d] =  %d \n", i, T[i]);

}

void Ver_Componentes(void){
// Imprime la matriz componente para verificar su correcto orden
	for(i = 1; i <= N_maquinas; i++){
		for(j = 1; j <= N_maquinas; j++)
			printf("  Comp[%d][%d] =  %d", i,  j, componente[i][j]);
	printf("\n");
	}
}


int Encuentra_U(void){
	int aux;

	for(j = 1; j <= N_maquinas; j++)
			for(i = 1; i <= N_maquinas; i++)
				if(comp_u == componente[i][j])
					aux = j;
	return aux;
}



int Encuentra_V(void){
	int aux;
	for(j = 1; j <= N_maquinas; j++)
			for(i = 1; i <= N_maquinas; i++)
				if(comp_v == componente[i][j])
					aux = j;
	return aux;
}


void Kruskal(int M){
printf("\n\n");

	printf("\n\n Iniciamos las componente \n\n");
	Iniciar_Ruta();
	Iniciar_Componentes();
 	Ver_Componentes();

	for(k = 1; k <= M; k++){

		// Vertices que voy a buscar en los componentes
		comp_u = arista[k].u;
		comp_v = arista[k].v;
		printf("\n |  Interaccion t= %d  |\n", k);
		printf("------------------------------------------------------------------------------------------------------\n");
		printf("\n arista[%d] = (U, V) =  (%d, %d) \n", k, comp_u, comp_v);

		comp_u = Encuentra_U();
		comp_v = Encuentra_V();

		printf(" Las aristas estan en los componentes [%d, %d]\n\n", comp_u, comp_v);


									// KRUSKAL

		if (comp_u != comp_v){
			for(i = 1; i <= N_maquinas; i++)
				if(componente[i][comp_u] == 0)
					break;
		aux = 1;
			while(componente[aux][comp_v] != 0){

				componente[i][comp_u] = componente[aux][comp_v];
				componente[aux][comp_v] = 0;
				i++;
				aux++;
			}

		printf(" Ahora las componentes quedan de la siguiente manera: \n\n");
			Ver_Componentes();

		T[n] = arista[k].a;
		printf("\n\n  Trayecto[%d] =  %d \n\n", n, T[n]);
		Aux[n].a = arista[k].a;
		Aux[n].u = arista[k].u;
		Aux[n].v = arista[k].v;
		n++;
		}
	}// fin for (KRUSKAL)

}

void Ver_Ruta_Aristas(int M){
printf("\n\n");

	for(n = 1; n <= N_maquinas; n++)	{
		printf(" Arista[%d].a =  %d ", n, Aux[n].a);
		printf("\t Arista[%d]= (%d , %d) \n", n, Aux[n].u, Aux[n].v);
	}

}

void Peso_Arbol(int M){
printf("\n\n");

	contador = 0;
	for(n = 1; n <= M; n++)
		contador = contador + Aux[n].a;

	printf(" Peso del Arbol = %d", contador);

}


int main()
{
	srand(clock());

   	// Asignacion del numero de maquinas
   	printf( " \n Numero de maquinas? :  "); // Numero de maquinas MAXIMO es de 721. Comprobado.
   	scanf("%d",&N_maquinas);

	Matriz_Incidencia(N_maquinas);
	if(Verificar_Conexion() == 1)
		Matriz_Incidencia(N_maquinas);

	Matriz_Ponderada(N_maquinas);
	Matriz_Adyacente(N_maquinas);

	Aristas(N_maquinas);
	Ver_Aristas();
	Heapsort();

   	Kruskal(N_aristas);

	Ver_Ruta(N_maquinas);
	Ver_Ruta_Aristas(N_maquinas);
	Peso_Arbol(N_maquinas);



printf("\n\n");
system("pause");
return 0;
}