#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;

 }