1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/test/bipartite_matching_test.cc	Fri Apr 07 09:51:23 2006 +0000
     1.3 @@ -0,0 +1,138 @@
     1.4 +#include <cstdlib>
     1.5 +#include <iostream>
     1.6 +#include <sstream>
     1.7 +
     1.8 +#include <lemon/list_graph.h>
     1.9 +
    1.10 +#include <lemon/bpugraph_adaptor.h>
    1.11 +#include <lemon/bipartite_matching.h>
    1.12 +
    1.13 +#include <lemon/graph_utils.h>
    1.14 +
    1.15 +#include "test_tools.h"
    1.16 +
    1.17 +using namespace std;
    1.18 +using namespace lemon;
    1.19 +
    1.20 +typedef ListBpUGraph Graph;
    1.21 +BPUGRAPH_TYPEDEFS(Graph);
    1.22 +
    1.23 +int main(int argc, const char *argv[]) {
    1.24 +  Graph graph;
    1.25 +  vector<Node> aNodes;
    1.26 +  vector<Node> bNodes;
    1.27 +  int n = argc > 1 ? atoi(argv[1]) : 100;
    1.28 +  int m = argc > 2 ? atoi(argv[2]) : 100;
    1.29 +  int e = argc > 3 ? atoi(argv[3]) : (int)((n+m) * log(n+m));
    1.30 +
    1.31 +  for (int i = 0; i < n; ++i) {
    1.32 +    Node node = graph.addANode();
    1.33 +    aNodes.push_back(node);
    1.34 +  }
    1.35 +  for (int i = 0; i < m; ++i) {
    1.36 +    Node node = graph.addBNode();
    1.37 +    bNodes.push_back(node);
    1.38 +  }
    1.39 +  for (int i = 0; i < e; ++i) {
    1.40 +    Node aNode = aNodes[urandom(n)];
    1.41 +    Node bNode = bNodes[urandom(m)];
    1.42 +    graph.addEdge(aNode, bNode);
    1.43 +  }
    1.44 +
    1.45 +  {
    1.46 +    MaxBipartiteMatching<Graph> bpmatch(graph);
    1.47 +
    1.48 +    bpmatch.run();
    1.49 +
    1.50 +    Graph::UEdgeMap<bool> mm(graph);
    1.51 +    Graph::NodeMap<bool> cs(graph);
    1.52 +    
    1.53 +    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
    1.54 +    
    1.55 +    for (UEdgeIt it(graph); it != INVALID; ++it) {
    1.56 +      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
    1.57 +    }
    1.58 +    
    1.59 +    for (ANodeIt it(graph); it != INVALID; ++it) {
    1.60 +      int num = 0;
    1.61 +      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
    1.62 +        if (mm[jt]) ++num;
    1.63 +    }
    1.64 +      check(num <= 1, "INVALID PRIMAL");
    1.65 +    }
    1.66 +  }
    1.67 +
    1.68 +  {
    1.69 +    MaxBipartiteMatching<Graph> bpmatch(graph);
    1.70 +
    1.71 +    bpmatch.greedyInit();
    1.72 +    bpmatch.start();
    1.73 +
    1.74 +    Graph::UEdgeMap<bool> mm(graph);
    1.75 +    Graph::NodeMap<bool> cs(graph);
    1.76 +
    1.77 +    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
    1.78 +    
    1.79 +    for (UEdgeIt it(graph); it != INVALID; ++it) {
    1.80 +      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
    1.81 +    }
    1.82 +    
    1.83 +    for (ANodeIt it(graph); it != INVALID; ++it) {
    1.84 +      int num = 0;
    1.85 +      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
    1.86 +        if (mm[jt]) ++num;
    1.87 +    }
    1.88 +      check(num <= 1, "INVALID PRIMAL");
    1.89 +    }
    1.90 +  }
    1.91 +
    1.92 +  {
    1.93 +    MaxBipartiteMatching<Graph> bpmatch(graph);
    1.94 +
    1.95 +    bpmatch.greedyInit();
    1.96 +    while (bpmatch.simpleAugment());
    1.97 +    
    1.98 +    Graph::UEdgeMap<bool> mm(graph);
    1.99 +    Graph::NodeMap<bool> cs(graph);
   1.100 +    
   1.101 +    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
   1.102 +    
   1.103 +    for (UEdgeIt it(graph); it != INVALID; ++it) {
   1.104 +      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
   1.105 +    }
   1.106 +    
   1.107 +    for (ANodeIt it(graph); it != INVALID; ++it) {
   1.108 +      int num = 0;
   1.109 +      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   1.110 +        if (mm[jt]) ++num;
   1.111 +    }
   1.112 +      check(num <= 1, "INVALID PRIMAL");
   1.113 +    }
   1.114 +  }
   1.115 +
   1.116 +  {
   1.117 +    SwapBpUGraphAdaptor<Graph> swapgraph(graph);
   1.118 +    MaxBipartiteMatching<SwapBpUGraphAdaptor<Graph> > bpmatch(swapgraph);
   1.119 +
   1.120 +    bpmatch.run();
   1.121 +
   1.122 +    Graph::UEdgeMap<bool> mm(graph);
   1.123 +    Graph::NodeMap<bool> cs(graph);
   1.124 +    
   1.125 +    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
   1.126 +    
   1.127 +    for (UEdgeIt it(graph); it != INVALID; ++it) {
   1.128 +      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
   1.129 +    }
   1.130 +    
   1.131 +    for (ANodeIt it(graph); it != INVALID; ++it) {
   1.132 +      int num = 0;
   1.133 +      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   1.134 +        if (mm[jt]) ++num;
   1.135 +    }
   1.136 +      check(num <= 1, "INVALID PRIMAL");
   1.137 +    }
   1.138 +  }
   1.139 +
   1.140 +  return 0;
   1.141 +}