MinLCA algorithms
|
Base class for MinLCA algorithms. More...
#include <base.hh>
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 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 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. | |
Base class for MinLCA algorithms.
|
inlineprotected |
|
inline |
|
inlinevirtual |
Reset the data structures of the algorithm.
Resets the data structures of the algorithm. Must be called before its execution with run().
Reimplemented in minlca::MinLCAColoursSA< Graph >::NodeSA, minlca::MinLCAOptMip< Graph >, minlca::MinLCAVertexOrderSA< Greedy, Graph >, and minlca::MinLCAColoursSA< Graph >.
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inlinevirtual |
Run the algorithm.
Runs the algorithm and returns its status. Need to call init() before executing.
Reimplemented in minlca::MinLCAColoursSA< Graph >::NodeSA, minlca::MinLCAOptMip< Graph >, minlca::MinLCAVertexOrderSA< Greedy, Graph >, minlca::MinLCAColoursSA< Graph >, and minlca::MinLCAGreedyLpBfs< Graph >.
|
inlineprotectedvirtual |
Set the colour of a vertex.
Sets the colour of a vertex and updates the cost accordingly.
v | Vertex to set the colour to |
vColour | Colour of the vertex |
Reimplemented in minlca::MinLCAColoursSA< Graph >::NodeSA.
|
inline |