source: tspsg/src/tspsolver.h @ 243b53b608

appveyorimgbotreadme
Last change on this file since 243b53b608 was 2940c14782, checked in by Oleksii Serdiuk, 11 years ago

Relicensed TSP Solver and Generator under GPLv2 license.

Due to potential conflicts between GPLv3 and app stores.

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