Index: lemon/Makefile.am
===================================================================
--- lemon/Makefile.am	(revision 686)
+++ lemon/Makefile.am	(revision 696)
@@ -58,4 +58,5 @@
 	lemon/arg_parser.h \
 	lemon/assert.h \
+	lemon/bellman_ford.h \
 	lemon/bfs.h \
 	lemon/bin_heap.h \
@@ -93,4 +94,5 @@
 	lemon/lp_base.h \
 	lemon/lp_skeleton.h \
+	lemon/list_graph.h \
 	lemon/maps.h \
 	lemon/matching.h \
Index: lemon/bellman_ford.h
===================================================================
--- lemon/bellman_ford.h	(revision 696)
+++ lemon/bellman_ford.h	(revision 696)
@@ -0,0 +1,1042 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2008
+ * 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.
+ *
+ */
+
+#ifndef LEMON_BELMANN_FORD_H
+#define LEMON_BELMANN_FORD_H
+
+/// \ingroup shortest_path
+/// \file
+/// \brief Bellman-Ford algorithm.
+///
+
+#include <lemon/bits/path_dump.h>
+#include <lemon/core.h>
+#include <lemon/error.h>
+#include <lemon/maps.h>
+
+#include <limits>
+
+namespace lemon {
+
+  /// \brief Default OperationTraits for the BellmanFord algorithm class.
+  ///  
+  /// It defines all computational operations and constants which are
+  /// used in the Bellman-Ford algorithm. The default implementation
+  /// is based on the numeric_limits class. If the numeric type does not
+  /// have infinity value then the maximum value is used as extremal
+  /// infinity value.
+  template <
+    typename Value, 
+    bool has_infinity = std::numeric_limits<Value>::has_infinity>
+  struct BellmanFordDefaultOperationTraits {
+    /// \brief Gives back the zero value of the type.
+    static Value zero() {
+      return static_cast<Value>(0);
+    }
+    /// \brief Gives back the positive infinity value of the type.
+    static Value infinity() {
+      return std::numeric_limits<Value>::infinity();
+    }
+    /// \brief Gives back the sum of the given two elements.
+    static Value plus(const Value& left, const Value& right) {
+      return left + right;
+    }
+    /// \brief Gives back true only if the first value less than the second.
+    static bool less(const Value& left, const Value& right) {
+      return left < right;
+    }
+  };
+
+  template <typename Value>
+  struct BellmanFordDefaultOperationTraits<Value, false> {
+    static Value zero() {
+      return static_cast<Value>(0);
+    }
+    static Value infinity() {
+      return std::numeric_limits<Value>::max();
+    }
+    static Value plus(const Value& left, const Value& right) {
+      if (left == infinity() || right == infinity()) return infinity();
+      return left + right;
+    }
+    static bool less(const Value& left, const Value& right) {
+      return left < right;
+    }
+  };
+  
+  /// \brief Default traits class of BellmanFord class.
+  ///
+  /// Default traits class of BellmanFord class.
+  /// \param _Digraph Digraph type.
+  /// \param _LegthMap Type of length map.
+  template<class _Digraph, class _LengthMap>
+  struct BellmanFordDefaultTraits {
+    /// The digraph type the algorithm runs on. 
+    typedef _Digraph Digraph;
+
+    /// \brief The type of the map that stores the arc lengths.
+    ///
+    /// The type of the map that stores the arc lengths.
+    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
+    typedef _LengthMap LengthMap;
+
+    // The type of the length of the arcs.
+    typedef typename _LengthMap::Value Value;
+
+    /// \brief Operation traits for Bellman-Ford algorithm.
+    ///
+    /// It defines the infinity type on the given Value type
+    /// and the used operation.
+    /// \see BellmanFordDefaultOperationTraits
+    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
+ 
+    /// \brief The type of the map that stores the last arcs of the 
+    /// shortest paths.
+    /// 
+    /// The type of the map that stores the last
+    /// arcs of the shortest paths.
+    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
+    ///
+    typedef typename Digraph::template NodeMap<typename _Digraph::Arc> PredMap;
+
+    /// \brief Instantiates a PredMap.
+    /// 
+    /// This function instantiates a \ref PredMap. 
+    /// \param digraph is the digraph, to which we would like to define the PredMap.
+    static PredMap *createPredMap(const _Digraph& digraph) {
+      return new PredMap(digraph);
+    }
+
+    /// \brief The type of the map that stores the dists of the nodes.
+    ///
+    /// The type of the map that stores the dists of the nodes.
+    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
+    ///
+    typedef typename Digraph::template NodeMap<typename _LengthMap::Value> 
+    DistMap;
+
+    /// \brief Instantiates a DistMap.
+    ///
+    /// This function instantiates a \ref DistMap. 
+    /// \param digraph is the digraph, to which we would like to define the 
+    /// \ref DistMap
+    static DistMap *createDistMap(const _Digraph& digraph) {
+      return new DistMap(digraph);
+    }
+
+  };
+  
+  /// \brief %BellmanFord algorithm class.
+  ///
+  /// \ingroup shortest_path
+  /// This class provides an efficient implementation of \c Bellman-Ford 
+  /// algorithm. The arc lengths are passed to the algorithm using a
+  /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any 
+  /// kind of length.
+  ///
+  /// The Bellman-Ford algorithm solves the shortest path from one node
+  /// problem when the arcs can have negative length but the digraph should
+  /// not contain cycles with negative sum of length. If we can assume
+  /// that all arc is non-negative in the digraph then the dijkstra algorithm
+  /// should be used rather.
+  ///
+  /// The maximal time complexity of the algorithm is \f$ O(ne) \f$.
+  ///
+  /// The type of the length is determined by the
+  /// \ref concepts::ReadMap::Value "Value" of the length map.
+  ///
+  /// \param _Digraph The digraph type the algorithm runs on. The default value
+  /// is \ref ListDigraph. The value of _Digraph is not used directly by
+  /// BellmanFord, it is only passed to \ref BellmanFordDefaultTraits.
+  /// \param _LengthMap This read-only ArcMap determines the lengths of the
+  /// arcs. The default map type is \ref concepts::Digraph::ArcMap 
+  /// "Digraph::ArcMap<int>".  The value of _LengthMap is not used directly 
+  /// by BellmanFord, it is only passed to \ref BellmanFordDefaultTraits.  
+  /// \param _Traits Traits class to set various data types used by the 
+  /// algorithm.  The default traits class is \ref BellmanFordDefaultTraits
+  /// "BellmanFordDefaultTraits<_Digraph,_LengthMap>".  See \ref
+  /// BellmanFordDefaultTraits for the documentation of a BellmanFord traits
+  /// class.
+#ifdef DOXYGEN
+  template <typename _Digraph, typename _LengthMap, typename _Traits>
+#else
+  template <typename _Digraph,
+	    typename _LengthMap=typename _Digraph::template ArcMap<int>,
+	    typename _Traits=BellmanFordDefaultTraits<_Digraph,_LengthMap> >
+#endif
+  class BellmanFord {
+  public:
+
+    typedef _Traits Traits;
+    ///The type of the underlying digraph.
+    typedef typename _Traits::Digraph Digraph;
+
+    typedef typename Digraph::Node Node;
+    typedef typename Digraph::NodeIt NodeIt;
+    typedef typename Digraph::Arc Arc;
+    typedef typename Digraph::OutArcIt OutArcIt;
+    
+    /// \brief The type of the length of the arcs.
+    typedef typename _Traits::LengthMap::Value Value;
+    /// \brief The type of the map that stores the arc lengths.
+    typedef typename _Traits::LengthMap LengthMap;
+    /// \brief The type of the map that stores the last
+    /// arcs of the shortest paths.
+    typedef typename _Traits::PredMap PredMap;
+    /// \brief The type of the map that stores the dists of the nodes.
+    typedef typename _Traits::DistMap DistMap;
+    /// \brief The operation traits.
+    typedef typename _Traits::OperationTraits OperationTraits;
+  private:
+    /// Pointer to the underlying digraph.
+    const Digraph *digraph;
+    /// Pointer to the length map
+    const LengthMap *length;
+    ///Pointer to the map of predecessors arcs.
+    PredMap *_pred;
+    ///Indicates if \ref _pred is locally allocated (\c true) or not.
+    bool local_pred;
+    ///Pointer to the map of distances.
+    DistMap *_dist;
+    ///Indicates if \ref _dist is locally allocated (\c true) or not.
+    bool local_dist;
+
+    typedef typename Digraph::template NodeMap<bool> MaskMap;
+    MaskMap *_mask;
+
+    std::vector<Node> _process;
+
+    /// Creates the maps if necessary.
+    void create_maps() {
+      if(!_pred) {
+	local_pred = true;
+	_pred = Traits::createPredMap(*digraph);
+      }
+      if(!_dist) {
+	local_dist = true;
+	_dist = Traits::createDistMap(*digraph);
+      }
+      _mask = new MaskMap(*digraph, false);
+    }
+    
+  public :
+ 
+    typedef BellmanFord Create;
+
+    /// \name Named template parameters
+
+    ///@{
+
+    template <class T>
+    struct DefPredMapTraits : public Traits {
+      typedef T PredMap;
+      static PredMap *createPredMap(const Digraph&) {
+        LEMON_ASSERT(false, "PredMap is not initialized");
+        return 0; // ignore warnings
+      }
+    };
+
+    /// \brief \ref named-templ-param "Named parameter" for setting PredMap 
+    /// type
+    /// \ref named-templ-param "Named parameter" for setting PredMap type
+    ///
+    template <class T>
+    struct SetPredMap 
+      : public BellmanFord< Digraph, LengthMap, DefPredMapTraits<T> > {
+      typedef BellmanFord< Digraph, LengthMap, DefPredMapTraits<T> > Create;
+    };
+    
+    template <class T>
+    struct DefDistMapTraits : public Traits {
+      typedef T DistMap;
+      static DistMap *createDistMap(const Digraph&) {
+        LEMON_ASSERT(false, "DistMap is not initialized");
+        return 0; // ignore warnings
+      }
+    };
+
+    /// \brief \ref named-templ-param "Named parameter" for setting DistMap 
+    /// type
+    ///
+    /// \ref named-templ-param "Named parameter" for setting DistMap type
+    ///
+    template <class T>
+    struct SetDistMap 
+      : public BellmanFord< Digraph, LengthMap, DefDistMapTraits<T> > {
+      typedef BellmanFord< Digraph, LengthMap, DefDistMapTraits<T> > Create;
+    };
+    
+    template <class T>
+    struct DefOperationTraitsTraits : public Traits {
+      typedef T OperationTraits;
+    };
+    
+    /// \brief \ref named-templ-param "Named parameter" for setting 
+    /// OperationTraits type
+    ///
+    /// \ref named-templ-param "Named parameter" for setting OperationTraits
+    /// type
+    template <class T>
+    struct SetOperationTraits
+      : public BellmanFord< Digraph, LengthMap, DefOperationTraitsTraits<T> > {
+      typedef BellmanFord< Digraph, LengthMap, DefOperationTraitsTraits<T> >
+      Create;
+    };
+    
+    ///@}
+
+  protected:
+    
+    BellmanFord() {}
+
+  public:      
+    
+    /// \brief Constructor.
+    ///
+    /// \param _graph the digraph the algorithm will run on.
+    /// \param _length the length map used by the algorithm.
+    BellmanFord(const Digraph& _graph, const LengthMap& _length) :
+      digraph(&_graph), length(&_length),
+      _pred(0), local_pred(false),
+      _dist(0), local_dist(false), _mask(0) {}
+    
+    ///Destructor.
+    ~BellmanFord() {
+      if(local_pred) delete _pred;
+      if(local_dist) delete _dist;
+      if(_mask) delete _mask;
+    }
+
+    /// \brief Sets the length map.
+    ///
+    /// Sets the length map.
+    /// \return \c (*this)
+    BellmanFord &lengthMap(const LengthMap &m) {
+      length = &m;
+      return *this;
+    }
+
+    /// \brief Sets the map storing the predecessor arcs.
+    ///
+    /// Sets the map storing the predecessor arcs.
+    /// If you don't use this function before calling \ref run(),
+    /// it will allocate one. The destuctor deallocates this
+    /// automatically allocated map, of course.
+    /// \return \c (*this)
+    BellmanFord &predMap(PredMap &m) {
+      if(local_pred) {
+	delete _pred;
+	local_pred=false;
+      }
+      _pred = &m;
+      return *this;
+    }
+
+    /// \brief Sets the map storing the distances calculated by the algorithm.
+    ///
+    /// Sets the map storing the distances calculated by the algorithm.
+    /// If you don't use this function before calling \ref run(),
+    /// it will allocate one. The destuctor deallocates this
+    /// automatically allocated map, of course.
+    /// \return \c (*this)
+    BellmanFord &distMap(DistMap &m) {
+      if(local_dist) {
+	delete _dist;
+	local_dist=false;
+      }
+      _dist = &m;
+      return *this;
+    }
+
+    /// \name Execution control
+    /// The simplest way to execute the algorithm is to use
+    /// one of the member functions called \c run(...).
+    /// \n
+    /// If you need more control on the execution,
+    /// first you must call \ref init(), then you can add several source nodes
+    /// with \ref addSource().
+    /// Finally \ref start() will perform the actual path
+    /// computation.
+
+    ///@{
+
+    /// \brief Initializes the internal data structures.
+    /// 
+    /// Initializes the internal data structures.
+    void init(const Value value = OperationTraits::infinity()) {
+      create_maps();
+      for (NodeIt it(*digraph); it != INVALID; ++it) {
+	_pred->set(it, INVALID);
+	_dist->set(it, value);
+      }
+      _process.clear();
+      if (OperationTraits::less(value, OperationTraits::infinity())) {
+	for (NodeIt it(*digraph); it != INVALID; ++it) {
+	  _process.push_back(it);
+	  _mask->set(it, true);
+	}
+      }
+    }
+    
+    /// \brief Adds a new source node.
+    ///
+    /// Adds a new source node. The optional second parameter is the 
+    /// initial distance of the node. It just sets the distance of the 
+    /// node to the given value.
+    void addSource(Node source, Value dst = OperationTraits::zero()) {
+      _dist->set(source, dst);
+      if (!(*_mask)[source]) {
+	_process.push_back(source);
+	_mask->set(source, true);
+      }
+    }
+
+    /// \brief Executes one round from the Bellman-Ford algorithm.
+    ///
+    /// If the algoritm calculated the distances in the previous round
+    /// exactly for all at most \f$ k \f$ length path lengths then it will
+    /// calculate the distances exactly for all at most \f$ k + 1 \f$
+    /// length path lengths. With \f$ k \f$ iteration this function
+    /// calculates the at most \f$ k \f$ length path lengths.
+    ///
+    /// \warning The paths with limited arc number cannot be retrieved
+    /// easily with \ref path() or \ref predArc() functions. If you
+    /// need the shortest path and not just the distance you should store
+    /// after each iteration the \ref predMap() map and manually build
+    /// the path.
+    ///
+    /// \return \c true when the algorithm have not found more shorter
+    /// paths.
+    bool processNextRound() {
+      for (int i = 0; i < int(_process.size()); ++i) {
+	_mask->set(_process[i], false);
+      }
+      std::vector<Node> nextProcess;
+      std::vector<Value> values(_process.size());
+      for (int i = 0; i < int(_process.size()); ++i) {
+	values[i] = (*_dist)[_process[i]];
+      }
+      for (int i = 0; i < int(_process.size()); ++i) {
+	for (OutArcIt it(*digraph, _process[i]); it != INVALID; ++it) {
+	  Node target = digraph->target(it);
+	  Value relaxed = OperationTraits::plus(values[i], (*length)[it]);
+	  if (OperationTraits::less(relaxed, (*_dist)[target])) {
+	    _pred->set(target, it);
+	    _dist->set(target, relaxed);
+	    if (!(*_mask)[target]) {
+	      _mask->set(target, true);
+	      nextProcess.push_back(target);
+	    }
+	  }	  
+	}
+      }
+      _process.swap(nextProcess);
+      return _process.empty();
+    }
+
+    /// \brief Executes one weak round from the Bellman-Ford algorithm.
+    ///
+    /// If the algorithm calculated the distances in the
+    /// previous round at least for all at most k length paths then it will
+    /// calculate the distances at least for all at most k + 1 length paths.
+    /// This function does not make it possible to calculate strictly the
+    /// at most k length minimal paths, this is why it is
+    /// called just weak round.
+    /// \return \c true when the algorithm have not found more shorter paths.
+    bool processNextWeakRound() {
+      for (int i = 0; i < int(_process.size()); ++i) {
+	_mask->set(_process[i], false);
+      }
+      std::vector<Node> nextProcess;
+      for (int i = 0; i < int(_process.size()); ++i) {
+	for (OutArcIt it(*digraph, _process[i]); it != INVALID; ++it) {
+	  Node target = digraph->target(it);
+	  Value relaxed = 
+	    OperationTraits::plus((*_dist)[_process[i]], (*length)[it]);
+	  if (OperationTraits::less(relaxed, (*_dist)[target])) {
+	    _pred->set(target, it);
+	    _dist->set(target, relaxed);
+	    if (!(*_mask)[target]) {
+	      _mask->set(target, true);
+	      nextProcess.push_back(target);
+	    }
+	  }	  
+	}
+      }
+      _process.swap(nextProcess);
+      return _process.empty();
+    }
+
+    /// \brief Executes the algorithm.
+    ///
+    /// \pre init() must be called and at least one node should be added
+    /// with addSource() before using this function.
+    ///
+    /// This method runs the %BellmanFord algorithm from the root node(s)
+    /// in order to compute the shortest path to each node. The algorithm 
+    /// computes 
+    /// - The shortest path tree.
+    /// - The distance of each node from the root(s).
+    void start() {
+      int num = countNodes(*digraph) - 1;
+      for (int i = 0; i < num; ++i) {
+	if (processNextWeakRound()) break;
+      }
+    }
+
+    /// \brief Executes the algorithm and checks the negative cycles.
+    ///
+    /// \pre init() must be called and at least one node should be added
+    /// with addSource() before using this function. 
+    ///
+    /// This method runs the %BellmanFord algorithm from the root node(s)
+    /// in order to compute the shortest path to each node. The algorithm 
+    /// computes 
+    /// - The shortest path tree.
+    /// - The distance of each node from the root(s).
+    /// 
+    /// \return \c false if there is a negative cycle in the digraph.
+    bool checkedStart() {
+      int num = countNodes(*digraph);
+      for (int i = 0; i < num; ++i) {
+	if (processNextWeakRound()) return true;
+      }
+      return _process.empty();
+    }
+
+    /// \brief Executes the algorithm with path length limit.
+    ///
+    /// \pre init() must be called and at least one node should be added
+    /// with addSource() before using this function.
+    ///
+    /// This method runs the %BellmanFord algorithm from the root
+    /// node(s) in order to compute the shortest path lengths with at
+    /// most \c num arc.
+    ///
+    /// \warning The paths with limited arc number cannot be retrieved
+    /// easily with \ref path() or \ref predArc() functions. If you
+    /// need the shortest path and not just the distance you should store
+    /// after each iteration the \ref predMap() map and manually build
+    /// the path.
+    ///
+    /// The algorithm computes
+    /// - The predecessor arc from each node.
+    /// - The limited distance of each node from the root(s).
+    void limitedStart(int num) {
+      for (int i = 0; i < num; ++i) {
+	if (processNextRound()) break;
+      }
+    }
+    
+    /// \brief Runs %BellmanFord algorithm from node \c s.
+    ///    
+    /// This method runs the %BellmanFord algorithm from a root node \c s
+    /// in order to compute the shortest path to each node. The algorithm 
+    /// computes
+    /// - The shortest path tree.
+    /// - The distance of each node from the root.
+    ///
+    /// \note d.run(s) is just a shortcut of the following code.
+    ///\code
+    ///  d.init();
+    ///  d.addSource(s);
+    ///  d.start();
+    ///\endcode
+    void run(Node s) {
+      init();
+      addSource(s);
+      start();
+    }
+    
+    /// \brief Runs %BellmanFord algorithm with limited path length 
+    /// from node \c s.
+    ///    
+    /// This method runs the %BellmanFord algorithm from a root node \c s
+    /// in order to compute the shortest path with at most \c len arcs 
+    /// to each node. The algorithm computes
+    /// - The shortest path tree.
+    /// - The distance of each node from the root.
+    ///
+    /// \note d.run(s, num) is just a shortcut of the following code.
+    ///\code
+    ///  d.init();
+    ///  d.addSource(s);
+    ///  d.limitedStart(num);
+    ///\endcode
+    void run(Node s, int num) {
+      init();
+      addSource(s);
+      limitedStart(num);
+    }
+    
+    ///@}
+
+    /// \name Query Functions
+    /// The result of the %BellmanFord algorithm can be obtained using these
+    /// functions.\n
+    /// Before the use of these functions,
+    /// either run() or start() must be called.
+    
+    ///@{
+
+    /// \brief Lemon iterator for get the active nodes.
+    ///
+    /// Lemon iterator for get the active nodes. This class provides a
+    /// common style lemon iterator which gives back a subset of the
+    /// nodes. The iterated nodes are active in the algorithm after
+    /// the last phase so these should be checked in the next phase to
+    /// find augmenting arcs from these.
+    class ActiveIt {
+    public:
+
+      /// \brief Constructor.
+      ///
+      /// Constructor for get the nodeset of the variable. 
+      ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
+      {
+        _index = _algorithm->_process.size() - 1;
+      }
+
+      /// \brief Invalid constructor.
+      ///
+      /// Invalid constructor.
+      ActiveIt(Invalid) : _algorithm(0), _index(-1) {}
+
+      /// \brief Conversion to node.
+      ///
+      /// Conversion to node.
+      operator Node() const { 
+        return _index >= 0 ? _algorithm->_process[_index] : INVALID;
+      }
+
+      /// \brief Increment operator.
+      ///
+      /// Increment operator.
+      ActiveIt& operator++() {
+        --_index;
+        return *this; 
+      }
+
+      bool operator==(const ActiveIt& it) const { 
+        return static_cast<Node>(*this) == static_cast<Node>(it); 
+      }
+      bool operator!=(const ActiveIt& it) const { 
+        return static_cast<Node>(*this) != static_cast<Node>(it); 
+      }
+      bool operator<(const ActiveIt& it) const { 
+        return static_cast<Node>(*this) < static_cast<Node>(it); 
+      }
+      
+    private:
+      const BellmanFord* _algorithm;
+      int _index;
+    };
+
+    typedef PredMapPath<Digraph, PredMap> Path;
+
+    /// \brief Gives back the shortest path.
+    ///    
+    /// Gives back the shortest path.
+    /// \pre The \c t should be reachable from the source.
+    Path path(Node t) 
+    {
+      return Path(*digraph, *_pred, t);
+    }
+
+
+    // TODO : implement negative cycle
+//     /// \brief Gives back a negative cycle.
+//     ///    
+//     /// This function gives back a negative cycle.
+//     /// If the algorithm have not found yet negative cycle it will give back
+//     /// an empty path.
+//     Path negativeCycle() {
+//       typename Digraph::template NodeMap<int> state(*digraph, 0);
+//       for (ActiveIt it(*this); it != INVALID; ++it) {
+//         if (state[it] == 0) {
+//           for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {
+//             if (state[t] == 0) {
+//               state[t] = 1;
+//             } else if (state[t] == 2) {
+//               break;
+//             } else {
+//               p.clear();
+//               typename Path::Builder b(p);
+//               b.setStartNode(t);
+//               b.pushFront(predArc(t));
+//               for(Node s = predNode(t); s != t; s = predNode(s)) {
+//                 b.pushFront(predArc(s));
+//               }
+//               b.commit();
+//               return true;
+//             }
+//           }
+//           for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {
+//             if (state[t] == 1) {
+//               state[t] = 2;
+//             } else {
+//               break;
+//             }
+//           }
+//         }
+//       }
+//       return false;
+//     }
+	  
+    /// \brief The distance of a node from the root.
+    ///
+    /// Returns the distance of a node from the root.
+    /// \pre \ref run() must be called before using this function.
+    /// \warning If node \c v in unreachable from the root the return value
+    /// of this funcion is undefined.
+    Value dist(Node v) const { return (*_dist)[v]; }
+
+    /// \brief Returns the 'previous arc' of the shortest path tree.
+    ///
+    /// For a node \c v it returns the 'previous arc' of the shortest path 
+    /// tree, i.e. it returns the last arc of a shortest path from the root 
+    /// to \c v. It is \ref INVALID if \c v is unreachable from the root or 
+    /// if \c v=s. The shortest path tree used here is equal to the shortest 
+    /// path tree used in \ref predNode(). 
+    /// \pre \ref run() must be called before using
+    /// this function.
+    Arc predArc(Node v) const { return (*_pred)[v]; }
+
+    /// \brief Returns the 'previous node' of the shortest path tree.
+    ///
+    /// For a node \c v it returns the 'previous node' of the shortest path 
+    /// tree, i.e. it returns the last but one node from a shortest path from 
+    /// the root to \c /v. It is INVALID if \c v is unreachable from the root 
+    /// or if \c v=s. The shortest path tree used here is equal to the 
+    /// shortest path tree used in \ref predArc().  \pre \ref run() must be 
+    /// called before using this function.
+    Node predNode(Node v) const { 
+      return (*_pred)[v] == INVALID ? INVALID : digraph->source((*_pred)[v]); 
+    }
+    
+    /// \brief Returns a reference to the NodeMap of distances.
+    ///
+    /// Returns a reference to the NodeMap of distances. \pre \ref run() must
+    /// be called before using this function.
+    const DistMap &distMap() const { return *_dist;}
+ 
+    /// \brief Returns a reference to the shortest path tree map.
+    ///
+    /// Returns a reference to the NodeMap of the arcs of the
+    /// shortest path tree.
+    /// \pre \ref run() must be called before using this function.
+    const PredMap &predMap() const { return *_pred; }
+ 
+    /// \brief Checks if a node is reachable from the root.
+    ///
+    /// Returns \c true if \c v is reachable from the root.
+    /// \pre \ref run() must be called before using this function.
+    ///
+    bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); }
+    
+    ///@}
+  };
+ 
+  /// \brief Default traits class of BellmanFord function.
+  ///
+  /// Default traits class of BellmanFord function.
+  /// \param _Digraph Digraph type.
+  /// \param _LengthMap Type of length map.
+  template <typename _Digraph, typename _LengthMap>
+  struct BellmanFordWizardDefaultTraits {
+    /// \brief The digraph type the algorithm runs on. 
+    typedef _Digraph Digraph;
+
+    /// \brief The type of the map that stores the arc lengths.
+    ///
+    /// The type of the map that stores the arc lengths.
+    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
+    typedef _LengthMap LengthMap;
+
+    /// \brief The value type of the length map.
+    typedef typename _LengthMap::Value Value;
+
+    /// \brief Operation traits for Bellman-Ford algorithm.
+    ///
+    /// It defines the infinity type on the given Value type
+    /// and the used operation.
+    /// \see BellmanFordDefaultOperationTraits
+    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
+
+    /// \brief The type of the map that stores the last
+    /// arcs of the shortest paths.
+    /// 
+    /// The type of the map that stores the last
+    /// arcs of the shortest paths.
+    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
+    typedef NullMap <typename _Digraph::Node,typename _Digraph::Arc> PredMap;
+
+    /// \brief Instantiates a PredMap.
+    /// 
+    /// This function instantiates a \ref PredMap. 
+    static PredMap *createPredMap(const _Digraph &) {
+      return new PredMap();
+    }
+    /// \brief The type of the map that stores the dists of the nodes.
+    ///
+    /// The type of the map that stores the dists of the nodes.
+    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
+    typedef NullMap<typename Digraph::Node, Value> DistMap;
+    /// \brief Instantiates a DistMap.
+    ///
+    /// This function instantiates a \ref DistMap. 
+    static DistMap *createDistMap(const _Digraph &) {
+      return new DistMap();
+    }
+  };
+  
+  /// \brief Default traits used by \ref BellmanFordWizard
+  ///
+  /// To make it easier to use BellmanFord algorithm
+  /// we have created a wizard class.
+  /// This \ref BellmanFordWizard class needs default traits,
+  /// as well as the \ref BellmanFord class.
+  /// The \ref BellmanFordWizardBase is a class to be the default traits of the
+  /// \ref BellmanFordWizard class.
+  /// \todo More named parameters are required...
+  template<class _Digraph,class _LengthMap>
+  class BellmanFordWizardBase 
+    : public BellmanFordWizardDefaultTraits<_Digraph,_LengthMap> {
+
+    typedef BellmanFordWizardDefaultTraits<_Digraph,_LengthMap> Base;
+  protected:
+    /// Type of the nodes in the digraph.
+    typedef typename Base::Digraph::Node Node;
+
+    /// Pointer to the underlying digraph.
+    void *_graph;
+    /// Pointer to the length map
+    void *_length;
+    ///Pointer to the map of predecessors arcs.
+    void *_pred;
+    ///Pointer to the map of distances.
+    void *_dist;
+    ///Pointer to the source node.
+    Node _source;
+
+    public:
+    /// Constructor.
+    
+    /// This constructor does not require parameters, therefore it initiates
+    /// all of the attributes to default values (0, INVALID).
+    BellmanFordWizardBase() : _graph(0), _length(0), _pred(0),
+			   _dist(0), _source(INVALID) {}
+
+    /// Constructor.
+    
+    /// This constructor requires some parameters,
+    /// listed in the parameters list.
+    /// Others are initiated to 0.
+    /// \param digraph is the initial value of  \ref _graph
+    /// \param length is the initial value of  \ref _length
+    /// \param source is the initial value of  \ref _source
+    BellmanFordWizardBase(const _Digraph& digraph, 
+			  const _LengthMap& length, 
+			  Node source = INVALID) :
+      _graph(reinterpret_cast<void*>(const_cast<_Digraph*>(&digraph))), 
+      _length(reinterpret_cast<void*>(const_cast<_LengthMap*>(&length))), 
+      _pred(0), _dist(0), _source(source) {}
+
+  };
+  
+  /// A class to make the usage of BellmanFord algorithm easier
+
+  /// This class is created to make it easier to use BellmanFord algorithm.
+  /// It uses the functions and features of the plain \ref BellmanFord,
+  /// but it is much simpler to use it.
+  ///
+  /// Simplicity means that the way to change the types defined
+  /// in the traits class is based on functions that returns the new class
+  /// and not on templatable built-in classes.
+  /// When using the plain \ref BellmanFord
+  /// the new class with the modified type comes from
+  /// the original class by using the ::
+  /// operator. In the case of \ref BellmanFordWizard only
+  /// a function have to be called and it will
+  /// return the needed class.
+  ///
+  /// It does not have own \ref run method. When its \ref run method is called
+  /// it initiates a plain \ref BellmanFord class, and calls the \ref 
+  /// BellmanFord::run method of it.
+  template<class _Traits>
+  class BellmanFordWizard : public _Traits {
+    typedef _Traits Base;
+
+    ///The type of the underlying digraph.
+    typedef typename _Traits::Digraph Digraph;
+
+    typedef typename Digraph::Node Node;
+    typedef typename Digraph::NodeIt NodeIt;
+    typedef typename Digraph::Arc Arc;
+    typedef typename Digraph::OutArcIt ArcIt;
+    
+    ///The type of the map that stores the arc lengths.
+    typedef typename _Traits::LengthMap LengthMap;
+
+    ///The type of the length of the arcs.
+    typedef typename LengthMap::Value Value;
+
+    ///\brief The type of the map that stores the last
+    ///arcs of the shortest paths.
+    typedef typename _Traits::PredMap PredMap;
+
+    ///The type of the map that stores the dists of the nodes.
+    typedef typename _Traits::DistMap DistMap;
+
+  public:
+    /// Constructor.
+    BellmanFordWizard() : _Traits() {}
+
+    /// \brief Constructor that requires parameters.
+    ///
+    /// Constructor that requires parameters.
+    /// These parameters will be the default values for the traits class.
+    BellmanFordWizard(const Digraph& digraph, const LengthMap& length, 
+		      Node src = INVALID) 
+      : _Traits(digraph, length, src) {}
+
+    /// \brief Copy constructor
+    BellmanFordWizard(const _Traits &b) : _Traits(b) {}
+
+    ~BellmanFordWizard() {}
+
+    /// \brief Runs BellmanFord algorithm from a given node.
+    ///    
+    /// Runs BellmanFord algorithm from a given node.
+    /// The node can be given by the \ref source function.
+    void run() {
+      LEMON_ASSERT(Base::_source != INVALID, "Source node is not given");
+      BellmanFord<Digraph,LengthMap,_Traits> 
+	bf(*reinterpret_cast<const Digraph*>(Base::_graph), 
+           *reinterpret_cast<const LengthMap*>(Base::_length));
+      if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
+      if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
+      bf.run(Base::_source);
+    }
+
+    /// \brief Runs BellmanFord algorithm from the given node.
+    ///
+    /// Runs BellmanFord algorithm from the given node.
+    /// \param src is the given source.
+    void run(Node src) {
+      Base::_source = src;
+      run();
+    }
+
+    template<class T>
+    struct DefPredMapBase : public Base {
+      typedef T PredMap;
+      static PredMap *createPredMap(const Digraph &) { return 0; };
+      DefPredMapBase(const _Traits &b) : _Traits(b) {}
+    };
+    
+    ///\brief \ref named-templ-param "Named parameter"
+    ///function for setting PredMap type
+    ///
+    /// \ref named-templ-param "Named parameter"
+    ///function for setting PredMap type
+    ///
+    template<class T>
+    BellmanFordWizard<DefPredMapBase<T> > predMap(const T &t) 
+    {
+      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
+      return BellmanFordWizard<DefPredMapBase<T> >(*this);
+    }
+    
+    template<class T>
+    struct DefDistMapBase : public Base {
+      typedef T DistMap;
+      static DistMap *createDistMap(const Digraph &) { return 0; };
+      DefDistMapBase(const _Traits &b) : _Traits(b) {}
+    };
+    
+    ///\brief \ref named-templ-param "Named parameter"
+    ///function for setting DistMap type
+    ///
+    /// \ref named-templ-param "Named parameter"
+    ///function for setting DistMap type
+    ///
+    template<class T>
+    BellmanFordWizard<DefDistMapBase<T> > distMap(const T &t) {
+      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
+      return BellmanFordWizard<DefDistMapBase<T> >(*this);
+    }
+
+    template<class T>
+    struct DefOperationTraitsBase : public Base {
+      typedef T OperationTraits;
+      DefOperationTraitsBase(const _Traits &b) : _Traits(b) {}
+    };
+    
+    ///\brief \ref named-templ-param "Named parameter"
+    ///function for setting OperationTraits type
+    ///
+    /// \ref named-templ-param "Named parameter"
+    ///function for setting OperationTraits type
+    ///
+    template<class T>
+    BellmanFordWizard<DefOperationTraitsBase<T> > distMap() {
+      return BellmanFordWizard<DefDistMapBase<T> >(*this);
+    }
+    
+    /// \brief Sets the source node, from which the BellmanFord algorithm runs.
+    ///
+    /// Sets the source node, from which the BellmanFord algorithm runs.
+    /// \param src is the source node.
+    BellmanFordWizard<_Traits>& source(Node src) {
+      Base::_source = src;
+      return *this;
+    }
+    
+  };
+  
+  /// \brief Function type interface for BellmanFord algorithm.
+  ///
+  /// \ingroup shortest_path
+  /// Function type interface for BellmanFord algorithm.
+  ///
+  /// This function also has several \ref named-templ-func-param 
+  /// "named parameters", they are declared as the members of class 
+  /// \ref BellmanFordWizard.
+  /// The following
+  /// example shows how to use these parameters.
+  ///\code
+  /// bellmanford(g,length,source).predMap(preds).run();
+  ///\endcode
+  /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()"
+  /// to the end of the parameter list.
+  /// \sa BellmanFordWizard
+  /// \sa BellmanFord
+  template<class _Digraph, class _LengthMap>
+  BellmanFordWizard<BellmanFordWizardBase<_Digraph,_LengthMap> >
+  bellmanFord(const _Digraph& digraph,
+	      const _LengthMap& length, 
+	      typename _Digraph::Node source = INVALID) {
+    return BellmanFordWizard<BellmanFordWizardBase<_Digraph,_LengthMap> >
+      (digraph, length, source);
+  }
+
+} //END OF NAMESPACE LEMON
+
+#endif
+
Index: lemon/bits/edge_set_extender.h
===================================================================
--- lemon/bits/edge_set_extender.h	(revision 685)
+++ lemon/bits/edge_set_extender.h	(revision 617)
@@ -538,5 +538,5 @@
 
     public:
