# HG changeset patch
# User deba
# Date 1198941101 0
# Node ID 88b81ec599ed77ff8caad2e634c213a522e8ec91
# Parent  a3ba22ebccc6953279296d8486f6cf5416f7f45f
Test program for max weighted matchings

diff -r a3ba22ebccc6 -r 88b81ec599ed lemon/max_matching.h
--- a/lemon/max_matching.h	Fri Dec 28 11:00:51 2007 +0000
+++ b/lemon/max_matching.h	Sat Dec 29 15:11:41 2007 +0000
@@ -30,7 +30,7 @@
 
 ///\ingroup matching
 ///\file
-///\brief Maximum matching algorithm in undirected graph.
+///\brief Maximum matching algorithms in undirected graph.
 
 namespace lemon {
 
@@ -1467,7 +1467,7 @@
       int b = _blossom_set->find(_ugraph.source(pred));
       int d = _blossom_set->find(_ugraph.source(next));
       
-      int ib, id;
+      int ib = -1, id = -1;
       for (int i = 0; i < int(subblossoms.size()); ++i) {
 	if (subblossoms[i] == b) ib = i;
 	if (subblossoms[i] == d) id = i;
@@ -2654,7 +2654,7 @@
       int b = _blossom_set->find(_ugraph.source(pred));
       int d = _blossom_set->find(_ugraph.source(next));
       
-      int ib, id;
+      int ib = -1, id = -1;
       for (int i = 0; i < int(subblossoms.size()); ++i) {
 	if (subblossoms[i] == b) ib = i;
 	if (subblossoms[i] == d) id = i;
diff -r a3ba22ebccc6 -r 88b81ec599ed test/Makefile.am
--- a/test/Makefile.am	Fri Dec 28 11:00:51 2007 +0000
+++ b/test/Makefile.am	Sat Dec 29 15:11:41 2007 +0000
@@ -30,6 +30,7 @@
 	test/maps_test \
 	test/matrix_maps_test \
 	test/max_matching_test \
+	test/max_weighted_matching_test \
 	test/min_cost_flow_test \
 	test/path_test \
 	test/polynomial_test \
@@ -79,6 +80,7 @@
 test_maps_test_SOURCES = test/maps_test.cc
 test_matrix_maps_test_SOURCES = test/matrix_maps_test.cc
 test_max_matching_test_SOURCES = test/max_matching_test.cc
+test_max_weighted_matching_test_SOURCES = test/max_weighted_matching_test.cc
 test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc
 test_path_test_SOURCES = test/path_test.cc
 test_polynomial_test_SOURCES = test/polynomial_test.cc
diff -r a3ba22ebccc6 -r 88b81ec599ed test/max_weighted_matching_test.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/max_weighted_matching_test.cc	Sat Dec 29 15:11:41 2007 +0000
@@ -0,0 +1,253 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2007
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#include <iostream>
+#include <sstream>
+#include <vector>
+#include <queue>
+#include <cmath>
+#include <cstdlib>
+
+#include "test_tools.h"
+#include <lemon/smart_graph.h>
+#include <lemon/max_matching.h>
+#include <lemon/graph_reader.h>
+
+UGRAPH_TYPEDEFS(SmartUGraph);
+
+using namespace std;
+using namespace lemon;
+
+const int lgfn = 3;
+const std::string lgf[lgfn] = {   
+  "@nodeset\n"
+  "label\n"
+  "0\n"
+  "1\n"
+  "2\n"
+  "3\n"
+  "4\n"
+  "5\n"
+  "6\n"
+  "7\n"
+  "@uedgeset\n"
+  "label        weight\n"
+  "7    4       0       984\n"
+  "0    7       1       73\n"
+  "7    1       2       204\n"
+  "2    3       3       583\n"
+  "2    7       4       565\n"
+  "2    1       5       582\n"
+  "0    4       6       551\n"
+  "2    5       7       385\n"
+  "1    5       8       561\n"
+  "5    3       9       484\n"
+  "7    5       10      904\n"
+  "3    6       11      47\n"
+  "7    6       12      888\n"
+  "3    0       13      747\n"
+  "6    1       14      310\n"
+  "@end\n",
+
+  "@nodeset\n"
+  "label\n"
+  "0\n"
+  "1\n"
+  "2\n"
+  "3\n"
+  "4\n"
+  "5\n"
+  "6\n"
+  "7\n"
+  "@uedgeset\n"
+  "label        weight\n"
+  "2    5       0       710\n"
+  "0    5       1       241\n"
+  "2    4       2       856\n"
+  "2    6       3       762\n"
+  "4    1       4       747\n"
+  "6    1       5       962\n"
+  "4    7       6       723\n"
+  "1    7       7       661\n"
+  "2    3       8       376\n"
+  "1    0       9       416\n"
+  "6    7       10      391\n"
+  "@end\n",
+
+  "@nodeset\n"
+  "label\n"
+  "0\n"
+  "1\n"
+  "2\n"
+  "3\n"
+  "4\n"
+  "5\n"
+  "6\n"
+  "7\n"
+  "@uedgeset\n"
+  "label        weight\n"
+  "6    2       0       553\n"
+  "0    7       1       653\n"
+  "6    3       2       22\n"
+  "4    7       3       846\n"
+  "7    2       4       981\n"
+  "7    6       5       250\n"
+  "5    2       6       539\n"
+  "@end\n"
+};
+
+void checkMatching(const SmartUGraph& ugraph,
+		   const SmartUGraph::UEdgeMap<int>& weight,
+		   const MaxWeightedMatching<SmartUGraph>& mwm) {
+  for (SmartUGraph::UEdgeIt e(ugraph); e != INVALID; ++e) {
+    if (ugraph.source(e) == ugraph.target(e)) continue;
+    int rw = 
+      mwm.nodeValue(ugraph.source(e)) + mwm.nodeValue(ugraph.target(e));
+
+    for (int i = 0; i < mwm.blossomNum(); ++i) {
+      bool s = false, t = false;
+      for (MaxWeightedMatching<SmartUGraph>::BlossomIt n(mwm, i); 
+	   n != INVALID; ++n) {
+	if (ugraph.source(e) == n) s = true;
+	if (ugraph.target(e) == n) t = true;
+      }
+      if (s == true && t == true) {
+	rw += mwm.blossomValue(i);
+      }
+    }
+    rw -= weight[e] * mwm.dualScale;
+
+    check(rw >= 0, "Negative reduced weight");
+    check(rw == 0 || !mwm.matching(e), 
+	  "Non-zero reduced weight on matching edge");
+  }
+
+  int pv = 0;
+  for (SmartUGraph::NodeIt n(ugraph); n != INVALID; ++n) {
+    if (mwm.matching(n) != INVALID) {
+      check(mwm.nodeValue(n) >= 0, "Invalid node value");
+      pv += weight[mwm.matching(n)];
+      SmartUGraph::Node o = ugraph.target(mwm.matching(n));
+      check(mwm.mate(n) == o, "Invalid matching");
+      check(mwm.matching(n) == ugraph.oppositeEdge(mwm.matching(o)), 
+	    "Invalid matching");
+    } else {
+      check(mwm.mate(n) == INVALID, "Invalid matching");
+      check(mwm.nodeValue(n) == 0, "Invalid matching");
+    }
+  }
+
+  int dv = 0;
+  for (SmartUGraph::NodeIt n(ugraph); n != INVALID; ++n) {
+    dv += mwm.nodeValue(n);
+  }
+
+  for (int i = 0; i < mwm.blossomNum(); ++i) {
+    check(mwm.blossomValue(i) >= 0, "Invalid blossom value");
+    check(mwm.blossomSize(i) % 2 == 1, "Even blossom size");
+    dv += mwm.blossomValue(i) * ((mwm.blossomSize(i) - 1) / 2);
+  }
+
+  check(pv * mwm.dualScale == dv * 2, "Wrong duality");
+
+  return;
+}
+
+void checkPerfectMatching(const SmartUGraph& ugraph,
+			  const SmartUGraph::UEdgeMap<int>& weight,
+			  const MaxWeightedPerfectMatching<SmartUGraph>& mwpm) {
+  for (SmartUGraph::UEdgeIt e(ugraph); e != INVALID; ++e) {
+    if (ugraph.source(e) == ugraph.target(e)) continue;
+    int rw = 
+      mwpm.nodeValue(ugraph.source(e)) + mwpm.nodeValue(ugraph.target(e));
+
+    for (int i = 0; i < mwpm.blossomNum(); ++i) {
+      bool s = false, t = false;
+      for (MaxWeightedPerfectMatching<SmartUGraph>::BlossomIt n(mwpm, i); 
+	   n != INVALID; ++n) {
+	if (ugraph.source(e) == n) s = true;
+	if (ugraph.target(e) == n) t = true;
+      }
+      if (s == true && t == true) {
+	rw += mwpm.blossomValue(i);
+      }
+    }
+    rw -= weight[e] * mwpm.dualScale;
+
+    check(rw >= 0, "Negative reduced weight");
+    check(rw == 0 || !mwpm.matching(e), 
+	  "Non-zero reduced weight on matching edge");
+  }
+
+  int pv = 0;
+  for (SmartUGraph::NodeIt n(ugraph); n != INVALID; ++n) {
+    check(mwpm.matching(n) != INVALID, "Non perfect");
+    pv += weight[mwpm.matching(n)];
+    SmartUGraph::Node o = ugraph.target(mwpm.matching(n));
+    check(mwpm.mate(n) == o, "Invalid matching");
+    check(mwpm.matching(n) == ugraph.oppositeEdge(mwpm.matching(o)), 
+	  "Invalid matching");
+  }
+
+  int dv = 0;
+  for (SmartUGraph::NodeIt n(ugraph); n != INVALID; ++n) {
+    dv += mwpm.nodeValue(n);
+  }
+
+  for (int i = 0; i < mwpm.blossomNum(); ++i) {
+    check(mwpm.blossomValue(i) >= 0, "Invalid blossom value");
+    check(mwpm.blossomSize(i) % 2 == 1, "Even blossom size");
+    dv += mwpm.blossomValue(i) * ((mwpm.blossomSize(i) - 1) / 2);
+  }
+
+  check(pv * mwpm.dualScale == dv * 2, "Wrong duality");
+
+  return;
+}
+
+
+int main() {
+
+  for (int i = 0; i < lgfn; ++i) {
+    SmartUGraph ugraph;
+    SmartUGraph::UEdgeMap<int> weight(ugraph);
+    
+    istringstream lgfs(lgf[i]);
+    UGraphReader<SmartUGraph>(lgfs, ugraph).
+      readUEdgeMap("weight", weight).run();
+
+    MaxWeightedMatching<SmartUGraph> mwm(ugraph, weight);
+    mwm.run();
+    checkMatching(ugraph, weight, mwm);
+
+    MaxMatching<SmartUGraph> mm(ugraph);
+    mm.run();
+
+    MaxWeightedPerfectMatching<SmartUGraph> mwpm(ugraph, weight);
+    bool perfect = mwpm.run();
+
+    check(perfect == (mm.size() * 2 == countNodes(ugraph)), 
+	  "Perfect matching found");
+
+    if (perfect) {
+      checkPerfectMatching(ugraph, weight, mwpm);
+    }
+  }
+  
+  return 0;
+}