initial_population.c

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "initial_population.h"
#include "extract_cities_csv.h"
#include "utils.h"

int all_cities_visited(int* visited_cities, int nb_nodes){
    int i;
    for(i = 1; i < nb_nodes; i++){
        if(visited_cities[i] == 0){
            return 0;
        }
    }
    return 1;
}

void mark_used_cities(Path* deliverer_path, int* visited_cities) {
    int j;
    /* Skip depot at start/end */
    for (j = 1; j < deliverer_path->path_length - 1; j++) {
        visited_cities[deliverer_path->path[j]] = 1;
    }
}

void shuffle_indices(int* indices, int count) {
    int i, j, tmp;
    for (i = count - 1; i > 0; i--) {
        j = rand() % (i + 1);
        tmp = indices[i];
        indices[i] = indices[j];
        indices[j] = tmp;
    }
}

Path* initialize_path(int path_length, int* current_path, float total_time, float total_distance){
    int i;
    Path* path;
    path = malloc(1 * sizeof(Path));
    if(!path){
        return NULL;
    }
    path->path = malloc(path_length * sizeof(int));
    if(!(path->path)){
        free(path);
        path = NULL;
        return NULL;
    }
    for (i = 0; i < path_length; i++) {
        path->path[i] = current_path[i];
    }
    path->path_length = path_length;
    path->total_time = total_time;
    path->total_distance = total_distance;
    return path;
}

void free_path(Path* path){
    if(!path){
        return;
    }
    if(path->path){
        free(path->path);
    }
    free(path);
    path = NULL;
}

Path* generate_path(Node** graph, int current_node, int* current_path, int* visited, 
    int path_length, float total_time, float total_distance, int start_node, 
    int nb_nodes, int* visited_cities) {
    float time_to_next;
    float final_time;
    float final_distance;
    float projected_time;
    float return_time;
    int i;
    int next_node;
    int continue_path;
    int city_stops;
    Path* final_path;
    int* indices = malloc(nb_nodes * sizeof(int));
    if(!indices){
        return NULL;
    }
    for (i = 0; i < nb_nodes; i++) {
        indices[i] = i;
    }
    city_stops = 0;
    projected_time = 0;
    continue_path = 1;
    visited[current_node] = 1;
    current_path[path_length] = current_node;
    path_length++;
    shuffle_indices(indices, nb_nodes);
    while (continue_path) {
        continue_path = 0;
        for (i = 0; i < nb_nodes; i++) {
            next_node = indices[i];
            if (!visited[next_node] && !visited_cities[next_node]) {
                time_to_next = total_time + graph[current_node][next_node].time;
                return_time = graph[next_node][start_node].time;
                projected_time = time_to_next + return_time + (city_stops + 1) * CITY_STOP;
                /* Check if we can visit this node and still return within time limit */
                if (projected_time <= MAX_TIME_PATH - (3*(path_length-1))) {
                    /* Accept next node */
                    total_time = time_to_next;
                    total_distance += graph[current_node][next_node].distance;
                    current_path[path_length] = next_node;
                    visited[next_node] = 1;
                    current_node = next_node;
                    path_length++;
                    city_stops++;
                    continue_path = 1;
                    shuffle_indices(indices, nb_nodes);
                    break;
                }
            }
        }
    }
    /* Calculate final metrics including return to depot */
    final_time = total_time + graph[current_node][start_node].time + (city_stops*CITY_STOP);
    final_distance = total_distance + graph[current_node][start_node].distance;
    if (final_time <= MAX_TIME_PATH - (3*(path_length-2)) && final_time > 0) {
        current_path[path_length] = start_node;
        path_length++;
        final_path = initialize_path(path_length, current_path, final_time, final_distance);
        if(final_path){
            free(indices);
            return final_path;
        }
        else{
            free(indices);
            return NULL;
        }
    }
    free(indices);
    return NULL;
}

Individual* initialize_individual(int nb_nodes) {
    Individual* individual;
    int i;
    individual = (Individual*)malloc(sizeof(Individual));
    if (!individual) {
        fprintf(stderr, "Memory allocation error (individual).\n");
        return NULL;
    }
    individual->nb_deliverers = 0;
    individual->total_time = 0;
    individual->total_distance = 0;
    individual->fitness = 0;
    individual->nb_nodes = nb_nodes;
    individual->visited = (int*)malloc(nb_nodes * sizeof(int));
    if (!individual->visited) {
        fprintf(stderr, "Memory allocation error (individual->visited).\n");
        free(individual);
        return NULL;
    }
    for (i = 0; i < nb_nodes; i++) {
        individual->visited[i] = 0;
    }
    individual->deliverers_paths = (Path*)malloc(nb_nodes * sizeof(Path));
    if (!individual->deliverers_paths) {
        fprintf(stderr, "Memory allocation error (individual->deliverers_paths).\n");
        free(individual->visited);
        free(individual);
        return NULL;
    }
    return individual;
}

