/* -*- 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 NN = 10;

 const int MM = 10;

 const int EE = 52;

 const int CC = 100;

 const int sa[EE] = { 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[EE] = { 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[EE] = { 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 < NN; ++i) {

     Node node = graph.addANode();

     aNodes.push_back(node);

   }

   for (int i = 0; i < MM; ++i) {

     Node node = graph.addBNode();

     bNodes.push_back(node);

   }

   for (int i = 0; i < EE; ++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>(CC), 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 * CC - 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 * CC - 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;

 }