optimisation-sa-greedy.hh

Go to the documentation of this file.

#ifndef __MINLCA_MINLCA_OPTIMISATION_SA_GREEDY_HH
#define __MINLCA_MINLCA_OPTIMISATION_SA_GREEDY_HH

#include <vector>
#include <minlca/base.hh>
#include <utils/simulated-annealing.hh>
#include <lemon/bfs.h>
#include <lemon/connectivity.h>


namespace minlca
{

template<template<typename> class Greedy, typename Graph = lemon::SmartGraph>
class MinLCAVertexOrderSA
  : public MinLCA<Graph>, private lemon::BfsVisitor<Graph>
{
  TEMPLATE_GRAPH_TYPEDEFS(Graph);
protected:
  typedef MinLCA<Graph> BaseLCA;
  typedef MinLCAVertexOrderSA<Greedy, Graph> SAorder;

  class GreedyNodeSA;

  friend class GreedyNodeSA;

  friend class lemon::BfsVisit<Graph, SAorder>;

  utils::SimulatedAnnealing<GreedyNodeSA>
  *_sa; 
  GreedyNodeSA
  *_result; 
  lemon::Random *_r; 
  bool _delete_random; 
  std::vector<Node> _order; 

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

public:
  MinLCAVertexOrderSA(
    const Graph &g,
    int maxK = 0,
    int seed = 0 
  )
    : BaseLCA(g, maxK),
      _sa(nullptr),
      _result(nullptr),
      _r(nullptr),
      _delete_random(true)
  {
    _order.reserve(lemon::countNodes(g));
    _r = new lemon::Random(seed);
  }

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

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

    if (_delete_random) {
      delete _r;
    }
  }

  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,
    bool initial = false 
  )
  {
    BaseLCA::init();

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

    _sa = new utils::SimulatedAnnealing<GreedyNodeSA>(steps, stIter, k, lambda,
        *_r);
    _order.clear();

    if (initial) {
      lemon::BfsVisit<Graph, SAorder> bfs(this->_g, *this);
      bfs.init();

      IntNodeMap cc(this->_g);
      int numCc = lemon::connectedComponents(this->_g, cc);
      std::vector<bool> withNode(numCc, false);

      for (NodeIt v(this->_g); v != lemon::INVALID; ++v) {
        if (not withNode[cc[v]]) {
          bfs.addSource(v);
          withNode[cc[v]] = true;
        }
      }

      bfs.run();
    }
    else {
      for (NodeIt v(this->_g); v != lemon::INVALID; ++v) {
        _order.push_back(v);
      }

      int n = lemon::countNodes(this->_g);

      for (int i = 0; i < n; ++i) {
        std::swap(_order[i], _order[_r->integer(i, n)]);
      }
    }

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


  virtual MinLCAStatus run()
  {
    _result = new GreedyNodeSA(this, _order);
    _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 GreedyNodeSA : public Greedy<Graph>
  {
  private:
    typedef Greedy<Graph> Base;
    std::vector<Node> _order;
    SAorder *_sa; 

  public:
    GreedyNodeSA(
      SAorder *sa, 
      const std::vector<Node> &initial 
    )
      : Base(sa->_g, sa->_max_k),
        _order(initial),
        _sa(sa)
    {
    }

    inline double energy()
    {
      if (this->status() == SOLUTION_FOUND) {
        return -static_cast<double>(this->lcaValue());
      }
      else {
        return -std::numeric_limits<double>::infinity();
      }
    }

    virtual MinLCAStatus run(
      int idx = 0 
    )
    {
      for (int i = idx; i < _order.size(); ++i) {
        this->paintVertex(_order[i]);
      }

      if (this->status() != SOLUTION_NOT_FOUND) {
        this->setSolutionFound();
      }

      return this->status();
    }

    MinLCAStatus run(
      const typename BaseLCA::Colouring
      &c, 
      int idx 
    )
    {
      for (int i = 0; i < idx; ++i) {
        this->setColour(_order[i], c[_order[i]]);
      }

      return run(idx);
    }

    GreedyNodeSA *randomNeighbour()
    {
      GreedyNodeSA *neighbour = new GreedyNodeSA(_sa, _order);
      int n = _order.size();
      int u = _sa->_r->integer(n - 1);
      int v = u + 1 + _sa->_r->integer(n - u - 1);
      std::swap(neighbour->_order[u], neighbour->_order[v]);
      neighbour->init();
      neighbour->run(this->_c, u);

      return neighbour;
    }
  };

private:
  void process(const Node &v)
  {
    _order.push_back(v);
  }
};
}

#endif