1.1 --- a/test/bipartite_matching_test.cc	Fri Apr 14 23:55:36 2006 +0000
     1.2 +++ b/test/bipartite_matching_test.cc	Tue Apr 18 07:01:55 2006 +0000
     1.3 @@ -23,8 +23,8 @@
     1.4    Graph graph;
     1.5    vector<Node> aNodes;
     1.6    vector<Node> bNodes;
     1.7 -  int n = argc > 1 ? atoi(argv[1]) : 100;
     1.8 -  int m = argc > 2 ? atoi(argv[2]) : 100;
     1.9 +  int n = argc > 1 ? atoi(argv[1]) : 10;
    1.10 +  int m = argc > 2 ? atoi(argv[2]) : 10;
    1.11    int e = argc > 3 ? atoi(argv[3]) : (int)((n+m) * log(n+m));
    1.12    int c = argc > 4 ? atoi(argv[4]) : 100;
    1.13  
    1.14 @@ -33,6 +33,7 @@
    1.15    int max_cardinality;
    1.16    int max_weight;
    1.17    int max_cardinality_max_weight;
    1.18 +  int min_cost_matching;
    1.19  
    1.20    for (int i = 0; i < n; ++i) {
    1.21      Node node = graph.addANode();
    1.22 @@ -74,6 +75,21 @@
    1.23    }
    1.24  
    1.25    {
    1.26 +    Graph::UEdgeMap<bool> mm(graph);
    1.27 +
    1.28 +    check(max_cardinality == maxBipartiteMatching(graph, mm),
    1.29 +          "WRONG MATCHING");
    1.30 +    
    1.31 +    for (ANodeIt it(graph); it != INVALID; ++it) {
    1.32 +      int num = 0;
    1.33 +      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
    1.34 +        if (mm[jt]) ++num;
    1.35 +      }
    1.36 +      check(num <= 1, "INVALID PRIMAL");
    1.37 +    }
    1.38 +  }
    1.39 +
    1.40 +  {
    1.41      MaxBipartiteMatching<Graph> bpmatch(graph);
    1.42  
    1.43      bpmatch.greedyInit();
    1.44 @@ -137,10 +153,10 @@
    1.45        
    1.46        for (UEdgeIt it(graph); it != INVALID; ++it) {
    1.47          if (mm[it]) {
    1.48 -          check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0,
    1.49 +          check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
    1.50                  "INVALID DUAL");
    1.51          } else {
    1.52 -          check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0,
    1.53 +          check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
    1.54                  "INVALID DUAL");
    1.55          }
    1.56        }
    1.57 @@ -159,6 +175,21 @@
    1.58    }
    1.59  
    1.60    {
    1.61 +    Graph::UEdgeMap<bool> mm(graph);
    1.62 +
    1.63 +    check(max_weight == maxWeightedBipartiteMatching(graph, weight, mm),
    1.64 +          "WRONG MATCHING");
    1.65 +    
    1.66 +    for (ANodeIt it(graph); it != INVALID; ++it) {
    1.67 +      int num = 0;
    1.68 +      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
    1.69 +        if (mm[jt]) ++num;
    1.70 +      }
    1.71 +      check(num <= 1, "INVALID PRIMAL");
    1.72 +    }
    1.73 +  }
    1.74 +
    1.75 +  {
    1.76      MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
    1.77  
    1.78      bpmatch.run();
    1.79 @@ -171,10 +202,10 @@
    1.80      
    1.81      for (UEdgeIt it(graph); it != INVALID; ++it) {
    1.82        if (mm[it]) {
    1.83 -        check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0,
    1.84 +        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
    1.85                "INVALID DUAL");
    1.86        } else {
    1.87 -        check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0,
    1.88 +        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
    1.89                "INVALID DUAL");
    1.90        }
    1.91      }
    1.92 @@ -202,10 +233,10 @@
    1.93      
    1.94      for (UEdgeIt it(graph); it != INVALID; ++it) {
    1.95        if (mm[it]) {
    1.96 -        check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0,
    1.97 +        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
    1.98                "INVALID DUAL");
    1.99        } else {
   1.100 -        check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0,
   1.101 +        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
   1.102                "INVALID DUAL");
   1.103        }
   1.104      }
   1.105 @@ -223,9 +254,25 @@
   1.106    }
   1.107  
   1.108    {
   1.109 -    Graph::UEdgeMap<int> cost(graph);
   1.110 +    Graph::UEdgeMap<bool> mm(graph);
   1.111  
   1.112 -    cost = subMap(constMap<UEdge>(c), weight);
   1.113 +    check(max_cardinality_max_weight == 
   1.114 +          maxWeightedMaxBipartiteMatching(graph, weight, mm),
   1.115 +          "WRONG MATCHING");
   1.116 +    
   1.117 +    for (ANodeIt it(graph); it != INVALID; ++it) {
   1.118 +      int num = 0;
   1.119 +      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   1.120 +        if (mm[jt]) ++num;
   1.121 +      }
   1.122 +      check(num <= 1, "INVALID PRIMAL");
   1.123 +    }
   1.124 +  }
   1.125 +
   1.126 +  Graph::UEdgeMap<int> cost(graph);
   1.127 +  cost = subMap(constMap<UEdge>(c), weight);
   1.128 +
   1.129 +  {
   1.130  
   1.131      MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost);
   1.132  
   1.133 @@ -255,11 +302,28 @@
   1.134        check(num <= 1, "INVALID PRIMAL");
   1.135      }
   1.136  
   1.137 +    min_cost_matching = bpmatch.matchingCost();
   1.138      check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
   1.139      check(max_cardinality * c - max_cardinality_max_weight 
   1.140            == bpmatch.matchingCost(), "WRONG SIZE");
   1.141  
   1.142    }
   1.143  
   1.144 +  {
   1.145 +    Graph::UEdgeMap<bool> mm(graph);
   1.146 +
   1.147 +    check(min_cost_matching == 
   1.148 +          minCostMaxBipartiteMatching(graph, cost, mm),
   1.149 +          "WRONG MATCHING");
   1.150 +    
   1.151 +    for (ANodeIt it(graph); it != INVALID; ++it) {
   1.152 +      int num = 0;
   1.153 +      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
   1.154 +        if (mm[jt]) ++num;
   1.155 +      }
   1.156 +      check(num <= 1, "INVALID PRIMAL");
   1.157 +    }
   1.158 +  }
   1.159 +
   1.160    return 0;
   1.161  }