alpar@2353: /* -*- C++ -*-
alpar@2353:  * lemon/preflow_matching.h - Part of LEMON, a generic C++ optimization library
alpar@2353:  *
alpar@2353:  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@2353:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@2353:  *
alpar@2353:  * Permission to use, modify and distribute this software is granted
alpar@2353:  * provided that this copyright notice appears in all copies. For
alpar@2353:  * precise terms see the accompanying LICENSE file.
alpar@2353:  *
alpar@2353:  * This software is provided "AS IS" with no warranty of any kind,
alpar@2353:  * express or implied, and with no claim as to its suitability for any
alpar@2353:  * purpose.
alpar@2353:  *
alpar@2353:  */
alpar@2353: 
alpar@2353: #ifndef LEMON_BP_MATCHING
alpar@2353: #define LEMON_BP_MATCHING
alpar@2353: 
alpar@2353: #include <lemon/graph_utils.h>
alpar@2353: #include <lemon/iterable_maps.h>
alpar@2353: #include <iostream>
alpar@2353: #include <queue>
alpar@2353: #include <lemon/counter.h>
alpar@2353: #include <lemon/elevator.h>
alpar@2353: 
alpar@2353: ///\ingroup matching
alpar@2353: ///\file
alpar@2353: ///\brief Push-prelabel maximum matching algorithms in bipartite graphs.
alpar@2353: ///
alpar@2353: ///\todo This file slightly conflicts with \ref lemon/bipartite_matching.h
alpar@2353: ///\todo (Re)move the XYZ_TYPEDEFS macros
alpar@2353: namespace lemon {
alpar@2353: 
alpar@2353: #define BIPARTITE_TYPEDEFS(Graph)		\
alpar@2353:   GRAPH_TYPEDEFS(Graph)				\
alpar@2353:     typedef Graph::ANodeIt ANodeIt;	\
alpar@2353:     typedef Graph::BNodeIt BNodeIt;
alpar@2353: 
alpar@2353: #define UNDIRBIPARTITE_TYPEDEFS(Graph)		\
alpar@2353:   UNDIRGRAPH_TYPEDEFS(Graph)			\
alpar@2353:     typedef Graph::ANodeIt ANodeIt;	\
alpar@2353:     typedef Graph::BNodeIt BNodeIt;
alpar@2353: 
alpar@2353:   template<class Graph,
alpar@2353: 	   class MT=typename Graph::template ANodeMap<typename Graph::UEdge> >
alpar@2353:   class BpMatching {
alpar@2353:     typedef typename Graph::Node Node;
alpar@2353:     typedef typename Graph::ANodeIt ANodeIt;
alpar@2353:     typedef typename Graph::BNodeIt BNodeIt;
alpar@2353:     typedef typename Graph::UEdge UEdge;
alpar@2353:     typedef typename Graph::IncEdgeIt IncEdgeIt;
alpar@2353:     
alpar@2353:     const Graph &_g;
alpar@2353:     int _node_num;
alpar@2353:     MT &_matching;
alpar@2353:     Elevator<Graph,typename Graph::BNode> _levels;
alpar@2353:     typename Graph::template BNodeMap<int> _cov;
alpar@2353: 
alpar@2353:   public:
alpar@2353:     BpMatching(const Graph &g, MT &matching) :
alpar@2353:       _g(g),
alpar@2353:       _node_num(countBNodes(g)),
alpar@2353:       _matching(matching),
alpar@2353:       _levels(g,_node_num),
alpar@2353:       _cov(g,0)
alpar@2353:     {
alpar@2353:     }
alpar@2353:     
alpar@2353:   private:
alpar@2353:     void init() 
alpar@2353:     {
alpar@2353: //     for(BNodeIt n(g);n!=INVALID;++n) cov[n]=0;
alpar@2353:       for(ANodeIt n(_g);n!=INVALID;++n)
alpar@2353: 	if((_matching[n]=IncEdgeIt(_g,n))!=INVALID)
alpar@2353: 	  ++_cov[_g.oppositeNode(n,_matching[n])];
alpar@2353: 
alpar@2353:       std::queue<Node> q;
alpar@2353:       _levels.initStart();
alpar@2353:       for(BNodeIt n(_g);n!=INVALID;++n)
alpar@2353: 	if(_cov[n]>1) {
alpar@2353: 	  _levels.initAddItem(n);
alpar@2353: 	  q.push(n);
alpar@2353: 	}
alpar@2353:       int hlev=0;
alpar@2353:       while(!q.empty()) {
alpar@2353: 	Node n=q.front();
alpar@2353: 	q.pop();
alpar@2353: 	int nlev=_levels[n]+1;
alpar@2353: 	for(IncEdgeIt e(_g,n);e!=INVALID;++e) {
alpar@2353: 	  Node m=_g.runningNode(e);
alpar@2353: 	  if(e==_matching[m]) {
alpar@2353: 	    for(IncEdgeIt f(_g,m);f!=INVALID;++f) {
alpar@2353: 	      Node r=_g.runningNode(f);
alpar@2353: 	      if(_levels[r]>nlev) {
alpar@2353: 		for(;nlev>hlev;hlev++)
alpar@2353: 		  _levels.initNewLevel();
alpar@2353: 		_levels.initAddItem(r);
alpar@2353: 		q.push(r);
alpar@2353: 	      }
alpar@2353: 	    }
alpar@2353: 	  }
alpar@2353: 	}
alpar@2353:       }
alpar@2353:       _levels.initFinish();
alpar@2353:       for(BNodeIt n(_g);n!=INVALID;++n)
alpar@2353: 	if(_cov[n]<1&&_levels[n]<_node_num)
alpar@2353: 	  _levels.activate(n);
alpar@2353:     }
alpar@2353:   public:
alpar@2353:     int run() 
alpar@2353:     {
alpar@2353:       init();
alpar@2353: 
alpar@2353:       Node act;
alpar@2353:       Node bact=INVALID;
alpar@2353:       Node last_activated=INVALID;
alpar@2353: //       while((act=last_activated!=INVALID?
alpar@2353: // 	     last_activated:_levels.highestActive())
alpar@2353: // 	    !=INVALID)
alpar@2353:       while((act=_levels.highestActive())!=INVALID) {
alpar@2353: 	last_activated=INVALID;
alpar@2353: 	int actlevel=_levels[act];
alpar@2353: 	
alpar@2353: 	UEdge bedge=INVALID;
alpar@2353: 	int nlevel=_node_num;
alpar@2353: 	{
alpar@2353: 	  int nnlevel;
alpar@2353: 	  for(IncEdgeIt tbedge(_g,act);
alpar@2353: 	      tbedge!=INVALID && nlevel>=actlevel;
alpar@2353: 	      ++tbedge)
alpar@2353: 	    if((nnlevel=_levels[_g.bNode(_matching[_g.runningNode(tbedge)])])<
alpar@2353: 	       nlevel)
alpar@2353: 	      {
alpar@2353: 		nlevel=nnlevel;
alpar@2353: 		bedge=tbedge;
alpar@2353: 	      }
alpar@2353: 	}
alpar@2353: 	if(nlevel<_node_num) {
alpar@2353: 	  if(nlevel>=actlevel)
alpar@2353: 	    _levels.liftHighestActiveTo(nlevel+1);
alpar@2353: // 	    _levels.liftTo(act,nlevel+1);
alpar@2353: 	  bact=_g.bNode(_matching[_g.aNode(bedge)]);
alpar@2353: 	  if(--_cov[bact]<1) {
alpar@2353: 	    _levels.activate(bact);
alpar@2353: 	    last_activated=bact;
alpar@2353: 	  }
alpar@2353: 	  _matching[_g.aNode(bedge)]=bedge;
alpar@2353: 	  _cov[act]=1;
alpar@2353: 	  _levels.deactivate(act);
alpar@2353: 	}
alpar@2353: 	else {
alpar@2353: 	  if(_node_num>actlevel) 
alpar@2353: 	    _levels.liftHighestActiveTo(_node_num);
alpar@2353: //  	    _levels.liftTo(act,_node_num);
alpar@2353: 	  _levels.deactivate(act); 
alpar@2353: 	}
alpar@2353: 
alpar@2353: 	if(_levels.onLevel(actlevel)==0)
alpar@2353: 	  _levels.liftToTop(actlevel);
alpar@2353:       }
alpar@2353:       
alpar@2353:       int ret=_node_num;
alpar@2353:       for(ANodeIt n(_g);n!=INVALID;++n)
alpar@2353: 	if(_matching[n]==INVALID) ret--;
alpar@2353: 	else if (_cov[_g.bNode(_matching[n])]>1) {
alpar@2353: 	  _cov[_g.bNode(_matching[n])]--;
alpar@2353: 	  ret--;
alpar@2353: 	  _matching[n]=INVALID;
alpar@2353: 	}
alpar@2353:       return ret;
alpar@2353:     }
alpar@2353:     
alpar@2353:     ///\returns -1 if there is a perfect matching, or an empty level
alpar@2353:     ///if it doesn't exists
alpar@2353:     int runPerfect() 
alpar@2353:     {
alpar@2353:       init();
alpar@2353: 
alpar@2353:       Node act;
alpar@2353:       Node bact=INVALID;
alpar@2353:       Node last_activated=INVALID;
alpar@2353:       while((act=_levels.highestActive())!=INVALID) {
alpar@2353: 	last_activated=INVALID;
alpar@2353: 	int actlevel=_levels[act];
alpar@2353: 	
alpar@2353: 	UEdge bedge=INVALID;
alpar@2353: 	int nlevel=_node_num;
alpar@2353: 	{
alpar@2353: 	  int nnlevel;
alpar@2353: 	  for(IncEdgeIt tbedge(_g,act);
alpar@2353: 	      tbedge!=INVALID && nlevel>=actlevel;
alpar@2353: 	      ++tbedge)
alpar@2353: 	    if((nnlevel=_levels[_g.bNode(_matching[_g.runningNode(tbedge)])])<
alpar@2353: 	       nlevel)
alpar@2353: 	      {
alpar@2353: 		nlevel=nnlevel;
alpar@2353: 		bedge=tbedge;
alpar@2353: 	      }
alpar@2353: 	}
alpar@2353: 	if(nlevel<_node_num) {
alpar@2353: 	  if(nlevel>=actlevel)
alpar@2353: 	    _levels.liftHighestActiveTo(nlevel+1);
alpar@2353: 	  bact=_g.bNode(_matching[_g.aNode(bedge)]);
alpar@2353: 	  if(--_cov[bact]<1) {
alpar@2353: 	    _levels.activate(bact);
alpar@2353: 	    last_activated=bact;
alpar@2353: 	  }
alpar@2353: 	  _matching[_g.aNode(bedge)]=bedge;
alpar@2353: 	  _cov[act]=1;
alpar@2353: 	  _levels.deactivate(act);
alpar@2353: 	}
alpar@2353: 	else {
alpar@2353: 	  if(_node_num>actlevel) 
alpar@2353: 	    _levels.liftHighestActiveTo(_node_num);
alpar@2353: 	  _levels.deactivate(act); 
alpar@2353: 	}
alpar@2353: 
alpar@2353: 	if(_levels.onLevel(actlevel)==0)
alpar@2353: 	  return actlevel;
alpar@2353:       }
alpar@2353:       return -1;
alpar@2353:     }
alpar@2353:  
alpar@2353:     template<class GT>
alpar@2353:     void aBarrier(GT &bar,int empty_level=-1) 
alpar@2353:     {
alpar@2353:       if(empty_level==-1)
alpar@2353: 	for(empty_level=0;_levels.onLevel(empty_level);empty_level++) ;
alpar@2353:       for(ANodeIt n(_g);n!=INVALID;++n)
alpar@2353: 	bar[n] = _matching[n]==INVALID ||
alpar@2353: 	  _levels[_g.bNode(_matching[n])]<empty_level;  
alpar@2353:     }  
alpar@2353:     template<class GT>
alpar@2353:     void bBarrier(GT &bar, int empty_level=-1) 
alpar@2353:     {
alpar@2353:       if(empty_level==-1)
alpar@2353: 	for(empty_level=0;_levels.onLevel(empty_level);empty_level++) ;
alpar@2353:       for(BNodeIt n(_g);n!=INVALID;++n) bar[n]=(_levels[n]>empty_level);  
alpar@2353:     }  
alpar@2353:   
alpar@2353:   };
alpar@2353:   
alpar@2353:   
alpar@2353:   ///Maximum cardinality of the matchings in a bipartite graph
alpar@2353: 
alpar@2353:   ///\ingroup matching
alpar@2353:   ///This function finds the maximum cardinality of the matchings
alpar@2353:   ///in a bipartite graph \c g.
alpar@2353:   ///\param g An undirected bipartite graph.
alpar@2353:   ///\return The cardinality of the maximum matching.
alpar@2353:   ///
alpar@2353:   ///\note The the implementation is based
alpar@2353:   ///on the push-relabel principle.
alpar@2353:   template<class Graph>
alpar@2353:   int maxBpMatching(const Graph &g)
alpar@2353:   {
alpar@2353:     typename Graph::template ANodeMap<typename Graph::UEdge> matching(g);
alpar@2353:     return maxBpMatching(g,matching);
alpar@2353:   }
alpar@2353: 
alpar@2353:   ///Maximum cardinality matching in a bipartite graph
alpar@2353: 
alpar@2353:   ///\ingroup matching
alpar@2353:   ///This function finds a maximum cardinality matching
alpar@2353:   ///in a bipartite graph \c g.
alpar@2353:   ///\param g An undirected bipartite graph.
alpar@2353:   ///\retval matching A readwrite ANodeMap of value type \c Edge.
alpar@2353:   /// The found edges will be returned in this map,
alpar@2353:   /// i.e. for an \c ANode \c n,
alpar@2353:   /// the edge <tt>matching[n]</tt> is the one that covers the node \c n, or
alpar@2353:   /// \ref INVALID if it is uncovered.
alpar@2353:   ///\return The cardinality of the maximum matching.
alpar@2353:   ///
alpar@2353:   ///\note The the implementation is based
alpar@2353:   ///on the push-relabel principle.
alpar@2353:   template<class Graph,class MT>
alpar@2353:   int maxBpMatching(const Graph &g,MT &matching) 
alpar@2353:   {
alpar@2353:     return BpMatching<Graph,MT>(g,matching).run();
alpar@2353:   }
alpar@2353: 
alpar@2353:   ///Maximum cardinality matching in a bipartite graph
alpar@2353: 
alpar@2353:   ///\ingroup matching
alpar@2353:   ///This function finds a maximum cardinality matching
alpar@2353:   ///in a bipartite graph \c g.
alpar@2353:   ///\param g An undirected bipartite graph.
alpar@2353:   ///\retval matching A readwrite ANodeMap of value type \c Edge.
alpar@2353:   /// The found edges will be returned in this map,
alpar@2353:   /// i.e. for an \c ANode \c n,
alpar@2353:   /// the edge <tt>matching[n]</tt> is the one that covers the node \c n, or
alpar@2353:   /// \ref INVALID if it is uncovered.
alpar@2353:   ///\retval barrier A \c bool WriteMap on the BNodes. The map will be set
alpar@2353:   /// exactly once for each BNode. The nodes with \c true value represent
alpar@2353:   /// a barrier \e B, i.e. the cardinality of \e B minus the number of its
alpar@2353:   /// neighbor is equal to the number of the <tt>BNode</tt>s minus the
alpar@2353:   /// cardinality of the maximum matching.
alpar@2353:   ///\return The cardinality of the maximum matching.
alpar@2353:   ///
alpar@2353:   ///\note The the implementation is based
alpar@2353:   ///on the push-relabel principle.
alpar@2353:   template<class Graph,class MT, class GT>
alpar@2353:   int maxBpMatching(const Graph &g,MT &matching,GT &barrier) 
alpar@2353:   {
alpar@2353:     BpMatching<Graph,MT> bpm(g,matching);
alpar@2353:     int ret=bpm.run();
alpar@2353:     bpm.barrier(barrier);
alpar@2353:     return ret;
alpar@2353:   }  
alpar@2353: 
alpar@2353:   ///Perfect matching in a bipartite graph
alpar@2353: 
alpar@2353:   ///\ingroup matching
alpar@2353:   ///This function checks whether the bipartite graph \c g
alpar@2353:   ///has a perfect matching.
alpar@2353:   ///\param g An undirected bipartite graph.
alpar@2353:   ///\return \c true iff \c g has a perfect matching.
alpar@2353:   ///
alpar@2353:   ///\note The the implementation is based
alpar@2353:   ///on the push-relabel principle.
alpar@2353:   template<class Graph>
alpar@2353:   bool perfectBpMatching(const Graph &g)
alpar@2353:   {
alpar@2353:     typename Graph::template ANodeMap<typename Graph::UEdge> matching(g);
alpar@2353:     return perfectBpMatching(g,matching);
alpar@2353:   }
alpar@2353: 
alpar@2353:   ///Perfect matching in a bipartite graph
alpar@2353: 
alpar@2353:   ///\ingroup matching
alpar@2353:   ///This function finds a perfect matching in a bipartite graph \c g.
alpar@2353:   ///\param g An undirected bipartite graph.
alpar@2353:   ///\retval matching A readwrite ANodeMap of value type \c Edge.
alpar@2353:   /// The found edges will be returned in this map,
alpar@2353:   /// i.e. for an \c ANode \c n,
alpar@2353:   /// the edge <tt>matching[n]</tt> is the one that covers the node \c n.
alpar@2353:   /// The values are unspecified if the graph
alpar@2353:   /// has no perfect matching.
alpar@2353:   ///\return \c true iff \c g has a perfect matching.
alpar@2353:   ///
alpar@2353:   ///\note The the implementation is based
alpar@2353:   ///on the push-relabel principle.
alpar@2353:   template<class Graph,class MT>
alpar@2353:   bool perfectBpMatching(const Graph &g,MT &matching) 
alpar@2353:   {
alpar@2353:     return BpMatching<Graph,MT>(g,matching).runPerfect()<0;
alpar@2353:   }
alpar@2353: 
alpar@2353:   ///Perfect matching in a bipartite graph
alpar@2353: 
alpar@2353:   ///\ingroup matching
alpar@2353:   ///This function finds a perfect matching in a bipartite graph \c g.
alpar@2353:   ///\param g An undirected bipartite graph.
alpar@2353:   ///\retval matching A readwrite ANodeMap of value type \c Edge.
alpar@2353:   /// The found edges will be returned in this map,
alpar@2353:   /// i.e. for an \c ANode \c n,
alpar@2353:   /// the edge <tt>matching[n]</tt> is the one that covers the node \c n.
alpar@2353:   /// The values are unspecified if the graph
alpar@2353:   /// has no perfect matching.
alpar@2353:   ///\retval barrier A \c bool WriteMap on the BNodes. The map will only
alpar@2353:   /// be set if \c g has no perfect matching. In this case it is set 
alpar@2353:   /// exactly once for each BNode. The nodes with \c true value represent
alpar@2353:   /// a barrier, i.e. a subset \e B a of BNodes with the property that
alpar@2353:   /// the cardinality of \e B is greater than the numner of its neighbors.
alpar@2353:   ///\return \c true iff \c g has a perfect matching.
alpar@2353:   ///
alpar@2353:   ///\note The the implementation is based
alpar@2353:   ///on the push-relabel principle.
alpar@2353:   template<class Graph,class MT, class GT>
alpar@2353:   int perfectBpMatching(const Graph &g,MT &matching,GT &barrier) 
alpar@2353:   {
alpar@2353:     BpMatching<Graph,MT> bpm(g,matching);
alpar@2353:     int ret=bpm.run();
alpar@2353:     if(ret>=0)
alpar@2353:       bpm.barrier(barrier,ret);
alpar@2353:     return ret<0;
alpar@2353:   }  
alpar@2353: }
alpar@2353: 
alpar@2353: #endif