optimisation-sa-colours.hh

Go to the documentation of this file.

#ifndef __MINLCA_MINLCA_OPTIMISATION_SA_COLOURS_HH
#define __MINLCA_MINLCA_OPTIMISATION_SA_COLOURS_HH

#include <minlca/base.hh>
#include <minlca/optimisation.hh>
#include <utils/simulated-annealing.hh>


namespace minlca
{

template<typename Graph = lemon::SmartGraph>
class MinLCAColoursSA : public MinLCAOpt<Graph>
{
  TEMPLATE_GRAPH_TYPEDEFS(Graph);
protected:
  typedef MinLCAOpt<Graph> Base; 

  class NodeSA;

  friend class NodeSA;

  utils::SimulatedAnnealing<NodeSA>
  *_sa; 
  NodeSA *_result; 
  lemon::Random *_r; 
  bool _delete_random; 
  lemon::RangeIdMap<Graph, Node> _vertex_id_map; 

  virtual void init()
  {
    Base::init();
  }

public:
  MinLCAColoursSA(
    const Graph &g,
    int maxK = 0,
    int seed = 0 
  )
    : Base(g, maxK),
      _sa(nullptr),
      _result(nullptr),
      _r(nullptr),
      _delete_random(true),
      _vertex_id_map(g)
  {
    _r = new lemon::Random(seed);
  }

  ~MinLCAColoursSA()
  {
    if (_sa != nullptr) {
      delete _sa;
    }

    if (_result != nullptr) {
      delete _result;
    }
  }

  void setRandom(
    lemon::Random *r, 
    bool deleteRandom =
      false 
  )
  {
    if (_delete_random) {
      delete _r;
    }

    _r = r;
    _delete_random = deleteRandom;
  }

  virtual void init(int steps, int stIter, int k, double lambda)
  {
    Base::init();

    if (_sa != nullptr) {
      delete _sa;
    }

    _sa = new utils::SimulatedAnnealing<NodeSA>(steps, stIter, k, lambda, *_r);

    if (_result != nullptr) {
      delete _result;
      _result = nullptr;
    }
  }

  virtual void initialSolution(const typename Base::Colouring &c)
  {
    if (_result != nullptr) {
      delete _result;
    }

    _result = new NodeSA(this, c);
  }

  virtual MinLCAStatus run()
  {
    _result->init();
    _result->run();

    _sa->init(_result);
    _result = _sa->run();

    for (NodeIt v(this->_g); v != lemon::INVALID; ++v) {
      this->setColour(v, _result->colouring()[v]);
    }

    if (_result->status() == SOLUTION_FOUND) {
      this->setSolutionFound();
    }
    else {
      this->setSolutionNotFound();
    }

    return this->status();
  }

protected:
  class NodeSA : public MinLCA<Graph>
  {
  protected:
    TEMPLATE_GRAPH_TYPEDEFS(Graph);
    typedef MinLCA<Graph> BaseLCA;
    typedef MinLCAColoursSA<Graph> BaseSA; 

    BaseSA *_sa; 
    using BaseLCA::_c;
    using BaseLCA::_lca;
    using BaseLCA::_g;
    using BaseLCA::_k;
    using BaseLCA::_max_k;
    std::vector<int> _counter; 


  public:
    NodeSA(
      BaseSA *sa, 
      const typename BaseLCA::Colouring &c, 
      MinLCAStatus s = UNDEFINED 
    )
      : BaseLCA(sa->_g, sa->_max_k), _sa(sa), _counter(_max_k)
    {
      for (NodeIt v(this->_g); v != lemon::INVALID; ++v) {
        this->setColour(v, c[v]);
      }

      this->_s = s;
    }

    virtual inline void init()
    {
      for (NodeIt v(this->_g); v != lemon::INVALID; ++v) {
        this->checkValid(v);
      }
    }

    inline void init(const std::vector<int> &oldCounter)
    {
      _counter = oldCounter;
    }

    virtual MinLCAStatus run()
    {
      if (this->status() != SOLUTION_FOUND) {
        return SOLUTION_NOT_FOUND;
      }

      for (NodeIt v(this->_g); v != lemon::INVALID; ++v) {
        checkValid(v);
      }

      return this->status();
    }

  protected:
    inline bool checkValid(
      const Node &v 
    )
    {
      if (this->status() == SOLUTION_NOT_FOUND) {
        return false;
      }

      for (IncEdgeIt e(_g, v); e != lemon::INVALID; ++e) {
        Node u = _g.oppositeNode(v, e);

        if (this->_c[u] == this->_c[v]) {
          this->setSolutionNotFound();
          return false;
        }
      }

      this->setSolutionFound();
      return true;
    }

    inline void swapColours(
      int c1, 
      int c2 
    )
    {
      for (NodeIt v(_g); v != lemon::INVALID; ++v) {
        if (this->_c[v] == c1) {
          this->setColour(v, c2);
        }
        else if (this->_c[v] == c2) {
          this->setColour(v, c1);
        }
      }
    }

    virtual inline void setColour(const Node &v, int vColour)
    {
      int old = _c[v];
      BaseLCA::setColour(v, vColour);

      if (vColour != -1) {
        ++_counter[vColour];
      }

      if (old != -1) {
        --_counter[old];
      }
    }

    inline void compress(
      int c 
    )
    {
      if (_counter[c] == 0) {
        if (_k >= c) {
          --_k;
        }

        for (NodeIt v(_g); v != lemon::INVALID; ++v) {
          if (_c[v] > c) {
            this->setColour(v, _c[v] - 1);
          }
        }
      }
    }

  public:

    NodeSA *randomNeighbour() const
    {
      NodeSA *next = nullptr;

      while (next == nullptr) {
        next = new NodeSA(_sa, _c, this->status());
        next->init(_counter);
        int diceSides = 10;

        if (this->totalColours() < _max_k) {
          diceSides = 12;
        }

        int option = _sa->_r->integer(diceSides);

        if (option >= 10) {
          Node v = _sa->_vertex_id_map(_sa->_r->integer(_sa->_vertex_id_map.size()));
          int old = _c[v];
          next->setColour(v, this->totalColours());
          next->compress(old);
        }
        else if (option <= 4) {
          int k = this->totalColours();
          int c1 = _sa->_r->integer(k - 1);
          int c2 = c1 + 1 + _sa->_r->integer(k - c1 - 1);
          next->swapColours(c1, c2);
        }
        else {
          Node v = _sa->_vertex_id_map(_sa->_r->integer(_sa->_vertex_id_map.size()));
          int c = _sa->_r->integer(this->totalColours() - 1);
          int old = _c[v];

          if (old <= c) {
            ++c;
          }

          next->setColour(v, c);
          next->compress(old);
          next->checkValid(v);
        }

        if (next->status() != SOLUTION_FOUND) {
          delete next;
          next = nullptr;
        }
      }

      return next;
    }

    inline double energy() const
    {
      if (this->status() == SOLUTION_FOUND) {
        return -static_cast<double>(this->lcaValue());
      }

      LEMON_ASSERT(false, "Using bad solution");
      return -std::numeric_limits<double>::infinity();
    }
  };

};
}

#endif