test/bipartite_matching_test.cc
author deba
Tue, 31 Oct 2006 14:27:58 +0000
changeset 2282 9d7b12f83daa
parent 2116 b6a68c15a6a3
child 2386 81b47fc5c444
permissions -rw-r--r--
Bug fixes
deba@2040
     1
#include <cstdlib>
deba@2040
     2
#include <iostream>
deba@2040
     3
#include <sstream>
deba@2040
     4
deba@2137
     5
#include <lemon/smart_graph.h>
deba@2040
     6
deba@2040
     7
#include <lemon/bpugraph_adaptor.h>
deba@2040
     8
#include <lemon/bipartite_matching.h>
deba@2040
     9
deba@2040
    10
#include <lemon/graph_utils.h>
deba@2040
    11
deba@2051
    12
#include <lemon/maps.h>
deba@2051
    13
deba@2040
    14
#include "test_tools.h"
deba@2040
    15
deba@2040
    16
using namespace std;
deba@2040
    17
using namespace lemon;
deba@2040
    18
deba@2137
    19
typedef SmartBpUGraph Graph;
deba@2040
    20
BPUGRAPH_TYPEDEFS(Graph);
deba@2040
    21
deba@2137
    22
const int n = 10;
deba@2137
    23
const int m = 10;
deba@2137
    24
const int e = 52;
deba@2137
    25
const int c = 100;
deba@2137
    26
deba@2137
    27
const int sa[e] = { 6, 5, 6, 4, 1, 0, 9, 5, 2, 4, 4, 3, 5,
deba@2137
    28
                    2, 3, 8, 3, 4, 9, 6, 9, 4, 3, 1, 5, 8,
deba@2137
    29
                    4, 8, 9, 2, 2, 3, 0, 5, 2, 3, 6, 3, 8,
deba@2137
    30
                    8, 4, 0, 9, 9, 6, 2, 1, 2, 7, 1, 9, 4};
deba@2137
    31
deba@2137
    32
const int ta[e] = { 2, 7, 4, 8, 6, 3, 4, 1, 7, 7, 0, 1, 6,
deba@2137
    33
                    3, 2, 6, 8, 3, 5, 6, 3, 1, 8, 7, 2, 0,
deba@2137
    34
                    6, 9, 6, 7, 8, 3, 3, 4, 5, 8, 6, 4, 1,
deba@2137
    35
                    4, 3, 3, 8, 7, 7, 3, 7, 7, 3, 5, 1, 6};
deba@2137
    36
deba@2137
    37
const int wa[e] = { 3, 99, 85, 16, 79, 52, 83, 99, 62, 6, 42, 6, 95,
deba@2137
    38
                    13, 34, 9, 5, 38, 39, 75, 99, 12, 73, 35, 93, 43,
deba@2137
    39
                    54, 91, 45, 26, 77, 47, 11, 22, 50, 74, 37, 64, 91,
deba@2137
    40
                    60, 6, 92, 29, 46, 34, 84, 67, 34, 45, 0, 39, 47};
deba@2137
    41
deba@2137
    42
deba@2137
    43
