85 |
85 |
86 /// \brief Initalize the data structures. |
86 /// \brief Initalize the data structures. |
87 /// |
87 /// |
88 /// It initalizes the data structures and creates an empty matching. |
88 /// It initalizes the data structures and creates an empty matching. |
89 void init() { |
89 void init() { |
90 for (ANodeIt it(*graph); it != INVALID; ++it) { |
90 for (ANodeIt it(*_graph); it != INVALID; ++it) { |
91 anode_matching[it] = INVALID; |
91 _matching.set(it, INVALID); |
92 } |
92 } |
93 for (BNodeIt it(*graph); it != INVALID; ++it) { |
93 for (BNodeIt it(*_graph); it != INVALID; ++it) { |
94 bnode_matching[it] = INVALID; |
94 _rmatching.set(it, INVALID); |
95 } |
95 _reached.set(it, -1); |
96 matching_size = 0; |
96 } |
|
97 _size = 0; |
|
98 _phase = -1; |
97 } |
99 } |
98 |
100 |
99 /// \brief Initalize the data structures. |
101 /// \brief Initalize the data structures. |
100 /// |
102 /// |
101 /// It initalizes the data structures and creates a greedy |
103 /// It initalizes the data structures and creates a greedy |
102 /// matching. From this matching sometimes it is faster to get |
104 /// matching. From this matching sometimes it is faster to get |
103 /// the matching than from the initial empty matching. |
105 /// the matching than from the initial empty matching. |
104 void greedyInit() { |
106 void greedyInit() { |
105 matching_size = 0; |
107 _size = 0; |
106 for (BNodeIt it(*graph); it != INVALID; ++it) { |
108 for (BNodeIt it(*_graph); it != INVALID; ++it) { |
107 bnode_matching[it] = INVALID; |
109 _rmatching.set(it, INVALID); |
108 } |
110 _reached.set(it, 0); |
109 for (ANodeIt it(*graph); it != INVALID; ++it) { |
111 } |
110 anode_matching[it] = INVALID; |
112 for (ANodeIt it(*_graph); it != INVALID; ++it) { |
111 for (IncEdgeIt jt(*graph, it); jt != INVALID; ++jt) { |
113 _matching[it] = INVALID; |
112 if (bnode_matching[graph->bNode(jt)] == INVALID) { |
114 for (IncEdgeIt jt(*_graph, it); jt != INVALID; ++jt) { |
113 anode_matching[it] = jt; |
115 if (_rmatching[_graph->bNode(jt)] == INVALID) { |
114 bnode_matching[graph->bNode(jt)] = jt; |
116 _matching.set(it, jt); |
115 ++matching_size; |
117 _rmatching.set(_graph->bNode(jt), jt); |
|
118 _reached.set(it, -1); |
|
119 ++_size; |
116 break; |
120 break; |
117 } |
121 } |
118 } |
122 } |
119 } |
123 } |
|
124 _phase = 0; |
120 } |
125 } |
121 |
126 |
122 /// \brief Initalize the data structures with an initial matching. |
127 /// \brief Initalize the data structures with an initial matching. |
123 /// |
128 /// |
124 /// It initalizes the data structures with an initial matching. |
129 /// It initalizes the data structures with an initial matching. |
125 template <typename MatchingMap> |
130 template <typename MatchingMap> |
126 void matchingInit(const MatchingMap& mm) { |
131 void matchingInit(const MatchingMap& mm) { |
127 for (ANodeIt it(*graph); it != INVALID; ++it) { |
132 for (ANodeIt it(*_graph); it != INVALID; ++it) { |
128 anode_matching[it] = INVALID; |
133 _matching.set(it, INVALID); |
129 } |
134 } |
130 for (BNodeIt it(*graph); it != INVALID; ++it) { |
135 for (BNodeIt it(*_graph); it != INVALID; ++it) { |
131 bnode_matching[it] = INVALID; |
136 _rmatching.set(it, INVALID); |
132 } |
137 _reached.set(it, 0); |
133 matching_size = 0; |
138 } |
134 for (UEdgeIt it(*graph); it != INVALID; ++it) { |
139 _size = 0; |
|
140 for (UEdgeIt it(*_graph); it != INVALID; ++it) { |
135 if (mm[it]) { |
141 if (mm[it]) { |
136 ++matching_size; |
142 ++_size; |
137 anode_matching[graph->aNode(it)] = it; |
143 _matching.set(_graph->aNode(it), it); |
138 bnode_matching[graph->bNode(it)] = it; |
144 _rmatching.set(_graph->bNode(it), it); |
139 } |
145 _reached.set(it, 0); |
140 } |
146 } |
|
147 } |
|
148 _phase = 0; |
141 } |
149 } |
142 |
150 |
143 /// \brief Initalize the data structures with an initial matching. |
151 /// \brief Initalize the data structures with an initial matching. |
144 /// |
152 /// |
145 /// It initalizes the data structures with an initial matching. |
153 /// It initalizes the data structures with an initial matching. |
146 /// \return %True when the given map contains really a matching. |
154 /// \return %True when the given map contains really a matching. |
147 template <typename MatchingMap> |
155 template <typename MatchingMap> |
148 void checkedMatchingInit(const MatchingMap& mm) { |
156 bool checkedMatchingInit(const MatchingMap& mm) { |
149 for (ANodeIt it(*graph); it != INVALID; ++it) { |
157 for (ANodeIt it(*_graph); it != INVALID; ++it) { |
150 anode_matching[it] = INVALID; |
158 _matching.set(it, INVALID); |
151 } |
159 } |
152 for (BNodeIt it(*graph); it != INVALID; ++it) { |
160 for (BNodeIt it(*_graph); it != INVALID; ++it) { |
153 bnode_matching[it] = INVALID; |
161 _rmatching.set(it, INVALID); |
154 } |
162 _reached.set(it, 0); |
155 matching_size = 0; |
163 } |
156 for (UEdgeIt it(*graph); it != INVALID; ++it) { |
164 _size = 0; |
|
165 for (UEdgeIt it(*_graph); it != INVALID; ++it) { |
157 if (mm[it]) { |
166 if (mm[it]) { |
158 ++matching_size; |
167 ++_size; |
159 if (anode_matching[graph->aNode(it)] != INVALID) { |
168 if (_matching[_graph->aNode(it)] != INVALID) { |
160 return false; |
169 return false; |
161 } |
170 } |
162 anode_matching[graph->aNode(it)] = it; |
171 _matching.set(_graph->aNode(it), it); |
163 if (bnode_matching[graph->aNode(it)] != INVALID) { |
172 if (_matching[_graph->bNode(it)] != INVALID) { |
164 return false; |
173 return false; |
165 } |
174 } |
166 bnode_matching[graph->bNode(it)] = it; |
175 _matching.set(_graph->bNode(it), it); |
167 } |
176 _reached.set(_graph->bNode(it), -1); |
|
177 } |
|
178 } |
|
179 _phase = 0; |
|
180 return true; |
|
181 } |
|
182 |
|
183 private: |
|
184 |
|
185 bool _find_path(Node anode, int maxlevel, |
|
186 typename Graph::template BNodeMap<int>& level) { |
|
187 for (IncEdgeIt it(*_graph, anode); it != INVALID; ++it) { |
|
188 Node bnode = _graph->bNode(it); |
|
189 if (level[bnode] == maxlevel) { |
|
190 level.set(bnode, -1); |
|
191 if (maxlevel == 0) { |
|
192 _matching.set(anode, it); |
|
193 _rmatching.set(bnode, it); |
|
194 return true; |
|
195 } else { |
|
196 Node nnode = _graph->aNode(_rmatching[bnode]); |
|
197 if (_find_path(nnode, maxlevel - 1, level)) { |
|
198 _matching.set(anode, it); |
|
199 _rmatching.set(bnode, it); |
|
200 return true; |
|
201 } |
|
202 } |
|
203 } |
168 } |
204 } |
169 return false; |
205 return false; |
170 } |
206 } |
171 |
207 |
|
208 public: |
|
209 |
172 /// \brief An augmenting phase of the Hopcroft-Karp algorithm |
210 /// \brief An augmenting phase of the Hopcroft-Karp algorithm |
173 /// |
211 /// |
174 /// It runs an augmenting phase of the Hopcroft-Karp |
212 /// It runs an augmenting phase of the Hopcroft-Karp |
175 /// algorithm. This phase finds maximum count of edge disjoint |
213 /// algorithm. This phase finds maximal edge disjoint augmenting |
176 /// augmenting paths and augments on these paths. The algorithm |
214 /// paths and augments on these paths. The algorithm consists at |
177 /// consists at most of \f$ O(\sqrt{n}) \f$ phase and one phase is |
215 /// most of \f$ O(\sqrt{n}) \f$ phase and one phase is \f$ O(e) |
178 /// \f$ O(e) \f$ long. |
216 /// \f$ long. |
179 bool augment() { |
217 bool augment() { |
180 |
218 |
181 typename Graph::template ANodeMap<bool> areached(*graph, false); |
219 ++_phase; |
182 typename Graph::template BNodeMap<bool> breached(*graph, false); |
220 |
183 |
221 typename Graph::template BNodeMap<int> _level(*_graph, -1); |
184 typename Graph::template BNodeMap<UEdge> bpred(*graph, INVALID); |
222 typename Graph::template ANodeMap<bool> _found(*_graph, false); |
185 |
223 |
186 std::vector<Node> queue, bqueue; |
224 std::vector<Node> queue, aqueue; |
187 for (ANodeIt it(*graph); it != INVALID; ++it) { |
225 for (BNodeIt it(*_graph); it != INVALID; ++it) { |
188 if (anode_matching[it] == INVALID) { |
226 if (_rmatching[it] == INVALID) { |
189 queue.push_back(it); |
227 queue.push_back(it); |
190 areached[it] = true; |
228 _reached.set(it, _phase); |
|
229 _level.set(it, 0); |
191 } |
230 } |
192 } |
231 } |
193 |
232 |
194 bool success = false; |
233 bool success = false; |
195 |
234 |
|
235 int level = 0; |
196 while (!success && !queue.empty()) { |
236 while (!success && !queue.empty()) { |
197 std::vector<Node> newqueue; |
237 std::vector<Node> nqueue; |
198 for (int i = 0; i < int(queue.size()); ++i) { |
238 for (int i = 0; i < int(queue.size()); ++i) { |
199 Node anode = queue[i]; |
239 Node bnode = queue[i]; |
200 for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) { |
240 for (IncEdgeIt jt(*_graph, bnode); jt != INVALID; ++jt) { |
201 Node bnode = graph->bNode(jt); |
241 Node anode = _graph->aNode(jt); |
202 if (breached[bnode]) continue; |
242 if (_matching[anode] == INVALID) { |
203 breached[bnode] = true; |
243 |
204 bpred[bnode] = jt; |
244 if (!_found[anode]) { |
205 if (bnode_matching[bnode] == INVALID) { |
245 if (_find_path(anode, level, _level)) { |
206 bqueue.push_back(bnode); |
246 ++_size; |
|
247 } |
|
248 _found.set(anode, true); |
|
249 } |
207 success = true; |
250 success = true; |
208 } else { |
251 } else { |
209 Node newanode = graph->aNode(bnode_matching[bnode]); |
252 Node nnode = _graph->bNode(_matching[anode]); |
210 if (!areached[newanode]) { |
253 if (_reached[nnode] != _phase) { |
211 areached[newanode] = true; |
254 _reached.set(nnode, _phase); |
212 newqueue.push_back(newanode); |
255 nqueue.push_back(nnode); |
|
256 _level.set(nnode, level + 1); |
213 } |
257 } |
214 } |
258 } |
215 } |
259 } |
216 } |
260 } |
217 queue.swap(newqueue); |
261 ++level; |
218 } |
262 queue.swap(nqueue); |
219 |
263 } |
220 if (success) { |
264 |
221 |
|
222 typename Graph::template ANodeMap<bool> aused(*graph, false); |
|
223 |
|
224 for (int i = 0; i < int(bqueue.size()); ++i) { |
|
225 Node bnode = bqueue[i]; |
|
226 |
|
227 bool used = false; |
|
228 |
|
229 while (bnode != INVALID) { |
|
230 UEdge uedge = bpred[bnode]; |
|
231 Node anode = graph->aNode(uedge); |
|
232 |
|
233 if (aused[anode]) { |
|
234 used = true; |
|
235 break; |
|
236 } |
|
237 |
|
238 bnode = anode_matching[anode] != INVALID ? |
|
239 graph->bNode(anode_matching[anode]) : INVALID; |
|
240 |
|
241 } |
|
242 |
|
243 if (used) continue; |
|
244 |
|
245 bnode = bqueue[i]; |
|
246 while (bnode != INVALID) { |
|
247 UEdge uedge = bpred[bnode]; |
|
248 Node anode = graph->aNode(uedge); |
|
249 |
|
250 bnode_matching[bnode] = uedge; |
|
251 |
|
252 bnode = anode_matching[anode] != INVALID ? |
|
253 graph->bNode(anode_matching[anode]) : INVALID; |
|
254 |
|
255 anode_matching[anode] = uedge; |
|
256 |
|
257 aused[anode] = true; |
|
258 } |
|
259 ++matching_size; |
|
260 |
|
261 } |
|
262 } |
|
263 return success; |
265 return success; |
264 } |
266 } |
265 |
267 private: |
266 /// \brief An augmenting phase of the Ford-Fulkerson algorithm |
268 |
267 /// |
269 void _find_path_bfs(Node anode, |
268 /// It runs an augmenting phase of the Ford-Fulkerson |
270 typename Graph::template ANodeMap<UEdge>& pred) { |
269 /// algorithm. This phase finds only one augmenting path and |
271 while (true) { |
270 /// augments only on this paths. The algorithm consists at most |
272 UEdge uedge = pred[anode]; |
271 /// of \f$ O(n) \f$ simple phase and one phase is at most |
273 Node bnode = _graph->bNode(uedge); |
272 /// \f$ O(e) \f$ long. |
274 |
273 bool simpleAugment() { |
275 UEdge nedge = _rmatching[bnode]; |
274 |
276 |
275 typename Graph::template ANodeMap<bool> areached(*graph, false); |
277 _matching.set(anode, uedge); |
276 typename Graph::template BNodeMap<bool> breached(*graph, false); |
278 _rmatching.set(bnode, uedge); |
277 |
279 |
278 typename Graph::template BNodeMap<UEdge> bpred(*graph, INVALID); |
280 if (nedge == INVALID) break; |
279 |
281 anode = _graph->aNode(nedge); |
280 std::vector<Node> queue; |
282 } |
281 for (ANodeIt it(*graph); it != INVALID; ++it) { |
283 } |
282 if (anode_matching[it] == INVALID) { |
284 |
|
285 public: |
|
286 |
|
287 /// \brief An augmenting phase with single path augementing |
|
288 /// |
|
289 /// This phase finds only one augmenting paths and augments on |
|
290 /// these paths. The algorithm consists at most of \f$ O(n) \f$ |
|
291 /// phase and one phase is \f$ O(e) \f$ long. |
|
292 bool simpleAugment() { |
|
293 ++_phase; |
|
294 |
|
295 typename Graph::template ANodeMap<UEdge> _pred(*_graph); |
|
296 |
|
297 std::vector<Node> queue, aqueue; |
|
298 for (BNodeIt it(*_graph); it != INVALID; ++it) { |
|
299 if (_rmatching[it] == INVALID) { |
283 queue.push_back(it); |
300 queue.push_back(it); |
284 areached[it] = true; |
301 _reached.set(it, _phase); |
285 } |
302 } |
286 } |
303 } |
287 |
304 |
288 while (!queue.empty()) { |
305 bool success = false; |
289 std::vector<Node> newqueue; |
306 |
|
307 int level = 0; |
|
308 while (!success && !queue.empty()) { |
|
309 std::vector<Node> nqueue; |
290 for (int i = 0; i < int(queue.size()); ++i) { |
310 for (int i = 0; i < int(queue.size()); ++i) { |
291 Node anode = queue[i]; |
311 Node bnode = queue[i]; |
292 for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) { |
312 for (IncEdgeIt jt(*_graph, bnode); jt != INVALID; ++jt) { |
293 Node bnode = graph->bNode(jt); |
313 Node anode = _graph->aNode(jt); |
294 if (breached[bnode]) continue; |
314 if (_matching[anode] == INVALID) { |
295 breached[bnode] = true; |
315 _pred.set(anode, jt); |
296 bpred[bnode] = jt; |
316 _find_path_bfs(anode, _pred); |
297 if (bnode_matching[bnode] == INVALID) { |
317 ++_size; |
298 while (bnode != INVALID) { |
318 return true; |
299 UEdge uedge = bpred[bnode]; |
|
300 anode = graph->aNode(uedge); |
|
301 |
|
302 bnode_matching[bnode] = uedge; |
|
303 |
|
304 bnode = anode_matching[anode] != INVALID ? |
|
305 graph->bNode(anode_matching[anode]) : INVALID; |
|
306 |
|
307 anode_matching[anode] = uedge; |
|
308 |
|
309 } |
|
310 ++matching_size; |
|
311 return true; |
|
312 } else { |
319 } else { |
313 Node newanode = graph->aNode(bnode_matching[bnode]); |
320 Node nnode = _graph->bNode(_matching[anode]); |
314 if (!areached[newanode]) { |
321 if (_reached[nnode] != _phase) { |
315 areached[newanode] = true; |
322 _pred.set(anode, jt); |
316 newqueue.push_back(newanode); |
323 _reached.set(nnode, _phase); |
|
324 nqueue.push_back(nnode); |
317 } |
325 } |
318 } |
326 } |
319 } |
327 } |
320 } |
328 } |
321 queue.swap(newqueue); |
329 ++level; |
|
330 queue.swap(nqueue); |
322 } |
331 } |
323 |
332 |
324 return false; |
333 return success; |
325 } |
334 } |
|
335 |
|
336 |
326 |
337 |
327 /// \brief Starts the algorithm. |
338 /// \brief Starts the algorithm. |
328 /// |
339 /// |
329 /// Starts the algorithm. It runs augmenting phases until the optimal |
340 /// Starts the algorithm. It runs augmenting phases until the optimal |
330 /// solution reached. |
341 /// solution reached. |
348 /// Before the use of these functions, |
359 /// Before the use of these functions, |
349 /// either run() or start() must be called. |
360 /// either run() or start() must be called. |
350 |
361 |
351 ///@{ |
362 ///@{ |
352 |
363 |
|
364 /// \brief Return true if the given uedge is in the matching. |
|
365 /// |
|
366 /// It returns true if the given uedge is in the matching. |
|
367 bool matchingEdge(const UEdge& edge) const { |
|
368 return _matching[_graph->aNode(edge)] == edge; |
|
369 } |
|
370 |
|
371 /// \brief Returns the matching edge from the node. |
|
372 /// |
|
373 /// Returns the matching edge from the node. If there is not such |
|
374 /// edge it gives back \c INVALID. |
|
375 /// \note If the parameter node is a B-node then the running time is |
|
376 /// propotional to the degree of the node. |
|
377 UEdge matchingEdge(const Node& node) const { |
|
378 if (_graph->aNode(node)) { |
|
379 return _matching[node]; |
|
380 } else { |
|
381 return _rmatching[node]; |
|
382 } |
|
383 } |
|
384 |
353 /// \brief Set true all matching uedge in the map. |
385 /// \brief Set true all matching uedge in the map. |
354 /// |
386 /// |
355 /// Set true all matching uedge in the map. It does not change the |
387 /// Set true all matching uedge in the map. It does not change the |
356 /// value mapped to the other uedges. |
388 /// value mapped to the other uedges. |
357 /// \return The number of the matching edges. |
389 /// \return The number of the matching edges. |
358 template <typename MatchingMap> |
390 template <typename MatchingMap> |
359 int quickMatching(MatchingMap& mm) const { |
391 int quickMatching(MatchingMap& mm) const { |
360 for (ANodeIt it(*graph); it != INVALID; ++it) { |
392 for (ANodeIt it(*_graph); it != INVALID; ++it) { |
361 if (anode_matching[it] != INVALID) { |
393 if (_matching[it] != INVALID) { |
362 mm.set(anode_matching[it], true); |
394 mm.set(_matching[it], true); |
363 } |
395 } |
364 } |
396 } |
365 return matching_size; |
397 return _size; |
366 } |
398 } |
367 |
399 |
368 /// \brief Set true all matching uedge in the map and the others to false. |
400 /// \brief Set true all matching uedge in the map and the others to false. |
369 /// |
401 /// |
370 /// Set true all matching uedge in the map and the others to false. |
402 /// Set true all matching uedge in the map and the others to false. |
371 /// \return The number of the matching edges. |
403 /// \return The number of the matching edges. |
372 template <typename MatchingMap> |
404 template <typename MatchingMap> |
373 int matching(MatchingMap& mm) const { |
405 int matching(MatchingMap& mm) const { |
374 for (UEdgeIt it(*graph); it != INVALID; ++it) { |
406 for (UEdgeIt it(*_graph); it != INVALID; ++it) { |
375 mm.set(it, it == anode_matching[graph->aNode(it)]); |
407 mm.set(it, it == _matching[_graph->aNode(it)]); |
376 } |
408 } |
377 return matching_size; |
409 return _size; |
378 } |
410 } |
379 |
411 |
380 ///Gives back the matching in an ANodeMap. |
412 ///Gives back the matching in an ANodeMap. |
381 |
413 |
382 ///Gives back the matching in an ANodeMap. The parameter should |
414 ///Gives back the matching in an ANodeMap. The parameter should |
383 ///be a write ANodeMap of UEdge values. |
415 ///be a write ANodeMap of UEdge values. |
384 ///\return The number of the matching edges. |
416 ///\return The number of the matching edges. |
385 template<class MatchingMap> |
417 template<class MatchingMap> |
386 int aMatching(MatchingMap& mm) const { |
418 int aMatching(MatchingMap& mm) const { |
387 for (ANodeIt it(*graph); it != INVALID; ++it) { |
419 for (ANodeIt it(*_graph); it != INVALID; ++it) { |
388 mm.set(it, anode_matching[it]); |
420 mm.set(it, _matching[it]); |
389 } |
421 } |
390 return matching_size; |
422 return _size; |
391 } |
423 } |
392 |
424 |
393 ///Gives back the matching in a BNodeMap. |
425 ///Gives back the matching in a BNodeMap. |
394 |
426 |
395 ///Gives back the matching in a BNodeMap. The parameter should |
427 ///Gives back the matching in a BNodeMap. The parameter should |
396 ///be a write BNodeMap of UEdge values. |
428 ///be a write BNodeMap of UEdge values. |
397 ///\return The number of the matching edges. |
429 ///\return The number of the matching edges. |
398 template<class MatchingMap> |
430 template<class MatchingMap> |
399 int bMatching(MatchingMap& mm) const { |
431 int bMatching(MatchingMap& mm) const { |
400 for (BNodeIt it(*graph); it != INVALID; ++it) { |
432 for (BNodeIt it(*_graph); it != INVALID; ++it) { |
401 mm.set(it, bnode_matching[it]); |
433 mm.set(it, _rmatching[it]); |
402 } |
434 } |
403 return matching_size; |
435 return _size; |
404 } |
|
405 |
|
406 /// \brief Return true if the given uedge is in the matching. |
|
407 /// |
|
408 /// It returns true if the given uedge is in the matching. |
|
409 bool matchingEdge(const UEdge& edge) const { |
|
410 return anode_matching[graph->aNode(edge)] == edge; |
|
411 } |
|
412 |
|
413 /// \brief Returns the matching edge from the node. |
|
414 /// |
|
415 /// Returns the matching edge from the node. If there is not such |
|
416 /// edge it gives back \c INVALID. |
|
417 UEdge matchingEdge(const Node& node) const { |
|
418 if (graph->aNode(node)) { |
|
419 return anode_matching[node]; |
|
420 } else { |
|
421 return bnode_matching[node]; |
|
422 } |
|
423 } |
|
424 |
|
425 /// \brief Gives back the number of the matching edges. |
|
426 /// |
|
427 /// Gives back the number of the matching edges. |
|
428 int matchingSize() const { |
|
429 return matching_size; |
|
430 } |
436 } |
431 |
437 |
432 /// \brief Returns a minimum covering of the nodes. |
438 /// \brief Returns a minimum covering of the nodes. |
433 /// |
439 /// |
434 /// The minimum covering set problem is the dual solution of the |
440 /// The minimum covering set problem is the dual solution of the |
436 /// problem what is proof of the optimality of the matching. |
442 /// problem what is proof of the optimality of the matching. |
437 /// \return The size of the cover set. |
443 /// \return The size of the cover set. |
438 template <typename CoverMap> |
444 template <typename CoverMap> |
439 int coverSet(CoverMap& covering) const { |
445 int coverSet(CoverMap& covering) const { |
440 |
446 |
441 typename Graph::template ANodeMap<bool> areached(*graph, false); |
|
442 typename Graph::template BNodeMap<bool> breached(*graph, false); |
|
443 |
|
444 std::vector<Node> queue; |
|
445 for (ANodeIt it(*graph); it != INVALID; ++it) { |
|
446 if (anode_matching[it] == INVALID) { |
|
447 queue.push_back(it); |
|
448 } |
|
449 } |
|
450 |
|
451 while (!queue.empty()) { |
|
452 std::vector<Node> newqueue; |
|
453 for (int i = 0; i < int(queue.size()); ++i) { |
|
454 Node anode = queue[i]; |
|
455 for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) { |
|
456 Node bnode = graph->bNode(jt); |
|
457 if (breached[bnode]) continue; |
|
458 breached[bnode] = true; |
|
459 if (bnode_matching[bnode] != INVALID) { |
|
460 Node newanode = graph->aNode(bnode_matching[bnode]); |
|
461 if (!areached[newanode]) { |
|
462 areached[newanode] = true; |
|
463 newqueue.push_back(newanode); |
|
464 } |
|
465 } |
|
466 } |
|
467 } |
|
468 queue.swap(newqueue); |
|
469 } |
|
470 |
|
471 int size = 0; |
447 int size = 0; |
472 for (ANodeIt it(*graph); it != INVALID; ++it) { |
448 for (ANodeIt it(*_graph); it != INVALID; ++it) { |
473 covering.set(it, !areached[it] && anode_matching[it] != INVALID); |
449 bool cn = _matching[it] != INVALID && |
474 if (!areached[it] && anode_matching[it] != INVALID) { |
450 _reached[_graph->bNode(_matching[it])] == _phase; |
475 ++size; |
451 covering.set(it, cn); |
476 } |
452 if (cn) ++size; |
477 } |
453 } |
478 for (BNodeIt it(*graph); it != INVALID; ++it) { |
454 for (BNodeIt it(*_graph); it != INVALID; ++it) { |
479 covering.set(it, breached[it]); |
455 bool cn = _reached[it] != _phase; |
480 if (breached[it]) { |
456 covering.set(it, cn); |
481 ++size; |
457 if (cn) ++size; |
482 } |
|
483 } |
458 } |
484 return size; |
459 return size; |
485 } |
460 } |
486 |
461 |
487 /// \brief Gives back a barrier on the A-nodes |
462 /// \brief Gives back a barrier on the A-nodes |
488 |
463 /// |
489 /// The barrier is s subset of the nodes on the same side of the |
464 /// The barrier is s subset of the nodes on the same side of the |
490 /// graph, which size minus its neighbours is exactly the |
465 /// graph, which size minus its neighbours is exactly the |
491 /// unmatched nodes on the A-side. |
466 /// unmatched nodes on the A-side. |
492 /// \retval barrier A WriteMap on the ANodes with bool value. |
467 /// \retval barrier A WriteMap on the ANodes with bool value. |
493 template <typename BarrierMap> |
468 template <typename BarrierMap> |
494 void aBarrier(BarrierMap& barrier) const { |
469 void aBarrier(BarrierMap& barrier) const { |
495 |
470 |
496 typename Graph::template ANodeMap<bool> areached(*graph, false); |
471 for (ANodeIt it(*_graph); it != INVALID; ++it) { |
497 typename Graph::template BNodeMap<bool> breached(*graph, false); |
472 barrier.set(it, _matching[it] == INVALID || |
498 |
473 _reached[_graph->bNode(_matching[it])] != _phase); |
499 std::vector<Node> queue; |
|
500 for (ANodeIt it(*graph); it != INVALID; ++it) { |
|
501 if (anode_matching[it] == INVALID) { |
|
502 queue.push_back(it); |
|
503 } |
|
504 } |
|
505 |
|
506 while (!queue.empty()) { |
|
507 std::vector<Node> newqueue; |
|
508 for (int i = 0; i < int(queue.size()); ++i) { |
|
509 Node anode = queue[i]; |
|
510 for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) { |
|
511 Node bnode = graph->bNode(jt); |
|
512 if (breached[bnode]) continue; |
|
513 breached[bnode] = true; |
|
514 if (bnode_matching[bnode] != INVALID) { |
|
515 Node newanode = graph->aNode(bnode_matching[bnode]); |
|
516 if (!areached[newanode]) { |
|
517 areached[newanode] = true; |
|
518 newqueue.push_back(newanode); |
|
519 } |
|
520 } |
|
521 } |
|
522 } |
|
523 queue.swap(newqueue); |
|
524 } |
|
525 |
|
526 for (ANodeIt it(*graph); it != INVALID; ++it) { |
|
527 barrier.set(it, areached[it] || anode_matching[it] == INVALID); |
|
528 } |
474 } |
529 } |
475 } |
530 |
476 |
531 /// \brief Gives back a barrier on the B-nodes |
477 /// \brief Gives back a barrier on the B-nodes |
532 |
478 /// |
533 /// The barrier is s subset of the nodes on the same side of the |
479 /// The barrier is s subset of the nodes on the same side of the |
534 /// graph, which size minus its neighbours is exactly the |
480 /// graph, which size minus its neighbours is exactly the |
535 /// unmatched nodes on the B-side. |
481 /// unmatched nodes on the B-side. |
536 /// \retval barrier A WriteMap on the BNodes with bool value. |
482 /// \retval barrier A WriteMap on the BNodes with bool value. |
537 template <typename BarrierMap> |
483 template <typename BarrierMap> |
538 void bBarrier(BarrierMap& barrier) const { |
484 void bBarrier(BarrierMap& barrier) const { |
539 |
485 |
540 typename Graph::template ANodeMap<bool> areached(*graph, false); |
486 for (BNodeIt it(*_graph); it != INVALID; ++it) { |
541 typename Graph::template BNodeMap<bool> breached(*graph, false); |
487 barrier.set(it, _reached[it] == _phase); |
542 |
488 } |
543 std::vector<Node> queue; |
489 } |
544 for (ANodeIt it(*graph); it != INVALID; ++it) { |
490 |
545 if (anode_matching[it] == INVALID) { |
491 /// \brief Gives back the number of the matching edges. |
546 queue.push_back(it); |
492 /// |
547 } |
493 /// Gives back the number of the matching edges. |
548 } |
494 int matchingSize() const { |
549 |
495 return _size; |
550 while (!queue.empty()) { |
|
551 std::vector<Node> newqueue; |
|
552 for (int i = 0; i < int(queue.size()); ++i) { |
|
553 Node anode = queue[i]; |
|
554 for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) { |
|
555 Node bnode = graph->bNode(jt); |
|
556 if (breached[bnode]) continue; |
|
557 breached[bnode] = true; |
|
558 if (bnode_matching[bnode] != INVALID) { |
|
559 Node newanode = graph->aNode(bnode_matching[bnode]); |
|
560 if (!areached[newanode]) { |
|
561 areached[newanode] = true; |
|
562 newqueue.push_back(newanode); |
|
563 } |
|
564 } |
|
565 } |
|
566 } |
|
567 queue.swap(newqueue); |
|
568 } |
|
569 |
|
570 for (BNodeIt it(*graph); it != INVALID; ++it) { |
|
571 barrier.set(it, !breached[it]); |
|
572 } |
|
573 } |
496 } |
574 |
497 |
575 /// @} |
498 /// @} |
576 |
499 |
577 private: |
500 private: |
578 |
501 |
579 ANodeMatchingMap anode_matching; |
502 typename BpUGraph::template ANodeMap<UEdge> _matching; |
580 BNodeMatchingMap bnode_matching; |
503 typename BpUGraph::template BNodeMap<UEdge> _rmatching; |
581 const Graph *graph; |
504 |
582 |
505 typename BpUGraph::template BNodeMap<int> _reached; |
583 int matching_size; |
506 |
|
507 int _phase; |
|
508 const Graph *_graph; |
|
509 |
|
510 int _size; |
584 |
511 |
585 }; |
512 }; |
586 |
513 |
587 /// \ingroup matching |
514 /// \ingroup matching |
588 /// |
515 /// |