COIN-OR::LEMON - Graph Library

Changeset 2587:061be2e64eca in lemon-0.x


Ignore:
Timestamp:
02/29/08 16:55:39 (12 years ago)
Author:
Peter Kovacs
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3469
Message:

External flow and potential maps can be used in MinCostMaxFlow?.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/min_cost_max_flow.h

    r2582 r2587  
    6565  class MinCostMaxFlow
    6666  {
    67     typedef typename Graph::Node Node;
    68     typedef typename Graph::Edge Edge;
     67    GRAPH_TYPEDEFS(typename Graph);
    6968
    7069    typedef typename CapacityMap::Value Capacity;
     
    8786    // The directed graph the algorithm runs on
    8887    const Graph &_graph;
    89     // The modified capacity map
     88    // The capacity map
    9089    const CapacityMap &_capacity;
    9190    // The cost map
     
    9392
    9493    // Edge map of the found flow
    95     FlowMap _flow;
    96     // Node map of the found potentials
    97     PotentialMap _potential;
     94    FlowMap *_flow;
     95    bool _local_flow;
     96    // Node map of the current potentials
     97    PotentialMap *_potential;
     98    bool _local_potential;
    9899
    99100    // The source node
     
    104105  public:
    105106
    106     /// \brief The constructor of the class.
    107     ///
    108     /// The constructor of the class.
    109     ///
    110     /// \param _graph The directed graph the algorithm runs on.
    111     /// \param _capacity The capacities (upper bounds) of the edges.
    112     /// \param _cost The cost (length) values of the edges.
    113     /// \param _s The source node.
    114     /// \param _t The target node.
     107    /// \brief Constructor.
     108    ///
     109    /// Constructor.
     110    ///
     111    /// \param graph The directed graph the algorithm runs on.
     112    /// \param capacity The capacities (upper bounds) of the edges.
     113    /// \param cost The cost (length) values of the edges.
     114    /// \param s The source node.
     115    /// \param t The target node.
    115116    MinCostMaxFlow( const Graph &graph,
    116117                    const CapacityMap &capacity,
    117118                    const CostMap &cost,
    118119                    Node s, Node t ) :
    119       _graph(graph), _capacity(capacity), _cost(cost), _flow(graph),
    120       _potential(graph), _source(s), _target(t)
    121     {}
     120      _graph(graph), _capacity(capacity), _cost(cost), _flow(0),
     121      _local_flow(false), _potential(0), _local_potential(false),
     122      _source(s), _target(t) {}
     123
     124    /// Destructor.
     125    ~MinCostMaxFlow() {
     126      if (_local_flow) delete _flow;
     127      if (_local_potential) delete _potential;
     128    }
     129
     130    /// \brief Sets the flow map.
     131    ///
     132    /// Sets the flow map.
     133    ///
     134    /// \return \c (*this)
     135    MinCostMaxFlow& flowMap(FlowMap &map) {
     136      if (_local_flow) {
     137        delete _flow;
     138        _local_flow = false;
     139      }
     140      _flow = ↦
     141      return *this;
     142    }
     143
     144    /// \brief Sets the potential map.
     145    ///
     146    /// Sets the potential map.
     147    ///
     148    /// \return \c (*this)
     149    MinCostMaxFlow& potentialMap(PotentialMap &map) {
     150      if (_local_potential) {
     151        delete _potential;
     152        _local_potential = false;
     153      }
     154      _potential = ↦
     155      return *this;
     156    }
     157
     158    /// \name Execution control
     159    /// The only way to execute the algorithm is to call the run()
     160    /// function.
     161
     162    /// @{
    122163
    123164    /// \brief Runs the algorithm.
     
    125166    /// Runs the algorithm.
    126167    void run() {
     168      // Initializing maps
     169      if (!_flow) {
     170        _flow = new FlowMap(_graph);
     171        _local_flow = true;
     172      }
     173      if (!_potential) {
     174        _potential = new PotentialMap(_graph);
     175        _local_potential = true;
     176      }
     177      // Running Preflow
    127178      MaxFlowImpl preflow(_graph, _capacity, _source, _target);
    128       preflow.flowMap(_flow).runMinCut();
     179      preflow.flowMap(*_flow).runMinCut();
     180      // Running NetworkSimplex
    129181      MinCostFlowImpl mcf( _graph, _capacity, _cost,
    130182                           _source, _target, preflow.flowValue() );
    131       mcf.flowMap(_flow).potentialMap(_potential).run();
    132     }
     183      mcf.flowMap(*_flow).potentialMap(*_potential).run();
     184    }
     185
     186    /// @}
     187
     188    /// \name Query Functions
     189    /// The result of the algorithm can be obtained using these
     190    /// functions.
     191    /// \n run() must be called before using them.
     192
     193    /// @{
    133194
    134195    /// \brief Returns a const reference to the edge map storing the
     
    139200    /// \pre \ref run() must be called before using this function.
    140201    const FlowMap& flowMap() const {
    141       return _flow;
     202      return *_flow;
    142203    }
    143204
     
    150211    /// \pre \ref run() must be called before using this function.
    151212    const PotentialMap& potentialMap() const {
    152       return _potential;
     213      return *_potential;
     214    }
     215
     216    /// \brief Returns the flow on the given edge.
     217    ///
     218    /// Returns the flow on the given edge.
     219    ///
     220    /// \pre \ref run() must be called before using this function.
     221    Capacity flow(const Edge& edge) const {
     222      return (*_flow)[edge];
     223    }
     224
     225    /// \brief Returns the potential of the given node.
     226    ///
     227    /// Returns the potential of the given node.
     228    ///
     229    /// \pre \ref run() must be called before using this function.
     230    Cost potential(const Node& node) const {
     231      return (*_potential)[node];
    153232    }
    154233
     
    161240    Cost totalCost() const {
    162241      Cost c = 0;
    163       for (typename Graph::EdgeIt e(_graph); e != INVALID; ++e)
    164         c += _flow[e] * _cost[e];
     242      for (EdgeIt e(_graph); e != INVALID; ++e)
     243        c += (*_flow)[e] * _cost[e];
    165244      return c;
    166245    }
    167246
     247    /// @}
     248
    168249  }; //class MinCostMaxFlow
    169250
Note: See TracChangeset for help on using the changeset viewer.