genetic-vsp/Reader.cpp

#include <climits>
#include <fstream>
#include <iostream>

#include "Reader.h"

const std::string& Reader::getName(int id) {
    return names[id];
}

const std::vector<int>& Reader::operator[](int x) const {
    return distances[x];
}

int Reader::getSize() const {
    return ids;
}

int Reader::getOrAddId(const std::string& s) {
    auto found = nameToId.find(s);
    if(found != nameToId.end()) {
        return found->second;
    }
    int id = ids++;
    nameToId[s] = id;
    for(std::vector<int>& inner : distances) {
        inner.push_back(-1);
    }
    distances.push_back(std::vector<int>(ids, -1));
    distances.back()[ids - 1] = 0;
    names.push_back(s);
    return id;
}

std::string Reader::trim(const std::string& s) const {
    size_t start = 0;
    while(start < s.length() && s[start] == ' ') {
        start++;
    }
    size_t end = s.length();
    while(end > 0 && s[end - 1] == ' ') {
        end--;
    }
    return s.substr(start, end - start);
}

bool Reader::read(const char* path) {
    std::ifstream in;
    in.open(path);
    if(!in.good()) {
        std::cout << "cannot find data\n";
        return true;
    }
    while(!in.eof()) {
        std::string s;
        std::getline(in, s);
        if(s.find("road(", 0) != 0) {
            continue;
        }
        s = s.substr(5, s.length() - 5);

        size_t fromIndex = s.find(",", 0);
        if(fromIndex == s.npos) {
            continue;
        }
        size_t toIndex = s.find(",", fromIndex + 1);
        if(toIndex == s.npos) {
            continue;
        }
        size_t distanceIndex = s.find(")", toIndex + 1);
        if(distanceIndex == s.npos) {
            continue;
        }

        std::string from = trim(s.substr(0, fromIndex));
        std::string to = trim(s.substr(fromIndex + 1, toIndex - fromIndex - 1));
        std::string distanceString =
            trim(s.substr(toIndex + 1, distanceIndex - toIndex - 1));

        int fromId = getOrAddId(from);
        int toId = getOrAddId(to);
        int distance = std::stoi(distanceString);

        distances[fromId][toId] = distance;
        distances[toId][fromId] = distance;
    }
    for(int i = 0; i < ids; i++) {
        distance(i);
    }
    return false;
}

void Reader::print() const {
    for(size_t x = 0; x < distances.size(); x++) {
        for(size_t y = 0; y < distances[x].size(); y++) {
            printf("%3d ", distances[x][y]);
        }
        std::cout << "\n";
    }
}

struct Node {
    int distance = INT_MAX;
    bool visited = false;
};

static bool notAllVisited(const std::vector<Node>& nodes) {
    for(const Node& n : nodes) {
        if(!n.visited) {
            return true;
        }
    }
    return false;
}

void Reader::distance(int column) {
    std::vector<Node> nodes(ids, Node());
    nodes[column].distance = 0;
    while(notAllVisited(nodes)) {
        size_t minIndex = 0;
        int minDistance = INT_MAX;
        for(size_t i = 0; i < nodes.size(); i++) {
            if(!nodes[i].visited && nodes[i].distance < minDistance) {
                minIndex = i;
                minDistance = nodes[i].distance;
            }
        }
        nodes[minIndex].visited = true;
        for(int i = 0; i < ids; i++) {
            if(!nodes[i].visited && distances[minIndex][i] != -1) {
                int newDistance = minDistance + distances[minIndex][i];
                if(newDistance < nodes[i].distance) {
                    nodes[i].distance = newDistance;
                }
            }
        }
    }
    for(size_t i = 0; i < nodes.size(); i++) {
        distances[column][i] = nodes[i].distance;
    }
}