lemon-0.x: test/bipartite_matching

     1 #include <cstdlib>

     2 #include <iostream>

     3 #include <sstream>

     5 #include <lemon/list_graph.h>

     7 #include <lemon/bpugraph_adaptor.h>

     8 #include <lemon/bipartite_matching.h>

    10 #include <lemon/graph_utils.h>

    12 #include <lemon/maps.h>

    14 #include "test_tools.h"

    16 using namespace std;

    17 using namespace lemon;

    19 typedef ListBpUGraph Graph;

    20 BPUGRAPH_TYPEDEFS(Graph);

    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;

    31   Graph::UEdgeMap<int> weight(graph);

    33   int max_cardinality;

    34   int max_weight;

    35   int max_cardinality_max_weight;

    36   int min_cost_matching;

    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   }

    53   {

    54     MaxBipartiteMatching<Graph> bpmatch(graph);

    56     bpmatch.run();

    58     Graph::UEdgeMap<bool> mm(graph);

    59     Graph::NodeMap<bool> cs(graph);

    61     check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");

    63     for (UEdgeIt it(graph); it != INVALID; ++it) {

    64       check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");

    65     }

    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   }

    77   {

    78     Graph::UEdgeMap<bool> mm(graph);

    80     check(max_cardinality == maxBipartiteMatching(graph, mm),

    81           "WRONG MATCHING");

    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   }

    92   {

    93     MaxBipartiteMatching<Graph> bpmatch(graph);

    95     bpmatch.greedyInit();

    96     bpmatch.start();

    98     Graph::UEdgeMap<bool> mm(graph);

    99     Graph::NodeMap<bool> cs(graph);

   101     check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");

   103     for (UEdgeIt it(graph); it != INVALID; ++it) {

   104       check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");

   105     }

   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   }

   116   {

   117     MaxBipartiteMatching<Graph> bpmatch(graph);

   119     bpmatch.greedyInit();

   120     while (bpmatch.simpleAugment());

   122     Graph::UEdgeMap<bool> mm(graph);

   123     Graph::NodeMap<bool> cs(graph);

   125     check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");

   127     for (UEdgeIt it(graph); it != INVALID; ++it) {

   128       check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");

   129     }

   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   }

   140   {

   141     MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);

   143     bpmatch.init();

   145     max_weight = 0;

   146     while (bpmatch.augment(true)) {

   148       Graph::UEdgeMap<bool> mm(graph);

   149       Graph::NodeMap<int> pm(graph);

   151       bpmatch.matching(mm);

   152       bpmatch.potential(pm);

   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       }

   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   }

   177   {

   178     Graph::UEdgeMap<bool> mm(graph);

   180     check(max_weight == maxWeightedBipartiteMatching(graph, weight, mm),

   181           "WRONG MATCHING");

   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   }

   192   {

   193     MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);

   195     bpmatch.run();

   197     Graph::UEdgeMap<bool> mm(graph);

   198     Graph::NodeMap<int> pm(graph);

   200     bpmatch.matching(mm);

   201     bpmatch.potential(pm);

   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     }

   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   }

   223   {

   224     MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);

   226     bpmatch.run(true);

   228     Graph::UEdgeMap<bool> mm(graph);

   229     Graph::NodeMap<int> pm(graph);

   231     bpmatch.matching(mm);

   232     bpmatch.potential(pm);

   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     }

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

   254   }

   256   {

   257     Graph::UEdgeMap<bool> mm(graph);

   259     check(max_cardinality_max_weight ==

   260           maxWeightedMaxBipartiteMatching(graph, weight, mm),

   261           "WRONG MATCHING");

   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   }

   272   Graph::UEdgeMap<int> cost(graph);

   273   cost = subMap(constMap<UEdge>(c), weight);

   275   {

   277     MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost);

   279     bpmatch.run();

   281     Graph::UEdgeMap<bool> mm(graph);

   282     Graph::NodeMap<int> pm(graph);

   284     bpmatch.matching(mm);

   285     bpmatch.potential(pm);

   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     }

   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     }

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

   310   }

   312   {

   313     Graph::UEdgeMap<bool> mm(graph);

   315     check(min_cost_matching ==

   316           minCostMaxBipartiteMatching(graph, cost, mm),

   317           "WRONG MATCHING");

   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   }

   328   return 0;

   329 }

author	alpar
	Tue, 16 May 2006 16:59:57 +0000
changeset 2086	3fc072264f77
parent 2051	08652c1763f6
child 2115	4cd528a30ec1
permissions	-rw-r--r--