Travelling salesman problem solver.

[zy96]

Hi all, I am actually working on one C++ program to solve a travelling salesman problem.

Here's the brief introduction on what the program intends to achieve.
1. The program reads a text file, stores the variable and computes the distance.
2. The program starts from a point, known as Depot, and ends in Depot as well.
3. There are 2 types of points/city in the text file, point and parcel, where the program should always visit point first before visiting parcel.
4. If there are more points than parcel, you don't need to visit all of the points.
5. The program should keep track of what point it visited, so that you can generate a text file of points u visited.
6. Brute force is allowed.

The text file for reading contains information like this:

Depot 265 143
Parcel1 253 278
Point2 439 148
Parcel3 458 304
Point4 609 230
Parcel5 597 101

What I know:
I know that we need to use Pythagoras theorem to solve the distance, that is not an issue, as it is relatively easy to solve.
I also know that we should store the points visited into a temp array before storing and printing it.
We should also have a mechanism that validate the type of points before visiting it.


My Issue:
But I am having trouble trying to save the information from the text file for interpretation. I know that we cannot store string and int values in an array, and it seems the same for matrix as well.
I am also unsure of how to create a validation for point visiting, do I use Boolean value?

[deleted account xyzzy]

Consider creating a struct so you can have a single data type to hold the point's location name, the starting and ending points as well as a visited Boolean.

struct Point
{
   std::string Location { };
   unsigned    Start    { };
   unsigned    End      { };
   bool        Visited  { };
};

https://www.learncpp.com/cpp-tutorial/introduction-to-structs-members-and-member-selection/

[zy96]

Hi George, thanks for replying, I will try to attempt that method and post my progress here. So if we used struct, does it mean I have to initialize multiple instance of it, let's say 5, to store the points in the text file above? What if I do not know the number of points existing in the file?

[deleted account xyzzy]

Do you know how to create an array?

Instead of creating an array like int arr[10]; do something like Point arr[10];

Personally I prefer using a C++ container, such as a std::vector, over a regular array.

https://www.learncpp.com/cpp-tutorial/an-introduction-to-stdvector/

A vector will resize as you add data to it, so you don't need to know how many data points required until you read the data from the file.

You might want to stick your feet in all over chapter 10, Learn C++ has lots of good info.

For that matter spelunk over the entire tutorial site. :)

[zy96]

Ahh, interesting, thanks for the information, will visit the tutorials and try it out.

[zy96]

So currently this is what I have, I managed to store the points accordingly into vector arrays:

#include <iostream>
#include <fstream>
#include <stdio.h>
#include <string>
#include <vector>
#include <list>
#include <sstream>
using namespace std;

struct Point
{
	std::string name;
	int x = 0;
	int y = 0;
	bool Visited;
};

struct Distance
{
	std::string Start;
	std::string End;
	int distance = 0;
};

int calculator(int x1, int x2, int y1 ,int y2) 
{
	int distance = sqrt(((x2 - x1) ^ 2) + ((y2 - y1) ^ 2));

	return distance;
}


int main()
{
	std::ifstream file("tsp.txt");

	if (!file)
		throw std::runtime_error("Error opening file");

	std::string line;
	Point temp;
	std::vector<Point> Coordinates;
	int point_count = 0;
	std::vector<Distance> Distance;

	while (std::getline(file, line))
	{
		std::stringstream ss;
		ss << line;
		std::string x, y, z;
		ss >> x >> y >> z;

		Point p = { x, std::stoi(y), std::stoi(z) ,false };

		Coordinates.push_back(p);
		cout << Coordinates[point_count].name << endl;

		point_count++;

	}
}

But I realized that, I was not sure how to compare the points one by one, while validating if they are the points I am supposed to visit first

[zy96]

The distance struct I created initially was so that I could compare the points and store the distance in between them. I had an idea of popping the vector array one by one while comparing the distance between the points and storing them. Unfortunately I am having trouble figuring out a solid logic.

[seeplus]

Note that in c++, ^ is NOT raise to power - but xor!

[seeplus]

