95 ///Runs Edmonds' algorithm. |
95 ///Runs Edmonds' algorithm. |
96 |
96 |
97 ///Runs Edmonds' algorithm for sparse graphs (number of edges < |
97 ///Runs Edmonds' algorithm for sparse graphs (number of edges < |
98 ///2*number of nodes), and a heuristical Edmonds' algorithm with a |
98 ///2*number of nodes), and a heuristical Edmonds' algorithm with a |
99 ///heuristic of postponing shrinks for dense graphs. |
99 ///heuristic of postponing shrinks for dense graphs. |
100 inline void run(); |
100 void run() { |
|
101 if ( countUndirEdges(g) < HEUR_density*countNodes(g) ) { |
|
102 greedyMatching(); |
|
103 runEdmonds(0); |
|
104 } else runEdmonds(1); |
|
105 } |
|
106 |
101 |
107 |
102 ///Runs Edmonds' algorithm. |
108 ///Runs Edmonds' algorithm. |
103 |
109 |
104 ///If heur=0 it runs Edmonds' algorithm. If heur=1 it runs |
110 ///If heur=0 it runs Edmonds' algorithm. If heur=1 it runs |
105 ///Edmonds' algorithm with a heuristic of postponing shrinks, |
111 ///Edmonds' algorithm with a heuristic of postponing shrinks, |
106 ///giving a faster algorithm for dense graphs. |
112 ///giving a faster algorithm for dense graphs. |
107 void runEdmonds( int heur ); |
113 void runEdmonds( int heur = 1 ) { |
|
114 |
|
115 for(NodeIt v(g); v!=INVALID; ++v) |
|
116 position.set(v,C); |
|
117 |
|
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 |
|
121 |
|
122 typename UFE::MapType blossom_base(g); |
|
123 UFE blossom(blossom_base); |
|
124 typename UFE::MapType tree_base(g); |
|
125 UFE tree(tree_base); |
|
126 //If these UFE's would be members of the class then also |
|
127 //blossom_base and tree_base should be a member. |
|
128 |
|
129 for(NodeIt v(g); v!=INVALID; ++v) { |
|
130 if ( position[v]==C && _mate[v]==INVALID ) { |
|
131 blossom.insert(v); |
|
132 tree.insert(v); |
|
133 position.set(v,D); |
|
134 if ( heur == 1 ) lateShrink( v, ear, blossom, tree ); |
|
135 else normShrink( v, ear, blossom, tree ); |
|
136 } |
|
137 } |
|
138 } |
|
139 |
108 |
140 |
109 ///Finds a greedy matching starting from the actual matching. |
141 ///Finds a greedy matching starting from the actual matching. |
110 |
142 |
111 ///Starting form the actual matching stored, it finds a maximal |
143 ///Starting form the actual matching stored, it finds a maximal |
112 ///greedy matching. |
144 ///greedy matching. |
113 void greedyMatching(); |
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 ) { |
|
151 _mate.set(v,y); |
|
152 _mate.set(y,v); |
|
153 break; |
|
154 } |
|
155 } |
|
156 } |
|
157 } |
114 |
158 |
115 ///Returns the size of the actual matching stored. |
159 ///Returns the size of the actual matching stored. |
116 |
160 |
117 ///Returns the size of the actual matching stored. After \ref |
161 ///Returns the size of the actual matching stored. After \ref |
118 ///run() it returns the size of a maximum matching in the graph. |
162 ///run() it returns the size of a maximum matching in the graph. |
119 int size() const; |
163 int size() const { |
|
164 int s=0; |
|
165 for(NodeIt v(g); v!=INVALID; ++v) { |
|
166 if ( _mate[v]!=INVALID ) { |
|
167 ++s; |
|
168 } |
|
169 } |
|
170 return s/2; |
|
171 } |
|
172 |
120 |
173 |
121 ///Resets the actual matching to the empty matching. |
174 ///Resets the actual matching to the empty matching. |
122 |
175 |
123 ///Resets the actual matching to the empty matching. |
176 ///Resets the actual matching to the empty matching. |
124 /// |
177 /// |
125 void resetMatching(); |
178 void resetMatching() { |
|
179 for(NodeIt v(g); v!=INVALID; ++v) |
|
180 _mate.set(v,INVALID); |
|
181 } |
126 |
182 |
127 ///Returns the mate of a node in the actual matching. |
183 ///Returns the mate of a node in the actual matching. |
128 |
184 |
129 ///Returns the mate of a \c node in the actual matching. |
185 ///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. |
186 ///Returns INVALID if the \c node is not covered by the actual matching. |
282 // IMPLEMENTATIONS |
338 // IMPLEMENTATIONS |
283 // ********************************************************************** |
339 // ********************************************************************** |
284 |
340 |
285 |
341 |
286 template <typename Graph> |
342 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, |
343 void MaxMatching<Graph>::lateShrink(Node v, typename Graph::template NodeMap<Node>& ear, |
326 UFE& blossom, UFE& tree) { |
344 UFE& blossom, UFE& tree) { |
327 |
345 |
328 std::queue<Node> Q; //queue of the totally unscanned nodes |
346 std::queue<Node> Q; //queue of the totally unscanned nodes |
329 Q.push(v); |
347 Q.push(v); |
455 break; |
473 break; |
456 default: break; |
474 default: break; |
457 } |
475 } |
458 } |
476 } |
459 } |
477 } |
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 } |
478 } |
493 |
479 |
494 template <typename Graph> |
480 template <typename Graph> |
495 bool MaxMatching<Graph>::noShrinkStep(Node x, |
481 bool MaxMatching<Graph>::noShrinkStep(Node x, |
496 typename Graph::template |
482 typename Graph::template |