Changeset 2051:08652c1763f6 in lemon-0.x for test

Timestamp:

04/14/06 20:07:33 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

MaxWeightedBipartiteMatching?
MinCostMaxBipartiteMatching?

Both algorithms are based on successive shortest
path algorithm with dijkstra shortest path
finding

File:

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

test/bipartite_matching_test.cc

@@ -9 +9 @@
 
 #include <lemon/graph_utils.h>
+
+#include <lemon/maps.h>
 
 #include "test_tools.h"
@@ -25 +27 @@
   int m = argc > 2 ? atoi(argv[2]) : 100;
   int e = argc > 3 ? atoi(argv[3]) : (int)((n+m) * log(n+m));
+  int c = argc > 4 ? atoi(argv[4]) : 100;
+
+  Graph::UEdgeMap<int> weight(graph);
+
+  int max_cardinality;
+  int max_weight;
+  int max_cardinality_max_weight;
 
   for (int i = 0; i < n; ++i) {
@@ -37 +46 @@
     Node aNode = aNodes[urandom(n)];
     Node bNode = bNodes[urandom(m)];
-    graph.addEdge(aNode, bNode);
+    UEdge uedge = graph.addEdge(aNode, bNode);
+    weight[uedge] = urandom(c);
   }
 
@@ -58 +68 @@
       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
         if (mm[jt]) ++num;
-    }
-      check(num <= 1, "INVALID PRIMAL");
-    }
+      }
+      check(num <= 1, "INVALID PRIMAL");
+    }
+    max_cardinality = bpmatch.matchingSize();
   }
 
@@ -112 +123 @@
 
   {
-    SwapBpUGraphAdaptor<Graph> swapgraph(graph);
-    MaxBipartiteMatching<SwapBpUGraphAdaptor<Graph> > bpmatch(swapgraph);
+    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
+
+    bpmatch.init();
+
+    max_weight = 0;
+    while (bpmatch.augment(true)) {
+    
+      Graph::UEdgeMap<bool> mm(graph);
+      Graph::NodeMap<int> pm(graph);
+      
+      bpmatch.matching(mm);
+      bpmatch.potential(pm);
+      
+      for (UEdgeIt it(graph); it != INVALID; ++it) {
+        if (mm[it]) {
+          check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0,
+                "INVALID DUAL");
+        } else {
+          check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0,
+                "INVALID DUAL");
+        }
+      }
+
+      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");
+      }
+      if (bpmatch.matchingValue() > max_weight) {
+        max_weight = bpmatch.matchingValue();
+      }
+    }
+  }
+
+  {
+    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
 
     bpmatch.run();
-
-    Graph::UEdgeMap<bool> mm(graph);
-    Graph::NodeMap<bool> cs(graph);
-    
-    check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
-    
-    for (UEdgeIt it(graph); it != INVALID; ++it) {
-      check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
-    }
-    
-    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<bool> mm(graph);
+    Graph::NodeMap<int> pm(graph);
+
+    bpmatch.matching(mm);
+    bpmatch.potential(pm);
+    
+    for (UEdgeIt it(graph); it != INVALID; ++it) {
+      if (mm[it]) {
+        check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0,
+              "INVALID DUAL");
+      } else {
+        check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0,
+              "INVALID DUAL");
+      }
+    }
+
+    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");
+    }
+    check(max_weight == bpmatch.matchingValue(), "WRONG WEIGHT");
+  }
+
+  {
+    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
+
+    bpmatch.run(true);
+    
+    Graph::UEdgeMap<bool> mm(graph);
+    Graph::NodeMap<int> pm(graph);
+
+    bpmatch.matching(mm);
+    bpmatch.potential(pm);
+    
+    for (UEdgeIt it(graph); it != INVALID; ++it) {
+      if (mm[it]) {
+        check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0,
+              "INVALID DUAL");
+      } else {
+        check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0,
+              "INVALID DUAL");
+      }
+    }
+
+    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");
+    }
+    check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
+    max_cardinality_max_weight = bpmatch.matchingValue();
+
+  }
+
+  {
+    Graph::UEdgeMap<int> cost(graph);
+
+    cost = subMap(constMap<UEdge>(c), weight);
+
+    MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost);
+
+    bpmatch.run();
+    
+    Graph::UEdgeMap<bool> mm(graph);
+    Graph::NodeMap<int> pm(graph);
+
+    bpmatch.matching(mm);
+    bpmatch.potential(pm);
+    
+    for (UEdgeIt it(graph); it != INVALID; ++it) {
+      if (mm[it]) {
+        check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] == 0,
+              "INVALID DUAL");
+      } else {
+        check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] >= 0,
+              "INVALID DUAL");
+      }
+    }
+
+    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");
+    }
+
+    check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
+    check(max_cardinality * c - max_cardinality_max_weight 
+          == bpmatch.matchingCost(), "WRONG SIZE");
+
   }