test/max_matching_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 17 Apr 2009 18:04:36 +0200
changeset 609 e6927fe719e6
parent 327 91d63b8b1a4c
child 590 b61354458b59
permissions -rw-r--r--
Support >= and <= constraints in NetworkSimplex (#219, #234)

By default the same inequality constraints are supported as by
Circulation (the GEQ form), but the LEQ form can also be selected
using the problemType() function.

The documentation of the min. cost flow module is reworked and
extended with important notes and explanations about the different
variants of the problem and about the dual solution and optimality
conditions.
deba@326
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@326
     2
 *
deba@326
     3
 * This file is a part of LEMON, a generic C++ optimization library.
deba@326
     4
 *
alpar@440
     5
 * Copyright (C) 2003-2009
deba@326
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@326
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@326
     8
 *
deba@326
     9
 * Permission to use, modify and distribute this software is granted
deba@326
    10
 * provided that this copyright notice appears in all copies. For
deba@326
    11
 * precise terms see the accompanying LICENSE file.
deba@326
    12
 *
deba@326
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@326
    14
 * express or implied, and with no claim as to its suitability for any
deba@326
    15
 * purpose.
deba@326
    16
 *
deba@326
    17
 */
deba@326
    18
deba@326
    19
#include <iostream>
deba@327
    20
#include <sstream>
deba@326
    21
#include <vector>
deba@326
    22
#include <queue>
deba@326
    23
#include <lemon/math.h>
deba@326
    24
#include <cstdlib>
deba@326
    25
deba@327
    26
#include <lemon/max_matching.h>
deba@327
    27
#include <lemon/smart_graph.h>
deba@327
    28
#include <lemon/lgf_reader.h>
deba@327
    29
deba@326
    30
#include "test_tools.h"
deba@326
    31
deba@326
    32
using namespace std;
deba@326
    33
using namespace lemon;
deba@326
    34
deba@327
    35
GRAPH_TYPEDEFS(SmartGraph);
deba@327
    36
deba@327
    37
deba@327
    38
const int lgfn = 3;
deba@327
    39
const std::string lgf[lgfn] = {
deba@327
    40
  "@nodes\n"
deba@327
    41
  "label\n"
deba@327
    42
  "0\n"
deba@327
    43
  "1\n"
deba@327
    44
  "2\n"
deba@327
    45
  "3\n"
deba@327
    46
  "4\n"
deba@327
    47
  "5\n"
deba@327
    48
  "6\n"
deba@327
    49
  "7\n"
deba@327
    50
  "@edges\n"
deba@327
    51
  "     label  weight\n"
deba@327
    52
  "7 4  0      984\n"
deba@327
    53
  "0 7  1      73\n"
deba@327
    54
  "7 1  2      204\n"
deba@327
    55
  "2 3  3      583\n"
deba@327
    56
  "2 7  4      565\n"
deba@327
    57
  "2 1  5      582\n"
deba@327
    58
  "0 4  6      551\n"
deba@327
    59
  "2 5  7      385\n"
deba@327
    60
  "1 5  8      561\n"
deba@327
    61
  "5 3  9      484\n"
deba@327
    62
  "7 5  10     904\n"
deba@327
    63
  "3 6  11     47\n"
deba@327
    64
  "7 6  12     888\n"
deba@327
    65
  "3 0  13     747\n"
deba@327
    66
  "6 1  14     310\n",
deba@327
    67
deba@327
    68
  "@nodes\n"
deba@327
    69
  "label\n"
deba@327
    70
  "0\n"
deba@327
    71
  "1\n"
deba@327
    72
  "2\n"
deba@327
    73
  "3\n"
deba@327
    74
  "4\n"
deba@327
    75
  "5\n"
deba@327
    76
  "6\n"
deba@327
    77
  "7\n"
deba@327
    78
  "@edges\n"
deba@327
    79
  "     label  weight\n"
deba@327
    80
  "2 5  0      710\n"
deba@327
    81
  "0 5  1      241\n"
deba@327
    82
  "2 4  2      856\n"
deba@327
    83
  "2 6  3      762\n"
deba@327
    84
  "4 1  4      747\n"
deba@327
    85
  "6 1  5      962\n"
deba@327
    86
  "4 7  6      723\n"
deba@327
    87
  "1 7  7      661\n"
deba@327
    88
  "2 3  8      376\n"
deba@327
    89
  "1 0  9      416\n"
deba@327
    90
  "6 7  10     391\n",
deba@327
    91
deba@327
    92
  "@nodes\n"
deba@327
    93
  "label\n"
deba@327
    94
  "0\n"
deba@327
    95
  "1\n"
deba@327
    96
  "2\n"
deba@327
    97
  "3\n"
deba@327
    98
  "4\n"
deba@327
    99
  "5\n"
deba@327
   100
  "6\n"
deba@327
   101
  "7\n"
deba@327
   102
  "@edges\n"
deba@327
   103
  "     label  weight\n"
deba@327
   104
  "6 2  0      553\n"
deba@327
   105
  "0 7  1      653\n"
deba@327
   106
  "6 3  2      22\n"
deba@327
   107
  "4 7  3      846\n"
deba@327
   108
  "7 2  4      981\n"
deba@327
   109
  "7 6  5      250\n"
deba@327
   110
  "5 2  6      539\n",
deba@327
   111
};
deba@327
   112
deba@327
   113
void checkMatching(const SmartGraph& graph,
deba@327
   114
                   const MaxMatching<SmartGraph>& mm) {
deba@327
   115
  int num = 0;
deba@327
   116
deba@327
   117
  IntNodeMap comp_index(graph);
deba@327
   118
  UnionFind<IntNodeMap> comp(comp_index);
deba@327
   119
deba@327
   120
  int barrier_num = 0;
deba@327
   121
deba@327
   122
  for (NodeIt n(graph); n != INVALID; ++n) {
deba@327
   123
    check(mm.decomposition(n) == MaxMatching<SmartGraph>::EVEN ||
deba@327
   124
          mm.matching(n) != INVALID, "Wrong Gallai-Edmonds decomposition");
deba@327
   125
    if (mm.decomposition(n) == MaxMatching<SmartGraph>::ODD) {
deba@327
   126
      ++barrier_num;
deba@327
   127
    } else {
deba@327
   128
      comp.insert(n);
deba@327
   129
    }
deba@327
   130
  }
deba@327
   131
deba@327
   132
  for (EdgeIt e(graph); e != INVALID; ++e) {
deba@327
   133
    if (mm.matching(e)) {
deba@327
   134
      check(e == mm.matching(graph.u(e)), "Wrong matching");
deba@327
   135
      check(e == mm.matching(graph.v(e)), "Wrong matching");
deba@327
   136
      ++num;
deba@327
   137
    }
deba@327
   138
    check(mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::EVEN ||
deba@327
   139
          mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::MATCHED,
deba@327
   140
          "Wrong Gallai-Edmonds decomposition");
deba@327
   141
deba@327
   142
    check(mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::EVEN ||
deba@327
   143
          mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::MATCHED,
deba@327
   144
          "Wrong Gallai-Edmonds decomposition");
deba@327
   145
deba@327
   146
    if (mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::ODD &&
deba@327
   147
        mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::ODD) {
deba@327
   148
      comp.join(graph.u(e), graph.v(e));
deba@327
   149
    }
deba@327
   150
  }
deba@327
   151
deba@327
   152
  std::set<int> comp_root;
deba@327
   153
  int odd_comp_num = 0;
deba@327
   154
  for (NodeIt n(graph); n != INVALID; ++n) {
deba@327
   155
    if (mm.decomposition(n) != MaxMatching<SmartGraph>::ODD) {
deba@327
   156
      int root = comp.find(n);
deba@327
   157
      if (comp_root.find(root) == comp_root.end()) {
deba@327
   158
        comp_root.insert(root);
deba@327
   159
        if (comp.size(n) % 2 == 1) {
deba@327
   160
          ++odd_comp_num;
deba@327
   161
        }
deba@327
   162
      }
deba@327
   163
    }
deba@327
   164
  }
deba@327
   165
deba@327
   166
  check(mm.matchingSize() == num, "Wrong matching");
deba@327
   167
  check(2 * num == countNodes(graph) - (odd_comp_num - barrier_num),
deba@327
   168
         "Wrong matching");
deba@327
   169
  return;
deba@327
   170
}
deba@327
   171
deba@327
   172
void checkWeightedMatching(const SmartGraph& graph,
deba@327
   173
                   const SmartGraph::EdgeMap<int>& weight,
deba@327
   174
                   const MaxWeightedMatching<SmartGraph>& mwm) {
deba@327
   175
  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
deba@327
   176
    if (graph.u(e) == graph.v(e)) continue;
deba@327
   177
    int rw = mwm.nodeValue(graph.u(e)) + mwm.nodeValue(graph.v(e));
deba@327
   178
deba@327
   179
    for (int i = 0; i < mwm.blossomNum(); ++i) {
deba@327
   180
      bool s = false, t = false;
deba@327
   181
      for (MaxWeightedMatching<SmartGraph>::BlossomIt n(mwm, i);
deba@327
   182
           n != INVALID; ++n) {
deba@327
   183
        if (graph.u(e) == n) s = true;
deba@327
   184
        if (graph.v(e) == n) t = true;
deba@327
   185
      }
deba@327
   186
      if (s == true && t == true) {
deba@327
   187
        rw += mwm.blossomValue(i);
deba@327
   188
      }
deba@327
   189
    }
deba@327
   190
    rw -= weight[e] * mwm.dualScale;
deba@327
   191
deba@327
   192
    check(rw >= 0, "Negative reduced weight");
deba@327
   193
    check(rw == 0 || !mwm.matching(e),
deba@327
   194
          "Non-zero reduced weight on matching edge");
deba@327
   195
  }
deba@327
   196
deba@327
   197
  int pv = 0;
deba@327
   198
  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@327
   199
    if (mwm.matching(n) != INVALID) {
deba@327
   200
      check(mwm.nodeValue(n) >= 0, "Invalid node value");
deba@327
   201
      pv += weight[mwm.matching(n)];
deba@327
   202
      SmartGraph::Node o = graph.target(mwm.matching(n));
deba@327
   203
      check(mwm.mate(n) == o, "Invalid matching");
deba@327
   204
      check(mwm.matching(n) == graph.oppositeArc(mwm.matching(o)),
deba@327
   205
            "Invalid matching");
deba@327
   206
    } else {
deba@327
   207
      check(mwm.mate(n) == INVALID, "Invalid matching");
deba@327
   208
      check(mwm.nodeValue(n) == 0, "Invalid matching");
deba@327
   209
    }
deba@327
   210
  }
