test/bipartite_matching_test.cc
author klao
Thu, 13 Apr 2006 17:57:03 +0000
changeset 2046 66d160810c0a
child 2051 08652c1763f6
permissions -rw-r--r--
more explicit :)
     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 "test_tools.h"
    13 
    14 using namespace std;
    15 using namespace lemon;
    16 
    17 typedef ListBpUGraph Graph;
    18 BPUGRAPH_TYPEDEFS(Graph);
    19 
    20 int main(int argc, const char *argv[]) {
    21   Graph graph;
    22   vector<Node> aNodes;
    23   vector<Node> bNodes;
    24   int n = argc > 1 ? atoi(argv[1]) : 100;
    25   int m = argc > 2 ? atoi(argv[2]) : 100;
    26   int e = argc > 3 ? atoi(argv[3]) : (int)((n+m) * log(n+m));
    27 
    28   for (int i = 0; i < n; ++i) {
    29     Node node = graph.addANode();
    30     aNodes.push_back(node);
    31   }
    32   for (int i = 0; i < m; ++i) {
    33     Node node = graph.addBNode();
    34     bNodes.push_back(node);
    35   }
    36   for (int i = 0; i < e; ++i) {
    37     Node aNode = aNodes[urandom(n)];
    38     Node bNode = bNodes[urandom(m)];
    39     graph.addEdge(aNode, bNode);
    40   }
    41 
    42   {
    43     MaxBipartiteMatching<Graph> bpmatch(graph);
    44 
    45     bpmatch.run();
    46 
    47     Graph::UEdgeMap<bool> mm(graph);
    48     Graph::NodeMap<bool> cs(graph);
    49     
    50     check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
    51     
    52     for (UEdgeIt it(graph); it != INVALID; ++it) {
    53       check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
    54     }
    55     
    56     for (ANodeIt it(graph); it != INVALID; ++it) {
    57       int num = 0;
    58       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
    59         if (mm[jt]) ++num;
    60     }
    61       check(num <= 1, "INVALID PRIMAL");
    62     }
    63   }
    64 
    65   {
    66     MaxBipartiteMatching<Graph> bpmatch(graph);
    67 
    68     bpmatch.greedyInit();
    69     bpmatch.start();
    70 
    71     Graph::UEdgeMap<bool> mm(graph);
    72     Graph::NodeMap<bool> cs(graph);
    73 
    74     check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
    75     
    76     for (UEdgeIt it(graph); it != INVALID; ++it) {
    77       check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
    78     }
    79     
    80     for (ANodeIt it(graph); it != INVALID; ++it) {
    81       int num = 0;
    82       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
    83         if (mm[jt]) ++num;
    84     }
    85       check(num <= 1, "INVALID PRIMAL");
    86     }
    87   }
    88 
    89   {
    90     MaxBipartiteMatching<Graph> bpmatch(graph);
    91 
    92     bpmatch.greedyInit();
    93     while (bpmatch.simpleAugment());
    94     
    95     Graph::UEdgeMap<bool> mm(graph);
    96     Graph::NodeMap<bool> cs(graph);
    97     
    98     check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
    99     
   100     for (UEdgeIt it(graph); it != INVALID; ++it) {
   101       check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
   102     }
   103     
   104     for (ANodeIt it(graph); it != INVALID; ++it) {
   105       int num = 0;
   106       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   107         if (mm[jt]) ++num;
   108     }
   109       check(num <= 1, "INVALID PRIMAL");
   110     }
   111   }
   112 
   113   {
   114     SwapBpUGraphAdaptor<Graph> swapgraph(graph);
   115     MaxBipartiteMatching<SwapBpUGraphAdaptor<Graph> > bpmatch(swapgraph);
   116 
   117     bpmatch.run();
   118 
   119     Graph::UEdgeMap<bool> mm(graph);
   120     Graph::NodeMap<bool> cs(graph);
   121     
   122     check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
   123     
   124     for (UEdgeIt it(graph); it != INVALID; ++it) {
   125       check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
   126     }
   127     
   128     for (ANodeIt it(graph); it != INVALID; ++it) {
   129       int num = 0;
   130       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   131         if (mm[jt]) ++num;
   132     }
   133       check(num <= 1, "INVALID PRIMAL");
   134     }
   135   }
   136 
   137   return 0;
   138 }