lemon-0.x: test/bipartite_matching

     1 #include <cstdlib>

     2 #include <iostream>

     3 #include <sstream>

     5 #include <lemon/smart_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 SmartBpUGraph Graph;

    20 BPUGRAPH_TYPEDEFS(Graph);

    22 const int n = 10;

    23 const int m = 10;

    24 const int e = 52;

    25 const int c = 100;

    27 const int sa[e] = { 6, 5, 6, 4, 1, 0, 9, 5, 2, 4, 4, 3, 5,

    28                     2, 3, 8, 3, 4, 9, 6, 9, 4, 3, 1, 5, 8,

    29                     4, 8, 9, 2, 2, 3, 0, 5, 2, 3, 6, 3, 8,

    30                     8, 4, 0, 9, 9, 6, 2, 1, 2, 7, 1, 9, 4};

    32 const int ta[e] = { 2, 7, 4, 8, 6, 3, 4, 1, 7, 7, 0, 1, 6,

    33                     3, 2, 6, 8, 3, 5, 6, 3, 1, 8, 7, 2, 0,

    34                     6, 9, 6, 7, 8, 3, 3, 4, 5, 8, 6, 4, 1,

    35                     4, 3, 3, 8, 7, 7, 3, 7, 7, 3, 5, 1, 6};

    37 const int wa[e] = { 3, 99, 85, 16, 79, 52, 83, 99, 62, 6, 42, 6, 95,

    38                     13, 34, 9, 5, 38, 39, 75, 99, 12, 73, 35, 93, 43,

    39                     54, 91, 45, 26, 77, 47, 11, 22, 50, 74, 37, 64, 91,

    40                     60, 6, 92, 29, 46, 34, 84, 67, 34, 45, 0, 39, 47};

    43 int main() {

    44   Graph graph;

    45   vector<Node> aNodes;

    46   vector<Node> bNodes;

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

    50   int max_cardinality;

    51   int max_weight;

    52   int max_cardinality_max_weight;

    53   int min_cost_matching;

    55   for (int i = 0; i < n; ++i) {

    56     Node node = graph.addANode();

    57     aNodes.push_back(node);

    58   }

    59   for (int i = 0; i < m; ++i) {

    60     Node node = graph.addBNode();

    61     bNodes.push_back(node);

    62   }

    63   for (int i = 0; i < e; ++i) {

    64     Node aNode = aNodes[sa[i]];

    65     Node bNode = bNodes[ta[i]];

    66     UEdge uedge = graph.addEdge(aNode, bNode);

    67     weight[uedge] = wa[i];

    68   }

    71   {

    72     MaxBipartiteMatching<Graph> bpmatch(graph);

    74     bpmatch.run();

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

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

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

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

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

    83     }

    85     for (ANodeIt it(graph); it != INVALID; ++it) {

    86       int num = 0;

    87       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {

    88         if (mm[jt]) ++num;

    89       }

    90       check(num <= 1, "INVALID PRIMAL");

    91     }

    92     max_cardinality = bpmatch.matchingSize();

    93   }

    95   {

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

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

    99           "WRONG MATCHING");

   101     for (ANodeIt it(graph); it != INVALID; ++it) {

   102       int num = 0;

   103       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {

   104         if (mm[jt]) ++num;

   105       }

   106       check(num <= 1, "INVALID PRIMAL");

   107     }

   108   }

   110   {

   111     MaxBipartiteMatching<Graph> bpmatch(graph);

   113     bpmatch.greedyInit();

   114     bpmatch.start();

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

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

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

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

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

   123     }

   125     for (ANodeIt it(graph); it != INVALID; ++it) {

   126       int num = 0;

   127       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {

   128         if (mm[jt]) ++num;

   129     }

   130       check(num <= 1, "INVALID PRIMAL");

   131     }

   132   }

   134   {

   135     MaxBipartiteMatching<Graph> bpmatch(graph);

   137     bpmatch.greedyInit();

   138     while (bpmatch.simpleAugment());

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

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

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

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

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

   147     }

   149     for (ANodeIt it(graph); it != INVALID; ++it) {

   150       int num = 0;

   151       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {

   152         if (mm[jt]) ++num;

   153     }

   154       check(num <= 1, "INVALID PRIMAL");

   155     }

   156   }

   158   {

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

   161     bpmatch.init();

   163     max_weight = 0;

   164     while (bpmatch.augment(true)) {

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

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

   169       bpmatch.matching(mm);

   170       bpmatch.potential(pm);

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

   173         if (mm[it]) {

   174           check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,

   175                 "INVALID DUAL");

   176         } else {

   177           check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,

   178                 "INVALID DUAL");

   179         }

   180       }

   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       if (bpmatch.matchingValue() > max_weight) {

   190         max_weight = bpmatch.matchingValue();

   191       }

   192     }

   193   }

   195   {

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

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

   199           "WRONG MATCHING");

   201     for (ANodeIt it(graph); it != INVALID; ++it) {

   202       int num = 0;

   203       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {

   204         if (mm[jt]) ++num;

   205       }

   206       check(num <= 1, "INVALID PRIMAL");

   207     }

   208   }

   210   {

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

   213     bpmatch.run();

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

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

   218     bpmatch.matching(mm);

   219     bpmatch.potential(pm);

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

   222       if (mm[it]) {

   223         check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,

   224               "INVALID DUAL");

   225       } else {

   226         check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,

   227               "INVALID DUAL");

   228       }

   229     }

   231     for (ANodeIt it(graph); it != INVALID; ++it) {

   232       int num = 0;

   233       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {

   234         if (mm[jt]) ++num;

   235     }

   236       check(num <= 1, "INVALID PRIMAL");

   237     }

   238     check(max_weight == bpmatch.matchingValue(), "WRONG WEIGHT");

   239   }

   241   {

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

   244     bpmatch.run(true);

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

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

   249     bpmatch.matching(mm);

   250     bpmatch.potential(pm);

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

   253       if (mm[it]) {

   254         check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,

   255               "INVALID DUAL");

   256       } else {

   257         check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,

   258               "INVALID DUAL");

   259       }

   260     }

   262     for (ANodeIt it(graph); it != INVALID; ++it) {

   263       int num = 0;

   264       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {

   265         if (mm[jt]) ++num;

   266     }

   267       check(num <= 1, "INVALID PRIMAL");

   268     }

   269     check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");

   270     max_cardinality_max_weight = bpmatch.matchingValue();

   272   }

   274   {

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

   277     check(max_cardinality_max_weight ==

   278           maxWeightedMaxBipartiteMatching(graph, weight, mm),

   279           "WRONG MATCHING");

   281     for (ANodeIt it(graph); it != INVALID; ++it) {

   282       int num = 0;

   283       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {

   284         if (mm[jt]) ++num;

   285       }

   286       check(num <= 1, "INVALID PRIMAL");

   287     }

   288   }

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

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

   292   {

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

   296     bpmatch.run();

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

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

   301     bpmatch.matching(mm);

   302     bpmatch.potential(pm);

   304     min_cost_matching = bpmatch.matchingCost();

   305     check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");

   306     check(max_cardinality * c - max_cardinality_max_weight

   307           == bpmatch.matchingCost(), "WRONG SIZE");

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

   310       if (mm[it]) {

   311         check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] == 0,

   312               "INVALID DUAL");

   313       } else {

   314         check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] >= 0,

   315               "INVALID DUAL");

   316       }

   317     }

   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     }

   327     min_cost_matching = bpmatch.matchingCost();

   328     check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");

   329     check(max_cardinality * c - max_cardinality_max_weight

   330           == bpmatch.matchingCost(), "WRONG SIZE");

   332   }

   334   {

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

   337     check(min_cost_matching ==

   338           minCostMaxBipartiteMatching(graph, cost, mm),

   339           "WRONG MATCHING");

   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   }

   350   return 0;

   351 }

author	athos
	Mon, 02 Oct 2006 14:41:53 +0000
changeset 2228	f71b0f9a7c3a
parent 2116	b6a68c15a6a3
child 2386	81b47fc5c444
permissions	-rw-r--r--