test/bipartite_matching_test.cc
author alpar
Thu, 23 Oct 2008 16:49:06 +0000
changeset 2626 324cfbf66a12
parent 2571 f5c6e63f51d1
permissions -rw-r--r--
Adapt the doc generation to the hg repo
alpar@2391
     1
/* -*- C++ -*-
alpar@2391
     2
 *
alpar@2391
     3
 * This file is a part of LEMON, a generic C++ optimization library
alpar@2391
     4
 *
alpar@2553
     5
 * Copyright (C) 2003-2008
alpar@2391
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@2391
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@2391
     8
 *
alpar@2391
     9
 * Permission to use, modify and distribute this software is granted
alpar@2391
    10
 * provided that this copyright notice appears in all copies. For
alpar@2391
    11
 * precise terms see the accompanying LICENSE file.
alpar@2391
    12
 *
alpar@2391
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@2391
    14
 * express or implied, and with no claim as to its suitability for any
alpar@2391
    15
 * purpose.
alpar@2391
    16
 *
alpar@2391
    17
 */
alpar@2391
    18
deba@2040
    19
#include <cstdlib>
deba@2040
    20
#include <iostream>
deba@2040
    21
#include <sstream>
deba@2040
    22
deba@2137
    23
#include <lemon/smart_graph.h>
deba@2040
    24
deba@2040
    25
#include <lemon/bpugraph_adaptor.h>
deba@2040
    26
#include <lemon/bipartite_matching.h>
deba@2462
    27
#include <lemon/pr_bipartite_matching.h>
deba@2040
    28
deba@2040
    29
#include <lemon/graph_utils.h>
deba@2040
    30
deba@2051
    31
#include <lemon/maps.h>
deba@2051
    32
deba@2040
    33
#include "test_tools.h"
deba@2040
    34
deba@2040
    35
using namespace std;
deba@2040
    36
using namespace lemon;
deba@2040
    37
deba@2137
    38
typedef SmartBpUGraph Graph;
deba@2040
    39
BPUGRAPH_TYPEDEFS(Graph);
deba@2040
    40
alpar@2571
    41
const int NN = 10;
alpar@2571
    42
const int MM = 10;
alpar@2571
    43
const int EE = 52;
alpar@2571
    44
const int CC = 100;
deba@2137
    45
alpar@2571
    46
const int sa[EE] = { 6, 5, 6, 4, 1, 0, 9, 5, 2, 4, 4, 3, 5,
deba@2137
    47
                    2, 3, 8, 3, 4, 9, 6, 9, 4, 3, 1, 5, 8,
deba@2137
    48
                    4, 8, 9, 2, 2, 3, 0, 5, 2, 3, 6, 3, 8,
deba@2137
    49
                    8, 4, 0, 9, 9, 6, 2, 1, 2, 7, 1, 9, 4};
deba@2137
    50
alpar@2571
    51
const int ta[EE] = { 2, 7, 4, 8, 6, 3, 4, 1, 7, 7, 0, 1, 6,
deba@2137
    52
                    3, 2, 6, 8, 3, 5, 6, 3, 1, 8, 7, 2, 0,
deba@2137
    53
                    6, 9, 6, 7, 8, 3, 3, 4, 5, 8, 6, 4, 1,
deba@2137
    54
                    4, 3, 3, 8, 7, 7, 3, 7, 7, 3, 5, 1, 6};
deba@2137
    55
alpar@2571
    56
const int wa[EE] = { 3, 99, 85, 16, 79, 52, 83, 99, 62, 6, 42, 6, 95,
deba@2137
    57
                    13, 34, 9, 5, 38, 39, 75, 99, 12, 73, 35, 93, 43,
deba@2137
    58
                    54, 91, 45, 26, 77, 47, 11, 22, 50, 74, 37, 64, 91,
deba@2137
    59
                    60, 6, 92, 29, 46, 34, 84, 67, 34, 45, 0, 39, 47};
deba@2137
    60
deba@2137
    61
deba@2137
    62
