Changeset 9eb63a1598 in tspsg for src/tspsolver.cpp


Ignore:
Timestamp:
Dec 20, 2010, 9:53:45 PM (13 years ago)
Author:
Oleksii Serdiuk
Branches:
0.1.4.170-beta2-bb10, appveyor, imgbot, master, readme
Children:
b8a2a118c4
Parents:
b59e2ea0b1
git-author:
Oleksii Serdiuk <contacts@…> (12/20/10 21:53:45)
git-committer:
Oleksii Serdiuk <contacts@…> (06/29/12 19:45:58)
Message:

Converted file formatting to have spaces instead of tabs. No code changes...

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/tspsolver.cpp

    rb59e2ea0b1 r9eb63a1598  
    3535QString CTSPSolver::getVersionId()
    3636{
    37         return QString("$Id$");
     37    return QString("$Id$");
    3838}
    3939
    … …  
    4343 */
    4444CTSPSolver::CTSPSolver(QObject *parent)
    45         : QObject(parent), cc(true), nCities(0), total(0), root(NULL) {}
     45    : QObject(parent), cc(true), nCities(0), total(0), root(NULL) {}
    4646
    4747/*!
    … …  
    5555void CTSPSolver::cleanup(bool processEvents)
    5656{
    57         route.clear();
    58         mayNotBeOptimal = false;
    59         if (root != NULL)
    60                 deleteTree(root, processEvents);
     57    route.clear();
     58    mayNotBeOptimal = false;
     59    if (root != NULL)
     60        deleteTree(root, processEvents);
    6161}
    6262
    … …  
    7272QString CTSPSolver::getSortedPath(const QString &city, const QString &separator) const
    7373{
    74         if (!root || route.isEmpty() || (route.size() != nCities))
    75                 return QString();
     74    if (!root || route.isEmpty() || (route.size() != nCities))
     75        return QString();
    7676
    7777int i = 0; // We start from City 1
    7878QStringList path;
    79         path << city.arg(1);
    80         while ((i = route[i]) != 0) {
    81                 path << city.arg(i + 1);
    82         }
    83         // And finish in City 1, too
    84         path << city.arg(1);
    85 
    86         return path.join(separator);
     79    path << city.arg(1);
     80    while ((i = route[i]) != 0) {
     81        path << city.arg(i + 1);
     82    }
     83    // And finish in City 1, too
     84    path << city.arg(1);
     85
     86    return path.join(separator);
    8787}
    8888
    … …  
    9494int CTSPSolver::getTotalSteps() const
    9595{
    96         return total;
     96    return total;
    9797}
    9898
    … …  
    106106bool CTSPSolver::isOptimal() const
    107107{
    108         return !mayNotBeOptimal;
     108    return !mayNotBeOptimal;
    109109}
    110110
    … …  
    121121void CTSPSolver::setCleanupOnCancel(bool enable)
    122122{
    123         cc = enable;
     123    cc = enable;
    124124}
    125125
    … …  
    134134SStep *CTSPSolver::solve(int numCities, const TMatrix &task)
    135135{
    136         if (numCities < 3)
    137                 return NULL;
     136    if (numCities < 3)
     137        return NULL;
    138138
    139139QMutexLocker locker(&mutex);
    140         cleanup();
    141         canceled = false;
    142         locker.unlock();
    143 
    144         nCities = numCities;
     140    cleanup();
     141    canceled = false;
     142    locker.unlock();
     143
     144    nCities = numCities;
    145145
    146146SStep *step = new SStep();
    147         step->matrix = task;
    148         // We need to distinguish the values forbidden by the user
    149         // from the values forbidden by the algorithm.
    150         // So we replace user's infinities by the maximum available double value.
    151         normalize(step->matrix);
     147    step->matrix = task;
     148    // We need to distinguish the values forbidden by the user
     149    // from the values forbidden by the algorithm.
     150    // So we replace user's infinities by the maximum available double value.
     151    normalize(step->matrix);
    152152#ifdef DEBUG
    153         qDebug() << step->matrix;
     153    qDebug() << step->matrix;
    154154#endif // DEBUG
    155         step->price = align(step->matrix);
    156         root = step;
     155    step->price = align(step->matrix);
     156    root = step;
    157157
    158158SStep *left, *right;
    … …  
    160160bool firstStep = true;
    161161double check = INFINITY;
    162         total = 0;
    163         while (route.size() < nCities) {
    164                 step->alts = findCandidate(step->matrix,nRow,nCol);
    165 
    166                 while (hasSubCycles(nRow,nCol)) {
     162    total = 0;
     163    while (route.size() < nCities) {
     164        step->alts = findCandidate(step->matrix,nRow,nCol);
     165
     166        while (hasSubCycles(nRow,nCol)) {
    167167#ifdef DEBUG
    168                         qDebug() << "Forbidden: (" << nRow << ";" << nCol << ")";
     168            qDebug() << "Forbidden: (" << nRow << ";" << nCol << ")";
    169169#endif // DEBUG
    170                         step->matrix[nRow][nCol] = INFINITY;
    171                         step->price += align(step->matrix);
    172                         step->alts = findCandidate(step->matrix,nRow,nCol);
    173                 }
     170            step->matrix[nRow][nCol] = INFINITY;
     171            step->price += align(step->matrix);
     172            step->alts = findCandidate(step->matrix,nRow,nCol);
     173        }
    174174
    175175#ifdef DEBUG
    176                 qDebug() /*<< step->matrix*/ << "Selected: (" << nRow << ";" << nCol << ")";
    177                 qDebug() << "Alternate:" << step->alts;
    178                 qDebug() << "Step price:" << step->price << endl;
     176        qDebug() /*<< step->matrix*/ << "Selected: (" << nRow << ";" << nCol << ")";
     177        qDebug() << "Alternate:" << step->alts;
     178        qDebug() << "Step price:" << step->price << endl;
    179179#endif // DEBUG
    180180
    181                 locker.relock();
    182                 if ((nRow == -1) || (nCol == -1) || canceled) {
    183                         if (canceled && cc)
    184                                 cleanup();
    185                         return NULL;
    186                 }
    187                 locker.unlock();
    188 
    189                 // Route with (nRow,nCol) path
    190                 right = new SStep();
    191                 right->pNode = step;
    192                 right->matrix = step->matrix;
    193                 for (int k = 0; k < nCities; k++) {
    194                         if (k != nCol)
    195                                 right->matrix[nRow][k] = INFINITY;
    196                         if (k != nRow)
    197                                 right->matrix[k][nCol] = INFINITY;
    198                 }
    199                 right->price = step->price + align(right->matrix);
    200                 // Forbid the selected route to exclude its reuse in next steps.
    201                 right->matrix[nCol][nRow] = INFINITY;
    202                 right->matrix[nRow][nCol] = INFINITY;
    203 
    204                 // Route without (nRow,nCol) path
    205                 left = new SStep();
    206                 left->pNode = step;
    207                 left->matrix = step->matrix;
    208                 left->matrix[nRow][nCol] = INFINITY;
    209                 left->price = step->price + align(left->matrix);
    210 
    211                 step->candidate.nRow = nRow;
    212                 step->candidate.nCol = nCol;
    213                 step->plNode = left;
    214                 step->prNode = right;
    215 
    216                 // This matrix is not used anymore. Restoring infinities back.
    217                 denormalize(step->matrix);
    218 
    219                 if (right->price <= left->price) {
    220                         // Route with (nRow,nCol) path is cheaper
    221                         step->next = SStep::RightBranch;
    222                         step = right;
    223                         route[nRow] = nCol;
    224                         emit routePartFound(route.size());
    225                         if (firstStep) {
    226                                 check = left->price;
    227                                 firstStep = false;
    228                         }
    229                 } else {
    230                         // Route without (nRow,nCol) path is cheaper
    231                         step->next = SStep::LeftBranch;
    232                         step = left;
    233                         QCoreApplication::processEvents();
    234                         if (firstStep) {
    235                                 check = right->price;
    236                                 firstStep = false;
    237                         }
    238                 }
    239                 total++;
    240         }
    241 
    242         mayNotBeOptimal = (check < step->price);
    243 
    244         return root;
     181        locker.relock();
     182        if ((nRow == -1) || (nCol == -1) || canceled) {
     183            if (canceled && cc)
     184                cleanup();
     185            return NULL;
     186        }
     187        locker.unlock();
     188
     189        // Route with (nRow,nCol) path
     190        right = new SStep();
     191        right->pNode = step;
     192        right->matrix = step->matrix;
     193        for (int k = 0; k < nCities; k++) {
     194            if (k != nCol)
     195                right->matrix[nRow][k] = INFINITY;
     196            if (k != nRow)
     197                right->matrix[k][nCol] = INFINITY;
     198        }
     199        right->price = step->price + align(right->matrix);
     200        // Forbid the selected route to exclude its reuse in next steps.
     201        right->matrix[nCol][nRow] = INFINITY;
     202        right->matrix[nRow][nCol] = INFINITY;
     203
     204        // Route without (nRow,nCol) path
     205        left = new SStep();
     206        left->pNode = step;
     207        left->matrix = step->matrix;
     208        left->matrix[nRow][nCol] = INFINITY;
     209        left->price = step->price + align(left->matrix);
     210
     211        step->candidate.nRow = nRow;
     212        step->candidate.nCol = nCol;
     213        step->plNode = left;
     214        step->prNode = right;
     215
     216        // This matrix is not used anymore. Restoring infinities back.
     217        denormalize(step->matrix);
     218
     219        if (right->price <= left->price) {
     220            // Route with (nRow,nCol) path is cheaper
     221            step->next = SStep::RightBranch;
     222            step = right;
     223            route[nRow] = nCol;
     224            emit routePartFound(route.size());
     225            if (firstStep) {
     226                check = left->price;
     227                firstStep = false;
     228            }
     229        } else {
     230            // Route without (nRow,nCol) path is cheaper
     231            step->next = SStep::LeftBranch;
     232            step = left;
     233            QCoreApplication::processEvents();
     234            if (firstStep) {
     235                check = right->price;
     236                firstStep = false;
     237            }
     238        }
     239        total++;
     240    }
     241
     242    mayNotBeOptimal = (check < step->price);
     243
     244    return root;
    245245}
    246246
    … …  
    252252{
    253253QMutexLocker locker(&mutex);
    254         return canceled;
     254    return canceled;
    255255}
    256256
    … …  
    261261{
    262262QMutexLocker locker(&mutex);
    263         canceled = true;
     263    canceled = true;
    264264}
    265265
    266266CTSPSolver::~CTSPSolver()
    267267{
    268         if (root != NULL)
    269                 deleteTree(root);
     268    if (root != NULL)
     269        deleteTree(root);
    270270}
    271271
    … …  
    276276double r = 0;
    277277double min;
    278         for (int k = 0; k < nCities; k++) {
    279                 min = findMinInRow(k,matrix);
    280                 if (min > 0) {
    281                         r += min;
    282                         if (min < MAX_DOUBLE)
    283                                 subRow(matrix,k,min);
    284                 }
    285         }
    286         for (int k = 0; k < nCities; k++) {
    287                 min = findMinInCol(k,matrix);
    288                 if (min > 0) {
    289                         r += min;
    290                         if (min < MAX_DOUBLE)
    291                                 subCol(matrix,k,min);
    292                 }
    293         }
    294         return (r != MAX_DOUBLE) ? r : INFINITY;
     278    for (int k = 0; k < nCities; k++) {
     279        min = findMinInRow(k,matrix);
     280        if (min > 0) {
     281            r += min;
     282            if (min < MAX_DOUBLE)
     283                subRow(matrix,k,min);
     284        }
     285    }
     286    for (int k = 0; k < nCities; k++) {
     287        min = findMinInCol(k,matrix);
     288        if (min > 0) {
     289            r += min;
     290            if (min < MAX_DOUBLE)
     291                subCol(matrix,k,min);
     292        }
     293    }
     294    return (r != MAX_DOUBLE) ? r : INFINITY;
    295295}
    296296
    297297void CTSPSolver::deleteTree(SStep *&root, bool processEvents)
    298298{
    299         if (root == NULL)
    300                 return;
     299    if (root == NULL)
     300        return;
    301301SStep *step = root;
    302302SStep *parent;
    303         forever {
    304                 if (processEvents)
    305                         QCoreApplication::processEvents(QEventLoop::ExcludeUserInputEvents);
    306                 if (step->plNode != NULL) {
    307                         // We have left child node - going inside it
    308                         step = step->plNode;
    309                         step->pNode->plNode = NULL;
    310                         continue;
    311                 } else if (step->prNode != NULL) {
    312                         // We have right child node - going inside it
    313                         step = step->prNode;
    314                         step->pNode->prNode = NULL;
    315                         continue;
    316                 } else {
    317                         // We have no child nodes. Deleting the current one.
    318                         parent = step->pNode;
    319                         delete step;
    320                         if (parent != NULL) {
    321                                 // Going back to the parent node.
    322                                 step = parent;
    323                         } else {
    324                                 // We came back to the root node. Finishing.
    325                                 root = NULL;
    326                                 break;
    327                         }
    328                 }
    329         }
     303    forever {
     304        if (processEvents)
     305            QCoreApplication::processEvents(QEventLoop::ExcludeUserInputEvents);
     306        if (step->plNode != NULL) {
     307            // We have left child node - going inside it
     308            step = step->plNode;
     309            step->pNode->plNode = NULL;
     310            continue;
     311        } else if (step->prNode != NULL) {
     312            // We have right child node - going inside it
     313            step = step->prNode;
     314            step->pNode->prNode = NULL;
     315            continue;
     316        } else {
     317            // We have no child nodes. Deleting the current one.
     318            parent = step->pNode;
     319            delete step;
     320            if (parent != NULL) {
     321                // Going back to the parent node.
     322                step = parent;
     323            } else {
     324                // We came back to the root node. Finishing.
     325                root = NULL;
     326                break;
     327            }
     328        }
     329    }
    330330}
    331331
    332332void CTSPSolver::denormalize(TMatrix &matrix) const
    333333{
    334         for (int r = 0; r < nCities; r++)
    335                 for (int c = 0; c < nCities; c++)
    336                         if ((r != c) && (matrix.at(r).at(c) == MAX_DOUBLE))
    337                                 matrix[r][c] = INFINITY;
     334    for (int r = 0; r < nCities; r++)
     335        for (int c = 0; c < nCities; c++)
     336            if ((r != c) && (matrix.at(r).at(c) == MAX_DOUBLE))
     337                matrix[r][c] = INFINITY;
    338338}
    339339
    340340QList<SStep::SCandidate> CTSPSolver::findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const
    341341{
    342         nRow = -1;
    343         nCol = -1;
     342    nRow = -1;
     343    nCol = -1;
    344344QList<SStep::SCandidate> alts;
    345345SStep::SCandidate cand;
    346346double h = -1;
    347347double sum;
    348         for (int r = 0; r < nCities; r++)
    349                 for (int c = 0; c < nCities; c++)
    350                         if (matrix.at(r).at(c) == 0) {
    351                                 sum = findMinInRow(r,matrix,c) + findMinInCol(c,matrix,r);
    352                                 if (sum > h) {
    353                                         h = sum;
    354                                         nRow = r;
    355                                         nCol = c;
    356                                         alts.clear();
    357                                 } else if ((sum == h) && !hasSubCycles(r,c)) {
    358                                         cand.nRow = r;
    359                                         cand.nCol = c;
    360                                         alts.append(cand);
    361                                 }
    362                         }
    363         return alts;
     348    for (int r = 0; r < nCities; r++)
     349        for (int c = 0; c < nCities; c++)
     350            if (matrix.at(r).at(c) == 0) {
     351                sum = findMinInRow(r,matrix,c) + findMinInCol(c,matrix,r);
     352                if (sum > h) {
     353                    h = sum;
     354                    nRow = r;
     355                    nCol = c;
     356                    alts.clear();
     357                } else if ((sum == h) && !hasSubCycles(r,c)) {
     358                    cand.nRow = r;
     359                    cand.nCol = c;
     360                    alts.append(cand);
     361                }
     362            }
     363    return alts;
    364364}
    365365
    … …  
    367367{
    368368double min = INFINITY;
    369         for (int k = 0; k < nCities; k++)
    370                 if ((k != exr) && (min > matrix.at(k).at(nCol)))
    371                         min = matrix.at(k).at(nCol);
    372         return (min == INFINITY) ? 0 : min;
     369    for (int k = 0; k < nCities; k++)
     370        if ((k != exr) && (min > matrix.at(k).at(nCol)))
     371            min = matrix.at(k).at(nCol);
     372    return (min == INFINITY) ? 0 : min;
    373373}
    374374
    … …  
    376376{
    377377double min = INFINITY;
    378         for (int k = 0; k < nCities; k++) {
    379                 if (((k != exc)) && (min > matrix.at(nRow).at(k)))
    380                         min = matrix.at(nRow).at(k);
    381         }
    382         return (min == INFINITY) ? 0 : min;
     378    for (int k = 0; k < nCities; k++) {
     379        if (((k != exc)) && (min > matrix.at(nRow).at(k)))
     380            min = matrix.at(nRow).at(k);
     381    }
     382    return (min == INFINITY) ? 0 : min;
    383383}
    384384
    385385bool CTSPSolver::hasSubCycles(int nRow, int nCol) const
    386386{
    387         if ((nRow < 0) || (nCol < 0) || route.isEmpty() || !(route.size() < nCities - 1) || !route.contains(nCol))
    388                 return false;
     387    if ((nRow < 0) || (nCol < 0) || route.isEmpty() || !(route.size() < nCities - 1) || !route.contains(nCol))
     388        return false;
    389389int i = nCol;
    390         forever {
    391                 if ((i = route.value(i)) == nRow)
    392                         return true;
    393                 if (!route.contains(i))
    394                         return false;
    395         }
    396         return false;
     390    forever {
     391        if ((i = route.value(i)) == nRow)
     392            return true;
     393        if (!route.contains(i))
     394            return false;
     395    }
     396    return false;
    397397}
    398398
    399399void CTSPSolver::normalize(TMatrix &matrix) const
    400400{
    401         for (int r = 0; r < nCities; r++)
    402                 for (int c = 0; c < nCities; c++)
    403                         if ((r != c) && (matrix.at(r).at(c) == INFINITY))
    404                                 matrix[r][c] = MAX_DOUBLE;
     401    for (int r = 0; r < nCities; r++)
     402        for (int c = 0; c < nCities; c++)
     403            if ((r != c) && (matrix.at(r).at(c) == INFINITY))
     404                matrix[r][c] = MAX_DOUBLE;
    405405}
    406406
    407407void CTSPSolver::subCol(TMatrix &matrix, int nCol, double val)
    408408{
    409         for (int k = 0; k < nCities; k++)
    410                 if (k != nCol)
    411                         matrix[k][nCol] -= val;
     409    for (int k = 0; k < nCities; k++)
     410        if (k != nCol)
     411            matrix[k][nCol] -= val;
    412412}
    413413
    414414void CTSPSolver::subRow(TMatrix &matrix, int nRow, double val)
    415415{
    416         for (int k = 0; k < nCities; k++)
    417                 if (k != nRow)
    418                         matrix[nRow][k] -= val;
     416    for (int k = 0; k < nCities; k++)
     417        if (k != nRow)
     418            matrix[nRow][k] -= val;
    419419}
    420420
    … …  
    424424QDebug operator<<(QDebug dbg, const TSPSolver::TMatrix &matrix)
    425425{
    426         for (int r = 0; r < matrix.count(); r++) {
    427                 for (int c = 0; c < matrix.at(r).count(); c++)
    428                         dbg.space() << QString::number(matrix.at(r).at(c)).leftJustified(5);
    429                 dbg << endl;
    430         }
    431         return dbg;
     426    for (int r = 0; r < matrix.count(); r++) {
     427        for (int c = 0; c < matrix.at(r).count(); c++)
     428            dbg.space() << QString::number(matrix.at(r).at(c)).leftJustified(5);
     429        dbg << endl;
     430    }
     431    return dbg;
    432432}
    433433
    434434QDebug operator<<(QDebug dbg, const TSPSolver::SStep::SCandidate &cand)
    435435{
    436         dbg.nospace() << "(" << cand.nRow << ";" << cand.nCol << ")";
    437         return dbg;
     436    dbg.nospace() << "(" << cand.nRow << ";" << cand.nCol << ")";
     437    return dbg;
    438438}
    439439#endif // DEBUG
Note: See TracChangeset for help on using the changeset viewer.