Class defining a local search approach doing greedy recolourings. More...

#include <optimisation-sa-greedy.hh>

Inheritance diagram for minlca::MinLCAVertexOrderSA< Greedy, Graph >:

Collaboration diagram for minlca::MinLCAVertexOrderSA< Greedy, Graph >:

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

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

	~MinLCAVertexOrderSA ()
	Destructor. More...

void	setRandom (lemon::Random *r, bool deleteRandom=false)

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

virtual MinLCAStatus	run ()
	Run 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 MinLCA< Graph >	BaseLCA

typedef MinLCAVertexOrderSA< Greedy, Graph >	SAorder

Protected Member Functions
virtual void	init ()
	Initialise data structures. Do not 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< GreedyNodeSA > *	_sa
	Pointer to the simulated annealing algorithm.

GreedyNodeSA *	_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.

std::vector< Node >	_order
	Initial vertex order.

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)

void	process (const Node &v)

Friends
class	GreedyNodeSA

class	lemon::BfsVisit< Graph, SAorder >

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

Detailed Description

template<template< typename > class Greedy, typename Graph = lemon::SmartGraph>
class minlca::MinLCAVertexOrderSA< Greedy, Graph >

Class defining a local search approach doing greedy recolourings.

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

Definition at line 21 of file optimisation-sa-greedy.hh.

Constructor & Destructor Documentation

template<template< typename > class Greedy, typename Graph = lemon::SmartGraph>

minlca::MinLCAVertexOrderSA< Greedy, Graph >::MinLCAVertexOrderSA	(	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: MinLCA::MinLCA(const Graph&, int); utils::SimulatedAnnealing(int, int, int, double, lemon::Random)

Parameters

seed	Seed for the random number generator

Definition at line 60 of file optimisation-sa-greedy.hh.

template<template< typename > class Greedy, typename Graph = lemon::SmartGraph>

minlca::MinLCAVertexOrderSA< Greedy, Graph >::~MinLCAVertexOrderSA ( )

inline

Destructor.

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

Definition at line 76 of file optimisation-sa-greedy.hh.

Member Function Documentation

template<template< typename > class Greedy, typename Graph = lemon::SmartGraph>

virtual void minlca::MinLCAVertexOrderSA< Greedy, Graph >::init ( )

inlineprotectedvirtual

Initialise data structures. Do not use.

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

Reimplemented from minlca::MinLCA< Graph >.

Definition at line 46 of file optimisation-sa-greedy.hh.

template<template< typename > class Greedy, typename Graph = lemon::SmartGraph>

virtual void minlca::MinLCAVertexOrderSA< Greedy, Graph >::init	(	int	steps,
		int	stIter,
		int	k,
		double	lambda,
		bool	initial = `false`
	)

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)

Parameters

initial If true, initial solution using Bfs. Else, random.

Definition at line 103 of file optimisation-sa-greedy.hh.

template<template< typename > class Greedy, typename Graph = lemon::SmartGraph>

virtual MinLCAStatus minlca::MinLCAVertexOrderSA< Greedy, 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 157 of file optimisation-sa-greedy.hh.

template<template< typename > class Greedy, typename Graph = lemon::SmartGraph>

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

inline

Definition at line 92 of file optimisation-sa-greedy.hh.

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

minlca/optimisation-sa-greedy.hh

Classes

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Private Member Functions

Friends

Additional Inherited Members

Detailed Description

template<template< typename > class Greedy, typename Graph = lemon::SmartGraph> class minlca::MinLCAVertexOrderSA< Greedy, Graph >

Constructor & Destructor Documentation

Member Function Documentation

template<template< typename > class Greedy, typename Graph = lemon::SmartGraph>
class minlca::MinLCAVertexOrderSA< Greedy, Graph >