alpar@2353: /* -*- C++ -*- alpar@2353: * alpar@2391: * This file is a part of LEMON, a generic C++ optimization library alpar@2391: * alpar@2391: * Copyright (C) 2003-2007 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 alpar@2353: #include alpar@2353: #include alpar@2353: #include alpar@2353: #include 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 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 _matching; alpar@2353: Elevator _levels; alpar@2353: typename Graph::template BNodeMap _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 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) 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) 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@2462: _levels.liftHighestActiveTo(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@2462: if(_node_num>actlevel) deba@2462: _levels.liftHighestActiveTo(_node_num); deba@2462: _levels.deactivate(act); deba@2462: } deba@2462: deba@2462: if(_levels.onLevel(actlevel)==0) 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 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 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 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 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 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 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 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 deba@2462: int prBipartiteMatching(const Graph &g) alpar@2353: { deba@2462: PrBipartiteMatching bpm(g); 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 matching[n] 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 deba@2462: int prBipartiteMatching(const Graph &g,MT &matching) alpar@2353: { deba@2462: PrBipartiteMatching 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 matching[n] 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 BNodes 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 deba@2462: int prBipartiteMatching(const Graph &g,MT &matching,GT &barrier) alpar@2353: { deba@2462: PrBipartiteMatching 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 deba@2462: bool prPerfectBipartiteMatching(const Graph &g) alpar@2353: { deba@2462: PrBipartiteMatching bpm(g); deba@2462: return bpm.runPerfect(); 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 matching[n] 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 deba@2462: bool prPerfectBipartiteMatching(const Graph &g,MT &matching) alpar@2353: { deba@2462: PrBipartiteMatching 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 matching[n] 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 deba@2463: bool prPerfectBipartiteMatching(const Graph &g,MT &matching,GT &barrier) alpar@2353: { deba@2462: PrBipartiteMatching 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