int main() {
deba@2040
    44
  Graph graph;
deba@2040
    45
  vector<Node> aNodes;
deba@2040
    46
  vector<Node> bNodes;
deba@2051
    47
deba@2051
    48
  Graph::UEdgeMap<int> weight(graph);
deba@2051
    49
deba@2051
    50
  int max_cardinality;
deba@2051
    51
  int max_weight;
deba@2051
    52
  int max_cardinality_max_weight;
deba@2058
    53
  int min_cost_matching;
deba@2040
    54
deba@2040
    55
  for (int i = 0; i < n; ++i) {
deba@2040
    56
    Node node = graph.addANode();
deba@2040
    57
    aNodes.push_back(node);
deba@2040
    58
  }
deba@2040
    59
  for (int i = 0; i < m; ++i) {
deba@2040
    60
    Node node = graph.addBNode();
deba@2040
    61
    bNodes.push_back(node);
deba@2040
    62
  }
deba@2040
    63
  for (int i = 0; i < e; ++i) {
deba@2137
    64
    Node aNode = aNodes[sa[i]];
deba@2137
    65
    Node bNode = bNodes[ta[i]];
deba@2051
    66
    UEdge uedge = graph.addEdge(aNode, bNode);
deba@2137
    67
    weight[uedge] = wa[i];
deba@2040
    68
  }
deba@2040
    69
deba@2137
    70
deba@2040
    71
  {
deba@2040
    72
    MaxBipartiteMatching<Graph> bpmatch(graph);
deba@2040
    73
deba@2040
    74
    bpmatch.run();
deba@2040
    75
deba@2040
    76
    Graph::UEdgeMap<bool> mm(graph);
deba@2040
    77
    Graph::NodeMap<bool> cs(graph);
deba@2040
    78
    
deba@2040
    79
    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
deba@2040
    80
    
deba@2040
    81
    for (UEdgeIt it(graph); it != INVALID; ++it) {
deba@2040
    82
      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
deba@2040
    83
    }
deba@2040
    84
    
deba@2040
    85
    for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2040
    86
      int num = 0;
deba@2040
    87
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2040
    88
        if (mm[jt]) ++num;
deba@2051
    89
      }
deba@2040
    90
      check(num <= 1, "INVALID PRIMAL");
deba@2040
    91
    }
deba@2051
    92
    max_cardinality = bpmatch.matchingSize();
deba@2040
    93
  }
deba@2040
    94
deba@2040
    95
  {
deba@2058
    96
    Graph::UEdgeMap<bool> mm(graph);
deba@2058
    97
deba@2058
    98
    check(max_cardinality == maxBipartiteMatching(graph, mm),
deba@2058
    99
          "WRONG MATCHING");
deba@2058
   100
    
deba@2058
   101
    for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2058
   102
      int num = 0;
deba@2058
   103
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2058
   104
        if (mm[jt]) ++num;
deba@2058
   105
      }
deba@2058
   106
      check(num <= 1, "INVALID PRIMAL");
deba@2058
   107
    }
deba@2058
   108
  }
deba@2058
   109
deba@2058
   110
  {
deba@2040
   111
    MaxBipartiteMatching<Graph> bpmatch(graph);
deba@2040
   112
deba@2040
   113
    bpmatch.greedyInit();
deba@2040
   114
    bpmatch.start();
deba@2040
   115
deba@2040
   116
    Graph::UEdgeMap<bool> mm(graph);
deba@2040
   117
    Graph::NodeMap<bool> cs(graph);
deba@2040
   118
deba@2040
   119
    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
deba@2040
   120
    
deba@2040
   121
    for (UEdgeIt it(graph); it != INVALID; ++it) {
deba@2040
   122
      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
deba@2040
   123
    }
deba@2040
   124
    
deba@2040
   125
    for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2040
   126
      int num = 0;
deba@2040
   127
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2040
   128
        if (mm[jt]) ++num;
deba@2040
   129
    }
deba@2040
   130
      check(num <= 1, "INVALID PRIMAL");
deba@2040
   131
    }
deba@2040
   132
  }
deba@2040
   133
deba@2040
   134
  {
deba@2040
   135
    MaxBipartiteMatching<Graph> bpmatch(graph);
deba@2040
   136
deba@2040
   137
    bpmatch.greedyInit();
deba@2040
   138
    while (bpmatch.simpleAugment());
deba@2040
   139
    
deba@2040
   140
    Graph::UEdgeMap<bool> mm(graph);
deba@2040
   141
    Graph::NodeMap<bool> cs(graph);
deba@2040
   142
    
deba@2040
   143
    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
deba@2040
   144
    
deba@2040
   145
    for (UEdgeIt it(graph); it != INVALID; ++it) {
deba@2040
   146
      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
deba@2040
   147
    }
deba@2040
   148
    
deba@2040
   149
    for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2040
   150
      int num = 0;
deba@2040
   151
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2040
   152
        if (mm[jt]) ++num;
deba@2040
   153
    }
deba@2040
   154
      check(num <= 1, "INVALID PRIMAL");
deba@2040
   155
    }
deba@2040
   156
  }
deba@2040
   157
