1.1 --- a/lemon/edmonds_karp.h Tue Nov 30 20:21:52 2010 +0100
1.2 +++ b/lemon/edmonds_karp.h Thu Feb 28 18:17:53 2013 +0100
1.3 @@ -45,19 +45,24 @@
1.4 /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
1.5 typedef CAP CapacityMap;
1.6
1.7 - /// \brief The type of the length of the arcs.
1.8 + /// \brief The type of the flow values.
1.9 typedef typename CapacityMap::Value Value;
1.10
1.11 - /// \brief The map type that stores the flow values.
1.12 + /// \brief The type of the map that stores the flow values.
1.13 ///
1.14 - /// The map type that stores the flow values.
1.15 + /// The type of the map that stores the flow values.
1.16 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.17 +#ifdef DOXYGEN
1.18 + typedef GR::ArcMap<Value> FlowMap;
1.19 +#else
1.20 typedef typename Digraph::template ArcMap<Value> FlowMap;
1.21 +#endif
1.22
1.23 /// \brief Instantiates a FlowMap.
1.24 ///
1.25 /// This function instantiates a \ref FlowMap.
1.26 - /// \param digraph The digraph, to which we would like to define the flow map.
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 return new FlowMap(digraph);
1.31 }
1.32 @@ -74,24 +79,28 @@
1.33 /// \brief Edmonds-Karp algorithms class.
1.34 ///
1.35 /// This class provides an implementation of the \e Edmonds-Karp \e
1.36 - /// algorithm producing a flow of maximum value in directed
1.37 - /// digraphs. The Edmonds-Karp algorithm is slower than the Preflow
1.38 - /// algorithm but it has an advantage of the step-by-step execution
1.39 + /// algorithm producing a \ref max_flow "flow of maximum value" in a
1.40 + /// digraph \ref clrs01algorithms, \ref amo93networkflows,
1.41 + /// \ref edmondskarp72theoretical.
1.42 + /// The Edmonds-Karp algorithm is slower than the Preflow
1.43 + /// algorithm, but it has an advantage of the step-by-step execution
1.44 /// control with feasible flow solutions. The \e source node, the \e
1.45 /// target node, the \e capacity of the arcs and the \e starting \e
1.46 /// flow value of the arcs should be passed to the algorithm
1.47 /// through the constructor.
1.48 ///
1.49 /// The time complexity of the algorithm is \f$ O(nm^2) \f$ in
1.50 - /// worst case. Always try the preflow algorithm instead of this if
1.51 + /// worst case. Always try the Preflow algorithm instead of this if
1.52 /// you just want to compute the optimal flow.
1.53 ///
1.54 - /// \param GR The digraph type the algorithm runs on.
1.55 - /// \param CAP The capacity map type.
1.56 - /// \param TR Traits class to set various data types used by
1.57 - /// the algorithm. The default traits class is \ref
1.58 - /// EdmondsKarpDefaultTraits. See \ref EdmondsKarpDefaultTraits for the
1.59 - /// documentation of a Edmonds-Karp traits class.
1.60 + /// \tparam GR The type of the digraph the algorithm runs on.
1.61 + /// \tparam CAP The type of the capacity map. The default map
1.62 + /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
1.63 + /// \tparam TR The traits class that defines various types used by the
1.64 + /// algorithm. By default, it is \ref EdmondsKarpDefaultTraits
1.65 + /// "EdmondsKarpDefaultTraits<GR, CAP>".
1.66 + /// In most cases, this parameter should not be set directly,
1.67 + /// consider to use the named template parameters instead.
1.68
1.69 #ifdef DOXYGEN
1.70 template <typename GR, typename CAP, typename TR>
1.71 @@ -103,12 +112,18 @@
1.72 class EdmondsKarp {
1.73 public:
1.74
1.75 + /// The \ref EdmondsKarpDefaultTraits "traits class" of the algorithm.
1.76 typedef TR Traits;
1.77 + /// The type of the digraph the algorithm runs on.
1.78 typedef typename Traits::Digraph Digraph;
1.79 + /// The type of the capacity map.
1.80 typedef typename Traits::CapacityMap CapacityMap;
1.81 + /// The type of the flow values.
1.82 typedef typename Traits::Value Value;
1.83
1.84 + /// The type of the flow map.
1.85 typedef typename Traits::FlowMap FlowMap;
1.86 + /// The type of the tolerance.
1.87 typedef typename Traits::Tolerance Tolerance;
1.88
1.89 private:
1.90 @@ -160,7 +175,7 @@
1.91 struct DefFlowMapTraits : public Traits {
1.92 typedef T FlowMap;
1.93 static FlowMap *createFlowMap(const Digraph&) {
1.94 - LEMON_ASSERT(false,"Uninitialized parameter.");
1.95 + LEMON_ASSERT(false, "FlowMap is not initialized");
1.96 return 0;
1.97 }
1.98 };
1.99 @@ -173,11 +188,10 @@
1.100 template <typename T>
1.101 struct DefFlowMap
1.102 : public EdmondsKarp<Digraph, CapacityMap, DefFlowMapTraits<T> > {
1.103 - typedef EdmondsKarp<Digraph, CapacityMap, DefFlowMapTraits<T> >
1.104 + typedef EdmondsKarp<Digraph, CapacityMap, DefFlowMapTraits<T> >
1.105 Create;
1.106 };
1.107
1.108 -
1.109 /// @}
1.110
1.111 protected:
1.112 @@ -198,7 +212,8 @@
1.113 : _graph(digraph), _capacity(&capacity), _source(source), _target(target),
1.114 _flow(0), _local_flow(false), _pred(0), _tolerance(), _flow_value()
1.115 {
1.116 - LEMON_ASSERT(_source != _target,"Flow source and target are the same nodes.");
1.117 + LEMON_ASSERT(_source != _target,
1.118 + "Flow source and target are the same nodes.");
1.119 }
1.120
1.121 /// \brief Destructor.
1.122 @@ -211,7 +226,7 @@
1.123 /// \brief Sets the capacity map.
1.124 ///
1.125 /// Sets the capacity map.
1.126 - /// \return \c (*this)
1.127 + /// \return <tt>(*this)</tt>
1.128 EdmondsKarp& capacityMap(const CapacityMap& map) {
1.129 _capacity = ↦
1.130 return *this;
1.131 @@ -220,7 +235,11 @@
1.132 /// \brief Sets the flow map.
1.133 ///
1.134 /// Sets the flow map.
1.135 - /// \return \c (*this)
1.136 + /// If you don't use this function before calling \ref run() or
1.137 + /// \ref init(), an instance will be allocated automatically.
1.138 + /// The destructor deallocates this automatically allocated map,
1.139 + /// of course.
1.140 + /// \return <tt>(*this)</tt>
1.141 EdmondsKarp& flowMap(FlowMap& map) {
1.142 if (_local_flow) {
1.143 delete _flow;
1.144 @@ -230,17 +249,10 @@
1.145 return *this;
1.146 }
1.147
1.148 - /// \brief Returns the flow map.
1.149 - ///
1.150 - /// \return The flow map.
1.151 - const FlowMap& flowMap() const {
1.152 - return *_flow;
1.153 - }
1.154 -
1.155 /// \brief Sets the source node.
1.156 ///
1.157 /// Sets the source node.
1.158 - /// \return \c (*this)
1.159 + /// \return <tt>(*this)</tt>
1.160 EdmondsKarp& source(const Node& node) {
1.161 _source = node;
1.162 return *this;
1.163 @@ -249,7 +261,7 @@
1.164 /// \brief Sets the target node.
1.165 ///
1.166 /// Sets the target node.
1.167 - /// \return \c (*this)
1.168 + /// \return <tt>(*this)</tt>
1.169 EdmondsKarp& target(const Node& node) {
1.170 _target = node;
1.171 return *this;
1.172 @@ -258,31 +270,32 @@
1.173 /// \brief Sets the tolerance used by algorithm.
1.174 ///
1.175 /// Sets the tolerance used by algorithm.
1.176 + /// \return <tt>(*this)</tt>
1.177 EdmondsKarp& tolerance(const Tolerance& tolerance) {
1.178 _tolerance = tolerance;
1.179 return *this;
1.180 }
1.181
1.182 - /// \brief Returns the tolerance used by algorithm.
1.183 + /// \brief Returns a const reference to the tolerance.
1.184 ///
1.185 - /// Returns the tolerance used by algorithm.
1.186 + /// Returns a const reference to the tolerance object used by
1.187 + /// the algorithm.
1.188 const Tolerance& tolerance() const {
1.189 return _tolerance;
1.190 }
1.191
1.192 /// \name Execution control
1.193 - /// The simplest way to execute the
1.194 - /// algorithm is to use the \c run() member functions.
1.195 - /// \n
1.196 - /// If you need more control on initial solution or
1.197 - /// execution then you have to call one \ref init() function and then
1.198 - /// the start() or multiple times the \c augment() member function.
1.199 + /// The simplest way to execute the algorithm is to use \ref run().\n
1.200 + /// If you need better control on the initial solution or the execution,
1.201 + /// you have to call one of the \ref init() functions first, then
1.202 + /// \ref start() or multiple times the \ref augment() function.
1.203
1.204 ///@{
1.205
1.206 - /// \brief Initializes the algorithm
1.207 - ///
1.208 - /// Sets the flow to empty flow.
1.209 + /// \brief Initializes the algorithm.
1.210 + ///
1.211 + /// Initializes the internal data structures and sets the initial
1.212 + /// flow to zero on each arc.
1.213 void init() {
1.214 createStructures();
1.215 for (ArcIt it(_graph); it != INVALID; ++it) {
1.216 @@ -291,11 +304,12 @@
1.217 _flow_value = 0;
1.218 }
1.219
1.220 - /// \brief Initializes the algorithm
1.221 - ///
1.222 - /// Initializes the flow to the \c flowMap. The \c flowMap should
1.223 - /// contain a feasible flow, ie. in each node excluding the source
1.224 - /// and the target the incoming flow should be equal to the
1.225 + /// \brief Initializes the algorithm using the given flow map.
1.226 + ///
1.227 + /// Initializes the internal data structures and sets the initial
1.228 + /// flow to the given \c flowMap. The \c flowMap should
1.229 + /// contain a feasible flow, i.e. at each node excluding the source
1.230 + /// and the target, the incoming flow should be equal to the
1.231 /// outgoing flow.
1.232 template <typename FlowMap>
1.233 void flowInit(const FlowMap& flowMap) {
1.234 @@ -312,13 +326,14 @@
1.235 }
1.236 }
1.237
1.238 - /// \brief Initializes the algorithm
1.239 - ///
1.240 - /// Initializes the flow to the \c flowMap. The \c flowMap should
1.241 - /// contain a feasible flow, ie. in each node excluding the source
1.242 - /// and the target the incoming flow should be equal to the
1.243 - /// outgoing flow.
1.244 - /// \return %False when the given flowMap does not contain
1.245 + /// \brief Initializes the algorithm using the given flow map.
1.246 + ///
1.247 + /// Initializes the internal data structures and sets the initial
1.248 + /// flow to the given \c flowMap. The \c flowMap should
1.249 + /// contain a feasible flow, i.e. at each node excluding the source
1.250 + /// and the target, the incoming flow should be equal to the
1.251 + /// outgoing flow.
1.252 + /// \return \c false when the given \c flowMap does not contain a
1.253 /// feasible flow.
1.254 template <typename FlowMap>
1.255 bool checkedFlowInit(const FlowMap& flowMap) {
1.256 @@ -354,15 +369,15 @@
1.257 return true;
1.258 }
1.259
1.260 - /// \brief Augment the solution on an arc shortest path.
1.261 + /// \brief Augments the solution along a shortest path.
1.262 ///
1.263 - /// Augment the solution on an arc shortest path. It searches an
1.264 - /// arc shortest path between the source and the target
1.265 - /// in the residual digraph by the bfs algoritm.
1.266 + /// Augments the solution along a shortest path. This function searches a
1.267 + /// shortest path between the source and the target
1.268 + /// in the residual digraph by the Bfs algoritm.
1.269 /// Then it increases the flow on this path with the minimal residual
1.270 - /// capacity on the path. If there is no such path it gives back
1.271 + /// capacity on the path. If there is no such path, it gives back
1.272 /// false.
1.273 - /// \return %False when the augmenting didn't success so the
1.274 + /// \return \c false when the augmenting did not success, i.e. the
1.275 /// current flow is a feasible and optimal solution.
1.276 bool augment() {
1.277 for (NodeIt n(_graph); n != INVALID; ++n) {
1.278 @@ -439,15 +454,18 @@
1.279
1.280 /// \brief Executes the algorithm
1.281 ///
1.282 - /// It runs augmenting phases until the optimal solution is reached.
1.283 + /// Executes the algorithm by performing augmenting phases until the
1.284 + /// optimal solution is reached.
1.285 + /// \pre One of the \ref init() functions must be called before
1.286 + /// using this function.
1.287 void start() {
1.288 while (augment()) {}
1.289 }
1.290
1.291 /// \brief Runs the algorithm.
1.292 ///
1.293 - /// It is just a shorthand for:
1.294 - ///
1.295 + /// Runs the Edmonds-Karp algorithm.
1.296 + /// \note ek.run() is just a shortcut of the following code.
1.297 ///\code
1.298 /// ek.init();
1.299 /// ek.start();
1.300 @@ -462,42 +480,63 @@
1.301 /// \name Query Functions
1.302 /// The result of the Edmonds-Karp algorithm can be obtained using these
1.303 /// functions.\n
1.304 - /// Before the use of these functions,
1.305 - /// either run() or start() must be called.
1.306 + /// Either \ref run() or \ref start() should be called before using them.
1.307
1.308 ///@{
1.309
1.310 /// \brief Returns the value of the maximum flow.
1.311 ///
1.312 - /// Returns the value of the maximum flow by returning the excess
1.313 - /// of the target node \c t.
1.314 -
1.315 + /// Returns the value of the maximum flow found by the algorithm.
1.316 + ///
1.317 + /// \pre Either \ref run() or \ref init() must be called before
1.318 + /// using this function.
1.319 Value flowValue() const {
1.320 return _flow_value;
1.321 }
1.322
1.323 -
1.324 - /// \brief Returns the flow on the arc.
1.325 + /// \brief Returns the flow value on the given arc.
1.326 ///
1.327 - /// Sets the \c flowMap to the flow on the arcs.
1.328 + /// Returns the flow value on the given arc.
1.329 + ///
1.330 + /// \pre Either \ref run() or \ref init() must be called before
1.331 + /// using this function.
1.332 Value flow(const Arc& arc) const {
1.333 return (*_flow)[arc];
1.334 }
1.335
1.336 - /// \brief Returns true when the node is on the source side of minimum cut.
1.337 + /// \brief Returns a const reference to the flow map.
1.338 ///
1.339 + /// Returns a const reference to the arc map storing the found flow.
1.340 + ///
1.341 + /// \pre Either \ref run() or \ref init() must be called before
1.342 + /// using this function.
1.343 + const FlowMap& flowMap() const {
1.344 + return *_flow;
1.345 + }
1.346
1.347 - /// Returns true when the node is on the source side of minimum
1.348 - /// cut.
1.349 -
1.350 + /// \brief Returns \c true when the node is on the source side of the
1.351 + /// minimum cut.
1.352 + ///
1.353 + /// Returns true when the node is on the source side of the found
1.354 + /// minimum cut.
1.355 + ///
1.356 + /// \pre Either \ref run() or \ref init() must be called before
1.357 + /// using this function.
1.358 bool minCut(const Node& node) const {
1.359 return ((*_pred)[node] != INVALID) or node == _source;
1.360 }
1.361
1.362 - /// \brief Returns a minimum value cut.
1.363 + /// \brief Gives back a minimum value cut.
1.364 ///
1.365 - /// Sets \c cutMap to the characteristic vector of a minimum value cut.
1.366 -
1.367 + /// Sets \c cutMap to the characteristic vector of a minimum value
1.368 + /// cut. \c cutMap should be a \ref concepts::WriteMap "writable"
1.369 + /// node map with \c bool (or convertible) value type.
1.370 + ///
1.371 + /// \note This function calls \ref minCut() for each node, so it runs in
1.372 + /// O(n) time.
1.373 + ///
1.374 + /// \pre Either \ref run() or \ref init() must be called before
1.375 + /// using this function.
1.376 template <typename CutMap>
1.377 void minCutMap(CutMap& cutMap) const {
1.378 for (NodeIt n(_graph); n != INVALID; ++n) {