void free_individual(Individual* individual) {
    int i;
    if (!individual) {
        return;
    }
    /* Free each path individually */
    if (individual->deliverers_paths) {
        for (i = 0; i < individual->nb_deliverers; i++) {
            if (individual->deliverers_paths[i].path) {
                free(individual->deliverers_paths[i].path);
            }
        }
        free(individual->deliverers_paths);
    }
    if (individual->visited) {
        free(individual->visited);
    }
    free(individual);
}

void copy_path_to_individual(Individual* individual, Path* final_path) {
    int i;
    if(!individual || !(final_path)){
        fprintf(stderr, "copy_path_to_individual: NULL pointer passed\n");
        return;
    }
    /* Validate indices */
    if (individual->nb_deliverers >= individual->nb_nodes) {
        fprintf(stderr, "copy_path_to_individual: Too many deliverers\n");
        return;
    }
    individual->deliverers_paths[individual->nb_deliverers].path_length = final_path->path_length;
    individual->deliverers_paths[individual->nb_deliverers].total_time = final_path->total_time;
    individual->deliverers_paths[individual->nb_deliverers].total_distance = final_path->total_distance;
    /* Allocate memory for the path */
    individual->deliverers_paths[individual->nb_deliverers].path = malloc(final_path->path_length * sizeof(int));
    if (!(individual->deliverers_paths[individual->nb_deliverers].path)) {
        fprintf(stderr, "copy_path_to_individual: malloc failed\n");
        return;
    }
    /* Copy path data */
    for (i = 0; i < final_path->path_length; i++) {
        individual->deliverers_paths[individual->nb_deliverers].path[i] = final_path->path[i];
    }
}

Individual* generate_individual(Node** graph, int nb_nodes) {
    Individual* individual;
    int* visited_local;
    int* current_path;
    Path* final_path;
    int i;
    individual = initialize_individual(nb_nodes);
    if(!individual){
        return NULL;
    }
    while (!all_cities_visited(individual->visited, nb_nodes)) {
        /* Prepare for one deliverer */
        visited_local = malloc(nb_nodes * sizeof(int));
        if(!visited_local){
            free_individual(individual);
            return NULL;
        }
        for(i = 0; i < nb_nodes; i++){
            visited_local[i] = 0;
        }
        current_path = malloc(nb_nodes * sizeof(int));
        if(!current_path){
            free(visited_local);
            free_individual(individual);
            return NULL;
        }        
        for(i = 0; i < nb_nodes; i++){
            current_path[i] = 0;
        }
        
        /* Generate candidate paths for this deliverer avoiding already visited cities */
        final_path = generate_path(graph, 0, current_path, visited_local, 0, 0, 0,
                              0, nb_nodes, individual->visited);

        /* Pick first valid path */
        if(!final_path){
            /* Free temporary resources */
            free(visited_local);
            free(current_path);
            /* If no path is possible, stop to avoid infinite loop */
            break;
        }
        else{
            copy_path_to_individual(individual, final_path);
            /* Mark cities as visited */
            mark_used_cities(&(individual->deliverers_paths[individual->nb_deliverers]), individual->visited);

            /* Update stats */
            individual->total_time += final_path->total_time ;
            individual->total_distance += final_path->total_distance;
            individual->nb_deliverers++;
            update_fitness(individual);
            free_path(final_path);
            /* Free temporary resources */
            free(visited_local);
            free(current_path);
        }
    }
    return individual;
}

Population* generate_population(Node** graph, int nb_nodes){
    int i;
    Individual* individual;
    Population* initial_population = (Population*)malloc(1 * sizeof(Population));
    if(!initial_population){
        return NULL;
    }
    /* Initialize pointers to NULL */
    for (i = 0; i < POPULATION_SIZE; i++) {
        initial_population->population[i] = NULL;
    }
    for (i = 0; i < POPULATION_SIZE; i++) {
        individual = generate_individual(graph, nb_nodes);
        if (!individual) {
            fprintf(stderr, " Failed to generate individual %d\n", i);
            /* Continue with other individuals */
        }
        else{
            initial_population->population[i] = individual;
        }
    }
    return initial_population;
}

void free_population(Population* population, int nb_nodes){
    int i;
    if(!population){
        return;
    }
    for (i = 0; i < POPULATION_SIZE; i++) {
        if (population->population[i]) {  /* Check before freeing */
            free_individual(population->population[i]);
        }
    }
    free(population);
}