Need help re-writing this into "better" code

[jazpearson]

I've written a travelling salesman problem (TSP) algorithm, that finds the quickest route between randomly distributed points, using brute force. This seems to work just fine, so that's not the issue. The issue is my lack of OOP background, having come from more of a fortran-based one. So any help in re-writing this code would be really appreciated. (written is VS 2008).

// TSP_BruteForce.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <math.h>
#include <stdlib.h>
#include <iostream>	
#include <vector>
#include <cassert>
#include <algorithm>


using namespace std;

float distance(float x1, float x2, float y1, float y2);

int _tmain(int argc, _TCHAR* argv[])
{

    int NumberOfPoints;

	srand (7);

	cout << "Please enter the number of points: " << endl;
	cin >> NumberOfPoints;
	cout << endl;

	vector <float> x(NumberOfPoints);
        vector <float> y(NumberOfPoints);
	vector <int> order(NumberOfPoints);
	
	float TotalDistance = 0;
	float ShortestDistance = 9999; // set this to a high target initially

	//vector< vector<float> > DistanceArray(NumberOfPoints, vector<float>(NumberOfPoints));


// ***********************************************************************************************************
// this bit is getting a set of random numbers


	for (int i = 0; i < NumberOfPoints; i++){  // this loop calculates 2 sets of random numbers (x,y) and sets order to be 0,1,2,3....
			
			x[i] = 10 * rand() / float(RAND_MAX);
			y[i] = 10 * rand() / float(RAND_MAX);
			
			order[i] = i;
	
			std::cout << i << "   " << x[i] << "   " << y[i] << std::endl;
		}

// ***********************************************************************************************************
// we have n sets of x,y values - set up a loop to calculate the total distance travelled, and permute


	do {

		TotalDistance = 0;

		for (int i = 0; i < NumberOfPoints - 1; i++){
			
			TotalDistance += distance(x[order[i]], x[order[i+1]], y[order[i]], y[order[i+1]]);

		}


		if (TotalDistance < ShortestDistance){
				
				ShortestDistance = TotalDistance;
				cout << "Shortest Distance: " << ShortestDistance << endl;
		
				for (int j = 0; j < NumberOfPoints; j++){

					cout << order[j] << " ";
				}

				cout << endl;

		}			
		
	} while (next_permutation(order.begin(), order.end() ));

	
	std::cout << std::endl;

	system("PAUSE");
	return 0;
}

float distance(float x1, float x2, float y1, float y2){ // function to calculate the (Euclidian) distance between 2 sets of points.

	return sqrt( (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1) );

}

when i say i'd like help in re-writing the code, i'd like to be shown how to rewrite this in terms of oop - classes (do i need?), constructors, destructors, member functions etc., rather than this archaic way of doing it, even if it does work. In the future, i'm going to be working on some rather large projects, so i need to get to grips with the OOP side.

[N85iE3v7]

Hey the code seems fine. However, if you plan to write OOP, start with simpler things. Some people will tell you to remove the System("PAUSE") line perhaps.

But right now, you could write a new class to handle command line processing arguments, instead of writing data input inside main, just to gain fluency on OOP, next try to encapsulate your ideas on a class. Basically leave just the class instantiation in the main function and subsequent calls to the math computations.

Your code uses STL container vector, which is good thing by the way. There is a library called Boost, which has some math libraries you could deal with.

[hanst99]

But right now, you could write a new class to handle command line processing arguments, instead of writing data input inside main

Disagreed. Completely pointless in this case. Unless you got a good idea what exactly a new i/o class instead of just doing to the i/o in the main function would do to benefit the program. What he should write a class for is the actual computation of the route, and seperate the i/o from it.

[N85iE3v7]

The OP wants to learn OOP, maybe it is a good motivator to write a class to do that. The OP seems to want to learn OOP. That was my idea.

[jazpearson]

Ok, thanks for the info.

I was wondering, what's up with system("PAUSE")?

[filipe]

http://www.cplusplus.com/forum/articles/11153/

[jazpearson]

ok, thanks - good to know. I'll leave it in this code for now - it's not for any commercial use, just me messing about. but when i'm writing up something properly, i'll make sure to leave it out.


so - back to classes: one of the things which i'm not clear on yet, is what do i make public / private? i'm sure it's quite obvious, but i seem to be confusing myself somewhat.

for example, in this code - what would be public/private? i'll post back with an attempt shortly.

[ne555]

You could make a point/vector class.
Then the distance will be (u-v).norm();

//float ShortestDistance = 9999; // set this to a high target initially
#include <limits>
float ShortestDistance = std::numeric_limits<float>::max();