graphe.c

#include "graphe.h"
graph create_graph(int num, int fourmiliere, int nourriture)
{
    graph gr = malloc(sizeof(g));
    if (gr == NULL)
    {
        return NULL;
    }
    gr->num = num;
    // init edges (links) matrix
    matrix *mat = malloc(sizeof(matrix));
    matrix_init(mat, num, num, 0);
    gr->edges = mat;

    // init pheromon matrix
    matrix *mat2 = malloc(sizeof(matrix));
    matrix_init(mat2, num, num, 1);
    gr->pheromone = mat2;
    //initialisation des variables de la matrice 
    gr->foumiliere = fourmiliere;
    gr->nourriture = nourriture;
    return gr;
}

int has_edge(graph g, int from_node, int to_node) //permet de contrôle s'il y a une arête entre deux sommets
{
    assert(g != NULL);
    assert(from_node < g->num);
    assert(to_node < g->num);
    return g->edges->data[from_node][to_node];
}

void add_edge(graph g, int from_node, int to_node, double distance) //permet d'ajouter une arête entre deux sommets
{
    assert(g != NULL);
    assert(from_node < g->num);
    assert(to_node < g->num);
    if (has_edge(g, from_node, to_node))
    {
        return;
    }

    g->edges->data[from_node][to_node] = distance;
}

graph main_create_graph(char *filename) //crée la matrice à partir d'un fichier csv
{
    graph g;
    FILE *fp;
    char buffer[100];

    fp = fopen(filename, "r"); //ouverture fichier 
    //contrôle ouverture fichier
    if (fp == NULL)
    {
        printf("non ouvert\n");
    }

    int line_counter = 0;
    while (fgets(buffer, 100, fp) != NULL)
    {

        int a, b;
        int c_int;
        double c;

        //récupérer les données de la première ligne qui indique les informations de la matrice
        if (line_counter == 0)
        {
            sscanf(buffer, "%d %d %d", &a, &b, &c_int);
            g = create_graph(a, b, c_int);
        }

        else //récupère les données pour créer les arêtes en les sommets
        {
            sscanf(buffer, "%d %d %lf", &a, &b, &c);
            add_edge(g, a, b, c);
        }
        line_counter++;
    }

    fclose(fp);
    return g;
}

//afin d'alléger le code la fonction ci-dessous permet de calculer [phéromone * (1/arête)]
double ph_x_dist(graph g, int from, int to) 
{
    double ph_x_dst = g->pheromone->data[from][to] * (1 / g->edges->data[from][to]);
    return ph_x_dst;
}

int path_probability_taken(graph g, int noeud)
{
    // initialisation des tableaux à 0
    double tab[g->num];
    double tab_cumul[g->num];
    for (int k = 0; k < g->num; k++)
    {
        tab[k] = 0;
        tab_cumul[k] = 0;
    }
    // mettre les phéromones aux places du tableau pour le choix de l'indicee
    //cette partie du code va créer un double qui sera le dénominateur pour nos calculs du chemin
    double somme_pour_proba = 0;
    for (int r = 0; r < g->num; r++)
    {
        if (has_edge(g, noeud, r))
        {
            somme_pour_proba += ph_x_dist(g, noeud, r);
        }
    }
    //si la fourmi ne trouve pas de chemin, il y a une division par 0, mais surtout, elle ne peut choisir aucun chemin
    //donc on retourne directement le noeud
    if (somme_pour_proba == 0)
    {
        return noeud;
    }
    //A partir de là, le tableau qui stocke 
    for (int i = 0; i < g->num; i++)
    {
        if (has_edge(g, noeud, i))
        {
            //calcul qui fait [(phéromone * (1/arête))]
            //                [-----------------------] //fraction
            //                [       somme_proba     ]
            tab[i] = (g->pheromone->data[noeud][i] * (1.0 / g->edges->data[noeud][i])) / somme_pour_proba;
        }
    }
    // Calcul nombre total de phéromone
    double sum_phero = 0;
    for (int j = 0; j < g->num; j++)
    {
        sum_phero += tab[j];
    }
    // somme cumulative du tableau
    for (int x = g->num - 1; x >= 0; x--)
    {
        for (int y = 0; y <= x; y++)
        {
            tab_cumul[x] += tab[y];
        }
    }
    // calcul de la probabilité

    double chemin_probabiliste = (double)rand() / (double)RAND_MAX; // nb entre 0 et 1 pour choisir le chemin à prendre
    for (int z = 0; z < g->num; z++) //tester toutes les cases du tablea
    {
        if (chemin_probabiliste <= tab_cumul[z]) //si le nombre probabilite est plus petit que la case du tableau, on retourne la case
        {
            return z;
        }
    }
    return 0;
}

double pheromone_depose(double distance)
{
    return 1.0000 / distance; //la phéromone est déposée en fonction de la longueur parcourue
}

