Changeset 9cda6e0f5d in tspsg for src/tspsolver.cpp

Timestamp:

Apr 25, 2010, 4:36:27 PM (14 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.

File:

• src/tspsolver.cpp (modified) (16 diffs)

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 << ")";