test/fractional_matching_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Fri, 25 Jun 2010 06:20:28 +0200
branch1.2
changeset 896 e958855b8186
parent 872 41d7ac528c3a
child 965 00f8d9f9920d
permissions -rw-r--r--
Merge bugfix #371 to branch 1.2
deba@869
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@869
     2
 *
deba@869
     3
 * This file is a part of LEMON, a generic C++ optimization library.
deba@869
     4
 *
alpar@877
     5
 * Copyright (C) 2003-2010
deba@869
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@869
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@869
     8
 *
deba@869
     9
 * Permission to use, modify and distribute this software is granted
deba@869
    10
 * provided that this copyright notice appears in all copies. For
deba@869
    11
 * precise terms see the accompanying LICENSE file.
deba@869
    12
 *
deba@869
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@869
    14
 * express or implied, and with no claim as to its suitability for any
deba@869
    15
 * purpose.
deba@869
    16
 *
deba@869
    17
 */
deba@869
    18
deba@869
    19
#include <iostream>
deba@869
    20
#include <sstream>
deba@869
    21
#include <vector>
deba@869
    22
#include <queue>
deba@869
    23
#include <cstdlib>
deba@869
    24
deba@869
    25
#include <lemon/fractional_matching.h>
deba@869
    26
#include <lemon/smart_graph.h>
deba@869
    27
#include <lemon/concepts/graph.h>
deba@869
    28
#include <lemon/concepts/maps.h>
deba@869
    29
#include <lemon/lgf_reader.h>
deba@869
    30
#include <lemon/math.h>
deba@869
    31
deba@869
    32
#include "test_tools.h"
deba@869
    33
deba@869
    34
using namespace std;
deba@869
    35
using namespace lemon;
deba@869
    36
deba@869
    37
GRAPH_TYPEDEFS(SmartGraph);
deba@869
    38
deba@869
    39
deba@869
    40
const int lgfn = 4;
deba@869
    41
const std::string lgf[lgfn] = {
deba@869
    42
  "@nodes\n"
deba@869
    43
  "label\n"
deba@869
    44
  "0\n"
deba@869
    45
  "1\n"
deba@869
    46
  "2\n"
deba@869
    47
  "3\n"
deba@869
    48
  "4\n"
deba@869
    49
  "5\n"
deba@869
    50
  "6\n"
deba@869
    51
  "7\n"
deba@869
    52
  "@edges\n"
deba@869
    53
  "     label  weight\n"
deba@869
    54
  "7 4  0      984\n"
deba@869
    55
  "0 7  1      73\n"
deba@869
    56
  "7 1  2      204\n"
deba@869
    57
  "2 3  3      583\n"
deba@869
    58
  "2 7  4      565\n"
deba@869
    59
  "2 1  5      582\n"
deba@869
    60
  "0 4  6      551\n"
deba@869
    61
  "2 5  7      385\n"
deba@869
    62
  "1 5  8      561\n"
deba@869
    63
  "5 3  9      484\n"
deba@869
    64
  "7 5  10     904\n"
deba@869
    65
  "3 6  11     47\n"
deba@869
    66
  "7 6  12     888\n"
deba@869
    67
  "3 0  13     747\n"
deba@869
    68
  "6 1  14     310\n",
deba@869
    69
deba@869
    70
  "@nodes\n"
deba@869
    71
  "label\n"
deba@869
    72
  "0\n"
deba@869
    73
  "1\n"
deba@869
    74
  "2\n"
deba@869
    75
  "3\n"
deba@869
    76
  "4\n"
deba@869
    77
  "5\n"
deba@869
    78
  "6\n"
deba@869
    79
  "7\n"
deba@869
    80
  "@edges\n"
deba@869
    81
  "     label  weight\n"
deba@869
    82
  "2 5  0      710\n"
deba@869
    83
  "0 5  1      241\n"
deba@869
    84
  "2 4  2      856\n"
deba@869
    85
  "2 6  3      762\n"
deba@869
    86
  "4 1  4      747\n"
deba@869
    87
  "6 1  5      962\n"
deba@869
    88
  "4 7  6      723\n"
deba@869
    89
  "1 7  7      661\n"
deba@869
    90
  "2 3  8      376\n"
deba@869
    91
  "1 0  9      416\n"
deba@869
    92
  "6 7  10     391\n",
deba@869
    93
deba@869
    94
  "@nodes\n"
deba@869
    95
  "label\n"
deba@869
    96
  "0\n"
deba@869
    97
  "1\n"
deba@869
    98
  "2\n"
deba@869
    99
  "3\n"
deba@869
   100
  "4\n"
deba@869
   101
  "5\n"
deba@869
   102
  "6\n"
deba@869
   103
  "7\n"
deba@869
   104
  "@edges\n"
deba@869
   105
  "     label  weight\n"
deba@869
   106
  "6 2  0      553\n"
deba@869
   107
  "0 7  1      653\n"
deba@869
   108
  "6 3  2      22\n"
deba@869
   109
  "4 7  3      846\n"
deba@869
   110
  "7 2  4      981\n"
deba@869
   111
  "7 6  5      250\n"
deba@869
   112
  "5 2  6      539\n",
deba@869
   113
deba@869
   114
  "@nodes\n"
deba@869
   115
  "label\n"
deba@869
   116
  "0\n"
deba@869
   117
  "@edges\n"
deba@869
   118
  "     label  weight\n"
deba@869
   119
  "0 0  0      100\n"
deba@869
   120
};
deba@869
   121
