base.hh

Go to the documentation of this file.

#ifndef __MINLCA_MINLCA_BASE_HH
#define __MINLCA_MINLCA_BASE_HH

#include <lemon/core.h>
#include <lemon/smart_graph.h>
#include <utils/graph_utils.hh>
#include <lemon/color.h>


namespace minlca
{

enum MinLCAStatus {
  UNDEFINED, 
  SOLUTION_FOUND, 
  SOLUTION_NOT_FOUND, 
};

template<typename Graph = lemon::SmartGraph>
class MinLCA
{
public:
  TEMPLATE_GRAPH_TYPEDEFS(Graph);
  typedef IntNodeMap Colouring; 

protected:
  const Graph &_g; 
  int _k; 
  int _max_k; 
  long long _lca; 
  Colouring _c; 
  MinLCAStatus _s; 

  inline void setSolutionNotFound()
  {
    _s = SOLUTION_NOT_FOUND;
  }

  inline void setSolutionFound()
  {
    _s = SOLUTION_FOUND;
  }

  virtual inline void setColour(
    const Node &v, 
    int vColour 
  )
  {
    int oldColour = _c[v];
    _c[v] = vColour;
    _k = std::max(_k, vColour);

    if (vColour == -1) {
      this->setSolutionNotFound();
    }
    else {
      for (IncEdgeIt e(_g, v); e != lemon::INVALID; ++e) {
        Node n = _g.oppositeNode(v, e);
        int nColour = _c[n];

        if (nColour != -1) {
          if (oldColour != -1) {
            _lca -= abs(nColour - oldColour);
          }

          _lca += abs(nColour - vColour);
        }
      }
    }
  }

  MinLCA(
    const Graph &g, 
    int maxK = 0 
  )
    : _g(g),
      _k(-1),
      _max_k(maxK > 0 ? maxK : 1 + utils::maxDegree(_g)),
      _lca(0),
      _c(g, -1),
      _s(UNDEFINED)
  {
  }

public:
  virtual void init()
  {
    _k = -1;
    _lca = 0;

    for (NodeIt v(_g); v != lemon::INVALID; ++v) {
      _c[v] = -1;
    }

    _s = UNDEFINED;
  }

  MinLCAStatus status() const
  {
    return _s;
  }

  virtual MinLCAStatus run()
  {
    _s = SOLUTION_NOT_FOUND;
    return status();
  }

  const Colouring &colouring() const
  {
    return _c;
  }

  int operator[](
    const Node &v 
  ) const
  {
    return _c[v];
  }

  int operator[](
    const Edge &e 
  ) const
  {
    return abs(_c[_g.u(e)] - _c[_g.v(e)]);
  }

  inline long long lcaValue() const
  {
    return _lca;
  }

  inline int totalColours() const
  {
    return _k + 1;
  }

  inline long long recalculateLca()
  {
    _lca = 0;

    for (EdgeIt e(_g); e != lemon::INVALID; ++e) {
      _lca += std::abs(_c[_g.u(e)] - _c[_g.v(e)]);
    }

    return _lca;
  }

  inline int maxK()
  {
    return _max_k;
  }
};

}

#endif