347 /// The minimum covering set problem is the dual solution of the |
347 /// The minimum covering set problem is the dual solution of the |
348 /// maximum bipartite matching. It provides an solution for this |
348 /// maximum bipartite matching. It provides an solution for this |
349 /// problem what is proof of the optimality of the matching. |
349 /// problem what is proof of the optimality of the matching. |
350 /// \return The size of the cover set. |
350 /// \return The size of the cover set. |
351 template <typename CoverMap> |
351 template <typename CoverMap> |
352 int coverSet(CoverMap& covering) { |
352 int coverSet(CoverMap& covering) const { |
353 |
353 |
354 typename Graph::template ANodeMap<bool> areached(*graph, false); |
354 typename Graph::template ANodeMap<bool> areached(*graph, false); |
355 typename Graph::template BNodeMap<bool> breached(*graph, false); |
355 typename Graph::template BNodeMap<bool> breached(*graph, false); |
356 |
356 |
357 std::vector<Node> queue; |
357 std::vector<Node> queue; |
401 /// |
401 /// |
402 /// Set true all matching uedge in the map. It does not change the |
402 /// Set true all matching uedge in the map. It does not change the |
403 /// value mapped to the other uedges. |
403 /// value mapped to the other uedges. |
404 /// \return The number of the matching edges. |
404 /// \return The number of the matching edges. |
405 template <typename MatchingMap> |
405 template <typename MatchingMap> |
406 int quickMatching(MatchingMap& matching) { |
406 int quickMatching(MatchingMap& matching) const { |
407 for (ANodeIt it(*graph); it != INVALID; ++it) { |
407 for (ANodeIt it(*graph); it != INVALID; ++it) { |
408 if (anode_matching[it] != INVALID) { |
408 if (anode_matching[it] != INVALID) { |
409 matching[anode_matching[it]] = true; |
409 matching[anode_matching[it]] = true; |
410 } |
410 } |
411 } |
411 } |
415 /// \brief Set true all matching uedge in the map and the others to false. |
415 /// \brief Set true all matching uedge in the map and the others to false. |
416 /// |
416 /// |
417 /// Set true all matching uedge in the map and the others to false. |
417 /// Set true all matching uedge in the map and the others to false. |
418 /// \return The number of the matching edges. |
418 /// \return The number of the matching edges. |
419 template <typename MatchingMap> |
419 template <typename MatchingMap> |
420 int matching(MatchingMap& matching) { |
420 int matching(MatchingMap& matching) const { |
421 for (UEdgeIt it(*graph); it != INVALID; ++it) { |
421 for (UEdgeIt it(*graph); it != INVALID; ++it) { |
422 matching[it] = it == anode_matching[graph->aNode(it)]; |
422 matching[it] = it == anode_matching[graph->aNode(it)]; |
423 } |
423 } |
424 return matching_size; |
424 return matching_size; |
425 } |
425 } |
426 |
426 |
427 |
427 |
428 /// \brief Return true if the given uedge is in the matching. |
428 /// \brief Return true if the given uedge is in the matching. |
429 /// |
429 /// |
430 /// It returns true if the given uedge is in the matching. |
430 /// It returns true if the given uedge is in the matching. |
431 bool matchingEdge(const UEdge& edge) { |
431 bool matchingEdge(const UEdge& edge) const { |
432 return anode_matching[graph->aNode(edge)] == edge; |
432 return anode_matching[graph->aNode(edge)] == edge; |
433 } |
433 } |
434 |
434 |
435 /// \brief Returns the matching edge from the node. |
435 /// \brief Returns the matching edge from the node. |
436 /// |
436 /// |
437 /// Returns the matching edge from the node. If there is not such |
437 /// Returns the matching edge from the node. If there is not such |
438 /// edge it gives back \c INVALID. |
438 /// edge it gives back \c INVALID. |
439 UEdge matchingEdge(const Node& node) { |
439 UEdge matchingEdge(const Node& node) const { |
440 if (graph->aNode(node)) { |
440 if (graph->aNode(node)) { |
441 return anode_matching[node]; |
441 return anode_matching[node]; |
442 } else { |
442 } else { |
443 return bnode_matching[node]; |
443 return bnode_matching[node]; |
444 } |
444 } |
460 const Graph *graph; |
460 const Graph *graph; |
461 |
461 |
462 int matching_size; |
462 int matching_size; |
463 |
463 |
464 }; |
464 }; |
|
465 |
|
466 /// \ingroup matching |
|
467 /// |
|
468 /// \brief Maximum cardinality bipartite matching |
|
469 /// |
|
470 /// This function calculates the maximum cardinality matching |
|
471 /// in a bipartite graph. It gives back the matching in an undirected |
|
472 /// edge map. |
|
473 /// |
|
474 /// \param graph The bipartite graph. |
|
475 /// \retval matching The undirected edge map which will be set to |
|
476 /// the matching. |
|
477 /// \return The size of the matching. |
|
478 template <typename BpUGraph, typename MatchingMap> |
|
479 int maxBipartiteMatching(const BpUGraph& graph, MatchingMap& matching) { |
|
480 MaxBipartiteMatching<BpUGraph> bpmatching(graph); |
|
481 bpmatching.run(); |
|
482 bpmatching.matching(matching); |
|
483 return bpmatching.matchingSize(); |
|
484 } |
465 |
485 |
466 /// \brief Default traits class for weighted bipartite matching algoritms. |
486 /// \brief Default traits class for weighted bipartite matching algoritms. |
467 /// |
487 /// |
468 /// Default traits class for weighted bipartite matching algoritms. |
488 /// Default traits class for weighted bipartite matching algoritms. |
469 /// \param _BpUGraph The bipartite undirected graph type. |
489 /// \param _BpUGraph The bipartite undirected graph type. |
699 } |
719 } |
700 for (BNodeIt it(*graph); it != INVALID; ++it) { |
720 for (BNodeIt it(*graph); it != INVALID; ++it) { |
701 bnode_matching[it] = INVALID; |
721 bnode_matching[it] = INVALID; |
702 bnode_potential[it] = 0; |
722 bnode_potential[it] = 0; |
703 for (IncEdgeIt jt(*graph, it); jt != INVALID; ++jt) { |
723 for (IncEdgeIt jt(*graph, it); jt != INVALID; ++jt) { |
704 if (-(*weight)[jt] <= bnode_potential[it]) { |
724 if ((*weight)[jt] > bnode_potential[it]) { |
705 bnode_potential[it] = -(*weight)[jt]; |
725 bnode_potential[it] = (*weight)[jt]; |
706 } |
726 } |
707 } |
727 } |
708 } |
728 } |
709 matching_value = 0; |
729 matching_value = 0; |
710 matching_size = 0; |
730 matching_size = 0; |
751 Value avalue = _heap->prio(); |
771 Value avalue = _heap->prio(); |
752 _heap->pop(); |
772 _heap->pop(); |
753 for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) { |
773 for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) { |
754 if (jt == anode_matching[anode]) continue; |
774 if (jt == anode_matching[anode]) continue; |
755 Node bnode = graph->bNode(jt); |
775 Node bnode = graph->bNode(jt); |
756 Value bvalue = avalue + anode_potential[anode] - |
776 Value bvalue = avalue - (*weight)[jt] + |
757 bnode_potential[bnode] - (*weight)[jt]; |
777 anode_potential[anode] + bnode_potential[bnode]; |
758 if (bpred[bnode] == INVALID || bvalue < bdist[bnode]) { |
778 if (bpred[bnode] == INVALID || bvalue < bdist[bnode]) { |
759 bdist[bnode] = bvalue; |
779 bdist[bnode] = bvalue; |
760 bpred[bnode] = jt; |
780 bpred[bnode] = jt; |
761 } |
781 } |
762 if (bvalue > bdistMax) { |
782 if (bvalue > bdistMax) { |
793 matching_value += bestValue; |
813 matching_value += bestValue; |
794 ++matching_size; |
814 ++matching_size; |
795 |
815 |
796 for (BNodeIt it(*graph); it != INVALID; ++it) { |
816 for (BNodeIt it(*graph); it != INVALID; ++it) { |
797 if (bpred[it] != INVALID) { |
817 if (bpred[it] != INVALID) { |
798 bnode_potential[it] += bdist[it]; |
818 bnode_potential[it] -= bdist[it]; |
799 } else { |
819 } else { |
800 bnode_potential[it] += bdistMax; |
820 bnode_potential[it] -= bdistMax; |
801 } |
821 } |
802 } |
822 } |
803 for (ANodeIt it(*graph); it != INVALID; ++it) { |
823 for (ANodeIt it(*graph); it != INVALID; ++it) { |
804 if (anode_matching[it] != INVALID) { |
824 if (anode_matching[it] != INVALID) { |
805 Node bnode = graph->bNode(anode_matching[it]); |
825 Node bnode = graph->bNode(anode_matching[it]); |
862 |
882 |
863 ///@{ |
883 ///@{ |
864 |
884 |
865 /// \brief Gives back the potential in the NodeMap |
885 /// \brief Gives back the potential in the NodeMap |
866 /// |
886 /// |
867 /// Gives back the potential in the NodeMap. The potential |
887 /// Gives back the potential in the NodeMap. The matching is optimal |
868 /// is feasible if \f$ \pi(a) - \pi(b) - w(ab) = 0 \f$ for |
888 /// with the current number of edges if \f$ \pi(a) + \pi(b) - w(ab) = 0 \f$ |
869 /// each matching edges and \f$ \pi(a) - \pi(b) - w(ab) \ge 0 \f$ |
889 /// for each matching edges and \f$ \pi(a) + \pi(b) - w(ab) \ge 0 \f$ |
870 /// for each edges. |
890 /// for each edges. |
871 template <typename PotentialMap> |
891 template <typename PotentialMap> |
872 void potential(PotentialMap& potential) { |
892 void potential(PotentialMap& potential) const { |
873 for (ANodeIt it(*graph); it != INVALID; ++it) { |
893 for (ANodeIt it(*graph); it != INVALID; ++it) { |
874 potential[it] = anode_potential[it]; |
894 potential[it] = anode_potential[it]; |
875 } |
895 } |
876 for (BNodeIt it(*graph); it != INVALID; ++it) { |
896 for (BNodeIt it(*graph); it != INVALID; ++it) { |
877 potential[it] = bnode_potential[it]; |
897 potential[it] = bnode_potential[it]; |
882 /// |
902 /// |
883 /// Set true all matching uedge in the map. It does not change the |
903 /// Set true all matching uedge in the map. It does not change the |
884 /// value mapped to the other uedges. |
904 /// value mapped to the other uedges. |
885 /// \return The number of the matching edges. |
905 /// \return The number of the matching edges. |
886 template <typename MatchingMap> |
906 template <typename MatchingMap> |
887 int quickMatching(MatchingMap& matching) { |
907 int quickMatching(MatchingMap& matching) const { |
888 for (ANodeIt it(*graph); it != INVALID; ++it) { |
908 for (ANodeIt it(*graph); it != INVALID; ++it) { |
889 if (anode_matching[it] != INVALID) { |
909 if (anode_matching[it] != INVALID) { |
890 matching[anode_matching[it]] = true; |
910 matching[anode_matching[it]] = true; |
891 } |
911 } |
892 } |
912 } |
896 /// \brief Set true all matching uedge in the map and the others to false. |
916 /// \brief Set true all matching uedge in the map and the others to false. |
897 /// |
917 /// |
898 /// Set true all matching uedge in the map and the others to false. |
918 /// Set true all matching uedge in the map and the others to false. |
899 /// \return The number of the matching edges. |
919 /// \return The number of the matching edges. |
900 template <typename MatchingMap> |
920 template <typename MatchingMap> |
901 int matching(MatchingMap& matching) { |
921 int matching(MatchingMap& matching) const { |
902 for (UEdgeIt it(*graph); it != INVALID; ++it) { |
922 for (UEdgeIt it(*graph); it != INVALID; ++it) { |
903 matching[it] = it == anode_matching[graph->aNode(it)]; |
923 matching[it] = it == anode_matching[graph->aNode(it)]; |
904 } |
924 } |
905 return matching_size; |
925 return matching_size; |
906 } |
926 } |
907 |
927 |
908 |
928 |
909 /// \brief Return true if the given uedge is in the matching. |
929 /// \brief Return true if the given uedge is in the matching. |
910 /// |
930 /// |
911 /// It returns true if the given uedge is in the matching. |
931 /// It returns true if the given uedge is in the matching. |
912 bool matchingEdge(const UEdge& edge) { |
932 bool matchingEdge(const UEdge& edge) const { |
913 return anode_matching[graph->aNode(edge)] == edge; |
933 return anode_matching[graph->aNode(edge)] == edge; |
914 } |
934 } |
915 |
935 |
916 /// \brief Returns the matching edge from the node. |
936 /// \brief Returns the matching edge from the node. |
917 /// |
937 /// |
918 /// Returns the matching edge from the node. If there is not such |
938 /// Returns the matching edge from the node. If there is not such |
919 /// edge it gives back \c INVALID. |
939 /// edge it gives back \c INVALID. |
920 UEdge matchingEdge(const Node& node) { |
940 UEdge matchingEdge(const Node& node) const { |
921 if (graph->aNode(node)) { |
941 if (graph->aNode(node)) { |
922 return anode_matching[node]; |
942 return anode_matching[node]; |
923 } else { |
943 } else { |
924 return bnode_matching[node]; |
944 return bnode_matching[node]; |
925 } |
945 } |
979 |
999 |
980 Heap *_heap; |
1000 Heap *_heap; |
981 bool local_heap; |
1001 bool local_heap; |
982 |
1002 |
983 }; |
1003 }; |
|
1004 |
|
1005 /// \ingroup matching |
|
1006 /// |
|
1007 /// \brief Maximum weighted bipartite matching |
|
1008 /// |
|
1009 /// This function calculates the maximum weighted matching |
|
1010 /// in a bipartite graph. It gives back the matching in an undirected |
|
1011 /// edge map. |
|
1012 /// |
|
1013 /// \param graph The bipartite graph. |
|
1014 /// \param weight The undirected edge map which contains the weights. |
|
1015 /// \retval matching The undirected edge map which will be set to |
|
1016 /// the matching. |
|
1017 /// \return The value of the matching. |
|
1018 template <typename BpUGraph, typename WeightMap, typename MatchingMap> |
|
1019 typename WeightMap::Value |
|
1020 maxWeightedBipartiteMatching(const BpUGraph& graph, const WeightMap& weight, |
|
1021 MatchingMap& matching) { |
|
1022 MaxWeightedBipartiteMatching<BpUGraph, WeightMap> |
|
1023 bpmatching(graph, weight); |
|
1024 bpmatching.run(); |
|
1025 bpmatching.matching(matching); |
|
1026 return bpmatching.matchingValue(); |
|
1027 } |
|
1028 |
|
1029 /// \ingroup matching |
|
1030 /// |
|
1031 /// \brief Maximum weighted maximum cardinality bipartite matching |
|
1032 /// |
|
1033 /// This function calculates the maximum weighted of the maximum cardinality |
|
1034 /// matchings of a bipartite graph. It gives back the matching in an |
|
1035 /// undirected edge map. |
|
1036 /// |
|
1037 /// \param graph The bipartite graph. |
|
1038 /// \param weight The undirected edge map which contains the weights. |
|
1039 /// \retval matching The undirected edge map which will be set to |
|
1040 /// the matching. |
|
1041 /// \return The value of the matching. |
|
1042 template <typename BpUGraph, typename WeightMap, typename MatchingMap> |
|
1043 typename WeightMap::Value |
|
1044 maxWeightedMaxBipartiteMatching(const BpUGraph& graph, |
|
1045 const WeightMap& weight, |
|
1046 MatchingMap& matching) { |
|
1047 MaxWeightedBipartiteMatching<BpUGraph, WeightMap> |
|
1048 bpmatching(graph, weight); |
|
1049 bpmatching.run(true); |
|
1050 bpmatching.matching(matching); |
|
1051 return bpmatching.matchingValue(); |
|
1052 } |
984 |
1053 |
985 /// \brief Default traits class for minimum cost bipartite matching |
1054 /// \brief Default traits class for minimum cost bipartite matching |
986 /// algoritms. |
1055 /// algoritms. |
987 /// |
1056 /// |
988 /// Default traits class for minimum cost bipartite matching |
1057 /// Default traits class for minimum cost bipartite matching |
1358 |
1427 |
1359 ///@{ |
1428 ///@{ |
1360 |
1429 |
1361 /// \brief Gives back the potential in the NodeMap |
1430 /// \brief Gives back the potential in the NodeMap |
1362 /// |
1431 /// |
1363 /// Gives back the potential in the NodeMap. The potential |
1432 /// Gives back the potential in the NodeMap. The potential is optimal with |
1364 /// is feasible if \f$ \pi(a) - \pi(b) + w(ab) = 0 \f$ for |
1433 /// the current number of edges if \f$ \pi(a) - \pi(b) + w(ab) = 0 \f$ for |
1365 /// each matching edges and \f$ \pi(a) - \pi(b) + w(ab) \ge 0 \f$ |
1434 /// each matching edges and \f$ \pi(a) - \pi(b) + w(ab) \ge 0 \f$ |
1366 /// for each edges. |
1435 /// for each edges. |
1367 template <typename PotentialMap> |
1436 template <typename PotentialMap> |
1368 void potential(PotentialMap& potential) { |
1437 void potential(PotentialMap& potential) const { |
1369 for (ANodeIt it(*graph); it != INVALID; ++it) { |
1438 for (ANodeIt it(*graph); it != INVALID; ++it) { |
1370 potential[it] = anode_potential[it]; |
1439 potential[it] = anode_potential[it]; |
1371 } |
1440 } |
1372 for (BNodeIt it(*graph); it != INVALID; ++it) { |
1441 for (BNodeIt it(*graph); it != INVALID; ++it) { |
1373 potential[it] = bnode_potential[it]; |
1442 potential[it] = bnode_potential[it]; |
1378 /// |
1447 /// |
1379 /// Set true all matching uedge in the map. It does not change the |
1448 /// Set true all matching uedge in the map. It does not change the |
1380 /// value mapped to the other uedges. |
1449 /// value mapped to the other uedges. |
1381 /// \return The number of the matching edges. |
1450 /// \return The number of the matching edges. |
1382 template <typename MatchingMap> |
1451 template <typename MatchingMap> |
1383 int quickMatching(MatchingMap& matching) { |
1452 int quickMatching(MatchingMap& matching) const { |
1384 for (ANodeIt it(*graph); it != INVALID; ++it) { |
1453 for (ANodeIt it(*graph); it != INVALID; ++it) { |
1385 if (anode_matching[it] != INVALID) { |
1454 if (anode_matching[it] != INVALID) { |
1386 matching[anode_matching[it]] = true; |
1455 matching[anode_matching[it]] = true; |
1387 } |
1456 } |
1388 } |
1457 } |
1392 /// \brief Set true all matching uedge in the map and the others to false. |
1461 /// \brief Set true all matching uedge in the map and the others to false. |
1393 /// |
1462 /// |
1394 /// Set true all matching uedge in the map and the others to false. |
1463 /// Set true all matching uedge in the map and the others to false. |
1395 /// \return The number of the matching edges. |
1464 /// \return The number of the matching edges. |
1396 template <typename MatchingMap> |
1465 template <typename MatchingMap> |
1397 int matching(MatchingMap& matching) { |
1466 int matching(MatchingMap& matching) const { |
1398 for (UEdgeIt it(*graph); it != INVALID; ++it) { |
1467 for (UEdgeIt it(*graph); it != INVALID; ++it) { |
1399 matching[it] = it == anode_matching[graph->aNode(it)]; |
1468 matching[it] = it == anode_matching[graph->aNode(it)]; |
1400 } |
1469 } |
1401 return matching_size; |
1470 return matching_size; |
1402 } |
1471 } |
1403 |
1472 |
1404 |
1473 |
1405 /// \brief Return true if the given uedge is in the matching. |
1474 /// \brief Return true if the given uedge is in the matching. |
1406 /// |
1475 /// |
1407 /// It returns true if the given uedge is in the matching. |
1476 /// It returns true if the given uedge is in the matching. |
1408 bool matchingEdge(const UEdge& edge) { |
1477 bool matchingEdge(const UEdge& edge) const { |
1409 return anode_matching[graph->aNode(edge)] == edge; |
1478 return anode_matching[graph->aNode(edge)] == edge; |
1410 } |
1479 } |
1411 |
1480 |
1412 /// \brief Returns the matching edge from the node. |
1481 /// \brief Returns the matching edge from the node. |
1413 /// |
1482 /// |
1414 /// Returns the matching edge from the node. If there is not such |
1483 /// Returns the matching edge from the node. If there is not such |
1415 /// edge it gives back \c INVALID. |
1484 /// edge it gives back \c INVALID. |
1416 UEdge matchingEdge(const Node& node) { |
1485 UEdge matchingEdge(const Node& node) const { |
1417 if (graph->aNode(node)) { |
1486 if (graph->aNode(node)) { |
1418 return anode_matching[node]; |
1487 return anode_matching[node]; |
1419 } else { |
1488 } else { |
1420 return bnode_matching[node]; |
1489 return bnode_matching[node]; |
1421 } |
1490 } |
1476 Heap *_heap; |
1545 Heap *_heap; |
1477 bool local_heap; |
1546 bool local_heap; |
1478 |
1547 |
1479 }; |
1548 }; |
1480 |
1549 |
|
1550 /// \ingroup matching |
|
1551 /// |
|
1552 /// \brief Minimum cost maximum cardinality bipartite matching |
|
1553 /// |
|
1554 /// This function calculates the minimum cost matching of the maximum |
|
1555 /// cardinality matchings of a bipartite graph. It gives back the matching |
|
1556 /// in an undirected edge map. |
|
1557 /// |
|
1558 /// \param graph The bipartite graph. |
|
1559 /// \param cost The undirected edge map which contains the costs. |
|
1560 /// \retval matching The undirected edge map which will be set to |
|
1561 /// the matching. |
|
1562 /// \return The cost of the matching. |
|
1563 template <typename BpUGraph, typename CostMap, typename MatchingMap> |
|
1564 typename CostMap::Value |
|
1565 minCostMaxBipartiteMatching(const BpUGraph& graph, |
|
1566 const CostMap& cost, |
|
1567 MatchingMap& matching) { |
|
1568 MinCostMaxBipartiteMatching<BpUGraph, CostMap> |
|
1569 bpmatching(graph, cost); |
|
1570 bpmatching.run(); |
|
1571 bpmatching.matching(matching); |
|
1572 return bpmatching.matchingCost(); |
|
1573 } |
|
1574 |
1481 } |
1575 } |
1482 |
1576 |
1483 #endif |
1577 #endif |