Changeset 2587:061be2e64eca in lemon-0.x
- Timestamp:
- 02/29/08 16:55:39 (16 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3469
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/min_cost_max_flow.h
r2582 r2587 65 65 class MinCostMaxFlow 66 66 { 67 typedef typename Graph::Node Node; 68 typedef typename Graph::Edge Edge; 67 GRAPH_TYPEDEFS(typename Graph); 69 68 70 69 typedef typename CapacityMap::Value Capacity; … … 87 86 // The directed graph the algorithm runs on 88 87 const Graph &_graph; 89 // The modifiedcapacity map88 // The capacity map 90 89 const CapacityMap &_capacity; 91 90 // The cost map … … 93 92 94 93 // 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; 98 99 99 100 // The source node … … 104 105 public: 105 106 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. 115 116 MinCostMaxFlow( const Graph &graph, 116 117 const CapacityMap &capacity, 117 118 const CostMap &cost, 118 119 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 /// @{ 122 163 123 164 /// \brief Runs the algorithm. … … 125 166 /// Runs the algorithm. 126 167 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 127 178 MaxFlowImpl preflow(_graph, _capacity, _source, _target); 128 preflow.flowMap(_flow).runMinCut(); 179 preflow.flowMap(*_flow).runMinCut(); 180 // Running NetworkSimplex 129 181 MinCostFlowImpl mcf( _graph, _capacity, _cost, 130 182 _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 /// @{ 133 194 134 195 /// \brief Returns a const reference to the edge map storing the … … 139 200 /// \pre \ref run() must be called before using this function. 140 201 const FlowMap& flowMap() const { 141 return _flow;202 return *_flow; 142 203 } 143 204 … … 150 211 /// \pre \ref run() must be called before using this function. 151 212 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]; 153 232 } 154 233 … … 161 240 Cost totalCost() const { 162 241 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]; 165 244 return c; 166 245 } 167 246 247 /// @} 248 168 249 }; //class MinCostMaxFlow 169 250
Note: See TracChangeset
for help on using the changeset viewer.