source: tspsg/src/tspsolver.h @ d45b48efe9

0.1.3.145-beta1-symbian
Last change on this file since d45b48efe9 was d45b48efe9, checked in by Oleksii Serdiuk, 14 years ago

Initial Symbian port.

Version 0.1.3.145-beta1, as published in the Nokia Ovi Store.

  • Property mode set to 100644
File size: 4.5 KB
Line 
1/*!
2 * \file tspsolver.h
3 * \author Copyright &copy; 2007-2010 Lёppa <contacts[at]oleksii[dot]name>
4 *
5 *  $Id$
6 *  $URL$
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 *  Define \c INFINITY if it's not already defined.
39 */
40#ifndef INFINITY
41        #define INFINITY std::numeric_limits<double>::infinity()
42#endif
43
44/*!
45 * \brief A TSP Solver namespace.
46 *
47 *  This namespace contains all the stuff required for solving TSP tasks.
48 */
49namespace TSPSolver {
50
51//! A matrix of city-to-city travel costs
52typedef QList<QList<double> > TMatrix;
53
54/*!
55 * \brief This structure represents one step of solving.
56 *
57 *  A tree of such elements will represent the solving process.
58 */
59struct SStep {
60        //! A structure that represents a candidate for branching
61        struct SCandidate {
62                int nRow; //!< A zero-based row number of the candidate
63                int nCol; //!< A zero-based column number of the candidate
64
65                //! Assigns default values
66                SCandidate() {
67                        nCol = nRow = -1;
68                }
69                //! An operator == implementation
70                bool operator ==(const SCandidate &cand) const {
71                        return ((cand.nRow == nRow) && (cand.nCol == nCol));
72                }
73        };
74
75        //! An enum that describes possible selection of the next step
76        enum NextStep {
77                NoNextStep, //!< No next step (end of solution)
78                LeftBranch, //!< Left branch was selected for the next step
79                RightBranch //!< Right branch was selected for the next step
80        };
81
82        TMatrix matrix; //!< This step's matrix
83        double price; //!< The price of travel to this step
84
85        SCandidate candidate; //!< A candiadate for branching in the current step
86        QList<SCandidate> alts; //!< A list of alternative branching candidates
87        SStep *pNode; //!< Pointer to the parent step
88        SStep *plNode; //!< Pointer to the left branch step
89        SStep *prNode; //!< Pointer to the right branch step
90        NextStep next; //!< Indicates what branch was selected for the next step
91
92        //! Assigns default values
93        SStep() {
94                price = -1;
95                pNode = plNode = prNode = NULL;
96                next = NoNextStep;
97        }
98};
99
100/*!
101 * \brief This class solves Travelling Salesman Problem task.
102 * \author Copyright &copy; 2007-2010 Lёppa <contacts[at]oleksii[dot]name>
103 */
104class CTSPSolver: public QObject
105{
106        Q_OBJECT
107
108public:
109        static QString getVersionId();
110
111        CTSPSolver(QObject *parent = NULL);
112        void cleanup(bool processEvents = false);
113        QString getSortedPath(const QString &city, const QString &separator = QString(" -> ")) const;
114        int getTotalSteps() const;
115        bool isOptimal() const;
116        void setCleanupOnCancel(bool enable = true);
117        SStep *solve(int numCities, const TMatrix &task);
118        bool wasCanceled() const;
119        ~CTSPSolver();
120
121public slots:
122        void cancel();
123
124signals:
125        /*!
126         * \brief This signal is emitted once every time a part of the route is found.
127         * \param n Indicates the number of the route parts found.
128         */
129        void routePartFound(int n);
130
131private:
132        bool mayNotBeOptimal, canceled, cc;
133        int nCities, total;
134        SStep *root;
135        QHash<int,int> route;
136        mutable QMutex mutex;
137
138        double align(TMatrix &matrix);
139        void deleteTree(SStep *&root, bool processEvents = false);
140        void denormalize(TMatrix &matrix) const;
141        QList<SStep::SCandidate> findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const;
142        double findMinInCol(int nCol, const TMatrix &matrix, int exr = -1) const;
143        double findMinInRow(int nRow, const TMatrix &matrix, int exc = -1) const;
144        void finishRoute();
145        bool hasSubCycles(int nRow, int nCol) const;
146        void normalize(TMatrix &matrix) const;
147        void subCol(TMatrix &matrix, int nCol, double val);
148        void subRow(TMatrix &matrix, int nRow, double val);
149};
150
151}
152
153#ifdef DEBUG
154QDebug operator<<(QDebug dbg, const TSPSolver::TMatrix &matrix);
155QDebug operator<<(QDebug dbg, const TSPSolver::SStep::SCandidate &candidate);
156#endif // DEBUG
157
158#endif // TSPSOLVER_H
Note: See TracBrowser for help on using the repository browser.