Changeset 2058:0b1fc1566fdb in lemon-0.x
- Timestamp:
- 04/18/06 09:01:55 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2702
- Files:
-
- 2 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 -
test/bipartite_matching_test.cc
r2051 r2058 24 24 vector<Node> aNodes; 25 25 vector<Node> bNodes; 26 int n = argc > 1 ? atoi(argv[1]) : 10 0;27 int m = argc > 2 ? atoi(argv[2]) : 10 0;26 int n = argc > 1 ? atoi(argv[1]) : 10; 27 int m = argc > 2 ? atoi(argv[2]) : 10; 28 28 int e = argc > 3 ? atoi(argv[3]) : (int)((n+m) * log(n+m)); 29 29 int c = argc > 4 ? atoi(argv[4]) : 100; … … 34 34 int max_weight; 35 35 int max_cardinality_max_weight; 36 int min_cost_matching; 36 37 37 38 for (int i = 0; i < n; ++i) { … … 72 73 } 73 74 max_cardinality = bpmatch.matchingSize(); 75 } 76 77 { 78 Graph::UEdgeMap<bool> mm(graph); 79 80 check(max_cardinality == maxBipartiteMatching(graph, mm), 81 "WRONG MATCHING"); 82 83 for (ANodeIt it(graph); it != INVALID; ++it) { 84 int num = 0; 85 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) { 86 if (mm[jt]) ++num; 87 } 88 check(num <= 1, "INVALID PRIMAL"); 89 } 74 90 } 75 91 … … 138 154 for (UEdgeIt it(graph); it != INVALID; ++it) { 139 155 if (mm[it]) { 140 check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0,156 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0, 141 157 "INVALID DUAL"); 142 158 } else { 143 check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0,159 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0, 144 160 "INVALID DUAL"); 145 161 } … … 160 176 161 177 { 178 Graph::UEdgeMap<bool> mm(graph); 179 180 check(max_weight == maxWeightedBipartiteMatching(graph, weight, mm), 181 "WRONG MATCHING"); 182 183 for (ANodeIt it(graph); it != INVALID; ++it) { 184 int num = 0; 185 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) { 186 if (mm[jt]) ++num; 187 } 188 check(num <= 1, "INVALID PRIMAL"); 189 } 190 } 191 192 { 162 193 MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight); 163 194 … … 172 203 for (UEdgeIt it(graph); it != INVALID; ++it) { 173 204 if (mm[it]) { 174 check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0,205 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0, 175 206 "INVALID DUAL"); 176 207 } else { 177 check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0,208 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0, 178 209 "INVALID DUAL"); 179 210 } … … 203 234 for (UEdgeIt it(graph); it != INVALID; ++it) { 204 235 if (mm[it]) { 205 check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0,236 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0, 206 237 "INVALID DUAL"); 207 238 } else { 208 check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0,239 check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0, 209 240 "INVALID DUAL"); 210 241 } … … 224 255 225 256 { 226 Graph::UEdgeMap<int> cost(graph); 227 228 cost = subMap(constMap<UEdge>(c), weight); 257 Graph::UEdgeMap<bool> mm(graph); 258 259 check(max_cardinality_max_weight == 260 maxWeightedMaxBipartiteMatching(graph, weight, mm), 261 "WRONG MATCHING"); 262 263 for (ANodeIt it(graph); it != INVALID; ++it) { 264 int num = 0; 265 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) { 266 if (mm[jt]) ++num; 267 } 268 check(num <= 1, "INVALID PRIMAL"); 269 } 270 } 271 272 Graph::UEdgeMap<int> cost(graph); 273 cost = subMap(constMap<UEdge>(c), weight); 274 275 { 229 276 230 277 MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost); … … 256 303 } 257 304 305 min_cost_matching = bpmatch.matchingCost(); 258 306 check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE"); 259 307 check(max_cardinality * c - max_cardinality_max_weight … … 262 310 } 263 311 312 { 313 Graph::UEdgeMap<bool> mm(graph); 314 315 check(min_cost_matching == 316 minCostMaxBipartiteMatching(graph, cost, mm), 317 "WRONG MATCHING"); 318 319 for (ANodeIt it(graph); it != INVALID; ++it) { 320 int num = 0; 321 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) { 322 if (mm[jt]) ++num; 323 } 324 check(num <= 1, "INVALID PRIMAL"); 325 } 326 } 327 264 328 return 0; 265 329 }
Note: See TracChangeset
for help on using the changeset viewer.