NewMapWin has become Dialog instead of Window. Therefore it is created dynamically, when there is need for it, instead of keeping one instance in memory. This solution is slower, but more correct than before.
2 * lemon/max_matching.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
17 #ifndef LEMON_MAX_MATCHING_H
18 #define LEMON_MAX_MATCHING_H
21 #include <lemon/invalid.h>
22 #include <lemon/unionfind.h>
23 #include <lemon/graph_utils.h>
27 ///\brief Maximum matching algorithm.
34 ///Edmonds' alternating forest maximum matching algorithm.
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.
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.
52 ///\param Graph The undirected graph type the algorithm runs on.
54 ///\author Jacint Szabo
55 template <typename Graph>
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;
67 typedef UnionFindEnum<Node, Graph::template NodeMap> UFE;
71 ///Indicates the Gallai-Edmonds decomposition of the graph.
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.
86 static const int HEUR_density=2;
88 typename Graph::template NodeMap<Node> _mate;
89 typename Graph::template NodeMap<pos_enum> position;
93 MaxMatching(const Graph& _g) : g(_g), _mate(_g,INVALID), position(_g) {}
95 ///Runs Edmonds' algorithm.
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.
101 if ( countUndirEdges(g) < HEUR_density*countNodes(g) ) {
104 } else runEdmonds(1);
108 ///Runs Edmonds' algorithm.
110 ///If heur=0 it runs Edmonds' algorithm. If heur=1 it runs
111 ///Edmonds' algorithm with a heuristic of postponing shrinks,
112 ///giving a faster algorithm for dense graphs.
113 void runEdmonds( int heur = 1 ) {
115 for(NodeIt v(g); v!=INVALID; ++v)
118 typename Graph::template NodeMap<Node> ear(g,INVALID);
119 //undefined for the base nodes of the blossoms (i.e. for the
120 //representative elements of UFE blossom) and for the nodes in C
122 typename UFE::MapType blossom_base(g);
123 UFE blossom(blossom_base);
124 typename UFE::MapType tree_base(g);
126 //If these UFE's would be members of the class then also
127 //blossom_base and tree_base should be a member.
129 for(NodeIt v(g); v!=INVALID; ++v) {
130 if ( position[v]==C && _mate[v]==INVALID ) {
134 if ( heur == 1 ) lateShrink( v, ear, blossom, tree );
135 else normShrink( v, ear, blossom, tree );
141 ///Finds a greedy matching starting from the actual matching.
143 ///Starting form the actual matching stored, it finds a maximal
145 void greedyMatching() {
146 for(NodeIt v(g); v!=INVALID; ++v)
147 if ( _mate[v]==INVALID ) {
148 for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) {
149 Node y=g.runningNode(e);
150 if ( _mate[y]==INVALID && y!=v ) {
159 ///Returns the size of the actual matching stored.
161 ///Returns the size of the actual matching stored. After \ref
162 ///run() it returns the size of a maximum matching in the graph.
165 for(NodeIt v(g); v!=INVALID; ++v) {
166 if ( _mate[v]!=INVALID ) {
174 ///Resets the actual matching to the empty matching.
176 ///Resets the actual matching to the empty matching.
178 void resetMatching() {
179 for(NodeIt v(g); v!=INVALID; ++v)
180 _mate.set(v,INVALID);
183 ///Returns the mate of a node in the actual matching.
185 ///Returns the mate of a \c node in the actual matching.
186 ///Returns INVALID if the \c node is not covered by the actual matching.
187 Node mate(Node& node) const {
191 ///Reads a matching from a \c Node valued \c Node map.
193 ///Reads a matching from a \c Node valued \c Node map. This map
194 ///must be \e symmetric, i.e. if \c map[u]==v then \c map[v]==u
195 ///must hold, and \c uv will be an edge of the matching.
196 template<typename NMapN>
197 void readNMapNode(NMapN& map) {
198 for(NodeIt v(g); v!=INVALID; ++v) {
203 ///Writes the stored matching to a \c Node valued \c Node map.
205 ///Writes the stored matching to a \c Node valued \c Node map. The
206 ///resulting map will be \e symmetric, i.e. if \c map[u]==v then \c
207 ///map[v]==u will hold, and now \c uv is an edge of the matching.
208 template<typename NMapN>
209 void writeNMapNode (NMapN& map) const {
210 for(NodeIt v(g); v!=INVALID; ++v) {
215 ///Reads a matching from an \c UndirEdge valued \c Node map.
217 ///Reads a matching from an \c UndirEdge valued \c Node map. \c
218 ///map[v] must be an \c UndirEdge incident to \c v. This map must
219 ///have the property that if \c g.oppositeNode(u,map[u])==v then
220 ///\c \c g.oppositeNode(v,map[v])==u holds, and now some edge
221 ///joining \c u to \c v will be an edge of the matching.
222 template<typename NMapE>
223 void readNMapEdge(NMapE& map) {
224 for(NodeIt v(g); v!=INVALID; ++v) {
227 _mate.set(v,g.oppositeNode(v,e));
231 ///Writes the matching stored to an \c UndirEdge valued \c Node map.
233 ///Writes the stored matching to an \c UndirEdge valued \c Node
234 ///map. \c map[v] will be an \c UndirEdge incident to \c v. This
235 ///map will have the property that if \c g.oppositeNode(u,map[u])
236 ///== v then \c map[u]==map[v] holds, and now this edge is an edge
238 template<typename NMapE>
239 void writeNMapEdge (NMapE& map) const {
240 typename Graph::template NodeMap<bool> todo(g,true);
241 for(NodeIt v(g); v!=INVALID; ++v) {
242 if ( todo[v] && _mate[v]!=INVALID ) {
244 for(IncEdgeIt e(g,v); e!=INVALID; ++e) {
245 if ( g.runningNode(e) == u ) {
258 ///Reads a matching from a \c bool valued \c Edge map.
260 ///Reads a matching from a \c bool valued \c Edge map. This map
261 ///must have the property that there are no two incident edges \c
262 ///e, \c f with \c map[e]==map[f]==true. The edges \c e with \c
263 ///map[e]==true form the matching.
264 template<typename EMapB>
265 void readEMapBool(EMapB& map) {
266 for(UndirEdgeIt e(g); e!=INVALID; ++e) {
277 ///Writes the matching stored to a \c bool valued \c Edge map.
279 ///Writes the matching stored to a \c bool valued \c Edge
280 ///map. This map will have the property that there are no two
281 ///incident edges \c e, \c f with \c map[e]==map[f]==true. The
282 ///edges \c e with \c map[e]==true form the matching.
283 template<typename EMapB>
284 void writeEMapBool (EMapB& map) const {
285 for(UndirEdgeIt e(g); e!=INVALID; ++e) map.set(e,false);
287 typename Graph::template NodeMap<bool> todo(g,true);
288 for(NodeIt v(g); v!=INVALID; ++v) {
289 if ( todo[v] && _mate[v]!=INVALID ) {
291 for(IncEdgeIt e(g,v); e!=INVALID; ++e) {
292 if ( g.runningNode(e) == u ) {
304 ///Writes the canonical decomposition of the graph after running
307 ///After calling any run methods of the class, it writes the
308 ///Gallai-Edmonds canonical decomposition of the graph. \c map
309 ///must be a node map of \ref pos_enum 's.
310 template<typename NMapEnum>
311 void writePos (NMapEnum& map) const {
312 for(NodeIt v(g); v!=INVALID; ++v) map.set(v,position[v]);
318 void lateShrink(Node v, typename Graph::template NodeMap<Node>& ear,
319 UFE& blossom, UFE& tree);
321 void normShrink(Node v, typename Graph::template NodeMap<Node>& ear,
322 UFE& blossom, UFE& tree);
324 bool noShrinkStep(Node x, typename Graph::template NodeMap<Node>& ear,
325 UFE& blossom, UFE& tree, std::queue<Node>& Q);
327 void shrinkStep(Node& top, Node& middle, Node& bottom,
328 typename Graph::template NodeMap<Node>& ear,
329 UFE& blossom, UFE& tree, std::queue<Node>& Q);
331 void augment(Node x, typename Graph::template NodeMap<Node>& ear,
332 UFE& blossom, UFE& tree);
337 // **********************************************************************
339 // **********************************************************************
342 template <typename Graph>
343 void MaxMatching<Graph>::lateShrink(Node v, typename Graph::template NodeMap<Node>& ear,
344 UFE& blossom, UFE& tree) {
346 std::queue<Node> Q; //queue of the totally unscanned nodes
349 //queue of the nodes which must be scanned for a possible shrink
351 while ( !Q.empty() ) {
354 if ( noShrinkStep( x, ear, blossom, tree, Q ) ) return;
358 while ( !R.empty() ) {
362 for( IncEdgeIt e(g,x); e!=INVALID ; ++e ) {
363 Node y=g.runningNode(e);
365 if ( position[y] == D && blossom.find(x) != blossom.find(y) ) {
366 //x and y must be in the same tree
368 typename Graph::template NodeMap<bool> path(g,false);
370 Node b=blossom.find(x);
373 while ( b!=INVALID ) {
374 b=blossom.find(ear[b]);
377 } //going till the root
380 Node middle=blossom.find(top);
382 while ( !path[middle] )
383 shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
387 middle=blossom.find(top);
389 Node blossom_base=blossom.find(base);
390 while ( middle!=blossom_base )
391 shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
393 blossom.makeRep(base);
394 } // if shrink is needed
396 while ( !Q.empty() ) {
399 if ( noShrinkStep(x, ear, blossom, tree, Q) ) return;
403 } // while ( !R.empty() )
407 template <typename Graph>
408 void MaxMatching<Graph>::normShrink(Node v,
409 typename Graph::template
411 UFE& blossom, UFE& tree) {
412 std::queue<Node> Q; //queue of the unscanned nodes
414 while ( !Q.empty() ) {
419 for( IncEdgeIt e(g,x); e!=INVALID; ++e ) {
420 Node y=g.runningNode(e);
422 switch ( position[y] ) {
423 case D: //x and y must be in the same tree
425 if ( blossom.find(x) != blossom.find(y) ) { //shrink
426 typename Graph::template NodeMap<bool> path(g,false);
428 Node b=blossom.find(x);
431 while ( b!=INVALID ) {
432 b=blossom.find(ear[b]);
435 } //going till the root
438 Node middle=blossom.find(top);
440 while ( !path[middle] )
441 shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
445 middle=blossom.find(top);
447 Node blossom_base=blossom.find(base);
448 while ( middle!=blossom_base )
449 shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
451 blossom.makeRep(base);
455 if ( _mate[y]!=INVALID ) { //grow
464 tree.join(y,blossom.find(x));
468 augment(x, ear, blossom, tree);
480 template <typename Graph>
481 bool MaxMatching<Graph>::noShrinkStep(Node x,
482 typename Graph::template
484 UFE& blossom, UFE& tree,
485 std::queue<Node>& Q) {
486 for( IncEdgeIt e(g,x); e!= INVALID; ++e ) {
487 Node y=g.runningNode(e);
489 if ( position[y]==C ) {
490 if ( _mate[y]!=INVALID ) { //grow
498 tree.join(y,blossom.find(x));
502 augment(x, ear, blossom, tree);
512 template <typename Graph>
513 void MaxMatching<Graph>::shrinkStep(Node& top, Node& middle, Node& bottom,
514 typename Graph::template
516 UFE& blossom, UFE& tree,
517 std::queue<Node>& Q) {
520 while ( t!=middle ) {
525 bottom=_mate[middle];
526 position.set(bottom,D);
529 Node oldmiddle=middle;
530 middle=blossom.find(top);
532 tree.erase(oldmiddle);
533 blossom.insert(bottom);
534 blossom.join(bottom, oldmiddle);
535 blossom.join(top, oldmiddle);
538 template <typename Graph>
539 void MaxMatching<Graph>::augment(Node x,
540 typename Graph::template NodeMap<Node>& ear,
541 UFE& blossom, UFE& tree) {
543 while ( v!=INVALID ) {
551 typename UFE::ItemIt it;
552 for (tree.first(it,blossom.find(x)); tree.valid(it); tree.next(it)) {
553 if ( position[it] == D ) {
554 typename UFE::ItemIt b_it;
555 for (blossom.first(b_it,it); blossom.valid(b_it); blossom.next(b_it)) {
556 position.set( b_it ,C);
558 blossom.eraseClass(it);
559 } else position.set( it ,C);
567 } //END OF NAMESPACE LEMON
569 #endif //LEMON_MAX_MATCHING_H