COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 607:9ad8d2122b50 in lemon-main


Ignore:
Timestamp:
04/03/09 13:46:16 (16 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Separate types for flow and cost values in NetworkSimplex? (#234)

Files:
2 edited

Legend:

Unmodified
Added
Removed

  • lemon/network_simplex.h

    r606 r607  
    5050  ///
    5151  /// \tparam GR The digraph type the algorithm runs on.
    52   /// \tparam V The value type used in the algorithm.
    53   /// By default it is \c int.
     52  /// \tparam F The value type used for flow amounts, capacity bounds
     53  /// and supply values in the algorithm. By default it is \c int.
     54  /// \tparam C The value type used for costs and potentials in the
     55  /// algorithm. By default it is the same as \c F.
    5456  ///
    55   /// \warning The value type must be a signed integer type.
     57  /// \warning Both value types must be signed integer types.
    5658  ///
    5759  /// \note %NetworkSimplex provides five different pivot rule
    5860  /// implementations. For more information see \ref PivotRule.
    59   template <typename GR, typename V = int>
     61  template <typename GR, typename F = int, typename C = F>
    6062  class NetworkSimplex
    6163  {
    6264  public:
    6365
    64     /// The value type of the algorithm
    65     typedef V Value;
     66    /// The flow type of the algorithm
     67    typedef F Flow;
     68    /// The cost type of the algorithm
     69    typedef C Cost;
    6670    /// The type of the flow map
    67     typedef typename GR::template ArcMap<Value> FlowMap;
     71    typedef typename GR::template ArcMap<Flow> FlowMap;
    6872    /// The type of the potential map
    69     typedef typename GR::template NodeMap<Value> PotentialMap;
     73    typedef typename GR::template NodeMap<Cost> PotentialMap;
    7074
    7175  public:
    … …  
    118122    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
    119123
    120     typedef typename GR::template ArcMap<Value> ValueArcMap;
    121     typedef typename GR::template NodeMap<Value> ValueNodeMap;
     124    typedef typename GR::template ArcMap<Flow> FlowArcMap;
     125    typedef typename GR::template ArcMap<Cost> CostArcMap;
     126    typedef typename GR::template NodeMap<Flow> FlowNodeMap;
    122127
    123128    typedef std::vector<Arc> ArcVector;
    … …  
    125130    typedef std::vector<int> IntVector;
    126131    typedef std::vector<bool> BoolVector;
    127     typedef std::vector<Value> ValueVector;
     132    typedef std::vector<Flow> FlowVector;
     133    typedef std::vector<Cost> CostVector;
    128134
    129135    // State constants for arcs
    … …  
    142148
    143149    // Parameters of the problem
    144     ValueArcMap *_plower;
    145     ValueArcMap *_pupper;
    146     ValueArcMap *_pcost;
    147     ValueNodeMap *_psupply;
     150    FlowArcMap *_plower;
     151    FlowArcMap *_pupper;
     152    CostArcMap *_pcost;
     153    FlowNodeMap *_psupply;
    148154    bool _pstsup;
    149155    Node _psource, _ptarget;
    150     Value _pstflow;
     156    Flow _pstflow;
    151157
    152158    // Result maps
    … …  
    163169
    164170    // Node and arc data
    165     ValueVector _cap;
    166     ValueVector _cost;
    167     ValueVector _supply;
    168     ValueVector _flow;
    169     ValueVector _pi;
     171    FlowVector _cap;
     172    CostVector _cost;
     173    FlowVector _supply;
     174    FlowVector _flow;
     175    CostVector _pi;
    170176
    171177    // Data for storing the spanning tree structure
    … …  
    185191    int first, second, right, last;
    186192    int stem, par_stem, new_stem;
    187     Value delta;
     193    Flow delta;
    188194
    189195  private:
    … …  
    197203      const IntVector  &_source;
    198204      const IntVector  &_target;
    199       const ValueVector &_cost;
     205      const CostVector &_cost;
    200206      const IntVector  &_state;
    201       const ValueVector &_pi;
     207      const CostVector &_pi;
    202208      int &_in_arc;
    203209      int _arc_num;
    … …  
    217223      // Find next entering arc
    218224      bool findEnteringArc() {
    219         Value c;
     225        Cost c;
    220226        for (int e = _next_arc; e < _arc_num; ++e) {
    221227          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    … …  
    248254      const IntVector  &_source;
    249255      const IntVector  &_target;
    250       const ValueVector &_cost;
     256      const CostVector &_cost;
    251257      const IntVector  &_state;
    252       const ValueVector &_pi;
     258      const CostVector &_pi;
    253259      int &_in_arc;
    254260      int _arc_num;
    … …  
    265271      // Find next entering arc
    266272      bool findEnteringArc() {
    267         Value c, min = 0;
     273        Cost c, min = 0;
    268274        for (int e = 0; e < _arc_num; ++e) {
    269275          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    … …  
    287293      const IntVector  &_source;
    288294      const IntVector  &_target;
    289       const ValueVector &_cost;
     295      const CostVector &_cost;
    290296      const IntVector  &_state;
    291       const ValueVector &_pi;
     297      const CostVector &_pi;
    292298      int &_in_arc;
    293299      int _arc_num;
    … …  
    315321      // Find next entering arc
    316322      bool findEnteringArc() {
    317         Value c, min = 0;
     323        Cost c, min = 0;
    318324        int cnt = _block_size;
    319325        int e, min_arc = _next_arc;
    … …  
    359365      const IntVector  &_source;
    360366      const IntVector  &_target;
    361       const ValueVector &_cost;
     367      const CostVector &_cost;
    362368      const IntVector  &_state;
    363       const ValueVector &_pi;
     369      const CostVector &_pi;
    364370      int &_in_arc;
    365371      int _arc_num;
    … …  
    395401      /// Find next entering arc
    396402      bool findEnteringArc() {
    397         Value min, c;
     403        Cost min, c;
    398404        int e, min_arc = _next_arc;
    399405        if (_curr_length > 0 && _minor_count < _minor_limit) {
    … …  
    464470      const IntVector  &_source;
    465471      const IntVector  &_target;
    466       const ValueVector &_cost;
     472      const CostVector &_cost;
    467473      const IntVector  &_state;
    468       const ValueVector &_pi;
     474      const CostVector &_pi;
    469475      int &_in_arc;
    470476      int _arc_num;
    … …  
    474480      int _next_arc;
    475481      IntVector _candidates;
    476       ValueVector _cand_cost;
     482      CostVector _cand_cost;
    477483
    478484      // Functor class to compare arcs during sort of the candidate list
    … …  
    480486      {
    481487      private:
    482         const ValueVector &_map;
     488        const CostVector &_map;
    483489      public:
    484         SortFunc(const ValueVector &map) : _map(map) {}
     490        SortFunc(const CostVector &map) : _map(map) {}
    485491        bool operator()(int left, int right) {
    486492          return _map[left] > _map[right];
    … …  
    591597      _node_id(graph)
    592598    {
    593       LEMON_ASSERT(std::numeric_limits<Value>::is_integer &&
    594                    std::numeric_limits<Value>::is_signed,
    595         "The value type of NetworkSimplex must be a signed integer");
     599      LEMON_ASSERT(std::numeric_limits<Flow>::is_integer &&
     600                   std::numeric_limits<Flow>::is_signed,
     601        "The flow type of NetworkSimplex must be signed integer");
     602      LEMON_ASSERT(std::numeric_limits<Cost>::is_integer &&
     603                   std::numeric_limits<Cost>::is_signed,
     604        "The cost type of NetworkSimplex must be signed integer");
    596605    }
    597606
    … …  
    610619    ///
    611620    /// \param map An arc map storing the lower bounds.
    612     /// Its \c Value type must be convertible to the \c Value type
     621    /// Its \c Value type must be convertible to the \c Flow type
    613622    /// of the algorithm.
    614623    ///
    … …  
    617626    NetworkSimplex& lowerMap(const LOWER& map) {
    618627      delete _plower;
    619       _plower = new ValueArcMap(_graph);
     628      _plower = new FlowArcMap(_graph);
    620629      for (ArcIt a(_graph); a != INVALID; ++a) {
    621630        (*_plower)[a] = map[a];
    … …  
    630639    /// and \ref boundMaps() is used before calling \ref run(),
    631640    /// the upper bounds (capacities) will be set to
    632     /// \c std::numeric_limits<Value>::max() on all arcs.
     641    /// \c std::numeric_limits<Flow>::max() on all arcs.
    633642    ///
    634643    /// \param map An arc map storing the upper bounds.
    635     /// Its \c Value type must be convertible to the \c Value type
     644    /// Its \c Value type must be convertible to the \c Flow type
    636645    /// of the algorithm.
    637646    ///
    … …  
    640649    NetworkSimplex& upperMap(const UPPER& map) {
    641650      delete _pupper;
    642       _pupper = new ValueArcMap(_graph);
     651      _pupper = new FlowArcMap(_graph);
    643652      for (ArcIt a(_graph); a != INVALID; ++a) {
    644653        (*_pupper)[a] = map[a];
    … …  
    667676    /// and \ref boundMaps() is used before calling \ref run(),
    668677    /// the upper bounds (capacities) will be set to
    669     /// \c std::numeric_limits<Value>::max() on all arcs.
     678    /// \c std::numeric_limits<Flow>::max() on all arcs.
    670679    ///
    671680    /// \param lower An arc map storing the lower bounds.
    … …  
    673682    ///
    674683    /// The \c Value type of the maps must be convertible to the
    675     /// \c Value type of the algorithm.
     684    /// \c Flow type of the algorithm.
    676685    ///
    677686    /// \note This function is just a shortcut of calling \ref lowerMap()
    … …  
    691700    ///
    692701    /// \param map An arc map storing the costs.
    693     /// Its \c Value type must be convertible to the \c Value type
     702    /// Its \c Value type must be convertible to the \c Cost type
    694703    /// of the algorithm.
    695704    ///
    … …  
    698707    NetworkSimplex& costMap(const COST& map) {
    699708      delete _pcost;
    700       _pcost = new ValueArcMap(_graph);
     709      _pcost = new CostArcMap(_graph);
    701710      for (ArcIt a(_graph); a != INVALID; ++a) {
    702711        (*_pcost)[a] = map[a];
    … …  
    713722    ///
    714723    /// \param map A node map storing the supply values.
    715     /// Its \c Value type must be convertible to the \c Value type
     724    /// Its \c Value type must be convertible to the \c Flow type
    716725    /// of the algorithm.
    717726    ///
    … …  
    721730      delete _psupply;
    722731      _pstsup = false;
    723       _psupply = new ValueNodeMap(_graph);
     732      _psupply = new FlowNodeMap(_graph);
    724733      for (NodeIt n(_graph); n != INVALID; ++n) {
    725734        (*_psupply)[n] = map[n];
    … …  
    742751    ///
    743752    /// \return <tt>(*this)</tt>
    744     NetworkSimplex& stSupply(const Node& s, const Node& t, Value k) {
     753    NetworkSimplex& stSupply(const Node& s, const Node& t, Flow k) {
    745754      delete _psupply;
    746755      _psupply = NULL;
    … …  
    875884    ///
    876885    /// This function returns the total cost of the found flow.
    877     /// The complexity of the function is \f$ O(e) \f$.
     886    /// The complexity of the function is O(e).
    878887    ///
    879888    /// \note The return type of the function can be specified as a
    … …  
    882891    ///   ns.totalCost<double>();
    883892    /// \endcode
    884     /// It is useful if the total cost cannot be stored in the \c Value
     893    /// It is useful if the total cost cannot be stored in the \c Cost
    885894    /// type of the algorithm, which is the default return type of the
    886895    /// function.
    … …  
    901910
    902911#ifndef DOXYGEN
    903     Value totalCost() const {
    904       return totalCost<Value>();
     912    Cost totalCost() const {
     913      return totalCost<Cost>();
    905914    }
    906915#endif
    … …  
    911920    ///
    912921    /// \pre \ref run() must be called before using this function.
    913     Value flow(const Arc& a) const {
     922    Flow flow(const Arc& a) const {
    914923      return (*_flow_map)[a];
    915924    }
    … …  
    931940    ///
    932941    /// \pre \ref run() must be called before using this function.
    933     Value potential(const Node& n) const {
     942    Cost potential(const Node& n) const {
    934943      return (*_potential_map)[n];
    935944    }
    … …  
    9971006      }
    9981007      if (_psupply) {
    999         Value sum = 0;
     1008        Flow sum = 0;
    10001009        int i = 0;
    10011010        for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
    … …  
    10361045
    10371046      // Initialize arc maps
     1047      Flow max_cap = std::numeric_limits<Flow>::max();
     1048      Cost max_cost = std::numeric_limits<Cost>::max() / 4;
    10381049      if (_pupper && _pcost) {
    10391050        for (int i = 0; i != _arc_num; ++i) {
    … …  
    10581069            _cap[i] = (*_pupper)[_arc_ref[i]];
    10591070        } else {
    1060           Value val = std::numeric_limits<Value>::max();
    10611071          for (int i = 0; i != _arc_num; ++i)
    1062             _cap[i] = val;
     1072            _cap[i] = max_cap;
    10631073        }
    10641074        if (_pcost) {
    … …  
    10741084      if (_plower) {
    10751085        for (int i = 0; i != _arc_num; ++i) {
    1076           Value c = (*_plower)[_arc_ref[i]];
     1086          Flow c = (*_plower)[_arc_ref[i]];
    10771087          if (c != 0) {
    10781088            _cap[i] -= c;
    … …  
    10841094
    10851095      // Add artificial arcs and initialize the spanning tree data structure
    1086       Value max_cap = std::numeric_limits<Value>::max();
    1087       Value max_cost = std::numeric_limits<Value>::max() / 4;
    10881096      for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
    10891097        _thread[u] = u + 1;
    … …  
    11381146      delta = _cap[in_arc];
    11391147      int result = 0;
    1140       Value d;
     1148      Flow d;
    11411149      int e;
    11421150
    … …  
    11761184      // Augment along the cycle
    11771185      if (delta > 0) {
    1178         Value val = _state[in_arc] * delta;
     1186        Flow val = _state[in_arc] * delta;
    11791187        _flow[in_arc] += val;
    11801188        for (int u = _source[in_arc]; u != join; u = _parent[u]) {
    … …  
    13171325    // Update potentials
    13181326    void updatePotential() {
    1319       Value sigma = _forward[u_in] ?
     1327      Cost sigma = _forward[u_in] ?
    13201328        _pi[v_in] - _pi[u_in] - _cost[_pred[u_in]] :
    13211329        _pi[v_in] - _pi[u_in] + _cost[_pred[u_in]];

  • test/min_cost_flow_test.cc

    r606 r607  
    7878
    7979// Check the interface of an MCF algorithm
    80 template <typename GR, typename Value>
     80template <typename GR, typename Flow, typename Cost>
    8181class McfClassConcept
    8282{
    … …  
    117117    typedef typename GR::Node Node;
    118118    typedef typename GR::Arc Arc;
    119     typedef concepts::ReadMap<Node, Value> NM;
    120     typedef concepts::ReadMap<Arc, Value> AM;
     119    typedef concepts::ReadMap<Node, Flow> NM;
     120    typedef concepts::ReadMap<Arc, Flow> FAM;
     121    typedef concepts::ReadMap<Arc, Cost> CAM;
    121122
    122123    const GR &g;
    123     const AM &lower;
    124     const AM &upper;
    125     const AM &cost;
     124    const FAM &lower;
     125    const FAM &upper;
     126    const CAM &cost;
    126127    const NM &sup;
    127128    const Node &n;
    128129    const Arc &a;
    129     const Value &k;
    130     Value v;
     130    const Flow &k;
     131    Flow v;
    131132    bool b;
    132133
    … …  
    207208  // Check the interfaces
    208209  {
    209     typedef int Value;
     210    typedef int Flow;
     211    typedef int Cost;
    210212    // TODO: This typedef should be enabled if the standard maps are
    211213    // reference maps in the graph concepts (See #190).
    … …  
    214216    typedef ListDigraph GR;
    215217/**/
    216     checkConcept< McfClassConcept<GR, Value>,
    217                   NetworkSimplex<GR, Value> >();
     218    checkConcept< McfClassConcept<GR, Flow, Cost>,
     219                  NetworkSimplex<GR, Flow, Cost> >();
    218220  }
    219221
Note: See TracChangeset for help on using the changeset viewer.