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

Last change on this file since 63 was 63, checked in by laleppa, 15 years ago
  • New TSPSG icon. Found some nice image among heap of images on my PC and thought it would be a nice icon for TSPSG. Original source: Internet (read, unknown).
  • Some insignificant code changes.
  • Property svn:keywords set to Id URL
File size: 2.1 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 63 2009-09-09 22:14:22Z 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
29typedef QList<QList<double> > tMatrix;
30
31// This structure represents one step of solving
32// The tree of such elements will represent the solving process
33struct sStep {
34        tMatrix matrix; // Steps's matrix
35        double price; // Price of travel to this step
36        struct {int nRow; int nCol;} candidate; // Candiadate for branching in current matrix
37        bool alts; // This matrix has alternative candidates
38        sStep *plNode, *prNode; // Pointers to left and right branch steps
39        sStep() { price = candidate.nRow = candidate.nCol = -1; alts = false; plNode = prNode = NULL; } // Default values
40};
41
42// TSP Solver class
43class CTSPSolver
44{
45        Q_DECLARE_TR_FUNCTIONS(CTSPSolver)
46
47public:
48        CTSPSolver();
49        QString getSortedPath() const;
50        bool isOptimal() const;
51        sStep *solve(int, tMatrix, QWidget *parent = 0);
52        static QString getVersionId();
53
54private:
55        bool mayNotBeOptimal;
56        int nCities;
57        sStep *root;
58        QHash<int,int> route;
59//      QHash<int,int> forbidden;
60        double align(tMatrix &);
61        void cleanup();
62        bool findCandidate(tMatrix, int &, int &);
63        double findMinInRow(int, tMatrix, int exc = -1);
64        double findMinInCol(int, tMatrix, int exr = -1);
65        bool hasSubCycles(int, int);
66        void subCol(tMatrix &, int, double);
67        void subRow(tMatrix &, int, double);
68};
69
70#endif // TSPSOLVER_H
Note: See TracBrowser for help on using the repository browser.