deba@2040: #include deba@2040: #include deba@2040: #include deba@2040: deba@2137: #include deba@2040: deba@2040: #include deba@2040: #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: deba@2137: const int n = 10; deba@2137: const int m = 10; deba@2137: const int e = 52; deba@2137: const int c = 100; deba@2137: deba@2137: const int sa[e] = { 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: deba@2137: const int ta[e] = { 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: deba@2137: const int wa[e] = { 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: deba@2040: for (int i = 0; i < n; ++i) { deba@2040: Node node = graph.addANode(); deba@2040: aNodes.push_back(node); deba@2040: } deba@2040: for (int i = 0; i < m; ++i) { deba@2040: Node node = graph.addBNode(); deba@2040: bNodes.push_back(node); deba@2040: } deba@2040: for (int i = 0; i < e; ++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@2058: Graph::UEdgeMap mm(graph); deba@2058: deba@2058: check(max_cardinality == maxBipartiteMatching(graph, 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@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@2040: 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); deba@2058: cost = subMap(constMap(c), 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"); deba@2137: check(max_cardinality * c - 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"); deba@2051: check(max_cardinality * c - 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: }