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 deba@2040: #include deba@2040: #include deba@2040: deba@2137: #include deba@2040: deba@2040: #include deba@2040: #include deba@2462: #include deba@2040: deba@2040: #include deba@2040: deba@2051: #include 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 aNodes; deba@2040: vector bNodes; deba@2051: deba@2051: Graph::UEdgeMap 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 bpmatch(graph); deba@2040: deba@2040: bpmatch.run(); deba@2040: deba@2040: Graph::UEdgeMap mm(graph); deba@2040: Graph::NodeMap 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 bpmatch(graph); deba@2462: deba@2462: bpmatch.run(); deba@2462: deba@2462: Graph::UEdgeMap mm(graph); deba@2462: Graph::NodeMap 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 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 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 bpmatch(graph); deba@2040: deba@2040: bpmatch.greedyInit(); deba@2040: bpmatch.start(); deba@2040: deba@2040: Graph::UEdgeMap mm(graph); deba@2040: Graph::NodeMap 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 bpmatch(graph); deba@2040: deba@2040: bpmatch.greedyInit(); deba@2618: while (bpmatch.simpleAugment()) { } deba@2040: deba@2040: Graph::UEdgeMap mm(graph); deba@2040: Graph::NodeMap 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 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 mm(graph); deba@2051: Graph::NodeMap 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 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 bpmatch(graph, weight); deba@2040: deba@2040: bpmatch.run(); deba@2051: deba@2051: Graph::UEdgeMap mm(graph); deba@2051: Graph::NodeMap 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 bpmatch(graph, weight); deba@2051: deba@2051: bpmatch.run(true); deba@2051: deba@2051: Graph::UEdgeMap mm(graph); deba@2051: Graph::NodeMap 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 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 cost(graph); alpar@2571: cost = subMap(constMap(CC), weight); deba@2058: { deba@2051: deba@2051: MinCostMaxBipartiteMatching bpmatch(graph, cost); deba@2051: deba@2051: bpmatch.run(); deba@2051: deba@2051: Graph::UEdgeMap mm(graph); deba@2051: Graph::NodeMap 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 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: }