int main() {
deba@2040
    63
  Graph graph;
deba@2040
    64
  vector<Node> aNodes;
deba@2040
    65
  vector<Node> bNodes;
deba@2051
    66
deba@2051
    67
  Graph::UEdgeMap<int> weight(graph);
deba@2051
    68
deba@2051
    69
  int max_cardinality;
deba@2051
    70
  int max_weight;
deba@2051
    71
  int max_cardinality_max_weight;
deba@2058
    72
  int min_cost_matching;
deba@2040
    73
alpar@2571
    74
  for (int i = 0; i < NN; ++i) {
deba@2040
    75
    Node node = graph.addANode();
deba@2040
    76
    aNodes.push_back(node);
deba@2040
    77
  }
alpar@2571
    78
  for (int i = 0; i < MM; ++i) {
deba@2040
    79
    Node node = graph.addBNode();
deba@2040
    80
    bNodes.push_back(node);
deba@2040
    81
  }
alpar@2571
    82
  for (int i = 0; i < EE; ++i) {
deba@2137
    83
    Node aNode = aNodes[sa[i]];
deba@2137
    84
    Node bNode = bNodes[ta[i]];
deba@2051
    85
    UEdge uedge = graph.addEdge(aNode, bNode);
deba@2137
    86
    weight[uedge] = wa[i];
deba@2040
    87
  }
deba@2040
    88
deba@2137
    89
deba@2040
    90
  {
deba@2040
    91
    MaxBipartiteMatching<Graph> bpmatch(graph);
deba@2040
    92
deba@2040
    93
    bpmatch.run();
deba@2040
    94
deba@2040
    95
    Graph::UEdgeMap<bool> mm(graph);
deba@2040
    96
    Graph::NodeMap<bool> cs(graph);
deba@2040
    97
    
deba@2040
    98
    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
deba@2040
    99
    
deba@2040
   100
    for (UEdgeIt it(graph); it != INVALID; ++it) {
deba@2040
   101
      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
deba@2040
   102
    }
deba@2040
   103
    
deba@2040
   104
    for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2040
   105
      int num = 0;
deba@2040
   106
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2040
   107
        if (mm[jt]) ++num;
deba@2051
   108
      }
deba@2040
   109
      check(num <= 1, "INVALID PRIMAL");
deba@2040
   110
    }
deba@2051
   111
    max_cardinality = bpmatch.matchingSize();
deba@2040
   112
  }
deba@2040
   113
deba@2040
   114
  {
deba@2462
   115
    PrBipartiteMatching<Graph> bpmatch(graph);
deba@2462
   116
deba@2462
   117
    bpmatch.run();
deba@2462
   118
deba@2462
   119
    Graph::UEdgeMap<bool> mm(graph);
deba@2462
   120
    Graph::NodeMap<bool> cs(graph);
deba@2462
   121
    
deba@2462
   122
    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
deba@2462
   123
    
deba@2462
   124
    for (UEdgeIt it(graph); it != INVALID; ++it) {
deba@2462
   125
      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
deba@2462
   126
    }
deba@2462
   127
    
deba@2462
   128
    for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2462
   129
      int num = 0;
deba@2462
   130
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2462
   131
        if (mm[jt]) ++num;
deba@2462
   132
      }
deba@2462
   133
      check(num <= 1, "INVALID PRIMAL");
deba@2462
   134
    }
deba@2462
   135
    max_cardinality = bpmatch.matchingSize();
deba@2462
   136
  }
deba@2462
   137
deba@2462
   138
  {
deba@2463
   139
    Graph::ANodeMap<UEdge> mm(graph);
deba@2058
   140
deba@2058
   141
    check(max_cardinality == maxBipartiteMatching(graph, mm),
deba@2058
   142
          "WRONG MATCHING");
deba@2058
   143
    
deba@2463
   144
    for (BNodeIt it(graph); it != INVALID; ++it) {
deba@2058
   145
      int num = 0;
deba@2463
   146
      
deba@2058
   147
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2463
   148
        if (mm[graph.aNode(jt)] == jt) ++num;
deba@2463
   149
      }
deba@2463
   150
      check(num <= 1, "INVALID PRIMAL");
deba@2463
   151
    }
deba@2463
   152
  }
deba@2463
   153
deba@2463
   154
  {
deba@2463
   155
    Graph::ANodeMap<UEdge> mm(graph);
deba@2463
   156
deba@2463
   157
    check(max_cardinality == prBipartiteMatching(graph, mm),
deba@2463
   158
          "WRONG MATCHING");
deba@2463
   159
    
deba@2463
   160
    for (BNodeIt it(graph); it != INVALID; ++it) {
deba@2463
   161
      int num = 0;
deba@2463
   162
      
deba@2463
   163
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2463
   164
        if (mm[graph.aNode(jt)] == jt) ++num;
deba@2058
   165
      }
deba@2058
   166
      check(num <= 1, "INVALID PRIMAL");
deba@2058
   167
    }
deba@2058
   168
  }
deba@2058
   169
deba@2058
   170
  {
deba@2040
   171
    MaxBipartiteMatching<Graph> bpmatch(graph);
deba@2040
   172
deba@2040
   173
    bpmatch.greedyInit();
deba@2040
   174
    bpmatch.start();
deba@2040
   175
deba@2040
   176
    Graph::UEdgeMap<bool> mm(graph);
deba@2040
   177
    Graph::NodeMap<bool> cs(graph);
deba@2040
   178
deba@2040
   179
    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
deba@2040
   180
    
deba@2040
   181
    for (UEdgeIt it(graph); it != INVALID; ++it) {
deba@2040
   182
      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
deba@2040
   183
    }
deba@2040
   184
    
deba@2040
   185
    for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2040
   186
      int num = 0;
deba@2040
   187
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2040
   188
        if (mm[jt]) ++num;
deba@2040
   189
    }
