Changeset 74 in tspsg-svn for trunk/src


Ignore:
Timestamp:
Dec 16, 2009, 11:22:05 PM (15 years ago)
Author:
laleppa
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).
Location:
trunk/src
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/mainwindow.cpp

    r71 r74  
    302302{
    303303//! \todo TODO: Normal about window :-)
    304 QString about = QString::fromUtf8("TSPSG: TSP Solver and Generator\n");
    305         about += QString::fromUtf8("    Version: "BUILD_VERSION"\n");
    306         about += QString::fromUtf8("    Copyright (C) 2007-%1 Lёppa <contacts[at]oleksii[dot]name>\n").arg(QDate::currentDate().toString("yyyy"));
    307         about += QString::fromUtf8("Target OS: %1\n").arg(OS);
    308         about += "Qt library:\n";
    309         about += QString::fromUtf8("    Compile time: %1\n").arg(QT_VERSION_STR);
    310         about += QString::fromUtf8("    Runtime: %1\n").arg(qVersion());
    311         about += QString::fromUtf8("Built on %1 at %2\n").arg(__DATE__).arg(__TIME__);
    312         about += QString::fromUtf8(VERSIONID"\n\n");
    313         about += QString::fromUtf8("Algorithm: %1\n").arg(CTSPSolver::getVersionId());
    314         about += "\n";
    315         about += "TSPSG is licensed under the terms of the GNU General Public License. You should have received a copy of the GNU General Public License along with TSPSG.";
    316         QMessageBox(QMessageBox::Information,"About",about,QMessageBox::Ok,this).exec();
     304QString about = QString::fromUtf8("<b>TSPSG: TSP Solver and Generator</b><br>");
     305        about += QString::fromUtf8("&nbsp;&nbsp;&nbsp;&nbsp;Version: <b>"BUILD_VERSION"</b><br>");
     306        about += QString::fromUtf8("&nbsp;&nbsp;&nbsp;&nbsp;Copyright: <b>&copy; 2007-%1 Lёppa</b><br>").arg(QDate::currentDate().toString("yyyy"));
     307        about += QString::fromUtf8("&nbsp;&nbsp;&nbsp;&nbsp;<b><a href=\"http://tspsg.sourceforge.net/\">http://tspsg.sourceforge.net/</a></b><br>");
     308        about += "<br>";
     309        about += QString::fromUtf8("Target OS: <b>%1</b><br>").arg(OS);
     310        about += "Qt library:<br>";
     311        about += QString::fromUtf8("&nbsp;&nbsp;&nbsp;&nbsp;Build time: <b>%1</b><br>").arg(QT_VERSION_STR);
     312        about += QString::fromUtf8("&nbsp;&nbsp;&nbsp;&nbsp;Runtime: <b>%1</b><br>").arg(qVersion());
     313        about += QString::fromUtf8("Built on <b>%1</b> at <b>%2</b><br>").arg(__DATE__).arg(__TIME__);
     314        about += QString::fromUtf8("Id: <b>"VERSIONID"</b><br>");
     315        about += QString::fromUtf8("Algorithm: <b>%1</b><br>").arg(CTSPSolver::getVersionId());
     316        about += "<br>";
     317        about += "TSPSG is free software: you can redistribute it and/or modify it<br>"
     318                "under the terms of the GNU General Public License as published<br>"
     319                "by the Free Software Foundation, either version 3 of the License,<br>"
     320                "or (at your option) any later version.<br>"
     321                "<br>"
     322                "TSPSG is distributed in the hope that it will be useful, but<br>"
     323                "WITHOUT ANY WARRANTY; without even the implied warranty of<br>"
     324                "MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the<br>"
     325                "GNU General Public License for more details.<br>"
     326                "<br>"
     327                "You should have received a copy of the GNU General Public License<br>"
     328                "along with TSPSG.  If not, see <a href=\"http://www.gnu.org/licenses/\">http://www.gnu.org/licenses/</a>.";
     329
     330QDialog *dlg = new QDialog(this);
     331QLabel *lblIcon = new QLabel(dlg);
     332QTextBrowser *txtAbout = new QTextBrowser(dlg);
     333QVBoxLayout *vb1 = new QVBoxLayout(),
     334        *vb2 = new QVBoxLayout();
     335QHBoxLayout *hb = new QHBoxLayout();
     336QDialogButtonBox *bb = new QDialogButtonBox(QDialogButtonBox::Ok, Qt::Horizontal, dlg);
     337
     338        lblIcon->setPixmap(QPixmap(":/images/tspsg.png").scaledToWidth(64, Qt::SmoothTransformation));
     339
     340        vb1->addWidget(lblIcon);
     341        vb1->addStretch();
     342
     343//      txtAbout->setTextInteractionFlags(txtAbout->textInteractionFlags() ^ Qt::TextEditable);
     344        txtAbout->setWordWrapMode(QTextOption::NoWrap);
     345        txtAbout->setOpenExternalLinks(true);
     346        txtAbout->setHtml(about);
     347        txtAbout->moveCursor(QTextCursor::Start);
     348
     349        hb->addLayout(vb1);
     350        hb->addWidget(txtAbout);
     351
     352        vb2->addLayout(hb);
     353        vb2->addWidget(bb);
     354
     355        dlg->setWindowTitle(trUtf8("About TSPSG"));
     356        dlg->setLayout(vb2);
     357
     358        connect(bb, SIGNAL(accepted()), dlg, SLOT(accept()));
     359
     360        dlg->resize(475, 350);
     361        dlg->exec();
     362
     363        delete dlg;
    317364}
    318365
    … …  
    331378void MainWindow::buttonSolveClicked()
    332379{
    333 tMatrix matrix;
     380TMatrix matrix;
    334381QList<double> row;
    335382int n = spinCities->value();
    … …  
    347394        }
    348395CTSPSolver solver;
    349 sStep *root = solver.solve(n,matrix,this);
     396SStep *root = solver.solve(n,matrix,this);
    350397        if (!root)
    351398                return;
    … …  
    358405        output.append("<hr>");
    359406        output.append("<p>" + trUtf8("Solution of Variant #%1 task").arg(spinVariant->value()) + "</p>");
    360 sStep *step = root;
     407SStep *step = root;
    361408        n = 1;
    362409        while (n <= spinCities->value()) {
    363                 if (step->prNode->prNode != NULL || (step->prNode->prNode == NULL && step->plNode->prNode == NULL)) {
     410                if (step->prNode->prNode != NULL || ((step->prNode->prNode == NULL) && (step->plNode->prNode == NULL))) {
    364411                        if (n != spinCities->value()) {
    365412                                output.append("<p>" + trUtf8("Step #%1").arg(n++) + "</p>");
    366                                 outputMatrix(step->matrix,output,step->candidate.nRow,step->candidate.nCol);
    367                                 if (step->alts)
    368                                         output.append("<p class=\"hasalts\">" + trUtf8("This step has alternate candidates for branching.") + "</p>");
     413                                outputMatrix(*step, output);
     414                                output.append("<p>" + trUtf8("Selected candidate for branching: %1.").arg(trUtf8("(%1;%2)").arg(step->candidate.nRow + 1).arg(step->candidate.nCol + 1)) + "</p>");
     415                                if (!step->alts.empty()) {
     416TCandidate cand;
     417QString alts;
     418                                        foreach(cand, step->alts) {
     419                                                if (!alts.isEmpty())
     420                                                        alts += ", ";
     421                                                alts += trUtf8("(%1;%2)").arg(cand.nRow + 1).arg(cand.nCol + 1);
     422                                        }
     423                                        output.append("<p class=\"hasalts\">" + trUtf8("%n alternate candidate(s) for branching: %1.","",step->alts.count()).arg(alts) + "</p>");
     424                                }
    369425                                output.append("<p>&nbsp;</p>");
    370426                        }
    … …  
    392448
    393449        // Scrolling to the end of text.
    394 QTextCursor cursor(solutionText->textCursor());
    395         cursor.movePosition(QTextCursor::End, QTextCursor::MoveAnchor);
    396         solutionText->setTextCursor(cursor);
     450        solutionText->moveCursor(QTextCursor::End);
    397451
    398452        enableSolutionActions();
    … …  
    536590                qtTranslator = NULL;
    537591        }
    538         qtTranslator = new QTranslator();
    539592static QTranslator *translator; // Application translator
    540593        if (translator) {
    … …  
    543596        }
    544597        translator = new QTranslator();
    545         if (lng.compare("en") && !lng.startsWith("en_")) {
     598        if ((lng.compare("en") != 0) && !lng.startsWith("en_")) {
    546599                // Trying to load system Qt library translation...
     600                qtTranslator = new QTranslator();
    547601                if (qtTranslator->load("qt_" + lng,QLibraryInfo::location(QLibraryInfo::TranslationsPath)))
    548602                        qApp->installTranslator(qtTranslator);
    549                 else
    550                         // No luck. Let's try to load bundled one.
     603                else {
     604                        // No luck. Let's try to load a bundled one.
    551605                        if (qtTranslator->load("qt_" + lng,PATH_I18N))
    552606                                qApp->installTranslator(qtTranslator);
    … …  
    556610                                qtTranslator = NULL;
    557611                        }
    558                 // Now let's load application translation.
    559                 if (translator->load(lng,PATH_I18N))
    560                         qApp->installTranslator(translator);
    561                 else {
     612                }
     613        }
     614        // Now let's load application translation.
     615        if (translator->load(lng,PATH_I18N))
     616                qApp->installTranslator(translator);
     617        else {
     618                delete translator;
     619                translator = NULL;
     620                if ((lng.compare("en") != 0) && !lng.startsWith("en_")) {
    562621                        if (!ad)
    563622                                QMessageBox(QMessageBox::Warning,trUtf8("Language Change"),trUtf8("Unable to load translation language."),QMessageBox::Ok,this).exec();
    564                         delete translator;
    565                         translator = NULL;
    566623                        return false;
    567624                }
    … …  
    583640}
    584641
    585 void MainWindow::outputMatrix(const tMatrix &matrix, QStringList &output, int nRow, int nCol)
     642void MainWindow::outputMatrix(const TMatrix &matrix, QStringList &output)
    586643{
    587644int n = spinCities->value();
    … …  
    593650                        if (matrix.at(r).at(c) == INFINITY)
    594651                                line += "<td align=\"center\">"INFSTR"</td>";
    595                         else if ((r == nRow) && (c == nCol))
    596                                 line += "<td align=\"center\" class=\"selected\">" + QVariant(matrix.at(r).at(c)).toString() + "</td>";
    597652                        else
    598653                                line += "<td align=\"center\">" + QVariant(matrix.at(r).at(c)).toString() + "</td>";
     654                }
     655                line += "</tr>";
     656                output.append(line);
     657        }
     658        output.append("</table>");
     659}
     660
     661void MainWindow::outputMatrix(const SStep &step, QStringList &output)
     662{
     663int n = spinCities->value();
     664QString line="";
     665        output.append("<table border=\"0\" cellspacing=\"0\" cellpadding=\"0\">");
     666        for (int r = 0; r < n; r++) {
     667                line = "<tr>";
     668                for (int c = 0; c < n; c++) {
     669                        if (step.matrix.at(r).at(c) == INFINITY)
     670                                line += "<td align=\"center\">"INFSTR"</td>";
     671                        else if ((r == step.candidate.nRow) && (c == step.candidate.nCol))
     672                                line += "<td align=\"center\" class=\"selected\">" + QVariant(step.matrix.at(r).at(c)).toString() + "</td>";
     673                        else {
     674TCandidate cand;
     675                                cand.nRow = r;
     676                                cand.nCol = c;
     677                                if (step.alts.contains(cand))
     678                                        line += "<td align=\"center\" class=\"alternate\">" + QVariant(step.matrix.at(r).at(c)).toString() + "</td>";
     679                                else
     680                                        line += "<td align=\"center\">" + QVariant(step.matrix.at(r).at(c)).toString() + "</td>";
     681                        }
    599682                }
    600683                line += "</tr>";

  • trunk/src/mainwindow.h

    r71 r74  
    9292        bool loadLanguage(const QString &lang = QString());
    9393        bool maybeSave();
    94         void outputMatrix(const tMatrix &matrix, QStringList &output, int nRow = -1, int nCol = -1);
     94        void outputMatrix(const TMatrix &matrix, QStringList &output);
     95        void outputMatrix(const SStep &step, QStringList &output);
    9596        bool saveTask();
    9697        void setFileName(const QString &fileName = trUtf8("Untitled") + ".tspt");

  • trunk/src/tspsolver.cpp

    r71 r74  
    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++)

  • trunk/src/tspsolver.h

    r71 r74  
    3434
    3535//! A matrix of city-to-city travel costs.
    36 typedef QList<QList<double> > tMatrix;
     36typedef QList<QList<double> > TMatrix;
     37
     38/*!
     39 * \brief A structure that represents a candidate for branching.
     40 */
     41struct TCandidate {
     42        int nRow; //!< A zero-based row number of the candidate
     43        int nCol; //!< A zero-based column number of the candidate
     44
     45        //! Assigns default values
     46        TCandidate() {
     47                nCol = nRow = -1;
     48        }
     49        //! An operator == implementation
     50        bool operator ==(const TCandidate &cand) const {
     51                return ((cand.nRow == nRow) && (cand.nCol == nCol));
     52        }
     53};
    3754
    3855/*!
    … …  
    4158 *  A tree of such elements will represent the solving process.
    4259 */
    43 //! \todo TODO: List alternative candidates.
    44 struct sStep {
    45         tMatrix matrix; //!< This step's matrix
     60struct SStep {
     61        TMatrix matrix; //!< This step's matrix
    4662        double price; //!< The price of travel to this step
    47         struct {
    48                 int nRow; //!< A zero-based row number of the candidate
    49                 int nCol; //!< A zero-based column number of the candidate
    50         } candidate; //!< A candiadate for branching in the current matrix
    51         bool alts; //!< Indicates whether or not matrix has alternative candidates
    52         sStep *plNode; //!< Pointer to the left branch step
    53         sStep *prNode; //!< Pointer to the right branch step
     63        TCandidate candidate; //!< A candiadate for branching in the current matrix
     64        QList<TCandidate> alts; //!< A list of alternative branching candidates
     65        SStep *plNode; //!< Pointer to the left branch step
     66        SStep *prNode; //!< Pointer to the right branch step
    5467
    5568        //! Assigns default values
    56         sStep() {
    57                 price = candidate.nRow = candidate.nCol = -1;
    58                 alts = false;
     69        SStep() {
     70                price = -1;
    5971                plNode = prNode = NULL;
    6072        }
    … …  
    7688        static QString getVersionId();
    7789        bool isOptimal() const;
    78         sStep *solve(int numCities, tMatrix task, QWidget *parent = 0);
     90        SStep *solve(int numCities, TMatrix task, QWidget *parent = 0);
     91        ~CTSPSolver();
    7992
    8093private:
    8194        bool mayNotBeOptimal;
    8295        int nCities;
    83         sStep *root;
     96        SStep *root;
    8497        QHash<int,int> route;
    8598//      QHash<int,int> forbidden;
    8699
    87         double align(tMatrix &matrix);
     100        double align(TMatrix &matrix);
    88101        void cleanup();
    89         bool findCandidate(const tMatrix &matrix, int &nRow, int &nCol) const;
    90         double findMinInCol(int nCol, const tMatrix &matrix, int exr = -1) const;
    91         double findMinInRow(int nRow, const tMatrix &matrix, int exc = -1) const;
     102        void deleteNode(SStep *node);
     103        QList<TCandidate> findCandidate(const TMatrix &matrix, int &nRow, int &nCol) const;
     104        double findMinInCol(int nCol, const TMatrix &matrix, int exr = -1) const;
     105        double findMinInRow(int nRow, const TMatrix &matrix, int exc = -1) const;
    92106        bool hasSubCycles(int nRow, int nCol) const;
    93         void subCol(tMatrix &matrix, int nCol, double val);
    94         void subRow(tMatrix &matrix, int nRow, double val);
     107        void subCol(TMatrix &matrix, int nCol, double val);
     108        void subRow(TMatrix &matrix, int nRow, double val);
    95109};
    96110
Note: See TracChangeset for help on using the changeset viewer.