views:

1298

answers:

4

Greetings everyone, new to the forums :)

I'm currently writing a Simulated Annealing code to solve a traveling salesman problem and have run into difficulties with storing and using my read data from a txt file. Each row & column in the file represents each city, with the distance between two different cities stored as a 15 x 15 matrix:

0.0 5.0 5.0 6.0 7.0 2.0 5.0 2.0 1.0 5.0 5.0 1.0 2.0 7.1 5.0
5.0 0.0 5.0 5.0 5.0 2.0 5.0 1.0 5.0 6.0 6.0 6.0 6.0 1.0 7.1
5.0 5.0 0.0 6.0 1.0 6.0 5.0 5.0 1.0 6.0 5.0 7.0 1.0 5.0 6.0
6.0 5.0 6.0 0.0 5.0 2.0 1.0 6.0 5.0 6.0 2.0 1.0 2.0 1.0 5.0
7.0 5.0 1.0 5.0 0.0 7.0 1.0 1.0 2.0 1.0 5.0 6.0 2.0 2.0 5.0
2.0 2.0 6.0 2.0 7.0 0.0 5.0 5.0 6.0 5.0 2.0 5.0 1.0 2.0 5.0
5.0 5.0 5.0 1.0 1.0 5.0 0.0 2.0 6.0 1.0 5.0 7.0 5.0 1.0 6.0
2.0 1.0 5.0 6.0 1.0 5.0 2.0 0.0 7.0 6.0 2.0 1.0 1.0 5.0 2.0
1.0 5.0 1.0 5.0 2.0 6.0 6.0 7.0 0.0 5.0 5.0 5.0 1.0 6.0 6.0
5.0 6.0 6.0 6.0 1.0 5.0 1.0 6.0 5.0 0.0 7.0 1.0 2.0 5.0 2.0
5.0 6.0 5.0 2.0 5.0 2.0 5.0 2.0 5.0 7.0 0.0 2.0 1.0 2.0 1.0
1.0 6.0 7.0 1.0 6.0 5.0 7.0 1.0 5.0 1.0 2.0 0.0 5.0 6.0 5.0
2.0 6.0 1.0 2.0 2.0 1.0 5.0 1.0 1.0 2.0 1.0 5.0 0.0 7.0 6.0
7.0 1.0 5.0 1.0 2.0 2.0 1.0 5.0 6.0 5.0 2.0 6.0 7.0 0.0 5.0
5.0 7.0 6.0 5.0 5.0 5.0 6.0 2.0 6.0 2.0 1.0 5.0 6.0 5.0 0.0

To read this I have a LoadCities() function as shown below:

#include "iostream"
#include "fstream"   
#include "string"   
using namespace std;

double distances [15][15];  

void LoadCities()
{
    ifstream CityFile;

    if (!CityFile.is_open()) //check is file has been opened
    {
        CityFile.open ("Cities.txt", ios::in | ios::out);

        if (!CityFile)
        {
            cerr << "Failed to open " << CityFile << endl;
            exit(EXIT_FAILURE);  //abort program
        }
    }

    int length;
    char * buffer;
    string cities;

    CityFile.seekg(0, ios::end);
    length = CityFile.tellg();
    CityFile.seekg (0, ios::beg);

    buffer = new char [length];

    cities = CityFile.read (buffer,length); 

    string rows = strtok(cities, "\n");

    distances = new double[rows.length()][rows.length()];

            for (int i = 0; i < (string) rows.length(); i++)
            {
                string distance = strtok(rows[i], " ");

                for (int j = 0; j < distance.length(); j++)
                {
                    distances[i][j] = (double) Parse(distance[j]);
                }
            }

    CityFile.close();
}

I've attempted an alternative istreambuf_iterator method to get to the point of manipulating the read material into arrays, however I always seem to run into complications:

ifstream CityFile("Cities.txt");
string theString((std::istreambuf_iterator<char>(CityFile)), std::istreambuf_iterator<char>());

Any help would be much appriciated. Been bashing my head against this with little success!

################ EDIT / Update