deba@2040
   158
  {
deba@2051
   159
    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
deba@2051
   160
deba@2051
   161
    bpmatch.init();
deba@2051
   162
deba@2051
   163
    max_weight = 0;
deba@2051
   164
    while (bpmatch.augment(true)) {
deba@2051
   165
    
deba@2051
   166
      Graph::UEdgeMap<bool> mm(graph);
deba@2051
   167
      Graph::NodeMap<int> pm(graph);
deba@2051
   168
      
deba@2051
   169
      bpmatch.matching(mm);
deba@2051
   170
      bpmatch.potential(pm);
deba@2051
   171
      
deba@2051
   172
      for (UEdgeIt it(graph); it != INVALID; ++it) {
deba@2051
   173
        if (mm[it]) {
deba@2058
   174
          check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
deba@2051
   175
                "INVALID DUAL");
deba@2051
   176
        } else {
deba@2058
   177
          check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
deba@2051
   178
                "INVALID DUAL");
deba@2051
   179
        }
deba@2051
   180
      }
deba@2051
   181
deba@2051
   182
      for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2051
   183
        int num = 0;
deba@2051
   184
        for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2051
   185
          if (mm[jt]) ++num;
deba@2051
   186
        }
deba@2051
   187
        check(num <= 1, "INVALID PRIMAL");
deba@2051
   188
      }
deba@2051
   189
      if (bpmatch.matchingValue() > max_weight) {
deba@2051
   190
        max_weight = bpmatch.matchingValue();
deba@2051
   191
      }
deba@2051
   192
    }
deba@2051
   193
  }
deba@2051
   194
deba@2051
   195
  {
deba@2058
   196
    Graph::UEdgeMap<bool> mm(graph);
deba@2058
   197
deba@2058
   198
    check(max_weight == maxWeightedBipartiteMatching(graph, weight, mm),
deba@2058
   199
          "WRONG MATCHING");
deba@2058
   200
    
deba@2058
   201
    for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2058
   202
      int num = 0;
deba@2058
   203
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2058
   204
        if (mm[jt]) ++num;
deba@2058
   205
      }
deba@2058
   206
      check(num <= 1, "INVALID PRIMAL");
deba@2058
   207
    }
deba@2058
   208
  }
deba@2058
   209
deba@2058
   210
  {
deba@2051
   211
    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
deba@2040
   212
deba@2040
   213
    bpmatch.run();
deba@2051
   214
    
deba@2051
   215
    Graph::UEdgeMap<bool> mm(graph);
deba@2051
   216
    Graph::NodeMap<int> pm(graph);
deba@2040
   217
deba@2051
   218
    bpmatch.matching(mm);
deba@2051
   219
    bpmatch.potential(pm);
deba@2040
   220
    
deba@2040
   221
    for (UEdgeIt it(graph); it != INVALID; ++it) {
deba@2051
   222
      if (mm[it]) {
deba@2058
   223
        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
deba@2051
   224
              "INVALID DUAL");
deba@2051
   225
      } else {
deba@2058
   226
        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
deba@2051
   227
              "INVALID DUAL");
deba@2051
   228
      }
deba@2040
   229
    }
deba@2051
   230
deba@2040
   231
    for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2040
   232
      int num = 0;
deba@2040
   233
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2040
   234
        if (mm[jt]) ++num;
deba@2040
   235
    }
deba@2040
   236
      check(num <= 1, "INVALID PRIMAL");
deba@2040
   237
    }
deba@2051
   238
    check(max_weight == bpmatch.matchingValue(), "WRONG WEIGHT");
deba@2051
   239
  }
deba@2051
   240
deba@2051
   241
  {
deba@2051
   242
    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
deba@2051
   243
deba@2051
   244
    bpmatch.run(true);
deba@2051
   245
    
deba@2051
   246
    Graph::UEdgeMap<bool> mm(graph);
deba@2051
   247
    Graph::NodeMap<int> pm(graph);
deba@2051
   248
deba@2051
   249
    bpmatch.matching(mm);
deba@2051
   250
    bpmatch.potential(pm);
deba@2051
   251
    
deba@2051
   252
    for (UEdgeIt it(graph); it != INVALID; ++it) {
deba@2051
   253
      if (mm[it]) {
deba@2058
   254
        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
deba@2051
   255
              "INVALID DUAL");
deba@2051
   256
      } else {
deba@2058
   257
        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
deba@2051
   258
              "INVALID DUAL");
deba@2051
   259
      }
