COIN-OR::LEMON - Graph Library

Changeset 951:41d7ac528c3a in lemon


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

Uniforming primal scale to 2 (#314)

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/fractional_matching.h

    r950 r951  
    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

    r948 r951  
    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.