45 ///MaxMatching::pos_enum, having values D, A and C showing the |
45 ///MaxMatching::pos_enum, having values D, A and C showing the |
46 ///Gallai-Edmonds decomposition of the graph. The nodes in D induce |
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 |
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 |
48 ///barrier, and the nodes in C induce a graph having a perfect |
49 ///matching. This decomposition can be attained by calling \ref |
49 ///matching. This decomposition can be attained by calling \ref |
50 ///writePos after running the algorithm. Before subsequent runs, |
50 ///writePos after running the algorithm. |
51 ///the function \ref resetPos() must be called. |
|
52 /// |
51 /// |
53 ///\param Graph The undirected graph type the algorithm runs on. |
52 ///\param Graph The undirected graph type the algorithm runs on. |
54 /// |
53 /// |
55 ///\author Jacint Szabo |
54 ///\author Jacint Szabo |
56 template <typename Graph> |
55 template <typename Graph> |
85 typename Graph::template NodeMap<Node> mate; |
84 typename Graph::template NodeMap<Node> mate; |
86 typename Graph::template NodeMap<pos_enum> position; |
85 typename Graph::template NodeMap<pos_enum> position; |
87 |
86 |
88 public: |
87 public: |
89 |
88 |
90 MaxMatching(const Graph& _g) : g(_g), mate(_g,INVALID), position(_g,C) {} |
89 MaxMatching(const Graph& _g) : g(_g), mate(_g,INVALID), position(_g) {} |
91 |
90 |
92 ///Runs Edmonds' algorithm. |
91 ///Runs Edmonds' algorithm. |
93 |
92 |
94 ///Runs Edmonds' algorithm for sparse graphs (number of edges < |
93 ///Runs Edmonds' algorithm for sparse graphs (number of edges < |
95 ///2*number of nodes), and a heuristical Edmonds' algorithm with a |
94 ///2*number of nodes), and a heuristical Edmonds' algorithm with a |
96 ///heuristic of postponing shrinks for dense graphs. \pre Before |
95 ///heuristic of postponing shrinks for dense graphs. |
97 ///the subsequent calls \ref resetPos must be called. |
|
98 inline void run(); |
96 inline void run(); |
99 |
97 |
100 ///Runs Edmonds' algorithm. |
98 ///Runs Edmonds' algorithm. |
101 |
99 |
102 ///If heur=0 it runs Edmonds' algorithm. If heur=1 it runs |
100 ///If heur=0 it runs Edmonds' algorithm. If heur=1 it runs |
103 ///Edmonds' algorithm with a heuristic of postponing shrinks, |
101 ///Edmonds' algorithm with a heuristic of postponing shrinks, |
104 ///giving a faster algorithm for dense graphs. \pre Before the |
102 ///giving a faster algorithm for dense graphs. |
105 ///subsequent calls \ref resetPos must be called. |
|
106 void runEdmonds( int heur ); |
103 void runEdmonds( int heur ); |
107 |
104 |
108 ///Finds a greedy matching starting from the actual matching. |
105 ///Finds a greedy matching starting from the actual matching. |
109 |
106 |
110 ///Starting form the actual matching stored, it finds a maximal |
107 ///Starting form the actual matching stored, it finds a maximal |
114 ///Returns the size of the actual matching stored. |
111 ///Returns the size of the actual matching stored. |
115 |
112 |
116 ///Returns the size of the actual matching stored. After \ref |
113 ///Returns the size of the actual matching stored. After \ref |
117 ///run() it returns the size of a maximum matching in the graph. |
114 ///run() it returns the size of a maximum matching in the graph. |
118 int size() const; |
115 int size() const; |
119 |
|
120 ///Resets the map storing the Gallai-Edmonds decomposition. |
|
121 |
|
122 ///Resets the map storing the Gallai-Edmonds decomposition of the |
|
123 ///graph, making it possible to run the algorithm. Must be called |
|
124 ///before all runs of the Edmonds algorithm, except for the first |
|
125 ///run. |
|
126 void resetPos(); |
|
127 |
116 |
128 ///Resets the actual matching to the empty matching. |
117 ///Resets the actual matching to the empty matching. |
129 |
118 |
130 ///Resets the actual matching to the empty matching. |
119 ///Resets the actual matching to the empty matching. |
131 /// |
120 /// |
243 |
232 |
244 |
233 |
245 ///Writes the canonical decomposition of the graph after running |
234 ///Writes the canonical decomposition of the graph after running |
246 ///the algorithm. |
235 ///the algorithm. |
247 |
236 |
248 ///After calling any run methods of the class, and before calling |
237 ///After calling any run methods of the class, it writes the |
249 ///\ref resetPos(), it writes the Gallai-Edmonds canonical |
238 ///Gallai-Edmonds canonical decomposition of the graph. \c map |
250 ///decomposition of the graph. \c map must be a node map |
239 ///must be a node map of \ref pos_enum 's. |
251 ///of \ref pos_enum 's. |
|
252 template<typename NMapEnum> |
240 template<typename NMapEnum> |
253 void writePos (NMapEnum& map) const { |
241 void writePos (NMapEnum& map) const { |
254 for(NodeIt v(g); v!=INVALID; ++v) map.set(v,position[v]); |
242 for(NodeIt v(g); v!=INVALID; ++v) map.set(v,position[v]); |
255 } |
243 } |
256 |
244 |
288 } |
276 } |
289 |
277 |
290 |
278 |
291 template <typename Graph> |
279 template <typename Graph> |
292 void MaxMatching<Graph>::runEdmonds( int heur=1 ) { |
280 void MaxMatching<Graph>::runEdmonds( int heur=1 ) { |
293 |
281 |
|
282 for(NodeIt v(g); v!=INVALID; ++v) |
|
283 position.set(v,C); |
|
284 |
294 typename Graph::template NodeMap<Node> ear(g,INVALID); |
285 typename Graph::template NodeMap<Node> ear(g,INVALID); |
295 //undefined for the base nodes of the blossoms (i.e. for the |
286 //undefined for the base nodes of the blossoms (i.e. for the |
296 //representative elements of UFE blossom) and for the nodes in C |
287 //representative elements of UFE blossom) and for the nodes in C |
297 |
288 |
298 typename UFE::MapType blossom_base(g); |
289 typename UFE::MapType blossom_base(g); |
471 if ( mate[v]!=INVALID ) { |
462 if ( mate[v]!=INVALID ) { |
472 ++s; |
463 ++s; |
473 } |
464 } |
474 } |
465 } |
475 return (int)s/2; |
466 return (int)s/2; |
476 } |
|
477 |
|
478 template <typename Graph> |
|
479 void MaxMatching<Graph>::resetPos() { |
|
480 for(NodeIt v(g); v!=INVALID; ++v) |
|
481 position.set(v,C); |
|
482 } |
467 } |
483 |
468 |
484 template <typename Graph> |
469 template <typename Graph> |
485 void MaxMatching<Graph>::resetMatching() { |
470 void MaxMatching<Graph>::resetMatching() { |
486 for(NodeIt v(g); v!=INVALID; ++v) |
471 for(NodeIt v(g); v!=INVALID; ++v) |