Class defining a local search approach changing the colours. More...

#include <optimisation-sa-colours.hh>

Inheritance diagram for minlca::MinLCAColoursSA< Graph >:

Collaboration diagram for minlca::MinLCAColoursSA< Graph >:

Classes
class	NodeSA
	Class defining the node for the simulated annealing search changing the colours. More...

Public Member Functions
	MinLCAColoursSA (const Graph &g, int maxK=0, int seed=0)
	Constructor. More...

	~MinLCAColoursSA ()
	Destructor. More...

void	setRandom (lemon::Random *r, bool deleteRandom=false)
	Change the random number generator. More...

virtual void	init (int steps, int stIter, int k, double lambda)
	Reset the data structures of the algorithm. More...

virtual void	initialSolution (const typename Base::Colouring &c)

virtual MinLCAStatus	run ()
	Run the algorithm. More...

Public Member Functions inherited from minlca::MinLCAOpt< Graph >
virtual void	initialSolution (const typename MinLCA< Graph >::Colouring &c)=0
	Set the initial solution for the algorithm. More...

Public Member Functions inherited from minlca::MinLCA< Graph >
	TEMPLATE_GRAPH_TYPEDEFS (Graph)

MinLCAStatus	status () const
	Status of the solution.

const Colouring &	colouring () const
	Current colouring. More...

int	operator[] (const Node &v) const
	Colour of a vertex. More...

int	operator[] (const Edge &e) const
	Cost of an edge. More...

long long	lcaValue () const
	Value (cost) of the current solution. More...

int	totalColours () const
	Total number of colours used. More...

long long	recalculateLca ()
	Force a recalculation of the cost for the current solution. More...

int	maxK ()
	Maximum number of allowed colours. More...

Protected Types
typedef MinLCAOpt< Graph >	Base
	Base class.

Protected Types inherited from minlca::MinLCAOpt< Graph >
typedef MinLCA< Graph >	Base

Protected Member Functions
virtual void	init ()
	Initialise data structures. Do not use. More...

Protected Member Functions inherited from minlca::MinLCAOpt< Graph >
	MinLCAOpt (const Graph &g, int maxK=0)
	Constructor for derived classes to use. More...

Protected Member Functions inherited from minlca::MinLCA< Graph >
void	setSolutionNotFound ()
	Auxiliary function to set solution status to not found.

void	setSolutionFound ()
	Auxiliary function to set solution status to found.

virtual void	setColour (const Node &v, int vColour)
	Set the colour of a vertex. More...

	MinLCA (const Graph &g, int maxK=0)
	Constructor for derived classes to use. More...

Protected Attributes
utils::SimulatedAnnealing< NodeSA > *	_sa
	Pointer to the simulated annealing algorithm.

NodeSA *	_result
	Pointer to the node obtained with simulated annealing.

lemon::Random *	_r
	Pointer to the random number generator used.

bool	_delete_random
	Delete the random number generator in destructor.

lemon::RangeIdMap< Graph, Node >	_vertex_id_map
	Map of vertex identifiers.

Protected Attributes inherited from minlca::MinLCA< Graph >
const Graph &	_g
	A const reference to the graph we want to arrange.

int	_k
	Largest index of the colours used.

int	_max_k
	Maximum number of colours allowed.

long long	_lca
	Cost of the current solution.

Colouring	_c
	The vertex colouring.

MinLCAStatus	_s
	The status of the solution.

Private Member Functions
	TEMPLATE_GRAPH_TYPEDEFS (Graph)

Friends
class	NodeSA

Additional Inherited Members
Public Types inherited from minlca::MinLCA< Graph >
typedef IntNodeMap	Colouring
	Type for graph colourings.

Detailed Description

template<typename Graph = lemon::SmartGraph>
class minlca::MinLCAColoursSA< Graph >

Class defining a local search approach changing the colours.

Read the report of Bachelor's Thesis Algorithms for the linear colouring arrangement problem for more information.

Definition at line 19 of file optimisation-sa-colours.hh.

Constructor & Destructor Documentation

template<typename Graph = lemon::SmartGraph>

minlca::MinLCAColoursSA< Graph >::MinLCAColoursSA	(	const Graph &	g,
		int	maxK = `0`,
		int	seed = `0`
	)

inline

Constructor.

Constructor for the class requesting an initial seed for the random number generator. If you want to use an existing random number generator, call setRandom(lemon::Random *).

See also: MinLCAOpt::MinLCAOpt(const Graph&, int); MinLCA::MinLCA(const Graph&, int); utils::SimulatedAnnealing(int, int, int, double, lemon::Random)

Parameters

seed	Seed for the random number generator

Definition at line 54 of file optimisation-sa-colours.hh.

template<typename Graph = lemon::SmartGraph>

minlca::MinLCAColoursSA< Graph >::~MinLCAColoursSA ( )

inline

Destructor.

Takes care of deleting the internal simulated annealing algorithm and the resulting node.

Definition at line 73 of file optimisation-sa-colours.hh.

Member Function Documentation

template<typename Graph = lemon::SmartGraph>

virtual void minlca::MinLCAColoursSA< Graph >::init ( )

inlineprotectedvirtual

Initialise data structures. Do not use.

Use init(int,int,int,double) instead

Reimplemented from minlca::MinLCA< Graph >.

Definition at line 39 of file optimisation-sa-colours.hh.

template<typename Graph = lemon::SmartGraph>

virtual void minlca::MinLCAColoursSA< Graph >::init	(	int	steps,
		int	stIter,
		int	k,
		double	lambda
	)

inlinevirtual

Reset the data structures of the algorithm.

Resets the data structures of the algorithm. Must be called before its execution with run().

See also: run()

Initialises the simulated annealing parameters.

See also: utils::SimulatedAnnealing::SimulatedAnnealing(int, int, int, double, lemon::Random)

Definition at line 105 of file optimisation-sa-colours.hh.

template<typename Graph = lemon::SmartGraph>

virtual MinLCAStatus minlca::MinLCAColoursSA< Graph >::run ( )

inlinevirtual

Run the algorithm.

Runs the algorithm and returns its status. Need to call init() before executing.

Returns: Status of the solution

See also: init()

Reimplemented from minlca::MinLCA< Graph >.

Definition at line 130 of file optimisation-sa-colours.hh.

template<typename Graph = lemon::SmartGraph>

void minlca::MinLCAColoursSA< Graph >::setRandom	(	lemon::Random *	r,
		bool	deleteRandom = `false`
	)

inline

Change the random number generator.

Sets a new random number generator

Parameters

r	Pointer to an existing random number generator
deleteRandom	Delete the contents of the pointer when changed or calling the destructor?

Definition at line 87 of file optimisation-sa-colours.hh.

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

minlca/optimisation-sa-colours.hh

Classes

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Private Member Functions

Friends

Additional Inherited Members

Detailed Description

template<typename Graph = lemon::SmartGraph> class minlca::MinLCAColoursSA< Graph >

Constructor & Destructor Documentation

Member Function Documentation

template<typename Graph = lemon::SmartGraph>
class minlca::MinLCAColoursSA< Graph >