cliques.hh

Go to the documentation of this file.

#ifndef __MINLCA_UTILS_GENERATORS_CLIQUES_HH
#define __MINLCA_UTILS_GENERATORS_CLIQUES_HH

#include <lemon/smart_graph.h>
#include <lemon/random.h>
#include <utils/generators/random-graph.hh>


namespace minlca
{
namespace utils
{

template<typename BaseGraph = lemon::SmartGraph>
class CliqueSet : public BaseGraph
{
protected:
  typedef CliqueSet<BaseGraph> Graph;
  int _s; 
  int _c; 

public:
  virtual Graph &init(
    int s, 
    int c 
  )
  {
    _s = s;
    _c = c;

    return *this;
  }

  int cliqueOrder() const
  {
    return _s;
  }

  int cliques() const
  {
    return _c;
  }

  virtual void generate()
  {
    this->clear();
    this->reserveNode(_c * _s);

    for (int i = 0; i < _c; ++i) {
      for (int j = 0; j < _s; ++j) {
        this->addNode();

        for (int l = i * _s; l < i * _s + j; ++l) {
          this->addEdge(this->nodeFromId(l), this->nodeFromId(i * _s + j));
        }
      }
    }
  }
};

template<typename BaseGraph = lemon::SmartGraph>
class CliqueCycle : public CliqueSet<BaseGraph>
{
protected:
  typedef CliqueCycle<BaseGraph> Graph;
  typedef CliqueSet<BaseGraph> Base;
  using Base::_s;
  using Base::_c;

public:
  virtual Graph &init(int s, int c)
  {
    Base::init(s, c);

    return *this;
  }

  virtual void generate()
  {
    Base::generate();

    for (int i = 0; i < _c - 1; ++i) {
      this->addEdge(this->nodeFromId(i * _s), this->nodeFromId(i * _s + 1));
    }

    this->addEdge(this->nodeFromId((_c - 1) * _s), this->nodeFromId(1));
  }
};

template<typename BaseGraph = lemon::SmartGraph>
class CliqueGraph : public RandomGraph<CliqueSet<BaseGraph>>
{
protected:
  typedef CliqueGraph<BaseGraph> Graph;
  typedef RandomGraph<CliqueSet<BaseGraph>> Base;
  using Base::_s;
  using Base::_c;
  using Base::_r;
  double _p; 

public:
  template<typename Number = int>
  CliqueGraph(Number seed = 0)
    : Base(seed)
  {
  }

  CliqueGraph(lemon::Random &r)
    : Base(r)
  {
  }

  double p()
  {
    return _p;
  }

  virtual Graph &init(
    int s,
    int c,
    double p 
  )
  {
    Base::init(s, c);
    _p = std::max(0.0, std::min(1.0, p));

    return *this;
  }

  virtual void generate()
  {
    CliqueSet<BaseGraph>::generate();

    for (int i = 0; i < _c; ++i) {
      for (int j = i + 1; j < _c; ++j)
        if (_r->boolean(_p))
          this->addEdge(this->nodeFromId(i * _s + _r->integer(_s)),
                        this->nodeFromId(j * _s + _r->integer(_s)));
    }
  }
};
}
}

#endif