|
MinLCA algorithms
|
Base class for greedy algorithms. More...
#include <greedy.hh>
Public Member Functions | |
| 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 MinLCA< Graph > | Base |
| The base class, for shorter reference. | |
Protected Member Functions | |
| MinLCAGreedy (const Graph &g, int maxK=0) | |
| Constructor for derived classes to use. More... | |
| virtual void | paintVertex (const Node &v)=0 |
| Assign a colour to a vertex using a greedy approach. 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... | |
Additional Inherited Members | |
| Public Types inherited from minlca::MinLCA< Graph > | |
| typedef IntNodeMap | Colouring |
| Type for graph colourings. | |
| 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. | |
Base class for greedy algorithms.
|
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)\).
|
protectedpure virtual |
Assign a colour to a vertex using a greedy approach.
| v | Vertex to assign a colour to |
Implemented in minlca::MinLCAGreedyLeastCost< Graph >, minlca::MinLCAGreedyNearest< Graph >, minlca::MinLCAGreedyLp< Graph >, and minlca::MinLCAGreedyNearestRnd< Graph >.
1.8.9.1