deba@869
   122
void checkMaxFractionalMatchingCompile()
deba@869
   123
{
deba@869
   124
  typedef concepts::Graph Graph;
deba@869
   125
  typedef Graph::Node Node;
deba@869
   126
  typedef Graph::Edge Edge;
deba@869
   127
deba@869
   128
  Graph g;
deba@869
   129
  Node n;
deba@869
   130
  Edge e;
deba@869
   131
deba@869
   132
  MaxFractionalMatching<Graph> mat_test(g);
deba@869
   133
  const MaxFractionalMatching<Graph>&
deba@869
   134
    const_mat_test = mat_test;
deba@869
   135
deba@869
   136
  mat_test.init();
deba@869
   137
  mat_test.start();
deba@869
   138
  mat_test.start(true);
deba@869
   139
  mat_test.startPerfect();
deba@869
   140
  mat_test.startPerfect(true);
deba@869
   141
  mat_test.run();
deba@869
   142
  mat_test.run(true);
deba@869
   143
  mat_test.runPerfect();
deba@869
   144
  mat_test.runPerfect(true);
deba@869
   145
deba@869
   146
  const_mat_test.matchingSize();
deba@869
   147
  const_mat_test.matching(e);
deba@869
   148
  const_mat_test.matching(n);
deba@869
   149
  const MaxFractionalMatching<Graph>::MatchingMap& mmap =
deba@869
   150
    const_mat_test.matchingMap();
deba@869
   151
  e = mmap[n];
deba@869
   152
deba@869
   153
  const_mat_test.barrier(n);
deba@869
   154
}
deba@869
   155
deba@869
   156
void checkMaxWeightedFractionalMatchingCompile()
deba@869
   157
{
deba@869
   158
  typedef concepts::Graph Graph;
deba@869
   159
  typedef Graph::Node Node;
deba@869
   160
  typedef Graph::Edge Edge;
deba@869
   161
  typedef Graph::EdgeMap<int> WeightMap;
deba@869
   162
deba@869
   163
  Graph g;
deba@869
   164
  Node n;
deba@869
   165
  Edge e;
deba@869
   166
  WeightMap w(g);
deba@869
   167
deba@869
   168
  MaxWeightedFractionalMatching<Graph> mat_test(g, w);
deba@869
   169
  const MaxWeightedFractionalMatching<Graph>&
deba@869
   170
    const_mat_test = mat_test;
deba@869
   171
deba@869
   172
  mat_test.init();
deba@869
   173
  mat_test.start();
deba@869
   174
  mat_test.run();
deba@869
   175
deba@869
   176
  const_mat_test.matchingWeight();
deba@869
   177
  const_mat_test.matchingSize();
deba@869
   178
  const_mat_test.matching(e);
deba@869
   179
  const_mat_test.matching(n);
deba@869
   180
  const MaxWeightedFractionalMatching<Graph>::MatchingMap& mmap =
deba@869
   181
    const_mat_test.matchingMap();
deba@869
   182
  e = mmap[n];
deba@869
   183
deba@869
   184
  const_mat_test.dualValue();
deba@869
   185
  const_mat_test.nodeValue(n);
deba@869
   186
}
deba@869
   187
deba@869
   188
