Index: test/bipartite_matching_test.cc
===================================================================
--- test/bipartite_matching_test.cc	(revision 2051)
+++ test/bipartite_matching_test.cc	(revision 2058)
@@ -24,6 +24,6 @@
   vector<Node> aNodes;
   vector<Node> bNodes;
-  int n = argc > 1 ? atoi(argv[1]) : 100;
-  int m = argc > 2 ? atoi(argv[2]) : 100;
+  int n = argc > 1 ? atoi(argv[1]) : 10;
+  int m = argc > 2 ? atoi(argv[2]) : 10;
   int e = argc > 3 ? atoi(argv[3]) : (int)((n+m) * log(n+m));
   int c = argc > 4 ? atoi(argv[4]) : 100;
@@ -34,4 +34,5 @@
   int max_weight;
   int max_cardinality_max_weight;
+  int min_cost_matching;
 
   for (int i = 0; i < n; ++i) {
@@ -72,4 +73,19 @@
     }
     max_cardinality = bpmatch.matchingSize();
+  }
+
+  {
+    Graph::UEdgeMap<bool> mm(graph);
+
+    check(max_cardinality == maxBipartiteMatching(graph, mm),
+          "WRONG MATCHING");
+    
+    for (ANodeIt it(graph); it != INVALID; ++it) {
+      int num = 0;
+      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
+        if (mm[jt]) ++num;
+      }
+      check(num <= 1, "INVALID PRIMAL");
+    }
   }
 
@@ -138,8 +154,8 @@
       for (UEdgeIt it(graph); it != INVALID; ++it) {
         if (mm[it]) {
-          check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0,
+          check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
                 "INVALID DUAL");
         } else {
-          check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0,
+          check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
                 "INVALID DUAL");
         }
@@ -160,4 +176,19 @@
 
   {
+    Graph::UEdgeMap<bool> mm(graph);
+
+    check(max_weight == maxWeightedBipartiteMatching(graph, weight, mm),
+          "WRONG MATCHING");
+    
+    for (ANodeIt it(graph); it != INVALID; ++it) {
+      int num = 0;
+      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
+        if (mm[jt]) ++num;
+      }
+      check(num <= 1, "INVALID PRIMAL");
+    }
+  }
+
+  {
     MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
 
@@ -172,8 +203,8 @@
     for (UEdgeIt it(graph); it != INVALID; ++it) {
       if (mm[it]) {
-        check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0,
+        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
               "INVALID DUAL");
       } else {
-        check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0,
+        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
               "INVALID DUAL");
       }
@@ -203,8 +234,8 @@
     for (UEdgeIt it(graph); it != INVALID; ++it) {
       if (mm[it]) {
-        check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0,
+        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
               "INVALID DUAL");
       } else {
-        check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0,
+        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
               "INVALID DUAL");
       }
@@ -224,7 +255,23 @@
 
   {
-    Graph::UEdgeMap<int> cost(graph);
-
-    cost = subMap(constMap<UEdge>(c), weight);
+    Graph::UEdgeMap<bool> mm(graph);
+
+    check(max_cardinality_max_weight == 
+          maxWeightedMaxBipartiteMatching(graph, weight, mm),
+          "WRONG MATCHING");
+    
+    for (ANodeIt it(graph); it != INVALID; ++it) {
+      int num = 0;
+      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
+        if (mm[jt]) ++num;
+      }
+      check(num <= 1, "INVALID PRIMAL");
+    }
+  }
+
+  Graph::UEdgeMap<int> cost(graph);
+  cost = subMap(constMap<UEdge>(c), weight);
+
+  {
 
     MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost);
@@ -256,4 +303,5 @@
     }
 
+    min_cost_matching = bpmatch.matchingCost();
     check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
     check(max_cardinality * c - max_cardinality_max_weight 
@@ -262,4 +310,20 @@
   }
 
+  {
+    Graph::UEdgeMap<bool> mm(graph);
+
+    check(min_cost_matching == 
+          minCostMaxBipartiteMatching(graph, cost, mm),
+          "WRONG MATCHING");
+    
+    for (ANodeIt it(graph); it != INVALID; ++it) {
+      int num = 0;
+      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
+        if (mm[jt]) ++num;
+      }
+      check(num <= 1, "INVALID PRIMAL");
+    }
+  }
+
   return 0;
 }
