Index: test/Makefile.am
===================================================================
--- test/Makefile.am	(revision 2025)
+++ test/Makefile.am	(revision 2040)
@@ -16,4 +16,5 @@
 	arborescence_test \
 	bfs_test \
+	bipartite_matching_test \
 	counter_test \
 	dfs_test \
@@ -56,4 +57,5 @@
 arborescence_test_SOURCES = arborescence_test.cc
 bfs_test_SOURCES = bfs_test.cc
+bipartite_matching_test_SOURCES = bipartite_matching_test.cc
 counter_test_SOURCES = counter_test.cc
 dfs_test_SOURCES = dfs_test.cc
Index: test/bipartite_matching_test.cc
===================================================================
--- test/bipartite_matching_test.cc	(revision 2040)
+++ test/bipartite_matching_test.cc	(revision 2040)
@@ -0,0 +1,138 @@
+#include <cstdlib>
+#include <iostream>
+#include <sstream>
+
+#include <lemon/list_graph.h>
+
+#include <lemon/bpugraph_adaptor.h>
+#include <lemon/bipartite_matching.h>
+
+#include <lemon/graph_utils.h>
+
+#include "test_tools.h"
+
+using namespace std;
+using namespace lemon;
+
+typedef ListBpUGraph Graph;
+BPUGRAPH_TYPEDEFS(Graph);
+
+int main(int argc, const char *argv[]) {
+  Graph graph;
+  vector<Node> aNodes;
+  vector<Node> bNodes;
+  int n = argc > 1 ? atoi(argv[1]) : 100;
+  int m = argc > 2 ? atoi(argv[2]) : 100;
+  int e = argc > 3 ? atoi(argv[3]) : (int)((n+m) * log(n+m));
+
+  for (int i = 0; i < n; ++i) {
+    Node node = graph.addANode();
+    aNodes.push_back(node);
+  }
+  for (int i = 0; i < m; ++i) {
+    Node node = graph.addBNode();
+    bNodes.push_back(node);
+  }
+  for (int i = 0; i < e; ++i) {
+    Node aNode = aNodes[urandom(n)];
+    Node bNode = bNodes[urandom(m)];
+    graph.addEdge(aNode, bNode);
+  }
+
+  {
+    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");
+    }
+  }
+
+  {
+    MaxBipartiteMatching<Graph> bpmatch(graph);
+
+    bpmatch.greedyInit();
+    bpmatch.start();
+
+    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");
+    }
+  }
+
+  {
+    MaxBipartiteMatching<Graph> bpmatch(graph);
+
+    bpmatch.greedyInit();
+    while (bpmatch.simpleAugment());
+    
+    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");
+    }
+  }
+
+  {
+    SwapBpUGraphAdaptor<Graph> swapgraph(graph);
+    MaxBipartiteMatching<SwapBpUGraphAdaptor<Graph> > bpmatch(swapgraph);
+
+    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");
+    }
+  }
+
+  return 0;
+}
