Changes in / [789:8e68671af789:788:10c9c3a35b83] in lemon

Files:

• doc/groups.dox (modified) (11 diffs)
• lemon/Makefile.am (modified) (4 diffs)
• lemon/bellman_ford.h (deleted)
• lemon/bfs.h (modified) (32 diffs)
• lemon/bin_heap.h (modified) (14 diffs)
• lemon/binom_heap.h (deleted)
• lemon/bits/map_extender.h (modified) (2 diffs)
• lemon/bucket_heap.h (modified) (27 diffs)
• lemon/circulation.h (modified) (4 diffs)
• lemon/concepts/heap.h (modified) (7 diffs)
• lemon/concepts/maps.h (modified) (1 diff)
• lemon/dfs.h (modified) (32 diffs)
• lemon/dijkstra.h (modified) (31 diffs)
• lemon/dim2.h (modified) (2 diffs)
• lemon/fib_heap.h (modified) (12 diffs)
• lemon/fourary_heap.h (deleted)
• lemon/gomory_hu.h (modified) (2 diffs)
• lemon/kary_heap.h (deleted)
• lemon/maps.h (modified) (32 diffs)
• lemon/min_cost_arborescence.h (modified) (1 diff)
• lemon/network_simplex.h (modified) (13 diffs)
• lemon/pairing_heap.h (deleted)
• lemon/preflow.h (modified) (6 diffs)
• lemon/radix_heap.h (modified) (9 diffs)
• scripts/bootstrap.sh (deleted)
• scripts/chg-len.py (modified) (1 diff)
• scripts/mk-release.sh (modified) (1 diff)
• scripts/unify-sources.sh (modified) (1 diff)
• test/CMakeLists.txt (modified) (1 diff)
• test/Makefile.am (modified) (2 diffs)
• test/bellman_ford_test.cc (deleted)
• test/circulation_test.cc (modified) (1 diff)
• test/heap_test.cc (modified) (13 diffs)
• test/maps_test.cc (modified) (6 diffs)
• test/preflow_test.cc (modified) (1 diff)
• tools/lemon-0.x-to-1.x.sh (modified) (2 diffs)

doc/groups.dox

@@ -227 +227 @@
 
 /**
+@defgroup matrices Matrices
+@ingroup datas
+\brief Two dimensional data storages implemented in LEMON.
+
+This group contains two dimensional data storages implemented in LEMON.
+*/
+
+/**
 @defgroup paths Path Structures
 @ingroup datas
@@ -239 +247 @@
 any kind of path structure.
 
-\sa \ref concepts::Path "Path concept"
-*/
-
-/**
-@defgroup heaps Heap Structures
-@ingroup datas
-\brief %Heap structures implemented in LEMON.
-
-This group contains the heap structures implemented in LEMON.
-
-LEMON provides several heap classes. They are efficient implementations
-of the abstract data type \e priority \e queue. They store items with
-specified values called \e priorities in such a way that finding and
-removing the item with minimum priority are efficient.
-The basic operations are adding and erasing items, changing the priority
-of an item, etc.
-
-Heaps are crucial in several algorithms, such as Dijkstra and Prim.
-The heap implementations have the same interface, thus any of them can be
-used easily in such algorithms.
-
-\sa \ref concepts::Heap "Heap concept"
-*/
-
-/**
-@defgroup matrices Matrices
-@ingroup datas
-\brief Two dimensional data storages implemented in LEMON.
-
-This group contains two dimensional data storages implemented in LEMON.
+\sa lemon::concepts::Path
 */
 
@@ -278 +257 @@
 This group contains some data structures implemented in LEMON in
 order to make it easier to implement combinatorial algorithms.
-*/
-
-/**
-@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.
 */
 
@@ -342 +299 @@
 
 /**
-@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
@@ -428 +376 @@
 
 \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:
@@ -441 +389 @@
 If you want to find minimum cut just between two distinict nodes,
 see the \ref max_flow "maximum flow problem".
+*/
+
+/**
+@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
 */
 
@@ -484 +456 @@
 
 /**
-@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 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 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 auxalg Auxiliary Algorithms
+@ingroup algs
+\brief Auxiliary algorithms implemented in LEMON.
+
+This group contains some algorithms implemented in LEMON
+in order to make it easier to implement complex algorithms.
 */
 
@@ -514 +480 @@
 This group contains the approximation and heuristic algorithms
 implemented in LEMON.
-*/
-
-/**
-@defgroup auxalg Auxiliary Algorithms
-@ingroup algs
-\brief Auxiliary algorithms implemented in LEMON.
-
-This group contains some algorithms implemented in LEMON
-in order to make it easier to implement complex algorithms.
 */
 
@@ -631 +588 @@
 
 /**
-@defgroup dimacs_group DIMACS Format
+@defgroup dimacs_group DIMACS format
 @ingroup io_group
 \brief Read and write files in DIMACS format
@@ -693 +650 @@
 
 /**
+\anchor demoprograms
+
+@defgroup demos Demo Programs
+
+Some demo programs are listed here. Their full source codes can be found in
+the \c demo subdirectory of the source tree.
+
+In order to compile them, use the <tt>make demo</tt> or the
+<tt>make check</tt> commands.
+*/
+
+/**
 @defgroup tools Standalone Utility Applications
 
@@ -701 +670 @@
 */
 
-/**
-\anchor demoprograms
-
-@defgroup demos Demo Programs
-
-Some demo programs are listed here. Their full source codes can be found in
-the \c demo subdirectory of the source tree.
-
-In order to compile them, use the <tt>make demo</tt> or the
-<tt>make check</tt> commands.
-*/
-
 }

lemon/Makefile.am

@@ -58 +58 @@
         lemon/arg_parser.h \
         lemon/assert.h \
-        lemon/bellman_ford.h \
         lemon/bfs.h \
         lemon/bin_heap.h \
-        lemon/binom_heap.h \
         lemon/bucket_heap.h \
         lemon/cbc.h \
@@ -81 +79 @@
         lemon/euler.h \
         lemon/fib_heap.h \
-        lemon/fourary_heap.h \
         lemon/full_graph.h \
         lemon/glpk.h \
@@ -88 +85 @@
         lemon/grid_graph.h \
         lemon/hypercube_graph.h \
-        lemon/kary_heap.h \
         lemon/kruskal.h \
         lemon/hao_orlin.h \
@@ -103 +99 @@
         lemon/nauty_reader.h \
         lemon/network_simplex.h \
-        lemon/pairing_heap.h \
         lemon/path.h \
         lemon/preflow.h \

lemon/bfs.h

@@ -48 +48 @@
     ///The type of the map that stores the predecessor
     ///arcs of the shortest paths.
-    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
     ///Instantiates a \c PredMap.
@@ -63 +63 @@
 
     ///The type of the map that indicates which nodes are processed.
-    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
-    ///By default it is a NullMap.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     ///Instantiates a \c ProcessedMap.
@@ -83 +82 @@
 
     ///The type of the map that indicates which nodes are reached.
-    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     typedef typename Digraph::template NodeMap<bool> ReachedMap;
     ///Instantiates a \c ReachedMap.
@@ -98 +97 @@
 
     ///The type of the map that stores the distances of the nodes.
-    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef typename Digraph::template NodeMap<int> DistMap;
     ///Instantiates a \c DistMap.
@@ -227 +226 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///\c PredMap type.
-    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
@@ -247 +246 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///\c DistMap type.
-    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
@@ -267 +266 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///\c ReachedMap type.
-    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     template <class T>
     struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
@@ -287 +286 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///\c ProcessedMap type.
-    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
@@ -415 +414 @@
     ///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 better control on the execution, you have to call
-    ///\ref init() first, then you can add several source nodes with
+    ///If you need more control on the execution, first you have to call
+    ///\ref init(), 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.
@@ -739 +738 @@
     ///@{
 
-    ///The shortest path to the given node.
-
-    ///Returns the shortest path to the given node from the root(s).
+    ///The shortest path to a node.
+
+    ///Returns the shortest path to a node.
     ///
     ///\warning \c t should be reached from the root(s).
@@ -749 +748 @@
     Path path(Node t) const { return Path(*G, *_pred, t); }
 
-    ///The distance of the given node from the root(s).
-
-    ///Returns the distance of the given node from the root(s).
+    ///The distance of a node from the root(s).
+
+    ///Returns the distance of a node from the root(s).
     ///
     ///\warning If node \c v is not reached from the root(s), then
@@ -760 +759 @@
     int dist(Node v) const { return (*_dist)[v]; }
 
-    ///\brief Returns the 'previous arc' of the shortest path tree for
-    ///the given node.
-    ///
+    ///Returns the 'previous arc' of the shortest path tree for a 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
@@ -769 +767 @@
     ///
     ///The shortest path tree used here is equal to the shortest path
-    ///tree used in \ref predNode() and \ref predMap().
+    ///tree used in \ref predNode().
     ///
     ///\pre Either \ref run(Node) "run()" or \ref init()
@@ -775 +773 @@
     Arc predArc(Node v) const { return (*_pred)[v];}
 
-    ///\brief Returns the 'previous node' of the shortest path tree for
-    ///the given node.
-    ///
+    ///Returns the 'previous node' of the shortest path tree for a 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
-    ///of a shortest path from a root to \c v. It is \c INVALID
+    ///from 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() and \ref predMap().
+    ///tree used in \ref predArc().
     ///
     ///\pre Either \ref run(Node) "run()" or \ref init()
@@ -805 +802 @@
     ///
     ///Returns a const reference to the node map that stores the predecessor
-    ///arcs, which form the shortest path tree (forest).
+    ///arcs, which form the shortest path tree.
     ///
     ///\pre Either \ref run(Node) "run()" or \ref init()
@@ -811 +808 @@
     const PredMap &predMap() const { return *_pred;}
 
-    ///Checks if the given node is reached from the root(s).
+    ///Checks if a node is reached from the root(s).
 
     ///Returns \c true if \c v is reached from the root(s).
@@ -837 +834 @@
     ///The type of the map that stores the predecessor
     ///arcs of the shortest paths.
-    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
     ///Instantiates a PredMap.
@@ -852 +849 @@
 
     ///The type of the map that indicates which nodes are processed.
-    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     ///By default it is a NullMap.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
@@ -872 +869 @@
 
     ///The type of the map that indicates which nodes are reached.
-    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     typedef typename Digraph::template NodeMap<bool> ReachedMap;
     ///Instantiates a ReachedMap.
@@ -887 +884 @@
 
     ///The type of the map that stores the distances of the nodes.
-    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef typename Digraph::template NodeMap<int> DistMap;
     ///Instantiates a DistMap.
@@ -902 +899 @@
 
     ///The type of the shortest paths.
-    ///It must conform to the \ref concepts::Path "Path" concept.
+    ///It must meet the \ref concepts::Path "Path" concept.
     typedef lemon::Path<Digraph> Path;
   };
@@ -908 +905 @@
   /// Default traits class used by BfsWizard
 
-  /// Default traits class used by BfsWizard.
-  /// \tparam GR The type of the digraph.
+  /// 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.
   template<class GR>
   class BfsWizardBase : public BfsWizardDefaultTraits<GR>
@@ -937 +938 @@
     /// Constructor.
 
-    /// This constructor does not require parameters, it initiates
+    /// This constructor does not require parameters, therefore it initiates
     /// all of the attributes to \c 0.
     BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
@@ -967 +968 @@
     typedef TR Base;
 
+    ///The type of the digraph the algorithm runs on.
     typedef typename TR::Digraph Digraph;
 
@@ -974 +976 @@
     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;
 
@@ -1060 +1068 @@
       SetPredMapBase(const TR &b) : TR(b) {}
     };
-
-    ///\brief \ref named-templ-param "Named parameter" for setting
-    ///the predecessor map.
-    ///
-    ///\ref named-templ-param "Named parameter" function for setting
-    ///the map that stores the predecessor arcs of the nodes.
+    ///\brief \ref named-func-param "Named parameter"
+    ///for setting PredMap object.
+    ///
+    ///\ref named-func-param "Named parameter"
+    ///for setting PredMap object.
     template<class T>
     BfsWizard<SetPredMapBase<T> > predMap(const T &t)
@@ -1079 +1086 @@
       SetReachedMapBase(const TR &b) : TR(b) {}
     };
-
-    ///\brief \ref named-templ-param "Named parameter" for setting
-    ///the reached map.
-    ///
-    ///\ref named-templ-param "Named parameter" function for setting
-    ///the map that indicates which nodes are reached.
+    ///\brief \ref named-func-param "Named parameter"
+    ///for setting ReachedMap object.
+    ///
+    /// \ref named-func-param "Named parameter"
+    ///for setting ReachedMap object.
     template<class T>
     BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
@@ -1098 +1104 @@
       SetDistMapBase(const TR &b) : TR(b) {}
     };
-
-    ///\brief \ref named-templ-param "Named parameter" for setting
-    ///the distance map.
-    ///
-    ///\ref named-templ-param "Named parameter" function for setting
-    ///the map that stores the distances of the nodes calculated
-    ///by the algorithm.
+    ///\brief \ref named-func-param "Named parameter"
+    ///for setting DistMap object.
+    ///
+    /// \ref named-func-param "Named parameter"
+    ///for setting DistMap object.
     template<class T>
     BfsWizard<SetDistMapBase<T> > distMap(const T &t)
@@ -1118 +1122 @@
       SetProcessedMapBase(const TR &b) : TR(b) {}
     };
-
-    ///\brief \ref named-func-param "Named parameter" for setting
-    ///the processed map.
-    ///
-    ///\ref named-templ-param "Named parameter" function for setting
-    ///the map that indicates which nodes are processed.
+    ///\brief \ref named-func-param "Named parameter"
+    ///for setting ProcessedMap object.
+    ///
+    /// \ref named-func-param "Named parameter"
+    ///for setting ProcessedMap object.
     template<class T>
     BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
@@ -1262 +1265 @@
     ///
     /// The type of the map that indicates which nodes are reached.
-    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     typedef typename Digraph::template NodeMap<bool> ReachedMap;
 
@@ -1423 +1426 @@
     /// 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 better control on the execution, you have to call
-    /// \ref init() first, then you can add several source nodes with
+    /// If you need more control on the execution, first you have to call
+    /// \ref init(), 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.
@@ -1733 +1736 @@
     ///@{
 
-    /// \brief Checks if the given node is reached from the root(s).
+    /// \brief Checks if a node is reached from the root(s).
     ///
     /// Returns \c true if \c v is reached from the root(s).

lemon/bin_heap.h

@@ -20 +20 @@
 #define LEMON_BIN_HEAP_H
 
-///\ingroup heaps
+///\ingroup auxdat
 ///\file
-///\brief Binary heap implementation.
+///\brief Binary Heap implementation.
 
 #include <vector>