int launch_colonization(graph g, int nb_fourmi, double rho)
{
    int nb_fourmi_perdue = 0;
    for (int i = 0; i < nb_fourmi; i++)
    {
        frmi f = create_fourmi(g->num); //crée la fourmi
        nb_fourmi_perdue += random_path(g, 0, rho, f); //appel la fonction principal à l'algorithme
        destroy_fourmi(f); //détruit la fourmi
    }
    //retourne le nombre de fourmi perdu
    return nb_fourmi_perdue;
}

int random_path(graph g, int noeud, double rho, frmi f)
{
    // condition d'arret si on arrive au noeud final
    if (noeud == g->nourriture)
    {
        f->depose_pheromone = 1;
        return 0;
    }

    // calcul chemin aléatoire et renvoi l'indice du chemin à prendre
    int chemin_aleatoire;
    chemin_aleatoire = path_probability_taken(g, noeud);
    //si le noeud retourné par le chemin est le même que celui par lequel il est rentré, c'est que le chemin n'as pas de sortie
    if (chemin_aleatoire == noeud)
    {
        f->depose_pheromone = 0;
        return 1;//retourne 1 pour compter les fourmis perdues
    }
    // stocke la distance parcourue dans la fourmi
    f->distance += g->edges->data[noeud][chemin_aleatoire];
    // la récursivité de l'algorithme (parcours graphe en profondeur)
    //récursivité de l'algorithme
    int fourmi_perdu;
    fourmi_perdu = random_path(g, chemin_aleatoire, rho, f);

    if (f->depose_pheromone)
    {
        //calcul qui dépose les phéromone en fonction de la dissipation et des phéromones à déposer
        // (1-rho)*phéromone_precedente + pheromone_a_déposer(en fonction de la distance)
        g->pheromone->data[noeud][chemin_aleatoire] = ((1 - rho) * g->pheromone->data[noeud][chemin_aleatoire]) + pheromone_depose(f->distance);
    }
    //permet le calcul du nombre de fourmi perdu récursivement
    if (fourmi_perdu)
    {
        return 1;
    }
    //si la fourmi n'est pas perdu
    return 0;
}

void create_graph_vis(graph g)
{
    FILE *file = fopen("test2.dot", "w");
    int affiche = 0;
    fprintf(file, "digraph Test {\n");
    for (int from = 0; from < g->num; from++)
    {
        for (int to = 0; to < g->num; to++)
        {
            if (g->edges->data[from][to])
            {
                fprintf(file, "%d->%d[penwidth=2, label= %f]\n", from, to, g->edges->data[from][to]);
            }
        }
        affiche++;
    }

    fprintf(file, "}");

    fclose(file);
}

void shortest_path(graph g, frmi f, int noeud)
{
    if (noeud == g->nourriture)
    {
        stack_push(f->path, noeud);
        return;
    }
    double bigger = 0;
    int index = 0;
    for (int i = 0; i < g->num; i++)
    {
        //on teste pour récupérer l'index des phéromones les plus grandes en excluant les phéromones à 1 où il n'y a pas de chemin
        if (g->pheromone->data[noeud][i] > bigger && g->pheromone->data[noeud][i] != 1.0) 
        {
            bigger = g->pheromone->data[noeud][i]; //récupère la valeur plus grande
            index = i; //on récupère l'index du sommet de destination
            
        }
        if (i == g->num - 1)
        {
            stack_push(f->path, noeud);
            shortest_path(g, f, index);
        }
    }
    f->distance+=g->edges->data[noeud][index]; //calcul la longueur du chemin parcouru
}

void export_shortest_path(graph g1, char *filename)
{
    //on crée un fourmi éclaireuse qui ira sur les noeuds avec le plus de phéromone à la suite
    int ecrit_chemin = 0;
    int trash;
    FILE *file = fopen(filename, "w");
    fprintf(file, "the shortest path is ");
    frmi eclaireuse = create_fourmi(g1->num);
    shortest_path(g1, eclaireuse, 0);
    //part du principe que le chemin le plus court ne sera jamais un chemin qui passe par tous les noeuds
    if (eclaireuse->path->top == g1->num - 1)
    {
        destroy_fourmi(eclaireuse);
        printf("Aucun chemin ne peut être défini\n");
        return;
    }
    printf("shortest path is ");
    print_stack(*eclaireuse->path);
    printf("with a cost of %d\n", eclaireuse->distance);

    while (!stack_is_empty(*eclaireuse->path))
    {
        //afficher le chemin dans le fichier de sortie
        stack_pop(eclaireuse->path, &trash);
        fprintf(file, "[%d]", eclaireuse->path->data[ecrit_chemin]);
        ecrit_chemin++;
    }
    fprintf(file, " with a cost of %d\n", eclaireuse->distance);
    printf("\n");
    destroy_fourmi(eclaireuse);

    fclose(file);
}

void display_graph_vis()
{
    //appel système pour lancer graphviz
    system("dot -Tpng -O test2.dot");
    system("xdg-open test2.dot.png");
}

void destroy_graph(graph g)
{
    if (g->edges->data == NULL)
    {
        return;
    }

    matrix_destroy(g->edges);

    matrix_destroy(g->pheromone);
    free(g);
}