greedy-lp.hh

Go to the documentation of this file.

#ifndef __MINLCA_MINLCA_GREEDY_LP_HH
#define __MINLCA_MINLCA_GREEDY_LP_HH

#include <minlca/greedy.hh>
#include "lp-model.hh"


namespace minlca
{

template<typename Graph = lemon::SmartGraph>
class MinLCAGreedyLp
  : public MinLCAGreedy<Graph>
{
  friend class lemon::BfsVisit<Graph, MinLCAGreedyLp<Graph>>;

protected:
  TEMPLATE_GRAPH_TYPEDEFS(Graph);
  typedef MinLCAGreedy<Graph> Base; 
  using Base::_g;
  using Base::_c;
  using Base::_max_k;
  using Base::_lca;
  using Base::_k;

  MinLCALpModel<Graph> model; 

  MinLCAGreedyLp(const Graph &g, int maxK = 0)
    : Base(g, maxK), model(g, _max_k)
  {
  }

  void solveModel()
  {
    model.solve();
  }

  virtual void paintVertex(const Node &v)
  {

    std::vector<bool> colours(_max_k, true);

    for (IncEdgeIt e(_g, v); e != lemon::INVALID; ++e) {
      Node n = _g.oppositeNode(v, e);
      int nColour = _c[n];

      if (nColour != -1) {
        colours[nColour] = false;
      }
    }

    std::vector<int> colourOrder = model.getColourOrder(v);
    int vColour = -1;

    for (int i = 0; i < _max_k and vColour == -1; ++i) {
      int currentColour = colourOrder[i];

      if (colours[currentColour]) {
        vColour = currentColour;
      }
    }

    this->setColour(v, vColour);
  }
};


template<typename Graph = lemon::SmartGraph>
class MinLCAGreedyLpBfs :
  public MinLCAGreedyBfs<MinLCAGreedyLp, Graph>
{
  typedef MinLCAGreedyBfs<MinLCAGreedyLp, Graph> Base;
public:
  MinLCAGreedyLpBfs(const Graph &g, int maxK = 0) : Base(g, maxK)
  {
  }

  virtual MinLCAStatus run()
  {
    this->solveModel();
    return Base::run();
  }
};
}

#endif