MinLCA algorithms
Public Types | Public Member Functions | Protected Member Functions | Protected Attributes | List of all members
minlca::MinLCA< Graph > Class Template Reference

Base class for MinLCA algorithms. More...

#include <base.hh>

Inheritance diagram for minlca::MinLCA< Graph >:
[legend]

Public Types

typedef IntNodeMap Colouring
 Type for graph colourings.
 

Public Member Functions

 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 Colouringcolouring () 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 Member Functions

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

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

Base class for MinLCA algorithms.

Definition at line 29 of file base.hh.

Constructor & Destructor Documentation

template<typename Graph = lemon::SmartGraph>
minlca::MinLCA< Graph >::MinLCA ( const Graph &  g,
int  maxK = 0 
)
inlineprotected

Constructor for derived classes to use.

The constructor the derived classes should call. If the maximum number of colours is 0, sets it to \(1+ \Delta(G)\).

Parameters
gGraph being arranged
maxKMaximum number of colours allowed

Definition at line 92 of file base.hh.

Member Function Documentation

template<typename Graph = lemon::SmartGraph>
const Colouring& minlca::MinLCA< Graph >::colouring ( ) const
inline

Current colouring.

Returns
Constant reference to the colouring of the current solution

Definition at line 147 of file base.hh.

template<typename Graph = lemon::SmartGraph>
virtual void minlca::MinLCA< Graph >::init ( )
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()

Reimplemented in minlca::MinLCAColoursSA< Graph >::NodeSA, minlca::MinLCAOptMip< Graph >, minlca::MinLCAVertexOrderSA< Greedy, Graph >, and minlca::MinLCAColoursSA< Graph >.

Definition at line 112 of file base.hh.

template<typename Graph = lemon::SmartGraph>
long long minlca::MinLCA< Graph >::lcaValue ( ) const
inline

Value (cost) of the current solution.

Returns
The cost of the current solution

Definition at line 175 of file base.hh.

template<typename Graph = lemon::SmartGraph>
int minlca::MinLCA< Graph >::maxK ( )
inline

Maximum number of allowed colours.

Returns
The maximum number of allowed colours

Definition at line 205 of file base.hh.

template<typename Graph = lemon::SmartGraph>
int minlca::MinLCA< Graph >::operator[] ( const Node &  v) const
inline

Colour of a vertex.

Returns
Integer representing the colour assigned to a vertex
Parameters
vThe vertex for which we want to know the colour

Definition at line 155 of file base.hh.

template<typename Graph = lemon::SmartGraph>
int minlca::MinLCA< Graph >::operator[] ( const Edge &  e) const
inline

Cost of an edge.

Returns
The cost of an edge
Parameters
eThe edge for which we want to know the cost

Definition at line 165 of file base.hh.

template<typename Graph = lemon::SmartGraph>
long long minlca::MinLCA< Graph >::recalculateLca ( )
inline

Force a recalculation of the cost for the current solution.

Returns
The recalculated value of the cost

Definition at line 191 of file base.hh.

template<typename Graph = lemon::SmartGraph>
virtual MinLCAStatus minlca::MinLCA< 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 in minlca::MinLCAColoursSA< Graph >::NodeSA, minlca::MinLCAOptMip< Graph >, minlca::MinLCAVertexOrderSA< Greedy, Graph >, minlca::MinLCAColoursSA< Graph >, and minlca::MinLCAGreedyLpBfs< Graph >.

Definition at line 138 of file base.hh.

template<typename Graph = lemon::SmartGraph>
virtual void minlca::MinLCA< Graph >::setColour ( const Node &  v,
int  vColour 
)
inlineprotectedvirtual

Set the colour of a vertex.

Sets the colour of a vertex and updates the cost accordingly.

Parameters
vVertex to set the colour to
vColourColour of the vertex

Reimplemented in minlca::MinLCAColoursSA< Graph >::NodeSA.

Definition at line 60 of file base.hh.

template<typename Graph = lemon::SmartGraph>
int minlca::MinLCA< Graph >::totalColours ( ) const
inline

Total number of colours used.

Returns
The total number of colours used

Definition at line 183 of file base.hh.


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