Changeset f0464480db in tspsg for src/tspsolver.cpp


Ignore:
Timestamp:
Dec 16, 2009, 11:22:05 PM (15 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:
1 edited

Legend:

Unmodified
Added
Removed
  • src/tspsolver.cpp

    r53f11f0e6c rf0464480db  
    2626//! Class constructor
    2727CTSPSolver::CTSPSolver()
    28         : nCities(0)
     28        : nCities(0), root(NULL)
    2929{
    3030}
     
    8080 * \todo TODO: Comment the algorithm.
    8181 */
    82 sStep *CTSPSolver::solve(int numCities, tMatrix task, QWidget *parent)
     82SStep *CTSPSolver::solve(int numCities, TMatrix task, QWidget *parent)
    8383{
    8484        if (numCities <= 1)
     
    9898        pd.setValue(0);
    9999
    100 sStep *step = new sStep();
     100SStep *step = new SStep();
    101101        step->matrix = task;
    102102        step->price = align(step->matrix);
    103103        root = step;
    104104
    105 sStep *left, *right;
     105SStep *left, *right;
    106106int nRow, nCol;
    107107bool firstStep = true;
     
    117117                }
    118118                if ((nRow == -1) || (nCol == -1) || pd.wasCanceled()) {
    119                         root = NULL;
     119                        cleanup();
    120120                        break;
    121121                }
    122122
    123123                // Route with (nRow,nCol) path
    124                 right = new sStep();
     124                right = new SStep();
    125125                right->matrix = step->matrix;
    126126                for (int k = 0; k < nCities; k++) {
     
    136136
    137137                // Route without (nRow,nCol) path
    138                 left = new sStep();
     138                left = new SStep();
    139139                left->matrix = step->matrix;
    140140                left->matrix[nRow][nCol] = INFINITY;
     
    180180}
    181181
     182CTSPSolver::~CTSPSolver()
     183{
     184        if (root != NULL)
     185                deleteNode(root);
     186}
     187
    182188/* Privates **********************************************************/
    183189
    184 double CTSPSolver::align(tMatrix &matrix)
     190double CTSPSolver::align(TMatrix &matrix)
    185191{
    186192double r = 0;
     
    207213        route.clear();
    208214        mayNotBeOptimal = false;
    209 }
    210 
    211 bool CTSPSolver::findCandidate(const tMatrix &matrix, int &nRow, int &nCol) const
     215        if (root != NULL)
     216                deleteNode(root);
     217}
     218
     219void CTSPSolver::deleteNode(SStep *node)
     220{
     221        if (node->plNode != NULL)
     222                deleteNode(node->plNode);
     223        if (node->prNode != NULL)
     224                deleteNode(node->prNode);
     225        delete node;
     226        node = NULL;
     227}
     228
     229QList<TCandidate> CTSPSolver::findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const
    212230{
    213231        nRow = -1;
    214232        nCol = -1;
    215 bool alts = false;
     233QList<TCandidate> alts;
     234TCandidate cand;
    216235double h = -1;
    217236double sum;
     
    225244                                        nRow = r;
    226245                                        nCol = c;
    227                                         alts = false;
    228                                 } else if ((sum == h) && !hasSubCycles(r,c))
    229                                         alts = true;
     246                                        alts.clear();
     247                                } else if ((sum == h) && !hasSubCycles(r,c)) {
     248                                        cand.nRow = r;
     249                                        cand.nCol = c;
     250                                        alts.append(cand);
     251                                }
    230252                        }
    231253        return alts;
    232254}
    233255
    234 double CTSPSolver::findMinInCol(int nCol, const tMatrix &matrix, int exr) const
     256double CTSPSolver::findMinInCol(int nCol, const TMatrix &matrix, int exr) const
    235257{
    236258double min = INFINITY;
     
    241263}
    242264
    243 double CTSPSolver::findMinInRow(int nRow, const tMatrix &matrix, int exc) const
     265double CTSPSolver::findMinInRow(int nRow, const TMatrix &matrix, int exc) const
    244266{
    245267double min = INFINITY;
     
    264286}
    265287
    266 void CTSPSolver::subCol(tMatrix &matrix, int nCol, double val)
     288void CTSPSolver::subCol(TMatrix &matrix, int nCol, double val)
    267289{
    268290        for (int k = 0; k < nCities; k++)
     
    271293}
    272294
    273 void CTSPSolver::subRow(tMatrix &matrix, int nRow, double val)
     295void CTSPSolver::subRow(TMatrix &matrix, int nRow, double val)
    274296{
    275297        for (int k = 0; k < nCities; k++)
Note: See TracChangeset for help on using the changeset viewer.