Changeset 1225:6a8a688eacf6 in lemon for lemon/edmonds_karp.h
 Timestamp:
 02/28/13 18:17:53 (11 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/edmonds_karp.h
r1224 r1225 46 46 typedef CAP CapacityMap; 47 47 48 /// \brief The type of the length of the arcs.48 /// \brief The type of the flow values. 49 49 typedef typename CapacityMap::Value Value; 50 50 51 /// \brief The map typethat stores the flow values.52 /// 53 /// The map type that stores the flow values.51 /// \brief The type of the map that stores the flow values. 52 /// 53 /// The type of the map that stores the flow values. 54 54 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 55 #ifdef DOXYGEN 56 typedef GR::ArcMap<Value> FlowMap; 57 #else 55 58 typedef typename Digraph::template ArcMap<Value> FlowMap; 59 #endif 56 60 57 61 /// \brief Instantiates a FlowMap. 58 62 /// 59 63 /// This function instantiates a \ref FlowMap. 60 /// \param digraph The digraph, to which we would like to define the flow map. 64 /// \param digraph The digraph for which we would like to define 65 /// the flow map. 61 66 static FlowMap* createFlowMap(const Digraph& digraph) { 62 67 return new FlowMap(digraph); … … 75 80 /// 76 81 /// This class provides an implementation of the \e EdmondsKarp \e 77 /// algorithm producing a flow of maximum value in directed 78 /// digraphs. The EdmondsKarp algorithm is slower than the Preflow 79 /// algorithm but it has an advantage of the stepbystep execution 82 /// algorithm producing a \ref max_flow "flow of maximum value" in a 83 /// digraph \ref clrs01algorithms, \ref amo93networkflows, 84 /// \ref edmondskarp72theoretical. 85 /// The EdmondsKarp algorithm is slower than the Preflow 86 /// algorithm, but it has an advantage of the stepbystep execution 80 87 /// control with feasible flow solutions. The \e source node, the \e 81 88 /// target node, the \e capacity of the arcs and the \e starting \e … … 84 91 /// 85 92 /// The time complexity of the algorithm is \f$ O(nm^2) \f$ in 86 /// worst case. Always try the preflow algorithm instead of this if93 /// worst case. Always try the Preflow algorithm instead of this if 87 94 /// you just want to compute the optimal flow. 88 95 /// 89 /// \param GR The digraph type the algorithm runs on. 90 /// \param CAP The capacity map type. 91 /// \param TR Traits class to set various data types used by 92 /// the algorithm. The default traits class is \ref 93 /// EdmondsKarpDefaultTraits. See \ref EdmondsKarpDefaultTraits for the 94 /// documentation of a EdmondsKarp traits class. 96 /// \tparam GR The type of the digraph the algorithm runs on. 97 /// \tparam CAP The type of the capacity map. The default map 98 /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 99 /// \tparam TR The traits class that defines various types used by the 100 /// algorithm. By default, it is \ref EdmondsKarpDefaultTraits 101 /// "EdmondsKarpDefaultTraits<GR, CAP>". 102 /// In most cases, this parameter should not be set directly, 103 /// consider to use the named template parameters instead. 95 104 96 105 #ifdef DOXYGEN … … 104 113 public: 105 114 115 /// The \ref EdmondsKarpDefaultTraits "traits class" of the algorithm. 106 116 typedef TR Traits; 117 /// The type of the digraph the algorithm runs on. 107 118 typedef typename Traits::Digraph Digraph; 119 /// The type of the capacity map. 108 120 typedef typename Traits::CapacityMap CapacityMap; 121 /// The type of the flow values. 109 122 typedef typename Traits::Value Value; 110 123 124 /// The type of the flow map. 111 125 typedef typename Traits::FlowMap FlowMap; 126 /// The type of the tolerance. 112 127 typedef typename Traits::Tolerance Tolerance; 113 128 … … 161 176 typedef T FlowMap; 162 177 static FlowMap *createFlowMap(const Digraph&) { 163 LEMON_ASSERT(false, "Uninitialized parameter.");178 LEMON_ASSERT(false, "FlowMap is not initialized"); 164 179 return 0; 165 180 } … … 174 189 struct DefFlowMap 175 190 : public EdmondsKarp<Digraph, CapacityMap, DefFlowMapTraits<T> > { 176 typedef EdmondsKarp<Digraph, CapacityMap, DefFlowMapTraits<T> > 191 typedef EdmondsKarp<Digraph, CapacityMap, DefFlowMapTraits<T> > 177 192 Create; 178 193 }; 179 180 194 181 195 /// @} … … 199 213 _flow(0), _local_flow(false), _pred(0), _tolerance(), _flow_value() 200 214 { 201 LEMON_ASSERT(_source != _target,"Flow source and target are the same nodes."); 215 LEMON_ASSERT(_source != _target, 216 "Flow source and target are the same nodes."); 202 217 } 203 218 … … 212 227 /// 213 228 /// Sets the capacity map. 214 /// \return \c (*this)229 /// \return <tt>(*this)</tt> 215 230 EdmondsKarp& capacityMap(const CapacityMap& map) { 216 231 _capacity = ↦ … … 221 236 /// 222 237 /// Sets the flow map. 223 /// \return \c (*this) 238 /// If you don't use this function before calling \ref run() or 239 /// \ref init(), an instance will be allocated automatically. 240 /// The destructor deallocates this automatically allocated map, 241 /// of course. 242 /// \return <tt>(*this)</tt> 224 243 EdmondsKarp& flowMap(FlowMap& map) { 225 244 if (_local_flow) { … … 231 250 } 232 251 233 /// \brief Returns the flow map.234 ///235 /// \return The flow map.236 const FlowMap& flowMap() const {237 return *_flow;238 }239 240 252 /// \brief Sets the source node. 241 253 /// 242 254 /// Sets the source node. 243 /// \return \c (*this)255 /// \return <tt>(*this)</tt> 244 256 EdmondsKarp& source(const Node& node) { 245 257 _source = node; … … 250 262 /// 251 263 /// Sets the target node. 252 /// \return \c (*this)264 /// \return <tt>(*this)</tt> 253 265 EdmondsKarp& target(const Node& node) { 254 266 _target = node; … … 259 271 /// 260 272 /// Sets the tolerance used by algorithm. 273 /// \return <tt>(*this)</tt> 261 274 EdmondsKarp& tolerance(const Tolerance& tolerance) { 262 275 _tolerance = tolerance; … … 264 277 } 265 278 266 /// \brief Returns the tolerance used by algorithm. 267 /// 268 /// Returns the tolerance used by algorithm. 279 /// \brief Returns a const reference to the tolerance. 280 /// 281 /// Returns a const reference to the tolerance object used by 282 /// the algorithm. 269 283 const Tolerance& tolerance() const { 270 284 return _tolerance; … … 272 286 273 287 /// \name Execution control 274 /// The simplest way to execute the 275 /// algorithm is to use the \c run() member functions. 276 /// \n 277 /// If you need more control on initial solution or 278 /// execution then you have to call one \ref init() function and then 279 /// the start() or multiple times the \c augment() member function. 288 /// The simplest way to execute the algorithm is to use \ref run().\n 289 /// If you need better control on the initial solution or the execution, 290 /// you have to call one of the \ref init() functions first, then 291 /// \ref start() or multiple times the \ref augment() function. 280 292 281 293 ///@{ 282 294 283 /// \brief Initializes the algorithm 284 /// 285 /// Sets the flow to empty flow. 295 /// \brief Initializes the algorithm. 296 /// 297 /// Initializes the internal data structures and sets the initial 298 /// flow to zero on each arc. 286 299 void init() { 287 300 createStructures(); … … 292 305 } 293 306 294 /// \brief Initializes the algorithm 295 /// 296 /// Initializes the flow to the \c flowMap. The \c flowMap should 297 /// contain a feasible flow, ie. in each node excluding the source 298 /// and the target the incoming flow should be equal to the 307 /// \brief Initializes the algorithm using the given flow map. 308 /// 309 /// Initializes the internal data structures and sets the initial 310 /// flow to the given \c flowMap. The \c flowMap should 311 /// contain a feasible flow, i.e. at each node excluding the source 312 /// and the target, the incoming flow should be equal to the 299 313 /// outgoing flow. 300 314 template <typename FlowMap> … … 313 327 } 314 328 315 /// \brief Initializes the algorithm 316 /// 317 /// Initializes the flow to the \c flowMap. The \c flowMap should 318 /// contain a feasible flow, ie. in each node excluding the source 319 /// and the target the incoming flow should be equal to the 320 /// outgoing flow. 321 /// \return %False when the given flowMap does not contain 329 /// \brief Initializes the algorithm using the given flow map. 330 /// 331 /// Initializes the internal data structures and sets the initial 332 /// flow to the given \c flowMap. The \c flowMap should 333 /// contain a feasible flow, i.e. at each node excluding the source 334 /// and the target, the incoming flow should be equal to the 335 /// outgoing flow. 336 /// \return \c false when the given \c flowMap does not contain a 322 337 /// feasible flow. 323 338 template <typename FlowMap> … … 355 370 } 356 371 357 /// \brief Augment the solution on an arcshortest path.372 /// \brief Augments the solution along a shortest path. 358 373 /// 359 /// Augment the solution on an arc shortest path. It searches an360 /// arcshortest path between the source and the target361 /// in the residual digraph by the bfs algoritm.374 /// Augments the solution along a shortest path. This function searches a 375 /// shortest path between the source and the target 376 /// in the residual digraph by the Bfs algoritm. 362 377 /// Then it increases the flow on this path with the minimal residual 363 /// capacity on the path. If there is no such path it gives back378 /// capacity on the path. If there is no such path, it gives back 364 379 /// false. 365 /// \return %False when the augmenting didn't success sothe380 /// \return \c false when the augmenting did not success, i.e. the 366 381 /// current flow is a feasible and optimal solution. 367 382 bool augment() { … … 440 455 /// \brief Executes the algorithm 441 456 /// 442 /// It runs augmenting phases until the optimal solution is reached. 457 /// Executes the algorithm by performing augmenting phases until the 458 /// optimal solution is reached. 459 /// \pre One of the \ref init() functions must be called before 460 /// using this function. 443 461 void start() { 444 462 while (augment()) {} … … 447 465 /// \brief Runs the algorithm. 448 466 /// 449 /// It is just a shorthand for:450 /// 467 /// Runs the EdmondsKarp algorithm. 468 /// \note ek.run() is just a shortcut of the following code. 451 469 ///\code 452 470 /// ek.init(); … … 463 481 /// The result of the EdmondsKarp algorithm can be obtained using these 464 482 /// functions.\n 465 /// Before the use of these functions, 466 /// either run() or start() must be called. 483 /// Either \ref run() or \ref start() should be called before using them. 467 484 468 485 ///@{ … … 470 487 /// \brief Returns the value of the maximum flow. 471 488 /// 472 /// Returns the value of the maximum flow by returning the excess 473 /// of the target node \c t. 474 489 /// Returns the value of the maximum flow found by the algorithm. 490 /// 491 /// \pre Either \ref run() or \ref init() must be called before 492 /// using this function. 475 493 Value flowValue() const { 476 494 return _flow_value; 477 495 } 478 496 479 480 /// \brief Returns the flow on the arc. 481 /// 482 /// Sets the \c flowMap to the flow on the arcs. 497 /// \brief Returns the flow value on the given arc. 498 /// 499 /// Returns the flow value on the given arc. 500 /// 501 /// \pre Either \ref run() or \ref init() must be called before 502 /// using this function. 483 503 Value flow(const Arc& arc) const { 484 504 return (*_flow)[arc]; 485 505 } 486 506 487 /// \brief Returns true when the node is on the source side of minimum cut. 488 /// 489 490 /// Returns true when the node is on the source side of minimum 491 /// cut. 492 507 /// \brief Returns a const reference to the flow map. 508 /// 509 /// Returns a const reference to the arc map storing the found flow. 510 /// 511 /// \pre Either \ref run() or \ref init() must be called before 512 /// using this function. 513 const FlowMap& flowMap() const { 514 return *_flow; 515 } 516 517 /// \brief Returns \c true when the node is on the source side of the 518 /// minimum cut. 519 /// 520 /// Returns true when the node is on the source side of the found 521 /// minimum cut. 522 /// 523 /// \pre Either \ref run() or \ref init() must be called before 524 /// using this function. 493 525 bool minCut(const Node& node) const { 494 526 return ((*_pred)[node] != INVALID) or node == _source; 495 527 } 496 528 497 /// \brief Returns a minimum value cut. 498 /// 499 /// Sets \c cutMap to the characteristic vector of a minimum value cut. 500 529 /// \brief Gives back a minimum value cut. 530 /// 531 /// Sets \c cutMap to the characteristic vector of a minimum value 532 /// cut. \c cutMap should be a \ref concepts::WriteMap "writable" 533 /// node map with \c bool (or convertible) value type. 534 /// 535 /// \note This function calls \ref minCut() for each node, so it runs in 536 /// O(n) time. 537 /// 538 /// \pre Either \ref run() or \ref init() must be called before 539 /// using this function. 501 540 template <typename CutMap> 502 541 void minCutMap(CutMap& cutMap) const {
Note: See TracChangeset
for help on using the changeset viewer.