void checkMaxWeightedPerfectFractionalMatchingCompile()
deba@869
   189
{
deba@869
   190
  typedef concepts::Graph Graph;
deba@869
   191
  typedef Graph::Node Node;
deba@869
   192
  typedef Graph::Edge Edge;
deba@869
   193
  typedef Graph::EdgeMap<int> WeightMap;
deba@869
   194
deba@869
   195
  Graph g;
deba@869
   196
  Node n;
deba@869
   197
  Edge e;
deba@869
   198
  WeightMap w(g);
deba@869
   199
deba@869
   200
  MaxWeightedPerfectFractionalMatching<Graph> mat_test(g, w);
deba@869
   201
  const MaxWeightedPerfectFractionalMatching<Graph>&
deba@869
   202
    const_mat_test = mat_test;
deba@869
   203
deba@869
   204
  mat_test.init();
deba@869
   205
  mat_test.start();
deba@869
   206
  mat_test.run();
deba@869
   207
deba@869
   208
  const_mat_test.matchingWeight();
deba@869
   209
  const_mat_test.matching(e);
deba@869
   210
  const_mat_test.matching(n);
deba@869
   211
  const MaxWeightedPerfectFractionalMatching<Graph>::MatchingMap& mmap =
deba@869
   212
    const_mat_test.matchingMap();
deba@869
   213
  e = mmap[n];
deba@869
   214
deba@869
   215
  const_mat_test.dualValue();
deba@869
   216
  const_mat_test.nodeValue(n);
deba@869
   217
}
deba@869
   218
deba@869
   219
void checkFractionalMatching(const SmartGraph& graph,
deba@869
   220
                             const MaxFractionalMatching<SmartGraph>& mfm,
deba@869
   221
                             bool allow_loops = true) {
deba@869
   222
  int pv = 0;
deba@869
   223
  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@869
   224
    int indeg = 0;
deba@869
   225
    for (InArcIt a(graph, n); a != INVALID; ++a) {
deba@869
   226
      if (mfm.matching(graph.source(a)) == a) {
deba@869
   227
        ++indeg;
deba@869
   228
      }
deba@869
   229
    }
deba@869
   230
    if (mfm.matching(n) != INVALID) {
deba@869
   231
      check(indeg == 1, "Invalid matching");
deba@869
   232
      ++pv;
deba@869
   233
    } else {
deba@869
   234
      check(indeg == 0, "Invalid matching");
deba@869
   235
    }
deba@869
   236
  }
deba@869
   237
  check(pv == mfm.matchingSize(), "Wrong matching size");
deba@869
   238
deba@872
   239
  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
deba@872
   240
    check((e == mfm.matching(graph.u(e)) ? 1 : 0) +
alpar@877
   241
          (e == mfm.matching(graph.v(e)) ? 1 : 0) ==
deba@872
   242
          mfm.matching(e), "Invalid matching");
deba@872
   243
  }
deba@872
   244
deba@869
   245
  SmartGraph::NodeMap<bool> processed(graph, false);
deba@869
   246
  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@869
   247
    if (processed[n]) continue;
deba@869
   248
    processed[n] = true;
deba@869
   249
    if (mfm.matching(n) == INVALID) continue;
deba@869
   250
    int num = 1;
deba@869
   251
    Node v = graph.target(mfm.matching(n));
deba@869
   252
    while (v != n) {
deba@869
   253
      processed[v] = true;
deba@869
   254
      ++num;
deba@869
   255
      v = graph.target(mfm.matching(v));
deba@869
   256
    }
deba@869
   257
    check(num == 2 || num % 2 == 1, "Wrong cycle size");
deba@869
   258
    check(allow_loops || num != 1, "Wrong cycle size");
deba@869
   259
  }
deba@869
   260
deba@869
   261
  int anum = 0, bnum = 0;
deba@869
   262
  SmartGraph::NodeMap<bool> neighbours(graph, false);
deba@869
   263
  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@869
   264
    if (!mfm.barrier(n)) continue;
deba@869
   265
    ++anum;
deba@869
   266
    for (SmartGraph::InArcIt a(graph, n); a != INVALID; ++a) {
deba@869
   267
      Node u = graph.source(a);
deba@869
   268
      if (!allow_loops && u == n) continue;
deba@869
   269
      if (!neighbours[u]) {
deba@869
   270
        neighbours[u] = true;
deba@869
   271
        ++bnum;
deba@869
   272
      }
deba@869
   273
    }
deba@869
   274
  }
deba@869
   275
  check(anum - bnum + mfm.matchingSize() == countNodes(graph),
deba@869
   276
        "Wrong barrier");