deba@2040
   190
      check(num <= 1, "INVALID PRIMAL");
deba@2040
   191
    }
deba@2040
   192
  }
deba@2040
   193
deba@2040
   194
  {
deba@2040
   195
    MaxBipartiteMatching<Graph> bpmatch(graph);
deba@2040
   196
deba@2040
   197
    bpmatch.greedyInit();
deba@2618
   198
    while (bpmatch.simpleAugment()) { }
deba@2040
   199
    
deba@2040
   200
    Graph::UEdgeMap<bool> mm(graph);
deba@2040
   201
    Graph::NodeMap<bool> cs(graph);
deba@2040
   202
    
deba@2040
   203
    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
deba@2040
   204
    
deba@2040
   205
    for (UEdgeIt it(graph); it != INVALID; ++it) {
deba@2040
   206
      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
deba@2040
   207
    }
deba@2040
   208
    
deba@2040
   209
    for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2040
   210
      int num = 0;
deba@2040
   211
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2040
   212
        if (mm[jt]) ++num;
deba@2040
   213
    }
deba@2040
   214
      check(num <= 1, "INVALID PRIMAL");
deba@2040
   215
    }
deba@2040
   216
  }
deba@2040
   217
deba@2040
   218
  {
deba@2051
   219
    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
deba@2051
   220
deba@2051
   221
    bpmatch.init();
deba@2051
   222
deba@2051
   223
    max_weight = 0;
deba@2051
   224
    while (bpmatch.augment(true)) {
deba@2051
   225
    
deba@2051
   226
      Graph::UEdgeMap<bool> mm(graph);
deba@2051
   227
      Graph::NodeMap<int> pm(graph);
deba@2051
   228
      
deba@2051
   229
      bpmatch.matching(mm);
deba@2051
   230
      bpmatch.potential(pm);
deba@2051
   231
      
deba@2051
   232
      for (UEdgeIt it(graph); it != INVALID; ++it) {
deba@2051
   233
        if (mm[it]) {
deba@2058
   234
          check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
deba@2051
   235
                "INVALID DUAL");
deba@2051
   236
        } else {
deba@2058
   237
          check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
deba@2051
   238
                "INVALID DUAL");
deba@2051
   239
        }
deba@2051
   240
      }
deba@2051
   241
deba@2051
   242
      for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2051
   243
        int num = 0;
deba@2051
   244
        for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2051
   245
          if (mm[jt]) ++num;
deba@2051
   246
        }
deba@2051
   247
        check(num <= 1, "INVALID PRIMAL");
deba@2051
   248
      }
deba@2051
   249
      if (bpmatch.matchingValue() > max_weight) {
deba@2051
   250
        max_weight = bpmatch.matchingValue();
deba@2051
   251
      }
deba@2051
   252
    }
deba@2051
   253
  }
deba@2051
   254
deba@2051
   255
  {
deba@2058
   256
    Graph::UEdgeMap<bool> mm(graph);
deba@2058
   257
deba@2058
   258
    check(max_weight == maxWeightedBipartiteMatching(graph, weight, mm),
deba@2058
   259
          "WRONG MATCHING");
deba@2058
   260
    
deba@2058
   261
    for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2058
   262
      int num = 0;
deba@2058
   263
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2058
   264
        if (mm[jt]) ++num;
deba@2058
   265
      }
deba@2058
   266
      check(num <= 1, "INVALID PRIMAL");
deba@2058
   267
    }
deba@2058
   268
  }
deba@2058
   269
deba@2058
   270
  {
deba@2051
   271
    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
deba@2040
   272
deba@2040
   273
    bpmatch.run();
deba@2051
   274
    
deba@2051
   275
    Graph::UEdgeMap<bool> mm(graph);
deba@2051
   276
    Graph::NodeMap<int> pm(graph);
deba@2040
   277
deba@2051
   278
    bpmatch.matching(mm);
deba@2051
   279
    bpmatch.potential(pm);
deba@2040
   280
    
deba@2040
   281
    for (UEdgeIt it(graph); it != INVALID; ++it) {
deba@2051
   282
      if (mm[it]) {
deba@2058
   283
        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
deba@2051
   284
              "INVALID DUAL");
deba@2051
   285
      } else {
deba@2058
   286
        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
deba@2051
   287
              "INVALID DUAL");
deba@2051
   288
      }
deba@2040
   289
    }
deba@2051
   290
deba@2040
   291
    for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2040
   292
      int num = 0;
deba@2040
   293
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2040
   294
        if (mm[jt]) ++num;
deba@2040
   295
    }
