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

}