@ SoapBox - Some Detail of the SA code, functions and main(). This is not clean, efficient, tidy and isn't ment to be at this stage, just needs to work for the moment. This version (below) works and is setup to solve polynomials (simplest problems). What needs to be done to convert it to a Traveling Salesman Problem is to:

  1. Write the LoadCities() function to gather the distance data. (Current)

  2. Change Initialise() to get the Total of the distances involved

  3. Change E() to the TSP function (e.g. Calculate distance of a random route)

The latter two I know I can do, however I require LoadCities() to do it. Nothing else needs to be changed in the following script.

#include "math.h"
#include "iostream"
#include "fstream"
#include "time.h"   // Define time()
#include "stdio.h"  // Define printf()
#include "randomc.h"    // Define classes for random number generators
#include "mersenne.cpp" // Include code for the chosen random number generator

using namespace std; // For the use of text generation in application

double T;
double T_initial;

double S;
double S_initial;
double S_current;
double S_trial;

double E_current;

int N_step;        // Number of Iterations for State Search per Temperature
int N_max;         //Number of Iterations for Temperature
int Write;

const double EXP = 2.718281828;

//------------------------------------------------------------------------------
//Problem Function of Primary Variable (Debugged 17/02/09 - Works as intended)

double E(double x) //ORIGNINAL
{
    double y = x*x - 6*x + 2;

     return y;
}

//------------------------------------------------------------------------------
//Random Number Generation Function (Mod 19/02/09 - Generated intergers only & fixed sequence)

double Random_Number_Generator(double nHigh, double nLow) 
{
    int seed = (int)time(0);   // Random seed

    CRandomMersenne RanGen(seed);  // Make instance of random number generator

    double fr;                          // Random floating point number

    fr = ((RanGen.Random() * (nHigh - nLow)) + nLow);   // Generatres Random Interger between nLow & nHigh

    return fr;
}

//------------------------------------------------------------------------------
//Initializing Function (Temp 17/02/09)

void Initialize() //E.g. Getting total Distance between Cities
{
    S_initial = Random_Number_Generator(10, -10);

    cout << "S_Initial: " << S_initial << endl;
}

//------------------------------------------------------------------------------
//Cooling Schedule Function (make variables) (Completed 16/02/09)

double Schedule(double Temp, int i) // Need to find cooling schedule
{
    double CoolingRate = 0.9999;

    return Temp *= CoolingRate; 
}

//------------------------------------------------------------------------------
//Next State Function (Mod 18/02/09)

double Next_State(double T_current, int i)
{
        S_trial = Random_Number_Generator(pow(3, 0.5), pow(3, 0.5)*-1); 

     S_trial += S_current;

     double E_t = E(S_trial);
     double E_c = E(S_current);

        double deltaE = E_t - E_c;         //Defines gradient of movement

        if ( deltaE <= 0 )           //Downhill
        {    
      S_current = S_trial;
      E_current = E_t;
     }
        else                //Uphill
        {
            double R = Random_Number_Generator(1,0);      //pseudo random number generated
      double Ratio = 1-(float)i/(float)N_max;    //Control Parameter Convergence to 0
      double ctrl_pram = pow(EXP, (-deltaE / T_current)); //Control Parameter

            if (R < ctrl_pram*Ratio)          //Checking 
            {   
       S_current = S_trial;       //Expresses probability of uphill acceptance
       E_current = E_t;        
      }
      else 
       E_current = E_c;
        }

     return S_current;
}

//------------------------------------------------------------------------------
//Metropolis Function (Mod 18/02/09)

double Metropolis(double S_start, double T_current, int N_Steps, int N_temperatures)
{
     S_current = S_start;            //Initialised S_initial equated to S_current

     for ( int i=1; i <= N_step; i++ )        //Iteration of neighbour states
     S_current = Next_State(T_current, N_temperatures);  //Determines acceptance of new states

     return S_current;
}

//------------------------------------------------------------------------------
//Write Results to Notepad (Completed 18/02/09)

