/* -*- 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