equal
deleted
inserted
replaced
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
2 * |
2 * |
3 * This file is a part of LEMON, a generic C++ optimization library. |
3 * This file is a part of LEMON, a generic C++ optimization library. |
4 * |
4 * |
5 * Copyright (C) 2003-2009 |
5 * Copyright (C) 2003-2010 |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
8 * |
8 * |
9 * Permission to use, modify and distribute this software is granted |
9 * Permission to use, modify and distribute this software is granted |
10 * provided that this copyright notice appears in all copies. For |
10 * provided that this copyright notice appears in all copies. For |
236 } |
236 } |
237 check(pv == mfm.matchingSize(), "Wrong matching size"); |
237 check(pv == mfm.matchingSize(), "Wrong matching size"); |
238 |
238 |
239 for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { |
239 for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { |
240 check((e == mfm.matching(graph.u(e)) ? 1 : 0) + |
240 check((e == mfm.matching(graph.u(e)) ? 1 : 0) + |
241 (e == mfm.matching(graph.v(e)) ? 1 : 0) == |
241 (e == mfm.matching(graph.v(e)) ? 1 : 0) == |
242 mfm.matching(e), "Invalid matching"); |
242 mfm.matching(e), "Invalid matching"); |
243 } |
243 } |
244 |
244 |
245 SmartGraph::NodeMap<bool> processed(graph, false); |
245 SmartGraph::NodeMap<bool> processed(graph, false); |
246 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { |
246 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { |
290 check(mfm.matching(n) != INVALID, "Invalid matching"); |
290 check(mfm.matching(n) != INVALID, "Invalid matching"); |
291 check(indeg == 1, "Invalid matching"); |
291 check(indeg == 1, "Invalid matching"); |
292 } |
292 } |
293 for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { |
293 for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { |
294 check((e == mfm.matching(graph.u(e)) ? 1 : 0) + |
294 check((e == mfm.matching(graph.u(e)) ? 1 : 0) + |
295 (e == mfm.matching(graph.v(e)) ? 1 : 0) == |
295 (e == mfm.matching(graph.v(e)) ? 1 : 0) == |
296 mfm.matching(e), "Invalid matching"); |
296 mfm.matching(e), "Invalid matching"); |
297 } |
297 } |
298 } else { |
298 } else { |
299 int anum = 0, bnum = 0; |
299 int anum = 0, bnum = 0; |
300 SmartGraph::NodeMap<bool> neighbours(graph, false); |
300 SmartGraph::NodeMap<bool> neighbours(graph, false); |
348 } |
348 } |
349 } |
349 } |
350 |
350 |
351 for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { |
351 for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { |
352 check((e == mwfm.matching(graph.u(e)) ? 1 : 0) + |
352 check((e == mwfm.matching(graph.u(e)) ? 1 : 0) + |
353 (e == mwfm.matching(graph.v(e)) ? 1 : 0) == |
353 (e == mwfm.matching(graph.v(e)) ? 1 : 0) == |
354 mwfm.matching(e), "Invalid matching"); |
354 mwfm.matching(e), "Invalid matching"); |
355 } |
355 } |
356 |
356 |
357 int dv = 0; |
357 int dv = 0; |
358 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { |
358 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { |
408 SmartGraph::Node o = graph.target(mwpfm.matching(n)); |
408 SmartGraph::Node o = graph.target(mwpfm.matching(n)); |
409 } |
409 } |
410 |
410 |
411 for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { |
411 for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) { |
412 check((e == mwpfm.matching(graph.u(e)) ? 1 : 0) + |
412 check((e == mwpfm.matching(graph.u(e)) ? 1 : 0) + |
413 (e == mwpfm.matching(graph.v(e)) ? 1 : 0) == |
413 (e == mwpfm.matching(graph.v(e)) ? 1 : 0) == |
414 mwpfm.matching(e), "Invalid matching"); |
414 mwpfm.matching(e), "Invalid matching"); |
415 } |
415 } |
416 |
416 |
417 int dv = 0; |
417 int dv = 0; |
418 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { |
418 for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) { |