author Balazs Dezso Thu, 04 Mar 2010 15:20:59 +0100 changeset 951 41d7ac528c3a parent 950 86613aa28a0c child 953 d8ea85825e02
Uniforming primal scale to 2 (#314)
 lemon/fractional_matching.h file | annotate | diff | comparison | revisions test/fractional_matching_test.cc file | annotate | diff | comparison | revisions
     1.1 --- a/lemon/fractional_matching.h	Thu Mar 04 10:17:02 2010 +0100
1.2 +++ b/lemon/fractional_matching.h	Thu Mar 04 15:20:59 2010 +0100
1.3 @@ -658,10 +658,11 @@
1.4    /// After it the matching (the primal solution) and the dual solution
1.5    /// can be obtained using the query functions.
1.6    ///
1.7 -  /// If the value type is integer, then the primal and the dual
1.8 -  /// solutions are multiplied by
1.9 -  /// \ref MaxWeightedFractionalMatching::primalScale "2" and
1.10 -  /// \ref MaxWeightedFractionalMatching::dualScale "4" respectively.
1.11 +  /// The primal solution is multiplied by
1.12 +  /// \ref MaxWeightedFractionalMatching::primalScale "2".
1.13 +  /// If the value type is integer, then the dual
1.14 +  /// solution is scaled by
1.15 +  /// \ref MaxWeightedFractionalMatching::dualScale "4".
1.16    ///
1.17    /// \tparam GR The undirected graph type the algorithm runs on.
1.18    /// \tparam WM The type edge weight map. The default type is
1.19 @@ -688,10 +689,8 @@
1.20
1.21      /// \brief Scaling factor for primal solution
1.22      ///
1.23 -    /// Scaling factor for primal solution. It is equal to 2 or 1
1.24 -    /// according to the value type.
1.25 -    static const int primalScale =
1.26 -      std::numeric_limits<Value>::is_integer ? 2 : 1;
1.27 +    /// Scaling factor for primal solution.
1.28 +    static const int primalScale = 2;
1.29
1.30      /// \brief Scaling factor for dual solution
1.31      ///
1.32 @@ -1329,10 +1328,9 @@
1.33      /// "primal scale".
1.34      ///
1.35      /// \pre Either run() or start() must be called before using this function.
1.36 -    Value matching(const Edge& edge) const {
1.37 -      return Value(edge == (*_matching)[_graph.u(edge)] ? 1 : 0)
1.38 -        * primalScale / 2 + Value(edge == (*_matching)[_graph.v(edge)] ? 1 : 0)
1.39 -        * primalScale / 2;
1.40 +    int matching(const Edge& edge) const {
1.41 +      return (edge == (*_matching)[_graph.u(edge)] ? 1 : 0)
1.42 +        + (edge == (*_matching)[_graph.v(edge)] ? 1 : 0);
1.43      }
1.44
1.45      /// \brief Return the fractional matching arc (or edge) incident
1.46 @@ -1423,11 +1421,12 @@
1.47    /// The algorithm can be executed with the run() function.
1.48    /// After it the matching (the primal solution) and the dual solution
1.49    /// can be obtained using the query functions.
1.50 -
1.51 -  /// If the value type is integer, then the primal and the dual
1.52 -  /// solutions are multiplied by
1.53 -  /// \ref MaxWeightedPerfectFractionalMatching::primalScale "2" and
1.54 -  /// \ref MaxWeightedPerfectFractionalMatching::dualScale "4" respectively.
1.55 +  ///
1.56 +  /// The primal solution is multiplied by
1.57 +  /// \ref MaxWeightedPerfectFractionalMatching::primalScale "2".
1.58 +  /// If the value type is integer, then the dual
1.59 +  /// solution is scaled by
1.60 +  /// \ref MaxWeightedPerfectFractionalMatching::dualScale "4".
1.61    ///
1.62    /// \tparam GR The undirected graph type the algorithm runs on.
1.63    /// \tparam WM The type edge weight map. The default type is
1.64 @@ -1454,10 +1453,8 @@
1.65
1.66      /// \brief Scaling factor for primal solution
1.67      ///
1.68 -    /// Scaling factor for primal solution. It is equal to 2 or 1
1.69 -    /// according to the value type.
1.70 -    static const int primalScale =
1.71 -      std::numeric_limits<Value>::is_integer ? 2 : 1;
1.72 +    /// Scaling factor for primal solution.
1.73 +    static const int primalScale = 2;
1.74
1.75      /// \brief Scaling factor for dual solution
1.76      ///
1.77 @@ -2064,10 +2061,9 @@
1.78      /// "primal scale".
1.79      ///
1.80      /// \pre Either run() or start() must be called before using this function.
1.81 -    Value matching(const Edge& edge) const {
1.82 -      return Value(edge == (*_matching)[_graph.u(edge)] ? 1 : 0)
1.83 -        * primalScale / 2 + Value(edge == (*_matching)[_graph.v(edge)] ? 1 : 0)
1.84 -        * primalScale / 2;
1.85 +    int matching(const Edge& edge) const {
1.86 +      return (edge == (*_matching)[_graph.u(edge)] ? 1 : 0)
1.87 +        + (edge == (*_matching)[_graph.v(edge)] ? 1 : 0);
1.88      }
1.89
1.90      /// \brief Return the fractional matching arc (or edge) incident

     2.1 --- a/test/fractional_matching_test.cc	Thu Mar 04 10:17:02 2010 +0100
2.2 +++ b/test/fractional_matching_test.cc	Thu Mar 04 15:20:59 2010 +0100
2.3 @@ -236,6 +236,12 @@
2.4    }
2.5    check(pv == mfm.matchingSize(), "Wrong matching size");
2.6
2.7 +  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
2.8 +    check((e == mfm.matching(graph.u(e)) ? 1 : 0) +
2.9 +          (e == mfm.matching(graph.v(e)) ? 1 : 0) ==
2.10 +          mfm.matching(e), "Invalid matching");
2.11 +  }
2.12 +
2.13    SmartGraph::NodeMap<bool> processed(graph, false);
2.14    for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
2.15      if (processed[n]) continue;
2.16 @@ -284,6 +290,11 @@
2.17        check(mfm.matching(n) != INVALID, "Invalid matching");
2.18        check(indeg == 1, "Invalid matching");
2.19      }
2.20 +    for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
2.21 +      check((e == mfm.matching(graph.u(e)) ? 1 : 0) +
2.22 +            (e == mfm.matching(graph.v(e)) ? 1 : 0) ==
2.23 +            mfm.matching(e), "Invalid matching");
2.24 +    }
2.25    } else {
2.26      int anum = 0, bnum = 0;
2.27      SmartGraph::NodeMap<bool> neighbours(graph, false);
2.28 @@ -337,6 +348,12 @@
2.29      }
2.30    }
2.31
2.32 +  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
2.33 +    check((e == mwfm.matching(graph.u(e)) ? 1 : 0) +
2.34 +          (e == mwfm.matching(graph.v(e)) ? 1 : 0) ==
2.35 +          mwfm.matching(e), "Invalid matching");
2.36 +  }
2.37 +
2.38    int dv = 0;
2.39    for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
2.40      dv += mwfm.nodeValue(n);
2.41 @@ -391,6 +408,12 @@
2.42      SmartGraph::Node o = graph.target(mwpfm.matching(n));
2.43    }
2.44
2.45 +  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
2.46 +    check((e == mwpfm.matching(graph.u(e)) ? 1 : 0) +
2.47 +          (e == mwpfm.matching(graph.v(e)) ? 1 : 0) ==
2.48 +          mwpfm.matching(e), "Invalid matching");
2.49 +  }
2.50 +
2.51    int dv = 0;
2.52    for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
2.53      dv += mwpfm.nodeValue(n);