/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2007
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#ifndef LEMON_BP_MATCHING
#define LEMON_BP_MATCHING

#include <lemon/graph_utils.h>
#include <lemon/iterable_maps.h>
#include <iostream>
#include <queue>
#include <lemon/counter.h>
#include <lemon/elevator.h>

///\ingroup matching
///\file
///\brief Push-prelabel maximum matching algorithms in bipartite graphs.
///
///\todo This file slightly conflicts with \ref lemon/bipartite_matching.h
///\todo (Re)move the XYZ_TYPEDEFS macros
namespace lemon {

#define BIPARTITE_TYPEDEFS(Graph)		\
  GRAPH_TYPEDEFS(Graph)				\
    typedef Graph::ANodeIt ANodeIt;	\
    typedef Graph::BNodeIt BNodeIt;

#define UNDIRBIPARTITE_TYPEDEFS(Graph)		\
  UNDIRGRAPH_TYPEDEFS(Graph)			\
    typedef Graph::ANodeIt ANodeIt;	\
    typedef Graph::BNodeIt BNodeIt;

  template<class Graph,
	   class MT=typename Graph::template ANodeMap<typename Graph::UEdge> >
  class BpMatching {
    typedef typename Graph::Node Node;
    typedef typename Graph::ANodeIt ANodeIt;
    typedef typename Graph::BNodeIt BNodeIt;
    typedef typename Graph::UEdge UEdge;
    typedef typename Graph::IncEdgeIt IncEdgeIt;
    
    const Graph &_g;
    int _node_num;
    MT &_matching;
    Elevator<Graph,typename Graph::BNode> _levels;
    typename Graph::template BNodeMap<int> _cov;

  public:
    BpMatching(const Graph &g, MT &matching) :
      _g(g),
      _node_num(countBNodes(g)),
      _matching(matching),
      _levels(g,_node_num),
      _cov(g,0)
    {
    }
    
  private:
    void init() 
    {
//     for(BNodeIt n(g);n!=INVALID;++n) cov[n]=0;
      for(ANodeIt n(_g);n!=INVALID;++n)
	if((_matching[n]=IncEdgeIt(_g,n))!=INVALID)
	  ++_cov[_g.oppositeNode(n,_matching[n])];

      std::queue<Node> q;
      _levels.initStart();
      for(BNodeIt n(_g);n!=INVALID;++n)
	if(_cov[n]>1) {
	  _levels.initAddItem(n);
	  q.push(n);
	}
      int hlev=0;
      while(!q.empty()) {
	Node n=q.front();
	q.pop();
	int nlev=_levels[n]+1;
	for(IncEdgeIt e(_g,n);e!=INVALID;++e) {
	  Node m=_g.runningNode(e);
	  if(e==_matching[m]) {
	    for(IncEdgeIt f(_g,m);f!=INVALID;++f) {
	      Node r=_g.runningNode(f);
	      if(_levels[r]>nlev) {
		for(;nlev>hlev;hlev++)
		  _levels.initNewLevel();
		_levels.initAddItem(r);
		q.push(r);
	      }
	    }
	  }
	}
      }
      _levels.initFinish();
      for(BNodeIt n(_g);n!=INVALID;++n)
	if(_cov[n]<1&&_levels[n]<_node_num)
	  _levels.activate(n);
    }
  public:
    int run() 
    {
      init();

      Node act;
      Node bact=INVALID;
      Node last_activated=INVALID;
//       while((act=last_activated!=INVALID?
// 	     last_activated:_levels.highestActive())
// 	    !=INVALID)
      while((act=_levels.highestActive())!=INVALID) {
	last_activated=INVALID;
	int actlevel=_levels[act];
	
	UEdge bedge=INVALID;
	int nlevel=_node_num;
	{
	  int nnlevel;
	  for(IncEdgeIt tbedge(_g,act);
	      tbedge!=INVALID && nlevel>=actlevel;
	      ++tbedge)
	    if((nnlevel=_levels[_g.bNode(_matching[_g.runningNode(tbedge)])])<
	       nlevel)
	      {
		nlevel=nnlevel;
		bedge=tbedge;
	      }
	}
	if(nlevel<_node_num) {
	  if(nlevel>=actlevel)
	    _levels.liftHighestActiveTo(nlevel+1);
// 	    _levels.liftTo(act,nlevel+1);
	  bact=_g.bNode(_matching[_g.aNode(bedge)]);
	  if(--_cov[bact]<1) {
	    _levels.activate(bact);
	    last_activated=bact;
	  }
	  _matching[_g.aNode(bedge)]=bedge;
	  _cov[act]=1;
	  _levels.deactivate(act);
	}
	else {
	  if(_node_num>actlevel) 
	    _levels.liftHighestActiveTo(_node_num);
//  	    _levels.liftTo(act,_node_num);
	  _levels.deactivate(act); 
	}

	if(_levels.onLevel(actlevel)==0)
	  _levels.liftToTop(actlevel);
      }
      
      int ret=_node_num;
      for(ANodeIt n(_g);n!=INVALID;++n)
	if(_matching[n]==INVALID) ret--;
	else if (_cov[_g.bNode(_matching[n])]>1) {
	  _cov[_g.bNode(_matching[n])]--;
	  ret--;
	  _matching[n]=INVALID;
	}
      return ret;
    }
    
