# Changeset 2587:061be2e64eca in lemon-0.x

Ignore:
Timestamp:
02/29/08 16:55:39 (11 years ago)
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

Unmodified
Added
Removed
• ## lemon/min_cost_max_flow.h

 r2582 class MinCostMaxFlow { typedef typename Graph::Node Node; typedef typename Graph::Edge Edge; GRAPH_TYPEDEFS(typename Graph); typedef typename CapacityMap::Value Capacity; // The directed graph the algorithm runs on const Graph &_graph; // The modified capacity map // The capacity map const CapacityMap &_capacity; // The cost map // Edge map of the found flow FlowMap _flow; // Node map of the found potentials PotentialMap _potential; FlowMap *_flow; bool _local_flow; // Node map of the current potentials PotentialMap *_potential; bool _local_potential; // The source node public: /// \brief The constructor of the class. /// /// The constructor of the class. /// /// \param _graph The directed graph the algorithm runs on. /// \param _capacity The capacities (upper bounds) of the edges. /// \param _cost The cost (length) values of the edges. /// \param _s The source node. /// \param _t The target node. /// \brief Constructor. /// /// Constructor. /// /// \param graph The directed graph the algorithm runs on. /// \param capacity The capacities (upper bounds) of the edges. /// \param cost The cost (length) values of the edges. /// \param s The source node. /// \param t The target node. MinCostMaxFlow( const Graph &graph, const CapacityMap &capacity, const CostMap &cost, Node s, Node t ) : _graph(graph), _capacity(capacity), _cost(cost), _flow(graph), _potential(graph), _source(s), _target(t) {} _graph(graph), _capacity(capacity), _cost(cost), _flow(0), _local_flow(false), _potential(0), _local_potential(false), _source(s), _target(t) {} /// Destructor. ~MinCostMaxFlow() { if (_local_flow) delete _flow; if (_local_potential) delete _potential; } /// \brief Sets the flow map. /// /// Sets the flow map. /// /// \return \c (*this) MinCostMaxFlow& flowMap(FlowMap &map) { if (_local_flow) { delete _flow; _local_flow = false; } _flow = ↦ return *this; } /// \brief Sets the potential map. /// /// Sets the potential map. /// /// \return \c (*this) MinCostMaxFlow& potentialMap(PotentialMap &map) { if (_local_potential) { delete _potential; _local_potential = false; } _potential = ↦ return *this; } /// \name Execution control /// The only way to execute the algorithm is to call the run() /// function. /// @{ /// \brief Runs the algorithm. /// Runs the algorithm. void run() { // Initializing maps if (!_flow) { _flow = new FlowMap(_graph); _local_flow = true; } if (!_potential) { _potential = new PotentialMap(_graph); _local_potential = true; } // Running Preflow MaxFlowImpl preflow(_graph, _capacity, _source, _target); preflow.flowMap(_flow).runMinCut(); preflow.flowMap(*_flow).runMinCut(); // Running NetworkSimplex MinCostFlowImpl mcf( _graph, _capacity, _cost, _source, _target, preflow.flowValue() ); mcf.flowMap(_flow).potentialMap(_potential).run(); } mcf.flowMap(*_flow).potentialMap(*_potential).run(); } /// @} /// \name Query Functions /// The result of the algorithm can be obtained using these /// functions. /// \n run() must be called before using them. /// @{ /// \brief Returns a const reference to the edge map storing the /// \pre \ref run() must be called before using this function. const FlowMap& flowMap() const { return _flow; return *_flow; } /// \pre \ref run() must be called before using this function. const PotentialMap& potentialMap() const { return _potential; return *_potential; } /// \brief Returns the flow on the given edge. /// /// Returns the flow on the given edge. /// /// \pre \ref run() must be called before using this function. Capacity flow(const Edge& edge) const { return (*_flow)[edge]; } /// \brief Returns the potential of the given node. /// /// Returns the potential of the given node. /// /// \pre \ref run() must be called before using this function. Cost potential(const Node& node) const { return (*_potential)[node]; } Cost totalCost() const { Cost c = 0; for (typename Graph::EdgeIt e(_graph); e != INVALID; ++e) c += _flow[e] * _cost[e]; for (EdgeIt e(_graph); e != INVALID; ++e) c += (*_flow)[e] * _cost[e]; return c; } /// @} }; //class MinCostMaxFlow
Note: See TracChangeset for help on using the changeset viewer.