deba@327
   211
deba@327
   212
  int dv = 0;
deba@327
   213
  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@327
   214
    dv += mwm.nodeValue(n);
deba@327
   215
  }
deba@327
   216
deba@327
   217
  for (int i = 0; i < mwm.blossomNum(); ++i) {
deba@327
   218
    check(mwm.blossomValue(i) >= 0, "Invalid blossom value");
deba@327
   219
    check(mwm.blossomSize(i) % 2 == 1, "Even blossom size");
deba@327
   220
    dv += mwm.blossomValue(i) * ((mwm.blossomSize(i) - 1) / 2);
deba@327
   221
  }
deba@327
   222
deba@327
   223
  check(pv * mwm.dualScale == dv * 2, "Wrong duality");
deba@327
   224
deba@327
   225
  return;
deba@327
   226
}
deba@327
   227
deba@327
   228
void checkWeightedPerfectMatching(const SmartGraph& graph,
deba@327
   229
                          const SmartGraph::EdgeMap<int>& weight,
deba@327
   230
                          const MaxWeightedPerfectMatching<SmartGraph>& mwpm) {
deba@327
   231
  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
deba@327
   232
    if (graph.u(e) == graph.v(e)) continue;
deba@327
   233
    int rw = mwpm.nodeValue(graph.u(e)) + mwpm.nodeValue(graph.v(e));
deba@327
   234
deba@327
   235
    for (int i = 0; i < mwpm.blossomNum(); ++i) {
deba@327
   236
      bool s = false, t = false;
deba@327
   237
      for (MaxWeightedPerfectMatching<SmartGraph>::BlossomIt n(mwpm, i);
deba@327
   238
           n != INVALID; ++n) {
deba@327
   239
        if (graph.u(e) == n) s = true;
deba@327
   240
        if (graph.v(e) == n) t = true;
deba@327
   241
      }
deba@327
   242
      if (s == true && t == true) {
deba@327
   243
        rw += mwpm.blossomValue(i);
deba@327
   244
      }
deba@327
   245
    }
deba@327
   246
    rw -= weight[e] * mwpm.dualScale;
deba@327
   247
deba@327
   248
    check(rw >= 0, "Negative reduced weight");
deba@327
   249
    check(rw == 0 || !mwpm.matching(e),
deba@327
   250
          "Non-zero reduced weight on matching edge");
deba@327
   251
  }
