test/max_weighted_matching_test.cc
author kpeter
Thu, 28 Feb 2008 02:58:26 +0000
changeset 2584 84ef3c5b3698
parent 2553 bfced05fa852
permissions -rw-r--r--
Test file for the min cost flow algorithms.
deba@2549
     1
/* -*- C++ -*-
deba@2549
     2
 *
deba@2549
     3
 * This file is a part of LEMON, a generic C++ optimization library
deba@2549
     4
 *
alpar@2553
     5
 * Copyright (C) 2003-2008
deba@2549
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@2549
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@2549
     8
 *
deba@2549
     9
 * Permission to use, modify and distribute this software is granted
deba@2549
    10
 * provided that this copyright notice appears in all copies. For
deba@2549
    11
 * precise terms see the accompanying LICENSE file.
deba@2549
    12
 *
deba@2549
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@2549
    14
 * express or implied, and with no claim as to its suitability for any
deba@2549
    15
 * purpose.
deba@2549
    16
 *
deba@2549
    17
 */
deba@2549
    18
deba@2549
    19
#include <iostream>
deba@2549
    20
#include <sstream>
deba@2549
    21
#include <vector>
deba@2549
    22
#include <queue>
alpar@2569
    23
#include <lemon/math.h>
deba@2549
    24
#include <cstdlib>
deba@2549
    25
deba@2549
    26
#include "test_tools.h"
deba@2549
    27
#include <lemon/smart_graph.h>
deba@2549
    28
#include <lemon/max_matching.h>
deba@2549
    29
#include <lemon/graph_reader.h>
deba@2549
    30
deba@2549
    31
UGRAPH_TYPEDEFS(SmartUGraph);
deba@2549
    32
deba@2549
    33
using namespace std;
deba@2549
    34
using namespace lemon;
deba@2549
    35
deba@2549
    36
const int lgfn = 3;
deba@2549
    37
const std::string lgf[lgfn] = {   
deba@2549
    38
  "@nodeset\n"
deba@2549
    39
  "label\n"
deba@2549
    40
  "0\n"
deba@2549
    41
  "1\n"
deba@2549
    42
  "2\n"
deba@2549
    43
  "3\n"
deba@2549
    44
  "4\n"
deba@2549
    45
  "5\n"
deba@2549
    46
  "6\n"
deba@2549
    47
  "7\n"
deba@2549
    48
  "@uedgeset\n"
deba@2549
    49
  "label        weight\n"
deba@2549
    50
  "7    4       0       984\n"
deba@2549
    51
  "0    7       1       73\n"
deba@2549
    52
  "7    1       2       204\n"
deba@2549
    53
  "2    3       3       583\n"
deba@2549
    54
  "2    7       4       565\n"
deba@2549
    55
  "2    1       5       582\n"
deba@2549
    56
  "0    4       6       551\n"
deba@2549
    57
  "2    5       7       385\n"
deba@2549
    58
  "1    5       8       561\n"
deba@2549
    59
  "5    3       9       484\n"
deba@2549
    60
  "7    5       10      904\n"
deba@2549
    61
  "3    6       11      47\n"
deba@2549
    62
  "7    6       12      888\n"
deba@2549
    63
  "3    0       13      747\n"
deba@2549
    64
  "6    1       14      310\n"
deba@2549
    65
  "@end\n",
deba@2549
    66
deba@2549
    67
  "@nodeset\n"
deba@2549
    68
  "label\n"
deba@2549
    69
  "0\n"
deba@2549
    70
  "1\n"
deba@2549
    71
  "2\n"
deba@2549
    72
  "3\n"
deba@2549
    73
  "4\n"
deba@2549
    74
  "5\n"
deba@2549
    75
  "6\n"
deba@2549
    76
  "7\n"
deba@2549
    77
  "@uedgeset\n"
deba@2549
    78
  "label        weight\n"
deba@2549
    79
  "2    5       0       710\n"
deba@2549
    80
  "0    5       1       241\n"
deba@2549
    81
  "2    4       2       856\n"
deba@2549
    82
  "2    6       3       762\n"
deba@2549
    83
  "4    1       4       747\n"
deba@2549
    84
  "6    1       5       962\n"
deba@2549
    85
  "4    7       6       723\n"
deba@2549
    86
  "1    7       7       661\n"
deba@2549
    87
  "2    3       8       376\n"
deba@2549
    88
  "1    0       9       416\n"
deba@2549
    89
  "6    7       10      391\n"
deba@2549
    90
  "@end\n",
deba@2549
    91
deba@2549
    92
  "@nodeset\n"
deba@2549
    93
  "label\n"
deba@2549
    94
  "0\n"
deba@2549
    95
  "1\n"
deba@2549
    96
  "2\n"
deba@2549
    97
  "3\n"
deba@2549
    98
  "4\n"
deba@2549
    99
  "5\n"
deba@2549
   100
  "6\n"
deba@2549
   101
  "7\n"
deba@2549
   102
  "@uedgeset\n"
deba@2549
   103
  "label        weight\n"
deba@2549
   104
  "6    2       0       553\n"
deba@2549
   105
  "0    7       1       653\n"
deba@2549
   106
  "6    3       2       22\n"
deba@2549
   107
  "4    7       3       846\n"
deba@2549
   108
  "7    2       4       981\n"
deba@2549
   109
  "7    6       5       250\n"
deba@2549
   110
  "5    2       6       539\n"
deba@2549
   111
  "@end\n"
deba@2549
   112
};
deba@2549
   113
