vmap.h: Enables one to create maps with a virtual base class.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
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_MAX_MATCHING_H
20 #define LEMON_MAX_MATCHING_H
23 #include <lemon/invalid.h>
24 #include <lemon/unionfind.h>
25 #include <lemon/graph_utils.h>
29 ///\brief Maximum matching algorithm.
36 ///Edmonds' alternating forest maximum matching algorithm.
38 ///This class provides Edmonds' alternating forest matching
39 ///algorithm. The starting matching (if any) can be passed to the
40 ///algorithm using read-in functions \ref readNMapNode, \ref
41 ///readNMapEdge or \ref readEMapBool depending on the container. The
42 ///resulting maximum matching can be attained by write-out functions
43 ///\ref writeNMapNode, \ref writeNMapEdge or \ref writeEMapBool
44 ///depending on the preferred container.
46 ///The dual side of a matching is a map of the nodes to
47 ///MaxMatching::pos_enum, having values D, A and C showing the
48 ///Gallai-Edmonds decomposition of the graph. The nodes in D induce
49 ///a graph with factor-critical components, the nodes in A form the
50 ///barrier, and the nodes in C induce a graph having a perfect
51 ///matching. This decomposition can be attained by calling \ref
52 ///writePos after running the algorithm.
54 ///\param Graph The undirected graph type the algorithm runs on.
56 ///\author Jacint Szabo
57 template <typename Graph>
62 typedef typename Graph::Node Node;
63 typedef typename Graph::Edge Edge;
64 typedef typename Graph::UEdge UEdge;
65 typedef typename Graph::UEdgeIt UEdgeIt;
66 typedef typename Graph::NodeIt NodeIt;
67 typedef typename Graph::IncEdgeIt IncEdgeIt;
69 typedef UnionFindEnum<Node, Graph::template NodeMap> UFE;
73 ///Indicates the Gallai-Edmonds decomposition of the graph.
75 ///Indicates the Gallai-Edmonds decomposition of the graph, which
76 ///shows an upper bound on the size of a maximum matching. The
77 ///nodes with pos_enum \c D induce a graph with factor-critical
78 ///components, the nodes in \c A form the canonical barrier, and the
79 ///nodes in \c C induce a graph having a perfect matching.
88 static const int HEUR_density=2;
90 typename Graph::template NodeMap<Node> _mate;
91 typename Graph::template NodeMap<pos_enum> position;
95 MaxMatching(const Graph& _g) : g(_g), _mate(_g,INVALID), position(_g) {}
97 ///Runs Edmonds' algorithm.
99 ///Runs Edmonds' algorithm for sparse graphs (number of edges <
100 ///2*number of nodes), and a heuristical Edmonds' algorithm with a
101 ///heuristic of postponing shrinks for dense graphs.
103 if ( countUEdges(g) < HEUR_density*countNodes(g) ) {
106 } else runEdmonds(1);
110 ///Runs Edmonds' algorithm.
112 ///If heur=0 it runs Edmonds' algorithm. If heur=1 it runs
113 ///Edmonds' algorithm with a heuristic of postponing shrinks,
114 ///giving a faster algorithm for dense graphs.
115 void runEdmonds( int heur = 1 ) {
117 for(NodeIt v(g); v!=INVALID; ++v)
120 typename Graph::template NodeMap<Node> ear(g,INVALID);
121 //undefined for the base nodes of the blossoms (i.e. for the
122 //representative elements of UFE blossom) and for the nodes in C
124 typename UFE::MapType blossom_base(g);
125 UFE blossom(blossom_base);
126 typename UFE::MapType tree_base(g);
128 //If these UFE's would be members of the class then also
129 //blossom_base and tree_base should be a member.
131 for(NodeIt v(g); v!=INVALID; ++v) {
132 if ( position[v]==C && _mate[v]==INVALID ) {
136 if ( heur == 1 ) lateShrink( v, ear, blossom, tree );
137 else normShrink( v, ear, blossom, tree );
143 ///Finds a greedy matching starting from the actual matching.
145 ///Starting form the actual matching stored, it finds a maximal
147 void greedyMatching() {
148 for(NodeIt v(g); v!=INVALID; ++v)
149 if ( _mate[v]==INVALID ) {
150 for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) {
151 Node y=g.runningNode(e);
152 if ( _mate[y]==INVALID && y!=v ) {
161 ///Returns the size of the actual matching stored.
163 ///Returns the size of the actual matching stored. After \ref
164 ///run() it returns the size of a maximum matching in the graph.
167 for(NodeIt v(g); v!=INVALID; ++v) {
168 if ( _mate[v]!=INVALID ) {
176 ///Resets the actual matching to the empty matching.
178 ///Resets the actual matching to the empty matching.
180 void resetMatching() {
181 for(NodeIt v(g); v!=INVALID; ++v)
182 _mate.set(v,INVALID);
185 ///Returns the mate of a node in the actual matching.
187 ///Returns the mate of a \c node in the actual matching.
188 ///Returns INVALID if the \c node is not covered by the actual matching.
189 Node mate(Node& node) const {
193 ///Reads a matching from a \c Node valued \c Node map.
195 ///Reads a matching from a \c Node valued \c Node map. This map
196 ///must be \e symmetric, i.e. if \c map[u]==v then \c map[v]==u
197 ///must hold, and \c uv will be an edge of the matching.
198 template<typename NMapN>
199 void readNMapNode(NMapN& map) {
200 for(NodeIt v(g); v!=INVALID; ++v) {
205 ///Writes the stored matching to a \c Node valued \c Node map.
207 ///Writes the stored matching to a \c Node valued \c Node map. The
208 ///resulting map will be \e symmetric, i.e. if \c map[u]==v then \c
209 ///map[v]==u will hold, and now \c uv is an edge of the matching.
210 template<typename NMapN>
211 void writeNMapNode (NMapN& map) const {
212 for(NodeIt v(g); v!=INVALID; ++v) {
217 ///Reads a matching from an \c UEdge valued \c Node map.
219 ///Reads a matching from an \c UEdge valued \c Node map. \c
220 ///map[v] must be an \c UEdge incident to \c v. This map must
221 ///have the property that if \c g.oppositeNode(u,map[u])==v then
222 ///\c \c g.oppositeNode(v,map[v])==u holds, and now some edge
223 ///joining \c u to \c v will be an edge of the matching.
224 template<typename NMapE>
225 void readNMapEdge(NMapE& map) {
226 for(NodeIt v(g); v!=INVALID; ++v) {
229 _mate.set(v,g.oppositeNode(v,e));
233 ///Writes the matching stored to an \c UEdge valued \c Node map.
235 ///Writes the stored matching to an \c UEdge valued \c Node
236 ///map. \c map[v] will be an \c UEdge incident to \c v. This
237 ///map will have the property that if \c g.oppositeNode(u,map[u])
238 ///== v then \c map[u]==map[v] holds, and now this edge is an edge
240 template<typename NMapE>
241 void writeNMapEdge (NMapE& map) const {
242 typename Graph::template NodeMap<bool> todo(g,true);
243 for(NodeIt v(g); v!=INVALID; ++v) {
244 if ( todo[v] && _mate[v]!=INVALID ) {
246 for(IncEdgeIt e(g,v); e!=INVALID; ++e) {
247 if ( g.runningNode(e) == u ) {
260 ///Reads a matching from a \c bool valued \c Edge map.
262 ///Reads a matching from a \c bool valued \c Edge map. This map
263 ///must have the property that there are no two incident edges \c
264 ///e, \c f with \c map[e]==map[f]==true. The edges \c e with \c
265 ///map[e]==true form the matching.
266 template<typename EMapB>
267 void readEMapBool(EMapB& map) {
268 for(UEdgeIt e(g); e!=INVALID; ++e) {
279 ///Writes the matching stored to a \c bool valued \c Edge map.
281 ///Writes the matching stored to a \c bool valued \c Edge
282 ///map. This map will have the property that there are no two
283 ///incident edges \c e, \c f with \c map[e]==map[f]==true. The
284 ///edges \c e with \c map[e]==true form the matching.
285 template<typename EMapB>
286 void writeEMapBool (EMapB& map) const {
287 for(UEdgeIt e(g); e!=INVALID; ++e) map.set(e,false);
289 typename Graph::template NodeMap<bool> todo(g,true);
290 for(NodeIt v(g); v!=INVALID; ++v) {
291 if ( todo[v] && _mate[v]!=INVALID ) {
293 for(IncEdgeIt e(g,v); e!=INVALID; ++e) {
294 if ( g.runningNode(e) == u ) {
306 ///Writes the canonical decomposition of the graph after running
309 ///After calling any run methods of the class, it writes the
310 ///Gallai-Edmonds canonical decomposition of the graph. \c map
311 ///must be a node map of \ref pos_enum 's.
312 template<typename NMapEnum>
313 void writePos (NMapEnum& map) const {
314 for(NodeIt v(g); v!=INVALID; ++v) map.set(v,position[v]);
320 void lateShrink(Node v, typename Graph::template NodeMap<Node>& ear,
321 UFE& blossom, UFE& tree);
323 void normShrink(Node v, typename Graph::template NodeMap<Node>& ear,
324 UFE& blossom, UFE& tree);
326 bool noShrinkStep(Node x, typename Graph::template NodeMap<Node>& ear,
327 UFE& blossom, UFE& tree, std::queue<Node>& Q);
329 void shrinkStep(Node& top, Node& middle, Node& bottom,
330 typename Graph::template NodeMap<Node>& ear,
331 UFE& blossom, UFE& tree, std::queue<Node>& Q);
333 void augment(Node x, typename Graph::template NodeMap<Node>& ear,
334 UFE& blossom, UFE& tree);
339 // **********************************************************************
341 // **********************************************************************
344 template <typename Graph>
345 void MaxMatching<Graph>::lateShrink(Node v, typename Graph::template NodeMap<Node>& ear,
346 UFE& blossom, UFE& tree) {
348 std::queue<Node> Q; //queue of the totally unscanned nodes
351 //queue of the nodes which must be scanned for a possible shrink
353 while ( !Q.empty() ) {
356 if ( noShrinkStep( x, ear, blossom, tree, Q ) ) return;
360 while ( !R.empty() ) {
364 for( IncEdgeIt e(g,x); e!=INVALID ; ++e ) {
365 Node y=g.runningNode(e);
367 if ( position[y] == D && blossom.find(x) != blossom.find(y) ) {
368 //x and y must be in the same tree
370 typename Graph::template NodeMap<bool> path(g,false);
372 Node b=blossom.find(x);
375 while ( b!=INVALID ) {
376 b=blossom.find(ear[b]);
379 } //going till the root
382 Node middle=blossom.find(top);
384 while ( !path[middle] )
385 shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
389 middle=blossom.find(top);
391 Node blossom_base=blossom.find(base);
392 while ( middle!=blossom_base )
393 shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
395 blossom.makeRep(base);
396 } // if shrink is needed
398 while ( !Q.empty() ) {
401 if ( noShrinkStep(x, ear, blossom, tree, Q) ) return;
405 } // while ( !R.empty() )
409 template <typename Graph>
410 void MaxMatching<Graph>::normShrink(Node v,
411 typename Graph::template
413 UFE& blossom, UFE& tree) {
414 std::queue<Node> Q; //queue of the unscanned nodes
416 while ( !Q.empty() ) {
421 for( IncEdgeIt e(g,x); e!=INVALID; ++e ) {
422 Node y=g.runningNode(e);
424 switch ( position[y] ) {
425 case D: //x and y must be in the same tree
427 if ( blossom.find(x) != blossom.find(y) ) { //shrink
428 typename Graph::template NodeMap<bool> path(g,false);
430 Node b=blossom.find(x);
433 while ( b!=INVALID ) {
434 b=blossom.find(ear[b]);
437 } //going till the root
440 Node middle=blossom.find(top);
442 while ( !path[middle] )
443 shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
447 middle=blossom.find(top);
449 Node blossom_base=blossom.find(base);
450 while ( middle!=blossom_base )
451 shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
453 blossom.makeRep(base);
457 if ( _mate[y]!=INVALID ) { //grow
466 tree.join(y,blossom.find(x));
470 augment(x, ear, blossom, tree);
482 template <typename Graph>
483 bool MaxMatching<Graph>::noShrinkStep(Node x,
484 typename Graph::template
486 UFE& blossom, UFE& tree,
487 std::queue<Node>& Q) {
488 for( IncEdgeIt e(g,x); e!= INVALID; ++e ) {
489 Node y=g.runningNode(e);
491 if ( position[y]==C ) {
492 if ( _mate[y]!=INVALID ) { //grow
500 tree.join(y,blossom.find(x));
504 augment(x, ear, blossom, tree);
514 template <typename Graph>
515 void MaxMatching<Graph>::shrinkStep(Node& top, Node& middle, Node& bottom,
516 typename Graph::template
518 UFE& blossom, UFE& tree,
519 std::queue<Node>& Q) {
522 while ( t!=middle ) {
527 bottom=_mate[middle];
528 position.set(bottom,D);
531 Node oldmiddle=middle;
532 middle=blossom.find(top);
534 tree.erase(oldmiddle);
535 blossom.insert(bottom);
536 blossom.join(bottom, oldmiddle);
537 blossom.join(top, oldmiddle);
540 template <typename Graph>
541 void MaxMatching<Graph>::augment(Node x,
542 typename Graph::template NodeMap<Node>& ear,
543 UFE& blossom, UFE& tree) {
545 while ( v!=INVALID ) {
553 typename UFE::ItemIt it;
554 for (tree.first(it,blossom.find(x)); tree.valid(it); tree.next(it)) {
555 if ( position[it] == D ) {
556 typename UFE::ItemIt b_it;
557 for (blossom.first(b_it,it); blossom.valid(b_it); blossom.next(b_it)) {
558 position.set( b_it ,C);
560 blossom.eraseClass(it);
561 } else position.set( it ,C);
569 } //END OF NAMESPACE LEMON
571 #endif //LEMON_MAX_MATCHING_H