Changeset 9cda6e0f5d in tspsg for src


Ignore:
Timestamp:
Apr 25, 2010, 4:36:27 PM (15 years ago)
Author:
Oleksii Serdiuk
Branches:
0.1.3.145-beta1-symbian, 0.1.4.170-beta2-bb10, appveyor, imgbot, master, readme
Children:
ca3d2a30fa
Parents:
345e7b6132
git-author:
Oleksii Serdiuk <contacts@…> (04/25/10 16:36:27)
git-committer:
Oleksii Serdiuk <contacts@…> (06/29/12 19:41:31)
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.
Location:
src
Files:
7 edited

Legend:

Unmodified
Added
Removed

  • src/defaults.h

    r345e7b6132 r9cda6e0f5d  
    6565//////// OUTPUT
    6666
     67//! Default for "Show solution graph"
     68#define DEF_SHOW_GRAPH true
    6769//! Default for "Show solution steps' matrices for every solution step"
    6870#define DEF_SHOW_MATRIX true

  • src/globals.h

    r345e7b6132 r9cda6e0f5d  
    3232#include <QtCore>
    3333#include <QtGui>
    34 #include <limits>
    3534
    3635// Version info
    … …  
    4039// TSPSG Defaults
    4140#include "defaults.h"
     41// TSPSolver
     42#include "tspsolver.h"
    4243#ifdef Q_OS_WIN32
    4344        // Vista/7 Eyecandy
    … …  
    8081#define ZKT_VERSION quint8(1)
    8182
    82 /*!
    83  * \def INFINITY
    84  * \brief This value means infinity :-)
    85  *
    86  *  Some libraries already have \c INFINITY defined.
    87  *  We need to redefine it for the \c INFINITY to always have the same value.
    88  */
    89 #ifdef INFINITY
    90         #undef INFINITY
    91 #endif
    92 #define INFINITY std::numeric_limits<double>::infinity()
    9383//! This string represents infinite value in the table
    9484#define INFSTR "---"

  • src/mainwindow.cpp

    r345e7b6132 r9cda6e0f5d  
    510510        pb->setFormat(tr("Generating header"));
    511511        pd.setLabelText(tr("Generating solution output..."));
    512         pd.setMaximum(n);
     512        pd.setMaximum(solver.getTotalSteps() + 1);
    513513        pd.setValue(0);
    514514
    … …  
    517517
    518518QPainter pic;
    519         pic.begin(&graph);
    520         pic.setRenderHint(QPainter::Antialiasing);
     519        if (settings->value("Output/ShowGraph", DEF_SHOW_GRAPH).toBool()) {
     520                pic.begin(&graph);
     521                pic.setRenderHint(QPainter::Antialiasing);
     522        }
    521523
    522524QTextDocument *doc = solutionText->document();
    … …  
    529531        cur.insertText(tr("Task:"));
    530532        outputMatrix(cur, matrix);
    531         drawNode(pic, 0);
     533        if (settings->value("Output/ShowGraph", DEF_SHOW_GRAPH).toBool())
     534                drawNode(pic, 0);
    532535        cur.insertHtml("<hr>");
    533536        cur.insertBlock(fmt_paragraph);
    … …  
    537540
    538541SStep *step = root;
    539         n = 1;
     542int c = n = 1;
    540543        pb->setFormat(tr("Generating step %v"));
    541         while (n < spinCities->value()) {
     544        while ((step->next != SStep::NoNextStep) && (c < spinCities->value())) {
    542545                if (pd.wasCanceled()) {
    543546                        pd.setLabelText(tr("Cleaning up..."));
    … …  
    553556                pd.setValue(n);
    554557
    555                 if (step->prNode->prNode != NULL || ((step->prNode->prNode == NULL) && (step->plNode->prNode == NULL))) {
    556                         if (n != spinCities->value()) {
    557                                 cur.beginEditBlock();
    558                                 cur.insertBlock(fmt_paragraph);
    559                                 cur.insertText(tr("Step #%1").arg(n++));
    560                                 if (settings->value("Output/ShowMatrix", DEF_SHOW_MATRIX).toBool() && (!settings->value("Output/UseShowMatrixLimit", DEF_USE_SHOW_MATRIX_LIMIT).toBool() || (settings->value("Output/UseShowMatrixLimit", DEF_USE_SHOW_MATRIX_LIMIT).toBool() && (spinCities->value() <= settings->value("Output/ShowMatrixLimit", DEF_SHOW_MATRIX_LIMIT).toInt())))) {
    561                                         outputMatrix(cur, *step);
    562                                 }
    563                                 cur.insertBlock(fmt_paragraph);
    564                                 cur.insertText(tr("Selected candidate for branching: %1.").arg(tr("(%1;%2)").arg(step->candidate.nRow + 1).arg(step->candidate.nCol + 1)), fmt_default);
    565                                 if (!step->alts.empty()) {
    566 SCandidate cand;
    567 QString alts;
    568                                         foreach(cand, step->alts) {
    569                                                 if (!alts.isEmpty())
    570                                                         alts += ", ";
    571                                                 alts += tr("(%1;%2)").arg(cand.nRow + 1).arg(cand.nCol + 1);
    572                                         }
    573                                         cur.insertBlock(fmt_paragraph);
    574                                         cur.insertText(tr("%n alternate candidate(s) for branching: %1.", "", step->alts.count()).arg(alts), fmt_altlist);
    575                                 }
    576                                 cur.insertBlock(fmt_paragraph);
    577                                 cur.insertText(" ", fmt_default);
    578                                 cur.endEditBlock();
     558                cur.beginEditBlock();
     559                cur.insertBlock(fmt_paragraph);
     560                cur.insertText(tr("Step #%1").arg(n));
     561                if (settings->value("Output/ShowMatrix", DEF_SHOW_MATRIX).toBool() && (!settings->value("Output/UseShowMatrixLimit", DEF_USE_SHOW_MATRIX_LIMIT).toBool() || (settings->value("Output/UseShowMatrixLimit", DEF_USE_SHOW_MATRIX_LIMIT).toBool() && (spinCities->value() <= settings->value("Output/ShowMatrixLimit", DEF_SHOW_MATRIX_LIMIT).toInt())))) {
     562                        outputMatrix(cur, *step);
     563                }
     564                cur.insertBlock(fmt_paragraph);
     565                cur.insertText(tr("Selected route %1 %2 part.").arg((step->next == SStep::RightBranch) ? tr("with") : tr("without")).arg(tr("(%1;%2)").arg(step->candidate.nRow + 1).arg(step->candidate.nCol + 1)), fmt_default);
     566                if (!step->alts.empty()) {
     567                        SStep::SCandidate cand;
     568                        QString alts;
     569                        foreach(cand, step->alts) {
     570                                if (!alts.isEmpty())
     571                                        alts += ", ";
     572                                alts += tr("(%1;%2)").arg(cand.nRow + 1).arg(cand.nCol + 1);
    579573                        }
    580                 }
    581                 if (n < spinCities->value()) {
     574                        cur.insertBlock(fmt_paragraph);
     575                        cur.insertText(tr("%n alternate candidate(s) for branching: %1.", "", step->alts.count()).arg(alts), fmt_altlist);
     576                }
     577                cur.insertBlock(fmt_paragraph);
     578                cur.insertText(" ", fmt_default);
     579                cur.endEditBlock();
     580
     581                if (settings->value("Output/ShowGraph", DEF_SHOW_GRAPH).toBool()) {
    582582                        if (step->prNode != NULL)
    583                                 drawNode(pic, n - 1, false, step->prNode);
     583                                drawNode(pic, n, false, step->prNode);
    584584                        if (step->plNode != NULL)
    585                                 drawNode(pic, n - 1, true, step->plNode);
    586                 }
    587                 if (step->prNode->prNode != NULL) {
     585                                drawNode(pic, n, true, step->plNode);
     586                }
     587                n++;
     588
     589                if (step->next == SStep::RightBranch) {
     590                        c++;
    588591                        step = step->prNode;
    589                 } else if (step->plNode->prNode != NULL) {
     592                } else if (step->next == SStep::LeftBranch) {
    590593                        step = step->plNode;
    591594                } else
    … …  
    617620        }
    618621        cur.endEditBlock();
    619         pic.end();
     622
     623        if (settings->value("Output/ShowGraph", DEF_SHOW_GRAPH).toBool()) {
     624                pic.end();
    620625
    621626QImage i(graph.width() + 2, graph.height() + 2, QImage::Format_ARGB32);
    622         i.fill(0);
    623         pic.begin(&i);
    624         pic.drawPicture(1, 1, graph);
    625         pic.end();
    626         doc->addResource(QTextDocument::ImageResource, QUrl("tspsg://graph.pic"), i);
     627                i.fill(0);
     628                pic.begin(&i);
     629                pic.drawPicture(1, 1, graph);
     630                pic.end();
     631                doc->addResource(QTextDocument::ImageResource, QUrl("tspsg://graph.pic"), i);
    627632
    628633QTextImageFormat img;
    629         img.setName("tspsg://graph.pic");
    630 
    631         cur.setPosition(imgpos);
    632         cur.insertImage(img, QTextFrameFormat::FloatRight);
     634                img.setName("tspsg://graph.pic");
     635
     636                cur.setPosition(imgpos);
     637                cur.insertImage(img, QTextFrameFormat::FloatRight);
     638        }
    633639
    634640        if (settings->value("Output/ScrollToEnd", DEF_SCROLL_TO_END).toBool()) {
    … …  
    784790                }
    785791                pic.setBackgroundMode(Qt::OpaqueMode);
    786                 pic.drawText(QRectF(x - r, y - r, r * 2, r * 2), Qt::AlignCenter, isInteger(step->price) ?  QString("\n%1").arg(step->price) : QString("\n%1").arg(step->price, 0, 'f', settings->value("Task/FractionalAccuracy", DEF_FRACTIONAL_ACCURACY).toInt()));
     792                if (step->price != INFINITY) {
     793                        pic.drawText(QRectF(x - r, y - r, r * 2, r * 2), Qt::AlignCenter, isInteger(step->price) ?  QString("\n%1").arg(step->price) : QString("\n%1").arg(step->price, 0, 'f', settings->value("Task/FractionalAccuracy", DEF_FRACTIONAL_ACCURACY).toInt()));
     794                } else {
     795                        pic.drawText(QRectF(x - r, y - r, r * 2, r * 2), Qt::AlignCenter, "\n"INFSTR);
     796                }
    787797                pic.setBackgroundMode(Qt::TransparentMode);
    788798        } else {
    … …  
    790800        }
    791801
    792         if (nstep == 1)
    793                 pic.drawLine(QPointF(r * 2.25, r * (3 * (nstep - 1) + 2)), QPointF(x, y - r));
    794         else
    795                 pic.drawLine(QPointF(r * 3.5, r * (3 * (nstep - 1) + 2)), QPointF(x, y - r));
     802        if (nstep == 1) {
     803                pic.drawLine(QPointF(x, y - r), QPointF(r * 2.25, y - 2 * r));
     804        } else if (nstep > 1) {
     805                pic.drawLine(QPointF(x, y - r), QPointF((step->pNode->next == SStep::RightBranch) ? r * 3.5 : r, y - 2 * r));
     806        }
    796807
    797808}
    … …  
    806817                toggleSolutionActions(false);
    807818
    808                 ev->acceptProposedAction();
     819                ev->setDropAction(Qt::CopyAction);
     820                ev->accept();
    809821        }
    810822}
    … …  
    9921004                                cur.insertText(isInteger(step.matrix.at(r).at(c)) ? QString("%1").arg(step.matrix.at(r).at(c)) : QString("%1").arg(step.matrix.at(r).at(c), 0, 'f', settings->value("Task/FractionalAccuracy", DEF_FRACTIONAL_ACCURACY).toInt()), fmt_selected);
    9931005                        else {
    994 SCandidate cand;
     1006SStep::SCandidate cand;
    9951007                                cand.nRow = r;
    9961008                                cand.nCol = c;

  • src/mainwindow.h

    r345e7b6132 r9cda6e0f5d  
    3434#include "settingsdialog.h"
    3535
    36 #include "tspsolver.h"
    3736#include "tspmodel.h"
     37
     38using namespace TSPSolver;
    3839
    3940/*!

  • src/settingsdialog.cpp

    r345e7b6132 r9cda6e0f5d  
    194194
    195195        settings->beginGroup("Output");
     196        cbShowGraph->setChecked(settings->value("ShowGraph", DEF_SHOW_GRAPH).toBool());
    196197        cbShowMatrix->setChecked(settings->value("ShowMatrix", DEF_SHOW_MATRIX).toBool());
    197198        cbCitiesLimit->setEnabled(cbShowMatrix->isChecked());
    … …  
    280281
    281282        settings->beginGroup("Output");
     283        settings->setValue("ShowGraph", cbShowGraph->isChecked());
    282284        settings->setValue("ShowMatrix", cbShowMatrix->isChecked());
    283285        settings->setValue("UseShowMatrixLimit", cbShowMatrix->isChecked() && cbCitiesLimit->isChecked());

  • src/tspsolver.cpp

    r345e7b6132 r9cda6e0f5d  
    2727#define MAX_DOUBLE std::numeric_limits<double>::max()
    2828
     29namespace TSPSolver {
     30
    2931/*!
    3032 * \brief Returns CTSPSolver's version ID.
    … …  
    4143 */
    4244CTSPSolver::CTSPSolver(QObject *parent)
    43         : QObject(parent), nCities(0), root(NULL) {}
     45        : QObject(parent), nCities(0), total(0), root(NULL) {}
    4446
    4547/*!
    4648 * \brief Cleans up the object and frees up memory used by the solution tree.
    47  * \param processEvents If set to \c true then \link QCoreApplication::processEvents() QApplication::processEvents(QEventLoop::ExcludeUserInputEvents)\endlink will be called from time to time while cleaning up.
     49 * \param processEvents If set to \c true then \link QCoreApplication::processEvents() QCoreApplication::processEvents(QEventLoop::ExcludeUserInputEvents)\endlink will be called from time to time while cleaning up.
    4850 * \warning After call to this function a solution tree returned by the solve() function is no longer valid.
    4951 * \note It is not required to call this function manually. This function is always called by solve() at the beginning of the solution process.
    … …  
    5355void CTSPSolver::cleanup(bool processEvents)
    5456{
     57#ifdef QAPPLICATION_H
    5558        if (!processEvents)
    5659                QApplication::setOverrideCursor(QCursor(Qt::WaitCursor));
     60#endif
    5761        route.clear();
    5862        mayNotBeOptimal = false;
    5963        if (root != NULL)
    6064                deleteTree(root, processEvents);
     65#ifdef QAPPLICATION_H
    6166        if (!processEvents)
    6267                QApplication::restoreOverrideCursor();
     68#endif
    6369}
    6470
    … …  
    8490
    8591/*!
     92 * \brief Returns a total number of steps in the current solution.
     93 * \return A total number of steps or \c 0 if no solution.
     94 * \note This is not always the same as the number of cities.
     95 */
     96int CTSPSolver::getTotalSteps() const
     97{
     98        return total;
     99}
     100
     101/*!
    86102 * \brief Indicates whether or not the solution is definitely optimal.
    87103 * \return \c true if the solution is definitely optimal, otherwise \c false.
    … …  
    105121SStep *CTSPSolver::solve(int numCities, const TMatrix &task)
    106122{
    107         if (numCities <= 1)
     123        if (numCities < 3)
    108124                return NULL;
    109125
    … …  
    131147bool firstStep = true;
    132148double check = INFINITY;
    133         while (this->route.size() < nCities) {
     149        total = 0;
     150        while (route.size() < nCities) {
    134151                step->alts = findCandidate(step->matrix,nRow,nCol);
    135152
    … …  
    188205                if (right->price <= left->price) {
    189206                        // Route with (nRow,nCol) path is cheaper
     207                        step->next = SStep::RightBranch;
    190208                        step = right;
    191                         this->route[nRow] = nCol;
    192                         emit routePartFound(this->route.size());
     209                        route[nRow] = nCol;
     210                        emit routePartFound(route.size());
    193211                        if (firstStep) {
    194212                                check = left->price;
    … …  
    197215                } else {
    198216                        // Route without (nRow,nCol) path is cheaper
     217                        step->next = SStep::LeftBranch;
    199218                        step = left;
    200                         qApp->processEvents();
     219                        QCoreApplication::processEvents();
    201220                        if (firstStep) {
    202221                                check = right->price;
    … …  
    204223                        }
    205224                }
    206         }
    207 
    208         route = this->route;
     225                total++;
     226        }
     227
    209228        mayNotBeOptimal = (check < step->price);
    210229
    … …  
    259278                }
    260279        }
    261         return r;
     280        return (r != MAX_DOUBLE) ? r : INFINITY;
    262281}
    263282
    … …  
    270289        forever {
    271290                if (processEvents)
    272                         QApplication::processEvents(QEventLoop::ExcludeUserInputEvents);
     291                        QCoreApplication::processEvents(QEventLoop::ExcludeUserInputEvents);
    273292                if (step->plNode != NULL) {
    274293                        // We have left child node - going inside it
    … …  
    282301                        continue;
    283302                } else {
    284                         // We have no child nodes. Deleting current one.
     303                        // We have no child nodes. Deleting the current one.
    285304                        parent = step->pNode;
    286305                        delete step;
    … …  
    305324}
    306325
    307 QList<SCandidate> CTSPSolver::findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const
     326QList<SStep::SCandidate> CTSPSolver::findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const
    308327{
    309328        nRow = -1;
    310329        nCol = -1;
    311 QList<SCandidate> alts;
    312 SCandidate cand;
     330QList<SStep::SCandidate> alts;
     331SStep::SCandidate cand;
    313332double h = -1;
    314333double sum;
    315334        for (int r = 0; r < nCities; r++)
    316335                for (int c = 0; c < nCities; c++)
    317 //                      if ((matrix.at(r).at(c) == 0) && !forbidden.values(r).contains(c)) {
    318336                        if (matrix.at(r).at(c) == 0) {
    319337                                sum = findMinInRow(r,matrix,c) + findMinInCol(c,matrix,r);
    … …  
    356374                return false;
    357375int i = nCol;
    358         while (true) {
    359                 if ((i = route[i]) == nRow)
     376        forever {
     377                if ((i = route.value(i)) == nRow)
    360378                        return true;
    361379                if (!route.contains(i))
    … …  
    387405}
    388406
     407}
     408
    389409#ifdef DEBUG
    390 QDebug operator<<(QDebug dbg, const TMatrix &matrix)
     410QDebug operator<<(QDebug dbg, const TSPSolver::TMatrix &matrix)
    391411{
    392412        for (int r = 0; r < matrix.count(); r++) {
    … …  
    398418}
    399419
    400 QDebug operator<<(QDebug dbg, const SCandidate &cand)
     420QDebug operator<<(QDebug dbg, const TSPSolver::SStep::SCandidate &cand)
    401421{
    402422        dbg.nospace() << "(" << cand.nRow << ";" << cand.nCol << ")";

  • src/tspsolver.h

    r345e7b6132 r9cda6e0f5d  
    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.