69 typename Graph::template NodeMap<Node> mate; |
69 typename Graph::template NodeMap<Node> mate; |
70 typename Graph::template NodeMap<pos_enum> position; |
70 typename Graph::template NodeMap<pos_enum> position; |
71 |
71 |
72 public: |
72 public: |
73 |
73 |
74 MaxMatching(Graph& _G) : G(_G), mate(_G,INVALID), position(_G,C) {} |
74 MaxMatching(const Graph& _G) : G(_G), mate(_G,INVALID), position(_G,C) {} |
75 |
75 |
76 ///Runs Edmonds' algorithm. |
76 ///Runs Edmonds' algorithm. |
77 |
77 |
78 ///Runs Edmonds' algorithm for sparse graphs (edgeNum >= |
78 ///Runs Edmonds' algorithm for sparse graphs (edgeNum >= |
79 ///2*nodeNum), and a heuristical Edmonds' algorithm with a |
79 ///2*nodeNum), and a heuristical Edmonds' algorithm with a |
80 ///heuristic of postponing shrinks for dense graphs. \pre Before |
80 ///heuristic of postponing shrinks for dense graphs. \pre Before |
81 ///the subsequent calls \ref resetPos must be called. |
81 ///the subsequent calls \ref resetPos must be called. |
82 void run(); |
82 inline void run(); |
83 |
83 |
84 ///Runs Edmonds' algorithm. |
84 ///Runs Edmonds' algorithm. |
85 |
85 |
86 ///If heur=0 it runs Edmonds' algorithm. If heur=1 it runs |
86 ///If heur=0 it runs Edmonds' algorithm. If heur=1 it runs |
87 ///Edmonds' algorithm with a heuristic of postponing shrinks, |
87 ///Edmonds' algorithm with a heuristic of postponing shrinks, |
97 |
97 |
98 ///Returns the size of the actual matching stored. |
98 ///Returns the size of the actual matching stored. |
99 |
99 |
100 ///Returns the size of the actual matching stored. After \ref |
100 ///Returns the size of the actual matching stored. After \ref |
101 ///run() it returns the size of a maximum matching in the graph. |
101 ///run() it returns the size of a maximum matching in the graph. |
102 int size(); |
102 int size () const; |
103 |
103 |
104 ///Resets the map storing the Gallai-Edmonds decomposition. |
104 ///Resets the map storing the Gallai-Edmonds decomposition. |
105 |
105 |
106 ///Resets the map storing the Gallai-Edmonds decomposition of the |
106 ///Resets the map storing the Gallai-Edmonds decomposition of the |
107 ///graph, making it possible to run the algorithm. Must be called |
107 ///graph, making it possible to run the algorithm. Must be called |
132 |
132 |
133 ///Writes the stored matching to a \c Node map of \c Nodes. The |
133 ///Writes the stored matching to a \c Node map of \c Nodes. The |
134 ///resulting map will be \e symmetric, i.e. if \c map[u]=v then \c |
134 ///resulting map will be \e symmetric, i.e. if \c map[u]=v then \c |
135 ///map[v]=u will hold, and now \c uv is an edge of the matching. |
135 ///map[v]=u will hold, and now \c uv is an edge of the matching. |
136 template<typename NMapN> |
136 template<typename NMapN> |
137 void writeNMapNode(NMapN& map) { |
137 void writeNMapNode (NMapN& map) const { |
138 NodeIt v; |
138 NodeIt v; |
139 for( G.first(v); G.valid(v); G.next(v)) { |
139 for( G.first(v); G.valid(v); G.next(v)) { |
140 map.set(v,mate[v]); |
140 map.set(v,mate[v]); |
141 } |
141 } |
142 } |
142 } |
162 ///Writes the stored matching to a \c Node map of incident \c |
162 ///Writes the stored matching to a \c Node map of incident \c |
163 ///Edges. This map will have the property that if \c |
163 ///Edges. This map will have the property that if \c |
164 ///G.bNode(map[u])=v then \c G.bNode(map[v])=u holds, and now this |
164 ///G.bNode(map[u])=v then \c G.bNode(map[v])=u holds, and now this |
165 ///edge is an edge of the matching. |
165 ///edge is an edge of the matching. |
166 template<typename NMapE> |
166 template<typename NMapE> |
167 void writeNMapEdge(NMapE& map) { |
167 void writeNMapEdge (NMapE& map) const { |
168 typename Graph::template NodeMap<bool> todo(G,false); |
168 typename Graph::template NodeMap<bool> todo(G,false); |
169 NodeIt v; |
169 NodeIt v; |
170 for( G.first(v); G.valid(v); G.next(v)) { |
170 for( G.first(v); G.valid(v); G.next(v)) { |
171 if ( mate[v]!=INVALID ) todo.set(v,true); |
171 if ( mate[v]!=INVALID ) todo.set(v,true); |
172 } |
172 } |
210 ///Writes the matching stored to an \c Edge map of \c bools. This |
210 ///Writes the matching stored to an \c Edge map of \c bools. This |
211 ///map will have the property that there are no two adjacent edges |
211 ///map will have the property that there are no two adjacent edges |
212 ///\c e, \c f with \c map[e]=map[f]=true. The edges \c e with \c |
212 ///\c e, \c f with \c map[e]=map[f]=true. The edges \c e with \c |
213 ///map[e]=true form the matching. |
213 ///map[e]=true form the matching. |
214 template<typename EMapB> |
214 template<typename EMapB> |
215 void writeEMapBool(EMapB& map) { |
215 void writeEMapBool (EMapB& map) const { |
216 typename Graph::template NodeMap<bool> todo(G,false); |
216 typename Graph::template NodeMap<bool> todo(G,false); |
217 NodeIt v; |
217 NodeIt v; |
218 for( G.first(v); G.valid(v); G.next(v)) { |
218 for( G.first(v); G.valid(v); G.next(v)) { |
219 if ( mate[v]!=INVALID ) todo.set(v,true); |
219 if ( mate[v]!=INVALID ) todo.set(v,true); |
220 } |
220 } |
239 |
239 |
240 ///After calling any run methods of the class, and before calling |
240 ///After calling any run methods of the class, and before calling |
241 ///\ref resetPos(), it writes the Gallai-Edmonds canonical |
241 ///\ref resetPos(), it writes the Gallai-Edmonds canonical |
242 ///decomposition of the graph. \c map must be a node map of \ref pos_enum 's. |
242 ///decomposition of the graph. \c map must be a node map of \ref pos_enum 's. |
243 template<typename NMapEnum> |
243 template<typename NMapEnum> |
244 void writePos(NMapEnum& map) { |
244 void writePos (NMapEnum& map) const { |
245 NodeIt v; |
245 NodeIt v; |
246 for( G.first(v); G.valid(v); G.next(v)) map.set(v,position[v]); |
246 for( G.first(v); G.valid(v); G.next(v)) map.set(v,position[v]); |
247 } |
247 } |
248 |
248 |
249 private: |
249 private: |