1.1 --- a/lemon/min_cost_max_flow.h Fri Feb 29 15:55:13 2008 +0000
1.2 +++ b/lemon/min_cost_max_flow.h Fri Feb 29 15:55:39 2008 +0000
1.3 @@ -64,8 +64,7 @@
1.4 typename CostMap = typename Graph::template EdgeMap<int> >
1.5 class MinCostMaxFlow
1.6 {
1.7 - typedef typename Graph::Node Node;
1.8 - typedef typename Graph::Edge Edge;
1.9 + GRAPH_TYPEDEFS(typename Graph);
1.10
1.11 typedef typename CapacityMap::Value Capacity;
1.12 typedef typename CostMap::Value Cost;
1.13 @@ -86,15 +85,17 @@
1.14
1.15 // The directed graph the algorithm runs on
1.16 const Graph &_graph;
1.17 - // The modified capacity map
1.18 + // The capacity map
1.19 const CapacityMap &_capacity;
1.20 // The cost map
1.21 const CostMap &_cost;
1.22
1.23 // Edge map of the found flow
1.24 - FlowMap _flow;
1.25 - // Node map of the found potentials
1.26 - PotentialMap _potential;
1.27 + FlowMap *_flow;
1.28 + bool _local_flow;
1.29 + // Node map of the current potentials
1.30 + PotentialMap *_potential;
1.31 + bool _local_potential;
1.32
1.33 // The source node
1.34 Node _source;
1.35 @@ -103,34 +104,94 @@
1.36
1.37 public:
1.38
1.39 - /// \brief The constructor of the class.
1.40 + /// \brief Constructor.
1.41 ///
1.42 - /// The constructor of the class.
1.43 + /// Constructor.
1.44 ///
1.45 - /// \param _graph The directed graph the algorithm runs on.
1.46 - /// \param _capacity The capacities (upper bounds) of the edges.
1.47 - /// \param _cost The cost (length) values of the edges.
1.48 - /// \param _s The source node.
1.49 - /// \param _t The target node.
1.50 + /// \param graph The directed graph the algorithm runs on.
1.51 + /// \param capacity The capacities (upper bounds) of the edges.
1.52 + /// \param cost The cost (length) values of the edges.
1.53 + /// \param s The source node.
1.54 + /// \param t The target node.
1.55 MinCostMaxFlow( const Graph &graph,
1.56 const CapacityMap &capacity,
1.57 const CostMap &cost,
1.58 Node s, Node t ) :
1.59 - _graph(graph), _capacity(capacity), _cost(cost), _flow(graph),
1.60 - _potential(graph), _source(s), _target(t)
1.61 - {}
1.62 + _graph(graph), _capacity(capacity), _cost(cost), _flow(0),
1.63 + _local_flow(false), _potential(0), _local_potential(false),
1.64 + _source(s), _target(t) {}
1.65 +
1.66 + /// Destructor.
1.67 + ~MinCostMaxFlow() {
1.68 + if (_local_flow) delete _flow;
1.69 + if (_local_potential) delete _potential;
1.70 + }
1.71 +
1.72 + /// \brief Sets the flow map.
1.73 + ///
1.74 + /// Sets the flow map.
1.75 + ///
1.76 + /// \return \c (*this)
1.77 + MinCostMaxFlow& flowMap(FlowMap &map) {
1.78 + if (_local_flow) {
1.79 + delete _flow;
1.80 + _local_flow = false;
1.81 + }
1.82 + _flow = ↦
1.83 + return *this;
1.84 + }
1.85 +
1.86 + /// \brief Sets the potential map.
1.87 + ///
1.88 + /// Sets the potential map.
1.89 + ///
1.90 + /// \return \c (*this)
1.91 + MinCostMaxFlow& potentialMap(PotentialMap &map) {
1.92 + if (_local_potential) {
1.93 + delete _potential;
1.94 + _local_potential = false;
1.95 + }
1.96 + _potential = ↦
1.97 + return *this;
1.98 + }
1.99 +
1.100 + /// \name Execution control
1.101 + /// The only way to execute the algorithm is to call the run()
1.102 + /// function.
1.103 +
1.104 + /// @{
1.105
1.106 /// \brief Runs the algorithm.
1.107 ///
1.108 /// Runs the algorithm.
1.109 void run() {
1.110 + // Initializing maps
1.111 + if (!_flow) {
1.112 + _flow = new FlowMap(_graph);
1.113 + _local_flow = true;
1.114 + }
1.115 + if (!_potential) {
1.116 + _potential = new PotentialMap(_graph);
1.117 + _local_potential = true;
1.118 + }
1.119 + // Running Preflow
1.120 MaxFlowImpl preflow(_graph, _capacity, _source, _target);
1.121 - preflow.flowMap(_flow).runMinCut();
1.122 + preflow.flowMap(*_flow).runMinCut();
1.123 + // Running NetworkSimplex
1.124 MinCostFlowImpl mcf( _graph, _capacity, _cost,
1.125 _source, _target, preflow.flowValue() );
1.126 - mcf.flowMap(_flow).potentialMap(_potential).run();
1.127 + mcf.flowMap(*_flow).potentialMap(*_potential).run();
1.128 }
1.129
1.130 + /// @}
1.131 +
1.132 + /// \name Query Functions
1.133 + /// The result of the algorithm can be obtained using these
1.134 + /// functions.
1.135 + /// \n run() must be called before using them.
1.136 +
1.137 + /// @{
1.138 +
1.139 /// \brief Returns a const reference to the edge map storing the
1.140 /// found flow.
1.141 ///
1.142 @@ -138,7 +199,7 @@
1.143 ///
1.144 /// \pre \ref run() must be called before using this function.
1.145 const FlowMap& flowMap() const {
1.146 - return _flow;
1.147 + return *_flow;
1.148 }
1.149
1.150 /// \brief Returns a const reference to the node map storing the
1.151 @@ -149,7 +210,25 @@
1.152 ///
1.153 /// \pre \ref run() must be called before using this function.
1.154 const PotentialMap& potentialMap() const {
1.155 - return _potential;
1.156 + return *_potential;
1.157 + }
1.158 +
1.159 + /// \brief Returns the flow on the given edge.
1.160 + ///
1.161 + /// Returns the flow on the given edge.
1.162 + ///
1.163 + /// \pre \ref run() must be called before using this function.
1.164 + Capacity flow(const Edge& edge) const {
1.165 + return (*_flow)[edge];
1.166 + }
1.167 +
1.168 + /// \brief Returns the potential of the given node.
1.169 + ///
1.170 + /// Returns the potential of the given node.
1.171 + ///
1.172 + /// \pre \ref run() must be called before using this function.
1.173 + Cost potential(const Node& node) const {
1.174 + return (*_potential)[node];
1.175 }
1.176
1.177 /// \brief Returns the total cost of the found flow.
1.178 @@ -160,11 +239,13 @@
1.179 /// \pre \ref run() must be called before using this function.
1.180 Cost totalCost() const {
1.181 Cost c = 0;
1.182 - for (typename Graph::EdgeIt e(_graph); e != INVALID; ++e)
1.183 - c += _flow[e] * _cost[e];
1.184 + for (EdgeIt e(_graph); e != INVALID; ++e)
1.185 + c += (*_flow)[e] * _cost[e];
1.186 return c;
1.187 }
1.188
1.189 + /// @}
1.190 +
1.191 }; //class MinCostMaxFlow
1.192
1.193 ///@}