void WriteResults(double i, double T, double x, double y)
{
//This function opens a results file (if not already opened)
//and stores results for one time step

    static ofstream OutputFile;
    const int MAXLENGTH = 80;

    if (!OutputFile.is_open()) //check is file has been opened
    {
        //no it hasn't. Get a file name and open it.
        char FileName[MAXLENGTH];

        //read file name
        cout << "Enter file name: ";
        do
        {
            cin.getline(FileName, MAXLENGTH);
        }
        while (strlen(FileName) <= 0); //try again if length of string is 0

        //open file
        OutputFile.open(FileName);

        // check if file was opened successfully
        if (!OutputFile)
        {
            cerr << "Failed to open " << FileName << endl;
            exit(EXIT_FAILURE);  //abort program
        }

     OutputFile << "Iterations" << '\t' << "Temperatures" << '\t' << "X-Value" << '\t' << "Y-Value" << endl; 
        OutputFile << endl;
    }

    //OutputFile.width(10);
    OutputFile << i << '\t' << T << '\t' << x << '\t' << y << endl; 

    if (i == N_max) 
    { 
     OutputFile << endl
         << "Settings: " << endl
         << "Initial Temperature: " << T_initial << endl
         << "Temperature Iterations: " << N_max << endl
         << "Step Iterations: " << N_step << endl
         << endl
         << "Results: " << endl
         << "Final Temperature: " << T << endl 
         << "Minimum: " << S << endl;

     OutputFile.close();
    }
}

//------------------------------------------------------------------------------
//Main SA Function (Mod 17/02/09)

void SA(int W)
{
    S = S_initial;
    T = T_initial;

    for ( int N_temperatures = 1 ; N_temperatures <= N_max ; N_temperatures++ )
    {
        S = Metropolis( S, T, N_step, N_temperatures);
        T = Schedule(T, N_temperatures);

     if (W == 1)
      WriteResults(N_temperatures, T, S, E_current);
    }

    cout << "Result" << endl
    << "Y-value> " << S << endl
    << "Temperature> " << T << endl;

}

//------------------------------------------------------------------------------
//Execution of Traveling Salesman Problem (Progress 18/02/09)


int main()
{
    cout << "Quadratic Function" << endl
      << "Solving method: Simulated Annealing" << endl;
    cout << "" << endl;

    cout << "Select desired Initial Temperature:" << endl
      << "> ";
    cin >> T_initial;

    cout << "Select desired number of Temperature Iterations:" << endl
      << "> ";
    cin >> N_max;

    cout << "Select desired number of step Iterations:" << endl
      << "> ";
    cin >> N_step;

    Initialize();

    cout << "Write to file: (1 / 0) " << endl
      << "> ";
    cin >> Write;

    SA(Write);

    system ("PAUSE");

    return 0;
}

@ strager - I know its bad code, but unfortunatly with the time constraints involved for my project and the consiquental learning curve, results are what are needed! :) It'll be tidied up at latter stages.

@ dirkgently - That was the initial reason for doing it this way, and hence why my first attempt is to go at it like so.

+1  A: 

Does it even compile? I get ~7 errors. A sample:

strtok(cities, "\n");

strtok()'s first argument is a char * and not a std::string.

Does this help?

void LoadCities()
{
  std::vector<double> f((std::istream_iterator<double>
       (std::ifstream("city.txt"))), /* replace filename with your own */
    (std::istream_iterator<double>()));
  if (!f.empty()) {
    std::cout << f.size() << "\n";
    /* print an arbitrary data point with 2 places of decimal */
    std::cout << std::setprecision(2) << f[ 0 ] << std::endl; 

  }
}

Working with matrices doesn't mean you need to have a multidimensional array. Especially, with 2D arrays. Of course it's easier to read and write ;)

dirkgently
as it is it doesn't compile. Only way to compile it is to delete everything from 'cities = ..." to the end and simply have: CityFile.read(buffer,length);, cout.write(buffer,length); CityFile.close(); - which doesn't help me much
Temperedsoul
@Temperedsoul: So, now do you have it fixed? If you do, why don't you mark schnaader's solution as accepted?
dirkgently
+4  A: 

How about this? (KISS solution)

void LoadCities() {
  int x, y;
  ifstream in("Cities.txt");

  if (!in) {
    cout << "Cannot open file.\n";
    return;
  }

  for (y = 0; y < 15; y++) {
    for (x = 0; x < 15; x++) {
      in >> distances[x][y];
    }
  }

  in.close();
}

