Changeset 393:37054b67d807 in lemon-1.2 for lemon
- Timestamp:
- 11/30/08 00:50:31 (16 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/preflow.h
r392 r393 32 32 /// 33 33 /// Default traits class of Preflow class. 34 /// \ param _Graph Digraph type.35 /// \ param _CapacityMap Type of capacity map.36 template <typename _ Graph, typename _CapacityMap>34 /// \tparam _Digraph Digraph type. 35 /// \tparam _CapacityMap Capacity map type. 36 template <typename _Digraph, typename _CapacityMap> 37 37 struct PreflowDefaultTraits { 38 38 39 /// \brief The digraph typethe algorithm runs on.40 typedef _ Graph Digraph;39 /// \brief The type of the digraph the algorithm runs on. 40 typedef _Digraph Digraph; 41 41 42 42 /// \brief The type of the map that stores the arc capacities. … … 46 46 typedef _CapacityMap 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 typethat 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 55 typedef typename Digraph::template ArcMap<Value> FlowMap; … … 64 64 } 65 65 66 /// \brief The ele avator type used by Preflow algorithm.66 /// \brief The elevator type used by Preflow algorithm. 67 67 /// 68 68 /// The elevator type used by Preflow algorithm. … … 74 74 /// \brief Instantiates an Elevator. 75 75 /// 76 /// This function instantiates a \ref Elevator.76 /// This function instantiates an \ref Elevator. 77 77 /// \param digraph The digraph, to which we would like to define 78 78 /// the elevator. … … 92 92 /// \ingroup max_flow 93 93 /// 94 /// \brief %Preflow algorithm sclass.94 /// \brief %Preflow algorithm class. 95 95 /// 96 /// This class provides an implementation of the Goldberg's \e97 /// preflow \ealgorithm producing a flow of maximum value in a98 /// digraph. The preflow algorithms are the fastest known max 96 /// This class provides an implementation of Goldberg-Tarjan's \e preflow 97 /// \e push-relabel algorithm producing a flow of maximum value in a 98 /// digraph. The preflow algorithms are the fastest known maximum 99 99 /// flow algorithms. The current implementation use a mixture of the 100 100 /// \e "highest label" and the \e "bound decrease" heuristics. 101 101 /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$. 102 102 /// 103 /// The algorithm consists fromtwo phases. After the first phase104 /// the maxim al flow value and the minimum cut can beobtained. The105 /// second phase constructs thefeasible maximum flow on each arc.103 /// The algorithm consists of two phases. After the first phase 104 /// the maximum flow value and the minimum cut is obtained. The 105 /// second phase constructs a feasible maximum flow on each arc. 106 106 /// 107 /// \param _Graph The digraph type the algorithm runs on. 108 /// \param _CapacityMap The flow map type. 109 /// \param _Traits Traits class to set various data types used by 110 /// the algorithm. The default traits class is \ref 111 /// PreflowDefaultTraits. See \ref PreflowDefaultTraits for the 112 /// documentation of a %Preflow traits class. 113 /// 114 ///\author Jacint Szabo and Balazs Dezso 107 /// \tparam _Digraph The type of the digraph the algorithm runs on. 108 /// \tparam _CapacityMap The type of the capacity map. The default map 109 /// type is \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>". 115 110 #ifdef DOXYGEN 116 template <typename _ Graph, typename _CapacityMap, typename _Traits>111 template <typename _Digraph, typename _CapacityMap, typename _Traits> 117 112 #else 118 template <typename _ Graph,119 typename _CapacityMap = typename _ Graph::template ArcMap<int>,120 typename _Traits = PreflowDefaultTraits<_ Graph, _CapacityMap> >113 template <typename _Digraph, 114 typename _CapacityMap = typename _Digraph::template ArcMap<int>, 115 typename _Traits = PreflowDefaultTraits<_Digraph, _CapacityMap> > 121 116 #endif 122 117 class Preflow { 123 118 public: 124 119 120 ///The \ref PreflowDefaultTraits "traits class" of the algorithm. 125 121 typedef _Traits Traits; 122 ///The type of the digraph the algorithm runs on. 126 123 typedef typename Traits::Digraph Digraph; 124 ///The type of the capacity map. 127 125 typedef typename Traits::CapacityMap CapacityMap; 126 ///The type of the flow values. 128 127 typedef typename Traits::Value Value; 129 128 129 ///The type of the flow map. 130 130 typedef typename Traits::FlowMap FlowMap; 131 ///The type of the elevator. 131 132 typedef typename Traits::Elevator Elevator; 133 ///The type of the tolerance. 132 134 typedef typename Traits::Tolerance Tolerance; 133 135 … … 189 191 typedef Preflow Create; 190 192 191 ///\name Named template parameters193 ///\name Named Template Parameters 192 194 193 195 ///@{ … … 206 208 /// 207 209 /// \ref named-templ-param "Named parameter" for setting FlowMap 208 /// type 210 /// type. 209 211 template <typename _FlowMap> 210 212 struct SetFlowMap … … 227 229 /// 228 230 /// \ref named-templ-param "Named parameter" for setting Elevator 229 /// type 231 /// type. If this named parameter is used, then an external 232 /// elevator object must be passed to the algorithm using the 233 /// \ref elevator(Elevator&) "elevator()" function before calling 234 /// \ref run() or \ref init(). 235 /// \sa SetStandardElevator 230 236 template <typename _Elevator> 231 237 struct SetElevator … … 244 250 245 251 /// \brief \ref named-templ-param "Named parameter" for setting 246 /// Elevator type 252 /// Elevator type with automatic allocation 247 253 /// 248 254 /// \ref named-templ-param "Named parameter" for setting Elevator 249 /// type. The Elevator should be standard constructor interface, ie. 250 /// the digraph and the maximum level should be passed to it. 255 /// type with automatic allocation. 256 /// The Elevator should have standard constructor interface to be 257 /// able to automatically created by the algorithm (i.e. the 258 /// digraph and the maximum level should be passed to it). 259 /// However an external elevator object could also be passed to the 260 /// algorithm with the \ref elevator(Elevator&) "elevator()" function 261 /// before calling \ref run() or \ref init(). 262 /// \sa SetElevator 251 263 template <typename _Elevator> 252 264 struct SetStandardElevator … … 274 286 /// \param target The target node. 275 287 Preflow(const Digraph& digraph, const CapacityMap& capacity, 276 288 Node source, Node target) 277 289 : _graph(digraph), _capacity(&capacity), 278 290 _node_num(0), _source(source), _target(target), … … 281 293 _excess(0), _tolerance(), _phase() {} 282 294 283 /// \brief Destr cutor.295 /// \brief Destructor. 284 296 /// 285 297 /// Destructor. … … 291 303 /// 292 304 /// Sets the capacity map. 293 /// \return \c (*this)305 /// \return <tt>(*this)</tt> 294 306 Preflow& capacityMap(const CapacityMap& map) { 295 307 _capacity = ↦ … … 300 312 /// 301 313 /// Sets the flow map. 302 /// \return \c (*this) 314 /// If you don't use this function before calling \ref run() or 315 /// \ref init(), an instance will be allocated automatically. 316 /// The destructor deallocates this automatically allocated map, 317 /// of course. 318 /// \return <tt>(*this)</tt> 303 319 Preflow& flowMap(FlowMap& map) { 304 320 if (_local_flow) { … … 310 326 } 311 327 312 /// \brief Returns the flow map. 313 /// 314 /// \return The flow map. 315 const FlowMap& flowMap() { 316 return *_flow; 317 } 318 319 /// \brief Sets the elevator. 320 /// 321 /// Sets the elevator. 322 /// \return \c (*this) 328 /// \brief Sets the source node. 329 /// 330 /// Sets the source node. 331 /// \return <tt>(*this)</tt> 332 Preflow& source(const Node& node) { 333 _source = node; 334 return *this; 335 } 336 337 /// \brief Sets the target node. 338 /// 339 /// Sets the target node. 340 /// \return <tt>(*this)</tt> 341 Preflow& target(const Node& node) { 342 _target = node; 343 return *this; 344 } 345 346 /// \brief Sets the elevator used by algorithm. 347 /// 348 /// Sets the elevator used by algorithm. 349 /// If you don't use this function before calling \ref run() or 350 /// \ref init(), an instance will be allocated automatically. 351 /// The destructor deallocates this automatically allocated elevator, 352 /// of course. 353 /// \return <tt>(*this)</tt> 323 354 Preflow& elevator(Elevator& elevator) { 324 355 if (_local_level) { … … 330 361 } 331 362 332 /// \brief Returns the elevator. 333 /// 334 /// \return The elevator. 363 /// \brief Returns a const reference to the elevator. 364 /// 365 /// Returns a const reference to the elevator. 366 /// 367 /// \pre Either \ref run() or \ref init() must be called before 368 /// using this function. 335 369 const Elevator& elevator() { 336 370 return *_level; 337 }338 339 /// \brief Sets the source node.340 ///341 /// Sets the source node.342 /// \return \c (*this)343 Preflow& source(const Node& node) {344 _source = node;345 return *this;346 }347 348 /// \brief Sets the target node.349 ///350 /// Sets the target node.351 /// \return \c (*this)352 Preflow& target(const Node& node) {353 _target = node;354 return *this;355 371 } 356 372 … … 363 379 } 364 380 365 /// \brief Returns the tolerance used by algorithm.366 /// 367 /// Returns the tolerance used by algorithm.381 /// \brief Returns a const reference to the tolerance. 382 /// 383 /// Returns a const reference to the tolerance. 368 384 const Tolerance& tolerance() const { 369 385 return tolerance; 370 386 } 371 387 372 /// \name Execution control The simplest way to execute the 373 /// algorithm is to use one of the member functions called \c 374 /// run(). 375 /// \n 376 /// If you need more control on initial solution or 377 /// execution then you have to call one \ref init() function and then 378 /// the startFirstPhase() and if you need the startSecondPhase(). 388 /// \name Execution Control 389 /// The simplest way to execute the preflow algorithm is to use 390 /// \ref run() or \ref runMinCut().\n 391 /// If you need more control on the initial solution or the execution, 392 /// first you have to call one of the \ref init() functions, then 393 /// \ref startFirstPhase() and if you need it \ref startSecondPhase(). 379 394 380 395 ///@{ … … 382 397 /// \brief Initializes the internal data structures. 383 398 /// 384 /// Initializes the internal data structures .385 /// 399 /// Initializes the internal data structures and sets the initial 400 /// flow to zero on each arc. 386 401 void init() { 387 402 createStructures(); … … 437 452 } 438 453 439 /// \brief Initializes the internal data structures. 454 /// \brief Initializes the internal data structures using the 455 /// given flow map. 440 456 /// 441 457 /// Initializes the internal data structures and sets the initial 442 458 /// flow to the given \c flowMap. The \c flowMap should contain a 443 /// flow or at least a preflow, i e. ineach node excluding the444 /// targetthe incoming flow should greater or equal to the459 /// flow or at least a preflow, i.e. at each node excluding the 460 /// source node the incoming flow should greater or equal to the 445 461 /// outgoing flow. 446 /// \return %False whenthe given \c flowMap is not a preflow.462 /// \return \c false if the given \c flowMap is not a preflow. 447 463 template <typename FlowMap> 448 464 bool init(const FlowMap& flowMap) { … … 537 553 /// \ref flowValue() returns the value of a maximum flow and \ref 538 554 /// minCut() returns a minimum cut. 539 /// \pre One of the \ref init() functions should be called. 555 /// \pre One of the \ref init() functions must be called before 556 /// using this function. 540 557 void startFirstPhase() { 541 558 _phase = true; … … 703 720 /// 704 721 /// The preflow algorithm consists of two phases, this method runs 705 /// the second phase. After calling \ref init() and \ref706 /// startFirstPhase() and then \ref startSecondPhase(), \ref707 /// flowMap() returna maximum flow, \ref flowValue() returns the722 /// the second phase. After calling one of the \ref init() functions 723 /// and \ref startFirstPhase() and then \ref startSecondPhase(), 724 /// \ref flowMap() returns a maximum flow, \ref flowValue() returns the 708 725 /// value of a maximum flow, \ref minCut() returns a minimum cut 709 /// \pre The \ref init() and startFirstPhase() functions should be710 /// called before.726 /// \pre One of the \ref init() functions and \ref startFirstPhase() 727 /// must be called before using this function. 711 728 void startSecondPhase() { 712 729 _phase = false; … … 864 881 865 882 /// \name Query Functions 866 /// The result of the %Preflow algorithm can be obtained using these883 /// The results of the preflow algorithm can be obtained using these 867 884 /// functions.\n 868 /// Before the use of these functions, 869 /// either run() or start() must be called. 885 /// Either one of the \ref run() "run*()" functions or one of the 886 /// \ref startFirstPhase() "start*()" functions should be called 887 /// before using them. 870 888 871 889 ///@{ … … 874 892 /// 875 893 /// Returns the value of the maximum flow by returning the excess 876 /// of the target node \c t. This value equals to the value of 877 /// the maximum flow already after the first phase. 894 /// of the target node. This value equals to the value of 895 /// the maximum flow already after the first phase of the algorithm. 896 /// 897 /// \pre Either \ref run() or \ref init() must be called before 898 /// using this function. 878 899 Value flowValue() const { 879 900 return (*_excess)[_target]; 880 901 } 881 902 882 /// \brief Returns true when the node is on the source side of minimum cut. 883 /// 884 /// Returns true when the node is on the source side of minimum 885 /// cut. This method can be called both after running \ref 903 /// \brief Returns the flow on the given arc. 904 /// 905 /// Returns the flow on the given arc. This method can 906 /// be called after the second phase of the algorithm. 907 /// 908 /// \pre Either \ref run() or \ref init() must be called before 909 /// using this function. 910 Value flow(const Arc& arc) const { 911 return (*_flow)[arc]; 912 } 913 914 /// \brief Returns a const reference to the flow map. 915 /// 916 /// Returns a const reference to the arc map storing the found flow. 917 /// This method can be called after the second phase of the algorithm. 918 /// 919 /// \pre Either \ref run() or \ref init() must be called before 920 /// using this function. 921 const FlowMap& flowMap() { 922 return *_flow; 923 } 924 925 /// \brief Returns \c true when the node is on the source side of the 926 /// minimum cut. 927 /// 928 /// Returns true when the node is on the source side of the found 929 /// minimum cut. This method can be called both after running \ref 886 930 /// startFirstPhase() and \ref startSecondPhase(). 931 /// 932 /// \pre Either \ref run() or \ref init() must be called before 933 /// using this function. 887 934 bool minCut(const Node& node) const { 888 935 return ((*_level)[node] == _level->maxLevel()) == _phase; 889 936 } 890 937 891 /// \brief Returns a minimum value cut. 892 /// 893 /// Sets the \c cutMap to the characteristic vector of a minimum value 894 /// cut. This method can be called both after running \ref 895 /// startFirstPhase() and \ref startSecondPhase(). The result after second 896 /// phase could be changed slightly if inexact computation is used. 897 /// \pre The \c cutMap should be a bool-valued node-map. 938 /// \brief Gives back a minimum value cut. 939 /// 940 /// Sets \c cutMap to the characteristic vector of a minimum value 941 /// cut. \c cutMap should be a \ref concepts::WriteMap "writable" 942 /// node map with \c bool (or convertible) value type. 943 /// 944 /// This method can be called both after running \ref startFirstPhase() 945 /// and \ref startSecondPhase(). The result after the second phase 946 /// could be slightly different if inexact computation is used. 947 /// 948 /// \note This function calls \ref minCut() for each node, so it runs in 949 /// \f$O(n)\f$ time. 950 /// 951 /// \pre Either \ref run() or \ref init() must be called before 952 /// using this function. 898 953 template <typename CutMap> 899 954 void minCutMap(CutMap& cutMap) const { … … 903 958 } 904 959 905 /// \brief Returns the flow on the arc.906 ///907 /// Sets the \c flowMap to the flow on the arcs. This method can908 /// be called after the second phase of algorithm.909 Value flow(const Arc& arc) const {910 return (*_flow)[arc];911 }912 913 960 /// @} 914 961 };
Note: See TracChangeset
for help on using the changeset viewer.