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

#include <tspsolver.h>

Inheritance diagram for TSPSolver::CTSPSolver:

Collaboration diagram for TSPSolver::CTSPSolver:

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. More...

Public Member Functions
	CTSPSolver (QObject *parent=NULL)
	Constructs CTSPSolver object. More...

void	cleanup (bool processEvents=false)
	Cleans up the object and frees up memory used by the solution tree. More...

QString	getSortedPath (const QString &city, const QString &separator=QString(" -> ")) const
	Returns the sorted optimal path, starting from City 1. More...

int	getTotalSteps () const
	Returns a total number of steps in the current solution. More...

bool	isOptimal () const
	Indicates whether or not the solution is definitely optimal. More...

void	setCleanupOnCancel (bool enable=true)
	Sets whether or not to call cleanup() on solution cancel. More...

SStep *	solve (int numCities, const TMatrix &task)
	Solves the given task. More...

bool	wasCanceled () const
	Indicates whether or not the solution process was canceled. More...

Public Member Functions inherited from QObject
	QObject (QObject *parent)

virtual bool	event (QEvent *e)

virtual bool	eventFilter (QObject watched, QEvent event)

virtual const QMetaObject *	metaObject () const

QString	objectName () const

void	setObjectName (const QString &name)

bool	isWidgetType () const

bool	signalsBlocked () const

bool	blockSignals (bool block)

QThread *	thread () const

void	moveToThread (QThread *targetThread)

int	startTimer (int interval)

void	killTimer (int id)

T	findChild (const QString &name) const

QList< T >	findChildren (const QString &name) const

QList< T >	findChildren (const QRegExp &regExp) const

QObject *	child (const char objName, const char inheritsClass, bool recursiveSearch) const

const QObjectList &	children () const

void	setParent (QObject *parent)

void	installEventFilter (QObject *filterObj)

void	removeEventFilter (QObject *obj)

bool	connect (const QObject sender, const char signal, const char *method, Qt::ConnectionType type) const

bool	disconnect (const char signal, const QObject receiver, const char *method)

bool	disconnect (const QObject receiver, const char method)

void	dumpObjectTree ()

void	dumpObjectInfo ()

bool	setProperty (const char *name, const QVariant &value)

QVariant	property (const char *name) const

QList< QByteArray >	dynamicPropertyNames () const

void	destroyed (QObject *obj)

QObject *	parent () const

bool	inherits (const char *className) const

void	deleteLater ()

	QObject (QObject parent, const char name)

void	insertChild (QObject *object)

void	removeChild (QObject *object)

bool	isA (const char *className) const

const char *	className () const

const char *	name () const

const char *	name (const char *defaultName) const

void	setName (const char *name)

Static Public Member Functions
static QString	getVersionId ()
	Returns CTSPSolver's version ID. More...

Static Public Member Functions inherited from QObject
QString	tr (const char sourceText, const char disambiguation, int n)

QString	trUtf8 (const char sourceText, const char disambiguation, int n)

bool	connect (const QObject sender, const char signal, const QObject receiver, const char method, Qt::ConnectionType type)

bool	connect (const QObject sender, const QMetaMethod &signal, const QObject receiver, const QMetaMethod &method, Qt::ConnectionType type)

bool	disconnect (const QObject sender, const char signal, const QObject receiver, const char method)

bool	disconnect (const QObject sender, const QMetaMethod &signal, const QObject receiver, const QMetaMethod &method)

Additional Inherited Members
Protected Member Functions inherited from QObject
QObject *	sender () const

int	senderSignalIndex () const

int	receivers (const char *signal) const

virtual void	timerEvent (QTimerEvent *event)

virtual void	childEvent (QChildEvent *event)

virtual void	customEvent (QEvent *event)

virtual void	connectNotify (const char *signal)

virtual void	disconnectNotify (const char *signal)

bool	checkConnectArgs (const char signal, const QObject object, const char *method)

Static Protected Member Functions inherited from QObject
QByteArray	normalizeSignalSlot (const char *signalSlot)

Properties inherited from QObject
	objectName

Detailed Description

This class solves Travelling Salesman Problem task.

Author: Copyright © 2007-2016 Oleksii Serdiuk <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: 0c8813f 2016-04-18 23:45:08 +0200 Oleksii Serdiuk $.

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

Public Slots

Signals

Public Member Functions

Static Public Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation