/* -*- C++ -*-

  * lemon/preflow_matching.h - Part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2005 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