TSP Solver and Generator: src/tspsolver.h Source File

TSP Solver and Generator
00001 
00028 #ifndef TSPSOLVER_H
00029 #define TSPSOLVER_H
00030 
00031 #include <QtCore>
00032 #include <limits>
00033 
00040 #ifndef INFINITY
00041 #   define INFINITY std::numeric_limits<double>::infinity()
00042 #endif
00043 
00049 namespace TSPSolver {
00050 
00052 typedef QList<QList<double> > TMatrix;
00053 
00059 struct SStep {
00061     struct SCandidate {
00062         int nRow; 
00063         int nCol; 
00064 
00066         SCandidate() {
00067             nCol = nRow = -1;
00068         }
00070         bool operator ==(const SCandidate &cand) const {
00071             return ((cand.nRow == nRow) && (cand.nCol == nCol));
00072         }
00073     };
00074 
00076     enum NextStep {
00077         NoNextStep, 
00078         LeftBranch, 
00079         RightBranch 
00080     };
00081 
00082     TMatrix matrix; 
00083     double price; 
00084 
00085     SCandidate candidate; 
00086     QList<SCandidate> alts; 
00087     SStep *pNode; 
00088     SStep *plNode; 
00089     SStep *prNode; 
00090     NextStep next; 
00091 
00093     SStep() {
00094         price = -1;
00095         pNode = plNode = prNode = NULL;
00096         next = NoNextStep;
00097     }
00098 };
00099 
00104 class CTSPSolver: public QObject
00105 {
00106     Q_OBJECT
00107 
00108 public:
00109     static QString getVersionId();
00110 
00111     CTSPSolver(QObject *parent = NULL);
00112     void cleanup(bool processEvents = false);
00113     QString getSortedPath(const QString &city, const QString &separator = QString(" -> ")) const;
00114     int getTotalSteps() const;
00115     bool isOptimal() const;
00116     void setCleanupOnCancel(bool enable = true);
00117     SStep *solve(int numCities, const TMatrix &task);
00118     bool wasCanceled() const;
00119     ~CTSPSolver();
00120 
00121 public slots:
00122     void cancel();
00123 
00124 signals:
00129     void routePartFound(int n);
00130 
00131 private:
00132     bool mayNotBeOptimal, canceled, cc;
00133     int nCities, total;
00134     SStep *root;
00135     QHash<int,int> route;
00136     mutable QMutex mutex;
00137 
00138     double align(TMatrix &matrix);
00139     void deleteTree(SStep *&root, bool processEvents = false);
00140     void denormalize(TMatrix &matrix) const;
00141     QList<SStep::SCandidate> findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const;
00142     double findMinInCol(int nCol, const TMatrix &matrix, int exr = -1) const;
00143     double findMinInRow(int nRow, const TMatrix &matrix, int exc = -1) const;
00144     void finishRoute();
00145     bool hasSubCycles(int nRow, int nCol) const;
00146     void normalize(TMatrix &matrix) const;
00147     void subCol(TMatrix &matrix, int nCol, double val);
00148     void subRow(TMatrix &matrix, int nRow, double val);
00149 };
00150 
00151 }
00152 
00153 #ifdef DEBUG
00154 QDebug operator<<(QDebug dbg, const TSPSolver::TMatrix &matrix);
00155 QDebug operator<<(QDebug dbg, const TSPSolver::SStep::SCandidate &candidate);
00156 #endif // DEBUG
00157 
00158 #endif // TSPSOLVER_H