Changeset 107 in tspsg-svn for trunk/src

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.

Location:

trunk/src

Files:

• defaults.h (modified) (1 diff)
• globals.h (modified) (3 diffs)
• mainwindow.cpp (modified) (10 diffs)
• mainwindow.h (modified) (1 diff)
• settingsdialog.cpp (modified) (2 diffs)
• tspsolver.cpp (modified) (16 diffs)
• tspsolver.h (modified) (8 diffs)

trunk/src/defaults.h

@@ -65 +65 @@
 //////// OUTPUT
 
+//! Default for "Show solution graph"
+#define DEF_SHOW_GRAPH true
 //! Default for "Show solution steps' matrices for every solution step"
 #define DEF_SHOW_MATRIX true

trunk/src/globals.h

@@ -32 +32 @@
 #include <QtCore>
 #include <QtGui>
-#include <limits>
 
 // Version info
@@ -40 +39 @@
 // TSPSG Defaults
 #include "defaults.h"
+// TSPSolver
+#include "tspsolver.h"
 #ifdef Q_OS_WIN32
         // Vista/7 Eyecandy
@@ -80 +81 @@
 #define ZKT_VERSION quint8(1)
 
-/*!
- * \def INFINITY
- * \brief This value means infinity :-)
- *
- *  Some libraries already have \c INFINITY defined.
- *  We need to redefine it for the \c INFINITY to always have the same value.
- */
-#ifdef INFINITY
-        #undef INFINITY
-#endif
-#define INFINITY std::numeric_limits<double>::infinity()
 //! This string represents infinite value in the table
 #define INFSTR "---"

trunk/src/mainwindow.cpp

@@ -510 +510 @@
         pb->setFormat(tr("Generating header"));
         pd.setLabelText(tr("Generating solution output..."));
-        pd.setMaximum(n);
+        pd.setMaximum(solver.getTotalSteps() + 1);
         pd.setValue(0);
 
@@ -517 +517 @@
 
 QPainter pic;
-        pic.begin(&graph);
-        pic.setRenderHint(QPainter::Antialiasing);
+        if (settings->value("Output/ShowGraph", DEF_SHOW_GRAPH).toBool()) {
+                pic.begin(&graph);
+                pic.setRenderHint(QPainter::Antialiasing);
+        }
 
 QTextDocument *doc = solutionText->document();
@@ -529 +531 @@
         cur.insertText(tr("Task:"));
         outputMatrix(cur, matrix);
-        drawNode(pic, 0);
+        if (settings->value("Output/ShowGraph", DEF_SHOW_GRAPH).toBool())
+                drawNode(pic, 0);
         cur.insertHtml("<hr>");
         cur.insertBlock(fmt_paragraph);
@@ -537 +540 @@
 
 SStep *step = root;
-        n = 1;
+int c = n = 1;
         pb->setFormat(tr("Generating step %v"));
-        while (n < spinCities->value()) {
+        while ((step->next != SStep::NoNextStep) && (c < spinCities->value())) {
                 if (pd.wasCanceled()) {
                         pd.setLabelText(tr("Cleaning up..."));
@@ -553 +556 @@
                 pd.setValue(n);
 
-                if (step->prNode->prNode != NULL || ((step->prNode->prNode == NULL) && (step->plNode->prNode == NULL))) {
-                        if (n != spinCities->value()) {
-                                cur.beginEditBlock();
-                                cur.insertBlock(fmt_paragraph);
-                                cur.insertText(tr("Step #%1").arg(n++));
-                                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())))) {
-                                        outputMatrix(cur, *step);
-                                }
-                                cur.insertBlock(fmt_paragraph);
-                                cur.insertText(tr("Selected candidate for branching: %1.").arg(tr("(%1;%2)").arg(step->candidate.nRow + 1).arg(step->candidate.nCol + 1)), fmt_default);
-                                if (!step->alts.empty()) {
-SCandidate cand;
-QString alts;
-                                        foreach(cand, step->alts) {
-                                                if (!alts.isEmpty())
-                                                        alts += ", ";
-                                                alts += tr("(%1;%2)").arg(cand.nRow + 1).arg(cand.nCol + 1);
-                                        }
-                                        cur.insertBlock(fmt_paragraph);
-                                        cur.insertText(tr("%n alternate candidate(s) for branching: %1.", "", step->alts.count()).arg(alts), fmt_altlist);
-                                }
-                                cur.insertBlock(fmt_paragraph);
-                                cur.insertText(" ", fmt_default);
-                                cur.endEditBlock();
+                cur.beginEditBlock();
+                cur.insertBlock(fmt_paragraph);
+                cur.insertText(tr("Step #%1").arg(n));
+                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())))) {
+                        outputMatrix(cur, *step);
+                }
+                cur.insertBlock(fmt_paragraph);
+                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);
+                if (!step->alts.empty()) {
+                        SStep::SCandidate cand;
+                        QString alts;
+                        foreach(cand, step->alts) {
+                                if (!alts.isEmpty())
+                                        alts += ", ";
+                                alts += tr("(%1;%2)").arg(cand.nRow + 1).arg(cand.nCol + 1);
                         }
-                }
-                if (n < spinCities->value()) {
+                        cur.insertBlock(fmt_paragraph);
+                        cur.insertText(tr("%n alternate candidate(s) for branching: %1.", "", step->alts.count()).arg(alts), fmt_altlist);
+                }
+                cur.insertBlock(fmt_paragraph);
+                cur.insertText(" ", fmt_default);
+                cur.endEditBlock();
+
+                if (settings->value("Output/ShowGraph", DEF_SHOW_GRAPH).toBool()) {
                         if (step->prNode != NULL)
-                                drawNode(pic, n - 1, false, step->prNode);
+                                drawNode(pic, n, false, step->prNode);
                         if (step->plNode != NULL)
-                                drawNode(pic, n - 1, true, step->plNode);
-                }
-                if (step->prNode->prNode != NULL) {
+                                drawNode(pic, n, true, step->plNode);
+                }
+                n++;
+
+                if (step->next == SStep::RightBranch) {
+                        c++;
                         step = step->prNode;
-                } else if (step->plNode->prNode != NULL) {
+                } else if (step->next == SStep::LeftBranch) {
                         step = step->plNode;
                 } else
