tspsolver.h

Go to the documentation of this file.

#ifndef TSPSOLVER_H
#define TSPSOLVER_H

#include <limits>

#include <QHash>
#include <QMutex>
#include <QObject>
#include <QStringList>

#ifndef INFINITY
#   define INFINITY std::numeric_limits<double>::infinity()
#endif

namespace TSPSolver {

typedef QList<QList<double> > TMatrix;

struct SStep {
    struct SCandidate {
        int nRow; 
        int nCol; 

        SCandidate() {
            nCol = nRow = -1;
        }
        bool operator ==(const SCandidate &cand) const {
            return ((cand.nRow == nRow) && (cand.nCol == nCol));
        }
    };

    enum NextStep {
        NoNextStep, 
        LeftBranch, 
        RightBranch 
    };

    TMatrix matrix; 
    double price; 

    SCandidate candidate; 
    QList<SCandidate> alts; 
    SStep *pNode; 
    SStep *plNode; 
    SStep *prNode; 
    NextStep next; 

    SStep() {
        price = -1;
        pNode = plNode = prNode = NULL;
        next = NoNextStep;
    }
};

class CTSPSolver: public QObject
{
    Q_OBJECT

public:
    static QString getVersionId();

    CTSPSolver(QObject *parent = NULL);
    void cleanup(bool processEvents = false);
    QString getSortedPath(const QString &city, const QString &separator = QString(" -> ")) const;
    int getTotalSteps() const;
    bool isOptimal() const;
    void setCleanupOnCancel(bool enable = true);
    SStep *solve(int numCities, const TMatrix &task);
    bool wasCanceled() const;
    ~CTSPSolver();

public slots:
    void cancel();

signals:
    void routePartFound(int n);

private:
    bool mayNotBeOptimal, canceled, cc;
    int nCities, total;
    SStep *root;
    QHash<int,int> route;
    mutable QMutex mutex;

    double align(TMatrix &matrix);
    void deleteTree(SStep *&root, bool processEvents = false);
    void denormalize(TMatrix &matrix) const;
    QList<SStep::SCandidate> findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const;
    double findMinInCol(int nCol, const TMatrix &matrix, int exr = -1) const;
    double findMinInRow(int nRow, const TMatrix &matrix, int exc = -1) const;
    void finishRoute();
    bool hasSubCycles(int nRow, int nCol) const;
    void normalize(TMatrix &matrix) const;
    void subCol(TMatrix &matrix, int nCol, double val);
    void subRow(TMatrix &matrix, int nRow, double val);
};

}

#ifdef DEBUG
QDebug operator<<(QDebug dbg, const TSPSolver::TMatrix &matrix);
QDebug operator<<(QDebug dbg, const TSPSolver::SStep::SCandidate &candidate);
#endif // DEBUG

#endif // TSPSOLVER_H