1 /* -*- C++ -*- |
|
2 * src/lemon/max_matching.h - Part of LEMON, a generic C++ optimization library |
|
3 * |
|
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
5 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
6 * |
|
7 * Permission to use, modify and distribute this software is granted |
|
8 * provided that this copyright notice appears in all copies. For |
|
9 * precise terms see the accompanying LICENSE file. |
|
10 * |
|
11 * This software is provided "AS IS" with no warranty of any kind, |
|
12 * express or implied, and with no claim as to its suitability for any |
|
13 * purpose. |
|
14 * |
|
15 */ |
|
16 |
|
17 #ifndef LEMON_MAX_MATCHING_H |
|
18 #define LEMON_MAX_MATCHING_H |
|
19 |
|
20 #include <queue> |
|
21 #include <lemon/invalid.h> |
|
22 #include <lemon/unionfind.h> |
|
23 #include <lemon/graph_utils.h> |
|
24 |
|
25 ///\ingroup galgs |
|
26 ///\file |
|
27 ///\brief Maximum matching algorithm. |
|
28 |
|
29 namespace lemon { |
|
30 |
|
31 /// \addtogroup galgs |
|
32 /// @{ |
|
33 |
|
34 ///Edmonds' alternating forest maximum matching algorithm. |
|
35 |
|
36 ///This class provides Edmonds' alternating forest matching |
|
37 ///algorithm. The starting matching (if any) can be passed to the |
|
38 ///algorithm using read-in functions \ref readNMapNode, \ref |
|
39 ///readNMapEdge or \ref readEMapBool depending on the container. The |
|
40 ///resulting maximum matching can be attained by write-out functions |
|
41 ///\ref writeNMapNode, \ref writeNMapEdge or \ref writeEMapBool |
|
42 ///depending on the preferred container. |
|
43 /// |
|
44 ///The dual side of a matching is a map of the nodes to |
|
45 ///MaxMatching::pos_enum, having values D, A and C showing the |
|
46 ///Gallai-Edmonds decomposition of the graph. The nodes in D induce |
|
47 ///a graph with factor-critical components, the nodes in A form the |
|
48 ///barrier, and the nodes in C induce a graph having a perfect |
|
49 ///matching. This decomposition can be attained by calling \ref |
|
50 ///writePos after running the algorithm. |
|
51 /// |
|
52 ///\param Graph The undirected graph type the algorithm runs on. |
|
53 /// |
|
54 ///\author Jacint Szabo |
|
55 template <typename Graph> |
|
56 class MaxMatching { |
|
57 |
|
58 protected: |
|
59 |
|
60 typedef typename Graph::Node Node; |
|
61 typedef typename Graph::Edge Edge; |
|
62 typedef typename Graph::UndirEdge UndirEdge; |
|
63 typedef typename Graph::UndirEdgeIt UndirEdgeIt; |
|
64 typedef typename Graph::NodeIt NodeIt; |
|
65 typedef typename Graph::IncEdgeIt IncEdgeIt; |
|
66 |
|
67 typedef UnionFindEnum<Node, Graph::template NodeMap> UFE; |
|
68 |
|
69 public: |
|
70 |
|
71 ///Indicates the Gallai-Edmonds decomposition of the graph. |
|
72 |
|
73 ///Indicates the Gallai-Edmonds decomposition of the graph, which |
|
74 ///shows an upper bound on the size of a maximum matching. The |
|
75 ///nodes with pos_enum \c D induce a graph with factor-critical |
|
76 ///components, the nodes in \c A form the canonical barrier, and the |
|
77 ///nodes in \c C induce a graph having a perfect matching. |
|
78 enum pos_enum { |
|
79 D=0, |
|
80 A=1, |
|
81 C=2 |
|
82 }; |
|
83 |
|
84 protected: |
|
85 |
|
86 static const int HEUR_density=2; |
|
87 const Graph& g; |
|
88 typename Graph::template NodeMap<Node> _mate; |
|
89 typename Graph::template NodeMap<pos_enum> position; |
|
90 |
|
91 public: |
|
92 |
|
93 MaxMatching(const Graph& _g) : g(_g), _mate(_g,INVALID), position(_g) {} |
|
94 |
|
95 ///Runs Edmonds' algorithm. |
|
96 |
|
97 ///Runs Edmonds' algorithm for sparse graphs (number of edges < |
|
98 ///2*number of nodes), and a heuristical Edmonds' algorithm with a |
|
99 ///heuristic of postponing shrinks for dense graphs. |
|
100 inline void run(); |
|
101 |
|
102 ///Runs Edmonds' algorithm. |
|
103 |
|
104 ///If heur=0 it runs Edmonds' algorithm. If heur=1 it runs |
|
105 ///Edmonds' algorithm with a heuristic of postponing shrinks, |
|
106 ///giving a faster algorithm for dense graphs. |
|
107 void runEdmonds( int heur ); |
|
108 |
|
109 ///Finds a greedy matching starting from the actual matching. |
|
110 |
|
111 ///Starting form the actual matching stored, it finds a maximal |
|
112 ///greedy matching. |
|
113 void greedyMatching(); |
|
114 |
|
115 ///Returns the size of the actual matching stored. |
|
116 |
|
117 ///Returns the size of the actual matching stored. After \ref |
|
118 ///run() it returns the size of a maximum matching in the graph. |
|
119 int size() const; |
|
120 |
|
121 ///Resets the actual matching to the empty matching. |
|
122 |
|
123 ///Resets the actual matching to the empty matching. |
|
124 /// |
|
125 void resetMatching(); |
|
126 |
|
127 ///Returns the mate of a node in the actual matching. |
|
128 |
|
129 ///Returns the mate of a \c node in the actual matching. |
|
130 ///Returns INVALID if the \c node is not covered by the actual matching. |
|
131 Node mate(Node& node) const { |
|
132 return _mate[node]; |
|
133 } |
|
134 |
|
135 ///Reads a matching from a \c Node valued \c Node map. |
|
136 |
|
137 ///Reads a matching from a \c Node valued \c Node map. This map |
|
138 ///must be \e symmetric, i.e. if \c map[u]==v then \c map[v]==u |
|
139 ///must hold, and \c uv will be an edge of the matching. |
|
140 template<typename NMapN> |
|
141 void readNMapNode(NMapN& map) { |
|
142 for(NodeIt v(g); v!=INVALID; ++v) { |
|
143 _mate.set(v,map[v]); |
|
144 } |
|
145 } |
|
146 |
|
147 ///Writes the stored matching to a \c Node valued \c Node map. |
|
148 |
|
149 ///Writes the stored matching to a \c Node valued \c Node map. The |
|
150 ///resulting map will be \e symmetric, i.e. if \c map[u]==v then \c |
|
151 ///map[v]==u will hold, and now \c uv is an edge of the matching. |
|
152 template<typename NMapN> |
|
153 void writeNMapNode (NMapN& map) const { |
|
154 for(NodeIt v(g); v!=INVALID; ++v) { |
|
155 map.set(v,_mate[v]); |
|
156 } |
|
157 } |
|
158 |
|
159 ///Reads a matching from an \c UndirEdge valued \c Node map. |
|
160 |
|
161 ///Reads a matching from an \c UndirEdge valued \c Node map. \c |
|
162 ///map[v] must be an \c UndirEdge incident to \c v. This map must |
|
163 ///have the property that if \c g.oppositeNode(u,map[u])==v then |
|
164 ///\c \c g.oppositeNode(v,map[v])==u holds, and now some edge |
|
165 ///joining \c u to \c v will be an edge of the matching. |
|
166 template<typename NMapE> |
|
167 void readNMapEdge(NMapE& map) { |
|
168 for(NodeIt v(g); v!=INVALID; ++v) { |
|
169 UndirEdge e=map[v]; |
|
170 if ( e!=INVALID ) |
|
171 _mate.set(v,g.oppositeNode(v,e)); |
|
172 } |
|
173 } |
|
174 |
|
175 ///Writes the matching stored to an \c UndirEdge valued \c Node map. |
|
176 |
|
177 ///Writes the stored matching to an \c UndirEdge valued \c Node |
|
178 ///map. \c map[v] will be an \c UndirEdge incident to \c v. This |
|
179 ///map will have the property that if \c g.oppositeNode(u,map[u]) |
|
180 ///== v then \c map[u]==map[v] holds, and now this edge is an edge |
|
181 ///of the matching. |
|
182 template<typename NMapE> |
|
183 void writeNMapEdge (NMapE& map) const { |
|
184 typename Graph::template NodeMap<bool> todo(g,true); |
|
185 for(NodeIt v(g); v!=INVALID; ++v) { |
|
186 if ( todo[v] && _mate[v]!=INVALID ) { |
|
187 Node u=_mate[v]; |
|
188 for(IncEdgeIt e(g,v); e!=INVALID; ++e) { |
|
189 if ( g.runningNode(e) == u ) { |
|
190 map.set(u,e); |
|
191 map.set(v,e); |
|
192 todo.set(u,false); |
|
193 todo.set(v,false); |
|
194 break; |
|
195 } |
|
196 } |
|
197 } |
|
198 } |
|
199 } |
|
200 |
|
201 |
|
202 ///Reads a matching from a \c bool valued \c Edge map. |
|
203 |
|
204 ///Reads a matching from a \c bool valued \c Edge map. This map |
|
205 ///must have the property that there are no two incident edges \c |
|
206 ///e, \c f with \c map[e]==map[f]==true. The edges \c e with \c |
|
207 ///map[e]==true form the matching. |
|
208 template<typename EMapB> |
|
209 void readEMapBool(EMapB& map) { |
|
210 for(UndirEdgeIt e(g); e!=INVALID; ++e) { |
|
211 if ( map[e] ) { |
|
212 Node u=g.source(e); |
|
213 Node v=g.target(e); |
|
214 _mate.set(u,v); |
|
215 _mate.set(v,u); |
|
216 } |
|
217 } |
|
218 } |
|
219 |
|
220 |
|
221 ///Writes the matching stored to a \c bool valued \c Edge map. |
|
222 |
|
223 ///Writes the matching stored to a \c bool valued \c Edge |
|
224 ///map. This map will have the property that there are no two |
|
225 ///incident edges \c e, \c f with \c map[e]==map[f]==true. The |
|
226 ///edges \c e with \c map[e]==true form the matching. |
|
227 template<typename EMapB> |
|
228 void writeEMapBool (EMapB& map) const { |
|
229 for(UndirEdgeIt e(g); e!=INVALID; ++e) map.set(e,false); |
|
230 |
|
231 typename Graph::template NodeMap<bool> todo(g,true); |
|
232 for(NodeIt v(g); v!=INVALID; ++v) { |
|
233 if ( todo[v] && _mate[v]!=INVALID ) { |
|
234 Node u=_mate[v]; |
|
235 for(IncEdgeIt e(g,v); e!=INVALID; ++e) { |
|
236 if ( g.runningNode(e) == u ) { |
|
237 map.set(e,true); |
|
238 todo.set(u,false); |
|
239 todo.set(v,false); |
|
240 break; |
|
241 } |
|
242 } |
|
243 } |
|
244 } |
|
245 } |
|
246 |
|
247 |
|
248 ///Writes the canonical decomposition of the graph after running |
|
249 ///the algorithm. |
|
250 |
|
251 ///After calling any run methods of the class, it writes the |
|
252 ///Gallai-Edmonds canonical decomposition of the graph. \c map |
|
253 ///must be a node map of \ref pos_enum 's. |
|
254 template<typename NMapEnum> |
|
255 void writePos (NMapEnum& map) const { |
|
256 for(NodeIt v(g); v!=INVALID; ++v) map.set(v,position[v]); |
|
257 } |
|
258 |
|
259 private: |
|
260 |
|
261 |
|
262 void lateShrink(Node v, typename Graph::template NodeMap<Node>& ear, |
|
263 UFE& blossom, UFE& tree); |
|
264 |
|
265 void normShrink(Node v, typename Graph::template NodeMap<Node>& ear, |
|
266 UFE& blossom, UFE& tree); |
|
267 |
|
268 bool noShrinkStep(Node x, typename Graph::template NodeMap<Node>& ear, |
|
269 UFE& blossom, UFE& tree, std::queue<Node>& Q); |
|
270 |
|
271 void shrinkStep(Node& top, Node& middle, Node& bottom, |
|
272 typename Graph::template NodeMap<Node>& ear, |
|
273 UFE& blossom, UFE& tree, std::queue<Node>& Q); |
|
274 |
|
275 void augment(Node x, typename Graph::template NodeMap<Node>& ear, |
|
276 UFE& blossom, UFE& tree); |
|
277 |
|
278 }; |
|
279 |
|
280 |
|
281 // ********************************************************************** |
|
282 // IMPLEMENTATIONS |
|
283 // ********************************************************************** |
|
284 |
|
285 |
|
286 template <typename Graph> |
|
287 void MaxMatching<Graph>::run() { |
|
288 if ( countUndirEdges(g) < HEUR_density*countNodes(g) ) { |
|
289 greedyMatching(); |
|
290 runEdmonds(0); |
|
291 } else runEdmonds(1); |
|
292 } |
|
293 |
|
294 |
|
295 template <typename Graph> |
|
296 void MaxMatching<Graph>::runEdmonds( int heur=1 ) { |
|
297 |
|
298 for(NodeIt v(g); v!=INVALID; ++v) |
|
299 position.set(v,C); |
|
300 |
|
301 typename Graph::template NodeMap<Node> ear(g,INVALID); |
|
302 //undefined for the base nodes of the blossoms (i.e. for the |
|
303 //representative elements of UFE blossom) and for the nodes in C |
|
304 |
|
305 typename UFE::MapType blossom_base(g); |
|
306 UFE blossom(blossom_base); |
|
307 typename UFE::MapType tree_base(g); |
|
308 UFE tree(tree_base); |
|
309 //If these UFE's would be members of the class then also |
|
310 //blossom_base and tree_base should be a member. |
|
311 |
|
312 for(NodeIt v(g); v!=INVALID; ++v) { |
|
313 if ( position[v]==C && _mate[v]==INVALID ) { |
|
314 blossom.insert(v); |
|
315 tree.insert(v); |
|
316 position.set(v,D); |
|
317 if ( heur == 1 ) lateShrink( v, ear, blossom, tree ); |
|
318 else normShrink( v, ear, blossom, tree ); |
|
319 } |
|
320 } |
|
321 } |
|
322 |
|
323 |
|
324 template <typename Graph> |
|
325 void MaxMatching<Graph>::lateShrink(Node v, typename Graph::template NodeMap<Node>& ear, |
|
326 UFE& blossom, UFE& tree) { |
|
327 |
|
328 std::queue<Node> Q; //queue of the totally unscanned nodes |
|
329 Q.push(v); |
|
330 std::queue<Node> R; |
|
331 //queue of the nodes which must be scanned for a possible shrink |
|
332 |
|
333 while ( !Q.empty() ) { |
|
334 Node x=Q.front(); |
|
335 Q.pop(); |
|
336 if ( noShrinkStep( x, ear, blossom, tree, Q ) ) return; |
|
337 else R.push(x); |
|
338 } |
|
339 |
|
340 while ( !R.empty() ) { |
|
341 Node x=R.front(); |
|
342 R.pop(); |
|
343 |
|
344 for( IncEdgeIt e(g,x); e!=INVALID ; ++e ) { |
|
345 Node y=g.runningNode(e); |
|
346 |
|
347 if ( position[y] == D && blossom.find(x) != blossom.find(y) ) { |
|
348 //x and y must be in the same tree |
|
349 |
|
350 typename Graph::template NodeMap<bool> path(g,false); |
|
351 |
|
352 Node b=blossom.find(x); |
|
353 path.set(b,true); |
|
354 b=_mate[b]; |
|
355 while ( b!=INVALID ) { |
|
356 b=blossom.find(ear[b]); |
|
357 path.set(b,true); |
|
358 b=_mate[b]; |
|
359 } //going till the root |
|
360 |
|
361 Node top=y; |
|
362 Node middle=blossom.find(top); |
|
363 Node bottom=x; |
|
364 while ( !path[middle] ) |
|
365 shrinkStep(top, middle, bottom, ear, blossom, tree, Q); |
|
366 |
|
367 Node base=middle; |
|
368 top=x; |
|
369 middle=blossom.find(top); |
|
370 bottom=y; |
|
371 Node blossom_base=blossom.find(base); |
|
372 while ( middle!=blossom_base ) |
|
373 shrinkStep(top, middle, bottom, ear, blossom, tree, Q); |
|
374 |
|
375 blossom.makeRep(base); |
|
376 } // if shrink is needed |
|
377 |
|
378 while ( !Q.empty() ) { |
|
379 Node x=Q.front(); |
|
380 Q.pop(); |
|
381 if ( noShrinkStep(x, ear, blossom, tree, Q) ) return; |
|
382 else R.push(x); |
|
383 } |
|
384 } //for e |
|
385 } // while ( !R.empty() ) |
|
386 } |
|
387 |
|
388 |
|
389 template <typename Graph> |
|
390 void MaxMatching<Graph>::normShrink(Node v, |
|
391 typename Graph::template |
|
392 NodeMap<Node>& ear, |
|
393 UFE& blossom, UFE& tree) { |
|
394 std::queue<Node> Q; //queue of the unscanned nodes |
|
395 Q.push(v); |
|
396 while ( !Q.empty() ) { |
|
397 |
|
398 Node x=Q.front(); |
|
399 Q.pop(); |
|
400 |
|
401 for( IncEdgeIt e(g,x); e!=INVALID; ++e ) { |
|
402 Node y=g.runningNode(e); |
|
403 |
|
404 switch ( position[y] ) { |
|
405 case D: //x and y must be in the same tree |
|
406 |
|
407 if ( blossom.find(x) != blossom.find(y) ) { //shrink |
|
408 typename Graph::template NodeMap<bool> path(g,false); |
|
409 |
|
410 Node b=blossom.find(x); |
|
411 path.set(b,true); |
|
412 b=_mate[b]; |
|
413 while ( b!=INVALID ) { |
|
414 b=blossom.find(ear[b]); |
|
415 path.set(b,true); |
|
416 b=_mate[b]; |
|
417 } //going till the root |
|
418 |
|
419 Node top=y; |
|
420 Node middle=blossom.find(top); |
|
421 Node bottom=x; |
|
422 while ( !path[middle] ) |
|
423 shrinkStep(top, middle, bottom, ear, blossom, tree, Q); |
|
424 |
|
425 Node base=middle; |
|
426 top=x; |
|
427 middle=blossom.find(top); |
|
428 bottom=y; |
|
429 Node blossom_base=blossom.find(base); |
|
430 while ( middle!=blossom_base ) |
|
431 shrinkStep(top, middle, bottom, ear, blossom, tree, Q); |
|
432 |
|
433 blossom.makeRep(base); |
|
434 } |
|
435 break; |
|
436 case C: |
|
437 if ( _mate[y]!=INVALID ) { //grow |
|
438 |
|
439 ear.set(y,x); |
|
440 Node w=_mate[y]; |
|
441 blossom.insert(w); |
|
442 position.set(y,A); |
|
443 position.set(w,D); |
|
444 tree.insert(y); |
|
445 tree.insert(w); |
|
446 tree.join(y,blossom.find(x)); |
|
447 tree.join(w,y); |
|
448 Q.push(w); |
|
449 } else { //augment |
|
450 augment(x, ear, blossom, tree); |
|
451 _mate.set(x,y); |
|
452 _mate.set(y,x); |
|
453 return; |
|
454 } //if |
|
455 break; |
|
456 default: break; |
|
457 } |
|
458 } |
|
459 } |
|
460 } |
|
461 |
|
462 template <typename Graph> |
|
463 void MaxMatching<Graph>::greedyMatching() { |
|
464 for(NodeIt v(g); v!=INVALID; ++v) |
|
465 if ( _mate[v]==INVALID ) { |
|
466 for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) { |
|
467 Node y=g.runningNode(e); |
|
468 if ( _mate[y]==INVALID && y!=v ) { |
|
469 _mate.set(v,y); |
|
470 _mate.set(y,v); |
|
471 break; |
|
472 } |
|
473 } |
|
474 } |
|
475 } |
|
476 |
|
477 template <typename Graph> |
|
478 int MaxMatching<Graph>::size() const { |
|
479 int s=0; |
|
480 for(NodeIt v(g); v!=INVALID; ++v) { |
|
481 if ( _mate[v]!=INVALID ) { |
|
482 ++s; |
|
483 } |
|
484 } |
|
485 return s/2; |
|
486 } |
|
487 |
|
488 template <typename Graph> |
|
489 void MaxMatching<Graph>::resetMatching() { |
|
490 for(NodeIt v(g); v!=INVALID; ++v) |
|
491 _mate.set(v,INVALID); |
|
492 } |
|
493 |
|
494 template <typename Graph> |
|
495 bool MaxMatching<Graph>::noShrinkStep(Node x, |
|
496 typename Graph::template |
|
497 NodeMap<Node>& ear, |
|
498 UFE& blossom, UFE& tree, |
|
499 std::queue<Node>& Q) { |
|
500 for( IncEdgeIt e(g,x); e!= INVALID; ++e ) { |
|
501 Node y=g.runningNode(e); |
|
502 |
|
503 if ( position[y]==C ) { |
|
504 if ( _mate[y]!=INVALID ) { //grow |
|
505 ear.set(y,x); |
|
506 Node w=_mate[y]; |
|
507 blossom.insert(w); |
|
508 position.set(y,A); |
|
509 position.set(w,D); |
|
510 tree.insert(y); |
|
511 tree.insert(w); |
|
512 tree.join(y,blossom.find(x)); |
|
513 tree.join(w,y); |
|
514 Q.push(w); |
|
515 } else { //augment |
|
516 augment(x, ear, blossom, tree); |
|
517 _mate.set(x,y); |
|
518 _mate.set(y,x); |
|
519 return true; |
|
520 } |
|
521 } |
|
522 } |
|
523 return false; |
|
524 } |
|
525 |
|
526 template <typename Graph> |
|
527 void MaxMatching<Graph>::shrinkStep(Node& top, Node& middle, Node& bottom, |
|
528 typename Graph::template |
|
529 NodeMap<Node>& ear, |
|
530 UFE& blossom, UFE& tree, |
|
531 std::queue<Node>& Q) { |
|
532 ear.set(top,bottom); |
|
533 Node t=top; |
|
534 while ( t!=middle ) { |
|
535 Node u=_mate[t]; |
|
536 t=ear[u]; |
|
537 ear.set(t,u); |
|
538 } |
|
539 bottom=_mate[middle]; |
|
540 position.set(bottom,D); |
|
541 Q.push(bottom); |
|
542 top=ear[bottom]; |
|
543 Node oldmiddle=middle; |
|
544 middle=blossom.find(top); |
|
545 tree.erase(bottom); |
|
546 tree.erase(oldmiddle); |
|
547 blossom.insert(bottom); |
|
548 blossom.join(bottom, oldmiddle); |
|
549 blossom.join(top, oldmiddle); |
|
550 } |
|
551 |
|
552 template <typename Graph> |
|
553 void MaxMatching<Graph>::augment(Node x, |
|
554 typename Graph::template NodeMap<Node>& ear, |
|
555 UFE& blossom, UFE& tree) { |
|
556 Node v=_mate[x]; |
|
557 while ( v!=INVALID ) { |
|
558 |
|
559 Node u=ear[v]; |
|
560 _mate.set(v,u); |
|
561 Node tmp=v; |
|
562 v=_mate[u]; |
|
563 _mate.set(u,tmp); |
|
564 } |
|
565 typename UFE::ItemIt it; |
|
566 for (tree.first(it,blossom.find(x)); tree.valid(it); tree.next(it)) { |
|
567 if ( position[it] == D ) { |
|
568 typename UFE::ItemIt b_it; |
|
569 for (blossom.first(b_it,it); blossom.valid(b_it); blossom.next(b_it)) { |
|
570 position.set( b_it ,C); |
|
571 } |
|
572 blossom.eraseClass(it); |
|
573 } else position.set( it ,C); |
|
574 } |
|
575 tree.eraseClass(x); |
|
576 |
|
577 } |
|
578 |
|
579 /// @} |
|
580 |
|
581 } //END OF NAMESPACE LEMON |
|
582 |
|
583 #endif //LEMON_MAX_MATCHING_H |
|