test/fractional_matching_test.cc
author Balazs Dezso <deba@inf.elte.hu>
Thu, 04 Mar 2010 10:17:02 +0100
changeset 871 86613aa28a0c
child 872 41d7ac528c3a
permissions -rw-r--r--
Fix documentation issues (#314)
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
 *
deba@869
     5
 * Copyright (C) 2003-2009
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@869
   239
  SmartGraph::NodeMap<bool> processed(graph, false);
deba@869
   240
  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@869
   241
    if (processed[n]) continue;
deba@869
   242
    processed[n] = true;
deba@869
   243
    if (mfm.matching(n) == INVALID) continue;
deba@869
   244
    int num = 1;
deba@869
   245
    Node v = graph.target(mfm.matching(n));
deba@869
   246
    while (v != n) {
deba@869
   247
      processed[v] = true;
deba@869
   248
      ++num;
deba@869
   249
      v = graph.target(mfm.matching(v));
deba@869
   250
    }
deba@869
   251
    check(num == 2 || num % 2 == 1, "Wrong cycle size");
deba@869
   252
    check(allow_loops || num != 1, "Wrong cycle size");
deba@869
   253
  }
deba@869
   254
deba@869
   255
  int anum = 0, bnum = 0;
deba@869
   256
  SmartGraph::NodeMap<bool> neighbours(graph, false);
deba@869
   257
  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@869
   258
    if (!mfm.barrier(n)) continue;
deba@869
   259
    ++anum;
deba@869
   260
    for (SmartGraph::InArcIt a(graph, n); a != INVALID; ++a) {
deba@869
   261
      Node u = graph.source(a);
deba@869
   262
      if (!allow_loops && u == n) continue;
deba@869
   263
      if (!neighbours[u]) {
deba@869
   264
        neighbours[u] = true;
deba@869
   265
        ++bnum;
deba@869
   266
      }
deba@869
   267
    }
deba@869
   268
  }
deba@869
   269
  check(anum - bnum + mfm.matchingSize() == countNodes(graph),
deba@869
   270
        "Wrong barrier");
deba@869
   271
}
deba@869
   272
deba@869
   273
void checkPerfectFractionalMatching(const SmartGraph& graph,
deba@869
   274
                             const MaxFractionalMatching<SmartGraph>& mfm,
deba@869
   275
                             bool perfect, bool allow_loops = true) {
deba@869
   276
  if (perfect) {
deba@869
   277
    for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@869
   278
      int indeg = 0;
deba@869
   279
      for (InArcIt a(graph, n); a != INVALID; ++a) {
deba@869
   280
        if (mfm.matching(graph.source(a)) == a) {
deba@869
   281
          ++indeg;
deba@869
   282
        }
deba@869
   283
      }
deba@869
   284
      check(mfm.matching(n) != INVALID, "Invalid matching");
deba@869
   285
      check(indeg == 1, "Invalid matching");
deba@869
   286
    }
deba@869
   287
  } else {
deba@869
   288
    int anum = 0, bnum = 0;
deba@869
   289
    SmartGraph::NodeMap<bool> neighbours(graph, false);
deba@869
   290
    for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@869
   291
      if (!mfm.barrier(n)) continue;
deba@869
   292
      ++anum;
deba@869
   293
      for (SmartGraph::InArcIt a(graph, n); a != INVALID; ++a) {
deba@869
   294
        Node u = graph.source(a);
deba@869
   295
        if (!allow_loops && u == n) continue;
deba@869
   296
        if (!neighbours[u]) {
deba@869
   297
          neighbours[u] = true;
deba@869
   298
          ++bnum;
deba@869
   299
        }
deba@869
   300
      }
deba@869
   301
    }
deba@869
   302
    check(anum - bnum > 0, "Wrong barrier");
deba@869
   303
  }
deba@869
   304
}
deba@869
   305
deba@869
   306
void checkWeightedFractionalMatching(const SmartGraph& graph,
deba@869
   307
                   const SmartGraph::EdgeMap<int>& weight,
deba@869
   308
                   const MaxWeightedFractionalMatching<SmartGraph>& mwfm,
deba@869
   309
                   bool allow_loops = true) {
deba@869
   310
  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
deba@869
   311
    if (graph.u(e) == graph.v(e) && !allow_loops) continue;
deba@869
   312
    int rw = mwfm.nodeValue(graph.u(e)) + mwfm.nodeValue(graph.v(e))
deba@869
   313
      - weight[e] * mwfm.dualScale;
deba@869
   314
deba@869
   315
    check(rw >= 0, "Negative reduced weight");
deba@869
   316
    check(rw == 0 || !mwfm.matching(e),
deba@869
   317
          "Non-zero reduced weight on matching edge");
deba@869
   318
  }
deba@869
   319
deba@869
   320
  int pv = 0;
