TSPSolver::CTSPSolver Class Reference

This class solves Travelling Salesman Problem task. More...

#include <tspsolver.h>

Inheritance diagram for TSPSolver::CTSPSolver:

Collaboration diagram for TSPSolver::CTSPSolver:

List of all members.

Public Slots
void	cancel ()
	Cancels the solution process.
Signals
void	routePartFound (int n)
	This signal is emitted once every time a part of the route is found.
Public Member Functions
	CTSPSolver (QObject *parent=NULL)
	Constructs CTSPSolver object.
void	cleanup (bool processEvents=false)
	Cleans up the object and frees up memory used by the solution tree.
QString	getSortedPath (const QString &city, const QString &separator=QString(" -> ")) const
	Returns the sorted optimal path, starting from City 1.
int	getTotalSteps () const
	Returns a total number of steps in the current solution.
bool	isOptimal () const
	Indicates whether or not the solution is definitely optimal.
void	setCleanupOnCancel (bool enable=true)
	Sets whether or not to call cleanup() on solution cancel.
SStep *	solve (int numCities, const TMatrix &task)
	Solves the given task.
bool	wasCanceled () const
	Indicates whether or not the solution process was canceled.
Static Public Member Functions
static QString	getVersionId ()
	Returns CTSPSolver's version ID.

---

Detailed Description

This class solves Travelling Salesman Problem task.

Author:

Copyright © 2007-2010 Lёppa <contacts[at]oleksii[dot]name>

---

Constructor & Destructor Documentation

TSPSolver::CTSPSolver::CTSPSolver

(

QObject *

parent = NULL

)

Constructs CTSPSolver object.

Parameters:

parent

A parent object.

---

Member Function Documentation

void TSPSolver::CTSPSolver::cleanup

(

bool

processEvents = false

)

Cleans up the object and frees up memory used by the solution tree.

Parameters:

processEvents

If set to true then QCoreApplication::processEvents(QEventLoop::ExcludeUserInputEvents) will be called from time to time while cleaning up.

Warning:

After call to this function a solution tree returned by the solve() function is no longer valid.

Note:

It is not required to call this function manually. This function is always called by solve() at the beginning of the solution process.

See also:

solve(), setCleanupOnCancel()

Here is the call graph for this function:

Here is the caller graph for this function:

QString TSPSolver::CTSPSolver::getSortedPath	(	const QString &	city,
		const QString &	separator = QString(" -> ")
	)			const

Returns the sorted optimal path, starting from City 1.

Parameters:

	city	A string that represents city elements in the path.
	separator	A string that represents separators between cities in the path.

Returns:

A string, containing sorted optimal path.

The resulting path will be in the form city+separator+city+...+separator+city. %1 in city will be replaced by the city number.

Here is the call graph for this function:

int TSPSolver::CTSPSolver::getTotalSteps

(

)

const

Returns a total number of steps in the current solution.

Returns:

A total number of steps or 0 if no solution.

Note:

This is not always the same as the number of cities.

QString TSPSolver::CTSPSolver::getVersionId

(

)

[static]

Returns CTSPSolver's version ID.

Returns:

A string: $Id: tspsolver.cpp 124 2010-07-04 01:03:13Z laleppa $.

bool TSPSolver::CTSPSolver::isOptimal

(

)

const

Indicates whether or not the solution is definitely optimal.

Returns:

true if the solution is definitely optimal, otherwise false.

The solution may need some further iterations to determine whether or not it is optimal. In such cases this function returns false.

void TSPSolver::CTSPSolver::routePartFound

(

int

n

)

[signal]

This signal is emitted once every time a part of the route is found.

Parameters:

n

Indicates the number of the route parts found.

Here is the caller graph for this function:

void TSPSolver::CTSPSolver::setCleanupOnCancel

(

bool

enable = true

)

Sets whether or not to call cleanup() on solution cancel.

Parameters:

enable

Set to true to enable clenup (default).

This may be useful if you want to make cleanup yourself or provide indication of clenup to user.

Note:

Please, note that cleanup() is explicitly called at the start of each solution. Disabling cleanup and forgetting to do it manually may considerably increase the solution time for large tasks (with more than 15 cities).

See also:

cleanup()

SStep * TSPSolver::CTSPSolver::solve	(	int	numCities,
		const TMatrix &	task
	)

Solves the given task.

Parameters:

	numCities	Number of cities in the task.
	task	The matrix of city-to-city travel costs.

Returns:

Pointer to the root of the solution tree.

Todo:

TODO: Comment the algorithm.

Here is the call graph for this function:

bool TSPSolver::CTSPSolver::wasCanceled

(

)

const

Indicates whether or not the solution process was canceled.

Returns:

true if the solution process was canceled, otherwise false.

---

The documentation for this class was generated from the following files:

• src/tspsolver.h
• src/tspsolver.cpp