Changeset 9cda6e0f5d in tspsg for src/tspsolver.h

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.h (modified) (8 diffs)

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