/*
Filename:  tsp2.cpp

Author:  Br. David Carlson with Daniel Kissel

Date:  January 11, 2002

Revised:    May 25th, 2017 by Daniel Kissel
            July 3, 2017 by Br. David Carlson

This software is made available under the license found
at http://cis.stvincent.edu/carlsond/cs171/tsp.html.

This program solves the travelling salesperson problem
(TSP) by enumerating all the possible tours of the cities
and choosing the best one.   To use the program, place your
data in a text file and see that it follows the format
shown in the following example:
4
0 9 5 3
9 0 4 8
5 4 0 6
3 8 6 0
Note that the number of cities (here 4) is placed on the
first line by itself.  Following that is a symmetric matrix
giving the costs for travelling between all pairs of cities.
Thus the (i,j) entry in the matrix gives the cost of going
from city i to city j.  The cities are assumed to be numbered
from 0 through 4 - 1 = 3, in this case.
The program will ask the user for the name of the data
file to open.
The output of the program shows the lowest cost tour of
all cities with city 0 being the starting point and ending
point.  It also displays the total number of tours that were
checked and the number of additions and comparisons used.
Backtracking is used in order to avoid some needless additions.
In the above example, after the tour of cities 0, 1, 2, 3 is
checked, the program would backtrack to the partial tour 0, 1, 2
to see if there is another choice for the last city.  There is
not.  Thus the program would backtrack to the partial tour 0, 1
and find another choice (city 3) for the third city.  The addition
of the original cost 0 and the cost to go from city 0 to city 1
is not recalculated thanks to this backtracking algorithm.  Rather,
the new cost to go from city 1 to city 3 is simply added to the
existing partial sum, etc.
*/

#include <iostream>
#include <iomanip>    // for setw
#include <fstream>
#include <limits.h>   // for LONG_MAX
using namespace std;

const int MaxCities = 100;
const int MaxString = 64;


/* A CityList variable will be used to keep track of the list of
cities chosen so far.  The integers representing the cities
will be at indices 0, 1, 2,...,MaxCities - 1 in the Info field.
*/
typedef int CityData[MaxCities];

typedef struct
    {
    CityData Info;
    } CityList;

/* An AvailList variable will be used to keep track of what cities
are available.  A true at index k in the Info field says that city k
is available, otherwise city k is not available.
*/
typedef bool AvailData[MaxCities];

typedef struct
    {
    AvailData Info;
    } AvailList;

/* Note that CityList and AvailList are structs so that call by copy
can be used when passing variables of these types as parameters.
*/


typedef int CostArray[MaxCities][MaxCities];
typedef char StringType[MaxString];


// Function prototypes:

void ReadData(int & NumCities, CostArray Cost);

void Choose(int Num, AvailList Avail, CityList Chosen, long Cost);

void ArrayCopy(CityList & Destination, const CityList & Source);


// Some global variables are used for speed:

int NumCities;
double NumAdditions, NumTours, NumCompares;
long MinCost;
CityList BestTour;
CostArray Cost;


int main(void)
    {
    AvailList Avail;
    CityList Tour;
    int k;

    ReadData(NumCities, Cost);
    cout << "Solving TSP for number of cities: " << NumCities << endl << endl;

    NumAdditions = NumTours = NumCompares = 0;
    MinCost = LONG_MAX;
    Tour.Info[0] = 0;
    Avail.Info[0] = false;

    for (k = 1; k < NumCities; k++)
        Avail.Info[k] = true;

    Choose(1, Avail, Tour, 0);

    if (MinCost < LONG_MAX)
        {
        cout << "The lowest cost was: " << MinCost << endl;
        cout << "This was for the following tour of the cities:" << endl;

        for (k = 0; k < NumCities; k++)
            cout << setw(4) << BestTour.Info[k];
        }
    else
        cout << "No solution was found" << endl;

    cout << endl << endl;
    cout << "Total number of tours checked was:  " << NumTours << endl;
    cout << "Total number of additions used was: " << NumAdditions << endl;
    cout << "Total number of comparisons used was: " << NumCompares << endl;
    cout << "Total number of additions and comparisons was: " << NumAdditions + NumCompares << endl;

    //added in 2017 to pause the program
    cout << "Press any key to exit the program..." << endl;
    cin.ignore();

    return 0;
    }


/* Given:  NumChosen   The number of cities already chosen in parameter Chosen.
           Avail       Array showing what cities are still not chosen.
           Chosen      Partial tour (list of cities) constructed so far.
           CostSoFar   Cost of the partial tour contained in parameter Chosen.
   Task:   To go through all possible ways of choosing cities to complete the
           tour, keeping track of the cheapest so far.
   Return: The global values BestTour and MinCost giving the least cost tour
           and its cost, MinCost.
*/
void Choose(int NumChosen, AvailList Avail, CityList Chosen, long CostSoFar)
    {
    int m;
    long NewCost;

    NumCompares++;
    if (NumChosen == NumCities)   // stopping case, all cities have been chosen
        {
        // Add the cost of returning to city 0 from last city:
        NewCost = CostSoFar + Cost[0][Chosen.Info[NumCities - 1]];
        NumAdditions++;
        NumTours++;
        NumCompares++;
        if (NewCost < MinCost)
            {
            ArrayCopy(BestTour, Chosen);
            MinCost = NewCost;
            }
        }
    else   // recursive case
        {
        for (m = 0; m < NumCities; m++)   // try each possibility
            {
            NumCompares++;
            if (Avail.Info[m])
                {
                Chosen.Info[NumChosen] = m;
                Avail.Info[m] = false;
                NewCost = CostSoFar + Cost[m][Chosen.Info[NumChosen - 1]];
                NumAdditions++;
                Choose(NumChosen + 1, Avail, Chosen, NewCost);
                Avail.Info[m] = true;
                }
            }
        }
    }


/* Given:   Nothing.
   Task:    To prompt the user for the data file to open, to open that file,
            and to read from it the number of cities and then the matrix of
            costs to travel between pairs of cities.  The program is halted
            if the file cannot be opened or the number of cities is too small
            or too large.
   Return:  NumCities  The number of cities specified in the data file.
            Cost       The matrix of costs.
*/
void ReadData(int & NumCities, CostArray Cost)
    {
    StringType FileName;
    fstream fs;
    int Row, Column;

    cout << "Enter the name of the TSP data file to be read: ";
    cin.getline(FileName, MaxString);

    fs.open(FileName, ios::in);
    if (fs.fail())
        {
        cerr << "Error: Could not open file: " << FileName << endl;
        //added in 2017 to pause the program
        cout << "Press any key to exit the program..." << endl;
        cin.ignore();
        exit(1);
        }

    fs >> NumCities;

    if ((NumCities > MaxCities) || (NumCities < 2))
        {
        cout << "Error: Number of cities must be from 2 to " << MaxCities << endl;
        //added in 2017 to pause the program
        cout << "Press any key to exit the program..." << endl;
        cin.ignore();
        exit(1);
        }
    else
        {
        for (Row = 0; Row < NumCities; Row++)
            for (Column = 0; Column < NumCities; Column++)
                fs >> Cost[Row][Column];
        }

    fs.close();
    }


/* Given:   Source       A CityList containing an array of cities (with the
                         number of cities given by the global variable NumCities
                         and with the first city at index 0).
   Task:    To copy the data from Source to Destination.
   Return:  Destination  A CityList containing a copy of the data from Source.
*/
void ArrayCopy(CityList & Destination, const CityList & Source)
    {
    int k;

    for (k = 0; k < NumCities; k++)
        Destination.Info[k] = Source.Info[k];
    }