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       ignore_unused_variable_warning(o);

   346     } else {

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

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

   349     }

   350   }

   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   }

   358   int dv = 0;

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

   360     dv += mwfm.nodeValue(n);

   361   }

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

   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   }

   381   return;

   382 }

   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;

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

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

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

   396   }

   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     ignore_unused_variable_warning(o);

   411   }

   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   }

   419   int dv = 0;

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

   421     dv += mwpfm.nodeValue(n);

   422   }

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

   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   }

   442   return;

   443 }

   446 int main() {

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

   449     SmartGraph graph;

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

   452     istringstream lgfs(lgf[i]);

   453     graphReader(graph, lgfs).

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

   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     }

   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     }

   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     }

   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     }

   486     {

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

   488       mwfm.run();

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

   490     }

   492     {

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

   494       mwfm.run();

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

   496     }

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

   506       if (perfect) {

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

   508       }

   509     }

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

   519       if (perfect) {

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

   521       }

   522     }

   524   }

   526   return 0;

   527 }

author	Alpar Juttner <alpar@cs.elte.hu>
	Sat, 25 May 2013 06:59:31 +0200
changeset 1064	fc3854d936f7
parent 877	141f9c0db4a3
child 1085	a337a0dd3f75
permissions	-rw-r--r--