Various doc improvements (#248)
authorPeter Kovacs <kpeter@inf.elte.hu>
Sun, 29 Mar 2009 23:08:20 +0200
changeset 559c5fd2d996909
parent 548 94387da47f79
child 560 49a39bae067c
Various doc improvements (#248)
- Rename all the ugly template parameters (too long and/or starting
with an underscore).
- Rename function parameters starting with an underscore.
- Extend the doc for many classes.
- Use LaTeX-style O(...) expressions only for the complicated ones.
- A lot of small unification changes.
- Small fixes.
- Some other improvements.
doc/groups.dox
doc/mainpage.dox
lemon/adaptors.h
lemon/bin_heap.h
lemon/bits/edge_set_extender.h
lemon/circulation.h
lemon/concepts/graph.h
lemon/concepts/graph_components.h
lemon/concepts/heap.h
lemon/concepts/path.h
lemon/connectivity.h
lemon/core.h
lemon/dijkstra.h
lemon/edge_set.h
lemon/elevator.h
lemon/euler.h
lemon/graph_to_eps.h
lemon/grid_graph.h
lemon/hao_orlin.h
lemon/hypercube_graph.h
lemon/lgf_reader.h
lemon/lgf_writer.h
lemon/list_graph.h
lemon/maps.h
lemon/max_matching.h
lemon/min_cost_arborescence.h
lemon/path.h
lemon/preflow.h
lemon/radix_sort.h
lemon/random.h
lemon/smart_graph.h
lemon/suurballe.h
lemon/unionfind.h
     1.1 --- a/doc/groups.dox	Thu Mar 05 10:13:20 2009 +0000
     1.2 +++ b/doc/groups.dox	Sun Mar 29 23:08:20 2009 +0200
     1.3 @@ -20,7 +20,7 @@
     1.4  
     1.5  /**
     1.6  @defgroup datas Data Structures
     1.7 -This group describes the several data structures implemented in LEMON.
     1.8 +This group contains the several data structures implemented in LEMON.
     1.9  */
    1.10  
    1.11  /**
    1.12 @@ -142,7 +142,7 @@
    1.13  @ingroup graphs
    1.14  \brief Graph types between real graphs and graph adaptors.
    1.15  
    1.16 -This group describes some graph types between real graphs and graph adaptors.
    1.17 +This group contains some graph types between real graphs and graph adaptors.
    1.18  These classes wrap graphs to give new functionality as the adaptors do it.
    1.19  On the other hand they are not light-weight structures as the adaptors.
    1.20  */
    1.21 @@ -152,7 +152,7 @@
    1.22  @ingroup datas
    1.23  \brief Map structures implemented in LEMON.
    1.24  
    1.25 -This group describes the map structures implemented in LEMON.
    1.26 +This group contains the map structures implemented in LEMON.
    1.27  
    1.28  LEMON provides several special purpose maps and map adaptors that e.g. combine
    1.29  new maps from existing ones.
    1.30 @@ -165,7 +165,7 @@
    1.31  @ingroup maps
    1.32  \brief Special graph-related maps.
    1.33  
    1.34 -This group describes maps that are specifically designed to assign
    1.35 +This group contains maps that are specifically designed to assign
    1.36  values to the nodes and arcs/edges of graphs.
    1.37  
    1.38  If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
    1.39 @@ -177,7 +177,7 @@
    1.40  \ingroup maps
    1.41  \brief Tools to create new maps from existing ones
    1.42  
    1.43 -This group describes map adaptors that are used to create "implicit"
    1.44 +This group contains map adaptors that are used to create "implicit"
    1.45  maps from other maps.
    1.46  
    1.47  Most of them are \ref concepts::ReadMap "read-only maps".
    1.48 @@ -240,7 +240,7 @@
    1.49  @ingroup datas
    1.50  \brief Two dimensional data storages implemented in LEMON.
    1.51  
    1.52 -This group describes two dimensional data storages implemented in LEMON.
    1.53 +This group contains two dimensional data storages implemented in LEMON.
    1.54  */
    1.55  
    1.56  /**
    1.57 @@ -248,7 +248,7 @@
    1.58  @ingroup datas
    1.59  \brief %Path structures implemented in LEMON.
    1.60  
    1.61 -This group describes the path structures implemented in LEMON.
    1.62 +This group contains the path structures implemented in LEMON.
    1.63  
    1.64  LEMON provides flexible data structures to work with paths.
    1.65  All of them have similar interfaces and they can be copied easily with
    1.66 @@ -264,16 +264,16 @@
    1.67  @ingroup datas
    1.68  \brief Auxiliary data structures implemented in LEMON.
    1.69  
    1.70 -This group describes some data structures implemented in LEMON in
    1.71 +This group contains some data structures implemented in LEMON in
    1.72  order to make it easier to implement combinatorial algorithms.
    1.73  */
    1.74  
    1.75  /**
    1.76  @defgroup algs Algorithms
    1.77 -\brief This group describes the several algorithms
    1.78 +\brief This group contains the several algorithms
    1.79  implemented in LEMON.
    1.80  
    1.81 -This group describes the several algorithms
    1.82 +This group contains the several algorithms
    1.83  implemented in LEMON.
    1.84  */
    1.85  
    1.86 @@ -282,7 +282,7 @@
    1.87  @ingroup algs
    1.88  \brief Common graph search algorithms.
    1.89  
    1.90 -This group describes the common graph search algorithms, namely
    1.91 +This group contains the common graph search algorithms, namely
    1.92  \e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
    1.93  */
    1.94  
    1.95 @@ -291,7 +291,7 @@
    1.96  @ingroup algs
    1.97  \brief Algorithms for finding shortest paths.
    1.98  
    1.99 -This group describes the algorithms for finding shortest paths in digraphs.
   1.100 +This group contains the algorithms for finding shortest paths in digraphs.
   1.101  
   1.102   - \ref Dijkstra algorithm for finding shortest paths from a source node
   1.103     when all arc lengths are non-negative.
   1.104 @@ -312,7 +312,7 @@
   1.105  @ingroup algs
   1.106  \brief Algorithms for finding maximum flows.
   1.107  
   1.108 -This group describes the algorithms for finding maximum flows and
   1.109 +This group contains the algorithms for finding maximum flows and
   1.110  feasible circulations.
   1.111  
   1.112  The \e maximum \e flow \e problem is to find a flow of maximum value between
   1.113 @@ -345,7 +345,7 @@
   1.114  
   1.115  \brief Algorithms for finding minimum cost flows and circulations.
   1.116  
   1.117 -This group describes the algorithms for finding minimum cost flows and
   1.118 +This group contains the algorithms for finding minimum cost flows and
   1.119  circulations.
   1.120  
   1.121  The \e minimum \e cost \e flow \e problem is to find a feasible flow of
   1.122 @@ -382,7 +382,7 @@
   1.123  
   1.124  \brief Algorithms for finding minimum cut in graphs.
   1.125  
   1.126 -This group describes the algorithms for finding minimum cut in graphs.
   1.127 +This group contains the algorithms for finding minimum cut in graphs.
   1.128  
   1.129  The \e minimum \e cut \e problem is to find a non-empty and non-complete
   1.130  \f$X\f$ subset of the nodes with minimum overall capacity on
   1.131 @@ -399,7 +399,7 @@
   1.132    in directed graphs.
   1.133  - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
   1.134    calculating minimum cut in undirected graphs.
   1.135 -- \ref GomoryHuTree "Gomory-Hu tree computation" for calculating
   1.136 +- \ref GomoryHu "Gomory-Hu tree computation" for calculating
   1.137    all-pairs minimum cut in undirected graphs.
   1.138  
   1.139  If you want to find minimum cut just between two distinict nodes,
   1.140 @@ -411,7 +411,7 @@
   1.141  @ingroup algs
   1.142  \brief Algorithms for discovering the graph properties
   1.143  
   1.144 -This group describes the algorithms for discovering the graph properties
   1.145 +This group contains the algorithms for discovering the graph properties
   1.146  like connectivity, bipartiteness, euler property, simplicity etc.
   1.147  
   1.148  \image html edge_biconnected_components.png
   1.149 @@ -423,7 +423,7 @@
   1.150  @ingroup algs
   1.151  \brief Algorithms for planarity checking, embedding and drawing
   1.152  
   1.153 -This group describes the algorithms for planarity checking,
   1.154 +This group contains the algorithms for planarity checking,
   1.155  embedding and drawing.
   1.156  
   1.157  \image html planar.png
   1.158 @@ -474,7 +474,7 @@
   1.159  @ingroup algs
   1.160  \brief Algorithms for finding a minimum cost spanning tree in a graph.
   1.161  
   1.162 -This group describes the algorithms for finding a minimum cost spanning
   1.163 +This group contains the algorithms for finding a minimum cost spanning
   1.164  tree in a graph.
   1.165  */
   1.166  
   1.167 @@ -483,7 +483,7 @@
   1.168  @ingroup algs
   1.169  \brief Auxiliary algorithms implemented in LEMON.
   1.170  
   1.171 -This group describes some algorithms implemented in LEMON
   1.172 +This group contains some algorithms implemented in LEMON
   1.173  in order to make it easier to implement complex algorithms.
   1.174  */
   1.175  
   1.176 @@ -492,16 +492,16 @@
   1.177  @ingroup algs
   1.178  \brief Approximation algorithms.
   1.179  
   1.180 -This group describes the approximation and heuristic algorithms
   1.181 +This group contains the approximation and heuristic algorithms
   1.182  implemented in LEMON.
   1.183  */
   1.184  
   1.185  /**
   1.186  @defgroup gen_opt_group General Optimization Tools
   1.187 -\brief This group describes some general optimization frameworks
   1.188 +\brief This group contains some general optimization frameworks
   1.189  implemented in LEMON.
   1.190  
   1.191 -This group describes some general optimization frameworks
   1.192 +This group contains some general optimization frameworks
   1.193  implemented in LEMON.
   1.194  */
   1.195  
   1.196 @@ -510,7 +510,7 @@
   1.197  @ingroup gen_opt_group
   1.198  \brief Lp and Mip solver interfaces for LEMON.
   1.199  
   1.200 -This group describes Lp and Mip solver interfaces for LEMON. The
   1.201 +This group contains Lp and Mip solver interfaces for LEMON. The
   1.202  various LP solvers could be used in the same manner with this
   1.203  interface.
   1.204  */
   1.205 @@ -529,7 +529,7 @@
   1.206  @ingroup gen_opt_group
   1.207  \brief Metaheuristics for LEMON library.
   1.208  
   1.209 -This group describes some metaheuristic optimization tools.
   1.210 +This group contains some metaheuristic optimization tools.
   1.211  */
   1.212  
   1.213  /**
   1.214 @@ -544,7 +544,7 @@
   1.215  @ingroup utils
   1.216  \brief Simple basic graph utilities.
   1.217  
   1.218 -This group describes some simple basic graph utilities.
   1.219 +This group contains some simple basic graph utilities.
   1.220  */
   1.221  
   1.222  /**
   1.223 @@ -552,7 +552,7 @@
   1.224  @ingroup utils
   1.225  \brief Tools for development, debugging and testing.
   1.226  
   1.227 -This group describes several useful tools for development,
   1.228 +This group contains several useful tools for development,
   1.229  debugging and testing.
   1.230  */
   1.231  
   1.232 @@ -561,7 +561,7 @@
   1.233  @ingroup misc
   1.234  \brief Simple tools for measuring the performance of algorithms.
   1.235  
   1.236 -This group describes simple tools for measuring the performance
   1.237 +This group contains simple tools for measuring the performance
   1.238  of algorithms.
   1.239  */
   1.240  
   1.241 @@ -570,14 +570,14 @@
   1.242  @ingroup utils
   1.243  \brief Exceptions defined in LEMON.
   1.244  
   1.245 -This group describes the exceptions defined in LEMON.
   1.246 +This group contains the exceptions defined in LEMON.
   1.247  */
   1.248  
   1.249  /**
   1.250  @defgroup io_group Input-Output
   1.251  \brief Graph Input-Output methods
   1.252  
   1.253 -This group describes the tools for importing and exporting graphs
   1.254 +This group contains the tools for importing and exporting graphs
   1.255  and graph related data. Now it supports the \ref lgf-format
   1.256  "LEMON Graph Format", the \c DIMACS format and the encapsulated
   1.257  postscript (EPS) format.
   1.258 @@ -588,7 +588,7 @@
   1.259  @ingroup io_group
   1.260  \brief Reading and writing LEMON Graph Format.
   1.261  
   1.262 -This group describes methods for reading and writing
   1.263 +This group contains methods for reading and writing
   1.264  \ref lgf-format "LEMON Graph Format".
   1.265  */
   1.266  
   1.267 @@ -597,7 +597,7 @@
   1.268  @ingroup io_group
   1.269  \brief General \c EPS drawer and graph exporter
   1.270  
   1.271 -This group describes general \c EPS drawing methods and special
   1.272 +This group contains general \c EPS drawing methods and special
   1.273  graph exporting tools.
   1.274  */
   1.275  
   1.276 @@ -621,7 +621,7 @@
   1.277  @defgroup concept Concepts
   1.278  \brief Skeleton classes and concept checking classes
   1.279  
   1.280 -This group describes the data/algorithm skeletons and concept checking
   1.281 +This group contains the data/algorithm skeletons and concept checking
   1.282  classes implemented in LEMON.
   1.283  
   1.284  The purpose of the classes in this group is fourfold.
   1.285 @@ -651,7 +651,7 @@
   1.286  @ingroup concept
   1.287  \brief Skeleton and concept checking classes for graph structures
   1.288  
   1.289 -This group describes the skeletons and concept checking classes of LEMON's
   1.290 +This group contains the skeletons and concept checking classes of LEMON's
   1.291  graph structures and helper classes used to implement these.
   1.292  */
   1.293  
   1.294 @@ -660,7 +660,7 @@
   1.295  @ingroup concept
   1.296  \brief Skeleton and concept checking classes for maps
   1.297  
   1.298 -This group describes the skeletons and concept checking classes of maps.
   1.299 +This group contains the skeletons and concept checking classes of maps.
   1.300  */
   1.301  
   1.302  /**
     2.1 --- a/doc/mainpage.dox	Thu Mar 05 10:13:20 2009 +0000
     2.2 +++ b/doc/mainpage.dox	Sun Mar 29 23:08:20 2009 +0200
     2.3 @@ -45,16 +45,11 @@
     2.4  take a look at our \ref quicktour
     2.5  "Quick Tour to LEMON" which will guide you along.
     2.6  
     2.7 -If you already feel like using our library, see the page that tells you
     2.8 -\ref getstart "How to start using LEMON".
     2.9 -
    2.10 -If you
    2.11 -want to see how LEMON works, see
    2.12 -some \ref demoprograms "demo programs".
    2.13 +If you already feel like using our library, see the
    2.14 +<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.
    2.15  
    2.16  If you know what you are looking for then try to find it under the
    2.17 -<a class="el" href="modules.html">Modules</a>
    2.18 -section.
    2.19 +<a class="el" href="modules.html">Modules</a> section.
    2.20  
    2.21  If you are a user of the old (0.x) series of LEMON, please check out the
    2.22  \ref migration "Migration Guide" for the backward incompatibilities.
     3.1 --- a/lemon/adaptors.h	Thu Mar 05 10:13:20 2009 +0000
     3.2 +++ b/lemon/adaptors.h	Sun Mar 29 23:08:20 2009 +0200
     3.3 @@ -2254,26 +2254,27 @@
     3.4      ///
     3.5      /// This map adaptor class adapts two arc maps of the underlying
     3.6      /// digraph to get an arc map of the undirected graph.
     3.7 -    /// Its value type is inherited from the first arc map type
     3.8 -    /// (\c %ForwardMap).
     3.9 -    template <typename ForwardMap, typename BackwardMap>
    3.10 +    /// Its value type is inherited from the first arc map type (\c FW).
    3.11 +    /// \tparam FW The type of the "foward" arc map.
    3.12 +    /// \tparam BK The type of the "backward" arc map.
    3.13 +    template <typename FW, typename BK>
    3.14      class CombinedArcMap {
    3.15      public:
    3.16  
    3.17        /// The key type of the map
    3.18        typedef typename Parent::Arc Key;
    3.19        /// The value type of the map
    3.20 -      typedef typename ForwardMap::Value Value;
    3.21 -
    3.22 -      typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag;
    3.23 -
    3.24 -      typedef typename MapTraits<ForwardMap>::ReturnValue ReturnValue;
    3.25 -      typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReturnValue;
    3.26 -      typedef typename MapTraits<ForwardMap>::ReturnValue Reference;
    3.27 -      typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReference;
    3.28 +      typedef typename FW::Value Value;
    3.29 +
    3.30 +      typedef typename MapTraits<FW>::ReferenceMapTag ReferenceMapTag;
    3.31 +
    3.32 +      typedef typename MapTraits<FW>::ReturnValue ReturnValue;
    3.33 +      typedef typename MapTraits<FW>::ConstReturnValue ConstReturnValue;
    3.34 +      typedef typename MapTraits<FW>::ReturnValue Reference;
    3.35 +      typedef typename MapTraits<FW>::ConstReturnValue ConstReference;
    3.36  
    3.37        /// Constructor
    3.38 -      CombinedArcMap(ForwardMap& forward, BackwardMap& backward)
    3.39 +      CombinedArcMap(FW& forward, BK& backward)
    3.40          : _forward(&forward), _backward(&backward) {}
    3.41  
    3.42        /// Sets the value associated with the given key.
    3.43 @@ -2305,39 +2306,36 @@
    3.44  
    3.45      protected:
    3.46  
    3.47 -      ForwardMap* _forward;
    3.48 -      BackwardMap* _backward;
    3.49 +      FW* _forward;
    3.50 +      BK* _backward;
    3.51  
    3.52      };
    3.53  
    3.54      /// \brief Returns a combined arc map
    3.55      ///
    3.56      /// This function just returns a combined arc map.
    3.57 -    template <typename ForwardMap, typename BackwardMap>
    3.58 -    static CombinedArcMap<ForwardMap, BackwardMap>
    3.59 -    combinedArcMap(ForwardMap& forward, BackwardMap& backward) {
    3.60 -      return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward);
    3.61 +    template <typename FW, typename BK>
    3.62 +    static CombinedArcMap<FW, BK>
    3.63 +    combinedArcMap(FW& forward, BK& backward) {
    3.64 +      return CombinedArcMap<FW, BK>(forward, backward);
    3.65      }
    3.66  
    3.67 -    template <typename ForwardMap, typename BackwardMap>
    3.68 -    static CombinedArcMap<const ForwardMap, BackwardMap>
    3.69 -    combinedArcMap(const ForwardMap& forward, BackwardMap& backward) {
    3.70 -      return CombinedArcMap<const ForwardMap,
    3.71 -        BackwardMap>(forward, backward);
    3.72 +    template <typename FW, typename BK>
    3.73 +    static CombinedArcMap<const FW, BK>
    3.74 +    combinedArcMap(const FW& forward, BK& backward) {
    3.75 +      return CombinedArcMap<const FW, BK>(forward, backward);
    3.76      }
    3.77  
    3.78 -    template <typename ForwardMap, typename BackwardMap>
    3.79 -    static CombinedArcMap<ForwardMap, const BackwardMap>
    3.80 -    combinedArcMap(ForwardMap& forward, const BackwardMap& backward) {
    3.81 -      return CombinedArcMap<ForwardMap,
    3.82 -        const BackwardMap>(forward, backward);
    3.83 +    template <typename FW, typename BK>
    3.84 +    static CombinedArcMap<FW, const BK>
    3.85 +    combinedArcMap(FW& forward, const BK& backward) {
    3.86 +      return CombinedArcMap<FW, const BK>(forward, backward);
    3.87      }
    3.88  
    3.89 -    template <typename ForwardMap, typename BackwardMap>
    3.90 -    static CombinedArcMap<const ForwardMap, const BackwardMap>
    3.91 -    combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) {
    3.92 -      return CombinedArcMap<const ForwardMap,
    3.93 -        const BackwardMap>(forward, backward);
    3.94 +    template <typename FW, typename BK>
    3.95 +    static CombinedArcMap<const FW, const BK>
    3.96 +    combinedArcMap(const FW& forward, const BK& backward) {
    3.97 +      return CombinedArcMap<const FW, const BK>(forward, backward);
    3.98      }
    3.99  
   3.100    };
   3.101 @@ -3406,25 +3404,26 @@
   3.102      ///
   3.103      /// This map adaptor class adapts two node maps of the original digraph
   3.104      /// to get a node map of the split digraph.
   3.105 -    /// Its value type is inherited from the first node map type
   3.106 -    /// (\c InNodeMap).
   3.107 -    template <typename InNodeMap, typename OutNodeMap>
   3.108 +    /// Its value type is inherited from the first node map type (\c IN).
   3.109 +    /// \tparam IN The type of the node map for the in-nodes. 
   3.110 +    /// \tparam OUT The type of the node map for the out-nodes.
   3.111 +    template <typename IN, typename OUT>
   3.112      class CombinedNodeMap {
   3.113      public:
   3.114  
   3.115        /// The key type of the map
   3.116        typedef Node Key;
   3.117        /// The value type of the map
   3.118 -      typedef typename InNodeMap::Value Value;
   3.119 -
   3.120 -      typedef typename MapTraits<InNodeMap>::ReferenceMapTag ReferenceMapTag;
   3.121 -      typedef typename MapTraits<InNodeMap>::ReturnValue ReturnValue;
   3.122 -      typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReturnValue;
   3.123 -      typedef typename MapTraits<InNodeMap>::ReturnValue Reference;
   3.124 -      typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReference;
   3.125 +      typedef typename IN::Value Value;
   3.126 +
   3.127 +      typedef typename MapTraits<IN>::ReferenceMapTag ReferenceMapTag;
   3.128 +      typedef typename MapTraits<IN>::ReturnValue ReturnValue;
   3.129 +      typedef typename MapTraits<IN>::ConstReturnValue ConstReturnValue;
   3.130 +      typedef typename MapTraits<IN>::ReturnValue Reference;
   3.131 +      typedef typename MapTraits<IN>::ConstReturnValue ConstReference;
   3.132  
   3.133        /// Constructor
   3.134 -      CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map)
   3.135 +      CombinedNodeMap(IN& in_map, OUT& out_map)
   3.136          : _in_map(in_map), _out_map(out_map) {}
   3.137  
   3.138        /// Returns the value associated with the given key.
   3.139 @@ -3456,8 +3455,8 @@
   3.140  
   3.141      private:
   3.142  
   3.143 -      InNodeMap& _in_map;
   3.144 -      OutNodeMap& _out_map;
   3.145 +      IN& _in_map;
   3.146 +      OUT& _out_map;
   3.147  
   3.148      };
   3.149  
   3.150 @@ -3465,29 +3464,28 @@
   3.151      /// \brief Returns a combined node map
   3.152      ///
   3.153      /// This function just returns a combined node map.
   3.154 -    template <typename InNodeMap, typename OutNodeMap>
   3.155 -    static CombinedNodeMap<InNodeMap, OutNodeMap>
   3.156 -    combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
   3.157 -      return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
   3.158 +    template <typename IN, typename OUT>
   3.159 +    static CombinedNodeMap<IN, OUT>
   3.160 +    combinedNodeMap(IN& in_map, OUT& out_map) {
   3.161 +      return CombinedNodeMap<IN, OUT>(in_map, out_map);
   3.162      }
   3.163  
   3.164 -    template <typename InNodeMap, typename OutNodeMap>
   3.165 -    static CombinedNodeMap<const InNodeMap, OutNodeMap>
   3.166 -    combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
   3.167 -      return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
   3.168 +    template <typename IN, typename OUT>
   3.169 +    static CombinedNodeMap<const IN, OUT>
   3.170 +    combinedNodeMap(const IN& in_map, OUT& out_map) {
   3.171 +      return CombinedNodeMap<const IN, OUT>(in_map, out_map);
   3.172      }
   3.173  
   3.174 -    template <typename InNodeMap, typename OutNodeMap>
   3.175 -    static CombinedNodeMap<InNodeMap, const OutNodeMap>
   3.176 -    combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
   3.177 -      return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
   3.178 +    template <typename IN, typename OUT>
   3.179 +    static CombinedNodeMap<IN, const OUT>
   3.180 +    combinedNodeMap(IN& in_map, const OUT& out_map) {
   3.181 +      return CombinedNodeMap<IN, const OUT>(in_map, out_map);
   3.182      }
   3.183  
   3.184 -    template <typename InNodeMap, typename OutNodeMap>
   3.185 -    static CombinedNodeMap<const InNodeMap, const OutNodeMap>
   3.186 -    combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
   3.187 -      return CombinedNodeMap<const InNodeMap,
   3.188 -        const OutNodeMap>(in_map, out_map);
   3.189 +    template <typename IN, typename OUT>
   3.190 +    static CombinedNodeMap<const IN, const OUT>
   3.191 +    combinedNodeMap(const IN& in_map, const OUT& out_map) {
   3.192 +      return CombinedNodeMap<const IN, const OUT>(in_map, out_map);
   3.193      }
   3.194  
   3.195      /// \brief Arc map combined from an arc map and a node map of the
   3.196 @@ -3495,25 +3493,26 @@
   3.197      ///
   3.198      /// This map adaptor class adapts an arc map and a node map of the
   3.199      /// original digraph to get an arc map of the split digraph.
   3.200 -    /// Its value type is inherited from the original arc map type
   3.201 -    /// (\c ArcMap).
   3.202 -    template <typename ArcMap, typename NodeMap>
   3.203 +    /// Its value type is inherited from the original arc map type (\c AM).
   3.204 +    /// \tparam AM The type of the arc map.
   3.205 +    /// \tparam NM the type of the node map.
   3.206 +    template <typename AM, typename NM>
   3.207      class CombinedArcMap {
   3.208      public:
   3.209  
   3.210        /// The key type of the map
   3.211        typedef Arc Key;
   3.212        /// The value type of the map
   3.213 -      typedef typename ArcMap::Value Value;
   3.214 -
   3.215 -      typedef typename MapTraits<ArcMap>::ReferenceMapTag ReferenceMapTag;
   3.216 -      typedef typename MapTraits<ArcMap>::ReturnValue ReturnValue;
   3.217 -      typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReturnValue;
   3.218 -      typedef typename MapTraits<ArcMap>::ReturnValue Reference;
   3.219 -      typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReference;
   3.220 +      typedef typename AM::Value Value;
   3.221 +
   3.222 +      typedef typename MapTraits<AM>::ReferenceMapTag ReferenceMapTag;
   3.223 +      typedef typename MapTraits<AM>::ReturnValue ReturnValue;
   3.224 +      typedef typename MapTraits<AM>::ConstReturnValue ConstReturnValue;
   3.225 +      typedef typename MapTraits<AM>::ReturnValue Reference;
   3.226 +      typedef typename MapTraits<AM>::ConstReturnValue ConstReference;
   3.227  
   3.228        /// Constructor
   3.229 -      CombinedArcMap(ArcMap& arc_map, NodeMap& node_map)
   3.230 +      CombinedArcMap(AM& arc_map, NM& node_map)
   3.231          : _arc_map(arc_map), _node_map(node_map) {}
   3.232  
   3.233        /// Returns the value associated with the given key.
   3.234 @@ -3544,8 +3543,10 @@
   3.235        }
   3.236  
   3.237      private:
   3.238 -      ArcMap& _arc_map;
   3.239 -      NodeMap& _node_map;
   3.240 +
   3.241 +      AM& _arc_map;
   3.242 +      NM& _node_map;
   3.243 +
   3.244      };
   3.245  
   3.246      /// \brief Returns a combined arc map
     4.1 --- a/lemon/bin_heap.h	Thu Mar 05 10:13:20 2009 +0000
     4.2 +++ b/lemon/bin_heap.h	Sun Mar 29 23:08:20 2009 +0200
     4.3 @@ -33,35 +33,36 @@
     4.4    ///
     4.5    ///\brief A Binary Heap implementation.
     4.6    ///
     4.7 -  ///This class implements the \e binary \e heap data structure. A \e heap
     4.8 -  ///is a data structure for storing items with specified values called \e
     4.9 -  ///priorities in such a way that finding the item with minimum priority is
    4.10 -  ///efficient. \c Compare specifies the ordering of the priorities. In a heap
    4.11 -  ///one can change the priority of an item, add or erase an item, etc.
    4.12 +  ///This class implements the \e binary \e heap data structure. 
    4.13 +  /// 
    4.14 +  ///A \e heap is a data structure for storing items with specified values
    4.15 +  ///called \e priorities in such a way that finding the item with minimum
    4.16 +  ///priority is efficient. \c Comp specifies the ordering of the priorities.
    4.17 +  ///In a heap one can change the priority of an item, add or erase an
    4.18 +  ///item, etc.
    4.19    ///
    4.20 -  ///\tparam _Prio Type of the priority of the items.
    4.21 -  ///\tparam _ItemIntMap A read and writable Item int map, used internally
    4.22 +  ///\tparam PR Type of the priority of the items.
    4.23 +  ///\tparam IM A read and writable item map with int values, used internally
    4.24    ///to handle the cross references.
    4.25 -  ///\tparam _Compare A class for the ordering of the priorities. The
    4.26 -  ///default is \c std::less<_Prio>.
    4.27 +  ///\tparam Comp A functor class for the ordering of the priorities.
    4.28 +  ///The default is \c std::less<PR>.
    4.29    ///
    4.30    ///\sa FibHeap
    4.31    ///\sa Dijkstra
    4.32 -  template <typename _Prio, typename _ItemIntMap,
    4.33 -            typename _Compare = std::less<_Prio> >
    4.34 +  template <typename PR, typename IM, typename Comp = std::less<PR> >
    4.35    class BinHeap {
    4.36  
    4.37    public:
    4.38      ///\e
    4.39 -    typedef _ItemIntMap ItemIntMap;
    4.40 +    typedef IM ItemIntMap;
    4.41      ///\e
    4.42 -    typedef _Prio Prio;
    4.43 +    typedef PR Prio;
    4.44      ///\e
    4.45      typedef typename ItemIntMap::Key Item;
    4.46      ///\e
    4.47      typedef std::pair<Item,Prio> Pair;
    4.48      ///\e
    4.49 -    typedef _Compare Compare;
    4.50 +    typedef Comp Compare;
    4.51  
    4.52      /// \brief Type to represent the items states.
    4.53      ///
    4.54 @@ -69,49 +70,49 @@
    4.55      /// "pre heap" or "post heap". The latter two are indifferent from the
    4.56      /// heap's point of view, but may be useful to the user.
    4.57      ///
    4.58 -    /// The ItemIntMap \e should be initialized in such way that it maps
    4.59 -    /// PRE_HEAP (-1) to any element to be put in the heap...
    4.60 +    /// The item-int map must be initialized in such way that it assigns
    4.61 +    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
    4.62      enum State {
    4.63 -      IN_HEAP = 0,
    4.64 -      PRE_HEAP = -1,
    4.65 -      POST_HEAP = -2
    4.66 +      IN_HEAP = 0,    ///< \e
    4.67 +      PRE_HEAP = -1,  ///< \e
    4.68 +      POST_HEAP = -2  ///< \e
    4.69      };
    4.70  
    4.71    private:
    4.72 -    std::vector<Pair> data;
    4.73 -    Compare comp;
    4.74 -    ItemIntMap &iim;
    4.75 +    std::vector<Pair> _data;
    4.76 +    Compare _comp;
    4.77 +    ItemIntMap &_iim;
    4.78  
    4.79    public:
    4.80      /// \brief The constructor.
    4.81      ///
    4.82      /// The constructor.
    4.83 -    /// \param _iim should be given to the constructor, since it is used
    4.84 +    /// \param map should be given to the constructor, since it is used
    4.85      /// internally to handle the cross references. The value of the map
    4.86 -    /// should be PRE_HEAP (-1) for each element.
    4.87 -    explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
    4.88 +    /// must be \c PRE_HEAP (<tt>-1</tt>) for every item.
    4.89 +    explicit BinHeap(ItemIntMap &map) : _iim(map) {}
    4.90  
    4.91      /// \brief The constructor.
    4.92      ///
    4.93      /// The constructor.
    4.94 -    /// \param _iim should be given to the constructor, since it is used
    4.95 +    /// \param map should be given to the constructor, since it is used
    4.96      /// internally to handle the cross references. The value of the map
    4.97      /// should be PRE_HEAP (-1) for each element.
    4.98      ///
    4.99 -    /// \param _comp The comparator function object.
   4.100 -    BinHeap(ItemIntMap &_iim, const Compare &_comp)
   4.101 -      : iim(_iim), comp(_comp) {}
   4.102 +    /// \param comp The comparator function object.
   4.103 +    BinHeap(ItemIntMap &map, const Compare &comp)
   4.104 +      : _iim(map), _comp(comp) {}
   4.105  
   4.106  
   4.107      /// The number of items stored in the heap.
   4.108      ///
   4.109      /// \brief Returns the number of items stored in the heap.
   4.110 -    int size() const { return data.size(); }
   4.111 +    int size() const { return _data.size(); }
   4.112  
   4.113      /// \brief Checks if the heap stores no items.
   4.114      ///
   4.115      /// Returns \c true if and only if the heap stores no items.
   4.116 -    bool empty() const { return data.empty(); }
   4.117 +    bool empty() const { return _data.empty(); }
   4.118  
   4.119      /// \brief Make empty this heap.
   4.120      ///
   4.121 @@ -120,7 +121,7 @@
   4.122      /// the heap and after that you should set the cross reference map for
   4.123      /// each item to \c PRE_HEAP.
   4.124      void clear() {
   4.125 -      data.clear();
   4.126 +      _data.clear();
   4.127      }
   4.128  
   4.129    private:
   4.130 @@ -128,13 +129,13 @@
   4.131  
   4.132      static int second_child(int i) { return 2*i+2; }
   4.133      bool less(const Pair &p1, const Pair &p2) const {
   4.134 -      return comp(p1.second, p2.second);
   4.135 +      return _comp(p1.second, p2.second);
   4.136      }
   4.137  
   4.138      int bubble_up(int hole, Pair p) {
   4.139        int par = parent(hole);
   4.140 -      while( hole>0 && less(p,data[par]) ) {
   4.141 -        move(data[par],hole);
   4.142 +      while( hole>0 && less(p,_data[par]) ) {
   4.143 +        move(_data[par],hole);
   4.144          hole = par;
   4.145          par = parent(hole);
   4.146        }
   4.147 @@ -145,18 +146,18 @@
   4.148      int bubble_down(int hole, Pair p, int length) {
   4.149        int child = second_child(hole);
   4.150        while(child < length) {
   4.151 -        if( less(data[child-1], data[child]) ) {
   4.152 +        if( less(_data[child-1], _data[child]) ) {
   4.153            --child;
   4.154          }
   4.155 -        if( !less(data[child], p) )
   4.156 +        if( !less(_data[child], p) )
   4.157            goto ok;
   4.158 -        move(data[child], hole);
   4.159 +        move(_data[child], hole);
   4.160          hole = child;
   4.161          child = second_child(hole);
   4.162        }
   4.163        child--;
   4.164 -      if( child<length && less(data[child], p) ) {
   4.165 -        move(data[child], hole);
   4.166 +      if( child<length && less(_data[child], p) ) {
   4.167 +        move(_data[child], hole);
   4.168          hole=child;
   4.169        }
   4.170      ok:
   4.171 @@ -165,8 +166,8 @@
   4.172      }
   4.173  
   4.174      void move(const Pair &p, int i) {
   4.175 -      data[i] = p;
   4.176 -      iim.set(p.first, i);
   4.177 +      _data[i] = p;
   4.178 +      _iim.set(p.first, i);
   4.179      }
   4.180  
   4.181    public:
   4.182 @@ -175,8 +176,8 @@
   4.183      /// Adds \c p.first to the heap with priority \c p.second.
   4.184      /// \param p The pair to insert.
   4.185      void push(const Pair &p) {
   4.186 -      int n = data.size();
   4.187 -      data.resize(n+1);
   4.188 +      int n = _data.size();
   4.189 +      _data.resize(n+1);
   4.190        bubble_up(n, p);
   4.191      }
   4.192  
   4.193 @@ -193,7 +194,7 @@
   4.194      /// Compare.
   4.195      /// \pre The heap must be nonempty.
   4.196      Item top() const {
   4.197 -      return data[0].first;
   4.198 +      return _data[0].first;
   4.199      }
   4.200  
   4.201      /// \brief Returns the minimum priority relative to \c Compare.
   4.202 @@ -201,7 +202,7 @@
   4.203      /// It returns the minimum priority relative to \c Compare.
   4.204      /// \pre The heap must be nonempty.
   4.205      Prio prio() const {
   4.206 -      return data[0].second;
   4.207 +      return _data[0].second;
   4.208      }
   4.209  
   4.210      /// \brief Deletes the item with minimum priority relative to \c Compare.
   4.211 @@ -210,12 +211,12 @@
   4.212      /// Compare from the heap.
   4.213      /// \pre The heap must be non-empty.
   4.214      void pop() {
   4.215 -      int n = data.size()-1;
   4.216 -      iim.set(data[0].first, POST_HEAP);
   4.217 +      int n = _data.size()-1;
   4.218 +      _iim.set(_data[0].first, POST_HEAP);
   4.219        if (n > 0) {
   4.220 -        bubble_down(0, data[n], n);
   4.221 +        bubble_down(0, _data[n], n);
   4.222        }
   4.223 -      data.pop_back();
   4.224 +      _data.pop_back();
   4.225      }
   4.226  
   4.227      /// \brief Deletes \c i from the heap.
   4.228 @@ -224,26 +225,26 @@
   4.229      /// \param i The item to erase.
   4.230      /// \pre The item should be in the heap.
   4.231      void erase(const Item &i) {
   4.232 -      int h = iim[i];
   4.233 -      int n = data.size()-1;
   4.234 -      iim.set(data[h].first, POST_HEAP);
   4.235 +      int h = _iim[i];
   4.236 +      int n = _data.size()-1;
   4.237 +      _iim.set(_data[h].first, POST_HEAP);
   4.238        if( h < n ) {
   4.239 -        if ( bubble_up(h, data[n]) == h) {
   4.240 -          bubble_down(h, data[n], n);
   4.241 +        if ( bubble_up(h, _data[n]) == h) {
   4.242 +          bubble_down(h, _data[n], n);
   4.243          }
   4.244        }
   4.245 -      data.pop_back();
   4.246 +      _data.pop_back();
   4.247      }
   4.248  
   4.249  
   4.250      /// \brief Returns the priority of \c i.
   4.251      ///
   4.252      /// This function returns the priority of item \c i.
   4.253 +    /// \param i The item.
   4.254      /// \pre \c i must be in the heap.
   4.255 -    /// \param i The item.
   4.256      Prio operator[](const Item &i) const {
   4.257 -      int idx = iim[i];
   4.258 -      return data[idx].second;
   4.259 +      int idx = _iim[i];
   4.260 +      return _data[idx].second;
   4.261      }
   4.262  
   4.263      /// \brief \c i gets to the heap with priority \c p independently
   4.264 @@ -254,40 +255,40 @@
   4.265      /// \param i The item.
   4.266      /// \param p The priority.
   4.267      void set(const Item &i, const Prio &p) {
   4.268 -      int idx = iim[i];
   4.269 +      int idx = _iim[i];
   4.270        if( idx < 0 ) {
   4.271          push(i,p);
   4.272        }
   4.273 -      else if( comp(p, data[idx].second) ) {
   4.274 +      else if( _comp(p, _data[idx].second) ) {
   4.275          bubble_up(idx, Pair(i,p));
   4.276        }
   4.277        else {
   4.278 -        bubble_down(idx, Pair(i,p), data.size());
   4.279 +        bubble_down(idx, Pair(i,p), _data.size());
   4.280        }
   4.281      }
   4.282  
   4.283      /// \brief Decreases the priority of \c i to \c p.
   4.284      ///
   4.285      /// This method decreases the priority of item \c i to \c p.
   4.286 +    /// \param i The item.
   4.287 +    /// \param p The priority.
   4.288      /// \pre \c i must be stored in the heap with priority at least \c
   4.289      /// p relative to \c Compare.
   4.290 -    /// \param i The item.
   4.291 -    /// \param p The priority.
   4.292      void decrease(const Item &i, const Prio &p) {
   4.293 -      int idx = iim[i];
   4.294 +      int idx = _iim[i];
   4.295        bubble_up(idx, Pair(i,p));
   4.296      }
   4.297  
   4.298      /// \brief Increases the priority of \c i to \c p.
   4.299      ///
   4.300      /// This method sets the priority of item \c i to \c p.
   4.301 +    /// \param i The item.
   4.302 +    /// \param p The priority.
   4.303      /// \pre \c i must be stored in the heap with priority at most \c
   4.304      /// p relative to \c Compare.
   4.305 -    /// \param i The item.
   4.306 -    /// \param p The priority.
   4.307      void increase(const Item &i, const Prio &p) {
   4.308 -      int idx = iim[i];
   4.309 -      bubble_down(idx, Pair(i,p), data.size());
   4.310 +      int idx = _iim[i];
   4.311 +      bubble_down(idx, Pair(i,p), _data.size());
   4.312      }
   4.313  
   4.314      /// \brief Returns if \c item is in, has already been in, or has
   4.315 @@ -299,7 +300,7 @@
   4.316      /// get back to the heap again.
   4.317      /// \param i The item.
   4.318      State state(const Item &i) const {
   4.319 -      int s = iim[i];
   4.320 +      int s = _iim[i];
   4.321        if( s>=0 )
   4.322          s=0;
   4.323        return State(s);
   4.324 @@ -319,7 +320,7 @@
   4.325          if (state(i) == IN_HEAP) {
   4.326            erase(i);
   4.327          }
   4.328 -        iim[i] = st;
   4.329 +        _iim[i] = st;
   4.330          break;
   4.331        case IN_HEAP:
   4.332          break;
   4.333 @@ -333,10 +334,10 @@
   4.334      /// \c i item will out of the heap and \c j will be in the heap
   4.335      /// with the same prioriority as prevoiusly the \c i item.
   4.336      void replace(const Item& i, const Item& j) {
   4.337 -      int idx = iim[i];
   4.338 -      iim.set(i, iim[j]);
   4.339 -      iim.set(j, idx);
   4.340 -      data[idx].first = j;
   4.341 +      int idx = _iim[i];
   4.342 +      _iim.set(i, _iim[j]);
   4.343 +      _iim.set(j, idx);
   4.344 +      _data[idx].first = j;
   4.345      }
   4.346  
   4.347    }; // class BinHeap
     5.1 --- a/lemon/bits/edge_set_extender.h	Thu Mar 05 10:13:20 2009 +0000
     5.2 +++ b/lemon/bits/edge_set_extender.h	Sun Mar 29 23:08:20 2009 +0200
     5.3 @@ -24,14 +24,14 @@
     5.4  #include <lemon/bits/default_map.h>
     5.5  #include <lemon/bits/map_extender.h>
     5.6  
     5.7 -///\ingroup digraphbits
     5.8 -///\file
     5.9 -///\brief Extenders for the arc set types
    5.10 +//\ingroup digraphbits
    5.11 +//\file
    5.12 +//\brief Extenders for the arc set types
    5.13  namespace lemon {
    5.14  
    5.15 -  /// \ingroup digraphbits
    5.16 -  ///
    5.17 -  /// \brief Extender for the ArcSets
    5.18 +  // \ingroup digraphbits
    5.19 +  //
    5.20 +  // \brief Extender for the ArcSets
    5.21    template <typename Base>
    5.22    class ArcSetExtender : public Base {
    5.23    public:
    5.24 @@ -72,7 +72,7 @@
    5.25  
    5.26      // Alteration notifier extensions
    5.27  
    5.28 -    /// The arc observer registry.
    5.29 +    // The arc observer registry.
    5.30      typedef AlterationNotifier<ArcSetExtender, Arc> ArcNotifier;
    5.31  
    5.32    protected:
    5.33 @@ -83,9 +83,7 @@
    5.34  
    5.35      using Parent::notifier;
    5.36  
    5.37 -    /// \brief Gives back the arc alteration notifier.
    5.38 -    ///
    5.39 -    /// Gives back the arc alteration notifier.
    5.40 +    // Gives back the arc alteration notifier.
    5.41      ArcNotifier& notifier(Arc) const {
    5.42        return arc_notifier;
    5.43      }
    5.44 @@ -185,30 +183,30 @@
    5.45  
    5.46      };
    5.47  
    5.48 -    /// \brief Base node of the iterator
    5.49 -    ///
    5.50 -    /// Returns the base node (ie. the source in this case) of the iterator
    5.51 +    // \brief Base node of the iterator
    5.52 +    //
    5.53 +    // Returns the base node (ie. the source in this case) of the iterator
    5.54      Node baseNode(const OutArcIt &e) const {
    5.55        return Parent::source(static_cast<const Arc&>(e));
    5.56      }
    5.57 -    /// \brief Running node of the iterator
    5.58 -    ///
    5.59 -    /// Returns the running node (ie. the target in this case) of the
    5.60 -    /// iterator
    5.61 +    // \brief Running node of the iterator
    5.62 +    //
    5.63 +    // Returns the running node (ie. the target in this case) of the
    5.64 +    // iterator
    5.65      Node runningNode(const OutArcIt &e) const {
    5.66        return Parent::target(static_cast<const Arc&>(e));
    5.67      }
    5.68  
    5.69 -    /// \brief Base node of the iterator
    5.70 -    ///
    5.71 -    /// Returns the base node (ie. the target in this case) of the iterator
    5.72 +    // \brief Base node of the iterator
    5.73 +    //
    5.74 +    // Returns the base node (ie. the target in this case) of the iterator
    5.75      Node baseNode(const InArcIt &e) const {
    5.76        return Parent::target(static_cast<const Arc&>(e));
    5.77      }
    5.78 -    /// \brief Running node of the iterator
    5.79 -    ///
    5.80 -    /// Returns the running node (ie. the source in this case) of the
    5.81 -    /// iterator
    5.82 +    // \brief Running node of the iterator
    5.83 +    //
    5.84 +    // Returns the running node (ie. the source in this case) of the
    5.85 +    // iterator
    5.86      Node runningNode(const InArcIt &e) const {
    5.87        return Parent::source(static_cast<const Arc&>(e));
    5.88      }
    5.89 @@ -271,9 +269,9 @@
    5.90    };
    5.91  
    5.92  
    5.93 -  /// \ingroup digraphbits
    5.94 -  ///
    5.95 -  /// \brief Extender for the EdgeSets
    5.96 +  // \ingroup digraphbits
    5.97 +  //
    5.98 +  // \brief Extender for the EdgeSets
    5.99    template <typename Base>
   5.100    class EdgeSetExtender : public Base {
   5.101  
   5.102 @@ -492,43 +490,43 @@
   5.103        }
   5.104      };
   5.105  
   5.106 -    /// \brief Base node of the iterator
   5.107 -    ///
   5.108 -    /// Returns the base node (ie. the source in this case) of the iterator
   5.109 +    // \brief Base node of the iterator
   5.110 +    //
   5.111 +    // Returns the base node (ie. the source in this case) of the iterator
   5.112      Node baseNode(const OutArcIt &e) const {
   5.113        return Parent::source(static_cast<const Arc&>(e));
   5.114      }
   5.115 -    /// \brief Running node of the iterator
   5.116 -    ///
   5.117 -    /// Returns the running node (ie. the target in this case) of the
   5.118 -    /// iterator
   5.119 +    // \brief Running node of the iterator
   5.120 +    //
   5.121 +    // Returns the running node (ie. the target in this case) of the
   5.122 +    // iterator
   5.123      Node runningNode(const OutArcIt &e) const {
   5.124        return Parent::target(static_cast<const Arc&>(e));
   5.125      }
   5.126  
   5.127 -    /// \brief Base node of the iterator
   5.128 -    ///
   5.129 -    /// Returns the base node (ie. the target in this case) of the iterator
   5.130 +    // \brief Base node of the iterator
   5.131 +    //
   5.132 +    // Returns the base node (ie. the target in this case) of the iterator
   5.133      Node baseNode(const InArcIt &e) const {
   5.134        return Parent::target(static_cast<const Arc&>(e));
   5.135      }
   5.136 -    /// \brief Running node of the iterator
   5.137 -    ///
   5.138 -    /// Returns the running node (ie. the source in this case) of the
   5.139 -    /// iterator
   5.140 +    // \brief Running node of the iterator
   5.141 +    //
   5.142 +    // Returns the running node (ie. the source in this case) of the
   5.143 +    // iterator
   5.144      Node runningNode(const InArcIt &e) const {
   5.145        return Parent::source(static_cast<const Arc&>(e));
   5.146      }
   5.147  
   5.148 -    /// Base node of the iterator
   5.149 -    ///
   5.150 -    /// Returns the base node of the iterator
   5.151 +    // Base node of the iterator
   5.152 +    //
   5.153 +    // Returns the base node of the iterator
   5.154      Node baseNode(const IncEdgeIt &e) const {
   5.155        return e.direction ? u(e) : v(e);
   5.156      }
   5.157 -    /// Running node of the iterator
   5.158 -    ///
   5.159 -    /// Returns the running node of the iterator
   5.160 +    // Running node of the iterator
   5.161 +    //
   5.162 +    // Returns the running node of the iterator
   5.163      Node runningNode(const IncEdgeIt &e) const {
   5.164        return e.direction ? v(e) : u(e);
   5.165      }
     6.1 --- a/lemon/circulation.h	Thu Mar 05 10:13:20 2009 +0000
     6.2 +++ b/lemon/circulation.h	Sun Mar 29 23:08:20 2009 +0200
     6.3 @@ -215,9 +215,9 @@
     6.4  
     6.5      ///@{
     6.6  
     6.7 -    template <typename _FlowMap>
     6.8 +    template <typename T>
     6.9      struct SetFlowMapTraits : public Traits {
    6.10 -      typedef _FlowMap FlowMap;
    6.11 +      typedef T FlowMap;
    6.12        static FlowMap *createFlowMap(const Digraph&) {
    6.13          LEMON_ASSERT(false, "FlowMap is not initialized");
    6.14          return 0; // ignore warnings
    6.15 @@ -229,17 +229,17 @@
    6.16      ///
    6.17      /// \ref named-templ-param "Named parameter" for setting FlowMap
    6.18      /// type.
    6.19 -    template <typename _FlowMap>
    6.20 +    template <typename T>
    6.21      struct SetFlowMap
    6.22        : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
    6.23 -                           SetFlowMapTraits<_FlowMap> > {
    6.24 +                           SetFlowMapTraits<T> > {
    6.25        typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
    6.26 -                          SetFlowMapTraits<_FlowMap> > Create;
    6.27 +                          SetFlowMapTraits<T> > Create;
    6.28      };
    6.29  
    6.30 -    template <typename _Elevator>
    6.31 +    template <typename T>
    6.32      struct SetElevatorTraits : public Traits {
    6.33 -      typedef _Elevator Elevator;
    6.34 +      typedef T Elevator;
    6.35        static Elevator *createElevator(const Digraph&, int) {
    6.36          LEMON_ASSERT(false, "Elevator is not initialized");
    6.37          return 0; // ignore warnings
    6.38 @@ -255,17 +255,17 @@
    6.39      /// \ref elevator(Elevator&) "elevator()" function before calling
    6.40      /// \ref run() or \ref init().
    6.41      /// \sa SetStandardElevator
    6.42 -    template <typename _Elevator>
    6.43 +    template <typename T>
    6.44      struct SetElevator
    6.45        : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
    6.46 -                           SetElevatorTraits<_Elevator> > {
    6.47 +                           SetElevatorTraits<T> > {
    6.48        typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
    6.49 -                          SetElevatorTraits<_Elevator> > Create;
    6.50 +                          SetElevatorTraits<T> > Create;
    6.51      };
    6.52  
    6.53 -    template <typename _Elevator>
    6.54 +    template <typename T>
    6.55      struct SetStandardElevatorTraits : public Traits {
    6.56 -      typedef _Elevator Elevator;
    6.57 +      typedef T Elevator;
    6.58        static Elevator *createElevator(const Digraph& digraph, int max_level) {
    6.59          return new Elevator(digraph, max_level);
    6.60        }
    6.61 @@ -283,12 +283,12 @@
    6.62      /// algorithm with the \ref elevator(Elevator&) "elevator()" function
    6.63      /// before calling \ref run() or \ref init().
    6.64      /// \sa SetElevator
    6.65 -    template <typename _Elevator>
    6.66 +    template <typename T>
    6.67      struct SetStandardElevator
    6.68        : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
    6.69 -                       SetStandardElevatorTraits<_Elevator> > {
    6.70 +                       SetStandardElevatorTraits<T> > {
    6.71        typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
    6.72 -                      SetStandardElevatorTraits<_Elevator> > Create;
    6.73 +                      SetStandardElevatorTraits<T> > Create;
    6.74      };
    6.75  
    6.76      /// @}
    6.77 @@ -682,7 +682,7 @@
    6.78      /// empty set, so \c bar[v] will be \c false for all nodes \c v.
    6.79      ///
    6.80      /// \note This function calls \ref barrier() for each node,
    6.81 -    /// so it runs in \f$O(n)\f$ time.
    6.82 +    /// so it runs in O(n) time.
    6.83      ///
    6.84      /// \pre Either \ref run() or \ref init() must be called before
    6.85      /// using this function.
     7.1 --- a/lemon/concepts/graph.h	Thu Mar 05 10:13:20 2009 +0000
     7.2 +++ b/lemon/concepts/graph.h	Sun Mar 29 23:08:20 2009 +0200
     7.3 @@ -601,23 +601,35 @@
     7.4  
     7.5        /// \brief Opposite node on an arc
     7.6        ///
     7.7 -      /// \return the opposite of the given Node on the given Edge
     7.8 +      /// \return The opposite of the given node on the given edge.
     7.9        Node oppositeNode(Node, Edge) const { return INVALID; }
    7.10  
    7.11        /// \brief First node of the edge.
    7.12        ///
    7.13 -      /// \return the first node of the given Edge.
    7.14 +      /// \return The first node of the given edge.
    7.15        ///
    7.16        /// Naturally edges don't have direction and thus
    7.17 -      /// don't have source and target node. But we use these two methods
    7.18 -      /// to query the two nodes of the arc. The direction of the arc
    7.19 -      /// which arises this way is called the inherent direction of the
    7.20 +      /// don't have source and target node. However we use \c u() and \c v()
    7.21 +      /// methods to query the two nodes of the arc. The direction of the
    7.22 +      /// arc which arises this way is called the inherent direction of the
    7.23        /// edge, and is used to define the "default" direction
    7.24        /// of the directed versions of the arcs.
    7.25 -      /// \sa direction
    7.26 +      /// \sa v()
    7.27 +      /// \sa direction()
    7.28        Node u(Edge) const { return INVALID; }
    7.29  
    7.30        /// \brief Second node of the edge.
    7.31 +      ///
    7.32 +      /// \return The second node of the given edge.
    7.33 +      ///
    7.34 +      /// Naturally edges don't have direction and thus
    7.35 +      /// don't have source and target node. However we use \c u() and \c v()
    7.36 +      /// methods to query the two nodes of the arc. The direction of the
    7.37 +      /// arc which arises this way is called the inherent direction of the
    7.38 +      /// edge, and is used to define the "default" direction
    7.39 +      /// of the directed versions of the arcs.
    7.40 +      /// \sa u()
    7.41 +      /// \sa direction()
    7.42        Node v(Edge) const { return INVALID; }
    7.43  
    7.44        /// \brief Source node of the directed arc.
     8.1 --- a/lemon/concepts/graph_components.h	Thu Mar 05 10:13:20 2009 +0000
     8.2 +++ b/lemon/concepts/graph_components.h	Sun Mar 29 23:08:20 2009 +0200
     8.3 @@ -20,7 +20,6 @@
     8.4  ///\file
     8.5  ///\brief The concept of graph components.
     8.6  
     8.7 -
     8.8  #ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
     8.9  #define LEMON_CONCEPTS_GRAPH_COMPONENTS_H
    8.10  
    8.11 @@ -44,7 +43,7 @@
    8.12      /// with 'a'.
    8.13  
    8.14  #ifndef DOXYGEN
    8.15 -    template <char _selector = '0'>
    8.16 +    template <char sel = '0'>
    8.17  #endif
    8.18      class GraphItem {
    8.19      public:
    8.20 @@ -296,11 +295,11 @@
    8.21      /// core id functions for the digraph structure.
    8.22      /// The most of the base digraphs should conform to this concept.
    8.23      /// The id's are unique and immutable.
    8.24 -    template <typename _Base = BaseDigraphComponent>
    8.25 -    class IDableDigraphComponent : public _Base {
    8.26 +    template <typename BAS = BaseDigraphComponent>
    8.27 +    class IDableDigraphComponent : public BAS {
    8.28      public:
    8.29  
    8.30 -      typedef _Base Base;
    8.31 +      typedef BAS Base;
    8.32        typedef typename Base::Node Node;
    8.33        typedef typename Base::Arc Arc;
    8.34  
    8.35 @@ -374,14 +373,14 @@
    8.36      /// core id functions for the undirected graph structure.  The
    8.37      /// most of the base undirected graphs should conform to this
    8.38      /// concept.  The id's are unique and immutable.
    8.39 -    template <typename _Base = BaseGraphComponent>
    8.40 -    class IDableGraphComponent : public IDableDigraphComponent<_Base> {
    8.41 +    template <typename BAS = BaseGraphComponent>
    8.42 +    class IDableGraphComponent : public IDableDigraphComponent<BAS> {
    8.43      public:
    8.44  
    8.45 -      typedef _Base Base;
    8.46 +      typedef BAS Base;
    8.47        typedef typename Base::Edge Edge;
    8.48  
    8.49 -      using IDableDigraphComponent<_Base>::id;
    8.50 +      using IDableDigraphComponent<Base>::id;
    8.51  
    8.52        /// \brief Gives back an unique integer id for the Edge.
    8.53        ///
    8.54 @@ -425,8 +424,8 @@
    8.55      ///
    8.56      /// Skeleton class for graph NodeIt and ArcIt.
    8.57      ///
    8.58 -    template <typename _Graph, typename _Item>
    8.59 -    class GraphItemIt : public _Item {
    8.60 +    template <typename GR, typename Item>
    8.61 +    class GraphItemIt : public Item {
    8.62      public:
    8.63        /// \brief Default constructor.
    8.64        ///
    8.65 @@ -442,7 +441,7 @@
    8.66        ///
    8.67        /// Sets the iterator to the first item of \c the graph.
    8.68        ///
    8.69 -      explicit GraphItemIt(const _Graph&) {}
    8.70 +      explicit GraphItemIt(const GR&) {}
    8.71        /// \brief Invalid constructor \& conversion.
    8.72        ///
    8.73        /// This constructor initializes the item to be invalid.
    8.74 @@ -479,24 +478,24 @@
    8.75            ++it2 = it1;
    8.76            ++(++it1);
    8.77  
    8.78 -          _Item bi = it1;
    8.79 +          Item bi = it1;
    8.80            bi = it2;
    8.81          }
    8.82 -        _Graph& g;
    8.83 +        GR& g;
    8.84        };
    8.85      };
    8.86  
    8.87      /// \brief Skeleton class for graph InArcIt and OutArcIt
    8.88      ///
    8.89      /// \note Because InArcIt and OutArcIt may not inherit from the same
    8.90 -    /// base class, the _selector is a additional template parameter. For
    8.91 -    /// InArcIt you should instantiate it with character 'i' and for
    8.92 +    /// base class, the \c sel is a additional template parameter (selector).
    8.93 +    /// For InArcIt you should instantiate it with character 'i' and for
    8.94      /// OutArcIt with 'o'.
    8.95 -    template <typename _Graph,
    8.96 -              typename _Item = typename _Graph::Arc,
    8.97 -              typename _Base = typename _Graph::Node,
    8.98 -              char _selector = '0'>
    8.99 -    class GraphIncIt : public _Item {
   8.100 +    template <typename GR,
   8.101 +              typename Item = typename GR::Arc,
   8.102 +              typename Base = typename GR::Node,
   8.103 +              char sel = '0'>
   8.104 +    class GraphIncIt : public Item {
   8.105      public:
   8.106        /// \brief Default constructor.
   8.107        ///
   8.108 @@ -507,14 +506,14 @@
   8.109        ///
   8.110        /// Copy constructor.
   8.111        ///
   8.112 -      GraphIncIt(GraphIncIt const& gi) : _Item(gi) {}
   8.113 +      GraphIncIt(GraphIncIt const& gi) : Item(gi) {}
   8.114        /// \brief Sets the iterator to the first arc incoming into or outgoing
   8.115        /// from the node.
   8.116        ///
   8.117        /// Sets the iterator to the first arc incoming into or outgoing
   8.118        /// from the node.
   8.119        ///
   8.120 -      explicit GraphIncIt(const _Graph&, const _Base&) {}
   8.121 +      explicit GraphIncIt(const GR&, const Base&) {}
   8.122        /// \brief Invalid constructor \& conversion.
   8.123        ///
   8.124        /// This constructor initializes the item to be invalid.
   8.125 @@ -546,21 +545,21 @@
   8.126        template <typename _GraphIncIt>
   8.127        struct Constraints {
   8.128          void constraints() {
   8.129 -          checkConcept<GraphItem<_selector>, _GraphIncIt>();
   8.130 +          checkConcept<GraphItem<sel>, _GraphIncIt>();
   8.131            _GraphIncIt it1(graph, node);
   8.132            _GraphIncIt it2;
   8.133  
   8.134            it2 = ++it1;
   8.135            ++it2 = it1;
   8.136            ++(++it1);
   8.137 -          _Item e = it1;
   8.138 +          Item e = it1;
   8.139            e = it2;
   8.140  
   8.141          }
   8.142  
   8.143 -        _Item arc;
   8.144 -        _Base node;
   8.145 -        _Graph graph;
   8.146 +        Item arc;
   8.147 +        Base node;
   8.148 +        GR graph;
   8.149          _GraphIncIt it;
   8.150        };
   8.151      };
   8.152 @@ -571,12 +570,12 @@
   8.153      /// This class provides beside the core digraph features
   8.154      /// iterator based iterable interface for the digraph structure.
   8.155      /// This concept is part of the Digraph concept.
   8.156 -    template <typename _Base = BaseDigraphComponent>
   8.157 -    class IterableDigraphComponent : public _Base {
   8.158 +    template <typename BAS = BaseDigraphComponent>
   8.159 +    class IterableDigraphComponent : public BAS {
   8.160  
   8.161      public:
   8.162  
   8.163 -      typedef _Base Base;
   8.164 +      typedef BAS Base;
   8.165        typedef typename Base::Node Node;
   8.166        typedef typename Base::Arc Arc;
   8.167  
   8.168 @@ -756,11 +755,11 @@
   8.169      /// This class provides beside the core graph features iterator
   8.170      /// based iterable interface for the undirected graph structure.
   8.171      /// This concept is part of the Graph concept.
   8.172 -    template <typename _Base = BaseGraphComponent>
   8.173 -    class IterableGraphComponent : public IterableDigraphComponent<_Base> {
   8.174 +    template <typename BAS = BaseGraphComponent>
   8.175 +    class IterableGraphComponent : public IterableDigraphComponent<BAS> {
   8.176      public:
   8.177  
   8.178 -      typedef _Base Base;
   8.179 +      typedef BAS Base;
   8.180        typedef typename Base::Node Node;
   8.181        typedef typename Base::Arc Arc;
   8.182        typedef typename Base::Edge Edge;
   8.183 @@ -773,8 +772,8 @@
   8.184        /// This interface provides functions for iteration on graph items
   8.185        /// @{
   8.186  
   8.187 -      using IterableDigraphComponent<_Base>::first;
   8.188 -      using IterableDigraphComponent<_Base>::next;
   8.189 +      using IterableDigraphComponent<Base>::first;
   8.190 +      using IterableDigraphComponent<Base>::next;
   8.191  
   8.192        /// \brief Gives back the first edge in the iterating
   8.193        /// order.
   8.194 @@ -808,8 +807,8 @@
   8.195        /// use it.
   8.196        void nextInc(Edge&, bool&) const {}
   8.197  
   8.198 -      using IterableDigraphComponent<_Base>::baseNode;
   8.199 -      using IterableDigraphComponent<_Base>::runningNode;
   8.200 +      using IterableDigraphComponent<Base>::baseNode;
   8.201 +      using IterableDigraphComponent<Base>::runningNode;
   8.202  
   8.203        /// @}
   8.204  
   8.205 @@ -875,7 +874,6 @@
   8.206          }
   8.207  
   8.208          const _Graph& graph;
   8.209 -
   8.210        };
   8.211      };
   8.212  
   8.213 @@ -887,11 +885,11 @@
   8.214      /// obsevers can be registered into the notifier and whenever an
   8.215      /// alteration occured in the digraph all the observers will
   8.216      /// notified about it.
   8.217 -    template <typename _Base = BaseDigraphComponent>
   8.218 -    class AlterableDigraphComponent : public _Base {
   8.219 +    template <typename BAS = BaseDigraphComponent>
   8.220 +    class AlterableDigraphComponent : public BAS {
   8.221      public:
   8.222  
   8.223 -      typedef _Base Base;
   8.224 +      typedef BAS Base;
   8.225        typedef typename Base::Node Node;
   8.226        typedef typename Base::Arc Arc;
   8.227  
   8.228 @@ -945,11 +943,11 @@
   8.229      /// obsevers can be registered into the notifier and whenever an
   8.230      /// alteration occured in the graph all the observers will
   8.231      /// notified about it.
   8.232 -    template <typename _Base = BaseGraphComponent>
   8.233 -    class AlterableGraphComponent : public AlterableDigraphComponent<_Base> {
   8.234 +    template <typename BAS = BaseGraphComponent>
   8.235 +    class AlterableGraphComponent : public AlterableDigraphComponent<BAS> {
   8.236      public:
   8.237  
   8.238 -      typedef _Base Base;
   8.239 +      typedef BAS Base;
   8.240        typedef typename Base::Edge Edge;
   8.241  
   8.242  
   8.243 @@ -974,9 +972,7 @@
   8.244          }
   8.245  
   8.246          const _Graph& graph;
   8.247 -
   8.248        };
   8.249 -
   8.250      };
   8.251  
   8.252      /// \brief Class describing the concept of graph maps
   8.253 @@ -984,18 +980,18 @@
   8.254      /// This class describes the common interface of the graph maps
   8.255      /// (NodeMap, ArcMap), that is maps that can be used to
   8.256      /// associate data to graph descriptors (nodes or arcs).
   8.257 -    template <typename _Graph, typename _Item, typename _Value>
   8.258 -    class GraphMap : public ReadWriteMap<_Item, _Value> {
   8.259 +    template <typename GR, typename K, typename V>
   8.260 +    class GraphMap : public ReadWriteMap<K, V> {
   8.261      public:
   8.262  
   8.263 -      typedef ReadWriteMap<_Item, _Value> Parent;
   8.264 +      typedef ReadWriteMap<K, V> Parent;
   8.265  
   8.266        /// The graph type of the map.
   8.267 -      typedef _Graph Graph;
   8.268 +      typedef GR Graph;
   8.269        /// The key type of the map.
   8.270 -      typedef _Item Key;
   8.271 +      typedef K Key;
   8.272        /// The value type of the map.
   8.273 -      typedef _Value Value;
   8.274 +      typedef V Value;
   8.275  
   8.276        /// \brief Construct a new map.
   8.277        ///
   8.278 @@ -1055,11 +1051,11 @@
   8.279      /// This class provides beside the core digraph features
   8.280      /// map interface for the digraph structure.
   8.281      /// This concept is part of the Digraph concept.
   8.282 -    template <typename _Base = BaseDigraphComponent>
   8.283 -    class MappableDigraphComponent : public _Base  {
   8.284 +    template <typename BAS = BaseDigraphComponent>
   8.285 +    class MappableDigraphComponent : public BAS  {
   8.286      public:
   8.287  
   8.288 -      typedef _Base Base;
   8.289 +      typedef BAS Base;
   8.290        typedef typename Base::Node Node;
   8.291        typedef typename Base::Arc Arc;
   8.292  
   8.293 @@ -1069,10 +1065,10 @@
   8.294        ///
   8.295        /// ReadWrite map of the nodes.
   8.296        ///
   8.297 -      template <typename _Value>
   8.298 -      class NodeMap : public GraphMap<Digraph, Node, _Value> {
   8.299 +      template <typename V>
   8.300 +      class NodeMap : public GraphMap<Digraph, Node, V> {
   8.301        public:
   8.302 -        typedef GraphMap<MappableDigraphComponent, Node, _Value> Parent;
   8.303 +        typedef GraphMap<MappableDigraphComponent, Node, V> Parent;
   8.304  
   8.305          /// \brief Construct a new map.
   8.306          ///
   8.307 @@ -1083,7 +1079,7 @@
   8.308          /// \brief Construct a new map with default value.
   8.309          ///
   8.310          /// Construct a new map for the digraph and initalise the values.
   8.311 -        NodeMap(const MappableDigraphComponent& digraph, const _Value& value)
   8.312 +        NodeMap(const MappableDigraphComponent& digraph, const V& value)
   8.313            : Parent(digraph, value) {}
   8.314  
   8.315        private:
   8.316 @@ -1097,7 +1093,7 @@
   8.317          /// Assign operator.
   8.318          template <typename CMap>
   8.319          NodeMap& operator=(const CMap&) {
   8.320 -          checkConcept<ReadMap<Node, _Value>, CMap>();
   8.321 +          checkConcept<ReadMap<Node, V>, CMap>();
   8.322            return *this;
   8.323          }
   8.324  
   8.325 @@ -1107,10 +1103,10 @@
   8.326        ///
   8.327        /// ReadWrite map of the arcs.
   8.328        ///
   8.329 -      template <typename _Value>
   8.330 -      class ArcMap : public GraphMap<Digraph, Arc, _Value> {
   8.331 +      template <typename V>
   8.332 +      class ArcMap : public GraphMap<Digraph, Arc, V> {
   8.333        public:
   8.334 -        typedef GraphMap<MappableDigraphComponent, Arc, _Value> Parent;
   8.335 +        typedef GraphMap<MappableDigraphComponent, Arc, V> Parent;
   8.336  
   8.337          /// \brief Construct a new map.
   8.338          ///
   8.339 @@ -1121,7 +1117,7 @@
   8.340          /// \brief Construct a new map with default value.
   8.341          ///
   8.342          /// Construct a new map for the digraph and initalise the values.
   8.343 -        ArcMap(const MappableDigraphComponent& digraph, const _Value& value)
   8.344 +        ArcMap(const MappableDigraphComponent& digraph, const V& value)
   8.345            : Parent(digraph, value) {}
   8.346  
   8.347        private:
   8.348 @@ -1135,7 +1131,7 @@
   8.349          /// Assign operator.
   8.350          template <typename CMap>
   8.351          ArcMap& operator=(const CMap&) {
   8.352 -          checkConcept<ReadMap<Arc, _Value>, CMap>();
   8.353 +          checkConcept<ReadMap<Arc, V>, CMap>();
   8.354            return *this;
   8.355          }
   8.356  
   8.357 @@ -1191,11 +1187,11 @@
   8.358      /// This class provides beside the core graph features
   8.359      /// map interface for the graph structure.
   8.360      /// This concept is part of the Graph concept.
   8.361 -    template <typename _Base = BaseGraphComponent>
   8.362 -    class MappableGraphComponent : public MappableDigraphComponent<_Base>  {
   8.363 +    template <typename BAS = BaseGraphComponent>
   8.364 +    class MappableGraphComponent : public MappableDigraphComponent<BAS>  {
   8.365      public:
   8.366  
   8.367 -      typedef _Base Base;
   8.368 +      typedef BAS Base;
   8.369        typedef typename Base::Edge Edge;
   8.370  
   8.371        typedef MappableGraphComponent Graph;
   8.372 @@ -1204,10 +1200,10 @@
   8.373        ///
   8.374        /// ReadWrite map of the edges.
   8.375        ///
   8.376 -      template <typename _Value>
   8.377 -      class EdgeMap : public GraphMap<Graph, Edge, _Value> {
   8.378 +      template <typename V>
   8.379 +      class EdgeMap : public GraphMap<Graph, Edge, V> {
   8.380        public:
   8.381 -        typedef GraphMap<MappableGraphComponent, Edge, _Value> Parent;
   8.382 +        typedef GraphMap<MappableGraphComponent, Edge, V> Parent;
   8.383  
   8.384          /// \brief Construct a new map.
   8.385          ///
   8.386 @@ -1218,7 +1214,7 @@
   8.387          /// \brief Construct a new map with default value.
   8.388          ///
   8.389          /// Construct a new map for the graph and initalise the values.
   8.390 -        EdgeMap(const MappableGraphComponent& graph, const _Value& value)
   8.391 +        EdgeMap(const MappableGraphComponent& graph, const V& value)
   8.392            : Parent(graph, value) {}
   8.393  
   8.394        private:
   8.395 @@ -1232,7 +1228,7 @@
   8.396          /// Assign operator.
   8.397          template <typename CMap>
   8.398          EdgeMap& operator=(const CMap&) {
   8.399 -          checkConcept<ReadMap<Edge, _Value>, CMap>();
   8.400 +          checkConcept<ReadMap<Edge, V>, CMap>();
   8.401            return *this;
   8.402          }
   8.403  
   8.404 @@ -1276,13 +1272,13 @@
   8.405      /// extendable interface for the digraph structure.  The main
   8.406      /// difference between the base and this interface is that the
   8.407      /// digraph alterations should handled already on this level.
   8.408 -    template <typename _Base = BaseDigraphComponent>
   8.409 -    class ExtendableDigraphComponent : public _Base {
   8.410 +    template <typename BAS = BaseDigraphComponent>
   8.411 +    class ExtendableDigraphComponent : public BAS {
   8.412      public:
   8.413 -      typedef _Base Base;
   8.414 +      typedef BAS Base;
   8.415  
   8.416 -      typedef typename _Base::Node Node;
   8.417 -      typedef typename _Base::Arc Arc;
   8.418 +      typedef typename Base::Node Node;
   8.419 +      typedef typename Base::Arc Arc;
   8.420  
   8.421        /// \brief Adds a new node to the digraph.
   8.422        ///
   8.423 @@ -1321,13 +1317,13 @@
   8.424      /// The main difference between the base and this interface is
   8.425      /// that the graph alterations should handled already on this
   8.426      /// level.
   8.427 -    template <typename _Base = BaseGraphComponent>
   8.428 -    class ExtendableGraphComponent : public _Base {
   8.429 +    template <typename BAS = BaseGraphComponent>
   8.430 +    class ExtendableGraphComponent : public BAS {
   8.431      public:
   8.432  
   8.433 -      typedef _Base Base;
   8.434 -      typedef typename _Base::Node Node;
   8.435 -      typedef typename _Base::Edge Edge;
   8.436 +      typedef BAS Base;
   8.437 +      typedef typename Base::Node Node;
   8.438 +      typedef typename Base::Edge Edge;
   8.439  
   8.440        /// \brief Adds a new node to the graph.
   8.441        ///
   8.442 @@ -1365,11 +1361,11 @@
   8.443      /// functions for the digraph structure. The main difference between
   8.444      /// the base and this interface is that the digraph alterations
   8.445      /// should handled already on this level.
   8.446 -    template <typename _Base = BaseDigraphComponent>
   8.447 -    class ErasableDigraphComponent : public _Base {
   8.448 +    template <typename BAS = BaseDigraphComponent>
   8.449 +    class ErasableDigraphComponent : public BAS {
   8.450      public:
   8.451  
   8.452 -      typedef _Base Base;
   8.453 +      typedef BAS Base;
   8.454        typedef typename Base::Node Node;
   8.455        typedef typename Base::Arc Arc;
   8.456  
   8.457 @@ -1405,11 +1401,11 @@
   8.458      /// core erase functions for the undirceted graph structure. The
   8.459      /// main difference between the base and this interface is that
   8.460      /// the graph alterations should handled already on this level.
   8.461 -    template <typename _Base = BaseGraphComponent>
   8.462 -    class ErasableGraphComponent : public _Base {
   8.463 +    template <typename BAS = BaseGraphComponent>
   8.464 +    class ErasableGraphComponent : public BAS {
   8.465      public:
   8.466  
   8.467 -      typedef _Base Base;
   8.468 +      typedef BAS Base;
   8.469        typedef typename Base::Node Node;
   8.470        typedef typename Base::Edge Edge;
   8.471  
   8.472 @@ -1445,11 +1441,11 @@
   8.473      /// functions for the digraph structure. The main difference between
   8.474      /// the base and this interface is that the digraph alterations
   8.475      /// should handled already on this level.
   8.476 -    template <typename _Base = BaseDigraphComponent>
   8.477 -    class ClearableDigraphComponent : public _Base {
   8.478 +    template <typename BAS = BaseDigraphComponent>
   8.479 +    class ClearableDigraphComponent : public BAS {
   8.480      public:
   8.481  
   8.482 -      typedef _Base Base;
   8.483 +      typedef BAS Base;
   8.484  
   8.485        /// \brief Erase all nodes and arcs from the digraph.
   8.486        ///
   8.487 @@ -1474,11 +1470,11 @@
   8.488      /// core clear functions for the undirected graph structure. The
   8.489      /// main difference between the base and this interface is that
   8.490      /// the graph alterations should handled already on this level.
   8.491 -    template <typename _Base = BaseGraphComponent>
   8.492 -    class ClearableGraphComponent : public ClearableDigraphComponent<_Base> {
   8.493 +    template <typename BAS = BaseGraphComponent>
   8.494 +    class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {
   8.495      public:
   8.496  
   8.497 -      typedef _Base Base;
   8.498 +      typedef BAS Base;
   8.499  
   8.500        template <typename _Graph>
   8.501        struct Constraints {
     9.1 --- a/lemon/concepts/heap.h	Thu Mar 05 10:13:20 2009 +0000
     9.2 +++ b/lemon/concepts/heap.h	Sun Mar 29 23:08:20 2009 +0200
     9.3 @@ -35,17 +35,32 @@
     9.4  
     9.5      /// \brief The heap concept.
     9.6      ///
     9.7 -    /// Concept class describing the main interface of heaps.
     9.8 -    template <typename Priority, typename ItemIntMap>
     9.9 +    /// Concept class describing the main interface of heaps. A \e heap
    9.10 +    /// is a data structure for storing items with specified values called
    9.11 +    /// \e priorities in such a way that finding the item with minimum
    9.12 +    /// priority is efficient. In a heap one can change the priority of an
    9.13 +    /// item, add or erase an item, etc.
    9.14 +    ///
    9.15 +    /// \tparam PR Type of the priority of the items.
    9.16 +    /// \tparam IM A read and writable item map with int values, used
    9.17 +    /// internally to handle the cross references.
    9.18 +    /// \tparam Comp A functor class for the ordering of the priorities.
    9.19 +    /// The default is \c std::less<PR>.
    9.20 +#ifdef DOXYGEN
    9.21 +    template <typename PR, typename IM, typename Comp = std::less<PR> >
    9.22 +#else
    9.23 +    template <typename PR, typename IM>
    9.24 +#endif
    9.25      class Heap {
    9.26      public:
    9.27  
    9.28 +      /// Type of the item-int map.
    9.29 +      typedef IM ItemIntMap;
    9.30 +      /// Type of the priorities.
    9.31 +      typedef PR Prio;
    9.32        /// Type of the items stored in the heap.
    9.33        typedef typename ItemIntMap::Key Item;
    9.34  
    9.35 -      /// Type of the priorities.
    9.36 -      typedef Priority Prio;
    9.37 -
    9.38        /// \brief Type to represent the states of the items.
    9.39        ///
    9.40        /// Each item has a state associated to it. It can be "in heap",
    9.41 @@ -53,12 +68,12 @@
    9.42        /// from the point of view of the heap, but may be useful for
    9.43        /// the user.
    9.44        ///
    9.45 -      /// The \c ItemIntMap must be initialized in such a way, that it
    9.46 -      /// assigns \c PRE_HEAP (<tt>-1</tt>) to every item.
    9.47 +      /// The item-int map must be initialized in such way that it assigns
    9.48 +      /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
    9.49        enum State {
    9.50 -        IN_HEAP = 0,
    9.51 -        PRE_HEAP = -1,
    9.52 -        POST_HEAP = -2
    9.53 +        IN_HEAP = 0,    ///< The "in heap" state constant.
    9.54 +        PRE_HEAP = -1,  ///< The "pre heap" state constant.
    9.55 +        POST_HEAP = -2  ///< The "post heap" state constant.
    9.56        };
    9.57  
    9.58        /// \brief The constructor.
    9.59 @@ -119,8 +134,8 @@
    9.60        /// \brief The priority of an item.
    9.61        ///
    9.62        /// Returns the priority of the given item.
    9.63 +      /// \param i The item.
    9.64        /// \pre \c i must be in the heap.
    9.65 -      /// \param i The item.
    9.66        Prio operator[](const Item &i) const {}
    9.67  
    9.68        /// \brief Sets the priority of an item or inserts it, if it is
    9.69 @@ -137,17 +152,17 @@
    9.70        /// \brief Decreases the priority of an item to the given value.
    9.71        ///
    9.72        /// Decreases the priority of an item to the given value.
    9.73 -      /// \pre \c i must be stored in the heap with priority at least \c p.
    9.74        /// \param i The item.
    9.75        /// \param p The priority.
    9.76 +      /// \pre \c i must be stored in the heap with priority at least \c p.
    9.77        void decrease(const Item &i, const Prio &p) {}
    9.78  
    9.79        /// \brief Increases the priority of an item to the given value.
    9.80        ///
    9.81        /// Increases the priority of an item to the given value.
    9.82 -      /// \pre \c i must be stored in the heap with priority at most \c p.
    9.83        /// \param i The item.
    9.84        /// \param p The priority.
    9.85 +      /// \pre \c i must be stored in the heap with priority at most \c p.
    9.86        void increase(const Item &i, const Prio &p) {}
    9.87  
    9.88        /// \brief Returns if an item is in, has already been in, or has
    10.1 --- a/lemon/concepts/path.h	Thu Mar 05 10:13:20 2009 +0000
    10.2 +++ b/lemon/concepts/path.h	Sun Mar 29 23:08:20 2009 +0200
    10.3 @@ -38,19 +38,19 @@
    10.4      ///
    10.5      /// A skeleton structure for representing directed paths in a
    10.6      /// digraph.
    10.7 -    /// \tparam _Digraph The digraph type in which the path is.
    10.8 +    /// \tparam GR The digraph type in which the path is.
    10.9      ///
   10.10      /// In a sense, the path can be treated as a list of arcs. The
   10.11      /// lemon path type stores just this list. As a consequence it
   10.12      /// cannot enumerate the nodes in the path and the zero length
   10.13      /// paths cannot store the source.
   10.14      ///
   10.15 -    template <typename _Digraph>
   10.16 +    template <typename GR>
   10.17      class Path {
   10.18      public:
   10.19  
   10.20        /// Type of the underlying digraph.
   10.21 -      typedef _Digraph Digraph;
   10.22 +      typedef GR Digraph;
   10.23        /// Arc type of the underlying digraph.
   10.24        typedef typename Digraph::Arc Arc;
   10.25  
   10.26 @@ -205,18 +205,17 @@
   10.27      /// LEMON such algorithms gives back a path dumper what can
   10.28      /// assigned to a real path and the dumpers can be implemented as
   10.29      /// an adaptor class to the predecessor map.
   10.30 -
   10.31 -    /// \tparam _Digraph  The digraph type in which the path is.
   10.32 +    ///
   10.33 +    /// \tparam GR The digraph type in which the path is.
   10.34      ///
   10.35      /// The paths can be constructed from any path type by a
   10.36      /// template constructor or a template assignment operator.
   10.37 -    ///
   10.38 -    template <typename _Digraph>
   10.39 +    template <typename GR>
   10.40      class PathDumper {
   10.41      public:
   10.42  
   10.43        /// Type of the underlying digraph.
   10.44 -      typedef _Digraph Digraph;
   10.45 +      typedef GR Digraph;
   10.46        /// Arc type of the underlying digraph.
   10.47        typedef typename Digraph::Arc Arc;
   10.48  
    11.1 --- a/lemon/connectivity.h	Thu Mar 05 10:13:20 2009 +0000
    11.2 +++ b/lemon/connectivity.h	Sun Mar 29 23:08:20 2009 +0200
    11.3 @@ -46,7 +46,7 @@
    11.4    ///
    11.5    /// Check whether the given undirected graph is connected.
    11.6    /// \param graph The undirected graph.
    11.7 -  /// \return %True when there is path between any two nodes in the graph.
    11.8 +  /// \return \c true when there is path between any two nodes in the graph.
    11.9    /// \note By definition, the empty graph is connected.
   11.10    template <typename Graph>
   11.11    bool connected(const Graph& graph) {
   11.12 @@ -234,7 +234,7 @@
   11.13    /// Check whether the given directed graph is strongly connected. The
   11.14    /// graph is strongly connected when any two nodes of the graph are
   11.15    /// connected with directed paths in both direction.
   11.16 -  /// \return %False when the graph is not strongly connected.
   11.17 +  /// \return \c false when the graph is not strongly connected.
   11.18    /// \see connected
   11.19    ///
   11.20    /// \note By definition, the empty graph is strongly connected.
   11.21 @@ -709,7 +709,7 @@
   11.22    /// on same circle.
   11.23    ///
   11.24    /// \param graph The graph.
   11.25 -  /// \return %True when the graph bi-node-connected.
   11.26 +  /// \return \c true when the graph bi-node-connected.
   11.27    template <typename Graph>
   11.28    bool biNodeConnected(const Graph& graph) {
   11.29      return countBiNodeConnectedComponents(graph) <= 1;
   11.30 @@ -1230,7 +1230,7 @@
   11.31    /// from 0 to the number of the nodes in the graph minus one. Each values
   11.32    /// of the map will be set exactly once, the values will be set descending
   11.33    /// order.
   11.34 -  /// \return %False when the graph is not DAG.
   11.35 +  /// \return \c false when the graph is not DAG.
   11.36    ///
   11.37    /// \see topologicalSort
   11.38    /// \see dag
   11.39 @@ -1279,7 +1279,7 @@
   11.40    ///
   11.41    /// Check that the given directed graph is a DAG. The DAG is
   11.42    /// an Directed Acyclic Digraph.
   11.43 -  /// \return %False when the graph is not DAG.
   11.44 +  /// \return \c false when the graph is not DAG.
   11.45    /// \see acyclic
   11.46    template <typename Digraph>
   11.47    bool dag(const Digraph& digraph) {
   11.48 @@ -1321,7 +1321,7 @@
   11.49    ///
   11.50    /// Check that the given undirected graph acyclic.
   11.51    /// \param graph The undirected graph.
   11.52 -  /// \return %True when there is no circle in the graph.
   11.53 +  /// \return \c true when there is no circle in the graph.
   11.54    /// \see dag
   11.55    template <typename Graph>
   11.56    bool acyclic(const Graph& graph) {
   11.57 @@ -1355,7 +1355,7 @@
   11.58    ///
   11.59    /// Check that the given undirected graph is tree.
   11.60    /// \param graph The undirected graph.
   11.61 -  /// \return %True when the graph is acyclic and connected.
   11.62 +  /// \return \c true when the graph is acyclic and connected.
   11.63    template <typename Graph>
   11.64    bool tree(const Graph& graph) {
   11.65      checkConcept<concepts::Graph, Graph>();
   11.66 @@ -1448,7 +1448,7 @@
   11.67    /// The function checks if the given undirected \c graph graph is bipartite
   11.68    /// or not. The \ref Bfs algorithm is used to calculate the result.
   11.69    /// \param graph The undirected graph.
   11.70 -  /// \return %True if \c graph is bipartite, %false otherwise.
   11.71 +  /// \return \c true if \c graph is bipartite, \c false otherwise.
   11.72    /// \sa bipartitePartitions
   11.73    template<typename Graph>
   11.74    inline bool bipartite(const Graph &graph){
   11.75 @@ -1489,7 +1489,7 @@
   11.76    /// \param graph The undirected graph.
   11.77    /// \retval partMap A writable bool map of nodes. It will be set as the
   11.78    /// two partitions of the graph.
   11.79 -  /// \return %True if \c graph is bipartite, %false otherwise.
   11.80 +  /// \return \c true if \c graph is bipartite, \c false otherwise.
   11.81    template<typename Graph, typename NodeMap>
   11.82    inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
   11.83      using namespace _connectivity_bits;
    12.1 --- a/lemon/core.h	Thu Mar 05 10:13:20 2009 +0000
    12.2 +++ b/lemon/core.h	Sun Mar 29 23:08:20 2009 +0200
    12.3 @@ -1034,11 +1034,11 @@
    12.4    ///
    12.5    ///\sa findArc()
    12.6    ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
    12.7 -  template <typename _Graph>
    12.8 -  class ConArcIt : public _Graph::Arc {
    12.9 +  template <typename GR>
   12.10 +  class ConArcIt : public GR::Arc {
   12.11    public:
   12.12  
   12.13 -    typedef _Graph Graph;
   12.14 +    typedef GR Graph;
   12.15      typedef typename Graph::Arc Parent;
   12.16  
   12.17      typedef typename Graph::Arc Arc;
   12.18 @@ -1157,11 +1157,11 @@
   12.19    ///\endcode
   12.20    ///
   12.21    ///\sa findEdge()
   12.22 -  template <typename _Graph>
   12.23 -  class ConEdgeIt : public _Graph::Edge {
   12.24 +  template <typename GR>
   12.25 +  class ConEdgeIt : public GR::Edge {
   12.26    public:
   12.27  
   12.28 -    typedef _Graph Graph;
   12.29 +    typedef GR Graph;
   12.30      typedef typename Graph::Edge Parent;
   12.31  
   12.32      typedef typename Graph::Edge Edge;
   12.33 @@ -1211,29 +1211,29 @@
   12.34    ///optimal time bound in a constant factor for any distribution of
   12.35    ///queries.
   12.36    ///
   12.37 -  ///\tparam G The type of the underlying digraph.
   12.38 +  ///\tparam GR The type of the underlying digraph.
   12.39    ///
   12.40    ///\sa ArcLookUp
   12.41    ///\sa AllArcLookUp
   12.42 -  template<class G>
   12.43 +  template <typename GR>
   12.44    class DynArcLookUp
   12.45 -    : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
   12.46 +    : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase
   12.47    {
   12.48    public:
   12.49 -    typedef typename ItemSetTraits<G, typename G::Arc>
   12.50 +    typedef typename ItemSetTraits<GR, typename GR::Arc>
   12.51      ::ItemNotifier::ObserverBase Parent;
   12.52  
   12.53 -    TEMPLATE_DIGRAPH_TYPEDEFS(G);
   12.54 -    typedef G Digraph;
   12.55 +    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
   12.56 +    typedef GR Digraph;
   12.57  
   12.58    protected:
   12.59  
   12.60 -    class AutoNodeMap : public ItemSetTraits<G, Node>::template Map<Arc>::Type {
   12.61 +    class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type {
   12.62      public:
   12.63  
   12.64 -      typedef typename ItemSetTraits<G, Node>::template Map<Arc>::Type Parent;
   12.65 +      typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
   12.66  
   12.67 -      AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
   12.68 +      AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {}
   12.69  
   12.70        virtual void add(const Node& node) {
   12.71          Parent::add(node);
   12.72 @@ -1623,16 +1623,16 @@
   12.73    ///digraph changes. This is a time consuming (superlinearly proportional
   12.74    ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
   12.75    ///
   12.76 -  ///\tparam G The type of the underlying digraph.
   12.77 +  ///\tparam GR The type of the underlying digraph.
   12.78    ///
   12.79    ///\sa DynArcLookUp
   12.80    ///\sa AllArcLookUp
   12.81 -  template<class G>
   12.82 +  template<class GR>
   12.83    class ArcLookUp
   12.84    {
   12.85    public:
   12.86 -    TEMPLATE_DIGRAPH_TYPEDEFS(G);
   12.87 -    typedef G Digraph;
   12.88 +    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
   12.89 +    typedef GR Digraph;
   12.90  
   12.91    protected:
   12.92      const Digraph &_g;
   12.93 @@ -1733,20 +1733,20 @@
   12.94    ///digraph changes. This is a time consuming (superlinearly proportional
   12.95    ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
   12.96    ///
   12.97 -  ///\tparam G The type of the underlying digraph.
   12.98 +  ///\tparam GR The type of the underlying digraph.
   12.99    ///
  12.100    ///\sa DynArcLookUp
  12.101    ///\sa ArcLookUp
  12.102 -  template<class G>
  12.103 -  class AllArcLookUp : public ArcLookUp<G>
  12.104 +  template<class GR>
  12.105 +  class AllArcLookUp : public ArcLookUp<GR>
  12.106    {
  12.107 -    using ArcLookUp<G>::_g;
  12.108 -    using ArcLookUp<G>::_right;
  12.109 -    using ArcLookUp<G>::_left;
  12.110 -    using ArcLookUp<G>::_head;
  12.111 +    using ArcLookUp<GR>::_g;
  12.112 +    using ArcLookUp<GR>::_right;
  12.113 +    using ArcLookUp<GR>::_left;
  12.114 +    using ArcLookUp<GR>::_head;
  12.115  
  12.116 -    TEMPLATE_DIGRAPH_TYPEDEFS(G);
  12.117 -    typedef G Digraph;
  12.118 +    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
  12.119 +    typedef GR Digraph;
  12.120  
  12.121      typename Digraph::template ArcMap<Arc> _next;
  12.122  
  12.123 @@ -1773,7 +1773,7 @@
  12.124      ///
  12.125      ///It builds up the search database, which remains valid until the digraph
  12.126      ///changes.
  12.127 -    AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
  12.128 +    AllArcLookUp(const Digraph &g) : ArcLookUp<GR>(g), _next(g) {refreshNext();}
  12.129  
  12.130      ///Refresh the data structure at a node.
  12.131  
  12.132 @@ -1783,7 +1783,7 @@
  12.133      ///the number of the outgoing arcs of \c n.
  12.134      void refresh(Node n)
  12.135      {
  12.136 -      ArcLookUp<G>::refresh(n);
  12.137 +      ArcLookUp<GR>::refresh(n);
  12.138        refreshNext(_head[n]);
  12.139      }
  12.140  
  12.141 @@ -1830,7 +1830,7 @@
  12.142  #ifdef DOXYGEN
  12.143      Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
  12.144  #else
  12.145 -    using ArcLookUp<G>::operator() ;
  12.146 +    using ArcLookUp<GR>::operator() ;
  12.147      Arc operator()(Node s, Node t, Arc prev) const
  12.148      {
  12.149        return prev==INVALID?(*this)(s,t):_next[prev];
    13.1 --- a/lemon/dijkstra.h	Thu Mar 05 10:13:20 2009 +0000
    13.2 +++ b/lemon/dijkstra.h	Sun Mar 29 23:08:20 2009 +0200
    13.3 @@ -38,8 +38,10 @@
    13.4    ///
    13.5    /// This operation traits class defines all computational operations and
    13.6    /// constants which are used in the Dijkstra algorithm.
    13.7 -  template <typename Value>
    13.8 +  template <typename V>
    13.9    struct DijkstraDefaultOperationTraits {
   13.10 +    /// \e
   13.11 +    typedef V Value;
   13.12      /// \brief Gives back the zero value of the type.
   13.13      static Value zero() {
   13.14        return static_cast<Value>(0);
   13.15 @@ -58,8 +60,8 @@
   13.16  
   13.17    ///Default traits class of Dijkstra class.
   13.18    ///\tparam GR The type of the digraph.
   13.19 -  ///\tparam LM The type of the length map.
   13.20 -  template<class GR, class LM>
   13.21 +  ///\tparam LEN The type of the length map.
   13.22 +  template<typename GR, typename LEN>
   13.23    struct DijkstraDefaultTraits
   13.24    {
   13.25      ///The type of the digraph the algorithm runs on.
   13.26 @@ -69,9 +71,9 @@
   13.27  
   13.28      ///The type of the map that stores the arc lengths.
   13.29      ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
   13.30 -    typedef LM LengthMap;
   13.31 +    typedef LEN LengthMap;
   13.32      ///The type of the length of the arcs.
   13.33 -    typedef typename LM::Value Value;
   13.34 +    typedef typename LEN::Value Value;
   13.35  
   13.36      /// Operation traits for %Dijkstra algorithm.
   13.37  
   13.38 @@ -100,7 +102,7 @@
   13.39      ///
   13.40      ///\sa BinHeap
   13.41      ///\sa Dijkstra
   13.42 -    typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
   13.43 +    typedef BinHeap<typename LEN::Value, HeapCrossRef, std::less<Value> > Heap;
   13.44      ///Instantiates a \c Heap.
   13.45  
   13.46      ///This function instantiates a \ref Heap.
   13.47 @@ -150,7 +152,7 @@
   13.48  
   13.49      ///The type of the map that stores the distances of the nodes.
   13.50      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   13.51 -    typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
   13.52 +    typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
   13.53      ///Instantiates a \c DistMap.
   13.54  
   13.55      ///This function instantiates a \ref DistMap.
   13.56 @@ -180,18 +182,18 @@
   13.57    ///
   13.58    ///\tparam GR The type of the digraph the algorithm runs on.
   13.59    ///The default type is \ref ListDigraph.
   13.60 -  ///\tparam LM A \ref concepts::ReadMap "readable" arc map that specifies
   13.61 +  ///\tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies
   13.62    ///the lengths of the arcs.
   13.63    ///It is read once for each arc, so the map may involve in
   13.64    ///relatively time consuming process to compute the arc lengths if
   13.65    ///it is necessary. The default map type is \ref
   13.66    ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
   13.67  #ifdef DOXYGEN
   13.68 -  template <typename GR, typename LM, typename TR>
   13.69 +  template <typename GR, typename LEN, typename TR>
   13.70  #else
   13.71    template <typename GR=ListDigraph,
   13.72 -            typename LM=typename GR::template ArcMap<int>,
   13.73 -            typename TR=DijkstraDefaultTraits<GR,LM> >
   13.74 +            typename LEN=typename GR::template ArcMap<int>,
   13.75 +            typename TR=DijkstraDefaultTraits<GR,LEN> >
   13.76  #endif
   13.77    class Dijkstra {
   13.78    public:
   13.79 @@ -913,8 +915,8 @@
   13.80  
   13.81    ///Default traits class of dijkstra() function.
   13.82    ///\tparam GR The type of the digraph.
   13.83 -  ///\tparam LM The type of the length map.
   13.84 -  template<class GR, class LM>
   13.85 +  ///\tparam LEN The type of the length map.
   13.86 +  template<class GR, class LEN>
   13.87    struct DijkstraWizardDefaultTraits
   13.88    {
   13.89      ///The type of the digraph the algorithm runs on.
   13.90 @@ -923,9 +925,9 @@
   13.91  
   13.92      ///The type of the map that stores the arc lengths.
   13.93      ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
   13.94 -    typedef LM LengthMap;
   13.95 +    typedef LEN LengthMap;
   13.96      ///The type of the length of the arcs.
   13.97 -    typedef typename LM::Value Value;
   13.98 +    typedef typename LEN::Value Value;
   13.99  
  13.100      /// Operation traits for Dijkstra algorithm.
  13.101  
  13.102 @@ -1007,7 +1009,7 @@
  13.103  
  13.104      ///The type of the map that stores the distances of the nodes.
  13.105      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
  13.106 -    typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
  13.107 +    typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
  13.108      ///Instantiates a DistMap.
  13.109  
  13.110      ///This function instantiates a DistMap.
  13.111 @@ -1033,10 +1035,10 @@
  13.112    /// as well as the \ref Dijkstra class.
  13.113    /// The \ref DijkstraWizardBase is a class to be the default traits of the
  13.114    /// \ref DijkstraWizard class.
  13.115 -  template<class GR,class LM>
  13.116 -  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
  13.117 +  template<typename GR, typename LEN>
  13.118 +  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN>
  13.119    {
  13.120 -    typedef DijkstraWizardDefaultTraits<GR,LM> Base;
  13.121 +    typedef DijkstraWizardDefaultTraits<GR,LEN> Base;
  13.122    protected:
  13.123      //The type of the nodes in the digraph.
  13.124      typedef typename Base::Digraph::Node Node;
  13.125 @@ -1070,9 +1072,9 @@
  13.126      /// others are initiated to \c 0.
  13.127      /// \param g The digraph the algorithm runs on.
  13.128      /// \param l The length map.
  13.129 -    DijkstraWizardBase(const GR &g,const LM &l) :
  13.130 +    DijkstraWizardBase(const GR &g,const LEN &l) :
  13.131        _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
  13.132 -      _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
  13.133 +      _length(reinterpret_cast<void*>(const_cast<LEN*>(&l))),
  13.134        _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
  13.135  
  13.136    };
  13.137 @@ -1281,11 +1283,11 @@
  13.138    ///to the end of the parameter list.
  13.139    ///\sa DijkstraWizard
  13.140    ///\sa Dijkstra
  13.141 -  template<class GR, class LM>
  13.142 -  DijkstraWizard<DijkstraWizardBase<GR,LM> >
  13.143 -  dijkstra(const GR &digraph, const LM &length)
  13.144 +  template<typename GR, typename LEN>
  13.145 +  DijkstraWizard<DijkstraWizardBase<GR,LEN> >
  13.146 +  dijkstra(const GR &digraph, const LEN &length)
  13.147    {
  13.148 -    return DijkstraWizard<DijkstraWizardBase<GR,LM> >(digraph,length);
  13.149 +    return DijkstraWizard<DijkstraWizardBase<GR,LEN> >(digraph,length);
  13.150    }
  13.151  
  13.152  } //END OF NAMESPACE LEMON
    14.1 --- a/lemon/edge_set.h	Thu Mar 05 10:13:20 2009 +0000
    14.2 +++ b/lemon/edge_set.h	Sun Mar 29 23:08:20 2009 +0200
    14.3 @@ -255,7 +255,7 @@
    14.4    /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
    14.5    /// concept.
    14.6    ///
    14.7 -  /// This class is fully conform to the \ref concepts::Digraph
    14.8 +  /// This class fully conforms to the \ref concepts::Digraph
    14.9    /// "Digraph" concept.
   14.10    template <typename GR>
   14.11    class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > {
   14.12 @@ -336,7 +336,7 @@
   14.13      ///
   14.14      /// Add a new arc to the digraph with source node \c s
   14.15      /// and target node \c t.
   14.16 -    /// \return the new arc.
   14.17 +    /// \return The new arc.
   14.18      Arc addArc(const Node& s, const Node& t) {
   14.19        return Parent::addArc(s, t);
   14.20      }
   14.21 @@ -684,7 +684,7 @@
   14.22    /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
   14.23    /// concept.
   14.24    ///
   14.25 -  /// This class is fully conform to the \ref concepts::Graph "Graph"
   14.26 +  /// This class fully conforms to the \ref concepts::Graph "Graph"
   14.27    /// concept.
   14.28    template <typename GR>
   14.29    class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<GR> > {
   14.30 @@ -761,7 +761,7 @@
   14.31      ///
   14.32      /// Add a new edge to the graph with node \c u
   14.33      /// and node \c v endpoints.
   14.34 -    /// \return the new edge.
   14.35 +    /// \return The new edge.
   14.36      Edge addEdge(const Node& u, const Node& v) {
   14.37        return Parent::addEdge(u, v);
   14.38      }
   14.39 @@ -952,7 +952,7 @@
   14.40    /// the arc set is invalidated, and it cannot be used anymore. The
   14.41    /// validity can be checked with the \c valid() member function.
   14.42    ///
   14.43 -  /// This class is fully conform to the \ref concepts::Digraph
   14.44 +  /// This class fully conforms to the \ref concepts::Digraph
   14.45    /// "Digraph" concept.
   14.46    template <typename GR>
   14.47    class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > {
   14.48 @@ -1041,7 +1041,7 @@
   14.49      ///
   14.50      /// Add a new arc to the digraph with source node \c s
   14.51      /// and target node \c t.
   14.52 -    /// \return the new arc.
   14.53 +    /// \return The new arc.
   14.54      Arc addArc(const Node& s, const Node& t) {
   14.55        return Parent::addArc(s, t);
   14.56      }
   14.57 @@ -1300,7 +1300,7 @@
   14.58    /// is invalidated, and it cannot be used anymore. The validity can
   14.59    /// be checked with the \c valid() member function.
   14.60    ///
   14.61 -  /// This class is fully conform to the \ref concepts::Graph
   14.62 +  /// This class fully conforms to the \ref concepts::Graph
   14.63    /// "Graph" concept.
   14.64    template <typename GR>
   14.65    class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > {
   14.66 @@ -1389,7 +1389,7 @@
   14.67      ///
   14.68      /// Add a new edge to the graph with node \c u
   14.69      /// and node \c v endpoints.
   14.70 -    /// \return the new edge.
   14.71 +    /// \return The new edge.
   14.72      Edge addEdge(const Node& u, const Node& v) {
   14.73        return Parent::addEdge(u, v);
   14.74      }
    15.1 --- a/lemon/elevator.h	Thu Mar 05 10:13:20 2009 +0000
    15.2 +++ b/lemon/elevator.h	Sun Mar 29 23:08:20 2009 +0200
    15.3 @@ -46,10 +46,10 @@
    15.4    ///
    15.5    ///\sa LinkedElevator
    15.6    ///
    15.7 -  ///\param Graph Type of the underlying graph.
    15.8 -  ///\param Item Type of the items the data is assigned to (Graph::Node,
    15.9 -  ///Graph::Arc, Graph::Edge).
   15.10 -  template<class Graph, class Item>
   15.11 +  ///\param GR Type of the underlying graph.
   15.12 +  ///\param Item Type of the items the data is assigned to (\c GR::Node,
   15.13 +  ///\c GR::Arc or \c GR::Edge).
   15.14 +  template<class GR, class Item>
   15.15    class Elevator
   15.16    {
   15.17    public:
   15.18 @@ -60,10 +60,10 @@
   15.19    private:
   15.20  
   15.21      typedef Item *Vit;
   15.22 -    typedef typename ItemSetTraits<Graph,Item>::template Map<Vit>::Type VitMap;
   15.23 -    typedef typename ItemSetTraits<Graph,Item>::template Map<int>::Type IntMap;
   15.24 +    typedef typename ItemSetTraits<GR,Item>::template Map<Vit>::Type VitMap;
   15.25 +    typedef typename ItemSetTraits<GR,Item>::template Map<int>::Type IntMap;
   15.26  
   15.27 -    const Graph &_g;
   15.28 +    const GR &_g;
   15.29      int _max_level;
   15.30      int _item_num;
   15.31      VitMap _where;
   15.32 @@ -105,7 +105,7 @@
   15.33      ///\param graph The underlying graph.
   15.34      ///\param max_level The maximum allowed level.
   15.35      ///Set the range of the possible labels to <tt>[0..max_level]</tt>.
   15.36 -    Elevator(const Graph &graph,int max_level) :
   15.37 +    Elevator(const GR &graph,int max_level) :
   15.38        _g(graph),
   15.39        _max_level(max_level),
   15.40        _item_num(_max_level),
   15.41 @@ -122,9 +122,9 @@
   15.42      ///\param graph The underlying graph.
   15.43      ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
   15.44      ///where \c max_level is equal to the number of labeled items in the graph.
   15.45 -    Elevator(const Graph &graph) :
   15.46 +    Elevator(const GR &graph) :
   15.47        _g(graph),
   15.48 -      _max_level(countItems<Graph, Item>(graph)),
   15.49 +      _max_level(countItems<GR, Item>(graph)),
   15.50        _item_num(_max_level),
   15.51        _where(graph),
   15.52        _level(graph,0),
   15.53 @@ -430,7 +430,7 @@
   15.54        _first[0]=&_items[0];
   15.55        _last_active[0]=&_items[0]-1;
   15.56        Vit n=&_items[0];
   15.57 -      for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
   15.58 +      for(typename ItemSetTraits<GR,Item>::ItemIt i(_g);i!=INVALID;++i)
   15.59          {
   15.60            *n=i;
   15.61            _where.set(i,n);
   15.62 @@ -489,10 +489,10 @@
   15.63    ///
   15.64    ///\sa Elevator
   15.65    ///
   15.66 -  ///\param Graph Type of the underlying graph.
   15.67 -  ///\param Item Type of the items the data is assigned to (Graph::Node,
   15.68 -  ///Graph::Arc, Graph::Edge).
   15.69 -  template <class Graph, class Item>
   15.70 +  ///\param GR Type of the underlying graph.
   15.71 +  ///\param Item Type of the items the data is assigned to (\c GR::Node,
   15.72 +  ///\c GR::Arc or \c GR::Edge).
   15.73 +  template <class GR, class Item>
   15.74    class LinkedElevator {
   15.75    public:
   15.76  
   15.77 @@ -501,14 +501,14 @@
   15.78  
   15.79    private:
   15.80  
   15.81 -    typedef typename ItemSetTraits<Graph,Item>::
   15.82 +    typedef typename ItemSetTraits<GR,Item>::
   15.83      template Map<Item>::Type ItemMap;
   15.84 -    typedef typename ItemSetTraits<Graph,Item>::
   15.85 +    typedef typename ItemSetTraits<GR,Item>::
   15.86      template Map<int>::Type IntMap;
   15.87 -    typedef typename ItemSetTraits<Graph,Item>::
   15.88 +    typedef typename ItemSetTraits<GR,Item>::
   15.89      template Map<bool>::Type BoolMap;
   15.90  
   15.91 -    const Graph &_graph;
   15.92 +    const GR &_graph;
   15.93      int _max_level;
   15.94      int _item_num;
   15.95      std::vector<Item> _first, _last;
   15.96 @@ -525,7 +525,7 @@
   15.97      ///\param graph The underlying graph.
   15.98      ///\param max_level The maximum allowed level.
   15.99      ///Set the range of the possible labels to <tt>[0..max_level]</tt>.
  15.100 -    LinkedElevator(const Graph& graph, int max_level)
  15.101 +    LinkedElevator(const GR& graph, int max_level)
  15.102        : _graph(graph), _max_level(max_level), _item_num(_max_level),
  15.103          _first(_max_level + 1), _last(_max_level + 1),
  15.104          _prev(graph), _next(graph),
  15.105 @@ -538,8 +538,8 @@
  15.106      ///\param graph The underlying graph.
  15.107      ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
  15.108      ///where \c max_level is equal to the number of labeled items in the graph.
  15.109 -    LinkedElevator(const Graph& graph)
  15.110 -      : _graph(graph), _max_level(countItems<Graph, Item>(graph)),
  15.111 +    LinkedElevator(const GR& graph)
  15.112 +      : _graph(graph), _max_level(countItems<GR, Item>(graph)),
  15.113          _item_num(_max_level),
  15.114          _first(_max_level + 1), _last(_max_level + 1),
  15.115          _prev(graph, INVALID), _next(graph, INVALID),
  15.116 @@ -935,7 +935,7 @@
  15.117          _first[i] = _last[i] = INVALID;
  15.118        }
  15.119        _init_level = 0;
  15.120 -      for(typename ItemSetTraits<Graph,Item>::ItemIt i(_graph);
  15.121 +      for(typename ItemSetTraits<GR,Item>::ItemIt i(_graph);
  15.122            i != INVALID; ++i) {
  15.123          _level.set(i, _max_level);
  15.124          _active.set(i, false);
    16.1 --- a/lemon/euler.h	Thu Mar 05 10:13:20 2009 +0000
    16.2 +++ b/lemon/euler.h	Sun Mar 29 23:08:20 2009 +0200
    16.3 @@ -54,29 +54,29 @@
    16.4    ///\endcode
    16.5    ///If \c g is not Euler then the resulted tour will not be full or closed.
    16.6    ///\sa EulerIt
    16.7 -  template<class Digraph>
    16.8 +  template<typename GR>
    16.9    class DiEulerIt
   16.10    {
   16.11 -    typedef typename Digraph::Node Node;
   16.12 -    typedef typename Digraph::NodeIt NodeIt;
   16.13 -    typedef typename Digraph::Arc Arc;
   16.14 -    typedef typename Digraph::ArcIt ArcIt;
   16.15 -    typedef typename Digraph::OutArcIt OutArcIt;
   16.16 -    typedef typename Digraph::InArcIt InArcIt;
   16.17 +    typedef typename GR::Node Node;
   16.18 +    typedef typename GR::NodeIt NodeIt;
   16.19 +    typedef typename GR::Arc Arc;
   16.20 +    typedef typename GR::ArcIt ArcIt;
   16.21 +    typedef typename GR::OutArcIt OutArcIt;
   16.22 +    typedef typename GR::InArcIt InArcIt;
   16.23  
   16.24 -    const Digraph &g;
   16.25 -    typename Digraph::template NodeMap<OutArcIt> nedge;
   16.26 +    const GR &g;
   16.27 +    typename GR::template NodeMap<OutArcIt> nedge;
   16.28      std::list<Arc> euler;
   16.29  
   16.30    public:
   16.31  
   16.32      ///Constructor
   16.33  
   16.34 -    ///\param _g A digraph.
   16.35 +    ///\param gr A digraph.
   16.36      ///\param start The starting point of the tour. If it is not given
   16.37      ///       the tour will start from the first node.
   16.38 -    DiEulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)
   16.39 -      : g(_g), nedge(g)
   16.40 +    DiEulerIt(const GR &gr, typename GR::Node start = INVALID)
   16.41 +      : g(gr), nedge(g)
   16.42      {
   16.43        if(start==INVALID) start=NodeIt(g);
   16.44        for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);
   16.45 @@ -145,31 +145,31 @@
   16.46    ///
   16.47    ///If \c g is not Euler then the resulted tour will not be full or closed.
   16.48    ///\sa EulerIt
   16.49 -  template<class Digraph>
   16.50 +  template<typename GR>
   16.51    class EulerIt
   16.52    {
   16.53 -    typedef typename Digraph::Node Node;
   16.54 -    typedef typename Digraph::NodeIt NodeIt;
   16.55 -    typedef typename Digraph::Arc Arc;
   16.56 -    typedef typename Digraph::Edge Edge;
   16.57 -    typedef typename Digraph::ArcIt ArcIt;
   16.58 -    typedef typename Digraph::OutArcIt OutArcIt;
   16.59 -    typedef typename Digraph::InArcIt InArcIt;
   16.60 +    typedef typename GR::Node Node;
   16.61 +    typedef typename GR::NodeIt NodeIt;
   16.62 +    typedef typename GR::Arc Arc;
   16.63 +    typedef typename GR::Edge Edge;
   16.64 +    typedef typename GR::ArcIt ArcIt;
   16.65 +    typedef typename GR::OutArcIt OutArcIt;
   16.66 +    typedef typename GR::InArcIt InArcIt;
   16.67  
   16.68 -    const Digraph &g;
   16.69 -    typename Digraph::template NodeMap<OutArcIt> nedge;
   16.70 -    typename Digraph::template EdgeMap<bool> visited;
   16.71 +    const GR &g;
   16.72 +    typename GR::template NodeMap<OutArcIt> nedge;
   16.73 +    typename GR::template EdgeMap<bool> visited;
   16.74      std::list<Arc> euler;
   16.75  
   16.76    public:
   16.77  
   16.78      ///Constructor
   16.79  
   16.80 -    ///\param _g An graph.
   16.81 +    ///\param gr An graph.
   16.82      ///\param start The starting point of the tour. If it is not given
   16.83      ///       the tour will start from the first node.
   16.84 -    EulerIt(const Digraph &_g,typename Digraph::Node start=INVALID)
   16.85 -      : g(_g), nedge(g), visited(g,false)
   16.86 +    EulerIt(const GR &gr, typename GR::Node start = INVALID)
   16.87 +      : g(gr), nedge(g), visited(g, false)
   16.88      {
   16.89        if(start==INVALID) start=NodeIt(g);
   16.90        for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutArcIt(g,n);
   16.91 @@ -238,25 +238,25 @@
   16.92    ///and only if it is connected and the number of incident arcs is even
   16.93    ///for each node. <em>Therefore, there are digraphs which are not Eulerian,
   16.94    ///but still have an Euler tour</em>.
   16.95 -  template<class Digraph>
   16.96 +  template<typename GR>
   16.97  #ifdef DOXYGEN
   16.98    bool
   16.99  #else
  16.100 -  typename enable_if<UndirectedTagIndicator<Digraph>,bool>::type
  16.101 -  eulerian(const Digraph &g)
  16.102 +  typename enable_if<UndirectedTagIndicator<GR>,bool>::type
  16.103 +  eulerian(const GR &g)
  16.104    {
  16.105 -    for(typename Digraph::NodeIt n(g);n!=INVALID;++n)
  16.106 +    for(typename GR::NodeIt n(g);n!=INVALID;++n)
  16.107        if(countIncEdges(g,n)%2) return false;
  16.108      return connected(g);
  16.109    }
  16.110 -  template<class Digraph>
  16.111 -  typename disable_if<UndirectedTagIndicator<Digraph>,bool>::type
  16.112 +  template<class GR>
  16.113 +  typename disable_if<UndirectedTagIndicator<GR>,bool>::type
  16.114  #endif
  16.115 -  eulerian(const Digraph &g)
  16.116 +  eulerian(const GR &g)
  16.117    {
  16.118 -    for(typename Digraph::NodeIt n(g);n!=INVALID;++n)
  16.119 +    for(typename GR::NodeIt n(g);n!=INVALID;++n)
  16.120        if(countInArcs(g,n)!=countOutArcs(g,n)) return false;
  16.121 -    return connected(Undirector<const Digraph>(g));
  16.122 +    return connected(Undirector<const GR>(g));
  16.123    }
  16.124  
  16.125  }
    17.1 --- a/lemon/graph_to_eps.h	Thu Mar 05 10:13:20 2009 +0000
    17.2 +++ b/lemon/graph_to_eps.h	Sun Mar 29 23:08:20 2009 +0200
    17.3 @@ -64,11 +64,11 @@
    17.4  
    17.5  ///Default traits class of \ref GraphToEps.
    17.6  ///
    17.7 -///\c G is the type of the underlying graph.
    17.8 -template<class G>
    17.9 +///\param GR is the type of the underlying graph.
   17.10 +template<class GR>
   17.11  struct DefaultGraphToEpsTraits
   17.12  {
   17.13 -  typedef G Graph;
   17.14 +  typedef GR Graph;
   17.15    typedef typename Graph::Node Node;
   17.16    typedef typename Graph::NodeIt NodeIt;
   17.17    typedef typename Graph::Arc Arc;
   17.18 @@ -139,15 +139,14 @@
   17.19    ///Constructor
   17.20  
   17.21    ///Constructor
   17.22 -  ///\param _g  Reference to the graph to be printed.
   17.23 -  ///\param _os Reference to the output stream.
   17.24 -  ///\param _os Reference to the output stream.
   17.25 +  ///\param gr  Reference to the graph to be printed.
   17.26 +  ///\param ost Reference to the output stream.
   17.27    ///By default it is <tt>std::cout</tt>.
   17.28 -  ///\param _pros If it is \c true, then the \c ostream referenced by \c _os
   17.29 +  ///\param pros If it is \c true, then the \c ostream referenced by \c os
   17.30    ///will be explicitly deallocated by the destructor.
   17.31 -  DefaultGraphToEpsTraits(const G &_g,std::ostream& _os=std::cout,
   17.32 -                          bool _pros=false) :
   17.33 -    g(_g), os(_os),
   17.34 +  DefaultGraphToEpsTraits(const GR &gr, std::ostream& ost = std::cout,
   17.35 +                          bool pros = false) :
   17.36 +    g(gr), os(ost),
   17.37      _coords(dim2::Point<double>(1,1)), _nodeSizes(1), _nodeShapes(0),
   17.38      _nodeColors(WHITE), _arcColors(BLACK),
   17.39      _arcWidths(1.0), _arcWidthScale(0.003),
   17.40 @@ -158,8 +157,8 @@
   17.41      _enableParallel(false), _parArcDist(1),
   17.42      _showNodeText(false), _nodeTexts(false), _nodeTextSize(1),
   17.43      _showNodePsText(false), _nodePsTexts(false), _nodePsTextsPreamble(0),
   17.44 -    _undirected(lemon::UndirectedTagIndicator<G>::value),
   17.45 -    _pleaseRemoveOsStream(_pros), _scaleToA4(false),
   17.46 +    _undirected(lemon::UndirectedTagIndicator<GR>::value),
   17.47 +    _pleaseRemoveOsStream(pros), _scaleToA4(false),
   17.48      _nodeTextColorType(SAME_COL), _nodeTextColors(BLACK),
   17.49      _autoNodeScale(false),
   17.50      _autoArcWidthScale(false),
   17.51 @@ -1134,55 +1133,55 @@
   17.52  ///\warning Don't forget to put the \ref GraphToEps::run() "run()"
   17.53  ///to the end of the parameter list.
   17.54  ///\sa GraphToEps
   17.55 -///\sa graphToEps(G &g, const char *file_name)
   17.56 -template<class G>
   17.57 -GraphToEps<DefaultGraphToEpsTraits<G> >
   17.58 -graphToEps(G &g, std::ostream& os=std::cout)
   17.59 +///\sa graphToEps(GR &g, const char *file_name)
   17.60 +template<class GR>
   17.61 +GraphToEps<DefaultGraphToEpsTraits<GR> >
   17.62 +graphToEps(GR &g, std::ostream& os=std::cout)
   17.63  {
   17.64    return
   17.65 -    GraphToEps<DefaultGraphToEpsTraits<G> >(DefaultGraphToEpsTraits<G>(g,os));
   17.66 +    GraphToEps<DefaultGraphToEpsTraits<GR> >(DefaultGraphToEpsTraits<GR>(g,os));
   17.67  }
   17.68  
   17.69  ///Generates an EPS file from a graph
   17.70  
   17.71  ///\ingroup eps_io
   17.72  ///This function does the same as
   17.73 -///\ref graphToEps(G &g,std::ostream& os)
   17.74 +///\ref graphToEps(GR &g,std::ostream& os)
   17.75  ///but it writes its output into the file \c file_name
   17.76  ///instead of a stream.
   17.77 -///\sa graphToEps(G &g, std::ostream& os)
   17.78 -template<class G>
   17.79 -GraphToEps<DefaultGraphToEpsTraits<G> >
   17.80 -graphToEps(G &g,const char *file_name)
   17.81 +///\sa graphToEps(GR &g, std::ostream& os)
   17.82 +template<class GR>
   17.83 +GraphToEps<DefaultGraphToEpsTraits<GR> >
   17.84 +graphToEps(GR &g,const char *file_name)
   17.85  {
   17.86    std::ostream* os = new std::ofstream(file_name);
   17.87    if (!(*os)) {
   17.88      delete os;
   17.89      throw IoError("Cannot write file", file_name);
   17.90    }
   17.91 -  return GraphToEps<DefaultGraphToEpsTraits<G> >
   17.92 -    (DefaultGraphToEpsTraits<G>(g,*os,true));
   17.93 +  return GraphToEps<DefaultGraphToEpsTraits<GR> >
   17.94 +    (DefaultGraphToEpsTraits<GR>(g,*os,true));
   17.95  }
   17.96  
   17.97  ///Generates an EPS file from a graph
   17.98  
   17.99  ///\ingroup eps_io
  17.100  ///This function does the same as
  17.101 -///\ref graphToEps(G &g,std::ostream& os)
  17.102 +///\ref graphToEps(GR &g,std::ostream& os)
  17.103  ///but it writes its output into the file \c file_name
  17.104  ///instead of a stream.
  17.105 -///\sa graphToEps(G &g, std::ostream& os)
  17.106 -template<class G>
  17.107 -GraphToEps<DefaultGraphToEpsTraits<G> >
  17.108 -graphToEps(G &g,const std::string& file_name)
  17.109 +///\sa graphToEps(GR &g, std::ostream& os)
  17.110 +template<class GR>
  17.111 +GraphToEps<DefaultGraphToEpsTraits<GR> >
  17.112 +graphToEps(GR &g,const std::string& file_name)
  17.113  {
  17.114    std::ostream* os = new std::ofstream(file_name.c_str());
  17.115    if (!(*os)) {
  17.116      delete os;
  17.117      throw IoError("Cannot write file", file_name);
  17.118    }
  17.119 -  return GraphToEps<DefaultGraphToEpsTraits<G> >
  17.120 -    (DefaultGraphToEpsTraits<G>(g,*os,true));
  17.121 +  return GraphToEps<DefaultGraphToEpsTraits<GR> >
  17.122 +    (DefaultGraphToEpsTraits<GR>(g,*os,true));
  17.123  }
  17.124  
  17.125  } //END OF NAMESPACE LEMON
    18.1 --- a/lemon/grid_graph.h	Thu Mar 05 10:13:20 2009 +0000
    18.2 +++ b/lemon/grid_graph.h	Sun Mar 29 23:08:20 2009 +0200
    18.3 @@ -496,7 +496,7 @@
    18.4    /// }
    18.5    ///\endcode
    18.6    ///
    18.7 -  /// This graph type is fully conform to the \ref concepts::Graph
    18.8 +  /// This graph type fully conforms to the \ref concepts::Graph
    18.9    /// "Graph" concept, and it also has an important extra feature
   18.10    /// that its maps are real \ref concepts::ReferenceMap
   18.11    /// "reference map"s.
    19.1 --- a/lemon/hao_orlin.h	Thu Mar 05 10:13:20 2009 +0000
    19.2 +++ b/lemon/hao_orlin.h	Sun Mar 29 23:08:20 2009 +0200
    19.3 @@ -57,27 +57,27 @@
    19.4    /// undirected graph you can run just the first phase of the
    19.5    /// algorithm or you can use the algorithm of Nagamochi and Ibaraki
    19.6    /// which solves the undirected problem in
    19.7 -  /// \f$ O(nm + n^2 \log(n)) \f$ time: it is implemented in the
    19.8 +  /// \f$ O(nm + n^2 \log n) \f$ time: it is implemented in the
    19.9    /// NagamochiIbaraki algorithm class.
   19.10    ///
   19.11 -  /// \param _Digraph is the graph type of the algorithm.
   19.12 -  /// \param _CapacityMap is an edge map of capacities which should
   19.13 -  /// be any numreric type. The default type is _Digraph::ArcMap<int>.
   19.14 -  /// \param _Tolerance is the handler of the inexact computation. The
   19.15 -  /// default type for this is Tolerance<CapacityMap::Value>.
   19.16 +  /// \param GR The digraph class the algorithm runs on.
   19.17 +  /// \param CAP An arc map of capacities which can be any numreric type.
   19.18 +  /// The default type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
   19.19 +  /// \param TOL Tolerance class for handling inexact computations. The
   19.20 +  /// default tolerance type is \ref Tolerance "Tolerance<CAP::Value>".
   19.21  #ifdef DOXYGEN
   19.22 -  template <typename _Digraph, typename _CapacityMap, typename _Tolerance>
   19.23 +  template <typename GR, typename CAP, typename TOL>
   19.24  #else
   19.25 -  template <typename _Digraph,
   19.26 -            typename _CapacityMap = typename _Digraph::template ArcMap<int>,
   19.27 -            typename _Tolerance = Tolerance<typename _CapacityMap::Value> >
   19.28 +  template <typename GR,
   19.29 +            typename CAP = typename GR::template ArcMap<int>,
   19.30 +            typename TOL = Tolerance<typename CAP::Value> >
   19.31  #endif
   19.32    class HaoOrlin {
   19.33    private:
   19.34  
   19.35 -    typedef _Digraph Digraph;
   19.36 -    typedef _CapacityMap CapacityMap;
   19.37 -    typedef _Tolerance Tolerance;
   19.38 +    typedef GR Digraph;
   19.39 +    typedef CAP CapacityMap;
   19.40 +    typedef TOL Tolerance;
   19.41  
   19.42      typedef typename CapacityMap::Value Value;
   19.43  
   19.44 @@ -817,7 +817,7 @@
   19.45  
   19.46      /// \name Execution control
   19.47      /// The simplest way to execute the algorithm is to use
   19.48 -    /// one of the member functions called \c run(...).
   19.49 +    /// one of the member functions called \ref run().
   19.50      /// \n
   19.51      /// If you need more control on the execution,
   19.52      /// first you must call \ref init(), then the \ref calculateIn() or
    20.1 --- a/lemon/hypercube_graph.h	Thu Mar 05 10:13:20 2009 +0000
    20.2 +++ b/lemon/hypercube_graph.h	Sun Mar 29 23:08:20 2009 +0200
    20.3 @@ -291,7 +291,7 @@
    20.4    /// reasons. Thus the maximum dimension of this implementation is 26
    20.5    /// (assuming that the size of \c int is 32 bit).
    20.6    ///
    20.7 -  /// This graph type is fully conform to the \ref concepts::Graph
    20.8 +  /// This graph type fully conforms to the \ref concepts::Graph
    20.9    /// "Graph" concept, and it also has an important extra feature
   20.10    /// that its maps are real \ref concepts::ReferenceMap
   20.11    /// "reference map"s.
    21.1 --- a/lemon/lgf_reader.h	Thu Mar 05 10:13:20 2009 +0000
    21.2 +++ b/lemon/lgf_reader.h	Sun Mar 29 23:08:20 2009 +0200
    21.3 @@ -448,16 +448,16 @@
    21.4    /// It is impossible to read this in
    21.5    /// a single pass, because the arcs are not constructed when the node
    21.6    /// maps are read.
    21.7 -  template <typename _Digraph>
    21.8 +  template <typename GR>
    21.9    class DigraphReader {
   21.10    public:
   21.11  
   21.12 -    typedef _Digraph Digraph;
   21.13 +    typedef GR Digraph;
   21.14 +
   21.15 +  private:
   21.16 +
   21.17      TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   21.18  
   21.19 -  private:
   21.20 -
   21.21 -
   21.22      std::istream* _is;
   21.23      bool local_is;
   21.24      std::string _filename;
   21.25 @@ -1246,15 +1246,16 @@
   21.26    /// prefixed with \c '+' and \c '-', then these can be read into an
   21.27    /// arc map.  Similarly, an attribute can be read into an arc, if
   21.28    /// it's value is an edge label prefixed with \c '+' or \c '-'.
   21.29 -  template <typename _Graph>
   21.30 +  template <typename GR>
   21.31    class GraphReader {
   21.32    public:
   21.33  
   21.34 -    typedef _Graph Graph;
   21.35 +    typedef GR Graph;
   21.36 +
   21.37 +  private:
   21.38 +
   21.39      TEMPLATE_GRAPH_TYPEDEFS(Graph);
   21.40  
   21.41 -  private:
   21.42 -
   21.43      std::istream* _is;
   21.44      bool local_is;
   21.45      std::string _filename;
   21.46 @@ -1356,12 +1357,12 @@
   21.47      }
   21.48  
   21.49    private:
   21.50 -    template <typename GR>
   21.51 -    friend GraphReader<GR> graphReader(GR& graph, std::istream& is);
   21.52 -    template <typename GR>
   21.53 -    friend GraphReader<GR> graphReader(GR& graph, const std::string& fn); 
   21.54 -    template <typename GR>
   21.55 -    friend GraphReader<GR> graphReader(GR& graph, const char *fn);
   21.56 +    template <typename Graph>
   21.57 +    friend GraphReader<Graph> graphReader(Graph& graph, std::istream& is);
   21.58 +    template <typename Graph>
   21.59 +    friend GraphReader<Graph> graphReader(Graph& graph, const std::string& fn); 
   21.60 +    template <typename Graph>
   21.61 +    friend GraphReader<Graph> graphReader(Graph& graph, const char *fn);
   21.62  
   21.63      GraphReader(GraphReader& other)
   21.64        : _is(other._is), local_is(other.local_is), _graph(other._graph),
    22.1 --- a/lemon/lgf_writer.h	Thu Mar 05 10:13:20 2009 +0000
    22.2 +++ b/lemon/lgf_writer.h	Sun Mar 29 23:08:20 2009 +0200
    22.3 @@ -406,11 +406,11 @@
    22.4    /// section to the stream. The output stream can be retrieved with
    22.5    /// the \c ostream() function, hence the second pass can append its
    22.6    /// output to the output of the first pass.
    22.7 -  template <typename _Digraph>
    22.8 +  template <typename GR>
    22.9    class DigraphWriter {
   22.10    public:
   22.11  
   22.12 -    typedef _Digraph Digraph;
   22.13 +    typedef GR Digraph;
   22.14      TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   22.15  
   22.16    private:
   22.17 @@ -974,11 +974,11 @@
   22.18    /// '+' and \c '-'. The arcs are written into the \c \@attributes
   22.19    /// section as a \c '+' or a \c '-' prefix (depends on the direction
   22.20    /// of the arc) and the label of corresponding edge.
   22.21 -  template <typename _Graph>
   22.22 +  template <typename GR>
   22.23    class GraphWriter {
   22.24    public:
   22.25  
   22.26 -    typedef _Graph Graph;
   22.27 +    typedef GR Graph;
   22.28      TEMPLATE_GRAPH_TYPEDEFS(Graph);
   22.29  
   22.30    private:
   22.31 @@ -1073,15 +1073,15 @@
   22.32  
   22.33    private:
   22.34  
   22.35 -    template <typename GR>
   22.36 -    friend GraphWriter<GR> graphWriter(const GR& graph,
   22.37 -                                       std::ostream& os);
   22.38 -    template <typename GR>
   22.39 -    friend GraphWriter<GR> graphWriter(const GR& graph,
   22.40 -                                       const std::string& fn);
   22.41 -    template <typename GR>
   22.42 -    friend GraphWriter<GR> graphWriter(const GR& graph,
   22.43 -                                       const char *fn);
   22.44 +    template <typename Graph>
   22.45 +    friend GraphWriter<Graph> graphWriter(const Graph& graph,
   22.46 +                                          std::ostream& os);
   22.47 +    template <typename Graph>
   22.48 +    friend GraphWriter<Graph> graphWriter(const Graph& graph,
   22.49 +                                          const std::string& fn);
   22.50 +    template <typename Graph>
   22.51 +    friend GraphWriter<Graph> graphWriter(const Graph& graph,
   22.52 +                                          const char *fn);
   22.53      
   22.54      GraphWriter(GraphWriter& other)
   22.55        : _os(other._os), local_os(other.local_os), _graph(other._graph),
    23.1 --- a/lemon/list_graph.h	Thu Mar 05 10:13:20 2009 +0000
    23.2 +++ b/lemon/list_graph.h	Sun Mar 29 23:08:20 2009 +0200
    23.3 @@ -351,14 +351,14 @@
    23.4      ///Add a new node to the digraph.
    23.5  
    23.6      ///Add a new node to the digraph.
    23.7 -    ///\return the new node.
    23.8 +    ///\return The new node.
    23.9      Node addNode() { return Parent::addNode(); }
   23.10  
   23.11      ///Add a new arc to the digraph.
   23.12  
   23.13      ///Add a new arc to the digraph with source node \c s
   23.14      ///and target node \c t.
   23.15 -    ///\return the new arc.
   23.16 +    ///\return The new arc.
   23.17      Arc addArc(const Node& s, const Node& t) {
   23.18        return Parent::addArc(s, t);
   23.19      }
   23.20 @@ -1208,14 +1208,14 @@
   23.21      /// \brief Add a new node to the graph.
   23.22      ///
   23.23      /// Add a new node to the graph.
   23.24 -    /// \return the new node.
   23.25 +    /// \return The new node.
   23.26      Node addNode() { return Parent::addNode(); }
   23.27  
   23.28      /// \brief Add a new edge to the graph.
   23.29      ///
   23.30      /// Add a new edge to the graph with source node \c s
   23.31      /// and target node \c t.
   23.32 -    /// \return the new edge.
   23.33 +    /// \return The new edge.
   23.34      Edge addEdge(const Node& s, const Node& t) {
   23.35        return Parent::addEdge(s, t);
   23.36      }
    24.1 --- a/lemon/maps.h	Thu Mar 05 10:13:20 2009 +0000
    24.2 +++ b/lemon/maps.h	Sun Mar 29 23:08:20 2009 +0200
    24.3 @@ -63,9 +63,10 @@
    24.4    template<typename K, typename V>
    24.5    class NullMap : public MapBase<K, V> {
    24.6    public:
    24.7 -    typedef MapBase<K, V> Parent;
    24.8 -    typedef typename Parent::Key Key;
    24.9 -    typedef typename Parent::Value Value;
   24.10 +    ///\e
   24.11 +    typedef K Key;
   24.12 +    ///\e
   24.13 +    typedef V Value;
   24.14  
   24.15      /// Gives back a default constructed element.
   24.16      Value operator[](const Key&) const { return Value(); }
   24.17 @@ -102,9 +103,10 @@
   24.18    private:
   24.19      V _value;
   24.20    public:
   24.21 -    typedef MapBase<K, V> Parent;
   24.22 -    typedef typename Parent::Key Key;
   24.23 -    typedef typename Parent::Value Value;
   24.24 +    ///\e
   24.25 +    typedef K Key;
   24.26 +    ///\e
   24.27 +    typedef V Value;
   24.28  
   24.29      /// Default constructor
   24.30  
   24.31 @@ -168,9 +170,10 @@
   24.32    template<typename K, typename V, V v>
   24.33    class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
   24.34    public:
   24.35 -    typedef MapBase<K, V> Parent;
   24.36 -    typedef typename Parent::Key Key;
   24.37 -    typedef typename Parent::Value Value;
   24.38 +    ///\e
   24.39 +    typedef K Key;
   24.40 +    ///\e
   24.41 +    typedef V Value;
   24.42  
   24.43      /// Constructor.
   24.44      ConstMap() {}
   24.45 @@ -202,9 +205,10 @@
   24.46    template <typename T>
   24.47    class IdentityMap : public MapBase<T, T> {
   24.48    public:
   24.49 -    typedef MapBase<T, T> Parent;
   24.50 -    typedef typename Parent::Key Key;
   24.51 -    typedef typename Parent::Value Value;
   24.52 +    ///\e
   24.53 +    typedef T Key;
   24.54 +    ///\e
   24.55 +    typedef T Value;
   24.56  
   24.57      /// Gives back the given value without any modification.
   24.58      Value operator[](const Key &k) const {
   24.59 @@ -245,11 +249,10 @@
   24.60  
   24.61    public:
   24.62  
   24.63 -    typedef MapBase<int, V> Parent;
   24.64      /// Key type
   24.65 -    typedef typename Parent::Key Key;
   24.66 +    typedef int Key;
   24.67      /// Value type
   24.68 -    typedef typename Parent::Value Value;
   24.69 +    typedef V Value;
   24.70      /// Reference type
   24.71      typedef typename Vector::reference Reference;
   24.72      /// Const reference type
   24.73 @@ -353,17 +356,16 @@
   24.74    ///
   24.75    /// The simplest way of using this map is through the sparseMap()
   24.76    /// function.
   24.77 -  template <typename K, typename V, typename Compare = std::less<K> >
   24.78 +  template <typename K, typename V, typename Comp = std::less<K> >
   24.79    class SparseMap : public MapBase<K, V> {
   24.80      template <typename K1, typename V1, typename C1>
   24.81      friend class SparseMap;
   24.82    public:
   24.83  
   24.84 -    typedef MapBase<K, V> Parent;
   24.85      /// Key type
   24.86 -    typedef typename Parent::Key Key;
   24.87 +    typedef K Key;
   24.88      /// Value type
   24.89 -    typedef typename Parent::Value Value;
   24.90 +    typedef V Value;
   24.91      /// Reference type
   24.92      typedef Value& Reference;
   24.93      /// Const reference type
   24.94 @@ -373,7 +375,7 @@
   24.95  
   24.96    private:
   24.97  
   24.98 -    typedef std::map<K, V, Compare> Map;
   24.99 +    typedef std::map<K, V, Comp> Map;
  24.100      Map _map;
  24.101      Value _value;
  24.102  
  24.103 @@ -489,14 +491,15 @@
  24.104      const M1 &_m1;
  24.105      const M2 &_m2;
  24.106    public:
  24.107 -    typedef MapBase<typename M2::Key, typename M1::Value> Parent;
  24.108 -    typedef typename Parent::Key Key;
  24.109 -    typedef typename Parent::Value Value;
  24.110 +    ///\e
  24.111 +    typedef typename M2::Key Key;
  24.112 +    ///\e
  24.113 +    typedef typename M1::Value Value;
  24.114  
  24.115      /// Constructor
  24.116      ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  24.117  
  24.118 -    /// \e
  24.119 +    ///\e
  24.120      typename MapTraits<M1>::ConstReturnValue
  24.121      operator[](const Key &k) const { return _m1[_m2[k]]; }
  24.122    };
  24.123 @@ -545,14 +548,15 @@
  24.124      const M2 &_m2;
  24.125      F _f;
  24.126    public:
  24.127 -    typedef MapBase<typename M1::Key, V> Parent;
  24.128 -    typedef typename Parent::Key Key;
  24.129 -    typedef typename Parent::Value Value;
  24.130 +    ///\e
  24.131 +    typedef typename M1::Key Key;
  24.132 +    ///\e
  24.133 +    typedef V Value;
  24.134  
  24.135      /// Constructor
  24.136      CombineMap(const M1 &m1, const M2 &m2, const F &f = F())
  24.137        : _m1(m1), _m2(m2), _f(f) {}
  24.138 -    /// \e
  24.139 +    ///\e
  24.140      Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); }
  24.141    };
  24.142  
  24.143 @@ -615,13 +619,14 @@
  24.144    class FunctorToMap : public MapBase<K, V> {
  24.145      F _f;
  24.146    public:
  24.147 -    typedef MapBase<K, V> Parent;
  24.148 -    typedef typename Parent::Key Key;
  24.149 -    typedef typename Parent::Value Value;
  24.150 +    ///\e
  24.151 +    typedef K Key;
  24.152 +    ///\e
  24.153 +    typedef V Value;
  24.154  
  24.155      /// Constructor
  24.156      FunctorToMap(const F &f = F()) : _f(f) {}
  24.157 -    /// \e
  24.158 +    ///\e
  24.159      Value operator[](const Key &k) const { return _f(k); }
  24.160    };
  24.161  
  24.162 @@ -669,18 +674,19 @@
  24.163    class MapToFunctor : public MapBase<typename M::Key, typename M::Value> {
  24.164      const M &_m;
  24.165    public:
  24.166 -    typedef MapBase<typename M::Key, typename M::Value> Parent;
  24.167 -    typedef typename Parent::Key Key;
  24.168 -    typedef typename Parent::Value Value;
  24.169 -
  24.170 -    typedef typename Parent::Key argument_type;
  24.171 -    typedef typename Parent::Value result_type;
  24.172 +    ///\e
  24.173 +    typedef typename M::Key Key;
  24.174 +    ///\e
  24.175 +    typedef typename M::Value Value;
  24.176 +
  24.177 +    typedef typename M::Key argument_type;
  24.178 +    typedef typename M::Value result_type;
  24.179  
  24.180      /// Constructor
  24.181      MapToFunctor(const M &m) : _m(m) {}
  24.182 -    /// \e
  24.183 +    ///\e
  24.184      Value operator()(const Key &k) const { return _m[k]; }
  24.185 -    /// \e
  24.186 +    ///\e
  24.187      Value operator[](const Key &k) const { return _m[k]; }
  24.188    };
  24.189  
  24.190 @@ -709,9 +715,10 @@
  24.191    class ConvertMap : public MapBase<typename M::Key, V> {
  24.192      const M &_m;
  24.193    public:
  24.194 -    typedef MapBase<typename M::Key, V> Parent;
  24.195 -    typedef typename Parent::Key Key;
  24.196 -    typedef typename Parent::Value Value;
  24.197 +    ///\e
  24.198 +    typedef typename M::Key Key;
  24.199 +    ///\e
  24.200 +    typedef V Value;
  24.201  
  24.202      /// Constructor
  24.203  
  24.204 @@ -719,7 +726,7 @@
  24.205      /// \param m The underlying map.
  24.206      ConvertMap(const M &m) : _m(m) {}
  24.207  
  24.208 -    /// \e
  24.209 +    ///\e
  24.210      Value operator[](const Key &k) const { return _m[k]; }
  24.211    };
  24.212  
  24.213 @@ -751,9 +758,10 @@
  24.214      M1 &_m1;
  24.215      M2 &_m2;
  24.216    public:
  24.217 -    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
  24.218 -    typedef typename Parent::Key Key;
  24.219 -    typedef typename Parent::Value Value;
  24.220 +    ///\e
  24.221 +    typedef typename M1::Key Key;
  24.222 +    ///\e
  24.223 +    typedef typename M1::Value Value;
  24.224  
  24.225      /// Constructor
  24.226      ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {}
  24.227 @@ -797,13 +805,14 @@
  24.228      const M1 &_m1;
  24.229      const M2 &_m2;
  24.230    public:
  24.231 -    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
  24.232 -    typedef typename Parent::Key Key;
  24.233 -    typedef typename Parent::Value Value;
  24.234 +    ///\e
  24.235 +    typedef typename M1::Key Key;
  24.236 +    ///\e
  24.237 +    typedef typename M1::Value Value;
  24.238  
  24.239      /// Constructor
  24.240      AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  24.241 -    /// \e
  24.242 +    ///\e
  24.243      Value operator[](const Key &k) const { return _m1[k]+_m2[k]; }
  24.244    };
  24.245  
  24.246 @@ -845,13 +854,14 @@
  24.247      const M1 &_m1;
  24.248      const M2 &_m2;
  24.249    public:
  24.250 -    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
  24.251 -    typedef typename Parent::Key Key;
  24.252 -    typedef typename Parent::Value Value;
  24.253 +    ///\e
  24.254 +    typedef typename M1::Key Key;
  24.255 +    ///\e
  24.256 +    typedef typename M1::Value Value;
  24.257  
  24.258      /// Constructor
  24.259      SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  24.260 -    /// \e
  24.261 +    ///\e
  24.262      Value operator[](const Key &k) const { return _m1[k]-_m2[k]; }
  24.263    };
  24.264  
  24.265 @@ -894,13 +904,14 @@
  24.266      const M1 &_m1;
  24.267      const M2 &_m2;
  24.268    public:
  24.269 -    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
  24.270 -    typedef typename Parent::Key Key;
  24.271 -    typedef typename Parent::Value Value;
  24.272 +    ///\e
  24.273 +    typedef typename M1::Key Key;
  24.274 +    ///\e
  24.275 +    typedef typename M1::Value Value;
  24.276  
  24.277      /// Constructor
  24.278      MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
  24.279 -    /// \e
  24.280 +    ///\e
  24.281      Value operator[](const Key &k) const { return _m1[k]*_m2[k]; }
  24.282    };
  24.283  
  24.284 @@ -942,13 +953,14 @@
  24.285      const M1 &_m1;
  24.286      const M2 &_m2;
  24.287    public:
  24.288 -    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
  24.289 -    typedef typename Parent::Key Key;
  24.290 -    typedef typename Parent::Value Value;
  24.291 +    ///\e
  24.292 +    typedef typename M1::Key Key;
  24.293 +    ///\e
  24.294 +    typedef typename M1::Value Value;
  24.295  
  24.296      /// Constructor
  24.297      DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
  24.298 -    /// \e
  24.299 +    ///\e
  24.300      Value operator[](const Key &k) const { return _m1[k]/_m2[k]; }
  24.301    };
  24.302  
  24.303 @@ -992,9 +1004,10 @@
  24.304      const M &_m;
  24.305      C _v;
  24.306    public:
  24.307 -    typedef MapBase<typename M::Key, typename M::Value> Parent;
  24.308 -    typedef typename Parent::Key Key;
  24.309 -    typedef typename Parent::Value Value;
  24.310 +    ///\e
  24.311 +    typedef typename M::Key Key;
  24.312 +    ///\e
  24.313 +    typedef typename M::Value Value;
  24.314  
  24.315      /// Constructor
  24.316  
  24.317 @@ -1002,7 +1015,7 @@
  24.318      /// \param m The undelying map.
  24.319      /// \param v The constant value.
  24.320      ShiftMap(const M &m, const C &v) : _m(m), _v(v) {}
  24.321 -    /// \e
  24.322 +    ///\e
  24.323      Value operator[](const Key &k) const { return _m[k]+_v; }
  24.324    };
  24.325  
  24.326 @@ -1022,9 +1035,10 @@
  24.327      M &_m;
  24.328      C _v;
  24.329    public:
  24.330 -    typedef MapBase<typename M::Key, typename M::Value> Parent;
  24.331 -    typedef typename Parent::Key Key;
  24.332 -    typedef typename Parent::Value Value;
  24.333 +    ///\e
  24.334 +    typedef typename M::Key Key;
  24.335 +    ///\e
  24.336 +    typedef typename M::Value Value;
  24.337  
  24.338      /// Constructor
  24.339  
  24.340 @@ -1032,9 +1046,9 @@
  24.341      /// \param m The undelying map.
  24.342      /// \param v The constant value.
  24.343      ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {}
  24.344 -    /// \e
  24.345 +    ///\e
  24.346      Value operator[](const Key &k) const { return _m[k]+_v; }
  24.347 -    /// \e
  24.348 +    ///\e
  24.349      void set(const Key &k, const Value &v) { _m.set(k, v-_v); }
  24.350    };
  24.351  
  24.352 @@ -1093,9 +1107,10 @@
  24.353      const M &_m;
  24.354      C _v;
  24.355    public:
  24.356 -    typedef MapBase<typename M::Key, typename M::Value> Parent;
  24.357 -    typedef typename Parent::Key Key;
  24.358 -    typedef typename Parent::Value Value;
  24.359 +    ///\e
  24.360 +    typedef typename M::Key Key;
  24.361 +    ///\e
  24.362 +    typedef typename M::Value Value;
  24.363  
  24.364      /// Constructor
  24.365  
  24.366 @@ -1103,7 +1118,7 @@
  24.367      /// \param m The undelying map.
  24.368      /// \param v The constant value.
  24.369      ScaleMap(const M &m, const C &v) : _m(m), _v(v) {}
  24.370 -    /// \e
  24.371 +    ///\e
  24.372      Value operator[](const Key &k) const { return _v*_m[k]; }
  24.373    };
  24.374  
  24.375 @@ -1124,9 +1139,10 @@
  24.376      M &_m;
  24.377      C _v;
  24.378    public:
  24.379 -    typedef MapBase<typename M::Key, typename M::Value> Parent;
  24.380 -    typedef typename Parent::Key Key;
  24.381 -    typedef typename Parent::Value Value;
  24.382 +    ///\e
  24.383 +    typedef typename M::Key Key;
  24.384 +    ///\e
  24.385 +    typedef typename M::Value Value;
  24.386  
  24.387      /// Constructor
  24.388  
  24.389 @@ -1134,9 +1150,9 @@
  24.390      /// \param m The undelying map.
  24.391      /// \param v The constant value.
  24.392      ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {}
  24.393 -    /// \e
  24.394 +    ///\e
  24.395      Value operator[](const Key &k) const { return _v*_m[k]; }
  24.396 -    /// \e
  24.397 +    ///\e
  24.398      void set(const Key &k, const Value &v) { _m.set(k, v/_v); }
  24.399    };
  24.400  
  24.401 @@ -1193,13 +1209,14 @@
  24.402    class NegMap : public MapBase<typename M::Key, typename M::Value> {
  24.403      const M& _m;
  24.404    public:
  24.405 -    typedef MapBase<typename M::Key, typename M::Value> Parent;
  24.406 -    typedef typename Parent::Key Key;
  24.407 -    typedef typename Parent::Value Value;
  24.408 +    ///\e
  24.409 +    typedef typename M::Key Key;
  24.410 +    ///\e
  24.411 +    typedef typename M::Value Value;
  24.412  
  24.413      /// Constructor
  24.414      NegMap(const M &m) : _m(m) {}
  24.415 -    /// \e
  24.416 +    ///\e
  24.417      Value operator[](const Key &k) const { return -_m[k]; }
  24.418    };
  24.419  
  24.420 @@ -1228,15 +1245,16 @@
  24.421    class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
  24.422      M &_m;
  24.423    public:
  24.424 -    typedef MapBase<typename M::Key, typename M::Value> Parent;
  24.425 -    typedef typename Parent::Key Key;
  24.426 -    typedef typename Parent::Value Value;
  24.427 +    ///\e
  24.428 +    typedef typename M::Key Key;
  24.429 +    ///\e
  24.430 +    typedef typename M::Value Value;
  24.431  
  24.432      /// Constructor
  24.433      NegWriteMap(M &m) : _m(m) {}
  24.434 -    /// \e
  24.435 +    ///\e
  24.436      Value operator[](const Key &k) const { return -_m[k]; }
  24.437 -    /// \e
  24.438 +    ///\e
  24.439      void set(const Key &k, const Value &v) { _m.set(k, -v); }
  24.440    };
  24.441  
  24.442 @@ -1282,13 +1300,14 @@
  24.443    class AbsMap : public MapBase<typename M::Key, typename M::Value> {
  24.444      const M &_m;
  24.445    public:
  24.446 -    typedef MapBase<typename M::Key, typename M::Value> Parent;
  24.447 -    typedef typename Parent::Key Key;
  24.448 -    typedef typename Parent::Value Value;
  24.449 +    ///\e
  24.450 +    typedef typename M::Key Key;
  24.451 +    ///\e
  24.452 +    typedef typename M::Value Value;
  24.453  
  24.454      /// Constructor
  24.455      AbsMap(const M &m) : _m(m) {}
  24.456 -    /// \e
  24.457 +    ///\e
  24.458      Value operator[](const Key &k) const {
  24.459        Value tmp = _m[k];
  24.460        return tmp >= 0 ? tmp : -tmp;
  24.461 @@ -1337,9 +1356,10 @@
  24.462    template <typename K>
  24.463    class TrueMap : public MapBase<K, bool> {
  24.464    public:
  24.465 -    typedef MapBase<K, bool> Parent;
  24.466 -    typedef typename Parent::Key Key;
  24.467 -    typedef typename Parent::Value Value;
  24.468 +    ///\e
  24.469 +    typedef K Key;
  24.470 +    ///\e
  24.471 +    typedef bool Value;
  24.472  
  24.473      /// Gives back \c true.
  24.474      Value operator[](const Key&) const { return true; }
  24.475 @@ -1374,9 +1394,10 @@
  24.476    template <typename K>
  24.477    class FalseMap : public MapBase<K, bool> {
  24.478    public:
  24.479 -    typedef MapBase<K, bool> Parent;
  24.480 -    typedef typename Parent::Key Key;
  24.481 -    typedef typename Parent::Value Value;
  24.482 +    ///\e
  24.483 +    typedef K Key;
  24.484 +    ///\e
  24.485 +    typedef bool Value;
  24.486  
  24.487      /// Gives back \c false.
  24.488      Value operator[](const Key&) const { return false; }
  24.489 @@ -1419,13 +1440,14 @@
  24.490      const M1 &_m1;
  24.491      const M2 &_m2;
  24.492    public:
  24.493 -    typedef MapBase<typename M1::Key, bool> Parent;
  24.494 -    typedef typename Parent::Key Key;
  24.495 -    typedef typename Parent::Value Value;
  24.496 +    ///\e
  24.497 +    typedef typename M1::Key Key;
  24.498 +    ///\e
  24.499 +    typedef bool Value;
  24.500  
  24.501      /// Constructor
  24.502      AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  24.503 -    /// \e
  24.504 +    ///\e
  24.505      Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; }
  24.506    };
  24.507  
  24.508 @@ -1467,13 +1489,14 @@
  24.509      const M1 &_m1;
  24.510      const M2 &_m2;
  24.511    public:
  24.512 -    typedef MapBase<typename M1::Key, bool> Parent;
  24.513 -    typedef typename Parent::Key Key;
  24.514 -    typedef typename Parent::Value Value;
  24.515 +    ///\e
  24.516 +    typedef typename M1::Key Key;
  24.517 +    ///\e
  24.518 +    typedef bool Value;
  24.519  
  24.520      /// Constructor
  24.521      OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  24.522 -    /// \e
  24.523 +    ///\e
  24.524      Value operator[](const Key &k) const { return _m1[k]||_m2[k]; }
  24.525    };
  24.526  
  24.527 @@ -1506,13 +1529,14 @@
  24.528    class NotMap : public MapBase<typename M::Key, bool> {
  24.529      const M &_m;
  24.530    public:
  24.531 -    typedef MapBase<typename M::Key, bool> Parent;
  24.532 -    typedef typename Parent::Key Key;
  24.533 -    typedef typename Parent::Value Value;
  24.534 +    ///\e
  24.535 +    typedef typename M::Key Key;
  24.536 +    ///\e
  24.537 +    typedef bool Value;
  24.538  
  24.539      /// Constructor
  24.540      NotMap(const M &m) : _m(m) {}
  24.541 -    /// \e
  24.542 +    ///\e
  24.543      Value operator[](const Key &k) const { return !_m[k]; }
  24.544    };
  24.545  
  24.546 @@ -1532,15 +1556,16 @@
  24.547    class NotWriteMap : public MapBase<typename M::Key, bool> {
  24.548      M &_m;
  24.549    public:
  24.550 -    typedef MapBase<typename M::Key, bool> Parent;
  24.551 -    typedef typename Parent::Key Key;
  24.552 -    typedef typename Parent::Value Value;
  24.553 +    ///\e
  24.554 +    typedef typename M::Key Key;
  24.555 +    ///\e
  24.556 +    typedef bool Value;
  24.557  
  24.558      /// Constructor
  24.559      NotWriteMap(M &m) : _m(m) {}
  24.560 -    /// \e
  24.561 +    ///\e
  24.562      Value operator[](const Key &k) const { return !_m[k]; }
  24.563 -    /// \e
  24.564 +    ///\e
  24.565      void set(const Key &k, bool v) { _m.set(k, !v); }
  24.566    };
  24.567  
  24.568 @@ -1595,13 +1620,14 @@
  24.569      const M1 &_m1;
  24.570      const M2 &_m2;
  24.571    public:
  24.572 -    typedef MapBase<typename M1::Key, bool> Parent;
  24.573 -    typedef typename Parent::Key Key;
  24.574 -    typedef typename Parent::Value Value;
  24.575 +    ///\e
  24.576 +    typedef typename M1::Key Key;
  24.577 +    ///\e
  24.578 +    typedef bool Value;
  24.579  
  24.580      /// Constructor
  24.581      EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  24.582 -    /// \e
  24.583 +    ///\e
  24.584      Value operator[](const Key &k) const { return _m1[k]==_m2[k]; }
  24.585    };
  24.586  
  24.587 @@ -1643,13 +1669,14 @@
  24.588      const M1 &_m1;
  24.589      const M2 &_m2;
  24.590    public:
  24.591 -    typedef MapBase<typename M1::Key, bool> Parent;
  24.592 -    typedef typename Parent::Key Key;
  24.593 -    typedef typename Parent::Value Value;
  24.594 +    ///\e
  24.595 +    typedef typename M1::Key Key;
  24.596 +    ///\e
  24.597 +    typedef bool Value;
  24.598  
  24.599      /// Constructor
  24.600      LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
  24.601 -    /// \e
  24.602 +    ///\e
  24.603      Value operator[](const Key &k) const { return _m1[k]<_m2[k]; }
  24.604    };
  24.605  
  24.606 @@ -1705,24 +1732,27 @@
  24.607    /// The simplest way of using this map is through the loggerBoolMap()
  24.608    /// function.
  24.609    ///
  24.610 -  /// \tparam It The type of the iterator.
  24.611 -  /// \tparam Ke The key type of the map. The default value set
  24.612 +  /// \tparam IT The type of the iterator.
  24.613 +  /// \tparam KEY The key type of the map. The default value set
  24.614    /// according to the iterator type should work in most cases.
  24.615    ///
  24.616    /// \note The container of the iterator must contain enough space
  24.617    /// for the elements or the iterator should be an inserter iterator.
  24.618  #ifdef DOXYGEN
  24.619 -  template <typename It, typename Ke>
  24.620 +  template <typename IT, typename KEY>
  24.621  #else
  24.622 -  template <typename It,
  24.623 -            typename Ke=typename _maps_bits::IteratorTraits<It>::Value>
  24.624 +  template <typename IT,
  24.625 +            typename KEY = typename _maps_bits::IteratorTraits<IT>::Value>
  24.626  #endif
  24.627 -  class LoggerBoolMap {
  24.628 +  class LoggerBoolMap : public MapBase<KEY, bool> {
  24.629    public:
  24.630 -    typedef It Iterator;
  24.631 -
  24.632 -    typedef Ke Key;
  24.633 +
  24.634 +    ///\e
  24.635 +    typedef KEY Key;
  24.636 +    ///\e
  24.637      typedef bool Value;
  24.638 +    ///\e
  24.639 +    typedef IT Iterator;
  24.640  
  24.641      /// Constructor
  24.642      LoggerBoolMap(Iterator it)
  24.643 @@ -1785,23 +1815,35 @@
  24.644    /// \addtogroup graph_maps
  24.645    /// @{
  24.646  
  24.647 -  /// Provides an immutable and unique id for each item in the graph.
  24.648 -
  24.649 -  /// The IdMap class provides a unique and immutable id for each item of the
  24.650 -  /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
  24.651 -  /// different items (nodes) get different ids <li>\b immutable: the id of an
  24.652 -  /// item (node) does not change (even if you delete other nodes).  </ul>
  24.653 -  /// Through this map you get access (i.e. can read) the inner id values of
  24.654 -  /// the items stored in the graph. This map can be inverted with its member
  24.655 +  /// \brief Provides an immutable and unique id for each item in a graph.
  24.656 +  ///
  24.657 +  /// IdMap provides a unique and immutable id for each item of the
  24.658 +  /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is 
  24.659 +  ///  - \b unique: different items get different ids,
  24.660 +  ///  - \b immutable: the id of an item does not change (even if you
  24.661 +  ///    delete other nodes).
  24.662 +  ///
  24.663 +  /// Using this map you get access (i.e. can read) the inner id values of
  24.664 +  /// the items stored in the graph, which is returned by the \c id()
  24.665 +  /// function of the graph. This map can be inverted with its member
  24.666    /// class \c InverseMap or with the \c operator() member.
  24.667    ///
  24.668 -  template <typename _Graph, typename _Item>
  24.669 -  class IdMap {
  24.670 +  /// \tparam GR The graph type.
  24.671 +  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
  24.672 +  /// \c GR::Edge).
  24.673 +  ///
  24.674 +  /// \see DescriptorMap
  24.675 +  template <typename GR, typename K>
  24.676 +  class IdMap : public MapBase<K, int> {
  24.677    public:
  24.678 -    typedef _Graph Graph;
  24.679 +    /// The graph type of IdMap.
  24.680 +    typedef GR Graph;
  24.681 +    /// The key type of IdMap (\c Node, \c Arc or \c Edge).
  24.682 +    typedef K Item;
  24.683 +    /// The key type of IdMap (\c Node, \c Arc or \c Edge).
  24.684 +    typedef K Key;
  24.685 +    /// The value type of IdMap.
  24.686      typedef int Value;
  24.687 -    typedef _Item Item;
  24.688 -    typedef _Item Key;
  24.689  
  24.690      /// \brief Constructor.
  24.691      ///
  24.692 @@ -1813,9 +1855,9 @@
  24.693      /// Gives back the immutable and unique \e id of the item.
  24.694      int operator[](const Item& item) const { return _graph->id(item);}
  24.695  
  24.696 -    /// \brief Gives back the item by its id.
  24.697 +    /// \brief Gives back the \e item by its id.
  24.698      ///
  24.699 -    /// Gives back the item by its id.
  24.700 +    /// Gives back the \e item by its id.
  24.701      Item operator()(int id) { return _graph->fromId(id, Item()); }
  24.702  
  24.703    private:
  24.704 @@ -1823,9 +1865,9 @@
  24.705  
  24.706    public:
  24.707  
  24.708 -    /// \brief The class represents the inverse of its owner (IdMap).
  24.709 +    /// \brief This class represents the inverse of its owner (IdMap).
  24.710      ///
  24.711 -    /// The class represents the inverse of its owner (IdMap).
  24.712 +    /// This class represents the inverse of its owner (IdMap).
  24.713      /// \see inverse()
  24.714      class InverseMap {
  24.715      public:
  24.716 @@ -1843,7 +1885,6 @@
  24.717        /// \brief Gives back the given item from its id.
  24.718        ///
  24.719        /// Gives back the given item from its id.
  24.720 -      ///
  24.721        Item operator[](int id) const { return _graph->fromId(id, Item());}
  24.722  
  24.723      private:
  24.724 @@ -1854,56 +1895,57 @@
  24.725      ///
  24.726      /// Gives back the inverse of the IdMap.
  24.727      InverseMap inverse() const { return InverseMap(*_graph);}
  24.728 -
  24.729    };
  24.730  
  24.731  
  24.732 -  /// \brief General invertable graph-map type.
  24.733 -
  24.734 -  /// This type provides simple invertable graph-maps.
  24.735 -  /// The InvertableMap wraps an arbitrary ReadWriteMap
  24.736 +  /// \brief General invertable graph map type.
  24.737 +
  24.738 +  /// This class provides simple invertable graph maps.
  24.739 +  /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap"
  24.740    /// and if a key is set to a new value then store it
  24.741    /// in the inverse map.
  24.742    ///
  24.743    /// The values of the map can be accessed
  24.744    /// with stl compatible forward iterator.
  24.745    ///
  24.746 -  /// \tparam _Graph The graph type.
  24.747 -  /// \tparam _Item The item type of the graph.
  24.748 -  /// \tparam _Value The value type of the map.
  24.749 +  /// \tparam GR The graph type.
  24.750 +  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
  24.751 +  /// \c GR::Edge).
  24.752 +  /// \tparam V The value type of the map.
  24.753    ///
  24.754    /// \see IterableValueMap
  24.755 -  template <typename _Graph, typename _Item, typename _Value>
  24.756 +  template <typename GR, typename K, typename V>
  24.757    class InvertableMap
  24.758 -    : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type {
  24.759 +    : protected ItemSetTraits<GR, K>::template Map<V>::Type {
  24.760    private:
  24.761  
  24.762 -    typedef typename ItemSetTraits<_Graph, _Item>::
  24.763 -    template Map<_Value>::Type Map;
  24.764 -    typedef _Graph Graph;
  24.765 -
  24.766 -    typedef std::map<_Value, _Item> Container;
  24.767 +    typedef typename ItemSetTraits<GR, K>::
  24.768 +      template Map<V>::Type Map;
  24.769 +
  24.770 +    typedef std::map<V, K> Container;
  24.771      Container _inv_map;
  24.772  
  24.773    public:
  24.774  
  24.775 -    /// The key type of InvertableMap (Node, Arc, Edge).
  24.776 -    typedef typename Map::Key Key;
  24.777 -    /// The value type of the InvertableMap.
  24.778 -    typedef typename Map::Value Value;
  24.779 +    /// The graph type of InvertableMap.
  24.780 +    typedef GR Graph;
  24.781 +    /// The key type of InvertableMap (\c Node, \c Arc or \c Edge).
  24.782 +    typedef K Item;
  24.783 +    /// The key type of InvertableMap (\c Node, \c Arc or \c Edge).
  24.784 +    typedef K Key;
  24.785 +    /// The value type of InvertableMap.
  24.786 +    typedef V Value;
  24.787  
  24.788      /// \brief Constructor.
  24.789      ///
  24.790 -    /// Construct a new InvertableMap for the graph.
  24.791 -    ///
  24.792 +    /// Construct a new InvertableMap for the given graph.
  24.793      explicit InvertableMap(const Graph& graph) : Map(graph) {}
  24.794  
  24.795      /// \brief Forward iterator for values.
  24.796      ///
  24.797      /// This iterator is an stl compatible forward
  24.798      /// iterator on the values of the map. The values can
  24.799 -    /// be accessed in the [beginValue, endValue) range.
  24.800 -    ///
  24.801 +    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
  24.802      class ValueIterator
  24.803        : public std::iterator<std::forward_iterator_tag, Value> {
  24.804        friend class InvertableMap;
  24.805 @@ -1935,7 +1977,7 @@
  24.806      ///
  24.807      /// Returns an stl compatible iterator to the
  24.808      /// first value of the map. The values of the
  24.809 -    /// map can be accessed in the [beginValue, endValue)
  24.810 +    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
  24.811      /// range.
  24.812      ValueIterator beginValue() const {
  24.813        return ValueIterator(_inv_map.begin());
  24.814 @@ -1945,15 +1987,15 @@
  24.815      ///
  24.816      /// Returns an stl compatible iterator after the
  24.817      /// last value of the map. The values of the
  24.818 -    /// map can be accessed in the [beginValue, endValue)
  24.819 +    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
  24.820      /// range.
  24.821      ValueIterator endValue() const {
  24.822        return ValueIterator(_inv_map.end());
  24.823      }
  24.824  
  24.825 -    /// \brief The setter function of the map.
  24.826 +    /// \brief Sets the value associated with the given key.
  24.827      ///
  24.828 -    /// Sets the mapped value.
  24.829 +    /// Sets the value associated with the given key.
  24.830      void set(const Key& key, const Value& val) {
  24.831        Value oldval = Map::operator[](key);
  24.832        typename Container::iterator it = _inv_map.find(oldval);
  24.833 @@ -1964,9 +2006,9 @@
  24.834        Map::set(key, val);
  24.835      }
  24.836  
  24.837 -    /// \brief The getter function of the map.
  24.838 +    /// \brief Returns the value associated with the given key.
  24.839      ///
  24.840 -    /// It gives back the value associated with the key.
  24.841 +    /// Returns the value associated with the given key.
  24.842      typename MapTraits<Map>::ConstReturnValue
  24.843      operator[](const Key& key) const {
  24.844        return Map::operator[](key);
  24.845 @@ -1982,9 +2024,9 @@
  24.846  
  24.847    protected:
  24.848  
  24.849 -    /// \brief Erase the key from the map.
  24.850 +    /// \brief Erase the key from the map and the inverse map.
  24.851      ///
  24.852 -    /// Erase the key to the map. It is called by the
  24.853 +    /// Erase the key from the map and the inverse map. It is called by the
  24.854      /// \c AlterationNotifier.
  24.855      virtual void erase(const Key& key) {
  24.856        Value val = Map::operator[](key);
  24.857 @@ -1995,9 +2037,9 @@
  24.858        Map::erase(key);
  24.859      }
  24.860  
  24.861 -    /// \brief Erase more keys from the map.
  24.862 +    /// \brief Erase more keys from the map and the inverse map.
  24.863      ///
  24.864 -    /// Erase more keys from the map. It is called by the
  24.865 +    /// Erase more keys from the map and the inverse map. It is called by the
  24.866      /// \c AlterationNotifier.
  24.867      virtual void erase(const std::vector<Key>& keys) {
  24.868        for (int i = 0; i < int(keys.size()); ++i) {
  24.869 @@ -2010,9 +2052,9 @@
  24.870        Map::erase(keys);
  24.871      }
  24.872  
  24.873 -    /// \brief Clear the keys from the map and inverse map.
  24.874 +    /// \brief Clear the keys from the map and the inverse map.
  24.875      ///
  24.876 -    /// Clear the keys from the map and inverse map. It is called by the
  24.877 +    /// Clear the keys from the map and the inverse map. It is called by the
  24.878      /// \c AlterationNotifier.
  24.879      virtual void clear() {
  24.880        _inv_map.clear();
  24.881 @@ -2024,10 +2066,10 @@
  24.882      /// \brief The inverse map type.
  24.883      ///
  24.884      /// The inverse of this map. The subscript operator of the map
  24.885 -    /// gives back always the item what was last assigned to the value.
  24.886 +    /// gives back the item that was last assigned to the value.
  24.887      class InverseMap {
  24.888      public:
  24.889 -      /// \brief Constructor of the InverseMap.
  24.890 +      /// \brief Constructor
  24.891        ///
  24.892        /// Constructor of the InverseMap.
  24.893        explicit InverseMap(const InvertableMap& inverted)
  24.894 @@ -2040,8 +2082,8 @@
  24.895  
  24.896        /// \brief Subscript operator.
  24.897        ///
  24.898 -      /// Subscript operator. It gives back always the item
  24.899 -      /// what was last assigned to the value.
  24.900 +      /// Subscript operator. It gives back the item
  24.901 +      /// that was last assigned to the given value.
  24.902        Value operator[](const Key& key) const {
  24.903          return _inverted(key);
  24.904        }
  24.905 @@ -2050,9 +2092,9 @@
  24.906        const InvertableMap& _inverted;
  24.907      };
  24.908  
  24.909 -    /// \brief It gives back the just readable inverse map.
  24.910 +    /// \brief It gives back the read-only inverse map.
  24.911      ///
  24.912 -    /// It gives back the just readable inverse map.
  24.913 +    /// It gives back the read-only inverse map.
  24.914      InverseMap inverse() const {
  24.915        return InverseMap(*this);
  24.916      }
  24.917 @@ -2060,40 +2102,48 @@
  24.918    };
  24.919  
  24.920    /// \brief Provides a mutable, continuous and unique descriptor for each
  24.921 -  /// item in the graph.
  24.922 +  /// item in a graph.
  24.923    ///
  24.924 -  /// The DescriptorMap class provides a unique and continuous (but mutable)
  24.925 -  /// descriptor (id) for each item of the same type (e.g. node) in the
  24.926 -  /// graph. This id is <ul><li>\b unique: different items (nodes) get
  24.927 -  /// different ids <li>\b continuous: the range of the ids is the set of
  24.928 -  /// integers between 0 and \c n-1, where \c n is the number of the items of
  24.929 -  /// this type (e.g. nodes) (so the id of a node can change if you delete an
  24.930 -  /// other node, i.e. this id is mutable).  </ul> This map can be inverted
  24.931 -  /// with its member class \c InverseMap, or with the \c operator() member.
  24.932 +  /// DescriptorMap provides a unique and continuous (but mutable)
  24.933 +  /// descriptor (id) for each item of the same type (\c Node, \c Arc or
  24.934 +  /// \c Edge) in a graph. This id is
  24.935 +  ///  - \b unique: different items get different ids,
  24.936 +  ///  - \b continuous: the range of the ids is the set of integers
  24.937 +  ///    between 0 and \c n-1, where \c n is the number of the items of
  24.938 +  ///    this type (\c Node, \c Arc or \c Edge). So the id of an item can
  24.939 +  ///    change if you delete an other item of the same type, i.e. this
  24.940 +  ///    id is mutable.
  24.941    ///
  24.942 -  /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
  24.943 -  /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
  24.944 -  /// Edge.
  24.945 -  template <typename _Graph, typename _Item>
  24.946 +  /// Thus this id is not (necessarily) the same as what can get using
  24.947 +  /// the \c id() function of the graph or \ref IdMap.
  24.948 +  /// This map can be inverted with its member class \c InverseMap,
  24.949 +  /// or with the \c operator() member.
  24.950 +  ///
  24.951 +  /// \tparam GR The graph type.
  24.952 +  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
  24.953 +  /// \c GR::Edge).
  24.954 +  ///
  24.955 +  /// \see IdMap
  24.956 +  template <typename GR, typename K>
  24.957    class DescriptorMap
  24.958 -    : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Type {
  24.959 -
  24.960 -    typedef _Item Item;
  24.961 -    typedef typename ItemSetTraits<_Graph, _Item>::template Map<int>::Type Map;
  24.962 +    : protected ItemSetTraits<GR, K>::template Map<int>::Type {
  24.963 +
  24.964 +    typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Map;
  24.965  
  24.966    public:
  24.967 -    /// The graph class of DescriptorMap.
  24.968 -    typedef _Graph Graph;
  24.969 -
  24.970 -    /// The key type of DescriptorMap (Node, Arc, Edge).
  24.971 -    typedef typename Map::Key Key;
  24.972 +    /// The graph type of DescriptorMap.
  24.973 +    typedef GR Graph;
  24.974 +    /// The key type of DescriptorMap (\c Node, \c Arc or \c Edge).
  24.975 +    typedef K Item;
  24.976 +    /// The key type of DescriptorMap (\c Node, \c Arc or \c Edge).
  24.977 +    typedef K Key;
  24.978      /// The value type of DescriptorMap.
  24.979 -    typedef typename Map::Value Value;
  24.980 +    typedef int Value;
  24.981  
  24.982      /// \brief Constructor.
  24.983      ///
  24.984      /// Constructor for descriptor map.
  24.985 -    explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
  24.986 +    explicit DescriptorMap(const Graph& gr) : Map(gr) {
  24.987        Item it;
  24.988        const typename Map::Notifier* nf = Map::notifier();
  24.989        for (nf->first(it); it != INVALID; nf->next(it)) {
  24.990 @@ -2104,7 +2154,7 @@
  24.991  
  24.992    protected:
  24.993  
  24.994 -    /// \brief Add a new key to the map.
  24.995 +    /// \brief Adds a new key to the map.
  24.996      ///
  24.997      /// Add a new key to the map. It is called by the
  24.998      /// \c AlterationNotifier.
  24.999 @@ -2214,12 +2264,13 @@
 24.1000      Container _inv_map;
 24.1001  
 24.1002    public:
 24.1003 +
 24.1004      /// \brief The inverse map type of DescriptorMap.
 24.1005      ///
 24.1006      /// The inverse map type of DescriptorMap.
 24.1007      class InverseMap {
 24.1008      public:
 24.1009 -      /// \brief Constructor of the InverseMap.
 24.1010 +      /// \brief Constructor
 24.1011        ///
 24.1012        /// Constructor of the InverseMap.
 24.1013        explicit InverseMap(const DescriptorMap& inverted)
 24.1014 @@ -2234,7 +2285,7 @@
 24.1015        /// \brief Subscript operator.
 24.1016        ///
 24.1017        /// Subscript operator. It gives back the item
 24.1018 -      /// that the descriptor belongs to currently.
 24.1019 +      /// that the descriptor currently belongs to.
 24.1020        Value operator[](const Key& key) const {
 24.1021          return _inverted(key);
 24.1022        }
 24.1023 @@ -2258,230 +2309,198 @@
 24.1024      }
 24.1025    };
 24.1026  
 24.1027 -  /// \brief Returns the source of the given arc.
 24.1028 +  /// \brief Map of the source nodes of arcs in a digraph.
 24.1029    ///
 24.1030 -  /// The SourceMap gives back the source Node of the given arc.
 24.1031 +  /// SourceMap provides access for the source node of each arc in a digraph,
 24.1032 +  /// which is returned by the \c source() function of the digraph.
 24.1033 +  /// \tparam GR The digraph type.
 24.1034    /// \see TargetMap
 24.1035 -  template <typename Digraph>
 24.1036 +  template <typename GR>
 24.1037    class SourceMap {
 24.1038    public:
 24.1039  
 24.1040 -    typedef typename Digraph::Node Value;
 24.1041 -    typedef typename Digraph::Arc Key;
 24.1042 +    ///\e
 24.1043 +    typedef typename GR::Arc Key;
 24.1044 +    ///\e
 24.1045 +    typedef typename GR::Node Value;
 24.1046  
 24.1047      /// \brief Constructor
 24.1048      ///
 24.1049 -    /// Constructor
 24.1050 +    /// Constructor.
 24.1051      /// \param digraph The digraph that the map belongs to.
 24.1052 -    explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
 24.1053 -
 24.1054 -    /// \brief The subscript operator.
 24.1055 +    explicit SourceMap(const GR& digraph) : _graph(digraph) {}
 24.1056 +
 24.1057 +    /// \brief Returns the source node of the given arc.
 24.1058      ///
 24.1059 -    /// The subscript operator.
 24.1060 -    /// \param arc The arc
 24.1061 -    /// \return The source of the arc
 24.1062 +    /// Returns the source node of the given arc.
 24.1063      Value operator[](const Key& arc) const {
 24.1064 -      return _digraph.source(arc);
 24.1065 +      return _graph.source(arc);
 24.1066      }
 24.1067  
 24.1068    private:
 24.1069 -    const Digraph& _digraph;
 24.1070 +    const GR& _graph;
 24.1071    };
 24.1072  
 24.1073    /// \brief Returns a \c SourceMap class.
 24.1074    ///
 24.1075    /// This function just returns an \c SourceMap class.
 24.1076    /// \relates SourceMap
 24.1077 -  template <typename Digraph>
 24.1078 -  inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
 24.1079 -    return SourceMap<Digraph>(digraph);
 24.1080 +  template <typename GR>
 24.1081 +  inline SourceMap<GR> sourceMap(const GR& graph) {
 24.1082 +    return SourceMap<GR>(graph);
 24.1083    }
 24.1084  
 24.1085 -  /// \brief Returns the target of the given arc.
 24.1086 +  /// \brief Map of the target nodes of arcs in a digraph.
 24.1087    ///
 24.1088 -  /// The TargetMap gives back the target Node of the given arc.
 24.1089 +  /// TargetMap provides access for the target node of each arc in a digraph,
 24.1090 +  /// which is returned by the \c target() function of the digraph.
 24.1091 +  /// \tparam GR The digraph type.
 24.1092    /// \see SourceMap
 24.1093 -  template <typename Digraph>
 24.1094 +  template <typename GR>
 24.1095    class TargetMap {
 24.1096    public:
 24.1097  
 24.1098 -    typedef typename Digraph::Node Value;
 24.1099 -    typedef typename Digraph::Arc Key;
 24.1100 +    ///\e
 24.1101 +    typedef typename GR::Arc Key;
 24.1102 +    ///\e
 24.1103 +    typedef typename GR::Node Value;
 24.1104  
 24.1105      /// \brief Constructor
 24.1106      ///
 24.1107 -    /// Constructor
 24.1108 +    /// Constructor.
 24.1109      /// \param digraph The digraph that the map belongs to.
 24.1110 -    explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
 24.1111 -
 24.1112 -    /// \brief The subscript operator.
 24.1113 +    explicit TargetMap(const GR& digraph) : _graph(digraph) {}
 24.1114 +
 24.1115 +    /// \brief Returns the target node of the given arc.
 24.1116      ///
 24.1117 -    /// The subscript operator.
 24.1118 -    /// \param e The arc
 24.1119 -    /// \return The target of the arc
 24.1120 +    /// Returns the target node of the given arc.
 24.1121      Value operator[](const Key& e) const {
 24.1122 -      return _digraph.target(e);
 24.1123 +      return _graph.target(e);
 24.1124      }
 24.1125  
 24.1126    private:
 24.1127 -    const Digraph& _digraph;
 24.1128 +    const GR& _graph;
 24.1129    };
 24.1130  
 24.1131    /// \brief Returns a \c TargetMap class.
 24.1132    ///
 24.1133    /// This function just returns a \c TargetMap class.
 24.1134    /// \relates TargetMap
 24.1135 -  template <typename Digraph>
 24.1136 -  inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
 24.1137 -    return TargetMap<Digraph>(digraph);
 24.1138 +  template <typename GR>
 24.1139 +  inline TargetMap<GR> targetMap(const GR& graph) {
 24.1140 +    return TargetMap<GR>(graph);
 24.1141    }
 24.1142  
 24.1143 -  /// \brief Returns the "forward" directed arc view of an edge.
 24.1144 +  /// \brief Map of the "forward" directed arc view of edges in a graph.
 24.1145    ///
 24.1146 -  /// Returns the "forward" directed arc view of an edge.
 24.1147 +  /// ForwardMap provides access for the "forward" directed arc view of
 24.1148 +  /// each edge in a graph, which is returned by the \c direct() function
 24.1149 +  /// of the graph with \c true parameter.
 24.1150 +  /// \tparam GR The graph type.
 24.1151    /// \see BackwardMap
 24.1152 -  template <typename Graph>
 24.1153 +  template <typename GR>
 24.1154    class ForwardMap {
 24.1155    public:
 24.1156  
 24.1157 -    typedef typename Graph::Arc Value;
 24.1158 -    typedef typename Graph::Edge Key;
 24.1159 +    typedef typename GR::Arc Value;
 24.1160 +    typedef typename GR::Edge Key;
 24.1161  
 24.1162      /// \brief Constructor
 24.1163      ///
 24.1164 -    /// Constructor
 24.1165 +    /// Constructor.
 24.1166      /// \param graph The graph that the map belongs to.
 24.1167 -    explicit ForwardMap(const Graph& graph) : _graph(graph) {}
 24.1168 -
 24.1169 -    /// \brief The subscript operator.
 24.1170 +    explicit ForwardMap(const GR& graph) : _graph(graph) {}
 24.1171 +
 24.1172 +    /// \brief Returns the "forward" directed arc view of the given edge.
 24.1173      ///
 24.1174 -    /// The subscript operator.
 24.1175 -    /// \param key An edge
 24.1176 -    /// \return The "forward" directed arc view of edge
 24.1177 +    /// Returns the "forward" directed arc view of the given edge.
 24.1178      Value operator[](const Key& key) const {
 24.1179        return _graph.direct(key, true);
 24.1180      }
 24.1181  
 24.1182    private:
 24.1183 -    const Graph& _graph;
 24.1184 +    const GR& _graph;
 24.1185    };
 24.1186  
 24.1187    /// \brief Returns a \c ForwardMap class.
 24.1188    ///
 24.1189    /// This function just returns an \c ForwardMap class.
 24.1190    /// \relates ForwardMap
 24.1191 -  template <typename Graph>
 24.1192 -  inline ForwardMap<Graph> forwardMap(const Graph& graph) {
 24.1193 -    return ForwardMap<Graph>(graph);
 24.1194 +  template <typename GR>
 24.1195 +  inline ForwardMap<GR> forwardMap(const GR& graph) {
 24.1196 +    return ForwardMap<GR>(graph);
 24.1197    }
 24.1198  
 24.1199 -  /// \brief Returns the "backward" directed arc view of an edge.
 24.1200 +  /// \brief Map of the "backward" directed arc view of edges in a graph.
 24.1201    ///
 24.1202 -  /// Returns the "backward" directed arc view of an edge.
 24.1203 +  /// BackwardMap provides access for the "backward" directed arc view of
 24.1204 +  /// each edge in a graph, which is returned by the \c direct() function
 24.1205 +  /// of the graph with \c false parameter.
 24.1206 +  /// \tparam GR The graph type.
 24.1207    /// \see ForwardMap
 24.1208 -  template <typename Graph>
 24.1209 +  template <typename GR>
 24.1210    class BackwardMap {
 24.1211    public:
 24.1212  
 24.1213 -    typedef typename Graph::Arc Value;
 24.1214 -    typedef typename Graph::Edge Key;
 24.1215 +    typedef typename GR::Arc Value;
 24.1216 +    typedef typename GR::Edge Key;
 24.1217  
 24.1218      /// \brief Constructor
 24.1219      ///
 24.1220 -    /// Constructor
 24.1221 +    /// Constructor.
 24.1222      /// \param graph The graph that the map belongs to.
 24.1223 -    explicit BackwardMap(const Graph& graph) : _graph(graph) {}
 24.1224 -
 24.1225 -    /// \brief The subscript operator.
 24.1226 +    explicit BackwardMap(const GR& graph) : _graph(graph) {}
 24.1227 +
 24.1228 +    /// \brief Returns the "backward" directed arc view of the given edge.
 24.1229      ///
 24.1230 -    /// The subscript operator.
 24.1231 -    /// \param key An edge
 24.1232 -    /// \return The "backward" directed arc view of edge
 24.1233 +    /// Returns the "backward" directed arc view of the given edge.
 24.1234      Value operator[](const Key& key) const {
 24.1235        return _graph.direct(key, false);
 24.1236      }
 24.1237  
 24.1238    private:
 24.1239 -    const Graph& _graph;
 24.1240 +    const GR& _graph;
 24.1241    };
 24.1242  
 24.1243    /// \brief Returns a \c BackwardMap class
 24.1244  
 24.1245    /// This function just returns a \c BackwardMap class.
 24.1246    /// \relates BackwardMap
 24.1247 -  template <typename Graph>
 24.1248 -  inline BackwardMap<Graph> backwardMap(const Graph& graph) {
 24.1249 -    return BackwardMap<Graph>(graph);
 24.1250 +  template <typename GR>
 24.1251 +  inline BackwardMap<GR> backwardMap(const GR& graph) {
 24.1252 +    return BackwardMap<GR>(graph);
 24.1253    }
 24.1254  
 24.1255 -  /// \brief Potential difference map
 24.1256 -  ///
 24.1257 -  /// If there is an potential map on the nodes then we
 24.1258 -  /// can get an arc map as we get the substraction of the
 24.1259 -  /// values of the target and source.
 24.1260 -  template <typename Digraph, typename NodeMap>
 24.1261 -  class PotentialDifferenceMap {
 24.1262 -  public:
 24.1263 -    typedef typename Digraph::Arc Key;
 24.1264 -    typedef typename NodeMap::Value Value;
 24.1265 -
 24.1266 -    /// \brief Constructor
 24.1267 -    ///
 24.1268 -    /// Contructor of the map
 24.1269 -    explicit PotentialDifferenceMap(const Digraph& digraph,
 24.1270 -                                    const NodeMap& potential)
 24.1271 -      : _digraph(digraph), _potential(potential) {}
 24.1272 -
 24.1273 -    /// \brief Const subscription operator
 24.1274 -    ///
 24.1275 -    /// Const subscription operator
 24.1276 -    Value operator[](const Key& arc) const {
 24.1277 -      return _potential[_digraph.target(arc)] -
 24.1278 -        _potential[_digraph.source(arc)];
 24.1279 -    }
 24.1280 -
 24.1281 -  private:
 24.1282 -    const Digraph& _digraph;
 24.1283 -    const NodeMap& _potential;
 24.1284 -  };
 24.1285 -
 24.1286 -  /// \brief Returns a PotentialDifferenceMap.
 24.1287 -  ///
 24.1288 -  /// This function just returns a PotentialDifferenceMap.
 24.1289 -  /// \relates PotentialDifferenceMap
 24.1290 -  template <typename Digraph, typename NodeMap>
 24.1291 -  PotentialDifferenceMap<Digraph, NodeMap>
 24.1292 -  potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
 24.1293 -    return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
 24.1294 -  }
 24.1295 -
 24.1296 -  /// \brief Map of the node in-degrees.
 24.1297 +  /// \brief Map of the in-degrees of nodes in a digraph.
 24.1298    ///
 24.1299    /// This map returns the in-degree of a node. Once it is constructed,
 24.1300 -  /// the degrees are stored in a standard NodeMap, so each query is done
 24.1301 +  /// the degrees are stored in a standard \c NodeMap, so each query is done
 24.1302    /// in constant time. On the other hand, the values are updated automatically
 24.1303    /// whenever the digraph changes.
 24.1304    ///
 24.1305 -  /// \warning Besides addNode() and addArc(), a digraph structure may provide
 24.1306 -  /// alternative ways to modify the digraph. The correct behavior of InDegMap
 24.1307 -  /// is not guarantied if these additional features are used. For example
 24.1308 -  /// the functions \ref ListDigraph::changeSource() "changeSource()",
 24.1309 +  /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
 24.1310 +  /// may provide alternative ways to modify the digraph.
 24.1311 +  /// The correct behavior of InDegMap is not guarantied if these additional
 24.1312 +  /// features are used. For example the functions
 24.1313 +  /// \ref ListDigraph::changeSource() "changeSource()",
 24.1314    /// \ref ListDigraph::changeTarget() "changeTarget()" and
 24.1315    /// \ref ListDigraph::reverseArc() "reverseArc()"
 24.1316    /// of \ref ListDigraph will \e not update the degree values correctly.
 24.1317    ///
 24.1318    /// \sa OutDegMap
 24.1319 -
 24.1320 -  template <typename _Digraph>
 24.1321 +  template <typename GR>
 24.1322    class InDegMap
 24.1323 -    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
 24.1324 +    : protected ItemSetTraits<GR, typename GR::Arc>
 24.1325        ::ItemNotifier::ObserverBase {
 24.1326  
 24.1327    public:
 24.1328 -
 24.1329 -    typedef _Digraph Digraph;
 24.1330 +    
 24.1331 +    /// The digraph type
 24.1332 +    typedef GR Digraph;
 24.1333 +    /// The key type
 24.1334 +    typedef typename Digraph::Node Key;
 24.1335 +    /// The value type
 24.1336      typedef int Value;
 24.1337 -    typedef typename Digraph::Node Key;
 24.1338  
 24.1339      typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
 24.1340      ::ItemNotifier::ObserverBase Parent;
 24.1341 @@ -2523,9 +2542,9 @@
 24.1342  
 24.1343      /// \brief Constructor.
 24.1344      ///
 24.1345 -    /// Constructor for creating in-degree map.
 24.1346 -    explicit InDegMap(const Digraph& digraph)
 24.1347 -      : _digraph(digraph), _deg(digraph) {
 24.1348 +    /// Constructor for creating an in-degree map.
 24.1349 +    explicit InDegMap(const Digraph& graph)
 24.1350 +      : _digraph(graph), _deg(graph) {
 24.1351        Parent::attach(_digraph.notifier(typename Digraph::Arc()));
 24.1352  
 24.1353        for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
 24.1354 @@ -2533,6 +2552,8 @@
 24.1355        }
 24.1356      }
 24.1357  
 24.1358 +    /// \brief Gives back the in-degree of a Node.
 24.1359 +    ///
 24.1360      /// Gives back the in-degree of a Node.
 24.1361      int operator[](const Key& key) const {
 24.1362        return _deg[key];
 24.1363 @@ -2579,33 +2600,36 @@
 24.1364      AutoNodeMap _deg;
 24.1365    };
 24.1366  
 24.1367 -  /// \brief Map of the node out-degrees.
 24.1368 +  /// \brief Map of the out-degrees of nodes in a digraph.
 24.1369    ///
 24.1370    /// This map returns the out-degree of a node. Once it is constructed,
 24.1371 -  /// the degrees are stored in a standard NodeMap, so each query is done
 24.1372 +  /// the degrees are stored in a standard \c NodeMap, so each query is done
 24.1373    /// in constant time. On the other hand, the values are updated automatically
 24.1374    /// whenever the digraph changes.
 24.1375    ///
 24.1376 -  /// \warning Besides addNode() and addArc(), a digraph structure may provide
 24.1377 -  /// alternative ways to modify the digraph. The correct behavior of OutDegMap
 24.1378 -  /// is not guarantied if these additional features are used. For example
 24.1379 -  /// the functions \ref ListDigraph::changeSource() "changeSource()",
 24.1380 +  /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
 24.1381 +  /// may provide alternative ways to modify the digraph.
 24.1382 +  /// The correct behavior of OutDegMap is not guarantied if these additional
 24.1383 +  /// features are used. For example the functions
 24.1384 +  /// \ref ListDigraph::changeSource() "changeSource()",
 24.1385    /// \ref ListDigraph::changeTarget() "changeTarget()" and
 24.1386    /// \ref ListDigraph::reverseArc() "reverseArc()"
 24.1387    /// of \ref ListDigraph will \e not update the degree values correctly.
 24.1388    ///
 24.1389    /// \sa InDegMap
 24.1390 -
 24.1391 -  template <typename _Digraph>
 24.1392 +  template <typename GR>
 24.1393    class OutDegMap
 24.1394 -    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
 24.1395 +    : protected ItemSetTraits<GR, typename GR::Arc>
 24.1396        ::ItemNotifier::ObserverBase {
 24.1397  
 24.1398    public:
 24.1399  
 24.1400 -    typedef _Digraph Digraph;
 24.1401 +    /// The digraph type
 24.1402 +    typedef GR Digraph;
 24.1403 +    /// The key type
 24.1404 +    typedef typename Digraph::Node Key;
 24.1405 +    /// The value type
 24.1406      typedef int Value;
 24.1407 -    typedef typename Digraph::Node Key;
 24.1408  
 24.1409      typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
 24.1410      ::ItemNotifier::ObserverBase Parent;
 24.1411 @@ -2645,9 +2669,9 @@
 24.1412  
 24.1413      /// \brief Constructor.
 24.1414      ///
 24.1415 -    /// Constructor for creating out-degree map.
 24.1416 -    explicit OutDegMap(const Digraph& digraph)
 24.1417 -      : _digraph(digraph), _deg(digraph) {
 24.1418 +    /// Constructor for creating an out-degree map.
 24.1419 +    explicit OutDegMap(const Digraph& graph)
 24.1420 +      : _digraph(graph), _deg(graph) {
 24.1421        Parent::attach(_digraph.notifier(typename Digraph::Arc()));
 24.1422  
 24.1423        for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
 24.1424 @@ -2655,6 +2679,8 @@
 24.1425        }
 24.1426      }
 24.1427  
 24.1428 +    /// \brief Gives back the out-degree of a Node.
 24.1429 +    ///
 24.1430      /// Gives back the out-degree of a Node.
 24.1431      int operator[](const Key& key) const {
 24.1432        return _deg[key];
 24.1433 @@ -2701,6 +2727,56 @@
 24.1434      AutoNodeMap _deg;
 24.1435    };
 24.1436  
 24.1437 +  /// \brief Potential difference map
 24.1438 +  ///
 24.1439 +  /// PotentialMap returns the difference between the potentials of the
 24.1440 +  /// source and target nodes of each arc in a digraph, i.e. it returns
 24.1441 +  /// \code
 24.1442 +  ///   potential[gr.target(arc)] - potential[gr.source(arc)].
 24.1443 +  /// \endcode
 24.1444 +  /// \tparam GR The digraph type.
 24.1445 +  /// \tparam POT A node map storing the potentials.
 24.1446 +  template <typename GR, typename POT>
 24.1447 +  class PotentialDifferenceMap {
 24.1448 +  public:
 24.1449 +    /// Key type
 24.1450 +    typedef typename GR::Arc Key;
 24.1451 +    /// Value type
 24.1452 +    typedef typename POT::Value Value;
 24.1453 +
 24.1454 +    /// \brief Constructor
 24.1455 +    ///
 24.1456 +    /// Contructor of the map.
 24.1457 +    explicit PotentialDifferenceMap(const GR& gr,
 24.1458 +                                    const POT& potential)
 24.1459 +      : _digraph(gr), _potential(potential) {}
 24.1460 +
 24.1461 +    /// \brief Returns the potential difference for the given arc.
 24.1462 +    ///
 24.1463 +    /// Returns the potential difference for the given arc, i.e.
 24.1464 +    /// \code
 24.1465 +    ///   potential[gr.target(arc)] - potential[gr.source(arc)].
 24.1466 +    /// \endcode
 24.1467 +    Value operator[](const Key& arc) const {
 24.1468 +      return _potential[_digraph.target(arc)] -
 24.1469 +        _potential[_digraph.source(arc)];
 24.1470 +    }
 24.1471 +
 24.1472 +  private:
 24.1473 +    const GR& _digraph;
 24.1474 +    const POT& _potential;
 24.1475 +  };
 24.1476 +
 24.1477 +  /// \brief Returns a PotentialDifferenceMap.
 24.1478 +  ///
 24.1479 +  /// This function just returns a PotentialDifferenceMap.
 24.1480 +  /// \relates PotentialDifferenceMap
 24.1481 +  template <typename GR, typename POT>
 24.1482 +  PotentialDifferenceMap<GR, POT>
 24.1483 +  potentialDifferenceMap(const GR& gr, const POT& potential) {
 24.1484 +    return PotentialDifferenceMap<GR, POT>(gr, potential);
 24.1485 +  }
 24.1486 +
 24.1487    /// @}
 24.1488  }
 24.1489  
    25.1 --- a/lemon/max_matching.h	Thu Mar 05 10:13:20 2009 +0000
    25.2 +++ b/lemon/max_matching.h	Sun Mar 29 23:08:20 2009 +0200
    25.3 @@ -55,12 +55,12 @@
    25.4    /// tight. This decomposition can be attained by calling \c
    25.5    /// decomposition() after running the algorithm.
    25.6    ///
    25.7 -  /// \param _Graph The graph type the algorithm runs on.
    25.8 -  template <typename _Graph>
    25.9 +  /// \param GR The graph type the algorithm runs on.
   25.10 +  template <typename GR>
   25.11    class MaxMatching {
   25.12    public:
   25.13  
   25.14 -    typedef _Graph Graph;
   25.15 +    typedef GR Graph;
   25.16      typedef typename Graph::template NodeMap<typename Graph::Arc>
   25.17      MatchingMap;
   25.18  
   25.19 @@ -463,7 +463,7 @@
   25.20      /// Initialize the matching from a \c bool valued \c Edge map. This
   25.21      /// map must have the property that there are no two incident edges
   25.22      /// with true value, ie. it contains a matching.
   25.23 -    /// \return %True if the map contains a matching.
   25.24 +    /// \return \c true if the map contains a matching.
   25.25      template <typename MatchingMap>
   25.26      bool matchingInit(const MatchingMap& matching) {
   25.27        createStructures();
   25.28 @@ -613,7 +613,7 @@
   25.29    /// This class provides an efficient implementation of Edmond's
   25.30    /// maximum weighted matching algorithm. The implementation is based
   25.31    /// on extensive use of priority queues and provides
   25.32 -  /// \f$O(nm\log(n))\f$ time complexity.
   25.33 +  /// \f$O(nm\log n)\f$ time complexity.
   25.34    ///
   25.35    /// The maximum weighted matching problem is to find undirected
   25.36    /// edges in the graph with maximum overall weight and no two of
   25.37 @@ -647,13 +647,16 @@
   25.38    /// "BlossomIt" nested class, which is able to iterate on the nodes
   25.39    /// of a blossom. If the value type is integral then the dual
   25.40    /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4".
   25.41 -  template <typename _Graph,
   25.42 -            typename _WeightMap = typename _Graph::template EdgeMap<int> >
   25.43 +  template <typename GR,
   25.44 +            typename WM = typename GR::template EdgeMap<int> >
   25.45    class MaxWeightedMatching {
   25.46    public:
   25.47  
   25.48 -    typedef _Graph Graph;
   25.49 -    typedef _WeightMap WeightMap;
   25.50 +    ///\e
   25.51 +    typedef GR Graph;
   25.52 +    ///\e
   25.53 +    typedef WM WeightMap;
   25.54 +    ///\e
   25.55      typedef typename WeightMap::Value Value;
   25.56  
   25.57      /// \brief Scaling factor for dual solution
   25.58 @@ -1957,7 +1960,7 @@
   25.59    /// This class provides an efficient implementation of Edmond's
   25.60    /// maximum weighted perfect matching algorithm. The implementation
   25.61    /// is based on extensive use of priority queues and provides
   25.62 -  /// \f$O(nm\log(n))\f$ time complexity.
   25.63 +  /// \f$O(nm\log n)\f$ time complexity.
   25.64    ///
   25.65    /// The maximum weighted matching problem is to find undirected
   25.66    /// edges in the graph with maximum overall weight and no two of
   25.67 @@ -1990,13 +1993,13 @@
   25.68    /// "BlossomIt" nested class which is able to iterate on the nodes
   25.69    /// of a blossom. If the value type is integral then the dual
   25.70    /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4".
   25.71 -  template <typename _Graph,
   25.72 -            typename _WeightMap = typename _Graph::template EdgeMap<int> >
   25.73 +  template <typename GR,
   25.74 +            typename WM = typename GR::template EdgeMap<int> >
   25.75    class MaxWeightedPerfectMatching {
   25.76    public:
   25.77  
   25.78 -    typedef _Graph Graph;
   25.79 -    typedef _WeightMap WeightMap;
   25.80 +    typedef GR Graph;
   25.81 +    typedef WM WeightMap;
   25.82      typedef typename WeightMap::Value Value;
   25.83  
   25.84      /// \brief Scaling factor for dual solution
    26.1 --- a/lemon/min_cost_arborescence.h	Thu Mar 05 10:13:20 2009 +0000
    26.2 +++ b/lemon/min_cost_arborescence.h	Sun Mar 29 23:08:20 2009 +0200
    26.3 @@ -35,19 +35,19 @@
    26.4    /// \brief Default traits class for MinCostArborescence class.
    26.5    ///
    26.6    /// Default traits class for MinCostArborescence class.
    26.7 -  /// \param _Digraph Digraph type.
    26.8 -  /// \param _CostMap Type of cost map.
    26.9 -  template <class _Digraph, class _CostMap>
   26.10 +  /// \param GR Digraph type.
   26.11 +  /// \param CM Type of cost map.
   26.12 +  template <class GR, class CM>
   26.13    struct MinCostArborescenceDefaultTraits{
   26.14  
   26.15      /// \brief The digraph type the algorithm runs on.
   26.16 -    typedef _Digraph Digraph;
   26.17 +    typedef GR Digraph;
   26.18  
   26.19      /// \brief The type of the map that stores the arc costs.
   26.20      ///
   26.21      /// The type of the map that stores the arc costs.
   26.22      /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
   26.23 -    typedef _CostMap CostMap;
   26.24 +    typedef CM CostMap;
   26.25  
   26.26      /// \brief The value type of the costs.
   26.27      ///
   26.28 @@ -63,25 +63,25 @@
   26.29      /// arc. After it will set all arborescence arcs once.
   26.30      typedef typename Digraph::template ArcMap<bool> ArborescenceMap;
   26.31  
   26.32 -    /// \brief Instantiates a ArborescenceMap.
   26.33 +    /// \brief Instantiates a \c ArborescenceMap.
   26.34      ///
   26.35 -    /// This function instantiates a \ref ArborescenceMap.
   26.36 +    /// This function instantiates a \c ArborescenceMap.
   26.37      /// \param digraph is the graph, to which we would like to
   26.38 -    /// calculate the ArborescenceMap.
   26.39 +    /// calculate the \c ArborescenceMap.
   26.40      static ArborescenceMap *createArborescenceMap(const Digraph &digraph){
   26.41        return new ArborescenceMap(digraph);
   26.42      }
   26.43  
   26.44 -    /// \brief The type of the PredMap
   26.45 +    /// \brief The type of the \c PredMap
   26.46      ///
   26.47 -    /// The type of the PredMap. It is a node map with an arc value type.
   26.48 +    /// The type of the \c PredMap. It is a node map with an arc value type.
   26.49      typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
   26.50  
   26.51 -    /// \brief Instantiates a PredMap.
   26.52 +    /// \brief Instantiates a \c PredMap.
   26.53      ///
   26.54 -    /// This function instantiates a \ref PredMap.
   26.55 -    /// \param _digraph is the digraph, to which we would like to define the
   26.56 -    /// PredMap.
   26.57 +    /// This function instantiates a \c PredMap.
   26.58 +    /// \param digraph The digraph to which we would like to define the
   26.59 +    /// \c PredMap.
   26.60      static PredMap *createPredMap(const Digraph &digraph){
   26.61        return new PredMap(digraph);
   26.62      }
   26.63 @@ -98,39 +98,37 @@
   26.64    /// more sources should be given for the algorithm and it will calculate
   26.65    /// the minimum cost subgraph which are union of arborescences with the
   26.66    /// given sources and spans all the nodes which are reachable from the
   26.67 -  /// sources. The time complexity of the algorithm is \f$ O(n^2+e) \f$.
   26.68 +  /// sources. The time complexity of the algorithm is O(n<sup>2</sup>+e).
   26.69    ///
   26.70    /// The algorithm provides also an optimal dual solution, therefore
   26.71    /// the optimality of the solution can be checked.
   26.72    ///
   26.73 -  /// \param _Digraph The digraph type the algorithm runs on. The default value
   26.74 +  /// \param GR The digraph type the algorithm runs on. The default value
   26.75    /// is \ref ListDigraph.
   26.76 -  /// \param _CostMap This read-only ArcMap determines the costs of the
   26.77 +  /// \param CM This read-only ArcMap determines the costs of the
   26.78    /// arcs. It is read once for each arc, so the map may involve in
   26.79    /// relatively time consuming process to compute the arc cost if
   26.80    /// it is necessary. The default map type is \ref
   26.81    /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
   26.82 -  /// \param _Traits Traits class to set various data types used
   26.83 +  /// \param TR Traits class to set various data types used
   26.84    /// by the algorithm. The default traits class is
   26.85    /// \ref MinCostArborescenceDefaultTraits
   26.86 -  /// "MinCostArborescenceDefaultTraits<_Digraph, _CostMap>".  See \ref
   26.87 +  /// "MinCostArborescenceDefaultTraits<GR, CM>".  See \ref
   26.88    /// MinCostArborescenceDefaultTraits for the documentation of a
   26.89    /// MinCostArborescence traits class.
   26.90 -  ///
   26.91 -  /// \author Balazs Dezso
   26.92  #ifndef DOXYGEN
   26.93 -  template <typename _Digraph = ListDigraph,
   26.94 -            typename _CostMap = typename _Digraph::template ArcMap<int>,
   26.95 -            typename _Traits =
   26.96 -            MinCostArborescenceDefaultTraits<_Digraph, _CostMap> >
   26.97 +  template <typename GR = ListDigraph,
   26.98 +            typename CM = typename GR::template ArcMap<int>,
   26.99 +            typename TR =
  26.100 +              MinCostArborescenceDefaultTraits<GR, CM> >
  26.101  #else
  26.102 -  template <typename _Digraph, typename _CostMap, typedef _Traits>
  26.103 +  template <typename GR, typename CM, typedef TR>
  26.104  #endif
  26.105    class MinCostArborescence {
  26.106    public:
  26.107  
  26.108      /// The traits.
  26.109 -    typedef _Traits Traits;
  26.110 +    typedef TR Traits;
  26.111      /// The type of the underlying digraph.
  26.112      typedef typename Traits::Digraph Digraph;
  26.113      /// The type of the map that stores the arc costs.
  26.114 @@ -440,8 +438,8 @@
  26.115  
  26.116      /// \brief Constructor.
  26.117      ///
  26.118 -    /// \param _digraph The digraph the algorithm will run on.
  26.119 -    /// \param _cost The cost map used by the algorithm.
  26.120 +    /// \param digraph The digraph the algorithm will run on.
  26.121 +    /// \param cost The cost map used by the algorithm.
  26.122      MinCostArborescence(const Digraph& digraph, const CostMap& cost)
  26.123        : _digraph(&digraph), _cost(&cost), _pred(0), local_pred(false),
  26.124          _arborescence(0), local_arborescence(false),
  26.125 @@ -456,7 +454,7 @@
  26.126      /// \brief Sets the arborescence map.
  26.127      ///
  26.128      /// Sets the arborescence map.
  26.129 -    /// \return \c (*this)
  26.130 +    /// \return <tt>(*this)</tt>
  26.131      MinCostArborescence& arborescenceMap(ArborescenceMap& m) {
  26.132        if (local_arborescence) {
  26.133          delete _arborescence;
  26.134 @@ -469,7 +467,7 @@
  26.135      /// \brief Sets the arborescence map.
  26.136      ///
  26.137      /// Sets the arborescence map.
  26.138 -    /// \return \c (*this)
  26.139 +    /// \return <tt>(*this)</tt>
  26.140      MinCostArborescence& predMap(PredMap& m) {
  26.141        if (local_pred) {
  26.142          delete _pred;
    27.1 --- a/lemon/path.h	Thu Mar 05 10:13:20 2009 +0000
    27.2 +++ b/lemon/path.h	Sun Mar 29 23:08:20 2009 +0200
    27.3 @@ -40,7 +40,7 @@
    27.4    /// \brief A structure for representing directed paths in a digraph.
    27.5    ///
    27.6    /// A structure for representing directed path in a digraph.
    27.7 -  /// \tparam _Digraph The digraph type in which the path is.
    27.8 +  /// \tparam GR The digraph type in which the path is.
    27.9    ///
   27.10    /// In a sense, the path can be treated as a list of arcs. The
   27.11    /// lemon path type stores just this list. As a consequence, it
   27.12 @@ -52,11 +52,11 @@
   27.13    /// insertion and erase is done in O(1) (amortized) time. The
   27.14    /// implementation uses two vectors for storing the front and back
   27.15    /// insertions.
   27.16 -  template <typename _Digraph>
   27.17 +  template <typename GR>
   27.18    class Path {
   27.19    public:
   27.20  
   27.21 -    typedef _Digraph Digraph;
   27.22 +    typedef GR Digraph;
   27.23      typedef typename Digraph::Arc Arc;
   27.24  
   27.25      /// \brief Default constructor
   27.26 @@ -137,7 +137,7 @@
   27.27  
   27.28      /// \brief The nth arc.
   27.29      ///
   27.30 -    /// \pre n is in the [0..length() - 1] range
   27.31 +    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
   27.32      const Arc& nth(int n) const {
   27.33        return n < int(head.size()) ? *(head.rbegin() + n) :
   27.34          *(tail.begin() + (n - head.size()));
   27.35 @@ -145,7 +145,7 @@
   27.36  
   27.37      /// \brief Initialize arc iterator to point to the nth arc
   27.38      ///
   27.39 -    /// \pre n is in the [0..length() - 1] range
   27.40 +    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
   27.41      ArcIt nthIt(int n) const {
   27.42        return ArcIt(*this, n);
   27.43      }
   27.44 @@ -228,7 +228,7 @@
   27.45    /// \brief A structure for representing directed paths in a digraph.
   27.46    ///
   27.47    /// A structure for representing directed path in a digraph.
   27.48 -  /// \tparam _Digraph The digraph type in which the path is.
   27.49 +  /// \tparam GR The digraph type in which the path is.
   27.50    ///
   27.51    /// In a sense, the path can be treated as a list of arcs. The
   27.52    /// lemon path type stores just this list. As a consequence it
   27.53 @@ -240,11 +240,11 @@
   27.54    /// erasure is amortized O(1) time. This implementation is faster
   27.55    /// then the \c Path type because it use just one vector for the
   27.56    /// arcs.
   27.57 -  template <typename _Digraph>
   27.58 +  template <typename GR>
   27.59    class SimplePath {
   27.60    public:
   27.61  
   27.62 -    typedef _Digraph Digraph;
   27.63 +    typedef GR Digraph;
   27.64      typedef typename Digraph::Arc Arc;
   27.65  
   27.66      /// \brief Default constructor
   27.67 @@ -329,7 +329,7 @@
   27.68  
   27.69      /// \brief The nth arc.
   27.70      ///
   27.71 -    /// \pre n is in the [0..length() - 1] range
   27.72 +    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
   27.73      const Arc& nth(int n) const {
   27.74        return data[n];
   27.75      }
   27.76 @@ -392,7 +392,7 @@
   27.77    /// \brief A structure for representing directed paths in a digraph.
   27.78    ///
   27.79    /// A structure for representing directed path in a digraph.
   27.80 -  /// \tparam _Digraph The digraph type in which the path is.
   27.81 +  /// \tparam GR The digraph type in which the path is.
   27.82    ///
   27.83    /// In a sense, the path can be treated as a list of arcs. The
   27.84    /// lemon path type stores just this list. As a consequence it
   27.85 @@ -404,11 +404,11 @@
   27.86    /// of the arc in the path. The length can be computed in O(n)
   27.87    /// time. The front and back insertion and erasure is O(1) time
   27.88    /// and it can be splited and spliced in O(1) time.
   27.89 -  template <typename _Digraph>
   27.90 +  template <typename GR>
   27.91    class ListPath {
   27.92    public:
   27.93  
   27.94 -    typedef _Digraph Digraph;
   27.95 +    typedef GR Digraph;
   27.96      typedef typename Digraph::Arc Arc;
   27.97  
   27.98    protected:
   27.99 @@ -507,7 +507,7 @@
  27.100      /// \brief The nth arc.
  27.101      ///
  27.102      /// This function looks for the nth arc in O(n) time.
  27.103 -    /// \pre n is in the [0..length() - 1] range
  27.104 +    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
  27.105      const Arc& nth(int n) const {
  27.106        Node *node = first;
  27.107        for (int i = 0; i < n; ++i) {
  27.108 @@ -732,7 +732,7 @@
  27.109    /// \brief A structure for representing directed paths in a digraph.
  27.110    ///
  27.111    /// A structure for representing directed path in a digraph.
  27.112 -  /// \tparam _Digraph The digraph type in which the path is.
  27.113 +  /// \tparam GR The digraph type in which the path is.
  27.114    ///
  27.115    /// In a sense, the path can be treated as a list of arcs. The
  27.116    /// lemon path type stores just this list. As a consequence it
  27.117 @@ -746,11 +746,11 @@
  27.118    /// Being the the most memory efficient path type in LEMON,
  27.119    /// it is intented to be
  27.120    /// used when you want to store a large number of paths.
  27.121 -  template <typename _Digraph>
  27.122 +  template <typename GR>
  27.123    class StaticPath {
  27.124    public:
  27.125  
  27.126 -    typedef _Digraph Digraph;
  27.127 +    typedef GR Digraph;
  27.128      typedef typename Digraph::Arc Arc;
  27.129  
  27.130      /// \brief Default constructor
  27.131 @@ -833,7 +833,7 @@
  27.132  
  27.133      /// \brief The nth arc.
  27.134      ///
  27.135 -    /// \pre n is in the [0..length() - 1] range
  27.136 +    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
  27.137      const Arc& nth(int n) const {
  27.138        return arcs[n];
  27.139      }
    28.1 --- a/lemon/preflow.h	Thu Mar 05 10:13:20 2009 +0000
    28.2 +++ b/lemon/preflow.h	Sun Mar 29 23:08:20 2009 +0200
    28.3 @@ -32,8 +32,8 @@
    28.4    ///
    28.5    /// Default traits class of Preflow class.
    28.6    /// \tparam GR Digraph type.
    28.7 -  /// \tparam CM Capacity map type.
    28.8 -  template <typename GR, typename CM>
    28.9 +  /// \tparam CAP Capacity map type.
   28.10 +  template <typename GR, typename CAP>
   28.11    struct PreflowDefaultTraits {
   28.12  
   28.13      /// \brief The type of the digraph the algorithm runs on.
   28.14 @@ -43,7 +43,7 @@
   28.15      ///
   28.16      /// The type of the map that stores the arc capacities.
   28.17      /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
   28.18 -    typedef CM CapacityMap;
   28.19 +    typedef CAP CapacityMap;
   28.20  
   28.21      /// \brief The type of the flow values.
   28.22      typedef typename CapacityMap::Value Value;
   28.23 @@ -94,8 +94,9 @@
   28.24    /// \brief %Preflow algorithm class.
   28.25    ///
   28.26    /// This class provides an implementation of Goldberg-Tarjan's \e preflow
   28.27 -  /// \e push-relabel algorithm producing a flow of maximum value in a
   28.28 -  /// digraph. The preflow algorithms are the fastest known maximum
   28.29 +  /// \e push-relabel algorithm producing a \ref max_flow
   28.30 +  /// "flow of maximum value" in a digraph.
   28.31 +  /// The preflow algorithms are the fastest known maximum
   28.32    /// flow algorithms. The current implementation use a mixture of the
   28.33    /// \e "highest label" and the \e "bound decrease" heuristics.
   28.34    /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
   28.35 @@ -105,14 +106,14 @@
   28.36    /// second phase constructs a feasible maximum flow on each arc.
   28.37    ///
   28.38    /// \tparam GR The type of the digraph the algorithm runs on.
   28.39 -  /// \tparam CM The type of the capacity map. The default map
   28.40 +  /// \tparam CAP The type of the capacity map. The default map
   28.41    /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
   28.42  #ifdef DOXYGEN
   28.43 -  template <typename GR, typename CM, typename TR>
   28.44 +  template <typename GR, typename CAP, typename TR>
   28.45  #else
   28.46    template <typename GR,
   28.47 -            typename CM = typename GR::template ArcMap<int>,
   28.48 -            typename TR = PreflowDefaultTraits<GR, CM> >
   28.49 +            typename CAP = typename GR::template ArcMap<int>,
   28.50 +            typename TR = PreflowDefaultTraits<GR, CAP> >
   28.51  #endif
   28.52    class Preflow {
   28.53    public:
   28.54 @@ -194,9 +195,9 @@
   28.55  
   28.56      ///@{
   28.57  
   28.58 -    template <typename _FlowMap>
   28.59 +    template <typename T>
   28.60      struct SetFlowMapTraits : public Traits {
   28.61 -      typedef _FlowMap FlowMap;
   28.62 +      typedef T FlowMap;
   28.63        static FlowMap *createFlowMap(const Digraph&) {
   28.64          LEMON_ASSERT(false, "FlowMap is not initialized");
   28.65          return 0; // ignore warnings
   28.66 @@ -208,16 +209,16 @@
   28.67      ///
   28.68      /// \ref named-templ-param "Named parameter" for setting FlowMap
   28.69      /// type.
   28.70 -    template <typename _FlowMap>
   28.71 +    template <typename T>
   28.72      struct SetFlowMap
   28.73 -      : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<_FlowMap> > {
   28.74 +      : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<T> > {
   28.75        typedef Preflow<Digraph, CapacityMap,
   28.76 -                      SetFlowMapTraits<_FlowMap> > Create;
   28.77 +                      SetFlowMapTraits<T> > Create;
   28.78      };
   28.79  
   28.80 -    template <typename _Elevator>
   28.81 +    template <typename T>
   28.82      struct SetElevatorTraits : public Traits {
   28.83 -      typedef _Elevator Elevator;
   28.84 +      typedef T Elevator;
   28.85        static Elevator *createElevator(const Digraph&, int) {
   28.86          LEMON_ASSERT(false, "Elevator is not initialized");
   28.87          return 0; // ignore warnings
   28.88 @@ -233,16 +234,16 @@
   28.89      /// \ref elevator(Elevator&) "elevator()" function before calling
   28.90      /// \ref run() or \ref init().
   28.91      /// \sa SetStandardElevator
   28.92 -    template <typename _Elevator>
   28.93 +    template <typename T>
   28.94      struct SetElevator
   28.95 -      : public Preflow<Digraph, CapacityMap, SetElevatorTraits<_Elevator> > {
   28.96 +      : public Preflow<Digraph, CapacityMap, SetElevatorTraits<T> > {
   28.97        typedef Preflow<Digraph, CapacityMap,
   28.98 -                      SetElevatorTraits<_Elevator> > Create;
   28.99 +                      SetElevatorTraits<T> > Create;
  28.100      };
  28.101  
  28.102 -    template <typename _Elevator>
  28.103 +    template <typename T>
  28.104      struct SetStandardElevatorTraits : public Traits {
  28.105 -      typedef _Elevator Elevator;
  28.106 +      typedef T Elevator;
  28.107        static Elevator *createElevator(const Digraph& digraph, int max_level) {
  28.108          return new Elevator(digraph, max_level);
  28.109        }
  28.110 @@ -260,12 +261,12 @@
  28.111      /// algorithm with the \ref elevator(Elevator&) "elevator()" function
  28.112      /// before calling \ref run() or \ref init().
  28.113      /// \sa SetElevator
  28.114 -    template <typename _Elevator>
  28.115 +    template <typename T>
  28.116      struct SetStandardElevator
  28.117        : public Preflow<Digraph, CapacityMap,
  28.118 -                       SetStandardElevatorTraits<_Elevator> > {
  28.119 +                       SetStandardElevatorTraits<T> > {
  28.120        typedef Preflow<Digraph, CapacityMap,
  28.121 -                      SetStandardElevatorTraits<_Elevator> > Create;
  28.122 +                      SetStandardElevatorTraits<T> > Create;
  28.123      };
  28.124  
  28.125      /// @}
  28.126 @@ -946,7 +947,7 @@
  28.127      /// could be slightly different if inexact computation is used.
  28.128      ///
  28.129      /// \note This function calls \ref minCut() for each node, so it runs in
  28.130 -    /// \f$O(n)\f$ time.
  28.131 +    /// O(n) time.
  28.132      ///
  28.133      /// \pre Either \ref run() or \ref init() must be called before
  28.134      /// using this function.
    29.1 --- a/lemon/radix_sort.h	Thu Mar 05 10:13:20 2009 +0000
    29.2 +++ b/lemon/radix_sort.h	Sun Mar 29 23:08:20 2009 +0200
    29.3 @@ -205,11 +205,11 @@
    29.4    /// the identity function instead.
    29.5    ///
    29.6    /// This is a special quick sort algorithm where the pivot
    29.7 -  /// values to split the items are choosen to be \f$ 2^k \f$ for each \c k.
    29.8 -  /// Therefore, the time complexity of the
    29.9 -  /// algorithm is \f$ O(\log(c)n) \f$ and it uses \f$ O(\log(c)) \f$,
   29.10 -  /// additional space, where \c c is the maximal value and \c n is the
   29.11 -  /// number of the items in the container.
   29.12 +  /// values to split the items are choosen to be 2<sup>k</sup>
   29.13 +  /// for each \c k.
   29.14 +  /// Therefore, the time complexity of the algorithm is O(log(c)*n) and
   29.15 +  /// it uses O(log(c)) additional space, where \c c is the maximal value
   29.16 +  /// and \c n is the number of the items in the container.
   29.17    ///
   29.18    /// \param first The begin of the given range.
   29.19    /// \param last The end of the given range.
   29.20 @@ -430,10 +430,10 @@
   29.21    /// bytes of the integer number. The algorithm sorts the items
   29.22    /// byte-by-byte. First, it counts how many times a byte value occurs
   29.23    /// in the container, then it copies the corresponding items to
   29.24 -  /// another container in asceding order in \c O(n) time.
   29.25 +  /// another container in asceding order in O(n) time.
   29.26    ///
   29.27 -  /// The time complexity of the algorithm is \f$ O(\log(c)n) \f$ and
   29.28 -  /// it uses \f$ O(n) \f$, additional space, where \c c is the
   29.29 +  /// The time complexity of the algorithm is O(log(c)*n) and
   29.30 +  /// it uses O(n) additional space, where \c c is the
   29.31    /// maximal value and \c n is the number of the items in the
   29.32    /// container.
   29.33    ///
    30.1 --- a/lemon/random.h	Thu Mar 05 10:13:20 2009 +0000
    30.2 +++ b/lemon/random.h	Sun Mar 29 23:08:20 2009 +0200
    30.3 @@ -603,7 +603,7 @@
    30.4      /// By default, this function calls the \c seedFromFile() member
    30.5      /// function with the <tt>/dev/urandom</tt> file. If it does not success,
    30.6      /// it uses the \c seedFromTime().
    30.7 -    /// \return Currently always true.
    30.8 +    /// \return Currently always \c true.
    30.9      bool seed() {
   30.10  #ifndef WIN32
   30.11        if (seedFromFile("/dev/urandom", 0)) return true;
   30.12 @@ -624,7 +624,7 @@
   30.13      /// entropy).
   30.14      /// \param file The source file
   30.15      /// \param offset The offset, from the file read.
   30.16 -    /// \return True when the seeding successes.
   30.17 +    /// \return \c true when the seeding successes.
   30.18  #ifndef WIN32
   30.19      bool seedFromFile(const std::string& file = "/dev/urandom", int offset = 0)
   30.20  #else
   30.21 @@ -645,7 +645,7 @@
   30.22      /// Seding from process id and time. This function uses the
   30.23      /// current process id and the current time for initialize the
   30.24      /// random sequence.
   30.25 -    /// \return Currently always true.
   30.26 +    /// \return Currently always \c true.
   30.27      bool seedFromTime() {
   30.28  #ifndef WIN32
   30.29        timeval tv;
    31.1 --- a/lemon/smart_graph.h	Thu Mar 05 10:13:20 2009 +0000
    31.2 +++ b/lemon/smart_graph.h	Sun Mar 29 23:08:20 2009 +0200
    31.3 @@ -225,15 +225,15 @@
    31.4  
    31.5      ///Add a new node to the digraph.
    31.6  
    31.7 -    /// \return the new node.
    31.8 -    ///
    31.9 +    /// Add a new node to the digraph.
   31.10 +    /// \return The new node.
   31.11      Node addNode() { return Parent::addNode(); }
   31.12  
   31.13      ///Add a new arc to the digraph.
   31.14  
   31.15      ///Add a new arc to the digraph with source node \c s
   31.16      ///and target node \c t.
   31.17 -    ///\return the new arc.
   31.18 +    ///\return The new arc.
   31.19      Arc addArc(const Node& s, const Node& t) {
   31.20        return Parent::addArc(s, t);
   31.21      }
   31.22 @@ -666,15 +666,15 @@
   31.23  
   31.24      ///Add a new node to the graph.
   31.25  
   31.26 -    /// \return the new node.
   31.27 -    ///
   31.28 +    /// Add a new node to the graph.
   31.29 +    /// \return The new node.
   31.30      Node addNode() { return Parent::addNode(); }
   31.31  
   31.32      ///Add a new edge to the graph.
   31.33  
   31.34      ///Add a new edge to the graph with node \c s
   31.35      ///and \c t.
   31.36 -    ///\return the new edge.
   31.37 +    ///\return The new edge.
   31.38      Edge addEdge(const Node& s, const Node& t) {
   31.39        return Parent::addEdge(s, t);
   31.40      }
    32.1 --- a/lemon/suurballe.h	Thu Mar 05 10:13:20 2009 +0000
    32.2 +++ b/lemon/suurballe.h	Sun Mar 29 23:08:20 2009 +0200
    32.3 @@ -45,9 +45,9 @@
    32.4    /// In fact, this implementation is the specialization of the
    32.5    /// \ref CapacityScaling "successive shortest path" algorithm.
    32.6    ///
    32.7 -  /// \tparam Digraph The digraph type the algorithm runs on.
    32.8 +  /// \tparam GR The digraph type the algorithm runs on.
    32.9    /// The default value is \c ListDigraph.
   32.10 -  /// \tparam LengthMap The type of the length (cost) map.
   32.11 +  /// \tparam LEN The type of the length (cost) map.
   32.12    /// The default value is <tt>Digraph::ArcMap<int></tt>.
   32.13    ///
   32.14    /// \warning Length values should be \e non-negative \e integers.
   32.15 @@ -55,21 +55,26 @@
   32.16    /// \note For finding node-disjoint paths this algorithm can be used
   32.17    /// with \ref SplitNodes.
   32.18  #ifdef DOXYGEN
   32.19 -  template <typename Digraph, typename LengthMap>
   32.20 +  template <typename GR, typename LEN>
   32.21  #else
   32.22 -  template < typename Digraph = ListDigraph,
   32.23 -             typename LengthMap = typename Digraph::template ArcMap<int> >
   32.24 +  template < typename GR = ListDigraph,
   32.25 +             typename LEN = typename GR::template ArcMap<int> >
   32.26  #endif
   32.27    class Suurballe
   32.28    {
   32.29 -    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   32.30 +    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
   32.31  
   32.32 -    typedef typename LengthMap::Value Length;
   32.33      typedef ConstMap<Arc, int> ConstArcMap;
   32.34 -    typedef typename Digraph::template NodeMap<Arc> PredMap;
   32.35 +    typedef typename GR::template NodeMap<Arc> PredMap;
   32.36  
   32.37    public:
   32.38  
   32.39 +    /// The type of the digraph the algorithm runs on.
   32.40 +    typedef GR Digraph;
   32.41 +    /// The type of the length map.
   32.42 +    typedef LEN LengthMap;
   32.43 +    /// The type of the lengths.
   32.44 +    typedef typename LengthMap::Value Length;
   32.45      /// The type of the flow map.
   32.46      typedef typename Digraph::template ArcMap<int> FlowMap;
   32.47      /// The type of the potential map.
   32.48 @@ -256,7 +261,7 @@
   32.49      /// The found flow contains only 0 and 1 values. It is the union of
   32.50      /// the found arc-disjoint paths.
   32.51      ///
   32.52 -    /// \return \c (*this)
   32.53 +    /// \return <tt>(*this)</tt>
   32.54      Suurballe& flowMap(FlowMap &map) {
   32.55        if (_local_flow) {
   32.56          delete _flow;
   32.57 @@ -273,7 +278,7 @@
   32.58      /// The potentials provide the dual solution of the underlying
   32.59      /// minimum cost flow problem.
   32.60      ///
   32.61 -    /// \return \c (*this)
   32.62 +    /// \return <tt>(*this)</tt>
   32.63      Suurballe& potentialMap(PotentialMap &map) {
   32.64        if (_local_potential) {
   32.65          delete _potential;
   32.66 @@ -458,7 +463,7 @@
   32.67      /// \brief Return the total length (cost) of the found paths (flow).
   32.68      ///
   32.69      /// This function returns the total length (cost) of the found paths
   32.70 -    /// (flow). The complexity of the function is \f$ O(e) \f$.
   32.71 +    /// (flow). The complexity of the function is O(e).
   32.72      ///
   32.73      /// \pre \ref run() or \ref findFlow() must be called before using
   32.74      /// this function.
    33.1 --- a/lemon/unionfind.h	Thu Mar 05 10:13:20 2009 +0000
    33.2 +++ b/lemon/unionfind.h	Sun Mar 29 23:08:20 2009 +0200
    33.3 @@ -51,11 +51,13 @@
    33.4    ///
    33.5    /// \pre You need to add all the elements by the \ref insert()
    33.6    /// method.
    33.7 -  template <typename _ItemIntMap>
    33.8 +  template <typename IM>
    33.9    class UnionFind {
   33.10    public:
   33.11  
   33.12 -    typedef _ItemIntMap ItemIntMap;
   33.13 +    ///\e
   33.14 +    typedef IM ItemIntMap;
   33.15 +    ///\e
   33.16      typedef typename ItemIntMap::Key Item;
   33.17  
   33.18    private:
   33.19 @@ -170,11 +172,13 @@
   33.20    /// \pre You need to add all the elements by the \ref insert()
   33.21    /// method.
   33.22    ///
   33.23 -  template <typename _ItemIntMap>
   33.24 +  template <typename IM>
   33.25    class UnionFindEnum {
   33.26    public:
   33.27  
   33.28 -    typedef _ItemIntMap ItemIntMap;
   33.29 +    ///\e
   33.30 +    typedef IM ItemIntMap;
   33.31 +    ///\e
   33.32      typedef typename ItemIntMap::Key Item;
   33.33  
   33.34    private:
   33.35 @@ -627,11 +631,13 @@
   33.36    ///
   33.37    /// \pre You need to add all the elements by the \ref insert()
   33.38    /// method.
   33.39 -  template <typename _ItemIntMap>
   33.40 +  template <typename IM>
   33.41    class ExtendFindEnum {
   33.42    public:
   33.43  
   33.44 -    typedef _ItemIntMap ItemIntMap;
   33.45 +    ///\e
   33.46 +    typedef IM ItemIntMap;
   33.47 +    ///\e
   33.48      typedef typename ItemIntMap::Key Item;
   33.49  
   33.50    private:
   33.51 @@ -948,18 +954,18 @@
   33.52    ///
   33.53    /// \pre You need to add all the elements by the \ref insert()
   33.54    /// method.
   33.55 -  ///
   33.56 -  template <typename _Value, typename _ItemIntMap,
   33.57 -            typename _Comp = std::less<_Value> >
   33.58 +  template <typename V, typename IM, typename Comp = std::less<V> >
   33.59    class HeapUnionFind {
   33.60    public:
   33.61  
   33.62 -    typedef _Value Value;
   33.63 -    typedef typename _ItemIntMap::Key Item;
   33.64 -
   33.65 -    typedef _ItemIntMap ItemIntMap;
   33.66 -
   33.67 -    typedef _Comp Comp;
   33.68 +    ///\e
   33.69 +    typedef V Value;
   33.70 +    ///\e
   33.71 +    typedef typename IM::Key Item;
   33.72 +    ///\e
   33.73 +    typedef IM ItemIntMap;
   33.74 +    ///\e
   33.75 +    typedef Comp Compare;
   33.76  
   33.77    private:
   33.78  
   33.79 @@ -1601,7 +1607,7 @@
   33.80  
   33.81      /// \brief Gives back the priority of the current item.
   33.82      ///
   33.83 -    /// \return Gives back the priority of the current item.
   33.84 +    /// Gives back the priority of the current item.
   33.85      const Value& operator[](const Item& item) const {
   33.86        return nodes[index[item]].prio;
   33.87      }
   33.88 @@ -1646,7 +1652,7 @@
   33.89  
   33.90      /// \brief Gives back the minimum priority of the class.
   33.91      ///
   33.92 -    /// \return Gives back the minimum priority of the class.
   33.93 +    /// Gives back the minimum priority of the class.
   33.94      const Value& classPrio(int cls) const {
   33.95        return nodes[~(classes[cls].parent)].prio;
   33.96      }
   33.97 @@ -1660,9 +1666,9 @@
   33.98  
   33.99      /// \brief Gives back a representant item of the class.
  33.100      ///
  33.101 +    /// Gives back a representant item of the class.
  33.102      /// The representant is indpendent from the priorities of the
  33.103      /// items.
  33.104 -    /// \return Gives back a representant item of the class.
  33.105      const Item& classRep(int id) const {
  33.106        int parent = classes[id].parent;
  33.107        return nodes[parent >= 0 ? classes[id].depth : leftNode(id)].item;