Travelling salesman with something like MST

Question

My objective is to solve travelling salesman problem. Program input is 100 lines, each having three numbers: first of them is city ID, and the next two are x and y coordinates. Example line: 12 4.554 5.6765.

Program

#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <fstream>
#include <algorithm>

class City;

bool distanceSort(City& _c1, City &_c2);


float calculateDistance(float _x1, float _y1,  float _x2, float _y2);
{
return sqrt( pow(_x2 - _x1,2) + pow(_y2 - _y1,2) );
}

class City
{
public:
  int id;
  float x,y;

  std::map<float, City*> childNodes;

  City* neighbourhoods[8];
  float distances[8]; // starting from city placed to the left from this, going clockwise
                    // 123
                    // 0X4
                    // 765

  float smallestDistance = 0;
  int nearestCityDir = 10;

  void exclude()
  {
    for ( int i = 0; i<8; ++i )
      {
        if (  neighbourhoods[i])
        {
          neighbourhoods[i]->distances[ (i+4)%8 ] = 0;
          neighbourhoods[i]->recalculateDistances();
        }
      }
  }

  void recalculateDistances()
  {
    smallestDistance = 0;
    nearestCityDir = 10;

   for(int i =0; i<8; ++i)
        if (distances[i] )
        {
          if (smallestDistance)
          {
            if (distances[i]<smallestDistance)
            {
              smallestDistance = distances[i];
              nearestCityDir = i;
            }
          }
          else
          {
            smallestDistance = distances[i];
            nearestCityDir = i;
          }
        }
  }


    City * getCityWithShortestDistance()
   {
      if(childNodes.empty())
      {
        return this;
      }
      else
      {
        City * cityWithShortestDistance = this;

        for (auto & childCity : childNodes)
        {
          City * shortestCityInBranch =  childCity.second->getCityWithShortestDistance();

          if (shortestCityInBranch->smallestDistance)
          {
            if ( (cityWithShortestDistance->smallestDistance  &&
               shortestCityInBranch->smallestDistance < cityWithShortestDistance->smallestDistance) ||
               cityWithShortestDistance->smallestDistance == 0)
               {
                 cityWithShortestDistance = shortestCityInBranch;
               }
          }
        }
        return cityWithShortestDistance;
      }
   }


   void organizeIntoMST()
  {
    exclude();

     for (int i =0; i<99; ++i)
     {
       City * cityToConnect = this->getCityWithShortestDistance();

       cityToConnect->childNodes.insert( std::pair<float,City*>(cityToConnect->smallestDistance, cityToConnect->neighbourhoods[cityToConnect->nearestCityDir]) );

       cityToConnect->neighbourhoods[cityToConnect->nearestCityDir]->exclude();
       cityToConnect->recalculateDistances();
      }

  }

  void preorderTraverseMST(std::vector<int> & cityOrder)
  {
    {
    cityOrder.push_back(this->id);

    if (childNodes.empty())
        return ;
    else
    {
      for (auto const& childCity : childNodes)
        childCity.second->preorderTraverseMST(cityOrder);
      }
    }
     return ;
  }
  City(int _id, float _x, float _y):id(_id),x(_x), y(_y){}
};


bool distanceSort(City& _c1, City &_c2)
{
  return _c1.y<_c2.y;
}

bool IDsort(City& _c1, City &_c2)
{
  return _c1.id < _c2.id;
}

float calculateDistance(City & _c1, City & _c2)
{
  return sqrt( pow(_c2.x - _c1.x,2) + pow(_c2.y - _c1.y,2) );
}

bool horizontalSort(City &_c1, City& _c2 )
{
  return _c1.x<_c2.x;
}

bool verticalSort(City& _c1, City& _c2)
{
  return _c1.y<_c2.y;
}




float salesmanRoute(std::vector<int>& citiesOrder, std::vector<City>& citiesSortedByID)
{

  float distance = 0;
   for (int i = 0; i < 100; ++i)
   {
        int startCityID = citiesOrder[i];
        int targetCityID = citiesOrder[i+1];

        distance += calculateDistance(citiesSortedByID[startCityID], citiesSortedByID[targetCityID]);
   }

   return distance ;
}


