Changeset 2058:0b1fc1566fdb in lemon0.x for lemon/bipartite_matching.h
 Timestamp:
 04/18/06 09:01:55 (14 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2702
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/bipartite_matching.h
r2051 r2058 329 329 /// It just initalize the algorithm and then start it. 330 330 void run() { 331 init();331 greedyInit(); 332 332 start(); 333 333 } … … 350 350 /// \return The size of the cover set. 351 351 template <typename CoverMap> 352 int coverSet(CoverMap& covering) {352 int coverSet(CoverMap& covering) const { 353 353 354 354 typename Graph::template ANodeMap<bool> areached(*graph, false); … … 404 404 /// \return The number of the matching edges. 405 405 template <typename MatchingMap> 406 int quickMatching(MatchingMap& matching) {406 int quickMatching(MatchingMap& matching) const { 407 407 for (ANodeIt it(*graph); it != INVALID; ++it) { 408 408 if (anode_matching[it] != INVALID) { … … 418 418 /// \return The number of the matching edges. 419 419 template <typename MatchingMap> 420 int matching(MatchingMap& matching) {420 int matching(MatchingMap& matching) const { 421 421 for (UEdgeIt it(*graph); it != INVALID; ++it) { 422 422 matching[it] = it == anode_matching[graph>aNode(it)]; … … 429 429 /// 430 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 432 return anode_matching[graph>aNode(edge)] == edge; 433 433 } … … 437 437 /// Returns the matching edge from the node. If there is not such 438 438 /// edge it gives back \c INVALID. 439 UEdge matchingEdge(const Node& node) {439 UEdge matchingEdge(const Node& node) const { 440 440 if (graph>aNode(node)) { 441 441 return anode_matching[node]; … … 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 486 /// \brief Default traits class for weighted bipartite matching algoritms. … … 702 722 bnode_potential[it] = 0; 703 723 for (IncEdgeIt jt(*graph, it); jt != INVALID; ++jt) { 704 if ( (*weight)[jt] <=bnode_potential[it]) {705 bnode_potential[it] = (*weight)[jt];724 if ((*weight)[jt] > bnode_potential[it]) { 725 bnode_potential[it] = (*weight)[jt]; 706 726 } 707 727 } … … 754 774 if (jt == anode_matching[anode]) continue; 755 775 Node bnode = graph>bNode(jt); 756 Value bvalue = avalue + anode_potential[anode] 757 bnode_potential[bnode]  (*weight)[jt];776 Value bvalue = avalue  (*weight)[jt] + 777 anode_potential[anode] + bnode_potential[bnode]; 758 778 if (bpred[bnode] == INVALID  bvalue < bdist[bnode]) { 759 779 bdist[bnode] = bvalue; … … 779 799 } else { 780 800 if (bestNode == INVALID  781  bvalue  bnode_potential[bnode]> bestValue) {782 bestValue =  bvalue  bnode_potential[bnode];801 bnode_potential[bnode]  bvalue > bestValue) { 802 bestValue = bnode_potential[bnode]  bvalue; 783 803 bestNode = bnode; 784 804 } … … 796 816 for (BNodeIt it(*graph); it != INVALID; ++it) { 797 817 if (bpred[it] != INVALID) { 798 bnode_potential[it] += bdist[it];818 bnode_potential[it] = bdist[it]; 799 819 } else { 800 bnode_potential[it] += bdistMax;820 bnode_potential[it] = bdistMax; 801 821 } 802 822 } … … 865 885 /// \brief Gives back the potential in the NodeMap 866 886 /// 867 /// Gives back the potential in the NodeMap. The potential868 /// is feasible if \f$ \pi(a)  \pi(b)  w(ab) = 0 \f$ for869 /// each matching edges and \f$ \pi(a) \pi(b)  w(ab) \ge 0 \f$870 /// for each edges. 887 /// Gives back the potential in the NodeMap. The matching is optimal 888 /// with the current number of edges if \f$ \pi(a) + \pi(b)  w(ab) = 0 \f$ 889 /// for each matching edges and \f$ \pi(a) + \pi(b)  w(ab) \ge 0 \f$ 890 /// for each edges. 871 891 template <typename PotentialMap> 872 void potential(PotentialMap& potential) {892 void potential(PotentialMap& potential) const { 873 893 for (ANodeIt it(*graph); it != INVALID; ++it) { 874 894 potential[it] = anode_potential[it]; … … 885 905 /// \return The number of the matching edges. 886 906 template <typename MatchingMap> 887 int quickMatching(MatchingMap& matching) {907 int quickMatching(MatchingMap& matching) const { 888 908 for (ANodeIt it(*graph); it != INVALID; ++it) { 889 909 if (anode_matching[it] != INVALID) { … … 899 919 /// \return The number of the matching edges. 900 920 template <typename MatchingMap> 901 int matching(MatchingMap& matching) {921 int matching(MatchingMap& matching) const { 902 922 for (UEdgeIt it(*graph); it != INVALID; ++it) { 903 923 matching[it] = it == anode_matching[graph>aNode(it)]; … … 910 930 /// 911 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 933 return anode_matching[graph>aNode(edge)] == edge; 914 934 } … … 918 938 /// Returns the matching edge from the node. If there is not such 919 939 /// edge it gives back \c INVALID. 920 UEdge matchingEdge(const Node& node) {940 UEdge matchingEdge(const Node& node) const { 921 941 if (graph>aNode(node)) { 922 942 return anode_matching[node]; … … 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 1054 /// \brief Default traits class for minimum cost bipartite matching … … 1361 1430 /// \brief Gives back the potential in the NodeMap 1362 1431 /// 1363 /// Gives back the potential in the NodeMap. The potential 1364 /// is feasibleif \f$ \pi(a)  \pi(b) + w(ab) = 0 \f$ for1432 /// Gives back the potential in the NodeMap. The potential is optimal with 1433 /// the current number of edges if \f$ \pi(a)  \pi(b) + w(ab) = 0 \f$ for 1365 1434 /// each matching edges and \f$ \pi(a)  \pi(b) + w(ab) \ge 0 \f$ 1366 1435 /// for each edges. 1367 1436 template <typename PotentialMap> 1368 void potential(PotentialMap& potential) {1437 void potential(PotentialMap& potential) const { 1369 1438 for (ANodeIt it(*graph); it != INVALID; ++it) { 1370 1439 potential[it] = anode_potential[it]; … … 1381 1450 /// \return The number of the matching edges. 1382 1451 template <typename MatchingMap> 1383 int quickMatching(MatchingMap& matching) {1452 int quickMatching(MatchingMap& matching) const { 1384 1453 for (ANodeIt it(*graph); it != INVALID; ++it) { 1385 1454 if (anode_matching[it] != INVALID) { … … 1395 1464 /// \return The number of the matching edges. 1396 1465 template <typename MatchingMap> 1397 int matching(MatchingMap& matching) {1466 int matching(MatchingMap& matching) const { 1398 1467 for (UEdgeIt it(*graph); it != INVALID; ++it) { 1399 1468 matching[it] = it == anode_matching[graph>aNode(it)]; … … 1406 1475 /// 1407 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 1478 return anode_matching[graph>aNode(edge)] == edge; 1410 1479 } … … 1414 1483 /// Returns the matching edge from the node. If there is not such 1415 1484 /// edge it gives back \c INVALID. 1416 UEdge matchingEdge(const Node& node) {1485 UEdge matchingEdge(const Node& node) const { 1417 1486 if (graph>aNode(node)) { 1418 1487 return anode_matching[node]; … … 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
Note: See TracChangeset
for help on using the changeset viewer.