1.1 --- a/test/bipartite_matching_test.cc Fri Apr 14 18:05:02 2006 +0000
1.2 +++ b/test/bipartite_matching_test.cc Fri Apr 14 18:07:33 2006 +0000
1.3 @@ -9,6 +9,8 @@
1.4
1.5 #include <lemon/graph_utils.h>
1.6
1.7 +#include <lemon/maps.h>
1.8 +
1.9 #include "test_tools.h"
1.10
1.11 using namespace std;
1.12 @@ -24,6 +26,13 @@
1.13 int n = argc > 1 ? atoi(argv[1]) : 100;
1.14 int m = argc > 2 ? atoi(argv[2]) : 100;
1.15 int e = argc > 3 ? atoi(argv[3]) : (int)((n+m) * log(n+m));
1.16 + int c = argc > 4 ? atoi(argv[4]) : 100;
1.17 +
1.18 + Graph::UEdgeMap<int> weight(graph);
1.19 +
1.20 + int max_cardinality;
1.21 + int max_weight;
1.22 + int max_cardinality_max_weight;
1.23
1.24 for (int i = 0; i < n; ++i) {
1.25 Node node = graph.addANode();
1.26 @@ -36,7 +45,8 @@
1.27 for (int i = 0; i < e; ++i) {
1.28 Node aNode = aNodes[urandom(n)];
1.29 Node bNode = bNodes[urandom(m)];
1.30 - graph.addEdge(aNode, bNode);
1.31 + UEdge uedge = graph.addEdge(aNode, bNode);
1.32 + weight[uedge] = urandom(c);
1.33 }
1.34
1.35 {
1.36 @@ -57,9 +67,10 @@
1.37 int num = 0;
1.38 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
1.39 if (mm[jt]) ++num;
1.40 - }
1.41 + }
1.42 check(num <= 1, "INVALID PRIMAL");
1.43 }
1.44 + max_cardinality = bpmatch.matchingSize();
1.45 }
1.46
1.47 {
1.48 @@ -111,20 +122,63 @@
1.49 }
1.50
1.51 {
1.52 - SwapBpUGraphAdaptor<Graph> swapgraph(graph);
1.53 - MaxBipartiteMatching<SwapBpUGraphAdaptor<Graph> > bpmatch(swapgraph);
1.54 + MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
1.55 +
1.56 + bpmatch.init();
1.57 +
1.58 + max_weight = 0;
1.59 + while (bpmatch.augment(true)) {
1.60 +
1.61 + Graph::UEdgeMap<bool> mm(graph);
1.62 + Graph::NodeMap<int> pm(graph);
1.63 +
1.64 + bpmatch.matching(mm);
1.65 + bpmatch.potential(pm);
1.66 +
1.67 + for (UEdgeIt it(graph); it != INVALID; ++it) {
1.68 + if (mm[it]) {
1.69 + check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0,
1.70 + "INVALID DUAL");
1.71 + } else {
1.72 + check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0,
1.73 + "INVALID DUAL");
1.74 + }
1.75 + }
1.76 +
1.77 + for (ANodeIt it(graph); it != INVALID; ++it) {
1.78 + int num = 0;
1.79 + for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
1.80 + if (mm[jt]) ++num;
1.81 + }
1.82 + check(num <= 1, "INVALID PRIMAL");
1.83 + }
1.84 + if (bpmatch.matchingValue() > max_weight) {
1.85 + max_weight = bpmatch.matchingValue();
1.86 + }
1.87 + }
1.88 + }
1.89 +
1.90 + {
1.91 + MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
1.92
1.93 bpmatch.run();
1.94 +
1.95 + Graph::UEdgeMap<bool> mm(graph);
1.96 + Graph::NodeMap<int> pm(graph);
1.97
1.98 - Graph::UEdgeMap<bool> mm(graph);
1.99 - Graph::NodeMap<bool> cs(graph);
1.100 -
1.101 - check(bpmatch.coverSet(cs) == bpmatch.matching(mm), "INVALID PRIMAL-DUAL");
1.102 + bpmatch.matching(mm);
1.103 + bpmatch.potential(pm);
1.104
1.105 for (UEdgeIt it(graph); it != INVALID; ++it) {
1.106 - check(cs[graph.aNode(it)] || cs[graph.bNode(it)], "INVALID DUAL");
1.107 + if (mm[it]) {
1.108 + check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0,
1.109 + "INVALID DUAL");
1.110 + } else {
1.111 + check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0,
1.112 + "INVALID DUAL");
1.113 + }
1.114 }
1.115 -
1.116 +
1.117 for (ANodeIt it(graph); it != INVALID; ++it) {
1.118 int num = 0;
1.119 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
1.120 @@ -132,6 +186,79 @@
1.121 }
1.122 check(num <= 1, "INVALID PRIMAL");
1.123 }
1.124 + check(max_weight == bpmatch.matchingValue(), "WRONG WEIGHT");
1.125 + }
1.126 +
1.127 + {
1.128 + MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
1.129 +
1.130 + bpmatch.run(true);
1.131 +
1.132 + Graph::UEdgeMap<bool> mm(graph);
1.133 + Graph::NodeMap<int> pm(graph);
1.134 +
1.135 + bpmatch.matching(mm);
1.136 + bpmatch.potential(pm);
1.137 +
1.138 + for (UEdgeIt it(graph); it != INVALID; ++it) {
1.139 + if (mm[it]) {
1.140 + check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0,
1.141 + "INVALID DUAL");
1.142 + } else {
1.143 + check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0,
1.144 + "INVALID DUAL");
1.145 + }
1.146 + }
1.147 +
1.148 + for (ANodeIt it(graph); it != INVALID; ++it) {
1.149 + int num = 0;
1.150 + for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
1.151 + if (mm[jt]) ++num;
1.152 + }
1.153 + check(num <= 1, "INVALID PRIMAL");
1.154 + }
1.155 + check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
1.156 + max_cardinality_max_weight = bpmatch.matchingValue();
1.157 +
1.158 + }
1.159 +
1.160 + {
1.161 + Graph::UEdgeMap<int> cost(graph);
1.162 +
1.163 + cost = subMap(constMap<UEdge>(c), weight);
1.164 +
1.165 + MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost);
1.166 +
1.167 + bpmatch.run();
1.168 +
1.169 + Graph::UEdgeMap<bool> mm(graph);
1.170 + Graph::NodeMap<int> pm(graph);
1.171 +
1.172 + bpmatch.matching(mm);
1.173 + bpmatch.potential(pm);
1.174 +
1.175 + for (UEdgeIt it(graph); it != INVALID; ++it) {
1.176 + if (mm[it]) {
1.177 + check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] == 0,
1.178 + "INVALID DUAL");
1.179 + } else {
1.180 + check(pm[graph.aNode(it)] + cost[it] - pm[graph.bNode(it)] >= 0,
1.181 + "INVALID DUAL");
1.182 + }
1.183 + }
1.184 +
1.185 + for (ANodeIt it(graph); it != INVALID; ++it) {
1.186 + int num = 0;
1.187 + for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
1.188 + if (mm[jt]) ++num;
1.189 + }
1.190 + check(num <= 1, "INVALID PRIMAL");
1.191 + }
1.192 +
1.193 + check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
1.194 + check(max_cardinality * c - max_cardinality_max_weight
1.195 + == bpmatch.matchingCost(), "WRONG SIZE");
1.196 +
1.197 }
1.198
1.199 return 0;