P4 ALgo

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <time.h>
#include <sys/time.h>
#define TAM_MAX 1600

// ------------------------------  X  ----------------------------------
// =====================================================================
// ------------------------------  X  ----------------------------------

 typedef int ** matriz;

 typedef struct {
    int x, y, peso;
 } arista;

 typedef arista tipo_elemento;

 typedef struct {
    int cabeza, final, tamano;
    tipo_elemento vector[TAM_MAX];
 } cola;

// ------------------------------  X  ----------------------------------
// =====================================================================
// ------------------------------  X  ----------------------------------

    double microsegundos() {
        /* obtiene la hora del sistema en microsegundos */
        struct timeval t;

        if (gettimeofday(&t, NULL) < 0 )
            return 0.0;
        return (t.tv_usec + t.tv_sec * 1000000.0);
    }

// ------------------------------  X  ----------------------------------
// =====================================================================
// ------------------------------  X  ----------------------------------



// ------------------------------  X  ----------------------------------
// =====================================================================
// ------------------------------  X  ----------------------------------

 void crear_cola(cola *c){


     c->tamano = 0;
     c->cabeza = 0;
     c->final = -1;
 }

// ------------------------------  X  ----------------------------------
// =====================================================================
// ------------------------------  X  ----------------------------------

 int cola_vacia(cola c){


    return (c.tamano==0);
 }

// ------------------------------  X  ----------------------------------
// =====================================================================
// ------------------------------  X  ----------------------------------

 void incrementar(int *x){ /*ESTO DEBE SER PRIVADO*/


    if (++(*x) == TAM_MAX)
        *x = 0;
 }

// ------------------------------  X  ----------------------------------
// =====================================================================
// ------------------------------  X  ----------------------------------

 void insertar(tipo_elemento x, cola * c){


    if (c->tamano == TAM_MAX){
        printf("error: cola llena: %d\n", c->tamano);
        exit(EXIT_FAILURE);
    }
    c->tamano++;
    incrementar(&(c->final));
    c->vector[c->final] = x;
 }

// ------------------------------  X  ----------------------------------
// =====================================================================
// ------------------------------  X  ----------------------------------

 tipo_elemento primero(cola c){


    if (cola_vacia(c)){
        printf("error: cola vacia\n");
        exit(EXIT_FAILURE);
    }
    return(c.vector[c.cabeza]);
 }

// ------------------------------  X  ----------------------------------
// =====================================================================
// ------------------------------  X  ----------------------------------

 tipo_elemento quitar_primero(cola *c){
    tipo_elemento x;


    if (cola_vacia(*c)) {
        printf("error: cola vacia\n");
        exit(EXIT_FAILURE);
    }
    c->tamano--;
    x = c->vector[c->cabeza];
    incrementar(&(c->cabeza));
    return x;
 }

// ------------------------------  X  ----------------------------------
// =====================================================================
// ------------------------------  X  ----------------------------------

void mostrar_cola(cola c){
    int j = c.tamano;
    int cont = 0;


    printf("Aristas: \n");
        for(int i = 0; i<j; i++){
            printf("(%i,%i) ",primero(c).x,
            primero(c).y);
            cont += primero(c).peso;
            quitar_primero(&c);
        }
    printf("\nPeso: %i\n\n", cont);
}

// ------------------------------  X  ----------------------------------
// =====================================================================
// ------------------------------  X  ----------------------------------

 matriz crear_matriz(int n) {
    int i;
    matriz aux;


    if ((aux = malloc(n*sizeof(int *))) == NULL)
        return NULL;
    for (i=0; i<n; i++)
        if ((aux[i] = malloc(n*sizeof(int))) == NULL)
            return NULL;
    return aux;
 }

// ------------------------------  X  ----------------------------------
// =====================================================================
// ------------------------------  X  ----------------------------------

 void inicializar_matriz(matriz m, int n) {
    /* Crea un grafo completo no dirigido con valores aleatorios entre 1 y n */
    int i, j;


    for (i=0; i<n; i++)
        for (j=i+1; j<n; j++)
            m[i][j] = rand() % n + 1;

    for (i=0; i<n; i++)
        for (j=0; j<=i; j++)
            if (i==j)
                m[i][j] = 0;
            else
                m[i][j] = m[j][i];
 }

// ------------------------------  X  ----------------------------------
// =====================================================================
// ------------------------------  X  ----------------------------------

 void liberar_matriz(matriz m, int n) {


    int i;
    for (i=0; i<n; i++)
        free(m[i]);
    free(m);
 }

// ------------------------------  X  ----------------------------------
// =====================================================================
// ------------------------------  X  ----------------------------------

 void prim(matriz m, int nodos, cola *aristas) {
    int min, i, j, k=0;
    int cont = 0;
    arista a;
    int *masProximo = (int *) malloc(nodos*sizeof(int));
    int *distanciaMinima = (int *) malloc(nodos*sizeof(int));


    crear_cola(aristas);
    distanciaMinima[0] = -1;
    for(i = 1; i < nodos; i++) {
        masProximo[i] = 0;
        distanciaMinima[i] = m[i][0];
    }
      while (cont<(nodos-1)){
      cont++;
      min = INT_MAX;
        for(j=1; j<nodos; j++){
            if ((0 <=distanciaMinima[j]) && (distanciaMinima[j]<min)){
                min = distanciaMinima[j];
                k=j;
            }
        }
     a.x =  masProximo[k];
     a.y = k;
     a.peso =m[masProximo[k]][k];
     insertar(a, aristas);
     distanciaMinima[k] = -1;
     for(j=1; j<nodos; j++){
        if (m[j][k] < distanciaMinima[j]){
            distanciaMinima[j] = m[j][k];
            masProximo[j] = k;
         }
     }
     }
    free(masProximo);
    free(distanciaMinima);
 }

