test/bipartite_matching_test.cc
author alpar
Thu, 03 Apr 2008 12:06:48 +0000
changeset 2599 b9905565d185
parent 2553 bfced05fa852
child 2618 6aa6fcaeaea5
permissions -rw-r--r--
Serious bugfix in Random::gamma()
Backport from hg b6bede534255
     1 /* -*- C++ -*-
     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 <cstdlib>
    20 #include <iostream>
    21 #include <sstream>
    22 
    23 #include <lemon/smart_graph.h>
    24 
    25 #include <lemon/bpugraph_adaptor.h>
    26 #include <lemon/bipartite_matching.h>
    27 #include <lemon/pr_bipartite_matching.h>
    28 
    29 #include <lemon/graph_utils.h>
    30 
    31 #include <lemon/maps.h>
    32 
    33 #include "test_tools.h"
    34 
    35 using namespace std;
    36 using namespace lemon;
    37 
    38 typedef SmartBpUGraph Graph;
    39 BPUGRAPH_TYPEDEFS(Graph);
    40 
    41 const int NN = 10;
    42 const int MM = 10;
    43 const int EE = 52;
    44 const int CC = 100;
    45 
    46 const int sa[EE] = { 6, 5, 6, 4, 1, 0, 9, 5, 2, 4, 4, 3, 5,
    47                     2, 3, 8, 3, 4, 9, 6, 9, 4, 3, 1, 5, 8,
    48                     4, 8, 9, 2, 2, 3, 0, 5, 2, 3, 6, 3, 8,
    49                     8, 4, 0, 9, 9, 6, 2, 1, 2, 7, 1, 9, 4};
    50 
    51 const int ta[EE] = { 2, 7, 4, 8, 6, 3, 4, 1, 7, 7, 0, 1, 6,
    52                     3, 2, 6, 8, 3, 5, 6, 3, 1, 8, 7, 2, 0,
    53                     6, 9, 6, 7, 8, 3, 3, 4, 5, 8, 6, 4, 1,
    54                     4, 3, 3, 8, 7, 7, 3, 7, 7, 3, 5, 1, 6};
    55 
    56 const int wa[EE] = { 3, 99, 85, 16, 79, 52, 83, 99, 62, 6, 42, 6, 95,
    57                     13, 34, 9, 5, 38, 39, 75, 99, 12, 73, 35, 93, 43,
    58                     54, 91, 45, 26, 77, 47, 11, 22, 50, 74, 37, 64, 91,
    59                     60, 6, 92, 29, 46, 34, 84, 67, 34, 45, 0, 39, 47};
    60 
    61 
    62 int main() {
    63   Graph graph;
    64   vector<Node> aNodes;
    65   vector<Node> bNodes;
    66 
    67   Graph::UEdgeMap<int> weight(graph);
    68 
    69   int max_cardinality;
    70   int max_weight;
    71   int max_cardinality_max_weight;
    72   int min_cost_matching;
    73 
    74   for (int i = 0; i < NN; ++i) {
    75     Node node = graph.addANode();
    76     aNodes.push_back(node);
    77   }
    78   for (int i = 0; i < MM; ++i) {
    79     Node node = graph.addBNode();
    80     bNodes.push_back(node);
    81   }
    82   for (int i = 0; i < EE; ++i) {
    83     Node aNode = aNodes[sa[i]];
    84     Node bNode = bNodes[ta[i]];
    85     UEdge uedge = graph.addEdge(aNode, bNode);
    86     weight[uedge] = wa[i];
    87   }
    88 
    89 
    90   {
    91     MaxBipartiteMatching<Graph> bpmatch(graph);
    92 
    93     bpmatch.run();
    94 
    95     Graph::UEdgeMap<bool> mm(graph);
    96     Graph::NodeMap<bool> cs(graph);
    97     
    98     check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
    99     
   100     for (UEdgeIt it(graph); it != INVALID; ++it) {
   101       check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
   102     }
   103     
   104     for (ANodeIt it(graph); it != INVALID; ++it) {
   105       int num = 0;
   106       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   107         if (mm[jt]) ++num;
   108       }
   109       check(num <= 1, "INVALID PRIMAL");
   110     }
   111     max_cardinality = bpmatch.matchingSize();
   112   }
   113 
   114   {
   115     PrBipartiteMatching<Graph> bpmatch(graph);
   116 
   117     bpmatch.run();
   118 
   119     Graph::UEdgeMap<bool> mm(graph);
   120     Graph::NodeMap<bool> cs(graph);
   121     
   122     check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
   123     
   124     for (UEdgeIt it(graph); it != INVALID; ++it) {
   125       check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
   126     }
   127     
   128     for (ANodeIt it(graph); it != INVALID; ++it) {
   129       int num = 0;
   130       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   131         if (mm[jt]) ++num;
   132       }
   133       check(num <= 1, "INVALID PRIMAL");
   134     }
   135     max_cardinality = bpmatch.matchingSize();
   136   }
   137 
   138   {
   139     Graph::ANodeMap<UEdge> mm(graph);
   140 
   141     check(max_cardinality == maxBipartiteMatching(graph, mm),
   142           "WRONG MATCHING");
   143     
   144     for (BNodeIt it(graph); it != INVALID; ++it) {
   145       int num = 0;
   146       
   147       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   148         if (mm[graph.aNode(jt)] == jt) ++num;
   149       }
   150       check(num <= 1, "INVALID PRIMAL");
   151     }
   152   }
   153 
   154   {
   155     Graph::ANodeMap<UEdge> mm(graph);
   156 
   157     check(max_cardinality == prBipartiteMatching(graph, mm),
   158           "WRONG MATCHING");
   159     
   160     for (BNodeIt it(graph); it != INVALID; ++it) {
   161       int num = 0;
   162       
   163       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   164         if (mm[graph.aNode(jt)] == jt) ++num;
   165       }
   166       check(num <= 1, "INVALID PRIMAL");
   167     }
   168   }
   169 
   170   {
   171     MaxBipartiteMatching<Graph> bpmatch(graph);
   172 
   173     bpmatch.greedyInit();
   174     bpmatch.start();
   175 
   176     Graph::UEdgeMap<bool> mm(graph);
   177     Graph::NodeMap<bool> cs(graph);
   178 
   179     check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
   180     
   181     for (UEdgeIt it(graph); it != INVALID; ++it) {
   182       check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
   183     }
   184     
   185     for (ANodeIt it(graph); it != INVALID; ++it) {
   186       int num = 0;
   187       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   188         if (mm[jt]) ++num;
   189     }
   190       check(num <= 1, "INVALID PRIMAL");
   191     }
   192   }
   193 
   194   {
   195     MaxBipartiteMatching<Graph> bpmatch(graph);
   196 
   197     bpmatch.greedyInit();
   198     while (bpmatch.simpleAugment());
   199     
   200     Graph::UEdgeMap<bool> mm(graph);
   201     Graph::NodeMap<bool> cs(graph);
   202     
   203     check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
   204     
   205     for (UEdgeIt it(graph); it != INVALID; ++it) {
   206       check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
   207     }
   208     
   209     for (ANodeIt it(graph); it != INVALID; ++it) {
   210       int num = 0;
   211       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   212         if (mm[jt]) ++num;
   213     }
   214       check(num <= 1, "INVALID PRIMAL");
   215     }
   216   }
   217 
   218   {
   219     MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
   220 
   221     bpmatch.init();
   222 
   223     max_weight = 0;
   224     while (bpmatch.augment(true)) {
   225     
   226       Graph::UEdgeMap<bool> mm(graph);
   227       Graph::NodeMap<int> pm(graph);
   228       
   229       bpmatch.matching(mm);
   230       bpmatch.potential(pm);
   231       
   232       for (UEdgeIt it(graph); it != INVALID; ++it) {
   233         if (mm[it]) {
   234           check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
   235                 "INVALID DUAL");
   236         } else {
   237           check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
   238                 "INVALID DUAL");
   239         }
   240       }
   241 
   242       for (ANodeIt it(graph); it != INVALID; ++it) {
   243         int num = 0;
   244         for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   245           if (mm[jt]) ++num;
   246         }
   247         check(num <= 1, "INVALID PRIMAL");
   248       }
   249       if (bpmatch.matchingValue() > max_weight) {
   250         max_weight = bpmatch.matchingValue();
   251       }
   252     }
   253   }
   254 
   255   {
   256     Graph::UEdgeMap<bool> mm(graph);
   257 
   258     check(max_weight == maxWeightedBipartiteMatching(graph, weight, mm),
   259           "WRONG MATCHING");
   260     
   261     for (ANodeIt it(graph); it != INVALID; ++it) {
   262       int num = 0;
   263       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   264         if (mm[jt]) ++num;
   265       }
   266       check(num <= 1, "INVALID PRIMAL");
   267     }
   268   }
   269 
   270   {
   271     MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
   272 
   273     bpmatch.run();
   274     
   275     Graph::UEdgeMap<bool> mm(graph);
   276     Graph::NodeMap<int> pm(graph);
   277 
   278     bpmatch.matching(mm);
   279     bpmatch.potential(pm);
   280     
   281     for (UEdgeIt it(graph); it != INVALID; ++it) {
   282       if (mm[it]) {
   283         check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
   284               "INVALID DUAL");
   285       } else {
   286         check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
   287               "INVALID DUAL");
   288       }
   289     }
   290 
   291     for (ANodeIt it(graph); it != INVALID; ++it) {
   292       int num = 0;
   293       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   294         if (mm[jt]) ++num;
   295     }
   296       check(num <= 1, "INVALID PRIMAL");
   297     }
   298     check(max_weight == bpmatch.matchingValue(), "WRONG WEIGHT");
   299   }
   300 
   301   {
   302     MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
   303 
   304     bpmatch.run(true);
   305     
   306     Graph::UEdgeMap<bool> mm(graph);
   307     Graph::NodeMap<int> pm(graph);
   308 
   309     bpmatch.matching(mm);
   310     bpmatch.potential(pm);
   311     
   312     for (UEdgeIt it(graph); it != INVALID; ++it) {
   313       if (mm[it]) {
   314         check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
   315               "INVALID DUAL");
   316       } else {
   317         check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
   318               "INVALID DUAL");
   319       }
   320     }
   321 
   322     for (ANodeIt it(graph); it != INVALID; ++it) {
   323       int num = 0;
   324       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   325         if (mm[jt]) ++num;
   326     }
   327       check(num <= 1, "INVALID PRIMAL");
   328     }
   329     check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
   330     max_cardinality_max_weight = bpmatch.matchingValue();
   331 
   332   }
   333 
   334   {
   335     Graph::UEdgeMap<bool> mm(graph);
   336 
   337     check(max_cardinality_max_weight == 
   338           maxWeightedMaxBipartiteMatching(graph, weight, mm),
   339           "WRONG MATCHING");
   340     
   341     for (ANodeIt it(graph); it != INVALID; ++it) {
   342       int num = 0;
   343       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   344         if (mm[jt]) ++num;
   345       }
   346       check(num <= 1, "INVALID PRIMAL");
   347     }
   348   }
   349 
   350   Graph::UEdgeMap<int> cost(graph);
   351   cost = subMap(constMap<UEdge>(CC), weight);
   352   {
   353 
   354     MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost);
   355 
   356     bpmatch.run();
   357     
   358     Graph::UEdgeMap<bool> mm(graph);
   359     Graph::NodeMap<int> pm(graph);
   360 
   361     bpmatch.matching(mm);
   362     bpmatch.potential(pm);
   363     
   364     min_cost_matching = bpmatch.matchingCost();
   365     check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
   366     check(max_cardinality * CC - max_cardinality_max_weight 
   367           == bpmatch.matchingCost(), "WRONG SIZE");
   368 
   369     for (UEdgeIt it(graph); it != INVALID; ++it) {
   370       if (mm[it]) {
   371         check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] == 0,
   372               "INVALID DUAL");
   373       } else {
   374         check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] >= 0,
   375               "INVALID DUAL");
   376       }
   377     }
   378 
   379     for (ANodeIt it(graph); it != INVALID; ++it) {
   380       int num = 0;
   381       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   382         if (mm[jt]) ++num;
   383     }
   384       check(num <= 1, "INVALID PRIMAL");
   385     }
   386 
   387     min_cost_matching = bpmatch.matchingCost();
   388     check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
   389     check(max_cardinality * CC - max_cardinality_max_weight 
   390           == bpmatch.matchingCost(), "WRONG SIZE");
   391 
   392   }
   393 
   394   {
   395     Graph::UEdgeMap<bool> mm(graph);
   396 
   397     check(min_cost_matching == 
   398           minCostMaxBipartiteMatching(graph, cost, mm),
   399           "WRONG MATCHING");
   400     
   401     for (ANodeIt it(graph); it != INVALID; ++it) {
   402       int num = 0;
   403       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   404         if (mm[jt]) ++num;
   405       }
   406       check(num <= 1, "INVALID PRIMAL");
   407     }
   408   }
   409 
   410   return 0;
   411 }