/*
Filename TSPcombined.cpp

Authors: Br. David Carlson with Paul Scarrone and Daniel Kissel

Date:  January 11, 2002 by Br. David Carlson

Revised:    January 18, 2010 by Paul Scarrone, combining the 3 traveling salesperson problem solution algorithms,
            available separately as tsp1.cpp, tsp2.cpp, and tsp3.cpp. Timing capabilities were also added.

            June 3, 2017 by Daniel Kissel: Added 3 global boolean flags to continue program execution until all 3 tsp
            algorithms have exceeded their time limit. Thus, when one TSP method exceeds the time limit the remaining tsp
            algorithms still continue their execution. Output statements have been added that tell the user additional
            timing information.

            July 4, 2017 by Br. David Carlson to make the documentation and outputs more consistent, as well as to
            eliminate some unneeded code.

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

This program utilizes the 3 traveling salesperson algorithms written by Br. David Carlson and executes them on
a sequence of datafiles that all use the same filename prefix. The prefix used in the sample data files is tsp.d.
All of the data files should be in the same directory and start with the same prefix followed by the number of cities
used by the graph contained in this file. For example, a 12 city data file might be named tsp.d12. This program always
assumes that the minimum number of cities to be processed is 3 and so will always look to the first file as being the
file prefix followed by 3.

Here is the format of a typical data file:
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.

First, the program asks for the common file prefix (typically tsp.d). Second, the program asks for the number of files
to process. Thus, if you ask for 5 files, it will process tsp.d3, tsp.d4, tsp.d5, tsp.d6, and tsp.d7. Third, the program
asks for a time limit (in seconds). If the execution for one of the 3 algorithms takes too long on a particular datafile, that
method will not be run on any of the larger datafiles. (The other algorithms might continue to be run as they may not have yet
exceeded the time limit.)

A report is written to a file named report.txt and is essentially a copy of the screen output.
The program also reports the execution time for running each algorithm on each data file and the total time used.
*/

#include <iostream>
#include <iomanip>    // for setw
#include <fstream>
#include <limits.h>   // for LONG_MAX
#include <string>
#include <sstream>    //for conversion of char array and strings
#include <windows.h>  //to set process priority
#include <time.h>     //for time tracking
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 string StringType;


// Function prototypes:

bool ReadData(int & NumCities, CostArray Cost, StringType FileName);

void TSP1Choose(int Num, AvailList Avail, CityList Chosen);
void TSP2Choose(int NumChosen, AvailList Avail, CityList Chosen, long CostSoFar);
void TSP3Choose(int NumChosen, AvailList Avail, CityList Chosen, long CostSoFar);

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

void TSP1(StringType FileName);
void TSP2(StringType FileName);
void TSP3(StringType FileName);


// Some global variables are used for speed:
int NumCities;
double NumAdditions, NumTours, NumCompares;
long MinCost;
CityList BestTour;
CostArray Cost;

// Added in 2017:
bool tsp1_pass = false, tsp2_pass = false, tsp3_pass = false;
ofstream outfile;


