Use the relaxed linear model as a base for colour preferences. More...

#include <greedy-lp.hh>

Inheritance diagram for minlca::MinLCAGreedyLp< Graph >:

Collaboration diagram for minlca::MinLCAGreedyLp< Graph >:

Protected Types
typedef MinLCAGreedy< Graph >	Base
	The greedy base class.

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

Protected Member Functions
	TEMPLATE_GRAPH_TYPEDEFS (Graph)

	MinLCAGreedyLp (const Graph &g, int maxK=0)
	Constructor. More...

void	solveModel ()

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
MinLCALpModel< Graph >	model
	Relaxed linear model for the graph.

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.

Friends
class	lemon::BfsVisit< Graph, MinLCAGreedyLp< Graph > >

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

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

Detailed Description

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

Use the relaxed linear model as a base for colour preferences.

Each vertex is assigned the colour according to the preferences derived from solving the linear model. Read the report of Bachelor's Thesis Algorithms for the linear colouring arrangement problem for more information (one of the discarded greedy approaches).