COIN-OR::LEMON - Graph Library

Changeset 2058:0b1fc1566fdb in lemon-0.x for test


Ignore:
Timestamp:
04/18/06 09:01:55 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2702
Message:

Refinements in bipartite matching algorithms

File:
1 edited

Legend:

Unmodified
Added
Removed
  • test/bipartite_matching_test.cc

    r2051 r2058  
    2424  vector<Node> aNodes;
    2525  vector<Node> bNodes;
    26   int n = argc > 1 ? atoi(argv[1]) : 100;
    27   int m = argc > 2 ? atoi(argv[2]) : 100;
     26  int n = argc > 1 ? atoi(argv[1]) : 10;
     27  int m = argc > 2 ? atoi(argv[2]) : 10;
    2828  int e = argc > 3 ? atoi(argv[3]) : (int)((n+m) * log(n+m));
    2929  int c = argc > 4 ? atoi(argv[4]) : 100;
     
    3434  int max_weight;
    3535  int max_cardinality_max_weight;
     36  int min_cost_matching;
    3637
    3738  for (int i = 0; i < n; ++i) {
     
    7273    }
    7374    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    }
    7490  }
    7591
     
    138154      for (UEdgeIt it(graph); it != INVALID; ++it) {
    139155        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,
    141157                "INVALID DUAL");
    142158        } 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,
    144160                "INVALID DUAL");
    145161        }
     
    160176
    161177  {
     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  {
    162193    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
    163194
     
    172203    for (UEdgeIt it(graph); it != INVALID; ++it) {
    173204      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,
    175206              "INVALID DUAL");
    176207      } 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,
    178209              "INVALID DUAL");
    179210      }
     
    203234    for (UEdgeIt it(graph); it != INVALID; ++it) {
    204235      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,
    206237              "INVALID DUAL");
    207238      } 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,
    209240              "INVALID DUAL");
    210241      }
     
    224255
    225256  {
    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  {
    229276
    230277    MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost);
     
    256303    }
    257304
     305    min_cost_matching = bpmatch.matchingCost();
    258306    check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
    259307    check(max_cardinality * c - max_cardinality_max_weight
     
    262310  }
    263311
     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
    264328  return 0;
    265329}
Note: See TracChangeset for help on using the changeset viewer.