COIN-OR::LEMON - Graph Library

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


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.
Location:
lemon
Files:
5 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;
  • lemon/cost_scaling.h

    r2577 r2581  
    5555  /// - Edge capacities and costs should be \e non-negative \e integers.
    5656  /// - Supply values should be \e signed \e integers.
    57   /// - \c LowerMap::Value must be convertible to \c CapacityMap::Value.
    58   /// - \c CapacityMap::Value and \c SupplyMap::Value must be
    59   ///   convertible to each other.
    60   /// - All value types must be convertible to \c CostMap::Value, which
    61   ///   must be signed type.
     57  /// - The value types of the maps should be convertible to each other.
     58  /// - \c CostMap::Value must be signed type.
    6259  ///
    6360  /// \note Edge costs are multiplied with the number of nodes during
     
    9895
    9996    /// The type of the flow map.
    100     typedef CapacityEdgeMap FlowMap;
     97    typedef typename Graph::template EdgeMap<Capacity> FlowMap;
    10198    /// The type of the potential map.
    10299    typedef typename Graph::template NodeMap<LCost> PotentialMap;
     
    108105    /// \ref ResidualCostMap is a map adaptor class for handling
    109106    /// residual edge costs.
    110     class ResidualCostMap : public MapBase<ResEdge, LCost>
     107    template <typename Map>
     108    class ResidualCostMap : public MapBase<ResEdge, typename Map::Value>
    111109    {
    112110    private:
    113111
    114       const LargeCostMap &_cost_map;
     112      const Map &_cost_map;
    115113
    116114    public:
    117115
    118116      ///\e
    119       ResidualCostMap(const LargeCostMap &cost_map) :
     117      ResidualCostMap(const Map &cost_map) :
    120118        _cost_map(cost_map) {}
    121119
    122120      ///\e
    123       LCost operator[](const ResEdge &e) const {
     121      typename Map::Value operator[](const ResEdge &e) const {
    124122        return ResGraph::forward(e) ?  _cost_map[e] : -_cost_map[e];
    125123      }
     
    161159
    162160    // Paramters for heuristics
    163     static const int BF_HEURISTIC_EPSILON_BOUND    = 5000;
    164     static const int BF_HEURISTIC_BOUND_FACTOR = 3;
     161    static const int BF_HEURISTIC_EPSILON_BOUND = 5000;
     162    static const int BF_HEURISTIC_BOUND_FACTOR  = 3;
    165163
    166164  private:
     
    181179
    182180    // Edge map of the current flow
    183     FlowMap _flow;
     181    FlowMap *_flow;
     182    bool _local_flow;
    184183    // Node map of the current potentials
    185     PotentialMap _potential;
     184    PotentialMap *_potential;
     185    bool _local_potential;
    186186
    187187    // The residual graph
    188     ResGraph _res_graph;
     188    ResGraph *_res_graph;
    189189    // The residual cost map
    190     ResidualCostMap _res_cost;
     190    ResidualCostMap<LargeCostMap> _res_cost;
    191191    // The reduced cost map
    192     ReducedCostMap _red_cost;
     192    ReducedCostMap *_red_cost;
    193193    // The excess map
    194194    SupplyNodeMap _excess;
     
    198198  public:
    199199
    200     /// \brief General constructor of the class (with lower bounds).
    201     ///
    202     /// General constructor of the class (with lower bounds).
     200    /// \brief General constructor (with lower bounds).
     201    ///
     202    /// General constructor (with lower bounds).
    203203    ///
    204204    /// \param graph The directed graph the algorithm runs on.
     
    213213                 const SupplyMap &supply ) :
    214214      _graph(graph), _lower(&lower), _capacity(graph), _orig_cost(cost),
    215       _cost(graph), _supply(graph), _flow(graph, 0), _potential(graph, 0),
    216       _res_graph(graph, _capacity, _flow), _res_cost(_cost),
    217       _red_cost(graph, _cost, _potential), _excess(graph, 0)
     215      _cost(graph), _supply(graph), _flow(0), _local_flow(false),
     216      _potential(0), _local_potential(false), _res_cost(_cost),
     217      _excess(graph, 0)
    218218    {
    219219      // Removing non-zero lower bounds
     
    232232    }
    233233
    234     /// \brief General constructor of the class (without lower bounds).
    235     ///
    236     /// General constructor of the class (without lower bounds).
     234    /// \brief General constructor (without lower bounds).
     235    ///
     236    /// General constructor (without lower bounds).
    237237    ///
    238238    /// \param graph The directed graph the algorithm runs on.
     
    245245                 const SupplyMap &supply ) :
    246246      _graph(graph), _lower(NULL), _capacity(capacity), _orig_cost(cost),
    247       _cost(graph), _supply(supply), _flow(graph, 0), _potential(graph, 0),
    248       _res_graph(graph, _capacity, _flow), _res_cost(_cost),
    249       _red_cost(graph, _cost, _potential), _excess(graph, 0)
     247      _cost(graph), _supply(supply), _flow(0), _local_flow(false),
     248      _potential(0), _local_potential(false), _res_cost(_cost),
     249      _excess(graph, 0)
    250250    {
    251251      // Checking the sum of supply values
     
    255255    }
    256256
    257     /// \brief Simple constructor of the class (with lower bounds).
    258     ///
    259     /// Simple constructor of the class (with lower bounds).
     257    /// \brief Simple constructor (with lower bounds).
     258    ///
     259    /// Simple constructor (with lower bounds).
    260260    ///
    261261    /// \param graph The directed graph the algorithm runs on.
     
    274274                 Supply flow_value ) :
    275275      _graph(graph), _lower(&lower), _capacity(graph), _orig_cost(cost),
    276       _cost(graph), _supply(graph), _flow(graph, 0), _potential(graph, 0),
    277       _res_graph(graph, _capacity, _flow), _res_cost(_cost),
    278       _red_cost(graph, _cost, _potential), _excess(graph, 0)
     276      _cost(graph), _supply(graph), _flow(0), _local_flow(false),
     277      _potential(0), _local_potential(false), _res_cost(_cost),
     278      _excess(graph, 0)
    279279    {
    280280      // Removing nonzero lower bounds
     
    293293    }
    294294
    295     /// \brief Simple constructor of the class (without lower bounds).
    296     ///
    297     /// Simple constructor of the class (without lower bounds).
     295    /// \brief Simple constructor (without lower bounds).
     296    ///
     297    /// Simple constructor (without lower bounds).
    298298    ///
    299299    /// \param graph The directed graph the algorithm runs on.
     
    310310                 Supply flow_value ) :
    311311      _graph(graph), _lower(NULL), _capacity(capacity), _orig_cost(cost),
    312       _cost(graph), _supply(graph, 0), _flow(graph, 0), _potential(graph, 0),
    313       _res_graph(graph, _capacity, _flow), _res_cost(_cost),
    314       _red_cost(graph, _cost, _potential), _excess(graph, 0)
     312      _cost(graph), _supply(graph, 0), _flow(0), _local_flow(false),
     313      _potential(0), _local_potential(false), _res_cost(_cost),
     314      _excess(graph, 0)
    315315    {
    316316      _supply[s] =  flow_value;
     
    319319    }
    320320
     321    /// Destructor.
     322    ~CostScaling() {
     323      if (_local_flow) delete _flow;
     324      if (_local_potential) delete _potential;
     325      delete _res_graph;
     326      delete _red_cost;
     327    }
     328
     329    /// \brief Sets the flow map.
     330    ///
     331    /// Sets the flow map.
     332    ///
     333    /// \return \c (*this)
     334    CostScaling& flowMap(FlowMap &map) {
     335      if (_local_flow) {
     336        delete _flow;
     337        _local_flow = false;
     338      }
     339      _flow = &map;
     340      return *this;
     341    }
     342
     343    /// \brief Sets the potential map.
     344    ///
     345    /// Sets the potential map.
     346    ///
     347    /// \return \c (*this)
     348    CostScaling& potentialMap(PotentialMap &map) {
     349      if (_local_potential) {
     350        delete _potential;
     351        _local_potential = false;
     352      }
     353      _potential = &map;
     354      return *this;
     355    }
     356
     357    /// \name Execution control
     358    /// The only way to execute the algorithm is to call the run()
     359    /// function.
     360
     361    /// @{
     362
    321363    /// \brief Runs the algorithm.
    322364    ///
     
    325367    /// \return \c true if a feasible flow can be found.
    326368    bool run() {
    327       init() && start();
    328     }
     369      return init() && start();
     370    }
     371
     372    /// @}
     373
     374    /// \name Query Functions
     375    /// The result of the algorithm can be obtained using these
     376    /// functions.
     377    /// \n run() must be called before using them.
     378
     379    /// @{
    329380
    330381    /// \brief Returns a const reference to the edge map storing the
     
    335386    /// \pre \ref run() must be called before using this function.
    336387    const FlowMap& flowMap() const {
    337       return _flow;
     388      return *_flow;
    338389    }
    339390
     
    346397    /// \pre \ref run() must be called before using this function.
    347398    const PotentialMap& potentialMap() const {
    348       return _potential;
     399      return *_potential;
     400    }
     401
     402    /// \brief Returns the flow on the edge.
     403    ///
     404    /// Returns the flow on the edge.
     405    ///
     406    /// \pre \ref run() must be called before using this function.
     407    Capacity flow(const Edge& edge) const {
     408      return (*_flow)[edge];
     409    }
     410
     411    /// \brief Returns the potential of the node.
     412    ///
     413    /// Returns the potential of the node.
     414    ///
     415    /// \pre \ref run() must be called before using this function.
     416    Cost potential(const Node& node) const {
     417      return (*_potential)[node];
    349418    }
    350419
     
    358427      Cost c = 0;
    359428      for (EdgeIt e(_graph); e != INVALID; ++e)
    360         c += _flow[e] * _orig_cost[e];
     429        c += (*_flow)[e] * _orig_cost[e];
    361430      return c;
    362431    }
     432
     433    /// @}
    363434
    364435  private:
     
    367438    bool init() {
    368439      if (!_valid_supply) return false;
     440
     441      // Initializing flow and potential maps
     442      if (!_flow) {
     443        _flow = new FlowMap(_graph);
     444        _local_flow = true;
     445      }
     446      if (!_potential) {
     447        _potential = new PotentialMap(_graph);
     448        _local_potential = true;
     449      }
     450
     451      _red_cost = new ReducedCostMap(_graph, _cost, *_potential);
     452      _res_graph = new ResGraph(_graph, _capacity, *_flow);
    369453
    370454      // Initializing the scaled cost map and the epsilon parameter
     
    380464      Circulation< Graph, ConstMap<Edge, Capacity>, CapacityEdgeMap,
    381465                   SupplyMap >
    382         circulation( _graph, constMap<Edge>((Capacity)0), _capacity,
     466        circulation( _graph, constMap<Edge>(Capacity(0)), _capacity,
    383467                     _supply );
    384       return circulation.flowMap(_flow).run();
     468      return circulation.flowMap(*_flow).run();
    385469    }
    386470
     
    398482        // algorithm
    399483        if (_epsilon <= BF_HEURISTIC_EPSILON_BOUND) {
    400           typedef ShiftMap<ResidualCostMap> ShiftCostMap;
     484          typedef ShiftMap< ResidualCostMap<LargeCostMap> > ShiftCostMap;
    401485          ShiftCostMap shift_cost(_res_cost, _epsilon);
    402           BellmanFord<ResGraph, ShiftCostMap> bf(_res_graph, shift_cost);
     486          BellmanFord<ResGraph, ShiftCostMap> bf(*_res_graph, shift_cost);
    403487          bf.init(0);
    404488          bool done = false;
     
    408492          if (done) {
    409493            for (NodeIt n(_graph); n != INVALID; ++n)
    410               _potential[n] = bf.dist(n);
     494              (*_potential)[n] = bf.dist(n);
    411495            continue;
    412496          }
     
    416500        Capacity delta;
    417501        for (EdgeIt e(_graph); e != INVALID; ++e) {
    418           if (_capacity[e] - _flow[e] > 0 && _red_cost[e] < 0) {
    419             delta = _capacity[e] - _flow[e];
     502          if (_capacity[e] - (*_flow)[e] > 0 && (*_red_cost)[e] < 0) {
     503            delta = _capacity[e] - (*_flow)[e];
    420504            _excess[_graph.source(e)] -= delta;
    421505            _excess[_graph.target(e)] += delta;
    422             _flow[e] = _capacity[e];
     506            (*_flow)[e] = _capacity[e];
    423507          }
    424           if (_flow[e] > 0 && -_red_cost[e] < 0) {
    425             _excess[_graph.target(e)] -= _flow[e];
    426             _excess[_graph.source(e)] += _flow[e];
    427             _flow[e] = 0;
     508          if ((*_flow)[e] > 0 && -(*_red_cost)[e] < 0) {
     509            _excess[_graph.target(e)] -= (*_flow)[e];
     510            _excess[_graph.source(e)] += (*_flow)[e];
     511            (*_flow)[e] = 0;
    428512          }
    429513        }
     
    441525          if (_excess[n] > 0) {
    442526            for (OutEdgeIt e(_graph, n); e != INVALID; ++e) {
    443               if (_capacity[e] - _flow[e] > 0 && _red_cost[e] < 0) {
    444                 delta = _capacity[e] - _flow[e] <= _excess[n] ?
    445                         _capacity[e] - _flow[e] : _excess[n];
     527              if (_capacity[e] - (*_flow)[e] > 0 && (*_red_cost)[e] < 0) {
     528                delta = _capacity[e] - (*_flow)[e] <= _excess[n] ?
     529                        _capacity[e] - (*_flow)[e] : _excess[n];
    446530                t = _graph.target(e);
    447531
     
    449533                Capacity ahead = -_excess[t];
    450534                for (OutEdgeIt oe(_graph, t); oe != INVALID; ++oe) {
    451                   if (_capacity[oe] - _flow[oe] > 0 && _red_cost[oe] < 0)
    452                     ahead += _capacity[oe] - _flow[oe];
     535                  if (_capacity[oe] - (*_flow)[oe] > 0 && (*_red_cost)[oe] < 0)
     536                    ahead += _capacity[oe] - (*_flow)[oe];
    453537                }
    454538                for (InEdgeIt ie(_graph, t); ie != INVALID; ++ie) {
    455                   if (_flow[ie] > 0 && -_red_cost[ie] < 0)
    456                     ahead += _flow[ie];
     539                  if ((*_flow)[ie] > 0 && -(*_red_cost)[ie] < 0)
     540                    ahead += (*_flow)[ie];
    457541                }
    458542                if (ahead < 0) ahead = 0;
     
    460544                // Pushing flow along the edge
    461545                if (ahead < delta) {
    462                   _flow[e] += ahead;
     546                  (*_flow)[e] += ahead;
    463547                  _excess[n] -= ahead;
    464548                  _excess[t] += ahead;
     
    468552                  break;
    469553                } else {
    470                   _flow[e] += delta;
     554                  (*_flow)[e] += delta;
    471555                  _excess[n] -= delta;
    472556                  _excess[t] += delta;
     
    482566          if (_excess[n] > 0) {
    483567            for (InEdgeIt e(_graph, n); e != INVALID; ++e) {
    484               if (_flow[e] > 0 && -_red_cost[e] < 0) {
    485                 delta = _flow[e] <= _excess[n] ? _flow[e] : _excess[n];
     568              if ((*_flow)[e] > 0 && -(*_red_cost)[e] < 0) {
     569                delta = (*_flow)[e] <= _excess[n] ? (*_flow)[e] : _excess[n];
    486570                t = _graph.source(e);
    487571
     
    489573                Capacity ahead = -_excess[t];
    490574                for (OutEdgeIt oe(_graph, t); oe != INVALID; ++oe) {
    491                   if (_capacity[oe] - _flow[oe] > 0 && _red_cost[oe] < 0)
    492                     ahead += _capacity[oe] - _flow[oe];
     575                  if (_capacity[oe] - (*_flow)[oe] > 0 && (*_red_cost)[oe] < 0)
     576                    ahead += _capacity[oe] - (*_flow)[oe];
    493577                }
    494578                for (InEdgeIt ie(_graph, t); ie != INVALID; ++ie) {
    495                   if (_flow[ie] > 0 && -_red_cost[ie] < 0)
    496                     ahead += _flow[ie];
     579                  if ((*_flow)[ie] > 0 && -(*_red_cost)[ie] < 0)
     580                    ahead += (*_flow)[ie];
    497581                }
    498582                if (ahead < 0) ahead = 0;
     
    500584                // Pushing flow along the edge
    501585                if (ahead < delta) {
    502                   _flow[e] -= ahead;
     586                  (*_flow)[e] -= ahead;
    503587                  _excess[n] -= ahead;
    504588                  _excess[t] += ahead;
     
    508592                  break;
    509593                } else {
    510                   _flow[e] -= delta;
     594                  (*_flow)[e] -= delta;
    511595                  _excess[n] -= delta;
    512596                  _excess[t] += delta;
     
    524608            LCost min_red_cost = std::numeric_limits<LCost>::max();
    525609            for (OutEdgeIt oe(_graph, n); oe != INVALID; ++oe) {
    526               if ( _capacity[oe] - _flow[oe] > 0 &&
    527                    _red_cost[oe] < min_red_cost )
    528                 min_red_cost = _red_cost[oe];
     610              if ( _capacity[oe] - (*_flow)[oe] > 0 &&
     611                   (*_red_cost)[oe] < min_red_cost )
     612                min_red_cost = (*_red_cost)[oe];
    529613            }
    530614            for (InEdgeIt ie(_graph, n); ie != INVALID; ++ie) {
    531               if (_flow[ie] > 0 && -_red_cost[ie] < min_red_cost)
    532                 min_red_cost = -_red_cost[ie];
     615              if ((*_flow)[ie] > 0 && -(*_red_cost)[ie] < min_red_cost)
     616                min_red_cost = -(*_red_cost)[ie];
    533617            }
    534             _potential[n] -= min_red_cost + _epsilon;
     618            (*_potential)[n] -= min_red_cost + _epsilon;
    535619            hyper[n] = false;
    536620          }
     
    545629      }
    546630
     631      // Computing node potentials for the original costs
     632      ResidualCostMap<CostMap> res_cost(_orig_cost);
     633      BellmanFord< ResGraph, ResidualCostMap<CostMap> >
     634        bf(*_res_graph, res_cost);
     635      bf.init(0); bf.start();
     636      for (NodeIt n(_graph); n != INVALID; ++n)
     637        (*_potential)[n] = bf.dist(n);
     638
    547639      // Handling non-zero lower bounds
    548640      if (_lower) {
    549641        for (EdgeIt e(_graph); e != INVALID; ++e)
    550           _flow[e] += (*_lower)[e];
     642          (*_flow)[e] += (*_lower)[e];
    551643      }
    552644      return true;
  • lemon/cycle_canceling.h

    r2573 r2581  
    5353  /// - Edge capacities and costs should be \e non-negative \e integers.
    5454  /// - Supply values should be \e signed \e integers.
    55   /// - \c LowerMap::Value must be convertible to \c CapacityMap::Value.
    56   /// - \c CapacityMap::Value and \c SupplyMap::Value must be
    57   ///   convertible to each other.
    58   /// - All value types must be convertible to \c CostMap::Value, which
    59   ///   must be signed type.
     55  /// - The value types of the maps should be convertible to each other.
     56  /// - \c CostMap::Value must be signed type.
    6057  ///
    6158  /// \note By default the \ref BellmanFord "Bellman-Ford" algorithm is
     
    9592    /// The type of the flow map.
    9693    typedef typename Graph::template EdgeMap<Capacity> FlowMap;
     94    /// The type of the potential map.
     95    typedef typename Graph::template NodeMap<Cost> PotentialMap;
    9796
    9897  private:
     
    144143
    145144    // Edge map of the current flow
    146     FlowMap _flow;
     145    FlowMap *_flow;
     146    bool _local_flow;
     147    // Node map of the current potentials
     148    PotentialMap *_potential;
     149    bool _local_potential;
    147150
    148151    // The residual graph
    149     ResGraph _res_graph;
     152    ResGraph *_res_graph;
    150153    // The residual cost map
    151154    ResidualCostMap _res_cost;
     
    153156  public:
    154157
    155     /// \brief General constructor of the class (with lower bounds).
    156     ///
    157     /// General constructor of the class (with lower bounds).
     158    /// \brief General constructor (with lower bounds).
     159    ///
     160    /// General constructor (with lower bounds).
    158161    ///
    159162    /// \param graph The directed graph the algorithm runs on.
     
    168171                    const SupplyMap &supply ) :
    169172      _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
    170       _supply(graph), _flow(graph, 0),
    171       _res_graph(graph, _capacity, _flow), _res_cost(_cost)
     173      _supply(graph), _flow(0), _local_flow(false),
     174      _potential(0), _local_potential(false), _res_cost(_cost)
    172175    {
    173176      // Removing non-zero lower bounds
     
    185188    }
    186189
    187     /// \brief General constructor of the class (without lower bounds).
    188     ///
    189     /// General constructor of the class (without lower bounds).
     190    /// \brief General constructor (without lower bounds).
     191    ///
     192    /// General constructor (without lower bounds).
    190193    ///
    191194    /// \param graph The directed graph the algorithm runs on.
     
    198201                    const SupplyMap &supply ) :
    199202      _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost),
    200       _supply(supply), _flow(graph, 0),
    201       _res_graph(graph, _capacity, _flow), _res_cost(_cost)
     203      _supply(supply), _flow(0), _local_flow(false),
     204      _potential(0), _local_potential(false), _res_cost(_cost)
    202205    {
    203206      // Checking the sum of supply values
     
    207210    }
    208211
    209     /// \brief Simple constructor of the class (with lower bounds).
    210     ///
    211     /// Simple constructor of the class (with lower bounds).
     212    /// \brief Simple constructor (with lower bounds).
     213    ///
     214    /// Simple constructor (with lower bounds).
    212215    ///
    213216    /// \param graph The directed graph the algorithm runs on.
     
    226229                    Supply flow_value ) :
    227230      _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
    228       _supply(graph), _flow(graph, 0),
    229       _res_graph(graph, _capacity, _flow), _res_cost(_cost)
     231      _supply(graph), _flow(0), _local_flow(false),
     232      _potential(0), _local_potential(false), _res_cost(_cost)
    230233    {
    231234      // Removing non-zero lower bounds
     
    244247    }
    245248
    246     /// \brief Simple constructor of the class (without lower bounds).
    247     ///
    248     /// Simple constructor of the class (without lower bounds).
     249    /// \brief Simple constructor (without lower bounds).
     250    ///
     251    /// Simple constructor (without lower bounds).
    249252    ///
    250253    /// \param graph The directed graph the algorithm runs on.
     
    261264                    Supply flow_value ) :
    262265      _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost),
    263       _supply(graph, 0), _flow(graph, 0),
    264       _res_graph(graph, _capacity, _flow), _res_cost(_cost)
     266      _supply(graph, 0), _flow(0), _local_flow(false),
     267      _potential(0), _local_potential(false), _res_cost(_cost)
    265268    {
    266269      _supply[s] =  flow_value;
     
    269272    }
    270273
     274    /// Destructor.
     275    ~CycleCanceling() {
     276      if (_local_flow) delete _flow;
     277      if (_local_potential) delete _potential;
     278      delete _res_graph;
     279    }
     280
     281    /// \brief Sets the flow map.
     282    ///
     283    /// Sets the flow map.
     284    ///
     285    /// \return \c (*this)
     286    CycleCanceling& flowMap(FlowMap &map) {
     287      if (_local_flow) {
     288        delete _flow;
     289        _local_flow = false;
     290      }
     291      _flow = &map;
     292      return *this;
     293    }
     294
     295    /// \brief Sets the potential map.
     296    ///
     297    /// Sets the potential map.
     298    ///
     299    /// \return \c (*this)
     300    CycleCanceling& potentialMap(PotentialMap &map) {
     301      if (_local_potential) {
     302        delete _potential;
     303        _local_potential = false;
     304      }
     305      _potential = &map;
     306      return *this;
     307    }
     308
     309    /// \name Execution control
     310    /// The only way to execute the algorithm is to call the run()
     311    /// function.
     312
     313    /// @{
     314
    271315    /// \brief Runs the algorithm.
    272316    ///
     
    282326    }
    283327
     328    /// @}
     329
     330    /// \name Query Functions
     331    /// The result of the algorithm can be obtained using these
     332    /// functions.
     333    /// \n run() must be called before using them.
     334
     335    /// @{
     336
    284337    /// \brief Returns a const reference to the edge map storing the
    285338    /// found flow.
     
    289342    /// \pre \ref run() must be called before using this function.
    290343    const FlowMap& flowMap() const {
    291       return _flow;
     344      return *_flow;
     345    }
     346
     347    /// \brief Returns a const reference to the node map storing the
     348    /// found potentials (the dual solution).
     349    ///
     350    /// Returns a const reference to the node map storing the found
     351    /// potentials (the dual solution).
     352    ///
     353    /// \pre \ref run() must be called before using this function.
     354    const PotentialMap& potentialMap() const {
     355      return *_potential;
     356    }
     357
     358    /// \brief Returns the flow on the edge.
     359    ///
     360    /// Returns the flow on the edge.
     361    ///
     362    /// \pre \ref run() must be called before using this function.
     363    Capacity flow(const Edge& edge) const {
     364      return (*_flow)[edge];
     365    }
     366
     367    /// \brief Returns the potential of the node.
     368    ///
     369    /// Returns the potential of the node.
     370    ///
     371    /// \pre \ref run() must be called before using this function.
     372    Cost potential(const Node& node) const {
     373      return (*_potential)[node];
    292374    }
    293375
     
    301383      Cost c = 0;
    302384      for (EdgeIt e(_graph); e != INVALID; ++e)
    303         c += _flow[e] * _cost[e];
     385        c += (*_flow)[e] * _cost[e];
    304386      return c;
    305387    }
     388
     389    /// @}
    306390
    307391  private:
     
    311395      if (!_valid_supply) return false;
    312396
     397      // Initializing flow and potential maps
     398      if (!_flow) {
     399        _flow = new FlowMap(_graph);
     400        _local_flow = true;
     401      }
     402      if (!_potential) {
     403        _potential = new PotentialMap(_graph);
     404        _local_potential = true;
     405      }
     406
     407      _res_graph = new ResGraph(_graph, _capacity, *_flow);
     408
    313409      // Finding a feasible flow using Circulation
    314410      Circulation< Graph, ConstMap<Edge, Capacity>, CapacityEdgeMap,
    315411                   SupplyMap >
    316         circulation( _graph, constMap<Edge>((Capacity)0), _capacity,
     412        circulation( _graph, constMap<Edge>(Capacity(0)), _capacity,
    317413                     _supply );
    318       return circulation.flowMap(_flow).run();
     414      return circulation.flowMap(*_flow).run();
    319415    }
    320416
    321417    bool start(bool min_mean_cc) {
    322418      if (min_mean_cc)
    323         return startMinMean();
     419        startMinMean();
    324420      else
    325         return start();
     421        start();
     422
     423      // Handling non-zero lower bounds
     424      if (_lower) {
     425        for (EdgeIt e(_graph); e != INVALID; ++e)
     426          (*_flow)[e] += (*_lower)[e];
     427      }
     428      return true;
    326429    }
    327430
     
    331434    /// "Bellman-Ford" algorithm for negative cycle detection with
    332435    /// successively larger limit for the number of iterations.
    333     bool start() {
    334       typename BellmanFord<ResGraph, ResidualCostMap>::PredMap pred(_res_graph);
    335       typename ResGraph::template NodeMap<int> visited(_res_graph);
     436    void start() {
     437      typename BellmanFord<ResGraph, ResidualCostMap>::PredMap pred(*_res_graph);
     438      typename ResGraph::template NodeMap<int> visited(*_res_graph);
    336439      std::vector<ResEdge> cycle;
    337440      int node_num = countNodes(_graph);
     
    340443      bool optimal = false;
    341444      while (!optimal) {
    342         BellmanFord<ResGraph, ResidualCostMap> bf(_res_graph, _res_cost);
     445        BellmanFord<ResGraph, ResidualCostMap> bf(*_res_graph, _res_cost);
    343446        bf.predMap(pred);
    344447        bf.init(0);
     
    357460          }
    358461          if (real_iter_num < curr_iter_num) {
     462            // Optimal flow is found
    359463            optimal = true;
     464            // Setting node potentials
     465            for (NodeIt n(_graph); n != INVALID; ++n)
     466              (*_potential)[n] = bf.dist(n);
    360467            break;
    361468          } else {
    362469            // Searching for node disjoint negative cycles
    363             for (ResNodeIt n(_res_graph); n != INVALID; ++n)
     470            for (ResNodeIt n(*_res_graph); n != INVALID; ++n)
    364471              visited[n] = 0;
    365472            int id = 0;
    366             for (ResNodeIt n(_res_graph); n != INVALID; ++n) {
     473            for (ResNodeIt n(*_res_graph); n != INVALID; ++n) {
    367474              if (visited[n] > 0) continue;
    368475              visited[n] = ++id;
    369476              ResNode u = pred[n] == INVALID ?
    370                           INVALID : _res_graph.source(pred[n]);
     477                          INVALID : _res_graph->source(pred[n]);
    371478              while (u != INVALID && visited[u] == 0) {
    372479                visited[u] = id;
    373480                u = pred[u] == INVALID ?
    374                     INVALID : _res_graph.source(pred[u]);
     481                    INVALID : _res_graph->source(pred[u]);
    375482              }
    376483              if (u != INVALID && visited[u] == id) {
     
    380487                ResEdge e = pred[u];
    381488                cycle.push_back(e);
    382                 Capacity d = _res_graph.rescap(e);
    383                 while (_res_graph.source(e) != u) {
    384                   cycle.push_back(e = pred[_res_graph.source(e)]);
    385                   if (_res_graph.rescap(e) < d)
    386                     d = _res_graph.rescap(e);
     489                Capacity d = _res_graph->rescap(e);
     490                while (_res_graph->source(e) != u) {
     491                  cycle.push_back(e = pred[_res_graph->source(e)]);
     492                  if (_res_graph->rescap(e) < d)
     493                    d = _res_graph->rescap(e);
    387494                }
    388495
    389496                // Augmenting along the cycle
    390497                for (int i = 0; i < int(cycle.size()); ++i)
    391                   _res_graph.augment(cycle[i], d);
     498                  _res_graph->augment(cycle[i], d);
    392499              }
    393500            }
     
    398505        }
    399506      }
    400 
    401       // Handling non-zero lower bounds
    402       if (_lower) {
    403         for (EdgeIt e(_graph); e != INVALID; ++e)
    404           _flow[e] += (*_lower)[e];
    405       }
    406       return true;
    407507    }
    408508
     
    411511    /// Executes the algorithm using \ref MinMeanCycle for negative
    412512    /// cycle detection.
    413     bool startMinMean() {
     513    void startMinMean() {
    414514      typedef Path<ResGraph> ResPath;
    415       MinMeanCycle<ResGraph, ResidualCostMap> mmc(_res_graph, _res_cost);
     515      MinMeanCycle<ResGraph, ResidualCostMap> mmc(*_res_graph, _res_cost);
    416516      ResPath cycle;
    417517
     
    426526          Capacity delta = 0;
    427527          for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) {
    428             if (delta == 0 || _res_graph.rescap(e) < delta)
    429               delta = _res_graph.rescap(e);
     528            if (delta == 0 || _res_graph->rescap(e) < delta)
     529              delta = _res_graph->rescap(e);
    430530          }
    431531
    432532          // Augmenting along the cycle
    433533          for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e)
    434             _res_graph.augment(e, delta);
     534            _res_graph->augment(e, delta);
    435535
    436536          // Finding the minimum cycle mean for the modified residual
     
    441541      }
    442542
    443       // Handling non-zero lower bounds
    444       if (_lower) {
    445         for (EdgeIt e(_graph); e != INVALID; ++e)
    446           _flow[e] += (*_lower)[e];
    447       }
    448       return true;
     543      // Computing node potentials
     544      BellmanFord<ResGraph, ResidualCostMap> bf(*_res_graph, _res_cost);
     545      bf.init(0); bf.start();
     546      for (NodeIt n(_graph); n != INVALID; ++n)
     547        (*_potential)[n] = bf.dist(n);
    449548    }
    450549
  • lemon/min_cost_flow.h

    r2579 r2581  
    4444  ///
    4545  /// There are four implementations for the minimum cost flow problem,
    46   /// which can be used exactly the same way except for the fact that
    47   /// \ref CycleCanceling does not provide dual solution (node
    48   /// potentials) since it is a pure primal method.
     46  /// which can be used exactly the same way.
    4947  /// - \ref CapacityScaling The capacity scaling algorithm.
    5048  /// - \ref CostScaling The cost scaling algorithm.
     
    6159  /// - Edge capacities and costs should be \e non-negative \e integers.
    6260  /// - Supply values should be \e signed \e integers.
    63   /// - \c LowerMap::Value must be convertible to \c CapacityMap::Value.
    64   /// - \c CapacityMap::Value and \c SupplyMap::Value must be
    65   ///   convertible to each other.
    66   /// - All value types must be convertible to \c CostMap::Value, which
    67   ///   must be signed type.
     61  /// - The value types of the maps should be convertible to each other.
     62  /// - \c CostMap::Value must be signed type.
    6863  ///
    6964  /// \author Peter Kovacs
     
    7166  template < typename Graph,
    7267             typename LowerMap = typename Graph::template EdgeMap<int>,
    73              typename CapacityMap = LowerMap,
     68             typename CapacityMap = typename Graph::template EdgeMap<int>,
    7469             typename CostMap = typename Graph::template EdgeMap<int>,
    75              typename SupplyMap = typename Graph::template NodeMap
    76                                   <typename CapacityMap::Value> >
     70             typename SupplyMap = typename Graph::template NodeMap<int> >
    7771  class MinCostFlow :
    7872    public NetworkSimplex< Graph, LowerMap, CapacityMap,
     
    8680  public:
    8781
    88     /// General constructor of the class (with lower bounds).
     82    /// General constructor (with lower bounds).
    8983    MinCostFlow( const Graph &graph,
    9084                 const LowerMap &lower,
     
    10195      MinCostFlowImpl(graph, capacity, cost, supply) {}
    10296
    103     /// Simple constructor of the class (with lower bounds).
     97    /// Simple constructor (with lower bounds).
    10498    MinCostFlow( const Graph &graph,
    10599                 const LowerMap &lower,
     
    111105                       s, t, flow_value ) {}
    112106
    113     /// Simple constructor of the class (without lower bounds).
     107    /// Simple constructor (without lower bounds).
    114108    MinCostFlow( const Graph &graph,
    115109                 const CapacityMap &capacity,
  • lemon/network_simplex.h

    r2579 r2581  
    5353  /// - Edge capacities and costs should be \e non-negative \e integers.
    5454  /// - Supply values should be \e signed \e integers.
    55   /// - \c LowerMap::Value must be convertible to \c CapacityMap::Value.
    56   /// - \c CapacityMap::Value and \c SupplyMap::Value must be
    57   ///   convertible to each other.
    58   /// - All value types must be convertible to \c CostMap::Value, which
    59   ///   must be signed type.
     55  /// - The value types of the maps should be convertible to each other.
     56  /// - \c CostMap::Value must be signed type.
    6057  ///
    6158  /// \note \ref NetworkSimplex provides six different pivot rule
     
    470467
    471468    // Members for handling the original graph
    472     FlowMap _flow_result;
    473     PotentialMap _potential_result;
     469    FlowMap *_flow_result;
     470    PotentialMap *_potential_result;
     471    bool _local_flow;
     472    bool _local_potential;
    474473    NodeRefMap _node_ref;
    475474    EdgeRefMap _edge_ref;
     
    488487  public :
    489488
    490     /// \brief General constructor of the class (with lower bounds).
    491     ///
    492     /// General constructor of the class (with lower bounds).
     489    /// \brief General constructor (with lower bounds).
     490    ///
     491    /// General constructor (with lower bounds).
    493492    ///
    494493    /// \param graph The directed graph the algorithm runs on.
     
    507506      _pred_edge(_graph), _thread(_graph), _forward(_graph),
    508507      _state(_graph), _red_cost(_graph, _cost, _potential),
    509       _flow_result(graph), _potential_result(graph),
     508      _flow_result(0), _potential_result(0),
     509      _local_flow(false), _local_potential(false),
    510510      _node_ref(graph), _edge_ref(graph)
    511511    {
     
    539539    }
    540540
    541     /// \brief General constructor of the class (without lower bounds).
    542     ///
    543     /// General constructor of the class (without lower bounds).
     541    /// \brief General constructor (without lower bounds).
     542    ///
     543    /// General constructor (without lower bounds).
    544544    ///
    545545    /// \param graph The directed graph the algorithm runs on.
     
    556556      _pred_edge(_graph), _thread(_graph), _forward(_graph),
    557557      _state(_graph), _red_cost(_graph, _cost, _potential),
    558       _flow_result(graph), _potential_result(graph),
     558      _flow_result(0), _potential_result(0),
     559      _local_flow(false), _local_potential(false),
    559560      _node_ref(graph), _edge_ref(graph)
    560561    {
     
    575576    }
    576577
    577     /// \brief Simple constructor of the class (with lower bounds).
    578     ///
    579     /// Simple constructor of the class (with lower bounds).
     578    /// \brief Simple constructor (with lower bounds).
     579    ///
     580    /// Simple constructor (with lower bounds).
    580581    ///
    581582    /// \param graph The directed graph the algorithm runs on.
     
    599600      _pred_edge(_graph), _thread(_graph), _forward(_graph),
    600601      _state(_graph), _red_cost(_graph, _cost, _potential),
    601       _flow_result(graph), _potential_result(graph),
     602      _flow_result(0), _potential_result(0),
     603      _local_flow(false), _local_potential(false),
    602604      _node_ref(graph), _edge_ref(graph)
    603605    {
     
    626628    }
    627629
    628     /// \brief Simple constructor of the class (without lower bounds).
    629     ///
    630     /// Simple constructor of the class (without lower bounds).
     630    /// \brief Simple constructor (without lower bounds).
     631    ///
     632    /// Simple constructor (without lower bounds).
    631633    ///
    632634    /// \param graph The directed graph the algorithm runs on.
     
    648650      _pred_edge(_graph), _thread(_graph), _forward(_graph),
    649651      _state(_graph), _red_cost(_graph, _cost, _potential),
    650       _flow_result(graph), _potential_result(graph),
     652      _flow_result(0), _potential_result(0),
     653      _local_flow(false), _local_potential(false),
    651654      _node_ref(graph), _edge_ref(graph)
    652655    {
     
    663666    }
    664667
     668    /// Destructor.
     669    ~NetworkSimplex() {
     670      if (_local_flow) delete _flow_result;
     671      if (_local_potential) delete _potential_result;
     672    }
     673
     674    /// \brief Sets the flow map.
     675    ///
     676    /// Sets the flow map.
     677    ///
     678    /// \return \c (*this)
     679    NetworkSimplex& flowMap(FlowMap &map) {
     680      if (_local_flow) {
     681        delete _flow_result;
     682        _local_flow = false;
     683      }
     684      _flow_result = &map;
     685      return *this;
     686    }
     687
     688    /// \brief Sets the potential map.
     689    ///
     690    /// Sets the potential map.
     691    ///
     692    /// \return \c (*this)
     693    NetworkSimplex& potentialMap(PotentialMap &map) {
     694      if (_local_potential) {
     695        delete _potential_result;
     696        _local_potential = false;
     697      }
     698      _potential_result = &map;
     699      return *this;
     700    }
     701
     702    /// \name Execution control
     703    /// The only way to execute the algorithm is to call the run()
     704    /// function.
     705
     706    /// @{
     707
    665708    /// \brief Runs the algorithm.
    666709    ///
     
    704747    }
    705748
     749    /// @}
     750
     751    /// \name Query Functions
     752    /// The result of the algorithm can be obtained using these
     753    /// functions.
     754    /// \n run() must be called before using them.
     755
     756    /// @{
     757
    706758    /// \brief Returns a const reference to the edge map storing the
    707759    /// found flow.
     
    711763    /// \pre \ref run() must be called before using this function.
    712764    const FlowMap& flowMap() const {
    713       return _flow_result;
     765      return *_flow_result;
    714766    }
    715767
     
    722774    /// \pre \ref run() must be called before using this function.
    723775    const PotentialMap& potentialMap() const {
    724       return _potential_result;
     776      return *_potential_result;
     777    }
     778
     779    /// \brief Returns the flow on the edge.
     780    ///
     781    /// Returns the flow on the edge.
     782    ///
     783    /// \pre \ref run() must be called before using this function.
     784    Capacity flow(const typename Graph::Edge& edge) const {
     785      return (*_flow_result)[edge];
     786    }
     787
     788    /// \brief Returns the potential of the node.
     789    ///
     790    /// Returns the potential of the node.
     791    ///
     792    /// \pre \ref run() must be called before using this function.
     793    Cost potential(const typename Graph::Node& node) const {
     794      return (*_potential_result)[node];
    725795    }
    726796
     
    734804      Cost c = 0;
    735805      for (typename Graph::EdgeIt e(_graph_ref); e != INVALID; ++e)
    736         c += _flow_result[e] * _cost[_edge_ref[e]];
     806        c += (*_flow_result)[e] * _cost[_edge_ref[e]];
    737807      return c;
    738808    }
     809
     810    /// @}
    739811
    740812  private:
     
    744816    bool init() {
    745817      if (!_valid_supply) return false;
     818
     819      // Initializing result maps
     820      if (!_flow_result) {
     821        _flow_result = new FlowMap(_graph_ref);
     822        _local_flow = true;
     823      }
     824      if (!_potential_result) {
     825        _potential_result = new PotentialMap(_graph_ref);
     826        _local_potential = true;
     827      }
    746828
    747829      // Initializing state and flow maps
     
    10161098      if (_lower) {
    10171099        for (typename Graph::EdgeIt e(_graph_ref); e != INVALID; ++e)
    1018           _flow_result[e] = (*_lower)[e] + _flow[_edge_ref[e]];
     1100          (*_flow_result)[e] = (*_lower)[e] + _flow[_edge_ref[e]];
    10191101      } else {
    10201102        for (typename Graph::EdgeIt e(_graph_ref); e != INVALID; ++e)
    1021           _flow_result[e] = _flow[_edge_ref[e]];
     1103          (*_flow_result)[e] = _flow[_edge_ref[e]];
    10221104      }
    10231105      // Copying potential values to _potential_result
    10241106      for (typename Graph::NodeIt n(_graph_ref); n != INVALID; ++n)
    1025         _potential_result[n] = _potential[_node_ref[n]];
     1107        (*_potential_result)[n] = _potential[_node_ref[n]];
    10261108
    10271109      return true;
Note: See TracChangeset for help on using the changeset viewer.