deba@2549
   114
void checkMatching(const SmartUGraph& ugraph,
deba@2549
   115
		   const SmartUGraph::UEdgeMap<int>& weight,
deba@2549
   116
		   const MaxWeightedMatching<SmartUGraph>& mwm) {
deba@2549
   117
  for (SmartUGraph::UEdgeIt e(ugraph); e != INVALID; ++e) {
deba@2549
   118
    if (ugraph.source(e) == ugraph.target(e)) continue;
deba@2549
   119
    int rw = 
deba@2549
   120
      mwm.nodeValue(ugraph.source(e)) + mwm.nodeValue(ugraph.target(e));
deba@2549
   121
deba@2549
   122
    for (int i = 0; i < mwm.blossomNum(); ++i) {
deba@2549
   123
      bool s = false, t = false;
deba@2549
   124
      for (MaxWeightedMatching<SmartUGraph>::BlossomIt n(mwm, i); 
deba@2549
   125
	   n != INVALID; ++n) {
deba@2549
   126
	if (ugraph.source(e) == n) s = true;
deba@2549
   127
	if (ugraph.target(e) == n) t = true;
deba@2549
   128
      }
deba@2549
   129
      if (s == true && t == true) {
deba@2549
   130
	rw += mwm.blossomValue(i);
deba@2549
   131
      }
deba@2549
   132
    }
deba@2549
   133
    rw -= weight[e] * mwm.dualScale;
deba@2549
   134
deba@2549
   135
    check(rw >= 0, "Negative reduced weight");
deba@2549
   136
    check(rw == 0 || !mwm.matching(e), 
deba@2549
   137
	  "Non-zero reduced weight on matching edge");
deba@2549
   138
  }
deba@2549
   139
deba@2549
   140
  int pv = 0;
deba@2549
   141
  for (SmartUGraph::NodeIt n(ugraph); n != INVALID; ++n) {
deba@2549
   142
    if (mwm.matching(n) != INVALID) {
deba@2549
   143
      check(mwm.nodeValue(n) >= 0, "Invalid node value");
deba@2549
   144
      pv += weight[mwm.matching(n)];
deba@2549
   145
      SmartUGraph::Node o = ugraph.target(mwm.matching(n));
deba@2549
   146
      check(mwm.mate(n) == o, "Invalid matching");
deba@2549
   147
      check(mwm.matching(n) == ugraph.oppositeEdge(mwm.matching(o)), 
deba@2549
   148
	    "Invalid matching");
deba@2549
   149
    } else {
deba@2549
   150
      check(mwm.mate(n) == INVALID, "Invalid matching");
deba@2549
   151
      check(mwm.nodeValue(n) == 0, "Invalid matching");
deba@2549
   152
    }
deba@2549
   153
  }
deba@2549
   154
deba@2549
   155
  int dv = 0;
deba@2549
   156
  for (SmartUGraph::NodeIt n(ugraph); n != INVALID; ++n) {
deba@2549
   157
    dv += mwm.nodeValue(n);
deba@2549
   158
  }
deba@2549
   159
deba@2549
   160
  for (int i = 0; i < mwm.blossomNum(); ++i) {
deba@2549
   161
    check(mwm.blossomValue(i) >= 0, "Invalid blossom value");
deba@2549
   162
    check(mwm.blossomSize(i) % 2 == 1, "Even blossom size");
deba@2549
   163
    dv += mwm.blossomValue(i) * ((mwm.blossomSize(i) - 1) / 2);
deba@2549
   164
  }
deba@2549
   165
deba@2549
   166
  check(pv * mwm.dualScale == dv * 2, "Wrong duality");
deba@2549
   167
deba@2549
   168
  return;
deba@2549
   169
}
deba@2549
   170
deba@2549
   171
