tsp_test

#include <iostream>
#include <math.h>
#include <fstream>
#include <vector>

using namespace std;

class City{
private:
    int id;
    int coord_x;
    int coord_y;
    bool visited;
public:
    City(){
        id = -1;
        coord_x = 0;
        coord_y = 0;
        visited = false;
    }
    City(int new_id, int new_x, int new_y){
        id = new_id;
        coord_x = new_x;
        coord_y = new_y;
        visited = false;
    }
    void set_id(int new_id){
        id = new_id;
    }
    void set_x(int new_x){
        coord_x = new_x;
    }
    void set_y(int new_y){
        coord_y = new_y;
    }
    void change_visited(){
        visited = !visited;
    }
    int get_id(){
        return id;
    }
    void print_city(){
        cout << "Id: " << id << endl;
        cout << "X coord: " << coord_x << endl;
        cout << "Y ooord: " << coord_y << endl;
        cout << "Visited: " << visited << endl;
        cout << "###" << endl;
    }
    double distance_between(City other){
        double dist = sqrt(pow((coord_x - other.coord_x), 2) + pow((coord_y - other.coord_y), 2));
        return dist;
    }
};

int read_file(string file_name, vector<City> &cities, int beginning = 0)
{
    ifstream my_file;
    int amount;
    int tmp[3];
    int index = 0;
    my_file.open(file_name.c_str());
    if(my_file.is_open() == false){
        cout << "Problem otwarcia pliku!" << endl;
    }
    my_file >> amount;
    while(!my_file.eof()){
        my_file >> tmp[0];
        my_file >> tmp[1];
        my_file >> tmp[2];
        cities.push_back(City(tmp[0], tmp[1], tmp[2]));
        index++;
    }
    my_file.close();
    return amount;
}

double find_shortest_dist(vector<City> &c_not_visited, City start, int &pos)
{
    double shortest_dist;
    bool first_time_set = false;
    int destination_pos = 0;
    for(int i = 0; i < c_not_visited.size(); i++){
        if(first_time_set == false){
            shortest_dist = start.distance_between(c_not_visited.at(i));
            destination_pos = i;
            first_time_set = true;
        }
        else{
            if(shortest_dist > start.distance_between(c_not_visited.at(i))){
                shortest_dist = start.distance_between(c_not_visited.at(i));
                destination_pos = i;
            }
        }
    }
    pos = destination_pos;
    return shortest_dist;
}

void TSP_greedy(vector<City> cities_copy, vector<City> &cities, int amount){
    double road_length = 0;
    int next_pos;
    vector<int> road_by_id;
    road_by_id.push_back(cities.at(0).get_id());
    City from_city = cities_copy.at(0);
    cities_copy.erase(cities_copy.begin());
    while(cities_copy.size() > 0){
        road_length += find_shortest_dist(cities_copy, from_city, next_pos);
        road_by_id.push_back(cities.at(next_pos).get_id());
        if(cities_copy.size() > 1)
            from_city = cities_copy.at(next_pos);
        cities_copy.erase(cities_copy.begin()+next_pos);
    }
    cout << "Dlugosc drogi: " << road_length << endl;
    cout << "Sciezka: ";
    for(int i = 0; i <= road_by_id.size(); i++){
        cout << road_by_id.at(i) << " ";
    }
    cout << endl;
}

int main()
{
    string file_name;
    vector<City> cities;
    cout << "Podaj nazwe pliku: ";
    cin >> file_name;
    int amount = read_file(file_name, cities);
    cout << "Ilosc miast: " << amount << endl;
    for(int i = 0; i < amount; i++)
    {
        cities.at(i).print_city();
    }
    TSP_greedy(cities, cities, amount);
    cin.sync();
    cin.get();
    return 0;
}