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 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: ///\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 > 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 _levels; alpar@2353: typename Graph::template BNodeMap _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 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 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])] 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 alpar@2353: int maxBpMatching(const Graph &g) alpar@2353: { alpar@2353: typename Graph::template ANodeMap 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 matching[n] 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 alpar@2353: int maxBpMatching(const Graph &g,MT &matching) alpar@2353: { alpar@2353: return BpMatching(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 matching[n] 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 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 alpar@2353: int maxBpMatching(const Graph &g,MT &matching,GT &barrier) alpar@2353: { alpar@2353: BpMatching 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 alpar@2353: bool perfectBpMatching(const Graph &g) alpar@2353: { alpar@2353: typename Graph::template ANodeMap 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 matching[n] 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 alpar@2353: bool perfectBpMatching(const Graph &g,MT &matching) alpar@2353: { alpar@2353: return BpMatching(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 matching[n] 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 alpar@2353: int perfectBpMatching(const Graph &g,MT &matching,GT &barrier) alpar@2353: { alpar@2353: BpMatching 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