@@ -30 +30 @@
 namespace lemon {
 
-  /// \ingroup heaps
-  ///
-  /// \brief Binary heap data structure.
-  ///
-  /// This class implements the \e binary \e heap data structure.
-  /// It fully conforms to the \ref concepts::Heap "heap concept".
-  ///
-  /// \tparam PR Type of the priorities of the items.
-  /// \tparam IM A read-writable item map with \c int values, used
-  /// internally to handle the cross references.
-  /// \tparam CMP A functor class for comparing the priorities.
-  /// The default is \c std::less<PR>.
-#ifdef DOXYGEN
-  template <typename PR, typename IM, typename CMP>
-#else
+  ///\ingroup auxdat
+  ///
+  ///\brief A Binary Heap implementation.
+  ///
+  ///This class implements the \e binary \e heap data structure.
+  ///
+  ///A \e heap is a data structure for storing items with specified values
+  ///called \e priorities in such a way that finding the item with minimum
+  ///priority is efficient. \c CMP specifies the ordering of the priorities.
+  ///In a heap one can change the priority of an item, add or erase an
+  ///item, etc.
+  ///
+  ///\tparam PR Type of the priority of the items.
+  ///\tparam IM A read and writable item map with int values, used internally
+  ///to handle the cross references.
+  ///\tparam CMP A functor class for the ordering of the priorities.
+  ///The default is \c std::less<PR>.
+  ///
+  ///\sa FibHeap
+  ///\sa Dijkstra
   template <typename PR, typename IM, typename CMP = std::less<PR> >
-#endif
   class BinHeap {
+
   public:
-
-    /// Type of the item-int map.
+    ///\e
     typedef IM ItemIntMap;
-    /// Type of the priorities.
+    ///\e
     typedef PR Prio;
-    /// Type of the items stored in the heap.
+    ///\e
     typedef typename ItemIntMap::Key Item;
-    /// Type of the item-priority pairs.
+    ///\e
     typedef std::pair<Item,Prio> Pair;
-    /// Functor type for comparing the priorities.
+    ///\e
     typedef CMP Compare;
 
-    /// \brief Type to represent the states of the items.
-    ///
-    /// Each item has a state associated to it. It can be "in heap",
-    /// "pre-heap" or "post-heap". The latter two are indifferent from the
+    /// \brief Type to represent the items states.
+    ///
+    /// Each Item element have a state associated to it. It may be "in heap",
+    /// "pre heap" or "post heap". The latter two are indifferent from the
     /// heap's point of view, but may be useful to the user.
     ///
@@ -81 +85 @@
 
   public:
-
-    /// \brief Constructor.
-    ///
-    /// Constructor.
-    /// \param map A map that assigns \c int values to the items.
-    /// It is used internally to handle the cross references.
-    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
+    /// \brief The constructor.
+    ///
+    /// The constructor.
+    /// \param map should be given to the constructor, since it is used
+    /// internally to handle the cross references. The value of the map
+    /// must be \c PRE_HEAP (<tt>-1</tt>) for every item.
     explicit BinHeap(ItemIntMap &map) : _iim(map) {}
 
-    /// \brief Constructor.
-    ///
-    /// Constructor.
-    /// \param map A map that assigns \c int values to the items.
-    /// It is used internally to handle the cross references.
-    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
-    /// \param comp The function object used for comparing the priorities.
+    /// \brief The constructor.
+    ///
+    /// The constructor.
+    /// \param map should be given to the constructor, since it is used
+    /// internally to handle the cross references. The value of the map
+    /// should be PRE_HEAP (-1) for each element.
+    ///
+    /// \param comp The comparator function object.
     BinHeap(ItemIntMap &map, const Compare &comp)
       : _iim(map), _comp(comp) {}
 
 
-    /// \brief The number of items stored in the heap.
-    ///
-    /// This function returns the number of items stored in the heap.
+    /// The number of items stored in the heap.
+    ///
+    /// \brief Returns the number of items stored in the heap.
     int size() const { return _data.size(); }
 
-    /// \brief Check if the heap is empty.
-    ///
-    /// This function returns \c true if the heap is empty.
+    /// \brief Checks if the heap stores no items.
+    ///
+    /// Returns \c true if and only if the heap stores no items.
     bool empty() const { return _data.empty(); }
 
-    /// \brief Make the heap empty.
-    ///
-    /// This functon makes the heap empty.
-    /// It does not change the cross reference map. If you want to reuse
-    /// a heap that is not surely empty, you should first clear it and
-    /// then you should set the cross reference map to \c PRE_HEAP
-    /// for each item.
+    /// \brief Make empty this heap.
+    ///
+    /// Make empty this heap. It does not change the cross reference map.
+    /// If you want to reuse what is not surely empty you should first clear
+    /// the heap and after that you should set the cross reference map for
+    /// each item to \c PRE_HEAP.
     void clear() {
       _data.clear();
@@ -125 +128 @@
     static int parent(int i) { return (i-1)/2; }
 
-    static int secondChild(int i) { return 2*i+2; }
+    static int second_child(int i) { return 2*i+2; }
     bool less(const Pair &p1, const Pair &p2) const {
       return _comp(p1.second, p2.second);
     }
 
-    int bubbleUp(int hole, Pair p) {
+    int bubble_up(int hole, Pair p) {
       int par = parent(hole);
       while( hole>0 && less(p,_data[par]) ) {
@@ -141 +144 @@
     }
 
-    int bubbleDown(int hole, Pair p, int length) {
-      int child = secondChild(hole);
+    int bubble_down(int hole, Pair p, int length) {
+      int child = second_child(hole);
       while(child < length) {
         if( less(_data[child-1], _data[child]) ) {
@@ -151 +154 @@
         move(_data[child], hole);
         hole = child;
-        child = secondChild(hole);
+        child = second_child(hole);
       }
       child--;
@@ -169 +172 @@
 
   public:
-
     /// \brief Insert a pair of item and priority into the heap.
     ///
-    /// This function inserts \c p.first to the heap with priority
-    /// \c p.second.
+    /// Adds \c p.first to the heap with priority \c p.second.
     /// \param p The pair to insert.
-    /// \pre \c p.first must not be stored in the heap.
     void push(const Pair &p) {
       int n = _data.size();
       _data.resize(n+1);
-      bubbleUp(n, p);
-    }
-
-    /// \brief Insert an item into the heap with the given priority.
-    ///
-    /// This function inserts the given item into the heap with the
-    /// given priority.
+      bubble_up(n, p);
+    }
+
+    /// \brief Insert an item into the heap with the given heap.
+    ///
+    /// Adds \c i to the heap with priority \c p.
     /// \param i The item to insert.
     /// \param p The priority of the item.
-    /// \pre \e i must not be stored in the heap.
     void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
 
-    /// \brief Return the item having minimum priority.
-    ///
-    /// This function returns the item having minimum priority.
-    /// \pre The heap must be non-empty.
+    /// \brief Returns the item with minimum priority relative to \c Compare.
+    ///
+    /// This method returns the item with minimum priority relative to \c
+    /// Compare.
+    /// \pre The heap must be nonempty.
     Item top() const {
       return _data[0].first;
     }
 
-    /// \brief The minimum priority.
-    ///
-    /// This function returns the minimum priority.
-    /// \pre The heap must be non-empty.
+    /// \brief Returns the minimum priority relative to \c Compare.
+    ///
+    /// It returns the minimum priority relative to \c Compare.
+    /// \pre The heap must be nonempty.
     Prio prio() const {
       return _data[0].second;
     }
 
-    /// \brief Remove the item having minimum priority.
-    ///
-    /// This function removes the item having minimum priority.
+    /// \brief Deletes the item with minimum priority relative to \c Compare.
+    ///
+    /// This method deletes the item with minimum priority relative to \c
+    /// Compare from the heap.
     /// \pre The heap must be non-empty.
     void pop() {
@@ -215 +215 @@
       _iim.set(_data[0].first, POST_HEAP);
       if (n > 0) {
-        bubbleDown(0, _data[n], n);
+        bubble_down(0, _data[n], n);
       }
       _data.pop_back();
     }
 
-    /// \brief Remove the given item from the heap.
-    ///
-    /// This function removes the given item from the heap if it is
-    /// already stored.
-    /// \param i The item to delete.
-    /// \pre \e i must be in the heap.
+    /// \brief Deletes \c i from the heap.
+    ///
+    /// This method deletes item \c i from the heap.
+    /// \param i The item to erase.
+    /// \pre The item should be in the heap.
     void erase(const Item &i) {
       int h = _iim[i];
@@ -231 +230 @@
       _iim.set(_data[h].first, POST_HEAP);
       if( h < n ) {
-        if ( bubbleUp(h, _data[n]) == h) {
-          bubbleDown(h, _data[n], n);
+        if ( bubble_up(h, _data[n]) == h) {
+          bubble_down(h, _data[n], n);
         }
       }
@@ -238 +237 @@
     }
 
-    /// \brief The priority of the given item.
-    ///
-    /// This function returns the priority of the given item.
-    /// \param i The item.
-    /// \pre \e i must be in the heap.
+
+    /// \brief Returns the priority of \c i.
+    ///
+    /// This function returns the priority of item \c i.
+    /// \param i The item.
+    /// \pre \c i must be in the heap.
     Prio operator[](const Item &i) const {
       int idx = _iim[i];
@@ -248 +248 @@
     }
 
-    /// \brief Set the priority of an item or insert it, if it is
-    /// not stored in the heap.
-    ///
-    /// This method sets the priority of the given item if it is
-    /// already stored in the heap. Otherwise it inserts the given
-    /// item into the heap with the given priority.
+    /// \brief \c i gets to the heap with priority \c p independently
+    /// if \c i was already there.
+    ///
+    /// This method calls \ref push(\c i, \c p) if \c i is not stored
+    /// in the heap and sets the priority of \c i to \c p otherwise.
     /// \param i The item.
     /// \param p The priority.
@@ -262 +261 @@
       }
       else if( _comp(p, _data[idx].second) ) {
-        bubbleUp(idx, Pair(i,p));
+        bubble_up(idx, Pair(i,p));
       }
       else {
-        bubbleDown(idx, Pair(i,p), _data.size());
-      }
-    }
-
-    /// \brief Decrease the priority of an item to the given value.
-    ///
-    /// This function decreases the priority of an item to the given value.
+        bubble_down(idx, Pair(i,p), _data.size());
+      }
+    }
+
+    /// \brief Decreases the priority of \c i to \c p.
+    ///
+    /// This method decreases the priority of item \c i to \c p.
     /// \param i The item.
     /// \param p The priority.
-    /// \pre \e i must be stored in the heap with priority at least \e p.
+    /// \pre \c i must be stored in the heap with priority at least \c
+    /// p relative to \c Compare.
     void decrease(const Item &i, const Prio &p) {
       int idx = _iim[i];
-      bubbleUp(idx, Pair(i,p));
-    }
-
-    /// \brief Increase the priority of an item to the given value.
-    ///
-    /// This function increases the priority of an item to the given value.
+      bubble_up(idx, Pair(i,p));
+    }
+
+    /// \brief Increases the priority of \c i to \c p.
+    ///
+    /// This method sets the priority of item \c i to \c p.
     /// \param i The item.
     /// \param p The priority.
-    /// \pre \e i must be stored in the heap with priority at most \e p.
+    /// \pre \c i must be stored in the heap with priority at most \c
+    /// p relative to \c Compare.
     void increase(const Item &i, const Prio &p) {
       int idx = _iim[i];
-      bubbleDown(idx, Pair(i,p), _data.size());
-    }
-
-    /// \brief Return the state of an item.
-    ///
-    /// This method returns \c PRE_HEAP if the given item has never
-    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
-    /// and \c POST_HEAP otherwise.
-    /// In the latter case it is possible that the item will get back
-    /// to the heap again.
+      bubble_down(idx, Pair(i,p), _data.size());
+    }
+
+    /// \brief Returns if \c item is in, has already been in, or has
+    /// never been in the heap.
+    ///
+    /// This method returns PRE_HEAP if \c item has never been in the
+    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
+    /// otherwise. In the latter case it is possible that \c item will
+    /// get back to the heap again.
     /// \param i The item.
     State state(const Item &i) const {
@@ -306 +307 @@
     }
 
-    /// \brief Set the state of an item in the heap.
-    ///
-    /// This function sets the state of the given item in the heap.
-    /// It can be used to manually clear the heap when it is important
-    /// to achive better time complexity.
+    /// \brief Sets the state of the \c item in the heap.
+    ///
+    /// Sets the state of the \c item in the heap. It can be used to
+    /// manually clear the heap when it is important to achive the
+    /// better time complexity.
     /// \param i The item.
     /// \param st The state. It should not be \c IN_HEAP.
@@ -327 +328 @@
     }
 
-    /// \brief Replace an item in the heap.
-    ///
-    /// This function replaces item \c i with item \c j.
-    /// Item \c i must be in the heap, while \c j must be out of the heap.
-    /// After calling this method, item \c i will be out of the
-    /// heap and \c j will be in the heap with the same prioriority
-    /// as item \c i had before.
+    /// \brief Replaces an item in the heap.
+    ///
+    /// The \c i item is replaced with \c j item. The \c i item should
+    /// be in the heap, while the \c j should be out of the heap. The
+    /// \c i item will out of the heap and \c j will be in the heap
+    /// with the same prioriority as prevoiusly the \c i item.
     void replace(const Item& i, const Item& j) {
       int idx = _iim[i];

lemon/bits/map_extender.h

@@ -50 +50 @@
     typedef typename Parent::ConstReference ConstReference;
 
-    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
-
     class MapIt;
     class ConstMapIt;
@@ -194 +192 @@
     typedef typename Parent::ConstReference ConstReference;
 
-    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
-
     class MapIt;
     class ConstMapIt;

lemon/bucket_heap.h

@@ -20 +20 @@
 #define LEMON_BUCKET_HEAP_H
 
-///\ingroup heaps
+///\ingroup auxdat
 ///\file
-///\brief Bucket heap implementation.
+///\brief Bucket Heap implementation.
 
 #include <vector>
@@ -54 +54 @@
   }
 
-  /// \ingroup heaps
-  ///
-  /// \brief Bucket heap data structure.
-  ///
-  /// This class implements the \e bucket \e heap data structure.
-  /// It practically conforms to the \ref concepts::Heap "heap concept",
-  /// but it has some limitations.
-  ///
-  /// The bucket heap is a very simple structure. It can store only
-  /// \c int priorities and it maintains a list of items for each priority
-  /// in the range <tt>[0..C)</tt>. So it should only be used when the
-  /// priorities are small. It is not intended to use as a Dijkstra heap.
-  ///
-  /// \tparam IM A read-writable item map with \c int values, used
-  /// internally to handle the cross references.
-  /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
-  /// The default is \e min-heap. If this parameter is set to \c false,
-  /// then the comparison is reversed, so the top(), prio() and pop()
-  /// functions deal with the item having maximum priority instead of the
-  /// minimum.
-  ///
-  /// \sa SimpleBucketHeap
+  /// \ingroup auxdat
+  ///
+  /// \brief A Bucket Heap implementation.
+  ///
+  /// This class implements the \e bucket \e heap data structure. A \e heap
+  /// is a data structure for storing items with specified values called \e
+  /// priorities in such a way that finding the item with minimum priority is
+  /// efficient. The bucket heap is very simple implementation, it can store
+  /// only integer priorities and it stores for each priority in the
+  /// \f$ [0..C) \f$ range a list of items. So it should be used only when
+  /// the priorities are small. It is not intended to use as dijkstra heap.
+  ///
+  /// \param IM A read and write Item int map, used internally
+  /// to handle the cross references.
+  /// \param MIN If the given parameter is false then instead of the
+  /// minimum value the maximum can be retrivied with the top() and
+  /// prio() member functions.
   template <typename IM, bool MIN = true>
   class BucketHeap {
 
   public:
-
-    /// Type of the item-int map.
+    /// \e
+    typedef typename IM::Key Item;
+    /// \e
+    typedef int Prio;
+    /// \e
+    typedef std::pair<Item, Prio> Pair;
+    /// \e
     typedef IM ItemIntMap;
-    /// Type of the priorities.
-    typedef int Prio;
-    /// Type of the items stored in the heap.
-    typedef typename ItemIntMap::Key Item;
-    /// Type of the item-priority pairs.
-    typedef std::pair<Item,Prio> Pair;
 
   private:
@@ -96 +90 @@
   public:
 
-    /// \brief Type to represent the states of the items.
-    ///
-    /// Each item has a state associated to it. It can be "in heap",
-    /// "pre-heap" or "post-heap". The latter two are indifferent from the
+    /// \brief Type to represent the items states.
+    ///
+    /// Each Item element have a state associated to it. It may be "in heap",
+    /// "pre heap" or "post heap". The latter two are indifferent from the
     /// heap's point of view, but may be useful to the user.
     ///
@@ -111 +105 @@
 
   public:
-
-    /// \brief Constructor.
-    ///
-    /// Constructor.
-    /// \param map A map that assigns \c int values to the items.
-    /// It is used internally to handle the cross references.
-    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
+    /// \brief The constructor.
+    ///
+    /// The constructor.
+    /// \param map should be given to the constructor, since it is used
+    /// internally to handle the cross references. The value of the map
+    /// should be PRE_HEAP (-1) for each element.
     explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {}
 
-    /// \brief The number of items stored in the heap.
-    ///
-    /// This function returns the number of items stored in the heap.
+    /// The number of items stored in the heap.
+    ///
+    /// \brief Returns the number of items stored in the heap.
     int size() const { return _data.size(); }
 
-    /// \brief Check if the heap is empty.
-    ///
-    /// This function returns \c true if the heap is empty.
+    /// \brief Checks if the heap stores no items.
+    ///
+    /// Returns \c true if and only if the heap stores no items.
     bool empty() const { return _data.empty(); }
 
-    /// \brief Make the heap empty.
-    ///
-    /// This functon makes the heap empty.
-    /// It does not change the cross reference map. If you want to reuse
-    /// a heap that is not surely empty, you should first clear it and
-    /// then you should set the cross reference map to \c PRE_HEAP
-    /// for each item.
+    /// \brief Make empty this heap.
+    ///
+    /// Make empty this heap. It does not change the cross reference
+    /// map.  If you want to reuse a heap what is not surely empty you
+    /// should first clear the heap and after that you should set the
+    /// cross reference map for each item to \c PRE_HEAP.
     void clear() {
       _data.clear(); _first.clear(); _minimum = 0;
@@ -143 +135 @@
   private:
 
-    void relocateLast(int idx) {
+    void relocate_last(int idx) {
       if (idx + 1 < int(_data.size())) {
         _data[idx] = _data.back();
@@ -183 +175 @@
 
   public:
-
     /// \brief Insert a pair of item and priority into the heap.
     ///
-    /// This function inserts \c p.first to the heap with priority
-    /// \c p.second.
+    /// Adds \c p.first to the heap with priority \c p.second.
     /// \param p The pair to insert.
-    /// \pre \c p.first must not be stored in the heap.
     void push(const Pair& p) {
       push(p.first, p.second);
@@ -196 +185 @@
     /// \brief Insert an item into the heap with the given priority.
     ///
-    /// This function inserts the given item into the heap with the
-    /// given priority.
+    /// Adds \c i to the heap with priority \c p.
     /// \param i The item to insert.
     /// \param p The priority of the item.
-    /// \pre \e i must not be stored in the heap.
     void push(const Item &i, const Prio &p) {
       int idx = _data.size();
@@ -211 +198 @@
     }
 
-    /// \brief Return the item having minimum priority.
-    ///
-    /// This function returns the item having minimum priority.
-    /// \pre The heap must be non-empty.
+    /// \brief Returns the item with minimum priority.
+    ///
+    /// This method returns the item with minimum priority.
+    /// \pre The heap must be nonempty.
     Item top() const {
       while (_first[_minimum] == -1) {
@@ -222 +209 @@
     }
 
-    /// \brief The minimum priority.
-    ///
-    /// This function returns the minimum priority.
-    /// \pre The heap must be non-empty.
+    /// \brief Returns the minimum priority.
+    ///
+    /// It returns the minimum priority.
+    /// \pre The heap must be nonempty.
     Prio prio() const {
       while (_first[_minimum] == -1) {
@@ -233 +220 @@
     }
 
-    /// \brief Remove the item having minimum priority.
-    ///
-    /// This function removes the item having minimum priority.
+    /// \brief Deletes the item with minimum priority.
+    ///
+    /// This method deletes the item with minimum priority from the heap.
     /// \pre The heap must be non-empty.
     void pop() {
@@ -244 +231 @@
       _iim[_data[idx].item] = -2;
       unlace(idx);
-      relocateLast(idx);
-    }
-
-    /// \brief Remove the given item from the heap.
-    ///
-    /// This function removes the given item from the heap if it is
-    /// already stored.
-    /// \param i The item to delete.
-    /// \pre \e i must be in the heap.
+      relocate_last(idx);
+    }
+
+    /// \brief Deletes \c i from the heap.
+    ///
+    /// This method deletes item \c i from the heap, if \c i was
+    /// already stored in the heap.
+    /// \param i The item to erase.
     void erase(const Item &i) {
       int idx = _iim[i];
       _iim[_data[idx].item] = -2;
       unlace(idx);
-      relocateLast(idx);
-    }
-
-    /// \brief The priority of the given item.
-    ///
-    /// This function returns the priority of the given item.
-    /// \param i The item.
-    /// \pre \e i must be in the heap.
+      relocate_last(idx);
+    }
+
+
+    /// \brief Returns the priority of \c i.
+    ///
+    /// This function returns the priority of item \c i.
+    /// \pre \c i must be in the heap.
+    /// \param i The item.
     Prio operator[](const Item &i) const {
       int idx = _iim[i];
@@ -270 +257 @@
     }
 
-    /// \brief Set the priority of an item or insert it, if it is
-    /// not stored in the heap.
-    ///
-    /// This method sets the priority of the given item if it is
-    /// already stored in the heap. Otherwise it inserts the given
-    /// item into the heap with the given priority.
+    /// \brief \c i gets to the heap with priority \c p independently
+    /// if \c i was already there.
+    ///
+    /// This method calls \ref push(\c i, \c p) if \c i is not stored
+    /// in the heap and sets the priority of \c i to \c p otherwise.
     /// \param i The item.
     /// \param p The priority.
@@ -289 +275 @@
     }
 
-    /// \brief Decrease the priority of an item to the given value.
-    ///
-    /// This function decreases the priority of an item to the given value.
+    /// \brief Decreases the priority of \c i to \c p.
+    ///
+    /// This method decreases the priority of item \c i to \c p.
+    /// \pre \c i must be stored in the heap with priority at least \c
+    /// p relative to \c Compare.
     /// \param i The item.
     /// \param p The priority.
-    /// \pre \e i must be stored in the heap with priority at least \e p.
     void decrease(const Item &i, const Prio &p) {
       int idx = _iim[i];
@@ -305 +292 @@
     }
 
-    /// \brief Increase the priority of an item to the given value.
-    ///
-    /// This function increases the priority of an item to the given value.
+    /// \brief Increases the priority of \c i to \c p.
+    ///
+    /// This method sets the priority of item \c i to \c p.
+    /// \pre \c i must be stored in the heap with priority at most \c
+    /// p relative to \c Compare.
     /// \param i The item.
     /// \param p The priority.
-    /// \pre \e i must be stored in the heap with priority at most \e p.
     void increase(const Item &i, const Prio &p) {
       int idx = _iim[i];
@@ -318 +306 @@
     }
 
-    /// \brief Return the state of an item.
-    ///
-    /// This method returns \c PRE_HEAP if the given item has never
-    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
-    /// and \c POST_HEAP otherwise.
-    /// In the latter case it is possible that the item will get back
-    /// to the heap again.
+    /// \brief Returns if \c item is in, has already been in, or has
+    /// never been in the heap.
+    ///
+    /// This method returns PRE_HEAP if \c item has never been in the
+    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
+    /// otherwise. In the latter case it is possible that \c item will
+    /// get back to the heap again.
     /// \param i The item.
     State state(const Item &i) const {
@@ -332 +320 @@
     }
 
-    /// \brief Set the state of an item in the heap.
-    ///
-    /// This function sets the state of the given item in the heap.
-    /// It can be used to manually clear the heap when it is important
-    /// to achive better time complexity.
+    /// \brief Sets the state of the \c item in the heap.
+    ///
+    /// Sets the state of the \c item in the heap. It can be used to
+    /// manually clear the heap when it is important to achive the
+    /// better time complexity.
     /// \param i The item.
     /// \param st The state. It should not be \c IN_HEAP.
@@ -372 +360 @@
   }; // class BucketHeap
 
-  /// \ingroup heaps
-  ///
-  /// \brief Simplified bucket heap data structure.
+  /// \ingroup auxdat
+  ///
+  /// \brief A Simplified Bucket Heap implementation.
   ///
   /// This class implements a simplified \e bucket \e heap data
-  /// structure. It does not provide some functionality, but it is
-  /// faster and simpler than BucketHeap. The main difference is
-  /// that BucketHeap stores a doubly-linked list for each key while
-  /// this class stores only simply-linked lists. It supports erasing
-  /// only for the item having minimum priority and it does not support
-  /// key increasing and decreasing.
-  ///
-  /// Note that this implementation does not conform to the
-  /// \ref concepts::Heap "heap concept" due to the lack of some 
-  /// functionality.
-  ///
-  /// \tparam IM A read-writable item map with \c int values, used
-  /// internally to handle the cross references.
-  /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
-  /// The default is \e min-heap. If this parameter is set to \c false,
-  /// then the comparison is reversed, so the top(), prio() and pop()
-  /// functions deal with the item having maximum priority instead of the
-  /// minimum.
+  /// structure.  It does not provide some functionality but it faster
+  /// and simplier data structure than the BucketHeap. The main
+  /// difference is that the BucketHeap stores for every key a double
+  /// linked list while this class stores just simple lists. In the
+  /// other way it does not support erasing each elements just the
+  /// minimal and it does not supports key increasing, decreasing.
+  ///
+  /// \param IM A read and write Item int map, used internally
+  /// to handle the cross references.
+  /// \param MIN If the given parameter is false then instead of the
+  /// minimum value the maximum can be retrivied with the top() and
+  /// prio() member functions.
   ///
   /// \sa BucketHeap
@@ -401 +383 @@
 
   public:
-
-    /// Type of the item-int map.
+    typedef typename IM::Key Item;
+    typedef int Prio;
+    typedef std::pair<Item, Prio> Pair;
     typedef IM ItemIntMap;
-    /// Type of the priorities.
-    typedef int Prio;
-    /// Type of the items stored in the heap.
-    typedef typename ItemIntMap::Key Item;
-    /// Type of the item-priority pairs.
-    typedef std::pair<Item,Prio> Pair;
 
   private:
@@ -417 +394 @@
   public:
 
-    /// \brief Type to represent the states of the items.
-    ///
-    /// Each item has a state associated to it. It can be "in heap",
-    /// "pre-heap" or "post-heap". The latter two are indifferent from the
+    /// \brief Type to represent the items states.
+    ///
+    /// Each Item element have a state associated to it. It may be "in heap",
+    /// "pre heap" or "post heap". The latter two are indifferent from the
     /// heap's point of view, but may be useful to the user.
     ///
@@ -433 +410 @@
   public:
 
-    /// \brief Constructor.
-    ///
-    /// Constructor.
-    /// \param map A map that assigns \c int values to the items.
-    /// It is used internally to handle the cross references.
-    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
+    /// \brief The constructor.
+    ///
+    /// The constructor.
+    /// \param map should be given to the constructor, since it is used
+    /// internally to handle the cross references. The value of the map
+    /// should be PRE_HEAP (-1) for each element.
     explicit SimpleBucketHeap(ItemIntMap &map)
       : _iim(map), _free(-1), _num(0), _minimum(0) {}
 
-    /// \brief The number of items stored in the heap.
-    ///
-    /// This function returns the number of items stored in the heap.
+    /// \brief Returns the number of items stored in the heap.
+    ///
+    /// The number of items stored in the heap.
     int size() const { return _num; }
 
-    /// \brief Check if the heap is empty.
-    ///
-    /// This function returns \c true if the heap is empty.
+    /// \brief Checks if the heap stores no items.
+    ///
+    /// Returns \c true if and only if the heap stores no items.
     bool empty() const { return _num == 0; }
 
-    /// \brief Make the heap empty.
-    ///
-    /// This functon makes the heap empty.
-    /// It does not change the cross reference map. If you want to reuse
-    /// a heap that is not surely empty, you should first clear it and
-    /// then you should set the cross reference map to \c PRE_HEAP
-    /// for each item.
+    /// \brief Make empty this heap.
+    ///
+    /// Make empty this heap. It does not change the cross reference
+    /// map.  If you want to reuse a heap what is not surely empty you
+    /// should first clear the heap and after that you should set the
+    /// cross reference map for each item to \c PRE_HEAP.
     void clear() {
       _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0;
@@ -465 +441 @@
     /// \brief Insert a pair of item and priority into the heap.
     ///
-    /// This function inserts \c p.first to the heap with priority
-    /// \c p.second.
+    /// Adds \c p.first to the heap with priority \c p.second.
     /// \param p The pair to insert.
-    /// \pre \c p.first must not be stored in the heap.
     void push(const Pair& p) {
       push(p.first, p.second);
@@ -475 +449 @@
     /// \brief Insert an item into the heap with the given priority.
     ///
-    /// This function inserts the given item into the heap with the
-    /// given priority.
+    /// Adds \c i to the heap with priority \c p.
     /// \param i The item to insert.
     /// \param p The priority of the item.
-    /// \pre \e i must not be stored in the heap.
     void push(const Item &i, const Prio &p) {
       int idx;
@@ -500 +472 @@
     }
 
-    /// \brief Return the item having minimum priority.
-    ///
-    /// This function returns the item having minimum priority.
-    /// \pre The heap must be non-empty.
+    /// \brief Returns the item with minimum priority.
+    ///
+    /// This method returns the item with minimum priority.
+    /// \pre The heap must be nonempty.
     Item top() const {
       while (_first[_minimum] == -1) {
@@ -511 +483 @@
     }
 
-    /// \brief The minimum priority.
-    ///
-    /// This function returns the minimum priority.
-    /// \pre The heap must be non-empty.
+    /// \brief Returns the minimum priority.
+    ///
+    /// It returns the minimum priority.
+    /// \pre The heap must be nonempty.
     Prio prio() const {
       while (_first[_minimum] == -1) {
@@ -522 +494 @@
     }
 
-    /// \brief Remove the item having minimum priority.
-    ///
-    /// This function removes the item having minimum priority.
+    /// \brief Deletes the item with minimum priority.
+    ///
+    /// This method deletes the item with minimum priority from the heap.
     /// \pre The heap must be non-empty.
     void pop() {
@@ -538 +510 @@
     }
 
-    /// \brief The priority of the given item.
-    ///
-    /// This function returns the priority of the given item.
-    /// \param i The item.
-    /// \pre \e i must be in the heap.
-    /// \warning This operator is not a constant time function because
-    /// it scans the whole data structure to find the proper value.
+    /// \brief Returns the priority of \c i.
+    ///
+    /// This function returns the priority of item \c i.
+    /// \warning This operator is not a constant time function
+    /// because it scans the whole data structure to find the proper
+    /// value.
+    /// \pre \c i must be in the heap.
+    /// \param i The item.
     Prio operator[](const Item &i) const {
-      for (int k = 0; k < int(_first.size()); ++k) {
+      for (int k = 0; k < _first.size(); ++k) {
         int idx = _first[k];
         while (idx != -1) {
@@ -558 +531 @@
     }
 
-    /// \brief Return the state of an item.
-    ///
-    /// This method returns \c PRE_HEAP if the given item has never
-    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
-    /// and \c POST_HEAP otherwise.
-    /// In the latter case it is possible that the item will get back
-    /// to the heap again.
+    /// \brief Returns if \c item is in, has already been in, or has
+    /// never been in the heap.
+    ///
+    /// This method returns PRE_HEAP if \c item has never been in the
+    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
+    /// otherwise. In the latter case it is possible that \c item will
+    /// get back to the heap again.
     /// \param i The item.
     State state(const Item &i) const {

lemon/circulation.h

@@ -73 +73 @@
     /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
     /// concept.
-#ifdef DOXYGEN
-    typedef GR::ArcMap<Value> FlowMap;
-#else
     typedef typename Digraph::template ArcMap<Value> FlowMap;
-#endif
 
     /// \brief Instantiates a FlowMap.
@@ -92 +88 @@
     /// The elevator type used by the algorithm.
     ///
-    /// \sa Elevator, LinkedElevator
-#ifdef DOXYGEN
-    typedef lemon::Elevator<GR, GR::Node> Elevator;
-#else
+    /// \sa Elevator
+    /// \sa LinkedElevator
     typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
-#endif
 
     /// \brief Instantiates an Elevator.
@@ -458 +451 @@
     }
 
-    /// \brief Sets the tolerance used by the algorithm.
-    ///
-    /// Sets the tolerance object used by the algorithm.
-    /// \return <tt>(*this)</tt>
-    Circulation& tolerance(const Tolerance& tolerance) {
+    /// \brief Sets the tolerance used by algorithm.
+    ///
+    /// Sets the tolerance used by algorithm.
+    Circulation& tolerance(const Tolerance& tolerance) const {
       _tol = tolerance;
       return *this;
@@ -469 +461 @@
     /// \brief Returns a const reference to the tolerance.
     ///
-    /// Returns a const reference to the tolerance object used by
-    /// the algorithm.
+    /// Returns a const reference to the tolerance.
     const Tolerance& tolerance() const {
-      return _tol;
+      return tolerance;
     }
 
     /// \name Execution Control
     /// The simplest way to execute the algorithm is to call \ref run().\n
-    /// If you need better control on the initial solution or the execution,
-    /// you have to call one of the \ref init() functions first, then
+    /// If you need more control on the initial solution or the execution,
+    /// first you have to call one of the \ref init() functions, then
     /// the \ref start() function.
 

lemon/concepts/heap.h

@@ -17 +17 @@
  */
 
-#ifndef LEMON_CONCEPTS_HEAP_H
-#define LEMON_CONCEPTS_HEAP_H
-
 ///\ingroup concept
 ///\file
 ///\brief The concept of heaps.
 
+#ifndef LEMON_CONCEPTS_HEAP_H
+#define LEMON_CONCEPTS_HEAP_H
+
 #include <lemon/core.h>
 #include <lemon/concept_check.h>
@@ -36 +36 @@
     /// \brief The heap concept.
     ///
-    /// This concept class describes the main interface of heaps.
-    /// The various \ref heaps "heap structures" are efficient
-    /// implementations of the abstract data type \e priority \e queue.
-    /// They store items with specified values called \e priorities
-    /// in such a way that finding and removing the item with minimum
-    /// priority are efficient. The basic operations are adding and
-    /// erasing items, changing the priority of an item, etc.
+    /// Concept class describing the main interface of heaps. A \e heap
+    /// is a data structure for storing items with specified values called
+    /// \e priorities in such a way that finding the item with minimum
+    /// priority is efficient. In a heap one can change the priority of an
+    /// item, add or erase an item, etc.
     ///
-    /// Heaps are crucial in several algorithms, such as Dijkstra and Prim.
-    /// Any class that conforms to this concept can be used easily in such
-    /// algorithms.
-    ///
-    /// \tparam PR Type of the priorities of the items.
-    /// \tparam IM A read-writable item map with \c int values, used
+    /// \tparam PR Type of the priority of the items.
+    /// \tparam IM A read and writable item map with int values, used
     /// internally to handle the cross references.
-    /// \tparam CMP A functor class for comparing the priorities.
+    /// \tparam Comp A functor class for the ordering of the priorities.
     /// The default is \c std::less<PR>.
 #ifdef DOXYGEN
-    template <typename PR, typename IM, typename CMP>
+    template <typename PR, typename IM, typename Comp = std::less<PR> >
 #else
-    template <typename PR, typename IM, typename CMP = std::less<PR> >
+    template <typename PR, typename IM>
 #endif
     class Heap {
@@ -71 +65 @@
       ///
       /// Each item has a state associated to it. It can be "in heap",
-      /// "pre-heap" or "post-heap". The latter two are indifferent from the
-      /// heap's point of view, but may be useful to the user.
+      /// "pre heap" or "post heap". The later two are indifferent
+      /// from the point of view of the heap, but may be useful for
+      /// the user.
       ///
       /// The item-int map must be initialized in such way that it assigns
@@ -78 +73 @@
       enum State {
         IN_HEAP = 0,    ///< = 0. The "in heap" state constant.
-        PRE_HEAP = -1,  ///< = -1. The "pre-heap" state constant.
-        POST_HEAP = -2  ///< = -2. The "post-heap" state constant.
+        PRE_HEAP = -1,  ///< = -1. The "pre heap" state constant.
+        POST_HEAP = -2  ///< = -2. The "post heap" state constant.
       };
 
-      /// \brief Constructor.
-      ///
-      /// Constructor.
+      /// \brief The constructor.
+      ///
+      /// The constructor.
       /// \param map A map that assigns \c int values to keys of type
       /// \c Item. It is used internally by the heap implementations to
       /// handle the cross references. The assigned value must be
-      /// \c PRE_HEAP (<tt>-1</tt>) for each item.
+      /// \c PRE_HEAP (<tt>-1</tt>) for every item.
       explicit Heap(ItemIntMap &map) {}
 
-      /// \brief Constructor.
-      ///
-      /// Constructor.
-      /// \param map A map that assigns \c int values to keys of type
-      /// \c Item. It is used internally by the heap implementations to
-      /// handle the cross references. The assigned value must be
-      /// \c PRE_HEAP (<tt>-1</tt>) for each item.
-      /// \param comp The function object used for comparing the priorities.
-      explicit Heap(ItemIntMap &map, const CMP &comp) {}
-
       /// \brief The number of items stored in the heap.
       ///
-      /// This function returns the number of items stored in the heap.
+      /// Returns the number of items stored in the heap.
       int size() const { return 0; }
 
-      /// \brief Check if the heap is empty.
-      ///
-      /// This function returns \c true if the heap is empty.
+      /// \brief Checks if the heap is empty.
+      ///
+      /// Returns \c true if the heap is empty.
       bool empty() const { return false; }
 
-      /// \brief Make the heap empty.
-      ///
-      /// This functon makes the heap empty.
-      /// It does not change the cross reference map. If you want to reuse
-      /// a heap that is not surely empty, you should first clear it and
-      /// then you should set the cross reference map to \c PRE_HEAP
-      /// for each item.
-      void clear() {}
-
-      /// \brief Insert an item into the heap with the given priority.
-      ///
-      /// This function inserts the given item into the heap with the
-      /// given priority.
+      /// \brief Makes the heap empty.
+      ///
+      /// Makes the heap empty.
+      void clear();
+
+      /// \brief Inserts an item into the heap with the given priority.
+      ///
+      /// Inserts the given item into the heap with the given priority.
       /// \param i The item to insert.
       /// \param p The priority of the item.
-      /// \pre \e i must not be stored in the heap.
       void push(const Item &i, const Prio &p) {}
 
-      /// \brief Return the item having minimum priority.
-      ///
-      /// This function returns the item having minimum priority.
+      /// \brief Returns the item having minimum priority.
+      ///
+      /// Returns the item having minimum priority.
       /// \pre The heap must be non-empty.
       Item top() const {}
@@ -137 +116 @@
       /// \brief The minimum priority.
       ///
-      /// This function returns the minimum priority.
+      /// Returns the minimum priority.
       /// \pre The heap must be non-empty.
       Prio prio() const {}
 
-      /// \brief Remove the item having minimum priority.
-      ///
-      /// This function removes the item having minimum priority.
+      /// \brief Removes the item having minimum priority.
+      ///
+      /// Removes the item having minimum priority.
       /// \pre The heap must be non-empty.
       void pop() {}
 
-      /// \brief Remove the given item from the heap.
-      ///
-      /// This function removes the given item from the heap if it is
-      /// already stored.
+      /// \brief Removes an item from the heap.
+      ///
+      /// Removes the given item from the heap if it is already stored.
       /// \param i The item to delete.
-      /// \pre \e i must be in the heap.
       void erase(const Item &i) {}
 
-      /// \brief The priority of the given item.
-      ///
-      /// This function returns the priority of the given item.
-      /// \param i The item.
-      /// \pre \e i must be in the heap.
+      /// \brief The priority of an item.
+      ///
+      /// Returns the priority of the given item.
+      /// \param i The item.
+      /// \pre \c i must be in the heap.
       Prio operator[](const Item &i) const {}
 
-      /// \brief Set the priority of an item or insert it, if it is
+      /// \brief Sets the priority of an item or inserts it, if it is
       /// not stored in the heap.
       ///
       /// This method sets the priority of the given item if it is
-      /// already stored in the heap. Otherwise it inserts the given
-      /// item into the heap with the given priority.
+      /// already stored in the heap.
+      /// Otherwise it inserts the given item with the given priority.
       ///
       /// \param i The item.
@@ -173 +150 @@
       void set(const Item &i, const Prio &p) {}
 
-      /// \brief Decrease the priority of an item to the given value.
-      ///
-      /// This function decreases the priority of an item to the given value.
+      /// \brief Decreases the priority of an item to the given value.
+      ///
+      /// Decreases the priority of an item to the given value.
       /// \param i The item.
       /// \param p The priority.
-      /// \pre \e i must be stored in the heap with priority at least \e p.
+      /// \pre \c i must be stored in the heap with priority at least \c p.
       void decrease(const Item &i, const Prio &p) {}
 
-      /// \brief Increase the priority of an item to the given value.
-      ///
-      /// This function increases the priority of an item to the given value.
+      /// \brief Increases the priority of an item to the given value.
+      ///
+      /// Increases the priority of an item to the given value.
       /// \param i The item.
       /// \param p The priority.
-      /// \pre \e i must be stored in the heap with priority at most \e p.
+      /// \pre \c i must be stored in the heap with priority at most \c p.
       void increase(const Item &i, const Prio &p) {}
 
-      /// \brief Return the state of an item.
+      /// \brief Returns if an item is in, has already been in, or has
+      /// never been in the heap.
       ///
       /// This method returns \c PRE_HEAP if the given item has never
@@ -199 +177 @@
       State state(const Item &i) const {}
 
-      /// \brief Set the state of an item in the heap.
-      ///
-      /// This function sets the state of the given item in the heap.
-      /// It can be used to manually clear the heap when it is important
-      /// to achive better time complexity.
+      /// \brief Sets the state of an item in the heap.
+      ///
+      /// Sets the state of the given item in the heap. It can be used
+      /// to manually clear the heap when it is important to achive the
+      /// better time complexity.
       /// \param i The item.
       /// \param st The state. It should not be \c IN_HEAP.

lemon/concepts/maps.h

@@ -183 +183 @@
       template<typename _ReferenceMap>
       struct Constraints {
-        typename enable_if<typename _ReferenceMap::ReferenceMapTag, void>::type
-        constraints() {
+        void constraints() {
           checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();
           ref = m[key];

lemon/dfs.h

@@ -48 +48 @@
     ///The type of the map that stores the predecessor
     ///arcs of the %DFS paths.
-    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
     ///Instantiates a \c PredMap.
@@ -63 +63 @@
 
     ///The type of the map that indicates which nodes are processed.
-    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
-    ///By default it is a NullMap.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     ///Instantiates a \c ProcessedMap.
@@ -83 +82 @@
 
     ///The type of the map that indicates which nodes are reached.
-    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     typedef typename Digraph::template NodeMap<bool> ReachedMap;
     ///Instantiates a \c ReachedMap.
@@ -98 +97 @@
 
     ///The type of the map that stores the distances of the nodes.
-    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef typename Digraph::template NodeMap<int> DistMap;
     ///Instantiates a \c DistMap.
@@ -226 +225 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///\c PredMap type.
-    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
@@ -246 +245 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///\c DistMap type.
-    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
@@ -266 +265 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///\c ReachedMap type.
-    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     template <class T>
     struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
@@ -286 +285 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///\c ProcessedMap type.
-    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
@@ -413 +412 @@
     ///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 better control on the execution, you have to call
-    ///\ref init() first, then you can add a source node with \ref addSource()
+    ///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()
     ///and perform the actual computation with \ref start().
     ///This procedure can be repeated if there are nodes that have not
@@ -671 +670 @@
     ///@{
 
-    ///The DFS path to the given node.
-
-    ///Returns the DFS path to the given node from the root(s).
+    ///The DFS path to a node.
+
+    ///Returns the DFS path to a node.
     ///
     ///\warning \c t should be reached from the root(s).
@@ -681 +680 @@
     Path path(Node t) const { return Path(*G, *_pred, t); }
 
-    ///The distance of the given node from the root(s).
-
-    ///Returns the distance of the given node from the root(s).
+    ///The distance of a node from the root(s).
+
+    ///Returns the distance of a node from the root(s).
     ///
     ///\warning If node \c v is not reached from the root(s), then
@@ -692 +691 @@
     int dist(Node v) const { return (*_dist)[v]; }
 
-    ///Returns the 'previous arc' of the %DFS tree for the given node.
+    ///Returns the 'previous arc' of the %DFS tree for a node.
 
     ///This function returns the 'previous arc' of the %DFS tree for the
@@ -700 +699 @@
     ///
     ///The %DFS tree used here is equal to the %DFS tree used in
-    ///\ref predNode() and \ref predMap().
+    ///\ref predNode().
     ///
     ///\pre Either \ref run(Node) "run()" or \ref init()
@@ -706 +705 @@
     Arc predArc(Node v) const { return (*_pred)[v];}
 
-    ///Returns the 'previous node' of the %DFS tree for the given node.
+    ///Returns the 'previous node' of the %DFS tree.
 
     ///This function returns the 'previous node' of the %DFS
     ///tree for the node \c v, i.e. it returns the last but one node
-    ///of a %DFS path from a root to \c v. It is \c INVALID
+    ///from 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() and \ref predMap().
+    ///\ref predArc().
     ///
     ///\pre Either \ref run(Node) "run()" or \ref init()
@@ -735 +734 @@
     ///
     ///Returns a const reference to the node map that stores the predecessor
-    ///arcs, which form the DFS tree (forest).
+    ///arcs, which form the DFS tree.
     ///
     ///\pre Either \ref run(Node) "run()" or \ref init()
@@ -741 +740 @@
     const PredMap &predMap() const { return *_pred;}
 
-    ///Checks if the given node. node is reached from the root(s).
+    ///Checks if a node is reached from the root(s).
 
     ///Returns \c true if \c v is reached from the root(s).
@@ -767 +766 @@
     ///The type of the map that stores the predecessor
     ///arcs of the %DFS paths.
-    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
     ///Instantiates a PredMap.
@@ -782 +781 @@
 
     ///The type of the map that indicates which nodes are processed.
-    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     ///By default it is a NullMap.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
@@ -802 +801 @@
 
     ///The type of the map that indicates which nodes are reached.
-    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     typedef typename Digraph::template NodeMap<bool> ReachedMap;
     ///Instantiates a ReachedMap.
@@ -817 +816 @@
 
     ///The type of the map that stores the distances of the nodes.
-    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef typename Digraph::template NodeMap<int> DistMap;
     ///Instantiates a DistMap.
@@ -832 +831 @@
 
     ///The type of the DFS paths.
-    ///It must conform to the \ref concepts::Path "Path" concept.
+    ///It must meet the \ref concepts::Path "Path" concept.
     typedef lemon::Path<Digraph> Path;
   };
@@ -838 +837 @@
   /// Default traits class used by DfsWizard
 
-  /// Default traits class used by DfsWizard.
-  /// \tparam GR The type of the digraph.
+  /// 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.
   template<class GR>
   class DfsWizardBase : public DfsWizardDefaultTraits<GR>
@@ -867 +870 @@
     /// Constructor.
 
-    /// This constructor does not require parameters, it initiates
+    /// This constructor does not require parameters, therefore it initiates
     /// all of the attributes to \c 0.
     DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
@@ -897 +900 @@
     typedef TR Base;
 
+    ///The type of the digraph the algorithm runs on.
     typedef typename TR::Digraph Digraph;
 
@@ -904 +908 @@
     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;
 
@@ -990 +1000 @@
       SetPredMapBase(const TR &b) : TR(b) {}
     };
-
-    ///\brief \ref named-templ-param "Named parameter" for setting
-    ///the predecessor map.
-    ///
-    ///\ref named-templ-param "Named parameter" function for setting
-    ///the map that stores the predecessor arcs of the nodes.
+    ///\brief \ref named-func-param "Named parameter"
+    ///for setting PredMap object.
+    ///
+    ///\ref named-func-param "Named parameter"
+    ///for setting PredMap object.
     template<class T>
     DfsWizard<SetPredMapBase<T> > predMap(const T &t)
@@ -1009 +1018 @@
       SetReachedMapBase(const TR &b) : TR(b) {}
     };
-
-    ///\brief \ref named-templ-param "Named parameter" for setting
-    ///the reached map.
-    ///
-    ///\ref named-templ-param "Named parameter" function for setting
-    ///the map that indicates which nodes are reached.
+    ///\brief \ref named-func-param "Named parameter"
+    ///for setting ReachedMap object.
+    ///
+    /// \ref named-func-param "Named parameter"
+    ///for setting ReachedMap object.
     template<class T>
     DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
@@ -1028 +1036 @@
       SetDistMapBase(const TR &b) : TR(b) {}
     };
-
-    ///\brief \ref named-templ-param "Named parameter" for setting
-    ///the distance map.
-    ///
-    ///\ref named-templ-param "Named parameter" function for setting
-    ///the map that stores the distances of the nodes calculated
-    ///by the algorithm.
+    ///\brief \ref named-func-param "Named parameter"
+    ///for setting DistMap object.
+    ///
+    /// \ref named-func-param "Named parameter"
+    ///for setting DistMap object.
     template<class T>
     DfsWizard<SetDistMapBase<T> > distMap(const T &t)
@@ -1048 +1054 @@
       SetProcessedMapBase(const TR &b) : TR(b) {}
     };
-
-    ///\brief \ref named-func-param "Named parameter" for setting
-    ///the processed map.
-    ///
-    ///\ref named-templ-param "Named parameter" function for setting
-    ///the map that indicates which nodes are processed.
+    ///\brief \ref named-func-param "Named parameter"
+    ///for setting ProcessedMap object.
+    ///
+    /// \ref named-func-param "Named parameter"
+    ///for setting ProcessedMap object.
     template<class T>
     DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
@@ -1204 +1209 @@
     ///
     /// The type of the map that indicates which nodes are reached.
-    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     typedef typename Digraph::template NodeMap<bool> ReachedMap;
 
@@ -1365 +1370 @@
     /// 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 better control on the execution, you have to call
-    /// \ref init() first, then you can add a source node with \ref addSource()
+    /// 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()
     /// and perform the actual computation with \ref start().
     /// This procedure can be repeated if there are nodes that have not
@@ -1616 +1621 @@
     ///@{
 
-    /// \brief Checks if the given node is reached from the root(s).
+    /// \brief Checks if a node is reached from the root(s).
     ///
     /// Returns \c true if \c v is reached from the root(s).

lemon/dijkstra.h

@@ -71 +71 @@
 
     ///The type of the map that stores the arc lengths.
-    ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
+    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
     typedef LEN LengthMap;
-    ///The type of the arc lengths.
+    ///The type of the length of the arcs.
     typedef typename LEN::Value Value;
 
@@ -117 +117 @@
     ///The type of the map that stores the predecessor
     ///arcs of the shortest paths.
-    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
     ///Instantiates a \c PredMap.
@@ -132 +132 @@
 
     ///The type of the map that indicates which nodes are processed.
-    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     ///By default it is a NullMap.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
@@ -152 +152 @@
 
     ///The type of the map that stores the distances of the nodes.
-    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
     ///Instantiates a \c DistMap.
@@ -169 +169 @@
   /// \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
@@ -206 +202 @@
     typedef typename TR::Digraph Digraph;
 
-    ///The type of the arc lengths.
+    ///The type of the length of the arcs.
     typedef typename TR::LengthMap::Value Value;
     ///The type of the map that stores the arc lengths.
@@ -309 +305 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///\c PredMap type.
-    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetPredMap
@@ -330 +326 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///\c DistMap type.
-    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetDistMap
@@ -351 +347 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///\c ProcessedMap type.
-    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetProcessedMap
@@ -448 +444 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///\c OperationTraits type.
-    /// For more information see \ref DijkstraDefaultOperationTraits.
     template <class T>
     struct SetOperationTraits
@@ -590 +585 @@
     ///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 better control on the execution, you have to call
-    ///\ref init() first, then you can add several source nodes with
+    ///If you need more control on the execution, first you have to call
+    ///\ref init(), 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.
@@ -807 +802 @@
     ///The results of the %Dijkstra algorithm can be obtained using these
     ///functions.\n
-    ///Either \ref run(Node) "run()" or \ref init() should be called
+    ///Either \ref run(Node) "run()" or \ref start() should be called
     ///before using them.
 
     ///@{
 
-    ///The shortest path to the given node.
-
-    ///Returns the shortest path to the given node from the root(s).
+    ///The shortest path to a node.
+
+    ///Returns the shortest path to a node.
     ///
     ///\warning \c t should be reached from the root(s).
@@ -822 +817 @@
     Path path(Node t) const { return Path(*G, *_pred, t); }
 
-    ///The distance of the given node from the root(s).
-
-    ///Returns the distance of the given node from the root(s).
+    ///The distance of a node from the root(s).
+
+    ///Returns the distance of a node from the root(s).
     ///
     ///\warning If node \c v is not reached from the root(s), then
@@ -833 +828 @@
     Value dist(Node v) const { return (*_dist)[v]; }
 
-    ///\brief Returns the 'previous arc' of the shortest path tree for
-    ///the given node.
-    ///
+    ///Returns the 'previous arc' of the shortest path tree for a 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
@@ -842 +836 @@
     ///
     ///The shortest path tree used here is equal to the shortest path
-    ///tree used in \ref predNode() and \ref predMap().
+    ///tree used in \ref predNode().
     ///
     ///\pre Either \ref run(Node) "run()" or \ref init()
@@ -848 +842 @@
     Arc predArc(Node v) const { return (*_pred)[v]; }
 
-    ///\brief Returns the 'previous node' of the shortest path tree for
-    ///the given node.
-    ///
+    ///Returns the 'previous node' of the shortest path tree for a 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
-    ///of a shortest path from a root to \c v. It is \c INVALID
+    ///from 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() and \ref predMap().
+    ///tree used in \ref predArc().
     ///
     ///\pre Either \ref run(Node) "run()" or \ref init()
@@ -878 +871 @@
     ///
     ///Returns a const reference to the node map that stores the predecessor
-    ///arcs, which form the shortest path tree (forest).
+    ///arcs, which form the shortest path tree.
     ///
     ///\pre Either \ref run(Node) "run()" or \ref init()
@@ -884 +877 @@
     const PredMap &predMap() const { return *_pred;}
 
-    ///Checks if the given node is reached from the root(s).
+    ///Checks if a node is reached from the root(s).
 
     ///Returns \c true if \c v is reached from the root(s).
@@ -903 +896 @@
                                           Heap::POST_HEAP; }
 
-    ///The current distance of the given node from the root(s).
-
-    ///Returns the current distance of the given node from the root(s).
+    ///The current distance of a node from the root(s).
+
+    ///Returns the current distance of a node from the root(s).
     ///It may be decreased in the following processes.
     ///
@@ -932 +925 @@
 
     ///The type of the map that stores the arc lengths.
-    ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
+    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
     typedef LEN LengthMap;
-    ///The type of the arc lengths.
+    ///The type of the length of the arcs.
     typedef typename LEN::Value Value;
 
@@ -981 +974 @@
     ///The type of the map that stores the predecessor
     ///arcs of the shortest paths.
-    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
     ///Instantiates a PredMap.
@@ -996 +989 @@
 
     ///The type of the map that indicates which nodes are processed.
-    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     ///By default it is a NullMap.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
@@ -1016 +1009 @@
 
     ///The type of the map that stores the distances of the nodes.
-    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
+    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
     ///Instantiates a DistMap.
@@ -1031 +1024 @@
 
     ///The type of the shortest paths.
-    ///It must conform to the \ref concepts::Path "Path" concept.
+    ///It must meet the \ref concepts::Path "Path" concept.
     typedef lemon::Path<Digraph> Path;
   };
@@ -1037 +1030 @@
   /// Default traits class used by DijkstraWizard
 
-  /// Default traits class used by DijkstraWizard.
-  /// \tparam GR The type of the digraph.
-  /// \tparam LEN The type of the length map.
+  /// 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.
   template<typename GR, typename LEN>
   class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN>
@@ -1098 +1094 @@
     typedef TR Base;
 
+    ///The type of the digraph the algorithm runs on.
     typedef typename TR::Digraph Digraph;
 
@@ -1105 +1102 @@
     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;
 
@@ -1182 +1187 @@
       SetPredMapBase(const TR &b) : TR(b) {}
     };
-
-    ///\brief \ref named-templ-param "Named parameter" for setting
-    ///the predecessor map.
-    ///
-    ///\ref named-templ-param "Named parameter" function for setting
-    ///the map that stores the predecessor arcs of the nodes.
+    ///\brief \ref named-func-param "Named parameter"
+    ///for setting PredMap object.
+    ///
+    ///\ref named-func-param "Named parameter"
+    ///for setting PredMap object.
     template<class T>
     DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
@@ -1201 +1205 @@
       SetDistMapBase(const TR &b) : TR(b) {}
     };
-
-    ///\brief \ref named-templ-param "Named parameter" for setting
-    ///the distance map.
-    ///
-    ///\ref named-templ-param "Named parameter" function for setting
-    ///the map that stores the distances of the nodes calculated
-    ///by the algorithm.
+    ///\brief \ref named-func-param "Named parameter"
+    ///for setting DistMap object.
+    ///
+    ///\ref named-func-param "Named parameter"
+    ///for setting DistMap object.
     template<class T>
     DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
@@ -1221 +1223 @@
       SetProcessedMapBase(const TR &b) : TR(b) {}
     };
-
-    ///\brief \ref named-func-param "Named parameter" for setting
-    ///the processed map.
-    ///
-    ///\ref named-templ-param "Named parameter" function for setting
-    ///the map that indicates which nodes are processed.
+    ///\brief \ref named-func-param "Named parameter"
+    ///for setting ProcessedMap object.
+    ///
+    /// \ref named-func-param "Named parameter"
+    ///for setting ProcessedMap object.
     template<class T>
     DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
@@ -1239 +1240 @@
       SetPathBase(const TR &b) : TR(b) {}
     };
-
     ///\brief \ref named-func-param "Named parameter"
     ///for getting the shortest path to the target node.

lemon/dim2.h

@@ -22 +22 @@
 #include <iostream>
 
-///\ingroup geomdat
+///\ingroup misc
 ///\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 {
@@ -34 +41 @@
   namespace dim2 {
 
-  /// \addtogroup geomdat
+  /// \addtogroup misc
   /// @{
 

lemon/fib_heap.h

@@ -21 +21 @@
 
 ///\file
-///\ingroup heaps
-///\brief Fibonacci heap implementation.
+///\ingroup auxdat
+///\brief Fibonacci Heap implementation.
 
 #include <vector>
-#include <utility>
 #include <functional>
 #include <lemon/math.h>
@@ -31 +30 @@
 namespace lemon {
 
-  /// \ingroup heaps
+  /// \ingroup auxdat
   ///
-  /// \brief Fibonacci heap data structure.
+  ///\brief Fibonacci Heap.
   ///
-  /// This class implements the \e Fibonacci \e heap data structure.
-  /// It fully conforms to the \ref concepts::Heap "heap concept".
+  ///This class implements the \e Fibonacci \e heap data structure. A \e heap
+  ///is a data structure for storing items with specified values called \e
+  ///priorities in such a way that finding the item with minimum priority is
+  ///efficient. \c CMP specifies the ordering of the priorities. In a heap
+  ///one can change the priority of an item, add or erase an item, etc.
   ///
-  /// The methods \ref increase() and \ref erase() are not efficient in a
-  /// Fibonacci heap. In case of many calls of these operations, it is
-  /// better to use other heap structure, e.g. \ref BinHeap "binary heap".
+  ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
+  ///heap. In case of many calls to these operations, it is better to use a
+  ///\ref BinHeap "binary heap".
   ///
-  /// \tparam PR Type of the priorities of the items.
-  /// \tparam IM A read-writable item map with \c int values, used
-  /// internally to handle the cross references.
-  /// \tparam CMP A functor class for comparing the priorities.
-  /// The default is \c std::less<PR>.
+  ///\param PRIO Type of the priority of the items.
+  ///\param IM A read and writable Item int map, used internally
+  ///to handle the cross references.
+  ///\param CMP A class for the ordering of the priorities. The
+  ///default is \c std::less<PRIO>.
+  ///
+  ///\sa BinHeap
+  ///\sa Dijkstra
 #ifdef DOXYGEN
-  template <typename PR, typename IM, typename CMP>
+  template <typename PRIO, typename IM, typename CMP>
 #else
-  template <typename PR, typename IM, typename CMP = std::less<PR> >
+  template <typename PRIO, typename IM, typename CMP = std::less<PRIO> >
 #endif
   class FibHeap {
   public:
-
-    /// Type of the item-int map.
+    ///\e
     typedef IM ItemIntMap;
-    /// Type of the priorities.
-    typedef PR Prio;
-    /// Type of the items stored in the heap.
+    ///\e
+    typedef PRIO Prio;
+    ///\e
     typedef typename ItemIntMap::Key Item;
-    /// Type of the item-priority pairs.
+    ///\e
     typedef std::pair<Item,Prio> Pair;
-    /// Functor type for comparing the priorities.
+    ///\e
     typedef CMP Compare;
 
@@ -77 +81 @@
   public:
 
-    /// \brief Type to represent the states of the items.
-    ///
-    /// Each item has a state associated to it. It can be "in heap",
-    /// "pre-heap" or "post-heap". The latter two are indifferent from the
+    /// \brief Type to represent the items states.
+    ///
+    /// Each Item element have a state associated to it. It may be "in heap",
+    /// "pre heap" or "post heap". The latter two are indifferent from the
     /// heap's point of view, but may be useful to the user.
     ///
@@ -91 +95 @@
     };
 
-    /// \brief Constructor.
-    ///
-    /// Constructor.
-    /// \param map A map that assigns \c int values to the items.
-    /// It is used internally to handle the cross references.
-    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
+    /// \brief The constructor
+    ///
+    /// \c map should be given to the constructor, since it is
+    ///   used internally to handle the cross references.
     explicit FibHeap(ItemIntMap &map)
       : _minimum(0), _iim(map), _num() {}
 
-    /// \brief Constructor.
-    ///
-    /// Constructor.
-    /// \param map A map that assigns \c int values to the items.
-    /// It is used internally to handle the cross references.
-    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
-    /// \param comp The function object used for comparing the priorities.
+    /// \brief The constructor
+    ///
+    /// \c map should be given to the constructor, since it is used
+    /// internally to handle the cross references. \c comp is an
+    /// object for ordering of the priorities.
     FibHeap(ItemIntMap &map, const Compare &comp)
       : _minimum(0), _iim(map), _comp(comp), _num() {}
@@ -112 +112 @@
     /// \brief The number of items stored in the heap.
     ///
-    /// This function returns the number of items stored in the heap.
+    /// Returns the number of items stored in the heap.
     int size() const { return _num; }
 
-    /// \brief Check if the heap is empty.
-    ///
-    /// This function returns \c true if the heap is empty.
+    /// \brief Checks if the heap stores no items.
+    ///
+    ///   Returns \c true if and only if the heap stores no items.
     bool empty() const { return _num==0; }
 
-    /// \brief Make the heap empty.
-    ///
-    /// This functon makes the heap empty.
-    /// It does not change the cross reference map. If you want to reuse
-    /// a heap that is not surely empty, you should first clear it and
-    /// then you should set the cross reference map to \c PRE_HEAP
-    /// for each item.
+    /// \brief Make empty this heap.
+    ///
+    /// Make empty this heap. It does not change the cross reference
+    /// map.  If you want to reuse a heap what is not surely empty you
+    /// should first clear the heap and after that you should set the
+    /// cross reference map for each item to \c PRE_HEAP.
     void clear() {
       _data.clear(); _minimum = 0; _num = 0;
     }
 
-    /// \brief Insert an item into the heap with the given priority.
-    ///
-    /// This function inserts the given item into the heap with the
-    /// given priority.
-    /// \param item The item to insert.
-    /// \param prio The priority of the item.
-    /// \pre \e item must not be stored in the heap.
-    void push (const Item& item, const Prio& prio) {
+    /// \brief \c item gets to the heap with priority \c value independently
+    /// if \c item was already there.
+    ///
+    /// This method calls \ref push(\c item, \c value) if \c item is not
+    /// stored in the heap and it calls \ref decrease(\c item, \c value) or
+    /// \ref increase(\c item, \c value) otherwise.
+    void set (const Item& item, const Prio& value) {
+      int i=_iim[item];
+      if ( i >= 0 && _data[i].in ) {
+        if ( _comp(value, _data[i].prio) ) decrease(item, value);
+        if ( _comp(_data[i].prio, value) ) increase(item, value);
+      } else push(item, value);
+    }
+
+    /// \brief Adds \c item to the heap with priority \c value.
+    ///
+    /// Adds \c item to the heap with priority \c value.
+    /// \pre \c item must not be stored in the heap.
+    void push (const Item& item, const Prio& value) {
       int i=_iim[item];
       if ( i < 0 ) {
@@ -159 +169 @@
         _data[_minimum].right_neighbor=i;
         _data[i].left_neighbor=_minimum;
-        if ( _comp( prio, _data[_minimum].prio) ) _minimum=i;
+        if ( _comp( value, _data[_minimum].prio) ) _minimum=i;
       } else {
         _data[i].right_neighbor=_data[i].left_neighbor=i;
         _minimum=i;
       }
-      _data[i].prio=prio;
+      _data[i].prio=value;
       ++_num;
     }
 
-    /// \brief Return the item having minimum priority.
-    ///
-    /// This function returns the item having minimum priority.
-    /// \pre The heap must be non-empty.
+    /// \brief Returns the item with minimum priority relative to \c Compare.
+    ///
+    /// This method returns the item with minimum priority relative to \c
+    /// Compare.
+    /// \pre The heap must be nonempty.
     Item top() const { return _data[_minimum].name; }
 
-    /// \brief The minimum priority.
-    ///
-    /// This function returns the minimum priority.
-    /// \pre The heap must be non-empty.
-    Prio prio() const { return _data[_minimum].prio; }
-
-    /// \brief Remove the item having minimum priority.
-    ///
-    /// This function removes the item having minimum priority.
+    /// \brief Returns the minimum priority relative to \c Compare.
+    ///
+    /// It returns the minimum priority relative to \c Compare.
+    /// \pre The heap must be nonempty.
+    const Prio& prio() const { return _data[_minimum].prio; }
+
+    /// \brief Returns the priority of \c item.
+    ///
+    /// It returns the priority of \c item.
+    /// \pre \c item must be in the heap.
+    const Prio& operator[](const Item& item) const {
+      return _data[_iim[item]].prio;
+    }
+
+    /// \brief Deletes the item with minimum priority relative to \c Compare.
+    ///
+    /// This method deletes the item with minimum priority relative to \c
+    /// Compare from the heap.
     /// \pre The heap must be non-empty.
     void pop() {
@@ -189 +209 @@
         _data[_minimum].in=false;
         if ( _data[_minimum].degree!=0 ) {
-          makeRoot(_data[_minimum].child);
+          makeroot(_data[_minimum].child);
           _minimum=_data[_minimum].child;
           balance();
@@ -202 +222 @@
           int last_child=_data[child].left_neighbor;
 
-          makeRoot(child);
+          makeroot(child);
 
           _data[left].right_neighbor=child;
@@ -215 +235 @@
     }
 
-    /// \brief Remove the given item from the heap.
-    ///
-    /// This function removes the given item from the heap if it is
-    /// already stored.
-    /// \param item The item to delete.
-    /// \pre \e item must be in the heap.
+    /// \brief Deletes \c item from the heap.
+    ///
+    /// This method deletes \c item from the heap, if \c item was already
+    /// stored in the heap. It is quite inefficient in Fibonacci heaps.
     void erase (const Item& item) {
       int i=_iim[item];
@@ -235 +253 @@
     }
 
-    /// \brief The priority of the given item.
-    ///
-    /// This function returns the priority of the given item.
-    /// \param item The item.
-    /// \pre \e item must be in the heap.
-    Prio operator[](const Item& item) const {
-      return _data[_iim[item]].prio;
-    }
-
-    /// \brief Set the priority of an item or insert it, if it is
-    /// not stored in the heap.
-    ///
-    /// This method sets the priority of the given item if it is
-    /// already stored in the heap. Otherwise it inserts the given
-    /// item into the heap with the given priority.
-    /// \param item The item.
-    /// \param prio The priority.
-    void set (const Item& item, const Prio& prio) {
+    /// \brief Decreases the priority of \c item to \c value.
+    ///
+    /// This method decreases the priority of \c item to \c value.
+    /// \pre \c item must be stored in the heap with priority at least \c
+    ///   value relative to \c Compare.
+    void decrease (Item item, const Prio& value) {
       int i=_iim[item];
-      if ( i >= 0 && _data[i].in ) {
-        if ( _comp(prio, _data[i].prio) ) decrease(item, prio);
-        if ( _comp(_data[i].prio, prio) ) increase(item, prio);
-      } else push(item, prio);
-    }
-
-    /// \brief Decrease the priority of an item to the given value.
-    ///
-    /// This function decreases the priority of an item to the given value.
-    /// \param item The item.
-    /// \param prio The priority.
-    /// \pre \e item must be stored in the heap with priority at least \e prio.
-    void decrease (const Item& item, const Prio& prio) {
-      int i=_iim[item];
-      _data[i].prio=prio;
+      _data[i].prio=value;
       int p=_data[i].parent;
 
-      if ( p!=-1 && _comp(prio, _data[p].prio) ) {
+      if ( p!=-1 && _comp(value, _data[p].prio) ) {
         cut(i,p);
         cascade(p);
       }
-      if ( _comp(prio, _data[_minimum].prio) ) _minimum=i;
-    }
-
-    /// \brief Increase the priority of an item to the given value.
-    ///
-    /// This function increases the priority of an item to the given value.
-    /// \param item The item.
-    /// \param prio The priority.
-    /// \pre \e item must be stored in the heap with priority at most \e prio.
-    void increase (const Item& item, const Prio& prio) {
+      if ( _comp(value, _data[_minimum].prio) ) _minimum=i;
+    }
+
+    /// \brief Increases the priority of \c item to \c value.
+    ///
+    /// This method sets the priority of \c item to \c value. Though
+    /// there is no precondition on the priority of \c item, this
+    /// method should be used only if it is indeed necessary to increase
+    /// (relative to \c Compare) the priority of \c item, because this
+    /// method is inefficient.
+    void increase (Item item, const Prio& value) {
       erase(item);
-      push(item, prio);
-    }
-
-    /// \brief Return the state of an item.
-    ///
-    /// This method returns \c PRE_HEAP if the given item has never
-    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
-    /// and \c POST_HEAP otherwise.
-    /// In the latter case it is possible that the item will get back
-    /// to the heap again.
-    /// \param item The item.
+      push(item, value);
+    }
+
+
+    /// \brief Returns if \c item is in, has already been in, or has never
+    /// been in the heap.
+    ///
+    /// This method returns PRE_HEAP if \c item has never been in the
+    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
+    /// otherwise. In the latter case it is possible that \c item will
+    /// get back to the heap again.
     State state(const Item &item) const {
       int i=_iim[item];
@@ -306 +299 @@
     }
 
-    /// \brief Set the state of an item in the heap.
-    ///
-    /// This function sets the state of the given item in the heap.
-    /// It can be used to manually clear the heap when it is important
-    /// to achive better time complexity.
+    /// \brief Sets the state of the \c item in the heap.
+    ///
+    /// Sets the state of the \c item in the heap. It can be used to
+    /// manually clear the heap when it is important to achive the
+    /// better time _complexity.
     /// \param i The item.
     /// \param st The state. It should not be \c IN_HEAP.
@@ -373 +366 @@
     }
 
-    void makeRoot(int c) {
+    void makeroot(int c) {
       int s=c;
       do {

lemon/gomory_hu.h

@@ -360 +360 @@
     /// \c t.
     /// \code
-    /// GomoryHu<Graph> gom(g, capacities);
+    /// GomoruHu<Graph> gom(g, capacities);
     /// gom.run();
     /// int cnt=0;
-    /// for(GomoryHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
+    /// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
     /// \endcode
     class MinCutNodeIt
@@ -457 +457 @@
     /// \c t.
     /// \code
-    /// GomoryHu<Graph> gom(g, capacities);
+    /// GomoruHu<Graph> gom(g, capacities);
     /// gom.run();
     /// int value=0;
-    /// for(GomoryHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
+    /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
     ///   value+=capacities[e];
     /// \endcode

lemon/maps.h

@@ -23 +23 @@
 #include <functional>
 #include <vector>
-#include <map>
 
 #include <lemon/core.h>
@@ -30 +29 @@
 ///\ingroup maps
 ///\brief Miscellaneous property maps
+
+#include <map>
 
 namespace lemon {
@@ -57 +58 @@
   /// but data written to it is not required (i.e. it will be sent to
   /// <tt>/dev/null</tt>).
-  /// It conforms to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+  /// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
   ///
   /// \sa ConstMap
@@ -90 +91 @@
   ///
   /// In other aspects it is equivalent to \c NullMap.
-  /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap"
+  /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
   /// concept, but it absorbs the data written to it.
   ///
@@ -159 +160 @@
   ///
   /// In other aspects it is equivalent to \c NullMap.
-  /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap"
+  /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
   /// concept, but it absorbs the data written to it.
   ///
@@ -233 +234 @@
   /// It can be used with some data structures, for example
   /// \c UnionFind, \c BinHeap, when the used items are small
-  /// integers. This map conforms to the \ref concepts::ReferenceMap
+  /// integers. This map conforms the \ref concepts::ReferenceMap
   /// "ReferenceMap" concept.
   ///
@@ -341 +342 @@
   /// stored actually. This value can be different from the default
   /// contructed value (i.e. \c %Value()).
-  /// This type conforms to the \ref concepts::ReferenceMap "ReferenceMap"
+  /// This type conforms the \ref concepts::ReferenceMap "ReferenceMap"
   /// concept.
   ///
@@ -707 +708 @@
   /// The \c Key type of it is inherited from \c M and the \c Value
   /// type is \c V.
-  /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
+  /// This type conforms the \ref concepts::ReadMap "ReadMap" concept.
   ///
   /// The simplest way of using this map is through the convertMap()
@@ -1790 +1791 @@
   /// \code
   ///   std::vector<Node> v;
-  ///   dfs(g).processedMap(loggerBoolMap(std::back_inserter(v))).run(s);
+  ///   dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run();
   /// \endcode
   /// \code
   ///   std::vector<Node> v(countNodes(g));
-  ///   dfs(g).processedMap(loggerBoolMap(v.begin())).run(s);
+  ///   dfs(g,s).processedMap(loggerBoolMap(v.begin())).run();
   /// \endcode
   ///
@@ -1818 +1819 @@
   ///
   /// IdMap provides a unique and immutable id for each item of the
-  /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is
+  /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is 
   ///  - \b unique: different items get different ids,
   ///  - \b immutable: the id of an item does not change (even if you
@@ -1826 +1827 @@
   /// 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.
@@ -1866 +1867 @@
   public:
 
-    /// \brief The inverse map type of 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.
+    /// \brief This class represents the inverse of its owner (IdMap).
+    ///
+    /// This class represents the inverse of its owner (IdMap).
     /// \see inverse()
     class InverseMap {
@@ -1885 +1884 @@
       explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
 
-      /// \brief Gives back an item by its id.
+      /// \brief Gives back the given item from its id.
       ///
-      /// Gives back an item by its id.
+      /// Gives back the given item from its id.
       Item operator[](int id) const { return _graph->fromId(id, Item());}
 
@@ -1900 +1899 @@
   };
 
-  /// \brief Returns an \c IdMap class.
-  ///
-  /// This function just returns an \c IdMap class.
-  /// \relates IdMap
-  template <typename K, typename GR>
-  inline IdMap<GR, K> idMap(const GR& graph) {
-    return IdMap<GR, K>(graph);
-  }
 
   /// \brief General cross reference graph map type.
@@ -1914 +1905 @@
   /// 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 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.
+  /// The values of the map can be accessed
+  /// with stl compatible forward iterator.
   ///
   /// This type is not reference map, so it cannot be modified with
@@ -1965 +1947 @@
     /// \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 <tt>[beginValue, endValue)</tt> range.
     /// They are considered with multiplicity, so each value is
     /// traversed for each item it is assigned to.
-    class ValueIt
+    class ValueIterator
       : public std::iterator<std::forward_iterator_tag, Value> {
       friend class CrossRefMap;
     private:
-      ValueIt(typename Container::const_iterator _it)
+      ValueIterator(typename Container::const_iterator _it)
         : it(_it) {}
     public:
 
-      /// Constructor
-      ValueIt() {}
-
-      /// \e
-      ValueIt& operator++() { ++it; return *this; }
-      /// \e
-      ValueIt operator++(int) {
-        ValueIt tmp(*this);
+      ValueIterator() {}
+
+      ValueIterator& operator++() { ++it; return *this; }
+      ValueIterator operator++(int) {
+        ValueIterator tmp(*this);
         operator++();
         return tmp;
       }
 
-      /// \e
       const Value& operator*() const { return it->first; }
-      /// \e
       const Value* operator->() const { return &(it->first); }
 
-      /// \e
-      bool operator==(ValueIt jt) const { return it == jt.it; }
-      /// \e
-      bool operator!=(ValueIt jt) const { return it != jt.it; }
+      bool operator==(ValueIterator jt) const { return it == jt.it; }
+      bool operator!=(ValueIterator 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 <tt>[beginValue, endValue)</tt>
     /// range.
-    ValueIt beginValue() const {
-      return ValueIt(_inv_map.begin());
+    ValueIterator beginValue() const {
+      return ValueIterator(_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 <tt>[beginValue, endValue)</tt>
     /// range.
-    ValueIt endValue() const {
-      return ValueIt(_inv_map.end());
+    ValueIterator endValue() const {
+      return ValueIterator(_inv_map.end());
     }
 
@@ -2061 +2033 @@
       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);
     }
 
@@ -2120 +2084 @@
   public:
 
-    /// \brief The inverse map type of CrossRefMap.
-    ///
-    /// 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()
+    /// \brief The inverse map type.
+    ///
+    /// The inverse of this map. The subscript operator of the map
+    /// gives back the item that was last assigned to the value.
     class InverseMap {
     public:
@@ -2152 +2114 @@
     };
 
-    /// \brief Gives back the inverse of the map.
-    ///
-    /// Gives back the inverse of the CrossRefMap.
+    /// \brief It gives back the read-only inverse map.
+    ///
+    /// It gives back the read-only inverse map.
     InverseMap inverse() const {
       return InverseMap(*this);
@@ -2161 +2123 @@
   };
 
-  /// \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,
@@ -2176 +2138 @@
   /// 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.
@@ -2304 +2266 @@
     }
 
-    /// \brief Gives back the \e range \e id of the item
-    ///
-    /// Gives back the \e range \e id of the item.
+    /// \brief Gives back the \e RangeId of the item
+    ///
+    /// Gives back the \e RangeId of the item.
     int operator[](const Item& item) const {
       return Map::operator[](item);
     }
 
-    /// \brief Gives back the item belonging to a \e range \e id
-    ///
-    /// Gives back the item belonging to the given \e range \e id.
+    /// \brief Gives back the item belonging to a \e RangeId
+    /// 
+    /// Gives back the item belonging to a \e RangeId.
     Item operator()(int id) const {
       return _inv_map[id];
@@ -2327 +2289 @@
     /// \brief 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.
+    /// The inverse map type of RangeIdMap.
     class InverseMap {
     public:
@@ -2347 +2307 @@
       ///
       /// Subscript operator. It gives back the item
-      /// that the given \e range \e id currently belongs to.
+      /// that the descriptor currently belongs to.
       Value operator[](const Key& key) const {
         return _inverted(key);
@@ -2365 +2325 @@
     /// \brief Gives back the inverse of the map.
     ///
-    /// Gives back the inverse of the RangeIdMap.
+    /// Gives back the inverse of the map.
     const InverseMap inverse() const {
       return InverseMap(*this);
     }
-  };
-
-  /// \brief Returns a \c RangeIdMap class.
-  ///
-  /// This function just returns an \c RangeIdMap class.
-  /// \relates RangeIdMap
-  template <typename K, typename GR>
-  inline RangeIdMap<GR, K> rangeIdMap(const GR& graph) {
-    return RangeIdMap<GR, K>(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 mapped to the value.
-  ///
-  /// This type is a reference map, so it can be modified with the
-  /// subscript operator.
-  ///
-  /// \tparam GR The graph type.
-  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
-  /// \c GR::Edge).
-  ///
-  /// \see IterableIntMap, IterableValueMap
-  /// \see CrossRefMap
-  template <typename GR, typename K>
-  class IterableBoolMap
-    : protected ItemSetTraits<GR, K>::template Map<int>::Type {
-  private:
-    typedef GR Graph;
-
-    typedef typename ItemSetTraits<GR, K>::ItemIt KeyIt;
-    typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Parent;
-
-    std::vector<K> _array;
-    int _sep;
-
-  public:
-
-    /// Indicates that the map is reference map.
-    typedef True ReferenceMapTag;
-
-    /// The key type
-    typedef K Key;
-    /// The value type
-    typedef bool Value;
-    /// The const reference type.
-    typedef const Value& ConstReference;
-
-  private:
-
-    int position(const Key& key) const {
-      return Parent::operator[](key);
-    }
-
-  public:
-
-    /// \brief Reference to the value of the map.
-    ///
-    /// This class is similar to the \c bool type. It can be converted to
-    /// \c bool and it provides the same operators.
-    class Reference {
-      friend class IterableBoolMap;
-    private:
-      Reference(IterableBoolMap& map, const Key& key)
-        : _key(key), _map(map) {}
-    public:
-
-      Reference& operator=(const Reference& value) {
-        _map.set(_key, static_cast<bool>(value));
-         return *this;
-      }
-
-      operator bool() const {
-        return static_cast<const IterableBoolMap&>(_map)[_key];
-      }
-
-      Reference& operator=(bool value) {
-        _map.set(_key, value);
-        return *this;
-      }
-      Reference& operator&=(bool value) {
-        _map.set(_key, _map[_key] & value);
-        return *this;
-      }
-      Reference& operator|=(bool value) {
-        _map.set(_key, _map[_key] | value);
-        return *this;
-      }
-      Reference& operator^=(bool value) {
-        _map.set(_key, _map[_key] ^ value);
-        return *this;
-      }
-    private:
-      Key _key;
-      IterableBoolMap& _map;
-    };
-
-    /// \brief Constructor of the map with a default value.
-    ///
-    /// Constructor of the map with a default value.
-    explicit IterableBoolMap(const Graph& graph, bool def = false)
-      : Parent(graph) {
-      typename Parent::Notifier* nf = Parent::notifier();
-      Key it;
-      for (nf->first(it); it != INVALID; nf->next(it)) {
-        Parent::set(it, _array.size());
-        _array.push_back(it);
-      }
-      _sep = (def ? _array.size() : 0);
-    }
-
-    /// \brief Const subscript operator of the map.
-    ///
-    /// Const subscript operator of the map.
-    bool operator[](const Key& key) const {
-      return position(key) < _sep;
-    }
-
-    /// \brief Subscript operator of the map.
-    ///
-    /// Subscript operator of the map.
-    Reference operator[](const Key& key) {
-      return Reference(*this, key);
-    }
-
-    /// \brief Set operation of the map.
-    ///
-    /// Set operation of the map.
-    void set(const Key& key, bool value) {
-      int pos = position(key);
-      if (value) {
-        if (pos < _sep) return;
-        Key tmp = _array[_sep];
-        _array[_sep] = key;
-        Parent::set(key, _sep);
-        _array[pos] = tmp;
-        Parent::set(tmp, pos);
-        ++_sep;
-      } else {
-        if (pos >= _sep) return;
-        --_sep;
-        Key tmp = _array[_sep];
-        _array[_sep] = key;
-        Parent::set(key, _sep);
-        _array[pos] = tmp;
-        Parent::set(tmp, pos);
-      }
-    }
-
-    /// \brief Set all items.
-    ///
-    /// Set all items in the map.
-    /// \note Constant time operation.
-    void setAll(bool value) {
-      _sep = (value ? _array.size() : 0);
-    }
-
-    /// \brief Returns the number of the keys mapped to \c true.
-    ///
-    /// Returns the number of the keys mapped to \c true.
-    int trueNum() const {
-      return _sep;
-    }
-
-    /// \brief Returns the number of the keys mapped to \c false.
-    ///
-    /// Returns the number of the keys mapped to \c false.
-    int falseNum() const {
-      return _array.size() - _sep;
-    }
-
-    /// \brief Iterator for the keys mapped to \c true.
-    ///
-    /// Iterator for the keys mapped to \c true. It works
-    /// like a graph item iterator, it can be converted to
-    /// the key type of the map, incremented with \c ++ operator, and
-    /// if the iterator leaves the last valid key, it will be equal to
-    /// \c INVALID.
-    class TrueIt : public Key {
-    public:
-      typedef Key Parent;
-
-      /// \brief Creates an iterator.
-      ///
-      /// Creates an iterator. It iterates on the
-      /// keys mapped to \c true.
-      /// \param map The IterableBoolMap.
-      explicit TrueIt(const IterableBoolMap& map)
-        : Parent(map._sep > 0 ? map._array[map._sep - 1] : INVALID),
-          _map(&map) {}
-
-      /// \brief Invalid constructor \& conversion.
-      ///
-      /// This constructor initializes the iterator to be invalid.
-      /// \sa Invalid for more details.
-      TrueIt(Invalid) : Parent(INVALID), _map(0) {}
-
-      /// \brief Increment operator.
-      ///
-      /// Increment operator.
-      TrueIt& operator++() {
-        int pos = _map->position(*this);
-        Parent::operator=(pos > 0 ? _map->_array[pos - 1] : INVALID);
-        return *this;
-      }
-
-    private:
-      const IterableBoolMap* _map;
-    };
-
-    /// \brief Iterator for the keys mapped to \c false.
-    ///
-    /// Iterator for the keys mapped to \c false. It works
-    /// like a graph item iterator, it can be converted to
-    /// the key type of the map, incremented with \c ++ operator, and
-    /// if the iterator leaves the last valid key, it will be equal to
-    /// \c INVALID.
-    class FalseIt : public Key {
-    public:
-      typedef Key Parent;
-
-      /// \brief Creates an iterator.
-      ///
-      /// Creates an iterator. It iterates on the
-      /// keys mapped to \c false.
-      /// \param map The IterableBoolMap.
-      explicit FalseIt(const IterableBoolMap& map)
-        : Parent(map._sep < int(map._array.size()) ?
-                 map._array.back() : INVALID), _map(&map) {}
-
-      /// \brief Invalid constructor \& conversion.
-      ///
-      /// This constructor initializes the iterator to be invalid.
-      /// \sa Invalid for more details.
-      FalseIt(Invalid) : Parent(INVALID), _map(0) {}
-
-      /// \brief Increment operator.
-      ///
-      /// Increment operator.
-      FalseIt& operator++() {
-        int pos = _map->position(*this);
-        Parent::operator=(pos > _map->_sep ? _map->_array[pos - 1] : INVALID);
-        return *this;
-      }
-
-    private:
-      const IterableBoolMap* _map;
-    };
-
-    /// \brief Iterator for the keys mapped to a given value.
-    ///
-    /// Iterator for the keys mapped to a given value. It works
-    /// like a graph item iterator, it can be converted to
-    /// the key type of the map, incremented with \c ++ operator, and
-    /// if the iterator leaves the last valid key, it will be equal to
-    /// \c INVALID.
-    class ItemIt : public Key {
-    public:
-      typedef Key Parent;
-
-      /// \brief Creates an iterator with a value.
-      ///
-      /// Creates an iterator with a value. It iterates on the
-      /// keys mapped to the given value.
-      /// \param map The IterableBoolMap.
-      /// \param value The value.
-      ItemIt(const IterableBoolMap& map, bool value)
-        : Parent(value ? 
-                 (map._sep > 0 ?
-                  map._array[map._sep - 1] : INVALID) :
-                 (map._sep < int(map._array.size()) ?
-                  map._array.back() : INVALID)), _map(&map) {}
-
-      /// \brief Invalid constructor \& conversion.
-      ///
-      /// This constructor initializes the iterator to be invalid.
-      /// \sa Invalid for more details.
-      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
-
-      /// \brief Increment operator.
-      ///
-      /// Increment operator.
-      ItemIt& operator++() {
-        int pos = _map->position(*this);
-        int _sep = pos >= _map->_sep ? _map->_sep : 0;
-        Parent::operator=(pos > _sep ? _map->_array[pos - 1] : INVALID);
-        return *this;
-      }
-
-    private:
-      const IterableBoolMap* _map;
-    };
-
-  protected:
-
-    virtual void add(const Key& key) {
-      Parent::add(key);
-      Parent::set(key, _array.size());
-      _array.push_back(key);
-    }
-
-    virtual void add(const std::vector<Key>& keys) {
-      Parent::add(keys);
-      for (int i = 0; i < int(keys.size()); ++i) {
-        Parent::set(keys[i], _array.size());
-        _array.push_back(keys[i]);
-      }
-    }
-
-    virtual void erase(const Key& key) {
-      int pos = position(key);
-      if (pos < _sep) {
-        --_sep;
-        Parent::set(_array[_sep], pos);
-        _array[pos] = _array[_sep];
-        Parent::set(_array.back(), _sep);
-        _array[_sep] = _array.back();
-        _array.pop_back();
-      } else {
-        Parent::set(_array.back(), pos);
-        _array[pos] = _array.back();
-        _array.pop_back();
-      }
-      Parent::erase(key);
-    }
-
-    virtual void erase(const std::vector<Key>& keys) {
-      for (int i = 0; i < int(keys.size()); ++i) {
-        int pos = position(keys[i]);
-        if (pos < _sep) {
-          --_sep;
-          Parent::set(_array[_sep], pos);
-          _array[pos] = _array[_sep];
-          Parent::set(_array.back(), _sep);
-          _array[_sep] = _array.back();
-          _array.pop_back();
-        } else {
-          Parent::set(_array.back(), pos);
-          _array[pos] = _array.back();
-          _array.pop_back();
-        }
-      }
-      Parent::erase(keys);
-    }
-
-    virtual void build() {
-      Parent::build();
-      typename Parent::Notifier* nf = Parent::notifier();
-      Key it;
-      for (nf->first(it); it != INVALID; nf->next(it)) {
-        Parent::set(it, _array.size());
-        _array.push_back(it);
-      }
-      _sep = 0;
-    }
-
-    virtual void clear() {
-      _array.clear();
-      _sep = 0;
-      Parent::clear();
-    }
-
-  };
-
-
-  namespace _maps_bits {
-    template <typename Item>
-    struct IterableIntMapNode {
-      IterableIntMapNode() : value(-1) {}
-      IterableIntMapNode(int _value) : value(_value) {}
-      Item prev, next;
-      int value;
-    };
-  }
-
-  /// \brief Dynamic iterable integer map.
-  ///
-  /// This class provides a special graph map type which can store an
-  /// integer value for graph items (\c Node, \c Arc or \c Edge).
-  /// 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.
-  ///
-  /// \note The size of the data structure depends on the largest
-  /// value in the map.
-  ///
-  /// \tparam GR The graph type.
-  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
-  /// \c GR::Edge).
-  ///
-  /// \see IterableBoolMap, IterableValueMap
-  /// \see CrossRefMap
-  template <typename GR, typename K>
-  class IterableIntMap
-    : protected ItemSetTraits<GR, K>::
-        template Map<_maps_bits::IterableIntMapNode<K> >::Type {
-  public:
-    typedef typename ItemSetTraits<GR, K>::
-      template Map<_maps_bits::IterableIntMapNode<K> >::Type Parent;
-
-    /// The key type
-    typedef K Key;
-    /// The value type
-    typedef int Value;
-    /// The graph type
-    typedef GR Graph;
-
-    /// \brief Constructor of the map.
-    ///
-    /// Constructor of the map. It sets all values to -1.
-    explicit IterableIntMap(const Graph& graph)
-      : Parent(graph) {}
-
-    /// \brief Constructor of the map with a given value.
-    ///
-    /// Constructor of the map with a given value.
-    explicit IterableIntMap(const Graph& graph, int value)
-      : Parent(graph, _maps_bits::IterableIntMapNode<K>(value)) {
-      if (value >= 0) {
-        for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
-          lace(it);
-        }
-      }
-    }
-
-  private:
-
-    void unlace(const Key& key) {
-      typename Parent::Value& node = Parent::operator[](key);
-      if (node.value < 0) return;
-      if (node.prev != INVALID) {
-        Parent::operator[](node.prev).next = node.next;
-      } else {
-        _first[node.value] = node.next;
-      }
-      if (node.next != INVALID) {
-        Parent::operator[](node.next).prev = node.prev;
-      }
-      while (!_first.empty() && _first.back() == INVALID) {
-        _first.pop_back();
-      }
-    }
-
-    void lace(const Key& key) {
-      typename Parent::Value& node = Parent::operator[](key);
-      if (node.value < 0) return;
-      if (node.value >= int(_first.size())) {
-        _first.resize(node.value + 1, INVALID);
-      }
-      node.prev = INVALID;
-      node.next = _first[node.value];
-      if (node.next != INVALID) {
-        Parent::operator[](node.next).prev = key;
-      }
-      _first[node.value] = key;
-    }
-
-  public:
-
-    /// Indicates that the map is reference map.
-    typedef True ReferenceMapTag;
-
-    /// \brief Reference to the value of the map.
-    ///
-    /// This class is similar to the \c int type. It can
-    /// be converted to \c int and it has the same operators.
-    class Reference {
-      friend class IterableIntMap;
-    private:
-      Reference(IterableIntMap& map, const Key& key)
-        : _key(key), _map(map) {}
-    public:
-
-      Reference& operator=(const Reference& value) {
-        _map.set(_key, static_cast<const int&>(value));
-         return *this;
-      }
-
-      operator const int&() const {
-        return static_cast<const IterableIntMap&>(_map)[_key];
-      }
-
-      Reference& operator=(int value) {
-        _map.set(_key, value);
-        return *this;
-      }
-      Reference& operator++() {
-        _map.set(_key, _map[_key] + 1);
-        return *this;
-      }
-      int operator++(int) {
-        int value = _map[_key];
-        _map.set(_key, value + 1);
-        return value;
-      }
-      Reference& operator--() {
-        _map.set(_key, _map[_key] - 1);
-        return *this;
-      }
-      int operator--(int) {
-        int value = _map[_key];
-        _map.set(_key, value - 1);
-        return value;
-      }
-      Reference& operator+=(int value) {
-        _map.set(_key, _map[_key] + value);
-        return *this;
-      }
-      Reference& operator-=(int value) {
-        _map.set(_key, _map[_key] - value);
-        return *this;
-      }
-      Reference& operator*=(int value) {
-        _map.set(_key, _map[_key] * value);
-        return *this;
-      }
-      Reference& operator/=(int value) {
-        _map.set(_key, _map[_key] / value);
-        return *this;
-      }
-      Reference& operator%=(int value) {
-        _map.set(_key, _map[_key] % value);
-        return *this;
-      }
-      Reference& operator&=(int value) {
-        _map.set(_key, _map[_key] & value);
-        return *this;
-      }
-      Reference& operator|=(int value) {
-        _map.set(_key, _map[_key] | value);
-        return *this;
-      }
-      Reference& operator^=(int value) {
-        _map.set(_key, _map[_key] ^ value);
-        return *this;
-      }
-      Reference& operator<<=(int value) {
-        _map.set(_key, _map[_key] << value);
-        return *this;
-      }
-      Reference& operator>>=(int value) {
-        _map.set(_key, _map[_key] >> value);
-        return *this;
-      }
-
-    private:
-      Key _key;
-      IterableIntMap& _map;
-    };
-
-    /// The const reference type.
-    typedef const Value& ConstReference;
-
-    /// \brief Gives back the maximal value plus one.
-    ///
-    /// Gives back the maximal value plus one.
-    int size() const {
-      return _first.size();
-    }
-
-    /// \brief Set operation of the map.
-    ///
-    /// Set operation of the map.
-    void set(const Key& key, const Value& value) {
-      unlace(key);
-      Parent::operator[](key).value = value;
-      lace(key);
-    }
-
-    /// \brief Const subscript operator of the map.
-    ///
-    /// Const subscript operator of the map.
-    const Value& operator[](const Key& key) const {
-      return Parent::operator[](key).value;
-    }
-
-    /// \brief Subscript operator of the map.
-    ///
-    /// Subscript operator of the map.
-    Reference operator[](const Key& key) {
-      return Reference(*this, key);
-    }
-
-    /// \brief Iterator for the keys with the same value.
-    ///
-    /// Iterator for the keys with the same value. It works
-    /// like a graph item iterator, it can be converted to
-    /// the item type of the map, incremented with \c ++ operator, and
-    /// if the iterator leaves the last valid item, it will be equal to
-    /// \c INVALID.
-    class ItemIt : public Key {
-    public:
-      typedef Key Parent;
-
-      /// \brief Invalid constructor \& conversion.
-      ///
-      /// This constructor initializes the iterator to be invalid.
-      /// \sa Invalid for more details.
-      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
-
-      /// \brief Creates an iterator with a value.
-      ///
-      /// Creates an iterator with a value. It iterates on the
-      /// keys mapped to the given value.
-      /// \param map The IterableIntMap.
-      /// \param value The value.
-      ItemIt(const IterableIntMap& map, int value) : _map(&map) {
-        if (value < 0 || value >= int(_map->_first.size())) {
-          Parent::operator=(INVALID);
-        } else {
-          Parent::operator=(_map->_first[value]);
-        }
-      }
-
-      /// \brief Increment operator.
-      ///
-      /// Increment operator.
-      ItemIt& operator++() {
-        Parent::operator=(_map->IterableIntMap::Parent::
-                          operator[](static_cast<Parent&>(*this)).next);
-        return *this;
-      }
-
-    private:
-      const IterableIntMap* _map;
-    };
-
-  protected:
-
-    virtual void erase(const Key& key) {
-      unlace(key);
-      Parent::erase(key);
-    }
-
-    virtual void erase(const std::vector<Key>& keys) {
-      for (int i = 0; i < int(keys.size()); ++i) {
-        unlace(keys[i]);
-      }
-      Parent::erase(keys);
-    }
-
-    virtual void clear() {
-      _first.clear();
-      Parent::clear();
-    }
-
-  private:
-    std::vector<Key> _first;
-  };
-
-  namespace _maps_bits {
-    template <typename Item, typename Value>
-    struct IterableValueMapNode {
-      IterableValueMapNode(Value _value = Value()) : value(_value) {}
-      Item prev, next;
-      Value value;
-    };
-  }
-
-  /// \brief Dynamic iterable map for comparable values.
-  ///
-  /// 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 (\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).
-  ///
-  /// \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.
-  ///
-  /// \tparam GR The graph type.
-  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
-  /// \c GR::Edge).
-  /// \tparam V The value type of the map. It can be any comparable
-  /// value type.
-  ///
-  /// \see IterableBoolMap, IterableIntMap
-  /// \see CrossRefMap
-  template <typename GR, typename K, typename V>
-  class IterableValueMap
-    : protected ItemSetTraits<GR, K>::
-        template Map<_maps_bits::IterableValueMapNode<K, V> >::Type {
-  public:
-    typedef typename ItemSetTraits<GR, K>::
-      template Map<_maps_bits::IterableValueMapNode<K, V> >::Type Parent;
-
-    /// The key type
-    typedef K Key;
-    /// The value type
-    typedef V Value;
-    /// The graph type
-    typedef GR Graph;
-
-  public:
-
-    /// \brief Constructor of the map with a given value.
-    ///
-    /// Constructor of the map with a given value.
-    explicit IterableValueMap(const Graph& graph,
-                              const Value& value = Value())
-      : Parent(graph, _maps_bits::IterableValueMapNode<K, V>(value)) {
-      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
-        lace(it);
-      }
-    }
-
-  protected:
-
-    void unlace(const Key& key) {
-      typename Parent::Value& node = Parent::operator[](key);
-      if (node.prev != INVALID) {
-        Parent::operator[](node.prev).next = node.next;
-      } else {
-        if (node.next != INVALID) {
-          _first[node.value] = node.next;
-        } else {
-          _first.erase(node.value);
-        }
-      }
-      if (node.next != INVALID) {
-        Parent::operator[](node.next).prev = node.prev;
-      }
-    }
-
-    void lace(const Key& key) {
-      typename Parent::Value& node = Parent::operator[](key);
-      typename std::map<Value, Key>::iterator it = _first.find(node.value);
-      if (it == _first.end()) {
-        node.prev = node.next = INVALID;
-        _first.insert(std::make_pair(node.value, key));
-      } else {
-        node.prev = INVALID;
-        node.next = it->second;
-        if (node.next != INVALID) {
-          Parent::operator[](node.next).prev = key;
-        }
-        it->second = key;
-      }
-    }
-
-  public:
-
-    /// \brief Forward iterator for values.
-    ///
-    /// This iterator is an STL compatible forward
-    /// iterator on the values of the map. The values can
-    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
-    class ValueIt
-      : public std::iterator<std::forward_iterator_tag, Value> {
-      friend class IterableValueMap;
-    private:
-      ValueIt(typename std::map<Value, Key>::const_iterator _it)
-        : it(_it) {}
-    public:
-
-      /// 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); }
-
-      /// \e
-      bool operator==(ValueIt jt) const { return it == jt.it; }
-      /// \e
-      bool operator!=(ValueIt jt) const { return it != jt.it; }
-
-    private:
-      typename std::map<Value, Key>::const_iterator it;
-    };
-
-    /// \brief Returns an iterator to the first value.
-    ///
-    /// Returns an STL compatible iterator to the
-    /// first value of the map. The values of the
-    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
-    /// range.
-    ValueIt beginValue() const {
-      return ValueIt(_first.begin());
-    }
-
-    /// \brief Returns an iterator after the last value.
-    ///
-    /// Returns an STL compatible iterator after the
-    /// last value of the map. The values of the
-    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
-    /// range.
-    ValueIt endValue() const {
-      return ValueIt(_first.end());
-    }
-
-    /// \brief Set operation of the map.
-    ///
-    /// Set operation of the map.
-    void set(const Key& key, const Value& value) {
-      unlace(key);
-      Parent::operator[](key).value = value;
-      lace(key);
-    }
-
-    /// \brief Const subscript operator of the map.
-    ///
-    /// Const subscript operator of the map.
-    const Value& operator[](const Key& key) const {
-      return Parent::operator[](key).value;
-    }
-
-    /// \brief Iterator for the keys with the same value.
-    ///
-    /// Iterator for the keys with the same value. It works
-    /// like a graph item iterator, it can be converted to
-    /// the item type of the map, incremented with \c ++ operator, and
-    /// if the iterator leaves the last valid item, it will be equal to
-    /// \c INVALID.
-    class ItemIt : public Key {
-    public:
-      typedef Key Parent;
-
-      /// \brief Invalid constructor \& conversion.
-      ///
-      /// This constructor initializes the iterator to be invalid.
-      /// \sa Invalid for more details.
-      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
-
-      /// \brief Creates an iterator with a value.
-      ///
-      /// Creates an iterator with a value. It iterates on the
-      /// keys which have the given value.
-      /// \param map The IterableValueMap
-      /// \param value The value
-      ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) {
-        typename std::map<Value, Key>::const_iterator it =
-          map._first.find(value);
-        if (it == map._first.end()) {
-          Parent::operator=(INVALID);
-        } else {
-          Parent::operator=(it->second);
-        }
-      }
-
-      /// \brief Increment operator.
-      ///
-      /// Increment Operator.
-      ItemIt& operator++() {
-        Parent::operator=(_map->IterableValueMap::Parent::
-                          operator[](static_cast<Parent&>(*this)).next);
-        return *this;
-      }
-
-
-    private:
-      const IterableValueMap* _map;
-    };
-
-  protected:
-
-    virtual void add(const Key& key) {
-      Parent::add(key);
-      unlace(key);
-    }
-
-    virtual void add(const std::vector<Key>& keys) {
-      Parent::add(keys);
-      for (int i = 0; i < int(keys.size()); ++i) {
-        lace(keys[i]);
-      }
-    }
-
-    virtual void erase(const Key& key) {
-      unlace(key);
-      Parent::erase(key);
-    }
-
-    virtual void erase(const std::vector<Key>& keys) {
-      for (int i = 0; i < int(keys.size()); ++i) {
-        unlace(keys[i]);
-      }
-      Parent::erase(keys);
-    }
-
-    virtual void build() {
-      Parent::build();
-      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
-        lace(it);
-      }
-    }
-
-    virtual void clear() {
-      _first.clear();
-      Parent::clear();
-    }
-
-  private:
-    std::map<Value, Key> _first;
   };
 
@@ -3301 +2341 @@
   public:
 
-    /// The key type (the \c Arc type of the digraph).
+    ///\e
     typedef typename GR::Arc Key;
-    /// The value type (the \c Node type of the digraph).
+    ///\e
     typedef typename GR::Node Value;
 
@@ -3342 +2382 @@
   public:
 
-    /// The key type (the \c Arc type of the digraph).
+    ///\e
     typedef typename GR::Arc Key;
-    /// The value type (the \c Node type of the digraph).
+    ///\e
     typedef typename GR::Node Value;
 
@@ -3384 +2424 @@
   public:
 
-    /// The key type (the \c Edge type of the digraph).
+    typedef typename GR::Arc Value;
     typedef typename GR::Edge Key;
-    /// The value type (the \c Arc type of the digraph).
-    typedef typename GR::Arc Value;
 
     /// \brief Constructor
@@ -3426 +2464 @@
   public:
 
-    /// The key type (the \c Edge type of the digraph).
+    typedef typename GR::Arc Value;
     typedef typename GR::Edge Key;
-    /// The value type (the \c Arc type of the digraph).
-    typedef typename GR::Arc Value;
 
     /// \brief Constructor
@@ -3464 +2500 @@
   /// whenever the digraph changes.
   ///
-  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
+  /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
   /// may provide alternative ways to modify the digraph.
   /// The correct behavior of InDegMap is not guarantied if these additional
@@ -3480 +2516 @@
 
   public:
-
+    
     /// The graph type of InDegMap
     typedef GR Graph;
@@ -3594 +2630 @@
   /// whenever the digraph changes.
   ///
-  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
+  /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
   /// may provide alternative ways to modify the digraph.
   /// The correct behavior of OutDegMap is not guarantied if these additional

lemon/min_cost_arborescence.h

@@ -489 +489 @@
     /// The simplest way to execute the algorithm is to use
     /// one of the member functions called \c run(...). \n
-    /// If you need better control on the execution,
-    /// you have to call \ref init() first, then you can add several
+    /// If you need more control on the execution,
+    /// first you must call \ref init(), then you can add several
     /// source nodes with \ref addSource().
     /// Finally \ref start() will perform the arborescence

lemon/network_simplex.h

@@ -162 +162 @@
     TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 
+    typedef std::vector<Arc> ArcVector;
+    typedef std::vector<Node> NodeVector;
     typedef std::vector<int> IntVector;
     typedef std::vector<bool> BoolVector;
@@ -363 +365 @@
         Cost c, min = 0;
         int cnt = _block_size;
-        int e;
+        int e, min_arc = _next_arc;
         for (e = _next_arc; e < _search_arc_num; ++e) {
           c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
           if (c < min) {
             min = c;
-            _in_arc = e;
+            min_arc = e;
           }
           if (--cnt == 0) {
-            if (min < 0) goto search_end;
+            if (min < 0) break;
             cnt = _block_size;
           }
         }
-        for (e = 0; e < _next_arc; ++e) {
-          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
-          if (c < min) {
-            min = c;
-            _in_arc = e;
-          }
-          if (--cnt == 0) {
-            if (min < 0) goto search_end;
-            cnt = _block_size;
+        if (min == 0 || cnt > 0) {
+          for (e = 0; e < _next_arc; ++e) {
+            c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
+            if (c < min) {
+              min = c;
+              min_arc = e;
+            }
+            if (--cnt == 0) {
+              if (min < 0) break;
+              cnt = _block_size;
+            }
           }
         }
         if (min >= 0) return false;
-
-      search_end:
+        _in_arc = min_arc;
         _next_arc = e;
         return true;
@@ -426 +429 @@
       {
         // The main parameters of the pivot rule
-        const double LIST_LENGTH_FACTOR = 0.25;
+        const double LIST_LENGTH_FACTOR = 1.0;
         const int MIN_LIST_LENGTH = 10;
         const double MINOR_LIMIT_FACTOR = 0.1;
@@ -443 +446 @@
       bool findEnteringArc() {
         Cost min, c;
-        int e;
+        int e, min_arc = _next_arc;
         if (_curr_length > 0 && _minor_count < _minor_limit) {
           // Minor iteration: select the best eligible arc from the
@@ -454 +457 @@
             if (c < min) {
               min = c;
-              _in_arc = e;
+              min_arc = e;
             }
-            else if (c >= 0) {
+            if (c >= 0) {
               _candidates[i--] = _candidates[--_curr_length];
             }
           }
-          if (min < 0) return true;
+          if (min < 0) {
+            _in_arc = min_arc;
+            return true;
+          }
         }
 
@@ -472 +478 @@
             if (c < min) {
               min = c;
-              _in_arc = e;
+              min_arc = e;
             }
-            if (_curr_length == _list_length) goto search_end;
-          }
-        }
-        for (e = 0; e < _next_arc; ++e) {
-          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
-          if (c < 0) {
-            _candidates[_curr_length++] = e;
-            if (c < min) {
-              min = c;
-              _in_arc = e;
+            if (_curr_length == _list_length) break;
+          }
+        }
+        if (_curr_length < _list_length) {
+          for (e = 0; e < _next_arc; ++e) {
+            c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
+            if (c < 0) {
+              _candidates[_curr_length++] = e;
+              if (c < min) {
+                min = c;
+                min_arc = e;
+              }
+              if (_curr_length == _list_length) break;
             }
-            if (_curr_length == _list_length) goto search_end;
           }
         }
         if (_curr_length == 0) return false;
-      
-      search_end:        
         _minor_count = 1;
+        _in_arc = min_arc;
         _next_arc = e;
         return true;
@@ -543 +550 @@
       {
         // The main parameters of the pivot rule
-        const double BLOCK_SIZE_FACTOR = 1.0;
+        const double BLOCK_SIZE_FACTOR = 1.5;
         const int MIN_BLOCK_SIZE = 10;
         const double HEAD_LENGTH_FACTOR = 0.1;
@@ -572 +579 @@
         // Extend the list
         int cnt = _block_size;
+        int last_arc = 0;
         int limit = _head_length;
 
-        for (e = _next_arc; e < _search_arc_num; ++e) {
+        for (int e = _next_arc; e < _search_arc_num; ++e) {
           _cand_cost[e] = _state[e] *
             (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
           if (_cand_cost[e] < 0) {
             _candidates[_curr_length++] = e;
+            last_arc = e;
           }
           if (--cnt == 0) {
-            if (_curr_length > limit) goto search_end;
+            if (_curr_length > limit) break;
             limit = 0;
             cnt = _block_size;
           }
         }
-        for (e = 0; e < _next_arc; ++e) {
-          _cand_cost[e] = _state[e] *
-            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
-          if (_cand_cost[e] < 0) {
-            _candidates[_curr_length++] = e;
-          }
-          if (--cnt == 0) {
-            if (_curr_length > limit) goto search_end;
-            limit = 0;
-            cnt = _block_size;
+        if (_curr_length <= limit) {
+          for (int e = 0; e < _next_arc; ++e) {
+            _cand_cost[e] = _state[e] *
+              (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
+            if (_cand_cost[e] < 0) {
+              _candidates[_curr_length++] = e;
+              last_arc = e;
+            }
+            if (--cnt == 0) {
+              if (_curr_length > limit) break;
+              limit = 0;
+              cnt = _block_size;
+            }
           }
         }
         if (_curr_length == 0) return false;
-        
-      search_end:
+        _next_arc = last_arc + 1;
 
         // Make heap of the candidate list (approximating a partial sort)
@@ -608 +619 @@
         // Pop the first element of the heap
         _in_arc = _candidates[0];
-        _next_arc = e;
         pop_heap( _candidates.begin(), _candidates.begin() + _curr_length,
                   _sort_func );
@@ -624 +634 @@
     ///
     /// \param graph The digraph the algorithm runs on.
-    /// \param arc_mixing Indicate if the arcs have to be stored in a
-    /// mixed order in the internal data structure. 
-    /// In special cases, it could lead to better overall performance,
-    /// but it is usually slower. Therefore it is disabled by default.
-    NetworkSimplex(const GR& graph, bool arc_mixing = false) :
+    NetworkSimplex(const GR& graph) :
       _graph(graph), _node_id(graph), _arc_id(graph),
       INF(std::numeric_limits<Value>::has_infinity ?
@@ -666 +672 @@
       _state.resize(max_arc_num);
 
-      // Copy the graph
+      // Copy the graph (store the arcs in a mixed order)
       int i = 0;
       for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
         _node_id[n] = i;
       }
-      if (arc_mixing) {
-        // Store the arcs in a mixed order
-        int k = std::max(int(std::sqrt(double(_arc_num))), 10);
-        int i = 0, j = 0;
-        for (ArcIt a(_graph); a != INVALID; ++a) {
-          _arc_id[a] = i;
-          _source[i] = _node_id[_graph.source(a)];
-          _target[i] = _node_id[_graph.target(a)];
-          if ((i += k) >= _arc_num) i = ++j;
-        }
-      } else {
-        // Store the arcs in the original order
-        int i = 0;
-        for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
-          _arc_id[a] = i;
-          _source[i] = _node_id[_graph.source(a)];
-          _target[i] = _node_id[_graph.target(a)];
-        }
+      int k = std::max(int(std::sqrt(double(_arc_num))), 10);
+      i = 0;
+      for (ArcIt a(_graph); a != INVALID; ++a) {
+        _arc_id[a] = i;
+        _source[i] = _node_id[_graph.source(a)];
+        _target[i] = _node_id[_graph.target(a)];
+        if ((i += k) >= _arc_num) i = (i % k) + 1;
       }
       
-      // Reset parameters
-      reset();
+      // Initialize maps
+      for (int i = 0; i != _node_num; ++i) {
+        _supply[i] = 0;
+      }
+      for (int i = 0; i != _arc_num; ++i) {
+        _lower[i] = 0;
+        _upper[i] = INF;
+        _cost[i] = 1;
+      }
+      _have_lower = false;
+      _stype = GEQ;
     }
 
@@ -765 +769 @@
     /// If neither this function nor \ref stSupply() is used before
     /// calling \ref run(), the supply of each node will be set to zero.
+    /// (It makes sense only if non-zero lower bounds are given.)
     ///
     /// \param map A node map storing the supply values.
@@ -785 +790 @@
     /// If neither this function nor \ref supplyMap() is used before
     /// calling \ref run(), the supply of each node will be set to zero.
+    /// (It makes sense only if non-zero lower bounds are given.)
     ///
     /// Using this function has the same effect as using \ref supplyMap()

lemon/preflow.h

@@ -53 +53 @@
     /// The type of the map that stores the flow values.
     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
-#ifdef DOXYGEN
-    typedef GR::ArcMap<Value> FlowMap;
-#else
     typedef typename Digraph::template ArcMap<Value> FlowMap;
-#endif
 
     /// \brief Instantiates a FlowMap.
@@ -72 +68 @@
     /// The elevator type used by Preflow algorithm.
     ///
-    /// \sa Elevator, LinkedElevator
-#ifdef DOXYGEN
-    typedef lemon::Elevator<GR, GR::Node> Elevator;
-#else
-    typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
-#endif
+    /// \sa Elevator
+    /// \sa LinkedElevator
+    typedef LinkedElevator<Digraph, typename Digraph::Node> Elevator;
 
     /// \brief Instantiates an Elevator.
@@ -105 +98 @@
   /// "flow of maximum value" in a digraph.
   /// The preflow algorithms are the fastest known maximum
-  /// flow algorithms. The current implementation uses a mixture of the
+  /// flow algorithms. The current implementation use a mixture of the
   /// \e "highest label" and the \e "bound decrease" heuristics.
   /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
@@ -379 +372 @@
     }
 
-    /// \brief Sets the tolerance used by the algorithm.
-    ///
-    /// Sets the tolerance object used by the algorithm.
-    /// \return <tt>(*this)</tt>
-    Preflow& tolerance(const Tolerance& tolerance) {
+    /// \brief Sets the tolerance used by algorithm.
+    ///
+    /// Sets the tolerance used by algorithm.
+    Preflow& tolerance(const Tolerance& tolerance) const {
       _tolerance = tolerance;
       return *this;
@@ -390 +382 @@
     /// \brief Returns a const reference to the tolerance.
     ///
-    /// Returns a const reference to the tolerance object used by
-    /// the algorithm.
+    /// Returns a const reference to the tolerance.
     const Tolerance& tolerance() const {
-      return _tolerance;
+      return tolerance;
     }
 
@@ -399 +390 @@
     /// The simplest way to execute the preflow algorithm is to use
     /// \ref run() or \ref runMinCut().\n
-    /// If you need better control on the initial solution or the execution,
-    /// you have to call one of the \ref init() functions first, then
+    /// If you need more control on the initial solution or the execution,
+    /// first you have to call one of the \ref init() functions, then
     /// \ref startFirstPhase() and if you need it \ref startSecondPhase().
 

lemon/radix_heap.h

@@ -20 +20 @@
 #define LEMON_RADIX_HEAP_H
 
-///\ingroup heaps
+///\ingroup auxdat
 ///\file
-///\brief Radix heap implementation.
+///\brief Radix Heap implementation.
 
 #include <vector>
@@ -30 +30 @@
 
 
-  /// \ingroup heaps
+  /// \ingroup auxdata
   ///
-  /// \brief Radix heap data structure.
+  /// \brief A Radix Heap implementation.
   ///
-  /// This class implements the \e radix \e heap data structure.
-  /// It practically conforms to the \ref concepts::Heap "heap concept",
-  /// but it has some limitations due its special implementation.
-  /// The type of the priorities must be \c int and the priority of an
-  /// item cannot be decreased under the priority of the last removed item.
+  /// This class implements the \e radix \e heap data structure. A \e heap
+  /// is a data structure for storing items with specified values called \e
+  /// priorities in such a way that finding the item with minimum priority is
+  /// efficient. This heap type can store only items with \e int priority.
+  /// In a heap one can change the priority of an item, add or erase an
+  /// item, but the priority cannot be decreased under the last removed
+  /// item's priority.
   ///
-  /// \tparam IM A read-writable item map with \c int values, used
-  /// internally to handle the cross references.
+  /// \param IM A read and writable Item int map, used internally
+  /// to handle the cross references.
+  ///
+  /// \see BinHeap
+  /// \see Dijkstra
   template <typename IM>
   class RadixHeap {
 
   public:
-
-    /// Type of the item-int map.
+    typedef typename IM::Key Item;
+    typedef int Prio;
     typedef IM ItemIntMap;
-    /// Type of the priorities.
-    typedef int Prio;
-    /// Type of the items stored in the heap.
-    typedef typename ItemIntMap::Key Item;
 
     /// \brief Exception thrown by RadixHeap.
     ///
-    /// This exception is thrown when an item is inserted into a
-    /// RadixHeap with a priority smaller than the last erased one.
+    /// This Exception is thrown when a smaller priority
+    /// is inserted into the \e RadixHeap then the last time erased.
     /// \see RadixHeap
-    class PriorityUnderflowError : public Exception {
+
+    class UnderFlowPriorityError : public Exception {
     public:
       virtual const char* what() const throw() {
-        return "lemon::RadixHeap::PriorityUnderflowError";
+        return "lemon::RadixHeap::UnderFlowPriorityError";
       }
     };
 
-    /// \brief Type to represent the states of the items.
-    ///
-    /// Each item has a state associated to it. It can be "in heap",
-    /// "pre-heap" or "post-heap". The latter two are indifferent from the
+    /// \brief Type to represent the items states.
+    ///
+    /// Each Item element have a state associated to it. It may be "in heap",
+    /// "pre heap" or "post heap". The latter two are indifferent from the
     /// heap's point of view, but may be useful to the user.
     ///
-    /// The item-int map must be initialized in such way that it assigns
-    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
+    /// The ItemIntMap \e should be initialized in such way that it maps
+    /// PRE_HEAP (-1) to any element to be put in the heap...
     enum State {
-      IN_HEAP = 0,    ///< = 0.
-      PRE_HEAP = -1,  ///< = -1.
-      POST_HEAP = -2  ///< = -2.
+      IN_HEAP = 0,
+      PRE_HEAP = -1,
+      POST_HEAP = -2
     };
 
@@ -95 +97 @@
     };
 
-    std::vector<RadixItem> _data;
-    std::vector<RadixBox> _boxes;
+    std::vector<RadixItem> data;
+    std::vector<RadixBox> boxes;
 
     ItemIntMap &_iim;
 
+
   public:
-
-    /// \brief Constructor.
-    ///
-    /// Constructor.
-    /// \param map A map that assigns \c int values to the items.
-    /// It is used internally to handle the cross references.
-    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
-    /// \param minimum The initial minimum value of the heap.
-    /// \param capacity The initial capacity of the heap.
-    RadixHeap(ItemIntMap &map, int minimum = 0, int capacity = 0)
-      : _iim(map)
-    {
-      _boxes.push_back(RadixBox(minimum, 1));
-      _boxes.push_back(RadixBox(minimum + 1, 1));
-      while (lower(_boxes.size() - 1, capacity + minimum - 1)) {
+    /// \brief The constructor.
+    ///
+    /// The constructor.
+    ///
+    /// \param map It should be given to the constructor, since it is used
+    /// internally to handle the cross references. The value of the map
+    /// should be PRE_HEAP (-1) for each element.
+    ///
+    /// \param minimal The initial minimal value of the heap.
+    /// \param capacity It determines the initial capacity of the heap.
+    RadixHeap(ItemIntMap &map, int minimal = 0, int capacity = 0)
+      : _iim(map) {
+      boxes.push_back(RadixBox(minimal, 1));
+      boxes.push_back(RadixBox(minimal + 1, 1));
+      while (lower(boxes.size() - 1, capacity + minimal - 1)) {
         extend();
       }
     }
 
-    /// \brief The number of items stored in the heap.
-    ///
-    /// This function returns the number of items stored in the heap.
-    int size() const { return _data.size(); }
-
-    /// \brief Check if the heap is empty.
-    ///
-    /// This function returns \c true if the heap is empty.
-    bool empty() const { return _data.empty(); }
-
-    /// \brief Make the heap empty.
-    ///
-    /// This functon makes the heap empty.
-    /// It does not change the cross reference map. If you want to reuse
-    /// a heap that is not surely empty, you should first clear it and
-    /// then you should set the cross reference map to \c PRE_HEAP
-    /// for each item.
-    /// \param minimum The minimum value of the heap.
-    /// \param capacity The capacity of the heap.
-    void clear(int minimum = 0, int capacity = 0) {
-      _data.clear(); _boxes.clear();
-      _boxes.push_back(RadixBox(minimum, 1));
-      _boxes.push_back(RadixBox(minimum + 1, 1));
-      while (lower(_boxes.size() - 1, capacity + minimum - 1)) {
+    /// The number of items stored in the heap.
+    ///
+    /// \brief Returns the number of items stored in the heap.
+    int size() const { return data.size(); }
+    /// \brief Checks if the heap stores no items.
+    ///
+    /// Returns \c true if and only if the heap stores no items.
+    bool empty() const { return data.empty(); }
+
+    /// \brief Make empty this heap.
+    ///
+    /// Make empty this heap. It does not change the cross reference
+    /// map.  If you want to reuse a heap what is not surely empty you
+    /// should first clear the heap and after that you should set the
+    /// cross reference map for each item to \c PRE_HEAP.
+    void clear(int minimal = 0, int capacity = 0) {
+      data.clear(); boxes.clear();
+      boxes.push_back(RadixBox(minimal, 1));
+      boxes.push_back(RadixBox(minimal + 1, 1));
+      while (lower(boxes.size() - 1, capacity + minimal - 1)) {
         extend();
       }
@@ -151 +150 @@
 
     bool upper(int box, Prio pr) {
-      return pr < _boxes[box].min;
+      return pr < boxes[box].min;
     }
 
     bool lower(int box, Prio pr) {
-      return pr >= _boxes[box].min + _boxes[box].size;
-    }
-
-    // Remove item from the box list
+      return pr >= boxes[box].min + boxes[box].size;
+    }
+
+    /// \brief Remove item from the box list.
     void remove(int index) {
-      if (_data[index].prev >= 0) {
-        _data[_data[index].prev].next = _data[index].next;
+      if (data[index].prev >= 0) {
+        data[data[index].prev].next = data[index].next;
       } else {
-        _boxes[_data[index].box].first = _data[index].next;
-      }
-      if (_data[index].next >= 0) {
-        _data[_data[index].next].prev = _data[index].prev;
-      }
-    }
-
-    // Insert item into the box list
+        boxes[data[index].box].first = data[index].next;
+      }
+      if (data[index].next >= 0) {
+        data[data[index].next].prev = data[index].prev;
+      }
+    }
+
+    /// \brief Insert item into the box list.
     void insert(int box, int index) {
-      if (_boxes[box].first == -1) {
-        _boxes[box].first = index;
-        _data[index].next = _data[index].prev = -1;
+      if (boxes[box].first == -1) {
+        boxes[box].first = index;
+        data[index].next = data[index].prev = -1;
       } else {
-        _data[index].next = _boxes[box].first;
-        _data[_boxes[box].first].prev = index;
-        _data[index].prev = -1;
-        _boxes[box].first = index;
-      }
-      _data[index].box = box;
-    }
-
-    // Add a new box to the box list
+        data[index].next = boxes[box].first;
+        data[boxes[box].first].prev = index;
+        data[index].prev = -1;
+        boxes[box].first = index;
+      }
+      data[index].box = box;
+    }
+
+    /// \brief Add a new box to the box list.
     void extend() {
-      int min = _boxes.back().min + _boxes.back().size;
-      int bs = 2 * _boxes.back().size;
-      _boxes.push_back(RadixBox(min, bs));
-    }
-
-    // Move an item up into the proper box.
-    void bubbleUp(int index) {
-      if (!lower(_data[index].box, _data[index].prio)) return;
+      int min = boxes.back().min + boxes.back().size;
+      int bs = 2 * boxes.back().size;
+      boxes.push_back(RadixBox(min, bs));
+    }
+
+    /// \brief Move an item up into the proper box.
+    void bubble_up(int index) {
+      if (!lower(data[index].box, data[index].prio)) return;
       remove(index);
-      int box = findUp(_data[index].box, _data[index].prio);
+      int box = findUp(data[index].box, data[index].prio);
       insert(box, index);
     }
 
-    // Find up the proper box for the item with the given priority
+    /// \brief Find up the proper box for the item with the given prio.
     int findUp(int start, int pr) {
       while (lower(start, pr)) {
-        if (++start == int(_boxes.size())) {
+        if (++start == int(boxes.size())) {
           extend();
         }
@@ -209 +208 @@
     }
 
-    // Move an item down into the proper box
-    void bubbleDown(int index) {
-      if (!upper(_data[index].box, _data[index].prio)) return;
+    /// \brief Move an item down into the proper box.
+    void bubble_down(int index) {
+      if (!upper(data[index].box, data[index].prio)) return;
       remove(index);
-      int box = findDown(_data[index].box, _data[index].prio);
+      int box = findDown(data[index].box, data[index].prio);
       insert(box, index);
     }
 
-    // Find down the proper box for the item with the given priority
+    /// \brief Find up the proper box for the item with the given prio.
     int findDown(int start, int pr) {
       while (upper(start, pr)) {
-        if (--start < 0) throw PriorityUnderflowError();
+        if (--start < 0) throw UnderFlowPriorityError();
       }
       return start;
     }
 
-    // Find the first non-empty box
+    /// \brief Find the first not empty box.
     int findFirst() {
       int first = 0;
-      while (_boxes[first].first == -1) ++first;
+      while (boxes[first].first == -1) ++first;
       return first;
     }
 
-    // Gives back the minimum priority of the given box
+    /// \brief Gives back the minimal prio of the box.
     int minValue(int box) {
-      int min = _data[_boxes[box].first].prio;
-      for (int k = _boxes[box].first; k != -1; k = _data[k].next) {
-        if (_data[k].prio < min) min = _data[k].prio;
+      int min = data[boxes[box].first].prio;
+      for (int k = boxes[box].first; k != -1; k = data[k].next) {
+        if (data[k].prio < min) min = data[k].prio;
       }
       return min;
     }
 
-    // Rearrange the items of the heap and make the first box non-empty
+    /// \brief Rearrange the items of the heap and makes the
+    /// first box not empty.
     void moveDown() {
       int box = findFirst();
@@ -247 +247 @@
       int min = minValue(box);
       for (int i = 0; i <= box; ++i) {
-        _boxes[i].min = min;
-        min += _boxes[i].size;
-      }
-      int curr = _boxes[box].first, next;
+        boxes[i].min = min;
+        min += boxes[i].size;
+      }
+      int curr = boxes[box].first, next;
       while (curr != -1) {
-        next = _data[curr].next;
-        bubbleDown(curr);
+        next = data[curr].next;
+        bubble_down(curr);
         curr = next;
       }
     }
 
-    void relocateLast(int index) {
-      if (index != int(_data.size()) - 1) {
-        _data[index] = _data.back();
-        if (_data[index].prev != -1) {
-          _data[_data[index].prev].next = index;
+    void relocate_last(int index) {
+      if (index != int(data.size()) - 1) {
+        data[index] = data.back();
+        if (data[index].prev != -1) {
+          data[data[index].prev].next = index;
         } else {
-          _boxes[_data[index].box].first = index;
+          boxes[data[index].box].first = index;
         }
-        if (_data[index].next != -1) {
-          _data[_data[index].next].prev = index;
+        if (data[index].next != -1) {
+          data[data[index].next].prev = index;
         }
-        _iim[_data[index].item] = index;
-      }
-      _data.pop_back();
+        _iim[data[index].item] = index;
+      }
+      data.pop_back();
     }
 
@@ -278 +278 @@
     /// \brief Insert an item into the heap with the given priority.
     ///
-    /// This function inserts the given item into the heap with the
-    /// given priority.
+    /// Adds \c i to the heap with priority \c p.
     /// \param i The item to insert.
     /// \param p The priority of the item.
-    /// \pre \e i must not be stored in the heap.
-    /// \warning This method may throw an \c UnderFlowPriorityException.
     void push(const Item &i, const Prio &p) {
-      int n = _data.size();
+      int n = data.size();
       _iim.set(i, n);
-      _data.push_back(RadixItem(i, p));
-      while (lower(_boxes.size() - 1, p)) {
+      data.push_back(RadixItem(i, p));
+      while (lower(boxes.size() - 1, p)) {
         extend();
       }
-      int box = findDown(_boxes.size() - 1, p);
+      int box = findDown(boxes.size() - 1, p);
       insert(box, n);
     }
 
-    /// \brief Return the item having minimum priority.
-    ///
-    /// This function returns the item having minimum priority.
-    /// \pre The heap must be non-empty.
+    /// \brief Returns the item with minimum priority.
+    ///
+    /// This method returns the item with minimum priority.
+    /// \pre The heap must be nonempty.
     Item top() const {
       const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
-      return _data[_boxes[0].first].item;
-    }
-
-    /// \brief The minimum priority.
-    ///
-    /// This function returns the minimum priority.
-    /// \pre The heap must be non-empty.
+      return data[boxes[0].first].item;
+    }
+
+    /// \brief Returns the minimum priority.
+    ///
+    /// It returns the minimum priority.
+    /// \pre The heap must be nonempty.
     Prio prio() const {
       const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
-      return _data[_boxes[0].first].prio;
+      return data[boxes[0].first].prio;
      }
 
-    /// \brief Remove the item having minimum priority.
-    ///
-    /// This function removes the item having minimum priority.
+    /// \brief Deletes the item with minimum priority.
+    ///
+    /// This method deletes the item with minimum priority.
     /// \pre The heap must be non-empty.
     void pop() {
       moveDown();
-      int index = _boxes[0].first;
-      _iim[_data[index].item] = POST_HEAP;
+      int index = boxes[0].first;
+      _iim[data[index].item] = POST_HEAP;
       remove(index);
-      relocateLast(index);
-    }
-
-    /// \brief Remove the given item from the heap.
-    ///
-    /// This function removes the given item from the heap if it is
-    /// already stored.
-    /// \param i The item to delete.
-    /// \pre \e i must be in the heap.
+      relocate_last(index);
+    }
+
+    /// \brief Deletes \c i from the heap.
+    ///
+    /// This method deletes item \c i from the heap, if \c i was
+    /// already stored in the heap.
+    /// \param i The item to erase.
     void erase(const Item &i) {
       int index = _iim[i];
       _iim[i] = POST_HEAP;
       remove(index);
-      relocateLast(index);
+      relocate_last(index);
    }
 
-    /// \brief The priority of the given item.
-    ///
-    /// This function returns the priority of the given item.
-    /// \param i The item.
-    /// \pre \e i must be in the heap.
+    /// \brief Returns the priority of \c i.
+    ///
+    /// This function returns the priority of item \c i.
+    /// \pre \c i must be in the heap.
+    /// \param i The item.
     Prio operator[](const Item &i) const {
       int idx = _iim[i];
-      return _data[idx].prio;
-    }
-
-    /// \brief Set the priority of an item or insert it, if it is
-    /// not stored in the heap.
-    ///
-    /// This method sets the priority of the given item if it is
-    /// already stored in the heap. Otherwise it inserts the given
-    /// item into the heap with the given priority.
+      return data[idx].prio;
+    }
+
+    /// \brief \c i gets to the heap with priority \c p independently
+    /// if \c i was already there.
+    ///
+    /// This method calls \ref push(\c i, \c p) if \c i is not stored
+    /// in the heap and sets the priority of \c i to \c p otherwise.
+    /// It may throw an \e UnderFlowPriorityException.
     /// \param i The item.
     /// \param p The priority.
-    /// \pre \e i must be in the heap.
-    /// \warning This method may throw an \c UnderFlowPriorityException.
     void set(const Item &i, const Prio &p) {
       int idx = _iim[i];
@@ -363 +357 @@
         push(i, p);
       }
-      else if( p >= _data[idx].prio ) {
-        _data[idx].prio = p;
-        bubbleUp(idx);
+      else if( p >= data[idx].prio ) {
+        data[idx].prio = p;
+        bubble_up(idx);
       } else {
-        _data[idx].prio = p;
-        bubbleDown(idx);
-      }
-    }
-
-    /// \brief Decrease the priority of an item to the given value.
-    ///
-    /// This function decreases the priority of an item to the given value.
+        data[idx].prio = p;
+        bubble_down(idx);
+      }
+    }
+
+
+    /// \brief Decreases the priority of \c i to \c p.
+    ///
+    /// This method decreases the priority of item \c i to \c p.
+    /// \pre \c i must be stored in the heap with priority at least \c p, and
+    /// \c should be greater or equal to the last removed item's priority.
     /// \param i The item.
     /// \param p The priority.
-    /// \pre \e i must be stored in the heap with priority at least \e p.
-    /// \warning This method may throw an \c UnderFlowPriorityException.
     void decrease(const Item &i, const Prio &p) {
       int idx = _iim[i];
-      _data[idx].prio = p;
-      bubbleDown(idx);
-    }
-
-    /// \brief Increase the priority of an item to the given value.
-    ///
-    /// This function increases the priority of an item to the given value.
+      data[idx].prio = p;
+      bubble_down(idx);
+    }
+
+    /// \brief Increases the priority of \c i to \c p.
+    ///
+    /// This method sets the priority of item \c i to \c p.
+    /// \pre \c i must be stored in the heap with priority at most \c p
     /// \param i The item.
     /// \param p The priority.
-    /// \pre \e i must be stored in the heap with priority at most \e p.
     void increase(const Item &i, const Prio &p) {
       int idx = _iim[i];
-      _data[idx].prio = p;
-      bubbleUp(idx);
-    }
-
-    /// \brief Return the state of an item.
-    ///
-    /// This method returns \c PRE_HEAP if the given item has never
-    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
-    /// and \c POST_HEAP otherwise.
-    /// In the latter case it is possible that the item will get back
-    /// to the heap again.
+      data[idx].prio = p;
+      bubble_up(idx);
+    }
+
+    /// \brief Returns if \c item is in, has already been in, or has
+    /// never been in the heap.
+    ///
+    /// This method returns PRE_HEAP if \c item has never been in the
+    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
+    /// otherwise. In the latter case it is possible that \c item will
+    /// get back to the heap again.
     /// \param i The item.
     State state(const Item &i) const {
@@ -411 +406 @@
     }
 
-    /// \brief Set the state of an item in the heap.
-    ///
-    /// This function sets the state of the given item in the heap.
-    /// It can be used to manually clear the heap when it is important
-    /// to achive better time complexity.
+    /// \brief Sets the state of the \c item in the heap.
+    ///
+    /// Sets the state of the \c item in the heap. It can be used to
+    /// manually clear the heap when it is important to achive the
+    /// better time complexity.
     /// \param i The item.
     /// \param st The state. It should not be \c IN_HEAP.

scripts/chg-len.py

@@ -1 +1 @@
 #! /usr/bin/env python
-#
-# This file is a part of LEMON, a generic C++ optimization library.
-#
-# Copyright (C) 2003-2009
-# Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
-# (Egervary Research Group on Combinatorial Optimization, EGRES).
-#
-# Permission to use, modify and distribute this software is granted
-# provided that this copyright notice appears in all copies. For
-# precise terms see the accompanying LICENSE file.
-#
-# This software is provided "AS IS" with no warranty of any kind,
-# express or implied, and with no claim as to its suitability for any
-# purpose.
 
 import sys

scripts/mk-release.sh

@@ -1 +1 @@
 #!/bin/bash
-#
-# This file is a part of LEMON, a generic C++ optimization library.
-#
-# Copyright (C) 2003-2009
-# Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
-# (Egervary Research Group on Combinatorial Optimization, EGRES).
-#
-# Permission to use, modify and distribute this software is granted
-# provided that this copyright notice appears in all copies. For
-# precise terms see the accompanying LICENSE file.
-#
-# This software is provided "AS IS" with no warranty of any kind,
-# express or implied, and with no claim as to its suitability for any
-# purpose.
 
 set -e

scripts/unify-sources.sh

@@ -1 +1 @@
 #!/bin/bash
-#
-# This file is a part of LEMON, a generic C++ optimization library.
-#
-# Copyright (C) 2003-2009
-# Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
-# (Egervary Research Group on Combinatorial Optimization, EGRES).
-#
-# Permission to use, modify and distribute this software is granted
-# provided that this copyright notice appears in all copies. For
-# precise terms see the accompanying LICENSE file.
-#
-# This software is provided "AS IS" with no warranty of any kind,
-# express or implied, and with no claim as to its suitability for any
-# purpose.
 
 YEAR=`date +%Y`

test/CMakeLists.txt

@@ -10 +10 @@
 SET(TESTS
   adaptors_test
-  bellman_ford_test
   bfs_test
   circulation_test

test/Makefile.am

@@ -8 +8 @@
 check_PROGRAMS += \
         test/adaptors_test \
-        test/bellman_ford_test \
         test/bfs_test \
         test/circulation_test \
@@ -54 +53 @@
 
 test_adaptors_test_SOURCES = test/adaptors_test.cc
-test_bellman_ford_test_SOURCES = test/bellman_ford_test.cc
 test_bfs_test_SOURCES = test/bfs_test.cc
 test_circulation_test_SOURCES = test/circulation_test.cc

test/circulation_test.cc

@@ -88 +88 @@
     .supplyMap(supply)
     .flowMap(flow);
-  
-  const CirculationType::Elevator& elev = const_circ_test.elevator();
-  circ_test.elevator(const_cast<CirculationType::Elevator&>(elev));
-  CirculationType::Tolerance tol = const_circ_test.tolerance();
-  circ_test.tolerance(tol);
 
   circ_test.init();

test/heap_test.cc

@@ -26 +26 @@
 
 #include <lemon/smart_graph.h>
+
 #include <lemon/lgf_reader.h>
 #include <lemon/dijkstra.h>
@@ -31 +32 @@
 
 #include <lemon/bin_heap.h>
-#include <lemon/fourary_heap.h>
-#include <lemon/kary_heap.h>
 #include <lemon/fib_heap.h>
-#include <lemon/pairing_heap.h>
 #include <lemon/radix_heap.h>
-#include <lemon/binom_heap.h>
 #include <lemon/bucket_heap.h>
 
@@ -93 +90 @@
 void heapSortTest() {
   RangeMap<int> map(test_len, -1);
+
   Heap heap(map);
 
   std::vector<int> v(test_len);
+
   for (int i = 0; i < test_len; ++i) {
     v[i] = test_seq[i];
@@ -102 +101 @@
   std::sort(v.begin(), v.end());
   for (int i = 0; i < test_len; ++i) {
-    check(v[i] == heap.prio(), "Wrong order in heap sort.");
+    check(v[i] == heap.prio() ,"Wrong order in heap sort.");
     heap.pop();
   }
@@ -114 +113 @@
 
   std::vector<int> v(test_len);
+
   for (int i = 0; i < test_len; ++i) {
     v[i] = test_seq[i];
@@ -124 +124 @@
   std::sort(v.begin(), v.end());
   for (int i = 0; i < test_len; ++i) {
-    check(v[i] == heap.prio(), "Wrong order in heap increase test.");
+    check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
     heap.pop();
   }
 }
+
+
 
 template <typename Heap>
@@ -143 +145 @@
     if (dijkstra.reached(s)) {
       check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
-             "Error in shortest path tree.");
+             "Error in a shortest path tree!");
     }
   }
@@ -152 +154 @@
       Node s = digraph.source(a);
       check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
-             "Error in shortest path tree.");
+             "Error in a shortest path tree!");
     }
   }
@@ -174 +176 @@
     run();
 
-  // BinHeap
   {
     typedef BinHeap<Prio, ItemIntMap> IntHeap;
@@ -186 +187 @@
   }
 
-  // FouraryHeap
-  {
-    typedef FouraryHeap<Prio, ItemIntMap> IntHeap;
-    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
-    heapSortTest<IntHeap>();
-    heapIncreaseTest<IntHeap>();
-
-    typedef FouraryHeap<Prio, IntNodeMap > NodeHeap;
-    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
-    dijkstraHeapTest<NodeHeap>(digraph, length, source);
-  }
-
-  // KaryHeap
-  {
-    typedef KaryHeap<Prio, ItemIntMap> IntHeap;
-    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
-    heapSortTest<IntHeap>();
-    heapIncreaseTest<IntHeap>();
-
-    typedef KaryHeap<Prio, IntNodeMap > NodeHeap;
-    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
-    dijkstraHeapTest<NodeHeap>(digraph, length, source);
-  }
-
-  // FibHeap
   {
     typedef FibHeap<Prio, ItemIntMap> IntHeap;
@@ -222 +198 @@
   }
 
-  // PairingHeap
-  {
-    typedef PairingHeap<Prio, ItemIntMap> IntHeap;
-    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
-    heapSortTest<IntHeap>();
-    heapIncreaseTest<IntHeap>();
-
-    typedef PairingHeap<Prio, IntNodeMap > NodeHeap;
-    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
-    dijkstraHeapTest<NodeHeap>(digraph, length, source);
-  }
-
-  // RadixHeap
   {
     typedef RadixHeap<ItemIntMap> IntHeap;
@@ -246 +209 @@
   }
 
-  // BinomHeap
-  {
-    typedef BinomHeap<Prio, ItemIntMap> IntHeap;
-    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
-    heapSortTest<IntHeap>();
-    heapIncreaseTest<IntHeap>();
-
-    typedef BinomHeap<Prio, IntNodeMap > NodeHeap;
-    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
-    dijkstraHeapTest<NodeHeap>(digraph, length, source);
-  }
-
-  // BucketHeap, SimpleBucketHeap
   {
     typedef BucketHeap<ItemIntMap> IntHeap;
@@ -268 +218 @@
     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
     dijkstraHeapTest<NodeHeap>(digraph, length, source);
-
-    typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap;
-    heapSortTest<SimpleIntHeap>();
-  }
+  }
+
 
   return 0;

test/maps_test.cc

@@ -24 +24 @@
 #include <lemon/maps.h>
 #include <lemon/list_graph.h>
-#include <lemon/smart_graph.h>
-#include <lemon/adaptors.h>
-#include <lemon/dfs.h>
 
 #include "test_tools.h"
@@ -64 +61 @@
 typedef ReadWriteMap<A, bool> BoolWriteMap;
 typedef ReferenceMap<A, bool, bool&, const bool&> BoolRefMap;
-
-template<typename Map1, typename Map2, typename ItemIt>
-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()
@@ -339 +330 @@
   {
     typedef std::vector<int> vec;
-    checkConcept<WriteMap<int, bool>, LoggerBoolMap<vec::iterator> >();
-    checkConcept<WriteMap<int, bool>,
-                 LoggerBoolMap<std::back_insert_iterator<vec> > >();
-
     vec v1;
     vec v2(10);
@@ -362 +349 @@
           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<Node> 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<Node> 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<ReadMap<Node, int>, IdMap<Graph, Node> >();
-    checkConcept<ReadMap<Arc, int>, IdMap<Graph, Arc> >();
-    checkConcept<ReadMap<Node, int>, RangeIdMap<Graph, Node> >();
-    checkConcept<ReadMap<Arc, int>, RangeIdMap<Graph, Arc> >();
-    
-    Graph gr;
-    IdMap<Graph, Node> nmap(gr);
-    IdMap<Graph, Arc> amap(gr);
-    RangeIdMap<Graph, Node> nrmap(gr);
-    RangeIdMap<Graph, Arc> 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<ReadMap<Arc, Node>, SourceMap<Graph> >();
-    checkConcept<ReadMap<Arc, Node>, TargetMap<Graph> >();
-    checkConcept<ReadMap<Edge, Arc>, ForwardMap<Graph> >();
-    checkConcept<ReadMap<Edge, Arc>, BackwardMap<Graph> >();
-    checkConcept<ReadMap<Node, int>, InDegMap<Graph> >();
-    checkConcept<ReadMap<Node, int>, OutDegMap<Graph> >();
-
-    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<Edge, bool>(true))),
-               targetMap(orienter(gr, constMap<Edge, bool>(false))),
-               EdgeIt(gr));
-
-    typedef Orienter<Graph, const ConstMap<Edge, bool> > Digraph;
-    Digraph dgr(gr, constMap<Edge, bool>(true));
-    OutDegMap<Digraph> odm(dgr);
-    InDegMap<Digraph> 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");
   }
   
@@ -516 +354 @@
   {
     typedef ListDigraph Graph;
-    DIGRAPH_TYPEDEFS(Graph);
-
-    checkConcept<ReadWriteMap<Node, int>,
-                 CrossRefMap<Graph, Node, int> >();
-    checkConcept<ReadWriteMap<Node, bool>,
-                 CrossRefMap<Graph, Node, bool> >();
-    checkConcept<ReadWriteMap<Node, double>,
-                 CrossRefMap<Graph, Node, double> >();
-    
-    Graph gr;
-    typedef CrossRefMap<Graph, Node, char> 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
-  {
-    typedef SmartDigraph Graph;
     DIGRAPH_TYPEDEFS(Graph);
 
@@ -613 +384 @@
           it == map.endValue(), "Wrong value iterator");
   }
-  
-  // Iterable bool map
-  {
-    typedef SmartGraph Graph;
-    typedef SmartGraph::Node Item;
-
-    typedef IterableBoolMap<SmartGraph, SmartGraph::Node> Ibm;
-    checkConcept<ReferenceMap<Item, bool, bool&, const bool&>, Ibm>();
-
-    const int num = 10;
-    Graph g;
-    std::vector<Item> items;
-    for (int i = 0; i < num; ++i) {
-      items.push_back(g.addNode());
-    }
-
-    Ibm map1(g, true);
-    int n = 0;
-    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
-      check(map1[static_cast<Item>(it)], "Wrong TrueIt");
-      ++n;
-    }
-    check(n == num, "Wrong number");
-
-    n = 0;
-    for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {
-        check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");
-        ++n;
-    }
-    check(n == num, "Wrong number");
-    check(Ibm::FalseIt(map1) == INVALID, "Wrong FalseIt");
-    check(Ibm::ItemIt(map1, false) == INVALID, "Wrong ItemIt for false");
-
-    map1[items[5]] = true;
-
-    n = 0;
-    for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {
-        check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");
-        ++n;
-    }
-    check(n == num, "Wrong number");
-
-    map1[items[num / 2]] = false;
-    check(map1[items[num / 2]] == false, "Wrong map value");
-
-    n = 0;
-    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
-        check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");
-        ++n;
-    }
-    check(n == num - 1, "Wrong number");
-
-    n = 0;
-    for (Ibm::FalseIt it(map1); it != INVALID; ++it) {
-        check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");
-        ++n;
-    }
-    check(n == 1, "Wrong number");
-
-    map1[items[0]] = false;
-    check(map1[items[0]] == false, "Wrong map value");
-
-    map1[items[num - 1]] = false;
-    check(map1[items[num - 1]] == false, "Wrong map value");
-
-    n = 0;
-    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
-        check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");
-        ++n;
-    }
-    check(n == num - 3, "Wrong number");
-    check(map1.trueNum() == num - 3, "Wrong number");
-
-    n = 0;
-    for (Ibm::FalseIt it(map1); it != INVALID; ++it) {
-        check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");
-        ++n;
-    }
-    check(n == 3, "Wrong number");
-    check(map1.falseNum() == 3, "Wrong number");
-  }
-
-  // Iterable int map
-  {
-    typedef SmartGraph Graph;
-    typedef SmartGraph::Node Item;
-    typedef IterableIntMap<SmartGraph, SmartGraph::Node> Iim;
-
-    checkConcept<ReferenceMap<Item, int, int&, const int&>, Iim>();
-
-    const int num = 10;
-    Graph g;
-    std::vector<Item> items;
-    for (int i = 0; i < num; ++i) {
-      items.push_back(g.addNode());
-    }
-
-    Iim map1(g);
-    check(map1.size() == 0, "Wrong size");
-
-    for (int i = 0; i < num; ++i) {
-      map1[items[i]] = i;
-    }
-    check(map1.size() == num, "Wrong size");
-
-    for (int i = 0; i < num; ++i) {
-      Iim::ItemIt it(map1, i);
-      check(static_cast<Item>(it) == items[i], "Wrong value");
-      ++it;
-      check(static_cast<Item>(it) == INVALID, "Wrong value");
-    }
-
-    for (int i = 0; i < num; ++i) {
-      map1[items[i]] = i % 2;
-    }
-    check(map1.size() == 2, "Wrong size");
-
-    int n = 0;
-    for (Iim::ItemIt it(map1, 0); it != INVALID; ++it) {
-      check(map1[static_cast<Item>(it)] == 0, "Wrong value");
-      ++n;
-    }
-    check(n == (num + 1) / 2, "Wrong number");
-
-    for (Iim::ItemIt it(map1, 1); it != INVALID; ++it) {
-      check(map1[static_cast<Item>(it)] == 1, "Wrong value");
-      ++n;
-    }
-    check(n == num, "Wrong number");
-
-  }
-
-  // Iterable value map
-  {
-    typedef SmartGraph Graph;
-    typedef SmartGraph::Node Item;
-    typedef IterableValueMap<SmartGraph, SmartGraph::Node, double> Ivm;
-
-    checkConcept<ReadWriteMap<Item, double>, Ivm>();
-
-    const int num = 10;
-    Graph g;
-    std::vector<Item> items;
-    for (int i = 0; i < num; ++i) {
-      items.push_back(g.addNode());
-    }
-
-    Ivm map1(g, 0.0);
-    check(distance(map1.beginValue(), map1.endValue()) == 1, "Wrong size");
-    check(*map1.beginValue() == 0.0, "Wrong value");
-
-    for (int i = 0; i < num; ++i) {
-      map1.set(items[i], static_cast<double>(i));
-    }
-    check(distance(map1.beginValue(), map1.endValue()) == num, "Wrong size");
-
-    for (int i = 0; i < num; ++i) {
-      Ivm::ItemIt it(map1, static_cast<double>(i));
-      check(static_cast<Item>(it) == items[i], "Wrong value");
-      ++it;
-      check(static_cast<Item>(it) == INVALID, "Wrong value");
-    }
-
-    for (Ivm::ValueIt vit = map1.beginValue();
-         vit != map1.endValue(); ++vit) {
-      check(map1[static_cast<Item>(Ivm::ItemIt(map1, *vit))] == *vit,
-            "Wrong ValueIt");
-    }
-
-    for (int i = 0; i < num; ++i) {
-      map1.set(items[i], static_cast<double>(i % 2));
-    }
-    check(distance(map1.beginValue(), map1.endValue()) == 2, "Wrong size");
-
-    int n = 0;
-    for (Ivm::ItemIt it(map1, 0.0); it != INVALID; ++it) {
-      check(map1[static_cast<Item>(it)] == 0.0, "Wrong value");
-      ++n;
-    }
-    check(n == (num + 1) / 2, "Wrong number");
-
-    for (Ivm::ItemIt it(map1, 1.0); it != INVALID; ++it) {
-      check(map1[static_cast<Item>(it)] == 1.0, "Wrong value");
-      ++n;
-    }
-    check(n == num, "Wrong number");
-
-  }
+
   return 0;
 }

test/preflow_test.cc

@@ -95 +95 @@
   PreflowType preflow_test(g, cap, n, n);
   const PreflowType& const_preflow_test = preflow_test;
-  
-  const PreflowType::Elevator& elev = const_preflow_test.elevator();
-  preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev));
-  PreflowType::Tolerance tol = const_preflow_test.tolerance();
-  preflow_test.tolerance(tol);
 
   preflow_test

tools/lemon-0.x-to-1.x.sh

@@ -36 +36 @@
         -e "s/Edge\>/_Ar_c_label_/g"\
         -e "s/\<edge\>/_ar_c_label_/g"\
-        -e "s/_edge\>/__ar_c_label_/g"\
+        -e "s/_edge\>/_ar_c_label_/g"\
         -e "s/Edges\>/_Ar_c_label_s/g"\
         -e "s/\<edges\>/_ar_c_label_s/g"\
-        -e "s/_edges\>/__ar_c_label_s/g"\
+        -e "s/_edges\>/_ar_c_label_s/g"\
         -e "s/\([Ee]\)dge\([a-z]\)/_\1d_ge_label_\2/g"\
         -e "s/\([a-z]\)edge/\1_ed_ge_label_/g"\
@@ -69 +69 @@
         -e "s/_GR_APH_TY_PEDE_FS_label_/GRAPH_TYPEDEFS/g"\
         -e "s/_DIGR_APH_TY_PEDE_FS_label_/DIGRAPH_TYPEDEFS/g"\
-        -e "s/\<digraph_adaptor\.h\>/adaptors.h/g"\
-        -e "s/\<digraph_utils\.h\>/core.h/g"\
-        -e "s/\<digraph_reader\.h\>/lgf_reader.h/g"\
-        -e "s/\<digraph_writer\.h\>/lgf_writer.h/g"\
-        -e "s/\<topology\.h\>/connectivity.h/g"\
         -e "s/DigraphToEps/GraphToEps/g"\
         -e "s/digraphToEps/graphToEps/g"\