Changeset e0fcac5f2c in tspsg
- Timestamp:
- Oct 24, 2009, 3:37:48 PM (15 years ago)
- Branches:
- 0.1.3.145-beta1-symbian, 0.1.4.170-beta2-bb10, appveyor, imgbot, master, readme
- Children:
- 8af59c4aa3
- Parents:
- 85ad815b0b
- Location:
- src
- Files:
-
- 12 edited
Legend:
- Unmodified
- Added
- Removed
-
src/globals.h
r85ad815b0b re0fcac5f2c 1 /* 2 * TSPSG: TSP Solver and Generator3 * Copyright (C) 2007-2009 Lёppa <contacts[at]oleksii[dot]name>1 /*! 2 * \file globals.h 3 * \author Copyright (C) 2007-2009 Lёppa <contacts[at]oleksii[dot]name> 4 4 * 5 5 * $Id$ 6 6 * $URL$ 7 * 8 * \brief Contains TSPSG global defines. 9 * 10 * <b>TSPSG: TSP Solver and Generator</b> 7 11 * 8 12 * This file is part of TSPSG. … … 24 28 #ifndef GLOBALS_H 25 29 #define GLOBALS_H 26 27 /*!28 * \file globals.h29 * \brief This file contains TSPSG global defines.30 */31 30 32 31 // INCLUDES -
src/mainwindow.cpp
r85ad815b0b re0fcac5f2c 115 115 } 116 116 117 /*! 118 * \brief Handles Main Window close event. 119 * \param event Close event. 120 * 121 * Checks whether or not a current task was saved and asks for saving if not. 122 * Saves TSPSG settings. 123 */ 124 void MainWindow::closeEvent(QCloseEvent *event) 125 { 126 if (!maybeSave()) { 127 event->ignore(); 128 return; 129 } 130 settings->setValue("NumCities",spinCities->value()); 131 #ifndef Q_OS_WINCE 132 // Saving windows state 133 if (settings->value("SavePos",false).toBool()) { 134 settings->beginGroup("MainWindow"); 135 settings->setValue("Maximized",isMaximized()); 136 if (!isMaximized()) { 137 settings->setValue("Size",size()); 138 settings->setValue("Position",pos()); 139 } 140 settings->endGroup(); 141 } 142 #endif // Q_OS_WINCE 143 QMainWindow::closeEvent(event); 144 } 145 146 /* Privates **********************************************************/ 147 148 void MainWindow::actionFileNewTriggered() 149 { 150 if (!maybeSave()) 151 return; 152 QApplication::setOverrideCursor(QCursor(Qt::WaitCursor)); 153 tspmodel->clear(); 154 setFileName(); 155 setWindowModified(false); 156 tabWidget->setCurrentIndex(0); 157 solutionText->clear(); 158 enableSolutionActions(false); 159 QApplication::restoreOverrideCursor(); 160 } 161 162 void MainWindow::actionFileOpenTriggered() 163 { 164 if (!maybeSave()) 165 return; 166 QFileDialog od(this); 167 od.setAcceptMode(QFileDialog::AcceptOpen); 168 od.setFileMode(QFileDialog::ExistingFile); 169 QStringList filters(trUtf8("All Supported Formats") + " (*.tspt *.zkt)"); 170 filters.append(trUtf8("%1 Task Files").arg("TSPSG") + " (*.tspt)"); 171 filters.append(trUtf8("%1 Task Files").arg("ZKomModRd") + " (*.zkt)"); 172 filters.append(trUtf8("All Files") + " (*)"); 173 od.setNameFilters(filters); 174 if (od.exec() != QDialog::Accepted) 175 return; 176 QStringList files = od.selectedFiles(); 177 if (files.empty()) 178 return; 179 if (!tspmodel->loadTask(files.first())) 180 return; 181 setFileName(files.first()); 182 tabWidget->setCurrentIndex(0); 183 setWindowModified(false); 184 solutionText->clear(); 185 enableSolutionActions(false); 186 } 187 188 void MainWindow::actionFileSaveTriggered() 189 { 190 if ((fileName == trUtf8("Untitled") + ".tspt") || (!fileName.endsWith(".tspt",Qt::CaseInsensitive))) 191 saveTask(); 192 else 193 if (tspmodel->saveTask(fileName)) 194 setWindowModified(false); 195 } 196 197 void MainWindow::actionFileSaveAsTaskTriggered() 198 { 199 saveTask(); 200 } 201 202 void MainWindow::actionFileSaveAsSolutionTriggered() 203 { 204 static QString selectedFile; 205 if (selectedFile.isEmpty()) 206 #ifndef QT_NO_PRINTER 207 selectedFile = "solution.pdf"; 208 #else 209 selectedFile = "solution.html"; 210 #endif // QT_NO_PRINTER 211 QFileDialog sd(this); 212 sd.setAcceptMode(QFileDialog::AcceptSave); 213 QStringList filters; 214 #ifndef QT_NO_PRINTER 215 filters.append(trUtf8("PDF Files") + "(*.pdf)"); 216 #endif 217 filters.append(trUtf8("HTML Files") + " (*.html *.htm)"); 218 #if QT_VERSION >= 0x040500 219 filters.append(trUtf8("OpenDocument Files") + " (*.odt)"); 220 #endif // QT_VERSION >= 0x040500 221 filters.append(trUtf8("All Files") + " (*)"); 222 sd.setNameFilters(filters); 223 sd.selectFile(selectedFile); 224 if (sd.exec() != QDialog::Accepted) 225 return; 226 QStringList files = sd.selectedFiles(); 227 if (files.empty()) 228 return; 229 selectedFile = files.first(); 230 QApplication::setOverrideCursor(QCursor(Qt::WaitCursor)); 231 #ifndef QT_NO_PRINTER 232 if (selectedFile.endsWith(".pdf",Qt::CaseInsensitive)) { 233 QPrinter printer(QPrinter::HighResolution); 234 printer.setOutputFormat(QPrinter::PdfFormat); 235 printer.setOutputFileName(selectedFile); 236 solutionText->document()->print(&printer); 237 QApplication::restoreOverrideCursor(); 238 return; 239 } 240 #endif 241 #if QT_VERSION >= 0x040500 242 QTextDocumentWriter dw(selectedFile); 243 if (!(selectedFile.endsWith(".htm",Qt::CaseInsensitive) || selectedFile.endsWith(".html",Qt::CaseInsensitive) || selectedFile.endsWith(".odt",Qt::CaseInsensitive) || selectedFile.endsWith(".txt",Qt::CaseInsensitive))) 244 dw.setFormat("plaintext"); 245 dw.write(solutionText->document()); 246 #else 247 // Qt < 4.5 has no QTextDocumentWriter class 248 QFile file(selectedFile); 249 if (!file.open(QFile::WriteOnly)) { 250 QApplication::restoreOverrideCursor(); 251 return; 252 } 253 QTextStream ts(&file); 254 ts.setCodec(QTextCodec::codecForName("UTF-8")); 255 ts << solutionText->document()->toHtml("UTF-8"); 256 file.close(); 257 #endif // QT_VERSION >= 0x040500 258 QApplication::restoreOverrideCursor(); 259 } 260 261 #ifndef QT_NO_PRINTER 262 void MainWindow::actionFilePrintPreviewTriggered() 263 { 264 QPrintPreviewDialog ppd(printer, this); 265 connect(&ppd,SIGNAL(paintRequested(QPrinter *)),SLOT(printPreview(QPrinter *))); 266 ppd.exec(); 267 } 268 269 void MainWindow::actionFilePrintTriggered() 270 { 271 QPrintDialog pd(printer,this); 272 #if QT_VERSION >= 0x040500 273 // No such methods in Qt < 4.5 274 pd.setOption(QAbstractPrintDialog::PrintSelection,false); 275 pd.setOption(QAbstractPrintDialog::PrintPageRange,false); 276 #endif 277 if (pd.exec() != QDialog::Accepted) 278 return; 279 QApplication::setOverrideCursor(QCursor(Qt::WaitCursor)); 280 solutionText->document()->print(printer); 281 QApplication::restoreOverrideCursor(); 282 } 283 #endif // QT_NO_PRINTER 284 285 void MainWindow::actionSettingsPreferencesTriggered() 286 { 287 SettingsDialog sd(this); 288 if (sd.exec() != QDialog::Accepted) 289 return; 290 if (sd.colorChanged() || sd.fontChanged()) { 291 initDocStyleSheet(); 292 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)) { 293 QApplication::setOverrideCursor(QCursor(Qt::WaitCursor)); 294 solutionText->clear(); 295 solutionText->setHtml(output.join("")); 296 QApplication::restoreOverrideCursor(); 297 } 298 } 299 } 300 301 void MainWindow::actionSettingsLanguageAutodetectTriggered(bool checked) 302 { 303 if (checked) { 304 settings->remove("Language"); 305 QMessageBox(QMessageBox::Information,trUtf8("Language change"),trUtf8("Language will be autodetected on next application start."),QMessageBox::Ok,this).exec(); 306 } else 307 settings->setValue("Language",groupSettingsLanguageList->checkedAction()->data().toString()); 308 } 309 310 void MainWindow::groupSettingsLanguageListTriggered(QAction *action) 311 { 312 if (actionSettingsLanguageAutodetect->isChecked()) { 313 // We have language autodetection. It needs to be disabled to change language. 314 if (QMessageBox(QMessageBox::Question,trUtf8("Language change"),trUtf8("You have language autodetection turned on.\nIt needs to be off.\nDo you wish to turn it off?"),QMessageBox::Yes | QMessageBox::No,this).exec() == QMessageBox::Yes) { 315 actionSettingsLanguageAutodetect->trigger(); 316 } else 317 return; 318 } 319 bool untitled = (fileName == trUtf8("Untitled") + ".tspt"); 320 if (loadLanguage(action->data().toString())) { 321 settings->setValue("Language",action->data().toString()); 322 retranslateUi(this); 323 if (untitled) 324 setFileName(); 325 } 326 } 327 328 void MainWindow::actionHelpAboutTriggered() 329 { 330 //! \todo TODO: Normal about window :-) 331 QString about = QString::fromUtf8("TSPSG: TSP Solver and Generator\n"); 332 about += QString::fromUtf8(" Version: "BUILD_VERSION"\n"); 333 about += QString::fromUtf8(" Copyright (C) 2007-%1 Lёppa <contacts[at]oleksii[dot]name>\n").arg(QDate::currentDate().toString("yyyy")); 334 about += QString::fromUtf8("Target OS: %1\n").arg(OS); 335 about += "Qt library:\n"; 336 about += QString::fromUtf8(" Compile time: %1\n").arg(QT_VERSION_STR); 337 about += QString::fromUtf8(" Runtime: %1\n").arg(qVersion()); 338 about += QString::fromUtf8("Built on %1 at %2\n").arg(__DATE__).arg(__TIME__); 339 about += QString::fromUtf8(VERSIONID"\n\n"); 340 about += QString::fromUtf8("Algorithm: %1\n").arg(CTSPSolver::getVersionId()); 341 about += "\n"; 342 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."; 343 QMessageBox(QMessageBox::Information,"About",about,QMessageBox::Ok,this).exec(); 344 } 345 346 void MainWindow::buttonBackToTaskClicked() 347 { 348 tabWidget->setCurrentIndex(0); 349 } 350 351 void MainWindow::buttonRandomClicked() 352 { 353 QApplication::setOverrideCursor(QCursor(Qt::WaitCursor)); 354 tspmodel->randomize(); 355 QApplication::restoreOverrideCursor(); 356 } 357 358 void MainWindow::buttonSolveClicked() 359 { 360 tMatrix matrix; 361 QList<double> row; 362 int n = spinCities->value(); 363 bool ok; 364 for (int r = 0; r < n; r++) { 365 row.clear(); 366 for (int c = 0; c < n; c++) { 367 row.append(tspmodel->index(r,c).data(Qt::UserRole).toDouble(&ok)); 368 if (!ok) { 369 QMessageBox(QMessageBox::Critical,trUtf8("Data error"),trUtf8("Error in cell [Row %1; Column %2]: Invalid data format.").arg(r + 1).arg(c + 1),QMessageBox::Ok,this).exec(); 370 return; 371 } 372 } 373 matrix.append(row); 374 } 375 CTSPSolver solver; 376 sStep *root = solver.solve(n,matrix,this); 377 if (!root) 378 return; 379 QApplication::setOverrideCursor(QCursor(Qt::WaitCursor)); 380 QColor color = settings->value("Output/Color",DEF_FONT_COLOR).value<QColor>(); 381 output.clear(); 382 output.append("<p>" + trUtf8("Variant #%1").arg(spinVariant->value()) + "</p>"); 383 output.append("<p>" + trUtf8("Task:") + "</p>"); 384 outputMatrix(matrix,output); 385 output.append("<hr>"); 386 output.append("<p>" + trUtf8("Solution of Variant #%1 task").arg(spinVariant->value()) + "</p>"); 387 sStep *step = root; 388 n = 1; 389 while (n <= spinCities->value()) { 390 if (step->prNode->prNode != NULL || (step->prNode->prNode == NULL && step->plNode->prNode == NULL)) { 391 if (n != spinCities->value()) { 392 output.append("<p>" + trUtf8("Step #%1").arg(n++) + "</p>"); 393 outputMatrix(step->matrix,output,step->candidate.nRow,step->candidate.nCol); 394 if (step->alts) 395 output.append("<p class=\"hasalts\">" + trUtf8("This step has alternate candidates for branching.") + "</p>"); 396 output.append("<p> </p>"); 397 } 398 } 399 if (step->prNode->prNode != NULL) 400 step = step->prNode; 401 else if (step->plNode->prNode != NULL) 402 step = step->plNode; 403 else 404 break; 405 } 406 if (solver.isOptimal()) 407 output.append("<p>" + trUtf8("Optimal path:") + "</p>"); 408 else 409 output.append("<p>" + trUtf8("Resulting path:") + "</p>"); 410 output.append("<p> " + solver.getSortedPath() + "</p>"); 411 output.append("<p>" + trUtf8("The price is <b>%1</b> units.").arg(step->price) + "</p>"); 412 if (!solver.isOptimal()) { 413 output.append("<p> </p>"); 414 output.append("<p>" + trUtf8("<b>WARNING!!!</b><br>This result is a record, but it may not be optimal.<br>Iterations need to be continued to check whether this result is optimal or get an optimal one.") + "</p>"); 415 } 416 output.append("<p></p>"); 417 solutionText->setHtml(output.join("")); 418 solutionText->setDocumentTitle(trUtf8("Solution of Variant #%1 task").arg(spinVariant->value())); 419 420 // Scrolling to the end of text. 421 QTextCursor cursor(solutionText->textCursor()); 422 cursor.movePosition(QTextCursor::End, QTextCursor::MoveAnchor); 423 solutionText->setTextCursor(cursor); 424 425 enableSolutionActions(); 426 tabWidget->setCurrentIndex(1); 427 QApplication::restoreOverrideCursor(); 428 } 429 430 void MainWindow::dataChanged() 431 { 432 setWindowModified(true); 433 } 434 435 void MainWindow::dataChanged(const QModelIndex &tl, const QModelIndex &br) 436 { 437 setWindowModified(true); 438 if (settings->value("Autosize",true).toBool()) { 439 for (int k = tl.row(); k <= br.row(); k++) 440 taskView->resizeRowToContents(k); 441 for (int k = tl.column(); k <= br.column(); k++) 442 taskView->resizeColumnToContents(k); 443 } 444 } 445 446 void MainWindow::numCitiesChanged(int nCities) 447 { 448 blockSignals(true); 449 spinCities->setValue(nCities); 450 blockSignals(false); 451 } 452 453 #ifndef QT_NO_PRINTER 454 void MainWindow::printPreview(QPrinter *printer) 455 { 456 solutionText->print(printer); 457 } 458 #endif // QT_NO_PRINTER 459 460 void MainWindow::spinCitiesValueChanged(int n) 461 { 462 int count = tspmodel->numCities(); 463 tspmodel->setNumCities(n); 464 if ((n > count) && settings->value("Autosize",true).toBool()) 465 for (int k = count; k < n; k++) { 466 taskView->resizeColumnToContents(k); 467 taskView->resizeRowToContents(k); 468 } 469 } 470 117 471 void MainWindow::enableSolutionActions(bool enable) 118 472 { … … 126 480 actionFilePrintPreview->setEnabled(enable); 127 481 #endif // QT_NO_PRINTER 482 } 483 484 void MainWindow::initDocStyleSheet() 485 { 486 QColor color = settings->value("Output/Color",DEF_FONT_COLOR).value<QColor>(); 487 QColor hilight; 488 if (color.value() < 192) 489 hilight.setHsv(color.hue(),color.saturation(),127 + qRound(color.value() / 2)); 490 else 491 hilight.setHsv(color.hue(),color.saturation(),color.value() / 2); 492 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;}"); 493 solutionText->document()->setDefaultFont(settings->value("Output/Font",QFont(DEF_FONT_FAMILY,DEF_FONT_SIZE)).value<QFont>()); 494 } 495 496 void MainWindow::loadLangList() 497 { 498 QSettings langinfo(PATH_I18N"/languages.ini",QSettings::IniFormat); 499 #if QT_VERSION >= 0x040500 500 // In Qt < 4.5 QSettings doesn't have method setIniCodec. 501 langinfo.setIniCodec("UTF-8"); 502 #endif 503 QDir dir(PATH_I18N,"*.qm",QDir::Name | QDir::IgnoreCase,QDir::Files); 504 if (!dir.exists()) 505 return; 506 QFileInfoList langs = dir.entryInfoList(); 507 if (langs.size() <= 0) 508 return; 509 QAction *a; 510 for (int k = 0; k < langs.size(); k++) { 511 QFileInfo lang = langs.at(k); 512 if (!lang.completeBaseName().startsWith("qt_") && lang.completeBaseName().compare("en")) { 513 #if QT_VERSION >= 0x040500 514 a = menuSettingsLanguage->addAction(langinfo.value(lang.completeBaseName() + "/NativeName",lang.completeBaseName()).toString()); 515 #else 516 // We use Name if Qt < 4.5 because NativeName is in UTF-8, QSettings 517 // reads .ini file as ASCII and there is no way to set file encoding. 518 a = menuSettingsLanguage->addAction(langinfo.value(lang.completeBaseName() + "/Name",lang.completeBaseName()).toString()); 519 #endif 520 a->setData(lang.completeBaseName()); 521 a->setCheckable(true); 522 a->setActionGroup(groupSettingsLanguageList); 523 if (settings->value("Language",QLocale::system().name()).toString().startsWith(lang.completeBaseName())) 524 a->setChecked(true); 525 } 526 } 128 527 } 129 528 … … 176 575 } 177 576 178 void MainWindow::initDocStyleSheet()179 {180 QColor color = settings->value("Output/Color",DEF_FONT_COLOR).value<QColor>();181 QColor hilight;182 if (color.value() < 192)183 hilight.setHsv(color.hue(),color.saturation(),127 + qRound(color.value() / 2));184 else185 hilight.setHsv(color.hue(),color.saturation(),color.value() / 2);186 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;}");187 solutionText->document()->setDefaultFont(settings->value("Output/Font",QFont(DEF_FONT_FAMILY,DEF_FONT_SIZE)).value<QFont>());188 }189 190 void MainWindow::setFileName(QString fileName)191 {192 this->fileName = fileName;193 setWindowTitle(QString("%1[*] - %2").arg(QFileInfo(fileName).completeBaseName()).arg(trUtf8("Travelling Salesman Problem")));194 }195 196 void MainWindow::spinCitiesValueChanged(int n)197 {198 int count = tspmodel->numCities();199 tspmodel->setNumCities(n);200 if ((n > count) && settings->value("Autosize",true).toBool())201 for (int k = count; k < n; k++) {202 taskView->resizeColumnToContents(k);203 taskView->resizeRowToContents(k);204 }205 }206 207 577 bool MainWindow::maybeSave() 208 578 { … … 218 588 } 219 589 220 void MainWindow::actionFileNewTriggered() 221 { 222 if (!maybeSave()) 223 return; 224 QApplication::setOverrideCursor(QCursor(Qt::WaitCursor)); 225 tspmodel->clear(); 226 setFileName(); 227 setWindowModified(false); 228 tabWidget->setCurrentIndex(0); 229 solutionText->clear(); 230 enableSolutionActions(false); 231 QApplication::restoreOverrideCursor(); 232 } 233 234 void MainWindow::actionFileOpenTriggered() 235 { 236 if (!maybeSave()) 237 return; 238 QFileDialog od(this); 239 od.setAcceptMode(QFileDialog::AcceptOpen); 240 od.setFileMode(QFileDialog::ExistingFile); 241 QStringList filters(trUtf8("All Supported Formats") + " (*.tspt *.zkt)"); 242 filters.append(trUtf8("%1 Task Files").arg("TSPSG") + " (*.tspt)"); 243 filters.append(trUtf8("%1 Task Files").arg("ZKomModRd") + " (*.zkt)"); 244 filters.append(trUtf8("All Files") + " (*)"); 245 od.setNameFilters(filters); 246 if (od.exec() != QDialog::Accepted) 247 return; 248 QStringList files = od.selectedFiles(); 249 if (files.empty()) 250 return; 251 if (!tspmodel->loadTask(files.first())) 252 return; 253 setFileName(files.first()); 254 tabWidget->setCurrentIndex(0); 255 setWindowModified(false); 256 solutionText->clear(); 257 enableSolutionActions(false); 258 } 259 260 void MainWindow::actionFileSaveTriggered() 261 { 262 if ((fileName == trUtf8("Untitled") + ".tspt") || (!fileName.endsWith(".tspt",Qt::CaseInsensitive))) 263 saveTask(); 264 else 265 if (tspmodel->saveTask(fileName)) 266 setWindowModified(false); 267 } 268 269 void MainWindow::actionFileSaveAsTaskTriggered() 270 { 271 saveTask(); 272 } 273 274 void MainWindow::actionFileSaveAsSolutionTriggered() 275 { 276 static QString selectedFile; 277 if (selectedFile.isEmpty()) 278 #ifndef QT_NO_PRINTER 279 selectedFile = "solution.pdf"; 280 #else 281 selectedFile = "solution.html"; 282 #endif // QT_NO_PRINTER 283 QFileDialog sd(this); 284 sd.setAcceptMode(QFileDialog::AcceptSave); 285 QStringList filters; 286 #ifndef QT_NO_PRINTER 287 filters.append(trUtf8("PDF Files") + "(*.pdf)"); 288 #endif 289 filters.append(trUtf8("HTML Files") + " (*.html *.htm)"); 290 #if QT_VERSION >= 0x040500 291 filters.append(trUtf8("OpenDocument Files") + " (*.odt)"); 292 #endif // QT_VERSION >= 0x040500 293 filters.append(trUtf8("All Files") + " (*)"); 294 sd.setNameFilters(filters); 295 sd.selectFile(selectedFile); 296 if (sd.exec() != QDialog::Accepted) 297 return; 298 QStringList files = sd.selectedFiles(); 299 if (files.empty()) 300 return; 301 selectedFile = files.first(); 302 QApplication::setOverrideCursor(QCursor(Qt::WaitCursor)); 303 #ifndef QT_NO_PRINTER 304 if (selectedFile.endsWith(".pdf",Qt::CaseInsensitive)) { 305 QPrinter printer(QPrinter::HighResolution); 306 printer.setOutputFormat(QPrinter::PdfFormat); 307 printer.setOutputFileName(selectedFile); 308 solutionText->document()->print(&printer); 309 QApplication::restoreOverrideCursor(); 310 return; 311 } 312 #endif 313 #if QT_VERSION >= 0x040500 314 QTextDocumentWriter dw(selectedFile); 315 if (!(selectedFile.endsWith(".htm",Qt::CaseInsensitive) || selectedFile.endsWith(".html",Qt::CaseInsensitive) || selectedFile.endsWith(".odt",Qt::CaseInsensitive) || selectedFile.endsWith(".txt",Qt::CaseInsensitive))) 316 dw.setFormat("plaintext"); 317 dw.write(solutionText->document()); 318 #else 319 // Qt < 4.5 has no QTextDocumentWriter class 320 QFile file(selectedFile); 321 if (!file.open(QFile::WriteOnly)) { 322 QApplication::restoreOverrideCursor(); 323 return; 324 } 325 QTextStream ts(&file); 326 ts.setCodec(QTextCodec::codecForName("UTF-8")); 327 ts << solutionText->document()->toHtml("UTF-8"); 328 file.close(); 329 #endif // QT_VERSION >= 0x040500 330 QApplication::restoreOverrideCursor(); 590 void MainWindow::outputMatrix(tMatrix matrix, QStringList &output, int nRow, int nCol) 591 { 592 int n = spinCities->value(); 593 QString line=""; 594 output.append("<table border=\"0\" cellspacing=\"0\" cellpadding=\"0\">"); 595 for (int r = 0; r < n; r++) { 596 line = "<tr>"; 597 for (int c = 0; c < n; c++) { 598 if (matrix[r][c] == INFINITY) 599 line += "<td align=\"center\">"INFSTR"</td>"; 600 else if ((r == nRow) && (c == nCol)) 601 line += "<td align=\"center\" class=\"selected\">" + QVariant(matrix[r][c]).toString() + "</td>"; 602 else 603 line += "<td align=\"center\">" + QVariant(matrix[r][c]).toString() + "</td>"; 604 } 605 line += "</tr>"; 606 output.append(line); 607 } 608 output.append("</table>"); 331 609 } 332 610 … … 355 633 } 356 634 357 void MainWindow::actionSettingsPreferencesTriggered() 358 { 359 SettingsDialog sd(this); 360 if (sd.exec() != QDialog::Accepted) 361 return; 362 if (sd.colorChanged() || sd.fontChanged()) { 363 initDocStyleSheet(); 364 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)) { 365 QApplication::setOverrideCursor(QCursor(Qt::WaitCursor)); 366 solutionText->clear(); 367 solutionText->setHtml(output.join("")); 368 QApplication::restoreOverrideCursor(); 369 } 370 } 371 } 372 373 #ifndef QT_NO_PRINTER 374 void MainWindow::printPreview(QPrinter *printer) 375 { 376 solutionText->print(printer); 377 } 378 379 void MainWindow::actionFilePrintPreviewTriggered() 380 { 381 QPrintPreviewDialog ppd(printer, this); 382 connect(&ppd,SIGNAL(paintRequested(QPrinter *)),SLOT(printPreview(QPrinter *))); 383 ppd.exec(); 384 } 385 386 void MainWindow::actionFilePrintTriggered() 387 { 388 QPrintDialog pd(printer,this); 389 #if QT_VERSION >= 0x040500 390 // No such methods in Qt < 4.5 391 pd.setOption(QAbstractPrintDialog::PrintSelection,false); 392 pd.setOption(QAbstractPrintDialog::PrintPageRange,false); 393 #endif 394 if (pd.exec() != QDialog::Accepted) 395 return; 396 QApplication::setOverrideCursor(QCursor(Qt::WaitCursor)); 397 solutionText->document()->print(printer); 398 QApplication::restoreOverrideCursor(); 399 } 400 #endif // QT_NO_PRINTER 401 402 void MainWindow::buttonRandomClicked() 403 { 404 QApplication::setOverrideCursor(QCursor(Qt::WaitCursor)); 405 tspmodel->randomize(); 406 QApplication::restoreOverrideCursor(); 407 } 408 409 void MainWindow::buttonBackToTaskClicked() 410 { 411 tabWidget->setCurrentIndex(0); 412 } 413 414 void MainWindow::outputMatrix(tMatrix matrix, QStringList &output, int nRow, int nCol) 415 { 416 int n = spinCities->value(); 417 QString line=""; 418 output.append("<table border=\"0\" cellspacing=\"0\" cellpadding=\"0\">"); 419 for (int r = 0; r < n; r++) { 420 line = "<tr>"; 421 for (int c = 0; c < n; c++) { 422 if (matrix[r][c] == INFINITY) 423 line += "<td align=\"center\">"INFSTR"</td>"; 424 else if ((r == nRow) && (c == nCol)) 425 line += "<td align=\"center\" class=\"selected\">" + QVariant(matrix[r][c]).toString() + "</td>"; 426 else 427 line += "<td align=\"center\">" + QVariant(matrix[r][c]).toString() + "</td>"; 428 } 429 line += "</tr>"; 430 output.append(line); 431 } 432 output.append("</table>"); 433 } 434 435 void MainWindow::buttonSolveClicked() 436 { 437 tMatrix matrix; 438 QList<double> row; 439 int n = spinCities->value(); 440 bool ok; 441 for (int r = 0; r < n; r++) { 442 row.clear(); 443 for (int c = 0; c < n; c++) { 444 row.append(tspmodel->index(r,c).data(Qt::UserRole).toDouble(&ok)); 445 if (!ok) { 446 QMessageBox(QMessageBox::Critical,trUtf8("Data error"),trUtf8("Error in cell [Row %1; Column %2]: Invalid data format.").arg(r + 1).arg(c + 1),QMessageBox::Ok,this).exec(); 447 return; 448 } 449 } 450 matrix.append(row); 451 } 452 CTSPSolver solver; 453 sStep *root = solver.solve(n,matrix,this); 454 if (!root) 455 return; 456 QApplication::setOverrideCursor(QCursor(Qt::WaitCursor)); 457 QColor color = settings->value("Output/Color",DEF_FONT_COLOR).value<QColor>(); 458 output.clear(); 459 output.append("<p>" + trUtf8("Variant #%1").arg(spinVariant->value()) + "</p>"); 460 output.append("<p>" + trUtf8("Task:") + "</p>"); 461 outputMatrix(matrix,output); 462 output.append("<hr>"); 463 output.append("<p>" + trUtf8("Solution of Variant #%1 task").arg(spinVariant->value()) + "</p>"); 464 sStep *step = root; 465 n = 1; 466 while (n <= spinCities->value()) { 467 if (step->prNode->prNode != NULL || (step->prNode->prNode == NULL && step->plNode->prNode == NULL)) { 468 if (n != spinCities->value()) { 469 output.append("<p>" + trUtf8("Step #%1").arg(n++) + "</p>"); 470 outputMatrix(step->matrix,output,step->candidate.nRow,step->candidate.nCol); 471 if (step->alts) 472 output.append("<p class=\"hasalts\">" + trUtf8("This step has alternate candidates for branching.") + "</p>"); 473 output.append("<p> </p>"); 474 } 475 } 476 if (step->prNode->prNode != NULL) 477 step = step->prNode; 478 else if (step->plNode->prNode != NULL) 479 step = step->plNode; 480 else 481 break; 482 } 483 if (solver.isOptimal()) 484 output.append("<p>" + trUtf8("Optimal path:") + "</p>"); 485 else 486 output.append("<p>" + trUtf8("Resulting path:") + "</p>"); 487 output.append("<p> " + solver.getSortedPath() + "</p>"); 488 output.append("<p>" + trUtf8("The price is <b>%1</b> units.").arg(step->price) + "</p>"); 489 if (!solver.isOptimal()) { 490 output.append("<p> </p>"); 491 output.append("<p>" + trUtf8("<b>WARNING!!!</b><br>This result is a record, but it may not be optimal.<br>Iterations need to be continued to check whether this result is optimal or get an optimal one.") + "</p>"); 492 } 493 output.append("<p></p>"); 494 solutionText->setHtml(output.join("")); 495 solutionText->setDocumentTitle(trUtf8("Solution of Variant #%1 task").arg(spinVariant->value())); 496 497 // Scrolling to the end of text. 498 QTextCursor cursor(solutionText->textCursor()); 499 cursor.movePosition(QTextCursor::End, QTextCursor::MoveAnchor); 500 solutionText->setTextCursor(cursor); 501 502 enableSolutionActions(); 503 tabWidget->setCurrentIndex(1); 504 QApplication::restoreOverrideCursor(); 505 } 506 507 void MainWindow::actionHelpAboutTriggered() 508 { 509 //! \todo TODO: Normal about window :-) 510 QString about = QString::fromUtf8("TSPSG: TSP Solver and Generator\n"); 511 about += QString::fromUtf8(" Version: "BUILD_VERSION"\n"); 512 about += QString::fromUtf8(" Copyright (C) 2007-%1 Lёppa <contacts[at]oleksii[dot]name>\n").arg(QDate::currentDate().toString("yyyy")); 513 about += QString::fromUtf8("Target OS: %1\n").arg(OS); 514 about += "Qt library:\n"; 515 about += QString::fromUtf8(" Compile time: %1\n").arg(QT_VERSION_STR); 516 about += QString::fromUtf8(" Runtime: %1\n").arg(qVersion()); 517 about += QString::fromUtf8("Built on %1 at %2\n").arg(__DATE__).arg(__TIME__); 518 about += QString::fromUtf8(VERSIONID"\n\n"); 519 about += QString::fromUtf8("Algorithm: %1\n").arg(CTSPSolver::getVersionId()); 520 about += "\n"; 521 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."; 522 QMessageBox(QMessageBox::Information,"About",about,QMessageBox::Ok,this).exec(); 523 } 524 525 void MainWindow::loadLangList() 526 { 527 QSettings langinfo(PATH_I18N"/languages.ini",QSettings::IniFormat); 528 #if QT_VERSION >= 0x040500 529 // In Qt < 4.5 QSettings doesn't have method setIniCodec. 530 langinfo.setIniCodec("UTF-8"); 531 #endif 532 QDir dir(PATH_I18N,"*.qm",QDir::Name | QDir::IgnoreCase,QDir::Files); 533 if (!dir.exists()) 534 return; 535 QFileInfoList langs = dir.entryInfoList(); 536 if (langs.size() <= 0) 537 return; 538 QAction *a; 539 for (int k = 0; k < langs.size(); k++) { 540 QFileInfo lang = langs.at(k); 541 if (!lang.completeBaseName().startsWith("qt_") && lang.completeBaseName().compare("en")) { 542 #if QT_VERSION >= 0x040500 543 a = menuSettingsLanguage->addAction(langinfo.value(lang.completeBaseName() + "/NativeName",lang.completeBaseName()).toString()); 544 #else 545 // We use Name if Qt < 4.5 because NativeName is in UTF-8, QSettings 546 // reads .ini file as ASCII and there is no way to set file encoding. 547 a = menuSettingsLanguage->addAction(langinfo.value(lang.completeBaseName() + "/Name",lang.completeBaseName()).toString()); 548 #endif 549 a->setData(lang.completeBaseName()); 550 a->setCheckable(true); 551 a->setActionGroup(groupSettingsLanguageList); 552 if (settings->value("Language",QLocale::system().name()).toString().startsWith(lang.completeBaseName())) 553 a->setChecked(true); 554 } 555 } 556 } 557 558 void MainWindow::actionSettingsLanguageAutodetectTriggered(bool checked) 559 { 560 if (checked) { 561 settings->remove("Language"); 562 QMessageBox(QMessageBox::Information,trUtf8("Language change"),trUtf8("Language will be autodetected on next application start."),QMessageBox::Ok,this).exec(); 563 } else 564 settings->setValue("Language",groupSettingsLanguageList->checkedAction()->data().toString()); 565 } 566 567 void MainWindow::groupSettingsLanguageListTriggered(QAction *action) 568 { 569 if (actionSettingsLanguageAutodetect->isChecked()) { 570 // We have language autodetection. It needs to be disabled to change language. 571 if (QMessageBox(QMessageBox::Question,trUtf8("Language change"),trUtf8("You have language autodetection turned on.\nIt needs to be off.\nDo you wish to turn it off?"),QMessageBox::Yes | QMessageBox::No,this).exec() == QMessageBox::Yes) { 572 actionSettingsLanguageAutodetect->trigger(); 573 } else 574 return; 575 } 576 bool untitled = (fileName == trUtf8("Untitled") + ".tspt"); 577 if (loadLanguage(action->data().toString())) { 578 settings->setValue("Language",action->data().toString()); 579 retranslateUi(this); 580 if (untitled) 581 setFileName(); 582 } 583 } 584 585 /*! 586 * \brief Handles Main Window close event. 587 * \param event Close event. 588 * 589 * Checks whether or not a current task was saved and asks for saving if not. 590 * Saves TSPSG settings. 591 */ 592 void MainWindow::closeEvent(QCloseEvent *event) 593 { 594 if (!maybeSave()) { 595 event->ignore(); 596 return; 597 } 598 settings->setValue("NumCities",spinCities->value()); 599 #ifndef Q_OS_WINCE 600 // Saving windows state 601 if (settings->value("SavePos",false).toBool()) { 602 settings->beginGroup("MainWindow"); 603 settings->setValue("Maximized",isMaximized()); 604 if (!isMaximized()) { 605 settings->setValue("Size",size()); 606 settings->setValue("Position",pos()); 607 } 608 settings->endGroup(); 609 } 610 #endif // Q_OS_WINCE 611 QMainWindow::closeEvent(event); 612 } 613 614 void MainWindow::dataChanged() 615 { 616 setWindowModified(true); 617 } 618 619 void MainWindow::dataChanged(const QModelIndex &tl, const QModelIndex &br) 620 { 621 setWindowModified(true); 622 if (settings->value("Autosize",true).toBool()) { 623 for (int k = tl.row(); k <= br.row(); k++) 624 taskView->resizeRowToContents(k); 625 for (int k = tl.column(); k <= br.column(); k++) 626 taskView->resizeColumnToContents(k); 627 } 628 } 629 630 void MainWindow::numCitiesChanged(int nCities) 631 { 632 blockSignals(true); 633 spinCities->setValue(nCities); 634 blockSignals(false); 635 } 635 void MainWindow::setFileName(QString fileName) 636 { 637 this->fileName = fileName; 638 setWindowTitle(QString("%1[*] - %2").arg(QFileInfo(fileName).completeBaseName()).arg(trUtf8("Travelling Salesman Problem"))); 639 } -
src/mainwindow.h
r85ad815b0b re0fcac5f2c 1 1 /*! 2 * \class MainWindow 3 * \brief Class for handling Main Window UI and logic. 2 * \file mainwindow.h 4 3 * \author Copyright © 2007-2009 Lёppa <contacts[at]oleksii[dot]name> 5 4 * 6 5 * $Id$ 7 6 * $URL$ 7 * 8 * \brief Defines MainWindow class. 8 9 * 9 10 * <b>TSPSG: TSP Solver and Generator</b> … … 28 29 #define MAINWINDOW_H 29 30 30 /*!31 * \file mainwindow.h32 * \brief Defines MainWindow class.33 */34 35 31 #include "globals.h" 36 32 … … 41 37 #include "tspmodel.h" 42 38 39 /*! 40 * \brief Class for handling Main Window UI and logic. 41 * \author Copyright © 2007-2009 Lёppa <contacts[at]oleksii[dot]name> 42 */ 43 43 class MainWindow: public QMainWindow, Ui::MainWindow 44 44 { … … 50 50 51 51 private slots: 52 // Actions 52 53 void actionFileNewTriggered(); 53 54 void actionFileOpenTriggered(); … … 55 56 void actionFileSaveAsTaskTriggered(); 56 57 void actionFileSaveAsSolutionTriggered(); 58 #ifndef QT_NO_PRINTER 59 void actionFilePrintPreviewTriggered(); 60 void actionFilePrintTriggered(); 61 #endif // QT_NO_PRINTER 57 62 void actionSettingsPreferencesTriggered(); 58 63 void actionSettingsLanguageAutodetectTriggered(bool); 59 64 void groupSettingsLanguageListTriggered(QAction *); 60 65 void actionHelpAboutTriggered(); 66 // Buttons 67 void buttonBackToTaskClicked(); 68 void buttonRandomClicked(); 69 void buttonSolveClicked(); 70 61 71 void dataChanged(); 62 72 void dataChanged(const QModelIndex &, const QModelIndex &); 73 void numCitiesChanged(int); 63 74 #ifndef QT_NO_PRINTER 64 75 void printPreview(QPrinter *printer); 65 void actionFilePrintPreviewTriggered();66 void actionFilePrintTriggered();67 76 #endif // QT_NO_PRINTER 68 void buttonSolveClicked();69 void buttonRandomClicked();70 void buttonBackToTaskClicked();71 77 void spinCitiesValueChanged(int); 72 void numCitiesChanged(int);73 78 74 79 private: 75 QSettings *settings; 80 QString fileName; 81 QActionGroup *groupSettingsLanguageList; 82 QStringList output; 76 83 #ifndef QT_NO_PRINTER 77 84 QPrinter *printer; 78 85 #endif // QT_NO_PRINTER 86 QSettings *settings; 79 87 CTSPModel *tspmodel; 80 QString fileName; 81 QActionGroup *groupSettingsLanguageList; 82 QStringList output; 88 83 89 void enableSolutionActions(bool enable = true); 84 90 void initDocStyleSheet(); 91 void loadLangList(); 85 92 bool loadLanguage(QString lang = ""); 86 void loadLangList();87 93 bool maybeSave(); 88 94 void outputMatrix(tMatrix, QStringList &, int nRow = -1, int nCol = -1); 95 bool saveTask(); 89 96 void setFileName(QString fileName = trUtf8("Untitled") + ".tspt"); 90 bool saveTask();91 97 }; 92 98 -
src/os.h
r85ad815b0b re0fcac5f2c 1 /* 2 * TSPSG: TSP Solver and Generator3 * Copyright (C) 2007-2009 Lёppa <contacts[at]oleksii[dot]name>1 /*! 2 * \file os.h 3 * \author Copyright (C) 2007-2009 Lёppa <contacts[at]oleksii[dot]name> 4 4 * 5 5 * $Id$ 6 6 * $URL$ 7 * 8 * \warning Arch detection works only for <b>GNU C</b>, <b>Visual Studio</b>, <b>Intel C/C++</b> and <b>MinGW32</b> compilers. 9 * OS detection should work for any compiler. 10 * 11 * \brief Contains TSPSG target CPU architecture and OS detection. 12 * 13 * <b>TSPSG: TSP Solver and Generator</b> 7 14 * 8 15 * This file is part of TSPSG. … … 24 31 #ifndef OS_H 25 32 #define OS_H 26 27 /*!28 * \file os.h29 * \brief This file contains TSPSG target CPU architecture and OS detection.30 *31 * Arch detection works only for <b>GNU C</b>, <b>Visual Studio</b>, <b>Intel C/C++</b> and <b>MinGW32</b> compilers.32 *33 * OS detection should work for any compiler.34 */35 33 36 34 // Some target arch detection. -
src/resource.h
r85ad815b0b re0fcac5f2c 1 /* 2 * TSPSG: TSP Solver and Generator3 * Copyright (C) 2007-2009 Lёppa <contacts[at]oleksii[dot]name>1 /*! 2 * \file resource.h 3 * \author Copyright (C) 2007-2009 Lёppa <contacts[at]oleksii[dot]name> 4 4 * 5 5 * $Id$ 6 6 * $URL$ 7 7 * 8 * \brief Contains windows resource IDs. 9 * 10 * <b>TSPSG: TSP Solver and Generator</b> 11 * 8 12 * This file is part of TSPSG. 9 13 * … … 24 28 #include "version.h" 25 29 26 /*!27 * \file resource.h28 * \brief This file contains windows resource IDs.29 */30 31 30 //! Version information resource ID 32 31 #define VS_VERSION_INFO 1 -
src/settingsdialog.cpp
r85ad815b0b re0fcac5f2c 188 188 } 189 189 190 /*! 191 * \brief Indicates whether or not the font color has been changed. 192 * \return \c true if font color changed, otherwise \c false. 193 */ 194 bool SettingsDialog::colorChanged() const 195 { 196 return newColor; 197 } 198 199 /*! 200 * \brief Indicates whether or not the font properties have been changed. 201 * \return \c true if font properties changed, otherwise \c false. 202 */ 203 bool SettingsDialog::fontChanged() const 204 { 205 return newFont; 206 } 207 208 /* Privates **********************************************************/ 209 190 210 void SettingsDialog::accept() 191 211 { … … 205 225 } 206 226 227 void SettingsDialog::buttonColorClicked() 228 { 229 QColor color = QColorDialog::getColor(this->color,this); 230 if (color.isValid() && (this->color != color)) { 231 this->color = color; 232 newColor = true; 233 } 234 } 235 207 236 void SettingsDialog::buttonFontClicked() 208 237 { … … 213 242 newFont = true; 214 243 } 215 }216 217 void SettingsDialog::buttonColorClicked()218 {219 QColor color = QColorDialog::getColor(this->color,this);220 if (color.isValid() && (this->color != color)) {221 this->color = color;222 newColor = true;223 }224 }225 226 /*!227 * \brief Indicates whether or not the font color has been changed.228 * \return \c true if font color changed, otherwise \c false.229 */230 bool SettingsDialog::colorChanged() const231 {232 return newColor;233 }234 235 /*!236 * \brief Indicates whether or not the font properties have been changed.237 * \return \c true if font properties changed, otherwise \c false.238 */239 bool SettingsDialog::fontChanged() const240 {241 return newFont;242 244 } 243 245 -
src/settingsdialog.h
r85ad815b0b re0fcac5f2c 1 1 /*! 2 * \class SettingsDialog 3 * \brief Class for handling Settings Dialog UI and logic. 2 * \file settingsdialog.h 4 3 * \author Copyright © 2007-2009 Lёppa <contacts[at]oleksii[dot]name> 5 4 * 6 5 * $Id$ 7 6 * $URL$ 7 * 8 * \brief Defines SettingsDialog class. 8 9 * 9 10 * <b>TSPSG: TSP Solver and Generator</b> … … 28 29 #define SETTINGSDIALOG_H 29 30 30 /*!31 * \file settingsdialog.h32 * \brief Defines SettingsDialog class.33 */34 35 31 #include "globals.h" 36 32 37 33 #include "ui_settingsdialog.h" 38 34 35 /*! 36 * \brief Class for handling Settings Dialog UI and logic. 37 * \author Copyright © 2007-2009 Lёppa <contacts[at]oleksii[dot]name> 38 */ 39 39 class SettingsDialog: public QDialog, Ui::SettingsDialog 40 40 { … … 52 52 QSettings *settings; 53 53 #ifndef Q_OS_WINCE 54 bool event(QEvent *);55 56 54 QCheckBox *cbSaveState; 57 55 QLabel *imgIcon; 58 56 QLabel *labelHint; 59 57 QFrame *lineVertical; 58 59 bool event(QEvent *); 60 60 #endif // Q_OS_WINCE 61 61 -
src/tspmodel.cpp
r85ad815b0b re0fcac5f2c 24 24 #include "tspmodel.h" 25 25 26 /*! 27 * \brief Class constructor. 28 * \param parent The parent of the table model. 29 */ 26 30 CTSPModel::CTSPModel(QObject *parent) 27 31 : QAbstractTableModel(parent), nCities(0) … … 30 34 } 31 35 32 inline int CTSPModel::rand(int min, int max) const 33 { 34 return min + (int)(((float)qrand() / RAND_MAX) * max); 35 } 36 37 int CTSPModel::rowCount(const QModelIndex &) const 36 /*! 37 * \brief Resets the table, setting all its elements to 0. 38 * 39 * \sa randomize() 40 */ 41 void CTSPModel::clear() 42 { 43 for (int r = 0; r < nCities; r++) 44 for (int c = 0; c < nCities; c++) 45 if (r != c) 46 table[r][c] = 0; 47 emit dataChanged(index(0,0),index(nCities - 1,nCities - 1)); 48 } 49 50 /*! 51 * \brief Returns the column count in the table. 52 * \return Number of columns in the table. 53 * 54 * Actually, this function returns the number of cities in the current task. 55 * 56 * \sa numCities(), rowCount() 57 */ 58 int CTSPModel::columnCount(const QModelIndex &) const 38 59 { 39 60 return nCities; 40 61 } 41 62 42 int CTSPModel::columnCount(const QModelIndex &) const 43 { 44 return nCities; 45 } 46 47 QVariant CTSPModel::headerData(int section, Qt::Orientation orientation, int role) const 48 { 49 if (role == Qt::DisplayRole) { 50 if (orientation == Qt::Vertical) 51 return trUtf8("City %1").arg(section + 1); 52 else 53 return trUtf8("%1").arg(section + 1); 54 } 55 return QVariant(); 56 } 57 63 /*! 64 * \brief Returns the data stored under the given \a role for the item referred to by the \a index. 65 * \param index An item index to get data from. 66 * \param role The role to get data for. 67 * \return Corresponding data. 68 * 69 * \sa setData(), headerData() 70 */ 58 71 QVariant CTSPModel::data(const QModelIndex &index, int role) const 59 72 { … … 71 84 return trUtf8(INFSTR); 72 85 else 73 //HACK: Converting to string to prevent spinbox in edit mode86 //! \hack HACK: Converting to string to prevent spinbox in edit mode 74 87 return QVariant(table[index.row()][index.column()]).toString(); 75 88 else … … 80 93 } 81 94 95 /*! 96 * \brief Returns the item flags for the given \a index. 97 * \param index An item index to get flags from. 98 * \return Corresponding item flags. 99 */ 100 Qt::ItemFlags CTSPModel::flags(const QModelIndex &index) const 101 { 102 Qt::ItemFlags flags = QAbstractItemModel::flags(index); 103 if (index.row() != index.column()) 104 flags |= Qt::ItemIsEditable; 105 return flags; 106 } 107 108 /*! 109 * \brief Returns the data for the given \a role and \a section in the header with the specified \a orientation. 110 * \param section The section to get header data for. 111 * \param orientation The orientation to get header data for. 112 * \param role The role to get header data for. 113 * \return Corresponding header data. 114 * 115 * For horizontal headers, the section number corresponds to the column number of items shown beneath it. For vertical headers, the section number typically to the row number of items shown alongside it. 116 */ 117 QVariant CTSPModel::headerData(int section, Qt::Orientation orientation, int role) const 118 { 119 if (role == Qt::DisplayRole) { 120 if (orientation == Qt::Vertical) 121 return trUtf8("City %1").arg(section + 1); 122 else 123 return trUtf8("%1").arg(section + 1); 124 } 125 return QVariant(); 126 } 127 128 /*! 129 * \brief Loads a task from \a fname. 130 * \param fname The name of the file to be loaded. 131 * \return \c true on success, otherwise \c false. 132 * 133 * \sa saveTask() 134 */ 135 bool CTSPModel::loadTask(QString fname) 136 { 137 QApplication::setOverrideCursor(QCursor(Qt::WaitCursor)); 138 QFile f(fname); 139 if (!f.open(QIODevice::ReadOnly)) { 140 QApplication::restoreOverrideCursor(); 141 QMessageBox(QMessageBox::Critical,trUtf8("Task Load"),QString(trUtf8("Unable to open task file.\nError: %1")).arg(f.errorString()),QMessageBox::Ok).exec(); 142 return false; 143 } 144 QDataStream ds(&f); 145 ds.setVersion(QDataStream::Qt_4_4); 146 quint32 sig; 147 ds >> sig; 148 if (loadError(ds.status())) { 149 return false; 150 } 151 ds.device()->reset(); 152 if (sig == TSPT) { 153 if (!loadTSPT(&ds)) { 154 f.close(); 155 return false; 156 } 157 } else if ((sig >> 16) == ZKT) { 158 if (!loadZKT(&ds)) { 159 f.close(); 160 return false; 161 } 162 } else { 163 f.close(); 164 QApplication::restoreOverrideCursor(); 165 QMessageBox(QMessageBox::Critical,trUtf8("Task Load"),trUtf8("Unable to load task:") + "\n" + trUtf8("Unknown file format or file is corrupted."),QMessageBox::Ok).exec(); 166 return false; 167 } 168 f.close(); 169 QApplication::restoreOverrideCursor(); 170 return true; 171 } 172 173 /*! 174 * \brief Returns the number of cities. 175 * \return Number of cities in the current task. 176 * 177 * \sa columnCount(), rowCount(), setNumCities() 178 */ 179 quint16 CTSPModel::numCities() const 180 { 181 return nCities; 182 } 183 184 /*! 185 * \brief Randomizes the table by setting all its values to random ones. 186 * 187 * Uses TSPSG settings to determine random values range. 188 * 189 * \sa clear() 190 */ 191 void CTSPModel::randomize() 192 { 193 int randMin = settings->value("MinCost",DEF_RAND_MIN).toInt(); 194 int randMax = settings->value("MaxCost",DEF_RAND_MAX).toInt(); 195 for (int r = 0; r < nCities; r++) 196 for (int c = 0; c < nCities; c++) 197 if (r != c) 198 table[r][c] = rand(randMin,randMax); 199 emit dataChanged(index(0,0),index(nCities - 1,nCities - 1)); 200 } 201 202 /*! 203 * \brief Returns the row count in the table. 204 * \return Number of rows in the table. 205 * 206 * Actually, this function returns the number of cities in the current task. 207 * 208 * \sa columnCount(), numCities() 209 */ 210 int CTSPModel::rowCount(const QModelIndex &) const 211 { 212 return nCities; 213 } 214 215 /*! 216 * \brief Saves current task to \a fname. 217 * \param fname The name of the file to seve to. 218 * \return \c true on success, otherwise \c false. 219 * 220 * \sa loadTask() 221 */ 222 bool CTSPModel::saveTask(QString fname) 223 { 224 QApplication::setOverrideCursor(QCursor(Qt::WaitCursor)); 225 QFile f(fname); 226 if (!f.open(QIODevice::WriteOnly)) { 227 QApplication::restoreOverrideCursor(); 228 QMessageBox(QMessageBox::Critical,trUtf8("Task Save"),QString(trUtf8("Unable to create task file.\nError: %1\nMaybe, file is read-only?")).arg(f.errorString()),QMessageBox::Ok).exec(); 229 return false; 230 } 231 QDataStream ds(&f); 232 ds.setVersion(QDataStream::Qt_4_4); 233 if (f.error() != QFile::NoError) { 234 f.close(); 235 QApplication::restoreOverrideCursor(); 236 QMessageBox(QMessageBox::Critical,trUtf8("Task Save"),trUtf8("Unable to save task.\nError: %1").arg(f.errorString()),QMessageBox::Ok).exec(); 237 return false; 238 } 239 // File signature 240 ds << TSPT; 241 if (f.error() != QFile::NoError) { 242 f.close(); 243 QApplication::restoreOverrideCursor(); 244 QMessageBox(QMessageBox::Critical,trUtf8("Task Save"),trUtf8("Unable to save task.\nError: %1").arg(f.errorString()),QMessageBox::Ok).exec(); 245 return false; 246 } 247 // File version 248 ds << TSPT_VERSION; 249 if (f.error() != QFile::NoError) { 250 f.close(); 251 QApplication::restoreOverrideCursor(); 252 QMessageBox(QMessageBox::Critical,trUtf8("Task Save"),trUtf8("Unable to save task.\nError: %1").arg(f.errorString()),QMessageBox::Ok).exec(); 253 return false; 254 } 255 // File metadata version 256 ds << TSPT_META_VERSION; 257 if (f.error() != QFile::NoError) { 258 f.close(); 259 QApplication::restoreOverrideCursor(); 260 QMessageBox(QMessageBox::Critical,trUtf8("Task Save"),trUtf8("Unable to save task.\nError: %1").arg(f.errorString()),QMessageBox::Ok).exec(); 261 return false; 262 } 263 // Metadata 264 ds << OSID; 265 if (f.error() != QFile::NoError) { 266 f.close(); 267 QApplication::restoreOverrideCursor(); 268 QMessageBox(QMessageBox::Critical,trUtf8("Task Save"),trUtf8("Unable to save task.\nError: %1").arg(f.errorString()),QMessageBox::Ok).exec(); 269 return false; 270 } 271 // Number of cities 272 ds << nCities; 273 if (f.error() != QFile::NoError) { 274 f.close(); 275 QApplication::restoreOverrideCursor(); 276 QMessageBox(QMessageBox::Critical,trUtf8("Task Save"),trUtf8("Unable to save task.\nError: %1").arg(f.errorString()),QMessageBox::Ok).exec(); 277 return false; 278 } 279 // Costs 280 for (int r = 0; r < nCities; r++) 281 for (int c = 0; c < nCities; c++) 282 if (r != c) { 283 ds << table[r][c]; 284 if (f.error() != QFile::NoError) { 285 f.close(); 286 QApplication::restoreOverrideCursor(); 287 QMessageBox(QMessageBox::Critical,trUtf8("Task Save"),trUtf8("Unable to save task.\nError: %1").arg(f.errorString()),QMessageBox::Ok).exec(); 288 return false; 289 } 290 } 291 f.close(); 292 QApplication::restoreOverrideCursor(); 293 return true; 294 } 295 296 /*! 297 * \brief Sets the \a role data for the item at \a index to \a value. 298 * \param index The index of the item to set data at. 299 * \param value The value of the item data to be set. 300 * \param role The role of the item to set data for. 301 * \return \c true on success, otherwise \c false. 302 * 303 * \sa data() 304 */ 82 305 bool CTSPModel::setData(const QModelIndex &index, const QVariant &value, int role) 83 306 { … … 101 324 } 102 325 103 Qt::ItemFlags CTSPModel::flags(const QModelIndex &index) const 104 { 105 Qt::ItemFlags flags = QAbstractItemModel::flags(index); 106 if (index.row() != index.column()) 107 flags |= Qt::ItemIsEditable; 108 return flags; 109 } 110 111 quint16 CTSPModel::numCities() const 112 { 113 return nCities; 114 } 115 326 /*! 327 * \brief Sets number of cities in the current task to \a n. 328 * \param n Number of cities to set to. 329 * 330 * \sa numCities() 331 */ 116 332 void CTSPModel::setNumCities(int n) 117 333 { … … 130 346 } 131 347 132 void CTSPModel::clear() 133 { 134 for (int r = 0; r < nCities; r++) 135 for (int c = 0; c < nCities; c++) 136 if (r != c) 137 table[r][c] = 0; 138 emit dataChanged(index(0,0),index(nCities - 1,nCities - 1)); 139 } 348 /* Privates **********************************************************/ 140 349 141 350 inline bool CTSPModel::loadError(QDataStream::Status status) … … 152 361 QApplication::restoreOverrideCursor(); 153 362 QMessageBox(QMessageBox::Critical,trUtf8("Task Load"),trUtf8("Unable to load task:") + "\n" + err,QMessageBox::Ok).exec(); 154 return true;155 }156 157 bool CTSPModel::loadTask(QString fname)158 {159 QApplication::setOverrideCursor(QCursor(Qt::WaitCursor));160 QFile f(fname);161 if (!f.open(QIODevice::ReadOnly)) {162 QApplication::restoreOverrideCursor();163 QMessageBox(QMessageBox::Critical,trUtf8("Task Load"),QString(trUtf8("Unable to open task file.\nError: %1")).arg(f.errorString()),QMessageBox::Ok).exec();164 return false;165 }166 QDataStream ds(&f);167 ds.setVersion(QDataStream::Qt_4_4);168 quint32 sig;169 ds >> sig;170 if (loadError(ds.status())) {171 return false;172 }173 ds.device()->reset();174 if (sig == TSPT) {175 if (!loadTSPT(&ds)) {176 f.close();177 return false;178 }179 } else if ((sig >> 16) == ZKT) {180 if (!loadZKT(&ds)) {181 f.close();182 return false;183 }184 } else {185 f.close();186 QApplication::restoreOverrideCursor();187 QMessageBox(QMessageBox::Critical,trUtf8("Task Load"),trUtf8("Unable to load task:") + "\n" + trUtf8("Unknown file format or file is corrupted."),QMessageBox::Ok).exec();188 return false;189 }190 f.close();191 QApplication::restoreOverrideCursor();192 363 return true; 193 364 } … … 295 466 } 296 467 297 bool CTSPModel::saveTask(QString fname) 298 { 299 QApplication::setOverrideCursor(QCursor(Qt::WaitCursor)); 300 QFile f(fname); 301 if (!f.open(QIODevice::WriteOnly)) { 302 QApplication::restoreOverrideCursor(); 303 QMessageBox(QMessageBox::Critical,trUtf8("Task Save"),QString(trUtf8("Unable to create task file.\nError: %1\nMaybe, file is read-only?")).arg(f.errorString()),QMessageBox::Ok).exec(); 304 return false; 305 } 306 QDataStream ds(&f); 307 ds.setVersion(QDataStream::Qt_4_4); 308 if (f.error() != QFile::NoError) { 309 f.close(); 310 QApplication::restoreOverrideCursor(); 311 QMessageBox(QMessageBox::Critical,trUtf8("Task Save"),trUtf8("Unable to save task.\nError: %1").arg(f.errorString()),QMessageBox::Ok).exec(); 312 return false; 313 } 314 // File signature 315 ds << TSPT; 316 if (f.error() != QFile::NoError) { 317 f.close(); 318 QApplication::restoreOverrideCursor(); 319 QMessageBox(QMessageBox::Critical,trUtf8("Task Save"),trUtf8("Unable to save task.\nError: %1").arg(f.errorString()),QMessageBox::Ok).exec(); 320 return false; 321 } 322 // File version 323 ds << TSPT_VERSION; 324 if (f.error() != QFile::NoError) { 325 f.close(); 326 QApplication::restoreOverrideCursor(); 327 QMessageBox(QMessageBox::Critical,trUtf8("Task Save"),trUtf8("Unable to save task.\nError: %1").arg(f.errorString()),QMessageBox::Ok).exec(); 328 return false; 329 } 330 // File metadata version 331 ds << TSPT_META_VERSION; 332 if (f.error() != QFile::NoError) { 333 f.close(); 334 QApplication::restoreOverrideCursor(); 335 QMessageBox(QMessageBox::Critical,trUtf8("Task Save"),trUtf8("Unable to save task.\nError: %1").arg(f.errorString()),QMessageBox::Ok).exec(); 336 return false; 337 } 338 // Metadata 339 ds << OSID; 340 if (f.error() != QFile::NoError) { 341 f.close(); 342 QApplication::restoreOverrideCursor(); 343 QMessageBox(QMessageBox::Critical,trUtf8("Task Save"),trUtf8("Unable to save task.\nError: %1").arg(f.errorString()),QMessageBox::Ok).exec(); 344 return false; 345 } 346 // Number of cities 347 ds << nCities; 348 if (f.error() != QFile::NoError) { 349 f.close(); 350 QApplication::restoreOverrideCursor(); 351 QMessageBox(QMessageBox::Critical,trUtf8("Task Save"),trUtf8("Unable to save task.\nError: %1").arg(f.errorString()),QMessageBox::Ok).exec(); 352 return false; 353 } 354 // Costs 355 for (int r = 0; r < nCities; r++) 356 for (int c = 0; c < nCities; c++) 357 if (r != c) { 358 ds << table[r][c]; 359 if (f.error() != QFile::NoError) { 360 f.close(); 361 QApplication::restoreOverrideCursor(); 362 QMessageBox(QMessageBox::Critical,trUtf8("Task Save"),trUtf8("Unable to save task.\nError: %1").arg(f.errorString()),QMessageBox::Ok).exec(); 363 return false; 364 } 365 } 366 f.close(); 367 QApplication::restoreOverrideCursor(); 368 return true; 369 } 370 371 void CTSPModel::randomize() 372 { 373 int randMin = settings->value("MinCost",DEF_RAND_MIN).toInt(); 374 int randMax = settings->value("MaxCost",DEF_RAND_MAX).toInt(); 375 for (int r = 0; r < nCities; r++) 376 for (int c = 0; c < nCities; c++) 377 if (r != c) 378 table[r][c] = rand(randMin,randMax); 379 emit dataChanged(index(0,0),index(nCities - 1,nCities - 1)); 380 } 468 inline int CTSPModel::rand(int min, int max) const 469 { 470 return min + (int)(((float)qrand() / RAND_MAX) * max); 471 } -
src/tspmodel.h
r85ad815b0b re0fcac5f2c 1 1 /*! 2 * \ class CTSPModel2 * \file tspmodel.h 3 3 * \author Copyright © 2007-2009 Lёppa <contacts[at]oleksii[dot]name> 4 * \brief This class implements table model for manipulating a task.5 4 * 6 5 * $Id$ 7 6 * $URL$ 7 * 8 * \brief Defines CTSPModel class. 8 9 * 9 10 * <b>TSPSG: TSP Solver and Generator</b> … … 28 29 #define TSPMODEL_H 29 30 30 /*!31 * \file tspmodel.h32 * \brief Defines CTSPModel class.33 */34 35 31 #include "globals.h" 36 32 33 /*! 34 * \brief This class implements table model for manipulating a task. 35 * \author Copyright © 2007-2009 Lёppa <contacts[at]oleksii[dot]name> 36 */ 37 37 class CTSPModel: public QAbstractTableModel 38 38 { … … 55 55 56 56 signals: 57 /*! 58 * \brief This signal is emitted whenever the number of cities in the task changes. 59 * 60 * \sa setNumCities() 61 */ 57 62 void numCitiesChanged(int); 58 63 -
src/tspsolver.cpp
r85ad815b0b re0fcac5f2c 30 30 } 31 31 32 void CTSPSolver::cleanup() 33 { 34 route.clear(); 35 mayNotBeOptimal = false; 36 } 37 38 double CTSPSolver::findMinInRow(int nRow, tMatrix matrix, int exc) 39 { 40 double min = INFINITY; 41 for (int k = 0; k < nCities; k++) 42 if (((k != exc)) && (min > matrix.at(nRow).at(k))) 43 min = matrix.at(nRow).at(k); 44 return min == INFINITY ? 0 : min; 45 } 46 47 double CTSPSolver::findMinInCol(int nCol, tMatrix matrix, int exr) 48 { 49 double min = INFINITY; 50 for (int k = 0; k < nCities; k++) 51 if ((k != exr) && (min > matrix.at(k).at(nCol))) 52 min = matrix.at(k).at(nCol); 53 return min == INFINITY ? 0 : min; 54 } 55 56 void CTSPSolver::subRow(tMatrix &matrix, int nRow, double val) 57 { 58 for (int k = 0; k < nCities; k++) 59 if (k != nRow) 60 matrix[nRow][k] -= val; 61 } 62 63 void CTSPSolver::subCol(tMatrix &matrix, int nCol, double val) 64 { 65 for (int k = 0; k < nCities; k++) 66 if (k != nCol) 67 matrix[k][nCol] -= val; 68 } 32 /*! 33 * \brief Returns the sorted optimal path, starting from City 1. 34 * \return A string, containing sorted optimal path. 35 */ 36 QString CTSPSolver::getSortedPath() const 37 { 38 if (!root || route.isEmpty() || (route.size() != nCities)) 39 return QString(); 40 41 int i = 0; // We start from City 1 42 QString path = trUtf8("City %1").arg(1) + " -> "; 43 while ((i = route[i]) != 0) { 44 path += trUtf8("City %1").arg(i + 1) + " -> "; 45 } 46 // And finish in City 1, too 47 path += trUtf8("City %1").arg(1); 48 49 return path; 50 } 51 52 /*! 53 * \brief Returns CTSPSolver's version ID. 54 * \return A string: <b>\$Id$</b>. 55 */ 56 QString CTSPSolver::getVersionId() 57 { 58 return QString("$Id$"); 59 } 60 61 /*! 62 * \brief Returns whether or not the solution is definitely optimal. 63 * \return \c true if solution is definitely optimal, otherwise \c false. 64 * 65 * The solution may need some further interations to determine whether it is optimal. 66 * In such cases this function returns \c false. 67 */ 68 bool CTSPSolver::isOptimal() const 69 { 70 return !mayNotBeOptimal; 71 } 72 73 /*! 74 * \brief Solves the given task. 75 * \param numCities Number of cities in the task. 76 * \param task The matrix of city-to-city travel costs. 77 * \param parent The parent widget for displaying messages and dialogs. 78 * \return Pointer to the root of the solution tree. 79 * 80 * \todo TODO: Comment the algorithm. 81 */ 82 sStep *CTSPSolver::solve(int numCities, tMatrix task, QWidget *parent) 83 { 84 if (numCities <= 1) 85 return NULL; 86 cleanup(); 87 nCities = numCities; 88 QProgressDialog pd(parent); 89 QProgressBar *pb = new QProgressBar(&pd); 90 pb->setAlignment(Qt::AlignCenter); 91 pb->setFormat(trUtf8("%v of %m parts found")); 92 pd.setBar(pb); 93 pd.setMaximum(nCities); 94 pd.setMinimumDuration(1000); 95 pd.setLabelText(trUtf8("Calculating optimal route...")); 96 pd.setWindowTitle(trUtf8("Solution Progress")); 97 pd.setWindowModality(Qt::ApplicationModal); 98 pd.setValue(0); 99 100 sStep *step = new sStep(); 101 step->matrix = task; 102 step->price = align(step->matrix); 103 root = step; 104 105 sStep *left, *right; 106 int nRow, nCol; 107 bool firstStep = true; 108 double check; 109 while (this->route.size() < nCities) { 110 // forbidden.clear(); 111 step->alts = findCandidate(step->matrix,nRow,nCol); 112 while (hasSubCycles(nRow,nCol)) { 113 // forbidden[nRow] = nCol; 114 step->matrix[nRow][nCol] = INFINITY; 115 step->price += align(step->matrix); 116 step->alts = findCandidate(step->matrix,nRow,nCol); 117 } 118 if ((nRow == -1) || (nCol == -1) || pd.wasCanceled()) { 119 root = NULL; 120 break; 121 } 122 123 // Route with (nRow,nCol) path 124 right = new sStep(); 125 right->matrix = step->matrix; 126 for (int k = 0; k < nCities; k++) { 127 if (k != nCol) 128 right->matrix[nRow][k] = INFINITY; 129 if (k != nRow) 130 right->matrix[k][nCol] = INFINITY; 131 } 132 right->price = step->price + align(right->matrix); 133 // Forbid selected route to exclude its reuse in next steps. 134 right->matrix[nCol][nRow] = INFINITY; 135 right->matrix[nRow][nCol] = INFINITY; 136 137 // Route without (nRow,nCol) path 138 left = new sStep(); 139 left->matrix = step->matrix; 140 left->matrix[nRow][nCol] = INFINITY; 141 left->price = step->price + align(left->matrix); 142 143 step->candidate.nRow = nRow; 144 step->candidate.nCol = nCol; 145 step->plNode = left; 146 step->prNode = right; 147 148 if (right->price <= left->price) { 149 // Route with (nRow,nCol) path is cheaper 150 step = right; 151 this->route[nRow] = nCol; 152 pd.setValue(this->route.size()); 153 if (firstStep) { 154 check = left->price; 155 firstStep = false; 156 } 157 } else { 158 // Route without (nRow,nCol) path is cheaper 159 step = left; 160 qApp->processEvents(); 161 if (firstStep) { 162 check = right->price; 163 firstStep = false; 164 } 165 } 166 } 167 168 if (!root && !pd.wasCanceled()) { 169 pd.reset(); 170 QMessageBox(QMessageBox::Warning,trUtf8("Solution Result"),trUtf8("Unable to find solution.\nMaybe, this task has no solutions."),QMessageBox::Ok,parent).exec(); 171 } 172 173 qApp->processEvents(); 174 175 if (root) { 176 route = this->route; 177 mayNotBeOptimal = (check < step->price); 178 } 179 return root; 180 } 181 182 /* Privates **********************************************************/ 69 183 70 184 double CTSPSolver::align(tMatrix &matrix) … … 87 201 } 88 202 return r; 203 } 204 205 void CTSPSolver::cleanup() 206 { 207 route.clear(); 208 mayNotBeOptimal = false; 89 209 } 90 210 … … 112 232 } 113 233 234 double CTSPSolver::findMinInCol(int nCol, tMatrix matrix, int exr) 235 { 236 double min = INFINITY; 237 for (int k = 0; k < nCities; k++) 238 if ((k != exr) && (min > matrix.at(k).at(nCol))) 239 min = matrix.at(k).at(nCol); 240 return min == INFINITY ? 0 : min; 241 } 242 243 double CTSPSolver::findMinInRow(int nRow, tMatrix matrix, int exc) 244 { 245 double min = INFINITY; 246 for (int k = 0; k < nCities; k++) 247 if (((k != exc)) && (min > matrix.at(nRow).at(k))) 248 min = matrix.at(nRow).at(k); 249 return min == INFINITY ? 0 : min; 250 } 251 114 252 bool CTSPSolver::hasSubCycles(int nRow, int nCol) 115 253 { … … 126 264 } 127 265 128 /*! 129 * \brief Solves the given task. 130 * \param numCities Number of cities in the task. 131 * \param task The matrix of city-to-city travel costs. 132 * \param parent The parent widget for displaying messages and dialogs. 133 * \return Pointer to the root of the solution tree. 134 * 135 * \todo TODO: Comment the algorithm. 136 */ 137 sStep *CTSPSolver::solve(int numCities, tMatrix task, QWidget *parent) 138 { 139 if (numCities <= 1) 140 return NULL; 141 cleanup(); 142 nCities = numCities; 143 QProgressDialog pd(parent); 144 QProgressBar *pb = new QProgressBar(&pd); 145 pb->setAlignment(Qt::AlignCenter); 146 pb->setFormat(trUtf8("%v of %m parts found")); 147 pd.setBar(pb); 148 pd.setMaximum(nCities); 149 pd.setMinimumDuration(1000); 150 pd.setLabelText(trUtf8("Calculating optimal route...")); 151 pd.setWindowTitle(trUtf8("Solution Progress")); 152 pd.setWindowModality(Qt::ApplicationModal); 153 pd.setValue(0); 154 155 sStep *step = new sStep(); 156 step->matrix = task; 157 step->price = align(step->matrix); 158 root = step; 159 160 sStep *left, *right; 161 int nRow, nCol; 162 bool firstStep = true; 163 double check; 164 while (this->route.size() < nCities) { 165 // forbidden.clear(); 166 step->alts = findCandidate(step->matrix,nRow,nCol); 167 while (hasSubCycles(nRow,nCol)) { 168 // forbidden[nRow] = nCol; 169 step->matrix[nRow][nCol] = INFINITY; 170 step->price += align(step->matrix); 171 step->alts = findCandidate(step->matrix,nRow,nCol); 172 } 173 if ((nRow == -1) || (nCol == -1) || pd.wasCanceled()) { 174 root = NULL; 175 break; 176 } 177 178 // Route with (nRow,nCol) path 179 right = new sStep(); 180 right->matrix = step->matrix; 181 for (int k = 0; k < nCities; k++) { 182 if (k != nCol) 183 right->matrix[nRow][k] = INFINITY; 184 if (k != nRow) 185 right->matrix[k][nCol] = INFINITY; 186 } 187 right->price = step->price + align(right->matrix); 188 // Forbid selected route to exclude its reuse in next steps. 189 right->matrix[nCol][nRow] = INFINITY; 190 right->matrix[nRow][nCol] = INFINITY; 191 192 // Route without (nRow,nCol) path 193 left = new sStep(); 194 left->matrix = step->matrix; 195 left->matrix[nRow][nCol] = INFINITY; 196 left->price = step->price + align(left->matrix); 197 198 step->candidate.nRow = nRow; 199 step->candidate.nCol = nCol; 200 step->plNode = left; 201 step->prNode = right; 202 203 if (right->price <= left->price) { 204 // Route with (nRow,nCol) path is cheaper 205 step = right; 206 this->route[nRow] = nCol; 207 pd.setValue(this->route.size()); 208 if (firstStep) { 209 check = left->price; 210 firstStep = false; 211 } 212 } else { 213 // Route without (nRow,nCol) path is cheaper 214 step = left; 215 qApp->processEvents(); 216 if (firstStep) { 217 check = right->price; 218 firstStep = false; 219 } 220 } 221 } 222 223 if (!root && !pd.wasCanceled()) { 224 pd.reset(); 225 QMessageBox(QMessageBox::Warning,trUtf8("Solution Result"),trUtf8("Unable to find solution.\nMaybe, this task has no solutions."),QMessageBox::Ok,parent).exec(); 226 } 227 228 qApp->processEvents(); 229 230 if (root) { 231 route = this->route; 232 mayNotBeOptimal = (check < step->price); 233 } 234 return root; 235 } 236 237 /*! 238 * \brief Returns the sorted optimal path, starting from City 1. 239 * \return A string, containing sorted optimal path. 240 */ 241 QString CTSPSolver::getSortedPath() const 242 { 243 if (!root || route.isEmpty() || (route.size() != nCities)) 244 return QString(); 245 246 int i = 0; // We start from City 1 247 QString path = trUtf8("City %1").arg(1) + " -> "; 248 while ((i = route[i]) != 0) { 249 path += trUtf8("City %1").arg(i + 1) + " -> "; 250 } 251 // And finish in City 1, too 252 path += trUtf8("City %1").arg(1); 253 254 return path; 255 } 256 257 /*! 258 * \brief Returns CTSPSolver's version ID. 259 * \return A string: <b>\$Id$</b>. 260 */ 261 QString CTSPSolver::getVersionId() 262 { 263 return QString("$Id$"); 264 } 265 266 /*! 267 * \brief Returns whether or not the solution is definitely optimal. 268 * \return \c true if solution is definitely optimal, otherwise \c false. 269 * 270 * The solution may need some further interations to determine whether it is optimal. 271 * In such cases this function returns \c false. 272 */ 273 bool CTSPSolver::isOptimal() const 274 { 275 return !mayNotBeOptimal; 276 } 266 void CTSPSolver::subCol(tMatrix &matrix, int nCol, double val) 267 { 268 for (int k = 0; k < nCities; k++) 269 if (k != nCol) 270 matrix[k][nCol] -= val; 271 } 272 273 void CTSPSolver::subRow(tMatrix &matrix, int nRow, double val) 274 { 275 for (int k = 0; k < nCities; k++) 276 if (k != nRow) 277 matrix[nRow][k] -= val; 278 } -
src/tspsolver.h
r85ad815b0b re0fcac5f2c 1 1 /*! 2 * \ class CTSPSolver2 * \file tspsolver.h 3 3 * \author Copyright © 2007-2009 Lёppa <contacts[at]oleksii[dot]name> 4 * \brief This class solves Travelling Salesman Problem task.5 4 * 6 5 * $Id$ 7 6 * $URL$ 7 * 8 * \brief Defines #tMatrix typedef, sStep struct and CTSPSolver class. 8 9 * 9 10 * <b>TSPSG: TSP Solver and Generator</b> … … 23 24 * You should have received a copy of the GNU General Public License 24 25 * along with TSPSG. If not, see <http://www.gnu.org/licenses/>. 25 *26 * \todo TODO: Deletion of solution tree on destroy and cleanup.27 26 */ 28 27 29 28 #ifndef TSPSOLVER_H 30 29 #define TSPSOLVER_H 31 32 /*!33 * \file tspsolver.h34 * \brief Defines #tMatrix typedef, sStep struct and CTSPSolver class.35 */36 30 37 31 #include "globals.h" … … 67 61 }; 68 62 63 /*! 64 * \brief This class solves Travelling Salesman Problem task. 65 * \author Copyright © 2007-2009 Lёppa <contacts[at]oleksii[dot]name> 66 * 67 * \todo TODO: Deletion of solution tree on destroy and cleanup. 68 */ 69 69 class CTSPSolver 70 70 { … … 74 74 CTSPSolver(); 75 75 QString getSortedPath() const; 76 static QString getVersionId(); 76 77 bool isOptimal() const; 77 78 sStep *solve(int, tMatrix, QWidget *parent = 0); 78 static QString getVersionId();79 79 80 80 private: … … 84 84 QHash<int,int> route; 85 85 // QHash<int,int> forbidden; 86 86 87 double align(tMatrix &); 87 88 void cleanup(); 88 89 bool findCandidate(tMatrix, int &, int &); 90 double findMinInCol(int, tMatrix, int exr = -1); 89 91 double findMinInRow(int, tMatrix, int exc = -1); 90 double findMinInCol(int, tMatrix, int exr = -1);91 92 bool hasSubCycles(int, int); 92 93 void subCol(tMatrix &, int, double); -
src/version.h
r85ad815b0b re0fcac5f2c 1 /*! \mainpage 1 /*! 2 * \file version.h 3 * \author Copyright (C) 2007-2009 Lёppa <contacts[at]oleksii[dot]name> 2 4 * 5 * $Id$ 6 * $URL$ 7 * 8 * \brief Contains TSPSG version information defines. 9 * 10 * <b>TSPSG: TSP Solver and Generator</b> 11 * 12 * This file is part of TSPSG. 13 * 14 * TSPSG is free software: you can redistribute it and/or modify 15 * it under the terms of the GNU General Public License as published by 16 * the Free Software Foundation, either version 3 of the License, or 17 * (at your option) any later version. 18 * 19 * TSPSG is distributed in the hope that it will be useful, 20 * but WITHOUT ANY WARRANTY; without even the implied warranty of 21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 22 * GNU General Public License for more details. 23 * 24 * You should have received a copy of the GNU General Public License 25 * along with TSPSG. If not, see <http://www.gnu.org/licenses/>. 26 */ 27 /*! 28 * \mainpage 3 29 * \image html tspsg.png 4 30 * <b>TSPSG: TSP Solver and Generator</b> … … 7 33 * $Id$ 8 34 * $URL$ 9 *10 * This file is part of TSPSG.11 35 * 12 36 * TSPSG is free software: you can redistribute it and/or modify … … 26 50 #ifndef VERSION_H 27 51 #define VERSION_H 28 29 /*!30 * \file version.h31 * \brief This file contains TSPSG version information defines.32 */33 52 34 53 //! TSPSG version ID
Note: See TracChangeset
for help on using the changeset viewer.