14 * express or implied, and with no claim as to its suitability for any |
14 * express or implied, and with no claim as to its suitability for any |
15 * purpose. |
15 * purpose. |
16 * |
16 * |
17 */ |
17 */ |
18 |
18 |
19 #ifndef LEMON_BP_MATCHING |
19 #ifndef LEMON_PR_BIPARTITE_MATCHING |
20 #define LEMON_BP_MATCHING |
20 #define LEMON_PR_BIPARTITE_MATCHING |
21 |
21 |
22 #include <lemon/graph_utils.h> |
22 #include <lemon/graph_utils.h> |
23 #include <lemon/iterable_maps.h> |
23 #include <lemon/iterable_maps.h> |
24 #include <iostream> |
24 #include <iostream> |
25 #include <queue> |
25 #include <queue> |
26 #include <lemon/counter.h> |
|
27 #include <lemon/elevator.h> |
26 #include <lemon/elevator.h> |
28 |
27 |
29 ///\ingroup matching |
28 ///\ingroup matching |
30 ///\file |
29 ///\file |
31 ///\brief Push-prelabel maximum matching algorithms in bipartite graphs. |
30 ///\brief Push-prelabel maximum matching algorithms in bipartite graphs. |
32 /// |
31 /// |
33 ///\todo This file slightly conflicts with \ref lemon/bipartite_matching.h |
|
34 ///\todo (Re)move the XYZ_TYPEDEFS macros |
|
35 namespace lemon { |
32 namespace lemon { |
36 |
33 |
37 #define BIPARTITE_TYPEDEFS(Graph) \ |
34 ///Max cardinality matching algorithm based on push-relabel principle |
38 GRAPH_TYPEDEFS(Graph) \ |
35 |
39 typedef Graph::ANodeIt ANodeIt; \ |
36 ///\ingroup matching |
40 typedef Graph::BNodeIt BNodeIt; |
37 ///Bipartite Max Cardinality Matching algorithm. This class uses the |
41 |
38 ///push-relabel principle which in several cases has better runtime |
42 #define UNDIRBIPARTITE_TYPEDEFS(Graph) \ |
39 ///performance than the augmenting path solutions. |
43 UNDIRGRAPH_TYPEDEFS(Graph) \ |
40 /// |
44 typedef Graph::ANodeIt ANodeIt; \ |
41 ///\author Alpar Juttner |
45 typedef Graph::BNodeIt BNodeIt; |
42 template<class Graph> |
46 |
43 class PrBipartiteMatching { |
47 template<class Graph, |
|
48 class MT=typename Graph::template ANodeMap<typename Graph::UEdge> > |
|
49 class BpMatching { |
|
50 typedef typename Graph::Node Node; |
44 typedef typename Graph::Node Node; |
51 typedef typename Graph::ANodeIt ANodeIt; |
45 typedef typename Graph::ANodeIt ANodeIt; |
52 typedef typename Graph::BNodeIt BNodeIt; |
46 typedef typename Graph::BNodeIt BNodeIt; |
53 typedef typename Graph::UEdge UEdge; |
47 typedef typename Graph::UEdge UEdge; |
|
48 typedef typename Graph::UEdgeIt UEdgeIt; |
54 typedef typename Graph::IncEdgeIt IncEdgeIt; |
49 typedef typename Graph::IncEdgeIt IncEdgeIt; |
55 |
50 |
56 const Graph &_g; |
51 const Graph &_g; |
57 int _node_num; |
52 int _node_num; |
58 MT &_matching; |
53 int _matching_size; |
|
54 int _empty_level; |
|
55 |
|
56 typename Graph::template ANodeMap<typename Graph::UEdge> _matching; |
59 Elevator<Graph,typename Graph::BNode> _levels; |
57 Elevator<Graph,typename Graph::BNode> _levels; |
60 typename Graph::template BNodeMap<int> _cov; |
58 typename Graph::template BNodeMap<int> _cov; |
61 |
59 |
62 public: |
60 public: |
63 BpMatching(const Graph &g, MT &matching) : |
61 |
|
62 PrBipartiteMatching(const Graph &g) : |
64 _g(g), |
63 _g(g), |
65 _node_num(countBNodes(g)), |
64 _node_num(countBNodes(g)), |
66 _matching(matching), |
65 _matching(g), |
67 _levels(g,_node_num), |
66 _levels(g,_node_num), |
68 _cov(g,0) |
67 _cov(g,0) |
69 { |
68 { |
70 } |
69 } |
71 |
70 |
72 private: |
71 /// \name Execution control |
73 void init() |
72 /// The simplest way to execute the algorithm is to use one of the |
74 { |
73 /// member functions called \c run(). \n |
75 // for(BNodeIt n(g);n!=INVALID;++n) cov[n]=0; |
74 /// If you need more control on the execution, first |
|
75 /// you must call \ref init() and then one variant of the start() |
|
76 /// member. |
|
77 |
|
78 /// @{ |
|
79 |
|
80 ///Initialize the data structures |
|
81 |
|
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 |
|
92 ///becomes active. |
|
93 void init() { |
|
94 _matching_size=0; |
|
95 _empty_level=_node_num; |
76 for(ANodeIt n(_g);n!=INVALID;++n) |
96 for(ANodeIt n(_g);n!=INVALID;++n) |
77 if((_matching[n]=IncEdgeIt(_g,n))!=INVALID) |
97 if((_matching[n]=IncEdgeIt(_g,n))!=INVALID) |
78 ++_cov[_g.oppositeNode(n,_matching[n])]; |
98 ++_cov[_g.bNode(_matching[n])]; |
79 |
99 |
80 std::queue<Node> q; |
100 std::queue<Node> q; |
81 _levels.initStart(); |
101 _levels.initStart(); |
82 for(BNodeIt n(_g);n!=INVALID;++n) |
102 for(BNodeIt n(_g);n!=INVALID;++n) |
83 if(_cov[n]>1) { |
103 if(_cov[n]>1) { |
107 _levels.initFinish(); |
127 _levels.initFinish(); |
108 for(BNodeIt n(_g);n!=INVALID;++n) |
128 for(BNodeIt n(_g);n!=INVALID;++n) |
109 if(_cov[n]<1&&_levels[n]<_node_num) |
129 if(_cov[n]<1&&_levels[n]<_node_num) |
110 _levels.activate(n); |
130 _levels.activate(n); |
111 } |
131 } |
112 public: |
132 |
113 int run() |
133 ///Start the main phase of the algorithm |
114 { |
134 |
115 init(); |
135 ///This algorithm calculates the maximum matching with the |
116 |
136 ///push-relabel principle. This function should be called just |
117 Node act; |
137 ///after the init() function which already set the initial |
118 Node bact=INVALID; |
138 ///prematching, the level function on the B-nodes and the active, |
119 Node last_activated=INVALID; |
139 ///ie. unmatched B-nodes. |
120 // while((act=last_activated!=INVALID? |
140 /// |
121 // last_activated:_levels.highestActive()) |
141 ///The algorithm always takes highest active B-node, and it try to |
122 // !=INVALID) |
142 ///find a B-node which is eligible to pass over one of it's |
123 while((act=_levels.highestActive())!=INVALID) { |
143 ///matching edge. This condition holds when the B-node is one |
124 last_activated=INVALID; |
144 ///level lower, and the opposite node of it's matching edge is |
125 int actlevel=_levels[act]; |
145 ///adjacent to the highest active node. In this case the current |
126 |
146 ///node steals the matching edge and becomes inactive. If there is |
127 UEdge bedge=INVALID; |
147 ///not eligible node then the highest active node should be lift |
128 int nlevel=_node_num; |
148 ///to the next proper level. |
129 { |
149 /// |
130 int nnlevel; |
150 ///The nodes should not lift higher than the number of the |
131 for(IncEdgeIt tbedge(_g,act); |
151 ///B-nodes, if a node reach this level it remains unmatched. If |
132 tbedge!=INVALID && nlevel>=actlevel; |
152 ///during the execution one level becomes empty the nodes above it |
133 ++tbedge) |
153 ///can be deactivated and lift to the highest level. |
134 if((nnlevel=_levels[_g.bNode(_matching[_g.runningNode(tbedge)])])< |
154 void start() { |
135 nlevel) |
|
136 { |
|
137 nlevel=nnlevel; |
|
138 bedge=tbedge; |
|
139 } |
|
140 } |
|
141 if(nlevel<_node_num) { |
|
142 if(nlevel>=actlevel) |
|
143 _levels.liftHighestActiveTo(nlevel+1); |
|
144 // _levels.liftTo(act,nlevel+1); |
|
145 bact=_g.bNode(_matching[_g.aNode(bedge)]); |
|
146 if(--_cov[bact]<1) { |
|
147 _levels.activate(bact); |
|
148 last_activated=bact; |
|
149 } |
|
150 _matching[_g.aNode(bedge)]=bedge; |
|
151 _cov[act]=1; |
|
152 _levels.deactivate(act); |
|
153 } |
|
154 else { |
|
155 if(_node_num>actlevel) |
|
156 _levels.liftHighestActiveTo(_node_num); |
|
157 // _levels.liftTo(act,_node_num); |
|
158 _levels.deactivate(act); |
|
159 } |
|
160 |
|
161 if(_levels.onLevel(actlevel)==0) |
|
162 _levels.liftToTop(actlevel); |
|
163 } |
|
164 |
|
165 int ret=_node_num; |
|
166 for(ANodeIt n(_g);n!=INVALID;++n) |
|
167 if(_matching[n]==INVALID) ret--; |
|
168 else if (_cov[_g.bNode(_matching[n])]>1) { |
|
169 _cov[_g.bNode(_matching[n])]--; |
|
170 ret--; |
|
171 _matching[n]=INVALID; |
|
172 } |
|
173 return ret; |
|
174 } |
|
175 |
|
176 ///\returns -1 if there is a perfect matching, or an empty level |
|
177 ///if it doesn't exists |
|
178 int runPerfect() |
|
179 { |
|
180 init(); |
|
181 |
|
182 Node act; |
155 Node act; |
183 Node bact=INVALID; |
156 Node bact=INVALID; |
184 Node last_activated=INVALID; |
157 Node last_activated=INVALID; |
185 while((act=_levels.highestActive())!=INVALID) { |
158 while((act=_levels.highestActive())!=INVALID) { |
186 last_activated=INVALID; |
159 last_activated=INVALID; |
217 _levels.liftHighestActiveTo(_node_num); |
190 _levels.liftHighestActiveTo(_node_num); |
218 _levels.deactivate(act); |
191 _levels.deactivate(act); |
219 } |
192 } |
220 |
193 |
221 if(_levels.onLevel(actlevel)==0) |
194 if(_levels.onLevel(actlevel)==0) |
222 return actlevel; |
195 _levels.liftToTop(actlevel); |
223 } |
196 } |
224 return -1; |
197 |
225 } |
198 _matching_size = _node_num; |
226 |
199 for(ANodeIt n(_g);n!=INVALID;++n) |
227 template<class GT> |
200 if(_matching[n]==INVALID) _matching_size--; |
228 void aBarrier(GT &bar,int empty_level=-1) |
201 else if (_cov[_g.bNode(_matching[n])]>1) { |
|
202 _cov[_g.bNode(_matching[n])]--; |
|
203 _matching_size--; |
|
204 _matching[n]=INVALID; |
|
205 } |
|
206 } |
|
207 |
|
208 ///Start the algorithm to find a perfect matching |
|
209 |
|
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 |
|
213 ///the graph |
|
214 /// |
|
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 |
|
219 ///return value. |
|
220 bool startPerfect() { |
|
221 Node act; |
|
222 Node bact=INVALID; |
|
223 Node last_activated=INVALID; |
|
224 while((act=_levels.highestActive())!=INVALID) { |
|
225 last_activated=INVALID; |
|
226 int actlevel=_levels[act]; |
|
227 |
|
228 UEdge bedge=INVALID; |
|
229 int nlevel=_node_num; |
|
230 { |
|
231 int nnlevel; |
|
232 for(IncEdgeIt tbedge(_g,act); |
|
233 tbedge!=INVALID && nlevel>=actlevel; |
|
234 ++tbedge) |
|
235 if((nnlevel=_levels[_g.bNode(_matching[_g.runningNode(tbedge)])])< |
|
236 nlevel) |
|
237 { |
|
238 nlevel=nnlevel; |
|
239 bedge=tbedge; |
|
240 } |
|
241 } |
|
242 if(nlevel<_node_num) { |
|
243 if(nlevel>=actlevel) |
|
244 _levels.liftHighestActiveTo(nlevel+1); |
|
245 bact=_g.bNode(_matching[_g.aNode(bedge)]); |
|
246 if(--_cov[bact]<1) { |
|
247 _levels.activate(bact); |
|
248 last_activated=bact; |
|
249 } |
|
250 _matching[_g.aNode(bedge)]=bedge; |
|
251 _cov[act]=1; |
|
252 _levels.deactivate(act); |
|
253 } |
|
254 else { |
|
255 if(_node_num>actlevel) |
|
256 _levels.liftHighestActiveTo(_node_num); |
|
257 _levels.deactivate(act); |
|
258 } |
|
259 |
|
260 if(_levels.onLevel(actlevel)==0) |
|
261 _empty_level=actlevel; |
|
262 return false; |
|
263 } |
|
264 return true; |
|
265 } |
|
266 |
|
267 ///Runs the algorithm |
|
268 |
|
269 ///Just a shortcut for the next code: |
|
270 ///\code |
|
271 /// init(); |
|
272 /// start(); |
|
273 ///\endcode |
|
274 void run() { |
|
275 init(); |
|
276 start(); |
|
277 } |
|
278 |
|
279 ///Runs the algorithm to find a perfect matching |
|
280 |
|
281 ///Just a shortcut for the next code: |
|
282 ///\code |
|
283 /// init(); |
|
284 /// startPerfect(); |
|
285 ///\endcode |
|
286 /// |
|
287 ///\note If the two nodesets of the graph have different size then |
|
288 ///this algorithm checks the perfect property on the B-side. |
|
289 bool runPerfect() { |
|
290 init(); |
|
291 return startPerfect(); |
|
292 } |
|
293 |
|
294 ///Runs the algorithm to find a perfect matching |
|
295 |
|
296 ///Just a shortcut for the next code: |
|
297 ///\code |
|
298 /// init(); |
|
299 /// startPerfect(); |
|
300 ///\endcode |
|
301 /// |
|
302 ///\note It checks that the size of the two nodesets are equal. |
|
303 bool checkedRunPerfect() { |
|
304 if (countANodes(_g) != _node_num) return false; |
|
305 init(); |
|
306 return startPerfect(); |
|
307 } |
|
308 |
|
309 ///@} |
|
310 |
|
311 /// \name Query Functions |
|
312 /// The result of the %Matching algorithm can be obtained using these |
|
313 /// functions.\n |
|
314 /// Before the use of these functions, |
|
315 /// either run() or start() must be called. |
|
316 ///@{ |
|
317 |
|
318 /// \brief Set true all matching uedge in the map. |
|
319 /// |
|
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); |
|
327 } |
|
328 return _matching_size; |
|
329 } |
|
330 |
|
331 ///\brief Set true all matching uedge in the map and the others to false. |
|
332 |
|
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)]); |
|
339 } |
|
340 return _matching_size; |
|
341 } |
|
342 |
|
343 |
|
344 ///Returns true if the given uedge is in the matching. |
|
345 |
|
346 ///It returns true if the given uedge is in the matching. |
|
347 /// |
|
348 bool matchingEdge(const UEdge& e) const { |
|
349 return _matching[_g.aNode(e)]==e; |
|
350 } |
|
351 |
|
352 ///Returns the matching edge from the node. |
|
353 |
|
354 ///Returns the matching edge from the node. If there is not such |
|
355 ///edge it gives back \c INVALID. |
|
356 ///\note If the parameter node is a B-node then the running time is |
|
357 ///propotional to the degree of the node. |
|
358 UEdge matchingEdge(const Node& n) const { |
|
359 if (_g.aNode(n)) { |
|
360 return _matching[n]; |
|
361 } else { |
|
362 for (IncEdgeIt e(_g,n);e!=INVALID;++e) |
|
363 if (e==_matching[_g.aNode(e)]) return e; |
|
364 return INVALID; |
|
365 } |
|
366 } |
|
367 |
|
368 ///Gives back the number of the matching edges. |
|
369 |
|
370 ///Gives back the number of the matching edges. |
|
371 int matchingSize() const { |
|
372 return _matching_size; |
|
373 } |
|
374 |
|
375 ///Gives back a barrier on the A-nodes |
|
376 |
|
377 ///The barrier is s subset of the nodes on the same side of the |
|
378 ///graph. If we tried to find a perfect matching and it failed |
|
379 ///then the barrier size will be greater than its neighbours. If |
|
380 ///the maximum matching searched then the barrier size minus its |
|
381 ///neighbours will be exactly the unmatched nodes on the A-side. |
|
382 ///\retval bar A WriteMap on the ANodes with bool value. |
|
383 template<class BarrierMap> |
|
384 void aBarrier(BarrierMap &bar) const |
229 { |
385 { |
230 if(empty_level==-1) |
|
231 for(empty_level=0;_levels.onLevel(empty_level);empty_level++) ; |
|
232 for(ANodeIt n(_g);n!=INVALID;++n) |
386 for(ANodeIt n(_g);n!=INVALID;++n) |
233 bar[n] = _matching[n]==INVALID || |
387 bar.set(n,_matching[n]==INVALID || |
234 _levels[_g.bNode(_matching[n])]<empty_level; |
388 _levels[_g.bNode(_matching[n])]<_empty_level); |
235 } |
389 } |
236 template<class GT> |
390 |
237 void bBarrier(GT &bar, int empty_level=-1) |
391 ///Gives back a barrier on the B-nodes |
|
392 |
|
393 ///The barrier is s subset of the nodes on the same side of the |
|
394 ///graph. If we tried to find a perfect matching and it failed |
|
395 ///then the barrier size will be greater than its neighbours. If |
|
396 ///the maximum matching searched then the barrier size minus its |
|
397 ///neighbours will be exactly the unmatched nodes on the B-side. |
|
398 ///\retval bar A WriteMap on the BNodes with bool value. |
|
399 template<class BarrierMap> |
|
400 void bBarrier(BarrierMap &bar) const |
238 { |
401 { |
239 if(empty_level==-1) |
402 for(BNodeIt n(_g);n!=INVALID;++n) bar.set(n,_levels[n]>=_empty_level); |
240 for(empty_level=0;_levels.onLevel(empty_level);empty_level++) ; |
403 } |
241 for(BNodeIt n(_g);n!=INVALID;++n) bar[n]=(_levels[n]>empty_level); |
404 |
242 } |
405 ///Returns a minimum covering of the nodes. |
243 |
406 |
|
407 ///The minimum covering set problem is the dual solution of the |
|
408 ///maximum bipartite matching. It provides a solution for this |
|
409 ///problem what is proof of the optimality of the matching. |
|
410 ///\param covering NodeMap of bool values, the nodes of the cover |
|
411 ///set will set true while the others false. |
|
412 ///\return The size of the cover set. |
|
413 ///\note This function can be called just after the algorithm have |
|
414 ///already found a matching. |
|
415 template<class CoverMap> |
|
416 int coverSet(CoverMap& covering) const { |
|
417 int ret=0; |
|
418 for(BNodeIt n(_g);n!=INVALID;++n) { |
|
419 if (_levels[n]<_empty_level) { covering.set(n,true); ++ret; } |
|
420 else covering.set(n,false); |
|
421 } |
|
422 for(ANodeIt n(_g);n!=INVALID;++n) { |
|
423 if (_matching[n]!=INVALID && |
|
424 _levels[_g.bNode(_matching[n])]>=_empty_level) |
|
425 { covering.set(n,true); ++ret; } |
|
426 else covering.set(n,false); |
|
427 } |
|
428 return ret; |
|
429 } |
|
430 |
|
431 |
|
432 /// @} |
|
433 |
244 }; |
434 }; |
245 |
435 |
246 |
436 |
247 ///Maximum cardinality of the matchings in a bipartite graph |
437 ///Maximum cardinality of the matchings in a bipartite graph |
248 |
438 |
253 ///\return The cardinality of the maximum matching. |
443 ///\return The cardinality of the maximum matching. |
254 /// |
444 /// |
255 ///\note The the implementation is based |
445 ///\note The the implementation is based |
256 ///on the push-relabel principle. |
446 ///on the push-relabel principle. |
257 template<class Graph> |
447 template<class Graph> |
258 int maxBpMatching(const Graph &g) |
448 int prBipartiteMatching(const Graph &g) |
259 { |
449 { |
260 typename Graph::template ANodeMap<typename Graph::UEdge> matching(g); |
450 PrBipartiteMatching<Graph> bpm(g); |
261 return maxBpMatching(g,matching); |
451 return bpm.matchingSize(); |
262 } |
452 } |
263 |
453 |
264 ///Maximum cardinality matching in a bipartite graph |
454 ///Maximum cardinality matching in a bipartite graph |
265 |
455 |
266 ///\ingroup matching |
456 ///\ingroup matching |
267 ///This function finds a maximum cardinality matching |
457 ///This function finds a maximum cardinality matching |
268 ///in a bipartite graph \c g. |
458 ///in a bipartite graph \c g. |
269 ///\param g An undirected bipartite graph. |
459 ///\param g An undirected bipartite graph. |
270 ///\retval matching A readwrite ANodeMap of value type \c Edge. |
460 ///\retval matching A write UEdgeMap of value type \c bool. |
271 /// The found edges will be returned in this map, |
461 /// The found edges will be returned in this map. |
272 /// i.e. for an \c ANode \c n, |
|
273 /// the edge <tt>matching[n]</tt> is the one that covers the node \c n, or |
|
274 /// \ref INVALID if it is uncovered. |
|
275 ///\return The cardinality of the maximum matching. |
462 ///\return The cardinality of the maximum matching. |
276 /// |
463 /// |
277 ///\note The the implementation is based |
464 ///\note The the implementation is based |
278 ///on the push-relabel principle. |
465 ///on the push-relabel principle. |
279 template<class Graph,class MT> |
466 template<class Graph,class MT> |
280 int maxBpMatching(const Graph &g,MT &matching) |
467 int prBipartiteMatching(const Graph &g,MT &matching) |
281 { |
468 { |
282 return BpMatching<Graph,MT>(g,matching).run(); |
469 PrBipartiteMatching<Graph> bpm(g); |
|
470 bpm.run(); |
|
471 bpm.matching(matching); |
|
472 return bpm.matchingSize(); |
283 } |
473 } |
284 |
474 |
285 ///Maximum cardinality matching in a bipartite graph |
475 ///Maximum cardinality matching in a bipartite graph |
286 |
476 |
287 ///\ingroup matching |
477 ///\ingroup matching |
288 ///This function finds a maximum cardinality matching |
478 ///This function finds a maximum cardinality matching |
289 ///in a bipartite graph \c g. |
479 ///in a bipartite graph \c g. |
290 ///\param g An undirected bipartite graph. |
480 ///\param g An undirected bipartite graph. |
291 ///\retval matching A readwrite ANodeMap of value type \c Edge. |
481 ///\retval matching A write UEdgeMap of value type \c bool. |
292 /// The found edges will be returned in this map, |
482 /// The found edges will be returned in this map. |
293 /// i.e. for an \c ANode \c n, |
|
294 /// the edge <tt>matching[n]</tt> is the one that covers the node \c n, or |
|
295 /// \ref INVALID if it is uncovered. |
|
296 ///\retval barrier A \c bool WriteMap on the BNodes. The map will be set |
483 ///\retval barrier A \c bool WriteMap on the BNodes. The map will be set |
297 /// exactly once for each BNode. The nodes with \c true value represent |
484 /// exactly once for each BNode. The nodes with \c true value represent |
298 /// a barrier \e B, i.e. the cardinality of \e B minus the number of its |
485 /// a barrier \e B, i.e. the cardinality of \e B minus the number of its |
299 /// neighbor is equal to the number of the <tt>BNode</tt>s minus the |
486 /// neighbor is equal to the number of the <tt>BNode</tt>s minus the |
300 /// cardinality of the maximum matching. |
487 /// cardinality of the maximum matching. |
301 ///\return The cardinality of the maximum matching. |
488 ///\return The cardinality of the maximum matching. |
302 /// |
489 /// |
303 ///\note The the implementation is based |
490 ///\note The the implementation is based |
304 ///on the push-relabel principle. |
491 ///on the push-relabel principle. |
305 template<class Graph,class MT, class GT> |
492 template<class Graph,class MT, class GT> |
306 int maxBpMatching(const Graph &g,MT &matching,GT &barrier) |
493 int prBipartiteMatching(const Graph &g,MT &matching,GT &barrier) |
307 { |
494 { |
308 BpMatching<Graph,MT> bpm(g,matching); |
495 PrBipartiteMatching<Graph> bpm(g); |
309 int ret=bpm.run(); |
496 bpm.run(); |
310 bpm.barrier(barrier); |
497 bpm.matching(matching); |
311 return ret; |
498 bpm.bBarrier(barrier); |
|
499 return bpm.matchingSize(); |
312 } |
500 } |
313 |
501 |
314 ///Perfect matching in a bipartite graph |
502 ///Perfect matching in a bipartite graph |
315 |
503 |
316 ///\ingroup matching |
504 ///\ingroup matching |
320 ///\return \c true iff \c g has a perfect matching. |
508 ///\return \c true iff \c g has a perfect matching. |
321 /// |
509 /// |
322 ///\note The the implementation is based |
510 ///\note The the implementation is based |
323 ///on the push-relabel principle. |
511 ///on the push-relabel principle. |
324 template<class Graph> |
512 template<class Graph> |
325 bool perfectBpMatching(const Graph &g) |
513 bool prPerfectBipartiteMatching(const Graph &g) |
326 { |
514 { |
327 typename Graph::template ANodeMap<typename Graph::UEdge> matching(g); |
515 PrBipartiteMatching<Graph> bpm(g); |
328 return perfectBpMatching(g,matching); |
516 return bpm.runPerfect(); |
329 } |
517 } |
330 |
518 |
331 ///Perfect matching in a bipartite graph |
519 ///Perfect matching in a bipartite graph |
332 |
520 |
333 ///\ingroup matching |
521 ///\ingroup matching |
334 ///This function finds a perfect matching in a bipartite graph \c g. |
522 ///This function finds a perfect matching in a bipartite graph \c g. |
335 ///\param g An undirected bipartite graph. |
523 ///\param g An undirected bipartite graph. |
336 ///\retval matching A readwrite ANodeMap of value type \c Edge. |
524 ///\retval matching A write UEdgeMap of value type \c bool. |
337 /// The found edges will be returned in this map, |
525 /// The found edges will be returned in this map. |
338 /// i.e. for an \c ANode \c n, |
526 /// The values are unchanged if the graph |
339 /// the edge <tt>matching[n]</tt> is the one that covers the node \c n. |
|
340 /// The values are unspecified if the graph |
|
341 /// has no perfect matching. |
527 /// has no perfect matching. |
342 ///\return \c true iff \c g has a perfect matching. |
528 ///\return \c true iff \c g has a perfect matching. |
343 /// |
529 /// |
344 ///\note The the implementation is based |
530 ///\note The the implementation is based |
345 ///on the push-relabel principle. |
531 ///on the push-relabel principle. |
346 template<class Graph,class MT> |
532 template<class Graph,class MT> |
347 bool perfectBpMatching(const Graph &g,MT &matching) |
533 bool prPerfectBipartiteMatching(const Graph &g,MT &matching) |
348 { |
534 { |
349 return BpMatching<Graph,MT>(g,matching).runPerfect()<0; |
535 PrBipartiteMatching<Graph> bpm(g); |
|
536 bool ret = bpm.runPerfect(); |
|
537 if (ret) bpm.matching(matching); |
|
538 return ret; |
350 } |
539 } |
351 |
540 |
352 ///Perfect matching in a bipartite graph |
541 ///Perfect matching in a bipartite graph |
353 |
542 |
354 ///\ingroup matching |
543 ///\ingroup matching |
355 ///This function finds a perfect matching in a bipartite graph \c g. |
544 ///This function finds a perfect matching in a bipartite graph \c g. |
356 ///\param g An undirected bipartite graph. |
545 ///\param g An undirected bipartite graph. |
357 ///\retval matching A readwrite ANodeMap of value type \c Edge. |
546 ///\retval matching A readwrite UEdgeMap of value type \c bool. |
358 /// The found edges will be returned in this map, |
547 /// The found edges will be returned in this map. |
359 /// i.e. for an \c ANode \c n, |
548 /// The values are unchanged if the graph |
360 /// the edge <tt>matching[n]</tt> is the one that covers the node \c n. |
|
361 /// The values are unspecified if the graph |
|
362 /// has no perfect matching. |
549 /// has no perfect matching. |
363 ///\retval barrier A \c bool WriteMap on the BNodes. The map will only |
550 ///\retval barrier A \c bool WriteMap on the BNodes. The map will only |
364 /// be set if \c g has no perfect matching. In this case it is set |
551 /// be set if \c g has no perfect matching. In this case it is set |
365 /// exactly once for each BNode. The nodes with \c true value represent |
552 /// exactly once for each BNode. The nodes with \c true value represent |
366 /// a barrier, i.e. a subset \e B a of BNodes with the property that |
553 /// a barrier, i.e. a subset \e B a of BNodes with the property that |
367 /// the cardinality of \e B is greater than the numner of its neighbors. |
554 /// the cardinality of \e B is greater than the number of its neighbors. |
368 ///\return \c true iff \c g has a perfect matching. |
555 ///\return \c true iff \c g has a perfect matching. |
369 /// |
556 /// |
370 ///\note The the implementation is based |
557 ///\note The the implementation is based |
371 ///on the push-relabel principle. |
558 ///on the push-relabel principle. |
372 template<class Graph,class MT, class GT> |
559 template<class Graph,class MT, class GT> |
373 int perfectBpMatching(const Graph &g,MT &matching,GT &barrier) |
560 int prPerfectBipartiteMatching(const Graph &g,MT &matching,GT &barrier) |
374 { |
561 { |
375 BpMatching<Graph,MT> bpm(g,matching); |
562 PrBipartiteMatching<Graph> bpm(g); |
376 int ret=bpm.run(); |
563 bool ret=bpm.runPerfect(); |
377 if(ret>=0) |
564 if(ret) |
378 bpm.barrier(barrier,ret); |
565 bpm.matching(matching); |
379 return ret<0; |
566 else |
|
567 bpm.bBarrier(barrier); |
|
568 return ret; |
380 } |
569 } |
381 } |
570 } |
382 |
571 |
383 #endif |
572 #endif |