123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141 |
- #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;
- }
- }
|