Bug fix in CapacityScaling.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
23 #include <lemon/math.h>
26 #include "test_tools.h"
27 #include <lemon/smart_graph.h>
28 #include <lemon/max_matching.h>
29 #include <lemon/graph_reader.h>
31 UGRAPH_TYPEDEFS(SmartUGraph);
34 using namespace lemon;
37 const std::string lgf[lgfn] = {
114 void checkMatching(const SmartUGraph& ugraph,
115 const SmartUGraph::UEdgeMap<int>& weight,
116 const MaxWeightedMatching<SmartUGraph>& mwm) {
117 for (SmartUGraph::UEdgeIt e(ugraph); e != INVALID; ++e) {
118 if (ugraph.source(e) == ugraph.target(e)) continue;
120 mwm.nodeValue(ugraph.source(e)) + mwm.nodeValue(ugraph.target(e));
122 for (int i = 0; i < mwm.blossomNum(); ++i) {
123 bool s = false, t = false;
124 for (MaxWeightedMatching<SmartUGraph>::BlossomIt n(mwm, i);
126 if (ugraph.source(e) == n) s = true;
127 if (ugraph.target(e) == n) t = true;
129 if (s == true && t == true) {
130 rw += mwm.blossomValue(i);
133 rw -= weight[e] * mwm.dualScale;
135 check(rw >= 0, "Negative reduced weight");
136 check(rw == 0 || !mwm.matching(e),
137 "Non-zero reduced weight on matching edge");
141 for (SmartUGraph::NodeIt n(ugraph); n != INVALID; ++n) {
142 if (mwm.matching(n) != INVALID) {
143 check(mwm.nodeValue(n) >= 0, "Invalid node value");
144 pv += weight[mwm.matching(n)];
145 SmartUGraph::Node o = ugraph.target(mwm.matching(n));
146 check(mwm.mate(n) == o, "Invalid matching");
147 check(mwm.matching(n) == ugraph.oppositeEdge(mwm.matching(o)),
150 check(mwm.mate(n) == INVALID, "Invalid matching");
151 check(mwm.nodeValue(n) == 0, "Invalid matching");
156 for (SmartUGraph::NodeIt n(ugraph); n != INVALID; ++n) {
157 dv += mwm.nodeValue(n);
160 for (int i = 0; i < mwm.blossomNum(); ++i) {
161 check(mwm.blossomValue(i) >= 0, "Invalid blossom value");
162 check(mwm.blossomSize(i) % 2 == 1, "Even blossom size");
163 dv += mwm.blossomValue(i) * ((mwm.blossomSize(i) - 1) / 2);
166 check(pv * mwm.dualScale == dv * 2, "Wrong duality");
171 void checkPerfectMatching(const SmartUGraph& ugraph,
172 const SmartUGraph::UEdgeMap<int>& weight,
173 const MaxWeightedPerfectMatching<SmartUGraph>& mwpm) {
174 for (SmartUGraph::UEdgeIt e(ugraph); e != INVALID; ++e) {
175 if (ugraph.source(e) == ugraph.target(e)) continue;
177 mwpm.nodeValue(ugraph.source(e)) + mwpm.nodeValue(ugraph.target(e));
179 for (int i = 0; i < mwpm.blossomNum(); ++i) {
180 bool s = false, t = false;
181 for (MaxWeightedPerfectMatching<SmartUGraph>::BlossomIt n(mwpm, i);
183 if (ugraph.source(e) == n) s = true;
184 if (ugraph.target(e) == n) t = true;
186 if (s == true && t == true) {
187 rw += mwpm.blossomValue(i);
190 rw -= weight[e] * mwpm.dualScale;
192 check(rw >= 0, "Negative reduced weight");
193 check(rw == 0 || !mwpm.matching(e),
194 "Non-zero reduced weight on matching edge");
198 for (SmartUGraph::NodeIt n(ugraph); n != INVALID; ++n) {
199 check(mwpm.matching(n) != INVALID, "Non perfect");
200 pv += weight[mwpm.matching(n)];
201 SmartUGraph::Node o = ugraph.target(mwpm.matching(n));
202 check(mwpm.mate(n) == o, "Invalid matching");
203 check(mwpm.matching(n) == ugraph.oppositeEdge(mwpm.matching(o)),
208 for (SmartUGraph::NodeIt n(ugraph); n != INVALID; ++n) {
209 dv += mwpm.nodeValue(n);
212 for (int i = 0; i < mwpm.blossomNum(); ++i) {
213 check(mwpm.blossomValue(i) >= 0, "Invalid blossom value");
214 check(mwpm.blossomSize(i) % 2 == 1, "Even blossom size");
215 dv += mwpm.blossomValue(i) * ((mwpm.blossomSize(i) - 1) / 2);
218 check(pv * mwpm.dualScale == dv * 2, "Wrong duality");
226 for (int i = 0; i < lgfn; ++i) {
228 SmartUGraph::UEdgeMap<int> weight(ugraph);
230 istringstream lgfs(lgf[i]);
231 UGraphReader<SmartUGraph>(lgfs, ugraph).
232 readUEdgeMap("weight", weight).run();
234 MaxWeightedMatching<SmartUGraph> mwm(ugraph, weight);
236 checkMatching(ugraph, weight, mwm);
238 MaxMatching<SmartUGraph> mm(ugraph);
241 MaxWeightedPerfectMatching<SmartUGraph> mwpm(ugraph, weight);
242 bool perfect = mwpm.run();
244 check(perfect == (mm.size() * 2 == countNodes(ugraph)),
245 "Perfect matching found");
248 checkPerfectMatching(ugraph, weight, mwpm);