Individual.cpp

#include "Individual.h"

// ========== Public methods ==========

// locus based representation is used for an individual
void Individual::generate_neighbour_vector(const Graph &graph) {
    int no_nodes = graph.size();

    chosen_neighbour_vector_.resize(no_nodes);

    for (int i = 0; i < no_nodes; i++) {
        const std::vector<int> &current_node_neighbours = graph[i];
        int no_neighbours = current_node_neighbours.size();

        if (no_neighbours > 0) {
            int random_neighbour_index = rand() % no_neighbours;

            chosen_neighbour_vector_[i] = current_node_neighbours[random_neighbour_index];
        } else {
            chosen_neighbour_vector_[i] = i;
        }
    }
}

Individual::Individual(const Graph &graph, const Evaluator &evaluator) {
    graph_type_ = graph.get_graph_type();

    generate_neighbour_vector(graph);

    std::vector<std::vector<int>> clusters = get_clusters();

    fitness_ = evaluator(clusters);
}

// create an offspring from two parents i.e. perform crossover between two parents
// here, a binary mask of length equal to the number of nodes is randomly
// created, and an offspring is generated by selecting from the
// first parent the genes where the mask is 0, and from the second
// parent the genes where the mask is 1.
Individual::Individual(const Individual &individual1, const Individual &individual2, const Evaluator &evaluator) {
    graph_type_ = individual1.get_graph_type();

    int no_chromosomes = individual1.size();

    for (int i = 0; i < no_chromosomes; i++) {
        int bit = rand() & 1;

        if (bit == 0) {
            chosen_neighbour_vector_.push_back(individual1[i]);
        } else {
            chosen_neighbour_vector_.push_back(individual2[i]);
        }
    }

    std::vector<std::vector<int>> clusters = get_clusters();

    fitness_ = evaluator(clusters);

}

std::ostream &operator<<(std::ostream &os, const Individual &individual) {
    for (int i : individual.chosen_neighbour_vector_) {
        os << i << " ";
    }

    return os;
}

int Individual::size() const {
    return chosen_neighbour_vector_.size();
}

int Individual::operator[](const int index) const {
    return chosen_neighbour_vector_[index];
}

bool Individual::operator<(const Individual &other_individual) const {
    return fitness_ < other_individual.fitness_;
}

// mutate each chromosome of the individual with a given probability;
// for each chromosome, a random new neighbour is selected
// and assigned as the new allele value of that chromosome
void Individual::mutate(const Graph &graph, double mutation_probability) {
    for (int i = 0; i < chosen_neighbour_vector_.size(); i++) {
        double current_mutation_probability = ((double) rand() / (RAND_MAX));

        if (current_mutation_probability < mutation_probability) {
            const std::vector<int> &current_node_neighbours = graph[i];

            int random_neighbour_index = rand() % current_node_neighbours.size();
            int new_neighbour = current_node_neighbours[random_neighbour_index];

            chosen_neighbour_vector_[i] = new_neighbour;
        }
    }
}

double Individual::get_fitness() const {
    return fitness_;
}

const std::vector<int> &Individual::get_chosen_neighbour_vector() const {
    return chosen_neighbour_vector_;
}

bool Individual::operator!=(const Individual &other_individual) const {
    return chosen_neighbour_vector_ != other_individual.chosen_neighbour_vector_;
}

void Individual::create_graph(Graph &graph) {
    std::vector<std::pair<int, int>> edges_list;

    for (int i = 0; i < chosen_neighbour_vector_.size(); i++) {
        std::pair<int, int> edge;

        edge.first = i;
        edge.second = chosen_neighbour_vector_[i];

        edges_list.push_back(edge);

        if (graph_type_ == "undirected") {
            std::pair<int, int> new_edge;

            new_edge.first = chosen_neighbour_vector_[i];
            new_edge.first = i;

            edges_list.push_back(new_edge);
        }
    }

    graph = Graph(edges_list, chosen_neighbour_vector_.size());
}

const std::string &Individual::get_graph_type() const {
    return graph_type_;
}

std::vector<std::vector<int>> Individual::get_clusters() {
    Graph graph;

    create_graph(graph);

    std::vector<bool> visited_nodes(chosen_neighbour_vector_.size(), false);
    std::vector<std::vector<int>> clusters;

    for (int current_node : chosen_neighbour_vector_) {
        if (visited_nodes[current_node]) continue;

        std::vector<int> cluster = breadth_first_search(current_node, graph, visited_nodes);

        clusters.push_back(cluster);
    }

    return clusters;
}

// ========== Private methods ==========
std::vector<int> Individual::breadth_first_search(int node, const Graph &graph, std::vector<bool> &visited_nodes) {
    std::vector<int> cluster = {node};
    std::queue<int> queue;

    queue.push(node);

    while (!queue.empty()) {
        int current_node = queue.front();
        queue.pop();

        for (auto neighbour : graph[current_node]) {
            if (visited_nodes[neighbour] == false) {
                cluster.push_back(neighbour);

                visited_nodes[neighbour] = true;

                queue.push(neighbour);
            }
        }
    }

    return cluster;
}

Individual::Individual() {
    fitness_ = 0;
}