LEMON/LEMON-official Changeset - r789:8e68671af789

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r789:8e68671af789

« 780:abf31e
« 788:10c9c3

790:94ef0a »

r789:8e68671af789

Wed, 30 Sep 2009 08:41:06

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Merge #311

0 29 7

merge default

1 file changed:

lemon/bellman_ford.h

1100

lemon/binom_heap.h

445

lemon/fourary_heap.h

342

lemon/kary_heap.h

352

doc/groups.dox

100

lemon/Makefile.am

lemon/bfs.h

lemon/bin_heap.h

110

lemon/bits/map_extender.h

lemon/bucket_heap.h

166

139

lemon/circulation.h

lemon/concepts/heap.h

lemon/concepts/maps.h

lemon/dfs.h

lemon/dijkstra.h

lemon/dim2.h

lemon/fib_heap.h

125

118

lemon/gomory_hu.h

lemon/maps.h

1023

lemon/min_cost_arborescence.h

lemon/network_simplex.h

Changeset was too big and was cut off... Show full diff

↑ Collapse diff ↑

lemon/bellman_ford.h

Show inline comments

 		/* -*- 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_BELLMAN_FORD_H
 		#define LEMON_BELLMAN_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 <lemon/path.h>
 		#include <limits>
 		namespace lemon {
 		  /// \brief Default OperationTraits for the BellmanFord algorithm class.
 		  ///
 		  /// This operation traits class defines all computational operations
 		  /// and constants that are used in the Bellman-Ford algorithm.
 		  /// The default implementation is based on the \c numeric_limits class.
 		  /// If the numeric type does not have infinity value, then the maximum
 		  /// value is used as extremal infinity value.
 		  template <
 		    typename V,
 		    bool has_inf = std::numeric_limits<V>::has_infinity>
 		  struct BellmanFordDefaultOperationTraits {
 		    /// \e
 		    typedef V Value;
 		    /// \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 \c true only if the first value is less than
 		    /// the second.
 		    static bool less(const Value& left, const Value& right) {
 		      return left < right;
+		    }
 		  };
 		  template <typename V>
 		  struct BellmanFordDefaultOperationTraits<V, false> {
 		    typedef V Value;
 		    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 GR The type of the digraph.
 		  /// \param LEN The type of the length map.
 		  template<typename GR, typename LEN>
 		  struct BellmanFordDefaultTraits {
 		    /// The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    /// \brief The type of the map that stores the arc lengths.
 		    ///
 		    /// The type of the map that stores the arc lengths.
 		    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef LEN LengthMap;
 		    /// The type of the arc lengths.
 		    typedef typename LEN::Value Value;
 		    /// \brief Operation traits for Bellman-Ford algorithm.
 		    ///
 		    /// It defines the used operations and the infinity value for the
 		    /// given \c Value type.
 		    /// \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 conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
 		    /// \brief Instantiates a \c PredMap.
 		    ///
 		    /// This function instantiates a \ref PredMap.
 		    /// \param g is the digraph to which we would like to define the
 		    /// \ref PredMap.
 		    static PredMap *createPredMap(const GR& g) {
 		      return new PredMap(g);
+		    }
 		    /// \brief The type of the map that stores the distances of the nodes.
 		    ///
 		    /// The type of the map that stores the distances of the nodes.
 		    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename GR::template NodeMap<typename LEN::Value> DistMap;
 		    /// \brief Instantiates a \c DistMap.
 		    ///
 		    /// This function instantiates a \ref DistMap.
 		    /// \param g is the digraph to which we would like to define the
 		    /// \ref DistMap.
 		    static DistMap *createDistMap(const GR& g) {
 		      return new DistMap(g);
+		    }
 		  };
 		  /// \brief %BellmanFord algorithm class.
 		  ///
 		  /// \ingroup shortest_path
 		  /// This class provides an efficient implementation of the Bellman-Ford
 		  /// algorithm. The maximum time complexity of the algorithm is
 		  /// <tt>O(ne)</tt>.
 		  ///
 		  /// The Bellman-Ford algorithm solves the single-source shortest path
 		  /// problem when the arcs can have negative lengths, but the digraph
 		  /// should not contain directed cycles with negative total length.
 		  /// If all arc costs are non-negative, consider to use the Dijkstra
 		  /// algorithm instead, since it is more efficient.
 		  ///
 		  /// 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 type of the length values is determined by the
 		  /// \ref concepts::ReadMap::Value "Value" type of the length map.
 		  ///
 		  /// There is also a \ref bellmanFord() "function-type interface" for the
 		  /// Bellman-Ford algorithm, which is convenient in the simplier cases and
 		  /// it can be used easier.
 		  ///
 		  /// \tparam GR The type of the digraph the algorithm runs on.
 		  /// The default type is \ref ListDigraph.
 		  /// \tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies
 		  /// the lengths of the arcs. The default map type is
 		  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		#ifdef DOXYGEN
 		  template <typename GR, typename LEN, typename TR>
 		#else
 		  template <typename GR=ListDigraph,
 		            typename LEN=typename GR::template ArcMap<int>,
 		            typename TR=BellmanFordDefaultTraits<GR,LEN> >
 		#endif
 		  class BellmanFord {
 		  public:
 		    ///The type of the underlying digraph.
 		    typedef typename TR::Digraph Digraph;
 		    /// \brief The type of the arc lengths.
 		    typedef typename TR::LengthMap::Value Value;
 		    /// \brief The type of the map that stores the arc lengths.
 		    typedef typename TR::LengthMap LengthMap;
 		    /// \brief The type of the map that stores the last
 		    /// 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;
 		    /// The type of the paths.
 		    typedef PredMapPath<Digraph, PredMap> Path;
 		    ///\brief The \ref BellmanFordDefaultOperationTraits
 		    /// "operation traits class" of the algorithm.
 		    typedef typename TR::OperationTraits OperationTraits;
 		    ///The \ref BellmanFordDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    // Pointer to the underlying digraph.
 		    const Digraph *_gr;
 		    // Pointer to the length map
 		    const LengthMap *_length;
 		    // Pointer to the map of predecessors arcs.
 		    PredMap *_pred;
 		    // Indicates if _pred is locally allocated (true) or not.
 		    bool _local_pred;
 		    // Pointer to the map of distances.
 		    DistMap *_dist;
 		    // Indicates if _dist is locally allocated (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(*_gr);
+		      }
 		      if(!_dist) {
 			_local_dist = true;
 			_dist = Traits::createDistMap(*_gr);
+		      }
 		      _mask = new MaskMap(*_gr, false);
+		    }
 		  public :
 		    typedef BellmanFord Create;
 		    /// \name Named Template Parameters
 		    ///@{
 		    template <class T>
 		    struct SetPredMapTraits : 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
 		    /// \c PredMap type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting
 		    /// \c PredMap type.
 		    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetPredMap
 		      : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > {
 		      typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetDistMapTraits : 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
 		    /// \c DistMap type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting
 		    /// \c DistMap type.
 		    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetDistMap
 		      : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > {
 		      typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetOperationTraitsTraits : public Traits {
 		      typedef T OperationTraits;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c OperationTraits type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting
 		    /// \c OperationTraits type.
 		    /// For more information see \ref BellmanFordDefaultOperationTraits.
 		    template <class T>
 		    struct SetOperationTraits
 		      : public BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> > {
 		      typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> >
 		      Create;
 		    };
 		    ///@}
 		  protected:
 		    BellmanFord() {}
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    /// \param g The digraph the algorithm runs on.
 		    /// \param length The length map used by the algorithm.
 		    BellmanFord(const Digraph& g, const LengthMap& length) :
 		      _gr(&g), _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 <tt>(*this)</tt>
 		    BellmanFord &lengthMap(const LengthMap &map) {
 		      _length = &map;
 		      return *this;
+		    }
 		    /// \brief Sets the map that stores the predecessor arcs.
 		    ///
 		    /// Sets the map that stores the predecessor arcs.
 		    /// If you don't use this function before calling \ref run()
 		    /// or \ref init(), an instance will be allocated automatically.
 		    /// The destructor deallocates this automatically allocated map,
 		    /// of course.
 		    /// \return <tt>(*this)</tt>
 		    BellmanFord &predMap(PredMap &map) {
 		      if(_local_pred) {
 			delete _pred;
 			_local_pred=false;
+		      }
 		      _pred = &map;
 		      return *this;
+		    }
 		    /// \brief Sets the map that stores the distances of the nodes.
 		    ///
 		    /// Sets the map that stores the distances of the nodes calculated
 		    /// by the algorithm.
 		    /// If you don't use this function before calling \ref run()
 		    /// or \ref init(), an instance will be allocated automatically.
 		    /// The destructor deallocates this automatically allocated map,
 		    /// of course.
 		    /// \return <tt>(*this)</tt>
 		    BellmanFord &distMap(DistMap &map) {
 		      if(_local_dist) {
 			delete _dist;
 			_local_dist=false;
+		      }
 		      _dist = &map;
 		      return *this;
+		    }
 		    /// \name Execution Control
 		    /// The simplest way to execute the Bellman-Ford algorithm is to use
 		    /// one of the member functions called \ref 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 \ref addSource(). Finally the actual path computation can be
 		    /// performed with \ref start(), \ref checkedStart() or
 		    /// \ref limitedStart().
 		    ///@{
 		    /// \brief Initializes the internal data structures.
 		    ///
 		    /// Initializes the internal data structures. The optional parameter
 		    /// is the initial distance of each node.
 		    void init(const Value value = OperationTraits::infinity()) {
 		      create_maps();
 		      for (NodeIt it(*_gr); it != INVALID; ++it) {
 			_pred->set(it, INVALID);
 			_dist->set(it, value);
+		      }
 		      _process.clear();
 		      if (OperationTraits::less(value, OperationTraits::infinity())) {
 			for (NodeIt it(*_gr); it != INVALID; ++it) {
 			  _process.push_back(it);
 			  _mask->set(it, true);
+			}
+		      }
+		    }
 		    /// \brief Adds a new source node.
 		    ///
 		    /// This function adds a new source node. The optional second parameter
 		    /// is the initial distance of the node.
 		    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 the paths of at most \c k arcs, then this function
 		    /// will calculate the distances exactly for the paths of at most
 		    /// <tt>k+1</tt> arcs. Performing \c k iterations using this function
 		    /// calculates the shortest path distances exactly for the paths
 		    /// consisting of at most \c k arcs.
 		    ///
 		    /// \warning The paths with limited arc number cannot be retrieved
 		    /// easily with \ref path() or \ref predArc() functions. If you also
 		    /// need the shortest paths and not only the distances, you should
 		    /// store the \ref predMap() "predecessor map" after each iteration
 		    /// and build the path manually.
 		    ///
 		    /// \return \c true when the algorithm have not found more shorter
 		    /// paths.
 		    ///
 		    /// \see ActiveIt
 		    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(*_gr, _process[i]); it != INVALID; ++it) {
 			  Node target = _gr->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 the paths of at most \c k arcs, then this function
 		    /// will calculate the distances at least for the paths of at most
 		    /// <tt>k+1</tt> arcs.
 		    /// This function does not make it possible to calculate the shortest
 		    /// path distances exactly for paths consisting of at most \c k arcs,
 		    /// this is why it is called weak round.
 		    ///
 		    /// \return \c true when the algorithm have not found more shorter
 		    /// paths.
 		    ///
 		    /// \see ActiveIt
 		    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(*_gr, _process[i]); it != INVALID; ++it) {
 			  Node target = _gr->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.
 		    ///
 		    /// Executes the algorithm.
 		    ///
 		    /// This method runs the Bellman-Ford algorithm from the root node(s)
 		    /// in order to compute the shortest path to each node.
 		    ///
 		    /// The algorithm computes
 		    /// - the shortest path tree (forest),
 		    /// - the distance of each node from the root(s).
 		    ///
 		    /// \pre init() must be called and at least one root node should be
 		    /// added with addSource() before using this function.
 		    void start() {
 		      int num = countNodes(*_gr) - 1;
 		      for (int i = 0; i < num; ++i) {
 			if (processNextWeakRound()) break;
+		      }
+		    }
 		    /// \brief Executes the algorithm and checks the negative cycles.
 		    ///
 		    /// Executes the algorithm and checks the negative cycles.
 		    ///
 		    /// This method runs the Bellman-Ford algorithm from the root node(s)
 		    /// in order to compute the shortest path to each node and also checks
 		    /// if the digraph contains cycles with negative total length.
 		    ///
 		    /// The algorithm computes
 		    /// - the shortest path tree (forest),
 		    /// - the distance of each node from the root(s).
 		    ///
 		    /// \return \c false if there is a negative cycle in the digraph.
 		    ///
 		    /// \pre init() must be called and at least one root node should be
 		    /// added with addSource() before using this function.
 		    bool checkedStart() {
 		      int num = countNodes(*_gr);
 		      for (int i = 0; i < num; ++i) {
 			if (processNextWeakRound()) return true;
+		      }
 		      return _process.empty();
+		    }
 		    /// \brief Executes the algorithm with arc number limit.
 		    ///
 		    /// Executes the algorithm with arc number limit.
 		    ///
 		    /// This method runs the Bellman-Ford algorithm from the root node(s)
 		    /// in order to compute the shortest path distance for each node
 		    /// using only the paths consisting of at most \c num arcs.
 		    ///
 		    /// The algorithm computes
 		    /// - the limited distance of each node from the root(s),
 		    /// - the predecessor arc for each node.
 		    ///
 		    /// \warning The paths with limited arc number cannot be retrieved
 		    /// easily with \ref path() or \ref predArc() functions. If you also
 		    /// need the shortest paths and not only the distances, you should
 		    /// store the \ref predMap() "predecessor map" after each iteration
 		    /// and build the path manually.
 		    ///
 		    /// \pre init() must be called and at least one root node should be
 		    /// added with addSource() before using this function.
 		    void limitedStart(int num) {
 		      for (int i = 0; i < num; ++i) {
 			if (processNextRound()) break;
+		      }
+		    }
 		    /// \brief Runs the algorithm from the given root node.
 		    ///
 		    /// This method runs the Bellman-Ford algorithm from the given root
 		    /// node \c s in order to compute the shortest path to each node.
 		    ///
 		    /// The algorithm computes
 		    /// - the shortest path tree (forest),
 		    /// - the distance of each node from the root(s).
 		    ///
 		    /// \note bf.run(s) is just a shortcut of the following code.
 		    /// \code
 		    ///   bf.init();
 		    ///   bf.addSource(s);
 		    ///   bf.start();
 		    /// \endcode
 		    void run(Node s) {
 		      init();
 		      addSource(s);
 		      start();
+		    }
 		    /// \brief Runs the algorithm from the given root node with arc
 		    /// number limit.
 		    ///
 		    /// This method runs the Bellman-Ford algorithm from the given root
 		    /// node \c s in order to compute the shortest path distance for each
 		    /// node using only the paths consisting of at most \c num arcs.
 		    ///
 		    /// The algorithm computes
 		    /// - the limited distance of each node from the root(s),
 		    /// - the predecessor arc for each node.
 		    ///
 		    /// \warning The paths with limited arc number cannot be retrieved
 		    /// easily with \ref path() or \ref predArc() functions. If you also
 		    /// need the shortest paths and not only the distances, you should
 		    /// store the \ref predMap() "predecessor map" after each iteration
 		    /// and build the path manually.
 		    ///
 		    /// \note bf.run(s, num) is just a shortcut of the following code.
 		    /// \code
 		    ///   bf.init();
 		    ///   bf.addSource(s);
 		    ///   bf.limitedStart(num);
 		    /// \endcode
 		    void run(Node s, int num) {
 		      init();
 		      addSource(s);
 		      limitedStart(num);
+		    }
 		    ///@}
 		    /// \brief LEMON iterator for getting the active nodes.
 		    ///
 		    /// This class provides a common style LEMON iterator that traverses
 		    /// the active nodes of the Bellman-Ford algorithm after the last
 		    /// phase. These nodes should be checked in the next phase to
 		    /// find augmenting arcs outgoing from them.
 		    class ActiveIt {
 		    public:
 		      /// \brief Constructor.
 		      ///
 		      /// Constructor for getting the active nodes of the given BellmanFord
 		      /// instance.
 		      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 \c Node.
 		      ///
 		      /// Conversion to \c 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;
 		    };
 		    /// \name Query Functions
 		    /// The result of the Bellman-Ford algorithm can be obtained using these
 		    /// functions.\n
 		    /// Either \ref run() or \ref init() should be called before using them.
 		    ///@{
 		    /// \brief The shortest path to the given node.
 		    ///
 		    /// Gives back the shortest path to the given node from the root(s).
 		    ///
 		    /// \warning \c t should be reached from the root(s).
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    Path path(Node t) const
+		    {
 		      return Path(*_gr, *_pred, t);
+		    }
 		    /// \brief The distance of the given node from the root(s).
 		    ///
 		    /// Returns the distance of the given node from the root(s).
 		    ///
 		    /// \warning If node \c v is not reached from the root(s), then
 		    /// the return value of this function is undefined.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    Value dist(Node v) const { return (*_dist)[v]; }
 		    /// \brief Returns the 'previous arc' of the shortest path tree for
 		    /// the given node.
 		    ///
 		    /// This function returns the 'previous arc' of the shortest path
 		    /// tree for node \c v, i.e. it returns the last arc of a
 		    /// shortest path from a root to \c v. It is \c INVALID if \c v
 		    /// is not reached from the root(s) or if \c v is a root.
 		    ///
 		    /// The shortest path tree used here is equal to the shortest path
 		    /// tree used in \ref predNode() and \predMap().
 		    ///
 		    /// \pre Either \ref run() or \ref init() 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
 		    /// the given node.
 		    ///
 		    /// This function returns the 'previous node' of the shortest path
 		    /// tree for 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 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 \predMap().
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    Node predNode(Node v) const {
 		      return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]);
+		    }
 		    /// \brief Returns a const reference to the node map that stores the
 		    /// distances of the nodes.
 		    ///
 		    /// Returns a const reference to the node map that stores the distances
 		    /// of the nodes calculated by the algorithm.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    const DistMap &distMap() const { return *_dist;}
 		    /// \brief Returns a const reference to the node map that stores the
 		    /// predecessor arcs.
 		    ///
 		    /// Returns a const reference to the node map that stores the predecessor
 		    /// arcs, which form the shortest path tree (forest).
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    const PredMap &predMap() const { return *_pred; }
 		    /// \brief Checks if a node is reached from the root(s).
 		    ///
 		    /// Returns \c true if \c v is reached from the root(s).
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    bool reached(Node v) const {
 		      return (*_dist)[v] != OperationTraits::infinity();
+		    }
 		    /// \brief Gives back a negative cycle.
 		    ///
 		    /// This function gives back a directed cycle with negative total
 		    /// length if the algorithm has already found one.
 		    /// Otherwise it gives back an empty path.
 		    lemon::Path<Digraph> negativeCycle() {
 		      typename Digraph::template NodeMap<int> state(*_gr, -1);
 		      lemon::Path<Digraph> cycle;
 		      for (int i = 0; i < int(_process.size()); ++i) {
 		        if (state[_process[i]] != -1) continue;
 		        for (Node v = _process[i]; (*_pred)[v] != INVALID;
 		             v = _gr->source((*_pred)[v])) {
 		          if (state[v] == i) {
 		            cycle.addFront((*_pred)[v]);
 		            for (Node u = _gr->source((*_pred)[v]); u != v;
 		                 u = _gr->source((*_pred)[u])) {
 		              cycle.addFront((*_pred)[u]);
+		            }
 		            return cycle;
+		          }
 		          else if (state[v] >= 0) {
 		            break;
+		          }
 		          state[v] = i;
+		        }
+		      }
 		      return cycle;
+		    }
 		    ///@}
 		  };
 		  /// \brief Default traits class of bellmanFord() function.
 		  ///
 		  /// Default traits class of bellmanFord() function.
 		  /// \tparam GR The type of the digraph.
 		  /// \tparam LEN The type of the length map.
 		  template <typename GR, typename LEN>
 		  struct BellmanFordWizardDefaultTraits {
 		    /// The type of the digraph the algorithm runs on.
 		    typedef GR 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 LEN LengthMap;
 		    /// The type of the arc lengths.
 		    typedef typename LEN::Value Value;
 		    /// \brief Operation traits for Bellman-Ford algorithm.
 		    ///
 		    /// It defines the used operations and the infinity value for the
 		    /// given \c Value type.
 		    /// \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 conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
 		    /// \brief Instantiates a \c PredMap.
 		    ///
 		    /// This function instantiates a \ref PredMap.
 		    /// \param g is the digraph to which we would like to define the
 		    /// \ref PredMap.
 		    static PredMap *createPredMap(const GR &g) {
 		      return new PredMap(g);
+		    }
 		    /// \brief The type of the map that stores the distances of the nodes.
 		    ///
 		    /// The type of the map that stores the distances of the nodes.
 		    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename GR::template NodeMap<Value> DistMap;
 		    /// \brief Instantiates a \c DistMap.
 		    ///
 		    /// This function instantiates a \ref DistMap.
 		    /// \param g is the digraph to which we would like to define the
 		    /// \ref DistMap.
 		    static DistMap *createDistMap(const GR &g) {
 		      return new DistMap(g);
+		    }
 		    ///The type of the shortest paths.
 		    ///The type of the shortest paths.
 		    ///It must meet the \ref concepts::Path "Path" concept.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  /// \brief Default traits class used by BellmanFordWizard.
 		  ///
 		  /// Default traits class used by BellmanFordWizard.
 		  /// \tparam GR The type of the digraph.
 		  /// \tparam LEN The type of the length map.
 		  template <typename GR, typename LEN>
 		  class BellmanFordWizardBase
 		    : public BellmanFordWizardDefaultTraits<GR, LEN> {
 		    typedef BellmanFordWizardDefaultTraits<GR, LEN> 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 shortest path to the target node.
 		    void *_path;
 		    //Pointer to the distance of the target node.
 		    void *_di;
 		    public:
 		    /// Constructor.
 		    /// This constructor does not require parameters, it initiates
 		    /// all of the attributes to default values \c 0.
 		    BellmanFordWizardBase() :
 		      _graph(0), _length(0), _pred(0), _dist(0), _path(0), _di(0) {}
 		    /// Constructor.
 		    /// This constructor requires two parameters,
 		    /// others are initiated to \c 0.
 		    /// \param gr The digraph the algorithm runs on.
 		    /// \param len The length map.
 		    BellmanFordWizardBase(const GR& gr,
 					  const LEN& len) :
 		      _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))),
 		      _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))),
 		      _pred(0), _dist(0), _path(0), _di(0) {}
 		  };
 		  /// \brief Auxiliary class for the function-type interface of the
 		  /// \ref BellmanFord "Bellman-Ford" algorithm.
 		  ///
 		  /// This auxiliary class is created to implement the
 		  /// \ref bellmanFord() "function-type interface" of the
 		  /// \ref BellmanFord "Bellman-Ford" algorithm.
 		  /// It does not have own \ref run() method, it uses the
 		  /// functions and features of the plain \ref BellmanFord.
 		  ///
 		  /// This class should only be used through the \ref bellmanFord()
 		  /// function, which makes it easier to use the algorithm.
 		  template<class TR>
 		  class BellmanFordWizard : public TR {
 		    typedef TR Base;
 		    typedef typename TR::Digraph Digraph;
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt ArcIt;
 		    typedef typename TR::LengthMap LengthMap;
 		    typedef typename LengthMap::Value Value;
 		    typedef typename TR::PredMap PredMap;
 		    typedef typename TR::DistMap DistMap;
 		    typedef typename TR::Path Path;
 		  public:
 		    /// Constructor.
 		    BellmanFordWizard() : TR() {}
 		    /// \brief Constructor that requires parameters.
 		    ///
 		    /// Constructor that requires parameters.
 		    /// These parameters will be the default values for the traits class.
 		    /// \param gr The digraph the algorithm runs on.
 		    /// \param len The length map.
 		    BellmanFordWizard(const Digraph& gr, const LengthMap& len)
 		      : TR(gr, len) {}
 		    /// \brief Copy constructor
 		    BellmanFordWizard(const TR &b) : TR(b) {}
 		    ~BellmanFordWizard() {}
 		    /// \brief Runs the Bellman-Ford algorithm from the given source node.
 		    ///
 		    /// This method runs the Bellman-Ford algorithm from the given source
 		    /// node in order to compute the shortest path to each node.
 		    void run(Node s) {
 		      BellmanFord<Digraph,LengthMap,TR>
 			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(s);
+		    }
 		    /// \brief Runs the Bellman-Ford algorithm to find the shortest path
 		    /// between \c s and \c t.
 		    ///
 		    /// This method runs the Bellman-Ford algorithm from node \c s
 		    /// in order to compute the shortest path to node \c t.
 		    /// Actually, it computes the shortest path to each node, but using
 		    /// this function you can retrieve the distance and the shortest path
 		    /// for a single target node easier.
 		    ///
 		    /// \return \c true if \c t is reachable form \c s.
 		    bool run(Node s, Node t) {
 		      BellmanFord<Digraph,LengthMap,TR>
 		        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(s);
 		      if (Base::_path) *reinterpret_cast<Path*>(Base::_path) = bf.path(t);
 		      if (Base::_di) *reinterpret_cast<Value*>(Base::_di) = bf.dist(t);
 		      return bf.reached(t);
+		    }
 		    template<class T>
 		    struct SetPredMapBase : public Base {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &) { return 0; };
 		      SetPredMapBase(const TR &b) : TR(b) {}
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// the predecessor map.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting
 		    /// the map that stores the predecessor arcs of the nodes.
 		    template<class T>
 		    BellmanFordWizard<SetPredMapBase<T> > predMap(const T &t) {
 		      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BellmanFordWizard<SetPredMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetDistMapBase : public Base {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &) { return 0; };
 		      SetDistMapBase(const TR &b) : TR(b) {}
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// the distance map.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting
 		    /// the map that stores the distances of the nodes calculated
 		    /// by the algorithm.
 		    template<class T>
 		    BellmanFordWizard<SetDistMapBase<T> > distMap(const T &t) {
 		      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BellmanFordWizard<SetDistMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetPathBase : public Base {
 		      typedef T Path;
 		      SetPathBase(const TR &b) : TR(b) {}
 		    };
 		    /// \brief \ref named-func-param "Named parameter" for getting
 		    /// the shortest path to the target node.
 		    ///
 		    /// \ref named-func-param "Named parameter" for getting
 		    /// the shortest path to the target node.
 		    template<class T>
 		    BellmanFordWizard<SetPathBase<T> > path(const T &t)
+		    {
 		      Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BellmanFordWizard<SetPathBase<T> >(*this);
+		    }
 		    /// \brief \ref named-func-param "Named parameter" for getting
 		    /// the distance of the target node.
 		    ///
 		    /// \ref named-func-param "Named parameter" for getting
 		    /// the distance of the target node.
 		    BellmanFordWizard dist(const Value &d)
+		    {
 		      Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d));
 		      return *this;
+		    }
 		  };
 		  /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford"
 		  /// algorithm.
 		  ///
 		  /// \ingroup shortest_path
 		  /// Function type interface for the \ref BellmanFord "Bellman-Ford"
 		  /// 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 examples show how to use these parameters.
 		  /// \code
 		  ///   // Compute shortest path from node s to each node
 		  ///   bellmanFord(g,length).predMap(preds).distMap(dists).run(s);
 		  ///
 		  ///   // Compute shortest path from s to t
 		  ///   bool reached = bellmanFord(g,length).path(p).dist(d).run(s,t);
 		  /// \endcode
 		  /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()"
 		  /// to the end of the parameter list.
 		  /// \sa BellmanFordWizard
 		  /// \sa BellmanFord
 		  template<typename GR, typename LEN>
 		  BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >
 		  bellmanFord(const GR& digraph,
 			      const LEN& length)
+		  {
 		    return BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >(digraph, length);
+		  }
 		} //END OF NAMESPACE LEMON
 		#endif

lemon/binom_heap.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * 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.
+		 *
 		 */
 		#ifndef LEMON_BINOM_HEAP_H
 		#define LEMON_BINOM_HEAP_H
 		///\file
 		///\ingroup heaps
 		///\brief Binomial Heap implementation.
 		#include <vector>
 		#include <utility>
 		#include <functional>
 		#include <lemon/math.h>
 		#include <lemon/counter.h>
 		namespace lemon {
 		  /// \ingroup heaps
 		  ///
 		  ///\brief Binomial heap data structure.
 		  ///
 		  /// This class implements the \e binomial \e heap data structure.
 		  /// It fully conforms to the \ref concepts::Heap "heap concept".
 		  ///
 		  /// The methods \ref increase() and \ref erase() are not efficient
 		  /// in a binomial heap. In case of many calls of these operations,
 		  /// it is better to use other heap structure, e.g. \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>.
 		#ifdef DOXYGEN
 		  template <typename PR, typename IM, typename CMP>
 		#else
 		  template <typename PR, typename IM, typename CMP = std::less<PR> >
 		#endif
 		  class BinomHeap {
 		  public:
 		    /// Type of the item-int map.
 		    typedef IM ItemIntMap;
 		    /// Type of the priorities.
 		    typedef PR Prio;
 		    /// Type of the items stored in the heap.
 		    typedef typename ItemIntMap::Key Item;
 		    /// Functor type for comparing the priorities.
 		    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
 		    /// 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.
 		    enum State {
 		      IN_HEAP = 0,    ///< = 0.
 		      PRE_HEAP = -1,  ///< = -1.
 		      POST_HEAP = -2  ///< = -2.
 		    };
 		  private:
 		    class Store;
 		    std::vector<Store> _data;
 		    int _min, _head;
 		    ItemIntMap &_iim;
 		    Compare _comp;
 		    int _num_items;
 		  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.
 		    explicit BinomHeap(ItemIntMap &map)
 		      : _min(0), _head(-1), _iim(map), _num_items(0) {}
 		    /// \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.
 		    BinomHeap(ItemIntMap &map, const Compare &comp)
 		      : _min(0), _head(-1), _iim(map), _comp(comp), _num_items(0) {}
 		    /// \brief The number of items stored in the heap.
 		    ///
 		    /// This function returns the number of items stored in the heap.
 		    int size() const { return _num_items; }
 		    /// \brief Check if the heap is empty.
 		    ///
 		    /// This function returns \c true if the heap is empty.
 		    bool empty() const { return _num_items==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.
 		    void clear() {
 		      _data.clear(); _min=0; _num_items=0; _head=-1;
+		    }
 		    /// \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 value The priority.
 		    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 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 value The priority of the item.
 		    /// \pre \e item must not be stored in the heap.
 		    void push (const Item& item, const Prio& value) {
 		      int i=_iim[item];
 		      if ( i<0 ) {
 		        int s=_data.size();
 		        _iim.set( item,s );
 		        Store st;
 		        st.name=item;
 		        st.prio=value;
 		        _data.push_back(st);
 		        i=s;
+		      }
 		      else {
 		        _data[i].parent=_data[i].right_neighbor=_data[i].child=-1;
 		        _data[i].degree=0;
 		        _data[i].in=true;
 		        _data[i].prio=value;
+		      }
 		      if( 0==_num_items ) {
 		        _head=i;
 		        _min=i;
 		      } else {
 		        merge(i);
 		        if( _comp(_data[i].prio, _data[_min].prio) ) _min=i;
+		      }
 		      ++_num_items;
+		    }
 		    /// \brief Return the item having minimum priority.
 		    ///
 		    /// This function returns the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Item top() const { return _data[_min].name; }
 		    /// \brief The minimum priority.
 		    ///
 		    /// This function returns the minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Prio prio() const { return _data[_min].prio; }
 		    /// \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.
 		    const Prio& operator[](const Item& item) const {
 		      return _data[_iim[item]].prio;
+		    }
 		    /// \brief Remove the item having minimum priority.
 		    ///
 		    /// This function removes the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    void pop() {
 		      _data[_min].in=false;
 		      int head_child=-1;
 		      if ( _data[_min].child!=-1 ) {
 		        int child=_data[_min].child;
 		        int neighb;
 		        while( child!=-1 ) {
 		          neighb=_data[child].right_neighbor;
 		          _data[child].parent=-1;
 		          _data[child].right_neighbor=head_child;
 		          head_child=child;
 		          child=neighb;
+		        }
+		      }
 		      if ( _data[_head].right_neighbor==-1 ) {
 		        // there was only one root
 		        _head=head_child;
+		      }
 		      else {
 		        // there were more roots
 		        if( _head!=_min )  { unlace(_min); }
 		        else { _head=_data[_head].right_neighbor; }
 		        merge(head_child);
+		      }
 		      _min=findMin();
 		      --_num_items;
+		    }
 		    /// \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.
 		    void erase (const Item& item) {
 		      int i=_iim[item];
 		      if ( i >= 0 && _data[i].in ) {
 		        decrease( item, _data[_min].prio-1 );
 		        pop();
+		      }
+		    }
 		    /// \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 value The priority.
 		    /// \pre \e item must be stored in the heap with priority at least \e value.
 		    void decrease (Item item, const Prio& value) {
 		      int i=_iim[item];
 		      int p=_data[i].parent;
 		      _data[i].prio=value;
 		      while( p!=-1 && _comp(value, _data[p].prio) ) {
 		        _data[i].name=_data[p].name;
 		        _data[i].prio=_data[p].prio;
 		        _data[p].name=item;
 		        _data[p].prio=value;
 		        _iim[_data[i].name]=i;
 		        i=p;
 		        p=_data[p].parent;
+		      }
 		      _iim[item]=i;
 		      if ( _comp(value, _data[_min].prio) ) _min=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 value The priority.
 		    /// \pre \e item must be stored in the heap with priority at most \e value.
 		    void increase (Item item, const Prio& value) {
 		      erase(item);
 		      push(item, value);
+		    }
 		    /// \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.
 		    State state(const Item &item) const {
 		      int i=_iim[item];
 		      if( i>=0 ) {
 		        if ( _data[i].in ) i=0;
 		        else i=-2;
+		      }
 		      return State(i);
+		    }
 		    /// \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.
 		    /// \param i The item.
 		    /// \param st The state. It should not be \c IN_HEAP.
 		    void state(const Item& i, State st) {
 		      switch (st) {
 		      case POST_HEAP:
 		      case PRE_HEAP:
 		        if (state(i) == IN_HEAP) {
 		          erase(i);
+		        }
 		        _iim[i] = st;
 		        break;
 		      case IN_HEAP:
 		        break;
+		      }
+		    }
 		  private:
 		    // Find the minimum of the roots
 		    int findMin() {
 		      if( _head!=-1 ) {
 		        int min_loc=_head, min_val=_data[_head].prio;
 		        for( int x=_data[_head].right_neighbor; x!=-1;
 		             x=_data[x].right_neighbor ) {
 		          if( _comp( _data[x].prio,min_val ) ) {
 		            min_val=_data[x].prio;
 		            min_loc=x;
+		          }
+		        }
 		        return min_loc;
+		      }
 		      else return -1;
+		    }
 		    // Merge the heap with another heap starting at the given position
 		    void merge(int a) {
 		      if( _head==-1 || a==-1 ) return;
 		      if( _data[a].right_neighbor==-1 &&
 		          _data[a].degree<=_data[_head].degree ) {
 		        _data[a].right_neighbor=_head;
 		        _head=a;
 		      } else {
 		        interleave(a);
+		      }
 		      if( _data[_head].right_neighbor==-1 ) return;
 		      int x=_head;
 		      int x_prev=-1, x_next=_data[x].right_neighbor;
 		      while( x_next!=-1 ) {
 		        if( _data[x].degree!=_data[x_next].degree ||
 		            ( _data[x_next].right_neighbor!=-1 &&
 		              _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) {
 		          x_prev=x;
 		          x=x_next;
+		        }
 		        else {
 		          if( _comp(_data[x_next].prio,_data[x].prio) ) {
 		            if( x_prev==-1 ) {
 		              _head=x_next;
 		            } else {
 		              _data[x_prev].right_neighbor=x_next;
+		            }
 		            fuse(x,x_next);
 		            x=x_next;
+		          }
 		          else {
 		            _data[x].right_neighbor=_data[x_next].right_neighbor;
 		            fuse(x_next,x);
+		          }
+		        }
 		        x_next=_data[x].right_neighbor;
+		      }
+		    }
 		    // Interleave the elements of the given list into the list of the roots
 		    void interleave(int a) {
 		      int p=_head, q=a;
 		      int curr=_data.size();
 		      _data.push_back(Store());
 		      while( p!=-1 || q!=-1 ) {
 		        if( q==-1 || ( p!=-1 && _data[p].degree<_data[q].degree ) ) {
 		          _data[curr].right_neighbor=p;
 		          curr=p;
 		          p=_data[p].right_neighbor;
+		        }
 		        else {
 		          _data[curr].right_neighbor=q;
 		          curr=q;
 		          q=_data[q].right_neighbor;
+		        }
+		      }
 		      _head=_data.back().right_neighbor;
 		      _data.pop_back();
+		    }
 		    // Lace node a under node b
 		    void fuse(int a, int b) {
 		      _data[a].parent=b;
 		      _data[a].right_neighbor=_data[b].child;
 		      _data[b].child=a;
 		      ++_data[b].degree;
+		    }
 		    // Unlace node a (if it has siblings)
 		    void unlace(int a) {
 		      int neighb=_data[a].right_neighbor;
 		      int other=_head;
 		      while( _data[other].right_neighbor!=a )
 		        other=_data[other].right_neighbor;
 		      _data[other].right_neighbor=neighb;
+		    }
 		  private:
 		    class Store {
 		      friend class BinomHeap;
 		      Item name;
 		      int parent;
 		      int right_neighbor;
 		      int child;
 		      int degree;
 		      bool in;
 		      Prio prio;
 		      Store() : parent(-1), right_neighbor(-1), child(-1), degree(0),
 		        in(true) {}
 		    };
 		  };
 		} //namespace lemon
 		#endif //LEMON_BINOM_HEAP_H

lemon/fourary_heap.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * 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.
+		 *
 		 */
 		#ifndef LEMON_FOURARY_HEAP_H
 		#define LEMON_FOURARY_HEAP_H
 		///\ingroup heaps
 		///\file
 		///\brief Fourary heap implementation.
 		#include <vector>
 		#include <utility>
 		#include <functional>
 		namespace lemon {
 		  /// \ingroup heaps
 		  ///
 		  ///\brief Fourary heap data structure.
 		  ///
 		  /// This class implements the \e fourary \e heap data structure.
 		  /// It fully conforms to the \ref concepts::Heap "heap concept".
 		  ///
 		  /// The fourary heap is a specialization of the \ref KaryHeap "K-ary heap"
 		  /// for <tt>K=4</tt>. It is similar to the \ref BinHeap "binary heap",
 		  /// but its nodes have at most four children, instead of two.
 		  ///
 		  /// \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>.
 		  ///
 		  ///\sa BinHeap
 		  ///\sa KaryHeap
 		#ifdef DOXYGEN
 		  template <typename PR, typename IM, typename CMP>
 		#else
 		  template <typename PR, typename IM, typename CMP = std::less<PR> >
 		#endif
 		  class FouraryHeap {
 		  public:
 		    /// Type of the item-int map.
 		    typedef IM ItemIntMap;
 		    /// Type of the priorities.
 		    typedef PR 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;
 		    /// Functor type for comparing the priorities.
 		    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
 		    /// 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.
 		    enum State {
 		      IN_HEAP = 0,    ///< = 0.
 		      PRE_HEAP = -1,  ///< = -1.
 		      POST_HEAP = -2  ///< = -2.
 		    };
 		  private:
 		    std::vector<Pair> _data;
 		    Compare _comp;
 		    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.
 		    explicit FouraryHeap(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.
 		    FouraryHeap(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.
 		    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.
 		    void clear() { _data.clear(); }
 		  private:
 		    static int parent(int i) { return (i-1)/4; }
 		    static int firstChild(int i) { return 4*i+1; }
 		    bool less(const Pair &p1, const Pair &p2) const {
 		      return _comp(p1.second, p2.second);
+		    }
 		    void bubbleUp(int hole, Pair p) {
 		      int par = parent(hole);
 		      while( hole>0 && less(p,_data[par]) ) {
 		        move(_data[par],hole);
 		        hole = par;
 		        par = parent(hole);
+		      }
 		      move(p, hole);
+		    }
 		    void bubbleDown(int hole, Pair p, int length) {
 		      if( length>1 ) {
 		        int child = firstChild(hole);
 		        while( child+3<length ) {
 		          int min=child;
 		          if( less(_data[++child], _data[min]) ) min=child;
 		          if( less(_data[++child], _data[min]) ) min=child;
 		          if( less(_data[++child], _data[min]) ) min=child;
 		          if( !less(_data[min], p) )
 		            goto ok;
 		          move(_data[min], hole);
 		          hole = min;
 		          child = firstChild(hole);
+		        }
 		        if ( child<length ) {
 		          int min = child;
 		          if( ++child<length && less(_data[child], _data[min]) ) min=child;
 		          if( ++child<length && less(_data[child], _data[min]) ) min=child;
 		          if( less(_data[min], p) ) {
 		            move(_data[min], hole);
 		            hole = min;
+		          }
+		        }
+		      }
 		    ok:
 		      move(p, hole);
+		    }
 		    void move(const Pair &p, int i) {
 		      _data[i] = p;
 		      _iim.set(p.first, i);
+		    }
 		  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.
 		    /// \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.
 		    /// \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.
 		    Item top() const { return _data[0].first; }
 		    /// \brief The minimum priority.
 		    ///
 		    /// This function returns the minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Prio prio() const { return _data[0].second; }
 		    /// \brief Remove the item having minimum priority.
 		    ///
 		    /// This function removes the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    void pop() {
 		      int n = _data.size()-1;
 		      _iim.set(_data[0].first, POST_HEAP);
 		      if (n>0) bubbleDown(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.
 		    void erase(const Item &i) {
 		      int h = _iim[i];
 		      int n = _data.size()-1;
 		      _iim.set(_data[h].first, POST_HEAP);
 		      if( h<n ) {
 		        if( less(_data[parent(h)], _data[n]) )
 		          bubbleDown(h, _data[n], n);
 		        else
 		          bubbleUp(h, _data[n]);
+		      }
 		      _data.pop_back();
+		    }
 		    /// \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.
 		    Prio operator[](const Item &i) const {
 		      int idx = _iim[i];
 		      return _data[idx].second;
+		    }
 		    /// \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 i The item.
 		    /// \param p The priority.
 		    void set(const Item &i, const Prio &p) {
 		      int idx = _iim[i];
 		      if( idx < 0 )
 		        push(i,p);
 		      else if( _comp(p, _data[idx].second) )
 		        bubbleUp(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.
 		    /// \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];
 		      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.
 		    /// \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];
 		      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.
 		    /// \param i The item.
 		    State state(const Item &i) const {
 		      int s = _iim[i];
 		      if (s>=0) s=0;
 		      return State(s);
+		    }
 		    /// \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.
 		    /// \param i The item.
 		    /// \param st The state. It should not be \c IN_HEAP.
 		    void state(const Item& i, State st) {
 		      switch (st) {
 		        case POST_HEAP:
 		        case PRE_HEAP:
 		          if (state(i) == IN_HEAP) erase(i);
 		          _iim[i] = st;
 		          break;
 		        case IN_HEAP:
 		          break;
+		      }
+		    }
 		    /// \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.
 		    void replace(const Item& i, const Item& j) {
 		      int idx = _iim[i];
 		      _iim.set(i, _iim[j]);
 		      _iim.set(j, idx);
 		      _data[idx].first = j;
+		    }
 		  }; // class FouraryHeap
 		} // namespace lemon
 		#endif // LEMON_FOURARY_HEAP_H

lemon/kary_heap.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * 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.
+		 *
 		 */
 		#ifndef LEMON_KARY_HEAP_H
 		#define LEMON_KARY_HEAP_H
 		///\ingroup heaps
 		///\file
 		///\brief Fourary heap implementation.
 		#include <vector>
 		#include <utility>
 		#include <functional>
 		namespace lemon {
 		  /// \ingroup heaps
 		  ///
 		  ///\brief K-ary heap data structure.
 		  ///
 		  /// This class implements the \e K-ary \e heap data structure.
 		  /// It fully conforms to the \ref concepts::Heap "heap concept".
 		  ///
 		  /// The \ref KaryHeap "K-ary heap" is a generalization of the
 		  /// \ref BinHeap "binary heap" structure, its nodes have at most
 		  /// \c K children, instead of two.
 		  /// \ref BinHeap and \ref FouraryHeap are specialized implementations
 		  /// of this structure for <tt>K=2</tt> and <tt>K=4</tt>, respectively.
 		  ///
 		  /// \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 K The degree of the heap, each node have at most \e K
 		  /// children. The default is 16. Powers of two are suggested to use
 		  /// so that the multiplications and divisions needed to traverse the
 		  /// nodes of the heap could be performed faster.
 		  /// \tparam CMP A functor class for comparing the priorities.
 		  /// The default is \c std::less<PR>.
 		  ///
 		  ///\sa BinHeap
 		  ///\sa FouraryHeap
 		#ifdef DOXYGEN
 		  template <typename PR, typename IM, int K, typename CMP>
 		#else
 		  template <typename PR, typename IM, int K = 16,
 		            typename CMP = std::less<PR> >
 		#endif
 		  class KaryHeap {
 		  public:
 		    /// Type of the item-int map.
 		    typedef IM ItemIntMap;
 		    /// Type of the priorities.
 		    typedef PR 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;
 		    /// Functor type for comparing the priorities.
 		    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
 		    /// 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.
 		    enum State {
 		      IN_HEAP = 0,    ///< = 0.
 		      PRE_HEAP = -1,  ///< = -1.
 		      POST_HEAP = -2  ///< = -2.
 		    };
 		  private:
 		    std::vector<Pair> _data;
 		    Compare _comp;
 		    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.
 		    explicit KaryHeap(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.
 		    KaryHeap(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.
 		    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.
 		    void clear() { _data.clear(); }
 		  private:
 		    int parent(int i) { return (i-1)/K; }
 		    int firstChild(int i) { return K*i+1; }
 		    bool less(const Pair &p1, const Pair &p2) const {
 		      return _comp(p1.second, p2.second);
+		    }
 		    void bubbleUp(int hole, Pair p) {
 		      int par = parent(hole);
 		      while( hole>0 && less(p,_data[par]) ) {
 		        move(_data[par],hole);
 		        hole = par;
 		        par = parent(hole);
+		      }
 		      move(p, hole);
+		    }
 		    void bubbleDown(int hole, Pair p, int length) {
 		      if( length>1 ) {
 		        int child = firstChild(hole);
 		        while( child+K<=length ) {
 		          int min=child;
 		          for (int i=1; i<K; ++i) {
 		            if( less(_data[child+i], _data[min]) )
 		              min=child+i;
+		          }
 		          if( !less(_data[min], p) )
 		            goto ok;
 		          move(_data[min], hole);
 		          hole = min;
 		          child = firstChild(hole);
+		        }
 		        if ( child<length ) {
 		          int min = child;
 		          while (++child < length) {
 		            if( less(_data[child], _data[min]) )
 		              min=child;
+		          }
 		          if( less(_data[min], p) ) {
 		            move(_data[min], hole);
 		            hole = min;
+		          }
+		        }
+		      }
 		    ok:
 		      move(p, hole);
+		    }
 		    void move(const Pair &p, int i) {
 		      _data[i] = p;
 		      _iim.set(p.first, i);
+		    }
 		  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.
 		    /// \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.
 		    /// \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.
 		    Item top() const { return _data[0].first; }
 		    /// \brief The minimum priority.
 		    ///
 		    /// This function returns the minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Prio prio() const { return _data[0].second; }
 		    /// \brief Remove the item having minimum priority.
 		    ///
 		    /// This function removes the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    void pop() {
 		      int n = _data.size()-1;
 		      _iim.set(_data[0].first, POST_HEAP);
 		      if (n>0) bubbleDown(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.
 		    void erase(const Item &i) {
 		      int h = _iim[i];
 		      int n = _data.size()-1;
 		      _iim.set(_data[h].first, POST_HEAP);
 		      if( h<n ) {
 		        if( less(_data[parent(h)], _data[n]) )
 		          bubbleDown(h, _data[n], n);
 		        else
 		          bubbleUp(h, _data[n]);
+		      }
 		      _data.pop_back();
+		    }
 		    /// \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.
 		    Prio operator[](const Item &i) const {
 		      int idx = _iim[i];
 		      return _data[idx].second;
+		    }
 		    /// \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 i The item.
 		    /// \param p The priority.
 		    void set(const Item &i, const Prio &p) {
 		      int idx = _iim[i];
 		      if( idx<0 )
 		        push(i,p);
 		      else if( _comp(p, _data[idx].second) )
 		        bubbleUp(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.
 		    /// \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];
 		      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.
 		    /// \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];
 		      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.
 		    /// \param i The item.
 		    State state(const Item &i) const {
 		      int s = _iim[i];
 		      if (s>=0) s=0;
 		      return State(s);
+		    }
 		    /// \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.
 		    /// \param i The item.
 		    /// \param st The state. It should not be \c IN_HEAP.
 		    void state(const Item& i, State st) {
 		      switch (st) {
 		        case POST_HEAP:
 		        case PRE_HEAP:
 		          if (state(i) == IN_HEAP) erase(i);
 		          _iim[i] = st;
 		          break;
 		        case IN_HEAP:
 		          break;
+		      }
+		    }
 		    /// \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.
 		    void replace(const Item& i, const Item& j) {
 		      int idx=_iim[i];
 		      _iim.set(i, _iim[j]);
 		      _iim.set(j, idx);
 		      _data[idx].first=j;
+		    }
 		  }; // class KaryHeap
 		} // namespace lemon
 		#endif // LEMON_KARY_HEAP_H

doc/groups.dox

Show inline comments

@@ -226,14 +226,6 @@
 		*/
 		/**
 		@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
 		\brief %Path structures implemented in LEMON.
@@ -246,7 +238,36 @@
 		efficient to have e.g. the Dijkstra algorithm to store its result in
 		any kind of path structure.
-		\sa lemon::concepts::Path
+		\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.
 		*/
 		/**
@@ -259,6 +280,28 @@
 		*/
 		/**
 		@defgroup geomdat Geometric Data Structures
 		@ingroup auxdat
 		\brief Geometric data structures implemented in LEMON.
 		This group contains geometric data structures implemented in LEMON.
 		 - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional
 		   vector with the usual operations.
 		 - \ref lemon::dim2::Box "dim2::Box" can be used to determine the
 		   rectangular bounding box of a set of \ref lemon::dim2::Point
 		   "dim2::Point"'s.
 		*/
 		/**
 		@defgroup matrices Matrices
 		@ingroup auxdat
 		\brief Two dimensional data storages implemented in LEMON.
 		This group contains two dimensional data storages implemented in LEMON.
 		*/
 		/**
 		@defgroup algs Algorithms
 		\brief This group contains the several algorithms
 		implemented in LEMON.
@@ -298,6 +341,15 @@
 		*/
 		/**
 		@defgroup spantree Minimum Spanning Tree Algorithms
 		@ingroup algs
 		\brief Algorithms for finding minimum cost spanning trees and arborescences.
 		This group contains the algorithms for finding minimum cost spanning
 		trees and arborescences.
 		*/
 		/**
 		@defgroup max_flow Maximum Flow Algorithms
 		@ingroup algs
 		\brief Algorithms for finding maximum flows.
@@ -375,7 +427,7 @@
 		cut is the \f$X\f$ solution of the next optimization problem:
 		\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
-		    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
+		    \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
 		LEMON contains several algorithms related to minimum cut problems:
@@ -391,30 +443,6 @@
 		*/
 		/**
 		@defgroup graph_properties Connectivity and Other Graph Properties
 		@ingroup algs
 		\brief Algorithms for discovering the graph properties
 		This group contains the algorithms for discovering the graph properties
 		like connectivity, bipartiteness, euler property, simplicity etc.
 		\image html edge_biconnected_components.png
 		\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
 		*/
 		/**
 		@defgroup planar Planarity Embedding and Drawing
 		@ingroup algs
 		\brief Algorithms for planarity checking, embedding and drawing
 		This group contains the algorithms for planarity checking,
 		embedding and drawing.
 		\image html planar.png
 		\image latex planar.eps "Plane graph" width=\textwidth
 		*/
 		/**
 		@defgroup matching Matching Algorithms
 		@ingroup algs
 		\brief Algorithms for finding matchings in graphs and bipartite graphs.
@@ -455,12 +483,36 @@
 		*/
 		/**
-		@defgroup spantree Minimum Spanning Tree Algorithms
+		@defgroup graph_properties Connectivity and Other Graph Properties
 		@ingroup algs
-		\brief Algorithms for finding minimum cost spanning trees and arborescences.
+		\brief Algorithms for discovering the graph properties
 		This group contains the algorithms for finding minimum cost spanning
 		trees and arborescences.
 		This group contains the algorithms for discovering the graph properties
 		like connectivity, bipartiteness, euler property, simplicity etc.
 		\image html connected_components.png
 		\image latex connected_components.eps "Connected components" width=\textwidth
 		*/
 		/**
 		@defgroup planar Planarity Embedding and Drawing
 		@ingroup algs
 		\brief Algorithms for planarity checking, embedding and drawing
 		This group contains the algorithms for planarity checking,
 		embedding and drawing.
 		\image html planar.png
 		\image latex planar.eps "Plane graph" width=\textwidth
 		*/
 		/**
 		@defgroup approx Approximation Algorithms
 		@ingroup algs
 		\brief Approximation algorithms.
 		This group contains the approximation and heuristic algorithms
 		implemented in LEMON.
 		*/
 		/**
@@ -473,15 +525,6 @@
 		*/
 		/**
 		@defgroup approx Approximation Algorithms
 		@ingroup algs
 		\brief Approximation algorithms.
 		This group contains the approximation and heuristic algorithms
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup gen_opt_group General Optimization Tools
 		\brief This group contains some general optimization frameworks
 		implemented in LEMON.
@@ -587,7 +630,7 @@
 		*/
 		/**
-		@defgroup dimacs_group DIMACS format
+		@defgroup dimacs_group DIMACS Format
 		@ingroup io_group
 		\brief Read and write files in DIMACS format
@@ -649,6 +692,15 @@
 		*/
 		/**
 		@defgroup tools Standalone Utility Applications
 		Some utility applications are listed here.
 		The standard compilation procedure (<tt>./configure;make</tt>) will compile
 		them, as well.
 		*/
 		/**
 		\anchor demoprograms
 		@defgroup demos Demo Programs
@@ -660,13 +712,4 @@
 		<tt>make check</tt> commands.
 		*/
 		/**
 		@defgroup tools Standalone Utility Applications
 		Some utility applications are listed here.
 		The standard compilation procedure (<tt>./configure;make</tt>) will compile
 		them, as well.
 		*/
+		}

lemon/Makefile.am

Show inline comments

@@ -57,8 +57,10 @@
 			lemon/adaptors.h \
 			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 \
 			lemon/circulation.h \
@@ -78,12 +80,14 @@
 			lemon/error.h \
 			lemon/euler.h \
 			lemon/fib_heap.h \
 			lemon/fourary_heap.h \
 			lemon/full_graph.h \
 			lemon/glpk.h \
 			lemon/gomory_hu.h \
 			lemon/graph_to_eps.h \
 			lemon/grid_graph.h \
 			lemon/hypercube_graph.h \
 			lemon/kary_heap.h \
 			lemon/kruskal.h \
 			lemon/hao_orlin.h \
 			lemon/lgf_reader.h \
@@ -98,6 +102,7 @@
 			lemon/min_cost_arborescence.h \
 			lemon/nauty_reader.h \
 			lemon/network_simplex.h \
 			lemon/pairing_heap.h \
 			lemon/path.h \
 			lemon/preflow.h \
 			lemon/radix_heap.h \

lemon/bfs.h

Show inline comments

@@ -47,7 +47,7 @@
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a \c PredMap.
@@ -62,7 +62,8 @@
 		    ///The type of the map that indicates which nodes are processed.
 		    ///The type of the map that indicates which nodes are processed.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default it is a NullMap.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a \c ProcessedMap.
@@ -81,7 +82,7 @@
 		    ///The type of the map that indicates which nodes are reached.
 		    ///The type of the map that indicates which nodes are reached.
-		    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+		    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    ///Instantiates a \c ReachedMap.
@@ -96,7 +97,7 @@
 		    ///The type of the map that stores the distances of the nodes.
 		    ///The type of the map that stores the distances of the nodes.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<int> DistMap;
 		    ///Instantiates a \c DistMap.
@@ -225,7 +226,7 @@
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c PredMap type.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
 		      typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
@@ -245,7 +246,7 @@
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c DistMap type.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
 		      typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
@@ -265,7 +266,7 @@
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c ReachedMap type.
-		    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+		    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    template <class T>
 		    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
 		      typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
@@ -285,7 +286,7 @@
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
 		      typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
@@ -413,8 +414,8 @@
 		    ///\name Execution Control
 		    ///The simplest way to execute the BFS algorithm is to use one of the
 		    ///member functions called \ref run(Node) "run()".\n
 		    ///If you need more control on the execution, first you have to call
 		    ///\ref init(), then you can add several source nodes with
 		    ///If you need better control on the execution, you have to call
 		    ///\ref init() first, then you can add several source nodes with
 		    ///\ref addSource(). Finally the actual path computation can be
 		    ///performed with one of the \ref start() functions.
@@ -737,9 +738,9 @@
 		    ///@{
-		    ///The shortest path to a node.
+		    ///The shortest path to the given node.
-		    ///Returns the shortest path to a node.
+		    ///Returns the shortest path to the given node from the root(s).
 		    ///
 		    ///\warning \c t should be reached from the root(s).
 		    ///
@@ -747,9 +748,9 @@
 		    ///must be called before using this function.
 		    Path path(Node t) const { return Path(*G, *_pred, t); }
-		    ///The distance of a node from the root(s).
+		    ///The distance of the given node from the root(s).
-		    ///Returns the distance of a node from the root(s).
+		    ///Returns the distance of the given node from the root(s).
 		    ///
 		    ///\warning If node \c v is not reached from the root(s), then
 		    ///the return value of this function is undefined.
@@ -758,29 +759,31 @@
 		    ///must be called before using this function.
 		    int dist(Node v) const { return (*_dist)[v]; }
 		    ///Returns the 'previous arc' of the shortest path tree for a node.
 		    ///\brief Returns the 'previous arc' of the shortest path tree for
 		    ///the given node.
 		    ///
 		    ///This function returns the 'previous arc' of the shortest path
 		    ///tree for the node \c v, i.e. it returns the last arc of a
 		    ///shortest path from a root to \c v. It is \c INVALID if \c v
 		    ///is not reached from the root(s) or if \c v is a root.
 		    ///
 		    ///The shortest path tree used here is equal to the shortest path
 		    ///tree used in \ref predNode().
+		    ///tree used in \ref predNode() and \ref predMap().
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    Arc predArc(Node v) const { return (*_pred)[v];}
 		    ///Returns the 'previous node' of the shortest path tree for a node.
 		    ///\brief Returns the 'previous node' of the shortest path tree for
 		    ///the given node.
 		    ///
 		    ///This function returns the 'previous node' of the shortest path
 		    ///tree for the node \c v, i.e. it returns the last but one node
-		    ///from a shortest path from a root to \c v. It is \c INVALID
+		    ///of a shortest path from a root to \c v. It is \c INVALID
 		    ///if \c v is not reached from the root(s) or if \c v is a root.
 		    ///
 		    ///The shortest path tree used here is equal to the shortest path
 		    ///tree used in \ref predArc().
+		    ///tree used in \ref predArc() and \ref predMap().
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
@@ -801,13 +804,13 @@
 		    ///predecessor arcs.
 		    ///
 		    ///Returns a const reference to the node map that stores the predecessor
 		    ///arcs, which form the shortest path tree.
+		    ///arcs, which form the shortest path tree (forest).
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    const PredMap &predMap() const { return *_pred;}
-		    ///Checks if a node is reached from the root(s).
+		    ///Checks if the given node is reached from the root(s).
 		    ///Returns \c true if \c v is reached from the root(s).
 		    ///
@@ -833,7 +836,7 @@
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a PredMap.
@@ -848,7 +851,7 @@
 		    ///The type of the map that indicates which nodes are processed.
 		    ///The type of the map that indicates which nodes are processed.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default it is a NullMap.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a ProcessedMap.
@@ -868,7 +871,7 @@
 		    ///The type of the map that indicates which nodes are reached.
 		    ///The type of the map that indicates which nodes are reached.
-		    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+		    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    ///Instantiates a ReachedMap.
@@ -883,7 +886,7 @@
 		    ///The type of the map that stores the distances of the nodes.
 		    ///The type of the map that stores the distances of the nodes.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<int> DistMap;
 		    ///Instantiates a DistMap.
@@ -898,18 +901,14 @@
 		    ///The type of the shortest paths.
 		    ///The type of the shortest paths.
-		    ///It must meet the \ref concepts::Path "Path" concept.
+		    ///It must conform to the \ref concepts::Path "Path" concept.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  /// Default traits class used by BfsWizard
 		  /// To make it easier to use Bfs algorithm
 		  /// we have created a wizard class.
 		  /// This \ref BfsWizard class needs default traits,
 		  /// as well as the \ref Bfs class.
 		  /// The \ref BfsWizardBase is a class to be the default traits of the
 		  /// \ref BfsWizard class.
 		  /// Default traits class used by BfsWizard.
 		  /// \tparam GR The type of the digraph.
 		  template<class GR>
 		  class BfsWizardBase : public BfsWizardDefaultTraits<GR>
+		  {
@@ -937,7 +936,7 @@
 		    public:
 		    /// Constructor.
-		    /// This constructor does not require parameters, therefore it initiates
 		    /// This constructor does not require parameters, it initiates
 		    /// all of the attributes to \c 0.
 		    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
 		                      _dist(0), _path(0), _di(0) {}
@@ -967,7 +966,6 @@
+		  {
 		    typedef TR Base;
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    typedef typename Digraph::Node Node;
@@ -975,16 +973,10 @@
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///\brief The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///\brief The type of the map that indicates which nodes are reached.
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///\brief The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the shortest paths
 		    typedef typename TR::Path Path;
 		  public:
@@ -1067,11 +1059,12 @@
 		      static PredMap *createPredMap(const Digraph &) { return 0; };
 		      SetPredMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting PredMap object.
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///the predecessor map.
 		    ///
 		    ///\ref named-func-param "Named parameter"
 		    ///for setting PredMap object.
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that stores the predecessor arcs of the nodes.
 		    template<class T>
 		    BfsWizard<SetPredMapBase<T> > predMap(const T &t)
+		    {
@@ -1085,11 +1078,12 @@
 		      static ReachedMap *createReachedMap(const Digraph &) { return 0; };
 		      SetReachedMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting ReachedMap object.
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///the reached map.
 		    ///
 		    /// \ref named-func-param "Named parameter"
 		    ///for setting ReachedMap object.
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that indicates which nodes are reached.
 		    template<class T>
 		    BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
+		    {
@@ -1103,11 +1097,13 @@
 		      static DistMap *createDistMap(const Digraph &) { return 0; };
 		      SetDistMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting DistMap object.
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///the distance map.
 		    ///
 		    /// \ref named-func-param "Named parameter"
 		    ///for setting DistMap object.
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that stores the distances of the nodes calculated
 		    ///by the algorithm.
 		    template<class T>
 		    BfsWizard<SetDistMapBase<T> > distMap(const T &t)
+		    {
@@ -1121,11 +1117,12 @@
 		      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
 		      SetProcessedMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting ProcessedMap object.
 		    ///\brief \ref named-func-param "Named parameter" for setting
 		    ///the processed map.
 		    ///
 		    /// \ref named-func-param "Named parameter"
 		    ///for setting ProcessedMap object.
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that indicates which nodes are processed.
 		    template<class T>
 		    BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
+		    {
@@ -1264,7 +1261,7 @@
 		    /// \brief The type of the map that indicates which nodes are reached.
 		    ///
 		    /// The type of the map that indicates which nodes are reached.
-		    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+		    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    /// \brief Instantiates a ReachedMap.
@@ -1425,8 +1422,8 @@
 		    /// \name Execution Control
 		    /// The simplest way to execute the BFS algorithm is to use one of the
 		    /// member functions called \ref run(Node) "run()".\n
 		    /// If you need more control on the execution, first you have to call
 		    /// \ref init(), then you can add several source nodes with
 		    /// If you need better control on the execution, you have to call
 		    /// \ref init() first, then you can add several source nodes with
 		    /// \ref addSource(). Finally the actual path computation can be
 		    /// performed with one of the \ref start() functions.
@@ -1735,7 +1732,7 @@
 		    ///@{
-		    /// \brief Checks if a node is reached from the root(s).
+		    /// \brief Checks if the given node is reached from the root(s).
 		    ///
 		    /// Returns \c true if \c v is reached from the root(s).
 		    ///

lemon/bin_heap.h

Show inline comments

@@ -19,9 +19,9 @@
 		#ifndef LEMON_BIN_HEAP_H
 		#define LEMON_BIN_HEAP_H
-		///\ingroup auxdat
+		///\ingroup heaps
 		///\file
-		///\brief Binary Heap implementation.
+		///\brief Binary heap implementation.
 		#include <vector>
 		#include <utility>
@@ -29,45 +29,41 @@
 		namespace lemon {
-		  ///\ingroup auxdat
+		  /// \ingroup heaps
 		  ///
-		  ///\brief A Binary Heap implementation.
+		  /// \brief Binary heap data structure.
 		  ///
 		  ///This class implements the \e binary \e heap data structure.
+		  /// This class implements the \e binary \e heap data structure.
 		  /// It fully conforms to the \ref concepts::Heap "heap concept".
 		  ///
 		  ///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
 		  /// \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
 		  template <typename PR, typename IM, typename CMP = std::less<PR> >
 		#endif
 		  class BinHeap {
 		  public:
 		  public:
 		    ///\e
 		    /// Type of the item-int map.
 		    typedef IM ItemIntMap;
-		    ///\e
+		    /// Type of the priorities.
 		    typedef PR Prio;
-		    ///\e
+		    /// Type of the items stored in the heap.
 		    typedef typename ItemIntMap::Key Item;
-		    ///\e
+		    /// Type of the item-priority pairs.
 		    typedef std::pair<Item,Prio> Pair;
-		    ///\e
+		    /// Functor type for comparing the priorities.
 		    typedef CMP Compare;
-		    /// \brief Type to represent the items states.
+		    /// \brief Type to represent the states of the items.
 		    ///
 		    /// 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
 		    /// 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.
 		    ///
 		    /// The item-int map must be initialized in such way that it assigns
@@ -84,42 +80,43 @@
 		    ItemIntMap &_iim;
 		  public:
-		    /// \brief The constructor.
 		    /// \brief 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.
 		    /// 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.
 		    explicit BinHeap(ItemIntMap &map) : _iim(map) {}
-		    /// \brief The constructor.
+		    /// \brief 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.
 		    /// 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.
 		    BinHeap(ItemIntMap &map, const Compare &comp)
 		      : _iim(map), _comp(comp) {}
 		    /// The number of items stored in the heap.
+		    /// \brief The number of items stored in the heap.
 		    ///
-		    /// \brief Returns 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 Checks if the heap stores no items.
+		    /// \brief Check if the heap is empty.
 		    ///
-		    /// Returns \c true if and only if the heap stores no items.
+		    /// This function returns \c true if the heap is empty.
 		    bool empty() const { return _data.empty(); }
-		    /// \brief Make empty this heap.
+		    /// \brief Make the heap empty.
 		    ///
 		    /// 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.
 		    /// 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() {
 		      _data.clear();
+		    }
@@ -127,12 +124,12 @@
 		  private:
 		    static int parent(int i) { return (i-1)/2; }
-		    static int second_child(int i) { return 2*i+2; }
+		    static int secondChild(int i) { return 2*i+2; }
 		    bool less(const Pair &p1, const Pair &p2) const {
 		      return _comp(p1.second, p2.second);
+		    }
-		    int bubble_up(int hole, Pair p) {
+		    int bubbleUp(int hole, Pair p) {
 		      int par = parent(hole);
 		      while( hole>0 && less(p,_data[par]) ) {
 		        move(_data[par],hole);
@@ -143,8 +140,8 @@
 		      return hole;
+		    }
 		    int bubble_down(int hole, Pair p, int length) {
 		      int child = second_child(hole);
 		    int bubbleDown(int hole, Pair p, int length) {
 		      int child = secondChild(hole);
 		      while(child < length) {
 		        if( less(_data[child-1], _data[child]) ) {
 		          --child;
@@ -153,7 +150,7 @@
 		          goto ok;
 		        move(_data[child], hole);
 		        hole = child;
-		        child = second_child(hole);
+		        child = secondChild(hole);
+		      }
 		      child--;
 		      if( child<length && less(_data[child], p) ) {
@@ -171,87 +168,91 @@
+		    }
 		  public:
 		    /// \brief Insert a pair of item and priority into the heap.
 		    ///
-		    /// Adds \c p.first to the heap with priority \c p.second.
+		    /// This function inserts \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);
-		      bubble_up(n, p);
+		      bubbleUp(n, p);
+		    }
-		    /// \brief Insert an item into the heap with the given heap.
+		    /// \brief Insert an item into the heap with the given priority.
 		    ///
-		    /// Adds \c i to the heap with priority \c p.
+		    /// This function 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) { push(Pair(i,p)); }
-		    /// \brief Returns the item with minimum priority relative to \c Compare.
+		    /// \brief Return the item having minimum priority.
 		    ///
 		    /// This method returns the item with minimum priority relative to \c
 		    /// Compare.
-		    /// \pre The heap must be nonempty.
+		    /// This function returns the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Item top() const {
 		      return _data[0].first;
+		    }
-		    /// \brief Returns the minimum priority relative to \c Compare.
+		    /// \brief The minimum priority.
 		    ///
 		    /// It returns the minimum priority relative to \c Compare.
 		    /// \pre The heap must be nonempty.
 		    /// This function returns the minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Prio prio() const {
 		      return _data[0].second;
+		    }
-		    /// \brief Deletes the item with minimum priority relative to \c Compare.
+		    /// \brief Remove the item having minimum priority.
 		    ///
 		    /// This method deletes the item with minimum priority relative to \c
 		    /// Compare from the heap.
 		    /// This function removes the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    void pop() {
 		      int n = _data.size()-1;
 		      _iim.set(_data[0].first, POST_HEAP);
 		      if (n > 0) {
-		        bubble_down(0, _data[n], n);
+		        bubbleDown(0, _data[n], n);
+		      }
 		      _data.pop_back();
+		    }
-		    /// \brief Deletes \c i from the heap.
+		    /// \brief Remove the given item 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.
+		    /// 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.
 		    void erase(const Item &i) {
 		      int h = _iim[i];
 		      int n = _data.size()-1;
 		      _iim.set(_data[h].first, POST_HEAP);
 		      if( h < n ) {
 		        if ( bubble_up(h, _data[n]) == h) {
 		          bubble_down(h, _data[n], n);
 		        if ( bubbleUp(h, _data[n]) == h) {
 		          bubbleDown(h, _data[n], n);
+		        }
+		      }
 		      _data.pop_back();
+		    }
 		    /// \brief Returns the priority of \c i.
 		    /// \brief The priority of the given item.
 		    ///
-		    /// This function returns the priority of item \c i.
+		    /// This function returns the priority of the given item.
 		    /// \param i The item.
-		    /// \pre \c i must be in the heap.
+		    /// \pre \e i must be in the heap.
 		    Prio operator[](const Item &i) const {
 		      int idx = _iim[i];
 		      return _data[idx].second;
+		    }
 		    /// \brief \c i gets to the heap with priority \c p independently
 		    /// if \c i was already there.
 		    /// \brief Set the priority of an item or insert it, if it is
 		    /// not stored in the heap.
 		    ///
 		    /// 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.
 		    /// 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 i The item.
 		    /// \param p The priority.
 		    void set(const Item &i, const Prio &p) {
@@ -260,44 +261,42 @@
 		        push(i,p);
+		      }
 		      else if( _comp(p, _data[idx].second) ) {
-		        bubble_up(idx, Pair(i,p));
+		        bubbleUp(idx, Pair(i,p));
+		      }
 		      else {
-		        bubble_down(idx, Pair(i,p), _data.size());
+		        bubbleDown(idx, Pair(i,p), _data.size());
+		      }
+		    }
-		    /// \brief Decreases the priority of \c i to \c p.
+		    /// \brief Decrease the priority of an item to the given value.
 		    ///
-		    /// This method decreases the priority of item \c i to \c p.
+		    /// This function decreases the priority of an item to the given value.
 		    /// \param i The item.
 		    /// \param p The priority.
 		    /// \pre \c i must be stored in the heap with priority at least \c
 		    /// p relative to \c Compare.
 		    /// \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];
-		      bubble_up(idx, Pair(i,p));
+		      bubbleUp(idx, Pair(i,p));
+		    }
-		    /// \brief Increases the priority of \c i to \c p.
+		    /// \brief Increase the priority of an item to the given value.
 		    ///
-		    /// This method sets the priority of item \c i to \c p.
+		    /// This function increases the priority of an item to the given value.
 		    /// \param i The item.
 		    /// \param p The priority.
 		    /// \pre \c i must be stored in the heap with priority at most \c
 		    /// p relative to \c Compare.
 		    /// \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];
-		      bubble_down(idx, Pair(i,p), _data.size());
+		      bubbleDown(idx, Pair(i,p), _data.size());
+		    }
 		    /// \brief Returns if \c item is in, has already been in, or has
 		    /// never been in the heap.
 		    /// \brief Return the state of an item.
 		    ///
 		    /// 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.
 		    /// 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 i The item.
 		    State state(const Item &i) const {
 		      int s = _iim[i];
@@ -306,11 +305,11 @@
 		      return State(s);
+		    }
-		    /// \brief Sets the state of the \c item in the heap.
+		    /// \brief Set the state of an 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.
+		    /// 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.
 		    /// \param i The item.
 		    /// \param st The state. It should not be \c IN_HEAP.
 		    void state(const Item& i, State st) {
@@ -327,12 +326,13 @@
+		      }
+		    }
-		    /// \brief Replaces an item in the heap.
+		    /// \brief Replace 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.
 		    /// 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.
 		    void replace(const Item& i, const Item& j) {
 		      int idx = _iim[i];
 		      _iim.set(i, _iim[j]);

lemon/bits/map_extender.h

Show inline comments

@@ -49,6 +49,8 @@
 		    typedef typename Parent::Reference Reference;
 		    typedef typename Parent::ConstReference ConstReference;
 		    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
 		    class MapIt;
 		    class ConstMapIt;
@@ -191,6 +193,8 @@
 		    typedef typename Parent::Reference Reference;
 		    typedef typename Parent::ConstReference ConstReference;
 		    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
 		    class MapIt;
 		    class ConstMapIt;

lemon/bucket_heap.h

Show inline comments

@@ -19,9 +19,9 @@
 		#ifndef LEMON_BUCKET_HEAP_H
 		#define LEMON_BUCKET_HEAP_H
-		///\ingroup auxdat
+		///\ingroup heaps
 		///\file
-		///\brief Bucket Heap implementation.
+		///\brief Bucket heap implementation.
 		#include <vector>
 		#include <utility>
@@ -53,35 +53,41 @@
+		  }
-		  /// \ingroup auxdat
+		  /// \ingroup heaps
 		  ///
-		  /// \brief A Bucket Heap implementation.
+		  /// \brief Bucket heap data structure.
 		  ///
 		  /// 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.
+		  /// 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.
 		  ///
 		  /// \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.
+		  /// 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
 		  template <typename IM, bool MIN = true>
 		  class BucketHeap {
 		  public:
 		    /// \e
 		    typedef typename IM::Key Item;
-		    /// \e
 		    /// Type of the item-int map.
 		    typedef IM ItemIntMap;
 		    /// Type of the priorities.
 		    typedef int Prio;
 		    /// \e
 		    typedef std::pair<Item, Prio> Pair;
 		    /// \e
 		    typedef IM ItemIntMap;
 		    /// 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:
@@ -89,10 +95,10 @@
 		  public:
-		    /// \brief Type to represent the items states.
+		    /// \brief Type to represent the states of the items.
 		    ///
 		    /// 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
 		    /// 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.
 		    ///
 		    /// The item-int map must be initialized in such way that it assigns
@@ -104,37 +110,39 @@
 		    };
 		  public:
-		    /// \brief The constructor.
 		    /// \brief 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.
 		    /// 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.
 		    explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {}
 		    /// The number of items stored in the heap.
+		    /// \brief The number of items stored in the heap.
 		    ///
-		    /// \brief Returns 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 Checks if the heap stores no items.
+		    /// \brief Check if the heap is empty.
 		    ///
-		    /// Returns \c true if and only if the heap stores no items.
+		    /// This function returns \c true if the heap is empty.
 		    bool empty() const { return _data.empty(); }
-		    /// \brief Make empty this heap.
+		    /// \brief Make the heap empty.
 		    ///
 		    /// 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.
 		    /// 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() {
 		      _data.clear(); _first.clear(); _minimum = 0;
+		    }
 		  private:
-		    void relocate_last(int idx) {
+		    void relocateLast(int idx) {
 		      if (idx + 1 < int(_data.size())) {
 		        _data[idx] = _data.back();
 		        if (_data[idx].prev != -1) {
@@ -174,19 +182,24 @@
+		    }
 		  public:
 		    /// \brief Insert a pair of item and priority into the heap.
 		    ///
-		    /// Adds \c p.first to the heap with priority \c p.second.
+		    /// This function inserts \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);
+		    }
 		    /// \brief Insert an item into the heap with the given priority.
 		    ///
-		    /// Adds \c i to the heap with priority \c p.
+		    /// This function 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) {
 		      int idx = _data.size();
 		      _iim[i] = idx;
@@ -197,10 +210,10 @@
+		      }
+		    }
-		    /// \brief Returns the item with minimum priority.
+		    /// \brief Return the item having minimum priority.
 		    ///
 		    /// This method returns the item with minimum priority.
 		    /// \pre The heap must be nonempty.
 		    /// This function returns the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Item top() const {
 		      while (_first[_minimum] == -1) {
 		        Direction::increase(_minimum);
@@ -208,10 +221,10 @@
 		      return _data[_first[_minimum]].item;
+		    }
-		    /// \brief Returns the minimum priority.
+		    /// \brief The minimum priority.
 		    ///
 		    /// It returns the minimum priority.
 		    /// \pre The heap must be nonempty.
 		    /// This function returns the minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Prio prio() const {
 		      while (_first[_minimum] == -1) {
 		        Direction::increase(_minimum);
@@ -219,9 +232,9 @@
 		      return _minimum;
+		    }
-		    /// \brief Deletes the item with minimum priority.
+		    /// \brief Remove the item having minimum priority.
 		    ///
-		    /// This method deletes the item with minimum priority from the heap.
+		    /// This function removes the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    void pop() {
 		      while (_first[_minimum] == -1) {
@@ -230,37 +243,38 @@
 		      int idx = _first[_minimum];
 		      _iim[_data[idx].item] = -2;
 		      unlace(idx);
-		      relocate_last(idx);
+		      relocateLast(idx);
+		    }
-		    /// \brief Deletes \c i from the heap.
+		    /// \brief Remove the given item 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.
+		    /// 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.
 		    void erase(const Item &i) {
 		      int idx = _iim[i];
 		      _iim[_data[idx].item] = -2;
 		      unlace(idx);
-		      relocate_last(idx);
+		      relocateLast(idx);
+		    }
 		    /// \brief Returns the priority of \c i.
 		    /// \brief The priority of the given item.
 		    ///
 		    /// This function returns the priority of item \c i.
 		    /// \pre \c i must be in the heap.
 		    /// This function returns the priority of the given item.
 		    /// \param i The item.
 		    /// \pre \e i must be in the heap.
 		    Prio operator[](const Item &i) const {
 		      int idx = _iim[i];
 		      return _data[idx].value;
+		    }
 		    /// \brief \c i gets to the heap with priority \c p independently
 		    /// if \c i was already there.
 		    /// \brief Set the priority of an item or insert it, if it is
 		    /// not stored in the heap.
 		    ///
 		    /// 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.
 		    /// 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 i The item.
 		    /// \param p The priority.
 		    void set(const Item &i, const Prio &p) {
@@ -274,13 +288,12 @@
+		      }
+		    }
-		    /// \brief Decreases the priority of \c i to \c p.
+		    /// \brief Decrease the priority of an item to the given value.
 		    ///
 		    /// 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.
+		    /// This function 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.
 		    void decrease(const Item &i, const Prio &p) {
 		      int idx = _iim[i];
 		      unlace(idx);
@@ -291,13 +304,12 @@
 		      lace(idx);
+		    }
-		    /// \brief Increases the priority of \c i to \c p.
+		    /// \brief Increase the priority of an item to the given value.
 		    ///
 		    /// 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.
+		    /// This function 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.
 		    void increase(const Item &i, const Prio &p) {
 		      int idx = _iim[i];
 		      unlace(idx);
@@ -305,13 +317,13 @@
 		      lace(idx);
+		    }
 		    /// \brief Returns if \c item is in, has already been in, or has
 		    /// never been in the heap.
 		    /// \brief Return the state of an item.
 		    ///
 		    /// 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.
 		    /// 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 i The item.
 		    State state(const Item &i) const {
 		      int idx = _iim[i];
@@ -319,11 +331,11 @@
 		      return State(idx);
+		    }
-		    /// \brief Sets the state of the \c item in the heap.
+		    /// \brief Set the state of an 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.
+		    /// 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.
 		    /// \param i The item.
 		    /// \param st The state. It should not be \c IN_HEAP.
 		    void state(const Item& i, State st) {
@@ -359,33 +371,44 @@
 		  }; // class BucketHeap
-		  /// \ingroup auxdat
+		  /// \ingroup heaps
 		  ///
-		  /// \brief A Simplified Bucket Heap implementation.
+		  /// \brief Simplified bucket heap data structure.
 		  ///
 		  /// This class implements a simplified \e bucket \e heap data
 		  /// 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.
 		  /// 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.
 		  ///
 		  /// \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.
+		  /// 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.
 		  ///
 		  /// \sa BucketHeap
 		  template <typename IM, bool MIN = true >
 		  class SimpleBucketHeap {
 		  public:
-		    typedef typename IM::Key Item;
 		    /// Type of the item-int map.
 		    typedef IM ItemIntMap;
 		    /// Type of the priorities.
 		    typedef int Prio;
 		    typedef std::pair<Item, Prio> Pair;
 		    typedef IM ItemIntMap;
 		    /// 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:
@@ -393,10 +416,10 @@
 		  public:
-		    /// \brief Type to represent the items states.
+		    /// \brief Type to represent the states of the items.
 		    ///
 		    /// 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
 		    /// 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.
 		    ///
 		    /// The item-int map must be initialized in such way that it assigns
@@ -409,48 +432,53 @@
 		  public:
-		    /// \brief The constructor.
+		    /// \brief 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.
 		    /// 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.
 		    explicit SimpleBucketHeap(ItemIntMap &map)
 		      : _iim(map), _free(-1), _num(0), _minimum(0) {}
-		    /// \brief Returns the number of items stored in the heap.
+		    /// \brief The number of items stored in the heap.
 		    ///
-		    /// The number of items stored in the heap.
+		    /// This function returns the number of items stored in the heap.
 		    int size() const { return _num; }
-		    /// \brief Checks if the heap stores no items.
+		    /// \brief Check if the heap is empty.
 		    ///
-		    /// Returns \c true if and only if the heap stores no items.
+		    /// This function returns \c true if the heap is empty.
 		    bool empty() const { return _num == 0; }
-		    /// \brief Make empty this heap.
+		    /// \brief Make the heap empty.
 		    ///
 		    /// 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.
 		    /// 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() {
 		      _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0;
+		    }
 		    /// \brief Insert a pair of item and priority into the heap.
 		    ///
-		    /// Adds \c p.first to the heap with priority \c p.second.
+		    /// This function inserts \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);
+		    }
 		    /// \brief Insert an item into the heap with the given priority.
 		    ///
-		    /// Adds \c i to the heap with priority \c p.
+		    /// This function 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) {
 		      int idx;
 		      if (_free == -1) {
@@ -471,10 +499,10 @@
 		      ++_num;
+		    }
-		    /// \brief Returns the item with minimum priority.
+		    /// \brief Return the item having minimum priority.
 		    ///
 		    /// This method returns the item with minimum priority.
 		    /// \pre The heap must be nonempty.
 		    /// This function returns the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Item top() const {
 		      while (_first[_minimum] == -1) {
 		        Direction::increase(_minimum);
@@ -482,10 +510,10 @@
 		      return _data[_first[_minimum]].item;
+		    }
-		    /// \brief Returns the minimum priority.
+		    /// \brief The minimum priority.
 		    ///
 		    /// It returns the minimum priority.
 		    /// \pre The heap must be nonempty.
 		    /// This function returns the minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Prio prio() const {
 		      while (_first[_minimum] == -1) {
 		        Direction::increase(_minimum);
@@ -493,9 +521,9 @@
 		      return _minimum;
+		    }
-		    /// \brief Deletes the item with minimum priority.
+		    /// \brief Remove the item having minimum priority.
 		    ///
-		    /// This method deletes the item with minimum priority from the heap.
+		    /// This function removes the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    void pop() {
 		      while (_first[_minimum] == -1) {
@@ -509,16 +537,15 @@
 		      --_num;
+		    }
-		    /// \brief Returns the priority of \c i.
+		    /// \brief The priority of the given item.
 		    ///
 		    /// 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.
+		    /// 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.
 		    Prio operator[](const Item &i) const {
 		      for (int k = 0; k < _first.size(); ++k) {
+		      for (int k = 0; k < int(_first.size()); ++k) {
 		        int idx = _first[k];
 		        while (idx != -1) {
 		          if (_data[idx].item == i) {
@@ -530,13 +557,13 @@
 		      return -1;
+		    }
 		    /// \brief Returns if \c item is in, has already been in, or has
 		    /// never been in the heap.
 		    /// \brief Return the state of an item.
 		    ///
 		    /// 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.
 		    /// 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 i The item.
 		    State state(const Item &i) const {
 		      int idx = _iim[i];

lemon/circulation.h

Show inline comments

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

lemon/concepts/heap.h

Show inline comments

@@ -16,13 +16,13 @@
+		 *
 		 */
 		#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>
@@ -35,21 +35,27 @@
 		    /// \brief The heap concept.
 		    ///
 		    /// 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.
+		    /// 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.
 		    ///
 		    /// \tparam PR Type of the priority of the items.
 		    /// \tparam IM A read and writable item map with int values, used
 		    /// 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
 		    /// internally to handle the cross references.
-		    /// \tparam Comp A functor class for the ordering of the priorities.
+		    /// \tparam CMP A functor class for comparing the priorities.
 		    /// The default is \c std::less<PR>.
 		#ifdef DOXYGEN
-		    template <typename PR, typename IM, typename Comp = std::less<PR> >
+		    template <typename PR, typename IM, typename CMP>
 		#else
 		    template <typename PR, typename IM>
+		    template <typename PR, typename IM, typename CMP = std::less<PR> >
 		#endif
 		    class Heap {
 		    public:
@@ -64,109 +70,125 @@
 		      /// \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 later two are indifferent
 		      /// from the point of view of the heap, but may be useful for
-		      /// the user.
+		      /// "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.
 		      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 The constructor.
+		      /// \brief Constructor.
 		      ///
-		      /// The 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 every item.
+		      /// \c PRE_HEAP (<tt>-1</tt>) for each 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.
 		      ///
-		      /// Returns the number of items stored in the heap.
+		      /// This function returns the number of items stored in the heap.
 		      int size() const { return 0; }
-		      /// \brief Checks if the heap is empty.
+		      /// \brief Check if the heap is empty.
 		      ///
-		      /// Returns \c true if the heap is empty.
+		      /// This function returns \c true if the heap is empty.
 		      bool empty() const { return false; }
-		      /// \brief Makes the heap empty.
+		      /// \brief Make the heap empty.
 		      ///
 		      /// Makes the heap empty.
 		      void clear();
 		      /// 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 Inserts an item into the heap with the given priority.
+		      /// \brief Insert an item into the heap with the given priority.
 		      ///
-		      /// Inserts the given item into the heap with the given priority.
+		      /// This function 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 Returns the item having minimum priority.
+		      /// \brief Return the item having minimum priority.
 		      ///
-		      /// Returns the item having minimum priority.
+		      /// This function returns the item having minimum priority.
 		      /// \pre The heap must be non-empty.
 		      Item top() const {}
 		      /// \brief The minimum priority.
 		      ///
-		      /// Returns the minimum priority.
+		      /// This function returns the minimum priority.
 		      /// \pre The heap must be non-empty.
 		      Prio prio() const {}
-		      /// \brief Removes the item having minimum priority.
+		      /// \brief Remove the item having minimum priority.
 		      ///
-		      /// Removes the item having minimum priority.
+		      /// This function removes the item having minimum priority.
 		      /// \pre The heap must be non-empty.
 		      void pop() {}
-		      /// \brief Removes an item from the heap.
+		      /// \brief Remove the given item from the heap.
 		      ///
-		      /// Removes the given item from the heap if it is already stored.
+		      /// 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.
 		      void erase(const Item &i) {}
-		      /// \brief The priority of an item.
+		      /// \brief The priority of the given item.
 		      ///
-		      /// Returns the priority of the given item.
+		      /// This function returns the priority of the given item.
 		      /// \param i The item.
-		      /// \pre \c i must be in the heap.
+		      /// \pre \e i must be in the heap.
 		      Prio operator[](const Item &i) const {}
-		      /// \brief Sets the priority of an item or inserts it, if it is
+		      /// \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 with the given priority.
 		      /// already stored in the heap. Otherwise it inserts the given
 		      /// item into the heap with the given priority.
 		      ///
 		      /// \param i The item.
 		      /// \param p The priority.
 		      void set(const Item &i, const Prio &p) {}
-		      /// \brief Decreases the priority of an item to the given value.
+		      /// \brief Decrease the priority of an item to the given value.
 		      ///
-		      /// Decreases the priority of an item to the given value.
+		      /// This function decreases the priority of an item to the given value.
 		      /// \param i The item.
 		      /// \param p The priority.
-		      /// \pre \c i must be stored in the heap with priority at least \c p.
+		      /// \pre \e i must be stored in the heap with priority at least \e p.
 		      void decrease(const Item &i, const Prio &p) {}
-		      /// \brief Increases the priority of an item to the given value.
+		      /// \brief Increase the priority of an item to the given value.
 		      ///
-		      /// Increases the priority of an item to the given value.
+		      /// This function increases the priority of an item to the given value.
 		      /// \param i The item.
 		      /// \param p The priority.
-		      /// \pre \c i must be stored in the heap with priority at most \c p.
+		      /// \pre \e i must be stored in the heap with priority at most \e p.
 		      void increase(const Item &i, const Prio &p) {}
 		      /// \brief Returns if an item is in, has already been in, or has
 		      /// never been in the heap.
 		      /// \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,
@@ -176,11 +198,11 @@
 		      /// \param i The item.
 		      State state(const Item &i) const {}
-		      /// \brief Sets the state of an item in the heap.
+		      /// \brief Set 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.
+		      /// 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.
 		      /// \param i The item.
 		      /// \param st The state. It should not be \c IN_HEAP.
 		      void state(const Item& i, State st) {}

lemon/concepts/maps.h

Show inline comments

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

lemon/dfs.h

Show inline comments

@@ -47,7 +47,7 @@
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the %DFS paths.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a \c PredMap.
@@ -62,7 +62,8 @@
 		    ///The type of the map that indicates which nodes are processed.
 		    ///The type of the map that indicates which nodes are processed.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default it is a NullMap.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a \c ProcessedMap.
@@ -81,7 +82,7 @@
 		    ///The type of the map that indicates which nodes are reached.
 		    ///The type of the map that indicates which nodes are reached.
-		    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+		    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    ///Instantiates a \c ReachedMap.
@@ -96,7 +97,7 @@
 		    ///The type of the map that stores the distances of the nodes.
 		    ///The type of the map that stores the distances of the nodes.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<int> DistMap;
 		    ///Instantiates a \c DistMap.
@@ -224,7 +225,7 @@
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c PredMap type.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
 		      typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
@@ -244,7 +245,7 @@
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c DistMap type.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
 		      typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
@@ -264,7 +265,7 @@
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c ReachedMap type.
-		    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+		    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    template <class T>
 		    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
 		      typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
@@ -284,7 +285,7 @@
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
 		      typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
@@ -411,8 +412,8 @@
 		    ///\name Execution Control
 		    ///The simplest way to execute the DFS algorithm is to use one of the
 		    ///member functions called \ref run(Node) "run()".\n
 		    ///If you need more control on the execution, first you have to call
 		    ///\ref init(), then you can add a source node with \ref addSource()
 		    ///If you need better control on the execution, you have to call
 		    ///\ref init() first, then you can add a source node with \ref addSource()
 		    ///and perform the actual computation with \ref start().
 		    ///This procedure can be repeated if there are nodes that have not
 		    ///been reached.
@@ -669,9 +670,9 @@
 		    ///@{
-		    ///The DFS path to a node.
+		    ///The DFS path to the given node.
-		    ///Returns the DFS path to a node.
+		    ///Returns the DFS path to the given node from the root(s).
 		    ///
 		    ///\warning \c t should be reached from the root(s).
 		    ///
@@ -679,9 +680,9 @@
 		    ///must be called before using this function.
 		    Path path(Node t) const { return Path(*G, *_pred, t); }
-		    ///The distance of a node from the root(s).
+		    ///The distance of the given node from the root(s).
-		    ///Returns the distance of a node from the root(s).
+		    ///Returns the distance of the given node from the root(s).
 		    ///
 		    ///\warning If node \c v is not reached from the root(s), then
 		    ///the return value of this function is undefined.
@@ -690,7 +691,7 @@
 		    ///must be called before using this function.
 		    int dist(Node v) const { return (*_dist)[v]; }
-		    ///Returns the 'previous arc' of the %DFS tree for a node.
+		    ///Returns the 'previous arc' of the %DFS tree for the given node.
 		    ///This function returns the 'previous arc' of the %DFS tree for the
 		    ///node \c v, i.e. it returns the last arc of a %DFS path from a
@@ -698,21 +699,21 @@
 		    ///root(s) or if \c v is a root.
 		    ///
 		    ///The %DFS tree used here is equal to the %DFS tree used in
 		    ///\ref predNode().
+		    ///\ref predNode() and \ref predMap().
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    Arc predArc(Node v) const { return (*_pred)[v];}
 		    ///Returns the 'previous node' of the %DFS tree.
+		    ///Returns the 'previous node' of the %DFS tree for the given node.
 		    ///This function returns the 'previous node' of the %DFS
 		    ///tree for the node \c v, i.e. it returns the last but one node
-		    ///from a %DFS path from a root to \c v. It is \c INVALID
+		    ///of a %DFS path from a root to \c v. It is \c INVALID
 		    ///if \c v is not reached from the root(s) or if \c v is a root.
 		    ///
 		    ///The %DFS tree used here is equal to the %DFS tree used in
 		    ///\ref predArc().
+		    ///\ref predArc() and \ref predMap().
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
@@ -733,13 +734,13 @@
 		    ///predecessor arcs.
 		    ///
 		    ///Returns a const reference to the node map that stores the predecessor
 		    ///arcs, which form the DFS tree.
+		    ///arcs, which form the DFS tree (forest).
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    const PredMap &predMap() const { return *_pred;}
-		    ///Checks if a node is reached from the root(s).
+		    ///Checks if the given node. node is reached from the root(s).
 		    ///Returns \c true if \c v is reached from the root(s).
 		    ///
@@ -765,7 +766,7 @@
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the %DFS paths.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a PredMap.
@@ -780,7 +781,7 @@
 		    ///The type of the map that indicates which nodes are processed.
 		    ///The type of the map that indicates which nodes are processed.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default it is a NullMap.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a ProcessedMap.
@@ -800,7 +801,7 @@
 		    ///The type of the map that indicates which nodes are reached.
 		    ///The type of the map that indicates which nodes are reached.
-		    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+		    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    ///Instantiates a ReachedMap.
@@ -815,7 +816,7 @@
 		    ///The type of the map that stores the distances of the nodes.
 		    ///The type of the map that stores the distances of the nodes.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<int> DistMap;
 		    ///Instantiates a DistMap.
@@ -830,18 +831,14 @@
 		    ///The type of the DFS paths.
 		    ///The type of the DFS paths.
-		    ///It must meet the \ref concepts::Path "Path" concept.
+		    ///It must conform to the \ref concepts::Path "Path" concept.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  /// Default traits class used by DfsWizard
 		  /// To make it easier to use Dfs algorithm
 		  /// we have created a wizard class.
 		  /// This \ref DfsWizard class needs default traits,
 		  /// as well as the \ref Dfs class.
 		  /// The \ref DfsWizardBase is a class to be the default traits of the
 		  /// \ref DfsWizard class.
 		  /// Default traits class used by DfsWizard.
 		  /// \tparam GR The type of the digraph.
 		  template<class GR>
 		  class DfsWizardBase : public DfsWizardDefaultTraits<GR>
+		  {
@@ -869,7 +866,7 @@
 		    public:
 		    /// Constructor.
-		    /// This constructor does not require parameters, therefore it initiates
 		    /// This constructor does not require parameters, it initiates
 		    /// all of the attributes to \c 0.
 		    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
 		                      _dist(0), _path(0), _di(0) {}
@@ -899,7 +896,6 @@
+		  {
 		    typedef TR Base;
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    typedef typename Digraph::Node Node;
@@ -907,16 +903,10 @@
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the DFS paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///\brief The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///\brief The type of the map that indicates which nodes are reached.
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///\brief The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the DFS paths
 		    typedef typename TR::Path Path;
 		  public:
@@ -999,11 +989,12 @@
 		      static PredMap *createPredMap(const Digraph &) { return 0; };
 		      SetPredMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting PredMap object.
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///the predecessor map.
 		    ///
 		    ///\ref named-func-param "Named parameter"
 		    ///for setting PredMap object.
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that stores the predecessor arcs of the nodes.
 		    template<class T>
 		    DfsWizard<SetPredMapBase<T> > predMap(const T &t)
+		    {
@@ -1017,11 +1008,12 @@
 		      static ReachedMap *createReachedMap(const Digraph &) { return 0; };
 		      SetReachedMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting ReachedMap object.
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///the reached map.
 		    ///
 		    /// \ref named-func-param "Named parameter"
 		    ///for setting ReachedMap object.
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that indicates which nodes are reached.
 		    template<class T>
 		    DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
+		    {
@@ -1035,11 +1027,13 @@
 		      static DistMap *createDistMap(const Digraph &) { return 0; };
 		      SetDistMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting DistMap object.
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///the distance map.
 		    ///
 		    /// \ref named-func-param "Named parameter"
 		    ///for setting DistMap object.
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that stores the distances of the nodes calculated
 		    ///by the algorithm.
 		    template<class T>
 		    DfsWizard<SetDistMapBase<T> > distMap(const T &t)
+		    {
@@ -1053,11 +1047,12 @@
 		      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
 		      SetProcessedMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting ProcessedMap object.
 		    ///\brief \ref named-func-param "Named parameter" for setting
 		    ///the processed map.
 		    ///
 		    /// \ref named-func-param "Named parameter"
 		    ///for setting ProcessedMap object.
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that indicates which nodes are processed.
 		    template<class T>
 		    DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
+		    {
@@ -1208,7 +1203,7 @@
 		    /// \brief The type of the map that indicates which nodes are reached.
 		    ///
 		    /// The type of the map that indicates which nodes are reached.
-		    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+		    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    /// \brief Instantiates a ReachedMap.
@@ -1369,8 +1364,8 @@
 		    /// \name Execution Control
 		    /// The simplest way to execute the DFS algorithm is to use one of the
 		    /// member functions called \ref run(Node) "run()".\n
 		    /// If you need more control on the execution, first you have to call
 		    /// \ref init(), then you can add a source node with \ref addSource()
 		    /// If you need better control on the execution, you have to call
 		    /// \ref init() first, then you can add a source node with \ref addSource()
 		    /// and perform the actual computation with \ref start().
 		    /// This procedure can be repeated if there are nodes that have not
 		    /// been reached.
@@ -1620,7 +1615,7 @@
 		    ///@{
-		    /// \brief Checks if a node is reached from the root(s).
+		    /// \brief Checks if the given node is reached from the root(s).
 		    ///
 		    /// Returns \c true if \c v is reached from the root(s).
 		    ///

lemon/dijkstra.h

Show inline comments

@@ -70,9 +70,9 @@
 		    ///The type of the map that stores the arc lengths.
 		    ///The type of the map that stores the arc lengths.
-		    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
+		    ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef LEN LengthMap;
-		    ///The type of the length of the arcs.
+		    ///The type of the arc lengths.
 		    typedef typename LEN::Value Value;
 		    /// Operation traits for %Dijkstra algorithm.
@@ -116,7 +116,7 @@
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a \c PredMap.
@@ -131,7 +131,7 @@
 		    ///The type of the map that indicates which nodes are processed.
 		    ///The type of the map that indicates which nodes are processed.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default it is a NullMap.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a \c ProcessedMap.
@@ -151,7 +151,7 @@
 		    ///The type of the map that stores the distances of the nodes.
 		    ///The type of the map that stores the distances of the nodes.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
 		    ///Instantiates a \c DistMap.
@@ -169,6 +169,10 @@
 		  /// \ingroup shortest_path
 		  ///This class provides an efficient implementation of the %Dijkstra algorithm.
 		  ///
 		  ///The %Dijkstra algorithm solves the single-source shortest path problem
 		  ///when all arc lengths are non-negative. If there are negative lengths,
 		  ///the BellmanFord algorithm should be used instead.
 		  ///
 		  ///The arc lengths are passed to the algorithm using a
 		  ///\ref concepts::ReadMap "ReadMap",
 		  ///so it is easy to change it to any kind of length.
@@ -201,7 +205,7 @@
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
-		    ///The type of the length of the arcs.
+		    ///The type of the arc lengths.
 		    typedef typename TR::LengthMap::Value Value;
 		    ///The type of the map that stores the arc lengths.
 		    typedef typename TR::LengthMap LengthMap;
@@ -304,7 +308,7 @@
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c PredMap type.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetPredMap
 		      : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
@@ -325,7 +329,7 @@
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c DistMap type.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetDistMap
 		      : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
@@ -346,7 +350,7 @@
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetProcessedMap
 		      : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
@@ -443,6 +447,7 @@
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c OperationTraits type.
 		    /// For more information see \ref DijkstraDefaultOperationTraits.
 		    template <class T>
 		    struct SetOperationTraits
 		      : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {
@@ -584,8 +589,8 @@
 		    ///\name Execution Control
 		    ///The simplest way to execute the %Dijkstra algorithm is to use
 		    ///one of the member functions called \ref run(Node) "run()".\n
 		    ///If you need more control on the execution, first you have to call
 		    ///\ref init(), then you can add several source nodes with
 		    ///If you need better control on the execution, you have to call
 		    ///\ref init() first, then you can add several source nodes with
 		    ///\ref addSource(). Finally the actual path computation can be
 		    ///performed with one of the \ref start() functions.
@@ -801,14 +806,14 @@
 		    ///\name Query Functions
 		    ///The results of the %Dijkstra algorithm can be obtained using these
 		    ///functions.\n
-		    ///Either \ref run(Node) "run()" or \ref start() should be called
+		    ///Either \ref run(Node) "run()" or \ref init() should be called
 		    ///before using them.
 		    ///@{
-		    ///The shortest path to a node.
+		    ///The shortest path to the given node.
-		    ///Returns the shortest path to a node.
+		    ///Returns the shortest path to the given node from the root(s).
 		    ///
 		    ///\warning \c t should be reached from the root(s).
 		    ///
@@ -816,9 +821,9 @@
 		    ///must be called before using this function.
 		    Path path(Node t) const { return Path(*G, *_pred, t); }
-		    ///The distance of a node from the root(s).
+		    ///The distance of the given node from the root(s).
-		    ///Returns the distance of a node from the root(s).
+		    ///Returns the distance of the given node from the root(s).
 		    ///
 		    ///\warning If node \c v is not reached from the root(s), then
 		    ///the return value of this function is undefined.
@@ -827,29 +832,31 @@
 		    ///must be called before using this function.
 		    Value dist(Node v) const { return (*_dist)[v]; }
 		    ///Returns the 'previous arc' of the shortest path tree for a node.
 		    ///\brief Returns the 'previous arc' of the shortest path tree for
 		    ///the given node.
 		    ///
 		    ///This function returns the 'previous arc' of the shortest path
 		    ///tree for the node \c v, i.e. it returns the last arc of a
 		    ///shortest path from a root to \c v. It is \c INVALID if \c v
 		    ///is not reached from the root(s) or if \c v is a root.
 		    ///
 		    ///The shortest path tree used here is equal to the shortest path
 		    ///tree used in \ref predNode().
+		    ///tree used in \ref predNode() and \ref predMap().
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    Arc predArc(Node v) const { return (*_pred)[v]; }
 		    ///Returns the 'previous node' of the shortest path tree for a node.
 		    ///\brief Returns the 'previous node' of the shortest path tree for
 		    ///the given node.
 		    ///
 		    ///This function returns the 'previous node' of the shortest path
 		    ///tree for the node \c v, i.e. it returns the last but one node
-		    ///from a shortest path from a root to \c v. It is \c INVALID
+		    ///of a shortest path from a root to \c v. It is \c INVALID
 		    ///if \c v is not reached from the root(s) or if \c v is a root.
 		    ///
 		    ///The shortest path tree used here is equal to the shortest path
 		    ///tree used in \ref predArc().
+		    ///tree used in \ref predArc() and \ref predMap().
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
@@ -870,13 +877,13 @@
 		    ///predecessor arcs.
 		    ///
 		    ///Returns a const reference to the node map that stores the predecessor
 		    ///arcs, which form the shortest path tree.
+		    ///arcs, which form the shortest path tree (forest).
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    const PredMap &predMap() const { return *_pred;}
-		    ///Checks if a node is reached from the root(s).
+		    ///Checks if the given node is reached from the root(s).
 		    ///Returns \c true if \c v is reached from the root(s).
 		    ///
@@ -895,9 +902,9 @@
 		    bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
 		                                          Heap::POST_HEAP; }
-		    ///The current distance of a node from the root(s).
+		    ///The current distance of the given node from the root(s).
-		    ///Returns the current distance of a node from the root(s).
+		    ///Returns the current distance of the given node from the root(s).
 		    ///It may be decreased in the following processes.
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
@@ -924,9 +931,9 @@
 		    ///The type of the map that stores the arc lengths.
 		    ///The type of the map that stores the arc lengths.
-		    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
+		    ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef LEN LengthMap;
-		    ///The type of the length of the arcs.
+		    ///The type of the arc lengths.
 		    typedef typename LEN::Value Value;
 		    /// Operation traits for Dijkstra algorithm.
@@ -973,7 +980,7 @@
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a PredMap.
@@ -988,7 +995,7 @@
 		    ///The type of the map that indicates which nodes are processed.
 		    ///The type of the map that indicates which nodes are processed.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default it is a NullMap.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a ProcessedMap.
@@ -1008,7 +1015,7 @@
 		    ///The type of the map that stores the distances of the nodes.
 		    ///The type of the map that stores the distances of the nodes.
-		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
 		    ///Instantiates a DistMap.
@@ -1023,18 +1030,15 @@
 		    ///The type of the shortest paths.
 		    ///The type of the shortest paths.
-		    ///It must meet the \ref concepts::Path "Path" concept.
+		    ///It must conform to the \ref concepts::Path "Path" concept.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  /// Default traits class used by DijkstraWizard
 		  /// To make it easier to use Dijkstra algorithm
 		  /// we have created a wizard class.
 		  /// This \ref DijkstraWizard class needs default traits,
 		  /// as well as the \ref Dijkstra class.
 		  /// The \ref DijkstraWizardBase is a class to be the default traits of the
 		  /// \ref DijkstraWizard class.
 		  /// Default traits class used by DijkstraWizard.
 		  /// \tparam GR The type of the digraph.
 		  /// \tparam LEN The type of the length map.
 		  template<typename GR, typename LEN>
 		  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN>
+		  {
@@ -1093,7 +1097,6 @@
+		  {
 		    typedef TR Base;
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    typedef typename Digraph::Node Node;
@@ -1101,20 +1104,12 @@
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    ///The type of the map that stores the arc lengths.
 		    typedef typename TR::LengthMap LengthMap;
 		    ///The type of the length of the arcs.
 		    typedef typename LengthMap::Value Value;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the shortest paths
 		    typedef typename TR::Path Path;
 		    ///The heap type used by the dijkstra algorithm.
 		    typedef typename TR::Heap Heap;
 		  public:
@@ -1186,11 +1181,12 @@
 		      static PredMap *createPredMap(const Digraph &) { return 0; };
 		      SetPredMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting PredMap object.
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///the predecessor map.
 		    ///
 		    ///\ref named-func-param "Named parameter"
 		    ///for setting PredMap object.
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that stores the predecessor arcs of the nodes.
 		    template<class T>
 		    DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
+		    {
@@ -1204,11 +1200,13 @@
 		      static DistMap *createDistMap(const Digraph &) { return 0; };
 		      SetDistMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting DistMap object.
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///the distance map.
 		    ///
 		    ///\ref named-func-param "Named parameter"
 		    ///for setting DistMap object.
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that stores the distances of the nodes calculated
 		    ///by the algorithm.
 		    template<class T>
 		    DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
+		    {
@@ -1222,11 +1220,12 @@
 		      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
 		      SetProcessedMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for setting ProcessedMap object.
 		    ///\brief \ref named-func-param "Named parameter" for setting
 		    ///the processed map.
 		    ///
 		    /// \ref named-func-param "Named parameter"
 		    ///for setting ProcessedMap object.
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that indicates which nodes are processed.
 		    template<class T>
 		    DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
+		    {
@@ -1239,6 +1238,7 @@
 		      typedef T Path;
 		      SetPathBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for getting the shortest path to the target node.
 		    ///

lemon/dim2.h

Show inline comments

@@ -21,16 +21,9 @@
 		#include <iostream>
-		///\ingroup misc
+		///\ingroup geomdat
 		///\file
 		///\brief A simple two dimensional vector and a bounding box implementation
 		///
 		/// The class \ref lemon::dim2::Point "dim2::Point" implements
 		/// a two dimensional vector with the usual operations.
 		///
 		/// The class \ref lemon::dim2::Box "dim2::Box" can be used to determine
 		/// the rectangular bounding box of a set of
 		/// \ref lemon::dim2::Point "dim2::Point"'s.
 		namespace lemon {
@@ -40,7 +33,7 @@
 		  ///tools for handling two dimensional coordinates
 		  namespace dim2 {
-		  /// \addtogroup misc
+		  /// \addtogroup geomdat
 		  /// @{
 		  /// Two dimensional vector (plain vector)

lemon/fib_heap.h

Show inline comments

@@ -20,53 +20,49 @@
 		#define LEMON_FIB_HEAP_H
 		///\file
 		///\ingroup auxdat
 		///\brief Fibonacci Heap implementation.
 		///\ingroup heaps
 		///\brief Fibonacci heap implementation.
 		#include <vector>
 		#include <utility>
 		#include <functional>
 		#include <lemon/math.h>
 		namespace lemon {
-		  /// \ingroup auxdat
+		  /// \ingroup heaps
 		  ///
-		  ///\brief Fibonacci Heap.
+		  /// \brief Fibonacci heap data structure.
 		  ///
 		  ///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.
+		  /// This class implements the \e Fibonacci \e heap data structure.
 		  /// It fully conforms to the \ref concepts::Heap "heap concept".
 		  ///
 		  ///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".
+		  /// 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".
 		  ///
 		  ///\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
 		  /// \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 PRIO, typename IM, typename CMP>
+		  template <typename PR, typename IM, typename CMP>
 		#else
-		  template <typename PRIO, typename IM, typename CMP = std::less<PRIO> >
+		  template <typename PR, typename IM, typename CMP = std::less<PR> >
 		#endif
 		  class FibHeap {
 		  public:
-		    ///\e
 		    /// Type of the item-int map.
 		    typedef IM ItemIntMap;
 		    ///\e
 		    typedef PRIO Prio;
-		    ///\e
+		    /// Type of the priorities.
 		    typedef PR Prio;
 		    /// Type of the items stored in the heap.
 		    typedef typename ItemIntMap::Key Item;
-		    ///\e
+		    /// Type of the item-priority pairs.
 		    typedef std::pair<Item,Prio> Pair;
-		    ///\e
+		    /// Functor type for comparing the priorities.
 		    typedef CMP Compare;
 		  private:
@@ -80,10 +76,10 @@
 		  public:
-		    /// \brief Type to represent the items states.
+		    /// \brief Type to represent the states of the items.
 		    ///
 		    /// 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
 		    /// 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.
 		    ///
 		    /// The item-int map must be initialized in such way that it assigns
@@ -94,60 +90,54 @@
 		      POST_HEAP = -2  ///< = -2.
 		    };
-		    /// \brief The constructor
+		    /// \brief Constructor.
 		    ///
 		    /// \c map should be given to the constructor, since it is
 		    ///   used internally to handle the cross references.
 		    /// 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.
 		    explicit FibHeap(ItemIntMap &map)
 		      : _minimum(0), _iim(map), _num() {}
-		    /// \brief The constructor
+		    /// \brief 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.
+		    /// 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.
 		    FibHeap(ItemIntMap &map, const Compare &comp)
 		      : _minimum(0), _iim(map), _comp(comp), _num() {}
 		    /// \brief The number of items stored in the heap.
 		    ///
-		    /// Returns the number of items stored in the heap.
+		    /// This function returns the number of items stored in the heap.
 		    int size() const { return _num; }
-		    /// \brief Checks if the heap stores no items.
+		    /// \brief Check if the heap is empty.
 		    ///
-		    ///   Returns \c true if and only if the heap stores no items.
+		    /// This function returns \c true if the heap is empty.
 		    bool empty() const { return _num==0; }
-		    /// \brief Make empty this heap.
+		    /// \brief Make the heap empty.
 		    ///
 		    /// 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.
 		    /// 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() {
 		      _data.clear(); _minimum = 0; _num = 0;
+		    }
 		    /// \brief \c item gets to the heap with priority \c value independently
 		    /// if \c item was already there.
 		    /// \brief Insert an item into the heap with the given priority.
 		    ///
 		    /// 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) {
 		    /// 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) {
 		      int i=_iim[item];
 		      if ( i < 0 ) {
 		        int s=_data.size();
@@ -168,47 +158,37 @@
 		        _data[i].right_neighbor=_data[_minimum].right_neighbor;
 		        _data[_minimum].right_neighbor=i;
 		        _data[i].left_neighbor=_minimum;
-		        if ( _comp( value, _data[_minimum].prio) ) _minimum=i;
+		        if ( _comp( prio, _data[_minimum].prio) ) _minimum=i;
 		      } else {
 		        _data[i].right_neighbor=_data[i].left_neighbor=i;
 		        _minimum=i;
+		      }
-		      _data[i].prio=value;
+		      _data[i].prio=prio;
 		      ++_num;
+		    }
-		    /// \brief Returns the item with minimum priority relative to \c Compare.
+		    /// \brief Return the item having minimum priority.
 		    ///
 		    /// This method returns the item with minimum priority relative to \c
 		    /// Compare.
-		    /// \pre The heap must be nonempty.
+		    /// This function returns the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Item top() const { return _data[_minimum].name; }
-		    /// \brief Returns the minimum priority relative to \c Compare.
+		    /// \brief The minimum priority.
 		    ///
 		    /// It returns the minimum priority relative to \c Compare.
 		    /// \pre The heap must be nonempty.
-		    const Prio& prio() const { return _data[_minimum].prio; }
+		    /// This function returns the minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Prio prio() const { return _data[_minimum].prio; }
-		    /// \brief Returns the priority of \c item.
+		    /// \brief Remove the item having minimum priority.
 		    ///
 		    /// 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.
 		    /// This function removes the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    void pop() {
 		      /*The first case is that there are only one root.*/
 		      if ( _data[_minimum].left_neighbor==_minimum ) {
 		        _data[_minimum].in=false;
 		        if ( _data[_minimum].degree!=0 ) {
-		          makeroot(_data[_minimum].child);
+		          makeRoot(_data[_minimum].child);
 		          _minimum=_data[_minimum].child;
 		          balance();
+		        }
@@ -221,7 +201,7 @@
 		          int child=_data[_minimum].child;
 		          int last_child=_data[child].left_neighbor;
-		          makeroot(child);
+		          makeRoot(child);
 		          _data[left].right_neighbor=child;
 		          _data[child].left_neighbor=left;
@@ -234,10 +214,12 @@
 		      --_num;
+		    }
-		    /// \brief Deletes \c item from the heap.
+		    /// \brief Remove the given 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.
 		    /// 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.
 		    void erase (const Item& item) {
 		      int i=_iim[item];
@@ -252,43 +234,68 @@
+		      }
+		    }
-		    /// \brief Decreases the priority of \c item to \c value.
+		    /// \brief The priority of the given item.
 		    ///
 		    /// 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) {
 		    /// 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) {
 		      int i=_iim[item];
-		      _data[i].prio=value;
+		      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;
 		      int p=_data[i].parent;
-		      if ( p!=-1 && _comp(value, _data[p].prio) ) {
+		      if ( p!=-1 && _comp(prio, _data[p].prio) ) {
 		        cut(i,p);
 		        cascade(p);
+		      }
-		      if ( _comp(value, _data[_minimum].prio) ) _minimum=i;
+		      if ( _comp(prio, _data[_minimum].prio) ) _minimum=i;
+		    }
-		    /// \brief Increases the priority of \c item to \c value.
+		    /// \brief Increase the priority of an item to the given 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) {
 		    /// 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) {
 		      erase(item);
-		      push(item, value);
+		      push(item, prio);
+		    }
 		    /// \brief Returns if \c item is in, has already been in, or has never
-		    /// been in the heap.
+		    /// \brief Return the state of an item.
 		    ///
 		    /// 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.
 		    /// 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.
 		    State state(const Item &item) const {
 		      int i=_iim[item];
 		      if( i>=0 ) {
@@ -298,11 +305,11 @@
 		      return State(i);
+		    }
-		    /// \brief Sets the state of the \c item in the heap.
+		    /// \brief Set the state of an 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.
+		    /// 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.
 		    /// \param i The item.
 		    /// \param st The state. It should not be \c IN_HEAP.
 		    void state(const Item& i, State st) {
@@ -365,7 +372,7 @@
 		      } while ( s != m );
+		    }
-		    void makeroot(int c) {
+		    void makeRoot(int c) {
 		      int s=c;
 		      do {
 		        _data[s].parent=-1;

lemon/gomory_hu.h

Show inline comments

@@ -359,10 +359,10 @@
 		    /// This example counts the nodes in the minimum cut separating \c s from
 		    /// \c t.
 		    /// \code
-		    /// GomoruHu<Graph> gom(g, capacities);
+		    /// GomoryHu<Graph> gom(g, capacities);
 		    /// gom.run();
 		    /// int cnt=0;
-		    /// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
+		    /// for(GomoryHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
 		    /// \endcode
 		    class MinCutNodeIt
+		    {
@@ -456,10 +456,10 @@
 		    /// This example computes the value of the minimum cut separating \c s from
 		    /// \c t.
 		    /// \code
-		    /// GomoruHu<Graph> gom(g, capacities);
+		    /// GomoryHu<Graph> gom(g, capacities);
 		    /// gom.run();
 		    /// int value=0;
-		    /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
+		    /// for(GomoryHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
 		    ///   value+=capacities[e];
 		    /// \endcode
 		    /// The result will be the same as the value returned by

lemon/maps.h

Show inline comments

@@ -22,6 +22,7 @@
 		#include <iterator>
 		#include <functional>
 		#include <vector>
 		#include <map>
 		#include <lemon/core.h>
@@ -29,8 +30,6 @@
 		///\ingroup maps
 		///\brief Miscellaneous property maps
 		#include <map>
 		namespace lemon {
 		  /// \addtogroup maps
@@ -57,7 +56,7 @@
 		  /// its type definitions, or if you have to provide a writable map,
 		  /// but data written to it is not required (i.e. it will be sent to
 		  /// <tt>/dev/null</tt>).
 		  /// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+		  /// It conforms to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		  ///
 		  /// \sa ConstMap
 		  template<typename K, typename V>
@@ -90,7 +89,7 @@
 		  /// value to each key.
 		  ///
 		  /// In other aspects it is equivalent to \c NullMap.
 		  /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
+		  /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap"
 		  /// concept, but it absorbs the data written to it.
 		  ///
 		  /// The simplest way of using this map is through the constMap()
@@ -159,7 +158,7 @@
 		  /// value to each key.
 		  ///
 		  /// In other aspects it is equivalent to \c NullMap.
 		  /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
+		  /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap"
 		  /// concept, but it absorbs the data written to it.
 		  ///
 		  /// The simplest way of using this map is through the constMap()
@@ -233,7 +232,7 @@
 		  /// values to integer keys from the range <tt>[0..size-1]</tt>.
 		  /// It can be used with some data structures, for example
 		  /// \c UnionFind, \c BinHeap, when the used items are small
 		  /// integers. This map conforms the \ref concepts::ReferenceMap
+		  /// integers. This map conforms to the \ref concepts::ReferenceMap
 		  /// "ReferenceMap" concept.
 		  ///
 		  /// The simplest way of using this map is through the rangeMap()
@@ -341,7 +340,7 @@
 		  /// that you can specify a default value for the keys that are not
 		  /// stored actually. This value can be different from the default
 		  /// contructed value (i.e. \c %Value()).
 		  /// This type conforms the \ref concepts::ReferenceMap "ReferenceMap"
+		  /// This type conforms to the \ref concepts::ReferenceMap "ReferenceMap"
 		  /// concept.
 		  ///
 		  /// This map is useful if a default value should be assigned to most of
@@ -707,7 +706,7 @@
 		  /// "readable map" to another type using the default conversion.
 		  /// The \c Key type of it is inherited from \c M and the \c Value
 		  /// type is \c V.
 		  /// This type conforms the \ref concepts::ReadMap "ReadMap" concept.
+		  /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
 		  ///
 		  /// The simplest way of using this map is through the convertMap()
 		  /// function.
@@ -1790,11 +1789,11 @@
 		  /// order of Dfs algorithm, as the following examples show.
 		  /// \code
 		  ///   std::vector<Node> v;
-		  ///   dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run();
+		  ///   dfs(g).processedMap(loggerBoolMap(std::back_inserter(v))).run(s);
 		  /// \endcode
 		  /// \code
 		  ///   std::vector<Node> v(countNodes(g));
-		  ///   dfs(g,s).processedMap(loggerBoolMap(v.begin())).run();
+		  ///   dfs(g).processedMap(loggerBoolMap(v.begin())).run(s);
 		  /// \endcode
 		  ///
 		  /// \note The container of the iterator must contain enough space
@@ -1818,7 +1817,7 @@
 		  /// \brief Provides an immutable and unique id for each item in a graph.
 		  ///
 		  /// 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
 		  ///    delete other nodes).
@@ -1826,7 +1825,7 @@
 		  /// Using this map you get access (i.e. can read) the inner id values of
 		  /// the items stored in the graph, which is returned by the \c id()
 		  /// function of the graph. This map can be inverted with its member
 		  /// class \c InverseMap or with the \c operator() member.
+		  /// class \c InverseMap or with the \c operator()() member.
 		  ///
 		  /// \tparam GR The graph type.
 		  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
@@ -1866,9 +1865,11 @@
 		  public:
-		    /// \brief This class represents the inverse of its owner (IdMap).
+		    /// \brief The inverse map type of IdMap.
 		    ///
-		    /// This class represents the inverse of its owner (IdMap).
+		    /// The inverse map type of IdMap. The subscript operator gives back
 		    /// an item by its id.
 		    /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
 		    /// \see inverse()
 		    class InverseMap {
 		    public:
@@ -1883,9 +1884,9 @@
 		      /// Constructor for creating an id-to-item map.
 		      explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
-		      /// \brief Gives back the given item from its id.
+		      /// \brief Gives back an item by its id.
 		      ///
-		      /// Gives back the given item from its id.
+		      /// Gives back an item by its id.
 		      Item operator[](int id) const { return _graph->fromId(id, Item());}
 		    private:
@@ -1898,14 +1899,31 @@
 		    InverseMap inverse() const { return InverseMap(*_graph);}
 		  };
 		  /// \brief Returns an \c IdMap class.
 		  ///
 		  /// This function just returns an \c IdMap class.
 		  /// \relates IdMap
 		  template <typename K, typename GR>
 		  inline IdMap<GR, K> idMap(const GR& graph) {
 		    return IdMap<GR, K>(graph);
+		  }
 		  /// \brief General cross reference graph map type.
 		  /// This class provides simple invertable graph maps.
 		  /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
 		  /// and if a key is set to a new value, then stores it in the inverse map.
 		  /// The values of the map can be accessed
 		  /// with stl compatible forward iterator.
 		  /// The graph items can be accessed by their values either using
 		  /// \c InverseMap or \c operator()(), and the values of the map can be
 		  /// accessed with an STL compatible forward iterator (\c ValueIt).
 		  ///
 		  /// This map is intended to be used when all associated values are
 		  /// different (the map is actually invertable) or there are only a few
 		  /// items with the same value.
 		  /// Otherwise consider to use \c IterableValueMap, which is more
 		  /// suitable and more efficient for such cases. It provides iterators
 		  /// to traverse the items with the same associated value, however
 		  /// it does not have \c InverseMap.
 		  ///
 		  /// This type is not reference map, so it cannot be modified with
 		  /// the subscript operator.
@@ -1946,56 +1964,66 @@
 		    /// \brief Forward iterator for values.
 		    ///
-		    /// This iterator is an stl compatible forward
+		    /// This iterator is an STL compatible forward
 		    /// iterator on the values of the map. The values can
 		    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
 		    /// They are considered with multiplicity, so each value is
 		    /// traversed for each item it is assigned to.
-		    class ValueIterator
+		    class ValueIt
 		      : public std::iterator<std::forward_iterator_tag, Value> {
 		      friend class CrossRefMap;
 		    private:
-		      ValueIterator(typename Container::const_iterator _it)
+		      ValueIt(typename Container::const_iterator _it)
 		        : it(_it) {}
 		    public:
 		      ValueIterator() {}
 		      ValueIterator& operator++() { ++it; return *this; }
 		      ValueIterator operator++(int) {
-		        ValueIterator tmp(*this);
+		      /// Constructor
 		      ValueIt() {}
 		      /// \e
 		      ValueIt& operator++() { ++it; return *this; }
 		      /// \e
 		      ValueIt operator++(int) {
 		        ValueIt tmp(*this);
 		        operator++();
 		        return tmp;
+		      }
 		      /// \e
 		      const Value& operator*() const { return it->first; }
 		      /// \e
 		      const Value* operator->() const { return &(it->first); }
 		      bool operator==(ValueIterator jt) const { return it == jt.it; }
 		      bool operator!=(ValueIterator jt) const { return it != jt.it; }
 		      /// \e
 		      bool operator==(ValueIt jt) const { return it == jt.it; }
 		      /// \e
 		      bool operator!=(ValueIt jt) const { return it != jt.it; }
 		    private:
 		      typename Container::const_iterator it;
 		    };
 		    /// Alias for \c ValueIt
 		    typedef ValueIt ValueIterator;
 		    /// \brief Returns an iterator to the first value.
 		    ///
-		    /// Returns an stl compatible iterator to the
+		    /// Returns an STL compatible iterator to the
 		    /// first value of the map. The values of the
 		    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
 		    /// range.
 		    ValueIterator beginValue() const {
 		      return ValueIterator(_inv_map.begin());
 		    ValueIt beginValue() const {
 		      return ValueIt(_inv_map.begin());
+		    }
 		    /// \brief Returns an iterator after the last value.
 		    ///
-		    /// Returns an stl compatible iterator after the
+		    /// Returns an STL compatible iterator after the
 		    /// last value of the map. The values of the
 		    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
 		    /// range.
 		    ValueIterator endValue() const {
 		      return ValueIterator(_inv_map.end());
 		    ValueIt endValue() const {
 		      return ValueIt(_inv_map.end());
+		    }
 		    /// \brief Sets the value associated with the given key.
@@ -2033,6 +2061,14 @@
 		      typename Container::const_iterator it = _inv_map.find(val);
 		      return it != _inv_map.end() ? it->second : INVALID;
+		    }
 		    /// \brief Returns the number of items with the given value.
 		    ///
 		    /// This function returns the number of items with the given value
 		    /// associated with it.
 		    int count(const Value &val) const {
 		      return _inv_map.count(val);
+		    }
 		  protected:
@@ -2083,10 +2119,12 @@
 		  public:
 		    /// \brief The inverse map type.
+		    /// \brief The inverse map type of CrossRefMap.
 		    ///
 		    /// The inverse of this map. The subscript operator of the map
 		    /// gives back the item that was last assigned to the value.
 		    /// The inverse map type of CrossRefMap. The subscript operator gives
 		    /// back an item by its value.
 		    /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
 		    /// \see inverse()
 		    class InverseMap {
 		    public:
 		      /// \brief Constructor
@@ -2113,20 +2151,20 @@
 		      const CrossRefMap& _inverted;
 		    };
-		    /// \brief It gives back the read-only inverse map.
+		    /// \brief Gives back the inverse of the map.
 		    ///
-		    /// It gives back the read-only inverse map.
+		    /// Gives back the inverse of the CrossRefMap.
 		    InverseMap inverse() const {
 		      return InverseMap(*this);
+		    }
 		  };
-		  /// \brief Provides continuous and unique ID for the
+		  /// \brief Provides continuous and unique id for the
 		  /// items of a graph.
 		  ///
 		  /// RangeIdMap provides a unique and continuous
-		  /// ID for each item of a given type (\c Node, \c Arc or
+		  /// id for each item of a given type (\c Node, \c Arc or
 		  /// \c Edge) in a graph. This id is
 		  ///  - \b unique: different items get different ids,
 		  ///  - \b continuous: the range of the ids is the set of integers
@@ -2137,7 +2175,7 @@
 		  /// Thus this id is not (necessarily) the same as what can get using
 		  /// the \c id() function of the graph or \ref IdMap.
 		  /// This map can be inverted with its member class \c InverseMap,
 		  /// or with the \c operator() member.
+		  /// or with the \c operator()() member.
 		  ///
 		  /// \tparam GR The graph type.
 		  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
@@ -2265,16 +2303,16 @@
 		      _inv_map[pi] = q;
+		    }
-		    /// \brief Gives back the \e RangeId of the item
+		    /// \brief Gives back the \e range \e id of the item
 		    ///
-		    /// Gives back the \e RangeId of the item.
+		    /// Gives back the \e range \e id of the item.
 		    int operator[](const Item& item) const {
 		      return Map::operator[](item);
+		    }
 		    /// \brief Gives back the item belonging to a \e RangeId
 		    ///
-		    /// Gives back the item belonging to a \e RangeId.
+		    /// \brief Gives back the item belonging to a \e range \e id
 		    ///
 		    /// Gives back the item belonging to the given \e range \e id.
 		    Item operator()(int id) const {
 		      return _inv_map[id];
+		    }
@@ -2288,7 +2326,9 @@
 		    /// \brief The inverse map type of RangeIdMap.
 		    ///
 		    /// The inverse map type of RangeIdMap.
+		    /// The inverse map type of RangeIdMap. The subscript operator gives
 		    /// back an item by its \e range \e id.
 		    /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
 		    class InverseMap {
 		    public:
 		      /// \brief Constructor
@@ -2306,7 +2346,7 @@
 		      /// \brief Subscript operator.
 		      ///
 		      /// Subscript operator. It gives back the item
-		      /// that the descriptor currently belongs to.
+		      /// that the given \e range \e id currently belongs to.
 		      Value operator[](const Key& key) const {
 		        return _inverted(key);
+		      }
@@ -2324,12 +2364,932 @@
 		    /// \brief Gives back the inverse of the map.
 		    ///
-		    /// Gives back the inverse of the map.
+		    /// Gives back the inverse of the RangeIdMap.
 		    const InverseMap inverse() const {
 		      return InverseMap(*this);
+		    }
 		  };
 		  /// \brief Returns a \c RangeIdMap class.
 		  ///
 		  /// This function just returns an \c RangeIdMap class.
 		  /// \relates RangeIdMap
 		  template <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;
 		  };
 		  /// \brief Map of the source nodes of arcs in a digraph.
 		  ///
 		  /// SourceMap provides access for the source node of each arc in a digraph,
@@ -2340,9 +3300,9 @@
 		  class SourceMap {
 		  public:
-		    ///\e
+		    /// The key type (the \c Arc type of the digraph).
 		    typedef typename GR::Arc Key;
-		    ///\e
+		    /// The value type (the \c Node type of the digraph).
 		    typedef typename GR::Node Value;
 		    /// \brief Constructor
@@ -2381,9 +3341,9 @@
 		  class TargetMap {
 		  public:
-		    ///\e
+		    /// The key type (the \c Arc type of the digraph).
 		    typedef typename GR::Arc Key;
-		    ///\e
+		    /// The value type (the \c Node type of the digraph).
 		    typedef typename GR::Node Value;
 		    /// \brief Constructor
@@ -2423,8 +3383,10 @@
 		  class ForwardMap {
 		  public:
 		    /// The key type (the \c Edge type of the digraph).
 		    typedef typename GR::Edge Key;
 		    /// The value type (the \c Arc type of the digraph).
 		    typedef typename GR::Arc Value;
 		    typedef typename GR::Edge Key;
 		    /// \brief Constructor
 		    ///
@@ -2463,8 +3425,10 @@
 		  class BackwardMap {
 		  public:
 		    /// The key type (the \c Edge type of the digraph).
 		    typedef typename GR::Edge Key;
 		    /// The value type (the \c Arc type of the digraph).
 		    typedef typename GR::Arc Value;
 		    typedef typename GR::Edge Key;
 		    /// \brief Constructor
 		    ///
@@ -2499,7 +3463,7 @@
 		  /// in constant time. On the other hand, the values are updated automatically
 		  /// 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
 		  /// features are used. For example the functions
@@ -2515,7 +3479,7 @@
 		      ::ItemNotifier::ObserverBase {
 		  public:
 		    /// The graph type of InDegMap
 		    typedef GR Graph;
 		    typedef GR Digraph;
@@ -2629,7 +3593,7 @@
 		  /// in constant time. On the other hand, the values are updated automatically
 		  /// 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
 		  /// features are used. For example the functions

lemon/min_cost_arborescence.h

Show inline comments

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

lemon/network_simplex.h

Show inline comments

@@ -161,8 +161,6 @@
 		    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		    typedef std::vector<Arc> ArcVector;
 		    typedef std::vector<Node> NodeVector;
 		    typedef std::vector<int> IntVector;
 		    typedef std::vector<bool> BoolVector;
 		    typedef std::vector<Value> ValueVector;
@@ -364,33 +362,32 @@
 		      bool findEnteringArc() {
 		        Cost c, min = 0;
 		        int cnt = _block_size;
-		        int e, min_arc = _next_arc;
 		        int e;
 		        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;
-		            min_arc = e;
+		            _in_arc = e;
+		          }
 		          if (--cnt == 0) {
-		            if (min < 0) break;
+		            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;
+		            }
+		        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) return false;
-		        _in_arc = min_arc;
 		      search_end:
 		        _next_arc = e;
 		        return true;
+		      }
@@ -428,7 +425,7 @@
 		        _next_arc(0)
+		      {
 		        // The main parameters of the pivot rule
-		        const double LIST_LENGTH_FACTOR = 1.0;
+		        const double LIST_LENGTH_FACTOR = 0.25;
 		        const int MIN_LIST_LENGTH = 10;
 		        const double MINOR_LIMIT_FACTOR = 0.1;
 		        const int MIN_MINOR_LIMIT = 3;
@@ -445,7 +442,7 @@
 		      /// Find next entering arc
 		      bool findEnteringArc() {
 		        Cost min, c;
-		        int e, min_arc = _next_arc;
 		        int e;
 		        if (_curr_length > 0 && _minor_count < _minor_limit) {
 		          // Minor iteration: select the best eligible arc from the
 		          // current candidate list
@@ -456,16 +453,13 @@
 		            c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
 		            if (c < min) {
 		              min = c;
-		              min_arc = e;
+		              _in_arc = e;
+		            }
 		            if (c >= 0) {
+		            else if (c >= 0) {
 		              _candidates[i--] = _candidates[--_curr_length];
+		            }
+		          }
 		          if (min < 0) {
 		            _in_arc = min_arc;
 		            return true;
+		          }
 		          if (min < 0) return true;
+		        }
 		        // Major iteration: build a new candidate list
@@ -477,27 +471,26 @@
 		            _candidates[_curr_length++] = e;
 		            if (c < min) {
 		              min = c;
-		              min_arc = e;
+		              _in_arc = e;
+		            }
-		            if (_curr_length == _list_length) break;
+		            if (_curr_length == _list_length) goto search_end;
+		          }
+		        }
 		        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;
 		        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) goto search_end;
+		          }
+		        }
 		        if (_curr_length == 0) return false;
 		      search_end:
 		        _minor_count = 1;
 		        _in_arc = min_arc;
 		        _next_arc = e;
 		        return true;
+		      }
@@ -549,7 +542,7 @@
 		        _next_arc(0), _cand_cost(ns._search_arc_num), _sort_func(_cand_cost)
+		      {
 		        // The main parameters of the pivot rule
-		        const double BLOCK_SIZE_FACTOR = 1.5;
+		        const double BLOCK_SIZE_FACTOR = 1.0;
 		        const int MIN_BLOCK_SIZE = 10;
 		        const double HEAD_LENGTH_FACTOR = 0.1;
 		        const int MIN_HEAD_LENGTH = 3;
@@ -578,39 +571,35 @@
 		        // Extend the list
 		        int cnt = _block_size;
 		        int last_arc = 0;
 		        int limit = _head_length;
-		        for (int e = _next_arc; e < _search_arc_num; ++e) {
 		        for (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) break;
+		            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;
+		            }
+		        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 == 0) return false;
-		        _next_arc = last_arc + 1;
 		      search_end:
 		        // Make heap of the candidate list (approximating a partial sort)
 		        make_heap( _candidates.begin(), _candidates.begin() + _curr_length,
@@ -618,6 +607,7 @@
 		        // Pop the first element of the heap
 		        _in_arc = _candidates[0];
 		        _next_arc = e;
 		        pop_heap( _candidates.begin(), _candidates.begin() + _curr_length,
 		                  _sort_func );
 		        _curr_length = std::min(_head_length, _curr_length - 1);
@@ -633,7 +623,11 @@
 		    /// The constructor of the class.
 		    ///
 		    /// \param graph The digraph the algorithm runs on.
-		    NetworkSimplex(const GR& graph) :
+		    /// \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) :
 		      _graph(graph), _node_id(graph), _arc_id(graph),
 		      INF(std::numeric_limits<Value>::has_infinity ?
 		          std::numeric_limits<Value>::infinity() :
@@ -671,31 +665,33 @@
 		      _last_succ.resize(all_node_num);
 		      _state.resize(max_arc_num);
-		      // Copy the graph (store the arcs in a mixed order)
 		      // Copy the graph
 		      int i = 0;
 		      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
 		        _node_id[n] = i;
+		      }
 		      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;
+		      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)];
+		        }
+		      }
 		      // 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;
+		      // Reset parameters
 		      reset();
+		    }
 		    /// \name Parameters
@@ -768,7 +764,6 @@
 		    /// This function sets the supply values of the nodes.
 		    /// 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.
 		    /// Its \c Value type must be convertible to the \c Value type
@@ -789,7 +784,6 @@
 		    /// and the required flow value.
 		    /// 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()
 		    /// with such a map in which \c k is assigned to \c s, \c -k is

Changeset was too big and was cut off... Show full diff

0 comments (0 inline)

RhodeCode

Login to your account

Changeset was too big and was cut off... Show full diff

Changeset was too big and was cut off... Show full diff