greedy-random.hh

Go to the documentation of this file.

#ifndef __MINLCA_MINLCA_GREEDY_RANDOM_HH
#define __MINLCA_MINLCA_GREEDY_RANDOM_HH

#include <minlca/greedy.hh>
#include <lemon/random.h>


namespace minlca
{

template<typename Graph = lemon::SmartGraph>
class MinLCAGreedyNearestRnd
  : public MinLCAGreedy<Graph>
{

protected:
  typedef MinLCAGreedyNearestRnd<Graph> Greedy;
  typedef MinLCAGreedy<Graph> Base;
  using Base::_g;
  using Base::_c;
  using Base::_max_k;
  using Base::_lca;
  using Base::_k;

  double _p; 
  lemon::Random _r; 

  TEMPLATE_GRAPH_TYPEDEFS(Graph);

  template<typename Number = unsigned long long>
  MinLCAGreedyNearestRnd(
    const Graph &g,
    int maxK = 0,
    double p = 0.0, 
    Number seed = 0ULL 
  )
    : Base(g, maxK), _p(p), _r(seed)
  {
  }

  virtual void paintVertex(const Node &v)
  {
    int available = _max_k;

    std::vector<int> colours(_max_k, 0);

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

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

        if (nColour - 1 >= 0 and colours[nColour - 1] != -1) {
          ++colours[nColour - 1];
        }

        if (nColour + 1 < _max_k and colours[nColour + 1] != -1) {
          ++colours[nColour + 1];
        }
      }
    }

    int vColour = utils::posMax(colours);
    colours[vColour] = -1;

    std::vector<int> nonNeg = utils::nonNegative(colours);

    if (nonNeg.size() > 0 and _r.boolean(_p)) {
      vColour = nonNeg[_r.integer(0, static_cast<int>(nonNeg.size()))];
    }

    this->setColour(v, vColour);
  }

public:
  void p(
    double p 
  )
  {
    _p = p;
  }

  template<typename Number>
  void seed(
    Number seed 
  )
  {
    _r.seed(seed);
  }
};

template<typename Graph>
#ifndef USING_NOT_AVAILABLE
using MinLCAGreedyNearestRndBfs =
  MinLCAGreedyBfs<MinLCAGreedyNearestRnd, Graph>;
#else
class MinLCAGreedyNearestRndBfs
  : public MinLCAGreedyBfs<MinLCAGreedyNearestRnd, Graph>
{
  typedef MinLCAGreedyBfs<MinLCAGreedyNearestRnd, Graph> Base;
public:
  template<typename Number = unsigned long long>
  MinLCAGreedyNearestRndBfs(const Graph &g, int maxK = 0, double p = 0.0,
                            Number seed = 0ULL)
    : Base(g, maxK)
  {
  }
};
#endif

}

#endif