deba@869
   321
  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@869
   322
    int indeg = 0;
deba@869
   323
    for (InArcIt a(graph, n); a != INVALID; ++a) {
deba@869
   324
      if (mwfm.matching(graph.source(a)) == a) {
deba@869
   325
        ++indeg;
deba@869
   326
      }
deba@869
   327
    }
deba@869
   328
    check(indeg <= 1, "Invalid matching");
deba@869
   329
    if (mwfm.matching(n) != INVALID) {
deba@869
   330
      check(mwfm.nodeValue(n) >= 0, "Invalid node value");
deba@869
   331
      check(indeg == 1, "Invalid matching");
deba@869
   332
      pv += weight[mwfm.matching(n)];
deba@869
   333
      SmartGraph::Node o = graph.target(mwfm.matching(n));
deba@869
   334
    } else {
deba@869
   335
      check(mwfm.nodeValue(n) == 0, "Invalid matching");
deba@869
   336
      check(indeg == 0, "Invalid matching");
deba@869
   337
    }
deba@869
   338
  }
deba@869
   339
deba@869
   340
  int dv = 0;
deba@869
   341
  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@869
   342
    dv += mwfm.nodeValue(n);
deba@869
   343
  }
deba@869
   344
deba@869
   345
  check(pv * mwfm.dualScale == dv * 2, "Wrong duality");
deba@869
   346
deba@869
   347
  SmartGraph::NodeMap<bool> processed(graph, false);
deba@869
   348
  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@869
   349
    if (processed[n]) continue;
deba@869
   350
    processed[n] = true;
deba@869
   351
    if (mwfm.matching(n) == INVALID) continue;
deba@869
   352
    int num = 1;
deba@869
   353
    Node v = graph.target(mwfm.matching(n));
deba@869
   354
    while (v != n) {
deba@869
   355
      processed[v] = true;
deba@869
   356
      ++num;
deba@869
   357
      v = graph.target(mwfm.matching(v));
deba@869
   358
    }
deba@869
   359
    check(num == 2 || num % 2 == 1, "Wrong cycle size");
deba@869
   360
    check(allow_loops || num != 1, "Wrong cycle size");
deba@869
   361
  }
deba@869
   362
deba@869
   363
  return;
deba@869
   364
}
deba@869
   365
deba@869
   366
void checkWeightedPerfectFractionalMatching(const SmartGraph& graph,
deba@869
   367
                const SmartGraph::EdgeMap<int>& weight,
deba@869
   368
                const MaxWeightedPerfectFractionalMatching<SmartGraph>& mwpfm,
deba@869
   369
                bool allow_loops = true) {
deba@869
   370
  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
deba@869
   371
    if (graph.u(e) == graph.v(e) && !allow_loops) continue;
deba@869
   372
    int rw = mwpfm.nodeValue(graph.u(e)) + mwpfm.nodeValue(graph.v(e))
deba@869
   373
      - weight[e] * mwpfm.dualScale;
deba@869
   374
deba@869
   375
    check(rw >= 0, "Negative reduced weight");
deba@869
   376
    check(rw == 0 || !mwpfm.matching(e),
deba@869
   377
          "Non-zero reduced weight on matching edge");
deba@869
   378
  }
deba@869
   379
deba@869
   380
  int pv = 0;
deba@869
   381
  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@869
   382
    int indeg = 0;
deba@869
   383
    for (InArcIt a(graph, n); a != INVALID; ++a) {
deba@869
   384
      if (mwpfm.matching(graph.source(a)) == a) {
deba@869
   385
        ++indeg;
deba@869
   386
      }
deba@869
   387
    }
deba@869
   388
    check(mwpfm.matching(n) != INVALID, "Invalid perfect matching");
deba@869
   389
    check(indeg == 1, "Invalid perfect matching");
deba@869
   390
    pv += weight[mwpfm.matching(n)];
deba@869
   391
    SmartGraph::Node o = graph.target(mwpfm.matching(n));
deba@869
   392
  }
deba@869
   393
deba@869
   394
  int dv = 0;
deba@869
   395
  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@869
   396
    dv += mwpfm.nodeValue(n);
deba@869
   397
  }
deba@869
   398
deba@869
   399
  check(pv * mwpfm.dualScale == dv * 2, "Wrong duality");
deba@869
   400
deba@869
   401
  SmartGraph::NodeMap<bool> processed(graph, false);
deba@869
   402
  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
deba@869
   403
    if (processed[n]) continue;
deba@869
   404
    processed[n] = true;
deba@869
   405
    if (mwpfm.matching(n) == INVALID) continue;
deba@869
   406
    int num = 1;
deba@869
   407
    Node v = graph.target(mwpfm.matching(n));