deba@327
   252
deba@327
   253
  int pv = 0;
deba@327
   254
  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@327
   255
    check(mwpm.matching(n) != INVALID, "Non perfect");
deba@327
   256
    pv += weight[mwpm.matching(n)];
deba@327
   257
    SmartGraph::Node o = graph.target(mwpm.matching(n));
deba@327
   258
    check(mwpm.mate(n) == o, "Invalid matching");
deba@327
   259
    check(mwpm.matching(n) == graph.oppositeArc(mwpm.matching(o)),
deba@327
   260
          "Invalid matching");
deba@327
   261
  }
deba@327
   262
deba@327
   263
  int dv = 0;
deba@327
   264
  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@327
   265
    dv += mwpm.nodeValue(n);
deba@327
   266
  }
deba@327
   267
deba@327
   268
  for (int i = 0; i < mwpm.blossomNum(); ++i) {
deba@327
   269
    check(mwpm.blossomValue(i) >= 0, "Invalid blossom value");
deba@327
   270
    check(mwpm.blossomSize(i) % 2 == 1, "Even blossom size");
deba@327
   271
    dv += mwpm.blossomValue(i) * ((mwpm.blossomSize(i) - 1) / 2);
deba@327
   272
  }
deba@327
   273
deba@327
   274
  check(pv * mwpm.dualScale == dv * 2, "Wrong duality");
