Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
test/bipartite_matching_test.cc
changeset 2053 7230185f0bd1
parent 2040 c7bd55c0d820
child 2058 0b1fc1566fdb
equal deleted inserted replaced
0:dee547b77760 1:66ad70027fbc 
     6 
     6 
     7 #include <lemon/bpugraph_adaptor.h>
 
     7 #include <lemon/bpugraph_adaptor.h>
 
     8 #include <lemon/bipartite_matching.h>
 
     8 #include <lemon/bipartite_matching.h>
 
     9 
     9 
    10 #include <lemon/graph_utils.h>
 
    10 #include <lemon/graph_utils.h>
 
       
    11 
       
    12 #include <lemon/maps.h>
 
    11 
    13 
    12 #include "test_tools.h"
 
    14 #include "test_tools.h"
 
    13 
    15 
    14 using namespace std;
 
    16 using namespace std;
 
    15 using namespace lemon;
 
    17 using namespace lemon;
 
    22   vector<Node> aNodes;
 
    24   vector<Node> aNodes;
 
    23   vector<Node> bNodes;
 
    25   vector<Node> bNodes;
 
    24   int n = argc > 1 ? atoi(argv[1]) : 100;
 
    26   int n = argc > 1 ? atoi(argv[1]) : 100;
 
    25   int m = argc > 2 ? atoi(argv[2]) : 100;
 
    27   int m = argc > 2 ? atoi(argv[2]) : 100;
 
    26   int e = argc > 3 ? atoi(argv[3]) : (int)((n+m) * log(n+m));
 
    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;
 
    27 
    36 
    28   for (int i = 0; i < n; ++i) {
 
    37   for (int i = 0; i < n; ++i) {
 
    29     Node node = graph.addANode();
 
    38     Node node = graph.addANode();
 
    30     aNodes.push_back(node);
 
    39     aNodes.push_back(node);
 
    31   }
 
    40   }
 
    34     bNodes.push_back(node);
 
    43     bNodes.push_back(node);
 
    35   }
 
    44   }
 
    36   for (int i = 0; i < e; ++i) {
 
    45   for (int i = 0; i < e; ++i) {
 
    37     Node aNode = aNodes[urandom(n)];
 
    46     Node aNode = aNodes[urandom(n)];
 
    38     Node bNode = bNodes[urandom(m)];
 
    47     Node bNode = bNodes[urandom(m)];
 
    39     graph.addEdge(aNode, bNode);
 
    48     UEdge uedge = graph.addEdge(aNode, bNode);
 
       
    49     weight[uedge] = urandom(c);
 
    40   }
 
    50   }
 
    41 
    51 
    42   {
 
    52   {
 
    43     MaxBipartiteMatching<Graph> bpmatch(graph);
 
    53     MaxBipartiteMatching<Graph> bpmatch(graph);
 
    44 
    54 
    55     
    65     
    56     for (ANodeIt it(graph); it != INVALID; ++it) {
 
    66     for (ANodeIt it(graph); it != INVALID; ++it) {
 
    57       int num = 0;
 
    67       int num = 0;
 
    58       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
 
    68       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
 
    59         if (mm[jt]) ++num;
 
    69         if (mm[jt]) ++num;
 
    60     }
 
    70       }
 
    61       check(num <= 1, "INVALID PRIMAL");
 
    71       check(num <= 1, "INVALID PRIMAL");
 
    62     }
 
    72     }
 
       
    73     max_cardinality = bpmatch.matchingSize();
 
    63   }
 
    74   }
 
    64 
    75 
    65   {
 
    76   {
 
    66     MaxBipartiteMatching<Graph> bpmatch(graph);
 
    77     MaxBipartiteMatching<Graph> bpmatch(graph);
 
    67 
    78 
   109       check(num <= 1, "INVALID PRIMAL");
 
   120       check(num <= 1, "INVALID PRIMAL");
 
   110     }
 
   121     }
 
   111   }
 
   122   }
 
   112 
   123 
   113   {
 
   124   {
 
   114     SwapBpUGraphAdaptor<Graph> swapgraph(graph);
 
   125     MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
 
   115     MaxBipartiteMatching<SwapBpUGraphAdaptor<Graph> > bpmatch(swapgraph);
 
   126 
       
   127     bpmatch.init();
 
       
   128 
       
   129     max_weight = 0;
 
       
   130     while (bpmatch.augment(true)) {
 
       
   131     
       
   132       Graph::UEdgeMap<bool> mm(graph);
 
       
   133       Graph::NodeMap<int> pm(graph);
 
       
   134       
       
   135       bpmatch.matching(mm);
 
       
   136       bpmatch.potential(pm);
 
       
   137       
       
   138       for (UEdgeIt it(graph); it != INVALID; ++it) {
 
       
   139         if (mm[it]) {
 
       
   140           check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0,
 
       
   141                 "INVALID DUAL");
 
       
   142         } else {
 
       
   143           check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0,
 
       
   144                 "INVALID DUAL");
 
       
   145         }
 
       
   146       }
 
       
   147 
       
   148       for (ANodeIt it(graph); it != INVALID; ++it) {
 
       
   149         int num = 0;
 
       
   150         for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
 
       
   151           if (mm[jt]) ++num;
 
       
   152         }
 
       
   153         check(num <= 1, "INVALID PRIMAL");
 
       
   154       }
 
       
   155       if (bpmatch.matchingValue() > max_weight) {
 
       
   156         max_weight = bpmatch.matchingValue();
 
       
   157       }
 
       
   158     }
 
       
   159   }
 
       
   160 
       
   161   {
 
       
   162     MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
 
   116 
   163 
   117     bpmatch.run();
 
   164     bpmatch.run();
 
   118 
   165     
   119     Graph::UEdgeMap<bool> mm(graph);
 
   166     Graph::UEdgeMap<bool> mm(graph);
 
   120     Graph::NodeMap<bool> cs(graph);
 
   167     Graph::NodeMap<int> pm(graph);
 
   121     
   168 
   122     check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
 
   169     bpmatch.matching(mm);
 
   123     
   170     bpmatch.potential(pm);
 
   124     for (UEdgeIt it(graph); it != INVALID; ++it) {
 
   171     
   125       check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
 
   172     for (UEdgeIt it(graph); it != INVALID; ++it) {
 
   126     }
 
   173       if (mm[it]) {
 
   127     
   174         check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0,
 
   128     for (ANodeIt it(graph); it != INVALID; ++it) {
 
   175               "INVALID DUAL");
 
   129       int num = 0;
 
   176       } else {
 
   130       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
 
   177         check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0,
 
   131         if (mm[jt]) ++num;
 
   178               "INVALID DUAL");
 
   132     }
 
   179       }
 
   133       check(num <= 1, "INVALID PRIMAL");
 
   180     }
 
   134     }
 
   181 
       
   182     for (ANodeIt it(graph); it != INVALID; ++it) {
 
       
   183       int num = 0;
 
       
   184       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
 
       
   185         if (mm[jt]) ++num;
 
       
   186     }
 
       
   187       check(num <= 1, "INVALID PRIMAL");
 
       
   188     }
 
       
   189     check(max_weight == bpmatch.matchingValue(), "WRONG WEIGHT");
 
       
   190   }
 
       
   191 
       
   192   {
 
       
   193     MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
 
       
   194 
       
   195     bpmatch.run(true);
 
       
   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)] - weight[it] - pm[graph.bNode(it)] == 0,
 
       
   206               "INVALID DUAL");
 
       
   207       } else {
 
       
   208         check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(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_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
 
       
   221     max_cardinality_max_weight = bpmatch.matchingValue();
 
       
   222 
       
   223   }
 
       
   224 
       
   225   {
 
       
   226     Graph::UEdgeMap<int> cost(graph);
 
       
   227 
       
   228     cost = subMap(constMap<UEdge>(c), weight);
 
       
   229 
       
   230     MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost);
 
       
   231 
       
   232     bpmatch.run();
 
       
   233     
       
   234     Graph::UEdgeMap<bool> mm(graph);
 
       
   235     Graph::NodeMap<int> pm(graph);
 
       
   236 
       
   237     bpmatch.matching(mm);
 
       
   238     bpmatch.potential(pm);
 
       
   239     
       
   240     for (UEdgeIt it(graph); it != INVALID; ++it) {
 
       
   241       if (mm[it]) {
 
       
   242         check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] == 0,
 
       
   243               "INVALID DUAL");
 
       
   244       } else {
 
       
   245         check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] >= 0,
 
       
   246               "INVALID DUAL");
 
       
   247       }
 
       
   248     }
 
       
   249 
       
   250     for (ANodeIt it(graph); it != INVALID; ++it) {
 
       
   251       int num = 0;
 
       
   252       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
 
       
   253         if (mm[jt]) ++num;
 
       
   254     }
 
       
   255       check(num <= 1, "INVALID PRIMAL");
 
       
   256     }
 
       
   257 
       
   258     check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
 
       
   259     check(max_cardinality * c - max_cardinality_max_weight 
       
   260           == bpmatch.matchingCost(), "WRONG SIZE");
 
       
   261 
   135   }
 
   262   }
 
   136 
   263 
   137   return 0;
 
   264   return 0;
 
   138 }
 
   265 }
lemon-0.x