outerplanar.hh

Go to the documentation of this file.

#ifndef __MINLCA_UTILS_GENERATORS_OUTERPLANAR_HH
#define __MINLCA_UTILS_GENERATORS_OUTERPLANAR_HH

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


namespace minlca
{
namespace utils
{

template<typename BaseGraph = lemon::SmartGraph>
class RandomOuterplanar : public RandomGraph<BaseGraph>
{
protected:
  typedef RandomOuterplanar<BaseGraph> Graph;
  typedef RandomGraph<BaseGraph> Base;

public:
  TEMPLATE_GRAPH_TYPEDEFS(Graph);

protected:
  using Base::_r;
  int _n; 
  int _side_a; 

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

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

  Graph &init(
    int n 
  )
  {
    _n = n;
    return *this;
  }

  virtual void generate()
  {
    using namespace lemon;
    this->clear();
    this->reserveNode(_n);
    this->reserveEdge(2 * _n);

    _side_a = _r->integer(1, _n / 2);

    for (int i = 0; i < _n; ++i) {
      this->addNode();
    }

    _crossingChords(0, _side_a - 1, _side_a, _n - 1);

    for (int i = 0; i < _side_a - 1; ++i)
      if (findEdge(*this, this->nodeFromId(i), this->nodeFromId(i + 1)) == INVALID) {
        this->addEdge(this->nodeFromId(i), this->nodeFromId(i + 1));
      }

    for (int i = _side_a; i < _n - 1; ++i)
      if (findEdge(*this, this->nodeFromId(i), this->nodeFromId(i + 1)) == INVALID) {
        this->addEdge(this->nodeFromId(i), this->nodeFromId(i + 1));
      }

    if (findEdge(*this, this->nodeFromId(0),
                 this->nodeFromId(_side_a)) == INVALID) {
      this->addEdge(this->nodeFromId(0), this->nodeFromId(_side_a));
    }

    if (findEdge(*this, this->nodeFromId(_side_a - 1),
                 this->nodeFromId(_n - 1)) == INVALID) {
      this->addEdge(this->nodeFromId(_side_a - 1), this->nodeFromId(_n - 1));
    }

    int bridgeLeft = 0;

    while (bridgeLeft < _side_a) {
      while (bridgeLeft < _side_a
             and degree(*this, this->nodeFromId(bridgeLeft)) > 2) {
        ++bridgeLeft;
      }

      int bridgeRight = bridgeLeft;

      while (bridgeRight < _side_a
             and degree(*this, this->nodeFromId(bridgeRight)) == 2) {
        ++bridgeRight;
      }

      if (bridgeRight < _side_a) {
        _bridges(bridgeLeft, bridgeRight);
      }

      bridgeLeft = bridgeRight + 1;
    }

    bridgeLeft = _side_a;

    while (bridgeLeft < _n) {
      while (bridgeLeft < _n and degree(*this, this->nodeFromId(bridgeLeft)) > 2) {
        ++bridgeLeft;
      }

      int bridgeRight = bridgeLeft;

      while (bridgeRight < _n
             and degree(*this, this->nodeFromId(bridgeRight)) == 2) {
        ++bridgeRight;
      }

      if (bridgeRight < _n) {
        _bridges(bridgeLeft, bridgeRight);
      }

      bridgeLeft = bridgeRight + 1;
    }
  }

  int sideA() const
  {
    return _side_a;
  }

protected:
  void _crossingChords(int l1, int r1, int l2, int r2)
  {
    if (r1 < l1 or r2 < l2) {
      return;
    }

    int top = _r->integer(l1, r1 + 1);
    int bottom = _r->integer(l2, r2 + 1);
    this->addEdge(this->nodeFromId(top), this->nodeFromId(bottom));

    if (_r->boolean()) {
      _crossingChords(l1, top, l2, bottom - 1);
    }
    else {
      _crossingChords(l1, top - 1, l2, bottom);
    }

    if (_r->boolean()) {
      _crossingChords(top, r1, bottom + 1, r2);
    }
    else {
      _crossingChords(top + 1, r1, bottom, r2);
    }
  }

  void _bridges(int l, int r)
  {
    if (r < l + 2) {
      return;
    }

    if (_r->boolean()) {
      this->addEdge(this->nodeFromId(l), this->nodeFromId(r));
    }

    switch (_r->integer(3)) {
    case 0:
      _bridges(l + 1, r - 1);
      break;

    case 1:
      _bridges(l, r - 1);
      break;

    default:
      _bridges(l + 1, r);
    }
  }
};
}
}

#endif