minlca::MinLCAGreedyLeastCost< Graph > Class Template Reference

Greedy nearest colour approach for MinLCA. More...

#include <greedy.hh>

Inheritance diagram for minlca::MinLCAGreedyLeastCost< Graph >:

Collaboration diagram for minlca::MinLCAGreedyLeastCost< Graph >:

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

Protected Member Functions
	MinLCAGreedyLeastCost (const Graph &g, int maxK=0)
	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...

Private Member Functions
	TEMPLATE_GRAPH_TYPEDEFS (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...
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.

Detailed Description

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

Greedy nearest colour approach for MinLCA.

Each vertex is assigned the colour which least increments the cost. Read the report of Bachelor's Thesis Algorithms for the linear colouring arrangement problem for more information.

Definition at line 233 of file greedy.hh.

Constructor & Destructor Documentation

template<typename Graph = lemon::SmartGraph>

minlca::MinLCAGreedyLeastCost< Graph >::MinLCAGreedyLeastCost ( const Graph &  g, int  maxK = 0  )

inlineprotected

Constructor.

See also

MinLCAGreedy::MinLCAGreedy(const Graph&, int)

MinLCA::MinLCA(const Graph&, int)

Definition at line 250 of file greedy.hh.

---

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

• minlca/greedy.hh