int main()
{

   std::vector<City> cities;

   std::ifstream file;
   file.open("TSP.txt");

  if (!file.good())
      std::cout<<"Error, file cannot be opened"<<std::endl;
  else
  {

    int cityID;
    float cityX, cityY;
    file >> cityID >> cityX >> cityY;

    while (file.good())
    {
      cities.push_back(City(cityID, cityX, cityY));
      file >> cityID >> cityX >> cityY;
    }

    std::sort(cities.begin(), cities.end()-1, horizontalSort);

    for (int i =0; i<9; ++i)
      std::sort(cities.begin() + i*10, cities.begin() +i*10 +10, verticalSort);



      // below, I'm using cities array, as a 2d array, using formula:
      //horizontalIndex * columnsAmmount + verticalIndex

      // calculate distances in horizontal
      for (int j =0; j<10; ++j) //  in column
      {
        for (int i =0; i<9; ++i) // in  row
        {
          City & c1 = cities[i*10 + j];
          City &c2 = cities[(i+1)*10 + j];
            c1.distances[4] = c2.distances[0] = calculateDistance(c1,c2);

            c1.neighbourhoods[4] = &c2;
            c2.neighbourhoods[0] = &c1;
        }
      }

      // calculate distances in vertical
      for (int i =0; i<10; ++i)//  in  row
      {
        for (int j =0; j<9; ++j)//  in column
        {
          City & c1 = cities[i*10 + j];
          City &c2 = cities[i*10 + j+1];
            c1.distances[6] = c2.distances[2] = calculateDistance(c1,c2);

            c1.neighbourhoods[6] = &c2;
            c2.neighbourhoods[2] = &c1;
        }
      }

// next two loops connects nodes along the slants, from top left to bottom right corner
      for (int j = 8, i = 0; j>0; --j) // i traverse row, j traverse column
      {
        for (int k=i, h =j; k<9 && h < 9 ; ++k, ++h)
        {
          City & c1 = cities[k*10 + h];
          City &c2 = cities[(k+1)*10 + h+1];
          c1.distances[5] = c2.distances[1] = calculateDistance(c1,c2);

          c1.neighbourhoods[5] = &c2;
          c2.neighbourhoods[1] = &c1;
        }

      }

      for (int j = 0, i =0; i<9; ++i) // i traverse row, j traverse column
      {
        for (int k=i, h =j; k<9 && h < 9 ; ++k, ++h)
        {
          City & c1 = cities[k*10 + h];
          City &c2 = cities[(k+1)*10 + h+1];
          c1.distances[5] = c2.distances[1] = calculateDistance(c1,c2);

          c1.neighbourhoods[5] = &c2;
          c2.neighbourhoods[1] = &c1;
        }
      }


// next two loops connects nodes along the slants, from bottom left to top right corner
      for (int j = 1, i = 0; j<9; ++j) // i traverse row, j traverse column
      {
        for (int k=i, h =j; k<9&& h >0 ; ++k, --h)
        {
          City & c1 = cities[k*10 + h];
          City &c2 = cities[(k+1)*10 + h-1];
          c1.distances[3] = c2.distances[7] = calculateDistance(c1,c2);

          c1.neighbourhoods[3] = &c2;
          c2.neighbourhoods[7] = &c1;
        }
      }


      for (int j = 9, i =0; i<9; ++i) // i traverse row, j traverse column
      {
        for (int k=i, h =j; k<9 && h >0 ; ++k, --h)
        {
          City & c1 = cities[k*10 + h];
          City &c2 = cities[(k+1)*10 + h-1];
          c1.distances[3] = c2.distances[7] = calculateDistance(c1,c2);

          c1.neighbourhoods[3] = &c2;
          c2.neighbourhoods[7] = &c1;
        }
      }


// next two loops is to fill dead ends

   for (int i=0; i< 10; ++i)
   {
     int j = 0 ;
      cities[i*10 + j].distances[1]=0;
        cities[i*10 + j].neighbourhoods[1]=nullptr;
      cities[i*10 + j].distances[3]=0;
        cities[i*10 + j].neighbourhoods[3]=nullptr;
      cities[i*10 + j].distances[2]=0;
        cities[i*10 + j].neighbourhoods[2]=nullptr;
    j=9;
    cities[i*10 + j].distances[7]=0;
      cities[i*10 + j].neighbourhoods[7]=nullptr;
    cities[i*10 + j].distances[5]=0;
      cities[i*10 + j].neighbourhoods[5]=nullptr;
    cities[i*10 + j].distances[6]=0;
      cities[i*10 + j].neighbourhoods[6]=nullptr;
   }

   for (int j=0; j< 10; ++j)
   {
     int i = 0 ;
      cities[i*10 + j].distances[1]=0;
        cities[i*10 + j].neighbourhoods[1]=nullptr;
      cities[i*10 + j].distances[0]=0;
        cities[i*10 + j].neighbourhoods[0]=nullptr;
      cities[i*10 + j].distances[7]=0;
        cities[i*10 + j].neighbourhoods[7]=nullptr;
    i=9;
    cities[i*10 + j].distances[3]=0;
      cities[i*10 + j].neighbourhoods[3]=nullptr;
    cities[i*10 + j].distances[4]=0;
      cities[i*10 + j].neighbourhoods[4]=nullptr;
    cities[i*10 + j].distances[5]=0;
      cities[i*10 + j].neighbourhoods[5]=nullptr;
   }


// Calculating MST

for ( int i =0; i<100; ++i)
   cities[i].recalculateDistances();

  int start_x = 2, start_y = 8;
  City *  mstRoot = &cities[start_x*10 + start_y];
  mstRoot->organizeIntoMST();

  std::vector<int> cityOrder;
  mstRoot->preorderTraverseMST(cityOrder );
  cityOrder.push_back(mstRoot->id);



    std::cout<<"Print cities order? (y/n)"<<std::endl;

    char answer;
    std::cin>>answer;

    if (answer == 'y')
    {
      std::cout<<"cityOrder Size : "<<cityOrder.size() <<std::endl;
      for (int i = 0; i<cityOrder.size(); ++i)
      std::cout<<"Order: "<<i<<"   City ID: "<<cityOrder[i]<<std::endl;

      std::sort(cities.begin(), cities.end()-1, IDsort);

      std::cout<<"DISTANCE:  "<<salesmanRoute(cityOrder,cities )<<std::endl;
    }
    else
    {
      return 0;
    }
  }



  return 0;
}

