Changeset 2058:0b1fc1566fdb in lemon-0.x for test/bipartite_matching_test.cc

Timestamp:

04/18/06 09:01:55 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2702

Message:

Refinements in bipartite matching algorithms

File:

• test/bipartite_matching_test.cc (modified) (10 diffs)

test/bipartite_matching_test.cc

@@ -24 +24 @@
   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 +34 @@
   int max_weight;
   int max_cardinality_max_weight;
+  int min_cost_matching;
 
   for (int i = 0; i < n; ++i) {
@@ -72 +73 @@
     }
     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 +154 @@
       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 +176 @@
 
   {
+    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 +203 @@
     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 +234 @@
     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 +255 @@
 
   {
-    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 +303 @@
     }
 
+    min_cost_matching = bpmatch.matchingCost();
     check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
     check(max_cardinality * c - max_cardinality_max_weight 
@@ -262 +310 @@
   }
 
+  {
+    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;
 }