27 #include <iostream> |
27 #include <iostream> |
28 |
28 |
29 ///\ingroup matching |
29 ///\ingroup matching |
30 ///\file |
30 ///\file |
31 ///\brief Maximum matching algorithms in bipartite graphs. |
31 ///\brief Maximum matching algorithms in bipartite graphs. |
|
32 /// |
|
33 ///\note The pr_bipartite_matching.h file also contains algorithms to |
|
34 ///solve maximum cardinality bipartite matching problems. |
32 |
35 |
33 namespace lemon { |
36 namespace lemon { |
34 |
37 |
35 /// \ingroup matching |
38 /// \ingroup matching |
36 /// |
39 /// |
37 /// \brief Bipartite Max Cardinality Matching algorithm |
40 /// \brief Bipartite Max Cardinality Matching algorithm |
38 /// |
41 /// |
39 /// Bipartite Max Cardinality Matching algorithm. This class implements |
42 /// Bipartite Max Cardinality Matching algorithm. This class implements |
40 /// the Hopcroft-Karp algorithm which has \f$ O(e\sqrt{n}) \f$ time |
43 /// the Hopcroft-Karp algorithm which has \f$ O(e\sqrt{n}) \f$ time |
41 /// complexity. |
44 /// complexity. |
|
45 /// |
|
46 /// \note In several cases the push-relabel based algorithms have |
|
47 /// better runtime performance than the augmenting path based ones. |
|
48 /// |
|
49 /// \see PrBipartiteMatching |
42 template <typename BpUGraph> |
50 template <typename BpUGraph> |
43 class MaxBipartiteMatching { |
51 class MaxBipartiteMatching { |
44 protected: |
52 protected: |
45 |
53 |
46 typedef BpUGraph Graph; |
54 typedef BpUGraph Graph; |
340 /// Before the use of these functions, |
348 /// Before the use of these functions, |
341 /// either run() or start() must be called. |
349 /// either run() or start() must be called. |
342 |
350 |
343 ///@{ |
351 ///@{ |
344 |
352 |
345 /// \brief Returns an minimum covering of the nodes. |
353 /// \brief Set true all matching uedge in the map. |
|
354 /// |
|
355 /// Set true all matching uedge in the map. It does not change the |
|
356 /// value mapped to the other uedges. |
|
357 /// \return The number of the matching edges. |
|
358 template <typename MatchingMap> |
|
359 int quickMatching(MatchingMap& mm) const { |
|
360 for (ANodeIt it(*graph); it != INVALID; ++it) { |
|
361 if (anode_matching[it] != INVALID) { |
|
362 mm[anode_matching[it]] = true; |
|
363 } |
|
364 } |
|
365 return matching_size; |
|
366 } |
|
367 |
|
368 /// \brief Set true all matching uedge in the map and the others to false. |
|
369 /// |
|
370 /// Set true all matching uedge in the map and the others to false. |
|
371 /// \return The number of the matching edges. |
|
372 template <typename MatchingMap> |
|
373 int matching(MatchingMap& mm) const { |
|
374 for (UEdgeIt it(*graph); it != INVALID; ++it) { |
|
375 mm[it] = it == anode_matching[graph->aNode(it)]; |
|
376 } |
|
377 return matching_size; |
|
378 } |
|
379 |
|
380 |
|
381 /// \brief Return true if the given uedge is in the matching. |
|
382 /// |
|
383 /// It returns true if the given uedge is in the matching. |
|
384 bool matchingEdge(const UEdge& edge) const { |
|
385 return anode_matching[graph->aNode(edge)] == edge; |
|
386 } |
|
387 |
|
388 /// \brief Returns the matching edge from the node. |
|
389 /// |
|
390 /// Returns the matching edge from the node. If there is not such |
|
391 /// edge it gives back \c INVALID. |
|
392 UEdge matchingEdge(const Node& node) const { |
|
393 if (graph->aNode(node)) { |
|
394 return anode_matching[node]; |
|
395 } else { |
|
396 return bnode_matching[node]; |
|
397 } |
|
398 } |
|
399 |
|
400 /// \brief Gives back the number of the matching edges. |
|
401 /// |
|
402 /// Gives back the number of the matching edges. |
|
403 int matchingSize() const { |
|
404 return matching_size; |
|
405 } |
|
406 |
|
407 /// \brief Returns a minimum covering of the nodes. |
346 /// |
408 /// |
347 /// The minimum covering set problem is the dual solution of the |
409 /// The minimum covering set problem is the dual solution of the |
348 /// maximum bipartite matching. It provides an solution for this |
410 /// maximum bipartite matching. It provides a solution for this |
349 /// problem what is proof of the optimality of the matching. |
411 /// problem what is proof of the optimality of the matching. |
350 /// \return The size of the cover set. |
412 /// \return The size of the cover set. |
351 template <typename CoverMap> |
413 template <typename CoverMap> |
352 int coverSet(CoverMap& covering) const { |
414 int coverSet(CoverMap& covering) const { |
353 |
415 |
395 } |
457 } |
396 } |
458 } |
397 return size; |
459 return size; |
398 } |
460 } |
399 |
461 |
400 /// \brief Set true all matching uedge in the map. |
462 /// \brief Gives back a barrier on the A-nodes |
401 /// |
463 |
402 /// Set true all matching uedge in the map. It does not change the |
464 /// The barrier is s subset of the nodes on the same side of the |
403 /// value mapped to the other uedges. |
465 /// graph, which size minus its neighbours is exactly the |
404 /// \return The number of the matching edges. |
466 /// unmatched nodes on the A-side. |
405 template <typename MatchingMap> |
467 /// \retval barrier A WriteMap on the ANodes with bool value. |
406 int quickMatching(MatchingMap& mm) const { |
468 template <typename BarrierMap> |
407 for (ANodeIt it(*graph); it != INVALID; ++it) { |
469 void aBarrier(BarrierMap& barrier) const { |
408 if (anode_matching[it] != INVALID) { |
470 |
409 mm[anode_matching[it]] = true; |
471 typename Graph::template ANodeMap<bool> areached(*graph, false); |
410 } |
472 typename Graph::template BNodeMap<bool> breached(*graph, false); |
411 } |
473 |
412 return matching_size; |
474 std::vector<Node> queue; |
413 } |
475 for (ANodeIt it(*graph); it != INVALID; ++it) { |
414 |
476 if (anode_matching[it] == INVALID) { |
415 /// \brief Set true all matching uedge in the map and the others to false. |
477 queue.push_back(it); |
416 /// |
478 } |
417 /// Set true all matching uedge in the map and the others to false. |
479 } |
418 /// \return The number of the matching edges. |
480 |
419 template <typename MatchingMap> |
481 while (!queue.empty()) { |
420 int matching(MatchingMap& mm) const { |
482 std::vector<Node> newqueue; |
421 for (UEdgeIt it(*graph); it != INVALID; ++it) { |
483 for (int i = 0; i < int(queue.size()); ++i) { |
422 mm[it] = it == anode_matching[graph->aNode(it)]; |
484 Node anode = queue[i]; |
423 } |
485 for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) { |
424 return matching_size; |
486 Node bnode = graph->bNode(jt); |
425 } |
487 if (breached[bnode]) continue; |
426 |
488 breached[bnode] = true; |
427 |
489 if (bnode_matching[bnode] != INVALID) { |
428 /// \brief Return true if the given uedge is in the matching. |
490 Node newanode = graph->aNode(bnode_matching[bnode]); |
429 /// |
491 if (!areached[newanode]) { |
430 /// It returns true if the given uedge is in the matching. |
492 areached[newanode] = true; |
431 bool matchingEdge(const UEdge& edge) const { |
493 newqueue.push_back(newanode); |
432 return anode_matching[graph->aNode(edge)] == edge; |
494 } |
433 } |
495 } |
434 |
496 } |
435 /// \brief Returns the matching edge from the node. |
497 } |
436 /// |
498 queue.swap(newqueue); |
437 /// Returns the matching edge from the node. If there is not such |
499 } |
438 /// edge it gives back \c INVALID. |
500 |
439 UEdge matchingEdge(const Node& node) const { |
501 for (ANodeIt it(*graph); it != INVALID; ++it) { |
440 if (graph->aNode(node)) { |
502 barrier[it] = areached[it] || anode_matching[it] == INVALID; |
441 return anode_matching[node]; |
503 } |
442 } else { |
504 } |
443 return bnode_matching[node]; |
505 |
444 } |
506 /// \brief Gives back a barrier on the B-nodes |
445 } |
507 |
446 |
508 /// The barrier is s subset of the nodes on the same side of the |
447 /// \brief Gives back the number of the matching edges. |
509 /// graph, which size minus its neighbours is exactly the |
448 /// |
510 /// unmatched nodes on the B-side. |
449 /// Gives back the number of the matching edges. |
511 /// \retval barrier A WriteMap on the BNodes with bool value. |
450 int matchingSize() const { |
512 template <typename BarrierMap> |
451 return matching_size; |
513 void bBarrier(BarrierMap& barrier) const { |
|
514 |
|
515 typename Graph::template ANodeMap<bool> areached(*graph, false); |
|
516 typename Graph::template BNodeMap<bool> breached(*graph, false); |
|
517 |
|
518 std::vector<Node> queue; |
|
519 for (ANodeIt it(*graph); it != INVALID; ++it) { |
|
520 if (anode_matching[it] == INVALID) { |
|
521 queue.push_back(it); |
|
522 } |
|
523 } |
|
524 |
|
525 while (!queue.empty()) { |
|
526 std::vector<Node> newqueue; |
|
527 for (int i = 0; i < int(queue.size()); ++i) { |
|
528 Node anode = queue[i]; |
|
529 for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) { |
|
530 Node bnode = graph->bNode(jt); |
|
531 if (breached[bnode]) continue; |
|
532 breached[bnode] = true; |
|
533 if (bnode_matching[bnode] != INVALID) { |
|
534 Node newanode = graph->aNode(bnode_matching[bnode]); |
|
535 if (!areached[newanode]) { |
|
536 areached[newanode] = true; |
|
537 newqueue.push_back(newanode); |
|
538 } |
|
539 } |
|
540 } |
|
541 } |
|
542 queue.swap(newqueue); |
|
543 } |
|
544 |
|
545 for (BNodeIt it(*graph); it != INVALID; ++it) { |
|
546 barrier[it] = !breached[it]; |
|
547 } |
452 } |
548 } |
453 |
549 |
454 /// @} |
550 /// @} |
455 |
551 |
456 private: |
552 private: |