alpar@2391: /* -*- C++ -*-
alpar@2391:  *
alpar@2391:  * This file is a part of LEMON, a generic C++ optimization library
alpar@2391:  *
alpar@2553:  * Copyright (C) 2003-2008
alpar@2391:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@2391:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@2391:  *
alpar@2391:  * Permission to use, modify and distribute this software is granted
alpar@2391:  * provided that this copyright notice appears in all copies. For
alpar@2391:  * precise terms see the accompanying LICENSE file.
alpar@2391:  *
alpar@2391:  * This software is provided "AS IS" with no warranty of any kind,
alpar@2391:  * express or implied, and with no claim as to its suitability for any
alpar@2391:  * purpose.
alpar@2391:  *
alpar@2391:  */
alpar@2391: 
deba@2040: #include <cstdlib>
deba@2040: #include <iostream>
deba@2040: #include <sstream>
deba@2040: 
deba@2137: #include <lemon/smart_graph.h>
deba@2040: 
deba@2040: #include <lemon/bpugraph_adaptor.h>
deba@2040: #include <lemon/bipartite_matching.h>
deba@2462: #include <lemon/pr_bipartite_matching.h>
deba@2040: 
deba@2040: #include <lemon/graph_utils.h>
deba@2040: 
deba@2051: #include <lemon/maps.h>
deba@2051: 
deba@2040: #include "test_tools.h"
deba@2040: 
deba@2040: using namespace std;
deba@2040: using namespace lemon;
deba@2040: 
deba@2137: typedef SmartBpUGraph Graph;
deba@2040: BPUGRAPH_TYPEDEFS(Graph);
deba@2040: 
alpar@2571: const int NN = 10;
alpar@2571: const int MM = 10;
alpar@2571: const int EE = 52;
alpar@2571: const int CC = 100;
deba@2137: 
alpar@2571: const int sa[EE] = { 6, 5, 6, 4, 1, 0, 9, 5, 2, 4, 4, 3, 5,
deba@2137:                     2, 3, 8, 3, 4, 9, 6, 9, 4, 3, 1, 5, 8,
deba@2137:                     4, 8, 9, 2, 2, 3, 0, 5, 2, 3, 6, 3, 8,
deba@2137:                     8, 4, 0, 9, 9, 6, 2, 1, 2, 7, 1, 9, 4};
deba@2137: 
alpar@2571: const int ta[EE] = { 2, 7, 4, 8, 6, 3, 4, 1, 7, 7, 0, 1, 6,
deba@2137:                     3, 2, 6, 8, 3, 5, 6, 3, 1, 8, 7, 2, 0,
deba@2137:                     6, 9, 6, 7, 8, 3, 3, 4, 5, 8, 6, 4, 1,
deba@2137:                     4, 3, 3, 8, 7, 7, 3, 7, 7, 3, 5, 1, 6};
deba@2137: 
alpar@2571: const int wa[EE] = { 3, 99, 85, 16, 79, 52, 83, 99, 62, 6, 42, 6, 95,
deba@2137:                     13, 34, 9, 5, 38, 39, 75, 99, 12, 73, 35, 93, 43,
deba@2137:                     54, 91, 45, 26, 77, 47, 11, 22, 50, 74, 37, 64, 91,
deba@2137:                     60, 6, 92, 29, 46, 34, 84, 67, 34, 45, 0, 39, 47};
deba@2137: 
deba@2137: 
deba@2137: int main() {
deba@2040:   Graph graph;
deba@2040:   vector<Node> aNodes;
deba@2040:   vector<Node> bNodes;
deba@2051: 
deba@2051:   Graph::UEdgeMap<int> weight(graph);
deba@2051: 
deba@2051:   int max_cardinality;
deba@2051:   int max_weight;
deba@2051:   int max_cardinality_max_weight;
deba@2058:   int min_cost_matching;
deba@2040: 
alpar@2571:   for (int i = 0; i < NN; ++i) {
deba@2040:     Node node = graph.addANode();
deba@2040:     aNodes.push_back(node);
deba@2040:   }
alpar@2571:   for (int i = 0; i < MM; ++i) {
deba@2040:     Node node = graph.addBNode();
deba@2040:     bNodes.push_back(node);
deba@2040:   }
alpar@2571:   for (int i = 0; i < EE; ++i) {
deba@2137:     Node aNode = aNodes[sa[i]];
deba@2137:     Node bNode = bNodes[ta[i]];
deba@2051:     UEdge uedge = graph.addEdge(aNode, bNode);
deba@2137:     weight[uedge] = wa[i];
deba@2040:   }
deba@2040: 
deba@2137: 
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@2051:       }
deba@2040:       check(num <= 1, "INVALID PRIMAL");
deba@2040:     }
deba@2051:     max_cardinality = bpmatch.matchingSize();
deba@2040:   }
deba@2040: 
deba@2040:   {
deba@2462:     PrBipartiteMatching<Graph> bpmatch(graph);
deba@2462: 
deba@2462:     bpmatch.run();
deba@2462: 
deba@2462:     Graph::UEdgeMap<bool> mm(graph);
deba@2462:     Graph::NodeMap<bool> cs(graph);
deba@2462:     
deba@2462:     check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
deba@2462:     
deba@2462:     for (UEdgeIt it(graph); it != INVALID; ++it) {
deba@2462:       check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
deba@2462:     }
deba@2462:     
deba@2462:     for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2462:       int num = 0;
deba@2462:       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2462:         if (mm[jt]) ++num;
deba@2462:       }
deba@2462:       check(num <= 1, "INVALID PRIMAL");
deba@2462:     }
deba@2462:     max_cardinality = bpmatch.matchingSize();
deba@2462:   }
deba@2462: 
deba@2462:   {
deba@2463:     Graph::ANodeMap<UEdge> mm(graph);
deba@2058: 
deba@2058:     check(max_cardinality == maxBipartiteMatching(graph, mm),
deba@2058:           "WRONG MATCHING");
deba@2058:     
deba@2463:     for (BNodeIt it(graph); it != INVALID; ++it) {
deba@2058:       int num = 0;
deba@2463:       
deba@2058:       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2463:         if (mm[graph.aNode(jt)] == jt) ++num;
deba@2463:       }
deba@2463:       check(num <= 1, "INVALID PRIMAL");
deba@2463:     }
deba@2463:   }
deba@2463: 
deba@2463:   {
deba@2463:     Graph::ANodeMap<UEdge> mm(graph);
deba@2463: 
deba@2463:     check(max_cardinality == prBipartiteMatching(graph, mm),
deba@2463:           "WRONG MATCHING");
deba@2463:     
deba@2463:     for (BNodeIt it(graph); it != INVALID; ++it) {
deba@2463:       int num = 0;
deba@2463:       
deba@2463:       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2463:         if (mm[graph.aNode(jt)] == jt) ++num;
deba@2058:       }
deba@2058:       check(num <= 1, "INVALID PRIMAL");
deba@2058:     }
deba@2058:   }
deba@2058: 
deba@2058:   {
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@2618:     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@2051:     MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
deba@2051: 
deba@2051:     bpmatch.init();
deba@2051: 
deba@2051:     max_weight = 0;
deba@2051:     while (bpmatch.augment(true)) {
deba@2051:     
deba@2051:       Graph::UEdgeMap<bool> mm(graph);
deba@2051:       Graph::NodeMap<int> pm(graph);
deba@2051:       
deba@2051:       bpmatch.matching(mm);
deba@2051:       bpmatch.potential(pm);
deba@2051:       
deba@2051:       for (UEdgeIt it(graph); it != INVALID; ++it) {
deba@2051:         if (mm[it]) {
deba@2058:           check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
deba@2051:                 "INVALID DUAL");
deba@2051:         } else {
deba@2058:           check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
deba@2051:                 "INVALID DUAL");
deba@2051:         }
deba@2051:       }
deba@2051: 
deba@2051:       for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2051:         int num = 0;
deba@2051:         for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2051:           if (mm[jt]) ++num;
deba@2051:         }
deba@2051:         check(num <= 1, "INVALID PRIMAL");
deba@2051:       }
deba@2051:       if (bpmatch.matchingValue() > max_weight) {
deba@2051:         max_weight = bpmatch.matchingValue();
deba@2051:       }
deba@2051:     }
deba@2051:   }
deba@2051: 
deba@2051:   {
deba@2058:     Graph::UEdgeMap<bool> mm(graph);
deba@2058: 
deba@2058:     check(max_weight == maxWeightedBipartiteMatching(graph, weight, mm),
deba@2058:           "WRONG MATCHING");
deba@2058:     
deba@2058:     for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2058:       int num = 0;
deba@2058:       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2058:         if (mm[jt]) ++num;
deba@2058:       }
deba@2058:       check(num <= 1, "INVALID PRIMAL");
deba@2058:     }
deba@2058:   }
deba@2058: 
deba@2058:   {
deba@2051:     MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
deba@2040: 
deba@2040:     bpmatch.run();
deba@2051:     
deba@2051:     Graph::UEdgeMap<bool> mm(graph);
deba@2051:     Graph::NodeMap<int> pm(graph);
deba@2040: 
deba@2051:     bpmatch.matching(mm);
deba@2051:     bpmatch.potential(pm);
deba@2040:     
deba@2040:     for (UEdgeIt it(graph); it != INVALID; ++it) {
deba@2051:       if (mm[it]) {
deba@2058:         check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
deba@2051:               "INVALID DUAL");
deba@2051:       } else {
deba@2058:         check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
deba@2051:               "INVALID DUAL");
deba@2051:       }
deba@2040:     }
deba@2051: 
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@2051:     check(max_weight == bpmatch.matchingValue(), "WRONG WEIGHT");
deba@2051:   }
deba@2051: 
deba@2051:   {
deba@2051:     MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
deba@2051: 
deba@2051:     bpmatch.run(true);
deba@2051:     
deba@2051:     Graph::UEdgeMap<bool> mm(graph);
deba@2051:     Graph::NodeMap<int> pm(graph);
deba@2051: 
deba@2051:     bpmatch.matching(mm);
deba@2051:     bpmatch.potential(pm);
deba@2051:     
deba@2051:     for (UEdgeIt it(graph); it != INVALID; ++it) {
deba@2051:       if (mm[it]) {
deba@2058:         check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
deba@2051:               "INVALID DUAL");
deba@2051:       } else {
deba@2058:         check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
deba@2051:               "INVALID DUAL");
deba@2051:       }
deba@2051:     }
deba@2051: 
deba@2051:     for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2051:       int num = 0;
deba@2051:       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2051:         if (mm[jt]) ++num;
deba@2051:     }
deba@2051:       check(num <= 1, "INVALID PRIMAL");
deba@2051:     }
deba@2051:     check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
deba@2051:     max_cardinality_max_weight = bpmatch.matchingValue();
deba@2051: 
deba@2051:   }
deba@2051: 
deba@2051:   {
deba@2058:     Graph::UEdgeMap<bool> mm(graph);
deba@2051: 
deba@2058:     check(max_cardinality_max_weight == 
deba@2058:           maxWeightedMaxBipartiteMatching(graph, weight, mm),
deba@2058:           "WRONG MATCHING");
deba@2058:     
deba@2058:     for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2058:       int num = 0;
deba@2058:       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2058:         if (mm[jt]) ++num;
deba@2058:       }
deba@2058:       check(num <= 1, "INVALID PRIMAL");
deba@2058:     }
deba@2058:   }
deba@2058: 
deba@2058:   Graph::UEdgeMap<int> cost(graph);
alpar@2571:   cost = subMap(constMap<UEdge>(CC), weight);
deba@2058:   {
deba@2051: 
deba@2051:     MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost);
deba@2051: 
deba@2051:     bpmatch.run();
deba@2051:     
deba@2051:     Graph::UEdgeMap<bool> mm(graph);
deba@2051:     Graph::NodeMap<int> pm(graph);
deba@2051: 
deba@2051:     bpmatch.matching(mm);
deba@2051:     bpmatch.potential(pm);
deba@2051:     
deba@2137:     min_cost_matching = bpmatch.matchingCost();
deba@2137:     check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
alpar@2571:     check(max_cardinality * CC - max_cardinality_max_weight 
deba@2137:           == bpmatch.matchingCost(), "WRONG SIZE");
deba@2137: 
deba@2051:     for (UEdgeIt it(graph); it != INVALID; ++it) {
deba@2051:       if (mm[it]) {
deba@2051:         check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] == 0,
deba@2051:               "INVALID DUAL");
deba@2051:       } else {
deba@2051:         check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] >= 0,
deba@2051:               "INVALID DUAL");
deba@2051:       }
deba@2051:     }
deba@2051: 
deba@2051:     for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2051:       int num = 0;
deba@2051:       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2051:         if (mm[jt]) ++num;
deba@2051:     }
deba@2051:       check(num <= 1, "INVALID PRIMAL");
deba@2051:     }
deba@2051: 
deba@2058:     min_cost_matching = bpmatch.matchingCost();
deba@2051:     check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
alpar@2571:     check(max_cardinality * CC - max_cardinality_max_weight 
deba@2051:           == bpmatch.matchingCost(), "WRONG SIZE");
deba@2051: 
deba@2040:   }
deba@2040: 
deba@2058:   {
deba@2058:     Graph::UEdgeMap<bool> mm(graph);
deba@2058: 
deba@2058:     check(min_cost_matching == 
deba@2058:           minCostMaxBipartiteMatching(graph, cost, mm),
deba@2058:           "WRONG MATCHING");
deba@2058:     
deba@2058:     for (ANodeIt it(graph); it != INVALID; ++it) {
deba@2058:       int num = 0;
deba@2058:       for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
deba@2058:         if (mm[jt]) ++num;
deba@2058:       }
deba@2058:       check(num <= 1, "INVALID PRIMAL");
deba@2058:     }
deba@2058:   }
deba@2058: 
deba@2040:   return 0;
deba@2040: }