1.1 --- a/lemon/edmonds_karp.h Fri Aug 09 14:07:27 2013 +0200
1.2 +++ b/lemon/edmonds_karp.h Fri Aug 09 11:28:17 2013 +0200
1.3 @@ -2,7 +2,7 @@
1.4 *
1.5 * This file is a part of LEMON, a generic C++ optimization library.
1.6 *
1.7 - * Copyright (C) 2003-2010
1.8 + * Copyright (C) 2003-2013
1.9 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 *
1.12 @@ -36,7 +36,7 @@
1.13 template <typename GR, typename CAP>
1.14 struct EdmondsKarpDefaultTraits {
1.15
1.16 - /// \brief The digraph type the algorithm runs on.
1.17 + /// \brief The digraph type the algorithm runs on.
1.18 typedef GR Digraph;
1.19
1.20 /// \brief The type of the map that stores the arc capacities.
1.21 @@ -60,7 +60,7 @@
1.22
1.23 /// \brief Instantiates a FlowMap.
1.24 ///
1.25 - /// This function instantiates a \ref FlowMap.
1.26 + /// This function instantiates a \ref FlowMap.
1.27 /// \param digraph The digraph for which we would like to define
1.28 /// the flow map.
1.29 static FlowMap* createFlowMap(const Digraph& digraph) {
1.30 @@ -95,7 +95,7 @@
1.31 ///
1.32 /// \tparam GR The type of the digraph the algorithm runs on.
1.33 /// \tparam CAP The type of the capacity map. The default map
1.34 - /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
1.35 + /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
1.36 /// \tparam TR The traits class that defines various types used by the
1.37 /// algorithm. By default, it is \ref EdmondsKarpDefaultTraits
1.38 /// "EdmondsKarpDefaultTraits<GR, CAP>".
1.39 @@ -104,9 +104,9 @@
1.40
1.41 #ifdef DOXYGEN
1.42 template <typename GR, typename CAP, typename TR>
1.43 -#else
1.44 +#else
1.45 template <typename GR,
1.46 - typename CAP = typename GR::template ArcMap<int>,
1.47 + typename CAP = typename GR::template ArcMap<int>,
1.48 typename TR = EdmondsKarpDefaultTraits<GR, CAP> >
1.49 #endif
1.50 class EdmondsKarp {
1.51 @@ -120,7 +120,7 @@
1.52 /// The type of the capacity map.
1.53 typedef typename Traits::CapacityMap CapacityMap;
1.54 /// The type of the flow values.
1.55 - typedef typename Traits::Value Value;
1.56 + typedef typename Traits::Value Value;
1.57
1.58 /// The type of the flow map.
1.59 typedef typename Traits::FlowMap FlowMap;
1.60 @@ -131,7 +131,7 @@
1.61
1.62 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.63 typedef typename Digraph::template NodeMap<Arc> PredMap;
1.64 -
1.65 +
1.66 const Digraph& _graph;
1.67 const CapacityMap* _capacity;
1.68
1.69 @@ -142,30 +142,30 @@
1.70
1.71 PredMap* _pred;
1.72 std::vector<Node> _queue;
1.73 -
1.74 +
1.75 Tolerance _tolerance;
1.76 Value _flow_value;
1.77
1.78 void createStructures() {
1.79 if (!_flow) {
1.80 - _flow = Traits::createFlowMap(_graph);
1.81 - _local_flow = true;
1.82 + _flow = Traits::createFlowMap(_graph);
1.83 + _local_flow = true;
1.84 }
1.85 if (!_pred) {
1.86 - _pred = new PredMap(_graph);
1.87 + _pred = new PredMap(_graph);
1.88 }
1.89 _queue.resize(countNodes(_graph));
1.90 }
1.91
1.92 void destroyStructures() {
1.93 if (_local_flow) {
1.94 - delete _flow;
1.95 + delete _flow;
1.96 }
1.97 if (_pred) {
1.98 - delete _pred;
1.99 + delete _pred;
1.100 }
1.101 }
1.102 -
1.103 +
1.104 public:
1.105
1.106 typedef EdmondsKarp Create;
1.107 @@ -178,7 +178,7 @@
1.108 struct SetFlowMapTraits : public Traits {
1.109 typedef T FlowMap;
1.110 static FlowMap *createFlowMap(const Digraph&) {
1.111 - LEMON_ASSERT(false, "FlowMap is not initialized");
1.112 + LEMON_ASSERT(false, "FlowMap is not initialized");
1.113 return 0;
1.114 }
1.115 };
1.116 @@ -189,7 +189,7 @@
1.117 /// \ref named-templ-param "Named parameter" for setting FlowMap
1.118 /// type
1.119 template <typename T>
1.120 - struct SetFlowMap
1.121 + struct SetFlowMap
1.122 : public EdmondsKarp<Digraph, CapacityMap, SetFlowMapTraits<T> > {
1.123 typedef EdmondsKarp<Digraph, CapacityMap, SetFlowMapTraits<T> > Create;
1.124 };
1.125 @@ -197,22 +197,22 @@
1.126 /// @}
1.127
1.128 protected:
1.129 -
1.130 +
1.131 EdmondsKarp() {}
1.132
1.133 public:
1.134
1.135 /// \brief The constructor of the class.
1.136 ///
1.137 - /// The constructor of the class.
1.138 - /// \param digraph The digraph the algorithm runs on.
1.139 - /// \param capacity The capacity of the arcs.
1.140 + /// The constructor of the class.
1.141 + /// \param digraph The digraph the algorithm runs on.
1.142 + /// \param capacity The capacity of the arcs.
1.143 /// \param source The source node.
1.144 /// \param target The target node.
1.145 EdmondsKarp(const Digraph& digraph, const CapacityMap& capacity,
1.146 - Node source, Node target)
1.147 + Node source, Node target)
1.148 : _graph(digraph), _capacity(&capacity), _source(source), _target(target),
1.149 - _flow(0), _local_flow(false), _pred(0), _tolerance(), _flow_value()
1.150 + _flow(0), _local_flow(false), _pred(0), _tolerance(), _flow_value()
1.151 {
1.152 LEMON_ASSERT(_source != _target,
1.153 "Flow source and target are the same nodes.");
1.154 @@ -244,8 +244,8 @@
1.155 /// \return <tt>(*this)</tt>
1.156 EdmondsKarp& flowMap(FlowMap& map) {
1.157 if (_local_flow) {
1.158 - delete _flow;
1.159 - _local_flow = false;
1.160 + delete _flow;
1.161 + _local_flow = false;
1.162 }
1.163 _flow = ↦
1.164 return *this;
1.165 @@ -276,7 +276,7 @@
1.166 EdmondsKarp& tolerance(const Tolerance& tolerance) {
1.167 _tolerance = tolerance;
1.168 return *this;
1.169 - }
1.170 + }
1.171
1.172 /// \brief Returns a const reference to the tolerance.
1.173 ///
1.174 @@ -284,14 +284,14 @@
1.175 /// the algorithm.
1.176 const Tolerance& tolerance() const {
1.177 return _tolerance;
1.178 - }
1.179 + }
1.180
1.181 /// \name Execution control
1.182 /// The simplest way to execute the algorithm is to use \ref run().\n
1.183 /// If you need better control on the initial solution or the execution,
1.184 /// you have to call one of the \ref init() functions first, then
1.185 /// \ref start() or multiple times the \ref augment() function.
1.186 -
1.187 +
1.188 ///@{
1.189
1.190 /// \brief Initializes the algorithm.
1.191 @@ -305,7 +305,7 @@
1.192 }
1.193 _flow_value = 0;
1.194 }
1.195 -
1.196 +
1.197 /// \brief Initializes the algorithm using the given flow map.
1.198 ///
1.199 /// Initializes the internal data structures and sets the initial
1.200 @@ -317,7 +317,7 @@
1.201 void init(const FlowMap& flowMap) {
1.202 createStructures();
1.203 for (ArcIt e(_graph); e != INVALID; ++e) {
1.204 - _flow->set(e, flowMap[e]);
1.205 + _flow->set(e, flowMap[e]);
1.206 }
1.207 _flow_value = 0;
1.208 for (OutArcIt jt(_graph, _source); jt != INVALID; ++jt) {
1.209 @@ -334,14 +334,14 @@
1.210 /// flow to the given \c flowMap. The \c flowMap should
1.211 /// contain a feasible flow, i.e. at each node excluding the source
1.212 /// and the target, the incoming flow should be equal to the
1.213 - /// outgoing flow.
1.214 + /// outgoing flow.
1.215 /// \return \c false when the given \c flowMap does not contain a
1.216 /// feasible flow.
1.217 template <typename FlowMap>
1.218 bool checkedInit(const FlowMap& flowMap) {
1.219 createStructures();
1.220 for (ArcIt e(_graph); e != INVALID; ++e) {
1.221 - _flow->set(e, flowMap[e]);
1.222 + _flow->set(e, flowMap[e]);
1.223 }
1.224 for (NodeIt it(_graph); it != INVALID; ++it) {
1.225 if (it == _source || it == _target) continue;
1.226 @@ -372,7 +372,7 @@
1.227 }
1.228
1.229 /// \brief Augments the solution along a shortest path.
1.230 - ///
1.231 + ///
1.232 /// Augments the solution along a shortest path. This function searches a
1.233 /// shortest path between the source and the target
1.234 /// in the residual digraph by the Bfs algoritm.
1.235 @@ -383,81 +383,81 @@
1.236 /// current flow is a feasible and optimal solution.
1.237 bool augment() {
1.238 for (NodeIt n(_graph); n != INVALID; ++n) {
1.239 - _pred->set(n, INVALID);
1.240 + _pred->set(n, INVALID);
1.241 }
1.242 -
1.243 +
1.244 int first = 0, last = 1;
1.245 -
1.246 +
1.247 _queue[0] = _source;
1.248 _pred->set(_source, OutArcIt(_graph, _source));
1.249
1.250 while (first != last && (*_pred)[_target] == INVALID) {
1.251 - Node n = _queue[first++];
1.252 -
1.253 - for (OutArcIt e(_graph, n); e != INVALID; ++e) {
1.254 - Value rem = (*_capacity)[e] - (*_flow)[e];
1.255 - Node t = _graph.target(e);
1.256 - if (_tolerance.positive(rem) && (*_pred)[t] == INVALID) {
1.257 - _pred->set(t, e);
1.258 - _queue[last++] = t;
1.259 - }
1.260 - }
1.261 - for (InArcIt e(_graph, n); e != INVALID; ++e) {
1.262 - Value rem = (*_flow)[e];
1.263 - Node t = _graph.source(e);
1.264 - if (_tolerance.positive(rem) && (*_pred)[t] == INVALID) {
1.265 - _pred->set(t, e);
1.266 - _queue[last++] = t;
1.267 - }
1.268 - }
1.269 + Node n = _queue[first++];
1.270 +
1.271 + for (OutArcIt e(_graph, n); e != INVALID; ++e) {
1.272 + Value rem = (*_capacity)[e] - (*_flow)[e];
1.273 + Node t = _graph.target(e);
1.274 + if (_tolerance.positive(rem) && (*_pred)[t] == INVALID) {
1.275 + _pred->set(t, e);
1.276 + _queue[last++] = t;
1.277 + }
1.278 + }
1.279 + for (InArcIt e(_graph, n); e != INVALID; ++e) {
1.280 + Value rem = (*_flow)[e];
1.281 + Node t = _graph.source(e);
1.282 + if (_tolerance.positive(rem) && (*_pred)[t] == INVALID) {
1.283 + _pred->set(t, e);
1.284 + _queue[last++] = t;
1.285 + }
1.286 + }
1.287 }
1.288
1.289 if ((*_pred)[_target] != INVALID) {
1.290 - Node n = _target;
1.291 - Arc e = (*_pred)[n];
1.292 + Node n = _target;
1.293 + Arc e = (*_pred)[n];
1.294
1.295 - Value prem = (*_capacity)[e] - (*_flow)[e];
1.296 - n = _graph.source(e);
1.297 - while (n != _source) {
1.298 - e = (*_pred)[n];
1.299 - if (_graph.target(e) == n) {
1.300 - Value rem = (*_capacity)[e] - (*_flow)[e];
1.301 - if (rem < prem) prem = rem;
1.302 - n = _graph.source(e);
1.303 - } else {
1.304 - Value rem = (*_flow)[e];
1.305 - if (rem < prem) prem = rem;
1.306 - n = _graph.target(e);
1.307 - }
1.308 - }
1.309 + Value prem = (*_capacity)[e] - (*_flow)[e];
1.310 + n = _graph.source(e);
1.311 + while (n != _source) {
1.312 + e = (*_pred)[n];
1.313 + if (_graph.target(e) == n) {
1.314 + Value rem = (*_capacity)[e] - (*_flow)[e];
1.315 + if (rem < prem) prem = rem;
1.316 + n = _graph.source(e);
1.317 + } else {
1.318 + Value rem = (*_flow)[e];
1.319 + if (rem < prem) prem = rem;
1.320 + n = _graph.target(e);
1.321 + }
1.322 + }
1.323
1.324 - n = _target;
1.325 - e = (*_pred)[n];
1.326 + n = _target;
1.327 + e = (*_pred)[n];
1.328
1.329 - _flow->set(e, (*_flow)[e] + prem);
1.330 - n = _graph.source(e);
1.331 - while (n != _source) {
1.332 - e = (*_pred)[n];
1.333 - if (_graph.target(e) == n) {
1.334 - _flow->set(e, (*_flow)[e] + prem);
1.335 - n = _graph.source(e);
1.336 - } else {
1.337 - _flow->set(e, (*_flow)[e] - prem);
1.338 - n = _graph.target(e);
1.339 - }
1.340 - }
1.341 + _flow->set(e, (*_flow)[e] + prem);
1.342 + n = _graph.source(e);
1.343 + while (n != _source) {
1.344 + e = (*_pred)[n];
1.345 + if (_graph.target(e) == n) {
1.346 + _flow->set(e, (*_flow)[e] + prem);
1.347 + n = _graph.source(e);
1.348 + } else {
1.349 + _flow->set(e, (*_flow)[e] - prem);
1.350 + n = _graph.target(e);
1.351 + }
1.352 + }
1.353
1.354 - _flow_value += prem;
1.355 - return true;
1.356 + _flow_value += prem;
1.357 + return true;
1.358 } else {
1.359 - return false;
1.360 + return false;
1.361 }
1.362 }
1.363
1.364 /// \brief Executes the algorithm
1.365 ///
1.366 /// Executes the algorithm by performing augmenting phases until the
1.367 - /// optimal solution is reached.
1.368 + /// optimal solution is reached.
1.369 /// \pre One of the \ref init() functions must be called before
1.370 /// using this function.
1.371 void start() {
1.372 @@ -465,10 +465,10 @@
1.373 }
1.374
1.375 /// \brief Runs the algorithm.
1.376 - ///
1.377 + ///
1.378 /// Runs the Edmonds-Karp algorithm.
1.379 /// \note ek.run() is just a shortcut of the following code.
1.380 - ///\code
1.381 + ///\code
1.382 /// ek.init();
1.383 /// ek.start();
1.384 ///\endcode
1.385 @@ -483,7 +483,7 @@
1.386 /// The result of the Edmonds-Karp algorithm can be obtained using these
1.387 /// functions.\n
1.388 /// Either \ref run() or \ref start() should be called before using them.
1.389 -
1.390 +
1.391 ///@{
1.392
1.393 /// \brief Returns the value of the maximum flow.
1.394 @@ -542,10 +542,10 @@
1.395 template <typename CutMap>
1.396 void minCutMap(CutMap& cutMap) const {
1.397 for (NodeIt n(_graph); n != INVALID; ++n) {
1.398 - cutMap.set(n, (*_pred)[n] != INVALID);
1.399 + cutMap.set(n, (*_pred)[n] != INVALID);
1.400 }
1.401 cutMap.set(_source, true);
1.402 - }
1.403 + }
1.404
1.405 /// @}
1.406