    ///\returns -1 if there is a perfect matching, or an empty level
    ///if it doesn't exists
    int runPerfect() 
    {
      init();

      Node act;
      Node bact=INVALID;
      Node last_activated=INVALID;
      while((act=_levels.highestActive())!=INVALID) {
	last_activated=INVALID;
	int actlevel=_levels[act];
	
	UEdge bedge=INVALID;
	int nlevel=_node_num;
	{
	  int nnlevel;
	  for(IncEdgeIt tbedge(_g,act);
	      tbedge!=INVALID && nlevel>=actlevel;
	      ++tbedge)
	    if((nnlevel=_levels[_g.bNode(_matching[_g.runningNode(tbedge)])])<
	       nlevel)
	      {
		nlevel=nnlevel;
		bedge=tbedge;
	      }
	}
	if(nlevel<_node_num) {
	  if(nlevel>=actlevel)
	    _levels.liftHighestActiveTo(nlevel+1);
	  bact=_g.bNode(_matching[_g.aNode(bedge)]);
	  if(--_cov[bact]<1) {
	    _levels.activate(bact);
	    last_activated=bact;
	  }
	  _matching[_g.aNode(bedge)]=bedge;
	  _cov[act]=1;
	  _levels.deactivate(act);
	}
	else {
	  if(_node_num>actlevel) 
	    _levels.liftHighestActiveTo(_node_num);
	  _levels.deactivate(act); 
	}

	if(_levels.onLevel(actlevel)==0)
	  return actlevel;
      }
      return -1;
    }
 
    template<class GT>
    void aBarrier(GT &bar,int empty_level=-1) 
    {
      if(empty_level==-1)
	for(empty_level=0;_levels.onLevel(empty_level);empty_level++) ;
      for(ANodeIt n(_g);n!=INVALID;++n)
	bar[n] = _matching[n]==INVALID ||
	  _levels[_g.bNode(_matching[n])]<empty_level;  
    }  
    template<class GT>
    void bBarrier(GT &bar, int empty_level=-1) 
    {
      if(empty_level==-1)
	for(empty_level=0;_levels.onLevel(empty_level);empty_level++) ;
      for(BNodeIt n(_g);n!=INVALID;++n) bar[n]=(_levels[n]>empty_level);  
    }  
  
  };
  
  
  ///Maximum cardinality of the matchings in a bipartite graph

  ///\ingroup matching
  ///This function finds the maximum cardinality of the matchings
  ///in a bipartite graph \c g.
  ///\param g An undirected bipartite graph.
  ///\return The cardinality of the maximum matching.
  ///
  ///\note The the implementation is based
  ///on the push-relabel principle.
  template<class Graph>
  int maxBpMatching(const Graph &g)
  {
    typename Graph::template ANodeMap<typename Graph::UEdge> matching(g);
    return maxBpMatching(g,matching);
  }

  ///Maximum cardinality matching in a bipartite graph

