Changeset 2462:7a096a6bf53a in lemon-0.x for test

Timestamp:

08/11/07 18:34:41 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Common interface for bipartite matchings
Some useful query function for push-relabel based matching

The naming should be rethink for these classes
for example: pr-ap prefix for push-relabel and augmenting path
algorithms

File:

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

test/bipartite_matching_test.cc

@@ -25 +25 @@
 #include <lemon/bpugraph_adaptor.h>
 #include <lemon/bipartite_matching.h>
+#include <lemon/pr_bipartite_matching.h>
 
 #include <lemon/graph_utils.h>
@@ -89 +90 @@
   {
     MaxBipartiteMatching<Graph> bpmatch(graph);
+
+    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");
+    }
+    max_cardinality = bpmatch.matchingSize();
+  }
+
+  {
+    PrBipartiteMatching<Graph> bpmatch(graph);
 
     bpmatch.run();