deba@869
   277
}
deba@869
   278
deba@869
   279
void checkPerfectFractionalMatching(const SmartGraph& graph,
deba@869
   280
                             const MaxFractionalMatching<SmartGraph>& mfm,
deba@869
   281
                             bool perfect, bool allow_loops = true) {
deba@869
   282
  if (perfect) {
deba@869
   283
    for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@869
   284
      int indeg = 0;
deba@869
   285
      for (InArcIt a(graph, n); a != INVALID; ++a) {
deba@869
   286
        if (mfm.matching(graph.source(a)) == a) {
deba@869
   287
          ++indeg;
deba@869
   288
        }
deba@869
   289
      }
deba@869
   290
      check(mfm.matching(n) != INVALID, "Invalid matching");
deba@869
   291
      check(indeg == 1, "Invalid matching");
deba@869
   292
    }
deba@872
   293
    for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
deba@872
   294
      check((e == mfm.matching(graph.u(e)) ? 1 : 0) +
alpar@877
   295
            (e == mfm.matching(graph.v(e)) ? 1 : 0) ==
deba@872
   296
            mfm.matching(e), "Invalid matching");
deba@872
   297
    }
deba@869
   298
  } else {
deba@869
   299
    int anum = 0, bnum = 0;
deba@869
   300
    SmartGraph::NodeMap<bool> neighbours(graph, false);
deba@869
   301
    for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@869
   302
      if (!mfm.barrier(n)) continue;
deba@869
   303
      ++anum;
deba@869
   304
      for (SmartGraph::InArcIt a(graph, n); a != INVALID; ++a) {
deba@869
   305
        Node u = graph.source(a);
deba@869
   306
        if (!allow_loops && u == n) continue;
deba@869
   307
        if (!neighbours[u]) {
deba@869
   308
          neighbours[u] = true;
deba@869
   309
          ++bnum;
deba@869
   310
        }
deba@869
   311
      }
deba@869
   312
    }
deba@869
   313
    check(anum - bnum > 0, "Wrong barrier");
deba@869
   314
  }
deba@869
   315
}
deba@869
   316
deba@869
   317
void checkWeightedFractionalMatching(const SmartGraph& graph,
deba@869
   318
                   const SmartGraph::EdgeMap<int>& weight,
deba@869
   319
                   const MaxWeightedFractionalMatching<SmartGraph>& mwfm,
deba@869
   320
                   bool allow_loops = true) {
deba@869
   321
  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
deba@869
   322
    if (graph.u(e) == graph.v(e) && !allow_loops) continue;
deba@869
   323
    int rw = mwfm.nodeValue(graph.u(e)) + mwfm.nodeValue(graph.v(e))
deba@869
   324
      - weight[e] * mwfm.dualScale;
deba@869
   325
deba@869
   326
    check(rw >= 0, "Negative reduced weight");
deba@869
   327
    check(rw == 0 || !mwfm.matching(e),
deba@869
   328
          "Non-zero reduced weight on matching edge");
deba@869
   329
  }
deba@869
   330
deba@869
   331
  int pv = 0;
deba@869
   332
  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@869
   333
    int indeg = 0;
deba@869
   334
    for (InArcIt a(graph, n); a != INVALID; ++a) {
deba@869
   335
      if (mwfm.matching(graph.source(a)) == a) {
deba@869
   336
        ++indeg;
deba@869
   337
      }
deba@869
   338
    }
deba@869
   339
    check(indeg <= 1, "Invalid matching");
deba@869
   340
    if (mwfm.matching(n) != INVALID) {
deba@869
   341
      check(mwfm.nodeValue(n) >= 0, "Invalid node value");
deba@869
   342
      check(indeg == 1, "Invalid matching");
deba@869
   343
      pv += weight[mwfm.matching(n)];
deba@869
   344
      SmartGraph::Node o = graph.target(mwfm.matching(n));
deba@869
   345
    } else {
deba@869
   346
      check(mwfm.nodeValue(n) == 0, "Invalid matching");
deba@869
   347
      check(indeg == 0, "Invalid matching");
deba@869
   348
    }
deba@869
   349
  }
deba@869
   350
deba@872
   351
  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
deba@872
   352
    check((e == mwfm.matching(graph.u(e)) ? 1 : 0) +
alpar@877
   353
          (e == mwfm.matching(graph.v(e)) ? 1 : 0) ==
deba@872
   354
          mwfm.matching(e), "Invalid matching");
deba@872
   355
  }
