test/bipartite_matching_test.cc
author alpar
Tue, 09 May 2006 09:21:02 +0000
changeset 2071 00c4ce4f4170
parent 2051 08652c1763f6
child 2115 4cd528a30ec1
permissions -rw-r--r--
Also install .gif files.
     1 #include <cstdlib>
     2 #include <iostream>
     3 #include <sstream>
     4 
     5 #include <lemon/list_graph.h>
     6 
     7 #include <lemon/bpugraph_adaptor.h>
     8 #include <lemon/bipartite_matching.h>
     9 
    10 #include <lemon/graph_utils.h>
    11 
    12 #include <lemon/maps.h>
    13 
    14 #include "test_tools.h"
    15 
    16 using namespace std;
    17 using namespace lemon;
    18 
    19 typedef ListBpUGraph Graph;
    20 BPUGRAPH_TYPEDEFS(Graph);
    21 
    22 int main(int argc, const char *argv[]) {
    23   Graph graph;
    24   vector<Node> aNodes;
    25   vector<Node> bNodes;
    26   int n = argc > 1 ? atoi(argv[1]) : 10;
    27   int m = argc > 2 ? atoi(argv[2]) : 10;
    28   int e = argc > 3 ? atoi(argv[3]) : (int)((n+m) * log(n+m));
    29   int c = argc > 4 ? atoi(argv[4]) : 100;
    30 
    31   Graph::UEdgeMap<int> weight(graph);
    32 
    33   int max_cardinality;
    34   int max_weight;
    35   int max_cardinality_max_weight;
    36   int min_cost_matching;
    37 
    38   for (int i = 0; i < n; ++i) {
    39     Node node = graph.addANode();
    40     aNodes.push_back(node);
    41   }
    42   for (int i = 0; i < m; ++i) {
    43     Node node = graph.addBNode();
    44     bNodes.push_back(node);
    45   }
    46   for (int i = 0; i < e; ++i) {
    47     Node aNode = aNodes[urandom(n)];
    48     Node bNode = bNodes[urandom(m)];
    49     UEdge uedge = graph.addEdge(aNode, bNode);
    50     weight[uedge] = urandom(c);
    51   }
    52 
    53   {
    54     MaxBipartiteMatching<Graph> bpmatch(graph);
    55 
    56     bpmatch.run();
    57 
    58     Graph::UEdgeMap<bool> mm(graph);
    59     Graph::NodeMap<bool> cs(graph);
    60     
    61     check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
    62     
    63     for (UEdgeIt it(graph); it != INVALID; ++it) {
    64       check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
    65     }
    66     
    67     for (ANodeIt it(graph); it != INVALID; ++it) {
    68       int num = 0;
    69       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
    70         if (mm[jt]) ++num;
    71       }
    72       check(num <= 1, "INVALID PRIMAL");
    73     }
    74     max_cardinality = bpmatch.matchingSize();
    75   }
    76 
    77   {
    78     Graph::UEdgeMap<bool> mm(graph);
    79 
    80     check(max_cardinality == maxBipartiteMatching(graph, mm),
    81           "WRONG MATCHING");
    82     
    83     for (ANodeIt it(graph); it != INVALID; ++it) {
    84       int num = 0;
    85       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
    86         if (mm[jt]) ++num;
    87       }
    88       check(num <= 1, "INVALID PRIMAL");
    89     }
    90   }
    91 
    92   {
    93     MaxBipartiteMatching<Graph> bpmatch(graph);
    94 
    95     bpmatch.greedyInit();
    96     bpmatch.start();
    97 
    98     Graph::UEdgeMap<bool> mm(graph);
    99     Graph::NodeMap<bool> cs(graph);
   100 
   101     check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
   102     
   103     for (UEdgeIt it(graph); it != INVALID; ++it) {
   104       check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
   105     }
   106     
   107     for (ANodeIt it(graph); it != INVALID; ++it) {
   108       int num = 0;
   109       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   110         if (mm[jt]) ++num;
   111     }
   112       check(num <= 1, "INVALID PRIMAL");
   113     }
   114   }
   115 
   116   {
   117     MaxBipartiteMatching<Graph> bpmatch(graph);
   118 
   119     bpmatch.greedyInit();
   120     while (bpmatch.simpleAugment());
   121     
   122     Graph::UEdgeMap<bool> mm(graph);
   123     Graph::NodeMap<bool> cs(graph);
   124     
   125     check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
   126     
   127     for (UEdgeIt it(graph); it != INVALID; ++it) {
   128       check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
   129     }
   130     
   131     for (ANodeIt it(graph); it != INVALID; ++it) {
   132       int num = 0;
   133       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   134         if (mm[jt]) ++num;
   135     }
   136       check(num <= 1, "INVALID PRIMAL");
   137     }
   138   }
   139 
   140   {
   141     MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
   142 
   143     bpmatch.init();
   144 
   145     max_weight = 0;
   146     while (bpmatch.augment(true)) {
   147     
   148       Graph::UEdgeMap<bool> mm(graph);
   149       Graph::NodeMap<int> pm(graph);
   150       
   151       bpmatch.matching(mm);
   152       bpmatch.potential(pm);
   153       
   154       for (UEdgeIt it(graph); it != INVALID; ++it) {
   155         if (mm[it]) {
   156           check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
   157                 "INVALID DUAL");
   158         } else {
   159           check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
   160                 "INVALID DUAL");
   161         }
   162       }
   163 
   164       for (ANodeIt it(graph); it != INVALID; ++it) {
   165         int num = 0;
   166         for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   167           if (mm[jt]) ++num;
   168         }
   169         check(num <= 1, "INVALID PRIMAL");
   170       }
   171       if (bpmatch.matchingValue() > max_weight) {
   172         max_weight = bpmatch.matchingValue();
   173       }
   174     }
   175   }
   176 
   177   {
   178     Graph::UEdgeMap<bool> mm(graph);
   179 
   180     check(max_weight == maxWeightedBipartiteMatching(graph, weight, mm),
   181           "WRONG MATCHING");
   182     
   183     for (ANodeIt it(graph); it != INVALID; ++it) {
   184       int num = 0;
   185       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   186         if (mm[jt]) ++num;
   187       }
   188       check(num <= 1, "INVALID PRIMAL");
   189     }
   190   }
   191 
   192   {
   193     MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
   194 
   195     bpmatch.run();
   196     
   197     Graph::UEdgeMap<bool> mm(graph);
   198     Graph::NodeMap<int> pm(graph);
   199 
   200     bpmatch.matching(mm);
   201     bpmatch.potential(pm);
   202     
   203     for (UEdgeIt it(graph); it != INVALID; ++it) {
   204       if (mm[it]) {
   205         check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
   206               "INVALID DUAL");
   207       } else {
   208         check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
   209               "INVALID DUAL");
   210       }
   211     }
   212 
   213     for (ANodeIt it(graph); it != INVALID; ++it) {
   214       int num = 0;
   215       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   216         if (mm[jt]) ++num;
   217     }
   218       check(num <= 1, "INVALID PRIMAL");
   219     }
   220     check(max_weight == bpmatch.matchingValue(), "WRONG WEIGHT");
   221   }
   222 
   223   {
   224     MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
   225 
   226     bpmatch.run(true);
   227     
   228     Graph::UEdgeMap<bool> mm(graph);
   229     Graph::NodeMap<int> pm(graph);
   230 
   231     bpmatch.matching(mm);
   232     bpmatch.potential(pm);
   233     
   234     for (UEdgeIt it(graph); it != INVALID; ++it) {
   235       if (mm[it]) {
   236         check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
   237               "INVALID DUAL");
   238       } else {
   239         check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
   240               "INVALID DUAL");
   241       }
   242     }
   243 
   244     for (ANodeIt it(graph); it != INVALID; ++it) {
   245       int num = 0;
   246       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   247         if (mm[jt]) ++num;
   248     }
   249       check(num <= 1, "INVALID PRIMAL");
   250     }
   251     check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
   252     max_cardinality_max_weight = bpmatch.matchingValue();
   253 
   254   }
   255 
   256   {
   257     Graph::UEdgeMap<bool> mm(graph);
   258 
   259     check(max_cardinality_max_weight == 
   260           maxWeightedMaxBipartiteMatching(graph, weight, mm),
   261           "WRONG MATCHING");
   262     
   263     for (ANodeIt it(graph); it != INVALID; ++it) {
   264       int num = 0;
   265       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   266         if (mm[jt]) ++num;
   267       }
   268       check(num <= 1, "INVALID PRIMAL");
   269     }
   270   }
   271 
   272   Graph::UEdgeMap<int> cost(graph);
   273   cost = subMap(constMap<UEdge>(c), weight);
   274 
   275   {
   276 
   277     MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost);
   278 
   279     bpmatch.run();
   280     
   281     Graph::UEdgeMap<bool> mm(graph);
   282     Graph::NodeMap<int> pm(graph);
   283 
   284     bpmatch.matching(mm);
   285     bpmatch.potential(pm);
   286     
   287     for (UEdgeIt it(graph); it != INVALID; ++it) {
   288       if (mm[it]) {
   289         check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] == 0,
   290               "INVALID DUAL");
   291       } else {
   292         check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] >= 0,
   293               "INVALID DUAL");
   294       }
   295     }
   296 
   297     for (ANodeIt it(graph); it != INVALID; ++it) {
   298       int num = 0;
   299       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   300         if (mm[jt]) ++num;
   301     }
   302       check(num <= 1, "INVALID PRIMAL");
   303     }
   304 
   305     min_cost_matching = bpmatch.matchingCost();
   306     check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
   307     check(max_cardinality * c - max_cardinality_max_weight 
   308           == bpmatch.matchingCost(), "WRONG SIZE");
   309 
   310   }
   311 
   312   {
   313     Graph::UEdgeMap<bool> mm(graph);
   314 
   315     check(min_cost_matching == 
   316           minCostMaxBipartiteMatching(graph, cost, mm),
   317           "WRONG MATCHING");
   318     
   319     for (ANodeIt it(graph); it != INVALID; ++it) {
   320       int num = 0;
   321       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   322         if (mm[jt]) ++num;
   323       }
   324       check(num <= 1, "INVALID PRIMAL");
   325     }
   326   }
   327 
   328   return 0;
   329 }