Randomised greedy nearest colour approach for MinLCA. More...

#include <greedy-random.hh>

Inheritance diagram for minlca::MinLCAGreedyNearestRnd< Graph >:

Collaboration diagram for minlca::MinLCAGreedyNearestRnd< Graph >:

Public Member Functions
void	p (double p)
	Change the probability of choosing a random colour. More...

template<typename Number >
void	seed (Number seed)
	Change the seed for the internal random number generator. More...

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

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

virtual void	init ()
	Reset the data structures of the algorithm. More...

MinLCAStatus	status () const
	Status of the solution.

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

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 MinLCAGreedyNearestRnd< Graph >	Greedy

typedef MinLCAGreedy< Graph >	Base

Protected Types inherited from minlca::MinLCAGreedy< Graph >
typedef MinLCA< Graph >	Base
	The base class, for shorter reference.

Protected Member Functions
	TEMPLATE_GRAPH_TYPEDEFS (Graph)

template<typename Number = unsigned long long>
	MinLCAGreedyNearestRnd (const Graph &g, int maxK=0, double p=0.0, Number seed=0ULL)
	Constructor. More...

virtual void	paintVertex (const Node &v)
	Assign a colour to a vertex using a greedy approach.

Protected Member Functions inherited from minlca::MinLCAGreedy< Graph >
	MinLCAGreedy (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
double	_p
	Probability of choosing a random colour.

lemon::Random	_r
	Random number generator.

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.

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::MinLCAGreedyNearestRnd< Graph >

Randomised greedy nearest colour approach for MinLCA.

Each vertex is assigned the colour which has more neighbours at distance 1, with some probability of getting a random colour. Read the report of Bachelor's Thesis Algorithms for the linear colouring arrangement problem for more information.

Definition at line 20 of file greedy-random.hh.

Constructor & Destructor Documentation

template<typename Graph = lemon::SmartGraph>

template<typename Number = unsigned long long>

minlca::MinLCAGreedyNearestRnd< Graph >::MinLCAGreedyNearestRnd	(	const Graph &	g,
		int	maxK = `0`,
		double	p = `0.0`,
		Number	seed = `0ULL`
	)

inlineprotected

Constructor.

See also: MinLCAGreedy::MinLCAGreedy(const Graph&, int); MinLCA::MinLCA(const Graph&, int)

Parameters

p	Probability of choosing a random colour
seed	Seed for the random number generator

Definition at line 43 of file greedy-random.hh.

Member Function Documentation

template<typename Graph = lemon::SmartGraph>

void minlca::MinLCAGreedyNearestRnd< Graph >::p ( double p )

inline

Change the probability of choosing a random colour.

Parameters

p	New probability

Definition at line 90 of file greedy-random.hh.

template<typename Graph = lemon::SmartGraph>

template<typename Number >

void minlca::MinLCAGreedyNearestRnd< Graph >::seed ( Number seed )

inline

Change the seed for the internal random number generator.

Parameters

seed New seed

Definition at line 99 of file greedy-random.hh.

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

minlca/greedy-random.hh

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

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

Constructor & Destructor Documentation

Member Function Documentation

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