-      explicit ArcMap(const Graph& _g) 
+      ArcMap(const Graph& _g) 
 	: Parent(_g) {}
       ArcMap(const Graph& _g, const _Value& _v) 
@@ -562,5 +562,5 @@
 
     public:
-      explicit EdgeMap(const Graph& _g) 
+      EdgeMap(const Graph& _g) 
 	: Parent(_g) {}
 
Index: lemon/bits/graph_extender.h
===================================================================
--- lemon/bits/graph_extender.h	(revision 685)
+++ lemon/bits/graph_extender.h	(revision 617)
@@ -605,5 +605,5 @@
 
     public:
-      explicit NodeMap(const Graph& graph)
+      NodeMap(const Graph& graph)
         : Parent(graph) {}
       NodeMap(const Graph& graph, const _Value& value)
@@ -629,5 +629,5 @@
 
     public:
-      explicit ArcMap(const Graph& graph)
+      ArcMap(const Graph& graph)
         : Parent(graph) {}
       ArcMap(const Graph& graph, const _Value& value)
@@ -653,5 +653,5 @@
 
     public:
-      explicit EdgeMap(const Graph& graph)
+      EdgeMap(const Graph& graph)
         : Parent(graph) {}
 
Index: lemon/circulation.h
===================================================================
--- lemon/circulation.h	(revision 689)
+++ lemon/circulation.h	(revision 641)
@@ -451,9 +451,8 @@
     }
 
