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