Merge #298
authorAlpar Juttner <alpar@cs.elte.hu>
Sat, 26 Sep 2009 07:21:54 +0200
changeset 7310977046c60d2
parent 730 4a45c8808b33
parent 726 3fc2a801c39e
child 732 1f8ad32f088b
child 781 6f10c6ec5a21
child 855 65a0521e744e
Merge #298
     1.1 --- a/doc/groups.dox	Sat Sep 26 07:16:22 2009 +0200
     1.2 +++ b/doc/groups.dox	Sat Sep 26 07:21:54 2009 +0200
     1.3 @@ -280,6 +280,28 @@
     1.4  */
     1.5  
     1.6  /**
     1.7 +@defgroup geomdat Geometric Data Structures
     1.8 +@ingroup auxdat
     1.9 +\brief Geometric data structures implemented in LEMON.
    1.10 +
    1.11 +This group contains geometric data structures implemented in LEMON.
    1.12 +
    1.13 + - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional
    1.14 +   vector with the usual operations.
    1.15 + - \ref lemon::dim2::Box "dim2::Box" can be used to determine the
    1.16 +   rectangular bounding box of a set of \ref lemon::dim2::Point
    1.17 +   "dim2::Point"'s.
    1.18 +*/
    1.19 +
    1.20 +/**
    1.21 +@defgroup matrices Matrices
    1.22 +@ingroup auxdat
    1.23 +\brief Two dimensional data storages implemented in LEMON.
    1.24 +
    1.25 +This group contains two dimensional data storages implemented in LEMON.
    1.26 +*/
    1.27 +
    1.28 +/**
    1.29  @defgroup algs Algorithms
    1.30  \brief This group contains the several algorithms
    1.31  implemented in LEMON.
    1.32 @@ -319,6 +341,15 @@
    1.33  */
    1.34  
    1.35  /**
    1.36 +@defgroup spantree Minimum Spanning Tree Algorithms
    1.37 +@ingroup algs
    1.38 +\brief Algorithms for finding minimum cost spanning trees and arborescences.
    1.39 +
    1.40 +This group contains the algorithms for finding minimum cost spanning
    1.41 +trees and arborescences.
    1.42 +*/
    1.43 +
    1.44 +/**
    1.45  @defgroup max_flow Maximum Flow Algorithms
    1.46  @ingroup algs
    1.47  \brief Algorithms for finding maximum flows.
    1.48 @@ -396,7 +427,7 @@
    1.49  cut is the \f$X\f$ solution of the next optimization problem:
    1.50  
    1.51  \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    1.52 -    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
    1.53 +    \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
    1.54  
    1.55  LEMON contains several algorithms related to minimum cut problems:
    1.56  
    1.57 @@ -412,30 +443,6 @@
    1.58  */
    1.59  
    1.60  /**
    1.61 -@defgroup graph_properties Connectivity and Other Graph Properties
    1.62 -@ingroup algs
    1.63 -\brief Algorithms for discovering the graph properties
    1.64 -
    1.65 -This group contains the algorithms for discovering the graph properties
    1.66 -like connectivity, bipartiteness, euler property, simplicity etc.
    1.67 -
    1.68 -\image html edge_biconnected_components.png
    1.69 -\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
    1.70 -*/
    1.71 -
    1.72 -/**
    1.73 -@defgroup planar Planarity Embedding and Drawing
    1.74 -@ingroup algs
    1.75 -\brief Algorithms for planarity checking, embedding and drawing
    1.76 -
    1.77 -This group contains the algorithms for planarity checking,
    1.78 -embedding and drawing.
    1.79 -
    1.80 -\image html planar.png
    1.81 -\image latex planar.eps "Plane graph" width=\textwidth
    1.82 -*/
    1.83 -
    1.84 -/**
    1.85  @defgroup matching Matching Algorithms
    1.86  @ingroup algs
    1.87  \brief Algorithms for finding matchings in graphs and bipartite graphs.
    1.88 @@ -476,12 +483,36 @@
    1.89  */
    1.90  
    1.91  /**
    1.92 -@defgroup spantree Minimum Spanning Tree Algorithms
    1.93 +@defgroup graph_properties Connectivity and Other Graph Properties
    1.94  @ingroup algs
    1.95 -\brief Algorithms for finding minimum cost spanning trees and arborescences.
    1.96 +\brief Algorithms for discovering the graph properties
    1.97  
    1.98 -This group contains the algorithms for finding minimum cost spanning
    1.99 -trees and arborescences.
   1.100 +This group contains the algorithms for discovering the graph properties
   1.101 +like connectivity, bipartiteness, euler property, simplicity etc.
   1.102 +
   1.103 +\image html connected_components.png
   1.104 +\image latex connected_components.eps "Connected components" width=\textwidth
   1.105 +*/
   1.106 +
   1.107 +/**
   1.108 +@defgroup planar Planarity Embedding and Drawing
   1.109 +@ingroup algs
   1.110 +\brief Algorithms for planarity checking, embedding and drawing
   1.111 +
   1.112 +This group contains the algorithms for planarity checking,
   1.113 +embedding and drawing.
   1.114 +
   1.115 +\image html planar.png
   1.116 +\image latex planar.eps "Plane graph" width=\textwidth
   1.117 +*/
   1.118 +
   1.119 +/**
   1.120 +@defgroup approx Approximation Algorithms
   1.121 +@ingroup algs
   1.122 +\brief Approximation algorithms.
   1.123 +
   1.124 +This group contains the approximation and heuristic algorithms
   1.125 +implemented in LEMON.
   1.126  */
   1.127  
   1.128  /**
   1.129 @@ -494,15 +525,6 @@
   1.130  */
   1.131  
   1.132  /**
   1.133 -@defgroup approx Approximation Algorithms
   1.134 -@ingroup algs
   1.135 -\brief Approximation algorithms.
   1.136 -
   1.137 -This group contains the approximation and heuristic algorithms
   1.138 -implemented in LEMON.
   1.139 -*/
   1.140 -
   1.141 -/**
   1.142  @defgroup gen_opt_group General Optimization Tools
   1.143  \brief This group contains some general optimization frameworks
   1.144  implemented in LEMON.
   1.145 @@ -608,7 +630,7 @@
   1.146  */
   1.147  
   1.148  /**
   1.149 -@defgroup dimacs_group DIMACS format
   1.150 +@defgroup dimacs_group DIMACS Format
   1.151  @ingroup io_group
   1.152  \brief Read and write files in DIMACS format
   1.153  
   1.154 @@ -670,6 +692,15 @@
   1.155  */
   1.156  
   1.157  /**
   1.158 +@defgroup tools Standalone Utility Applications
   1.159 +
   1.160 +Some utility applications are listed here.
   1.161 +
   1.162 +The standard compilation procedure (<tt>./configure;make</tt>) will compile
   1.163 +them, as well.
   1.164 +*/
   1.165 +
   1.166 +/**
   1.167  \anchor demoprograms
   1.168  
   1.169  @defgroup demos Demo Programs
   1.170 @@ -681,13 +712,4 @@
   1.171  <tt>make check</tt> commands.
   1.172  */
   1.173  
   1.174 -/**
   1.175 -@defgroup tools Standalone Utility Applications
   1.176 -
   1.177 -Some utility applications are listed here.
   1.178 -
   1.179 -The standard compilation procedure (<tt>./configure;make</tt>) will compile
   1.180 -them, as well.
   1.181 -*/
   1.182 -
   1.183  }
     2.1 --- a/lemon/bfs.h	Sat Sep 26 07:16:22 2009 +0200
     2.2 +++ b/lemon/bfs.h	Sat Sep 26 07:21:54 2009 +0200
     2.3 @@ -47,7 +47,7 @@
     2.4      ///
     2.5      ///The type of the map that stores the predecessor
     2.6      ///arcs of the shortest paths.
     2.7 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     2.8 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     2.9      typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    2.10      ///Instantiates a \c PredMap.
    2.11  
    2.12 @@ -62,7 +62,8 @@
    2.13      ///The type of the map that indicates which nodes are processed.
    2.14  
    2.15      ///The type of the map that indicates which nodes are processed.
    2.16 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    2.17 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    2.18 +    ///By default it is a NullMap.
    2.19      typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    2.20      ///Instantiates a \c ProcessedMap.
    2.21  
    2.22 @@ -81,7 +82,7 @@
    2.23      ///The type of the map that indicates which nodes are reached.
    2.24  
    2.25      ///The type of the map that indicates which nodes are reached.
    2.26 -    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    2.27 +    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    2.28      typedef typename Digraph::template NodeMap<bool> ReachedMap;
    2.29      ///Instantiates a \c ReachedMap.
    2.30  
    2.31 @@ -96,7 +97,7 @@
    2.32      ///The type of the map that stores the distances of the nodes.
    2.33  
    2.34      ///The type of the map that stores the distances of the nodes.
    2.35 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    2.36 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    2.37      typedef typename Digraph::template NodeMap<int> DistMap;
    2.38      ///Instantiates a \c DistMap.
    2.39  
    2.40 @@ -225,7 +226,7 @@
    2.41      ///
    2.42      ///\ref named-templ-param "Named parameter" for setting
    2.43      ///\c PredMap type.
    2.44 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    2.45 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    2.46      template <class T>
    2.47      struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
    2.48        typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
    2.49 @@ -245,7 +246,7 @@
    2.50      ///
    2.51      ///\ref named-templ-param "Named parameter" for setting
    2.52      ///\c DistMap type.
    2.53 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    2.54 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    2.55      template <class T>
    2.56      struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
    2.57        typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
    2.58 @@ -265,7 +266,7 @@
    2.59      ///
    2.60      ///\ref named-templ-param "Named parameter" for setting
    2.61      ///\c ReachedMap type.
    2.62 -    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    2.63 +    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    2.64      template <class T>
    2.65      struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
    2.66        typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
    2.67 @@ -285,7 +286,7 @@
    2.68      ///
    2.69      ///\ref named-templ-param "Named parameter" for setting
    2.70      ///\c ProcessedMap type.
    2.71 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    2.72 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    2.73      template <class T>
    2.74      struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
    2.75        typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
    2.76 @@ -413,8 +414,8 @@
    2.77      ///\name Execution Control
    2.78      ///The simplest way to execute the BFS algorithm is to use one of the
    2.79      ///member functions called \ref run(Node) "run()".\n
    2.80 -    ///If you need more control on the execution, first you have to call
    2.81 -    ///\ref init(), then you can add several source nodes with
    2.82 +    ///If you need better control on the execution, you have to call
    2.83 +    ///\ref init() first, then you can add several source nodes with
    2.84      ///\ref addSource(). Finally the actual path computation can be
    2.85      ///performed with one of the \ref start() functions.
    2.86  
    2.87 @@ -737,9 +738,9 @@
    2.88  
    2.89      ///@{
    2.90  
    2.91 -    ///The shortest path to a node.
    2.92 +    ///The shortest path to the given node.
    2.93  
    2.94 -    ///Returns the shortest path to a node.
    2.95 +    ///Returns the shortest path to the given node from the root(s).
    2.96      ///
    2.97      ///\warning \c t should be reached from the root(s).
    2.98      ///
    2.99 @@ -747,9 +748,9 @@
   2.100      ///must be called before using this function.
   2.101      Path path(Node t) const { return Path(*G, *_pred, t); }
   2.102  
   2.103 -    ///The distance of a node from the root(s).
   2.104 +    ///The distance of the given node from the root(s).
   2.105  
   2.106 -    ///Returns the distance of a node from the root(s).
   2.107 +    ///Returns the distance of the given node from the root(s).
   2.108      ///
   2.109      ///\warning If node \c v is not reached from the root(s), then
   2.110      ///the return value of this function is undefined.
   2.111 @@ -758,29 +759,31 @@
   2.112      ///must be called before using this function.
   2.113      int dist(Node v) const { return (*_dist)[v]; }
   2.114  
   2.115 -    ///Returns the 'previous arc' of the shortest path tree for a node.
   2.116 -
   2.117 +    ///\brief Returns the 'previous arc' of the shortest path tree for
   2.118 +    ///the given node.
   2.119 +    ///
   2.120      ///This function returns the 'previous arc' of the shortest path
   2.121      ///tree for the node \c v, i.e. it returns the last arc of a
   2.122      ///shortest path from a root to \c v. It is \c INVALID if \c v
   2.123      ///is not reached from the root(s) or if \c v is a root.
   2.124      ///
   2.125      ///The shortest path tree used here is equal to the shortest path
   2.126 -    ///tree used in \ref predNode().
   2.127 +    ///tree used in \ref predNode() and \ref predMap().
   2.128      ///
   2.129      ///\pre Either \ref run(Node) "run()" or \ref init()
   2.130      ///must be called before using this function.
   2.131      Arc predArc(Node v) const { return (*_pred)[v];}
   2.132  
   2.133 -    ///Returns the 'previous node' of the shortest path tree for a node.
   2.134 -
   2.135 +    ///\brief Returns the 'previous node' of the shortest path tree for
   2.136 +    ///the given node.
   2.137 +    ///
   2.138      ///This function returns the 'previous node' of the shortest path
   2.139      ///tree for the node \c v, i.e. it returns the last but one node
   2.140 -    ///from a shortest path from a root to \c v. It is \c INVALID
   2.141 +    ///of a shortest path from a root to \c v. It is \c INVALID
   2.142      ///if \c v is not reached from the root(s) or if \c v is a root.
   2.143      ///
   2.144      ///The shortest path tree used here is equal to the shortest path
   2.145 -    ///tree used in \ref predArc().
   2.146 +    ///tree used in \ref predArc() and \ref predMap().
   2.147      ///
   2.148      ///\pre Either \ref run(Node) "run()" or \ref init()
   2.149      ///must be called before using this function.
   2.150 @@ -801,13 +804,13 @@
   2.151      ///predecessor arcs.
   2.152      ///
   2.153      ///Returns a const reference to the node map that stores the predecessor
   2.154 -    ///arcs, which form the shortest path tree.
   2.155 +    ///arcs, which form the shortest path tree (forest).
   2.156      ///
   2.157      ///\pre Either \ref run(Node) "run()" or \ref init()
   2.158      ///must be called before using this function.
   2.159      const PredMap &predMap() const { return *_pred;}
   2.160  
   2.161 -    ///Checks if a node is reached from the root(s).
   2.162 +    ///Checks if the given node is reached from the root(s).
   2.163  
   2.164      ///Returns \c true if \c v is reached from the root(s).
   2.165      ///
   2.166 @@ -833,7 +836,7 @@
   2.167      ///
   2.168      ///The type of the map that stores the predecessor
   2.169      ///arcs of the shortest paths.
   2.170 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   2.171 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   2.172      typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
   2.173      ///Instantiates a PredMap.
   2.174  
   2.175 @@ -848,7 +851,7 @@
   2.176      ///The type of the map that indicates which nodes are processed.
   2.177  
   2.178      ///The type of the map that indicates which nodes are processed.
   2.179 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   2.180 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   2.181      ///By default it is a NullMap.
   2.182      typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
   2.183      ///Instantiates a ProcessedMap.
   2.184 @@ -868,7 +871,7 @@
   2.185      ///The type of the map that indicates which nodes are reached.
   2.186  
   2.187      ///The type of the map that indicates which nodes are reached.
   2.188 -    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
   2.189 +    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
   2.190      typedef typename Digraph::template NodeMap<bool> ReachedMap;
   2.191      ///Instantiates a ReachedMap.
   2.192  
   2.193 @@ -883,7 +886,7 @@
   2.194      ///The type of the map that stores the distances of the nodes.
   2.195  
   2.196      ///The type of the map that stores the distances of the nodes.
   2.197 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   2.198 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   2.199      typedef typename Digraph::template NodeMap<int> DistMap;
   2.200      ///Instantiates a DistMap.
   2.201  
   2.202 @@ -898,18 +901,14 @@
   2.203      ///The type of the shortest paths.
   2.204  
   2.205      ///The type of the shortest paths.
   2.206 -    ///It must meet the \ref concepts::Path "Path" concept.
   2.207 +    ///It must conform to the \ref concepts::Path "Path" concept.
   2.208      typedef lemon::Path<Digraph> Path;
   2.209    };
   2.210  
   2.211    /// Default traits class used by BfsWizard
   2.212  
   2.213 -  /// To make it easier to use Bfs algorithm
   2.214 -  /// we have created a wizard class.
   2.215 -  /// This \ref BfsWizard class needs default traits,
   2.216 -  /// as well as the \ref Bfs class.
   2.217 -  /// The \ref BfsWizardBase is a class to be the default traits of the
   2.218 -  /// \ref BfsWizard class.
   2.219 +  /// Default traits class used by BfsWizard.
   2.220 +  /// \tparam GR The type of the digraph.
   2.221    template<class GR>
   2.222    class BfsWizardBase : public BfsWizardDefaultTraits<GR>
   2.223    {
   2.224 @@ -937,7 +936,7 @@
   2.225      public:
   2.226      /// Constructor.
   2.227  
   2.228 -    /// This constructor does not require parameters, therefore it initiates
   2.229 +    /// This constructor does not require parameters, it initiates
   2.230      /// all of the attributes to \c 0.
   2.231      BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
   2.232                        _dist(0), _path(0), _di(0) {}
   2.233 @@ -967,7 +966,6 @@
   2.234    {
   2.235      typedef TR Base;
   2.236  
   2.237 -    ///The type of the digraph the algorithm runs on.
   2.238      typedef typename TR::Digraph Digraph;
   2.239  
   2.240      typedef typename Digraph::Node Node;
   2.241 @@ -975,16 +973,10 @@
   2.242      typedef typename Digraph::Arc Arc;
   2.243      typedef typename Digraph::OutArcIt OutArcIt;
   2.244  
   2.245 -    ///\brief The type of the map that stores the predecessor
   2.246 -    ///arcs of the shortest paths.
   2.247      typedef typename TR::PredMap PredMap;
   2.248 -    ///\brief The type of the map that stores the distances of the nodes.
   2.249      typedef typename TR::DistMap DistMap;
   2.250 -    ///\brief The type of the map that indicates which nodes are reached.
   2.251      typedef typename TR::ReachedMap ReachedMap;
   2.252 -    ///\brief The type of the map that indicates which nodes are processed.
   2.253      typedef typename TR::ProcessedMap ProcessedMap;
   2.254 -    ///The type of the shortest paths
   2.255      typedef typename TR::Path Path;
   2.256  
   2.257    public:
   2.258 @@ -1067,11 +1059,12 @@
   2.259        static PredMap *createPredMap(const Digraph &) { return 0; };
   2.260        SetPredMapBase(const TR &b) : TR(b) {}
   2.261      };
   2.262 -    ///\brief \ref named-func-param "Named parameter"
   2.263 -    ///for setting PredMap object.
   2.264 +
   2.265 +    ///\brief \ref named-templ-param "Named parameter" for setting
   2.266 +    ///the predecessor map.
   2.267      ///
   2.268 -    ///\ref named-func-param "Named parameter"
   2.269 -    ///for setting PredMap object.
   2.270 +    ///\ref named-templ-param "Named parameter" function for setting
   2.271 +    ///the map that stores the predecessor arcs of the nodes.
   2.272      template<class T>
   2.273      BfsWizard<SetPredMapBase<T> > predMap(const T &t)
   2.274      {
   2.275 @@ -1085,11 +1078,12 @@
   2.276        static ReachedMap *createReachedMap(const Digraph &) { return 0; };
   2.277        SetReachedMapBase(const TR &b) : TR(b) {}
   2.278      };
   2.279 -    ///\brief \ref named-func-param "Named parameter"
   2.280 -    ///for setting ReachedMap object.
   2.281 +
   2.282 +    ///\brief \ref named-templ-param "Named parameter" for setting
   2.283 +    ///the reached map.
   2.284      ///
   2.285 -    /// \ref named-func-param "Named parameter"
   2.286 -    ///for setting ReachedMap object.
   2.287 +    ///\ref named-templ-param "Named parameter" function for setting
   2.288 +    ///the map that indicates which nodes are reached.
   2.289      template<class T>
   2.290      BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
   2.291      {
   2.292 @@ -1103,11 +1097,13 @@
   2.293        static DistMap *createDistMap(const Digraph &) { return 0; };
   2.294        SetDistMapBase(const TR &b) : TR(b) {}
   2.295      };
   2.296 -    ///\brief \ref named-func-param "Named parameter"
   2.297 -    ///for setting DistMap object.
   2.298 +
   2.299 +    ///\brief \ref named-templ-param "Named parameter" for setting
   2.300 +    ///the distance map.
   2.301      ///
   2.302 -    /// \ref named-func-param "Named parameter"
   2.303 -    ///for setting DistMap object.
   2.304 +    ///\ref named-templ-param "Named parameter" function for setting
   2.305 +    ///the map that stores the distances of the nodes calculated
   2.306 +    ///by the algorithm.
   2.307      template<class T>
   2.308      BfsWizard<SetDistMapBase<T> > distMap(const T &t)
   2.309      {
   2.310 @@ -1121,11 +1117,12 @@
   2.311        static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
   2.312        SetProcessedMapBase(const TR &b) : TR(b) {}
   2.313      };
   2.314 -    ///\brief \ref named-func-param "Named parameter"
   2.315 -    ///for setting ProcessedMap object.
   2.316 +
   2.317 +    ///\brief \ref named-func-param "Named parameter" for setting
   2.318 +    ///the processed map.
   2.319      ///
   2.320 -    /// \ref named-func-param "Named parameter"
   2.321 -    ///for setting ProcessedMap object.
   2.322 +    ///\ref named-templ-param "Named parameter" function for setting
   2.323 +    ///the map that indicates which nodes are processed.
   2.324      template<class T>
   2.325      BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
   2.326      {
   2.327 @@ -1264,7 +1261,7 @@
   2.328      /// \brief The type of the map that indicates which nodes are reached.
   2.329      ///
   2.330      /// The type of the map that indicates which nodes are reached.
   2.331 -    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
   2.332 +    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
   2.333      typedef typename Digraph::template NodeMap<bool> ReachedMap;
   2.334  
   2.335      /// \brief Instantiates a ReachedMap.
   2.336 @@ -1425,8 +1422,8 @@
   2.337      /// \name Execution Control
   2.338      /// The simplest way to execute the BFS algorithm is to use one of the
   2.339      /// member functions called \ref run(Node) "run()".\n
   2.340 -    /// If you need more control on the execution, first you have to call
   2.341 -    /// \ref init(), then you can add several source nodes with
   2.342 +    /// If you need better control on the execution, you have to call
   2.343 +    /// \ref init() first, then you can add several source nodes with
   2.344      /// \ref addSource(). Finally the actual path computation can be
   2.345      /// performed with one of the \ref start() functions.
   2.346  
   2.347 @@ -1735,7 +1732,7 @@
   2.348  
   2.349      ///@{
   2.350  
   2.351 -    /// \brief Checks if a node is reached from the root(s).
   2.352 +    /// \brief Checks if the given node is reached from the root(s).
   2.353      ///
   2.354      /// Returns \c true if \c v is reached from the root(s).
   2.355      ///
     3.1 --- a/lemon/bits/map_extender.h	Sat Sep 26 07:16:22 2009 +0200
     3.2 +++ b/lemon/bits/map_extender.h	Sat Sep 26 07:21:54 2009 +0200
     3.3 @@ -49,6 +49,8 @@
     3.4      typedef typename Parent::Reference Reference;
     3.5      typedef typename Parent::ConstReference ConstReference;
     3.6  
     3.7 +    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
     3.8 +
     3.9      class MapIt;
    3.10      class ConstMapIt;
    3.11  
    3.12 @@ -191,6 +193,8 @@
    3.13      typedef typename Parent::Reference Reference;
    3.14      typedef typename Parent::ConstReference ConstReference;
    3.15  
    3.16 +    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
    3.17 +
    3.18      class MapIt;
    3.19      class ConstMapIt;
    3.20  
     4.1 --- a/lemon/circulation.h	Sat Sep 26 07:16:22 2009 +0200
     4.2 +++ b/lemon/circulation.h	Sat Sep 26 07:21:54 2009 +0200
     4.3 @@ -72,7 +72,11 @@
     4.4      /// The type of the map that stores the flow values.
     4.5      /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
     4.6      /// concept.
     4.7 +#ifdef DOXYGEN
     4.8 +    typedef GR::ArcMap<Value> FlowMap;
     4.9 +#else
    4.10      typedef typename Digraph::template ArcMap<Value> FlowMap;
    4.11 +#endif
    4.12  
    4.13      /// \brief Instantiates a FlowMap.
    4.14      ///
    4.15 @@ -87,9 +91,12 @@
    4.16      ///
    4.17      /// The elevator type used by the algorithm.
    4.18      ///
    4.19 -    /// \sa Elevator
    4.20 -    /// \sa LinkedElevator
    4.21 +    /// \sa Elevator, LinkedElevator
    4.22 +#ifdef DOXYGEN
    4.23 +    typedef lemon::Elevator<GR, GR::Node> Elevator;
    4.24 +#else
    4.25      typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
    4.26 +#endif
    4.27  
    4.28      /// \brief Instantiates an Elevator.
    4.29      ///
    4.30 @@ -469,8 +476,8 @@
    4.31  
    4.32      /// \name Execution Control
    4.33      /// The simplest way to execute the algorithm is to call \ref run().\n
    4.34 -    /// If you need more control on the initial solution or the execution,
    4.35 -    /// first you have to call one of the \ref init() functions, then
    4.36 +    /// If you need better control on the initial solution or the execution,
    4.37 +    /// you have to call one of the \ref init() functions first, then
    4.38      /// the \ref start() function.
    4.39  
    4.40      ///@{
     5.1 --- a/lemon/concepts/maps.h	Sat Sep 26 07:16:22 2009 +0200
     5.2 +++ b/lemon/concepts/maps.h	Sat Sep 26 07:21:54 2009 +0200
     5.3 @@ -182,7 +182,8 @@
     5.4  
     5.5        template<typename _ReferenceMap>
     5.6        struct Constraints {
     5.7 -        void constraints() {
     5.8 +        typename enable_if<typename _ReferenceMap::ReferenceMapTag, void>::type
     5.9 +        constraints() {
    5.10            checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();
    5.11            ref = m[key];
    5.12            m[key] = val;
     6.1 --- a/lemon/dfs.h	Sat Sep 26 07:16:22 2009 +0200
     6.2 +++ b/lemon/dfs.h	Sat Sep 26 07:21:54 2009 +0200
     6.3 @@ -47,7 +47,7 @@
     6.4      ///
     6.5      ///The type of the map that stores the predecessor
     6.6      ///arcs of the %DFS paths.
     6.7 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     6.8 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     6.9      typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    6.10      ///Instantiates a \c PredMap.
    6.11  
    6.12 @@ -62,7 +62,8 @@
    6.13      ///The type of the map that indicates which nodes are processed.
    6.14  
    6.15      ///The type of the map that indicates which nodes are processed.
    6.16 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    6.17 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    6.18 +    ///By default it is a NullMap.
    6.19      typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    6.20      ///Instantiates a \c ProcessedMap.
    6.21  
    6.22 @@ -81,7 +82,7 @@
    6.23      ///The type of the map that indicates which nodes are reached.
    6.24  
    6.25      ///The type of the map that indicates which nodes are reached.
    6.26 -    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    6.27 +    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    6.28      typedef typename Digraph::template NodeMap<bool> ReachedMap;
    6.29      ///Instantiates a \c ReachedMap.
    6.30  
    6.31 @@ -96,7 +97,7 @@
    6.32      ///The type of the map that stores the distances of the nodes.
    6.33  
    6.34      ///The type of the map that stores the distances of the nodes.
    6.35 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    6.36 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    6.37      typedef typename Digraph::template NodeMap<int> DistMap;
    6.38      ///Instantiates a \c DistMap.
    6.39  
    6.40 @@ -224,7 +225,7 @@
    6.41      ///
    6.42      ///\ref named-templ-param "Named parameter" for setting
    6.43      ///\c PredMap type.
    6.44 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    6.45 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    6.46      template <class T>
    6.47      struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
    6.48        typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
    6.49 @@ -244,7 +245,7 @@
    6.50      ///
    6.51      ///\ref named-templ-param "Named parameter" for setting
    6.52      ///\c DistMap type.
    6.53 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    6.54 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    6.55      template <class T>
    6.56      struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
    6.57        typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
    6.58 @@ -264,7 +265,7 @@
    6.59      ///
    6.60      ///\ref named-templ-param "Named parameter" for setting
    6.61      ///\c ReachedMap type.
    6.62 -    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    6.63 +    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    6.64      template <class T>
    6.65      struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
    6.66        typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
    6.67 @@ -284,7 +285,7 @@
    6.68      ///
    6.69      ///\ref named-templ-param "Named parameter" for setting
    6.70      ///\c ProcessedMap type.
    6.71 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    6.72 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    6.73      template <class T>
    6.74      struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
    6.75        typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
    6.76 @@ -411,8 +412,8 @@
    6.77      ///\name Execution Control
    6.78      ///The simplest way to execute the DFS algorithm is to use one of the
    6.79      ///member functions called \ref run(Node) "run()".\n
    6.80 -    ///If you need more control on the execution, first you have to call
    6.81 -    ///\ref init(), then you can add a source node with \ref addSource()
    6.82 +    ///If you need better control on the execution, you have to call
    6.83 +    ///\ref init() first, then you can add a source node with \ref addSource()
    6.84      ///and perform the actual computation with \ref start().
    6.85      ///This procedure can be repeated if there are nodes that have not
    6.86      ///been reached.
    6.87 @@ -669,9 +670,9 @@
    6.88  
    6.89      ///@{
    6.90  
    6.91 -    ///The DFS path to a node.
    6.92 +    ///The DFS path to the given node.
    6.93  
    6.94 -    ///Returns the DFS path to a node.
    6.95 +    ///Returns the DFS path to the given node from the root(s).
    6.96      ///
    6.97      ///\warning \c t should be reached from the root(s).
    6.98      ///
    6.99 @@ -679,9 +680,9 @@
   6.100      ///must be called before using this function.
   6.101      Path path(Node t) const { return Path(*G, *_pred, t); }
   6.102  
   6.103 -    ///The distance of a node from the root(s).
   6.104 +    ///The distance of the given node from the root(s).
   6.105  
   6.106 -    ///Returns the distance of a node from the root(s).
   6.107 +    ///Returns the distance of the given node from the root(s).
   6.108      ///
   6.109      ///\warning If node \c v is not reached from the root(s), then
   6.110      ///the return value of this function is undefined.
   6.111 @@ -690,7 +691,7 @@
   6.112      ///must be called before using this function.
   6.113      int dist(Node v) const { return (*_dist)[v]; }
   6.114  
   6.115 -    ///Returns the 'previous arc' of the %DFS tree for a node.
   6.116 +    ///Returns the 'previous arc' of the %DFS tree for the given node.
   6.117  
   6.118      ///This function returns the 'previous arc' of the %DFS tree for the
   6.119      ///node \c v, i.e. it returns the last arc of a %DFS path from a
   6.120 @@ -698,21 +699,21 @@
   6.121      ///root(s) or if \c v is a root.
   6.122      ///
   6.123      ///The %DFS tree used here is equal to the %DFS tree used in
   6.124 -    ///\ref predNode().
   6.125 +    ///\ref predNode() and \ref predMap().
   6.126      ///
   6.127      ///\pre Either \ref run(Node) "run()" or \ref init()
   6.128      ///must be called before using this function.
   6.129      Arc predArc(Node v) const { return (*_pred)[v];}
   6.130  
   6.131 -    ///Returns the 'previous node' of the %DFS tree.
   6.132 +    ///Returns the 'previous node' of the %DFS tree for the given node.
   6.133  
   6.134      ///This function returns the 'previous node' of the %DFS
   6.135      ///tree for the node \c v, i.e. it returns the last but one node
   6.136 -    ///from a %DFS path from a root to \c v. It is \c INVALID
   6.137 +    ///of a %DFS path from a root to \c v. It is \c INVALID
   6.138      ///if \c v is not reached from the root(s) or if \c v is a root.
   6.139      ///
   6.140      ///The %DFS tree used here is equal to the %DFS tree used in
   6.141 -    ///\ref predArc().
   6.142 +    ///\ref predArc() and \ref predMap().
   6.143      ///
   6.144      ///\pre Either \ref run(Node) "run()" or \ref init()
   6.145      ///must be called before using this function.
   6.146 @@ -733,13 +734,13 @@
   6.147      ///predecessor arcs.
   6.148      ///
   6.149      ///Returns a const reference to the node map that stores the predecessor
   6.150 -    ///arcs, which form the DFS tree.
   6.151 +    ///arcs, which form the DFS tree (forest).
   6.152      ///
   6.153      ///\pre Either \ref run(Node) "run()" or \ref init()
   6.154      ///must be called before using this function.
   6.155      const PredMap &predMap() const { return *_pred;}
   6.156  
   6.157 -    ///Checks if a node is reached from the root(s).
   6.158 +    ///Checks if the given node. node is reached from the root(s).
   6.159  
   6.160      ///Returns \c true if \c v is reached from the root(s).
   6.161      ///
   6.162 @@ -765,7 +766,7 @@
   6.163      ///
   6.164      ///The type of the map that stores the predecessor
   6.165      ///arcs of the %DFS paths.
   6.166 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   6.167 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   6.168      typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
   6.169      ///Instantiates a PredMap.
   6.170  
   6.171 @@ -780,7 +781,7 @@
   6.172      ///The type of the map that indicates which nodes are processed.
   6.173  
   6.174      ///The type of the map that indicates which nodes are processed.
   6.175 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   6.176 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   6.177      ///By default it is a NullMap.
   6.178      typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
   6.179      ///Instantiates a ProcessedMap.
   6.180 @@ -800,7 +801,7 @@
   6.181      ///The type of the map that indicates which nodes are reached.
   6.182  
   6.183      ///The type of the map that indicates which nodes are reached.
   6.184 -    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
   6.185 +    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
   6.186      typedef typename Digraph::template NodeMap<bool> ReachedMap;
   6.187      ///Instantiates a ReachedMap.
   6.188  
   6.189 @@ -815,7 +816,7 @@
   6.190      ///The type of the map that stores the distances of the nodes.
   6.191  
   6.192      ///The type of the map that stores the distances of the nodes.
   6.193 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   6.194 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   6.195      typedef typename Digraph::template NodeMap<int> DistMap;
   6.196      ///Instantiates a DistMap.
   6.197  
   6.198 @@ -830,18 +831,14 @@
   6.199      ///The type of the DFS paths.
   6.200  
   6.201      ///The type of the DFS paths.
   6.202 -    ///It must meet the \ref concepts::Path "Path" concept.
   6.203 +    ///It must conform to the \ref concepts::Path "Path" concept.
   6.204      typedef lemon::Path<Digraph> Path;
   6.205    };
   6.206  
   6.207    /// Default traits class used by DfsWizard
   6.208  
   6.209 -  /// To make it easier to use Dfs algorithm
   6.210 -  /// we have created a wizard class.
   6.211 -  /// This \ref DfsWizard class needs default traits,
   6.212 -  /// as well as the \ref Dfs class.
   6.213 -  /// The \ref DfsWizardBase is a class to be the default traits of the
   6.214 -  /// \ref DfsWizard class.
   6.215 +  /// Default traits class used by DfsWizard.
   6.216 +  /// \tparam GR The type of the digraph.
   6.217    template<class GR>
   6.218    class DfsWizardBase : public DfsWizardDefaultTraits<GR>
   6.219    {
   6.220 @@ -869,7 +866,7 @@
   6.221      public:
   6.222      /// Constructor.
   6.223  
   6.224 -    /// This constructor does not require parameters, therefore it initiates
   6.225 +    /// This constructor does not require parameters, it initiates
   6.226      /// all of the attributes to \c 0.
   6.227      DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
   6.228                        _dist(0), _path(0), _di(0) {}
   6.229 @@ -899,7 +896,6 @@
   6.230    {
   6.231      typedef TR Base;
   6.232  
   6.233 -    ///The type of the digraph the algorithm runs on.
   6.234      typedef typename TR::Digraph Digraph;
   6.235  
   6.236      typedef typename Digraph::Node Node;
   6.237 @@ -907,16 +903,10 @@
   6.238      typedef typename Digraph::Arc Arc;
   6.239      typedef typename Digraph::OutArcIt OutArcIt;
   6.240  
   6.241 -    ///\brief The type of the map that stores the predecessor
   6.242 -    ///arcs of the DFS paths.
   6.243      typedef typename TR::PredMap PredMap;
   6.244 -    ///\brief The type of the map that stores the distances of the nodes.
   6.245      typedef typename TR::DistMap DistMap;
   6.246 -    ///\brief The type of the map that indicates which nodes are reached.
   6.247      typedef typename TR::ReachedMap ReachedMap;
   6.248 -    ///\brief The type of the map that indicates which nodes are processed.
   6.249      typedef typename TR::ProcessedMap ProcessedMap;
   6.250 -    ///The type of the DFS paths
   6.251      typedef typename TR::Path Path;
   6.252  
   6.253    public:
   6.254 @@ -999,11 +989,12 @@
   6.255        static PredMap *createPredMap(const Digraph &) { return 0; };
   6.256        SetPredMapBase(const TR &b) : TR(b) {}
   6.257      };
   6.258 -    ///\brief \ref named-func-param "Named parameter"
   6.259 -    ///for setting PredMap object.
   6.260 +
   6.261 +    ///\brief \ref named-templ-param "Named parameter" for setting
   6.262 +    ///the predecessor map.
   6.263      ///
   6.264 -    ///\ref named-func-param "Named parameter"
   6.265 -    ///for setting PredMap object.
   6.266 +    ///\ref named-templ-param "Named parameter" function for setting
   6.267 +    ///the map that stores the predecessor arcs of the nodes.
   6.268      template<class T>
   6.269      DfsWizard<SetPredMapBase<T> > predMap(const T &t)
   6.270      {
   6.271 @@ -1017,11 +1008,12 @@
   6.272        static ReachedMap *createReachedMap(const Digraph &) { return 0; };
   6.273        SetReachedMapBase(const TR &b) : TR(b) {}
   6.274      };
   6.275 -    ///\brief \ref named-func-param "Named parameter"
   6.276 -    ///for setting ReachedMap object.
   6.277 +
   6.278 +    ///\brief \ref named-templ-param "Named parameter" for setting
   6.279 +    ///the reached map.
   6.280      ///
   6.281 -    /// \ref named-func-param "Named parameter"
   6.282 -    ///for setting ReachedMap object.
   6.283 +    ///\ref named-templ-param "Named parameter" function for setting
   6.284 +    ///the map that indicates which nodes are reached.
   6.285      template<class T>
   6.286      DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
   6.287      {
   6.288 @@ -1035,11 +1027,13 @@
   6.289        static DistMap *createDistMap(const Digraph &) { return 0; };
   6.290        SetDistMapBase(const TR &b) : TR(b) {}
   6.291      };
   6.292 -    ///\brief \ref named-func-param "Named parameter"
   6.293 -    ///for setting DistMap object.
   6.294 +
   6.295 +    ///\brief \ref named-templ-param "Named parameter" for setting
   6.296 +    ///the distance map.
   6.297      ///
   6.298 -    /// \ref named-func-param "Named parameter"
   6.299 -    ///for setting DistMap object.
   6.300 +    ///\ref named-templ-param "Named parameter" function for setting
   6.301 +    ///the map that stores the distances of the nodes calculated
   6.302 +    ///by the algorithm.
   6.303      template<class T>
   6.304      DfsWizard<SetDistMapBase<T> > distMap(const T &t)
   6.305      {
   6.306 @@ -1053,11 +1047,12 @@
   6.307        static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
   6.308        SetProcessedMapBase(const TR &b) : TR(b) {}
   6.309      };
   6.310 -    ///\brief \ref named-func-param "Named parameter"
   6.311 -    ///for setting ProcessedMap object.
   6.312 +
   6.313 +    ///\brief \ref named-func-param "Named parameter" for setting
   6.314 +    ///the processed map.
   6.315      ///
   6.316 -    /// \ref named-func-param "Named parameter"
   6.317 -    ///for setting ProcessedMap object.
   6.318 +    ///\ref named-templ-param "Named parameter" function for setting
   6.319 +    ///the map that indicates which nodes are processed.
   6.320      template<class T>
   6.321      DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
   6.322      {
   6.323 @@ -1208,7 +1203,7 @@
   6.324      /// \brief The type of the map that indicates which nodes are reached.
   6.325      ///
   6.326      /// The type of the map that indicates which nodes are reached.
   6.327 -    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
   6.328 +    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
   6.329      typedef typename Digraph::template NodeMap<bool> ReachedMap;
   6.330  
   6.331      /// \brief Instantiates a ReachedMap.
   6.332 @@ -1369,8 +1364,8 @@
   6.333      /// \name Execution Control
   6.334      /// The simplest way to execute the DFS algorithm is to use one of the
   6.335      /// member functions called \ref run(Node) "run()".\n
   6.336 -    /// If you need more control on the execution, first you have to call
   6.337 -    /// \ref init(), then you can add a source node with \ref addSource()
   6.338 +    /// If you need better control on the execution, you have to call
   6.339 +    /// \ref init() first, then you can add a source node with \ref addSource()
   6.340      /// and perform the actual computation with \ref start().
   6.341      /// This procedure can be repeated if there are nodes that have not
   6.342      /// been reached.
   6.343 @@ -1620,7 +1615,7 @@
   6.344  
   6.345      ///@{
   6.346  
   6.347 -    /// \brief Checks if a node is reached from the root(s).
   6.348 +    /// \brief Checks if the given node is reached from the root(s).
   6.349      ///
   6.350      /// Returns \c true if \c v is reached from the root(s).
   6.351      ///
     7.1 --- a/lemon/dijkstra.h	Sat Sep 26 07:16:22 2009 +0200
     7.2 +++ b/lemon/dijkstra.h	Sat Sep 26 07:21:54 2009 +0200
     7.3 @@ -70,9 +70,9 @@
     7.4      ///The type of the map that stores the arc lengths.
     7.5  
     7.6      ///The type of the map that stores the arc lengths.
     7.7 -    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
     7.8 +    ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
     7.9      typedef LEN LengthMap;
    7.10 -    ///The type of the length of the arcs.
    7.11 +    ///The type of the arc lengths.
    7.12      typedef typename LEN::Value Value;
    7.13  
    7.14      /// Operation traits for %Dijkstra algorithm.
    7.15 @@ -116,7 +116,7 @@
    7.16      ///
    7.17      ///The type of the map that stores the predecessor
    7.18      ///arcs of the shortest paths.
    7.19 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    7.20 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    7.21      typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    7.22      ///Instantiates a \c PredMap.
    7.23  
    7.24 @@ -131,7 +131,7 @@
    7.25      ///The type of the map that indicates which nodes are processed.
    7.26  
    7.27      ///The type of the map that indicates which nodes are processed.
    7.28 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    7.29 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    7.30      ///By default it is a NullMap.
    7.31      typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    7.32      ///Instantiates a \c ProcessedMap.
    7.33 @@ -151,7 +151,7 @@
    7.34      ///The type of the map that stores the distances of the nodes.
    7.35  
    7.36      ///The type of the map that stores the distances of the nodes.
    7.37 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    7.38 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    7.39      typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
    7.40      ///Instantiates a \c DistMap.
    7.41  
    7.42 @@ -169,6 +169,10 @@
    7.43    /// \ingroup shortest_path
    7.44    ///This class provides an efficient implementation of the %Dijkstra algorithm.
    7.45    ///
    7.46 +  ///The %Dijkstra algorithm solves the single-source shortest path problem
    7.47 +  ///when all arc lengths are non-negative. If there are negative lengths,
    7.48 +  ///the BellmanFord algorithm should be used instead.
    7.49 +  ///
    7.50    ///The arc lengths are passed to the algorithm using a
    7.51    ///\ref concepts::ReadMap "ReadMap",
    7.52    ///so it is easy to change it to any kind of length.
    7.53 @@ -201,7 +205,7 @@
    7.54      ///The type of the digraph the algorithm runs on.
    7.55      typedef typename TR::Digraph Digraph;
    7.56  
    7.57 -    ///The type of the length of the arcs.
    7.58 +    ///The type of the arc lengths.
    7.59      typedef typename TR::LengthMap::Value Value;
    7.60      ///The type of the map that stores the arc lengths.
    7.61      typedef typename TR::LengthMap LengthMap;
    7.62 @@ -304,7 +308,7 @@
    7.63      ///
    7.64      ///\ref named-templ-param "Named parameter" for setting
    7.65      ///\c PredMap type.
    7.66 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    7.67 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    7.68      template <class T>
    7.69      struct SetPredMap
    7.70        : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
    7.71 @@ -325,7 +329,7 @@
    7.72      ///
    7.73      ///\ref named-templ-param "Named parameter" for setting
    7.74      ///\c DistMap type.
    7.75 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    7.76 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    7.77      template <class T>
    7.78      struct SetDistMap
    7.79        : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
    7.80 @@ -346,7 +350,7 @@
    7.81      ///
    7.82      ///\ref named-templ-param "Named parameter" for setting
    7.83      ///\c ProcessedMap type.
    7.84 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    7.85 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    7.86      template <class T>
    7.87      struct SetProcessedMap
    7.88        : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
    7.89 @@ -443,6 +447,7 @@
    7.90      ///
    7.91      ///\ref named-templ-param "Named parameter" for setting
    7.92      ///\c OperationTraits type.
    7.93 +    /// For more information see \ref DijkstraDefaultOperationTraits.
    7.94      template <class T>
    7.95      struct SetOperationTraits
    7.96        : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {
    7.97 @@ -584,8 +589,8 @@
    7.98      ///\name Execution Control
    7.99      ///The simplest way to execute the %Dijkstra algorithm is to use
   7.100      ///one of the member functions called \ref run(Node) "run()".\n
   7.101 -    ///If you need more control on the execution, first you have to call
   7.102 -    ///\ref init(), then you can add several source nodes with
   7.103 +    ///If you need better control on the execution, you have to call
   7.104 +    ///\ref init() first, then you can add several source nodes with
   7.105      ///\ref addSource(). Finally the actual path computation can be
   7.106      ///performed with one of the \ref start() functions.
   7.107  
   7.108 @@ -801,14 +806,14 @@
   7.109      ///\name Query Functions
   7.110      ///The results of the %Dijkstra algorithm can be obtained using these
   7.111      ///functions.\n
   7.112 -    ///Either \ref run(Node) "run()" or \ref start() should be called
   7.113 +    ///Either \ref run(Node) "run()" or \ref init() should be called
   7.114      ///before using them.
   7.115  
   7.116      ///@{
   7.117  
   7.118 -    ///The shortest path to a node.
   7.119 +    ///The shortest path to the given node.
   7.120  
   7.121 -    ///Returns the shortest path to a node.
   7.122 +    ///Returns the shortest path to the given node from the root(s).
   7.123      ///
   7.124      ///\warning \c t should be reached from the root(s).
   7.125      ///
   7.126 @@ -816,9 +821,9 @@
   7.127      ///must be called before using this function.
   7.128      Path path(Node t) const { return Path(*G, *_pred, t); }
   7.129  
   7.130 -    ///The distance of a node from the root(s).
   7.131 +    ///The distance of the given node from the root(s).
   7.132  
   7.133 -    ///Returns the distance of a node from the root(s).
   7.134 +    ///Returns the distance of the given node from the root(s).
   7.135      ///
   7.136      ///\warning If node \c v is not reached from the root(s), then
   7.137      ///the return value of this function is undefined.
   7.138 @@ -827,29 +832,31 @@
   7.139      ///must be called before using this function.
   7.140      Value dist(Node v) const { return (*_dist)[v]; }
   7.141  
   7.142 -    ///Returns the 'previous arc' of the shortest path tree for a node.
   7.143 -
   7.144 +    ///\brief Returns the 'previous arc' of the shortest path tree for
   7.145 +    ///the given node.
   7.146 +    ///
   7.147      ///This function returns the 'previous arc' of the shortest path
   7.148      ///tree for the node \c v, i.e. it returns the last arc of a
   7.149      ///shortest path from a root to \c v. It is \c INVALID if \c v
   7.150      ///is not reached from the root(s) or if \c v is a root.
   7.151      ///
   7.152      ///The shortest path tree used here is equal to the shortest path
   7.153 -    ///tree used in \ref predNode().
   7.154 +    ///tree used in \ref predNode() and \ref predMap().
   7.155      ///
   7.156      ///\pre Either \ref run(Node) "run()" or \ref init()
   7.157      ///must be called before using this function.
   7.158      Arc predArc(Node v) const { return (*_pred)[v]; }
   7.159  
   7.160 -    ///Returns the 'previous node' of the shortest path tree for a node.
   7.161 -
   7.162 +    ///\brief Returns the 'previous node' of the shortest path tree for
   7.163 +    ///the given node.
   7.164 +    ///
   7.165      ///This function returns the 'previous node' of the shortest path
   7.166      ///tree for the node \c v, i.e. it returns the last but one node
   7.167 -    ///from a shortest path from a root to \c v. It is \c INVALID
   7.168 +    ///of a shortest path from a root to \c v. It is \c INVALID
   7.169      ///if \c v is not reached from the root(s) or if \c v is a root.
   7.170      ///
   7.171      ///The shortest path tree used here is equal to the shortest path
   7.172 -    ///tree used in \ref predArc().
   7.173 +    ///tree used in \ref predArc() and \ref predMap().
   7.174      ///
   7.175      ///\pre Either \ref run(Node) "run()" or \ref init()
   7.176      ///must be called before using this function.
   7.177 @@ -870,13 +877,13 @@
   7.178      ///predecessor arcs.
   7.179      ///
   7.180      ///Returns a const reference to the node map that stores the predecessor
   7.181 -    ///arcs, which form the shortest path tree.
   7.182 +    ///arcs, which form the shortest path tree (forest).
   7.183      ///
   7.184      ///\pre Either \ref run(Node) "run()" or \ref init()
   7.185      ///must be called before using this function.
   7.186      const PredMap &predMap() const { return *_pred;}
   7.187  
   7.188 -    ///Checks if a node is reached from the root(s).
   7.189 +    ///Checks if the given node is reached from the root(s).
   7.190  
   7.191      ///Returns \c true if \c v is reached from the root(s).
   7.192      ///
   7.193 @@ -895,9 +902,9 @@
   7.194      bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
   7.195                                            Heap::POST_HEAP; }
   7.196  
   7.197 -    ///The current distance of a node from the root(s).
   7.198 +    ///The current distance of the given node from the root(s).
   7.199  
   7.200 -    ///Returns the current distance of a node from the root(s).
   7.201 +    ///Returns the current distance of the given node from the root(s).
   7.202      ///It may be decreased in the following processes.
   7.203      ///
   7.204      ///\pre Either \ref run(Node) "run()" or \ref init()
   7.205 @@ -924,9 +931,9 @@
   7.206      ///The type of the map that stores the arc lengths.
   7.207  
   7.208      ///The type of the map that stores the arc lengths.
   7.209 -    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
   7.210 +    ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
   7.211      typedef LEN LengthMap;
   7.212 -    ///The type of the length of the arcs.
   7.213 +    ///The type of the arc lengths.
   7.214      typedef typename LEN::Value Value;
   7.215  
   7.216      /// Operation traits for Dijkstra algorithm.
   7.217 @@ -973,7 +980,7 @@
   7.218      ///
   7.219      ///The type of the map that stores the predecessor
   7.220      ///arcs of the shortest paths.
   7.221 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   7.222 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   7.223      typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
   7.224      ///Instantiates a PredMap.
   7.225  
   7.226 @@ -988,7 +995,7 @@
   7.227      ///The type of the map that indicates which nodes are processed.
   7.228  
   7.229      ///The type of the map that indicates which nodes are processed.
   7.230 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   7.231 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   7.232      ///By default it is a NullMap.
   7.233      typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
   7.234      ///Instantiates a ProcessedMap.
   7.235 @@ -1008,7 +1015,7 @@
   7.236      ///The type of the map that stores the distances of the nodes.
   7.237  
   7.238      ///The type of the map that stores the distances of the nodes.
   7.239 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   7.240 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   7.241      typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
   7.242      ///Instantiates a DistMap.
   7.243  
   7.244 @@ -1023,18 +1030,15 @@
   7.245      ///The type of the shortest paths.
   7.246  
   7.247      ///The type of the shortest paths.
   7.248 -    ///It must meet the \ref concepts::Path "Path" concept.
   7.249 +    ///It must conform to the \ref concepts::Path "Path" concept.
   7.250      typedef lemon::Path<Digraph> Path;
   7.251    };
   7.252  
   7.253    /// Default traits class used by DijkstraWizard
   7.254  
   7.255 -  /// To make it easier to use Dijkstra algorithm
   7.256 -  /// we have created a wizard class.
   7.257 -  /// This \ref DijkstraWizard class needs default traits,
   7.258 -  /// as well as the \ref Dijkstra class.
   7.259 -  /// The \ref DijkstraWizardBase is a class to be the default traits of the
   7.260 -  /// \ref DijkstraWizard class.
   7.261 +  /// Default traits class used by DijkstraWizard.
   7.262 +  /// \tparam GR The type of the digraph.
   7.263 +  /// \tparam LEN The type of the length map.
   7.264    template<typename GR, typename LEN>
   7.265    class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN>
   7.266    {
   7.267 @@ -1093,7 +1097,6 @@
   7.268    {
   7.269      typedef TR Base;
   7.270  
   7.271 -    ///The type of the digraph the algorithm runs on.
   7.272      typedef typename TR::Digraph Digraph;
   7.273  
   7.274      typedef typename Digraph::Node Node;
   7.275 @@ -1101,20 +1104,12 @@
   7.276      typedef typename Digraph::Arc Arc;
   7.277      typedef typename Digraph::OutArcIt OutArcIt;
   7.278  
   7.279 -    ///The type of the map that stores the arc lengths.
   7.280      typedef typename TR::LengthMap LengthMap;
   7.281 -    ///The type of the length of the arcs.
   7.282      typedef typename LengthMap::Value Value;
   7.283 -    ///\brief The type of the map that stores the predecessor
   7.284 -    ///arcs of the shortest paths.
   7.285      typedef typename TR::PredMap PredMap;
   7.286 -    ///The type of the map that stores the distances of the nodes.
   7.287      typedef typename TR::DistMap DistMap;
   7.288 -    ///The type of the map that indicates which nodes are processed.
   7.289      typedef typename TR::ProcessedMap ProcessedMap;
   7.290 -    ///The type of the shortest paths
   7.291      typedef typename TR::Path Path;
   7.292 -    ///The heap type used by the dijkstra algorithm.
   7.293      typedef typename TR::Heap Heap;
   7.294  
   7.295    public:
   7.296 @@ -1186,11 +1181,12 @@
   7.297        static PredMap *createPredMap(const Digraph &) { return 0; };
   7.298        SetPredMapBase(const TR &b) : TR(b) {}
   7.299      };
   7.300 -    ///\brief \ref named-func-param "Named parameter"
   7.301 -    ///for setting PredMap object.
   7.302 +
   7.303 +    ///\brief \ref named-templ-param "Named parameter" for setting
   7.304 +    ///the predecessor map.
   7.305      ///
   7.306 -    ///\ref named-func-param "Named parameter"
   7.307 -    ///for setting PredMap object.
   7.308 +    ///\ref named-templ-param "Named parameter" function for setting
   7.309 +    ///the map that stores the predecessor arcs of the nodes.
   7.310      template<class T>
   7.311      DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
   7.312      {
   7.313 @@ -1204,11 +1200,13 @@
   7.314        static DistMap *createDistMap(const Digraph &) { return 0; };
   7.315        SetDistMapBase(const TR &b) : TR(b) {}
   7.316      };
   7.317 -    ///\brief \ref named-func-param "Named parameter"
   7.318 -    ///for setting DistMap object.
   7.319 +
   7.320 +    ///\brief \ref named-templ-param "Named parameter" for setting
   7.321 +    ///the distance map.
   7.322      ///
   7.323 -    ///\ref named-func-param "Named parameter"
   7.324 -    ///for setting DistMap object.
   7.325 +    ///\ref named-templ-param "Named parameter" function for setting
   7.326 +    ///the map that stores the distances of the nodes calculated
   7.327 +    ///by the algorithm.
   7.328      template<class T>
   7.329      DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
   7.330      {
   7.331 @@ -1222,11 +1220,12 @@
   7.332        static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
   7.333        SetProcessedMapBase(const TR &b) : TR(b) {}
   7.334      };
   7.335 -    ///\brief \ref named-func-param "Named parameter"
   7.336 -    ///for setting ProcessedMap object.
   7.337 +
   7.338 +    ///\brief \ref named-func-param "Named parameter" for setting
   7.339 +    ///the processed map.
   7.340      ///
   7.341 -    /// \ref named-func-param "Named parameter"
   7.342 -    ///for setting ProcessedMap object.
   7.343 +    ///\ref named-templ-param "Named parameter" function for setting
   7.344 +    ///the map that indicates which nodes are processed.
   7.345      template<class T>
   7.346      DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
   7.347      {
   7.348 @@ -1239,6 +1238,7 @@
   7.349        typedef T Path;
   7.350        SetPathBase(const TR &b) : TR(b) {}
   7.351      };
   7.352 +
   7.353      ///\brief \ref named-func-param "Named parameter"
   7.354      ///for getting the shortest path to the target node.
   7.355      ///
     8.1 --- a/lemon/dim2.h	Sat Sep 26 07:16:22 2009 +0200
     8.2 +++ b/lemon/dim2.h	Sat Sep 26 07:21:54 2009 +0200
     8.3 @@ -21,16 +21,9 @@
     8.4  
     8.5  #include <iostream>
     8.6  
     8.7 -///\ingroup misc
     8.8 +///\ingroup geomdat
     8.9  ///\file
    8.10  ///\brief A simple two dimensional vector and a bounding box implementation
    8.11 -///
    8.12 -/// The class \ref lemon::dim2::Point "dim2::Point" implements
    8.13 -/// a two dimensional vector with the usual operations.
    8.14 -///
    8.15 -/// The class \ref lemon::dim2::Box "dim2::Box" can be used to determine
    8.16 -/// the rectangular bounding box of a set of
    8.17 -/// \ref lemon::dim2::Point "dim2::Point"'s.
    8.18  
    8.19  namespace lemon {
    8.20  
    8.21 @@ -40,7 +33,7 @@
    8.22    ///tools for handling two dimensional coordinates
    8.23    namespace dim2 {
    8.24  
    8.25 -  /// \addtogroup misc
    8.26 +  /// \addtogroup geomdat
    8.27    /// @{
    8.28  
    8.29    /// Two dimensional vector (plain vector)
     9.1 --- a/lemon/gomory_hu.h	Sat Sep 26 07:16:22 2009 +0200
     9.2 +++ b/lemon/gomory_hu.h	Sat Sep 26 07:21:54 2009 +0200
     9.3 @@ -359,10 +359,10 @@
     9.4      /// This example counts the nodes in the minimum cut separating \c s from
     9.5      /// \c t.
     9.6      /// \code
     9.7 -    /// GomoruHu<Graph> gom(g, capacities);
     9.8 +    /// GomoryHu<Graph> gom(g, capacities);
     9.9      /// gom.run();
    9.10      /// int cnt=0;
    9.11 -    /// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
    9.12 +    /// for(GomoryHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
    9.13      /// \endcode
    9.14      class MinCutNodeIt
    9.15      {
    9.16 @@ -456,10 +456,10 @@
    9.17      /// This example computes the value of the minimum cut separating \c s from
    9.18      /// \c t.
    9.19      /// \code
    9.20 -    /// GomoruHu<Graph> gom(g, capacities);
    9.21 +    /// GomoryHu<Graph> gom(g, capacities);
    9.22      /// gom.run();
    9.23      /// int value=0;
    9.24 -    /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
    9.25 +    /// for(GomoryHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
    9.26      ///   value+=capacities[e];
    9.27      /// \endcode
    9.28      /// The result will be the same as the value returned by
    10.1 --- a/lemon/maps.h	Sat Sep 26 07:16:22 2009 +0200
    10.2 +++ b/lemon/maps.h	Sat Sep 26 07:21:54 2009 +0200
    10.3 @@ -56,7 +56,7 @@
    10.4    /// its type definitions, or if you have to provide a writable map,
    10.5    /// but data written to it is not required (i.e. it will be sent to
    10.6    /// <tt>/dev/null</tt>).
    10.7 -  /// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    10.8 +  /// It conforms to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    10.9    ///
   10.10    /// \sa ConstMap
   10.11    template<typename K, typename V>
   10.12 @@ -89,7 +89,7 @@
   10.13    /// value to each key.
   10.14    ///
   10.15    /// In other aspects it is equivalent to \c NullMap.
   10.16 -  /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
   10.17 +  /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap"
   10.18    /// concept, but it absorbs the data written to it.
   10.19    ///
   10.20    /// The simplest way of using this map is through the constMap()
   10.21 @@ -158,7 +158,7 @@
   10.22    /// value to each key.
   10.23    ///
   10.24    /// In other aspects it is equivalent to \c NullMap.
   10.25 -  /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
   10.26 +  /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap"
   10.27    /// concept, but it absorbs the data written to it.
   10.28    ///
   10.29    /// The simplest way of using this map is through the constMap()
   10.30 @@ -232,7 +232,7 @@
   10.31    /// values to integer keys from the range <tt>[0..size-1]</tt>.
   10.32    /// It can be used with some data structures, for example
   10.33    /// \c UnionFind, \c BinHeap, when the used items are small
   10.34 -  /// integers. This map conforms the \ref concepts::ReferenceMap
   10.35 +  /// integers. This map conforms to the \ref concepts::ReferenceMap
   10.36    /// "ReferenceMap" concept.
   10.37    ///
   10.38    /// The simplest way of using this map is through the rangeMap()
   10.39 @@ -340,7 +340,7 @@
   10.40    /// that you can specify a default value for the keys that are not
   10.41    /// stored actually. This value can be different from the default
   10.42    /// contructed value (i.e. \c %Value()).
   10.43 -  /// This type conforms the \ref concepts::ReferenceMap "ReferenceMap"
   10.44 +  /// This type conforms to the \ref concepts::ReferenceMap "ReferenceMap"
   10.45    /// concept.
   10.46    ///
   10.47    /// This map is useful if a default value should be assigned to most of
   10.48 @@ -706,7 +706,7 @@
   10.49    /// "readable map" to another type using the default conversion.
   10.50    /// The \c Key type of it is inherited from \c M and the \c Value
   10.51    /// type is \c V.
   10.52 -  /// This type conforms the \ref concepts::ReadMap "ReadMap" concept.
   10.53 +  /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
   10.54    ///
   10.55    /// The simplest way of using this map is through the convertMap()
   10.56    /// function.
   10.57 @@ -1789,11 +1789,11 @@
   10.58    /// order of Dfs algorithm, as the following examples show.
   10.59    /// \code
   10.60    ///   std::vector<Node> v;
   10.61 -  ///   dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run();
   10.62 +  ///   dfs(g).processedMap(loggerBoolMap(std::back_inserter(v))).run(s);
   10.63    /// \endcode
   10.64    /// \code
   10.65    ///   std::vector<Node> v(countNodes(g));
   10.66 -  ///   dfs(g,s).processedMap(loggerBoolMap(v.begin())).run();
   10.67 +  ///   dfs(g).processedMap(loggerBoolMap(v.begin())).run(s);
   10.68    /// \endcode
   10.69    ///
   10.70    /// \note The container of the iterator must contain enough space
   10.71 @@ -1825,7 +1825,7 @@
   10.72    /// Using this map you get access (i.e. can read) the inner id values of
   10.73    /// the items stored in the graph, which is returned by the \c id()
   10.74    /// function of the graph. This map can be inverted with its member
   10.75 -  /// class \c InverseMap or with the \c operator() member.
   10.76 +  /// class \c InverseMap or with the \c operator()() member.
   10.77    ///
   10.78    /// \tparam GR The graph type.
   10.79    /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
   10.80 @@ -1865,9 +1865,11 @@
   10.81  
   10.82    public:
   10.83  
   10.84 -    /// \brief This class represents the inverse of its owner (IdMap).
   10.85 +    /// \brief The inverse map type of IdMap.
   10.86      ///
   10.87 -    /// This class represents the inverse of its owner (IdMap).
   10.88 +    /// The inverse map type of IdMap. The subscript operator gives back
   10.89 +    /// an item by its id.
   10.90 +    /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
   10.91      /// \see inverse()
   10.92      class InverseMap {
   10.93      public:
   10.94 @@ -1882,9 +1884,9 @@
   10.95        /// Constructor for creating an id-to-item map.
   10.96        explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
   10.97  
   10.98 -      /// \brief Gives back the given item from its id.
   10.99 +      /// \brief Gives back an item by its id.
  10.100        ///
  10.101 -      /// Gives back the given item from its id.
  10.102 +      /// Gives back an item by its id.
  10.103        Item operator[](int id) const { return _graph->fromId(id, Item());}
  10.104  
  10.105      private:
  10.106 @@ -1897,14 +1899,31 @@
  10.107      InverseMap inverse() const { return InverseMap(*_graph);}
  10.108    };
  10.109  
  10.110 +  /// \brief Returns an \c IdMap class.
  10.111 +  ///
  10.112 +  /// This function just returns an \c IdMap class.
  10.113 +  /// \relates IdMap
  10.114 +  template <typename K, typename GR>
  10.115 +  inline IdMap<GR, K> idMap(const GR& graph) {
  10.116 +    return IdMap<GR, K>(graph);
  10.117 +  }
  10.118  
  10.119    /// \brief General cross reference graph map type.
  10.120  
  10.121    /// This class provides simple invertable graph maps.
  10.122    /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
  10.123    /// and if a key is set to a new value, then stores it in the inverse map.
  10.124 -  /// The values of the map can be accessed
  10.125 -  /// with stl compatible forward iterator.
  10.126 +  /// The graph items can be accessed by their values either using
  10.127 +  /// \c InverseMap or \c operator()(), and the values of the map can be
  10.128 +  /// accessed with an STL compatible forward iterator (\c ValueIt).
  10.129 +  /// 
  10.130 +  /// This map is intended to be used when all associated values are
  10.131 +  /// different (the map is actually invertable) or there are only a few
  10.132 +  /// items with the same value.
  10.133 +  /// Otherwise consider to use \c IterableValueMap, which is more 
  10.134 +  /// suitable and more efficient for such cases. It provides iterators
  10.135 +  /// to traverse the items with the same associated value, however
  10.136 +  /// it does not have \c InverseMap.
  10.137    ///
  10.138    /// This type is not reference map, so it cannot be modified with
  10.139    /// the subscript operator.
  10.140 @@ -1945,56 +1964,66 @@
  10.141  
  10.142      /// \brief Forward iterator for values.
  10.143      ///
  10.144 -    /// This iterator is an stl compatible forward
  10.145 +    /// This iterator is an STL compatible forward
  10.146      /// iterator on the values of the map. The values can
  10.147      /// be accessed in the <tt>[beginValue, endValue)</tt> range.
  10.148      /// They are considered with multiplicity, so each value is
  10.149      /// traversed for each item it is assigned to.
  10.150 -    class ValueIterator
  10.151 +    class ValueIt
  10.152        : public std::iterator<std::forward_iterator_tag, Value> {
  10.153        friend class CrossRefMap;
  10.154      private:
  10.155 -      ValueIterator(typename Container::const_iterator _it)
  10.156 +      ValueIt(typename Container::const_iterator _it)
  10.157          : it(_it) {}
  10.158      public:
  10.159  
  10.160 -      ValueIterator() {}
  10.161 -
  10.162 -      ValueIterator& operator++() { ++it; return *this; }
  10.163 -      ValueIterator operator++(int) {
  10.164 -        ValueIterator tmp(*this);
  10.165 +      /// Constructor
  10.166 +      ValueIt() {}
  10.167 +
  10.168 +      /// \e
  10.169 +      ValueIt& operator++() { ++it; return *this; }
  10.170 +      /// \e
  10.171 +      ValueIt operator++(int) {
  10.172 +        ValueIt tmp(*this);
  10.173          operator++();
  10.174          return tmp;
  10.175        }
  10.176  
  10.177 +      /// \e
  10.178        const Value& operator*() const { return it->first; }
  10.179 +      /// \e
  10.180        const Value* operator->() const { return &(it->first); }
  10.181  
  10.182 -      bool operator==(ValueIterator jt) const { return it == jt.it; }
  10.183 -      bool operator!=(ValueIterator jt) const { return it != jt.it; }
  10.184 +      /// \e
  10.185 +      bool operator==(ValueIt jt) const { return it == jt.it; }
  10.186 +      /// \e
  10.187 +      bool operator!=(ValueIt jt) const { return it != jt.it; }
  10.188  
  10.189      private:
  10.190        typename Container::const_iterator it;
  10.191      };
  10.192 +    
  10.193 +    /// Alias for \c ValueIt
  10.194 +    typedef ValueIt ValueIterator;
  10.195  
  10.196      /// \brief Returns an iterator to the first value.
  10.197      ///
  10.198 -    /// Returns an stl compatible iterator to the
  10.199 +    /// Returns an STL compatible iterator to the
  10.200      /// first value of the map. The values of the
  10.201      /// map can be accessed in the <tt>[beginValue, endValue)</tt>
  10.202      /// range.
  10.203 -    ValueIterator beginValue() const {
  10.204 -      return ValueIterator(_inv_map.begin());
  10.205 +    ValueIt beginValue() const {
  10.206 +      return ValueIt(_inv_map.begin());
  10.207      }
  10.208  
  10.209      /// \brief Returns an iterator after the last value.
  10.210      ///
  10.211 -    /// Returns an stl compatible iterator after the
  10.212 +    /// Returns an STL compatible iterator after the
  10.213      /// last value of the map. The values of the
  10.214      /// map can be accessed in the <tt>[beginValue, endValue)</tt>
  10.215      /// range.
  10.216 -    ValueIterator endValue() const {
  10.217 -      return ValueIterator(_inv_map.end());
  10.218 +    ValueIt endValue() const {
  10.219 +      return ValueIt(_inv_map.end());
  10.220      }
  10.221  
  10.222      /// \brief Sets the value associated with the given key.
  10.223 @@ -2032,6 +2061,14 @@
  10.224        typename Container::const_iterator it = _inv_map.find(val);
  10.225        return it != _inv_map.end() ? it->second : INVALID;
  10.226      }
  10.227 +    
  10.228 +    /// \brief Returns the number of items with the given value.
  10.229 +    ///
  10.230 +    /// This function returns the number of items with the given value
  10.231 +    /// associated with it.
  10.232 +    int count(const Value &val) const {
  10.233 +      return _inv_map.count(val);
  10.234 +    }
  10.235  
  10.236    protected:
  10.237  
  10.238 @@ -2082,10 +2119,12 @@
  10.239  
  10.240    public:
  10.241  
  10.242 -    /// \brief The inverse map type.
  10.243 +    /// \brief The inverse map type of CrossRefMap.
  10.244      ///
  10.245 -    /// The inverse of this map. The subscript operator of the map
  10.246 -    /// gives back the item that was last assigned to the value.
  10.247 +    /// The inverse map type of CrossRefMap. The subscript operator gives
  10.248 +    /// back an item by its value.
  10.249 +    /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
  10.250 +    /// \see inverse()
  10.251      class InverseMap {
  10.252      public:
  10.253        /// \brief Constructor
  10.254 @@ -2112,20 +2151,20 @@
  10.255        const CrossRefMap& _inverted;
  10.256      };
  10.257  
  10.258 -    /// \brief It gives back the read-only inverse map.
  10.259 +    /// \brief Gives back the inverse of the map.
  10.260      ///
  10.261 -    /// It gives back the read-only inverse map.
  10.262 +    /// Gives back the inverse of the CrossRefMap.
  10.263      InverseMap inverse() const {
  10.264        return InverseMap(*this);
  10.265      }
  10.266  
  10.267    };
  10.268  
  10.269 -  /// \brief Provides continuous and unique ID for the
  10.270 +  /// \brief Provides continuous and unique id for the
  10.271    /// items of a graph.
  10.272    ///
  10.273    /// RangeIdMap provides a unique and continuous
  10.274 -  /// ID for each item of a given type (\c Node, \c Arc or
  10.275 +  /// id for each item of a given type (\c Node, \c Arc or
  10.276    /// \c Edge) in a graph. This id is
  10.277    ///  - \b unique: different items get different ids,
  10.278    ///  - \b continuous: the range of the ids is the set of integers
  10.279 @@ -2136,7 +2175,7 @@
  10.280    /// Thus this id is not (necessarily) the same as what can get using
  10.281    /// the \c id() function of the graph or \ref IdMap.
  10.282    /// This map can be inverted with its member class \c InverseMap,
  10.283 -  /// or with the \c operator() member.
  10.284 +  /// or with the \c operator()() member.
  10.285    ///
  10.286    /// \tparam GR The graph type.
  10.287    /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
  10.288 @@ -2264,16 +2303,16 @@
  10.289        _inv_map[pi] = q;
  10.290      }
  10.291  
  10.292 -    /// \brief Gives back the \e RangeId of the item
  10.293 +    /// \brief Gives back the \e range \e id of the item
  10.294      ///
  10.295 -    /// Gives back the \e RangeId of the item.
  10.296 +    /// Gives back the \e range \e id of the item.
  10.297      int operator[](const Item& item) const {
  10.298        return Map::operator[](item);
  10.299      }
  10.300  
  10.301 -    /// \brief Gives back the item belonging to a \e RangeId
  10.302 +    /// \brief Gives back the item belonging to a \e range \e id
  10.303      ///
  10.304 -    /// Gives back the item belonging to a \e RangeId.
  10.305 +    /// Gives back the item belonging to the given \e range \e id.
  10.306      Item operator()(int id) const {
  10.307        return _inv_map[id];
  10.308      }
  10.309 @@ -2287,7 +2326,9 @@
  10.310  
  10.311      /// \brief The inverse map type of RangeIdMap.
  10.312      ///
  10.313 -    /// The inverse map type of RangeIdMap.
  10.314 +    /// The inverse map type of RangeIdMap. The subscript operator gives
  10.315 +    /// back an item by its \e range \e id.
  10.316 +    /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
  10.317      class InverseMap {
  10.318      public:
  10.319        /// \brief Constructor
  10.320 @@ -2305,7 +2346,7 @@
  10.321        /// \brief Subscript operator.
  10.322        ///
  10.323        /// Subscript operator. It gives back the item
  10.324 -      /// that the descriptor currently belongs to.
  10.325 +      /// that the given \e range \e id currently belongs to.
  10.326        Value operator[](const Key& key) const {
  10.327          return _inverted(key);
  10.328        }
  10.329 @@ -2323,18 +2364,27 @@
  10.330  
  10.331      /// \brief Gives back the inverse of the map.
  10.332      ///
  10.333 -    /// Gives back the inverse of the map.
  10.334 +    /// Gives back the inverse of the RangeIdMap.
  10.335      const InverseMap inverse() const {
  10.336        return InverseMap(*this);
  10.337      }
  10.338    };
  10.339  
  10.340 +  /// \brief Returns a \c RangeIdMap class.
  10.341 +  ///
  10.342 +  /// This function just returns an \c RangeIdMap class.
  10.343 +  /// \relates RangeIdMap
  10.344 +  template <typename K, typename GR>
  10.345 +  inline RangeIdMap<GR, K> rangeIdMap(const GR& graph) {
  10.346 +    return RangeIdMap<GR, K>(graph);
  10.347 +  }
  10.348 +  
  10.349    /// \brief Dynamic iterable \c bool map.
  10.350    ///
  10.351    /// This class provides a special graph map type which can store a
  10.352    /// \c bool value for graph items (\c Node, \c Arc or \c Edge).
  10.353    /// For both \c true and \c false values it is possible to iterate on
  10.354 -  /// the keys.
  10.355 +  /// the keys mapped to the value.
  10.356    ///
  10.357    /// This type is a reference map, so it can be modified with the
  10.358    /// subscript operator.
  10.359 @@ -2703,6 +2753,11 @@
  10.360    /// For each non-negative value it is possible to iterate on the keys
  10.361    /// mapped to the value.
  10.362    ///
  10.363 +  /// This map is intended to be used with small integer values, for which
  10.364 +  /// it is efficient, and supports iteration only for non-negative values.
  10.365 +  /// If you need large values and/or iteration for negative integers,
  10.366 +  /// consider to use \ref IterableValueMap instead.
  10.367 +  ///
  10.368    /// This type is a reference map, so it can be modified with the
  10.369    /// subscript operator.
  10.370    ///
  10.371 @@ -2984,15 +3039,17 @@
  10.372  
  10.373    /// \brief Dynamic iterable map for comparable values.
  10.374    ///
  10.375 -  /// This class provides a special graph map type which can store an
  10.376 +  /// This class provides a special graph map type which can store a
  10.377    /// comparable value for graph items (\c Node, \c Arc or \c Edge).
  10.378    /// For each value it is possible to iterate on the keys mapped to
  10.379 -  /// the value.
  10.380 +  /// the value (\c ItemIt), and the values of the map can be accessed
  10.381 +  /// with an STL compatible forward iterator (\c ValueIt).
  10.382 +  /// The map stores a linked list for each value, which contains
  10.383 +  /// the items mapped to the value, and the used values are stored
  10.384 +  /// in balanced binary tree (\c std::map).
  10.385    ///
  10.386 -  /// The map stores for each value a linked list with
  10.387 -  /// the items which mapped to the value, and the values are stored
  10.388 -  /// in balanced binary tree. The values of the map can be accessed
  10.389 -  /// with stl compatible forward iterator.
  10.390 +  /// \ref IterableBoolMap and \ref IterableIntMap are similar classes
  10.391 +  /// specialized for \c bool and \c int values, respectively.
  10.392    ///
  10.393    /// This type is not reference map, so it cannot be modified with
  10.394    /// the subscript operator.
  10.395 @@ -3071,31 +3128,38 @@
  10.396  
  10.397      /// \brief Forward iterator for values.
  10.398      ///
  10.399 -    /// This iterator is an stl compatible forward
  10.400 +    /// This iterator is an STL compatible forward
  10.401      /// iterator on the values of the map. The values can
  10.402      /// be accessed in the <tt>[beginValue, endValue)</tt> range.
  10.403 -    class ValueIterator
  10.404 +    class ValueIt
  10.405        : public std::iterator<std::forward_iterator_tag, Value> {
  10.406        friend class IterableValueMap;
  10.407      private:
  10.408 -      ValueIterator(typename std::map<Value, Key>::const_iterator _it)
  10.409 +      ValueIt(typename std::map<Value, Key>::const_iterator _it)
  10.410          : it(_it) {}
  10.411      public:
  10.412  
  10.413 -      ValueIterator() {}
  10.414 -
  10.415 -      ValueIterator& operator++() { ++it; return *this; }
  10.416 -      ValueIterator operator++(int) {
  10.417 -        ValueIterator tmp(*this);
  10.418 +      /// Constructor
  10.419 +      ValueIt() {}
  10.420 +
  10.421 +      /// \e
  10.422 +      ValueIt& operator++() { ++it; return *this; }
  10.423 +      /// \e
  10.424 +      ValueIt operator++(int) {
  10.425 +        ValueIt tmp(*this);
  10.426          operator++();
  10.427          return tmp;
  10.428        }
  10.429  
  10.430 +      /// \e
  10.431        const Value& operator*() const { return it->first; }
  10.432 +      /// \e
  10.433        const Value* operator->() const { return &(it->first); }
  10.434  
  10.435 -      bool operator==(ValueIterator jt) const { return it == jt.it; }
  10.436 -      bool operator!=(ValueIterator jt) const { return it != jt.it; }
  10.437 +      /// \e
  10.438 +      bool operator==(ValueIt jt) const { return it == jt.it; }
  10.439 +      /// \e
  10.440 +      bool operator!=(ValueIt jt) const { return it != jt.it; }
  10.441  
  10.442      private:
  10.443        typename std::map<Value, Key>::const_iterator it;
  10.444 @@ -3103,22 +3167,22 @@
  10.445  
  10.446      /// \brief Returns an iterator to the first value.
  10.447      ///
  10.448 -    /// Returns an stl compatible iterator to the
  10.449 +    /// Returns an STL compatible iterator to the
  10.450      /// first value of the map. The values of the
  10.451      /// map can be accessed in the <tt>[beginValue, endValue)</tt>
  10.452      /// range.
  10.453 -    ValueIterator beginValue() const {
  10.454 -      return ValueIterator(_first.begin());
  10.455 +    ValueIt beginValue() const {
  10.456 +      return ValueIt(_first.begin());
  10.457      }
  10.458  
  10.459      /// \brief Returns an iterator after the last value.
  10.460      ///
  10.461 -    /// Returns an stl compatible iterator after the
  10.462 +    /// Returns an STL compatible iterator after the
  10.463      /// last value of the map. The values of the
  10.464      /// map can be accessed in the <tt>[beginValue, endValue)</tt>
  10.465      /// range.
  10.466 -    ValueIterator endValue() const {
  10.467 -      return ValueIterator(_first.end());
  10.468 +    ValueIt endValue() const {
  10.469 +      return ValueIt(_first.end());
  10.470      }
  10.471  
  10.472      /// \brief Set operation of the map.
  10.473 @@ -3236,9 +3300,9 @@
  10.474    class SourceMap {
  10.475    public:
  10.476  
  10.477 -    ///\e
  10.478 +    /// The key type (the \c Arc type of the digraph).
  10.479      typedef typename GR::Arc Key;
  10.480 -    ///\e
  10.481 +    /// The value type (the \c Node type of the digraph).
  10.482      typedef typename GR::Node Value;
  10.483  
  10.484      /// \brief Constructor
  10.485 @@ -3277,9 +3341,9 @@
  10.486    class TargetMap {
  10.487    public:
  10.488  
  10.489 -    ///\e
  10.490 +    /// The key type (the \c Arc type of the digraph).
  10.491      typedef typename GR::Arc Key;
  10.492 -    ///\e
  10.493 +    /// The value type (the \c Node type of the digraph).
  10.494      typedef typename GR::Node Value;
  10.495  
  10.496      /// \brief Constructor
  10.497 @@ -3319,8 +3383,10 @@
  10.498    class ForwardMap {
  10.499    public:
  10.500  
  10.501 +    /// The key type (the \c Edge type of the digraph).
  10.502 +    typedef typename GR::Edge Key;
  10.503 +    /// The value type (the \c Arc type of the digraph).
  10.504      typedef typename GR::Arc Value;
  10.505 -    typedef typename GR::Edge Key;
  10.506  
  10.507      /// \brief Constructor
  10.508      ///
  10.509 @@ -3359,8 +3425,10 @@
  10.510    class BackwardMap {
  10.511    public:
  10.512  
  10.513 +    /// The key type (the \c Edge type of the digraph).
  10.514 +    typedef typename GR::Edge Key;
  10.515 +    /// The value type (the \c Arc type of the digraph).
  10.516      typedef typename GR::Arc Value;
  10.517 -    typedef typename GR::Edge Key;
  10.518  
  10.519      /// \brief Constructor
  10.520      ///
    11.1 --- a/lemon/min_cost_arborescence.h	Sat Sep 26 07:16:22 2009 +0200
    11.2 +++ b/lemon/min_cost_arborescence.h	Sat Sep 26 07:21:54 2009 +0200
    11.3 @@ -488,8 +488,8 @@
    11.4      /// \name Execution Control
    11.5      /// The simplest way to execute the algorithm is to use
    11.6      /// one of the member functions called \c run(...). \n
    11.7 -    /// If you need more control on the execution,
    11.8 -    /// first you must call \ref init(), then you can add several
    11.9 +    /// If you need better control on the execution,
   11.10 +    /// you have to call \ref init() first, then you can add several
   11.11      /// source nodes with \ref addSource().
   11.12      /// Finally \ref start() will perform the arborescence
   11.13      /// computation.
    12.1 --- a/lemon/preflow.h	Sat Sep 26 07:16:22 2009 +0200
    12.2 +++ b/lemon/preflow.h	Sat Sep 26 07:21:54 2009 +0200
    12.3 @@ -52,7 +52,11 @@
    12.4      ///
    12.5      /// The type of the map that stores the flow values.
    12.6      /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12.7 +#ifdef DOXYGEN
    12.8 +    typedef GR::ArcMap<Value> FlowMap;
    12.9 +#else
   12.10      typedef typename Digraph::template ArcMap<Value> FlowMap;
   12.11 +#endif
   12.12  
   12.13      /// \brief Instantiates a FlowMap.
   12.14      ///
   12.15 @@ -67,9 +71,12 @@
   12.16      ///
   12.17      /// The elevator type used by Preflow algorithm.
   12.18      ///
   12.19 -    /// \sa Elevator
   12.20 -    /// \sa LinkedElevator
   12.21 -    typedef LinkedElevator<Digraph, typename Digraph::Node> Elevator;
   12.22 +    /// \sa Elevator, LinkedElevator
   12.23 +#ifdef DOXYGEN
   12.24 +    typedef lemon::Elevator<GR, GR::Node> Elevator;
   12.25 +#else
   12.26 +    typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
   12.27 +#endif
   12.28  
   12.29      /// \brief Instantiates an Elevator.
   12.30      ///
   12.31 @@ -391,8 +398,8 @@
   12.32      /// \name Execution Control
   12.33      /// The simplest way to execute the preflow algorithm is to use
   12.34      /// \ref run() or \ref runMinCut().\n
   12.35 -    /// If you need more control on the initial solution or the execution,
   12.36 -    /// first you have to call one of the \ref init() functions, then
   12.37 +    /// If you need better control on the initial solution or the execution,
   12.38 +    /// you have to call one of the \ref init() functions first, then
   12.39      /// \ref startFirstPhase() and if you need it \ref startSecondPhase().
   12.40  
   12.41      ///@{
    13.1 --- a/test/maps_test.cc	Sat Sep 26 07:16:22 2009 +0200
    13.2 +++ b/test/maps_test.cc	Sat Sep 26 07:21:54 2009 +0200
    13.3 @@ -22,7 +22,10 @@
    13.4  #include <lemon/concept_check.h>
    13.5  #include <lemon/concepts/maps.h>
    13.6  #include <lemon/maps.h>
    13.7 +#include <lemon/list_graph.h>
    13.8  #include <lemon/smart_graph.h>
    13.9 +#include <lemon/adaptors.h>
   13.10 +#include <lemon/dfs.h>
   13.11  
   13.12  #include "test_tools.h"
   13.13  
   13.14 @@ -61,6 +64,12 @@
   13.15  typedef ReadWriteMap<A, bool> BoolWriteMap;
   13.16  typedef ReferenceMap<A, bool, bool&, const bool&> BoolRefMap;
   13.17  
   13.18 +template<typename Map1, typename Map2, typename ItemIt>
   13.19 +void compareMap(const Map1& map1, const Map2& map2, ItemIt it) {
   13.20 +  for (; it != INVALID; ++it)
   13.21 +    check(map1[it] == map2[it], "The maps are not equal");
   13.22 +}
   13.23 +
   13.24  int main()
   13.25  {
   13.26    // Map concepts
   13.27 @@ -329,6 +338,10 @@
   13.28    // LoggerBoolMap
   13.29    {
   13.30      typedef std::vector<int> vec;
   13.31 +    checkConcept<WriteMap<int, bool>, LoggerBoolMap<vec::iterator> >();
   13.32 +    checkConcept<WriteMap<int, bool>,
   13.33 +                 LoggerBoolMap<std::back_insert_iterator<vec> > >();
   13.34 +
   13.35      vec v1;
   13.36      vec v2(10);
   13.37      LoggerBoolMap<std::back_insert_iterator<vec> >
   13.38 @@ -348,6 +361,222 @@
   13.39      for ( LoggerBoolMap<vec::iterator>::Iterator it = map2.begin();
   13.40            it != map2.end(); ++it )
   13.41        check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");
   13.42 +    
   13.43 +    typedef ListDigraph Graph;
   13.44 +    DIGRAPH_TYPEDEFS(Graph);
   13.45 +    Graph gr;
   13.46 +
   13.47 +    Node n0 = gr.addNode();
   13.48 +    Node n1 = gr.addNode();
   13.49 +    Node n2 = gr.addNode();
   13.50 +    Node n3 = gr.addNode();
   13.51 +    
   13.52 +    gr.addArc(n3, n0);
   13.53 +    gr.addArc(n3, n2);
   13.54 +    gr.addArc(n0, n2);
   13.55 +    gr.addArc(n2, n1);
   13.56 +    gr.addArc(n0, n1);
   13.57 +    
   13.58 +    {
   13.59 +      std::vector<Node> v;
   13.60 +      dfs(gr).processedMap(loggerBoolMap(std::back_inserter(v))).run();
   13.61 +
   13.62 +      check(v.size()==4 && v[0]==n1 && v[1]==n2 && v[2]==n0 && v[3]==n3,
   13.63 +            "Something is wrong with LoggerBoolMap");
   13.64 +    }
   13.65 +    {
   13.66 +      std::vector<Node> v(countNodes(gr));
   13.67 +      dfs(gr).processedMap(loggerBoolMap(v.begin())).run();
   13.68 +      
   13.69 +      check(v.size()==4 && v[0]==n1 && v[1]==n2 && v[2]==n0 && v[3]==n3,
   13.70 +            "Something is wrong with LoggerBoolMap");
   13.71 +    }
   13.72 +  }
   13.73 +  
   13.74 +  // IdMap, RangeIdMap
   13.75 +  {
   13.76 +    typedef ListDigraph Graph;
   13.77 +    DIGRAPH_TYPEDEFS(Graph);
   13.78 +
   13.79 +    checkConcept<ReadMap<Node, int>, IdMap<Graph, Node> >();
   13.80 +    checkConcept<ReadMap<Arc, int>, IdMap<Graph, Arc> >();
   13.81 +    checkConcept<ReadMap<Node, int>, RangeIdMap<Graph, Node> >();
   13.82 +    checkConcept<ReadMap<Arc, int>, RangeIdMap<Graph, Arc> >();
   13.83 +    
   13.84 +    Graph gr;
   13.85 +    IdMap<Graph, Node> nmap(gr);
   13.86 +    IdMap<Graph, Arc> amap(gr);
   13.87 +    RangeIdMap<Graph, Node> nrmap(gr);
   13.88 +    RangeIdMap<Graph, Arc> armap(gr);
   13.89 +    
   13.90 +    Node n0 = gr.addNode();
   13.91 +    Node n1 = gr.addNode();
   13.92 +    Node n2 = gr.addNode();
   13.93 +    
   13.94 +    Arc a0 = gr.addArc(n0, n1);
   13.95 +    Arc a1 = gr.addArc(n0, n2);
   13.96 +    Arc a2 = gr.addArc(n2, n1);
   13.97 +    Arc a3 = gr.addArc(n2, n0);
   13.98 +    
   13.99 +    check(nmap[n0] == gr.id(n0) && nmap(gr.id(n0)) == n0, "Wrong IdMap");
  13.100 +    check(nmap[n1] == gr.id(n1) && nmap(gr.id(n1)) == n1, "Wrong IdMap");
  13.101 +    check(nmap[n2] == gr.id(n2) && nmap(gr.id(n2)) == n2, "Wrong IdMap");
  13.102 +
  13.103 +    check(amap[a0] == gr.id(a0) && amap(gr.id(a0)) == a0, "Wrong IdMap");
  13.104 +    check(amap[a1] == gr.id(a1) && amap(gr.id(a1)) == a1, "Wrong IdMap");
  13.105 +    check(amap[a2] == gr.id(a2) && amap(gr.id(a2)) == a2, "Wrong IdMap");
  13.106 +    check(amap[a3] == gr.id(a3) && amap(gr.id(a3)) == a3, "Wrong IdMap");
  13.107 +
  13.108 +    check(nmap.inverse()[gr.id(n0)] == n0, "Wrong IdMap::InverseMap");
  13.109 +    check(amap.inverse()[gr.id(a0)] == a0, "Wrong IdMap::InverseMap");
  13.110 +    
  13.111 +    check(nrmap.size() == 3 && armap.size() == 4,
  13.112 +          "Wrong RangeIdMap::size()");
  13.113 +
  13.114 +    check(nrmap[n0] == 0 && nrmap(0) == n0, "Wrong RangeIdMap");
  13.115 +    check(nrmap[n1] == 1 && nrmap(1) == n1, "Wrong RangeIdMap");
  13.116 +    check(nrmap[n2] == 2 && nrmap(2) == n2, "Wrong RangeIdMap");
  13.117 +    
  13.118 +    check(armap[a0] == 0 && armap(0) == a0, "Wrong RangeIdMap");
  13.119 +    check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap");
  13.120 +    check(armap[a2] == 2 && armap(2) == a2, "Wrong RangeIdMap");
  13.121 +    check(armap[a3] == 3 && armap(3) == a3, "Wrong RangeIdMap");
  13.122 +
  13.123 +    check(nrmap.inverse()[0] == n0, "Wrong RangeIdMap::InverseMap");
  13.124 +    check(armap.inverse()[0] == a0, "Wrong RangeIdMap::InverseMap");
  13.125 +    
  13.126 +    gr.erase(n1);
  13.127 +    
  13.128 +    if (nrmap[n0] == 1) nrmap.swap(n0, n2);
  13.129 +    nrmap.swap(n2, n0);
  13.130 +    if (armap[a1] == 1) armap.swap(a1, a3);
  13.131 +    armap.swap(a3, a1);
  13.132 +    
  13.133 +    check(nrmap.size() == 2 && armap.size() == 2,
  13.134 +          "Wrong RangeIdMap::size()");
  13.135 +
  13.136 +    check(nrmap[n0] == 1 && nrmap(1) == n0, "Wrong RangeIdMap");
  13.137 +    check(nrmap[n2] == 0 && nrmap(0) == n2, "Wrong RangeIdMap");
  13.138 +    
  13.139 +    check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap");
  13.140 +    check(armap[a3] == 0 && armap(0) == a3, "Wrong RangeIdMap");
  13.141 +
  13.142 +    check(nrmap.inverse()[0] == n2, "Wrong RangeIdMap::InverseMap");
  13.143 +    check(armap.inverse()[0] == a3, "Wrong RangeIdMap::InverseMap");
  13.144 +  }
  13.145 +  
  13.146 +  // SourceMap, TargetMap, ForwardMap, BackwardMap, InDegMap, OutDegMap
  13.147 +  {
  13.148 +    typedef ListGraph Graph;
  13.149 +    GRAPH_TYPEDEFS(Graph);
  13.150 +    
  13.151 +    checkConcept<ReadMap<Arc, Node>, SourceMap<Graph> >();
  13.152 +    checkConcept<ReadMap<Arc, Node>, TargetMap<Graph> >();
  13.153 +    checkConcept<ReadMap<Edge, Arc>, ForwardMap<Graph> >();
  13.154 +    checkConcept<ReadMap<Edge, Arc>, BackwardMap<Graph> >();
  13.155 +    checkConcept<ReadMap<Node, int>, InDegMap<Graph> >();
  13.156 +    checkConcept<ReadMap<Node, int>, OutDegMap<Graph> >();
  13.157 +
  13.158 +    Graph gr;
  13.159 +    Node n0 = gr.addNode();
  13.160 +    Node n1 = gr.addNode();
  13.161 +    Node n2 = gr.addNode();
  13.162 +    
  13.163 +    gr.addEdge(n0,n1);
  13.164 +    gr.addEdge(n1,n2);
  13.165 +    gr.addEdge(n0,n2);
  13.166 +    gr.addEdge(n2,n1);
  13.167 +    gr.addEdge(n1,n2);
  13.168 +    gr.addEdge(n0,n1);
  13.169 +    
  13.170 +    for (EdgeIt e(gr); e != INVALID; ++e) {
  13.171 +      check(forwardMap(gr)[e] == gr.direct(e, true), "Wrong ForwardMap");
  13.172 +      check(backwardMap(gr)[e] == gr.direct(e, false), "Wrong BackwardMap");
  13.173 +    }
  13.174 +    
  13.175 +    compareMap(sourceMap(orienter(gr, constMap<Edge, bool>(true))),
  13.176 +               targetMap(orienter(gr, constMap<Edge, bool>(false))),
  13.177 +               EdgeIt(gr));
  13.178 +
  13.179 +    typedef Orienter<Graph, const ConstMap<Edge, bool> > Digraph;
  13.180 +    Digraph dgr(gr, constMap<Edge, bool>(true));
  13.181 +    OutDegMap<Digraph> odm(dgr);
  13.182 +    InDegMap<Digraph> idm(dgr);
  13.183 +    
  13.184 +    check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 1, "Wrong OutDegMap");
  13.185 +    check(idm[n0] == 0 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap");
  13.186 +   
  13.187 +    gr.addEdge(n2, n0);
  13.188 +
  13.189 +    check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 2, "Wrong OutDegMap");
  13.190 +    check(idm[n0] == 1 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap");
  13.191 +  }
  13.192 +  
  13.193 +  // CrossRefMap
  13.194 +  {
  13.195 +    typedef ListDigraph Graph;
  13.196 +    DIGRAPH_TYPEDEFS(Graph);
  13.197 +
  13.198 +    checkConcept<ReadWriteMap<Node, int>,
  13.199 +                 CrossRefMap<Graph, Node, int> >();
  13.200 +    checkConcept<ReadWriteMap<Node, bool>,
  13.201 +                 CrossRefMap<Graph, Node, bool> >();
  13.202 +    checkConcept<ReadWriteMap<Node, double>,
  13.203 +                 CrossRefMap<Graph, Node, double> >();
  13.204 +    
  13.205 +    Graph gr;
  13.206 +    typedef CrossRefMap<Graph, Node, char> CRMap;
  13.207 +    CRMap map(gr);
  13.208 +    
  13.209 +    Node n0 = gr.addNode();
  13.210 +    Node n1 = gr.addNode();
  13.211 +    Node n2 = gr.addNode();
  13.212 +    
  13.213 +    map.set(n0, 'A');
  13.214 +    map.set(n1, 'B');
  13.215 +    map.set(n2, 'C');
  13.216 +    
  13.217 +    check(map[n0] == 'A' && map('A') == n0 && map.inverse()['A'] == n0,
  13.218 +          "Wrong CrossRefMap");
  13.219 +    check(map[n1] == 'B' && map('B') == n1 && map.inverse()['B'] == n1,
  13.220 +          "Wrong CrossRefMap");
  13.221 +    check(map[n2] == 'C' && map('C') == n2 && map.inverse()['C'] == n2,
  13.222 +          "Wrong CrossRefMap");
  13.223 +    check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1,
  13.224 +          "Wrong CrossRefMap::count()");
  13.225 +    
  13.226 +    CRMap::ValueIt it = map.beginValue();
  13.227 +    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
  13.228 +          it == map.endValue(), "Wrong value iterator");
  13.229 +    
  13.230 +    map.set(n2, 'A');
  13.231 +
  13.232 +    check(map[n0] == 'A' && map[n1] == 'B' && map[n2] == 'A',
  13.233 +          "Wrong CrossRefMap");
  13.234 +    check(map('A') == n0 && map.inverse()['A'] == n0, "Wrong CrossRefMap");
  13.235 +    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");
  13.236 +    check(map('C') == INVALID && map.inverse()['C'] == INVALID,
  13.237 +          "Wrong CrossRefMap");
  13.238 +    check(map.count('A') == 2 && map.count('B') == 1 && map.count('C') == 0,
  13.239 +          "Wrong CrossRefMap::count()");
  13.240 +
  13.241 +    it = map.beginValue();
  13.242 +    check(*it++ == 'A' && *it++ == 'A' && *it++ == 'B' &&
  13.243 +          it == map.endValue(), "Wrong value iterator");
  13.244 +
  13.245 +    map.set(n0, 'C');
  13.246 +
  13.247 +    check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A',
  13.248 +          "Wrong CrossRefMap");
  13.249 +    check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap");
  13.250 +    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");
  13.251 +    check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap");
  13.252 +    check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1,
  13.253 +          "Wrong CrossRefMap::count()");
  13.254 +
  13.255 +    it = map.beginValue();
  13.256 +    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
  13.257 +          it == map.endValue(), "Wrong value iterator");
  13.258    }
  13.259  
  13.260    // CrossRefMap
  13.261 @@ -546,10 +775,10 @@
  13.262        check(static_cast<Item>(it) == INVALID, "Wrong value");
  13.263      }
  13.264  
  13.265 -    for (Ivm::ValueIterator vit = map1.beginValue();
  13.266 +    for (Ivm::ValueIt vit = map1.beginValue();
  13.267           vit != map1.endValue(); ++vit) {
  13.268        check(map1[static_cast<Item>(Ivm::ItemIt(map1, *vit))] == *vit,
  13.269 -            "Wrong ValueIterator");
  13.270 +            "Wrong ValueIt");
  13.271      }
  13.272  
  13.273      for (int i = 0; i < num; ++i) {