deba@2051
   260
    }
deba@2051
   261
deba@2051
   262
    for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2051
   263
      int num = 0;
deba@2051
   264
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2051
   265
        if (mm[jt]) ++num;
deba@2051
   266
    }
deba@2051
   267
      check(num <= 1, "INVALID PRIMAL");
deba@2051
   268
    }
deba@2051
   269
    check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
deba@2051
   270
    max_cardinality_max_weight = bpmatch.matchingValue();
deba@2051
   271
deba@2051
   272
  }
deba@2051
   273
deba@2051
   274
  {
deba@2058
   275
    Graph::UEdgeMap<bool> mm(graph);
deba@2051
   276
deba@2058
   277
    check(max_cardinality_max_weight == 
deba@2058
   278
          maxWeightedMaxBipartiteMatching(graph, weight, mm),
deba@2058
   279
          "WRONG MATCHING");
deba@2058
   280
    
deba@2058
   281
    for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2058
   282
      int num = 0;
deba@2058
   283
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2058
   284
        if (mm[jt]) ++num;
deba@2058
   285
      }
deba@2058
   286
      check(num <= 1, "INVALID PRIMAL");
deba@2058
   287
    }
deba@2058
   288
  }
deba@2058
   289
deba@2058
   290
  Graph::UEdgeMap<int> cost(graph);
deba@2058
   291
  cost = subMap(constMap<UEdge>(c), weight);
deba@2058
   292
  {
deba@2051
   293
deba@2051
   294
    MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost);
deba@2051
   295
deba@2051
   296
    bpmatch.run();
deba@2051
   297
    
deba@2051
   298
    Graph::UEdgeMap<bool> mm(graph);
deba@2051
   299
    Graph::NodeMap<int> pm(graph);
deba@2051
   300
deba@2051
   301
    bpmatch.matching(mm);
deba@2051
   302
    bpmatch.potential(pm);
deba@2051
   303
    
deba@2137
   304
    min_cost_matching = bpmatch.matchingCost();
deba@2137
   305
    check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
deba@2137
   306
    check(max_cardinality * c - max_cardinality_max_weight 
deba@2137
   307
          == bpmatch.matchingCost(), "WRONG SIZE");
deba@2137
   308
deba@2051
   309
    for (UEdgeIt it(graph); it != INVALID; ++it) {
deba@2051
   310
      if (mm[it]) {
deba@2051
   311
        check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] == 0,
deba@2051
   312
              "INVALID DUAL");
deba@2051
   313
      } else {
deba@2051
   314
        check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] >= 0,
deba@2051
   315
              "INVALID DUAL");
deba@2051
   316
      }
deba@2051
   317
    }
deba@2051
   318
deba@2051
   319
    for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2051
   320
      int num = 0;
deba@2051
   321
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2051
   322
        if (mm[jt]) ++num;
deba@2051
   323
    }
deba@2051
   324
      check(num <= 1, "INVALID PRIMAL");
deba@2051
   325
    }
deba@2051
   326
deba@2058
   327
    min_cost_matching = bpmatch.matchingCost();
deba@2051
   328
    check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
deba@2051
   329
    check(max_cardinality * c - max_cardinality_max_weight 
deba@2051
   330
          == bpmatch.matchingCost(), "WRONG SIZE");
deba@2051
   331
deba@2040
   332
  }
deba@2040
   333
deba@2058
   334
  {
deba@2058
   335
    Graph::UEdgeMap<bool> mm(graph);
deba@2058
   336
deba@2058
   337
    check(min_cost_matching == 
deba@2058
   338
          minCostMaxBipartiteMatching(graph, cost, mm),
deba@2058
   339
          "WRONG MATCHING");
deba@2058
   340
    
deba@2058
   341
    for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2058
   342
      int num = 0;
deba@2058
   343
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2058
   344
        if (mm[jt]) ++num;
deba@2058
   345
      }
deba@2058
   346
      check(num <= 1, "INVALID PRIMAL");
deba@2058
   347
    }
deba@2058
   348
  }
deba@2058
   349
deba@2040
   350
  return 0;
deba@2040
   351
}