Works for me. Might not be that complex and perhaps isn't very performant, but as long as you aren't reading a 1000x1000 array, you won't see any difference.

schnaader
Nice and simplistic, however for some reason its outputting 0 or every value when I test it. E.g adding the following right after the << operation: "cout << x << "\t" << y << '\t' << distances[x][y] << endl;"
Temperedsoul
Hm.. works here (using G++).
schnaader
@Temperedsoul: Look at your data. It's double, but has no significant part after the decimal. If you want a 5.0 you'd need to do tell cout so. I'll update my example.
dirkgently
A: 

You probably want something simpler, like this:

std::vector<std::vector<std::string> > LoadCities(const std::string &filename)
{
    using namespace std;

    ifstream file;
    file.open(filename, ios::in | ios::out);

    if(!file.is_open()) {
        // error
        return vector<vector<double> >();
    }

    vector<vector<double> > data;
    string line;

    while(!std::getline(file, line, '\n').eof()) {
        istringstream reader(line);

        vector<double> lineData;

        string::const_iterator i = line.begin();

        while(!reader.eof()) {
            double val;
            reader << val;

            if(reader.fail())
                break;

            lineData.push_back(val);
        }

        data.push_back(lineData);
    }

    return data;
}

Basically you use streams to input the data. I'm probably doing something wrong (I have never dealt with iostreams ;P) but this should give you the general idea of how to structure a matrix reader.

strager
Results in 4 errors, three of them C2664 - 'function' : cannot convert parameter number from 'type1' to 'type2' - I will see if I can clear them up.
Temperedsoul
A: 

Here is how I would load/save it:

#include <iostream>
#include <fstream>
#include <string>

int width = 0;
int height = 0;
double **distances;

void WriteDouble( std::ofstream &stream, double toWrite )
{
    char buffer[8];
    memcpy( buffer, &toWrite, 8 );
    stream.write( buffer, 8 );
}

void WriteInt( std::ofstream &stream, int toWrite )
{
    char buffer[4];
    memcpy( buffer, &toWrite, 4 );
    stream.write( buffer, 4 );
}

double ReadDouble( std::ifstream &stream )
{
    double d = 0;
    stream.read( (char *)&d, 8 );
    return d;
}

int ReadInt( std::ifstream &stream )
{
    int i = 0;
    stream.read( (char *)&i, 4 );
    return i;
}

void Save()
{
    std::ofstream stream( "cities", std::ios::out | std::ios::binary );

    if( !stream.good() ) {
     throw std::exception( "Error opening stream" );
    }

    WriteInt( stream, width );
    WriteInt( stream, height );

    for( int x = 0; x < width; x++ ) {
     for( int y = 0; y < height; y++ ) {
      WriteDouble( stream, distances[x][y] );
     }
    }

    stream.close();
}

void Load()
{
    std::ifstream stream( "cities", std::ios::in | std::ios::binary );

    if( !stream.good() ) {
     throw std::exception( "Error opening stream" );
    }

    width = ReadInt( stream );
    height = ReadInt( stream );

    distances = new double *[width];

    for( int i = 0; i < width; i++ ) {
     distances[i] = new double[height];
    }

    for( int x = 0; x < width; x++ ) {
     for( int y = 0; y < height; y++ ) {
      distances[x][y] = ReadDouble( stream );
     }
    }

    stream.close();
}

void RunSaveTest()
{
    width = 15;
    height = 15;

    distances = new double *[width];

    for( int i = 0; i < width; i++ ) {
     distances[i] = new double[height];
    }

    for( int x = 0; x < width; x++ ) {
     for( int y = 0; y < height; y++ ) {
      distances[x][y] = (double)x / (double)( y + 1 );
      std::cout << distances[x][y] << std::endl;
     }
    }

    Save();
}

void RunLoadTest()
{
    Load();

    for( int x = 0; x < width; x++ ) {
     for( int y = 0; y < height; y++ ) {
      std::cout << distances[x][y] << std::endl;
     }
    }
}

int main()
{
    RunSaveTest();
    // RunLoadTest();

    return 0;
}
kitchen