-    /// \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;
@@ -462,8 +461,7 @@
     /// \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;
     }
 
Index: lemon/maps.h
===================================================================
--- lemon/maps.h	(revision 695)
+++ lemon/maps.h	(revision 617)
@@ -23,5 +23,4 @@
 #include <functional>
 #include <vector>
-#include <map>
 
 #include <lemon/core.h>
@@ -30,4 +29,6 @@
 ///\ingroup maps
 ///\brief Miscellaneous property maps
+
+#include <map>
 
 namespace lemon {
@@ -1818,5 +1819,5 @@
   ///
   /// 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
@@ -1902,11 +1903,10 @@
 
   /// This class provides simple invertable graph maps.
-  /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
-  /// and if a key is set to a new value, then stores it in the inverse map.
+  /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap"
+  /// and if a key is set to a new value then store it
+  /// in the inverse map.
+  ///
   /// 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
-  /// the subscript operator.
   ///
   /// \tparam GR The graph type.
@@ -1924,5 +1924,5 @@
       template Map<V>::Type Map;
 
-    typedef std::multimap<V, K> Container;
+    typedef std::map<V, K> Container;
     Container _inv_map;
 
@@ -1949,6 +1949,4 @@
     /// 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 ValueIterator
       : public std::iterator<std::forward_iterator_tag, Value> {
@@ -2003,13 +2001,9 @@
     void set(const Key& key, const Value& val) {
       Value oldval = Map::operator[](key);
-      typename Container::iterator it;
-      for (it = _inv_map.equal_range(oldval).first;
-           it != _inv_map.equal_range(oldval).second; ++it) {
-        if (it->second == key) {
-          _inv_map.erase(it);
-          break;
-        }
+      typename Container::iterator it = _inv_map.find(oldval);
+      if (it != _inv_map.end() && it->second == key) {
+        _inv_map.erase(it);
       }
-      _inv_map.insert(std::make_pair(val, key));
+      _inv_map.insert(make_pair(val, key));
       Map::set(key, val);
     }
@@ -2023,12 +2017,9 @@
     }
 
-    /// \brief Gives back an item by its value.
-    ///
-    /// This function gives back an item that is assigned to
-    /// the given value or \c INVALID if no such item exists.
-    /// If there are more items with the same associated value,
-    /// only one of them is returned.
-    Key operator()(const Value& val) const {
-      typename Container::const_iterator it = _inv_map.find(val);
+    /// \brief Gives back the item by its value.
+    ///
+    /// Gives back the item by its value.
+    Key operator()(const Value& key) const {
+      typename Container::const_iterator it = _inv_map.find(key);
       return it != _inv_map.end() ? it->second : INVALID;
     }
@@ -2042,11 +2033,7 @@
     virtual void erase(const Key& key) {
       Value val = Map::operator[](key);
-      typename Container::iterator it;
-      for (it = _inv_map.equal_range(val).first;
-           it != _inv_map.equal_range(val).second; ++it) {
-        if (it->second == key) {
-          _inv_map.erase(it);
-          break;
-        }
+      typename Container::iterator it = _inv_map.find(val);
+      if (it != _inv_map.end() && it->second == key) {
+        _inv_map.erase(it);
       }
       Map::erase(key);
@@ -2060,11 +2047,7 @@
       for (int i = 0; i < int(keys.size()); ++i) {
         Value val = Map::operator[](keys[i]);
-        typename Container::iterator it;
-        for (it = _inv_map.equal_range(val).first;
-             it != _inv_map.equal_range(val).second; ++it) {
-          if (it->second == keys[i]) {
-            _inv_map.erase(it);
-            break;
-          }
+        typename Container::iterator it = _inv_map.find(val);
+        if (it != _inv_map.end() && it->second == keys[i]) {
+          _inv_map.erase(it);
         }
       }
@@ -2102,7 +2085,6 @@
       /// \brief Subscript operator.
       ///
-      /// Subscript operator. It gives back an item
-      /// that is assigned to the given value or \c INVALID
-      /// if no such item exists.
+      /// Subscript operator. It gives back the item
+      /// that was last assigned to the given value.
       Value operator[](const Key& key) const {
         return _inverted(key);
@@ -2273,5 +2255,5 @@
 
     /// \brief Gives back the item belonging to a \e RangeId
-    ///
+    /// 
     /// Gives back the item belonging to a \e RangeId.
     Item operator()(int id) const {
@@ -2330,901 +2312,4 @@
   };
 
-  /// \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.
-  ///
-  /// 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 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 an
-  /// comparable value for graph items (\c Node, \c Arc or \c Edge).
-  /// For each value it is possible to iterate on the keys mapped to
-  /// the value.
-  ///
-  /// The map stores for each value a linked list with
-  /// the items which mapped to the value, and the values are stored
-  /// in balanced binary tree. The values of the map can be accessed
-  /// with stl compatible forward iterator.
-  ///
-  /// 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 ValueIterator
-      : public std::iterator<std::forward_iterator_tag, Value> {
-      friend class IterableValueMap;
-    private:
-      ValueIterator(typename std::map<Value, Key>::const_iterator _it)
-        : it(_it) {}
-    public:
-
-      ValueIterator() {}
-
-      ValueIterator& operator++() { ++it; return *this; }
-      ValueIterator operator++(int) {
-        ValueIterator tmp(*this);
-        operator++();
-        return tmp;
-      }
-
-      const Value& operator*() const { return it->first; }
-      const Value* operator->() const { return &(it->first); }
-
-      bool operator==(ValueIterator jt) const { return it == jt.it; }
-      bool operator!=(ValueIterator jt) const { return it != jt.it; }
-
-    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.
-    ValueIterator beginValue() const {
-      return ValueIterator(_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.
-    ValueIterator endValue() const {
-      return ValueIterator(_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;
-  };
-
   /// \brief Map of the source nodes of arcs in a digraph.
   ///
@@ -3396,5 +2481,5 @@
   /// 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
@@ -3412,5 +2497,5 @@
 
   public:
-
+    
     /// The graph type of InDegMap
     typedef GR Graph;
@@ -3526,5 +2611,5 @@
   /// 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
Index: lemon/preflow.h
===================================================================
--- lemon/preflow.h	(revision 689)
+++ lemon/preflow.h	(revision 641)
@@ -98,5 +98,5 @@
   /// "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$.
@@ -372,9 +372,8 @@
     }
 
-    /// \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;
@@ -383,8 +382,7 @@
     /// \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;
     }
 
Index: test/circulation_test.cc
===================================================================
--- test/circulation_test.cc	(revision 689)
+++ test/circulation_test.cc	(revision 611)
@@ -88,9 +88,4 @@
     .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();
Index: test/maps_test.cc
===================================================================
--- test/maps_test.cc	(revision 695)
+++ test/maps_test.cc	(revision 507)
@@ -23,5 +23,4 @@
 #include <lemon/concepts/maps.h>
 #include <lemon/maps.h>
-#include <lemon/smart_graph.h>
 
 #include "test_tools.h"
@@ -351,225 +350,4 @@
   }
 
-  // CrossRefMap
-  {
-    typedef SmartDigraph Graph;
-    DIGRAPH_TYPEDEFS(Graph);
-
-    checkConcept<ReadWriteMap<Node, int>,
-                 CrossRefMap<Graph, Node, int> >();
-    
-    Graph gr;
-    typedef CrossRefMap<Graph, Node, char> CRMap;
-    typedef CRMap::ValueIterator ValueIt;
-    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');
-    map.set(n2, 'A');
-    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");
-
-    ValueIt it = map.beginValue();
-    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
-          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::ValueIterator vit = map1.beginValue();
-         vit != map1.endValue(); ++vit) {
-      check(map1[static_cast<Item>(Ivm::ItemIt(map1, *vit))] == *vit,
-            "Wrong ValueIterator");
-    }
-
-    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;
 }
Index: test/preflow_test.cc
===================================================================
--- test/preflow_test.cc	(revision 689)
+++ test/preflow_test.cc	(revision 585)
@@ -95,9 +95,4 @@
   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
Index: tools/lemon-0.x-to-1.x.sh
===================================================================
--- tools/lemon-0.x-to-1.x.sh	(revision 691)
+++ tools/lemon-0.x-to-1.x.sh	(revision 574)
@@ -36,8 +36,8 @@
         -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,9 +69,4 @@
         -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"\
