Changeset 42 in tspsg-svn for trunk/src


Ignore:
Timestamp:
Jul 31, 2009, 8:23:07 PM (15 years ago)
Author:
laleppa
Message:

+ Finished solving algorithm (needs thorough testing).
+ Solution can be saved to HTML or OpenDocument? format.
+ Added VERSIONINFO resource for windows builds.

  • Updated translations to have unified terminology everywhere.

NB: This will be the first public alpha build.

Location:
trunk/src
Files:
1 added
12 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/globals.h

    r31 r42  
    11/*
    2  *  TSPSG - TSP Solver and Generator
     2 *  TSPSG: TSP Solver and Generator
    33 *  Copyright (C) 2007-2009 Lёppa <contacts[at]oleksii[dot]name>
    44 *
    … …  
    2929#include <QtGui>
    3030
     31// Version info
     32#include "version.h"
    3133// OS detection
    3234#include "os.h"
    … …  
    3840#define DEF_OFFSET 100
    3941#define DEF_FONT_FAMILY "Courier New"
    40 #define DEF_FONT_SIZE 12
     42#define DEF_FONT_SIZE 10
    4143#define DEF_FONT_COLOR Qt::black
    4244
    … …  
    5456#define ZKT_VERSION quint8(1)
    5557
    56 // Decided, that static array with 100 of cities maximum hard limit
    57 // will be enough for most cases, but the code will be simplier than
    58 // when using dynamic lists. If you need more, just change this value
    59 // and recompile the program ;-)
    60 #define MAX_CITIES 100
    6158// This value means infinity :-)
    6259#ifndef INFINITY
    … …  
    6461#endif
    6562// This is string, which represents infinite value in table
    66 #define INFSTR "-----"
     63#define INFSTR "---"
    6764
    6865#endif // GLOBALS_H

  • trunk/src/main.cpp

    r35 r42  
    11/*
    2  *  TSPSG - TSP Solver and Generator
     2 *  TSPSG: TSP Solver and Generator
    33 *  Copyright (C) 2007-2009 Lёppa <contacts[at]oleksii[dot]name>
    44 *

  • trunk/src/mainwindow.cpp

    r41 r42  
    1 /*
    2  *  TSPSG - TSP Solver and Generator
     1        /*
     2 *  TSPSG: TSP Solver and Generator
    33 *  Copyright (C) 2007-2009 Lёppa <contacts[at]oleksii[dot]name>
    44 *
    … …  
    3030        loadLanguage();
    3131        setupUi(this);
     32        initDocStyleSheet();
     33        solutionText->document()->setDefaultFont(settings->value("Output/Font",QFont(DEF_FONT_FAMILY,DEF_FONT_SIZE)).value<QFont>());
     34        solutionText->setTextColor(settings->value("Output/Color",DEF_FONT_COLOR).value<QColor>());
     35        solutionText->setWordWrapMode(QTextOption::WordWrap);
    3236#ifdef Q_OS_WINCE
    3337        // A little hack for toolbar icons to have sane size.
    … …  
    4650        connect(actionFileNew,SIGNAL(triggered()),this,SLOT(actionFileNewTriggered()));
    4751        connect(actionFileOpen,SIGNAL(triggered()),this,SLOT(actionFileOpenTriggered()));
    48         connect(actionFileSaveTask,SIGNAL(triggered()),this,SLOT(actionFileSaveTaskTriggered()));
     52        connect(actionFileSaveAsTask,SIGNAL(triggered()),this,SLOT(actionFileSaveAsTaskTriggered()));
     53        connect(actionFileSaveAsSolution,SIGNAL(triggered()),this,SLOT(actionFileSaveAsSolutionTriggered()));
    4954        connect(actionSettingsPreferences,SIGNAL(triggered()),this,SLOT(actionSettingsPreferencesTriggered()));
    5055        connect(actionSettingsLanguageAutodetect,SIGNAL(triggered(bool)),this,SLOT(actionSettingsLanguageAutodetectTriggered(bool)));
    … …  
    5964        connect(spinCities,SIGNAL(valueChanged(int)),this,SLOT(spinCitiesValueChanged(int)));
    6065QRect rect = geometry();
    61 #ifdef Q_OS_WINCE
    62         // HACK: Fix for all tabWidget elements becoming "unclickable" if making it central widget.
    63 /*      rect.setSize(QApplication::desktop()->availableGeometry().size());
    64         rect.setHeight(rect.height() - (QApplication::desktop()->screenGeometry().height() - QApplication::desktop()->availableGeometry().height()));
    65         tabWidget->resize(rect.width(),rect.height() - toolBar->iconSize().height());*/
    66         // Somehow, this works now. No more "unclickable" elements :-\
    6766        setCentralWidget(tabWidget);
    68 #else
     67#ifndef Q_OS_WINCE
    6968        if (settings->value("SavePos",false).toBool()) {
    7069                // Loading of saved window state
    … …  
    9291        taskView->resizeRowsToContents();
    9392#endif // Q_OS_WINCE
     93}
     94
     95void MainWindow::enableSolutionActions(bool enable)
     96{
     97        actionFileSaveAsSolution->setEnabled(enable);
     98        solutionText->setEnabled(enable);
     99        if (!enable)
     100                output.clear();
    94101}
    95102
    … …  
    141148}
    142149
     150void MainWindow::initDocStyleSheet()
     151{
     152QColor color = settings->value("Output/Color",DEF_FONT_COLOR).value<QColor>();
     153QColor hilight;
     154        if (color.value() < 192)
     155                hilight.setHsv(color.hue(),color.saturation(),127 + qRound(color.value() / 2));
     156        else
     157                hilight.setHsv(color.hue(),color.saturation(),color.value() / 2);
     158        solutionText->document()->setDefaultStyleSheet("* {color: " + color.name() +";} p {margin: 0px 10px;} table {margin: 5px;} td {padding: 1px 5px;} .hasalts {color: " + hilight.name() + ";} .selected {color: #A00000; font-weight: bold;} .alternate {color: #008000; font-weight: bold;}");
     159        solutionText->document()->setDefaultFont(settings->value("Output/Font",QFont(DEF_FONT_FAMILY,DEF_FONT_SIZE)).value<QFont>());
     160}
     161
    143162void MainWindow::spinCitiesValueChanged(int n)
    144163{
    … …  
    166185        tspmodel->clear();
    167186        setWindowModified(false);
     187        tabWidget->setCurrentIndex(0);
     188        solutionText->clear();
     189        enableSolutionActions(false);
    168190}
    169191
    … …  
    190212        tspmodel->loadTask(files.first());
    191213        setWindowModified(false);
    192 }
    193 
    194 void MainWindow::actionFileSaveTaskTriggered()
     214        solutionText->clear();
     215        enableSolutionActions(false);
     216}
     217
     218void MainWindow::actionFileSaveAsTaskTriggered()
    195219{
    196220        saveTask();
     221}
     222
     223void MainWindow::actionFileSaveAsSolutionTriggered()
     224{
     225static QString selectedFile;
     226        if (selectedFile.isEmpty())
     227                selectedFile = "solution.html";
     228QFileDialog sd(this);
     229        sd.setAcceptMode(QFileDialog::AcceptSave);
     230QStringList filters(trUtf8("HTML Files") + " (*.html *.htm)");
     231        filters.append(trUtf8("OpenDocument Files") + " (*.odt)");
     232        filters.append(trUtf8("All Files") + " (*)");
     233        sd.setNameFilters(filters);
     234        sd.selectFile(selectedFile);
     235        if (sd.exec() != QDialog::Accepted)
     236                return;
     237QStringList files = sd.selectedFiles();
     238        if (files.empty())
     239                return;
     240        selectedFile = files.first();
     241QTextDocumentWriter dw(selectedFile);
     242        if (!(selectedFile.endsWith(".htm",Qt::CaseInsensitive) || selectedFile.endsWith(".html",Qt::CaseInsensitive) || selectedFile.endsWith(".odt",Qt::CaseInsensitive) || selectedFile.endsWith(".txt",Qt::CaseInsensitive)))
     243                dw.setFormat("plaintext");
     244        dw.write(solutionText->document());
    197245}
    198246
    … …  
    219267{
    220268SettingsDialog sd(this);
    221         sd.exec();
     269        if (sd.exec() != QDialog::Accepted)
     270                return;
     271        if (sd.colorChanged() || sd.fontChanged()) {
     272                initDocStyleSheet();
     273                if (!output.isEmpty() && sd.colorChanged() && (QMessageBox(QMessageBox::Question,trUtf8("Settings Changed"),trUtf8("You have changed color settings.\nDo you wish to apply them to current solution text?"),QMessageBox::Yes | QMessageBox::No,this).exec() == QMessageBox::Yes)) {
     274                        QApplication::setOverrideCursor(QCursor(Qt::WaitCursor));
     275                        solutionText->clear();
     276                        solutionText->setHtml(output.join(""));
     277                        QApplication::restoreOverrideCursor();
     278                }
     279        }
    222280}
    223281
    … …  
    245303}
    246304
     305void MainWindow::outputMatrix(tMatrix matrix, QStringList &output, int nRow, int nCol)
     306{
     307int n = spinCities->value();
     308QString line="";
     309        output.append("<table border=\"0\" cellspacing=\"0\" cellpadding=\"0\">");
     310        for (int r = 0; r < n; r++) {
     311                line = "<tr>";
     312                for (int c = 0; c < n; c++) {
     313                        if (matrix[r][c] == INFINITY)
     314                                line += "<td align=\"center\">"INFSTR"</td>";
     315                        else if ((r == nRow) && (c == nCol))
     316                                line += "<td align=\"center\" class=\"selected\">" + QVariant(matrix[r][c]).toString() + "</td>";
     317                        else
     318                                line += "<td align=\"center\">" + QVariant(matrix[r][c]).toString() + "</td>";
     319                }
     320                line += "</tr>";
     321                output.append(line);
     322        }
     323        output.append("</table>");
     324}
     325
    247326void MainWindow::buttonSolveClicked()
    248327{
    249         // TODO: Task solving goes here :-)
    250328tMatrix matrix;
    251 double *row;
     329QList<double> row;
    252330int n = spinCities->value();
    253331bool ok;
    254332        for (int r = 0; r < n; r++) {
    255                 row = new double[n];
     333                row.clear();
    256334                for (int c = 0; c < n; c++) {
    257                         row[c] = tspmodel->index(r,c).data(Qt::UserRole).toDouble(&ok);
     335                        row.append(tspmodel->index(r,c).data(Qt::UserRole).toDouble(&ok));
    258336                        if (!ok) {
    259337                                QMessageBox(QMessageBox::Critical,trUtf8("Data error"),QString(trUtf8("Error in cell [Row %1; Column %2]: Invalid data format.")).arg(r + 1).arg(c + 1),QMessageBox::Ok,this).exec();
    … …  
    266344sStep *root = solver.solve(spinCities->value(),matrix);
    267345        if (!root)
    268                 QMessageBox(QMessageBox::Critical,trUtf8("Solution error"),trUtf8("There was an error while solving the task."),QMessageBox::Ok,this).exec();
    269         // tabWidget->setCurrentIndex(1);
     346                return;
     347        QApplication::setOverrideCursor(QCursor(Qt::WaitCursor));
     348QColor color = settings->value("Output/Color",DEF_FONT_COLOR).value<QColor>();
     349        output.clear();
     350        output.append("<p>" + trUtf8("Variant #%1").arg(spinVariant->value()) + "</p>");
     351        output.append("<p>" + trUtf8("Task:") + "</p>");
     352        outputMatrix(matrix,output);
     353        output.append("<hr>");
     354        output.append("<p>" + trUtf8("Solution of Variant #%1 task").arg(spinVariant->value()) + "</p>");
     355sStep *step = root;
     356        n = 1;
     357QString path = "";
     358        while (n <= spinCities->value()) {
     359                if (step->prNode->prNode != NULL || (step->prNode->prNode == NULL && step->plNode->prNode == NULL)) {
     360                        if (n != spinCities->value()) {
     361                                output.append("<p>" + trUtf8("Step #%1").arg(n++) + "</p>");
     362                                outputMatrix(step->matrix,output,step->candidate.nRow,step->candidate.nCol);
     363                                if (step->alts)
     364                                        output.append("<p class=\"hasalts\">" + trUtf8("This step has alternate candidates for branching.") + "</p>");
     365                                output.append("<p>&nbsp;</p>");
     366                        }
     367                        path += QString(" (%1,%2)").arg(step->candidate.nRow + 1).arg(step->candidate.nCol + 1);
     368                }
     369                if (step->prNode->prNode != NULL)
     370                        step = step->prNode;
     371                else if (step->plNode->prNode != NULL)
     372                        step = step->plNode;
     373                else
     374                        break;
     375        }
     376        output.append("<p>" + trUtf8("Optimal path:") + "</p>");
     377        output.append("<p>&nbsp;&nbsp;" + path + "</p>");
     378        output.append("<p>" + trUtf8("The price is <b>%1</b> units.").arg(step->price) + "</p>");
     379        solutionText->setHtml(output.join(""));
     380        solutionText->setDocumentTitle(trUtf8("Solution of Variant #%1 task").arg(spinVariant->value()));
     381        enableSolutionActions();
     382        tabWidget->setCurrentIndex(1);
     383        QApplication::restoreOverrideCursor();
    270384}
    271385
    … …  
    274388        // TODO: Normal about window :-)
    275389QString about = QString::fromUtf8("TSPSG - TSP Solver and Generator\n");
    276 about += QString::fromUtf8("    Copyright (C) 2007-%1 Lёppa <contacts[at]oleksii[dot]name>\n").arg(QDate::currentDate().toString("yyyy"));
     390        about += QString::fromUtf8("    Version: "BUILD_VERSION" ("BUILD_STATUS")\n");
     391        about += QString::fromUtf8("    Copyright (C) 2007-%1 Lёppa <contacts[at]oleksii[dot]name>\n").arg(QDate::currentDate().toString("yyyy"));
    277392        about += QString::fromUtf8("Target OS: %1\n").arg(OS);
    278393        about += "Qt library:\n";

  • trunk/src/mainwindow.h

    r37 r42  
    11/*
    2  *  TSPSG - TSP Solver and Generator
     2 *  TSPSG: TSP Solver and Generator
    33 *  Copyright (C) 2007-2009 Lёppa <contacts[at]oleksii[dot]name>
    44 *
    … …  
    4444        void actionFileNewTriggered();
    4545        void actionFileOpenTriggered();
    46         void actionFileSaveTaskTriggered();
     46        void actionFileSaveAsTaskTriggered();
     47        void actionFileSaveAsSolutionTriggered();
    4748        void actionSettingsPreferencesTriggered();
    4849        void actionSettingsLanguageAutodetectTriggered(bool);
    … …  
    6263        CTSPModel *tspmodel;
    6364        QActionGroup *groupSettingsLanguageList;
     65        QStringList output;
    6466        bool loadLanguage(QString lang = "");
    6567        void loadLangList();
     68        void initDocStyleSheet();
    6669        bool saveTask();
     70        void outputMatrix(tMatrix, QStringList &, int nRow = -1, int nCol = -1);
     71        void enableSolutionActions(bool enable = true);
    6772};
    6873

  • trunk/src/os.h

    r41 r42  
    11/*
    2  *  TSPSG - TSP Solver and Generator
     2 *  TSPSG: TSP Solver and Generator
    33 *  Copyright (C) 2007-2009 Lёppa <contacts[at]oleksii[dot]name>
    44 *

  • trunk/src/resource.h

    r18 r42  
    11/*
    2  *  TSPSG - TSP Solver and Generator
     2 *  TSPSG: TSP Solver and Generator
    33 *  Copyright (C) 2007-2009 Lёppa <contacts[at]oleksii[dot]name>
    44 *
    … …  
    99 */
    1010
     11#include "version.h"
     12
     13#define VS_VERSION_INFO 1
    1114#define IDI_APPICON 101

  • trunk/src/settingsdialog.cpp

    r31 r42  
    11/*
    2  *  TSPSG - TSP Solver and Generator
     2 *  TSPSG: TSP Solver and Generator
    33 *  Copyright (C) 2007-2009 Lёppa <contacts[at]oleksii[dot]name>
    44 *
    … …  
    2525
    2626SettingsDialog::SettingsDialog(QWidget *parent)
    27         : QDialog(parent)
     27        : QDialog(parent), newFont(false), newColor(false)
    2828{
    2929        setupUi(this);
    … …  
    3535//      setWindowFlags(Qt::Dialog | Qt::CustomizeWindowHint | Qt::WindowTitleHint | Qt::MSWindowsFixedSizeDialogHint);
    3636        setWindowFlags(windowFlags() ^ Qt::WindowContextHelpButtonHint);
    37         layout()->setSizeConstraint(layout()->SetFixedSize);
    3837#ifndef Q_OS_WINCE
    3938        // Setting initial text of dialog hint label to own status tip
    4039        // text.
    4140        labelHint->setText(labelHint->statusTip());
    42         // HACK: Do not resize label hint (and dialog) when text changes
    43         // from one-line to two-line and vice versa. Any better solution?
    44         labelHint->setMaximumHeight(labelHint->height());
    45         labelHint->setMinimumHeight(labelHint->height());
    4641#endif // Q_OS_WINCE
    4742        settings = new QSettings(QSettings::IniFormat,QSettings::UserScope,"TSPSG","tspsg");
    … …  
    5146        cbSaveState->setChecked(settings->value("SavePos",false).toBool());
    5247#endif // Q_OS_WINCE
    53         settings->beginGroup("Print");
     48        settings->beginGroup("Output");
    5449        font = settings->value("Font",QFont(DEF_FONT_FAMILY,DEF_FONT_SIZE)).value<QFont>();
    5550        color = settings->value("Color",DEF_FONT_COLOR).value<QColor>();
     51        settings->endGroup();
     52}
     53
     54void SettingsDialog::accept()
     55{
    5656#ifndef Q_OS_WINCE
    57         spinLeftMargin->setValue(settings->value("Offset",DEF_OFFSET).toInt());
     57        settings->setValue("SavePos",cbSaveState->isChecked());
    5858#endif // Q_OS_WINCE
     59        settings->setValue("MinCost",spinRandMin->value());
     60        settings->setValue("MaxCost",spinRandMax->value());
     61        settings->beginGroup("Output");
     62        if (newFont)
     63                settings->setValue("Font",font);
     64        if (newColor)
     65                settings->setValue("Color",color);
    5966        settings->endGroup();
     67        QDialog::accept();
     68}
     69
     70void SettingsDialog::buttonFontClicked()
     71{
     72bool ok;
     73QFont font = QFontDialog::getFont(&ok,this->font,this);
     74        if (ok && (this->font != font)) {
     75                this->font = font;
     76                newFont = true;
     77        }
     78}
     79
     80void SettingsDialog::buttonColorClicked()
     81{
     82QColor color = QColorDialog::getColor(this->color,this);
     83        if (color.isValid() && (this->color != color)) {
     84                this->color = color;
     85                newColor = true;
     86        }
     87}
     88
     89bool SettingsDialog::colorChanged() const
     90{
     91        return newColor;
     92}
     93
     94bool SettingsDialog::fontChanged() const
     95{
     96        return newFont;
    6097}
    6198
    … …  
    77114}
    78115#endif // Q_OS_WINCE
    79 
    80 void SettingsDialog::buttonFontClicked()
    81 {
    82 bool ok;
    83 QFont font = QFontDialog::getFont(&ok,this->font,this);
    84         if (ok)
    85                 this->font = font;
    86 }
    87 
    88 void SettingsDialog::buttonColorClicked()
    89 {
    90 QColor color = QColorDialog::getColor(this->color,this);
    91         if (color.isValid())
    92                 this->color = color;
    93 }
    94 
    95 void SettingsDialog::accept()
    96 {
    97 #ifndef Q_OS_WINCE
    98         settings->setValue("SavePos",cbSaveState->isChecked());
    99 #endif // Q_OS_WINCE
    100         settings->setValue("MinCost",spinRandMin->value());
    101         settings->setValue("MaxCost",spinRandMax->value());
    102         settings->beginGroup("Print");
    103         settings->setValue("Font",font);
    104         settings->setValue("Color",color);
    105 #ifndef Q_OS_WINCE
    106         settings->setValue("Offset",spinLeftMargin->value());
    107 #endif // Q_OS_WINCE
    108         settings->endGroup();
    109         QDialog::accept();
    110 }

  • trunk/src/settingsdialog.h

    r31 r42  
    11/*
    2  *  TSPSG - TSP Solver and Generator
     2 *  TSPSG: TSP Solver and Generator
    33 *  Copyright (C) 2007-2009 Lёppa <contacts[at]oleksii[dot]name>
    44 *
    … …  
    3737public:
    3838        SettingsDialog(QWidget *parent = 0);
     39        bool fontChanged() const;
     40        bool colorChanged() const;
    3941
    4042private:
    … …  
    4244        QFont font;
    4345        QColor color;
     46        bool newFont;
     47        bool newColor;
    4448#ifndef Q_OS_WINCE
    4549        bool event(QEvent *);

  • trunk/src/tspmodel.cpp

    r37 r42  
    11/*
    2  *  TSPSG - TSP Solver and Generator
     2 *  TSPSG: TSP Solver and Generator
    33 *  Copyright (C) 2007-2009 Lёppa <contacts[at]oleksii[dot]name>
    44 *
    … …  
    119119                return;
    120120        emit layoutAboutToBeChanged();
    121         if (n > nCities) {
    122                 for (int r = 0; r < nCities; r++) {
    123                         for (int c = nCities; c < n; c++)
    124                                 if (r == c)
    125                                         table[r][c] = INFINITY;
    126                                 else
    127                                         table[r][c] = 0;
    128                 }
    129                 for (int r = nCities; r < n; r++) {
    130                         for (int c = 0; c < n; c++)
    131                                 if (r == c)
    132                                         table[r][c] = INFINITY;
    133                                 else
    134                                         table[r][c] = 0;
    135                 }
    136         }
     121        table.resize(n);
     122        for (int k = 0; k < n; k++) {
     123                table[k].resize(n);
     124        }
     125        if (n > nCities)
     126                for (int k = nCities; k < n; k++)
     127                        table[k][k] = INFINITY;
    137128        nCities = n;
    138129        emit layoutChanged();
    … …  
    148139}
    149140
    150 inline bool CTSPModel::loadError(QDataStream::Status status) const
     141inline bool CTSPModel::loadError(QDataStream::Status status)
    151142{
    152143QString err;
    … …  
    257248        // Costs
    258249double val;
    259         for (int r = 0; r < size; r++)
    260                 for (int c = 0; c < size; c++)
    261                         if (r != c) {
     250        for (int r = 0; r < 5; r++)
     251                for (int c = 0; c < 5; c++)
     252                        if ((r != c) && (r < size)) {
    262253                                ds->readRawData(reinterpret_cast<char *>(&val),8);
    263254                                if (loadError(ds->status())) {

  • trunk/src/tspmodel.h

    r37 r42  
    11/*
    2  *  TSPSG - TSP Solver and Generator
     2 *  TSPSG: TSP Solver and Generator
    33 *  Copyright (C) 2007-2009 Lёppa <contacts[at]oleksii[dot]name>
    44 *
    … …  
    4848private:
    4949        QSettings *settings;
    50         double table[MAX_CITIES][MAX_CITIES];
     50        QVector<QVector<double>> table;
    5151        quint16 nCities;
    5252        int rand(int, int) const;
    53         bool loadError(QDataStream::Status) const;
     53        bool loadError(QDataStream::Status);
    5454        void loadZKT(QDataStream *);
    5555        void loadTSPT(QDataStream *);

  • trunk/src/tspsolver.cpp

    r17 r42  
    11/*
    2  *  TSPSG - TSP Solver and Generator
     2 *  TSPSG: TSP Solver and Generator
    33 *  Copyright (C) 2007-2009 Lёppa <contacts[at]oleksii[dot]name>
    44 *
    … …  
    2626
    2727CTSPSolver::CTSPSolver()
    28 {
    29 }
    30 
    31 double CTSPSolver::findMinInRow(int nRow, tMatrix matrix)
     28        : nCities(0)
     29{
     30}
     31
     32void CTSPSolver::cleanup()
     33{
     34        route.clear();
     35}
     36
     37double CTSPSolver::findMinInRow(int nRow, tMatrix matrix, int exc)
    3238{
    3339double min = INFINITY;
    3440        for (int k = 0; k < nCities; k++)
    35                 if (min > matrix[nRow][k])
     41                if (((k != exc)) && (min > matrix[nRow][k]))
    3642                        min = matrix[nRow][k];
    3743        return min == INFINITY ? 0 : min;
    3844}
    3945
    40 double CTSPSolver::findMinInCol(int nCol, tMatrix matrix)
     46double CTSPSolver::findMinInCol(int nCol, tMatrix matrix, int exr)
    4147{
    4248double min = INFINITY;
    4349        for (int k = 0; k < nCities; k++)
    44                 if (min > matrix[k][nCol])
     50                if ((k != exr) && (min > matrix[k][nCol]))
    4551                        min = matrix[k][nCol];
    4652        return min == INFINITY ? 0 : min;
    4753}
    4854
    49 sStep *CTSPSolver::solve(int numCities, tMatrix task)
     55void CTSPSolver::subRow(tMatrix &matrix, int nRow, double val)
     56{
     57        for (int k = 0; k < nCities; k++)
     58                if (k != nRow)
     59                        matrix[nRow][k] -= val;
     60}
     61
     62void CTSPSolver::subCol(tMatrix &matrix, int nCol, double val)
     63{
     64        for (int k = 0; k < nCities; k++)
     65                if (k != nCol)
     66                        matrix[k][nCol] -= val;
     67}
     68
     69double CTSPSolver::align(tMatrix &matrix)
     70{
     71double r = 0;
     72double min;
     73        for (int k = 0; k < nCities; k++) {
     74                min = findMinInRow(k,matrix);
     75                if (min > 0) {
     76                        r += min;
     77                        subRow(matrix,k,min);
     78                }
     79        }
     80        for (int k = 0; k < nCities; k++) {
     81                min = findMinInCol(k,matrix);
     82                if (min > 0) {
     83                        r += min;
     84                        subCol(matrix,k,min);
     85                }
     86        }
     87        return r;
     88}
     89
     90bool CTSPSolver::findCandidate(tMatrix matrix, int &nRow, int &nCol, double &h)
     91{
     92        h = -1;
     93        nRow = -1;
     94        nCol = -1;
     95bool alts = false;
     96double sum;
     97        for (int r = 0; r < nCities; r++)
     98                for (int c = 0; c < nCities; c++)
     99                        if ((matrix[r][c] == 0) && !forbidden.values(r).contains(c)) {
     100                                sum = findMinInRow(r,matrix,c) + findMinInCol(c,matrix,r);
     101                                if (sum > h) {
     102                                        h = sum;
     103                                        nRow = r;
     104                                        nCol = c;
     105                                        alts = false;
     106                                } else if (sum == h)
     107                                        alts = true;
     108                        }
     109        return alts;
     110}
     111
     112bool CTSPSolver::hasSubCycles(int nRow, int nCol)
     113{
     114        if ((nRow < 0) || (nCol < 0) || route.isEmpty() || !(route.size() < nCities - 1) || !route.contains(nCol))
     115                return false;
     116int i = nCol;
     117        while (true) {
     118                if ((i = route[i]) == nRow)
     119                        return true;
     120                if (!route.contains(i))
     121                        return false;
     122        }
     123        return false;
     124}
     125
     126// TODO: Comment the algorithm
     127sStep *CTSPSolver::solve(int numCities, tMatrix task, QWidget *parent)
    50128{
    51129        if (numCities <= 1)
    52130                return NULL;
     131        cleanup();
    53132        nCities = numCities;
     133double s;
     134QProgressDialog pd(parent);
     135QProgressBar *pb = new QProgressBar(&pd);
     136        pb->setAlignment(Qt::AlignCenter);
     137        pb->setFormat(trUtf8("%v of %m parts found"));
     138        pd.setBar(pb);
     139        pd.setMaximum(nCities);
     140        pd.setMinimumDuration(1000);
     141        pd.setLabelText(trUtf8("Calculating optimal route..."));
     142        pd.setWindowTitle(trUtf8("Solution Progress"));
     143        pd.setWindowModality(Qt::ApplicationModal);
     144        pd.setValue(0);
     145
    54146sStep *step = new sStep();
    55147        step->matrix = task;
     148
     149        s = align(step->matrix);
     150        step->price = s;
    56151        root = step;
    57152
    58         return step;
    59 }
     153sStep *left, *right;
     154int nRow, nCol;
     155        while (route.size() < nCities) {
     156                forbidden.clear();
     157                step->alts = findCandidate(step->matrix,nRow,nCol,s);
     158                while (hasSubCycles(nRow,nCol)) {
     159                        forbidden[nRow] = nCol;
     160                        step->matrix[nRow][nCol] = INFINITY;
     161                        step->price += align(step->matrix);
     162                        step->alts = findCandidate(step->matrix,nRow,nCol,s);
     163                }
     164                if ((nRow == -1) || (nCol == -1) || pd.wasCanceled()) {
     165                        root = NULL;
     166                        break;
     167                }
     168
     169                // Route with (nRow,nCol) path
     170                right = new sStep();
     171                right->matrix = step->matrix;
     172                for (int k = 0; k < nCities; k++) {
     173                        if (k != nCol)
     174                                right->matrix[nRow][k] = INFINITY;
     175                        if (k != nRow)
     176                                right->matrix[k][nCol] = INFINITY;
     177                }
     178                right->price = step->price + align(right->matrix);
     179                // Forbid selected route to exclude its reuse in next steps.
     180                right->matrix[nCol][nRow] = INFINITY;
     181                right->matrix[nRow][nCol] = INFINITY;
     182
     183                // Route without (nRow,nCol) path
     184                left = new sStep();
     185                left->matrix = step->matrix;
     186                left->matrix[nRow][nCol] = INFINITY;
     187                left->price = step->price + align(left->matrix);
     188
     189                step->candidate.nRow = nRow;
     190                step->candidate.nCol = nCol;
     191                step->plNode = left;
     192                step->prNode = right;
     193
     194                if (right->price <= left->price) {
     195                        // Route with (nRow,nCol) path is cheaper
     196                        step = right;
     197                        route[nRow] = nCol;
     198                        pd.setValue(route.size());
     199                } else {
     200                        // Route without (nRow,nCol) path is cheaper
     201                        step = left;
     202                        qApp->processEvents();
     203                }
     204        }
     205
     206        pd.reset();
     207        qApp->processEvents();
     208
     209        if (!root && !pd.wasCanceled()) {
     210                QMessageBox(QMessageBox::Warning,trUtf8("Solution Result"),trUtf8("This task has no solution."),QMessageBox::Ok,parent).exec();
     211        }
     212
     213        return root;
     214}

  • trunk/src/tspsolver.h

    r31 r42  
    11/*
    2  *  TSPSG - TSP Solver and Generator
     2 *  TSPSG: TSP Solver and Generator
    33 *  Copyright (C) 2007-2009 Lёppa <contacts[at]oleksii[dot]name>
    44 *
    … …  
    2727#include "globals.h"
    2828
    29 typedef QList<double *> tMatrix;
     29typedef QList<QList<double>> tMatrix;
    3030
    3131// This structure represents one step of solving
    3232// The tree of such elements will represent the solving process
    3333struct sStep {
    34         tMatrix matrix;
    35         double price;
    36         struct {unsigned int x; unsigned int y;} pos;
    37         sStep *plNode, *prNode;
    38         sStep() { price = pos.x = pos.y = 0; plNode = prNode = NULL; }
     34        tMatrix matrix; // Steps's matrix
     35        double price; // Price of travel to this step
     36        struct {unsigned int nRow; unsigned int nCol;} candidate; // Candiadate for branching in current matrix
     37        bool alts; // This matrix has alternative candidates
     38        sStep *plNode, *prNode; // Pointers to left and right branch steps
     39        sStep() { price = candidate.nRow = candidate.nCol = -1; alts = false; plNode = prNode = NULL; } // Default values
    3940};
    4041
    … …  
    4243class CTSPSolver
    4344{
     45        Q_DECLARE_TR_FUNCTIONS(CTSPSolver)
     46
    4447public:
    4548        CTSPSolver();
    46         sStep *solve(int, tMatrix);
     49        sStep *solve(int, tMatrix, QWidget *parent = 0);
     50
    4751private:
    4852        int nCities;
    4953        sStep *root;
    50         double findMinInRow(int, tMatrix);
    51         double findMinInCol(int, tMatrix);
     54        QHash<int,int> route;
     55        QHash<int,int> forbidden;
     56        double align(tMatrix &);
     57        void cleanup();
     58        bool findCandidate(tMatrix, int &, int &, double &);
     59        double findMinInRow(int, tMatrix, int exc = -1);
     60        double findMinInCol(int, tMatrix, int exr = -1);
     61        bool hasSubCycles(int, int);
     62        void subCol(tMatrix &, int, double);
     63        void subRow(tMatrix &, int, double);
    5264};
    5365
Note: See TracChangeset for help on using the changeset viewer.