57 |
57 |
58 protected: |
58 protected: |
59 |
59 |
60 typedef typename Graph::Node Node; |
60 typedef typename Graph::Node Node; |
61 typedef typename Graph::Edge Edge; |
61 typedef typename Graph::Edge Edge; |
62 typedef typename Graph::UndirEdge UndirEdge; |
62 typedef typename Graph::UEdge UEdge; |
63 typedef typename Graph::UndirEdgeIt UndirEdgeIt; |
63 typedef typename Graph::UEdgeIt UEdgeIt; |
64 typedef typename Graph::NodeIt NodeIt; |
64 typedef typename Graph::NodeIt NodeIt; |
65 typedef typename Graph::IncEdgeIt IncEdgeIt; |
65 typedef typename Graph::IncEdgeIt IncEdgeIt; |
66 |
66 |
67 typedef UnionFindEnum<Node, Graph::template NodeMap> UFE; |
67 typedef UnionFindEnum<Node, Graph::template NodeMap> UFE; |
68 |
68 |
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 void run() { |
100 void run() { |
101 if ( countUndirEdges(g) < HEUR_density*countNodes(g) ) { |
101 if ( countUEdges(g) < HEUR_density*countNodes(g) ) { |
102 greedyMatching(); |
102 greedyMatching(); |
103 runEdmonds(0); |
103 runEdmonds(0); |
104 } else runEdmonds(1); |
104 } else runEdmonds(1); |
105 } |
105 } |
106 |
106 |
210 for(NodeIt v(g); v!=INVALID; ++v) { |
210 for(NodeIt v(g); v!=INVALID; ++v) { |
211 map.set(v,_mate[v]); |
211 map.set(v,_mate[v]); |
212 } |
212 } |
213 } |
213 } |
214 |
214 |
215 ///Reads a matching from an \c UndirEdge valued \c Node map. |
215 ///Reads a matching from an \c UEdge valued \c Node map. |
216 |
216 |
217 ///Reads a matching from an \c UndirEdge valued \c Node map. \c |
217 ///Reads a matching from an \c UEdge valued \c Node map. \c |
218 ///map[v] must be an \c UndirEdge incident to \c v. This map must |
218 ///map[v] must be an \c UEdge incident to \c v. This map must |
219 ///have the property that if \c g.oppositeNode(u,map[u])==v then |
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 |
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. |
221 ///joining \c u to \c v will be an edge of the matching. |
222 template<typename NMapE> |
222 template<typename NMapE> |
223 void readNMapEdge(NMapE& map) { |
223 void readNMapEdge(NMapE& map) { |
224 for(NodeIt v(g); v!=INVALID; ++v) { |
224 for(NodeIt v(g); v!=INVALID; ++v) { |
225 UndirEdge e=map[v]; |
225 UEdge e=map[v]; |
226 if ( e!=INVALID ) |
226 if ( e!=INVALID ) |
227 _mate.set(v,g.oppositeNode(v,e)); |
227 _mate.set(v,g.oppositeNode(v,e)); |
228 } |
228 } |
229 } |
229 } |
230 |
230 |
231 ///Writes the matching stored to an \c UndirEdge valued \c Node map. |
231 ///Writes the matching stored to an \c UEdge valued \c Node map. |
232 |
232 |
233 ///Writes the stored matching to an \c UndirEdge valued \c Node |
233 ///Writes the stored matching to an \c UEdge valued \c Node |
234 ///map. \c map[v] will be an \c UndirEdge incident to \c v. This |
234 ///map. \c map[v] will be an \c UEdge incident to \c v. This |
235 ///map will have the property that if \c g.oppositeNode(u,map[u]) |
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 |
236 ///== v then \c map[u]==map[v] holds, and now this edge is an edge |
237 ///of the matching. |
237 ///of the matching. |
238 template<typename NMapE> |
238 template<typename NMapE> |
239 void writeNMapEdge (NMapE& map) const { |
239 void writeNMapEdge (NMapE& map) const { |
261 ///must have the property that there are no two incident edges \c |
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 |
262 ///e, \c f with \c map[e]==map[f]==true. The edges \c e with \c |
263 ///map[e]==true form the matching. |
263 ///map[e]==true form the matching. |
264 template<typename EMapB> |
264 template<typename EMapB> |
265 void readEMapBool(EMapB& map) { |
265 void readEMapBool(EMapB& map) { |
266 for(UndirEdgeIt e(g); e!=INVALID; ++e) { |
266 for(UEdgeIt e(g); e!=INVALID; ++e) { |
267 if ( map[e] ) { |
267 if ( map[e] ) { |
268 Node u=g.source(e); |
268 Node u=g.source(e); |
269 Node v=g.target(e); |
269 Node v=g.target(e); |
270 _mate.set(u,v); |
270 _mate.set(u,v); |
271 _mate.set(v,u); |
271 _mate.set(v,u); |
280 ///map. This map will have the property that there are no two |
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 |
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. |
282 ///edges \c e with \c map[e]==true form the matching. |
283 template<typename EMapB> |
283 template<typename EMapB> |
284 void writeEMapBool (EMapB& map) const { |
284 void writeEMapBool (EMapB& map) const { |
285 for(UndirEdgeIt e(g); e!=INVALID; ++e) map.set(e,false); |
285 for(UEdgeIt e(g); e!=INVALID; ++e) map.set(e,false); |
286 |
286 |
287 typename Graph::template NodeMap<bool> todo(g,true); |
287 typename Graph::template NodeMap<bool> todo(g,true); |
288 for(NodeIt v(g); v!=INVALID; ++v) { |
288 for(NodeIt v(g); v!=INVALID; ++v) { |
289 if ( todo[v] && _mate[v]!=INVALID ) { |
289 if ( todo[v] && _mate[v]!=INVALID ) { |
290 Node u=_mate[v]; |
290 Node u=_mate[v]; |