Input file

1   16.218  64.432
2   79.428  37.861
3   31.122  81.158
4   52.853  53.283
5   16.565  35.073
6   60.198  93.9
7   26.297  87.594
8   65.408  55.016
9   68.921  62.248
10  74.815  58.704
11  45.054  20.774
12  8.3821  30.125
13  22.898  47.092
14  91.334  23.049
15  15.238  84.431
16  82.582  19.476
17  53.834  22.592
18  99.613  17.071
19  7.8176  22.766
20  44.268  43.57
21  10.665  31.11
22  96.19   92.338
23  0.46342 43.021
24  77.491  18.482
25  81.73   90.488
26  86.869  97.975
27  8.4436  43.887
28  39.978  11.112
29  25.987  25.806
30  80.007  40.872
31  43.141  59.49
32  91.065  26.221
33  18.185  60.284
34  26.38   71.122
35  14.554  22.175
36  13.607  11.742
37  86.929  29.668
38  57.97   31.878
39  54.986  42.417
40  14.495  50.786
41  85.303  8.5516
42  62.206  26.248
43  35.095  80.101
44  51.325  2.922
45  40.181  92.885
46  7.5967  73.033
47  23.992  48.861
48  12.332  57.853
49  18.391  23.728
50  23.995  45.885
51  41.727  96.309
52  4.9654  54.681
53  90.272  52.114
54  94.479  23.159
55  49.086  48.89
56  48.925  62.406
57  33.772  67.914
58  90.005  39.552
59  36.925  36.744
60  11.12   98.798
61  78.025  3.7739
62  38.974  88.517
63  24.169  91.329
64  40.391  79.618
65  9.6455  9.8712
66  13.197  26.187
67  94.205  33.536
68  95.613  67.973
69  57.521  13.655
70  5.978   72.123
71  23.478  10.676
72  35.316  65.376
73  82.119  49.417
74  1.5403  77.905
75  4.3024  71.504
76  16.899  90.372
77  64.912  89.092
78  73.172  33.416
79  64.775  69.875
80  45.092  19.781
81  54.701  3.0541
82  29.632  74.407
83  74.469  50.002
84  18.896  47.992
85  68.678  90.472
86  18.351  60.987
87  36.848  61.767
88  62.562  85.944
89  78.023  80.549
90  8.1126  57.672
91  92.939  18.292
92  77.571  23.993
93  48.679  88.651
94  43.586  2.8674
95  44.678  48.99
96  30.635  16.793
97  50.851  97.868
98  51.077  71.269
99  81.763  50.047
100 79.483  47.109

