Changeset 2466:feb7974cf4ec in lemon-0.x
- Timestamp:
- 08/28/07 15:58:54 (17 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3304
- Location:
- lemon
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bipartite_matching.h
r2463 r2466 70 70 /// 71 71 /// Constructor of the algorithm. 72 MaxBipartiteMatching(const BpUGraph& _graph)73 : anode_matching(_graph), bnode_matching(_graph), graph(&_graph) {}72 MaxBipartiteMatching(const BpUGraph& graph) 73 : _matching(graph), _rmatching(graph), _reached(graph), _graph(&graph) {} 74 74 75 75 /// \name Execution control … … 88 88 /// It initalizes the data structures and creates an empty matching. 89 89 void init() { 90 for (ANodeIt it(*graph); it != INVALID; ++it) { 91 anode_matching[it] = INVALID; 92 } 93 for (BNodeIt it(*graph); it != INVALID; ++it) { 94 bnode_matching[it] = INVALID; 95 } 96 matching_size = 0; 90 for (ANodeIt it(*_graph); it != INVALID; ++it) { 91 _matching.set(it, INVALID); 92 } 93 for (BNodeIt it(*_graph); it != INVALID; ++it) { 94 _rmatching.set(it, INVALID); 95 _reached.set(it, -1); 96 } 97 _size = 0; 98 _phase = -1; 97 99 } 98 100 … … 103 105 /// the matching than from the initial empty matching. 104 106 void greedyInit() { 105 matching_size = 0; 106 for (BNodeIt it(*graph); it != INVALID; ++it) { 107 bnode_matching[it] = INVALID; 108 } 109 for (ANodeIt it(*graph); it != INVALID; ++it) { 110 anode_matching[it] = INVALID; 111 for (IncEdgeIt jt(*graph, it); jt != INVALID; ++jt) { 112 if (bnode_matching[graph->bNode(jt)] == INVALID) { 113 anode_matching[it] = jt; 114 bnode_matching[graph->bNode(jt)] = jt; 115 ++matching_size; 107 _size = 0; 108 for (BNodeIt it(*_graph); it != INVALID; ++it) { 109 _rmatching.set(it, INVALID); 110 _reached.set(it, 0); 111 } 112 for (ANodeIt it(*_graph); it != INVALID; ++it) { 113 _matching[it] = INVALID; 114 for (IncEdgeIt jt(*_graph, it); jt != INVALID; ++jt) { 115 if (_rmatching[_graph->bNode(jt)] == INVALID) { 116 _matching.set(it, jt); 117 _rmatching.set(_graph->bNode(jt), jt); 118 _reached.set(it, -1); 119 ++_size; 116 120 break; 117 121 } 118 122 } 119 123 } 124 _phase = 0; 120 125 } 121 126 … … 125 130 template <typename MatchingMap> 126 131 void matchingInit(const MatchingMap& mm) { 127 for (ANodeIt it(*graph); it != INVALID; ++it) { 128 anode_matching[it] = INVALID; 129 } 130 for (BNodeIt it(*graph); it != INVALID; ++it) { 131 bnode_matching[it] = INVALID; 132 } 133 matching_size = 0; 134 for (UEdgeIt it(*graph); it != INVALID; ++it) { 132 for (ANodeIt it(*_graph); it != INVALID; ++it) { 133 _matching.set(it, INVALID); 134 } 135 for (BNodeIt it(*_graph); it != INVALID; ++it) { 136 _rmatching.set(it, INVALID); 137 _reached.set(it, 0); 138 } 139 _size = 0; 140 for (UEdgeIt it(*_graph); it != INVALID; ++it) { 135 141 if (mm[it]) { 136 ++matching_size; 137 anode_matching[graph->aNode(it)] = it; 138 bnode_matching[graph->bNode(it)] = it; 139 } 140 } 142 ++_size; 143 _matching.set(_graph->aNode(it), it); 144 _rmatching.set(_graph->bNode(it), it); 145 _reached.set(it, 0); 146 } 147 } 148 _phase = 0; 141 149 } 142 150 … … 146 154 /// \return %True when the given map contains really a matching. 147 155 template <typename MatchingMap> 148 void checkedMatchingInit(const MatchingMap& mm) { 149 for (ANodeIt it(*graph); it != INVALID; ++it) { 150 anode_matching[it] = INVALID; 151 } 152 for (BNodeIt it(*graph); it != INVALID; ++it) { 153 bnode_matching[it] = INVALID; 154 } 155 matching_size = 0; 156 for (UEdgeIt it(*graph); it != INVALID; ++it) { 156 bool checkedMatchingInit(const MatchingMap& mm) { 157 for (ANodeIt it(*_graph); it != INVALID; ++it) { 158 _matching.set(it, INVALID); 159 } 160 for (BNodeIt it(*_graph); it != INVALID; ++it) { 161 _rmatching.set(it, INVALID); 162 _reached.set(it, 0); 163 } 164 _size = 0; 165 for (UEdgeIt it(*_graph); it != INVALID; ++it) { 157 166 if (mm[it]) { 158 ++ matching_size;159 if ( anode_matching[graph->aNode(it)] != INVALID) {167 ++_size; 168 if (_matching[_graph->aNode(it)] != INVALID) { 160 169 return false; 161 170 } 162 anode_matching[graph->aNode(it)] = it;163 if ( bnode_matching[graph->aNode(it)] != INVALID) {171 _matching.set(_graph->aNode(it), it); 172 if (_matching[_graph->bNode(it)] != INVALID) { 164 173 return false; 165 174 } 166 bnode_matching[graph->bNode(it)] = it; 167 } 175 _matching.set(_graph->bNode(it), it); 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 205 return false; 170 206 } 171 207 208 public: 209 172 210 /// \brief An augmenting phase of the Hopcroft-Karp algorithm 173 211 /// 174 212 /// It runs an augmenting phase of the Hopcroft-Karp 175 /// algorithm. This phase finds maxim um count of edge disjoint176 /// augmenting paths and augments on these paths. The algorithm177 /// consists at most of \f$ O(\sqrt{n}) \f$ phase and one phase is178 /// \f$ O(e) \f$long.213 /// algorithm. This phase finds maximal edge disjoint augmenting 214 /// paths and augments on these paths. The algorithm consists at 215 /// most of \f$ O(\sqrt{n}) \f$ phase and one phase is \f$ O(e) 216 /// \f$ long. 179 217 bool augment() { 180 218 181 typename Graph::template ANodeMap<bool> areached(*graph, false);182 typename Graph::template BNodeMap<bool> breached(*graph, false);183 184 typename Graph::template BNodeMap<UEdge> bpred(*graph, INVALID);185 186 std::vector<Node> queue, bqueue;187 for ( ANodeIt it(*graph); it != INVALID; ++it) {188 if ( anode_matching[it] == INVALID) {219 ++_phase; 220 221 typename Graph::template BNodeMap<int> _level(*_graph, -1); 222 typename Graph::template ANodeMap<bool> _found(*_graph, false); 223 224 std::vector<Node> queue, aqueue; 225 for (BNodeIt it(*_graph); it != INVALID; ++it) { 226 if (_rmatching[it] == INVALID) { 189 227 queue.push_back(it); 190 areached[it] = true; 228 _reached.set(it, _phase); 229 _level.set(it, 0); 191 230 } 192 231 } … … 194 233 bool success = false; 195 234 235 int level = 0; 196 236 while (!success && !queue.empty()) { 197 std::vector<Node> n ewqueue;237 std::vector<Node> nqueue; 198 238 for (int i = 0; i < int(queue.size()); ++i) { 199 Node anode = queue[i]; 200 for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) { 201 Node bnode = graph->bNode(jt); 202 if (breached[bnode]) continue; 203 breached[bnode] = true; 204 bpred[bnode] = jt; 205 if (bnode_matching[bnode] == INVALID) { 206 bqueue.push_back(bnode); 239 Node bnode = queue[i]; 240 for (IncEdgeIt jt(*_graph, bnode); jt != INVALID; ++jt) { 241 Node anode = _graph->aNode(jt); 242 if (_matching[anode] == INVALID) { 243 244 if (!_found[anode]) { 245 if (_find_path(anode, level, _level)) { 246 ++_size; 247 } 248 _found.set(anode, true); 249 } 207 250 success = true; 208 251 } else { 209 Node newanode = graph->aNode(bnode_matching[bnode]); 210 if (!areached[newanode]) { 211 areached[newanode] = true; 212 newqueue.push_back(newanode); 252 Node nnode = _graph->bNode(_matching[anode]); 253 if (_reached[nnode] != _phase) { 254 _reached.set(nnode, _phase); 255 nqueue.push_back(nnode); 256 _level.set(nnode, level + 1); 213 257 } 214 258 } 215 259 } 216 260 } 217 queue.swap(newqueue); 218 } 219 220 if (success) { 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 } 261 ++level; 262 queue.swap(nqueue); 263 } 264 263 265 return success; 264 266 } 265 266 /// \brief An augmenting phase of the Ford-Fulkerson algorithm 267 /// 268 /// It runs an augmenting phase of the Ford-Fulkerson 269 /// algorithm. This phase finds only one augmenting path and 270 /// augments only on this paths. The algorithm consists at most 271 /// of \f$ O(n) \f$ simple phase and one phase is at most 272 /// \f$ O(e) \f$ long. 273 bool simpleAugment() { 274 275 typename Graph::template ANodeMap<bool> areached(*graph, false); 276 typename Graph::template BNodeMap<bool> breached(*graph, false); 277 278 typename Graph::template BNodeMap<UEdge> bpred(*graph, INVALID); 279 280 std::vector<Node> queue; 281 for (ANodeIt it(*graph); it != INVALID; ++it) { 282 if (anode_matching[it] == INVALID) { 267 private: 268 269 void _find_path_bfs(Node anode, 270 typename Graph::template ANodeMap<UEdge>& pred) { 271 while (true) { 272 UEdge uedge = pred[anode]; 273 Node bnode = _graph->bNode(uedge); 274 275 UEdge nedge = _rmatching[bnode]; 276 277 _matching.set(anode, uedge); 278 _rmatching.set(bnode, uedge); 279 280 if (nedge == INVALID) break; 281 anode = _graph->aNode(nedge); 282 } 283 } 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 300 queue.push_back(it); 284 areached[it] = true; 285 } 286 } 287 288 while (!queue.empty()) { 289 std::vector<Node> newqueue; 301 _reached.set(it, _phase); 302 } 303 } 304 305 bool success = false; 306 307 int level = 0; 308 while (!success && !queue.empty()) { 309 std::vector<Node> nqueue; 290 310 for (int i = 0; i < int(queue.size()); ++i) { 291 Node anode = queue[i]; 292 for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) { 293 Node bnode = graph->bNode(jt); 294 if (breached[bnode]) continue; 295 breached[bnode] = true; 296 bpred[bnode] = jt; 297 if (bnode_matching[bnode] == INVALID) { 298 while (bnode != INVALID) { 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; 311 Node bnode = queue[i]; 312 for (IncEdgeIt jt(*_graph, bnode); jt != INVALID; ++jt) { 313 Node anode = _graph->aNode(jt); 314 if (_matching[anode] == INVALID) { 315 _pred.set(anode, jt); 316 _find_path_bfs(anode, _pred); 317 ++_size; 318 return true; 312 319 } else { 313 Node newanode = graph->aNode(bnode_matching[bnode]); 314 if (!areached[newanode]) { 315 areached[newanode] = true; 316 newqueue.push_back(newanode); 320 Node nnode = _graph->bNode(_matching[anode]); 321 if (_reached[nnode] != _phase) { 322 _pred.set(anode, jt); 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; 325 } 333 return success; 334 } 335 336 326 337 327 338 /// \brief Starts the algorithm. … … 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 385 /// \brief Set true all matching uedge in the map. 354 386 /// … … 358 390 template <typename MatchingMap> 359 391 int quickMatching(MatchingMap& mm) const { 360 for (ANodeIt it(* graph); it != INVALID; ++it) {361 if ( anode_matching[it] != INVALID) {362 mm.set( anode_matching[it], true);363 } 364 } 365 return matching_size;392 for (ANodeIt it(*_graph); it != INVALID; ++it) { 393 if (_matching[it] != INVALID) { 394 mm.set(_matching[it], true); 395 } 396 } 397 return _size; 366 398 } 367 399 … … 372 404 template <typename MatchingMap> 373 405 int matching(MatchingMap& mm) const { 374 for (UEdgeIt it(* graph); it != INVALID; ++it) {375 mm.set(it, it == anode_matching[graph->aNode(it)]);376 } 377 return matching_size;406 for (UEdgeIt it(*_graph); it != INVALID; ++it) { 407 mm.set(it, it == _matching[_graph->aNode(it)]); 408 } 409 return _size; 378 410 } 379 411 … … 385 417 template<class MatchingMap> 386 418 int aMatching(MatchingMap& mm) const { 387 for (ANodeIt it(* graph); it != INVALID; ++it) {388 mm.set(it, anode_matching[it]);389 } 390 return matching_size;419 for (ANodeIt it(*_graph); it != INVALID; ++it) { 420 mm.set(it, _matching[it]); 421 } 422 return _size; 391 423 } 392 424 … … 398 430 template<class MatchingMap> 399 431 int bMatching(MatchingMap& mm) const { 400 for (BNodeIt it(*graph); it != INVALID; ++it) { 401 mm.set(it, bnode_matching[it]); 402 } 403 return matching_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; 432 for (BNodeIt it(*_graph); it != INVALID; ++it) { 433 mm.set(it, _rmatching[it]); 434 } 435 return _size; 430 436 } 431 437 … … 439 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 447 int size = 0; 472 for (ANodeIt it(*graph); it != INVALID; ++it) { 473 covering.set(it, !areached[it] && anode_matching[it] != INVALID); 474 if (!areached[it] && anode_matching[it] != INVALID) { 475 ++size; 476 } 477 } 478 for (BNodeIt it(*graph); it != INVALID; ++it) { 479 covering.set(it, breached[it]); 480 if (breached[it]) { 481 ++size; 482 } 448 for (ANodeIt it(*_graph); it != INVALID; ++it) { 449 bool cn = _matching[it] != INVALID && 450 _reached[_graph->bNode(_matching[it])] == _phase; 451 covering.set(it, cn); 452 if (cn) ++size; 453 } 454 for (BNodeIt it(*_graph); it != INVALID; ++it) { 455 bool cn = _reached[it] != _phase; 456 covering.set(it, cn); 457 if (cn) ++size; 483 458 } 484 459 return size; … … 486 461 487 462 /// \brief Gives back a barrier on the A-nodes 488 463 /// 489 464 /// The barrier is s subset of the nodes on the same side of the 490 465 /// graph, which size minus its neighbours is exactly the … … 494 469 void aBarrier(BarrierMap& barrier) const { 495 470 496 typename Graph::template ANodeMap<bool> areached(*graph, false); 497 typename Graph::template BNodeMap<bool> breached(*graph, false); 498 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); 471 for (ANodeIt it(*_graph); it != INVALID; ++it) { 472 barrier.set(it, _matching[it] == INVALID || 473 _reached[_graph->bNode(_matching[it])] != _phase); 528 474 } 529 475 } 530 476 531 477 /// \brief Gives back a barrier on the B-nodes 532 478 /// 533 479 /// The barrier is s subset of the nodes on the same side of the 534 480 /// graph, which size minus its neighbours is exactly the … … 538 484 void bBarrier(BarrierMap& barrier) const { 539 485 540 typename Graph::template ANodeMap<bool> areached(*graph, false); 541 typename Graph::template BNodeMap<bool> breached(*graph, false); 542 543 std::vector<Node> queue; 544 for (ANodeIt it(*graph); it != INVALID; ++it) { 545 if (anode_matching[it] == INVALID) { 546 queue.push_back(it); 547 } 548 } 549 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 } 486 for (BNodeIt it(*_graph); it != INVALID; ++it) { 487 barrier.set(it, _reached[it] == _phase); 488 } 489 } 490 491 /// \brief Gives back the number of the matching edges. 492 /// 493 /// Gives back the number of the matching edges. 494 int matchingSize() const { 495 return _size; 573 496 } 574 497 … … 577 500 private: 578 501 579 ANodeMatchingMap anode_matching; 580 BNodeMatchingMap bnode_matching; 581 const Graph *graph; 582 583 int matching_size; 502 typename BpUGraph::template ANodeMap<UEdge> _matching; 503 typename BpUGraph::template BNodeMap<UEdge> _rmatching; 504 505 typename BpUGraph::template BNodeMap<int> _reached; 506 507 int _phase; 508 const Graph *_graph; 509 510 int _size; 584 511 585 512 }; -
lemon/pr_bipartite_matching.h
r2463 r2466 60 60 public: 61 61 62 /// Constructor 63 64 /// Constructor 65 /// 62 66 PrBipartiteMatching(const Graph &g) : 63 67 _g(g), … … 196 200 } 197 201 198 _matching_size = _node_num; 199 for(ANodeIt n(_g);n!=INVALID;++n) 200 if(_matching[n]==INVALID) _matching_size--; 201 else if (_cov[_g.bNode(_matching[n])]>1) { 202 for(ANodeIt n(_g);n!=INVALID;++n) { 203 if (_matching[n]==INVALID)continue; 204 if (_cov[_g.bNode(_matching[n])]>1) { 202 205 _cov[_g.bNode(_matching[n])]--; 203 _matching_size--;204 206 _matching[n]=INVALID; 205 } 207 } else { 208 ++_matching_size; 209 } 210 } 206 211 } 207 212 … … 262 267 return false; 263 268 } 269 _matching_size = _node_num; 264 270 return true; 265 271 }
Note: See TracChangeset
for help on using the changeset viewer.