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