source: tspsg-svn/trunk/src/tspsolver.h @ 134

Last change on this file since 134 was 124, checked in by laleppa, 14 years ago

+ Added support for Windows 7 Taskbar Extensions (namely, Progress Bars).

  • Cleanup is done in a separate thread now, so progress bar runs more smooth.
  • "Tabified" About dialog. Added GPL License and Credits.
  • Updated translations and tspsg.tag file.
  • Property svn:eol-style set to native
  • Property svn:keywords set to Id URL
File size: 4.6 KB
Line 
1/*!
2 * \file tspsolver.h
3 * \author Copyright &copy; 2007-2010 Lёppa <contacts[at]oleksii[dot]name>
4 *
5 *  $Id: tspsolver.h 124 2010-07-04 01:03:13Z laleppa $
6 *  $URL: https://tspsg.svn.sourceforge.net/svnroot/tspsg/trunk/src/tspsolver.h $
7 *
8 * \brief Defines TSPSolver namespace and everything needed for solving TSP tasks.
9 *
10 *  <b>TSPSG: TSP Solver and Generator</b>
11 *
12 *  This file is part of TSPSG.
13 *
14 *  TSPSG is free software: you can redistribute it and/or modify
15 *  it under the terms of the GNU General Public License as published by
16 *  the Free Software Foundation, either version 3 of the License, or
17 *  (at your option) any later version.
18 *
19 *  TSPSG is distributed in the hope that it will be useful,
20 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
21 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
22 *  GNU General Public License for more details.
23 *
24 *  You should have received a copy of the GNU General Public License
25 *  along with TSPSG.  If not, see <http://www.gnu.org/licenses/>.
26 */
27
28#ifndef TSPSOLVER_H
29#define TSPSOLVER_H
30
31#include <QtCore>
32#include <limits>
33
34/*!
35 * \def INFINITY
36 * \brief This value means infinity :-)
37 *
38 *  Some libraries already have \c INFINITY defined.
39 *  We need to redefine it for the \c INFINITY to always have the same value.
40 */
41#ifdef INFINITY
42        #undef INFINITY
43#endif
44#define INFINITY std::numeric_limits<double>::infinity()
45
46/*!
47 * \brief A TSP Solver namespace.
48 *
49 *  This namespace contains all the stuff required for solving TSP tasks.
50 */
51namespace TSPSolver {
52
53//! A matrix of city-to-city travel costs
54typedef QList<QList<double> > TMatrix;
55
56/*!
57 * \brief This structure represents one step of solving.
58 *
59 *  A tree of such elements will represent the solving process.
60 */
61struct SStep {
62        //! A structure that represents a candidate for branching
63        struct SCandidate {
64                int nRow; //!< A zero-based row number of the candidate
65                int nCol; //!< A zero-based column number of the candidate
66
67                //! Assigns default values
68                SCandidate() {
69                        nCol = nRow = -1;
70                }
71                //! An operator == implementation
72                bool operator ==(const SCandidate &cand) const {
73                        return ((cand.nRow == nRow) && (cand.nCol == nCol));
74                }
75        };
76
77        //! An enum that describes possible selection of the next step
78        enum NextStep {
79                NoNextStep, //!< No next step (end of solution)
80                LeftBranch, //!< Left branch was selected for the next step
81                RightBranch //!< Right branch was selected for the next step
82        };
83
84        TMatrix matrix; //!< This step's matrix
85        double price; //!< The price of travel to this step
86
87        SCandidate candidate; //!< A candiadate for branching in the current step
88        QList<SCandidate> alts; //!< A list of alternative branching candidates
89        SStep *pNode; //!< Pointer to the parent step
90        SStep *plNode; //!< Pointer to the left branch step
91        SStep *prNode; //!< Pointer to the right branch step
92        NextStep next; //!< Indicates what branch was selected for the next step
93
94        //! Assigns default values
95        SStep() {
96                price = -1;
97                pNode = plNode = prNode = NULL;
98                next = NoNextStep;
99        }
100};
101
102/*!
103 * \brief This class solves Travelling Salesman Problem task.
104 * \author Copyright &copy; 2007-2010 Lёppa <contacts[at]oleksii[dot]name>
105 */
106class CTSPSolver: public QObject
107{
108        Q_OBJECT
109
110public:
111        static QString getVersionId();
112
113        CTSPSolver(QObject *parent = NULL);
114        void cleanup(bool processEvents = false);
115        QString getSortedPath(const QString &city, const QString &separator = QString(" -> ")) const;
116        int getTotalSteps() const;
117        bool isOptimal() const;
118        void setCleanupOnCancel(bool enable = true);
119        SStep *solve(int numCities, const TMatrix &task);
120        bool wasCanceled() const;
121        ~CTSPSolver();
122
123public slots:
124        void cancel();
125
126signals:
127        /*!
128         * \brief This signal is emitted once every time a part of the route is found.
129         * \param n Indicates the number of the route parts found.
130         */
131        void routePartFound(int n);
132
133private:
134        bool mayNotBeOptimal, canceled, cc;
135        int nCities, total;
136        SStep *root;
137        QHash<int,int> route;
138        mutable QMutex mutex;
139
140        double align(TMatrix &matrix);
141        void deleteTree(SStep *&root, bool processEvents = false);
142        void denormalize(TMatrix &matrix) const;
143        QList<SStep::SCandidate> findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const;
144        double findMinInCol(int nCol, const TMatrix &matrix, int exr = -1) const;
145        double findMinInRow(int nRow, const TMatrix &matrix, int exc = -1) const;
146        void finishRoute();
147        bool hasSubCycles(int nRow, int nCol) const;
148        void normalize(TMatrix &matrix) const;
149        void subCol(TMatrix &matrix, int nCol, double val);
150        void subRow(TMatrix &matrix, int nRow, double val);
151};
152
153}
154
155#ifdef DEBUG
156QDebug operator<<(QDebug dbg, const TSPSolver::TMatrix &matrix);
157QDebug operator<<(QDebug dbg, const TSPSolver::SStep::SCandidate &candidate);
158#endif // DEBUG
159
160#endif // TSPSOLVER_H
Note: See TracBrowser for help on using the repository browser.