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