greedy.hh

Go to the documentation of this file.

#ifndef __MINLCA_MINLCA_GREEDY_HH
#define __MINLCA_MINLCA_GREEDY_HH

#include <minlca/base.hh>
#include <list>
#include <vector>
#include <lemon/connectivity.h>
#include <lemon/bfs.h>
#include <utils/utils.hh>
#include <iostream>
#include <limits>
#include <cstdlib>


namespace minlca
{

template<typename Graph>
class MinLCAGreedy : public MinLCA<Graph>
{
public:
  TEMPLATE_GRAPH_TYPEDEFS(Graph);

protected:
  typedef MinLCA<Graph> Base; 
  using Base::_g;
  using Base::_c;
  using Base::_max_k;
  using Base::_lca;
  using Base::_k;

  MinLCAGreedy(const Graph &g, int maxK = 0) : Base(g, maxK)
  {
  }

  virtual void paintVertex(
    const Node &v 
  ) = 0;
};


template<template<typename> class Greedy, typename Graph = lemon::SmartGraph>
class MinLCAGreedyBfs
  : public Greedy<Graph>,
    private lemon::BfsVisitor<Graph>
{
public:
  TEMPLATE_GRAPH_TYPEDEFS(Graph);

protected:
  typedef Greedy<Graph> BaseGreedy; 
  typedef MinLCAGreedyBfs<Greedy, Graph> Visitor; 

  using BaseGreedy::_g;

  std::list<Node> _sources; 
  lemon::BfsVisit<Graph, Visitor> *_bfs; 

  friend class lemon::BfsVisit<Graph, Visitor>;

public:
  MinLCAGreedyBfs(const Graph &g, int maxK = 0)
    : BaseGreedy(g, maxK), _bfs(NULL)
  {
    _bfs = new lemon::BfsVisit<Graph, Visitor>(_g, *this);
  }

  virtual ~MinLCAGreedyBfs()
  {
    delete _bfs;
  }

  virtual void init()
  {
    BaseGreedy::init();
    _sources.clear();
    connectedComponentsSourceNodes();
    _bfs->init();
  }

  void setSourceNodes(
    const std::list<Node> &sources 
  )
  {
    _sources = sources;
  }

  void setSourceNode(
    const Node &v 
  )
  {
    _sources.clear();
    _sources.push_back(v);
  }

  virtual MinLCAStatus run()
  {
    for (Node source : _sources) {
      _bfs->addSource(source);
    }

    _bfs->start();

    if (this->status() != SOLUTION_NOT_FOUND) {
      this->setSolutionFound();
    }

    return this->status();
  }

private:
  void connectedComponentsSourceNodes()
  {
    IntNodeMap cc(_g);
    int numCc = lemon::connectedComponents(_g, cc);
    std::vector<bool> withNode(numCc, false);

    for (NodeIt v(_g); v != lemon::INVALID; ++v) {
      if (not withNode[cc[v]]) {
        _sources.push_back(v);
        withNode[cc[v]] = true;
      }
    }
  }

  void process(const Node &v)
  {
    this->paintVertex(v);
  }
};

template<typename Graph = lemon::SmartGraph>
class MinLCAGreedyNearest
  : public MinLCAGreedy<Graph>
{
  TEMPLATE_GRAPH_TYPEDEFS(Graph);

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

  MinLCAGreedyNearest(const Graph &g, int maxK = 0) : Base(g, maxK)
  {
  }

  virtual void paintVertex(const Node &v)
  {
    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);

    if (colours[vColour] == -1) {
      vColour = -1;
    }

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

template<typename Graph = lemon::SmartGraph>
class MinLCAGreedyLeastCost
  : public MinLCAGreedy<Graph>
{
  TEMPLATE_GRAPH_TYPEDEFS(Graph);
protected:
  typedef MinLCAGreedy<Graph> Base; 
  typedef long long ll;
  using Base::_g;
  using Base::_c;
  using Base::_max_k;
  using Base::_lca;
  using Base::_k;

  MinLCAGreedyLeastCost(const Graph &g, int maxK = 0) : Base(g, maxK)
  {
  }

  virtual void paintVertex(const Node &v)
  {
    std::vector<int> colourCount(_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) {
        ++colourCount[nColour];
      }
    }

    int vColour = -1;
    ll vColourCost = std::numeric_limits<ll>::max();

    for (int c = 0; c < _max_k; ++c)
      if (colourCount[c] == 0) {
        ll currentCost = 0;

        for (int nColour = 0; nColour != _max_k; ++nColour) {
          currentCost += ll(std::abs(nColour - c)) * ll(colourCount[nColour]);
        }

        if (currentCost < vColourCost) {
          vColourCost = currentCost;
          vColour = c;
        }
      }

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

template<typename Graph>
#ifndef USING_NOT_AVAILABLE
using MinLCAGreedyNearestBfs = MinLCAGreedyBfs<MinLCAGreedyNearest, Graph>;
#else
class MinLCAGreedyNearestBfs
  : public MinLCAGreedyBfs<MinLCAGreedyNearest, Graph>
{
  typedef MinLCAGreedyBfs<MinLCAGreedyNearest, Graph> Base;
public:
  MinLCAGreedyNearestBfs(const Graph &g, int maxK = 0) : Base(g, maxK)
  {
  }
};
#endif

template<typename Graph>
#ifndef USING_NOT_AVAILABLE
using MinLCAGreedyLeastCostBfs = MinLCAGreedyBfs<MinLCAGreedyLeastCost, Graph>;
#else
class MinLCAGreedyLeastCostBfs
  : public MinLCAGreedyBfs<MinLCAGreedyLeastCost, Graph>
{
  typedef MinLCAGreedyBfs<MinLCAGreedyLeastCost, Graph> Base;
public:
  MinLCAGreedyLeastCostBfs(const Graph &g, int maxK = 0) : Base(g, maxK)
  {
  }
};
#endif
}

#endif