void checkPerfectMatching(const SmartUGraph& ugraph,
deba@2549
   172
			  const SmartUGraph::UEdgeMap<int>& weight,
deba@2549
   173
			  const MaxWeightedPerfectMatching<SmartUGraph>& mwpm) {
deba@2549
   174
  for (SmartUGraph::UEdgeIt e(ugraph); e != INVALID; ++e) {
deba@2549
   175
    if (ugraph.source(e) == ugraph.target(e)) continue;
deba@2549
   176
    int rw = 
deba@2549
   177
      mwpm.nodeValue(ugraph.source(e)) + mwpm.nodeValue(ugraph.target(e));
deba@2549
   178
deba@2549
   179
    for (int i = 0; i < mwpm.blossomNum(); ++i) {
deba@2549
   180
      bool s = false, t = false;
deba@2549
   181
      for (MaxWeightedPerfectMatching<SmartUGraph>::BlossomIt n(mwpm, i); 
deba@2549
   182
	   n != INVALID; ++n) {
deba@2549
   183
	if (ugraph.source(e) == n) s = true;
deba@2549
   184
	if (ugraph.target(e) == n) t = true;
deba@2549
   185
      }
deba@2549
   186
      if (s == true && t == true) {
deba@2549
   187
	rw += mwpm.blossomValue(i);
deba@2549
   188
      }
deba@2549
   189
    }
deba@2549
   190
    rw -= weight[e] * mwpm.dualScale;
deba@2549
   191
deba@2549
   192
    check(rw >= 0, "Negative reduced weight");
deba@2549
   193
    check(rw == 0 || !mwpm.matching(e), 
deba@2549
   194
	  "Non-zero reduced weight on matching edge");
deba@2549
   195
  }
deba@2549
   196
deba@2549
   197
  int pv = 0;
deba@2549
   198
  for (SmartUGraph::NodeIt n(ugraph); n != INVALID; ++n) {
deba@2549
   199
    check(mwpm.matching(n) != INVALID, "Non perfect");
deba@2549
   200
    pv += weight[mwpm.matching(n)];
deba@2549
   201
    SmartUGraph::Node o = ugraph.target(mwpm.matching(n));
deba@2549
   202
    check(mwpm.mate(n) == o, "Invalid matching");
deba@2549
   203
    check(mwpm.matching(n) == ugraph.oppositeEdge(mwpm.matching(o)), 
deba@2549
   204
	  "Invalid matching");
deba@2549
   205
  }
deba@2549
   206
deba@2549
   207
  int dv = 0;
deba@2549
   208
  for (SmartUGraph::NodeIt n(ugraph); n != INVALID; ++n) {
deba@2549
   209
    dv += mwpm.nodeValue(n);
deba@2549
   210
  }
deba@2549
   211
deba@2549
   212
  for (int i = 0; i < mwpm.blossomNum(); ++i) {
deba@2549
   213
    check(mwpm.blossomValue(i) >= 0, "Invalid blossom value");
deba@2549
   214
    check(mwpm.blossomSize(i) % 2 == 1, "Even blossom size");
deba@2549
   215
    dv += mwpm.blossomValue(i) * ((mwpm.blossomSize(i) - 1) / 2);
deba@2549
   216
  }
deba@2549
   217
deba@2549
   218
  check(pv * mwpm.dualScale == dv * 2, "Wrong duality");
deba@2549
   219
deba@2549
   220
  return;
deba@2549
   221
}
deba@2549
   222
deba@2549
   223
deba@2549
   224
int main() {
deba@2549
   225
deba@2549
   226
  for (int i = 0; i < lgfn; ++i) {
deba@2549
   227
    SmartUGraph ugraph;
deba@2549
   228
    SmartUGraph::UEdgeMap<int> weight(ugraph);
deba@2549
   229
    
deba@2549
   230
    istringstream lgfs(lgf[i]);
deba@2549
   231
    UGraphReader<SmartUGraph>(lgfs, ugraph).
deba@2549
   232
      readUEdgeMap("weight", weight).run();
deba@2549
   233
deba@2549
   234
    MaxWeightedMatching<SmartUGraph> mwm(ugraph, weight);
deba@2549
   235
    mwm.run();
deba@2549
   236
    checkMatching(ugraph, weight, mwm);
deba@2549
   237
deba@2549
   238
    MaxMatching<SmartUGraph> mm(ugraph);
deba@2549
   239
    mm.run();
deba@2549
   240
deba@2549
   241
    MaxWeightedPerfectMatching<SmartUGraph> mwpm(ugraph, weight);
deba@2549
   242
    bool perfect = mwpm.run();
deba@2549
   243
deba@2549
   244
    check(perfect == (mm.size() * 2 == countNodes(ugraph)), 
deba@2549
   245
	  "Perfect matching found");
deba@2549
   246
deba@2549
   247
    if (perfect) {
deba@2549
   248
      checkPerfectMatching(ugraph, weight, mwpm);
deba@2549
   249
    }
deba@2549
   250
  }
deba@2549
   251
  
deba@2549
   252
  return 0;
deba@2549
   253
}