source: tspsg/src/tspsolver.h @ f383cb181c

0.1.3.145-beta1-symbian0.1.4.170-beta2-bb10appveyorimgbotreadme
Last change on this file since f383cb181c was e0fcac5f2c, checked in by Oleksii Serdiuk, 15 years ago
  • Finished documentation.
  • Sorted all functions in .cpp files according to order of their declaration in .h files.
  • Property mode set to 100644
File size: 2.8 KB
RevLine 
[caef58b531]1/*!
[e0fcac5f2c]2 * \file tspsolver.h
[caef58b531]3 * \author Copyright &copy; 2007-2009 Lёppa <contacts[at]oleksii[dot]name>
[67e53c96d7]4 *
5 *  $Id$
6 *  $URL$
7 *
[e0fcac5f2c]8 * \brief Defines #tMatrix typedef, sStep struct and CTSPSolver class.
9 *
[caef58b531]10 *  <b>TSPSG: TSP Solver and Generator</b>
11 *
[67e53c96d7]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
[993d5af6f6]31#include "globals.h"
[67e53c96d7]32
[bc1b8837b6]33#include "tspmodel.h"
34
[caef58b531]35//! A matrix of city-to-city travel costs.
[9aa0e521ed]36typedef QList<QList<double> > tMatrix;
[e664262f7d]37
[caef58b531]38/*!
39 * \brief This structure represents one step of solving.
40 *
41 *  A tree of such elements will represent the solving process.
42 */
43//! \todo TODO: List alternative candidates.
[67e53c96d7]44struct sStep {
[caef58b531]45        tMatrix matrix; //!< This step's matrix
46        double price; //!< The price of travel to this step
47        struct {
48                int nRow; //!< A zero-based row number of the candidate
49                int nCol; //!< A zero-based column number of the candidate
50        } candidate; //!< A candiadate for branching in the current matrix
51        bool alts; //!< Indicates whether or not matrix has alternative candidates
52        sStep *plNode; //!< Pointer to the left branch step
53        sStep *prNode; //!< Pointer to the right branch step
54
55        //! Assigns default values
56        sStep() {
57                price = candidate.nRow = candidate.nCol = -1;
58                alts = false;
59                plNode = prNode = NULL;
60        }
[67e53c96d7]61};
62
[e0fcac5f2c]63/*!
64 * \brief This class solves Travelling Salesman Problem task.
65 * \author Copyright &copy; 2007-2009 Lёppa <contacts[at]oleksii[dot]name>
66 *
67 * \todo TODO: Deletion of solution tree on destroy and cleanup.
68 */
[67e53c96d7]69class CTSPSolver
70{
[430bd7f7e9]71        Q_DECLARE_TR_FUNCTIONS(CTSPSolver)
72
[67e53c96d7]73public:
74        CTSPSolver();
[9cf98b9bd6]75        QString getSortedPath() const;
[e0fcac5f2c]76        static QString getVersionId();
[9cf98b9bd6]77        bool isOptimal() const;
[430bd7f7e9]78        sStep *solve(int, tMatrix, QWidget *parent = 0);
79
[e664262f7d]80private:
[9cf98b9bd6]81        bool mayNotBeOptimal;
[e664262f7d]82        int nCities;
83        sStep *root;
[430bd7f7e9]84        QHash<int,int> route;
[aaf2113307]85//      QHash<int,int> forbidden;
[e0fcac5f2c]86
[430bd7f7e9]87        double align(tMatrix &);
88        void cleanup();
[9cf98b9bd6]89        bool findCandidate(tMatrix, int &, int &);
[430bd7f7e9]90        double findMinInCol(int, tMatrix, int exr = -1);
[e0fcac5f2c]91        double findMinInRow(int, tMatrix, int exc = -1);
[430bd7f7e9]92        bool hasSubCycles(int, int);
93        void subCol(tMatrix &, int, double);
94        void subRow(tMatrix &, int, double);
[67e53c96d7]95};
96
97#endif // TSPSOLVER_H
Note: See TracBrowser for help on using the repository browser.