Completions.
2 #ifndef LEMON_MAX_MATCHING_H
3 #define LEMON_MAX_MATCHING_H
7 ///\brief Maximum matching algorithm.
17 #include <unionfind.h>
18 #include <lemon/graph_utils.h>
25 ///Maximum matching algorithms class.
27 ///This class provides Edmonds' alternating forest matching
28 ///algorithm. The starting matching (if any) can be passed to the
29 ///algorithm using read-in functions \ref readNMapNode, \ref
30 ///readNMapEdge or \ref readEMapBool depending on the container. The
31 ///resulting maximum matching can be attained by write-out functions
32 ///\ref writeNMapNode, \ref writeNMapEdge or \ref writeEMapBool
33 ///depending on the preferred container.
35 ///The dual side of a mathcing is a map of the nodes to
36 ///MaxMatching::pos_enum, having values D, A and C showing the
37 ///Gallai-Edmonds decomposition of the graph. The nodes in D induce
38 ///a graph with factor-critical components, the nodes in A form the
39 ///barrier, and the nodes in C induce a graph having a perfect
40 ///matching. This decomposition can be attained by calling \ref
41 ///writePos after running the algorithm. Before subsequent runs,
42 ///the function \ref resetPos() must be called.
44 ///\param Graph The undirected graph type the algorithm runs on.
46 ///\author Jacint Szabo
47 template <typename Graph>
49 typedef typename Graph::Node Node;
50 typedef typename Graph::Edge Edge;
51 typedef typename Graph::UndirEdgeIt UndirEdgeIt;
52 typedef typename Graph::NodeIt NodeIt;
53 typedef typename Graph::IncEdgeIt IncEdgeIt;
55 typedef UnionFindEnum<Node, Graph::template NodeMap> UFE;
59 ///Indicates the Gallai-Edmonds decomposition of the graph.
61 ///Indicates the Gallai-Edmonds decomposition of the graph, which
62 ///shows an upper bound on the size of a maximum matching. The
63 ///nodes with pos_enum \c D induce a graph with factor-critical
64 ///components, the nodes in \c A form the canonical barrier, and the
65 ///nodes in \c C induce a graph having a perfect matching.
74 static const int HEUR_density=2;
76 typename Graph::template NodeMap<Node> mate;
77 typename Graph::template NodeMap<pos_enum> position;
81 MaxMatching(const Graph& _g) : g(_g), mate(_g,INVALID), position(_g,C) {}
83 ///Runs Edmonds' algorithm.
85 ///Runs Edmonds' algorithm for sparse graphs (countEdges <=
86 ///2*countNodes), and a heuristical Edmonds' algorithm with a
87 ///heuristic of postponing shrinks for dense graphs. \pre Before
88 ///the subsequent calls \ref resetPos must be called.
91 ///Runs Edmonds' algorithm.
93 ///If heur=0 it runs Edmonds' algorithm. If heur=1 it runs
94 ///Edmonds' algorithm with a heuristic of postponing shrinks,
95 ///giving a faster algorithm for dense graphs. \pre Before the
96 ///subsequent calls \ref resetPos must be called.
97 void runEdmonds( int heur );
99 ///Finds a greedy matching starting from the actual matching.
101 ///Starting form the actual matching stored, it finds a maximal
103 void greedyMatching();
105 ///Returns the size of the actual matching stored.
107 ///Returns the size of the actual matching stored. After \ref
108 ///run() it returns the size of a maximum matching in the graph.
111 ///Resets the map storing the Gallai-Edmonds decomposition.
113 ///Resets the map storing the Gallai-Edmonds decomposition of the
114 ///graph, making it possible to run the algorithm. Must be called
115 ///before all runs of the Edmonds algorithm, except for the first
119 ///Resets the actual matching to the empty matching.
121 ///Resets the actual matching to the empty matching.
123 void resetMatching();
125 ///Reads a matching from a \c Node map of \c Nodes.
127 ///Reads a matching from a \c Node map of \c Nodes. This map must be \e
128 ///symmetric, i.e. if \c map[u]=v then \c map[v]=u must hold, and
129 ///\c uv will be an edge of the matching.
130 template<typename NMapN>
131 void readNMapNode(NMapN& map) {
132 for(NodeIt v(g); v!=INVALID; ++v) {
137 ///Writes the stored matching to a \c Node map of \c Nodes.
139 ///Writes the stored matching to a \c Node map of \c Nodes. The
140 ///resulting map will be \e symmetric, i.e. if \c map[u]=v then \c
141 ///map[v]=u will hold, and now \c uv is an edge of the matching.
142 template<typename NMapN>
143 void writeNMapNode (NMapN& map) const {
144 for(NodeIt v(g); v!=INVALID; ++v) {
149 ///Reads a matching from a \c Node map of \c Edges.
151 ///Reads a matching from a \c Node map of incident \c Edges. This
152 ///map must have the property that if \c G.target(map[u])=v then \c
153 ///G.target(map[v])=u must hold, and now this edge is an edge of
155 template<typename NMapE>
156 void readNMapEdge(NMapE& map) {
157 for(NodeIt v(g); v!=INVALID; ++v) {
160 g.source(e) == v ? mate.set(v,g.target(e)) : mate.set(v,g.source(e));
164 ///Writes the matching stored to a \c Node map of \c Edges.
166 ///Writes the stored matching to a \c Node map of incident \c
167 ///Edges. This map will have the property that if \c
168 ///g.target(map[u])=v then \c g.target(map[v])=u holds, and now this
169 ///edge is an edge of the matching.
170 template<typename NMapE>
171 void writeNMapEdge (NMapE& map) const {
172 typename Graph::template NodeMap<bool> todo(g,true);
173 for(NodeIt v(g); v!=INVALID; ++v) {
174 if ( todo[v] && mate[v]!=INVALID ) {
176 for(IncEdgeIt e(g,v); e!=INVALID; ++e) {
177 if ( g.target(e) == u ) {
190 ///Reads a matching from an \c Edge map of \c bools.
192 ///Reads a matching from an \c Edge map of \c bools. This map must
193 ///have the property that there are no two adjacent edges \c e, \c
194 ///f with \c map[e]=map[f]=true. The edges \c e with \c
195 ///map[e]=true form the matching.
196 template<typename EMapB>
197 void readEMapBool(EMapB& map) {
198 for(UndirEdgeIt e(g); e!=INVALID; ++e) {
210 ///Writes the matching stored to an \c Edge map of \c bools.
212 ///Writes the matching stored to an \c Edge map of \c bools. This
213 ///map will have the property that there are no two adjacent edges
214 ///\c e, \c f with \c map[e]=map[f]=true. The edges \c e with \c
215 ///map[e]=true form the matching.
216 template<typename EMapB>
217 void writeEMapBool (EMapB& map) const {
218 for(UndirEdgeIt e(g); e!=INVALID; ++e) map.set(e,false);
220 typename Graph::template NodeMap<bool> todo(g,true);
221 for(NodeIt v(g); v!=INVALID; ++v) {
222 if ( todo[v] && mate[v]!=INVALID ) {
224 for(IncEdgeIt e(g,v); e!=INVALID; ++e) {
225 if ( g.target(e) == u ) {
237 ///Writes the canonical decomposition of the graph after running
240 ///After calling any run methods of the class, and before calling
241 ///\ref resetPos(), it writes the Gallai-Edmonds canonical
242 ///decomposition of the graph. \c map must be a node map
243 ///of \ref pos_enum 's.
244 template<typename NMapEnum>
245 void writePos (NMapEnum& map) const {
246 for(NodeIt v(g); v!=INVALID; ++v) map.set(v,position[v]);
251 void lateShrink(Node v, typename Graph::template NodeMap<Node>& ear,
252 UFE& blossom, UFE& tree);
254 void normShrink(Node v, typename Graph::NodeMap<Node>& ear,
255 UFE& blossom, UFE& tree);
257 bool noShrinkStep(Node x, typename Graph::NodeMap<Node>& ear,
258 UFE& blossom, UFE& tree, std::queue<Node>& Q);
260 void shrinkStep(Node& top, Node& middle, Node& bottom, typename Graph::NodeMap<Node>& ear,
261 UFE& blossom, UFE& tree, std::queue<Node>& Q);
263 void augment(Node x, typename Graph::NodeMap<Node>& ear,
264 UFE& blossom, UFE& tree);
268 // **********************************************************************
270 // **********************************************************************
273 template <typename Graph>
274 void MaxMatching<Graph>::run() {
275 if ( countUndirEdges(g) < HEUR_density*countNodes(g) ) {
278 } else runEdmonds(0);
282 template <typename Graph>
283 void MaxMatching<Graph>::runEdmonds( int heur=1 ) {
285 std::cout<<"Entering runEdmonds"<<std::endl;
287 typename Graph::template NodeMap<Node> ear(g,INVALID);
288 //undefined for the base nodes of the blossoms (i.e. for the
289 //representative elements of UFE blossom) and for the nodes in C
291 typename UFE::MapType blossom_base(g);
292 UFE blossom(blossom_base);
293 typename UFE::MapType tree_base(g);
296 for(NodeIt v(g); v!=INVALID; ++v) {
297 if ( position[v]==C && mate[v]==INVALID ) {
301 if ( heur == 1 ) lateShrink( v, ear, blossom, tree );
302 else normShrink( v, ear, blossom, tree );
307 std::cout<<" runEdmonds end"<<std::endl;
312 template <typename Graph>
313 void MaxMatching<Graph>::lateShrink(Node v, typename Graph::template NodeMap<Node>& ear,
314 UFE& blossom, UFE& tree) {
317 std::cout<<"Entering lateShrink"<<std::endl;
320 std::queue<Node> Q; //queue of the totally unscanned nodes
323 //queue of the nodes which must be scanned for a possible shrink
325 while ( !Q.empty() ) {
328 if ( noShrinkStep( x, ear, blossom, tree, Q ) ) return;
332 while ( !R.empty() ) {
336 for( IncEdgeIt e(g,x); e!=INVALID ; ++e ) {
339 if ( position[y] == D && blossom.find(x) != blossom.find(y) ) {
340 //x and y must be in the same tree//biztos? az oddbol d-belive lettek is?
342 typename Graph::template NodeMap<bool> path(g,false);
344 Node b=blossom.find(x);
347 while ( b!=INVALID ) {
348 b=blossom.find(ear[b]);
351 } //going till the root
354 Node middle=blossom.find(top);
356 while ( !path[middle] )
357 shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
361 middle=blossom.find(top);
363 Node blossom_base=blossom.find(base);
364 while ( middle!=blossom_base )
365 shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
367 blossom.makeRep(base);
368 } // if shrink is needed
370 //most nehany odd node is d-beli lett, es rajuk az is megnezendo hogy mely d-beliekkel szonszedosak mas faban
372 while ( !Q.empty() ) {
375 if ( noShrinkStep(x, ear, blossom, tree, Q) ) return;
379 } // while ( !R.empty() )
383 template <typename Graph>
384 void MaxMatching<Graph>::normShrink(Node v, typename Graph::NodeMap<Node>& ear,
385 UFE& blossom, UFE& tree) {
388 std::cout<<"Entering normShrink with node "<<g.id(v)<<std::endl;
391 std::queue<Node> Q; //queue of the unscanned nodes
393 while ( !Q.empty() ) {
395 std::cout<<"beginning of norm while"<<std::endl;
400 for( IncEdgeIt e(g,x); e!=INVALID; ++e ) {
403 for( IncEdgeIt f(g,x); f!=INVALID; ++f ) {
404 std::cout<<"Starting for." <<std::endl;
405 std::cout<<"edges " << g.id(f)<< " : " << g.id(g.target(f))<<std::endl;
406 std::cout<<"Ending for." <<std::endl;
409 std::cout<<"Ending the whole for." <<std::endl;
410 std::cout<<"for (In normShrink) with edge " << g.id(e)<< " : " << g.id(x);
414 std::cout<<" "<<g.id(y)<<std::endl;
416 switch ( position[y] ) {
417 case D: //x and y must be in the same tree //asszem nem!!!
419 std::cout<<" pos[y] " << position[y]<<std::endl;
420 std::cout<<" blossom.find(x) ="<< g.id(blossom.find(x))<<std::endl;
421 std::cout<<" blossom.find(y) ="<< g.id(blossom.find(y))<<std::endl;
424 if ( blossom.find(x) != blossom.find(y) ) { //shrink
425 typename Graph::template NodeMap<bool> path(g,false);
427 Node b=blossom.find(x);
430 while ( b!=INVALID ) {
431 b=blossom.find(ear[b]);
434 } //going till the root
437 Node middle=blossom.find(top);
439 while ( !path[middle] )
440 shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
444 middle=blossom.find(top);
446 Node blossom_base=blossom.find(base);
447 while ( middle!=blossom_base )
448 shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
450 blossom.makeRep(base);
454 if ( mate[y]!=INVALID ) { //grow
456 std::cout<<"grow"<<std::endl;
465 tree.join(y,blossom.find(x));
471 std::cout<<"augment"<<std::endl;
473 augment(x, ear, blossom, tree);
479 std::cout<<"end c eset"<<std::endl;
483 std::cout<<"end switch"<<std::endl;
488 template <typename Graph>
489 void MaxMatching<Graph>::greedyMatching() {
490 for(NodeIt v(g); v!=INVALID; ++v)
491 if ( mate[v]==INVALID ) {
492 for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) {
494 if ( mate[y]==INVALID && y!=v ) {
503 template <typename Graph>
504 int MaxMatching<Graph>::size() const {
506 for(NodeIt v(g); v!=INVALID; ++v) {
507 if ( mate[v]!=INVALID ) {
514 template <typename Graph>
515 void MaxMatching<Graph>::resetPos() {
516 for(NodeIt v(g); v!=INVALID; ++v)
520 template <typename Graph>
521 void MaxMatching<Graph>::resetMatching() {
522 for(NodeIt v(g); v!=INVALID; ++v)
526 template <typename Graph>
527 bool MaxMatching<Graph>::noShrinkStep(Node x, typename Graph::NodeMap<Node>& ear,
528 UFE& blossom, UFE& tree, std::queue<Node>& Q) {
529 for( IncEdgeIt e(g,x); e!= INVALID; ++e ) {
532 if ( position[y]==C ) {
533 if ( mate[y]!=INVALID ) { //grow
541 tree.join(y,blossom.find(x));
545 augment(x, ear, blossom, tree);
555 template <typename Graph>
556 void MaxMatching<Graph>::shrinkStep(Node& top, Node& middle, Node& bottom, typename Graph::NodeMap<Node>& ear,
557 UFE& blossom, UFE& tree, std::queue<Node>& Q) {
560 while ( t!=middle ) {
566 position.set(bottom,D);
569 Node oldmiddle=middle;
570 middle=blossom.find(top);
572 tree.erase(oldmiddle);
573 blossom.insert(bottom);
574 blossom.join(bottom, oldmiddle);
575 blossom.join(top, oldmiddle);
578 template <typename Graph>
579 void MaxMatching<Graph>::augment(Node x, typename Graph::NodeMap<Node>& ear,
580 UFE& blossom, UFE& tree) {
582 while ( v!=INVALID ) {
590 typename UFE::ItemIt it;
591 for (tree.first(it,blossom.find(x)); tree.valid(it); tree.next(it)) {
592 if ( position[it] == D ) {
593 typename UFE::ItemIt b_it;
594 for (blossom.first(b_it,it); blossom.valid(b_it); blossom.next(b_it)) {
595 position.set( b_it ,C);
597 blossom.eraseClass(it);
598 } else position.set( it ,C);
606 } //END OF NAMESPACE LEMON