3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_PR_BIPARTITE_MATCHING
20 #define LEMON_PR_BIPARTITE_MATCHING
22 #include <lemon/graph_utils.h>
23 #include <lemon/iterable_maps.h>
26 #include <lemon/elevator.h>
30 ///\brief Push-prelabel maximum matching algorithms in bipartite graphs.
34 ///Max cardinality matching algorithm based on push-relabel principle
37 ///Bipartite Max Cardinality Matching algorithm. This class uses the
38 ///push-relabel principle which in several cases has better runtime
39 ///performance than the augmenting path solutions.
41 ///\author Alpar Juttner
43 class PrBipartiteMatching {
44 typedef typename Graph::Node Node;
45 typedef typename Graph::ANodeIt ANodeIt;
46 typedef typename Graph::BNodeIt BNodeIt;
47 typedef typename Graph::UEdge UEdge;
48 typedef typename Graph::UEdgeIt UEdgeIt;
49 typedef typename Graph::IncEdgeIt IncEdgeIt;
56 typename Graph::template ANodeMap<typename Graph::UEdge> _matching;
57 Elevator<Graph,typename Graph::BNode> _levels;
58 typename Graph::template BNodeMap<int> _cov;
62 PrBipartiteMatching(const Graph &g) :
64 _node_num(countBNodes(g)),
71 /// \name Execution control
72 /// The simplest way to execute the algorithm is to use one of the
73 /// member functions called \c run(). \n
74 /// If you need more control on the execution, first
75 /// you must call \ref init() and then one variant of the start()
80 ///Initialize the data structures
82 ///This function constructs a prematching first, which is a
83 ///regular matching on the A-side of the graph, but on the B-side
84 ///each node could cover more matching edges. After that, the
85 ///B-nodes which multiple matched, will be pushed into the lowest
86 ///level of the Elevator. The remaning B-nodes will be pushed to
87 ///the consequent levels respect to a Bfs on following graph: the
88 ///nodes are the B-nodes of the original bipartite graph and two
89 ///nodes are adjacent if a node can pass over a matching edge to
90 ///an other node. The source of the Bfs are the lowest level
91 ///nodes. Last, the reached B-nodes without covered matching edge
95 _empty_level=_node_num;
96 for(ANodeIt n(_g);n!=INVALID;++n)
97 if((_matching[n]=IncEdgeIt(_g,n))!=INVALID)
98 ++_cov[_g.bNode(_matching[n])];
102 for(BNodeIt n(_g);n!=INVALID;++n)
104 _levels.initAddItem(n);
111 int nlev=_levels[n]+1;
112 for(IncEdgeIt e(_g,n);e!=INVALID;++e) {
113 Node m=_g.runningNode(e);
114 if(e==_matching[m]) {
115 for(IncEdgeIt f(_g,m);f!=INVALID;++f) {
116 Node r=_g.runningNode(f);
117 if(_levels[r]>nlev) {
118 for(;nlev>hlev;hlev++)
119 _levels.initNewLevel();
120 _levels.initAddItem(r);
127 _levels.initFinish();
128 for(BNodeIt n(_g);n!=INVALID;++n)
129 if(_cov[n]<1&&_levels[n]<_node_num)
133 ///Start the main phase of the algorithm
135 ///This algorithm calculates the maximum matching with the
136 ///push-relabel principle. This function should be called just
137 ///after the init() function which already set the initial
138 ///prematching, the level function on the B-nodes and the active,
139 ///ie. unmatched B-nodes.
141 ///The algorithm always takes highest active B-node, and it try to
142 ///find a B-node which is eligible to pass over one of it's
143 ///matching edge. This condition holds when the B-node is one
144 ///level lower, and the opposite node of it's matching edge is
145 ///adjacent to the highest active node. In this case the current
146 ///node steals the matching edge and becomes inactive. If there is
147 ///not eligible node then the highest active node should be lift
148 ///to the next proper level.
150 ///The nodes should not lift higher than the number of the
151 ///B-nodes, if a node reach this level it remains unmatched. If
152 ///during the execution one level becomes empty the nodes above it
153 ///can be deactivated and lift to the highest level.
157 Node last_activated=INVALID;
158 while((act=_levels.highestActive())!=INVALID) {
159 last_activated=INVALID;
160 int actlevel=_levels[act];
163 int nlevel=_node_num;
166 for(IncEdgeIt tbedge(_g,act);
167 tbedge!=INVALID && nlevel>=actlevel;
169 if((nnlevel=_levels[_g.bNode(_matching[_g.runningNode(tbedge)])])<
176 if(nlevel<_node_num) {
178 _levels.liftHighestActiveTo(nlevel+1);
179 bact=_g.bNode(_matching[_g.aNode(bedge)]);
181 _levels.activate(bact);
184 _matching[_g.aNode(bedge)]=bedge;
186 _levels.deactivate(act);
189 if(_node_num>actlevel)
190 _levels.liftHighestActiveTo(_node_num);
191 _levels.deactivate(act);
194 if(_levels.onLevel(actlevel)==0)
195 _levels.liftToTop(actlevel);
198 _matching_size = _node_num;
199 for(ANodeIt n(_g);n!=INVALID;++n)
200 if(_matching[n]==INVALID) _matching_size--;
201 else if (_cov[_g.bNode(_matching[n])]>1) {
202 _cov[_g.bNode(_matching[n])]--;
204 _matching[n]=INVALID;
208 ///Start the algorithm to find a perfect matching
210 ///This function is close to identical to the simple start()
211 ///member function but it calculates just perfect matching.
212 ///However, the perfect property is only checked on the B-side of
215 ///The main difference between the two function is the handling of
216 ///the empty levels. The simple start() function let the nodes
217 ///above the empty levels unmatched while this variant if it find
218 ///an empty level immediately terminates and gives back false
220 bool startPerfect() {
223 Node last_activated=INVALID;
224 while((act=_levels.highestActive())!=INVALID) {
225 last_activated=INVALID;
226 int actlevel=_levels[act];
229 int nlevel=_node_num;
232 for(IncEdgeIt tbedge(_g,act);
233 tbedge!=INVALID && nlevel>=actlevel;
235 if((nnlevel=_levels[_g.bNode(_matching[_g.runningNode(tbedge)])])<
242 if(nlevel<_node_num) {
244 _levels.liftHighestActiveTo(nlevel+1);
245 bact=_g.bNode(_matching[_g.aNode(bedge)]);
247 _levels.activate(bact);
250 _matching[_g.aNode(bedge)]=bedge;
252 _levels.deactivate(act);
255 if(_node_num>actlevel)
256 _levels.liftHighestActiveTo(_node_num);
257 _levels.deactivate(act);
260 if(_levels.onLevel(actlevel)==0)
261 _empty_level=actlevel;
267 ///Runs the algorithm
269 ///Just a shortcut for the next code:
279 ///Runs the algorithm to find a perfect matching
281 ///Just a shortcut for the next code:
287 ///\note If the two nodesets of the graph have different size then
288 ///this algorithm checks the perfect property on the B-side.
291 return startPerfect();
294 ///Runs the algorithm to find a perfect matching
296 ///Just a shortcut for the next code:
302 ///\note It checks that the size of the two nodesets are equal.
303 bool checkedRunPerfect() {
304 if (countANodes(_g) != _node_num) return false;
306 return startPerfect();
311 /// \name Query Functions
312 /// The result of the %Matching algorithm can be obtained using these
314 /// Before the use of these functions,
315 /// either run() or start() must be called.
318 ///Set true all matching uedge in the map.
320 ///Set true all matching uedge in the map. It does not change the
321 ///value mapped to the other uedges.
322 ///\return The number of the matching edges.
323 template <typename MatchingMap>
324 int quickMatching(MatchingMap& mm) const {
325 for (ANodeIt n(_g);n!=INVALID;++n) {
326 if (_matching[n]!=INVALID) mm.set(_matching[n],true);
328 return _matching_size;
331 ///Set true all matching uedge in the map and the others to false.
333 ///Set true all matching uedge in the map and the others to false.
334 ///\return The number of the matching edges.
335 template<class MatchingMap>
336 int matching(MatchingMap& mm) const {
337 for (UEdgeIt e(_g);e!=INVALID;++e) {
338 mm.set(e,e==_matching[_g.aNode(e)]);
340 return _matching_size;
343 ///Gives back the matching in an ANodeMap.
345 ///Gives back the matching in an ANodeMap. The parameter should
346 ///be a write ANodeMap of UEdge values.
347 ///\return The number of the matching edges.
348 template<class MatchingMap>
349 int aMatching(MatchingMap& mm) const {
350 for (ANodeIt n(_g);n!=INVALID;++n) {
351 mm.set(n,_matching[n]);
353 return _matching_size;
356 ///Gives back the matching in a BNodeMap.
358 ///Gives back the matching in a BNodeMap. The parameter should
359 ///be a write BNodeMap of UEdge values.
360 ///\return The number of the matching edges.
361 template<class MatchingMap>
362 int bMatching(MatchingMap& mm) const {
363 for (BNodeIt n(_g);n!=INVALID;++n) {
366 for (ANodeIt n(_g);n!=INVALID;++n) {
367 if (_matching[n]!=INVALID)
368 mm.set(_g.bNode(_matching[n]),_matching[n]);
370 return _matching_size;
374 ///Returns true if the given uedge is in the matching.
376 ///It returns true if the given uedge is in the matching.
378 bool matchingEdge(const UEdge& e) const {
379 return _matching[_g.aNode(e)]==e;
382 ///Returns the matching edge from the node.
384 ///Returns the matching edge from the node. If there is not such
385 ///edge it gives back \c INVALID.
386 ///\note If the parameter node is a B-node then the running time is
387 ///propotional to the degree of the node.
388 UEdge matchingEdge(const Node& n) const {
392 for (IncEdgeIt e(_g,n);e!=INVALID;++e)
393 if (e==_matching[_g.aNode(e)]) return e;
398 ///Gives back the number of the matching edges.
400 ///Gives back the number of the matching edges.
401 int matchingSize() const {
402 return _matching_size;
405 ///Gives back a barrier on the A-nodes
407 ///The barrier is s subset of the nodes on the same side of the
408 ///graph. If we tried to find a perfect matching and it failed
409 ///then the barrier size will be greater than its neighbours. If
410 ///the maximum matching searched then the barrier size minus its
411 ///neighbours will be exactly the unmatched nodes on the A-side.
412 ///\retval bar A WriteMap on the ANodes with bool value.
413 template<class BarrierMap>
414 void aBarrier(BarrierMap &bar) const
416 for(ANodeIt n(_g);n!=INVALID;++n)
417 bar.set(n,_matching[n]==INVALID ||
418 _levels[_g.bNode(_matching[n])]<_empty_level);
421 ///Gives back a barrier on the B-nodes
423 ///The barrier is s subset of the nodes on the same side of the
424 ///graph. If we tried to find a perfect matching and it failed
425 ///then the barrier size will be greater than its neighbours. If
426 ///the maximum matching searched then the barrier size minus its
427 ///neighbours will be exactly the unmatched nodes on the B-side.
428 ///\retval bar A WriteMap on the BNodes with bool value.
429 template<class BarrierMap>
430 void bBarrier(BarrierMap &bar) const
432 for(BNodeIt n(_g);n!=INVALID;++n) bar.set(n,_levels[n]>=_empty_level);
435 ///Returns a minimum covering of the nodes.
437 ///The minimum covering set problem is the dual solution of the
438 ///maximum bipartite matching. It provides a solution for this
439 ///problem what is proof of the optimality of the matching.
440 ///\param covering NodeMap of bool values, the nodes of the cover
441 ///set will set true while the others false.
442 ///\return The size of the cover set.
443 ///\note This function can be called just after the algorithm have
444 ///already found a matching.
445 template<class CoverMap>
446 int coverSet(CoverMap& covering) const {
448 for(BNodeIt n(_g);n!=INVALID;++n) {
449 if (_levels[n]<_empty_level) { covering.set(n,true); ++ret; }
450 else covering.set(n,false);
452 for(ANodeIt n(_g);n!=INVALID;++n) {
453 if (_matching[n]!=INVALID &&
454 _levels[_g.bNode(_matching[n])]>=_empty_level)
455 { covering.set(n,true); ++ret; }
456 else covering.set(n,false);
467 ///Maximum cardinality of the matchings in a bipartite graph
470 ///This function finds the maximum cardinality of the matchings
471 ///in a bipartite graph \c g.
472 ///\param g An undirected bipartite graph.
473 ///\return The cardinality of the maximum matching.
475 ///\note The the implementation is based
476 ///on the push-relabel principle.
477 template<class Graph>
478 int prBipartiteMatching(const Graph &g)
480 PrBipartiteMatching<Graph> bpm(g);
481 return bpm.matchingSize();
484 ///Maximum cardinality matching in a bipartite graph
487 ///This function finds a maximum cardinality matching
488 ///in a bipartite graph \c g.
489 ///\param g An undirected bipartite graph.
490 ///\retval matching A write ANodeMap of value type \c UEdge.
491 /// The found edges will be returned in this map,
492 /// i.e. for an \c ANode \c n the edge <tt>matching[n]</tt> is the one
493 /// that covers the node \c n.
494 ///\return The cardinality of the maximum matching.
496 ///\note The the implementation is based
497 ///on the push-relabel principle.
498 template<class Graph,class MT>
499 int prBipartiteMatching(const Graph &g,MT &matching)
501 PrBipartiteMatching<Graph> bpm(g);
503 bpm.aMatching(matching);
504 return bpm.matchingSize();
507 ///Maximum cardinality matching in a bipartite graph
510 ///This function finds a maximum cardinality matching
511 ///in a bipartite graph \c g.
512 ///\param g An undirected bipartite graph.
513 ///\retval matching A write ANodeMap of value type \c UEdge.
514 /// The found edges will be returned in this map,
515 /// i.e. for an \c ANode \c n the edge <tt>matching[n]</tt> is the one
516 /// that covers the node \c n.
517 ///\retval barrier A \c bool WriteMap on the BNodes. The map will be set
518 /// exactly once for each BNode. The nodes with \c true value represent
519 /// a barrier \e B, i.e. the cardinality of \e B minus the number of its
520 /// neighbor is equal to the number of the <tt>BNode</tt>s minus the
521 /// cardinality of the maximum matching.
522 ///\return The cardinality of the maximum matching.
524 ///\note The the implementation is based
525 ///on the push-relabel principle.
526 template<class Graph,class MT, class GT>
527 int prBipartiteMatching(const Graph &g,MT &matching,GT &barrier)
529 PrBipartiteMatching<Graph> bpm(g);
531 bpm.aMatching(matching);
532 bpm.bBarrier(barrier);
533 return bpm.matchingSize();
536 ///Perfect matching in a bipartite graph
539 ///This function checks whether the bipartite graph \c g
540 ///has a perfect matching.
541 ///\param g An undirected bipartite graph.
542 ///\return \c true iff \c g has a perfect matching.
544 ///\note The the implementation is based
545 ///on the push-relabel principle.
546 template<class Graph>
547 bool prPerfectBipartiteMatching(const Graph &g)
549 PrBipartiteMatching<Graph> bpm(g);
550 return bpm.runPerfect();
553 ///Perfect matching in a bipartite graph
556 ///This function finds a perfect matching in a bipartite graph \c g.
557 ///\param g An undirected bipartite graph.
558 ///\retval matching A write ANodeMap of value type \c UEdge.
559 /// The found edges will be returned in this map,
560 /// i.e. for an \c ANode \c n the edge <tt>matching[n]</tt> is the one
561 /// that covers the node \c n.
562 /// The values are unchanged if the graph
563 /// has no perfect matching.
564 ///\return \c true iff \c g has a perfect matching.
566 ///\note The the implementation is based
567 ///on the push-relabel principle.
568 template<class Graph,class MT>
569 bool prPerfectBipartiteMatching(const Graph &g,MT &matching)
571 PrBipartiteMatching<Graph> bpm(g);
572 bool ret = bpm.checkedRunPerfect();
573 if (ret) bpm.aMatching(matching);
577 ///Perfect matching in a bipartite graph
580 ///This function finds a perfect matching in a bipartite graph \c g.
581 ///\param g An undirected bipartite graph.
582 ///\retval matching A write ANodeMap of value type \c UEdge.
583 /// The found edges will be returned in this map,
584 /// i.e. for an \c ANode \c n the edge <tt>matching[n]</tt> is the one
585 /// that covers the node \c n.
586 /// The values are unchanged if the graph
587 /// has no perfect matching.
588 ///\retval barrier A \c bool WriteMap on the BNodes. The map will only
589 /// be set if \c g has no perfect matching. In this case it is set
590 /// exactly once for each BNode. The nodes with \c true value represent
591 /// a barrier, i.e. a subset \e B a of BNodes with the property that
592 /// the cardinality of \e B is greater than the number of its neighbors.
593 ///\return \c true iff \c g has a perfect matching.
595 ///\note The the implementation is based
596 ///on the push-relabel principle.
597 template<class Graph,class MT, class GT>
598 bool prPerfectBipartiteMatching(const Graph &g,MT &matching,GT &barrier)
600 PrBipartiteMatching<Graph> bpm(g);
601 bool ret=bpm.checkedRunPerfect();
603 bpm.aMatching(matching);
605 bpm.bBarrier(barrier);