deba@869
   408
    while (v != n) {
deba@869
   409
      processed[v] = true;
deba@869
   410
      ++num;
deba@869
   411
      v = graph.target(mwpfm.matching(v));
deba@869
   412
    }
deba@869
   413
    check(num == 2 || num % 2 == 1, "Wrong cycle size");
deba@869
   414
    check(allow_loops || num != 1, "Wrong cycle size");
deba@869
   415
  }
deba@869
   416
deba@869
   417
  return;
deba@869
   418
}
deba@869
   419
deba@869
   420
deba@869
   421
int main() {
deba@869
   422
deba@869
   423
  for (int i = 0; i < lgfn; ++i) {
deba@869
   424
    SmartGraph graph;
deba@869
   425
    SmartGraph::EdgeMap<int> weight(graph);
deba@869
   426
deba@869
   427
    istringstream lgfs(lgf[i]);
deba@869
   428
    graphReader(graph, lgfs).
deba@869
   429
      edgeMap("weight", weight).run();
deba@869
   430
deba@869
   431
    bool perfect_with_loops;
deba@869
   432
    {
deba@869
   433
      MaxFractionalMatching<SmartGraph> mfm(graph, true);
deba@869
   434
      mfm.run();
deba@869
   435
      checkFractionalMatching(graph, mfm, true);
deba@869
   436
      perfect_with_loops = mfm.matchingSize() == countNodes(graph);
deba@869
   437
    }
deba@869
   438
deba@869
   439
    bool perfect_without_loops;
deba@869
   440
    {
deba@869
   441
      MaxFractionalMatching<SmartGraph> mfm(graph, false);
deba@869
   442
      mfm.run();
deba@869
   443
      checkFractionalMatching(graph, mfm, false);
deba@869
   444
      perfect_without_loops = mfm.matchingSize() == countNodes(graph);
deba@869
   445
    }
deba@869
   446
deba@869
   447
    {
deba@869
   448
      MaxFractionalMatching<SmartGraph> mfm(graph, true);
deba@869
   449
      bool result = mfm.runPerfect();
deba@869
   450
      checkPerfectFractionalMatching(graph, mfm, result, true);
deba@869
   451
      check(result == perfect_with_loops, "Wrong perfect matching");
deba@869
   452
    }
deba@869
   453
deba@869
   454
    {
deba@869
   455
      MaxFractionalMatching<SmartGraph> mfm(graph, false);
deba@869
   456
      bool result = mfm.runPerfect();
deba@869
   457
      checkPerfectFractionalMatching(graph, mfm, result, false);
deba@869
   458
      check(result == perfect_without_loops, "Wrong perfect matching");
deba@869
   459
    }
deba@869
   460
deba@869
   461
    {
deba@869
   462
      MaxWeightedFractionalMatching<SmartGraph> mwfm(graph, weight, true);
deba@869
   463
      mwfm.run();
deba@869
   464
      checkWeightedFractionalMatching(graph, weight, mwfm, true);
deba@869
   465
    }
deba@869
   466
deba@869
   467
    {
deba@869
   468
      MaxWeightedFractionalMatching<SmartGraph> mwfm(graph, weight, false);
deba@869
   469
      mwfm.run();
deba@869
   470
      checkWeightedFractionalMatching(graph, weight, mwfm, false);
deba@869
   471
    }
deba@869
   472
deba@869
   473
    {
deba@869
   474
      MaxWeightedPerfectFractionalMatching<SmartGraph> mwpfm(graph, weight,
deba@869
   475
                                                             true);
deba@869
   476
      bool perfect = mwpfm.run();
deba@869
   477
      check(perfect == (mwpfm.matchingSize() == countNodes(graph)),
deba@869
   478
            "Perfect matching found");
deba@869
   479
      check(perfect == perfect_with_loops, "Wrong perfect matching");
deba@869
   480
deba@869
   481
      if (perfect) {
deba@869
   482
        checkWeightedPerfectFractionalMatching(graph, weight, mwpfm, true);
deba@869
   483
      }
deba@869
   484
    }
deba@869
   485
deba@869
   486
    {
deba@869
   487
      MaxWeightedPerfectFractionalMatching<SmartGraph> mwpfm(graph, weight,
deba@869
   488
                                                             false);
deba@869
   489
      bool perfect = mwpfm.run();
deba@869
   490
      check(perfect == (mwpfm.matchingSize() == countNodes(graph)),
deba@869
   491
            "Perfect matching found");
deba@869
   492
      check(perfect == perfect_without_loops, "Wrong perfect matching");
deba@869
   493
deba@869
   494
      if (perfect) {
deba@869
   495
        checkWeightedPerfectFractionalMatching(graph, weight, mwpfm, false);
deba@869
   496
      }
deba@869
   497
    }
deba@869
   498
deba@869
   499
  }
deba@869
   500
deba@869
   501
  return 0;
deba@869
   502
}