1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
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/lgf_reader.h>
32 using namespace lemon;
34 GRAPH_TYPEDEFS(SmartGraph);
37 const std::string lgf[lgfn] = {
111 void checkMatching(const SmartGraph& graph,
112 const SmartGraph::EdgeMap<int>& weight,
113 const MaxWeightedMatching<SmartGraph>& mwm) {
114 for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
115 if (graph.u(e) == graph.v(e)) continue;
117 mwm.nodeValue(graph.u(e)) + mwm.nodeValue(graph.v(e));
119 for (int i = 0; i < mwm.blossomNum(); ++i) {
120 bool s = false, t = false;
121 for (MaxWeightedMatching<SmartGraph>::BlossomIt n(mwm, i);
123 if (graph.u(e) == n) s = true;
124 if (graph.v(e) == n) t = true;
126 if (s == true && t == true) {
127 rw += mwm.blossomValue(i);
130 rw -= weight[e] * mwm.dualScale;
132 check(rw >= 0, "Negative reduced weight");
133 check(rw == 0 || !mwm.matching(e),
134 "Non-zero reduced weight on matching arc");
138 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
139 if (mwm.matching(n) != INVALID) {
140 check(mwm.nodeValue(n) >= 0, "Invalid node value");
141 pv += weight[mwm.matching(n)];
142 SmartGraph::Node o = graph.target(mwm.matching(n));
143 check(mwm.mate(n) == o, "Invalid matching");
144 check(mwm.matching(n) == graph.oppositeArc(mwm.matching(o)),
147 check(mwm.mate(n) == INVALID, "Invalid matching");
148 check(mwm.nodeValue(n) == 0, "Invalid matching");
153 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
154 dv += mwm.nodeValue(n);
157 for (int i = 0; i < mwm.blossomNum(); ++i) {
158 check(mwm.blossomValue(i) >= 0, "Invalid blossom value");
159 check(mwm.blossomSize(i) % 2 == 1, "Even blossom size");
160 dv += mwm.blossomValue(i) * ((mwm.blossomSize(i) - 1) / 2);
163 check(pv * mwm.dualScale == dv * 2, "Wrong duality");
168 void checkPerfectMatching(const SmartGraph& graph,
169 const SmartGraph::EdgeMap<int>& weight,
170 const MaxWeightedPerfectMatching<SmartGraph>& mwpm) {
171 for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
172 if (graph.u(e) == graph.v(e)) continue;
174 mwpm.nodeValue(graph.u(e)) + mwpm.nodeValue(graph.v(e));
176 for (int i = 0; i < mwpm.blossomNum(); ++i) {
177 bool s = false, t = false;
178 for (MaxWeightedPerfectMatching<SmartGraph>::BlossomIt n(mwpm, i);
180 if (graph.u(e) == n) s = true;
181 if (graph.v(e) == n) t = true;
183 if (s == true && t == true) {
184 rw += mwpm.blossomValue(i);
187 rw -= weight[e] * mwpm.dualScale;
189 check(rw >= 0, "Negative reduced weight");
190 check(rw == 0 || !mwpm.matching(e),
191 "Non-zero reduced weight on matching arc");
195 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
196 check(mwpm.matching(n) != INVALID, "Non perfect");
197 pv += weight[mwpm.matching(n)];
198 SmartGraph::Node o = graph.target(mwpm.matching(n));
199 check(mwpm.mate(n) == o, "Invalid matching");
200 check(mwpm.matching(n) == graph.oppositeArc(mwpm.matching(o)),
205 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
206 dv += mwpm.nodeValue(n);
209 for (int i = 0; i < mwpm.blossomNum(); ++i) {
210 check(mwpm.blossomValue(i) >= 0, "Invalid blossom value");
211 check(mwpm.blossomSize(i) % 2 == 1, "Even blossom size");
212 dv += mwpm.blossomValue(i) * ((mwpm.blossomSize(i) - 1) / 2);
215 check(pv * mwpm.dualScale == dv * 2, "Wrong duality");
223 for (int i = 0; i < lgfn; ++i) {
225 SmartGraph::EdgeMap<int> weight(graph);
227 istringstream lgfs(lgf[i]);
228 graphReader(graph, lgfs).
229 edgeMap("weight", weight).run();
231 MaxWeightedMatching<SmartGraph> mwm(graph, weight);
233 checkMatching(graph, weight, mwm);
235 MaxMatching<SmartGraph> mm(graph);
238 MaxWeightedPerfectMatching<SmartGraph> mwpm(graph, weight);
239 bool perfect = mwpm.run();
241 check(perfect == (mm.size() * 2 == countNodes(graph)),
242 "Perfect matching found");
245 checkPerfectMatching(graph, weight, mwpm);