tsp.h

Go to the documentation of this file.

//==================================================================
// File                 : tsp.h
// Author               : rsagalyn
// Date                 : Aug 18, 2013
// Description  :
//==================================================================

#pragma once

#ifndef MWM_H_
#define MWM_H_

#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <limits>
#include <pthread.h>
#include <queue>
#include <stack>
#include <string>
#include <stdio.h>
#include <vector>

#include "twoOpt.h"

// Eigen
#include <Eigen/Dense> 
#include <Eigen/src/Geometry/Quaternion.h>

//#include "../Global.h"
//#include "../DistanceMetric.h"

using namespace std;

// Toggle printing debugging info to console
#define DEBUG 0

// Number of threads to use to fill N x N cost matrix
#define THREADS 1

// Calcualte lowest index controlled by thread id
#define START_AT(id,p,n) ((id)*(n)/(p))

// Calculate highest index controlled by thread id
#define END_AT(id,p,n) (START_AT((id)+1,p,n)-1)



class TSP
{
private:

        // x and y coords of a node
        struct City
        {
                double x;
                double y;
        };

        // Filename supplied on command line to read from
        string inFname;

        // Program-generated filename to output to
        string outFname;

        // List of odd nodes
        vector<int>odds;

        // Smaller cost matrix used to store distances between odd nodes
        // Used to find minimum matching on odd nodes
        double **cost; // dsy: maybe useless 

        // Initialization function
        void getNodeCount();

        // Find odd vertices in graph
        void findOdds();

        // Prim helper function
        int minKey(double key[], bool mstSet[]);


protected:


public:
        // Number of nodes
        int n;

        // euler circuit
        vector<int>circuit;

        // Store cities and coords read in from file
        vector<City>cities;

        // Full n x n cost matrix of distances between each city
        double **graph;

        // Current shortest path length
        double pathLength;


        // Adjacency list
        // Array of n dynamic arrays, each holding a list of nodes it's index is attached to
        vector<int> *adjlist;


        int start_idx[THREADS];

        int end_idx[THREADS];

        // n x 2 array to store length of TSP path starting at each node
        // col 0 => starting index   col 1 => path length from that node
        double **path_vals;

        // Constructor
        TSP(string in, string out);
        //TSP(vector<Point_2> nodes); // dsy
        //TSP(vector<Point_2> nodes, vector<vector<double>> weights); // dsy
        TSP(vector<Eigen::Vector2d> nodes, vector<vector<double>> weights); // dsy

        // Destructor
        ~TSP();

        // Calculate distance
        double get_distance(struct City c1, struct City c2);


        // Initialization functions
        void readCities();
        void fillMatrix_threads();

        // Find MST using Prim's algorithm
        void findMST_old();


        // Find perfect matching
        void perfect_matching();

        // Find best node to start euler at
        // Doesn't create tour, just checks
        int find_best_path(int);

        // Create tour starting at specified node
        void create_tour(int);

        // Private functions implemented by create_tour() and find_best_path()
        void euler (int pos, vector<int> &);
        //void euler(int);
        void make_hamilton(vector<int> &, double&);

        // Calls twoOpt function
        void make_shorter();


        // Debugging functions
        void printCities();
        void printAdjList();
        void printResult();
        void printEuler();
        void printPath();

        // Get node count
        int get_size() {return n;};
};

#endif /* MWM_H_ */