int main(void)
    {
    SetPriorityClass(GetCurrentProcess(), REALTIME_PRIORITY_CLASS);
    /*
    REALTIME_PRIORITY_CLASS------highest
    HIGH_PRIORITY_CLASS
    ABOVE_NORMAL_PRIORITY_CLASS
    NORMAL_PRIORITY_CLASS
    BELOW_NORMAL_PRIORITY_CLASS
    IDLE_PRIORITY_CLASS------lowest
    */
    time_t seconds_start, seconds_end, Start, End;
    double dif;
    stringstream out;
    StringType FileName, filePoint, FilePrefix;
    int fileList, bailTime;

    outfile.open("report.txt");
    if (outfile.fail())
        {
        cerr << "Error: Could not open file report.txt" << endl;
        cout << "Press any key to exit the program..." << endl;
        cin.ignore();
        exit(1);
        }

    cout << "Enter file prefix (such as 'tsp.d'): " << endl;
    cin >> FilePrefix;
    cout << "Enter number of files to be processed: " << endl;
    cin >> fileList;
    cout << "Enter per algorithm time limit (in seconds) for one TSP graph: " << endl;
    cin >> bailTime;

    outfile << "Running program tspcombined" << endl << endl;
    outfile << "Number of data files to be processsed: " << fileList << endl;
    outfile << "Per algorithm time limit (in seconds) for one TSP graph: " << bailTime << endl << endl;

    // Start time is placed here so that the time while inputing data will not be counted.
    Start = time(NULL);

    // In 2017, the following code was adjusted by using 3 if statements and bool variables so that if a tsp algorithm exceeds
    // its time limit, then that one is no longer executed, but the others continue to run. In addition, if all 3 algorithms
    // have exceeded their time limits, then the program is ended.

    for (int i = 0; i < fileList; i++)
        {
        out << i + 3;
        filePoint = out.str();
        out.str("");
        FileName = FilePrefix + filePoint;
        outfile << endl << endl << "|||||||||||||||||||||||||||||Processing " << FileName << "||||||||||||||||||||||||" << endl;
        cout << endl << endl << "|||||||||||||||||||||||||||||Processing " << FileName << "||||||||||||||||||||||||" << endl;

        // Check to see if we should run the tsp1 algorithm:
        if (tsp1_pass == false)
            {
            outfile << "---------------Running TSP1------------------" << endl;
            cout << "---------------Running TSP1------------------" << endl;
            seconds_start = time(NULL);
            TSP1(FileName);
            seconds_end = time(NULL);
            dif = difftime(seconds_end, seconds_start);
            outfile << endl << "--------------Execution time for TSP1: " << dif << "s---------------------" << endl;
            cout << endl << "--------------Execution time for TSP1: " << dif << "s---------------------" << endl;
            if (dif > bailTime)    // if statement to stop execution of tsp1 testing if time limit has been exceeded. 
                {
                tsp1_pass = true;
                outfile << endl << "TSP1 execution has exceeded " << bailTime << " seconds, TSP1 processing halted" << endl;
                cout << endl << "TSP1 execution has exceeded " << bailTime << " seconds, TSP1 processing halted" << endl;
                }
            }

        // Check to see if we should run the tsp2 algorithm:
        if (tsp2_pass == false)
            {
            outfile << endl << "---------------Running TSP2------------------" << endl;
            cout << endl << "---------------Running TSP2------------------" << endl;
            seconds_start = time(NULL);
            TSP2(FileName);
            seconds_end = time(NULL);
            dif = difftime(seconds_end, seconds_start);
            outfile << endl << "--------------Execution time for TSP2: " << dif << "s---------------------" << endl;
            cout << endl << "--------------Execution time for TSP2: " << dif << "s---------------------" << endl;
            if (dif > bailTime)    // if statement to stop execution of tsp2 testing if time limit has been exceeded.
                {
                tsp2_pass = true;
                outfile << endl << "TSP2 execution has exceeded " << bailTime << " seconds, TSP2 processing halted" << endl;
                cout << endl << "TSP2 execution has exceeded " << bailTime << " seconds, TSP2 processing halted" << endl;
                }
            }

        // Check to see if we should run the tsp3 algorithm: 
        if (tsp3_pass == false)
            {
            outfile << endl << "---------------Running TSP3------------------" << endl;
            cout << endl << "---------------Running TSP3------------------" << endl;
            seconds_start = time(NULL);
            TSP3(FileName);
            seconds_end = time(NULL);
            dif = difftime(seconds_end, seconds_start);
            outfile << endl << "--------------Execution time for TSP3: " << dif << "s---------------------" << endl;
            cout << endl << "--------------Execution time for TSP3: " << dif << "s---------------------" << endl;
            if (dif > bailTime)    // if statement to stop execution of tsp3 testing if time limit has been exceeded.
                {
                tsp3_pass = true;
                outfile << endl << "TSP3 execution has exceeded " << bailTime << " seconds, TSP3 processing halted" << endl;
                cout << endl << "TSP3 execution has exceeded " << bailTime << " seconds, TSP3 processing halted" << endl;
                }
            }

        End = time(NULL);
        dif = difftime(End, Start);

        // Check to see if all 3 algorithms ended.
        if (tsp1_pass && tsp2_pass && tsp3_pass)
            break;
        
        outfile << endl << "Current cumulative execution time: " << dif << "s" << endl;
        cout << endl << "Current cumulative execution time: " << dif << "s" << endl;
        }

    outfile << endl << endl << endl << "Total cumulative execution time: " << dif << "s" << endl;
    cout << endl << endl << endl << "Total cumulative execution time: " << dif << "s" << endl;

    outfile.close();
    cout << "Press any key to exit the program..." << endl;
    cin.ignore();
    cin.get();
    return 0;
    }


 /* Author:  Br. David Carlson
    Date:    January 11, 2002
    Revised: July 4, 2017
    Given:   FileName   A string giving the name of the data file to process.
    Task:    This function solves the traveling salesperson problem on the data file whose name is in FileName.
             It does so by enumerating all the possible tours of the cities and choosing the best one.
             This is therefore the brute-force method. This version uses backtracking to generate all possible tours.
             However, it does not use the backtracking to avoid needless additions.  Instead, it only adds up the costs
             for a tour when the complete tour has been generated. The output 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.
    Return:  Nothing except for the items sent back in the global variables, of which only the following are used:
             outfile    The opened output file stream.
             tsp1_pass  A flag that, if true, indicates that TSP1 has passed the time limit.       
    */
