lemon-1.1: comparison lemon/preflow.h

equal deleted inserted replaced

-:b30313fcaa5f
+:492580ed5f8a
 namespace lemon {
 /// \brief Default traits class of Preflow class.
 ///
 /// Default traits class of Preflow class.
-/// \param _Graph Digraph type.
+/// \tparam _Digraph Digraph type.
-/// \param _CapacityMap Type of capacity map.
+/// \tparam _CapacityMap Capacity map type.
-template <typename _Graph, typename _CapacityMap>
+template <typename _Digraph, typename _CapacityMap>
 struct PreflowDefaultTraits {
-/// \brief The digraph type the algorithm runs on.
+/// \brief The type of the digraph the algorithm runs on.
-typedef _Graph Digraph;
+typedef _Digraph Digraph;
 /// \brief The type of the map that stores the arc capacities.
 ///
 /// The type of the map that stores the arc capacities.
 /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
 typedef _CapacityMap CapacityMap;
-/// \brief The type of the length of the arcs.
+/// \brief The type of the flow values.
 typedef typename CapacityMap::Value Value;
-/// \brief The map type that stores the flow values.
+/// \brief The type of the map that stores the flow values.
 ///
-/// The map type that stores the flow values.
+/// The type of the map that stores the flow values.
 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 typedef typename Digraph::template ArcMap<Value> FlowMap;
 /// \brief Instantiates a FlowMap.
 ///
 /// the flow map.
 static FlowMap* createFlowMap(const Digraph& digraph) {
 return new FlowMap(digraph);
 }
-/// \brief The eleavator type used by Preflow algorithm.
+/// \brief The elevator type used by Preflow algorithm.
 ///
 /// The elevator type used by Preflow algorithm.
 ///
 /// \sa Elevator
 /// \sa LinkedElevator
 typedef LinkedElevator<Digraph, typename Digraph::Node> Elevator;
 /// \brief Instantiates an Elevator.
 ///
-/// This function instantiates a \ref Elevator.
+/// This function instantiates an \ref Elevator.
 /// \param digraph The digraph, to which we would like to define
 /// the elevator.
 /// \param max_level The maximum level of the elevator.
 static Elevator* createElevator(const Digraph& digraph, int max_level) {
 return new Elevator(digraph, max_level);
 };
 /// \ingroup max_flow
 ///
-/// \brief %Preflow algorithms class.
+/// \brief %Preflow algorithm class.
 ///
-/// This class provides an implementation of the Goldberg's \e
+/// This class provides an implementation of Goldberg-Tarjan's \e preflow
-/// preflow \e algorithm producing a flow of maximum value in a
+/// \e push-relabel algorithm producing a flow of maximum value in a
-/// digraph. The preflow algorithms are the fastest known max
+/// digraph. The preflow algorithms are the fastest known maximum
 /// flow algorithms. The current implementation use a mixture of the
 /// \e "highest label" and the \e "bound decrease" heuristics.
 /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
 ///
-/// The algorithm consists from two phases. After the first phase
+/// The algorithm consists of two phases. After the first phase
-/// the maximal flow value and the minimum cut can be obtained. The
+/// the maximum flow value and the minimum cut is obtained. The
-/// second phase constructs the feasible maximum flow on each arc.
+/// second phase constructs a feasible maximum flow on each arc.
 ///
-/// \param _Graph The digraph type the algorithm runs on.
+/// \tparam _Digraph The type of the digraph the algorithm runs on.
-/// \param _CapacityMap The flow map type.
+/// \tparam _CapacityMap The type of the capacity map. The default map
-/// \param _Traits Traits class to set various data types used by
+/// type is \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>".
-/// the algorithm.  The default traits class is \ref
-/// PreflowDefaultTraits.  See \ref PreflowDefaultTraits for the
-/// documentation of a %Preflow traits class.
-///
-///\author Jacint Szabo and Balazs Dezso
 #ifdef DOXYGEN
-template <typename _Graph, typename _CapacityMap, typename _Traits>
+template <typename _Digraph, typename _CapacityMap, typename _Traits>
 #else
-template <typename _Graph,
+template <typename _Digraph,
-typename _CapacityMap = typename _Graph::template ArcMap<int>,
+typename _CapacityMap = typename _Digraph::template ArcMap<int>,
-typename _Traits = PreflowDefaultTraits<_Graph, _CapacityMap> >
+typename _Traits = PreflowDefaultTraits<_Digraph, _CapacityMap> >
 #endif
 class Preflow {
 public:
+///The \ref PreflowDefaultTraits "traits class" of the algorithm.
 typedef _Traits Traits;
+///The type of the digraph the algorithm runs on.
 typedef typename Traits::Digraph Digraph;
+///The type of the capacity map.
 typedef typename Traits::CapacityMap CapacityMap;
+///The type of the flow values.
 typedef typename Traits::Value Value;
+///The type of the flow map.
 typedef typename Traits::FlowMap FlowMap;
+///The type of the elevator.
 typedef typename Traits::Elevator Elevator;
+///The type of the tolerance.
 typedef typename Traits::Tolerance Tolerance;
 private:
 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 public:
 typedef Preflow Create;
-///\name Named template parameters
+///\name Named Template Parameters
 ///@{
 template <typename _FlowMap>
 struct SetFlowMapTraits : public Traits {
 /// \brief \ref named-templ-param "Named parameter" for setting
 /// FlowMap type
 ///
 /// \ref named-templ-param "Named parameter" for setting FlowMap
-/// type
+/// type.
 template <typename _FlowMap>
 struct SetFlowMap
 : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<_FlowMap> > {
 typedef Preflow<Digraph, CapacityMap,
 SetFlowMapTraits<_FlowMap> > Create;
 /// \brief \ref named-templ-param "Named parameter" for setting
 /// Elevator type
 ///
 /// \ref named-templ-param "Named parameter" for setting Elevator
-/// type
+/// type. If this named parameter is used, then an external
+/// elevator object must be passed to the algorithm using the
+/// \ref elevator(Elevator&) "elevator()" function before calling
+/// \ref run() or \ref init().
+/// \sa SetStandardElevator
 template <typename _Elevator>
 struct SetElevator
 : public Preflow<Digraph, CapacityMap, SetElevatorTraits<_Elevator> > {
 typedef Preflow<Digraph, CapacityMap,
 SetElevatorTraits<_Elevator> > Create;
 return new Elevator(digraph, max_level);
 }
 };
 /// \brief \ref named-templ-param "Named parameter" for setting
-/// Elevator type
+/// Elevator type with automatic allocation
 ///
 /// \ref named-templ-param "Named parameter" for setting Elevator
-/// type. The Elevator should be standard constructor interface, ie.
+/// type with automatic allocation.
-/// the digraph and the maximum level should be passed to it.
+/// The Elevator should have standard constructor interface to be
+/// able to automatically created by the algorithm (i.e. the
+/// digraph and the maximum level should be passed to it).
+/// However an external elevator object could also be passed to the
+/// algorithm with the \ref elevator(Elevator&) "elevator()" function
+/// before calling \ref run() or \ref init().
+/// \sa SetElevator
 template <typename _Elevator>
 struct SetStandardElevator
 : public Preflow<Digraph, CapacityMap,
 SetStandardElevatorTraits<_Elevator> > {
 typedef Preflow<Digraph, CapacityMap,
 /// \param digraph The digraph the algorithm runs on.
 /// \param capacity The capacity of the arcs.
 /// \param source The source node.
 /// \param target The target node.
 Preflow(const Digraph& digraph, const CapacityMap& capacity,
 Node source, Node target)
 : _graph(digraph), _capacity(&capacity),
 _node_num(0), _source(source), _target(target),
 _flow(0), _local_flow(false),
 _level(0), _local_level(false),
 _excess(0), _tolerance(), _phase() {}
-/// \brief Destrcutor.
+/// \brief Destructor.
 ///
 /// Destructor.
 ~Preflow() {
 destroyStructures();
 }
 /// \brief Sets the capacity map.
 ///
 /// Sets the capacity map.
-/// \return \c (*this)
+/// \return <tt>(*this)</tt>
 Preflow& capacityMap(const CapacityMap& map) {
 _capacity = &map;
 return *this;
 }
 /// \brief Sets the flow map.
 ///
 /// Sets the flow map.
-/// \return \c (*this)
+/// If you don't use this function before calling \ref run() or
+/// \ref init(), an instance will be allocated automatically.
+/// The destructor deallocates this automatically allocated map,
+/// of course.
+/// \return <tt>(*this)</tt>
 Preflow& flowMap(FlowMap& map) {
 if (_local_flow) {
 delete _flow;
 _local_flow = false;
 }
 _flow = &map;
 return *this;
 }
-/// \brief Returns the flow map.
+/// \brief Sets the source node.
 ///
-/// \return The flow map.
+/// Sets the source node.
-const FlowMap& flowMap() {
+/// \return <tt>(*this)</tt>
-return *_flow;
+Preflow& source(const Node& node) {
-}
+_source = node;
+return *this;
-/// \brief Sets the elevator.
+}
-///
-/// Sets the elevator.
+/// \brief Sets the target node.
-/// \return \c (*this)
+///
+/// Sets the target node.
+/// \return <tt>(*this)</tt>
+Preflow& target(const Node& node) {
+_target = node;
+return *this;
+}
+/// \brief Sets the elevator used by algorithm.
+///
+/// Sets the elevator used by algorithm.
+/// If you don't use this function before calling \ref run() or
+/// \ref init(), an instance will be allocated automatically.
+/// The destructor deallocates this automatically allocated elevator,
+/// of course.
+/// \return <tt>(*this)</tt>
 Preflow& elevator(Elevator& elevator) {
 if (_local_level) {
 delete _level;
 _local_level = false;
 }
 _level = &elevator;
 return *this;
 }
-/// \brief Returns the elevator.
+/// \brief Returns a const reference to the elevator.
 ///
-/// \return The elevator.
+/// Returns a const reference to the elevator.
+///
+/// \pre Either \ref run() or \ref init() must be called before
+/// using this function.
 const Elevator& elevator() {
 return *_level;
-}
-/// \brief Sets the source node.
-///
-/// Sets the source node.
-/// \return \c (*this)
-Preflow& source(const Node& node) {
-_source = node;
-return *this;
-}
-/// \brief Sets the target node.
-///
-/// Sets the target node.
-/// \return \c (*this)
-Preflow& target(const Node& node) {
-_target = node;
-return *this;
 }
 /// \brief Sets the tolerance used by algorithm.
 ///
 /// Sets the tolerance used by algorithm.
 Preflow& tolerance(const Tolerance& tolerance) const {
 _tolerance = tolerance;
 return *this;
 }
-/// \brief Returns the tolerance used by algorithm.
+/// \brief Returns a const reference to the tolerance.
 ///
-/// Returns the tolerance used by algorithm.
+/// Returns a const reference to the tolerance.
 const Tolerance& tolerance() const {
 return tolerance;
 }
-/// \name Execution control The simplest way to execute the
+/// \name Execution Control
-/// algorithm is to use one of the member functions called \c
+/// The simplest way to execute the preflow algorithm is to use
-/// run().
+/// \ref run() or \ref runMinCut().\n
-/// \n
+/// If you need more control on the initial solution or the execution,
-/// If you need more control on initial solution or
+/// first you have to call one of the \ref init() functions, then
-/// execution then you have to call one \ref init() function and then
+/// \ref startFirstPhase() and if you need it \ref startSecondPhase().
-/// the startFirstPhase() and if you need the startSecondPhase().
 ///@{
 /// \brief Initializes the internal data structures.
 ///
-/// Initializes the internal data structures.
+/// Initializes the internal data structures and sets the initial
-///
+/// flow to zero on each arc.
 void init() {
 createStructures();
 _phase = true;
 for (NodeIt n(_graph); n != INVALID; ++n) {
 }
 }
 }
 }
-/// \brief Initializes the internal data structures.
+/// \brief Initializes the internal data structures using the
+/// given flow map.
 ///
 /// Initializes the internal data structures and sets the initial
 /// flow to the given \c flowMap. The \c flowMap should contain a
-/// flow or at least a preflow, ie. in each node excluding the
+/// flow or at least a preflow, i.e. at each node excluding the
-/// target the incoming flow should greater or equal to the
+/// source node the incoming flow should greater or equal to the
 /// outgoing flow.
-/// \return %False when the given \c flowMap is not a preflow.
+/// \return \c false if the given \c flowMap is not a preflow.
 template <typename FlowMap>
 bool init(const FlowMap& flowMap) {
 createStructures();
 for (ArcIt e(_graph); e != INVALID; ++e) {
 /// the first phase. After the first phase the maximum flow value
 /// and a minimum value cut can already be computed, although a
 /// maximum flow is not yet obtained. So after calling this method
 /// \ref flowValue() returns the value of a maximum flow and \ref
 /// minCut() returns a minimum cut.
-/// \pre One of the \ref init() functions should be called.
+/// \pre One of the \ref init() functions must be called before
+/// using this function.
 void startFirstPhase() {
 _phase = true;
 Node n = _level->highestActive();
 int level = _level->highestActiveLevel();
 }
 /// \brief Starts the second phase of the preflow algorithm.
 ///
 /// The preflow algorithm consists of two phases, this method runs
-/// the second phase. After calling \ref init() and \ref
+/// the second phase. After calling one of the \ref init() functions
-/// startFirstPhase() and then \ref startSecondPhase(), \ref
+/// and \ref startFirstPhase() and then \ref startSecondPhase(),
-/// flowMap() return a maximum flow, \ref flowValue() returns the
+/// \ref flowMap() returns a maximum flow, \ref flowValue() returns the
 /// value of a maximum flow, \ref minCut() returns a minimum cut
-/// \pre The \ref init() and startFirstPhase() functions should be
+/// \pre One of the \ref init() functions and \ref startFirstPhase()
-/// called before.
+/// must be called before using this function.
 void startSecondPhase() {
 _phase = false;
 typename Digraph::template NodeMap<bool> reached(_graph);
 for (NodeIt n(_graph); n != INVALID; ++n) {
 }
 /// @}
 /// \name Query Functions
-/// The result of the %Preflow algorithm can be obtained using these
+/// The results of the preflow algorithm can be obtained using these
 /// functions.\n
-/// Before the use of these functions,
+/// Either one of the \ref run() "run*()" functions or one of the
-/// either run() or start() must be called.
+/// \ref startFirstPhase() "start*()" functions should be called
+/// before using them.
 ///@{
 /// \brief Returns the value of the maximum flow.
 ///
 /// Returns the value of the maximum flow by returning the excess
-/// of the target node \c t. This value equals to the value of
+/// of the target node. This value equals to the value of
-/// the maximum flow already after the first phase.
+/// the maximum flow already after the first phase of the algorithm.
+///
+/// \pre Either \ref run() or \ref init() must be called before
+/// using this function.
 Value flowValue() const {
 return (*_excess)[_target];
 }
-/// \brief Returns true when the node is on the source side of minimum cut.
+/// \brief Returns the flow on the given arc.
 ///
-/// Returns true when the node is on the source side of minimum
+/// Returns the flow on the given arc. This method can
-/// cut. This method can be called both after running \ref
+/// be called after the second phase of the algorithm.
+///
+/// \pre Either \ref run() or \ref init() must be called before
+/// using this function.
+Value flow(const Arc& arc) const {
+return (*_flow)[arc];
+}
+/// \brief Returns a const reference to the flow map.
+///
+/// Returns a const reference to the arc map storing the found flow.
+/// This method can be called after the second phase of the algorithm.
+///
+/// \pre Either \ref run() or \ref init() must be called before
+/// using this function.
+const FlowMap& flowMap() {
+return *_flow;
+}
+/// \brief Returns \c true when the node is on the source side of the
+/// minimum cut.
+///
+/// Returns true when the node is on the source side of the found
+/// minimum cut. This method can be called both after running \ref
 /// startFirstPhase() and \ref startSecondPhase().
+///
+/// \pre Either \ref run() or \ref init() must be called before
+/// using this function.
 bool minCut(const Node& node) const {
 return ((*_level)[node] == _level->maxLevel()) == _phase;
 }
-/// \brief Returns a minimum value cut.
+/// \brief Gives back a minimum value cut.
 ///
-/// Sets the \c cutMap to the characteristic vector of a minimum value
+/// Sets \c cutMap to the characteristic vector of a minimum value
-/// cut. This method can be called both after running \ref
+/// cut. \c cutMap should be a \ref concepts::WriteMap "writable"
-/// startFirstPhase() and \ref startSecondPhase(). The result after second
+/// node map with \c bool (or convertible) value type.
-/// phase could be changed slightly if inexact computation is used.
+///
-/// \pre The \c cutMap should be a bool-valued node-map.
+/// This method can be called both after running \ref startFirstPhase()
+/// and \ref startSecondPhase(). The result after the second phase
+/// could be slightly different if inexact computation is used.
+///
+/// \note This function calls \ref minCut() for each node, so it runs in
+/// \f$O(n)\f$ time.
+///
+/// \pre Either \ref run() or \ref init() must be called before
+/// using this function.
 template <typename CutMap>
 void minCutMap(CutMap& cutMap) const {
 for (NodeIt n(_graph); n != INVALID; ++n) {
 cutMap.set(n, minCut(n));
 }
 }
-/// \brief Returns the flow on the arc.
-///
-/// Sets the \c flowMap to the flow on the arcs. This method can
-/// be called after the second phase of algorithm.
-Value flow(const Arc& arc) const {
-return (*_flow)[arc];
-}
 /// @}
 };
 }
 #endif

changeset 448	9d9990909fc8
parent 392	db3251947eba
child 420	6a2a33ad261b