alpar@2353: /* -*- C++ -*-
alpar@2353:  *
alpar@2391:  * This file is a part of LEMON, a generic C++ optimization library
alpar@2391:  *
alpar@2553:  * Copyright (C) 2003-2008
alpar@2391:  * 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: 
deba@2462: #ifndef LEMON_PR_BIPARTITE_MATCHING
deba@2462: #define LEMON_PR_BIPARTITE_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/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: namespace lemon {
alpar@2353: 
deba@2462:   ///Max cardinality matching algorithm based on push-relabel principle
alpar@2353: 
deba@2462:   ///\ingroup matching
deba@2462:   ///Bipartite Max Cardinality Matching algorithm. This class uses the
deba@2462:   ///push-relabel principle which in several cases has better runtime
deba@2462:   ///performance than the augmenting path solutions.
deba@2462:   ///
deba@2462:   ///\author Alpar Juttner
deba@2462:   template<class Graph>
deba@2462:   class PrBipartiteMatching {
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;
deba@2462:     typedef typename Graph::UEdgeIt UEdgeIt;
alpar@2353:     typedef typename Graph::IncEdgeIt IncEdgeIt;
alpar@2353:     
alpar@2353:     const Graph &_g;
alpar@2353:     int _node_num;
deba@2462:     int _matching_size;
deba@2462:     int _empty_level;
deba@2462:     
deba@2462:     typename Graph::template ANodeMap<typename Graph::UEdge> _matching;
alpar@2353:     Elevator<Graph,typename Graph::BNode> _levels;
alpar@2353:     typename Graph::template BNodeMap<int> _cov;
alpar@2353: 
alpar@2353:   public:
deba@2462: 
deba@2466:     /// Constructor
deba@2466: 
deba@2466:     /// Constructor
deba@2466:     ///
deba@2462:     PrBipartiteMatching(const Graph &g) :
alpar@2353:       _g(g),
alpar@2353:       _node_num(countBNodes(g)),
deba@2462:       _matching(g),
alpar@2353:       _levels(g,_node_num),
alpar@2353:       _cov(g,0)
alpar@2353:     {
alpar@2353:     }
alpar@2353:     
deba@2462:     /// \name Execution control 
deba@2462:     /// The simplest way to execute the algorithm is to use one of the
deba@2462:     /// member functions called \c run(). \n
deba@2462:     /// If you need more control on the execution, first
deba@2462:     /// you must call \ref init() and then one variant of the start()
deba@2462:     /// member. 
deba@2462: 
deba@2462:     /// @{
deba@2462: 
deba@2462:     ///Initialize the data structures
deba@2462: 
deba@2462:     ///This function constructs a prematching first, which is a
deba@2462:     ///regular matching on the A-side of the graph, but on the B-side
deba@2462:     ///each node could cover more matching edges. After that, the
deba@2462:     ///B-nodes which multiple matched, will be pushed into the lowest
deba@2462:     ///level of the Elevator. The remaning B-nodes will be pushed to
deba@2462:     ///the consequent levels respect to a Bfs on following graph: the
deba@2462:     ///nodes are the B-nodes of the original bipartite graph and two
deba@2462:     ///nodes are adjacent if a node can pass over a matching edge to
deba@2462:     ///an other node. The source of the Bfs are the lowest level
deba@2462:     ///nodes. Last, the reached B-nodes without covered matching edge
deba@2462:     ///becomes active.
deba@2462:     void init() {
deba@2462:       _matching_size=0;
deba@2462:       _empty_level=_node_num;
alpar@2353:       for(ANodeIt n(_g);n!=INVALID;++n)
alpar@2353: 	if((_matching[n]=IncEdgeIt(_g,n))!=INVALID)
deba@2462: 	  ++_cov[_g.bNode(_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: 
deba@2462:     ///Start the main phase of the algorithm
alpar@2353:     
deba@2462:     ///This algorithm calculates the maximum matching with the
deba@2462:     ///push-relabel principle. This function should be called just
deba@2462:     ///after the init() function which already set the initial
deba@2462:     ///prematching, the level function on the B-nodes and the active,
deba@2462:     ///ie. unmatched B-nodes.
deba@2462:     ///
deba@2462:     ///The algorithm always takes highest active B-node, and it try to
deba@2462:     ///find a B-node which is eligible to pass over one of it's
deba@2462:     ///matching edge. This condition holds when the B-node is one
deba@2462:     ///level lower, and the opposite node of it's matching edge is
deba@2462:     ///adjacent to the highest active node. In this case the current
deba@2462:     ///node steals the matching edge and becomes inactive. If there is
deba@2462:     ///not eligible node then the highest active node should be lift
deba@2462:     ///to the next proper level.
deba@2462:     ///
deba@2462:     ///The nodes should not lift higher than the number of the
deba@2462:     ///B-nodes, if a node reach this level it remains unmatched. If
deba@2462:     ///during the execution one level becomes empty the nodes above it
deba@2462:     ///can be deactivated and lift to the highest level.
deba@2462:     void start() {
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)
deba@2512: 	    _levels.liftHighestActive(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 {
deba@2512: 	  _levels.liftHighestActiveToTop();
alpar@2353: 	}
alpar@2353: 
deba@2512: 	if(_levels.emptyLevel(actlevel))
deba@2462: 	  _levels.liftToTop(actlevel);
alpar@2353:       }
deba@2462:       
deba@2466:       for(ANodeIt n(_g);n!=INVALID;++n) {
deba@2466: 	if (_matching[n]==INVALID)continue;
deba@2466: 	if (_cov[_g.bNode(_matching[n])]>1) {
deba@2462: 	  _cov[_g.bNode(_matching[n])]--;
deba@2462: 	  _matching[n]=INVALID;
deba@2466: 	} else {
deba@2466: 	  ++_matching_size;
deba@2462: 	}
deba@2466:       }
alpar@2353:     }
deba@2462: 
deba@2462:     ///Start the algorithm to find a perfect matching
deba@2462: 
deba@2462:     ///This function is close to identical to the simple start()
deba@2462:     ///member function but it calculates just perfect matching.
deba@2462:     ///However, the perfect property is only checked on the B-side of
deba@2462:     ///the graph
deba@2462:     ///
deba@2462:     ///The main difference between the two function is the handling of
deba@2462:     ///the empty levels. The simple start() function let the nodes
deba@2462:     ///above the empty levels unmatched while this variant if it find
deba@2462:     ///an empty level immediately terminates and gives back false
deba@2462:     ///return value.
deba@2462:     bool startPerfect() {
deba@2462:       Node act;
deba@2462:       Node bact=INVALID;
deba@2462:       Node last_activated=INVALID;
deba@2462:       while((act=_levels.highestActive())!=INVALID) {
deba@2462: 	last_activated=INVALID;
deba@2462: 	int actlevel=_levels[act];
deba@2462: 	
deba@2462: 	UEdge bedge=INVALID;
deba@2462: 	int nlevel=_node_num;
deba@2462: 	{
deba@2462: 	  int nnlevel;
deba@2462: 	  for(IncEdgeIt tbedge(_g,act);
deba@2462: 	      tbedge!=INVALID && nlevel>=actlevel;
deba@2462: 	      ++tbedge)
deba@2462: 	    if((nnlevel=_levels[_g.bNode(_matching[_g.runningNode(tbedge)])])<
deba@2462: 	       nlevel)
deba@2462: 	      {
deba@2462: 		nlevel=nnlevel;
deba@2462: 		bedge=tbedge;
deba@2462: 	      }
deba@2462: 	}
deba@2462: 	if(nlevel<_node_num) {
deba@2462: 	  if(nlevel>=actlevel)
deba@2512: 	    _levels.liftHighestActive(nlevel+1);
deba@2462: 	  bact=_g.bNode(_matching[_g.aNode(bedge)]);
deba@2462: 	  if(--_cov[bact]<1) {
deba@2462: 	    _levels.activate(bact);
deba@2462: 	    last_activated=bact;
deba@2462: 	  }
deba@2462: 	  _matching[_g.aNode(bedge)]=bedge;
deba@2462: 	  _cov[act]=1;
deba@2462: 	  _levels.deactivate(act);
deba@2462: 	}
deba@2462: 	else {
deba@2512: 	  _levels.liftHighestActiveToTop();
deba@2462: 	}
deba@2462: 
deba@2512: 	if(_levels.emptyLevel(actlevel))
deba@2462: 	  _empty_level=actlevel;
deba@2462: 	  return false;
deba@2462:       }
deba@2466:       _matching_size = _node_num;
deba@2462:       return true;
deba@2462:     }
deba@2462:   
deba@2462:     ///Runs the algorithm
deba@2462:     
deba@2462:     ///Just a shortcut for the next code:
deba@2462:     ///\code
deba@2462:     /// init();
deba@2462:     /// start();
deba@2462:     ///\endcode
deba@2462:     void run() {
deba@2462:       init();
deba@2462:       start();
deba@2462:     }
deba@2462:     
deba@2462:     ///Runs the algorithm to find a perfect matching
deba@2462:     
deba@2462:     ///Just a shortcut for the next code:
deba@2462:     ///\code
deba@2462:     /// init();
deba@2462:     /// startPerfect();
deba@2462:     ///\endcode
deba@2462:     ///
deba@2462:     ///\note If the two nodesets of the graph have different size then
deba@2462:     ///this algorithm checks the perfect property on the B-side.
deba@2462:     bool runPerfect() {
deba@2462:       init();
deba@2462:       return startPerfect();
deba@2462:     }
deba@2462: 
deba@2462:     ///Runs the algorithm to find a perfect matching
deba@2462:     
deba@2462:     ///Just a shortcut for the next code:
deba@2462:     ///\code
deba@2462:     /// init();
deba@2462:     /// startPerfect();
deba@2462:     ///\endcode
deba@2462:     ///
deba@2462:     ///\note It checks that the size of the two nodesets are equal.
deba@2462:     bool checkedRunPerfect() {
deba@2462:       if (countANodes(_g) != _node_num) return false;
deba@2462:       init();
deba@2462:       return startPerfect();
deba@2462:     }
deba@2462: 
deba@2462:     ///@}
deba@2462: 
deba@2462:     /// \name Query Functions
deba@2462:     /// The result of the %Matching algorithm can be obtained using these
deba@2462:     /// functions.\n
deba@2462:     /// Before the use of these functions,
deba@2462:     /// either run() or start() must be called.
deba@2462:     ///@{
deba@2462: 
deba@2463:     ///Set true all matching uedge in the map.
deba@2463: 
deba@2463:     ///Set true all matching uedge in the map. It does not change the
deba@2463:     ///value mapped to the other uedges.
deba@2463:     ///\return The number of the matching edges.
deba@2462:     template <typename MatchingMap>
deba@2462:     int quickMatching(MatchingMap& mm) const {
deba@2462:       for (ANodeIt n(_g);n!=INVALID;++n) {
deba@2462:         if (_matching[n]!=INVALID) mm.set(_matching[n],true);
deba@2462:       }
deba@2462:       return _matching_size;
deba@2462:     }
deba@2462: 
deba@2463:     ///Set true all matching uedge in the map and the others to false.
deba@2462: 
deba@2462:     ///Set true all matching uedge in the map and the others to false.
deba@2462:     ///\return The number of the matching edges.
deba@2462:     template<class MatchingMap>
deba@2462:     int matching(MatchingMap& mm) const {
deba@2462:       for (UEdgeIt e(_g);e!=INVALID;++e) {
deba@2462:         mm.set(e,e==_matching[_g.aNode(e)]);
deba@2462:       }
deba@2462:       return _matching_size;
deba@2462:     }
deba@2462: 
deba@2463:     ///Gives back the matching in an ANodeMap.
deba@2463: 
deba@2463:     ///Gives back the matching in an ANodeMap. The parameter should
deba@2463:     ///be a write ANodeMap of UEdge values.
deba@2463:     ///\return The number of the matching edges.
deba@2463:     template<class MatchingMap>
deba@2463:     int aMatching(MatchingMap& mm) const {
deba@2463:       for (ANodeIt n(_g);n!=INVALID;++n) {
deba@2463:         mm.set(n,_matching[n]);
deba@2463:       }
deba@2463:       return _matching_size;
deba@2463:     }
deba@2463: 
deba@2463:     ///Gives back the matching in a BNodeMap.
deba@2463: 
deba@2463:     ///Gives back the matching in a BNodeMap. The parameter should
deba@2463:     ///be a write BNodeMap of UEdge values.
deba@2463:     ///\return The number of the matching edges.
deba@2463:     template<class MatchingMap>
deba@2463:     int bMatching(MatchingMap& mm) const {
deba@2463:       for (BNodeIt n(_g);n!=INVALID;++n) {
deba@2463:         mm.set(n,INVALID);
deba@2463:       }
deba@2463:       for (ANodeIt n(_g);n!=INVALID;++n) {
deba@2463:         if (_matching[n]!=INVALID)
deba@2463: 	  mm.set(_g.bNode(_matching[n]),_matching[n]);
deba@2463:       }
deba@2463:       return _matching_size;
deba@2463:     }
deba@2463: 
deba@2462: 
deba@2462:     ///Returns true if the given uedge is in the matching.
deba@2462: 
deba@2462:     ///It returns true if the given uedge is in the matching.
deba@2462:     ///
deba@2462:     bool matchingEdge(const UEdge& e) const {
deba@2462:       return _matching[_g.aNode(e)]==e;
deba@2462:     }
deba@2462: 
deba@2462:     ///Returns the matching edge from the node.
deba@2462: 
deba@2462:     ///Returns the matching edge from the node. If there is not such
deba@2462:     ///edge it gives back \c INVALID.  
deba@2462:     ///\note If the parameter node is a B-node then the running time is
deba@2462:     ///propotional to the degree of the node.
deba@2462:     UEdge matchingEdge(const Node& n) const {
deba@2462:       if (_g.aNode(n)) {
deba@2462:         return _matching[n];
deba@2462:       } else {
deba@2462: 	for (IncEdgeIt e(_g,n);e!=INVALID;++e)
deba@2462: 	  if (e==_matching[_g.aNode(e)]) return e;
deba@2462: 	return INVALID;
deba@2462:       }
deba@2462:     }
deba@2462: 
deba@2462:     ///Gives back the number of the matching edges.
deba@2462: 
deba@2462:     ///Gives back the number of the matching edges.
deba@2462:     int matchingSize() const {
deba@2462:       return _matching_size;
deba@2462:     }
deba@2462: 
deba@2462:     ///Gives back a barrier on the A-nodes
deba@2462:     
deba@2462:     ///The barrier is s subset of the nodes on the same side of the
deba@2462:     ///graph. If we tried to find a perfect matching and it failed
deba@2462:     ///then the barrier size will be greater than its neighbours. If
deba@2462:     ///the maximum matching searched then the barrier size minus its
deba@2462:     ///neighbours will be exactly the unmatched nodes on the A-side.
deba@2462:     ///\retval bar A WriteMap on the ANodes with bool value.
deba@2462:     template<class BarrierMap>
deba@2462:     void aBarrier(BarrierMap &bar) const 
alpar@2353:     {
alpar@2353:       for(ANodeIt n(_g);n!=INVALID;++n)
deba@2462: 	bar.set(n,_matching[n]==INVALID ||
deba@2462: 	  _levels[_g.bNode(_matching[n])]<_empty_level);  
alpar@2353:     }  
deba@2462: 
deba@2462:     ///Gives back a barrier on the B-nodes
deba@2462:     
deba@2462:     ///The barrier is s subset of the nodes on the same side of the
deba@2462:     ///graph. If we tried to find a perfect matching and it failed
deba@2462:     ///then the barrier size will be greater than its neighbours. If
deba@2462:     ///the maximum matching searched then the barrier size minus its
deba@2462:     ///neighbours will be exactly the unmatched nodes on the B-side.
deba@2462:     ///\retval bar A WriteMap on the BNodes with bool value.
deba@2462:     template<class BarrierMap>
deba@2462:     void bBarrier(BarrierMap &bar) const
alpar@2353:     {
deba@2462:       for(BNodeIt n(_g);n!=INVALID;++n) bar.set(n,_levels[n]>=_empty_level);  
deba@2462:     }
deba@2462: 
deba@2462:     ///Returns a minimum covering of the nodes.
deba@2462: 
deba@2462:     ///The minimum covering set problem is the dual solution of the
deba@2462:     ///maximum bipartite matching. It provides a solution for this
deba@2462:     ///problem what is proof of the optimality of the matching.
deba@2462:     ///\param covering NodeMap of bool values, the nodes of the cover
deba@2462:     ///set will set true while the others false.  
deba@2462:     ///\return The size of the cover set.
deba@2462:     ///\note This function can be called just after the algorithm have
deba@2462:     ///already found a matching. 
deba@2462:     template<class CoverMap>
deba@2462:     int coverSet(CoverMap& covering) const {
deba@2462:       int ret=0;
deba@2462:       for(BNodeIt n(_g);n!=INVALID;++n) {
deba@2462: 	if (_levels[n]<_empty_level) { covering.set(n,true); ++ret; }
deba@2462: 	else covering.set(n,false);
deba@2462:       }
deba@2462:       for(ANodeIt n(_g);n!=INVALID;++n) {
deba@2462: 	if (_matching[n]!=INVALID &&
deba@2462: 	    _levels[_g.bNode(_matching[n])]>=_empty_level) 
deba@2462: 	  { covering.set(n,true); ++ret; }
deba@2462: 	else covering.set(n,false);
deba@2462:       }
deba@2462:       return ret;
deba@2462:     }
deba@2462: 
deba@2462: 
deba@2462:     /// @}
deba@2462:     
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>
deba@2462:   int prBipartiteMatching(const Graph &g)
alpar@2353:   {
deba@2462:     PrBipartiteMatching<Graph> bpm(g);
deba@2580:     bpm.run();
deba@2462:     return bpm.matchingSize();
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.
deba@2463:   ///\retval matching A write ANodeMap of value type \c UEdge.
deba@2463:   /// The found edges will be returned in this map,
deba@2463:   /// i.e. for an \c ANode \c n the edge <tt>matching[n]</tt> is the one
deba@2463:   /// that covers the node \c n.
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>
deba@2462:   int prBipartiteMatching(const Graph &g,MT &matching) 
alpar@2353:   {
deba@2462:     PrBipartiteMatching<Graph> bpm(g);
deba@2462:     bpm.run();
deba@2463:     bpm.aMatching(matching);
deba@2462:     return bpm.matchingSize();
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.
deba@2463:   ///\retval matching A write ANodeMap of value type \c UEdge.
deba@2463:   /// The found edges will be returned in this map,
deba@2463:   /// i.e. for an \c ANode \c n the edge <tt>matching[n]</tt> is the one
deba@2463:   /// that covers the node \c n.
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>
deba@2462:   int prBipartiteMatching(const Graph &g,MT &matching,GT &barrier) 
alpar@2353:   {
deba@2462:     PrBipartiteMatching<Graph> bpm(g);
deba@2462:     bpm.run();
deba@2463:     bpm.aMatching(matching);
deba@2462:     bpm.bBarrier(barrier);
deba@2462:     return bpm.matchingSize();
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>
deba@2462:   bool prPerfectBipartiteMatching(const Graph &g)
alpar@2353:   {
deba@2462:     PrBipartiteMatching<Graph> bpm(g);
deba@2580:     bpm.run();
deba@2580:     return bpm.checkedRunPerfect();
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.
deba@2463:   ///\retval matching A write ANodeMap of value type \c UEdge.
deba@2463:   /// The found edges will be returned in this map,
deba@2463:   /// i.e. for an \c ANode \c n the edge <tt>matching[n]</tt> is the one
deba@2463:   /// that covers the node \c n.
deba@2462:   /// The values are unchanged 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>
deba@2462:   bool prPerfectBipartiteMatching(const Graph &g,MT &matching) 
alpar@2353:   {
deba@2462:     PrBipartiteMatching<Graph> bpm(g);
deba@2463:     bool ret = bpm.checkedRunPerfect();
deba@2463:     if (ret) bpm.aMatching(matching);
deba@2462:     return ret;
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.
deba@2463:   ///\retval matching A write ANodeMap of value type \c UEdge.
deba@2463:   /// The found edges will be returned in this map,
deba@2463:   /// i.e. for an \c ANode \c n the edge <tt>matching[n]</tt> is the one
deba@2463:   /// that covers the node \c n.
deba@2462:   /// The values are unchanged 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
deba@2462:   /// the cardinality of \e B is greater than the number 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>
deba@2463:   bool prPerfectBipartiteMatching(const Graph &g,MT &matching,GT &barrier) 
alpar@2353:   {
deba@2462:     PrBipartiteMatching<Graph> bpm(g);
deba@2463:     bool ret=bpm.checkedRunPerfect();
deba@2462:     if(ret)
deba@2463:       bpm.aMatching(matching);
deba@2462:     else
deba@2462:       bpm.bBarrier(barrier);
deba@2462:     return ret;
alpar@2353:   }  
alpar@2353: }
alpar@2353: 
alpar@2353: #endif