This is updated code to read and display the file contents - with some other tidy up:

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cmath>

struct Point {
	std::string name;
	int x {};
	int y {};
	bool visited {};
};

struct Distance {
	std::string start;
	std::string end;
	double distance {};
};

double getDist(int x1, int x2, int y1, int y2) {
	return sqrt(((x2 - x1) * (x2 - x1)) + ((y2 - y1) * (y2 - y1)));
}

int main() {
	std::ifstream file("tsp.txt");

	if (!file)
		return (std::cout << "Error opening file\n"), 1;

	unsigned point_count {};

	std::vector<Point> coordinates;
	std::vector<Distance> distance;

	for (Point p; file >> p.name >> p.x >> p.y; coordinates.emplace_back(p), ++point_count);

	for (const auto& [n, x, y, v] : coordinates)
		std::cout << n << "  " << x << "  " << y << '\n';
}

[seeplus]

This will create 2 maps - one sorted by start/end names with the distance between them. The second sorted by computed distance obtained from the first map.

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <iomanip>
#include <cmath>

struct Point {
	std::string name;
	int x {};
	int y {};
	bool visited {};
};

struct Distance {
	std::string start;
	std::string end;
	Distance(const std::string& s, const std::string& e) : start(s), end(e) {}
};

struct mapcomp {
	bool operator() (const Distance& lhs, const Distance& rhs) const {
		if (lhs.start < rhs.start)
			return true;

		return lhs.end < rhs.end;
	}
};

double getDist(int x1, int x2, int y1, int y2) {
	return sqrt(((x2 - x1) * (x2 - x1)) + ((y2 - y1) * (y2 - y1)));
}

int main() {
	std::ifstream file("tsp.txt");

	if (!file)
		return (std::cout << "Error opening file\n"), 1;

	unsigned point_count {};

	std::vector<Point> coordinates;
	std::map<Distance, double, mapcomp> dists;
	std::multimap<double, Distance> sortDists;

	for (Point p; file >> p.name >> p.x >> p.y; coordinates.emplace_back(p), ++point_count);

	for (size_t i {}; i < coordinates.size(); ++i)
		for (size_t j {}; j < coordinates.size(); ++j)
			if (i != j)
				dists[{coordinates[i].name, coordinates[j].name}] = getDist(coordinates[i].x, coordinates[j].x, coordinates[i].y, coordinates[j].y);

	for (const auto& [names, dist] : dists)
		sortDists.insert({dist, names});

	for (const auto& [dist, names] : sortDists)
		std::cout << names.start << " - " << std::setw(20 - names.start.size() - 3) << std::left << names.end << "  " << dist << '\n';
}

Parcel5 - Point4      129.557
Point4 - Parcel5      129.557
Depot - Parcel1       135.532
Parcel1 - Depot       135.532
Point2 - Parcel3      157.153
Parcel3 - Point2      157.153
Point2 - Parcel5      164.842
Parcel5 - Point2      164.842
Parcel3 - Point4      168.158
Point4 - Parcel3      168.158
Depot - Point2        174.072
Point2 - Depot        174.072
Point2 - Point4       188.743
Point4 - Point2       188.743
Parcel1 - Parcel3     206.642
Parcel3 - Parcel1     206.642
Parcel1 - Point2      226.927
Point2 - Parcel1      226.927
Parcel5 - Parcel3     246.028
Parcel3 - Parcel5     246.028
Depot - Parcel3       251.336
Parcel3 - Depot       251.336
Depot - Parcel5       334.646
Parcel5 - Depot       334.646
Depot - Point4        354.831
Point4 - Depot        354.831
Parcel1 - Point4      359.221
Point4 - Parcel1      359.221
Parcel1 - Parcel5     386.866
Parcel5 - Parcel1     386.866

[zy96]

Would you kindly elaborate on the Distance struct content?

[seeplus]

It has 2 member variables and one constructor that takes 2 strings.

Have you come upon struct/class constructors yet? if not, see
https://www.learncpp.com/cpp-tutorial/constructors/

The constructor is called when the struct is instantiated and stores the passed arg values in the member variables.