COIN-OR::LEMON - Graph Library

Changeset 1225:6a8a688eacf6 in lemon


Ignore:
Timestamp:
02/28/13 18:17:53 (7 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Improve and fix API doc of EdmondsKarp? according to Preflow (#177)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/edmonds_karp.h

    r1224 r1225  
    4646    typedef CAP 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.
     55#ifdef DOXYGEN
     56    typedef GR::ArcMap<Value> FlowMap;
     57#else
    5558    typedef typename Digraph::template ArcMap<Value> FlowMap;
     59#endif
    5660
    5761    /// \brief Instantiates a FlowMap.
    5862    ///
    5963    /// 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.
    6166    static FlowMap* createFlowMap(const Digraph& digraph) {
    6267      return new FlowMap(digraph);
     
    7580  ///
    7681  /// This class provides an implementation of the \e Edmonds-Karp \e
    77   /// algorithm producing a flow of maximum value in directed
    78   /// digraphs. The Edmonds-Karp algorithm is slower than the Preflow
    79   /// algorithm but it has an advantage of the step-by-step 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 Edmonds-Karp algorithm is slower than the Preflow
     86  /// algorithm, but it has an advantage of the step-by-step execution
    8087  /// control with feasible flow solutions. The \e source node, the \e
    8188  /// target node, the \e capacity of the arcs and the \e starting \e
     
    8491  ///
    8592  /// The time complexity of the algorithm is \f$ O(nm^2) \f$ in
    86   /// worst case.  Always try the preflow algorithm instead of this if
     93  /// worst case. Always try the Preflow algorithm instead of this if
    8794  /// you just want to compute the optimal flow.
    8895  ///
    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 Edmonds-Karp 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.
    95104
    96105#ifdef DOXYGEN
     
    104113  public:
    105114
     115    /// The \ref EdmondsKarpDefaultTraits "traits class" of the algorithm.
    106116    typedef TR Traits;
     117    /// The type of the digraph the algorithm runs on.
    107118    typedef typename Traits::Digraph Digraph;
     119    /// The type of the capacity map.
    108120    typedef typename Traits::CapacityMap CapacityMap;
     121    /// The type of the flow values.
    109122    typedef typename Traits::Value Value;
    110123
     124    /// The type of the flow map.
    111125    typedef typename Traits::FlowMap FlowMap;
     126    /// The type of the tolerance.
    112127    typedef typename Traits::Tolerance Tolerance;
    113128
     
    161176      typedef T FlowMap;
    162177      static FlowMap *createFlowMap(const Digraph&) {
    163         LEMON_ASSERT(false,"Uninitialized parameter.");
     178        LEMON_ASSERT(false, "FlowMap is not initialized");
    164179        return 0;
    165180      }
     
    174189    struct DefFlowMap
    175190      : public EdmondsKarp<Digraph, CapacityMap, DefFlowMapTraits<T> > {
    176       typedef EdmondsKarp<Digraph, CapacityMap, DefFlowMapTraits<T> > 
     191      typedef EdmondsKarp<Digraph, CapacityMap, DefFlowMapTraits<T> >
    177192      Create;
    178193    };
    179 
    180194
    181195    /// @}
     
    199213        _flow(0), _local_flow(false), _pred(0), _tolerance(), _flow_value()
    200214    {
    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.");
    202217    }
    203218
     
    212227    ///
    213228    /// Sets the capacity map.
    214     /// \return \c (*this)
     229    /// \return <tt>(*this)</tt>
    215230    EdmondsKarp& capacityMap(const CapacityMap& map) {
    216231      _capacity = &map;
     
    221236    ///
    222237    /// 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>
    224243    EdmondsKarp& flowMap(FlowMap& map) {
    225244      if (_local_flow) {
     
    231250    }
    232251
    233     /// \brief Returns the flow map.
    234     ///
    235     /// \return The flow map.
    236     const FlowMap& flowMap() const {
    237       return *_flow;
    238     }
    239 
    240252    /// \brief Sets the source node.
    241253    ///
    242254    /// Sets the source node.
    243     /// \return \c (*this)
     255    /// \return <tt>(*this)</tt>
    244256    EdmondsKarp& source(const Node& node) {
    245257      _source = node;
     
    250262    ///
    251263    /// Sets the target node.
    252     /// \return \c (*this)
     264    /// \return <tt>(*this)</tt>
    253265    EdmondsKarp& target(const Node& node) {
    254266      _target = node;
     
    259271    ///
    260272    /// Sets the tolerance used by algorithm.
     273    /// \return <tt>(*this)</tt>
    261274    EdmondsKarp& tolerance(const Tolerance& tolerance) {
    262275      _tolerance = tolerance;
     
    264277    }
    265278
    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.
    269283    const Tolerance& tolerance() const {
    270284      return _tolerance;
     
    272286
    273287    /// \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.
    280292   
    281293    ///@{
    282294
    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.
    286299    void init() {
    287300      createStructures();
     
    292305    }
    293306   
    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
    299313    /// outgoing flow.
    300314    template <typename FlowMap>
     
    313327    }
    314328
    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
    322337    /// feasible flow.
    323338    template <typename FlowMap>
     
    355370    }
    356371
    357     /// \brief Augment the solution on an arc shortest path.
     372    /// \brief Augments the solution along a shortest path.
    358373    ///
    359     /// Augment the solution on an arc shortest path. It searches an
    360     /// arc shortest path between the source and the target
    361     /// 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.
    362377    /// 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 back
     378    /// capacity on the path. If there is no such path, it gives back
    364379    /// false.
    365     /// \return %False when the augmenting didn't success so the
     380    /// \return \c false when the augmenting did not success, i.e. the
    366381    /// current flow is a feasible and optimal solution.
    367382    bool augment() {
     
    440455    /// \brief Executes the algorithm
    441456    ///
    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.
    443461    void start() {
    444462      while (augment()) {}
     
    447465    /// \brief Runs the algorithm.
    448466    ///
    449     /// It is just a shorthand for:
    450     ///
     467    /// Runs the Edmonds-Karp algorithm.
     468    /// \note ek.run() is just a shortcut of the following code.
    451469    ///\code
    452470    /// ek.init();
     
    463481    /// The result of the Edmonds-Karp algorithm can be obtained using these
    464482    /// 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.
    467484   
    468485    ///@{
     
    470487    /// \brief Returns the value of the maximum flow.
    471488    ///
    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.
    475493    Value flowValue() const {
    476494      return _flow_value;
    477495    }
    478496
    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.
    483503    Value flow(const Arc& arc) const {
    484504      return (*_flow)[arc];
    485505    }
    486506
    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.
    493525    bool minCut(const Node& node) const {
    494526      return ((*_pred)[node] != INVALID) or node == _source;
    495527    }
    496528
    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.
    501540    template <typename CutMap>
    502541    void minCutMap(CutMap& cutMap) const {
Note: See TracChangeset for help on using the changeset viewer.