void TSP1(StringType FileName)
    {
    AvailList Avail;
    CityList Tour;
    int k;

    if (ReadData(NumCities, Cost, FileName))
        {
        cout << "Solving TSP for number of cities: " << NumCities << endl << endl;
        outfile << "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;

        TSP1Choose(1, Avail, Tour);

        if (MinCost < LONG_MAX)
            {
            cout << "The lowest cost was: " << MinCost << endl;
            cout << "This was for the following tour of the cities:" << endl;
            outfile << "The lowest cost was: " << MinCost << endl;
            outfile << "This was for the following tour of the cities:" << endl;
            for (k = 0; k < NumCities; k++)
                {
                cout << setw(4) << BestTour.Info[k];
                outfile << setw(4) << BestTour.Info[k];
                }
            }
        else
            {
            cout << "No solution was found" << endl;
            outfile << "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;

        outfile << endl << endl;
        outfile << "Total number of tours checked was:  " << NumTours << endl;
        outfile << "Total number of additions used was: " << NumAdditions << endl;
        outfile << "Total number of comparisons used was: " << NumCompares << endl;
        outfile << "Total number of additions and comparisons was: " << NumAdditions + NumCompares << endl;
        }
    else
       {
       outfile << endl << "Reading of this data file failed: " << FileName << endl << endl;
       cout << endl << "Reading of this data file failed: " << FileName << endl << endl;
       }
    }


/* Author:  Br. David Carlson
   Date:    January 11, 2002
   Revised: July 4, 2017
   Given:   FileName   A string giving the name of the data file to process.
   Task:    This function solves the traveling salesperson problem on the data file whose name is in FileName.
            It does so by enumerating all the possible tours of the cities and choosing the best one.
            This is therefore a version of the brute-force method. This version uses backtracking to generate all possible
            tours and uses the backtracking to avoid needless additions. For example, in a 4 city TSP, 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. Appropriate output is written to the screen and to
            the report file (the one using file stream outfile, passed as a global variable for efficiency). The output 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.
   Return:  Nothing except for the items sent back in the global variables, of which only the following are used:
            outfile    The opened output file stream.
            tsp2_pass  A flag that, if true, indicates that TSP2 has passed the time limit.
*/
void TSP2(StringType FileName)
    {
    AvailList Avail;
    CityList Tour;
    int k;

    if (ReadData(NumCities, Cost, FileName))
        {
        cout << "Solving TSP for number of cities: " << NumCities << endl << endl;
        outfile << "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;

        TSP2Choose(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;
            outfile << "The lowest cost was: " << MinCost << endl;
            outfile << "This was for the following tour of the cities:" << endl;

            for (k = 0; k < NumCities; k++)
                {
                cout << setw(4) << BestTour.Info[k];
                outfile << setw(4) << BestTour.Info[k];
                }
            }
        else
            {
            cout << "No solution was found" << endl;
            outfile << "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;

        outfile << endl << endl;
        outfile << "Total number of tours checked was:  " << NumTours << endl;
        outfile << "Total number of additions used was: " << NumAdditions << endl;
        outfile << "Total number of comparisons used was: " << NumCompares << endl;
        outfile << "Total number of additions and comparisons was: " << NumAdditions + NumCompares << endl;
        }
    else
        {
        outfile << endl << "Reading of this data file failed: " << FileName << endl << endl;
        cout << endl << "Reading of this data file failed: " << FileName << endl << endl;
        }
    }


/* Author:  Br. David Carlson
   Date:    January 11, 2002
   Revised: July 4, 2017
   Given:   FileName   A string giving the name of the data file to process.
   Task:    This function solves the traveling salesperson problem on the data file whose name is in FileName.
            It does so by enumerating all the possible tours of the cities and choosing the best one.
            This is therefore a version of the brute-force method. This version uses backtracking to generate all possible
            tours and uses the backtracking to avoid needless additions. For example, in a 4 city TSP, 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. This program also eliminates some needless additions by
            giving up on any partial tour whose cost already equals or exceeds that of the best tour found thus far. This reduces
            the number of additions, but adds some comparisons.  On test data the net result seems to be a faster program.
            Appropriate output is written to the screen and to the report file (the one using file stream outfile, passed as a
            global variable for efficiency). The output 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.
   Return:  Nothing except for the items sent back in the global variables, of which only the following are used:
            outfile    The opened output file stream.
            tsp2_pass  A flag that, if true, indicates that TSP2 has passed the time limit.
*/
void TSP3(StringType FileName)
    {
    AvailList Avail;
    CityList Tour;
    int k;

    if (ReadData(NumCities, Cost, FileName))
        {
        cout << "Solving TSP for number of cities: " << NumCities << endl << endl;
        outfile << "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;

        TSP3Choose(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;
            outfile << "The lowest cost was: " << MinCost << endl;
            outfile << "This was for the following tour of the cities:" << endl;

            for (k = 0; k < NumCities; k++)
                {
                cout << setw(4) << BestTour.Info[k];
                outfile << setw(4) << BestTour.Info[k];
                }
            }
        else
            {
            cout << "No solution was found" << endl;
            outfile << "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;

        outfile << endl << endl;
        outfile << "Total number of tours checked was:  " << NumTours << endl;
        outfile << "Total number of additions used was: " << NumAdditions << endl;
        outfile << "Total number of comparisons used was: " << NumCompares << endl;
        outfile << "Total number of additions and comparisons was: " << NumAdditions + NumCompares << endl;
        }
    else
        {
        outfile << endl << "Reading of this data file failed: " << FileName << endl << endl;
        cout << endl << "Reading of this data file failed: " << FileName << endl << endl;
        }
    }


/* 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.
   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 TSP1Choose(int NumChosen, AvailList Avail, CityList Chosen)
    {
    int m;
    long NewCost = 0;

    NumCompares++;
    if (NumChosen == NumCities)   // stopping case, all cities have been chosen
        {
        // Add up the costs for this tour:
        for (m = 0; m < NumCities - 1; m++)
            {
            NewCost = NewCost + Cost[Chosen.Info[m]][Chosen.Info[m + 1]];
            NumAdditions++;
            }
        // Add on the cost to go back to city 0:
        NewCost = NewCost + 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;
                TSP1Choose(NumChosen + 1, Avail, Chosen);
                Avail.Info[m] = true;
                }
            }
        }
    }
    

/* 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 TSP2Choose(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++;
                TSP2Choose(NumChosen + 1, Avail, Chosen, NewCost);
                Avail.Info[m] = true;
                }
            }
        }
    }


/* 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 TSP3Choose(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++;
                NumCompares++;
                if (NewCost < MinCost)
                    TSP3Choose(NumChosen + 1, Avail, Chosen, NewCost);
                //*** else, don't even bother to try to choose more cities. Here is where "branch and bound" is used.

                Avail.Info[m] = true;
                }
            }
        }
    }


/* 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];
    }


/* Given:   Filename   The name of the TSP data file to be read.
   Task:    To open the file whose name is in FileName and to read from it the number of cities and then the matrix
            of costs to travel between pairs of cities.
   Return:  NumCities  The number of cities specified in the data file.
            Cost       The matrix of costs.
            A boolean is returned in the function name to indicate if ReadData succeeded or not. False is returned
            if the file cannot be opened or the number of cities is too small or too large. Otherwise, true is returned.
*/
bool ReadData(int & NumCities, CostArray Cost, StringType FileName)
    {
    fstream fs;
    int Row, Column;

    fs.open(FileName, ios::in);
    if (fs.fail())
        {
        cerr << "Error: Could not open file: " << FileName << endl;
        outfile << endl << "Error: Could not open file: " << FileName << endl;
        return false;
        }

    fs >> NumCities;

    if ((NumCities > MaxCities) || (NumCities < 2))
        {
        cout << "Error: Number of cities must be from 2 to " << MaxCities << endl;
        outfile << endl << "Error: Number of cities must be from 2 to " << MaxCities << endl;
        return false;
        }
    else
        {
        for (Row = 0; Row < NumCities; Row++)
            for (Column = 0; Column < NumCities; Column++)
                fs >> Cost[Row][Column];
        }

    fs.close();
    return true;
    }