deba@327
   275
deba@327
   276
  return;
deba@327
   277
}
deba@327
   278
deba@327
   279
deba@326
   280
int main() {
deba@326
   281
deba@327
   282
  for (int i = 0; i < lgfn; ++i) {
deba@327
   283
    SmartGraph graph;
deba@327
   284
    SmartGraph::EdgeMap<int> weight(graph);
deba@326
   285
deba@327
   286
    istringstream lgfs(lgf[i]);
deba@327
   287
    graphReader(graph, lgfs).
deba@327
   288
      edgeMap("weight", weight).run();
deba@326
   289
deba@327
   290
    MaxMatching<SmartGraph> mm(graph);
deba@327
   291
    mm.run();
deba@327
   292
    checkMatching(graph, mm);
deba@326
   293
deba@327
   294
    MaxWeightedMatching<SmartGraph> mwm(graph, weight);
deba@327
   295
    mwm.run();
deba@327
   296
    checkWeightedMatching(graph, weight, mwm);
deba@326
   297
deba@327
   298
    MaxWeightedPerfectMatching<SmartGraph> mwpm(graph, weight);
deba@327
   299
    bool perfect = mwpm.run();
deba@326
   300
deba@327
   301
    check(perfect == (mm.matchingSize() * 2 == countNodes(graph)),
deba@327
   302
          "Perfect matching found");
deba@326
   303
deba@327
   304
    if (perfect) {
deba@327
   305
      checkWeightedPerfectMatching(graph, weight, mwpm);
deba@326
   306
    }
deba@326
   307
  }
deba@326
   308
deba@326
   309
  return 0;
deba@326
   310
}