// ------------------------------  X  ----------------------------------
// =====================================================================
// ------------------------------  X  ----------------------------------

     void filaTabla(double time, int n, int flag) {
        double cotasub, cotaaxus, cotasobre;

        cotasub= time / (pow(n, 1.8));
        cotaaxus= time / (pow(n,2));
        cotasobre= time / (pow(n,2.2));
        if (flag==0) {
            printf("%13d%17f%14f%14f%14f\n", n, time, cotasub, cotaaxus,
               cotasobre);
        } else {
            printf("%3s%10d%17f%14f%14f%14f\n","(*)", n, time, cotasub, cotaaxus,
               cotasobre);
        }
    }

// ------------------------------  X  ----------------------------------
// =====================================================================
// ------------------------------  X  ----------------------------------

 double comprobacionTiempo (int nodos) {
        int cont = 0;
        double atime, btime;
        double time;
        matriz M;
        cola queue;


        atime = microsegundos();
        while (cont <= 10000) {
            M = crear_matriz(nodos);
            inicializar_matriz(M, nodos);
            prim(M, nodos, &queue);
            liberar_matriz(M, nodos);
            cont++;
        }
        btime = microsegundos();
        time = btime - atime;

        cont = 0;
        atime = microsegundos();
        while (cont <= 10000) {
            M = crear_matriz(nodos);
            inicializar_matriz(M, nodos);
            liberar_matriz(M, nodos);
            cont++;
        }
        btime = microsegundos();
        time = time - (btime - atime);
        time = time / cont;

        return time;
    }

// ------------------------------  X  ----------------------------------
// =====================================================================
// ------------------------------  X  ----------------------------------

    void test2() {
        int nodos;
        matriz M;
        cola queue;
        double a_time, b_time, t_time;
        int flag;

        printf("Cálculo de tiempos del algoritmo de Prim. \n");
        printf("========================================================================\n");
        printf("%13s%17s%14s%14s%14s\n", "n", "t(n)", "t(n)/n^1.8",
                "t(n)/n^2", "t(n)/n^2.2");
        for (nodos = 25; nodos <= 1600; nodos = nodos * 2) {
            flag = 0;
            a_time = microsegundos();
            M = crear_matriz(nodos);
            inicializar_matriz(M, nodos);
            prim(M, nodos, &queue);
            liberar_matriz(M, nodos);
            b_time = microsegundos();
            t_time = b_time - a_time;
            if (t_time < 500) {
                t_time = comprobacionTiempo(nodos);
                flag = 1;
            }
            filaTabla(t_time, nodos, flag);
        }
    }

// ------------------------------  X  ----------------------------------
// =====================================================================
// ------------------------------  X  ----------------------------------

 void matrizTest(matriz mTest, int flag){

    int m1[4][4]= {{0,1,4,7},{1,0,2,8},{4,2,0,3},{7,8,3,0}};
    int m2[5][5]= {{0,1,8,4,7},{1,0,2,6,5},{8,2,0,9,5},
                    {4,6,9,0,3},{7,5,5,3,0}};
    int m3[7][7]= {{0,7,99,5,99,99,99},{7,0,8,9,7,99,99},
                    {99,8,0,99,5,99,99},{5,9,99,0,15,6,99},
                    {99,7,5,15,0,8,9},{99,99,99,6,8,0,11},
                    {99,99,99,99,9,11,0}};

    if (flag==1){
        for(int i=0; i<4; i++){
            for(int j=0;j<4;j++){
            mTest[i][j] = m1[i][j];
            }
        }
    } else if(flag==2){

        for(int i=0; i<5; i++){
            for(int j=0;j<5;j++){
            mTest[i][j] = m2[i][j];
            }
        }
    } else{
        for(int i=0; i<7; i++){
            for(int j=0;j<7;j++){
            mTest[i][j] = m3[i][j];
            }
        }
    }

    return;
}

// ------------------------------  X  ----------------------------------
// =====================================================================
// ------------------------------  X  ----------------------------------

 void test1() {
    matriz m1 = crear_matriz(4);
    matriz m2 = crear_matriz(5);
    matriz m3 = crear_matriz(7);
    cola c;


    matrizTest(m1,1);
    prim(m1, 4, &c);
    mostrar_cola(c);

    matrizTest(m2,2);
    prim(m2, 5, &c);
    mostrar_cola(c);

    matrizTest(m3,3);
    prim(m3, 7, &c);
    mostrar_cola(c);

    liberar_matriz(m1,4);
    liberar_matriz(m2,5);
    liberar_matriz(m3,7);

 }

// ------------------------------  X  ----------------------------------
// =====================================================================
// ------------------------------  X  ----------------------------------

 int main() {
     test1();
     test2();
     return 0;
 }