COIN-OR::LEMON - Graph Library

Changeset 872:41d7ac528c3a in lemon-1.2


Ignore:
Timestamp:
03/04/10 15:20:59 (14 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

Uniforming primal scale to 2 (#314)

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/fractional_matching.h

    r871 r872  
    659659  /// can be obtained using the query functions.
    660660  ///
    661   /// If the value type is integer, then the primal and the dual
    662   /// solutions are multiplied by
    663   /// \ref MaxWeightedFractionalMatching::primalScale "2" and
    664   /// \ref MaxWeightedFractionalMatching::dualScale "4" respectively.
     661  /// The primal solution is multiplied by
     662  /// \ref MaxWeightedFractionalMatching::primalScale "2".
     663  /// If the value type is integer, then the dual
     664  /// solution is scaled by
     665  /// \ref MaxWeightedFractionalMatching::dualScale "4".
    665666  ///
    666667  /// \tparam GR The undirected graph type the algorithm runs on.
     
    689690    /// \brief Scaling factor for primal solution
    690691    ///
    691     /// Scaling factor for primal solution. It is equal to 2 or 1
    692     /// according to the value type.
    693     static const int primalScale =
    694       std::numeric_limits<Value>::is_integer ? 2 : 1;
     692    /// Scaling factor for primal solution.
     693    static const int primalScale = 2;
    695694
    696695    /// \brief Scaling factor for dual solution
     
    13301329    ///
    13311330    /// \pre Either run() or start() must be called before using this function.
    1332     Value matching(const Edge& edge) const {
    1333       return Value(edge == (*_matching)[_graph.u(edge)] ? 1 : 0)
    1334         * primalScale / 2 + Value(edge == (*_matching)[_graph.v(edge)] ? 1 : 0)
    1335         * primalScale / 2;
     1331    int matching(const Edge& edge) const {
     1332      return (edge == (*_matching)[_graph.u(edge)] ? 1 : 0)
     1333        + (edge == (*_matching)[_graph.v(edge)] ? 1 : 0);
    13361334    }
    13371335
     
    14241422  /// After it the matching (the primal solution) and the dual solution
    14251423  /// can be obtained using the query functions.
    1426 
    1427   /// If the value type is integer, then the primal and the dual
    1428   /// solutions are multiplied by
    1429   /// \ref MaxWeightedPerfectFractionalMatching::primalScale "2" and
    1430   /// \ref MaxWeightedPerfectFractionalMatching::dualScale "4" respectively.
     1424  ///
     1425  /// The primal solution is multiplied by
     1426  /// \ref MaxWeightedPerfectFractionalMatching::primalScale "2".
     1427  /// If the value type is integer, then the dual
     1428  /// solution is scaled by
     1429  /// \ref MaxWeightedPerfectFractionalMatching::dualScale "4".
    14311430  ///
    14321431  /// \tparam GR The undirected graph type the algorithm runs on.
     
    14551454    /// \brief Scaling factor for primal solution
    14561455    ///
    1457     /// Scaling factor for primal solution. It is equal to 2 or 1
    1458     /// according to the value type.
    1459     static const int primalScale =
    1460       std::numeric_limits<Value>::is_integer ? 2 : 1;
     1456    /// Scaling factor for primal solution.
     1457    static const int primalScale = 2;
    14611458
    14621459    /// \brief Scaling factor for dual solution
     
    20652062    ///
    20662063    /// \pre Either run() or start() must be called before using this function.
    2067     Value matching(const Edge& edge) const {
    2068       return Value(edge == (*_matching)[_graph.u(edge)] ? 1 : 0)
    2069         * primalScale / 2 + Value(edge == (*_matching)[_graph.v(edge)] ? 1 : 0)
    2070         * primalScale / 2;
     2064    int matching(const Edge& edge) const {
     2065      return (edge == (*_matching)[_graph.u(edge)] ? 1 : 0)
     2066        + (edge == (*_matching)[_graph.v(edge)] ? 1 : 0);
    20712067    }
    20722068
  • test/fractional_matching_test.cc

    r869 r872  
    237237  check(pv == mfm.matchingSize(), "Wrong matching size");
    238238
     239  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
     240    check((e == mfm.matching(graph.u(e)) ? 1 : 0) +
     241          (e == mfm.matching(graph.v(e)) ? 1 : 0) ==
     242          mfm.matching(e), "Invalid matching");
     243  }
     244
    239245  SmartGraph::NodeMap<bool> processed(graph, false);
    240246  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
     
    284290      check(mfm.matching(n) != INVALID, "Invalid matching");
    285291      check(indeg == 1, "Invalid matching");
     292    }
     293    for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
     294      check((e == mfm.matching(graph.u(e)) ? 1 : 0) +
     295            (e == mfm.matching(graph.v(e)) ? 1 : 0) ==
     296            mfm.matching(e), "Invalid matching");
    286297    }
    287298  } else {
     
    338349  }
    339350
     351  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
     352    check((e == mwfm.matching(graph.u(e)) ? 1 : 0) +
     353          (e == mwfm.matching(graph.v(e)) ? 1 : 0) ==
     354          mwfm.matching(e), "Invalid matching");
     355  }
     356
    340357  int dv = 0;
    341358  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
     
    392409  }
    393410
     411  for (SmartGraph::EdgeIt e(graph); e != INVALID; ++e) {
     412    check((e == mwpfm.matching(graph.u(e)) ? 1 : 0) +
     413          (e == mwpfm.matching(graph.v(e)) ? 1 : 0) ==
     414          mwpfm.matching(e), "Invalid matching");
     415  }
     416
    394417  int dv = 0;
    395418  for (SmartGraph::NodeIt n(graph); n != INVALID; ++n) {
Note: See TracChangeset for help on using the changeset viewer.