  ///\ingroup matching
  ///This function finds a maximum cardinality matching
  ///in a bipartite graph \c g.
  ///\param g An undirected bipartite graph.
  ///\retval matching A readwrite ANodeMap of value type \c Edge.
  /// The found edges will be returned in this map,
  /// i.e. for an \c ANode \c n,
  /// the edge <tt>matching[n]</tt> is the one that covers the node \c n, or
  /// \ref INVALID if it is uncovered.
  ///\return The cardinality of the maximum matching.
  ///
  ///\note The the implementation is based
  ///on the push-relabel principle.
  template<class Graph,class MT>
  int maxBpMatching(const Graph &g,MT &matching) 
  {
    return BpMatching<Graph,MT>(g,matching).run();
  }

  ///Maximum cardinality matching in a bipartite graph

  ///\ingroup matching
  ///This function finds a maximum cardinality matching
  ///in a bipartite graph \c g.
  ///\param g An undirected bipartite graph.
  ///\retval matching A readwrite ANodeMap of value type \c Edge.
  /// The found edges will be returned in this map,
  /// i.e. for an \c ANode \c n,
  /// the edge <tt>matching[n]</tt> is the one that covers the node \c n, or
  /// \ref INVALID if it is uncovered.
  ///\retval barrier A \c bool WriteMap on the BNodes. The map will be set
  /// exactly once for each BNode. The nodes with \c true value represent
  /// a barrier \e B, i.e. the cardinality of \e B minus the number of its
  /// neighbor is equal to the number of the <tt>BNode</tt>s minus the
  /// cardinality of the maximum matching.
  ///\return The cardinality of the maximum matching.
  ///
  ///\note The the implementation is based
  ///on the push-relabel principle.
  template<class Graph,class MT, class GT>
  int maxBpMatching(const Graph &g,MT &matching,GT &barrier) 
  {
    BpMatching<Graph,MT> bpm(g,matching);
    int ret=bpm.run();
    bpm.barrier(barrier);
    return ret;
  }  

  ///Perfect matching in a bipartite graph

  ///\ingroup matching
  ///This function checks whether the bipartite graph \c g
  ///has a perfect matching.
  ///\param g An undirected bipartite graph.
  ///\return \c true iff \c g has a perfect matching.
  ///
  ///\note The the implementation is based
  ///on the push-relabel principle.
  template<class Graph>
  bool perfectBpMatching(const Graph &g)
  {
    typename Graph::template ANodeMap<typename Graph::UEdge> matching(g);
    return perfectBpMatching(g,matching);
  }

  ///Perfect matching in a bipartite graph

  ///\ingroup matching
  ///This function finds a perfect matching in a bipartite graph \c g.
  ///\param g An undirected bipartite graph.
  ///\retval matching A readwrite ANodeMap of value type \c Edge.
  /// The found edges will be returned in this map,
  /// i.e. for an \c ANode \c n,
  /// the edge <tt>matching[n]</tt> is the one that covers the node \c n.
  /// The values are unspecified if the graph
  /// has no perfect matching.
  ///\return \c true iff \c g has a perfect matching.
  ///
  ///\note The the implementation is based
  ///on the push-relabel principle.
  template<class Graph,class MT>
  bool perfectBpMatching(const Graph &g,MT &matching) 
  {
    return BpMatching<Graph,MT>(g,matching).runPerfect()<0;
  }

  ///Perfect matching in a bipartite graph

  ///\ingroup matching
  ///This function finds a perfect matching in a bipartite graph \c g.
  ///\param g An undirected bipartite graph.
  ///\retval matching A readwrite ANodeMap of value type \c Edge.
  /// The found edges will be returned in this map,
  /// i.e. for an \c ANode \c n,
  /// the edge <tt>matching[n]</tt> is the one that covers the node \c n.
  /// The values are unspecified if the graph
  /// has no perfect matching.
  ///\retval barrier A \c bool WriteMap on the BNodes. The map will only
  /// be set if \c g has no perfect matching. In this case it is set 
  /// exactly once for each BNode. The nodes with \c true value represent
  /// a barrier, i.e. a subset \e B a of BNodes with the property that
  /// the cardinality of \e B is greater than the numner of its neighbors.
  ///\return \c true iff \c g has a perfect matching.
  ///
  ///\note The the implementation is based
  ///on the push-relabel principle.
  template<class Graph,class MT, class GT>
  int perfectBpMatching(const Graph &g,MT &matching,GT &barrier) 
  {
    BpMatching<Graph,MT> bpm(g,matching);
    int ret=bpm.run();
    if(ret>=0)
      bpm.barrier(barrier,ret);
    return ret<0;
  }  
}

#endif