initial_population.h

#ifndef __INITIAL_POPULATION_H__
#define __INITIAL_POPULATION_H__
#define CITY_STOP 3
#define POPULATION_SIZE 100
#define NB_GENERATIONS 6000
#define MUTATION_RATE 0.2
#define CROSSOVER_RATE 0.8


/**
 * @brief Represents a node in the graph with distance and time metrics
 */
typedef struct {
    float distance;  /* Distance between two nodes */
    float time;      /* Time required to travel between two nodes */
} Node;

/**
 * @brief Represents a delivery path for a single deliverer
 */
typedef struct {
    int *path;              /* Array of node indices representing the path */
    int path_length;        /* Number of nodes in the path */
    float total_time;       /* Total time for this path */
    float total_distance;   /* Total distance for this path */
} Path;

/**
 * @brief Represents an individual solution in the genetic algorithm
 */
typedef struct {
    Path* deliverers_paths;       /* Array of paths, one per deliverer */
    int nb_deliverers;           /* Number of deliverers used */
    int* visited;                /* Array marking visited cities */
    int nb_nodes;                /* Total number of nodes/cities */
    float total_time;            /* Total time for all deliverers */
    float total_distance;        /* Total distance for all deliverers */
    float fitness;               /* Fitness score of this individual */
} Individual;

/**
 * @brief Represents a population of individuals
 */
typedef struct {
   Individual* population[POPULATION_SIZE];  /* Array of individual pointers */
}Population;

/**
 * @brief Check if all cities have been visited
 * @param visited_cities Array indicating which cities have been visited (1=visited, 0=not visited)
 * @param nb_nodes Total number of nodes/cities in the graph
 * @return 1 if all cities have been visited, 0 otherwise
 */
int all_cities_visited(int* visited_cities, int nb_nodes);

/**
 * @brief Mark cities as visited based on a deliverer's path
 * Updates the visited_cities array to reflect cities covered by this path
 * @param deliverer_path The path taken by a deliverer
 * @param visited_cities Array to update with visited status
 */
void mark_used_cities(Path* deliverer_path, int* visited_cities);

/**
 * @brief Initialize memory for a delivery path
 * Allocates and initializes a Path structure with given parameters
 * @param path_length Number of nodes in the path
 * @param current_path Array of node indices representing the path
 * @param total_time Total time for this path
 * @param total_distance Total distance for this path
 * @return Pointer to newly allocated Path, or NULL on failure
 */
Path* initialize_path(int path_length, int* current_path, float total_time, float total_distance);

/**
 * @brief Free memory allocated for a path
 * Safely deallocates all memory associated with a Path structure
 * @param path Pointer to the Path to free
 */
void free_path(Path* path);

/**
 * @brief Generate a delivery path for a single deliverer using greedy approach
 * Creates a path starting from depot (node 0), visiting unvisited cities while respecting
 * time constraints, and returning to depot
 * @param graph 2D array representing the network with distances and times
 * @param current_node Starting node for path generation
 * @param current_path Array to store the path being built
 * @param visited Local array tracking visited nodes in this path
 * @param path_length Current length of the path being built
 * @param total_time Accumulated time for the current path
 * @param total_distance Accumulated distance for the current path
 * @param start_node The depot node (typically 0)
 * @param nb_nodes Total number of nodes in the graph
 * @param visited_cities Global array of cities already assigned to other deliverers
 * @return Pointer to completed Path, or NULL if no valid path found
 */
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);

/**
 * @brief Copy a path into an individual's deliverer paths array
 * Performs deep copy of path data into the individual's deliverer_paths array
 * @param individual Target individual to copy path into
 * @param final_path Source path to copy from
 */
void copy_path_to_individual(Individual* individual, Path* final_path);

/**
 * @brief Initialize memory for an individual solution
 * Allocates and initializes all necessary memory for an Individual structure
 * @param nb_nodes Total number of nodes in the problem
 * @return Pointer to newly allocated Individual, or NULL on failure
 */
Individual* initialize_individual(int nb_nodes);

/**
 * @brief Free all memory allocated for an individual
 * Safely deallocates all memory associated with an Individual structure
 * including all paths and arrays
 * @param individual Pointer to the Individual to free
 */
void free_individual(Individual* individual);

/**
 * @brief Generate a complete individual solution
 * Creates paths for multiple deliverers until all cities are visited,
 * respecting time constraints for each deliverer
 * @param graph 2D array representing the network
 * @param nb_nodes Total number of nodes in the graph
 * @return Pointer to newly generated Individual, or NULL on failure
 */
Individual* generate_individual(Node** graph, int nb_nodes);

/**
 * @brief Generate initial population for genetic algorithm
 * Creates a population of randomly generated individuals
 * @param graph 2D array representing the network
 * @param nb_nodes Total number of nodes in the graph
 * @return Pointer to newly generated Population, or NULL on failure
 */
Population* generate_population(Node** graph, int nb_nodes);

/**
 * @brief Free all memory allocated for a population
 * Safely deallocates all memory associated with a Population structure
 * including all individuals
 * @param population Pointer to the Population to free
 * @param nb_nodes Total number of nodes (used for validation)
 */
void free_population(Population* population, int nb_nodes);

/**
 * @brief Print population details for debugging
 * Outputs formatted information about all individuals in the population
 * @param population Pointer to the Population to print
 */
void print_population(Population* population);

#endif