COIN-OR::LEMON - Graph Library

Changeset 408:37054b67d807 in lemon for lemon/preflow.h


Ignore:
Timestamp:
11/30/08 00:50:31 (11 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Many doc improvements for Preflow (#176)

  • More precise doc for members.
  • Add doc for public types.
  • Hide the doc of the traits class parameter.
  • Removing \author comments.
  • Use \tparam for template parameters.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/preflow.h

    r407 r408  
    3232  ///
    3333  /// 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>
    3737  struct PreflowDefaultTraits {
    3838
    39     /// \brief The digraph type the algorithm runs on.
    40     typedef _Graph Digraph;
     39    /// \brief The type of the digraph the algorithm runs on.
     40    typedef _Digraph Digraph;
    4141
    4242    /// \brief The type of the map that stores the arc capacities.
     
    4646    typedef _CapacityMap CapacityMap;
    4747
    48     /// \brief The type of the length of the arcs.
     48    /// \brief The type of the flow values.
    4949    typedef typename CapacityMap::Value Value;
    5050
    51     /// \brief The map type that 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.
    5454    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    5555    typedef typename Digraph::template ArcMap<Value> FlowMap;
     
    6464    }
    6565
    66     /// \brief The eleavator type used by Preflow algorithm.
     66    /// \brief The elevator type used by Preflow algorithm.
    6767    ///
    6868    /// The elevator type used by Preflow algorithm.
     
    7474    /// \brief Instantiates an Elevator.
    7575    ///
    76     /// This function instantiates a \ref Elevator.
     76    /// This function instantiates an \ref Elevator.
    7777    /// \param digraph The digraph, to which we would like to define
    7878    /// the elevator.
     
    9292  /// \ingroup max_flow
    9393  ///
    94   /// \brief %Preflow algorithms class.
     94  /// \brief %Preflow algorithm class.
    9595  ///
    96   /// This class provides an implementation of the Goldberg's \e
    97   /// preflow \e algorithm producing a flow of maximum value in a
    98   /// 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
    9999  /// flow algorithms. The current implementation use a mixture of the
    100100  /// \e "highest label" and the \e "bound decrease" heuristics.
    101101  /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
    102102  ///
    103   /// The algorithm consists from two phases. After the first phase
    104   /// the maximal flow value and the minimum cut can be obtained. The
    105   /// second phase constructs the feasible 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.
    106106  ///
    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>".
    115110#ifdef DOXYGEN
    116   template <typename _Graph, typename _CapacityMap, typename _Traits>
     111  template <typename _Digraph, typename _CapacityMap, typename _Traits>
    117112#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> >
    121116#endif
    122117  class Preflow {
    123118  public:
    124119
     120    ///The \ref PreflowDefaultTraits "traits class" of the algorithm.
    125121    typedef _Traits Traits;
     122    ///The type of the digraph the algorithm runs on.
    126123    typedef typename Traits::Digraph Digraph;
     124    ///The type of the capacity map.
    127125    typedef typename Traits::CapacityMap CapacityMap;
     126    ///The type of the flow values.
    128127    typedef typename Traits::Value Value;
    129128
     129    ///The type of the flow map.
    130130    typedef typename Traits::FlowMap FlowMap;
     131    ///The type of the elevator.
    131132    typedef typename Traits::Elevator Elevator;
     133    ///The type of the tolerance.
    132134    typedef typename Traits::Tolerance Tolerance;
    133135
     
    189191    typedef Preflow Create;
    190192
    191     ///\name Named template parameters
     193    ///\name Named Template Parameters
    192194
    193195    ///@{
     
    206208    ///
    207209    /// \ref named-templ-param "Named parameter" for setting FlowMap
    208     /// type
     210    /// type.
    209211    template <typename _FlowMap>
    210212    struct SetFlowMap
     
    227229    ///
    228230    /// \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
    230236    template <typename _Elevator>
    231237    struct SetElevator
     
    244250
    245251    /// \brief \ref named-templ-param "Named parameter" for setting
    246     /// Elevator type
     252    /// Elevator type with automatic allocation
    247253    ///
    248254    /// \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
    251263    template <typename _Elevator>
    252264    struct SetStandardElevator
     
    274286    /// \param target The target node.
    275287    Preflow(const Digraph& digraph, const CapacityMap& capacity,
    276                Node source, Node target)
     288            Node source, Node target)
    277289      : _graph(digraph), _capacity(&capacity),
    278290        _node_num(0), _source(source), _target(target),
     
    281293        _excess(0), _tolerance(), _phase() {}
    282294
    283     /// \brief Destrcutor.
     295    /// \brief Destructor.
    284296    ///
    285297    /// Destructor.
     
    291303    ///
    292304    /// Sets the capacity map.
    293     /// \return \c (*this)
     305    /// \return <tt>(*this)</tt>
    294306    Preflow& capacityMap(const CapacityMap& map) {
    295307      _capacity = &map;
     
    300312    ///
    301313    /// 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>
    303319    Preflow& flowMap(FlowMap& map) {
    304320      if (_local_flow) {
     
    310326    }
    311327
    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>
    323354    Preflow& elevator(Elevator& elevator) {
    324355      if (_local_level) {
     
    330361    }
    331362
    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.
    335369    const Elevator& elevator() {
    336370      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;
    355371    }
    356372
     
    363379    }
    364380
    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.
    368384    const Tolerance& tolerance() const {
    369385      return tolerance;
    370386    }
    371387
    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().
    379394
    380395    ///@{
     
    382397    /// \brief Initializes the internal data structures.
    383398    ///
    384     /// Initializes the internal data structures.
    385     ///
     399    /// Initializes the internal data structures and sets the initial
     400    /// flow to zero on each arc.
    386401    void init() {
    387402      createStructures();
     
    437452    }
    438453
    439     /// \brief Initializes the internal data structures.
     454    /// \brief Initializes the internal data structures using the
     455    /// given flow map.
    440456    ///
    441457    /// Initializes the internal data structures and sets the initial
    442458    /// flow to the given \c flowMap. The \c flowMap should contain a
    443     /// flow or at least a preflow, ie. in each node excluding the
    444     /// target the incoming flow should greater or equal to the
     459    /// 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
    445461    /// outgoing flow.
    446     /// \return %False when the given \c flowMap is not a preflow.
     462    /// \return \c false if the given \c flowMap is not a preflow.
    447463    template <typename FlowMap>
    448464    bool init(const FlowMap& flowMap) {
     
    537553    /// \ref flowValue() returns the value of a maximum flow and \ref
    538554    /// 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.
    540557    void startFirstPhase() {
    541558      _phase = true;
     
    703720    ///
    704721    /// The preflow algorithm consists of two phases, this method runs
    705     /// the second phase. After calling \ref init() and \ref
    706     /// startFirstPhase() and then \ref startSecondPhase(), \ref
    707     /// flowMap() return a maximum flow, \ref flowValue() returns the
     722    /// 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
    708725    /// value of a maximum flow, \ref minCut() returns a minimum cut
    709     /// \pre The \ref init() and startFirstPhase() functions should be
    710     /// called before.
     726    /// \pre One of the \ref init() functions and \ref startFirstPhase()
     727    /// must be called before using this function.
    711728    void startSecondPhase() {
    712729      _phase = false;
     
    864881
    865882    /// \name Query Functions
    866     /// The result of the %Preflow algorithm can be obtained using these
     883    /// The results of the preflow algorithm can be obtained using these
    867884    /// 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.
    870888
    871889    ///@{
     
    874892    ///
    875893    /// 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.
    878899    Value flowValue() const {
    879900      return (*_excess)[_target];
    880901    }
    881902
    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
    886930    /// startFirstPhase() and \ref startSecondPhase().
     931    ///
     932    /// \pre Either \ref run() or \ref init() must be called before
     933    /// using this function.
    887934    bool minCut(const Node& node) const {
    888935      return ((*_level)[node] == _level->maxLevel()) == _phase;
    889936    }
    890937
    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.
    898953    template <typename CutMap>
    899954    void minCutMap(CutMap& cutMap) const {
     
    903958    }
    904959
    905     /// \brief Returns the flow on the arc.
    906     ///
    907     /// Sets the \c flowMap to the flow on the arcs. This method can
    908     /// be called after the second phase of algorithm.
    909     Value flow(const Arc& arc) const {
    910       return (*_flow)[arc];
    911     }
    912 
    913960    /// @}
    914961  };
Note: See TracChangeset for help on using the changeset viewer.