@@ -617 +620 @@
         }
         cur.endEditBlock();
-        pic.end();
+
+        if (settings->value("Output/ShowGraph", DEF_SHOW_GRAPH).toBool()) {
+                pic.end();
 
 QImage i(graph.width() + 2, graph.height() + 2, QImage::Format_ARGB32);
-        i.fill(0);
-        pic.begin(&i);
-        pic.drawPicture(1, 1, graph);
-        pic.end();
-        doc->addResource(QTextDocument::ImageResource, QUrl("tspsg://graph.pic"), i);
+                i.fill(0);
+                pic.begin(&i);
+                pic.drawPicture(1, 1, graph);
+                pic.end();
+                doc->addResource(QTextDocument::ImageResource, QUrl("tspsg://graph.pic"), i);
 
 QTextImageFormat img;
-        img.setName("tspsg://graph.pic");
-
-        cur.setPosition(imgpos);
-        cur.insertImage(img, QTextFrameFormat::FloatRight);
+                img.setName("tspsg://graph.pic");
+
+                cur.setPosition(imgpos);
+                cur.insertImage(img, QTextFrameFormat::FloatRight);
+        }
 
         if (settings->value("Output/ScrollToEnd", DEF_SCROLL_TO_END).toBool()) {
@@ -784 +790 @@
                 }
                 pic.setBackgroundMode(Qt::OpaqueMode);
-                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()));
+                if (step->price != INFINITY) {
+                        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()));
+                } else {
+                        pic.drawText(QRectF(x - r, y - r, r * 2, r * 2), Qt::AlignCenter, "\n"INFSTR);
+                }
                 pic.setBackgroundMode(Qt::TransparentMode);
         } else {
@@ -790 +800 @@
         }
 
-        if (nstep == 1)
-                pic.drawLine(QPointF(r * 2.25, r * (3 * (nstep - 1) + 2)), QPointF(x, y - r));
-        else
-                pic.drawLine(QPointF(r * 3.5, r * (3 * (nstep - 1) + 2)), QPointF(x, y - r));
+        if (nstep == 1) {
+                pic.drawLine(QPointF(x, y - r), QPointF(r * 2.25, y - 2 * r));
+        } else if (nstep > 1) {
+                pic.drawLine(QPointF(x, y - r), QPointF((step->pNode->next == SStep::RightBranch) ? r * 3.5 : r, y - 2 * r));
+        }
 
 }
@@ -806 +817 @@
                 toggleSolutionActions(false);
 
-                ev->acceptProposedAction();
+                ev->setDropAction(Qt::CopyAction);
+                ev->accept();
         }
 }
