Changeset f0464480db in tspsg for src/tspsolver.cpp

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.cpp (modified) (11 diffs)

src/tspsolver.cpp

@@ -26 +26 @@
 //! Class constructor
 CTSPSolver::CTSPSolver()
-        : nCities(0)
+        : nCities(0), root(NULL)
 {
 }
@@ -80 +80 @@
  * \todo TODO: Comment the algorithm.
  */
-sStep *CTSPSolver::solve(int numCities, tMatrix task, QWidget *parent)
+SStep *CTSPSolver::solve(int numCities, TMatrix task, QWidget *parent)
 {
         if (numCities <= 1)
@@ -98 +98 @@
         pd.setValue(0);
 
-sStep *step = new sStep();
+SStep *step = new SStep();
         step->matrix = task;
         step->price = align(step->matrix);
         root = step;
 
-sStep *left, *right;
+SStep *left, *right;
 int nRow, nCol;
 bool firstStep = true;
@@ -117 +117 @@
                 }
                 if ((nRow == -1) || (nCol == -1) || pd.wasCanceled()) {
-                        root = NULL;
+                        cleanup();
                         break;
                 }
 
                 // Route with (nRow,nCol) path
-                right = new sStep();
+                right = new SStep();
                 right->matrix = step->matrix;
                 for (int k = 0; k < nCities; k++) {
@@ -136 +136 @@
 
                 // Route without (nRow,nCol) path
-                left = new sStep();
+                left = new SStep();
                 left->matrix = step->matrix;
                 left->matrix[nRow][nCol] = INFINITY;
@@ -180 +180 @@
 }
 
+CTSPSolver::~CTSPSolver()
+{
+        if (root != NULL)
+                deleteNode(root);
+}
+
 /* Privates **********************************************************/
 
-double CTSPSolver::align(tMatrix &matrix)
+double CTSPSolver::align(TMatrix &matrix)
 {
 double r = 0;
@@ -207 +213 @@
         route.clear();
         mayNotBeOptimal = false;
-}
-
-bool CTSPSolver::findCandidate(const tMatrix &matrix, int &nRow, int &nCol) const
+        if (root != NULL)
+                deleteNode(root);
+}
+
+void CTSPSolver::deleteNode(SStep *node)
+{
+        if (node->plNode != NULL)
+                deleteNode(node->plNode);
+        if (node->prNode != NULL)
+                deleteNode(node->prNode);
+        delete node;
+        node = NULL;
+}
+
+QList<TCandidate> CTSPSolver::findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const
 {
         nRow = -1;
         nCol = -1;
-bool alts = false;
+QList<TCandidate> alts;
+TCandidate cand;
 double h = -1;
 double sum;
@@ -225 +244 @@
                                         nRow = r;
                                         nCol = c;
-                                        alts = false;
-                                } else if ((sum == h) && !hasSubCycles(r,c))
-                                        alts = true;
+                                        alts.clear();
+                                } else if ((sum == h) && !hasSubCycles(r,c)) {
+                                        cand.nRow = r;
+                                        cand.nCol = c;
+                                        alts.append(cand);
+                                }
                         }
         return alts;
 }
 
-double CTSPSolver::findMinInCol(int nCol, const tMatrix &matrix, int exr) const
+double CTSPSolver::findMinInCol(int nCol, const TMatrix &matrix, int exr) const
 {
 double min = INFINITY;
@@ -241 +263 @@
 }
 
-double CTSPSolver::findMinInRow(int nRow, const tMatrix &matrix, int exc) const
+double CTSPSolver::findMinInRow(int nRow, const TMatrix &matrix, int exc) const
 {
 double min = INFINITY;
@@ -264 +286 @@
 }
 
-void CTSPSolver::subCol(tMatrix &matrix, int nCol, double val)
+void CTSPSolver::subCol(TMatrix &matrix, int nCol, double val)
 {
         for (int k = 0; k < nCities; k++)
@@ -271 +293 @@
 }
 
-void CTSPSolver::subRow(tMatrix &matrix, int nRow, double val)
+void CTSPSolver::subRow(TMatrix &matrix, int nRow, double val)
 {
         for (int k = 0; k < nCities; k++)