deba@872
   356
deba@869
   357
  int dv = 0;
deba@869
   358
  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@869
   359
    dv += mwfm.nodeValue(n);
deba@869
   360
  }
deba@869
   361
deba@869
   362
  check(pv * mwfm.dualScale == dv * 2, "Wrong duality");
deba@869
   363
deba@869
   364
  SmartGraph::NodeMap<bool> processed(graph, false);
deba@869
   365
  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@869
   366
    if (processed[n]) continue;
deba@869
   367
    processed[n] = true;
deba@869
   368
    if (mwfm.matching(n) == INVALID) continue;
deba@869
   369
    int num = 1;
deba@869
   370
    Node v = graph.target(mwfm.matching(n));
deba@869
   371
    while (v != n) {
deba@869
   372
      processed[v] = true;
deba@869
   373
      ++num;
deba@869
   374
      v = graph.target(mwfm.matching(v));
deba@869
   375
    }
deba@869
   376
    check(num == 2 || num % 2 == 1, "Wrong cycle size");
deba@869
   377
    check(allow_loops || num != 1, "Wrong cycle size");
deba@869
   378
  }
deba@869
   379
deba@869
   380
  return;
deba@869
   381
}
deba@869
   382
deba@869
   383
void checkWeightedPerfectFractionalMatching(const SmartGraph& graph,
deba@869
   384
                const SmartGraph::EdgeMap<int>& weight,
deba@869
   385
                const MaxWeightedPerfectFractionalMatching<SmartGraph>& mwpfm,
deba@869
   386
                bool allow_loops = true) {
deba@869
   387
  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
deba@869
   388
    if (graph.u(e) == graph.v(e) && !allow_loops) continue;
deba@869
   389
    int rw = mwpfm.nodeValue(graph.u(e)) + mwpfm.nodeValue(graph.v(e))
deba@869
   390
      - weight[e] * mwpfm.dualScale;
deba@869
   391
deba@869
   392
    check(rw >= 0, "Negative reduced weight");
deba@869
   393
    check(rw == 0 || !mwpfm.matching(e),
deba@869
   394
          "Non-zero reduced weight on matching edge");
deba@869
   395
  }
deba@869
   396
deba@869
   397
  int pv = 0;
deba@869
   398
  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@869
   399
    int indeg = 0;
deba@869
   400
    for (InArcIt a(graph, n); a != INVALID; ++a) {
deba@869
   401
      if (mwpfm.matching(graph.source(a)) == a) {
deba@869
   402
        ++indeg;
deba@869
   403
      }
deba@869
   404
    }
deba@869
   405
    check(mwpfm.matching(n) != INVALID, "Invalid perfect matching");
deba@869
   406
    check(indeg == 1, "Invalid perfect matching");
deba@869
   407
    pv += weight[mwpfm.matching(n)];
deba@869
   408
    SmartGraph::Node o = graph.target(mwpfm.matching(n));
deba@869
   409
  }
deba@869
   410
deba@872
   411
  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
deba@872
   412
    check((e == mwpfm.matching(graph.u(e)) ? 1 : 0) +
alpar@877
   413
          (e == mwpfm.matching(graph.v(e)) ? 1 : 0) ==
deba@872
   414
          mwpfm.matching(e), "Invalid matching");
deba@872
   415
  }
deba@872
   416
deba@869
   417
  int dv = 0;
deba@869
   418
  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@869
   419
    dv += mwpfm.nodeValue(n);
deba@869
   420
  }
deba@869
   421
deba@869
   422
  check(pv * mwpfm.dualScale == dv * 2, "Wrong duality");
deba@869
   423
deba@869
   424
  SmartGraph::NodeMap<bool> processed(graph, false);
deba@869
   425
  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@869
   426
    if (processed[n]) continue;
deba@869
   427
    processed[n] = true;
deba@869
   428
    if (mwpfm.matching(n) == INVALID) continue;
deba@869
   429
    int num = 1;
deba@869
   430
    Node v = graph.target(mwpfm.matching(n));
deba@869
   431
    while (v != n) {
deba@869
   432
      processed[v] = true;
deba@869
   433
      ++num;
deba@869
   434
      v = graph.target(mwpfm.matching(v));
deba@869
   435
    }
deba@869
   436
    check(num == 2 || num % 2 == 1, "Wrong cycle size");
deba@869
   437
    check(allow_loops || num != 1, "Wrong cycle size");
deba@869
   438
  }
deba@869
   439