Answer 1

Fix the syntax errors

This should have been compiled before posting here:

g++ -std=c++17 -fPIC -g -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Weffc++      163517.cpp    -o 163517
163517.cpp:14:1: error: expected unqualified-id before ‘{’ token
 {
 ^

(caused by a stray semicolon following the function signature)

Address the compilation warnings:

163517.cpp:18:7: warning: ‘class City’ has pointer data members [-Weffc++]
 class City
       ^~~~
163517.cpp:18:7: warning:   but does not override ‘City(const City&)’ [-Weffc++]
163517.cpp:18:7: warning:   or ‘operator=(const City&)’ [-Weffc++]
163517.cpp: In constructor ‘City::City(int, float, float)’:
163517.cpp:132:3: warning: ‘City::childNodes’ should be initialized in the member initialization list [-Weffc++]
   City(int _id, float _x, float _y):id(_id),x(_x), y(_y){}
   ^~~~
163517.cpp: In function ‘int main()’:
163517.cpp:205:5: warning: this ‘for’ clause does not guard... [-Wmisleading-indentation]
     for (int i =0; i<9; ++i)
     ^~~
163517.cpp:214:7: note: ...this statement, but the latter is misleadingly indented as if it is guarded by the ‘for’
       for (int j =0; j<10; ++j) //  in column
       ^~~
163517.cpp:361:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i<cityOrder.size(); ++i)
                       ~^~~~~~~~~~~~~~~~~

Know your libraries

You can use the provided std::hypot() instead of writing a less-efficient (and possibly less-correct, for large values which may overflow double) implementation yourself:

float calculateDistance(float x1, float y1,  float x2, float y2)
{
    //return sqrt(pow(_x2 - _x1,2) + pow(_y2 - _y1,2));
    return std::hypot(x2 - x1,  y2 - y1);
}

In passing, note that including <cmath> is not specified to define sqrt(), pow(), hypot() or any other function into the global namespace. If your implementation does, and you don't qualify your uses, you make your code less portable (possibly even to future versions of your compiler and library).

We can implement the other overload in terms of this function, instead of duplicating the logic:

float calculateDistance(City & c1, City & c2)
{
    //return sqrt(pow(c2.x - c1.x,2) + pow(c2.y - c1.y,2));
    return calculateDistance(c1.x, c1.y, c2.x, c2.y);
}

Know the naming rules

Don't name your identifiers with a leading underscore. Such names are reserved for the implementation. Even if you know the rules inside out (and most of us don't!), it's wise to assume that others reading or modifying your code may be less capable.

Magic numbers

There are many constants scattered throughout the code:

