COIN-OR::LEMON - Graph Library

Changeset 2581:054566ac0934 in lemon-0.x for lemon/capacity_scaling.h


Ignore:
Timestamp:
02/28/08 03:54:27 (12 years ago)
Author:
Peter Kovacs
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3463
Message:

Query improvements in the min cost flow algorithms.

  • External flow and potential maps can be used.
  • New query functions: flow() and potential().
  • CycleCanceling? also provides dual solution (node potentials).
  • Doc improvements.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/capacity_scaling.h

    r2574 r2581  
    5151  /// - Edge capacities and costs should be \e non-negative \e integers.
    5252  /// - Supply values should be \e signed \e integers.
    53   /// - \c LowerMap::Value must be convertible to \c CapacityMap::Value.
    54   /// - \c CapacityMap::Value and \c SupplyMap::Value must be
    55   ///   convertible to each other.
    56   /// - All value types must be convertible to \c CostMap::Value, which
    57   ///   must be signed type.
     53  /// - The value types of the maps should be convertible to each other.
     54  /// - \c CostMap::Value must be signed type.
    5855  ///
    5956  /// \author Peter Kovacs
     
    121118    public:
    122119
    123       /// The constructor of the class.
     120      /// Constructor.
    124121      ResidualDijkstra( const Graph &graph,
    125122                        const FlowMap &flow,
     
    222219
    223220    // Edge map of the current flow
    224     FlowMap _flow;
     221    FlowMap *_flow;
     222    bool _local_flow;
    225223    // Node map of the current potentials
    226     PotentialMap _potential;
     224    PotentialMap *_potential;
     225    bool _local_potential;
    227226
    228227    // The residual capacity map
     
    244243    // Implementation of the Dijkstra algorithm for finding augmenting
    245244    // shortest paths in the residual network
    246     ResidualDijkstra _dijkstra;
    247 
    248   public :
    249 
    250     /// \brief General constructor of the class (with lower bounds).
    251     ///
    252     /// General constructor of the class (with lower bounds).
     245    ResidualDijkstra *_dijkstra;
     246
     247  public:
     248
     249    /// \brief General constructor (with lower bounds).
     250    ///
     251    /// General constructor (with lower bounds).
    253252    ///
    254253    /// \param graph The directed graph the algorithm runs on.
     
    263262                     const SupplyMap &supply ) :
    264263      _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
    265       _supply(graph), _flow(graph, 0), _potential(graph, 0),
    266       _res_cap(graph), _excess(graph), _pred(graph),
    267       _dijkstra(_graph, _flow, _res_cap, _cost, _excess, _potential, _pred)
     264      _supply(graph), _flow(0), _local_flow(false),
     265      _potential(0), _local_potential(false),
     266      _res_cap(graph), _excess(graph), _pred(graph)
    268267    {
    269268      // Removing non-zero lower bounds
     
    283282    }
    284283
    285     /// \brief General constructor of the class (without lower bounds).
    286     ///
    287     /// General constructor of the class (without lower bounds).
     284    /// \brief General constructor (without lower bounds).
     285    ///
     286    /// General constructor (without lower bounds).
    288287    ///
    289288    /// \param graph The directed graph the algorithm runs on.
     
    296295                     const SupplyMap &supply ) :
    297296      _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost),
    298       _supply(supply), _flow(graph, 0), _potential(graph, 0),
    299       _res_cap(capacity), _excess(graph), _pred(graph),
    300       _dijkstra(_graph, _flow, _res_cap, _cost, _excess, _potential, _pred)
     297      _supply(supply), _flow(0), _local_flow(false),
     298      _potential(0), _local_potential(false),
     299      _res_cap(capacity), _excess(graph), _pred(graph)
    301300    {
    302301      // Checking the sum of supply values
     
    306305    }
    307306
    308     /// \brief Simple constructor of the class (with lower bounds).
    309     ///
    310     /// Simple constructor of the class (with lower bounds).
     307    /// \brief Simple constructor (with lower bounds).
     308    ///
     309    /// Simple constructor (with lower bounds).
    311310    ///
    312311    /// \param graph The directed graph the algorithm runs on.
     
    325324                     Supply flow_value ) :
    326325      _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
    327       _supply(graph), _flow(graph, 0), _potential(graph, 0),
    328       _res_cap(graph), _excess(graph), _pred(graph),
    329       _dijkstra(_graph, _flow, _res_cap, _cost, _excess, _potential, _pred)
     326      _supply(graph), _flow(0), _local_flow(false),
     327      _potential(0), _local_potential(false),
     328      _res_cap(graph), _excess(graph), _pred(graph)
    330329    {
    331330      // Removing non-zero lower bounds
     
    345344    }
    346345
    347     /// \brief Simple constructor of the class (without lower bounds).
    348     ///
    349     /// Simple constructor of the class (without lower bounds).
     346    /// \brief Simple constructor (without lower bounds).
     347    ///
     348    /// Simple constructor (without lower bounds).
    350349    ///
    351350    /// \param graph The directed graph the algorithm runs on.
     
    362361                     Supply flow_value ) :
    363362      _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost),
    364       _supply(graph, 0), _flow(graph, 0), _potential(graph, 0),
    365       _res_cap(capacity), _excess(graph), _pred(graph),
    366       _dijkstra(_graph, _flow, _res_cap, _cost, _excess, _potential, _pred)
     363      _supply(graph, 0), _flow(0), _local_flow(false),
     364      _potential(0), _local_potential(false),
     365      _res_cap(capacity), _excess(graph), _pred(graph)
    367366    {
    368367      _supply[s] =  flow_value;
     
    371370    }
    372371
     372    /// Destructor.
     373    ~CapacityScaling() {
     374      if (_local_flow) delete _flow;
     375      if (_local_potential) delete _potential;
     376      delete _dijkstra;
     377    }
     378
     379    /// \brief Sets the flow map.
     380    ///
     381    /// Sets the flow map.
     382    ///
     383    /// \return \c (*this)
     384    CapacityScaling& flowMap(FlowMap &map) {
     385      if (_local_flow) {
     386        delete _flow;
     387        _local_flow = false;
     388      }
     389      _flow = ↦
     390      return *this;
     391    }
     392
     393    /// \brief Sets the potential map.
     394    ///
     395    /// Sets the potential map.
     396    ///
     397    /// \return \c (*this)
     398    CapacityScaling& potentialMap(PotentialMap &map) {
     399      if (_local_potential) {
     400        delete _potential;
     401        _local_potential = false;
     402      }
     403      _potential = ↦
     404      return *this;
     405    }
     406
     407    /// \name Execution control
     408    /// The only way to execute the algorithm is to call the run()
     409    /// function.
     410
     411    /// @{
     412
    373413    /// \brief Runs the algorithm.
    374414    ///
     
    385425    }
    386426
     427    /// @}
     428
     429    /// \name Query Functions
     430    /// The result of the algorithm can be obtained using these
     431    /// functions.
     432    /// \n run() must be called before using them.
     433
     434    /// @{
     435
    387436    /// \brief Returns a const reference to the edge map storing the
    388437    /// found flow.
     
    392441    /// \pre \ref run() must be called before using this function.
    393442    const FlowMap& flowMap() const {
    394       return _flow;
     443      return *_flow;
    395444    }
    396445
     
    403452    /// \pre \ref run() must be called before using this function.
    404453    const PotentialMap& potentialMap() const {
    405       return _potential;
     454      return *_potential;
     455    }
     456
     457    /// \brief Returns the flow on the edge.
     458    ///
     459    /// Returns the flow on the edge.
     460    ///
     461    /// \pre \ref run() must be called before using this function.
     462    Capacity flow(const Edge& edge) const {
     463      return (*_flow)[edge];
     464    }
     465
     466    /// \brief Returns the potential of the node.
     467    ///
     468    /// Returns the potential of the node.
     469    ///
     470    /// \pre \ref run() must be called before using this function.
     471    Cost potential(const Node& node) const {
     472      return (*_potential)[node];
    406473    }
    407474
     
    415482      Cost c = 0;
    416483      for (EdgeIt e(_graph); e != INVALID; ++e)
    417         c += _flow[e] * _cost[e];
     484        c += (*_flow)[e] * _cost[e];
    418485      return c;
    419486    }
     487
     488    /// @}
    420489
    421490  private:
     
    424493    bool init(bool scaling) {
    425494      if (!_valid_supply) return false;
     495
     496      // Initializing maps
     497      if (!_flow) {
     498        _flow = new FlowMap(_graph);
     499        _local_flow = true;
     500      }
     501      if (!_potential) {
     502        _potential = new PotentialMap(_graph);
     503        _local_potential = true;
     504      }
     505      for (EdgeIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;
     506      for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;
    426507      _excess = _supply;
    427508
    428       // Initilaizing delta value
     509      _dijkstra = new ResidualDijkstra( _graph, *_flow, _res_cap, _cost,
     510                                        _excess, *_potential, _pred );
     511
     512      // Initializing delta value
    429513      if (scaling) {
    430514        // With scaling
     
    442526        _delta = 1;
    443527      }
     528
    444529      return true;
    445530    }
     
    462547        for (EdgeIt e(_graph); e != INVALID; ++e) {
    463548          Node u = _graph.source(e), v = _graph.target(e);
    464           Cost c = _cost[e] + _potential[u] - _potential[v];
     549          Cost c = _cost[e] + (*_potential)[u] - (*_potential)[v];
    465550          if (c < 0 && _res_cap[e] >= _delta) {
    466551            _excess[u] -= _res_cap[e];
    467552            _excess[v] += _res_cap[e];
    468             _flow[e] = _capacity[e];
     553            (*_flow)[e] = _capacity[e];
    469554            _res_cap[e] = 0;
    470555          }
    471           else if (c > 0 && _flow[e] >= _delta) {
    472             _excess[u] += _flow[e];
    473             _excess[v] -= _flow[e];
    474             _flow[e] = 0;
     556          else if (c > 0 && (*_flow)[e] >= _delta) {
     557            _excess[u] += (*_flow)[e];
     558            _excess[v] -= (*_flow)[e];
     559            (*_flow)[e] = 0;
    475560            _res_cap[e] = _capacity[e];
    476561          }
     
    502587          // Running Dijkstra
    503588          s = _excess_nodes[next_node];
    504           if ((t = _dijkstra.run(s, _delta)) == INVALID) {
     589          if ((t = _dijkstra->run(s, _delta)) == INVALID) {
    505590            if (_delta > 1) {
    506591              ++next_node;
     
    521606                u = _graph.source(e);
    522607              } else {
    523                 rc = _flow[e];
     608                rc = (*_flow)[e];
    524609                u = _graph.target(e);
    525610              }
     
    530615          while ((e = _pred[u]) != INVALID) {
    531616            if (u == _graph.target(e)) {
    532               _flow[e] += d;
     617              (*_flow)[e] += d;
    533618              _res_cap[e] -= d;
    534619              u = _graph.source(e);
    535620            } else {
    536               _flow[e] -= d;
     621              (*_flow)[e] -= d;
    537622              _res_cap[e] += d;
    538623              u = _graph.target(e);
     
    553638      if (_lower) {
    554639        for (EdgeIt e(_graph); e != INVALID; ++e)
    555           _flow[e] += (*_lower)[e];
     640          (*_flow)[e] += (*_lower)[e];
    556641      }
    557642      return true;
     
    573658        // Running Dijkstra
    574659        s = _excess_nodes[next_node];
    575         if ((t = _dijkstra.run(s, 1)) == INVALID)
     660        if ((t = _dijkstra->run(s, 1)) == INVALID)
    576661          return false;
    577662
     
    586671            u = _graph.source(e);
    587672          } else {
    588             rc = _flow[e];
     673            rc = (*_flow)[e];
    589674            u = _graph.target(e);
    590675          }
     
    594679        while ((e = _pred[u]) != INVALID) {
    595680          if (u == _graph.target(e)) {
    596             _flow[e] += d;
     681            (*_flow)[e] += d;
    597682            _res_cap[e] -= d;
    598683            u = _graph.source(e);
    599684          } else {
    600             _flow[e] -= d;
     685            (*_flow)[e] -= d;
    601686            _res_cap[e] += d;
    602687            u = _graph.target(e);
     
    610695      if (_lower) {
    611696        for (EdgeIt e(_graph); e != INVALID; ++e)
    612           _flow[e] += (*_lower)[e];
     697          (*_flow)[e] += (*_lower)[e];
    613698      }
    614699      return true;
Note: See TracChangeset for help on using the changeset viewer.