deba@869
   440
  return;
deba@869
   441
}
deba@869
   442
deba@869
   443
deba@869
   444
int main() {
deba@869
   445
deba@869
   446
  for (int i = 0; i < lgfn; ++i) {
deba@869
   447
    SmartGraph graph;
deba@869
   448
    SmartGraph::EdgeMap<int> weight(graph);
deba@869
   449
deba@869
   450
    istringstream lgfs(lgf[i]);
deba@869
   451
    graphReader(graph, lgfs).
deba@869
   452
      edgeMap("weight", weight).run();
deba@869
   453
deba@869
   454
    bool perfect_with_loops;
deba@869
   455
    {
deba@869
   456
      MaxFractionalMatching<SmartGraph> mfm(graph, true);
deba@869
   457
      mfm.run();
deba@869
   458
      checkFractionalMatching(graph, mfm, true);
deba@869
   459
      perfect_with_loops = mfm.matchingSize() == countNodes(graph);
deba@869
   460
    }
deba@869
   461
deba@869
   462
    bool perfect_without_loops;
deba@869
   463
    {
deba@869
   464
      MaxFractionalMatching<SmartGraph> mfm(graph, false);
deba@869
   465
      mfm.run();
deba@869
   466
      checkFractionalMatching(graph, mfm, false);
deba@869
   467
      perfect_without_loops = mfm.matchingSize() == countNodes(graph);
deba@869
   468
    }
deba@869
   469
deba@869
   470
    {
deba@869
   471
      MaxFractionalMatching<SmartGraph> mfm(graph, true);
deba@869
   472
      bool result = mfm.runPerfect();
deba@869
   473
      checkPerfectFractionalMatching(graph, mfm, result, true);
deba@869
   474
      check(result == perfect_with_loops, "Wrong perfect matching");
deba@869
   475
    }
deba@869
   476
deba@869
   477
    {
deba@869
   478
      MaxFractionalMatching<SmartGraph> mfm(graph, false);
deba@869
   479
      bool result = mfm.runPerfect();
deba@869
   480
      checkPerfectFractionalMatching(graph, mfm, result, false);
deba@869
   481
      check(result == perfect_without_loops, "Wrong perfect matching");
deba@869
   482
    }
deba@869
   483
deba@869
   484
    {
deba@869
   485
      MaxWeightedFractionalMatching<SmartGraph> mwfm(graph, weight, true);
deba@869
   486
      mwfm.run();
deba@869
   487
      checkWeightedFractionalMatching(graph, weight, mwfm, true);
deba@869
   488
    }
deba@869
   489
deba@869
   490
    {
deba@869
   491
      MaxWeightedFractionalMatching<SmartGraph> mwfm(graph, weight, false);
deba@869
   492
      mwfm.run();
deba@869
   493
      checkWeightedFractionalMatching(graph, weight, mwfm, false);
deba@869
   494
    }
deba@869
   495
deba@869
   496
    {
deba@869
   497
      MaxWeightedPerfectFractionalMatching<SmartGraph> mwpfm(graph, weight,
deba@869
   498
                                                             true);
deba@869
   499
      bool perfect = mwpfm.run();
deba@869
   500
      check(perfect == (mwpfm.matchingSize() == countNodes(graph)),
deba@869
   501
            "Perfect matching found");
deba@869
   502
      check(perfect == perfect_with_loops, "Wrong perfect matching");
deba@869
   503
deba@869
   504
      if (perfect) {
deba@869
   505
        checkWeightedPerfectFractionalMatching(graph, weight, mwpfm, true);
deba@869
   506
      }
deba@869
   507
    }
deba@869
   508
deba@869
   509
    {
deba@869
   510
      MaxWeightedPerfectFractionalMatching<SmartGraph> mwpfm(graph, weight,
deba@869
   511
                                                             false);
deba@869
   512
      bool perfect = mwpfm.run();
deba@869
   513
      check(perfect == (mwpfm.matchingSize() == countNodes(graph)),
deba@869
   514
            "Perfect matching found");
deba@869
   515
      check(perfect == perfect_without_loops, "Wrong perfect matching");
deba@869
   516
deba@869
   517
      if (perfect) {
deba@869
   518
        checkWeightedPerfectFractionalMatching(graph, weight, mwpfm, false);
deba@869
   519
      }
deba@869
   520
    }
deba@869
   521
deba@869
   522
  }
deba@869
   523
deba@869
   524
  return 0;
deba@869
   525
}