City* neighbourhoods[8];

    for (int i = 0; i<8; ++i) {
        if (neighbourhoods[i]) {
            neighbourhoods[i]->distances[ (i+4)%8 ] = 0;
            neighbourhoods[i]->recalculateDistances();
        }
    }
    smallestDistance = 0;
    nearestCityDir = 10;
    for (int i =0; i<99; ++i) {
for (int i = 0; i < 100; ++i) {
    int startCityID = citiesOrder[i];
    int targetCityID = citiesOrder[i+1];

    distance += calculateDistance(citiesSortedByID[startCityID], citiesSortedByID[targetCityID]);
}

It's hard to tell which of these are related to each other, and/or to the assumptions about the input file. By giving them names, we can make it easier to change any of our assumptions.

Think about encapsulation

At present, everything in City is public (so it could have been declared using struct) and modifiable. This means that any code can change the location or identifier of a city, or indeed any of its internal state. These members should be private; we can provide accessors to read their values, but they should only be set by the constructors, assignment operator and stream operator (we'll have to define operator>>(istream&, City&) as a friend function).

File handling and errors

Consider this extract:

std::ifstream file;
file.open("TSP.txt");

if (!file.good())
    std::cout<<"Error, file cannot be opened"<<std::endl;
else {

We can open the file at construction time:

std::ifstream file("TSP.txt");

Streams have a contextual conversion to bool, so we can simplify the test; we should also use cerr for error messages and return a non-zero value on failure, so our program plays nicely with others:

if (!file) {
    std::cerr << "Error, file cannot be opened" << std::endl;
    return 1;  // Or, EXIT_FAILURE (from <cstdlib>)
}

Another advantage of this approach is that we no longer need an else block for the rest of the function, which means less context to keep in one's head whilst reading it.

Answer 2

Your code is fairly straightforward and easy to understand. You should strive to keep it that way in the future. I agree with @Toby Speight's answer and have a few things to add.

Break Out Your Source Code Into Files

Why is all your source code in one file? You have all the methods for the class in the class declaration. Normally you'd put the method declarations inside the class declaration in the header (.h or .hpp) file and the method implementations in a separate source (.cpp) file. This makes it faster for the compiler when you have a lot of classes used in different source files.

Careful with floats

Having a float for the key in a std::map is a really bad idea. Floating point numbers are imprecise. For example, many simple values like 1/3 are not exactly representable as float or double types. Further, when calculations are done with them, it's easy to lose precision. See this Stack Overflow question for some detailed examples of problems you commonly run into with float types.

Furthermore, you never even use the key! You only ever use the City portion of the std::map using an iterator, so there's really no point in even using a std::map. You should just put them into a std::vector or std::array.

Use struct or class for Things that Go Together

There are several places where you have what should clearly constitute a data type, but you've separated it out into pieces that you then have to keep in sync. For example, the City's location. You're storing it as separate x and y coordinates. You should have a Point class with an x and y coordinate and pass Point objects around. It could have methods for adding points, subtracting them, and finding distances between them.

Similarly you have 2 arrays of 8 members each - neighbourhoods and distances. Why not have a Neighbourhood class that holds a City and a distance, and have a single array of 8 Neighbourhood objects?

Work on Formatting

Your formatting is very odd and hard to read. It could just be that entering in the form on the web site here was difficult, but if not, you really should clean it up. Have a look at any open source project on GitHub or your favorite code site and just examine how they format things like loops, conditionals, functions, etc. It's not so important which style you use, so much as that you use a consistent style.

Avoid Pointers

C++ has a number of ways to avoid using pointers. Pointers are the source of a large class of errors in programming, so avoiding them helps you write better code. You have a few choices - references, smart or shared pointers, and unique pointers. It's a bit much to describe in this post, but read the links for some good descriptions of what they are and when to use them.

Use More Functions

Your main() function does a number of things. It would be best to break each of those things out into their own function and call that function from main(). For example, you read the data from the file, then calculate horizontal distances, then vertical distances, then connect nodes, then traverse them, then fill in dead ends... etc. Each of those should be a separate function.