/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#include <cstdlib>

#include <iostream>

#include <sstream>

#include <lemon/smart_graph.h>

#include <lemon/bpugraph_adaptor.h>

#include <lemon/bipartite_matching.h>

#include <lemon/pr_bipartite_matching.h>

#include <lemon/graph_utils.h>

#include <lemon/maps.h>

#include "test_tools.h"

using namespace std;

using namespace lemon;

typedef SmartBpUGraph Graph;

BPUGRAPH_TYPEDEFS(Graph);

const int N = 10;

const int M = 10;

const int E = 52;

const int C = 100;

const int sa[E] = { 6, 5, 6, 4, 1, 0, 9, 5, 2, 4, 4, 3, 5,

                    2, 3, 8, 3, 4, 9, 6, 9, 4, 3, 1, 5, 8,

                    4, 8, 9, 2, 2, 3, 0, 5, 2, 3, 6, 3, 8,

                    8, 4, 0, 9, 9, 6, 2, 1, 2, 7, 1, 9, 4};

const int ta[E] = { 2, 7, 4, 8, 6, 3, 4, 1, 7, 7, 0, 1, 6,

                    3, 2, 6, 8, 3, 5, 6, 3, 1, 8, 7, 2, 0,

                    6, 9, 6, 7, 8, 3, 3, 4, 5, 8, 6, 4, 1,

                    4, 3, 3, 8, 7, 7, 3, 7, 7, 3, 5, 1, 6};

const int wa[E] = { 3, 99, 85, 16, 79, 52, 83, 99, 62, 6, 42, 6, 95,

                    13, 34, 9, 5, 38, 39, 75, 99, 12, 73, 35, 93, 43,

                    54, 91, 45, 26, 77, 47, 11, 22, 50, 74, 37, 64, 91,

                    60, 6, 92, 29, 46, 34, 84, 67, 34, 45, 0, 39, 47};

int main() {

  Graph graph;

  vector<Node> aNodes;

  vector<Node> bNodes;

  Graph::UEdgeMap<int> weight(graph);

  int max_cardinality;

  int max_weight;

  int max_cardinality_max_weight;

  int min_cost_matching;

  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[sa[i]];

    Node bNode = bNodes[ta[i]];

    UEdge uedge = graph.addEdge(aNode, bNode);

    weight[uedge] = wa[i];

  }

  {

    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();

    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();

  }

  {

    Graph::ANodeMap<UEdge> mm(graph);

    check(max_cardinality == maxBipartiteMatching(graph, mm),

          "WRONG MATCHING");

    for (BNodeIt it(graph); it != INVALID; ++it) {

      int num = 0;

      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {

        if (mm[graph.aNode(jt)] == jt) ++num;

      }

      check(num <= 1, "INVALID PRIMAL");

    }

  }

  {

    Graph::ANodeMap<UEdge> mm(graph);

    check(max_cardinality == prBipartiteMatching(graph, mm),

          "WRONG MATCHING");

    for (BNodeIt it(graph); it != INVALID; ++it) {

      int num = 0;

      for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {

        if (mm[graph.aNode(jt)] == 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");

    }

  }

  {

    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);

    bpmatch.init();

    max_weight = 0;

    while (bpmatch.augment(true)) {

      Graph::UEdgeMap<bool> mm(graph);

      Graph::NodeMap<int> pm(graph);

      bpmatch.matching(mm);

      bpmatch.potential(pm);

      for (UEdgeIt it(graph); it != INVALID; ++it) {

        if (mm[it]) {

          check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,

                "INVALID DUAL");

        } else {

          check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,

                "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");

      }

      if (bpmatch.matchingValue() > max_weight) {

        max_weight = bpmatch.matchingValue();

      }

    }

  }

  {

    Graph::UEdgeMap<bool> mm(graph);

    check(max_weight == maxWeightedBipartiteMatching(graph, weight, mm),

          "WRONG MATCHING");

    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");

    }

  }

  {

    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);

    bpmatch.run();

    Graph::UEdgeMap<bool> mm(graph);

    Graph::NodeMap<int> pm(graph);

    bpmatch.matching(mm);

    bpmatch.potential(pm);

    for (UEdgeIt it(graph); it != INVALID; ++it) {

      if (mm[it]) {

        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,

              "INVALID DUAL");

      } else {

        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,

              "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");

    }

    check(max_weight == bpmatch.matchingValue(), "WRONG WEIGHT");

  }

  {

    MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);

    bpmatch.run(true);

    Graph::UEdgeMap<bool> mm(graph);

    Graph::NodeMap<int> pm(graph);

    bpmatch.matching(mm);

    bpmatch.potential(pm);

    for (UEdgeIt it(graph); it != INVALID; ++it) {

      if (mm[it]) {

        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,

              "INVALID DUAL");

      } else {

        check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,

              "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");

    }

    check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");

    max_cardinality_max_weight = bpmatch.matchingValue();

  }

  {

    Graph::UEdgeMap<bool> mm(graph);

    check(max_cardinality_max_weight == 

          maxWeightedMaxBipartiteMatching(graph, weight, mm),

          "WRONG MATCHING");

    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");

    }

  }

  Graph::UEdgeMap<int> cost(graph);

  cost = subMap(constMap<UEdge>(C), weight);

  {

    MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost);

    bpmatch.run();

    Graph::UEdgeMap<bool> mm(graph);

    Graph::NodeMap<int> pm(graph);

    bpmatch.matching(mm);

    bpmatch.potential(pm);

    min_cost_matching = bpmatch.matchingCost();

    check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");

    check(max_cardinality * C - max_cardinality_max_weight 

          == bpmatch.matchingCost(), "WRONG SIZE");

    for (UEdgeIt it(graph); it != INVALID; ++it) {

      if (mm[it]) {

        check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] == 0,

              "INVALID DUAL");

      } else {

        check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] >= 0,

              "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");

    }

    min_cost_matching = bpmatch.matchingCost();

    check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");

    check(max_cardinality * C - max_cardinality_max_weight 

          == bpmatch.matchingCost(), "WRONG SIZE");

  }

  {

    Graph::UEdgeMap<bool> mm(graph);

    check(min_cost_matching == 

          minCostMaxBipartiteMatching(graph, cost, mm),

          "WRONG MATCHING");

    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;

}