deba@2040
   296
      check(num <= 1, "INVALID PRIMAL");
deba@2040
   297
    }
deba@2051
   298
    check(max_weight == bpmatch.matchingValue(), "WRONG WEIGHT");
deba@2051
   299
  }
deba@2051
   300
deba@2051
   301
  {
deba@2051
   302
    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
deba@2051
   303
deba@2051
   304
    bpmatch.run(true);
deba@2051
   305
    
deba@2051
   306
    Graph::UEdgeMap<bool> mm(graph);
deba@2051
   307
    Graph::NodeMap<int> pm(graph);
deba@2051
   308
deba@2051
   309
    bpmatch.matching(mm);
deba@2051
   310
    bpmatch.potential(pm);
deba@2051
   311
    
deba@2051
   312
    for (UEdgeIt it(graph); it != INVALID; ++it) {
deba@2051
   313
      if (mm[it]) {
deba@2058
   314
        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
deba@2051
   315
              "INVALID DUAL");
deba@2051
   316
      } else {
deba@2058
   317
        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
deba@2051
   318
              "INVALID DUAL");
deba@2051
   319
      }
deba@2051
   320
    }
deba@2051
   321
deba@2051
   322
    for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2051
   323
      int num = 0;
deba@2051
   324
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2051
   325
        if (mm[jt]) ++num;
deba@2051
   326
    }
deba@2051
   327
      check(num <= 1, "INVALID PRIMAL");
deba@2051
   328
    }
deba@2051
   329
    check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
deba@2051
   330
    max_cardinality_max_weight = bpmatch.matchingValue();
deba@2051
   331
deba@2051
   332
  }
deba@2051
   333
deba@2051
   334
  {
deba@2058
   335
    Graph::UEdgeMap<bool> mm(graph);
deba@2051
   336
deba@2058
   337
    check(max_cardinality_max_weight == 
deba@2058
   338
          maxWeightedMaxBipartiteMatching(graph, weight, 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@2058
   350
  Graph::UEdgeMap<int> cost(graph);
alpar@2571
   351
  cost = subMap(constMap<UEdge>(CC), weight);
deba@2058
   352
  {
deba@2051
   353
deba@2051
   354
    MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost);
deba@2051
   355
deba@2051
   356
    bpmatch.run();
deba@2051
   357
    
deba@2051
   358
    Graph::UEdgeMap<bool> mm(graph);
deba@2051
   359
    Graph::NodeMap<int> pm(graph);
deba@2051
   360
deba@2051
   361
    bpmatch.matching(mm);
deba@2051
   362
    bpmatch.potential(pm);
deba@2051
   363
    
deba@2137
   364
    min_cost_matching = bpmatch.matchingCost();
deba@2137
   365
    check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
alpar@2571
   366
    check(max_cardinality * CC - max_cardinality_max_weight 
deba@2137
   367
          == bpmatch.matchingCost(), "WRONG SIZE");
deba@2137
   368
deba@2051
   369
    for (UEdgeIt it(graph); it != INVALID; ++it) {
deba@2051
   370
      if (mm[it]) {
deba@2051
   371
        check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] == 0,
deba@2051
   372
              "INVALID DUAL");
deba@2051
   373
      } else {
deba@2051
   374
        check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] >= 0,
deba@2051
   375
              "INVALID DUAL");
deba@2051
   376
      }
deba@2051
   377
    }
deba@2051
   378
deba@2051
   379
    for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2051
   380
      int num = 0;
deba@2051
   381
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2051
   382
        if (mm[jt]) ++num;
deba@2051
   383
    }
deba@2051
   384
      check(num <= 1, "INVALID PRIMAL");
deba@2051
   385
    }
deba@2051
   386
deba@2058
   387
    min_cost_matching = bpmatch.matchingCost();
deba@2051
   388
    check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
alpar@2571
   389
    check(max_cardinality * CC - max_cardinality_max_weight 
deba@2051
   390
          == bpmatch.matchingCost(), "WRONG SIZE");
deba@2051
   391
deba@2040
   392
  }
deba@2040
   393
deba@2058
   394
  {
deba@2058
   395
    Graph::UEdgeMap<bool> mm(graph);
deba@2058
   396
deba@2058
   397
    check(min_cost_matching == 
deba@2058
   398
          minCostMaxBipartiteMatching(graph, cost, mm),
deba@2058
   399
          "WRONG MATCHING");
deba@2058
   400
    
deba@2058
   401
    for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2058
   402
      int num = 0;
deba@2058
   403
      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2058
   404
        if (mm[jt]) ++num;
deba@2058
   405
      }
deba@2058
   406
      check(num <= 1, "INVALID PRIMAL");
deba@2058
   407
    }
deba@2058
   408
  }
deba@2058
   409
deba@2040
   410
  return 0;
deba@2040
   411
}