@@ -992 +1004 @@
                                 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);
                         else {
-SCandidate cand;
+SStep::SCandidate cand;
                                 cand.nRow = r;
                                 cand.nCol = c;

trunk/src/mainwindow.h

@@ -34 +34 @@
 #include "settingsdialog.h"
 
-#include "tspsolver.h"
 #include "tspmodel.h"
+
+using namespace TSPSolver;
 
 /*!

trunk/src/settingsdialog.cpp

@@ -194 +194 @@
 
         settings->beginGroup("Output");
+        cbShowGraph->setChecked(settings->value("ShowGraph", DEF_SHOW_GRAPH).toBool());
         cbShowMatrix->setChecked(settings->value("ShowMatrix", DEF_SHOW_MATRIX).toBool());
         cbCitiesLimit->setEnabled(cbShowMatrix->isChecked());
@@ -280 +281 @@
 
         settings->beginGroup("Output");
+        settings->setValue("ShowGraph", cbShowGraph->isChecked());
         settings->setValue("ShowMatrix", cbShowMatrix->isChecked());
         settings->setValue("UseShowMatrixLimit", cbShowMatrix->isChecked() && cbCitiesLimit->isChecked());

trunk/src/tspsolver.cpp

@@ -27 +27 @@
 #define MAX_DOUBLE std::numeric_limits<double>::max()
 
+namespace TSPSolver {
+
 /*!
  * \brief Returns CTSPSolver's version ID.
@@ -41 +43 @@
  */
 CTSPSolver::CTSPSolver(QObject *parent)
-        : QObject(parent), nCities(0), root(NULL) {}
+        : QObject(parent), nCities(0), total(0), root(NULL) {}
 
 /*!
  * \brief Cleans up the object and frees up memory used by the solution tree.
- * \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.
+ * \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.
  * \warning After call to this function a solution tree returned by the solve() function is no longer valid.
  * \note It is not required to call this function manually. This function is always called by solve() at the beginning of the solution process.
@@ -53 +55 @@
 void CTSPSolver::cleanup(bool processEvents)
 {
+#ifdef QAPPLICATION_H
         if (!processEvents)
                 QApplication::setOverrideCursor(QCursor(Qt::WaitCursor));
+#endif
         route.clear();
         mayNotBeOptimal = false;
         if (root != NULL)
                 deleteTree(root, processEvents);
+#ifdef QAPPLICATION_H
         if (!processEvents)
                 QApplication::restoreOverrideCursor();
+#endif
 }
 
@@ -84 +90 @@
 
 /*!
+ * \brief Returns a total number of steps in the current solution.
+ * \return A total number of steps or \c 0 if no solution.
+ * \note This is not always the same as the number of cities.
+ */
+int CTSPSolver::getTotalSteps() const
+{
+        return total;
+}
+
+/*!
  * \brief Indicates whether or not the solution is definitely optimal.
  * \return \c true if the solution is definitely optimal, otherwise \c false.
@@ -105 +121 @@
 SStep *CTSPSolver::solve(int numCities, const TMatrix &task)
 {
-        if (numCities <= 1)
+        if (numCities < 3)
                 return NULL;
 
@@ -131 +147 @@
 bool firstStep = true;
 double check = INFINITY;
-        while (this->route.size() < nCities) {
+        total = 0;
+        while (route.size() < nCities) {
                 step->alts = findCandidate(step->matrix,nRow,nCol);
 
@@ -188 +205 @@
                 if (right->price <= left->price) {
                         // Route with (nRow,nCol) path is cheaper
+                        step->next = SStep::RightBranch;
                         step = right;
-                        this->route[nRow] = nCol;
-                        emit routePartFound(this->route.size());
+                        route[nRow] = nCol;
+                        emit routePartFound(route.size());
                         if (firstStep) {
                                 check = left->price;
@@ -197 +215 @@
                 } else {
                         // Route without (nRow,nCol) path is cheaper
+                        step->next = SStep::LeftBranch;
                         step = left;
-                        qApp->processEvents();
+                        QCoreApplication::processEvents();
                         if (firstStep) {
                                 check = right->price;
@@ -204 +223 @@
                         }
                 }
-        }
-
-        route = this->route;
+                total++;
+        }
+
         mayNotBeOptimal = (check < step->price);
 
@@ -259 +278 @@
                 }
         }
-        return r;
+        return (r != MAX_DOUBLE) ? r : INFINITY;
 }
 
@@ -270 +289 @@
         forever {
                 if (processEvents)
-                        QApplication::processEvents(QEventLoop::ExcludeUserInputEvents);
+                        QCoreApplication::processEvents(QEventLoop::ExcludeUserInputEvents);
                 if (step->plNode != NULL) {
                         // We have left child node - going inside it
@@ -282 +301 @@
                         continue;
                 } else {
-                        // We have no child nodes. Deleting current one.
+                        // We have no child nodes. Deleting the current one.
                         parent = step->pNode;
                         delete step;
@@ -305 +324 @@
 }
 
-QList<SCandidate> CTSPSolver::findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const
+QList<SStep::SCandidate> CTSPSolver::findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const
 {
         nRow = -1;
         nCol = -1;
-QList<SCandidate> alts;
-SCandidate cand;
+QList<SStep::SCandidate> alts;
+SStep::SCandidate cand;
 double h = -1;
 double sum;
         for (int r = 0; r < nCities; r++)
                 for (int c = 0; c < nCities; c++)
-//                      if ((matrix.at(r).at(c) == 0) && !forbidden.values(r).contains(c)) {
                         if (matrix.at(r).at(c) == 0) {
                                 sum = findMinInRow(r,matrix,c) + findMinInCol(c,matrix,r);
@@ -356 +374 @@
                 return false;
 int i = nCol;
-        while (true) {
-                if ((i = route[i]) == nRow)
+        forever {
+                if ((i = route.value(i)) == nRow)
                         return true;
                 if (!route.contains(i))
@@ -387 +405 @@
 }
 
+}
+
 #ifdef DEBUG
-QDebug operator<<(QDebug dbg, const TMatrix &matrix)
+QDebug operator<<(QDebug dbg, const TSPSolver::TMatrix &matrix)
 {
         for (int r = 0; r < matrix.count(); r++) {
@@ -398 +418 @@
 }
 
-QDebug operator<<(QDebug dbg, const SCandidate &cand)
+QDebug operator<<(QDebug dbg, const TSPSolver::SStep::SCandidate &cand)
 {
         dbg.nospace() << "(" << cand.nRow << ";" << cand.nCol << ")";

trunk/src/tspsolver.h

@@ -6 +6 @@
  *  $URL$
  *
- * \brief Defines #TMatrix typedef, SCandidate and SStep structs and CTSPSolver class.
+ * \brief Defines TSPSolver namespace and everything needed for solving TSP tasks.
  *
  *  <b>TSPSG: TSP Solver and Generator</b>
@@ -29 +29 @@
 #define TSPSOLVER_H
 
-#include "globals.h"
-
-#include "tspmodel.h"
-
-//! A matrix of city-to-city travel costs.
-typedef QList<QList<double> > TMatrix;
+#include <QtCore>
+#include <limits>
 
 /*!
- * \brief A structure that represents a candidate for branching.
+ * \def INFINITY
+ * \brief This value means infinity :-)
+ *
+ *  Some libraries already have \c INFINITY defined.
+ *  We need to redefine it for the \c INFINITY to always have the same value.
  */
-struct SCandidate {
-        int nRow; //!< A zero-based row number of the candidate
-        int nCol; //!< A zero-based column number of the candidate
+#ifdef INFINITY
+        #undef INFINITY
+#endif
+#define INFINITY std::numeric_limits<double>::infinity()
 
-        //! Assigns default values
-        SCandidate() {
-                nCol = nRow = -1;
-        }
-        //! An operator == implementation
-        bool operator ==(const SCandidate &cand) const {
-                return ((cand.nRow == nRow) && (cand.nCol == nCol));
-        }
-};
+/*!
+ * \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;
 
 /*!
@@ -59 +60 @@
  */
 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 matrix
+
+        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
@@ -71 +96 @@
                 price = -1;
                 pNode = plNode = prNode = NULL;
+                next = NoNextStep;
         }
 };
@@ -88 +114 @@
         void cleanup(bool processEvents = false);
         QString getSortedPath() const;
+        int getTotalSteps() const;
         bool isOptimal() const;
         SStep *solve(int numCities, const TMatrix &task);
@@ -105 +132 @@
 private:
         bool mayNotBeOptimal, canceled;
-        int nCities;
+        int nCities, total;
         SStep *root;
         QHash<int,int> route;
@@ -113 +140 @@
         void deleteTree(SStep *&root, bool processEvents = false);
         void denormalize(TMatrix &matrix) const;
-        QList<SCandidate> findCandidate(const TMatrix &matrix, int &nRow, int &nCol) 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;
@@ -122 +150 @@
 };
 
+}
+
 #ifdef DEBUG
-QDebug operator<<(QDebug dbg, const TMatrix &matrix);
-QDebug operator<<(QDebug dbg, const SCandidate &candidate);
+QDebug operator<<(QDebug dbg, const TSPSolver::TMatrix &matrix);
+QDebug operator<<(QDebug dbg, const TSPSolver::SStep::SCandidate &candidate);
 #endif // DEBUG