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

/*!

 * \file tspsolver.h

 * \author Copyright &copy; 2007-2011 Lёppa <contacts[at]oleksii[dot]name>

 *

 *  $Id: tspsolver.h 154 2011-03-13 20:23:53Z laleppa $

 *  $URL: https://tspsg.svn.sourceforge.net/svnroot/tspsg/trunk/src/tspsolver.h $

 *

 * \brief Defines TSPSolver namespace and everything needed for solving TSP tasks.

 *

 *  <b>TSPSG: TSP Solver and Generator</b>

 *

 *  This file is part of TSPSG.

 *

 *  TSPSG is free software: you can redistribute it and/or modify

 *  it under the terms of the GNU General Public License as published by

 *  the Free Software Foundation, either version 3 of the License, or

 *  (at your option) any later version.

 *

 *  TSPSG is distributed in the hope that it will be useful,

 *  but WITHOUT ANY WARRANTY; without even the implied warranty of

 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

 *  GNU General Public License for more details.

 *

 *  You should have received a copy of the GNU General Public License

 *  along with TSPSG.  If not, see <http://www.gnu.org/licenses/>.

 */



#ifndef TSPSOLVER_H

#define TSPSOLVER_H



#include <QtCore>

#include <limits>



/*!

 * \def INFINITY

 * \brief This value means infinity :-)

 *

 *  Define \c INFINITY if it's not already defined.

 */

#ifndef INFINITY

#   define INFINITY std::numeric_limits<double>::infinity()

#endif



/*!

 * \brief A TSP Solver namespace.

 *

 *  This namespace contains all the stuff required for solving TSP tasks.

 */

namespace TSPSolver {



//! A matrix of city-to-city travel costs

typedef QList<QList<double> > TMatrix;



/*!

 * \brief This structure represents one step of solving.

 *

 *  A tree of such elements will represent the solving process.

 */

struct SStep {

    //! A structure that represents a candidate for branching

    struct SCandidate {

        int nRow; //!< A zero-based row number of the candidate

        int nCol; //!< A zero-based column number of the candidate



        //! Assigns default values

        SCandidate() {

            nCol = nRow = -1;

        }

        //! An operator == implementation

        bool operator ==(const SCandidate &cand) const {

            return ((cand.nRow == nRow) && (cand.nCol == nCol));

        }

    };



    //! An enum that describes possible selection of the next step

    enum NextStep {

        NoNextStep, //!< No next step (end of solution)

        LeftBranch, //!< Left branch was selected for the next step

        RightBranch //!< Right branch was selected for the next step

    };



    TMatrix matrix; //!< This step's matrix

    double price; //!< The price of travel to this step



    SCandidate candidate; //!< A candiadate for branching in the current step

    QList<SCandidate> alts; //!< A list of alternative branching candidates

    SStep *pNode; //!< Pointer to the parent step

    SStep *plNode; //!< Pointer to the left branch step

    SStep *prNode; //!< Pointer to the right branch step

    NextStep next; //!< Indicates what branch was selected for the next step



    //! Assigns default values

    SStep() {

        price = -1;

        pNode = plNode = prNode = NULL;

        next = NoNextStep;

    }

};



/*!

 * \brief This class solves Travelling Salesman Problem task.

 * \author Copyright &copy; 2007-2011 Lёppa <contacts[at]oleksii[dot]name>

 */

class CTSPSolver: public QObject

{

    Q_OBJECT



public:

    static QString getVersionId();



    CTSPSolver(QObject *parent = NULL);

    void cleanup(bool processEvents = false);

    QString getSortedPath(const QString &city, const QString &separator = QString(" -> ")) const;

    int getTotalSteps() const;

    bool isOptimal() const;

    void setCleanupOnCancel(bool enable = true);

    SStep *solve(int numCities, const TMatrix &task);

    bool wasCanceled() const;

    ~CTSPSolver();



public slots:

    void cancel();



signals:

    /*!

     * \brief This signal is emitted once every time a part of the route is found.

     * \param n Indicates the number of the route parts found.

     */

    void routePartFound(int n);



private:

    bool mayNotBeOptimal, canceled, cc;

    int nCities, total;

    SStep *root;

    QHash<int,int> route;

    mutable QMutex mutex;



    double align(TMatrix &matrix);

    void deleteTree(SStep *&root, bool processEvents = false);

    void denormalize(TMatrix &matrix) const;

    QList<SStep::SCandidate> findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const;

    double findMinInCol(int nCol, const TMatrix &matrix, int exr = -1) const;

    double findMinInRow(int nRow, const TMatrix &matrix, int exc = -1) const;

    void finishRoute();

    bool hasSubCycles(int nRow, int nCol) const;

    void normalize(TMatrix &matrix) const;

    void subCol(TMatrix &matrix, int nCol, double val);

    void subRow(TMatrix &matrix, int nRow, double val);

};



}



#ifdef DEBUG

QDebug operator<<(QDebug dbg, const TSPSolver::TMatrix &matrix);

QDebug operator<<(QDebug dbg, const TSPSolver::SStep::SCandidate &candidate);

#endif // DEBUG



#endif // TSPSOLVER_H