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) {