# HG changeset patch # User Alpar Juttner # Date 1253942514 -7200 # Node ID 0977046c60d27196e3b008fe9f65350180ec5362 # Parent 4a45c8808b33461ccbd84d4f9874a15eeb96fa2d# Parent 3fc2a801c39e0313c8bcb0336e3cdf02f28d9da3 Merge #298 diff -r 4a45c8808b33 -r 0977046c60d2 doc/groups.dox --- a/doc/groups.dox Sat Sep 26 07:16:22 2009 +0200 +++ b/doc/groups.dox Sat Sep 26 07:21:54 2009 +0200 @@ -280,6 +280,28 @@ */ /** +@defgroup geomdat Geometric Data Structures +@ingroup auxdat +\brief Geometric data structures implemented in LEMON. + +This group contains geometric data structures implemented in LEMON. + + - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional + vector with the usual operations. + - \ref lemon::dim2::Box "dim2::Box" can be used to determine the + rectangular bounding box of a set of \ref lemon::dim2::Point + "dim2::Point"'s. +*/ + +/** +@defgroup matrices Matrices +@ingroup auxdat +\brief Two dimensional data storages implemented in LEMON. + +This group contains two dimensional data storages implemented in LEMON. +*/ + +/** @defgroup algs Algorithms \brief This group contains the several algorithms implemented in LEMON. @@ -319,6 +341,15 @@ */ /** +@defgroup spantree Minimum Spanning Tree Algorithms +@ingroup algs +\brief Algorithms for finding minimum cost spanning trees and arborescences. + +This group contains the algorithms for finding minimum cost spanning +trees and arborescences. +*/ + +/** @defgroup max_flow Maximum Flow Algorithms @ingroup algs \brief Algorithms for finding maximum flows. @@ -396,7 +427,7 @@ cut is the \f$X\f$ solution of the next optimization problem: \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}} - \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f] + \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f] LEMON contains several algorithms related to minimum cut problems: @@ -412,30 +443,6 @@ */ /** -@defgroup graph_properties Connectivity and Other Graph Properties -@ingroup algs -\brief Algorithms for discovering the graph properties - -This group contains the algorithms for discovering the graph properties -like connectivity, bipartiteness, euler property, simplicity etc. - -\image html edge_biconnected_components.png -\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth -*/ - -/** -@defgroup planar Planarity Embedding and Drawing -@ingroup algs -\brief Algorithms for planarity checking, embedding and drawing - -This group contains the algorithms for planarity checking, -embedding and drawing. - -\image html planar.png -\image latex planar.eps "Plane graph" width=\textwidth -*/ - -/** @defgroup matching Matching Algorithms @ingroup algs \brief Algorithms for finding matchings in graphs and bipartite graphs. @@ -476,12 +483,36 @@ */ /** -@defgroup spantree Minimum Spanning Tree Algorithms +@defgroup graph_properties Connectivity and Other Graph Properties @ingroup algs -\brief Algorithms for finding minimum cost spanning trees and arborescences. +\brief Algorithms for discovering the graph properties -This group contains the algorithms for finding minimum cost spanning -trees and arborescences. +This group contains the algorithms for discovering the graph properties +like connectivity, bipartiteness, euler property, simplicity etc. + +\image html connected_components.png +\image latex connected_components.eps "Connected components" width=\textwidth +*/ + +/** +@defgroup planar Planarity Embedding and Drawing +@ingroup algs +\brief Algorithms for planarity checking, embedding and drawing + +This group contains the algorithms for planarity checking, +embedding and drawing. + +\image html planar.png +\image latex planar.eps "Plane graph" width=\textwidth +*/ + +/** +@defgroup approx Approximation Algorithms +@ingroup algs +\brief Approximation algorithms. + +This group contains the approximation and heuristic algorithms +implemented in LEMON. */ /** @@ -494,15 +525,6 @@ */ /** -@defgroup approx Approximation Algorithms -@ingroup algs -\brief Approximation algorithms. - -This group contains the approximation and heuristic algorithms -implemented in LEMON. -*/ - -/** @defgroup gen_opt_group General Optimization Tools \brief This group contains some general optimization frameworks implemented in LEMON. @@ -608,7 +630,7 @@ */ /** -@defgroup dimacs_group DIMACS format +@defgroup dimacs_group DIMACS Format @ingroup io_group \brief Read and write files in DIMACS format @@ -670,6 +692,15 @@ */ /** +@defgroup tools Standalone Utility Applications + +Some utility applications are listed here. + +The standard compilation procedure (./configure;make) will compile +them, as well. +*/ + +/** \anchor demoprograms @defgroup demos Demo Programs @@ -681,13 +712,4 @@ make check commands. */ -/** -@defgroup tools Standalone Utility Applications - -Some utility applications are listed here. - -The standard compilation procedure (./configure;make) will compile -them, as well. -*/ - } diff -r 4a45c8808b33 -r 0977046c60d2 lemon/bfs.h --- a/lemon/bfs.h Sat Sep 26 07:16:22 2009 +0200 +++ b/lemon/bfs.h Sat Sep 26 07:21:54 2009 +0200 @@ -47,7 +47,7 @@ /// ///The type of the map that stores the predecessor ///arcs of the shortest paths. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap PredMap; ///Instantiates a \c PredMap. @@ -62,7 +62,8 @@ ///The type of the map that indicates which nodes are processed. ///The type of the map that indicates which nodes are processed. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///By default it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a \c ProcessedMap. @@ -81,7 +82,7 @@ ///The type of the map that indicates which nodes are reached. ///The type of the map that indicates which nodes are reached. - ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; ///Instantiates a \c ReachedMap. @@ -96,7 +97,7 @@ ///The type of the map that stores the distances of the nodes. ///The type of the map that stores the distances of the nodes. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap DistMap; ///Instantiates a \c DistMap. @@ -225,7 +226,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///\c PredMap type. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetPredMap : public Bfs< Digraph, SetPredMapTraits > { typedef Bfs< Digraph, SetPredMapTraits > Create; @@ -245,7 +246,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///\c DistMap type. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetDistMap : public Bfs< Digraph, SetDistMapTraits > { typedef Bfs< Digraph, SetDistMapTraits > Create; @@ -265,7 +266,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///\c ReachedMap type. - ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. template struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits > { typedef Bfs< Digraph, SetReachedMapTraits > Create; @@ -285,7 +286,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///\c ProcessedMap type. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits > { typedef Bfs< Digraph, SetProcessedMapTraits > Create; @@ -413,8 +414,8 @@ ///\name Execution Control ///The simplest way to execute the BFS algorithm is to use one of the ///member functions called \ref run(Node) "run()".\n - ///If you need more control on the execution, first you have to call - ///\ref init(), then you can add several source nodes with + ///If you need better control on the execution, you have to call + ///\ref init() first, then you can add several source nodes with ///\ref addSource(). Finally the actual path computation can be ///performed with one of the \ref start() functions. @@ -737,9 +738,9 @@ ///@{ - ///The shortest path to a node. + ///The shortest path to the given node. - ///Returns the shortest path to a node. + ///Returns the shortest path to the given node from the root(s). /// ///\warning \c t should be reached from the root(s). /// @@ -747,9 +748,9 @@ ///must be called before using this function. Path path(Node t) const { return Path(*G, *_pred, t); } - ///The distance of a node from the root(s). + ///The distance of the given node from the root(s). - ///Returns the distance of a node from the root(s). + ///Returns the distance of the given node from the root(s). /// ///\warning If node \c v is not reached from the root(s), then ///the return value of this function is undefined. @@ -758,29 +759,31 @@ ///must be called before using this function. int dist(Node v) const { return (*_dist)[v]; } - ///Returns the 'previous arc' of the shortest path tree for a node. - + ///\brief Returns the 'previous arc' of the shortest path tree for + ///the given node. + /// ///This function returns the 'previous arc' of the shortest path ///tree for the node \c v, i.e. it returns the last arc of a ///shortest path from a root to \c v. It is \c INVALID if \c v ///is not reached from the root(s) or if \c v is a root. /// ///The shortest path tree used here is equal to the shortest path - ///tree used in \ref predNode(). + ///tree used in \ref predNode() and \ref predMap(). /// ///\pre Either \ref run(Node) "run()" or \ref init() ///must be called before using this function. Arc predArc(Node v) const { return (*_pred)[v];} - ///Returns the 'previous node' of the shortest path tree for a node. - + ///\brief Returns the 'previous node' of the shortest path tree for + ///the given node. + /// ///This function returns the 'previous node' of the shortest path ///tree for the node \c v, i.e. it returns the last but one node - ///from a shortest path from a root to \c v. It is \c INVALID + ///of a shortest path from a root to \c v. It is \c INVALID ///if \c v is not reached from the root(s) or if \c v is a root. /// ///The shortest path tree used here is equal to the shortest path - ///tree used in \ref predArc(). + ///tree used in \ref predArc() and \ref predMap(). /// ///\pre Either \ref run(Node) "run()" or \ref init() ///must be called before using this function. @@ -801,13 +804,13 @@ ///predecessor arcs. /// ///Returns a const reference to the node map that stores the predecessor - ///arcs, which form the shortest path tree. + ///arcs, which form the shortest path tree (forest). /// ///\pre Either \ref run(Node) "run()" or \ref init() ///must be called before using this function. const PredMap &predMap() const { return *_pred;} - ///Checks if a node is reached from the root(s). + ///Checks if the given node is reached from the root(s). ///Returns \c true if \c v is reached from the root(s). /// @@ -833,7 +836,7 @@ /// ///The type of the map that stores the predecessor ///arcs of the shortest paths. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap PredMap; ///Instantiates a PredMap. @@ -848,7 +851,7 @@ ///The type of the map that indicates which nodes are processed. ///The type of the map that indicates which nodes are processed. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a ProcessedMap. @@ -868,7 +871,7 @@ ///The type of the map that indicates which nodes are reached. ///The type of the map that indicates which nodes are reached. - ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; ///Instantiates a ReachedMap. @@ -883,7 +886,7 @@ ///The type of the map that stores the distances of the nodes. ///The type of the map that stores the distances of the nodes. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap DistMap; ///Instantiates a DistMap. @@ -898,18 +901,14 @@ ///The type of the shortest paths. ///The type of the shortest paths. - ///It must meet the \ref concepts::Path "Path" concept. + ///It must conform to the \ref concepts::Path "Path" concept. typedef lemon::Path Path; }; /// Default traits class used by BfsWizard - /// To make it easier to use Bfs algorithm - /// we have created a wizard class. - /// This \ref BfsWizard class needs default traits, - /// as well as the \ref Bfs class. - /// The \ref BfsWizardBase is a class to be the default traits of the - /// \ref BfsWizard class. + /// Default traits class used by BfsWizard. + /// \tparam GR The type of the digraph. template class BfsWizardBase : public BfsWizardDefaultTraits { @@ -937,7 +936,7 @@ public: /// Constructor. - /// This constructor does not require parameters, therefore it initiates + /// This constructor does not require parameters, it initiates /// all of the attributes to \c 0. BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {} @@ -967,7 +966,6 @@ { typedef TR Base; - ///The type of the digraph the algorithm runs on. typedef typename TR::Digraph Digraph; typedef typename Digraph::Node Node; @@ -975,16 +973,10 @@ typedef typename Digraph::Arc Arc; typedef typename Digraph::OutArcIt OutArcIt; - ///\brief The type of the map that stores the predecessor - ///arcs of the shortest paths. typedef typename TR::PredMap PredMap; - ///\brief The type of the map that stores the distances of the nodes. typedef typename TR::DistMap DistMap; - ///\brief The type of the map that indicates which nodes are reached. typedef typename TR::ReachedMap ReachedMap; - ///\brief The type of the map that indicates which nodes are processed. typedef typename TR::ProcessedMap ProcessedMap; - ///The type of the shortest paths typedef typename TR::Path Path; public: @@ -1067,11 +1059,12 @@ static PredMap *createPredMap(const Digraph &) { return 0; }; SetPredMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting PredMap object. + + ///\brief \ref named-templ-param "Named parameter" for setting + ///the predecessor map. /// - ///\ref named-func-param "Named parameter" - ///for setting PredMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that stores the predecessor arcs of the nodes. template BfsWizard > predMap(const T &t) { @@ -1085,11 +1078,12 @@ static ReachedMap *createReachedMap(const Digraph &) { return 0; }; SetReachedMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting ReachedMap object. + + ///\brief \ref named-templ-param "Named parameter" for setting + ///the reached map. /// - /// \ref named-func-param "Named parameter" - ///for setting ReachedMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that indicates which nodes are reached. template BfsWizard > reachedMap(const T &t) { @@ -1103,11 +1097,13 @@ static DistMap *createDistMap(const Digraph &) { return 0; }; SetDistMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting DistMap object. + + ///\brief \ref named-templ-param "Named parameter" for setting + ///the distance map. /// - /// \ref named-func-param "Named parameter" - ///for setting DistMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that stores the distances of the nodes calculated + ///by the algorithm. template BfsWizard > distMap(const T &t) { @@ -1121,11 +1117,12 @@ static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; SetProcessedMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting ProcessedMap object. + + ///\brief \ref named-func-param "Named parameter" for setting + ///the processed map. /// - /// \ref named-func-param "Named parameter" - ///for setting ProcessedMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that indicates which nodes are processed. template BfsWizard > processedMap(const T &t) { @@ -1264,7 +1261,7 @@ /// \brief The type of the map that indicates which nodes are reached. /// /// The type of the map that indicates which nodes are reached. - /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; /// \brief Instantiates a ReachedMap. @@ -1425,8 +1422,8 @@ /// \name Execution Control /// The simplest way to execute the BFS algorithm is to use one of the /// member functions called \ref run(Node) "run()".\n - /// If you need more control on the execution, first you have to call - /// \ref init(), then you can add several source nodes with + /// If you need better control on the execution, you have to call + /// \ref init() first, then you can add several source nodes with /// \ref addSource(). Finally the actual path computation can be /// performed with one of the \ref start() functions. @@ -1735,7 +1732,7 @@ ///@{ - /// \brief Checks if a node is reached from the root(s). + /// \brief Checks if the given node is reached from the root(s). /// /// Returns \c true if \c v is reached from the root(s). /// diff -r 4a45c8808b33 -r 0977046c60d2 lemon/bits/map_extender.h --- a/lemon/bits/map_extender.h Sat Sep 26 07:16:22 2009 +0200 +++ b/lemon/bits/map_extender.h Sat Sep 26 07:21:54 2009 +0200 @@ -49,6 +49,8 @@ typedef typename Parent::Reference Reference; typedef typename Parent::ConstReference ConstReference; + typedef typename Parent::ReferenceMapTag ReferenceMapTag; + class MapIt; class ConstMapIt; @@ -191,6 +193,8 @@ typedef typename Parent::Reference Reference; typedef typename Parent::ConstReference ConstReference; + typedef typename Parent::ReferenceMapTag ReferenceMapTag; + class MapIt; class ConstMapIt; diff -r 4a45c8808b33 -r 0977046c60d2 lemon/circulation.h --- a/lemon/circulation.h Sat Sep 26 07:16:22 2009 +0200 +++ b/lemon/circulation.h Sat Sep 26 07:21:54 2009 +0200 @@ -72,7 +72,11 @@ /// The type of the map that stores the flow values. /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" /// concept. +#ifdef DOXYGEN + typedef GR::ArcMap FlowMap; +#else typedef typename Digraph::template ArcMap FlowMap; +#endif /// \brief Instantiates a FlowMap. /// @@ -87,9 +91,12 @@ /// /// The elevator type used by the algorithm. /// - /// \sa Elevator - /// \sa LinkedElevator + /// \sa Elevator, LinkedElevator +#ifdef DOXYGEN + typedef lemon::Elevator Elevator; +#else typedef lemon::Elevator Elevator; +#endif /// \brief Instantiates an Elevator. /// @@ -469,8 +476,8 @@ /// \name Execution Control /// The simplest way to execute the algorithm is to call \ref run().\n - /// If you need more control on the initial solution or the execution, - /// first you have to call one of the \ref init() functions, then + /// If you need better control on the initial solution or the execution, + /// you have to call one of the \ref init() functions first, then /// the \ref start() function. ///@{ diff -r 4a45c8808b33 -r 0977046c60d2 lemon/concepts/maps.h --- a/lemon/concepts/maps.h Sat Sep 26 07:16:22 2009 +0200 +++ b/lemon/concepts/maps.h Sat Sep 26 07:21:54 2009 +0200 @@ -182,7 +182,8 @@ template struct Constraints { - void constraints() { + typename enable_if::type + constraints() { checkConcept, _ReferenceMap >(); ref = m[key]; m[key] = val; diff -r 4a45c8808b33 -r 0977046c60d2 lemon/dfs.h --- a/lemon/dfs.h Sat Sep 26 07:16:22 2009 +0200 +++ b/lemon/dfs.h Sat Sep 26 07:21:54 2009 +0200 @@ -47,7 +47,7 @@ /// ///The type of the map that stores the predecessor ///arcs of the %DFS paths. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap PredMap; ///Instantiates a \c PredMap. @@ -62,7 +62,8 @@ ///The type of the map that indicates which nodes are processed. ///The type of the map that indicates which nodes are processed. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///By default it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a \c ProcessedMap. @@ -81,7 +82,7 @@ ///The type of the map that indicates which nodes are reached. ///The type of the map that indicates which nodes are reached. - ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; ///Instantiates a \c ReachedMap. @@ -96,7 +97,7 @@ ///The type of the map that stores the distances of the nodes. ///The type of the map that stores the distances of the nodes. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap DistMap; ///Instantiates a \c DistMap. @@ -224,7 +225,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///\c PredMap type. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetPredMap : public Dfs > { typedef Dfs > Create; @@ -244,7 +245,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///\c DistMap type. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetDistMap : public Dfs< Digraph, SetDistMapTraits > { typedef Dfs > Create; @@ -264,7 +265,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///\c ReachedMap type. - ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. template struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits > { typedef Dfs< Digraph, SetReachedMapTraits > Create; @@ -284,7 +285,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///\c ProcessedMap type. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits > { typedef Dfs< Digraph, SetProcessedMapTraits > Create; @@ -411,8 +412,8 @@ ///\name Execution Control ///The simplest way to execute the DFS algorithm is to use one of the ///member functions called \ref run(Node) "run()".\n - ///If you need more control on the execution, first you have to call - ///\ref init(), then you can add a source node with \ref addSource() + ///If you need better control on the execution, you have to call + ///\ref init() first, then you can add a source node with \ref addSource() ///and perform the actual computation with \ref start(). ///This procedure can be repeated if there are nodes that have not ///been reached. @@ -669,9 +670,9 @@ ///@{ - ///The DFS path to a node. + ///The DFS path to the given node. - ///Returns the DFS path to a node. + ///Returns the DFS path to the given node from the root(s). /// ///\warning \c t should be reached from the root(s). /// @@ -679,9 +680,9 @@ ///must be called before using this function. Path path(Node t) const { return Path(*G, *_pred, t); } - ///The distance of a node from the root(s). + ///The distance of the given node from the root(s). - ///Returns the distance of a node from the root(s). + ///Returns the distance of the given node from the root(s). /// ///\warning If node \c v is not reached from the root(s), then ///the return value of this function is undefined. @@ -690,7 +691,7 @@ ///must be called before using this function. int dist(Node v) const { return (*_dist)[v]; } - ///Returns the 'previous arc' of the %DFS tree for a node. + ///Returns the 'previous arc' of the %DFS tree for the given node. ///This function returns the 'previous arc' of the %DFS tree for the ///node \c v, i.e. it returns the last arc of a %DFS path from a @@ -698,21 +699,21 @@ ///root(s) or if \c v is a root. /// ///The %DFS tree used here is equal to the %DFS tree used in - ///\ref predNode(). + ///\ref predNode() and \ref predMap(). /// ///\pre Either \ref run(Node) "run()" or \ref init() ///must be called before using this function. Arc predArc(Node v) const { return (*_pred)[v];} - ///Returns the 'previous node' of the %DFS tree. + ///Returns the 'previous node' of the %DFS tree for the given node. ///This function returns the 'previous node' of the %DFS ///tree for the node \c v, i.e. it returns the last but one node - ///from a %DFS path from a root to \c v. It is \c INVALID + ///of a %DFS path from a root to \c v. It is \c INVALID ///if \c v is not reached from the root(s) or if \c v is a root. /// ///The %DFS tree used here is equal to the %DFS tree used in - ///\ref predArc(). + ///\ref predArc() and \ref predMap(). /// ///\pre Either \ref run(Node) "run()" or \ref init() ///must be called before using this function. @@ -733,13 +734,13 @@ ///predecessor arcs. /// ///Returns a const reference to the node map that stores the predecessor - ///arcs, which form the DFS tree. + ///arcs, which form the DFS tree (forest). /// ///\pre Either \ref run(Node) "run()" or \ref init() ///must be called before using this function. const PredMap &predMap() const { return *_pred;} - ///Checks if a node is reached from the root(s). + ///Checks if the given node. node is reached from the root(s). ///Returns \c true if \c v is reached from the root(s). /// @@ -765,7 +766,7 @@ /// ///The type of the map that stores the predecessor ///arcs of the %DFS paths. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap PredMap; ///Instantiates a PredMap. @@ -780,7 +781,7 @@ ///The type of the map that indicates which nodes are processed. ///The type of the map that indicates which nodes are processed. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a ProcessedMap. @@ -800,7 +801,7 @@ ///The type of the map that indicates which nodes are reached. ///The type of the map that indicates which nodes are reached. - ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; ///Instantiates a ReachedMap. @@ -815,7 +816,7 @@ ///The type of the map that stores the distances of the nodes. ///The type of the map that stores the distances of the nodes. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap DistMap; ///Instantiates a DistMap. @@ -830,18 +831,14 @@ ///The type of the DFS paths. ///The type of the DFS paths. - ///It must meet the \ref concepts::Path "Path" concept. + ///It must conform to the \ref concepts::Path "Path" concept. typedef lemon::Path Path; }; /// Default traits class used by DfsWizard - /// To make it easier to use Dfs algorithm - /// we have created a wizard class. - /// This \ref DfsWizard class needs default traits, - /// as well as the \ref Dfs class. - /// The \ref DfsWizardBase is a class to be the default traits of the - /// \ref DfsWizard class. + /// Default traits class used by DfsWizard. + /// \tparam GR The type of the digraph. template class DfsWizardBase : public DfsWizardDefaultTraits { @@ -869,7 +866,7 @@ public: /// Constructor. - /// This constructor does not require parameters, therefore it initiates + /// This constructor does not require parameters, it initiates /// all of the attributes to \c 0. DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {} @@ -899,7 +896,6 @@ { typedef TR Base; - ///The type of the digraph the algorithm runs on. typedef typename TR::Digraph Digraph; typedef typename Digraph::Node Node; @@ -907,16 +903,10 @@ typedef typename Digraph::Arc Arc; typedef typename Digraph::OutArcIt OutArcIt; - ///\brief The type of the map that stores the predecessor - ///arcs of the DFS paths. typedef typename TR::PredMap PredMap; - ///\brief The type of the map that stores the distances of the nodes. typedef typename TR::DistMap DistMap; - ///\brief The type of the map that indicates which nodes are reached. typedef typename TR::ReachedMap ReachedMap; - ///\brief The type of the map that indicates which nodes are processed. typedef typename TR::ProcessedMap ProcessedMap; - ///The type of the DFS paths typedef typename TR::Path Path; public: @@ -999,11 +989,12 @@ static PredMap *createPredMap(const Digraph &) { return 0; }; SetPredMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting PredMap object. + + ///\brief \ref named-templ-param "Named parameter" for setting + ///the predecessor map. /// - ///\ref named-func-param "Named parameter" - ///for setting PredMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that stores the predecessor arcs of the nodes. template DfsWizard > predMap(const T &t) { @@ -1017,11 +1008,12 @@ static ReachedMap *createReachedMap(const Digraph &) { return 0; }; SetReachedMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting ReachedMap object. + + ///\brief \ref named-templ-param "Named parameter" for setting + ///the reached map. /// - /// \ref named-func-param "Named parameter" - ///for setting ReachedMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that indicates which nodes are reached. template DfsWizard > reachedMap(const T &t) { @@ -1035,11 +1027,13 @@ static DistMap *createDistMap(const Digraph &) { return 0; }; SetDistMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting DistMap object. + + ///\brief \ref named-templ-param "Named parameter" for setting + ///the distance map. /// - /// \ref named-func-param "Named parameter" - ///for setting DistMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that stores the distances of the nodes calculated + ///by the algorithm. template DfsWizard > distMap(const T &t) { @@ -1053,11 +1047,12 @@ static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; SetProcessedMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting ProcessedMap object. + + ///\brief \ref named-func-param "Named parameter" for setting + ///the processed map. /// - /// \ref named-func-param "Named parameter" - ///for setting ProcessedMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that indicates which nodes are processed. template DfsWizard > processedMap(const T &t) { @@ -1208,7 +1203,7 @@ /// \brief The type of the map that indicates which nodes are reached. /// /// The type of the map that indicates which nodes are reached. - /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; /// \brief Instantiates a ReachedMap. @@ -1369,8 +1364,8 @@ /// \name Execution Control /// The simplest way to execute the DFS algorithm is to use one of the /// member functions called \ref run(Node) "run()".\n - /// If you need more control on the execution, first you have to call - /// \ref init(), then you can add a source node with \ref addSource() + /// If you need better control on the execution, you have to call + /// \ref init() first, then you can add a source node with \ref addSource() /// and perform the actual computation with \ref start(). /// This procedure can be repeated if there are nodes that have not /// been reached. @@ -1620,7 +1615,7 @@ ///@{ - /// \brief Checks if a node is reached from the root(s). + /// \brief Checks if the given node is reached from the root(s). /// /// Returns \c true if \c v is reached from the root(s). /// diff -r 4a45c8808b33 -r 0977046c60d2 lemon/dijkstra.h --- a/lemon/dijkstra.h Sat Sep 26 07:16:22 2009 +0200 +++ b/lemon/dijkstra.h Sat Sep 26 07:21:54 2009 +0200 @@ -70,9 +70,9 @@ ///The type of the map that stores the arc lengths. ///The type of the map that stores the arc lengths. - ///It must meet the \ref concepts::ReadMap "ReadMap" concept. + ///It must conform to the \ref concepts::ReadMap "ReadMap" concept. typedef LEN LengthMap; - ///The type of the length of the arcs. + ///The type of the arc lengths. typedef typename LEN::Value Value; /// Operation traits for %Dijkstra algorithm. @@ -116,7 +116,7 @@ /// ///The type of the map that stores the predecessor ///arcs of the shortest paths. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap PredMap; ///Instantiates a \c PredMap. @@ -131,7 +131,7 @@ ///The type of the map that indicates which nodes are processed. ///The type of the map that indicates which nodes are processed. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a \c ProcessedMap. @@ -151,7 +151,7 @@ ///The type of the map that stores the distances of the nodes. ///The type of the map that stores the distances of the nodes. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap DistMap; ///Instantiates a \c DistMap. @@ -169,6 +169,10 @@ /// \ingroup shortest_path ///This class provides an efficient implementation of the %Dijkstra algorithm. /// + ///The %Dijkstra algorithm solves the single-source shortest path problem + ///when all arc lengths are non-negative. If there are negative lengths, + ///the BellmanFord algorithm should be used instead. + /// ///The arc lengths are passed to the algorithm using a ///\ref concepts::ReadMap "ReadMap", ///so it is easy to change it to any kind of length. @@ -201,7 +205,7 @@ ///The type of the digraph the algorithm runs on. typedef typename TR::Digraph Digraph; - ///The type of the length of the arcs. + ///The type of the arc lengths. typedef typename TR::LengthMap::Value Value; ///The type of the map that stores the arc lengths. typedef typename TR::LengthMap LengthMap; @@ -304,7 +308,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///\c PredMap type. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetPredMap : public Dijkstra< Digraph, LengthMap, SetPredMapTraits > { @@ -325,7 +329,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///\c DistMap type. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetDistMap : public Dijkstra< Digraph, LengthMap, SetDistMapTraits > { @@ -346,7 +350,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///\c ProcessedMap type. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetProcessedMap : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits > { @@ -443,6 +447,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///\c OperationTraits type. + /// For more information see \ref DijkstraDefaultOperationTraits. template struct SetOperationTraits : public Dijkstra > { @@ -584,8 +589,8 @@ ///\name Execution Control ///The simplest way to execute the %Dijkstra algorithm is to use ///one of the member functions called \ref run(Node) "run()".\n - ///If you need more control on the execution, first you have to call - ///\ref init(), then you can add several source nodes with + ///If you need better control on the execution, you have to call + ///\ref init() first, then you can add several source nodes with ///\ref addSource(). Finally the actual path computation can be ///performed with one of the \ref start() functions. @@ -801,14 +806,14 @@ ///\name Query Functions ///The results of the %Dijkstra algorithm can be obtained using these ///functions.\n - ///Either \ref run(Node) "run()" or \ref start() should be called + ///Either \ref run(Node) "run()" or \ref init() should be called ///before using them. ///@{ - ///The shortest path to a node. + ///The shortest path to the given node. - ///Returns the shortest path to a node. + ///Returns the shortest path to the given node from the root(s). /// ///\warning \c t should be reached from the root(s). /// @@ -816,9 +821,9 @@ ///must be called before using this function. Path path(Node t) const { return Path(*G, *_pred, t); } - ///The distance of a node from the root(s). + ///The distance of the given node from the root(s). - ///Returns the distance of a node from the root(s). + ///Returns the distance of the given node from the root(s). /// ///\warning If node \c v is not reached from the root(s), then ///the return value of this function is undefined. @@ -827,29 +832,31 @@ ///must be called before using this function. Value dist(Node v) const { return (*_dist)[v]; } - ///Returns the 'previous arc' of the shortest path tree for a node. - + ///\brief Returns the 'previous arc' of the shortest path tree for + ///the given node. + /// ///This function returns the 'previous arc' of the shortest path ///tree for the node \c v, i.e. it returns the last arc of a ///shortest path from a root to \c v. It is \c INVALID if \c v ///is not reached from the root(s) or if \c v is a root. /// ///The shortest path tree used here is equal to the shortest path - ///tree used in \ref predNode(). + ///tree used in \ref predNode() and \ref predMap(). /// ///\pre Either \ref run(Node) "run()" or \ref init() ///must be called before using this function. Arc predArc(Node v) const { return (*_pred)[v]; } - ///Returns the 'previous node' of the shortest path tree for a node. - + ///\brief Returns the 'previous node' of the shortest path tree for + ///the given node. + /// ///This function returns the 'previous node' of the shortest path ///tree for the node \c v, i.e. it returns the last but one node - ///from a shortest path from a root to \c v. It is \c INVALID + ///of a shortest path from a root to \c v. It is \c INVALID ///if \c v is not reached from the root(s) or if \c v is a root. /// ///The shortest path tree used here is equal to the shortest path - ///tree used in \ref predArc(). + ///tree used in \ref predArc() and \ref predMap(). /// ///\pre Either \ref run(Node) "run()" or \ref init() ///must be called before using this function. @@ -870,13 +877,13 @@ ///predecessor arcs. /// ///Returns a const reference to the node map that stores the predecessor - ///arcs, which form the shortest path tree. + ///arcs, which form the shortest path tree (forest). /// ///\pre Either \ref run(Node) "run()" or \ref init() ///must be called before using this function. const PredMap &predMap() const { return *_pred;} - ///Checks if a node is reached from the root(s). + ///Checks if the given node is reached from the root(s). ///Returns \c true if \c v is reached from the root(s). /// @@ -895,9 +902,9 @@ bool processed(Node v) const { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; } - ///The current distance of a node from the root(s). + ///The current distance of the given node from the root(s). - ///Returns the current distance of a node from the root(s). + ///Returns the current distance of the given node from the root(s). ///It may be decreased in the following processes. /// ///\pre Either \ref run(Node) "run()" or \ref init() @@ -924,9 +931,9 @@ ///The type of the map that stores the arc lengths. ///The type of the map that stores the arc lengths. - ///It must meet the \ref concepts::ReadMap "ReadMap" concept. + ///It must conform to the \ref concepts::ReadMap "ReadMap" concept. typedef LEN LengthMap; - ///The type of the length of the arcs. + ///The type of the arc lengths. typedef typename LEN::Value Value; /// Operation traits for Dijkstra algorithm. @@ -973,7 +980,7 @@ /// ///The type of the map that stores the predecessor ///arcs of the shortest paths. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap PredMap; ///Instantiates a PredMap. @@ -988,7 +995,7 @@ ///The type of the map that indicates which nodes are processed. ///The type of the map that indicates which nodes are processed. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a ProcessedMap. @@ -1008,7 +1015,7 @@ ///The type of the map that stores the distances of the nodes. ///The type of the map that stores the distances of the nodes. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap DistMap; ///Instantiates a DistMap. @@ -1023,18 +1030,15 @@ ///The type of the shortest paths. ///The type of the shortest paths. - ///It must meet the \ref concepts::Path "Path" concept. + ///It must conform to the \ref concepts::Path "Path" concept. typedef lemon::Path Path; }; /// Default traits class used by DijkstraWizard - /// To make it easier to use Dijkstra algorithm - /// we have created a wizard class. - /// This \ref DijkstraWizard class needs default traits, - /// as well as the \ref Dijkstra class. - /// The \ref DijkstraWizardBase is a class to be the default traits of the - /// \ref DijkstraWizard class. + /// Default traits class used by DijkstraWizard. + /// \tparam GR The type of the digraph. + /// \tparam LEN The type of the length map. template class DijkstraWizardBase : public DijkstraWizardDefaultTraits { @@ -1093,7 +1097,6 @@ { typedef TR Base; - ///The type of the digraph the algorithm runs on. typedef typename TR::Digraph Digraph; typedef typename Digraph::Node Node; @@ -1101,20 +1104,12 @@ typedef typename Digraph::Arc Arc; typedef typename Digraph::OutArcIt OutArcIt; - ///The type of the map that stores the arc lengths. typedef typename TR::LengthMap LengthMap; - ///The type of the length of the arcs. typedef typename LengthMap::Value Value; - ///\brief The type of the map that stores the predecessor - ///arcs of the shortest paths. typedef typename TR::PredMap PredMap; - ///The type of the map that stores the distances of the nodes. typedef typename TR::DistMap DistMap; - ///The type of the map that indicates which nodes are processed. typedef typename TR::ProcessedMap ProcessedMap; - ///The type of the shortest paths typedef typename TR::Path Path; - ///The heap type used by the dijkstra algorithm. typedef typename TR::Heap Heap; public: @@ -1186,11 +1181,12 @@ static PredMap *createPredMap(const Digraph &) { return 0; }; SetPredMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting PredMap object. + + ///\brief \ref named-templ-param "Named parameter" for setting + ///the predecessor map. /// - ///\ref named-func-param "Named parameter" - ///for setting PredMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that stores the predecessor arcs of the nodes. template DijkstraWizard > predMap(const T &t) { @@ -1204,11 +1200,13 @@ static DistMap *createDistMap(const Digraph &) { return 0; }; SetDistMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting DistMap object. + + ///\brief \ref named-templ-param "Named parameter" for setting + ///the distance map. /// - ///\ref named-func-param "Named parameter" - ///for setting DistMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that stores the distances of the nodes calculated + ///by the algorithm. template DijkstraWizard > distMap(const T &t) { @@ -1222,11 +1220,12 @@ static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; SetProcessedMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting ProcessedMap object. + + ///\brief \ref named-func-param "Named parameter" for setting + ///the processed map. /// - /// \ref named-func-param "Named parameter" - ///for setting ProcessedMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that indicates which nodes are processed. template DijkstraWizard > processedMap(const T &t) { @@ -1239,6 +1238,7 @@ typedef T Path; SetPathBase(const TR &b) : TR(b) {} }; + ///\brief \ref named-func-param "Named parameter" ///for getting the shortest path to the target node. /// diff -r 4a45c8808b33 -r 0977046c60d2 lemon/dim2.h --- a/lemon/dim2.h Sat Sep 26 07:16:22 2009 +0200 +++ b/lemon/dim2.h Sat Sep 26 07:21:54 2009 +0200 @@ -21,16 +21,9 @@ #include -///\ingroup misc +///\ingroup geomdat ///\file ///\brief A simple two dimensional vector and a bounding box implementation -/// -/// The class \ref lemon::dim2::Point "dim2::Point" implements -/// a two dimensional vector with the usual operations. -/// -/// The class \ref lemon::dim2::Box "dim2::Box" can be used to determine -/// the rectangular bounding box of a set of -/// \ref lemon::dim2::Point "dim2::Point"'s. namespace lemon { @@ -40,7 +33,7 @@ ///tools for handling two dimensional coordinates namespace dim2 { - /// \addtogroup misc + /// \addtogroup geomdat /// @{ /// Two dimensional vector (plain vector) diff -r 4a45c8808b33 -r 0977046c60d2 lemon/gomory_hu.h --- a/lemon/gomory_hu.h Sat Sep 26 07:16:22 2009 +0200 +++ b/lemon/gomory_hu.h Sat Sep 26 07:21:54 2009 +0200 @@ -359,10 +359,10 @@ /// This example counts the nodes in the minimum cut separating \c s from /// \c t. /// \code - /// GomoruHu gom(g, capacities); + /// GomoryHu gom(g, capacities); /// gom.run(); /// int cnt=0; - /// for(GomoruHu::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt; + /// for(GomoryHu::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt; /// \endcode class MinCutNodeIt { @@ -456,10 +456,10 @@ /// This example computes the value of the minimum cut separating \c s from /// \c t. /// \code - /// GomoruHu gom(g, capacities); + /// GomoryHu gom(g, capacities); /// gom.run(); /// int value=0; - /// for(GomoruHu::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e) + /// for(GomoryHu::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e) /// value+=capacities[e]; /// \endcode /// The result will be the same as the value returned by diff -r 4a45c8808b33 -r 0977046c60d2 lemon/maps.h --- a/lemon/maps.h Sat Sep 26 07:16:22 2009 +0200 +++ b/lemon/maps.h Sat Sep 26 07:21:54 2009 +0200 @@ -56,7 +56,7 @@ /// its type definitions, or if you have to provide a writable map, /// but data written to it is not required (i.e. it will be sent to /// /dev/null). - /// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + /// It conforms to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. /// /// \sa ConstMap template @@ -89,7 +89,7 @@ /// value to each key. /// /// In other aspects it is equivalent to \c NullMap. - /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap" + /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap" /// concept, but it absorbs the data written to it. /// /// The simplest way of using this map is through the constMap() @@ -158,7 +158,7 @@ /// value to each key. /// /// In other aspects it is equivalent to \c NullMap. - /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap" + /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap" /// concept, but it absorbs the data written to it. /// /// The simplest way of using this map is through the constMap() @@ -232,7 +232,7 @@ /// values to integer keys from the range [0..size-1]. /// It can be used with some data structures, for example /// \c UnionFind, \c BinHeap, when the used items are small - /// integers. This map conforms the \ref concepts::ReferenceMap + /// integers. This map conforms to the \ref concepts::ReferenceMap /// "ReferenceMap" concept. /// /// The simplest way of using this map is through the rangeMap() @@ -340,7 +340,7 @@ /// that you can specify a default value for the keys that are not /// stored actually. This value can be different from the default /// contructed value (i.e. \c %Value()). - /// This type conforms the \ref concepts::ReferenceMap "ReferenceMap" + /// This type conforms to the \ref concepts::ReferenceMap "ReferenceMap" /// concept. /// /// This map is useful if a default value should be assigned to most of @@ -706,7 +706,7 @@ /// "readable map" to another type using the default conversion. /// The \c Key type of it is inherited from \c M and the \c Value /// type is \c V. - /// This type conforms the \ref concepts::ReadMap "ReadMap" concept. + /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept. /// /// The simplest way of using this map is through the convertMap() /// function. @@ -1789,11 +1789,11 @@ /// order of Dfs algorithm, as the following examples show. /// \code /// std::vector v; - /// dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run(); + /// dfs(g).processedMap(loggerBoolMap(std::back_inserter(v))).run(s); /// \endcode /// \code /// std::vector v(countNodes(g)); - /// dfs(g,s).processedMap(loggerBoolMap(v.begin())).run(); + /// dfs(g).processedMap(loggerBoolMap(v.begin())).run(s); /// \endcode /// /// \note The container of the iterator must contain enough space @@ -1825,7 +1825,7 @@ /// Using this map you get access (i.e. can read) the inner id values of /// the items stored in the graph, which is returned by the \c id() /// function of the graph. This map can be inverted with its member - /// class \c InverseMap or with the \c operator() member. + /// class \c InverseMap or with the \c operator()() member. /// /// \tparam GR The graph type. /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or @@ -1865,9 +1865,11 @@ public: - /// \brief This class represents the inverse of its owner (IdMap). + /// \brief The inverse map type of IdMap. /// - /// This class represents the inverse of its owner (IdMap). + /// The inverse map type of IdMap. The subscript operator gives back + /// an item by its id. + /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept. /// \see inverse() class InverseMap { public: @@ -1882,9 +1884,9 @@ /// Constructor for creating an id-to-item map. explicit InverseMap(const IdMap& map) : _graph(map._graph) {} - /// \brief Gives back the given item from its id. + /// \brief Gives back an item by its id. /// - /// Gives back the given item from its id. + /// Gives back an item by its id. Item operator[](int id) const { return _graph->fromId(id, Item());} private: @@ -1897,14 +1899,31 @@ InverseMap inverse() const { return InverseMap(*_graph);} }; + /// \brief Returns an \c IdMap class. + /// + /// This function just returns an \c IdMap class. + /// \relates IdMap + template + inline IdMap idMap(const GR& graph) { + return IdMap(graph); + } /// \brief General cross reference graph map type. /// This class provides simple invertable graph maps. /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap) /// and if a key is set to a new value, then stores it in the inverse map. - /// The values of the map can be accessed - /// with stl compatible forward iterator. + /// The graph items can be accessed by their values either using + /// \c InverseMap or \c operator()(), and the values of the map can be + /// accessed with an STL compatible forward iterator (\c ValueIt). + /// + /// This map is intended to be used when all associated values are + /// different (the map is actually invertable) or there are only a few + /// items with the same value. + /// Otherwise consider to use \c IterableValueMap, which is more + /// suitable and more efficient for such cases. It provides iterators + /// to traverse the items with the same associated value, however + /// it does not have \c InverseMap. /// /// This type is not reference map, so it cannot be modified with /// the subscript operator. @@ -1945,56 +1964,66 @@ /// \brief Forward iterator for values. /// - /// This iterator is an stl compatible forward + /// This iterator is an STL compatible forward /// iterator on the values of the map. The values can /// be accessed in the [beginValue, endValue) range. /// They are considered with multiplicity, so each value is /// traversed for each item it is assigned to. - class ValueIterator + class ValueIt : public std::iterator { friend class CrossRefMap; private: - ValueIterator(typename Container::const_iterator _it) + ValueIt(typename Container::const_iterator _it) : it(_it) {} public: - ValueIterator() {} - - ValueIterator& operator++() { ++it; return *this; } - ValueIterator operator++(int) { - ValueIterator tmp(*this); + /// Constructor + ValueIt() {} + + /// \e + ValueIt& operator++() { ++it; return *this; } + /// \e + ValueIt operator++(int) { + ValueIt tmp(*this); operator++(); return tmp; } + /// \e const Value& operator*() const { return it->first; } + /// \e const Value* operator->() const { return &(it->first); } - bool operator==(ValueIterator jt) const { return it == jt.it; } - bool operator!=(ValueIterator jt) const { return it != jt.it; } + /// \e + bool operator==(ValueIt jt) const { return it == jt.it; } + /// \e + bool operator!=(ValueIt jt) const { return it != jt.it; } private: typename Container::const_iterator it; }; + + /// Alias for \c ValueIt + typedef ValueIt ValueIterator; /// \brief Returns an iterator to the first value. /// - /// Returns an stl compatible iterator to the + /// Returns an STL compatible iterator to the /// first value of the map. The values of the /// map can be accessed in the [beginValue, endValue) /// range. - ValueIterator beginValue() const { - return ValueIterator(_inv_map.begin()); + ValueIt beginValue() const { + return ValueIt(_inv_map.begin()); } /// \brief Returns an iterator after the last value. /// - /// Returns an stl compatible iterator after the + /// Returns an STL compatible iterator after the /// last value of the map. The values of the /// map can be accessed in the [beginValue, endValue) /// range. - ValueIterator endValue() const { - return ValueIterator(_inv_map.end()); + ValueIt endValue() const { + return ValueIt(_inv_map.end()); } /// \brief Sets the value associated with the given key. @@ -2032,6 +2061,14 @@ typename Container::const_iterator it = _inv_map.find(val); return it != _inv_map.end() ? it->second : INVALID; } + + /// \brief Returns the number of items with the given value. + /// + /// This function returns the number of items with the given value + /// associated with it. + int count(const Value &val) const { + return _inv_map.count(val); + } protected: @@ -2082,10 +2119,12 @@ public: - /// \brief The inverse map type. + /// \brief The inverse map type of CrossRefMap. /// - /// The inverse of this map. The subscript operator of the map - /// gives back the item that was last assigned to the value. + /// The inverse map type of CrossRefMap. The subscript operator gives + /// back an item by its value. + /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept. + /// \see inverse() class InverseMap { public: /// \brief Constructor @@ -2112,20 +2151,20 @@ const CrossRefMap& _inverted; }; - /// \brief It gives back the read-only inverse map. + /// \brief Gives back the inverse of the map. /// - /// It gives back the read-only inverse map. + /// Gives back the inverse of the CrossRefMap. InverseMap inverse() const { return InverseMap(*this); } }; - /// \brief Provides continuous and unique ID for the + /// \brief Provides continuous and unique id for the /// items of a graph. /// /// RangeIdMap provides a unique and continuous - /// ID for each item of a given type (\c Node, \c Arc or + /// id for each item of a given type (\c Node, \c Arc or /// \c Edge) in a graph. This id is /// - \b unique: different items get different ids, /// - \b continuous: the range of the ids is the set of integers @@ -2136,7 +2175,7 @@ /// Thus this id is not (necessarily) the same as what can get using /// the \c id() function of the graph or \ref IdMap. /// This map can be inverted with its member class \c InverseMap, - /// or with the \c operator() member. + /// or with the \c operator()() member. /// /// \tparam GR The graph type. /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or @@ -2264,16 +2303,16 @@ _inv_map[pi] = q; } - /// \brief Gives back the \e RangeId of the item + /// \brief Gives back the \e range \e id of the item /// - /// Gives back the \e RangeId of the item. + /// Gives back the \e range \e id of the item. int operator[](const Item& item) const { return Map::operator[](item); } - /// \brief Gives back the item belonging to a \e RangeId + /// \brief Gives back the item belonging to a \e range \e id /// - /// Gives back the item belonging to a \e RangeId. + /// Gives back the item belonging to the given \e range \e id. Item operator()(int id) const { return _inv_map[id]; } @@ -2287,7 +2326,9 @@ /// \brief The inverse map type of RangeIdMap. /// - /// The inverse map type of RangeIdMap. + /// The inverse map type of RangeIdMap. The subscript operator gives + /// back an item by its \e range \e id. + /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept. class InverseMap { public: /// \brief Constructor @@ -2305,7 +2346,7 @@ /// \brief Subscript operator. /// /// Subscript operator. It gives back the item - /// that the descriptor currently belongs to. + /// that the given \e range \e id currently belongs to. Value operator[](const Key& key) const { return _inverted(key); } @@ -2323,18 +2364,27 @@ /// \brief Gives back the inverse of the map. /// - /// Gives back the inverse of the map. + /// Gives back the inverse of the RangeIdMap. const InverseMap inverse() const { return InverseMap(*this); } }; + /// \brief Returns a \c RangeIdMap class. + /// + /// This function just returns an \c RangeIdMap class. + /// \relates RangeIdMap + template + inline RangeIdMap rangeIdMap(const GR& graph) { + return RangeIdMap(graph); + } + /// \brief Dynamic iterable \c bool map. /// /// This class provides a special graph map type which can store a /// \c bool value for graph items (\c Node, \c Arc or \c Edge). /// For both \c true and \c false values it is possible to iterate on - /// the keys. + /// the keys mapped to the value. /// /// This type is a reference map, so it can be modified with the /// subscript operator. @@ -2703,6 +2753,11 @@ /// For each non-negative value it is possible to iterate on the keys /// mapped to the value. /// + /// This map is intended to be used with small integer values, for which + /// it is efficient, and supports iteration only for non-negative values. + /// If you need large values and/or iteration for negative integers, + /// consider to use \ref IterableValueMap instead. + /// /// This type is a reference map, so it can be modified with the /// subscript operator. /// @@ -2984,15 +3039,17 @@ /// \brief Dynamic iterable map for comparable values. /// - /// This class provides a special graph map type which can store an + /// This class provides a special graph map type which can store a /// comparable value for graph items (\c Node, \c Arc or \c Edge). /// For each value it is possible to iterate on the keys mapped to - /// the value. + /// the value (\c ItemIt), and the values of the map can be accessed + /// with an STL compatible forward iterator (\c ValueIt). + /// The map stores a linked list for each value, which contains + /// the items mapped to the value, and the used values are stored + /// in balanced binary tree (\c std::map). /// - /// The map stores for each value a linked list with - /// the items which mapped to the value, and the values are stored - /// in balanced binary tree. The values of the map can be accessed - /// with stl compatible forward iterator. + /// \ref IterableBoolMap and \ref IterableIntMap are similar classes + /// specialized for \c bool and \c int values, respectively. /// /// This type is not reference map, so it cannot be modified with /// the subscript operator. @@ -3071,31 +3128,38 @@ /// \brief Forward iterator for values. /// - /// This iterator is an stl compatible forward + /// This iterator is an STL compatible forward /// iterator on the values of the map. The values can /// be accessed in the [beginValue, endValue) range. - class ValueIterator + class ValueIt : public std::iterator { friend class IterableValueMap; private: - ValueIterator(typename std::map::const_iterator _it) + ValueIt(typename std::map::const_iterator _it) : it(_it) {} public: - ValueIterator() {} - - ValueIterator& operator++() { ++it; return *this; } - ValueIterator operator++(int) { - ValueIterator tmp(*this); + /// Constructor + ValueIt() {} + + /// \e + ValueIt& operator++() { ++it; return *this; } + /// \e + ValueIt operator++(int) { + ValueIt tmp(*this); operator++(); return tmp; } + /// \e const Value& operator*() const { return it->first; } + /// \e const Value* operator->() const { return &(it->first); } - bool operator==(ValueIterator jt) const { return it == jt.it; } - bool operator!=(ValueIterator jt) const { return it != jt.it; } + /// \e + bool operator==(ValueIt jt) const { return it == jt.it; } + /// \e + bool operator!=(ValueIt jt) const { return it != jt.it; } private: typename std::map::const_iterator it; @@ -3103,22 +3167,22 @@ /// \brief Returns an iterator to the first value. /// - /// Returns an stl compatible iterator to the + /// Returns an STL compatible iterator to the /// first value of the map. The values of the /// map can be accessed in the [beginValue, endValue) /// range. - ValueIterator beginValue() const { - return ValueIterator(_first.begin()); + ValueIt beginValue() const { + return ValueIt(_first.begin()); } /// \brief Returns an iterator after the last value. /// - /// Returns an stl compatible iterator after the + /// Returns an STL compatible iterator after the /// last value of the map. The values of the /// map can be accessed in the [beginValue, endValue) /// range. - ValueIterator endValue() const { - return ValueIterator(_first.end()); + ValueIt endValue() const { + return ValueIt(_first.end()); } /// \brief Set operation of the map. @@ -3236,9 +3300,9 @@ class SourceMap { public: - ///\e + /// The key type (the \c Arc type of the digraph). typedef typename GR::Arc Key; - ///\e + /// The value type (the \c Node type of the digraph). typedef typename GR::Node Value; /// \brief Constructor @@ -3277,9 +3341,9 @@ class TargetMap { public: - ///\e + /// The key type (the \c Arc type of the digraph). typedef typename GR::Arc Key; - ///\e + /// The value type (the \c Node type of the digraph). typedef typename GR::Node Value; /// \brief Constructor @@ -3319,8 +3383,10 @@ class ForwardMap { public: + /// The key type (the \c Edge type of the digraph). + typedef typename GR::Edge Key; + /// The value type (the \c Arc type of the digraph). typedef typename GR::Arc Value; - typedef typename GR::Edge Key; /// \brief Constructor /// @@ -3359,8 +3425,10 @@ class BackwardMap { public: + /// The key type (the \c Edge type of the digraph). + typedef typename GR::Edge Key; + /// The value type (the \c Arc type of the digraph). typedef typename GR::Arc Value; - typedef typename GR::Edge Key; /// \brief Constructor /// diff -r 4a45c8808b33 -r 0977046c60d2 lemon/min_cost_arborescence.h --- a/lemon/min_cost_arborescence.h Sat Sep 26 07:16:22 2009 +0200 +++ b/lemon/min_cost_arborescence.h Sat Sep 26 07:21:54 2009 +0200 @@ -488,8 +488,8 @@ /// \name Execution Control /// The simplest way to execute the algorithm is to use /// one of the member functions called \c run(...). \n - /// If you need more control on the execution, - /// first you must call \ref init(), then you can add several + /// If you need better control on the execution, + /// you have to call \ref init() first, then you can add several /// source nodes with \ref addSource(). /// Finally \ref start() will perform the arborescence /// computation. diff -r 4a45c8808b33 -r 0977046c60d2 lemon/preflow.h --- a/lemon/preflow.h Sat Sep 26 07:16:22 2009 +0200 +++ b/lemon/preflow.h Sat Sep 26 07:21:54 2009 +0200 @@ -52,7 +52,11 @@ /// /// The type of the map that stores the flow values. /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. +#ifdef DOXYGEN + typedef GR::ArcMap FlowMap; +#else typedef typename Digraph::template ArcMap FlowMap; +#endif /// \brief Instantiates a FlowMap. /// @@ -67,9 +71,12 @@ /// /// The elevator type used by Preflow algorithm. /// - /// \sa Elevator - /// \sa LinkedElevator - typedef LinkedElevator Elevator; + /// \sa Elevator, LinkedElevator +#ifdef DOXYGEN + typedef lemon::Elevator Elevator; +#else + typedef lemon::Elevator Elevator; +#endif /// \brief Instantiates an Elevator. /// @@ -391,8 +398,8 @@ /// \name Execution Control /// The simplest way to execute the preflow algorithm is to use /// \ref run() or \ref runMinCut().\n - /// If you need more control on the initial solution or the execution, - /// first you have to call one of the \ref init() functions, then + /// If you need better control on the initial solution or the execution, + /// you have to call one of the \ref init() functions first, then /// \ref startFirstPhase() and if you need it \ref startSecondPhase(). ///@{ diff -r 4a45c8808b33 -r 0977046c60d2 test/maps_test.cc --- a/test/maps_test.cc Sat Sep 26 07:16:22 2009 +0200 +++ b/test/maps_test.cc Sat Sep 26 07:21:54 2009 +0200 @@ -22,7 +22,10 @@ #include #include #include +#include #include +#include +#include #include "test_tools.h" @@ -61,6 +64,12 @@ typedef ReadWriteMap BoolWriteMap; typedef ReferenceMap BoolRefMap; +template +void compareMap(const Map1& map1, const Map2& map2, ItemIt it) { + for (; it != INVALID; ++it) + check(map1[it] == map2[it], "The maps are not equal"); +} + int main() { // Map concepts @@ -329,6 +338,10 @@ // LoggerBoolMap { typedef std::vector vec; + checkConcept, LoggerBoolMap >(); + checkConcept, + LoggerBoolMap > >(); + vec v1; vec v2(10); LoggerBoolMap > @@ -348,6 +361,222 @@ for ( LoggerBoolMap::Iterator it = map2.begin(); it != map2.end(); ++it ) check(v1[i++] == *it, "Something is wrong with LoggerBoolMap"); + + typedef ListDigraph Graph; + DIGRAPH_TYPEDEFS(Graph); + Graph gr; + + Node n0 = gr.addNode(); + Node n1 = gr.addNode(); + Node n2 = gr.addNode(); + Node n3 = gr.addNode(); + + gr.addArc(n3, n0); + gr.addArc(n3, n2); + gr.addArc(n0, n2); + gr.addArc(n2, n1); + gr.addArc(n0, n1); + + { + std::vector v; + dfs(gr).processedMap(loggerBoolMap(std::back_inserter(v))).run(); + + check(v.size()==4 && v[0]==n1 && v[1]==n2 && v[2]==n0 && v[3]==n3, + "Something is wrong with LoggerBoolMap"); + } + { + std::vector v(countNodes(gr)); + dfs(gr).processedMap(loggerBoolMap(v.begin())).run(); + + check(v.size()==4 && v[0]==n1 && v[1]==n2 && v[2]==n0 && v[3]==n3, + "Something is wrong with LoggerBoolMap"); + } + } + + // IdMap, RangeIdMap + { + typedef ListDigraph Graph; + DIGRAPH_TYPEDEFS(Graph); + + checkConcept, IdMap >(); + checkConcept, IdMap >(); + checkConcept, RangeIdMap >(); + checkConcept, RangeIdMap >(); + + Graph gr; + IdMap nmap(gr); + IdMap amap(gr); + RangeIdMap nrmap(gr); + RangeIdMap armap(gr); + + Node n0 = gr.addNode(); + Node n1 = gr.addNode(); + Node n2 = gr.addNode(); + + Arc a0 = gr.addArc(n0, n1); + Arc a1 = gr.addArc(n0, n2); + Arc a2 = gr.addArc(n2, n1); + Arc a3 = gr.addArc(n2, n0); + + check(nmap[n0] == gr.id(n0) && nmap(gr.id(n0)) == n0, "Wrong IdMap"); + check(nmap[n1] == gr.id(n1) && nmap(gr.id(n1)) == n1, "Wrong IdMap"); + check(nmap[n2] == gr.id(n2) && nmap(gr.id(n2)) == n2, "Wrong IdMap"); + + check(amap[a0] == gr.id(a0) && amap(gr.id(a0)) == a0, "Wrong IdMap"); + check(amap[a1] == gr.id(a1) && amap(gr.id(a1)) == a1, "Wrong IdMap"); + check(amap[a2] == gr.id(a2) && amap(gr.id(a2)) == a2, "Wrong IdMap"); + check(amap[a3] == gr.id(a3) && amap(gr.id(a3)) == a3, "Wrong IdMap"); + + check(nmap.inverse()[gr.id(n0)] == n0, "Wrong IdMap::InverseMap"); + check(amap.inverse()[gr.id(a0)] == a0, "Wrong IdMap::InverseMap"); + + check(nrmap.size() == 3 && armap.size() == 4, + "Wrong RangeIdMap::size()"); + + check(nrmap[n0] == 0 && nrmap(0) == n0, "Wrong RangeIdMap"); + check(nrmap[n1] == 1 && nrmap(1) == n1, "Wrong RangeIdMap"); + check(nrmap[n2] == 2 && nrmap(2) == n2, "Wrong RangeIdMap"); + + check(armap[a0] == 0 && armap(0) == a0, "Wrong RangeIdMap"); + check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap"); + check(armap[a2] == 2 && armap(2) == a2, "Wrong RangeIdMap"); + check(armap[a3] == 3 && armap(3) == a3, "Wrong RangeIdMap"); + + check(nrmap.inverse()[0] == n0, "Wrong RangeIdMap::InverseMap"); + check(armap.inverse()[0] == a0, "Wrong RangeIdMap::InverseMap"); + + gr.erase(n1); + + if (nrmap[n0] == 1) nrmap.swap(n0, n2); + nrmap.swap(n2, n0); + if (armap[a1] == 1) armap.swap(a1, a3); + armap.swap(a3, a1); + + check(nrmap.size() == 2 && armap.size() == 2, + "Wrong RangeIdMap::size()"); + + check(nrmap[n0] == 1 && nrmap(1) == n0, "Wrong RangeIdMap"); + check(nrmap[n2] == 0 && nrmap(0) == n2, "Wrong RangeIdMap"); + + check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap"); + check(armap[a3] == 0 && armap(0) == a3, "Wrong RangeIdMap"); + + check(nrmap.inverse()[0] == n2, "Wrong RangeIdMap::InverseMap"); + check(armap.inverse()[0] == a3, "Wrong RangeIdMap::InverseMap"); + } + + // SourceMap, TargetMap, ForwardMap, BackwardMap, InDegMap, OutDegMap + { + typedef ListGraph Graph; + GRAPH_TYPEDEFS(Graph); + + checkConcept, SourceMap >(); + checkConcept, TargetMap >(); + checkConcept, ForwardMap >(); + checkConcept, BackwardMap >(); + checkConcept, InDegMap >(); + checkConcept, OutDegMap >(); + + Graph gr; + Node n0 = gr.addNode(); + Node n1 = gr.addNode(); + Node n2 = gr.addNode(); + + gr.addEdge(n0,n1); + gr.addEdge(n1,n2); + gr.addEdge(n0,n2); + gr.addEdge(n2,n1); + gr.addEdge(n1,n2); + gr.addEdge(n0,n1); + + for (EdgeIt e(gr); e != INVALID; ++e) { + check(forwardMap(gr)[e] == gr.direct(e, true), "Wrong ForwardMap"); + check(backwardMap(gr)[e] == gr.direct(e, false), "Wrong BackwardMap"); + } + + compareMap(sourceMap(orienter(gr, constMap(true))), + targetMap(orienter(gr, constMap(false))), + EdgeIt(gr)); + + typedef Orienter > Digraph; + Digraph dgr(gr, constMap(true)); + OutDegMap odm(dgr); + InDegMap idm(dgr); + + check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 1, "Wrong OutDegMap"); + check(idm[n0] == 0 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap"); + + gr.addEdge(n2, n0); + + check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 2, "Wrong OutDegMap"); + check(idm[n0] == 1 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap"); + } + + // CrossRefMap + { + typedef ListDigraph Graph; + DIGRAPH_TYPEDEFS(Graph); + + checkConcept, + CrossRefMap >(); + checkConcept, + CrossRefMap >(); + checkConcept, + CrossRefMap >(); + + Graph gr; + typedef CrossRefMap CRMap; + CRMap map(gr); + + Node n0 = gr.addNode(); + Node n1 = gr.addNode(); + Node n2 = gr.addNode(); + + map.set(n0, 'A'); + map.set(n1, 'B'); + map.set(n2, 'C'); + + check(map[n0] == 'A' && map('A') == n0 && map.inverse()['A'] == n0, + "Wrong CrossRefMap"); + check(map[n1] == 'B' && map('B') == n1 && map.inverse()['B'] == n1, + "Wrong CrossRefMap"); + check(map[n2] == 'C' && map('C') == n2 && map.inverse()['C'] == n2, + "Wrong CrossRefMap"); + check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1, + "Wrong CrossRefMap::count()"); + + CRMap::ValueIt it = map.beginValue(); + check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' && + it == map.endValue(), "Wrong value iterator"); + + map.set(n2, 'A'); + + check(map[n0] == 'A' && map[n1] == 'B' && map[n2] == 'A', + "Wrong CrossRefMap"); + check(map('A') == n0 && map.inverse()['A'] == n0, "Wrong CrossRefMap"); + check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap"); + check(map('C') == INVALID && map.inverse()['C'] == INVALID, + "Wrong CrossRefMap"); + check(map.count('A') == 2 && map.count('B') == 1 && map.count('C') == 0, + "Wrong CrossRefMap::count()"); + + it = map.beginValue(); + check(*it++ == 'A' && *it++ == 'A' && *it++ == 'B' && + it == map.endValue(), "Wrong value iterator"); + + map.set(n0, 'C'); + + check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A', + "Wrong CrossRefMap"); + check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap"); + check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap"); + check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap"); + check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1, + "Wrong CrossRefMap::count()"); + + it = map.beginValue(); + check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' && + it == map.endValue(), "Wrong value iterator"); } // CrossRefMap @@ -546,10 +775,10 @@ check(static_cast(it) == INVALID, "Wrong value"); } - for (Ivm::ValueIterator vit = map1.beginValue(); + for (Ivm::ValueIt vit = map1.beginValue(); vit != map1.endValue(); ++vit) { check(map1[static_cast(Ivm::ItemIt(map1, *vit))] == *vit, - "Wrong ValueIterator"); + "Wrong ValueIt"); } for (int i = 0; i < num; ++i) {