
/*
**  This file forms part of the GOBLIN C++ Class Library.
**
**  Written by Christian Fremuth-Paeger, November 2000.
**  
**  Copying, compiling, distribution and modification
**  of this source code is permitted only in accordance
**  with the GOBLIN general licence information.
*/             


#if !defined(_BBCOLOUR_H_)

#define _BBCOLOUR_H_

#include <bbscheme.h>
#include <absmix.h>
#include <statstaq.h>


class BBColouring : public goblinBBNode<TNode,TFloat>
{
private:
        
    abstractMixedGraph &G;
        // The original graph
        
    bool master; // Distinguish the master problem
        
    TNode   n;
    TArc    m;
        // Dimensions of the original graph
        
    TNode   nActive;
    TNode   nDominated;
    TNode   nColoured;
        // Number of active, dominated and coloured nodes
        
    TNode                       kMax;
        // The maximum node degree (constant).
        
    TNode                       k;
        // The desired number of colours. Bounded by kMax+1,
        // and initialized to kMax.
        
    TNode                       DOMINATED;
        // Colour which indicates that a node is dominated.
        // That is, the node has small degree, and every
        // partial colouring which covers the undominated
        // nodes can be completed without conflicts.
        // Effectively, dominated nodes are deleted.
        
    TNode *                     colour;
        // Node colours

    bool*                       active;
        // True for the nodes which are neither coloured nor dominated

    TNode **                    neighbours;
        // For each colour c in 0,1,..,kMax-1 and each node v,
        // the number of neighbours of v which are coloured with c.
        
    TNode *                     conflicts;
        // For each node v, the number of colours
        // which are occupied by a neighbour of v
        // plus the number of uncoloured neighbours
        // of v.
    
    goblinIterator *    I;
        // An iterator object which is used by Set and Reduce operations.
    
    staticStack<TNode,TFloat> * Dominated;
        // A stack which is used to colour the dominated nodes
        // in the correct order.

public:

    BBColouring(abstractMixedGraph &,TNode) throw();
    BBColouring(BBColouring &) throw();
    ~BBColouring() throw();

    unsigned long   Size() throw();
    unsigned long   Allocated() throw();
    
    void            Show() throw();

private:

    void            SetColour(TNode v,TNode c) throw(ERRange,ERRejected);
    void            Reduce(TNode w = NoNode) throw(ERRange,ERRejected);

public: 

    bool            Complete() throw(ERRejected);
    void            PlanarComplete() throw(ERCheck);
    
    TNode           SelectVariable() throw();    // Select variable to branch with
    char            Direction1(TNode) throw(ERRange); // Select branching direction
    char            Direction2(TNode) throw(ERRange); // Select branching direction

    goblinBBNode<TNode,TFloat> *  Clone() throw(); // Generate a copy of the branch node
    void            Raise(TNode) throw(ERRange);   // Raise lower variable bound
    void            Lower(TNode) throw(ERRange);   // Lower upper variable bound
    TFloat          SolveRelaxation() throw();     // Returns the objective value of the relaxed
                                                   // subproblem and a corresponding solution
    TFloat          Infinity() throw() {return InfFloat;};
    void            SaveSolution() throw();      // Copy the current solution to the original instance

};                           


#endif
