lemon-main: test/fractional_matching

     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  */

    19 #include <iostream>

    20 #include <sstream>

    21 #include <vector>

    22 #include <queue>

    23 #include <cstdlib>

    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>

    32 #include "test_tools.h"

    34 using namespace std;

    35 using namespace lemon;

    37 GRAPH_TYPEDEFS(SmartGraph);

    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",

    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",

    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",

   114   "@nodes\n"

   115   "label\n"

   116   "0\n"

   117   "@edges\n"

   118   "     label  weight\n"

   119   "0 0  0      100\n"

   120 };

   122 void checkMaxFractionalMatchingCompile()

   123 {

   124   typedef concepts::Graph Graph;

   125   typedef Graph::Node Node;

   126   typedef Graph::Edge Edge;

   128   Graph g;

   129   Node n;

   130   Edge e;

   132   MaxFractionalMatching<Graph> mat_test(g);

   133   const MaxFractionalMatching<Graph>&

   134     const_mat_test = mat_test;

   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);

   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];

   153   const_mat_test.barrier(n);

   154 }

   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;

   163   Graph g;

   164   Node n;

   165   Edge e;

   166   WeightMap w(g);

   168   MaxWeightedFractionalMatching<Graph> mat_test(g, w);

   169   const MaxWeightedFractionalMatching<Graph>&

   170     const_mat_test = mat_test;

   172   mat_test.init();

   173   mat_test.start();

   174   mat_test.run();

   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];

   184   const_mat_test.dualValue();

   185   const_mat_test.nodeValue(n);

   186 }

   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;

   195   Graph g;

   196   Node n;

   197   Edge e;

   198   WeightMap w(g);

   200   MaxWeightedPerfectFractionalMatching<Graph> mat_test(g, w);

   201   const MaxWeightedPerfectFractionalMatching<Graph>&

   202     const_mat_test = mat_test;

   204   mat_test.init();

   205   mat_test.start();

   206   mat_test.run();

   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];

   215   const_mat_test.dualValue();

   216   const_mat_test.nodeValue(n);

   217 }

   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");

   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   }

   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   }

   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 }

   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 }

   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;

   326     check(rw >= 0, "Negative reduced weight");

   327     check(rw == 0 || !mwfm.matching(e),

   328           "Non-zero reduced weight on matching edge");

   329   }

   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     } else {

   346       check(mwfm.nodeValue(n) == 0, "Invalid matching");

   347       check(indeg == 0, "Invalid matching");

   348     }

   349   }

   351   for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {

   352     check((e == mwfm.matching(graph.u(e)) ? 1 : 0) +

   353           (e == mwfm.matching(graph.v(e)) ? 1 : 0) ==

   354           mwfm.matching(e), "Invalid matching");

   355   }

   357   int dv = 0;

   358   for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {

   359     dv += mwfm.nodeValue(n);

   360   }

   362   check(pv * mwfm.dualScale == dv * 2, "Wrong duality");

   364   SmartGraph::NodeMap<bool> processed(graph, false);

   365   for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {

   366     if (processed[n]) continue;

   367     processed[n] = true;

   368     if (mwfm.matching(n) == INVALID) continue;

   369     int num = 1;

   370     Node v = graph.target(mwfm.matching(n));

   371     while (v != n) {

   372       processed[v] = true;

   373       ++num;

   374       v = graph.target(mwfm.matching(v));

   375     }

   376     check(num == 2 || num % 2 == 1, "Wrong cycle size");

   377     check(allow_loops || num != 1, "Wrong cycle size");

   378   }

   380   return;

   381 }

   383 void checkWeightedPerfectFractionalMatching(const SmartGraph& graph,

   384                 const SmartGraph::EdgeMap<int>& weight,

   385                 const MaxWeightedPerfectFractionalMatching<SmartGraph>& mwpfm,

   386                 bool allow_loops = true) {

   387   for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {

   388     if (graph.u(e) == graph.v(e) && !allow_loops) continue;

   389     int rw = mwpfm.nodeValue(graph.u(e)) + mwpfm.nodeValue(graph.v(e))

   390       - weight[e] * mwpfm.dualScale;

   392     check(rw >= 0, "Negative reduced weight");

   393     check(rw == 0 || !mwpfm.matching(e),

   394           "Non-zero reduced weight on matching edge");

   395   }

   397   int pv = 0;

   398   for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {

   399     int indeg = 0;

   400     for (InArcIt a(graph, n); a != INVALID; ++a) {

   401       if (mwpfm.matching(graph.source(a)) == a) {

   402         ++indeg;

   403       }

   404     }

   405     check(mwpfm.matching(n) != INVALID, "Invalid perfect matching");

   406     check(indeg == 1, "Invalid perfect matching");

   407     pv += weight[mwpfm.matching(n)];

   408     SmartGraph::Node o = graph.target(mwpfm.matching(n));

   409   }

   411   for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {

   412     check((e == mwpfm.matching(graph.u(e)) ? 1 : 0) +

   413           (e == mwpfm.matching(graph.v(e)) ? 1 : 0) ==

   414           mwpfm.matching(e), "Invalid matching");

   415   }

   417   int dv = 0;

   418   for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {

   419     dv += mwpfm.nodeValue(n);

   420   }

   422   check(pv * mwpfm.dualScale == dv * 2, "Wrong duality");

   424   SmartGraph::NodeMap<bool> processed(graph, false);

   425   for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {

   426     if (processed[n]) continue;

   427     processed[n] = true;

   428     if (mwpfm.matching(n) == INVALID) continue;

   429     int num = 1;

   430     Node v = graph.target(mwpfm.matching(n));

   431     while (v != n) {

   432       processed[v] = true;

   433       ++num;

   434       v = graph.target(mwpfm.matching(v));

   435     }

   436     check(num == 2 || num % 2 == 1, "Wrong cycle size");

   437     check(allow_loops || num != 1, "Wrong cycle size");

   438   }

   440   return;

   441 }

   444 int main() {

   446   for (int i = 0; i < lgfn; ++i) {

   447     SmartGraph graph;

   448     SmartGraph::EdgeMap<int> weight(graph);

   450     istringstream lgfs(lgf[i]);

   451     graphReader(graph, lgfs).

   452       edgeMap("weight", weight).run();

   454     bool perfect_with_loops;

   455     {

   456       MaxFractionalMatching<SmartGraph> mfm(graph, true);

   457       mfm.run();

   458       checkFractionalMatching(graph, mfm, true);

   459       perfect_with_loops = mfm.matchingSize() == countNodes(graph);

   460     }

   462     bool perfect_without_loops;

   463     {

   464       MaxFractionalMatching<SmartGraph> mfm(graph, false);

   465       mfm.run();

   466       checkFractionalMatching(graph, mfm, false);

   467       perfect_without_loops = mfm.matchingSize() == countNodes(graph);

   468     }

   470     {

   471       MaxFractionalMatching<SmartGraph> mfm(graph, true);

   472       bool result = mfm.runPerfect();

   473       checkPerfectFractionalMatching(graph, mfm, result, true);

   474       check(result == perfect_with_loops, "Wrong perfect matching");

   475     }

   477     {

   478       MaxFractionalMatching<SmartGraph> mfm(graph, false);

   479       bool result = mfm.runPerfect();

   480       checkPerfectFractionalMatching(graph, mfm, result, false);

   481       check(result == perfect_without_loops, "Wrong perfect matching");

   482     }

   484     {

   485       MaxWeightedFractionalMatching<SmartGraph> mwfm(graph, weight, true);

   486       mwfm.run();

   487       checkWeightedFractionalMatching(graph, weight, mwfm, true);

   488     }

   490     {

   491       MaxWeightedFractionalMatching<SmartGraph> mwfm(graph, weight, false);

   492       mwfm.run();

   493       checkWeightedFractionalMatching(graph, weight, mwfm, false);

   494     }

   496     {

   497       MaxWeightedPerfectFractionalMatching<SmartGraph> mwpfm(graph, weight,

   498                                                              true);

   499       bool perfect = mwpfm.run();

   500       check(perfect == (mwpfm.matchingSize() == countNodes(graph)),

   501             "Perfect matching found");

   502       check(perfect == perfect_with_loops, "Wrong perfect matching");

   504       if (perfect) {

   505         checkWeightedPerfectFractionalMatching(graph, weight, mwpfm, true);

   506       }

   507     }

   509     {

   510       MaxWeightedPerfectFractionalMatching<SmartGraph> mwpfm(graph, weight,

   511                                                              false);

   512       bool perfect = mwpfm.run();

   513       check(perfect == (mwpfm.matchingSize() == countNodes(graph)),

   514             "Perfect matching found");

   515       check(perfect == perfect_without_loops, "Wrong perfect matching");

   517       if (perfect) {

   518         checkWeightedPerfectFractionalMatching(graph, weight, mwpfm, false);

   519       }

   520     }

   522   }

   524   return 0;

   525 }

author	Peter Kovacs <kpeter@inf.elte.hu>
	Tue, 15 Mar 2011 19:54:11 +0100
changeset 938	a07b6b27fe69
parent 872	41d7ac528c3a
child 999	00f8d9f9920d
permissions	-rw-r--r--