Various doc improvements
authorPeter Kovacs <kpeter@inf.elte.hu>
Mon, 23 Feb 2009 12:10:26 +0100
changeset 5039605e051942f
parent 440 88ed40ad0d4f
child 534 6d3a9eec82b4
Various doc improvements
lemon/bfs.h
lemon/bits/array_map.h
lemon/bits/vector_map.h
lemon/circulation.h
lemon/concepts/graph_components.h
lemon/dfs.h
lemon/dijkstra.h
lemon/preflow.h
     1.1 --- a/lemon/bfs.h	Thu Jan 01 00:00:00 2009 +0100
     1.2 +++ b/lemon/bfs.h	Mon Feb 23 12:10:26 2009 +0100
     1.3 @@ -49,11 +49,11 @@
     1.4      ///arcs of the shortest paths.
     1.5      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     1.6      typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
     1.7 -    ///Instantiates a PredMap.
     1.8 +    ///Instantiates a \c PredMap.
     1.9  
    1.10 -    ///This function instantiates a PredMap.
    1.11 +    ///This function instantiates a \ref PredMap.
    1.12      ///\param g is the digraph, to which we would like to define the
    1.13 -    ///PredMap.
    1.14 +    ///\ref PredMap.
    1.15      static PredMap *createPredMap(const Digraph &g)
    1.16      {
    1.17        return new PredMap(g);
    1.18 @@ -64,11 +64,11 @@
    1.19      ///The type of the map that indicates which nodes are processed.
    1.20      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1.21      typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    1.22 -    ///Instantiates a ProcessedMap.
    1.23 +    ///Instantiates a \c ProcessedMap.
    1.24  
    1.25 -    ///This function instantiates a ProcessedMap.
    1.26 +    ///This function instantiates a \ref ProcessedMap.
    1.27      ///\param g is the digraph, to which
    1.28 -    ///we would like to define the ProcessedMap
    1.29 +    ///we would like to define the \ref ProcessedMap
    1.30  #ifdef DOXYGEN
    1.31      static ProcessedMap *createProcessedMap(const Digraph &g)
    1.32  #else
    1.33 @@ -83,11 +83,11 @@
    1.34      ///The type of the map that indicates which nodes are reached.
    1.35      ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    1.36      typedef typename Digraph::template NodeMap<bool> ReachedMap;
    1.37 -    ///Instantiates a ReachedMap.
    1.38 +    ///Instantiates a \c ReachedMap.
    1.39  
    1.40 -    ///This function instantiates a ReachedMap.
    1.41 +    ///This function instantiates a \ref ReachedMap.
    1.42      ///\param g is the digraph, to which
    1.43 -    ///we would like to define the ReachedMap.
    1.44 +    ///we would like to define the \ref ReachedMap.
    1.45      static ReachedMap *createReachedMap(const Digraph &g)
    1.46      {
    1.47        return new ReachedMap(g);
    1.48 @@ -98,11 +98,11 @@
    1.49      ///The type of the map that stores the distances of the nodes.
    1.50      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1.51      typedef typename Digraph::template NodeMap<int> DistMap;
    1.52 -    ///Instantiates a DistMap.
    1.53 +    ///Instantiates a \c DistMap.
    1.54  
    1.55 -    ///This function instantiates a DistMap.
    1.56 +    ///This function instantiates a \ref DistMap.
    1.57      ///\param g is the digraph, to which we would like to define the
    1.58 -    ///DistMap.
    1.59 +    ///\ref DistMap.
    1.60      static DistMap *createDistMap(const Digraph &g)
    1.61      {
    1.62        return new DistMap(g);
    1.63 @@ -221,10 +221,10 @@
    1.64        }
    1.65      };
    1.66      ///\brief \ref named-templ-param "Named parameter" for setting
    1.67 -    ///PredMap type.
    1.68 +    ///\c PredMap type.
    1.69      ///
    1.70      ///\ref named-templ-param "Named parameter" for setting
    1.71 -    ///PredMap type.
    1.72 +    ///\c PredMap type.
    1.73      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1.74      template <class T>
    1.75      struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
    1.76 @@ -241,10 +241,10 @@
    1.77        }
    1.78      };
    1.79      ///\brief \ref named-templ-param "Named parameter" for setting
    1.80 -    ///DistMap type.
    1.81 +    ///\c DistMap type.
    1.82      ///
    1.83      ///\ref named-templ-param "Named parameter" for setting
    1.84 -    ///DistMap type.
    1.85 +    ///\c DistMap type.
    1.86      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1.87      template <class T>
    1.88      struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
    1.89 @@ -261,10 +261,10 @@
    1.90        }
    1.91      };
    1.92      ///\brief \ref named-templ-param "Named parameter" for setting
    1.93 -    ///ReachedMap type.
    1.94 +    ///\c ReachedMap type.
    1.95      ///
    1.96      ///\ref named-templ-param "Named parameter" for setting
    1.97 -    ///ReachedMap type.
    1.98 +    ///\c ReachedMap type.
    1.99      ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
   1.100      template <class T>
   1.101      struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
   1.102 @@ -281,10 +281,10 @@
   1.103        }
   1.104      };
   1.105      ///\brief \ref named-templ-param "Named parameter" for setting
   1.106 -    ///ProcessedMap type.
   1.107 +    ///\c ProcessedMap type.
   1.108      ///
   1.109      ///\ref named-templ-param "Named parameter" for setting
   1.110 -    ///ProcessedMap type.
   1.111 +    ///\c ProcessedMap type.
   1.112      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   1.113      template <class T>
   1.114      struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
   1.115 @@ -300,10 +300,10 @@
   1.116        }
   1.117      };
   1.118      ///\brief \ref named-templ-param "Named parameter" for setting
   1.119 -    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   1.120 +    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   1.121      ///
   1.122      ///\ref named-templ-param "Named parameter" for setting
   1.123 -    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   1.124 +    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   1.125      ///If you don't set it explicitly, it will be automatically allocated.
   1.126      struct SetStandardProcessedMap :
   1.127        public Bfs< Digraph, SetStandardProcessedMapTraits > {
   1.128 @@ -1194,9 +1194,9 @@
   1.129    ///
   1.130    /// This class defines the interface of the BfsVisit events, and
   1.131    /// it could be the base of a real visitor class.
   1.132 -  template <typename _Digraph>
   1.133 +  template <typename GR>
   1.134    struct BfsVisitor {
   1.135 -    typedef _Digraph Digraph;
   1.136 +    typedef GR Digraph;
   1.137      typedef typename Digraph::Arc Arc;
   1.138      typedef typename Digraph::Node Node;
   1.139      /// \brief Called for the source node(s) of the BFS.
   1.140 @@ -1224,9 +1224,9 @@
   1.141      void examine(const Arc& arc) {}
   1.142    };
   1.143  #else
   1.144 -  template <typename _Digraph>
   1.145 +  template <typename GR>
   1.146    struct BfsVisitor {
   1.147 -    typedef _Digraph Digraph;
   1.148 +    typedef GR Digraph;
   1.149      typedef typename Digraph::Arc Arc;
   1.150      typedef typename Digraph::Node Node;
   1.151      void start(const Node&) {}
   1.152 @@ -1254,12 +1254,12 @@
   1.153    /// \brief Default traits class of BfsVisit class.
   1.154    ///
   1.155    /// Default traits class of BfsVisit class.
   1.156 -  /// \tparam _Digraph The type of the digraph the algorithm runs on.
   1.157 -  template<class _Digraph>
   1.158 +  /// \tparam GR The type of the digraph the algorithm runs on.
   1.159 +  template<class GR>
   1.160    struct BfsVisitDefaultTraits {
   1.161  
   1.162      /// \brief The type of the digraph the algorithm runs on.
   1.163 -    typedef _Digraph Digraph;
   1.164 +    typedef GR Digraph;
   1.165  
   1.166      /// \brief The type of the map that indicates which nodes are reached.
   1.167      ///
   1.168 @@ -1280,12 +1280,12 @@
   1.169  
   1.170    /// \ingroup search
   1.171    ///
   1.172 -  /// \brief %BFS algorithm class with visitor interface.
   1.173 +  /// \brief BFS algorithm class with visitor interface.
   1.174    ///
   1.175 -  /// This class provides an efficient implementation of the %BFS algorithm
   1.176 +  /// This class provides an efficient implementation of the BFS algorithm
   1.177    /// with visitor interface.
   1.178    ///
   1.179 -  /// The %BfsVisit class provides an alternative interface to the Bfs
   1.180 +  /// The BfsVisit class provides an alternative interface to the Bfs
   1.181    /// class. It works with callback mechanism, the BfsVisit object calls
   1.182    /// the member functions of the \c Visitor class on every BFS event.
   1.183    ///
   1.184 @@ -1294,37 +1294,37 @@
   1.185    /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()
   1.186    /// instead.
   1.187    ///
   1.188 -  /// \tparam _Digraph The type of the digraph the algorithm runs on.
   1.189 -  /// The default value is
   1.190 -  /// \ref ListDigraph. The value of _Digraph is not used directly by
   1.191 -  /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
   1.192 -  /// \tparam _Visitor The Visitor type that is used by the algorithm.
   1.193 -  /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
   1.194 +  /// \tparam GR The type of the digraph the algorithm runs on.
   1.195 +  /// The default type is \ref ListDigraph.
   1.196 +  /// The value of GR is not used directly by \ref BfsVisit,
   1.197 +  /// it is only passed to \ref BfsVisitDefaultTraits.
   1.198 +  /// \tparam VS The Visitor type that is used by the algorithm.
   1.199 +  /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which
   1.200    /// does not observe the BFS events. If you want to observe the BFS
   1.201    /// events, you should implement your own visitor class.
   1.202 -  /// \tparam _Traits Traits class to set various data types used by the
   1.203 +  /// \tparam TR Traits class to set various data types used by the
   1.204    /// algorithm. The default traits class is
   1.205 -  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
   1.206 +  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
   1.207    /// See \ref BfsVisitDefaultTraits for the documentation of
   1.208    /// a BFS visit traits class.
   1.209  #ifdef DOXYGEN
   1.210 -  template <typename _Digraph, typename _Visitor, typename _Traits>
   1.211 +  template <typename GR, typename VS, typename TR>
   1.212  #else
   1.213 -  template <typename _Digraph = ListDigraph,
   1.214 -            typename _Visitor = BfsVisitor<_Digraph>,
   1.215 -            typename _Traits = BfsVisitDefaultTraits<_Digraph> >
   1.216 +  template <typename GR = ListDigraph,
   1.217 +            typename VS = BfsVisitor<GR>,
   1.218 +            typename TR = BfsVisitDefaultTraits<GR> >
   1.219  #endif
   1.220    class BfsVisit {
   1.221    public:
   1.222  
   1.223      ///The traits class.
   1.224 -    typedef _Traits Traits;
   1.225 +    typedef TR Traits;
   1.226  
   1.227      ///The type of the digraph the algorithm runs on.
   1.228      typedef typename Traits::Digraph Digraph;
   1.229  
   1.230      ///The visitor type used by the algorithm.
   1.231 -    typedef _Visitor Visitor;
   1.232 +    typedef VS Visitor;
   1.233  
   1.234      ///The type of the map that indicates which nodes are reached.
   1.235      typedef typename Traits::ReachedMap ReachedMap;
     2.1 --- a/lemon/bits/array_map.h	Thu Jan 01 00:00:00 2009 +0100
     2.2 +++ b/lemon/bits/array_map.h	Mon Feb 23 12:10:26 2009 +0100
     2.3 @@ -135,7 +135,7 @@
     2.4  
     2.5      // \brief Template assign operator.
     2.6      //
     2.7 -    // The given parameter should be conform to the ReadMap
     2.8 +    // The given parameter should conform to the ReadMap
     2.9      // concecpt and could be indiced by the current item set of
    2.10      // the NodeMap. In this case the value for each item
    2.11      // is assigned by the value of the given ReadMap.
     3.1 --- a/lemon/bits/vector_map.h	Thu Jan 01 00:00:00 2009 +0100
     3.2 +++ b/lemon/bits/vector_map.h	Mon Feb 23 12:10:26 2009 +0100
     3.3 @@ -124,7 +124,7 @@
     3.4  
     3.5      // \brief Template assign operator.
     3.6      //
     3.7 -    // The given parameter should be conform to the ReadMap
     3.8 +    // The given parameter should conform to the ReadMap
     3.9      // concecpt and could be indiced by the current item set of
    3.10      // the NodeMap. In this case the value for each item
    3.11      // is assigned by the value of the given ReadMap.
     4.1 --- a/lemon/circulation.h	Thu Jan 01 00:00:00 2009 +0100
     4.2 +++ b/lemon/circulation.h	Mon Feb 23 12:10:26 2009 +0100
     4.3 @@ -31,30 +31,30 @@
     4.4    /// \brief Default traits class of Circulation class.
     4.5    ///
     4.6    /// Default traits class of Circulation class.
     4.7 -  /// \tparam _Diraph Digraph type.
     4.8 -  /// \tparam _LCapMap Lower bound capacity map type.
     4.9 -  /// \tparam _UCapMap Upper bound capacity map type.
    4.10 -  /// \tparam _DeltaMap Delta map type.
    4.11 -  template <typename _Diraph, typename _LCapMap,
    4.12 -            typename _UCapMap, typename _DeltaMap>
    4.13 +  /// \tparam GR Digraph type.
    4.14 +  /// \tparam LM Lower bound capacity map type.
    4.15 +  /// \tparam UM Upper bound capacity map type.
    4.16 +  /// \tparam DM Delta map type.
    4.17 +  template <typename GR, typename LM,
    4.18 +            typename UM, typename DM>
    4.19    struct CirculationDefaultTraits {
    4.20  
    4.21      /// \brief The type of the digraph the algorithm runs on.
    4.22 -    typedef _Diraph Digraph;
    4.23 +    typedef GR Digraph;
    4.24  
    4.25      /// \brief The type of the map that stores the circulation lower
    4.26      /// bound.
    4.27      ///
    4.28      /// The type of the map that stores the circulation lower bound.
    4.29      /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    4.30 -    typedef _LCapMap LCapMap;
    4.31 +    typedef LM LCapMap;
    4.32  
    4.33      /// \brief The type of the map that stores the circulation upper
    4.34      /// bound.
    4.35      ///
    4.36      /// The type of the map that stores the circulation upper bound.
    4.37      /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    4.38 -    typedef _UCapMap UCapMap;
    4.39 +    typedef UM UCapMap;
    4.40  
    4.41      /// \brief The type of the map that stores the lower bound for
    4.42      /// the supply of the nodes.
    4.43 @@ -62,7 +62,7 @@
    4.44      /// The type of the map that stores the lower bound for the supply
    4.45      /// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap"
    4.46      /// concept.
    4.47 -    typedef _DeltaMap DeltaMap;
    4.48 +    typedef DM DeltaMap;
    4.49  
    4.50      /// \brief The type of the flow values.
    4.51      typedef typename DeltaMap::Value Value;
    4.52 @@ -137,35 +137,33 @@
    4.53       \ref min_cost_flow "minimum cost flow" problem can be calculated
    4.54       in this way.
    4.55  
    4.56 -     \tparam _Digraph The type of the digraph the algorithm runs on.
    4.57 -     \tparam _LCapMap The type of the lower bound capacity map. The default
    4.58 -     map type is \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>".
    4.59 -     \tparam _UCapMap The type of the upper bound capacity map. The default
    4.60 -     map type is \c _LCapMap.
    4.61 -     \tparam _DeltaMap The type of the map that stores the lower bound
    4.62 +     \tparam GR The type of the digraph the algorithm runs on.
    4.63 +     \tparam LM The type of the lower bound capacity map. The default
    4.64 +     map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    4.65 +     \tparam UM The type of the upper bound capacity map. The default
    4.66 +     map type is \c LM.
    4.67 +     \tparam DM The type of the map that stores the lower bound
    4.68       for the supply of the nodes. The default map type is
    4.69 -     \c _Digraph::ArcMap<_UCapMap::Value>.
    4.70 +     \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
    4.71    */
    4.72  #ifdef DOXYGEN
    4.73 -template< typename _Digraph,
    4.74 -          typename _LCapMap,
    4.75 -          typename _UCapMap,
    4.76 -          typename _DeltaMap,
    4.77 -          typename _Traits >
    4.78 +template< typename GR,
    4.79 +          typename LM,
    4.80 +          typename UM,
    4.81 +          typename DM,
    4.82 +          typename TR >
    4.83  #else
    4.84 -template< typename _Digraph,
    4.85 -          typename _LCapMap = typename _Digraph::template ArcMap<int>,
    4.86 -          typename _UCapMap = _LCapMap,
    4.87 -          typename _DeltaMap = typename _Digraph::
    4.88 -                               template NodeMap<typename _UCapMap::Value>,
    4.89 -          typename _Traits=CirculationDefaultTraits<_Digraph, _LCapMap,
    4.90 -                                                    _UCapMap, _DeltaMap> >
    4.91 +template< typename GR,
    4.92 +          typename LM = typename GR::template ArcMap<int>,
    4.93 +          typename UM = LM,
    4.94 +          typename DM = typename GR::template NodeMap<typename UM::Value>,
    4.95 +          typename TR = CirculationDefaultTraits<GR, LM, UM, DM> >
    4.96  #endif
    4.97    class Circulation {
    4.98    public:
    4.99  
   4.100      ///The \ref CirculationDefaultTraits "traits class" of the algorithm.
   4.101 -    typedef _Traits Traits;
   4.102 +    typedef TR Traits;
   4.103      ///The type of the digraph the algorithm runs on.
   4.104      typedef typename Traits::Digraph Digraph;
   4.105      ///The type of the flow values.
     5.1 --- a/lemon/concepts/graph_components.h	Thu Jan 01 00:00:00 2009 +0100
     5.2 +++ b/lemon/concepts/graph_components.h	Mon Feb 23 12:10:26 2009 +0100
     5.3 @@ -114,7 +114,7 @@
     5.4      /// \brief An empty base directed graph class.
     5.5      ///
     5.6      /// This class provides the minimal set of features needed for a
     5.7 -    /// directed graph structure. All digraph concepts have to be
     5.8 +    /// directed graph structure. All digraph concepts have to
     5.9      /// conform to this base directed graph. It just provides types
    5.10      /// for nodes and arcs and functions to get the source and the
    5.11      /// target of the arcs.
    5.12 @@ -179,7 +179,7 @@
    5.13      ///
    5.14      /// This class provides the minimal set of features needed for an
    5.15      /// undirected graph structure. All undirected graph concepts have
    5.16 -    /// to be conform to this base graph. It just provides types for
    5.17 +    /// to conform to this base graph. It just provides types for
    5.18      /// nodes, arcs and edges and functions to get the
    5.19      /// source and the target of the arcs and edges,
    5.20      /// conversion from arcs to edges and function to get
    5.21 @@ -294,7 +294,7 @@
    5.22      ///
    5.23      /// This class provides beside the core digraph features
    5.24      /// core id functions for the digraph structure.
    5.25 -    /// The most of the base digraphs should be conform to this concept.
    5.26 +    /// The most of the base digraphs should conform to this concept.
    5.27      /// The id's are unique and immutable.
    5.28      template <typename _Base = BaseDigraphComponent>
    5.29      class IDableDigraphComponent : public _Base {
    5.30 @@ -372,7 +372,7 @@
    5.31      ///
    5.32      /// This class provides beside the core undirected graph features
    5.33      /// core id functions for the undirected graph structure.  The
    5.34 -    /// most of the base undirected graphs should be conform to this
    5.35 +    /// most of the base undirected graphs should conform to this
    5.36      /// concept.  The id's are unique and immutable.
    5.37      template <typename _Base = BaseGraphComponent>
    5.38      class IDableGraphComponent : public IDableDigraphComponent<_Base> {
     6.1 --- a/lemon/dfs.h	Thu Jan 01 00:00:00 2009 +0100
     6.2 +++ b/lemon/dfs.h	Mon Feb 23 12:10:26 2009 +0100
     6.3 @@ -49,11 +49,11 @@
     6.4      ///arcs of the %DFS paths.
     6.5      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     6.6      typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
     6.7 -    ///Instantiates a PredMap.
     6.8 +    ///Instantiates a \c PredMap.
     6.9  
    6.10 -    ///This function instantiates a PredMap.
    6.11 +    ///This function instantiates a \ref PredMap.
    6.12      ///\param g is the digraph, to which we would like to define the
    6.13 -    ///PredMap.
    6.14 +    ///\ref PredMap.
    6.15      static PredMap *createPredMap(const Digraph &g)
    6.16      {
    6.17        return new PredMap(g);
    6.18 @@ -64,11 +64,11 @@
    6.19      ///The type of the map that indicates which nodes are processed.
    6.20      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    6.21      typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    6.22 -    ///Instantiates a ProcessedMap.
    6.23 +    ///Instantiates a \c ProcessedMap.
    6.24  
    6.25 -    ///This function instantiates a ProcessedMap.
    6.26 +    ///This function instantiates a \ref ProcessedMap.
    6.27      ///\param g is the digraph, to which
    6.28 -    ///we would like to define the ProcessedMap
    6.29 +    ///we would like to define the \ref ProcessedMap.
    6.30  #ifdef DOXYGEN
    6.31      static ProcessedMap *createProcessedMap(const Digraph &g)
    6.32  #else
    6.33 @@ -83,11 +83,11 @@
    6.34      ///The type of the map that indicates which nodes are reached.
    6.35      ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    6.36      typedef typename Digraph::template NodeMap<bool> ReachedMap;
    6.37 -    ///Instantiates a ReachedMap.
    6.38 +    ///Instantiates a \c ReachedMap.
    6.39  
    6.40 -    ///This function instantiates a ReachedMap.
    6.41 +    ///This function instantiates a \ref ReachedMap.
    6.42      ///\param g is the digraph, to which
    6.43 -    ///we would like to define the ReachedMap.
    6.44 +    ///we would like to define the \ref ReachedMap.
    6.45      static ReachedMap *createReachedMap(const Digraph &g)
    6.46      {
    6.47        return new ReachedMap(g);
    6.48 @@ -98,11 +98,11 @@
    6.49      ///The type of the map that stores the distances of the nodes.
    6.50      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    6.51      typedef typename Digraph::template NodeMap<int> DistMap;
    6.52 -    ///Instantiates a DistMap.
    6.53 +    ///Instantiates a \c DistMap.
    6.54  
    6.55 -    ///This function instantiates a DistMap.
    6.56 +    ///This function instantiates a \ref DistMap.
    6.57      ///\param g is the digraph, to which we would like to define the
    6.58 -    ///DistMap.
    6.59 +    ///\ref DistMap.
    6.60      static DistMap *createDistMap(const Digraph &g)
    6.61      {
    6.62        return new DistMap(g);
    6.63 @@ -220,10 +220,10 @@
    6.64        }
    6.65      };
    6.66      ///\brief \ref named-templ-param "Named parameter" for setting
    6.67 -    ///PredMap type.
    6.68 +    ///\c PredMap type.
    6.69      ///
    6.70      ///\ref named-templ-param "Named parameter" for setting
    6.71 -    ///PredMap type.
    6.72 +    ///\c PredMap type.
    6.73      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    6.74      template <class T>
    6.75      struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
    6.76 @@ -240,10 +240,10 @@
    6.77        }
    6.78      };
    6.79      ///\brief \ref named-templ-param "Named parameter" for setting
    6.80 -    ///DistMap type.
    6.81 +    ///\c DistMap type.
    6.82      ///
    6.83      ///\ref named-templ-param "Named parameter" for setting
    6.84 -    ///DistMap type.
    6.85 +    ///\c DistMap type.
    6.86      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    6.87      template <class T>
    6.88      struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
    6.89 @@ -260,10 +260,10 @@
    6.90        }
    6.91      };
    6.92      ///\brief \ref named-templ-param "Named parameter" for setting
    6.93 -    ///ReachedMap type.
    6.94 +    ///\c ReachedMap type.
    6.95      ///
    6.96      ///\ref named-templ-param "Named parameter" for setting
    6.97 -    ///ReachedMap type.
    6.98 +    ///\c ReachedMap type.
    6.99      ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
   6.100      template <class T>
   6.101      struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
   6.102 @@ -280,10 +280,10 @@
   6.103        }
   6.104      };
   6.105      ///\brief \ref named-templ-param "Named parameter" for setting
   6.106 -    ///ProcessedMap type.
   6.107 +    ///\c ProcessedMap type.
   6.108      ///
   6.109      ///\ref named-templ-param "Named parameter" for setting
   6.110 -    ///ProcessedMap type.
   6.111 +    ///\c ProcessedMap type.
   6.112      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   6.113      template <class T>
   6.114      struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
   6.115 @@ -298,10 +298,10 @@
   6.116        }
   6.117      };
   6.118      ///\brief \ref named-templ-param "Named parameter" for setting
   6.119 -    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   6.120 +    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   6.121      ///
   6.122      ///\ref named-templ-param "Named parameter" for setting
   6.123 -    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   6.124 +    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   6.125      ///If you don't set it explicitly, it will be automatically allocated.
   6.126      struct SetStandardProcessedMap :
   6.127        public Dfs< Digraph, SetStandardProcessedMapTraits > {
   6.128 @@ -1126,9 +1126,9 @@
   6.129    ///
   6.130    /// This class defines the interface of the DfsVisit events, and
   6.131    /// it could be the base of a real visitor class.
   6.132 -  template <typename _Digraph>
   6.133 +  template <typename GR>
   6.134    struct DfsVisitor {
   6.135 -    typedef _Digraph Digraph;
   6.136 +    typedef GR Digraph;
   6.137      typedef typename Digraph::Arc Arc;
   6.138      typedef typename Digraph::Node Node;
   6.139      /// \brief Called for the source node of the DFS.
   6.140 @@ -1164,9 +1164,9 @@
   6.141      void backtrack(const Arc& arc) {}
   6.142    };
   6.143  #else
   6.144 -  template <typename _Digraph>
   6.145 +  template <typename GR>
   6.146    struct DfsVisitor {
   6.147 -    typedef _Digraph Digraph;
   6.148 +    typedef GR Digraph;
   6.149      typedef typename Digraph::Arc Arc;
   6.150      typedef typename Digraph::Node Node;
   6.151      void start(const Node&) {}
   6.152 @@ -1199,11 +1199,11 @@
   6.153    ///
   6.154    /// Default traits class of DfsVisit class.
   6.155    /// \tparam _Digraph The type of the digraph the algorithm runs on.
   6.156 -  template<class _Digraph>
   6.157 +  template<class GR>
   6.158    struct DfsVisitDefaultTraits {
   6.159  
   6.160      /// \brief The type of the digraph the algorithm runs on.
   6.161 -    typedef _Digraph Digraph;
   6.162 +    typedef GR Digraph;
   6.163  
   6.164      /// \brief The type of the map that indicates which nodes are reached.
   6.165      ///
   6.166 @@ -1224,12 +1224,12 @@
   6.167  
   6.168    /// \ingroup search
   6.169    ///
   6.170 -  /// \brief %DFS algorithm class with visitor interface.
   6.171 +  /// \brief DFS algorithm class with visitor interface.
   6.172    ///
   6.173 -  /// This class provides an efficient implementation of the %DFS algorithm
   6.174 +  /// This class provides an efficient implementation of the DFS algorithm
   6.175    /// with visitor interface.
   6.176    ///
   6.177 -  /// The %DfsVisit class provides an alternative interface to the Dfs
   6.178 +  /// The DfsVisit class provides an alternative interface to the Dfs
   6.179    /// class. It works with callback mechanism, the DfsVisit object calls
   6.180    /// the member functions of the \c Visitor class on every DFS event.
   6.181    ///
   6.182 @@ -1238,37 +1238,37 @@
   6.183    /// events of the DFS algorithm. Otherwise consider to use Dfs or dfs()
   6.184    /// instead.
   6.185    ///
   6.186 -  /// \tparam _Digraph The type of the digraph the algorithm runs on.
   6.187 -  /// The default value is
   6.188 -  /// \ref ListDigraph. The value of _Digraph is not used directly by
   6.189 -  /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits.
   6.190 -  /// \tparam _Visitor The Visitor type that is used by the algorithm.
   6.191 -  /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which
   6.192 +  /// \tparam GR The type of the digraph the algorithm runs on.
   6.193 +  /// The default type is \ref ListDigraph.
   6.194 +  /// The value of GR is not used directly by \ref DfsVisit,
   6.195 +  /// it is only passed to \ref DfsVisitDefaultTraits.
   6.196 +  /// \tparam VS The Visitor type that is used by the algorithm.
   6.197 +  /// \ref DfsVisitor "DfsVisitor<GR>" is an empty visitor, which
   6.198    /// does not observe the DFS events. If you want to observe the DFS
   6.199    /// events, you should implement your own visitor class.
   6.200 -  /// \tparam _Traits Traits class to set various data types used by the
   6.201 +  /// \tparam TR Traits class to set various data types used by the
   6.202    /// algorithm. The default traits class is
   6.203 -  /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
   6.204 +  /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<GR>".
   6.205    /// See \ref DfsVisitDefaultTraits for the documentation of
   6.206    /// a DFS visit traits class.
   6.207  #ifdef DOXYGEN
   6.208 -  template <typename _Digraph, typename _Visitor, typename _Traits>
   6.209 +  template <typename GR, typename VS, typename TR>
   6.210  #else
   6.211 -  template <typename _Digraph = ListDigraph,
   6.212 -            typename _Visitor = DfsVisitor<_Digraph>,
   6.213 -            typename _Traits = DfsVisitDefaultTraits<_Digraph> >
   6.214 +  template <typename GR = ListDigraph,
   6.215 +            typename VS = DfsVisitor<GR>,
   6.216 +            typename TR = DfsVisitDefaultTraits<GR> >
   6.217  #endif
   6.218    class DfsVisit {
   6.219    public:
   6.220  
   6.221      ///The traits class.
   6.222 -    typedef _Traits Traits;
   6.223 +    typedef TR Traits;
   6.224  
   6.225      ///The type of the digraph the algorithm runs on.
   6.226      typedef typename Traits::Digraph Digraph;
   6.227  
   6.228      ///The visitor type used by the algorithm.
   6.229 -    typedef _Visitor Visitor;
   6.230 +    typedef VS Visitor;
   6.231  
   6.232      ///The type of the map that indicates which nodes are reached.
   6.233      typedef typename Traits::ReachedMap ReachedMap;
     7.1 --- a/lemon/dijkstra.h	Thu Jan 01 00:00:00 2009 +0100
     7.2 +++ b/lemon/dijkstra.h	Mon Feb 23 12:10:26 2009 +0100
     7.3 @@ -73,7 +73,7 @@
     7.4      ///The type of the length of the arcs.
     7.5      typedef typename LM::Value Value;
     7.6  
     7.7 -    /// Operation traits for Dijkstra algorithm.
     7.8 +    /// Operation traits for %Dijkstra algorithm.
     7.9  
    7.10      /// This class defines the operations that are used in the algorithm.
    7.11      /// \see DijkstraDefaultOperationTraits
    7.12 @@ -84,7 +84,7 @@
    7.13      /// The cross reference type used by the heap.
    7.14      /// Usually it is \c Digraph::NodeMap<int>.
    7.15      typedef typename Digraph::template NodeMap<int> HeapCrossRef;
    7.16 -    ///Instantiates a \ref HeapCrossRef.
    7.17 +    ///Instantiates a \c HeapCrossRef.
    7.18  
    7.19      ///This function instantiates a \ref HeapCrossRef.
    7.20      /// \param g is the digraph, to which we would like to define the
    7.21 @@ -94,14 +94,14 @@
    7.22        return new HeapCrossRef(g);
    7.23      }
    7.24  
    7.25 -    ///The heap type used by the Dijkstra algorithm.
    7.26 +    ///The heap type used by the %Dijkstra algorithm.
    7.27  
    7.28      ///The heap type used by the Dijkstra algorithm.
    7.29      ///
    7.30      ///\sa BinHeap
    7.31      ///\sa Dijkstra
    7.32      typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
    7.33 -    ///Instantiates a \ref Heap.
    7.34 +    ///Instantiates a \c Heap.
    7.35  
    7.36      ///This function instantiates a \ref Heap.
    7.37      static Heap *createHeap(HeapCrossRef& r)
    7.38 @@ -116,11 +116,11 @@
    7.39      ///arcs of the shortest paths.
    7.40      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    7.41      typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    7.42 -    ///Instantiates a PredMap.
    7.43 +    ///Instantiates a \c PredMap.
    7.44  
    7.45 -    ///This function instantiates a PredMap.
    7.46 +    ///This function instantiates a \ref PredMap.
    7.47      ///\param g is the digraph, to which we would like to define the
    7.48 -    ///PredMap.
    7.49 +    ///\ref PredMap.
    7.50      static PredMap *createPredMap(const Digraph &g)
    7.51      {
    7.52        return new PredMap(g);
    7.53 @@ -132,11 +132,11 @@
    7.54      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    7.55      ///By default it is a NullMap.
    7.56      typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    7.57 -    ///Instantiates a ProcessedMap.
    7.58 +    ///Instantiates a \c ProcessedMap.
    7.59  
    7.60 -    ///This function instantiates a ProcessedMap.
    7.61 +    ///This function instantiates a \ref ProcessedMap.
    7.62      ///\param g is the digraph, to which
    7.63 -    ///we would like to define the ProcessedMap
    7.64 +    ///we would like to define the \ref ProcessedMap.
    7.65  #ifdef DOXYGEN
    7.66      static ProcessedMap *createProcessedMap(const Digraph &g)
    7.67  #else
    7.68 @@ -151,11 +151,11 @@
    7.69      ///The type of the map that stores the distances of the nodes.
    7.70      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    7.71      typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
    7.72 -    ///Instantiates a DistMap.
    7.73 +    ///Instantiates a \c DistMap.
    7.74  
    7.75 -    ///This function instantiates a DistMap.
    7.76 +    ///This function instantiates a \ref DistMap.
    7.77      ///\param g is the digraph, to which we would like to define
    7.78 -    ///the DistMap
    7.79 +    ///the \ref DistMap.
    7.80      static DistMap *createDistMap(const Digraph &g)
    7.81      {
    7.82        return new DistMap(g);
    7.83 @@ -216,7 +216,8 @@
    7.84      typedef typename TR::HeapCrossRef HeapCrossRef;
    7.85      ///The heap type used by the algorithm.
    7.86      typedef typename TR::Heap Heap;
    7.87 -    ///The operation traits class.
    7.88 +    ///\brief The \ref DijkstraDefaultOperationTraits "operation traits class"
    7.89 +    ///of the algorithm.
    7.90      typedef typename TR::OperationTraits OperationTraits;
    7.91  
    7.92      ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
    7.93 @@ -232,7 +233,7 @@
    7.94      //Pointer to the underlying digraph.
    7.95      const Digraph *G;
    7.96      //Pointer to the length map.
    7.97 -    const LengthMap *length;
    7.98 +    const LengthMap *_length;
    7.99      //Pointer to the map of predecessors arcs.
   7.100      PredMap *_pred;
   7.101      //Indicates if _pred is locally allocated (true) or not.
   7.102 @@ -297,10 +298,10 @@
   7.103        }
   7.104      };
   7.105      ///\brief \ref named-templ-param "Named parameter" for setting
   7.106 -    ///PredMap type.
   7.107 +    ///\c PredMap type.
   7.108      ///
   7.109      ///\ref named-templ-param "Named parameter" for setting
   7.110 -    ///PredMap type.
   7.111 +    ///\c PredMap type.
   7.112      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   7.113      template <class T>
   7.114      struct SetPredMap
   7.115 @@ -318,10 +319,10 @@
   7.116        }
   7.117      };
   7.118      ///\brief \ref named-templ-param "Named parameter" for setting
   7.119 -    ///DistMap type.
   7.120 +    ///\c DistMap type.
   7.121      ///
   7.122      ///\ref named-templ-param "Named parameter" for setting
   7.123 -    ///DistMap type.
   7.124 +    ///\c DistMap type.
   7.125      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   7.126      template <class T>
   7.127      struct SetDistMap
   7.128 @@ -339,10 +340,10 @@
   7.129        }
   7.130      };
   7.131      ///\brief \ref named-templ-param "Named parameter" for setting
   7.132 -    ///ProcessedMap type.
   7.133 +    ///\c ProcessedMap type.
   7.134      ///
   7.135      ///\ref named-templ-param "Named parameter" for setting
   7.136 -    ///ProcessedMap type.
   7.137 +    ///\c ProcessedMap type.
   7.138      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   7.139      template <class T>
   7.140      struct SetProcessedMap
   7.141 @@ -358,10 +359,10 @@
   7.142        }
   7.143      };
   7.144      ///\brief \ref named-templ-param "Named parameter" for setting
   7.145 -    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   7.146 +    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   7.147      ///
   7.148      ///\ref named-templ-param "Named parameter" for setting
   7.149 -    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   7.150 +    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   7.151      ///If you don't set it explicitly, it will be automatically allocated.
   7.152      struct SetStandardProcessedMap
   7.153        : public Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits > {
   7.154 @@ -439,7 +440,7 @@
   7.155      ///\c OperationTraits type
   7.156      ///
   7.157      ///\ref named-templ-param "Named parameter" for setting
   7.158 -    ///\ref OperationTraits type.
   7.159 +    ///\c OperationTraits type.
   7.160      template <class T>
   7.161      struct SetOperationTraits
   7.162        : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {
   7.163 @@ -458,10 +459,10 @@
   7.164      ///Constructor.
   7.165  
   7.166      ///Constructor.
   7.167 -    ///\param _g The digraph the algorithm runs on.
   7.168 -    ///\param _length The length map used by the algorithm.
   7.169 -    Dijkstra(const Digraph& _g, const LengthMap& _length) :
   7.170 -      G(&_g), length(&_length),
   7.171 +    ///\param g The digraph the algorithm runs on.
   7.172 +    ///\param length The length map used by the algorithm.
   7.173 +    Dijkstra(const Digraph& g, const LengthMap& length) :
   7.174 +      G(&g), _length(&length),
   7.175        _pred(NULL), local_pred(false),
   7.176        _dist(NULL), local_dist(false),
   7.177        _processed(NULL), local_processed(false),
   7.178 @@ -485,7 +486,7 @@
   7.179      ///\return <tt> (*this) </tt>
   7.180      Dijkstra &lengthMap(const LengthMap &m)
   7.181      {
   7.182 -      length = &m;
   7.183 +      _length = &m;
   7.184        return *this;
   7.185      }
   7.186  
   7.187 @@ -638,12 +639,12 @@
   7.188          Node w=G->target(e);
   7.189          switch(_heap->state(w)) {
   7.190          case Heap::PRE_HEAP:
   7.191 -          _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e]));
   7.192 +          _heap->push(w,OperationTraits::plus(oldvalue, (*_length)[e]));
   7.193            _pred->set(w,e);
   7.194            break;
   7.195          case Heap::IN_HEAP:
   7.196            {
   7.197 -            Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]);
   7.198 +            Value newvalue = OperationTraits::plus(oldvalue, (*_length)[e]);
   7.199              if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
   7.200                _heap->decrease(w, newvalue);
   7.201                _pred->set(w,e);
     8.1 --- a/lemon/preflow.h	Thu Jan 01 00:00:00 2009 +0100
     8.2 +++ b/lemon/preflow.h	Mon Feb 23 12:10:26 2009 +0100
     8.3 @@ -31,19 +31,19 @@
     8.4    /// \brief Default traits class of Preflow class.
     8.5    ///
     8.6    /// Default traits class of Preflow class.
     8.7 -  /// \tparam _Digraph Digraph type.
     8.8 -  /// \tparam _CapacityMap Capacity map type.
     8.9 -  template <typename _Digraph, typename _CapacityMap>
    8.10 +  /// \tparam GR Digraph type.
    8.11 +  /// \tparam CM Capacity map type.
    8.12 +  template <typename GR, typename CM>
    8.13    struct PreflowDefaultTraits {
    8.14  
    8.15      /// \brief The type of the digraph the algorithm runs on.
    8.16 -    typedef _Digraph Digraph;
    8.17 +    typedef GR Digraph;
    8.18  
    8.19      /// \brief The type of the map that stores the arc capacities.
    8.20      ///
    8.21      /// The type of the map that stores the arc capacities.
    8.22      /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
    8.23 -    typedef _CapacityMap CapacityMap;
    8.24 +    typedef CM CapacityMap;
    8.25  
    8.26      /// \brief The type of the flow values.
    8.27      typedef typename CapacityMap::Value Value;
    8.28 @@ -104,21 +104,21 @@
    8.29    /// the maximum flow value and the minimum cut is obtained. The
    8.30    /// second phase constructs a feasible maximum flow on each arc.
    8.31    ///
    8.32 -  /// \tparam _Digraph The type of the digraph the algorithm runs on.
    8.33 -  /// \tparam _CapacityMap The type of the capacity map. The default map
    8.34 -  /// type is \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>".
    8.35 +  /// \tparam GR The type of the digraph the algorithm runs on.
    8.36 +  /// \tparam CM The type of the capacity map. The default map
    8.37 +  /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    8.38  #ifdef DOXYGEN
    8.39 -  template <typename _Digraph, typename _CapacityMap, typename _Traits>
    8.40 +  template <typename GR, typename CM, typename TR>
    8.41  #else
    8.42 -  template <typename _Digraph,
    8.43 -            typename _CapacityMap = typename _Digraph::template ArcMap<int>,
    8.44 -            typename _Traits = PreflowDefaultTraits<_Digraph, _CapacityMap> >
    8.45 +  template <typename GR,
    8.46 +            typename CM = typename GR::template ArcMap<int>,
    8.47 +            typename TR = PreflowDefaultTraits<GR, CM> >
    8.48  #endif
    8.49    class Preflow {
    8.50    public:
    8.51  
    8.52      ///The \ref PreflowDefaultTraits "traits class" of the algorithm.
    8.53 -    typedef _Traits Traits;
    8.54 +    typedef TR Traits;
    8.55      ///The type of the digraph the algorithm runs on.
    8.56      typedef typename Traits::Digraph Digraph;
    8.57      ///The type of the capacity map.