Changeset 107 in tspsg-svn for trunk/src/tspsolver.h


Ignore:
Timestamp:
Apr 25, 2010, 4:36:27 PM (15 years ago)
Author:
laleppa
Message:

+ Added SStep::next that indicates what branch was selected for the next step.
+ Added "Show solution graph" option.
+ New CTSPSolver::getTotalSteps() method that returns a total number of steps in the current solution.

  • Moved SCandidate declaration into SStep declaration.
  • Moved everything in tspsolver.h and tspsolver.cpp into TSPSolver namespace.
  • Force CopyAction? on file drop or it will be deleted after dropping in Windows if MoveAction? was selected.
File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/tspsolver.h

    r99 r107  
    66 *  $URL$
    77 *
    8  * \brief Defines #TMatrix typedef, SCandidate and SStep structs and CTSPSolver class.
     8 * \brief Defines TSPSolver namespace and everything needed for solving TSP tasks.
    99 *
    1010 *  <b>TSPSG: TSP Solver and Generator</b>
    … …  
    2929#define TSPSOLVER_H
    3030
    31 #include "globals.h"
    32 
    33 #include "tspmodel.h"
    34 
    35 //! A matrix of city-to-city travel costs.
    36 typedef QList<QList<double> > TMatrix;
     31#include <QtCore>
     32#include <limits>
    3733
    3834/*!
    39  * \brief A structure that represents a candidate for branching.
     35 * \def INFINITY
     36 * \brief This value means infinity :-)
     37 *
     38 *  Some libraries already have \c INFINITY defined.
     39 *  We need to redefine it for the \c INFINITY to always have the same value.
    4040 */
    41 struct SCandidate {
    42         int nRow; //!< A zero-based row number of the candidate
    43         int nCol; //!< A zero-based column number of the candidate
     41#ifdef INFINITY
     42        #undef INFINITY
     43#endif
     44#define INFINITY std::numeric_limits<double>::infinity()
    4445
    45         //! Assigns default values
    46         SCandidate() {
    47                 nCol = nRow = -1;
    48         }
    49         //! An operator == implementation
    50         bool operator ==(const SCandidate &cand) const {
    51                 return ((cand.nRow == nRow) && (cand.nCol == nCol));
    52         }
    53 };
     46/*!
     47 * \brief A TSP Solver namespace.
     48 *
     49 *  This namespace contains all the stuff required for solving TSP tasks.
     50 */
     51namespace TSPSolver {
     52
     53//! A matrix of city-to-city travel costs
     54typedef QList<QList<double> > TMatrix;
    5455
    5556/*!
    … …  
    5960 */
    6061struct SStep {
     62        //! A structure that represents a candidate for branching
     63        struct SCandidate {
     64                int nRow; //!< A zero-based row number of the candidate
     65                int nCol; //!< A zero-based column number of the candidate
     66
     67                //! Assigns default values
     68                SCandidate() {
     69                        nCol = nRow = -1;
     70                }
     71                //! An operator == implementation
     72                bool operator ==(const SCandidate &cand) const {
     73                        return ((cand.nRow == nRow) && (cand.nCol == nCol));
     74                }
     75        };
     76
     77        //! An enum that describes possible selection of the next step
     78        enum NextStep {
     79                NoNextStep, //!< No next step (end of solution)
     80                LeftBranch, //!< Left branch was selected for the next step
     81                RightBranch //!< Right branch was selected for the next step
     82        };
     83
    6184        TMatrix matrix; //!< This step's matrix
    6285        double price; //!< The price of travel to this step
    63         SCandidate candidate; //!< A candiadate for branching in the current matrix
     86
     87        SCandidate candidate; //!< A candiadate for branching in the current step
    6488        QList<SCandidate> alts; //!< A list of alternative branching candidates
    6589        SStep *pNode; //!< Pointer to the parent step
    6690        SStep *plNode; //!< Pointer to the left branch step
    6791        SStep *prNode; //!< Pointer to the right branch step
     92        NextStep next; //!< Indicates what branch was selected for the next step
    6893
    6994        //! Assigns default values
    … …  
    7196                price = -1;
    7297                pNode = plNode = prNode = NULL;
     98                next = NoNextStep;
    7399        }
    74100};
    … …  
    88114        void cleanup(bool processEvents = false);
    89115        QString getSortedPath() const;
     116        int getTotalSteps() const;
    90117        bool isOptimal() const;
    91118        SStep *solve(int numCities, const TMatrix &task);
    … …  
    105132private:
    106133        bool mayNotBeOptimal, canceled;
    107         int nCities;
     134        int nCities, total;
    108135        SStep *root;
    109136        QHash<int,int> route;
    … …  
    113140        void deleteTree(SStep *&root, bool processEvents = false);
    114141        void denormalize(TMatrix &matrix) const;
    115         QList<SCandidate> findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const;
     142        QList<SStep::SCandidate> findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const;
    116143        double findMinInCol(int nCol, const TMatrix &matrix, int exr = -1) const;
    117144        double findMinInRow(int nRow, const TMatrix &matrix, int exc = -1) const;
     145        void finishRoute();
    118146        bool hasSubCycles(int nRow, int nCol) const;
    119147        void normalize(TMatrix &matrix) const;
    … …  
    122150};
    123151
     152}
     153
    124154#ifdef DEBUG
    125 QDebug operator<<(QDebug dbg, const TMatrix &matrix);
    126 QDebug operator<<(QDebug dbg, const SCandidate &candidate);
     155QDebug operator<<(QDebug dbg, const TSPSolver::TMatrix &matrix);
     156QDebug operator<<(QDebug dbg, const TSPSolver::SStep::SCandidate &candidate);
    127157#endif // DEBUG
    128158
Note: See TracChangeset for help on using the changeset viewer.