deba@2040: #include <cstdlib>
deba@2040: #include <iostream>
deba@2040: #include <sstream>
deba@2040: 
deba@2040: #include <lemon/list_graph.h>
deba@2040: 
deba@2040: #include <lemon/bpugraph_adaptor.h>
deba@2040: #include <lemon/bipartite_matching.h>
deba@2040: 
deba@2040: #include <lemon/graph_utils.h>
deba@2040: 
deba@2040: #include "test_tools.h"
deba@2040: 
deba@2040: using namespace std;
deba@2040: using namespace lemon;
deba@2040: 
deba@2040: typedef ListBpUGraph Graph;
deba@2040: BPUGRAPH_TYPEDEFS(Graph);
deba@2040: 
deba@2040: int main(int argc, const char *argv[]) {
deba@2040:   Graph graph;
deba@2040:   vector<Node> aNodes;
deba@2040:   vector<Node> bNodes;
deba@2040:   int n = argc > 1 ? atoi(argv[1]) : 100;
deba@2040:   int m = argc > 2 ? atoi(argv[2]) : 100;
deba@2040:   int e = argc > 3 ? atoi(argv[3]) : (int)((n+m) * log(n+m));
deba@2040: 
deba@2040:   for (int i = 0; i < n; ++i) {
deba@2040:     Node node = graph.addANode();
deba@2040:     aNodes.push_back(node);
deba@2040:   }
deba@2040:   for (int i = 0; i < m; ++i) {
deba@2040:     Node node = graph.addBNode();
deba@2040:     bNodes.push_back(node);
deba@2040:   }
deba@2040:   for (int i = 0; i < e; ++i) {
deba@2040:     Node aNode = aNodes[urandom(n)];
deba@2040:     Node bNode = bNodes[urandom(m)];
deba@2040:     graph.addEdge(aNode, bNode);
deba@2040:   }
deba@2040: 
deba@2040:   {
deba@2040:     MaxBipartiteMatching<Graph> bpmatch(graph);
deba@2040: 
deba@2040:     bpmatch.run();
deba@2040: 
deba@2040:     Graph::UEdgeMap<bool> mm(graph);
deba@2040:     Graph::NodeMap<bool> cs(graph);
deba@2040:     
deba@2040:     check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
deba@2040:     
deba@2040:     for (UEdgeIt it(graph); it != INVALID; ++it) {
deba@2040:       check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
deba@2040:     }
deba@2040:     
deba@2040:     for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2040:       int num = 0;
deba@2040:       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2040:         if (mm[jt]) ++num;
deba@2040:     }
deba@2040:       check(num <= 1, "INVALID PRIMAL");
deba@2040:     }
deba@2040:   }
deba@2040: 
deba@2040:   {
deba@2040:     MaxBipartiteMatching<Graph> bpmatch(graph);
deba@2040: 
deba@2040:     bpmatch.greedyInit();
deba@2040:     bpmatch.start();
deba@2040: 
deba@2040:     Graph::UEdgeMap<bool> mm(graph);
deba@2040:     Graph::NodeMap<bool> cs(graph);
deba@2040: 
deba@2040:     check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
deba@2040:     
deba@2040:     for (UEdgeIt it(graph); it != INVALID; ++it) {
deba@2040:       check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
deba@2040:     }
deba@2040:     
deba@2040:     for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2040:       int num = 0;
deba@2040:       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2040:         if (mm[jt]) ++num;
deba@2040:     }
deba@2040:       check(num <= 1, "INVALID PRIMAL");
deba@2040:     }
deba@2040:   }
deba@2040: 
deba@2040:   {
deba@2040:     MaxBipartiteMatching<Graph> bpmatch(graph);
deba@2040: 
deba@2040:     bpmatch.greedyInit();
deba@2040:     while (bpmatch.simpleAugment());
deba@2040:     
deba@2040:     Graph::UEdgeMap<bool> mm(graph);
deba@2040:     Graph::NodeMap<bool> cs(graph);
deba@2040:     
deba@2040:     check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
deba@2040:     
deba@2040:     for (UEdgeIt it(graph); it != INVALID; ++it) {
deba@2040:       check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
deba@2040:     }
deba@2040:     
deba@2040:     for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2040:       int num = 0;
deba@2040:       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2040:         if (mm[jt]) ++num;
deba@2040:     }
deba@2040:       check(num <= 1, "INVALID PRIMAL");
deba@2040:     }
deba@2040:   }
deba@2040: 
deba@2040:   {
deba@2040:     SwapBpUGraphAdaptor<Graph> swapgraph(graph);
deba@2040:     MaxBipartiteMatching<SwapBpUGraphAdaptor<Graph> > bpmatch(swapgraph);
deba@2040: 
deba@2040:     bpmatch.run();
deba@2040: 
deba@2040:     Graph::UEdgeMap<bool> mm(graph);
deba@2040:     Graph::NodeMap<bool> cs(graph);
deba@2040:     
deba@2040:     check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
deba@2040:     
deba@2040:     for (UEdgeIt it(graph); it != INVALID; ++it) {
deba@2040:       check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
deba@2040:     }
deba@2040:     
deba@2040:     for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2040:       int num = 0;
deba@2040:       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2040:         if (mm[jt]) ++num;
deba@2040:     }
deba@2040:       check(num <= 1, "INVALID PRIMAL");
deba@2040:     }
deba@2040:   }
deba@2040: 
deba@2040:   return 0;
deba@2040: }