/* -*- 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 #include #include #include #include #include #include #include #include #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 aNodes; vector bNodes; Graph::UEdgeMap 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 bpmatch(graph); bpmatch.run(); Graph::UEdgeMap mm(graph); Graph::NodeMap 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 bpmatch(graph); bpmatch.run(); Graph::UEdgeMap mm(graph); Graph::NodeMap 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 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 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 bpmatch(graph); bpmatch.greedyInit(); bpmatch.start(); Graph::UEdgeMap mm(graph); Graph::NodeMap 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 bpmatch(graph); bpmatch.greedyInit(); while (bpmatch.simpleAugment()); Graph::UEdgeMap mm(graph); Graph::NodeMap 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 bpmatch(graph, weight); bpmatch.init(); max_weight = 0; while (bpmatch.augment(true)) { Graph::UEdgeMap mm(graph); Graph::NodeMap 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 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 bpmatch(graph, weight); bpmatch.run(); Graph::UEdgeMap mm(graph); Graph::NodeMap 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 bpmatch(graph, weight); bpmatch.run(true); Graph::UEdgeMap mm(graph); Graph::NodeMap 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 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 cost(graph); cost = subMap(constMap(C), weight); { MinCostMaxBipartiteMatching bpmatch(graph, cost); bpmatch.run(); Graph::UEdgeMap mm(graph); Graph::NodeMap 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 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; }