Changeset 872:41d7ac528c3a in lemon-main

Timestamp:

03/04/10 15:20:59 (15 years ago)

Author:

Balazs Dezso <deba@…>

Branch:

default

Phase:

public

Message:

Uniforming primal scale to 2 (#314)

Files:

• lemon/fractional_matching.h (modified) (6 diffs)
• test/fractional_matching_test.cc (modified) (4 diffs)

lemon/fractional_matching.h

@@ -659 +659 @@
   /// can be obtained using the query functions.
   ///
-  /// If the value type is integer, then the primal and the dual
-  /// solutions are multiplied by
-  /// \ref MaxWeightedFractionalMatching::primalScale "2" and
-  /// \ref MaxWeightedFractionalMatching::dualScale "4" respectively.
+  /// The primal solution is multiplied by
+  /// \ref MaxWeightedFractionalMatching::primalScale "2".
+  /// If the value type is integer, then the dual
+  /// solution is scaled by
+  /// \ref MaxWeightedFractionalMatching::dualScale "4".
   ///
   /// \tparam GR The undirected graph type the algorithm runs on.
@@ -689 +690 @@
     /// \brief Scaling factor for primal solution
     ///
-    /// Scaling factor for primal solution. It is equal to 2 or 1
-    /// according to the value type.
-    static const int primalScale =
-      std::numeric_limits<Value>::is_integer ? 2 : 1;
+    /// Scaling factor for primal solution.
+    static const int primalScale = 2;
 
     /// \brief Scaling factor for dual solution
@@ -1330 +1329 @@
     ///
     /// \pre Either run() or start() must be called before using this function.
-    Value matching(const Edge& edge) const {
-      return Value(edge == (*_matching)[_graph.u(edge)] ? 1 : 0)
-        * primalScale / 2 + Value(edge == (*_matching)[_graph.v(edge)] ? 1 : 0)
-        * primalScale / 2;
+    int matching(const Edge& edge) const {
+      return (edge == (*_matching)[_graph.u(edge)] ? 1 : 0)
+        + (edge == (*_matching)[_graph.v(edge)] ? 1 : 0);
     }
 
@@ -1424 +1422 @@
   /// After it the matching (the primal solution) and the dual solution
   /// can be obtained using the query functions.
-
-  /// If the value type is integer, then the primal and the dual
-  /// solutions are multiplied by
-  /// \ref MaxWeightedPerfectFractionalMatching::primalScale "2" and
-  /// \ref MaxWeightedPerfectFractionalMatching::dualScale "4" respectively.
+  ///
+  /// The primal solution is multiplied by
+  /// \ref MaxWeightedPerfectFractionalMatching::primalScale "2".
+  /// If the value type is integer, then the dual
+  /// solution is scaled by
+  /// \ref MaxWeightedPerfectFractionalMatching::dualScale "4".
   ///
   /// \tparam GR The undirected graph type the algorithm runs on.
@@ -1455 +1454 @@
     /// \brief Scaling factor for primal solution
     ///
-    /// Scaling factor for primal solution. It is equal to 2 or 1
-    /// according to the value type.
-    static const int primalScale =
-      std::numeric_limits<Value>::is_integer ? 2 : 1;
+    /// Scaling factor for primal solution.
+    static const int primalScale = 2;
 
     /// \brief Scaling factor for dual solution
@@ -2065 +2062 @@
     ///
     /// \pre Either run() or start() must be called before using this function.
-    Value matching(const Edge& edge) const {
-      return Value(edge == (*_matching)[_graph.u(edge)] ? 1 : 0)
-        * primalScale / 2 + Value(edge == (*_matching)[_graph.v(edge)] ? 1 : 0)
-        * primalScale / 2;
+    int matching(const Edge& edge) const {
+      return (edge == (*_matching)[_graph.u(edge)] ? 1 : 0)
+        + (edge == (*_matching)[_graph.v(edge)] ? 1 : 0);
     }
 

test/fractional_matching_test.cc

@@ -237 +237 @@
   check(pv == mfm.matchingSize(), "Wrong matching size");
 
+  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
+    check((e == mfm.matching(graph.u(e)) ? 1 : 0) +
+          (e == mfm.matching(graph.v(e)) ? 1 : 0) == 
+          mfm.matching(e), "Invalid matching");
+  }
+
   SmartGraph::NodeMap<bool> processed(graph, false);
   for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
@@ -284 +290 @@
       check(mfm.matching(n) != INVALID, "Invalid matching");
       check(indeg == 1, "Invalid matching");
+    }
+    for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
+      check((e == mfm.matching(graph.u(e)) ? 1 : 0) +
+            (e == mfm.matching(graph.v(e)) ? 1 : 0) == 
+            mfm.matching(e), "Invalid matching");
     }
   } else {
@@ -338 +349 @@
   }
 
+  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
+    check((e == mwfm.matching(graph.u(e)) ? 1 : 0) +
+          (e == mwfm.matching(graph.v(e)) ? 1 : 0) == 
+          mwfm.matching(e), "Invalid matching");
+  }
+
   int dv = 0;
   for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
@@ -392 +409 @@
   }
 
+  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
+    check((e == mwpfm.matching(graph.u(e)) ? 1 : 0) +
+          (e == mwpfm.matching(graph.v(e)) ? 1 : 0) == 
+          mwpfm.matching(e), "Invalid matching");
+  }
+
   int dv = 0;
   for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {