#include <Graphics.h>
#include <StrStream.H>
#include <IOManip.H>

/* *********************************************************************** */
/* CALCULO DEL CAMINO MINIMO POR EL ALGORITMO DE FLOYD
/* *********************************************************************** */
//IMPLEMENTACION EN MATRICES
//Conjuntos seg£n teor¡a de grafos, que se forman:
//Grafo = {R, S, T, U}            conjunto de v‚rtices

//Relaci¢n={(R,R),(R,S),(S,R),(S,U),(T,S),(U,R),(U,T)} conjunto de aristas
//Pesos =  {  7,    5,    7,    2,   3,    4,     1  }

// Se implementar  el algoritmo de Warshall, modificado para el camino m¡nimo

const N=4, Infinito=150;
char Nombre[N][15]={"R", "S", "T", "U"}, Mensaje[80];
int Arista[N][N]={7 , 5 , 0 , 0 ,    //caminos entre los nodos o pesos
									7 , 0 , 0 , 2 ,
									0 , 3 , 0 , 0 ,
									4 , 0 , 1 , 0 };
//---------------------------------------------------------------------------
void AsignarCadena(char *cadena2, char *cadena1){

	while(*cadena1){
		*cadena2 = *cadena1;
		cadena2++;
		cadena1++;
	}
	*cadena2 = *cadena1;  //Siempre debe ser NULL lo que asigne aqu¡
}
//---------------------------------------------------------------------------
//La siguiente funci¢n reemplaza a strcat del archivo a incluir string.h
void ConcatenarCadenas(char *cadena2, char *cadena1){
	while (*cadena2) //Encuentra final de cadena2
		cadena2++;

	while(*cadena1){  //a¤ade contenido de cadena1
		*cadena2 = *cadena1;
		cadena2++;
		cadena1++;
	}
	*cadena2 = *cadena1;  //Siempre debe ser NULL lo que asigne aqu¡
}

//---------------------------------------------------------------------------
void AlgoritmoDeFloyd(){
	int i, j, k, x=10, y=50;
	struct MatrizDeFloyd{
		int Distancia;
		char Trayectoria[100];
	} W[N][N];

	for(i=0; i<N; i++)       //Se inicializa la matriz de Floyd
		for(j=0; j<N; j++){
			if(Arista[i][j]==0){
				W[i][j].Distancia = Infinito;
				AsignarCadena(W[i][j].Trayectoria, "\0");
			}
			else{
				W[i][j].Distancia = Arista[i][j];
				AsignarCadena(W[i][j].Trayectoria, Nombre[i]);
				ConcatenarCadenas(W[i][j].Trayectoria, "->");
				ConcatenarCadenas(W[i][j].Trayectoria, Nombre[j]);
			}
		}

	for(k=0; k<N; k++)
		for(i=0; i<N; i++)
			for(j=0; j<N; j++)
				if(W[i][j].Distancia > (W[i][k].Distancia + W[k][j].Distancia) ){
					W[i][j].Distancia = W[i][k].Distancia + W[k][j].Distancia;
					AsignarCadena(W[i][j].Trayectoria, W[i][k].Trayectoria);
					ConcatenarCadenas(W[i][j].Trayectoria, " ");
					ConcatenarCadenas(W[i][j].Trayectoria, W[k][j].Trayectoria);
					ConcatenarCadenas(W[i][j].Trayectoria, " ");
				}

	cleardevice();
	outtextxy(x, 10, "Caminos minimos entre nodos: ");
	outtextxy(x, 30,  "DESDE         HASTA        DISTANCIA     TRAYECTORIA MINIMA");
	for(i=0; i<N; i++)
		for(j=0; j<N; j++)
			if(W[i][j].Distancia){
				ostrstream(Mensaje,80) << setiosflags(ios::left)
						<< setw(15) << Nombre[i]
						<< setw(15) << Nombre[j]	 << setw(15) << W[i][j].Distancia
						<< setw(15) << W[i][j].Trayectoria << ends;
				outtextxy(x,y, Mensaje);
				y+=20;
			}
}
//---------------------------------------------------------------------------
void AristasDelGrafo(){
	int x=10, y=50;
	cleardevice();
	outtextxy(x,10,
			 "Los siguientes son los caminos(aristas) que existen en el grafo:");
	outtextxy(x,30, "DESDE         HASTA        DISTANCIA");
	for(int i=0; i<N; i++)
		for(int j=0; j<N; j++)
			if(Arista[i][j]){
				ostrstream(Mensaje,80) << setiosflags(ios::left)
								<< setw(15) << Nombre[i]
								<< setw(15) << Nombre[j]
								<< setw(15) << Arista[i][j] << ends;
				outtextxy(x,y, Mensaje);
				y+=20;
			}
	cin.get();
}
/* *********************************************************************** */
/*    FIN DEL MODULO DEL CALCULO DEL CAMINO MINIMO
/* *********************************************************************** */

void main(){
	int Manejador = DETECT, Modo;
	initgraph (&Manejador, &Modo, "\\tc\\bgi");

	AristasDelGrafo();
	AlgoritmoDeFloyd();
	cin.get();
}