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

Last change on this file since 64 was 64, checked in by laleppa, 15 years ago

Started documenting the source code in doxygen format.

  • Property svn:keywords set to Id URL
File size: 2.2 KB
Line 
1/*
2 *  TSPSG: TSP Solver and Generator
3 *  Copyright (C) 2007-2009 Lёppa <contacts[at]oleksii[dot]name>
4 *
5 *  $Id: tspsolver.h 64 2009-10-20 09:40:16Z laleppa $
6 *  $URL: https://tspsg.svn.sourceforge.net/svnroot/tspsg/trunk/src/tspsolver.h $
7 *
8 *  This file is part of TSPSG.
9 *
10 *  TSPSG is free software: you can redistribute it and/or modify
11 *  it under the terms of the GNU General Public License as published by
12 *  the Free Software Foundation, either version 3 of the License, or
13 *  (at your option) any later version.
14 *
15 *  TSPSG is distributed in the hope that it will be useful,
16 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
17 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
18 *  GNU General Public License for more details.
19 *
20 *  You should have received a copy of the GNU General Public License
21 *  along with TSPSG.  If not, see <http://www.gnu.org/licenses/>.
22 */
23
24#ifndef TSPSOLVER_H
25#define TSPSOLVER_H
26
27#include "globals.h"
28
29#include "tspmodel.h"
30
31typedef QList<QList<double> > tMatrix;
32
33// This structure represents one step of solving
34// The tree of such elements will represent the solving process
35struct sStep {
36        tMatrix matrix; // Steps's matrix
37        double price; // Price of travel to this step
38        struct {int nRow; int nCol;} candidate; // Candiadate for branching in current matrix
39        bool alts; // This matrix has alternative candidates
40        sStep *plNode, *prNode; // Pointers to left and right branch steps
41        sStep() { price = candidate.nRow = candidate.nCol = -1; alts = false; plNode = prNode = NULL; } // Default values
42};
43
44// TSP Solver class
45class CTSPSolver
46{
47        Q_DECLARE_TR_FUNCTIONS(CTSPSolver)
48
49public:
50        CTSPSolver();
51        QString getSortedPath() const;
52        bool isOptimal() const;
53        sStep *solve(int, tMatrix, QWidget *parent = 0);
54        static QString getVersionId();
55
56private:
57        bool mayNotBeOptimal;
58        int nCities;
59        sStep *root;
60        QHash<int,int> route;
61//      QHash<int,int> forbidden;
62        double align(tMatrix &);
63        void cleanup();
64        bool findCandidate(tMatrix, int &, int &);
65        double findMinInRow(int, tMatrix, int exc = -1);
66        double findMinInCol(int, tMatrix, int exr = -1);
67        bool hasSubCycles(int, int);
68        void subCol(tMatrix &, int, double);
69        void subRow(tMatrix &, int, double);
70};
71
72#endif // TSPSOLVER_H
Note: See TracBrowser for help on using the repository browser.