1.1 --- a/lemon/preflow.h	Tue Dec 20 17:44:38 2011 +0100
     1.2 +++ b/lemon/preflow.h	Tue Dec 20 18:15:14 2011 +0100
     1.3 @@ -2,7 +2,7 @@
     1.4   *
     1.5   * This file is a part of LEMON, a generic C++ optimization library.
     1.6   *
     1.7 - * Copyright (C) 2003-2009
     1.8 + * Copyright (C) 2003-2010
     1.9   * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.10   * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.11   *
    1.12 @@ -52,7 +52,11 @@
    1.13      ///
    1.14      /// The type of the map that stores the flow values.
    1.15      /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    1.16 +#ifdef DOXYGEN
    1.17 +    typedef GR::ArcMap<Value> FlowMap;
    1.18 +#else
    1.19      typedef typename Digraph::template ArcMap<Value> FlowMap;
    1.20 +#endif
    1.21  
    1.22      /// \brief Instantiates a FlowMap.
    1.23      ///
    1.24 @@ -67,9 +71,12 @@
    1.25      ///
    1.26      /// The elevator type used by Preflow algorithm.
    1.27      ///
    1.28 -    /// \sa Elevator
    1.29 -    /// \sa LinkedElevator
    1.30 -    typedef LinkedElevator<Digraph, typename Digraph::Node> Elevator;
    1.31 +    /// \sa Elevator, LinkedElevator
    1.32 +#ifdef DOXYGEN
    1.33 +    typedef lemon::Elevator<GR, GR::Node> Elevator;
    1.34 +#else
    1.35 +    typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
    1.36 +#endif
    1.37  
    1.38      /// \brief Instantiates an Elevator.
    1.39      ///
    1.40 @@ -95,9 +102,10 @@
    1.41    ///
    1.42    /// This class provides an implementation of Goldberg-Tarjan's \e preflow
    1.43    /// \e push-relabel algorithm producing a \ref max_flow
    1.44 -  /// "flow of maximum value" in a digraph.
    1.45 +  /// "flow of maximum value" in a digraph \ref clrs01algorithms,
    1.46 +  /// \ref amo93networkflows, \ref goldberg88newapproach.
    1.47    /// The preflow algorithms are the fastest known maximum
    1.48 -  /// flow algorithms. The current implementation use a mixture of the
    1.49 +  /// flow algorithms. The current implementation uses a mixture of the
    1.50    /// \e "highest label" and the \e "bound decrease" heuristics.
    1.51    /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
    1.52    ///
    1.53 @@ -105,9 +113,17 @@
    1.54    /// the maximum flow value and the minimum cut is obtained. The
    1.55    /// second phase constructs a feasible maximum flow on each arc.
    1.56    ///
    1.57 +  /// \warning This implementation cannot handle infinite or very large
    1.58 +  /// capacities (e.g. the maximum value of \c CAP::Value).
    1.59 +  ///
    1.60    /// \tparam GR The type of the digraph the algorithm runs on.
    1.61    /// \tparam CAP The type of the capacity map. The default map
    1.62    /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    1.63 +  /// \tparam TR The traits class that defines various types used by the
    1.64 +  /// algorithm. By default, it is \ref PreflowDefaultTraits
    1.65 +  /// "PreflowDefaultTraits<GR, CAP>".
    1.66 +  /// In most cases, this parameter should not be set directly,
    1.67 +  /// consider to use the named template parameters instead.
    1.68  #ifdef DOXYGEN
    1.69    template <typename GR, typename CAP, typename TR>
    1.70  #else
    1.71 @@ -257,7 +273,7 @@
    1.72      /// The Elevator should have standard constructor interface to be
    1.73      /// able to automatically created by the algorithm (i.e. the
    1.74      /// digraph and the maximum level should be passed to it).
    1.75 -    /// However an external elevator object could also be passed to the
    1.76 +    /// However, an external elevator object could also be passed to the
    1.77      /// algorithm with the \ref elevator(Elevator&) "elevator()" function
    1.78      /// before calling \ref run() or \ref init().
    1.79      /// \sa SetElevator
    1.80 @@ -371,9 +387,10 @@
    1.81        return *_level;
    1.82      }
    1.83  
    1.84 -    /// \brief Sets the tolerance used by algorithm.
    1.85 +    /// \brief Sets the tolerance used by the algorithm.
    1.86      ///
    1.87 -    /// Sets the tolerance used by algorithm.
    1.88 +    /// Sets the tolerance object used by the algorithm.
    1.89 +    /// \return <tt>(*this)</tt>
    1.90      Preflow& tolerance(const Tolerance& tolerance) {
    1.91        _tolerance = tolerance;
    1.92        return *this;
    1.93 @@ -381,7 +398,8 @@
    1.94  
    1.95      /// \brief Returns a const reference to the tolerance.
    1.96      ///
    1.97 -    /// Returns a const reference to the tolerance.
    1.98 +    /// Returns a const reference to the tolerance object used by
    1.99 +    /// the algorithm.
   1.100      const Tolerance& tolerance() const {
   1.101        return _tolerance;
   1.102      }
   1.103 @@ -389,8 +407,8 @@
   1.104      /// \name Execution Control
   1.105      /// The simplest way to execute the preflow algorithm is to use
   1.106      /// \ref run() or \ref runMinCut().\n
   1.107 -    /// If you need more control on the initial solution or the execution,
   1.108 -    /// first you have to call one of the \ref init() functions, then
   1.109 +    /// If you need better control on the initial solution or the execution,
   1.110 +    /// you have to call one of the \ref init() functions first, then
   1.111      /// \ref startFirstPhase() and if you need it \ref startSecondPhase().
   1.112  
   1.113      ///@{