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]) : 100;

    27   int m = argc > 2 ? atoi(argv[2]) : 100;

    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;

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

    38     Node node = graph.addANode();

    39     aNodes.push_back(node);

    40   }

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

    42     Node node = graph.addBNode();

    43     bNodes.push_back(node);

    44   }

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

    46     Node aNode = aNodes[urandom(n)];

    47     Node bNode = bNodes[urandom(m)];

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

    49     weight[uedge] = urandom(c);

    50   }

    52   {

    53     MaxBipartiteMatching<Graph> bpmatch(graph);

    55     bpmatch.run();

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

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

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

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

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

    64     }

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

    67       int num = 0;

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

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

    70       }

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

    72     }

    73     max_cardinality = bpmatch.matchingSize();

    74   }

    76   {

    77     MaxBipartiteMatching<Graph> bpmatch(graph);

    79     bpmatch.greedyInit();

    80     bpmatch.start();

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

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

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

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

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

    89     }

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

    92       int num = 0;

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

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

    95     }

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

    97     }

    98   }

   100   {

   101     MaxBipartiteMatching<Graph> bpmatch(graph);

   103     bpmatch.greedyInit();

   104     while (bpmatch.simpleAugment());

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

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

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

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

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

   113     }

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

   116       int num = 0;

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

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

   119     }

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

   121     }

   122   }

   124   {

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

   127     bpmatch.init();

   129     max_weight = 0;

   130     while (bpmatch.augment(true)) {

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

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

   135       bpmatch.matching(mm);

   136       bpmatch.potential(pm);

   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       }

   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   }

   161   {

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

   164     bpmatch.run();

   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)] - weight[it] - pm[graph.bNode(it)] == 0,

   175               "INVALID DUAL");

   176       } else {

   177         check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(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     check(max_weight == bpmatch.matchingValue(), "WRONG WEIGHT");

   190   }

   192   {

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

   195     bpmatch.run(true);

   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)] - 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     }

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

   223   }

   225   {

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

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

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

   232     bpmatch.run();

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

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

   237     bpmatch.matching(mm);

   238     bpmatch.potential(pm);

   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     }

   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     }

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

   259     check(max_cardinality * c - max_cardinality_max_weight

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

   262   }

   264   return 0;

   265 }

author	deba
	Fri, 14 Apr 2006 18:07:33 +0000
changeset 2051	08652c1763f6
parent 2040	c7bd55c0d820
child 2058	0b1fc1566fdb
permissions	-rw-r--r--