Changeset f0464480db in tspsg for src/tspsolver.h

Timestamp:

Dec 16, 2009, 11:22:05 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:

0bd0e1aca7

Parents:

53f11f0e6c

Message:

+ CTSPSolver class now deletes all solution tree on cleanup and delete to avoid memory leaks.
+ List of alternate candidates for branching is now saved in every solution step and displayed on output.
+ New struct TCandidate that represents a candidate for branching.

• Renamed sStep to SStep and tMatrix to TMatrix.
• Made a better and more readable About window.
• English translation is now loaded too. This is needed to support plurals (e.g., 1 candidate, 4 candidates).

File:

• src/tspsolver.h (modified) (3 diffs)

src/tspsolver.h

@@ -34 +34 @@
 
 //! A matrix of city-to-city travel costs.
-typedef QList<QList<double> > tMatrix;
+typedef QList<QList<double> > TMatrix;
+
+/*!
+ * \brief A structure that represents a candidate for branching.
+ */
+struct TCandidate {
+        int nRow; //!< A zero-based row number of the candidate
+        int nCol; //!< A zero-based column number of the candidate
+
+        //! Assigns default values
+        TCandidate() {
+                nCol = nRow = -1;
+        }
+        //! An operator == implementation
+        bool operator ==(const TCandidate &cand) const {
+                return ((cand.nRow == nRow) && (cand.nCol == nCol));
+        }
+};
 
 /*!
@@ -41 +58 @@
  *  A tree of such elements will represent the solving process.
  */
-//! \todo TODO: List alternative candidates.
-struct sStep {
-        tMatrix matrix; //!< This step's matrix
+struct SStep {
+        TMatrix matrix; //!< This step's matrix
         double price; //!< The price of travel to this step
-        struct {
-                int nRow; //!< A zero-based row number of the candidate
-                int nCol; //!< A zero-based column number of the candidate
-        } candidate; //!< A candiadate for branching in the current matrix
-        bool alts; //!< Indicates whether or not matrix has alternative candidates
-        sStep *plNode; //!< Pointer to the left branch step
-        sStep *prNode; //!< Pointer to the right branch step
+        TCandidate candidate; //!< A candiadate for branching in the current matrix
+        QList<TCandidate> alts; //!< A list of alternative branching candidates
+        SStep *plNode; //!< Pointer to the left branch step
+        SStep *prNode; //!< Pointer to the right branch step
 
         //! Assigns default values
-        sStep() {
-                price = candidate.nRow = candidate.nCol = -1;
-                alts = false;
+        SStep() {
+                price = -1;
                 plNode = prNode = NULL;
         }
@@ -76 +88 @@
         static QString getVersionId();
         bool isOptimal() const;
-        sStep *solve(int numCities, tMatrix task, QWidget *parent = 0);
+        SStep *solve(int numCities, TMatrix task, QWidget *parent = 0);
+        ~CTSPSolver();
 
 private:
         bool mayNotBeOptimal;
         int nCities;
-        sStep *root;
+        SStep *root;
         QHash<int,int> route;
 //      QHash<int,int> forbidden;
 
-        double align(tMatrix &matrix);
+        double align(TMatrix &matrix);
         void cleanup();
-        bool 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 deleteNode(SStep *node);
+        QList<TCandidate> 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;
         bool hasSubCycles(int nRow, int nCol) const;
-        void subCol(tMatrix &matrix, int nCol, double val);
-        void subRow(tMatrix &matrix, int nRow, double val);
+        void subCol(TMatrix &matrix, int nCol, double val);
+        void subRow(TMatrix &matrix, int nRow, double val);
 };