LEMON/LEMON-official Changeset - r764:684964884a2e

Repositories » LEMON » LEMON-official

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

Changeset - r764:684964884a2e

« 762:ece801
« 763:f47b6c

766:ba79e8 »

r764:684964884a2e

Fri, 25 Sep 2009 09:13:03

[Not Reviewed]

0 comments (0 inline)

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

Merge

0 22 9

merge default

4 files changed with 6144 insertions and 314 deletions:

lemon/bellman_ford.h

1100

lemon/binom_heap.h

445

lemon/bucket_heap.h

594

lemon/fib_heap.h

475

lemon/fourary_heap.h

342

lemon/kary_heap.h

352

lemon/pairing_heap.h

474

lemon/radix_heap.h

438

test/bellman_ford_test.cc

283

doc/groups.dox

100

lemon/Makefile.am

lemon/bfs.h

lemon/bin_heap.h

112

lemon/bits/edge_set_extender.h

lemon/bits/graph_extender.h

lemon/circulation.h

lemon/concepts/heap.h

lemon/dfs.h

lemon/dijkstra.h

lemon/dim2.h

lemon/gomory_hu.h

lemon/maps.h

943

lemon/min_cost_arborescence.h

lemon/preflow.h

test/CMakeLists.txt

test/Makefile.am

test/circulation_test.cc

test/heap_test.cc

test/maps_test.cc

222

test/preflow_test.cc

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

↑ 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/bucket_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_BUCKET_HEAP_H
 		#define LEMON_BUCKET_HEAP_H
 		///\ingroup heaps
 		///\file
 		///\brief Bucket heap implementation.
 		#include <vector>
 		#include <utility>
 		#include <functional>
 		namespace lemon {
 		  namespace _bucket_heap_bits {
 		    template <bool MIN>
 		    struct DirectionTraits {
 		      static bool less(int left, int right) {
 		        return left < right;
+		      }
 		      static void increase(int& value) {
 		        ++value;
+		      }
 		    };
 		    template <>
 		    struct DirectionTraits<false> {
 		      static bool less(int left, int right) {
 		        return left > right;
+		      }
 		      static void increase(int& value) {
 		        --value;
+		      }
 		    };
+		  }
 		  /// \ingroup heaps
 		  ///
 		  /// \brief Bucket heap data structure.
 		  ///
 		  /// This class implements the \e bucket \e heap data structure.
 		  /// It practically conforms to the \ref concepts::Heap "heap concept",
 		  /// but it has some limitations.
 		  ///
 		  /// The bucket heap is a very simple structure. It can store only
 		  /// \c int priorities and it maintains a list of items for each priority
 		  /// in the range <tt>[0..C)</tt>. So it should only be used when the
 		  /// priorities are small. It is not intended to use as a Dijkstra heap.
 		  ///
 		  /// \tparam IM A read-writable item map with \c int values, used
 		  /// internally to handle the cross references.
 		  /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
 		  /// The default is \e min-heap. If this parameter is set to \c false,
 		  /// then the comparison is reversed, so the top(), prio() and pop()
 		  /// functions deal with the item having maximum priority instead of the
 		  /// minimum.
 		  ///
 		  /// \sa SimpleBucketHeap
 		  template <typename IM, bool MIN = true>
 		  class BucketHeap {
 		  public:
 		    /// Type of the item-int map.
 		    typedef IM ItemIntMap;
 		    /// Type of the priorities.
 		    typedef int Prio;
 		    /// Type of the items stored in the heap.
 		    typedef typename ItemIntMap::Key Item;
 		    /// Type of the item-priority pairs.
 		    typedef std::pair<Item,Prio> Pair;
 		  private:
 		    typedef _bucket_heap_bits::DirectionTraits<MIN> Direction;
 		  public:
 		    /// \brief Type to represent the states of the items.
 		    ///
 		    /// Each item has a state associated to it. It can be "in heap",
 		    /// "pre-heap" or "post-heap". The latter two are indifferent from the
 		    /// 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.
 		    };
 		  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 BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {}
 		    /// \brief The number of items stored in the heap.
 		    ///
 		    /// This function returns the number of items stored in the heap.
 		    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(); _first.clear(); _minimum = 0;
+		    }
 		  private:
 		    void relocateLast(int idx) {
 		      if (idx + 1 < int(_data.size())) {
 		        _data[idx] = _data.back();
 		        if (_data[idx].prev != -1) {
 		          _data[_data[idx].prev].next = idx;
 		        } else {
 		          _first[_data[idx].value] = idx;
+		        }
 		        if (_data[idx].next != -1) {
 		          _data[_data[idx].next].prev = idx;
+		        }
 		        _iim[_data[idx].item] = idx;
+		      }
 		      _data.pop_back();
+		    }
 		    void unlace(int idx) {
 		      if (_data[idx].prev != -1) {
 		        _data[_data[idx].prev].next = _data[idx].next;
 		      } else {
 		        _first[_data[idx].value] = _data[idx].next;
+		      }
 		      if (_data[idx].next != -1) {
 		        _data[_data[idx].next].prev = _data[idx].prev;
+		      }
+		    }
 		    void lace(int idx) {
 		      if (int(_first.size()) <= _data[idx].value) {
 		        _first.resize(_data[idx].value + 1, -1);
+		      }
 		      _data[idx].next = _first[_data[idx].value];
 		      if (_data[idx].next != -1) {
 		        _data[_data[idx].next].prev = idx;
+		      }
 		      _first[_data[idx].value] = idx;
 		      _data[idx].prev = -1;
+		    }
 		  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) {
 		      push(p.first, p.second);
+		    }
 		    /// \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) {
 		      int idx = _data.size();
 		      _iim[i] = idx;
 		      _data.push_back(BucketItem(i, p));
 		      lace(idx);
 		      if (Direction::less(p, _minimum)) {
 		        _minimum = 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 {
 		      while (_first[_minimum] == -1) {
 		        Direction::increase(_minimum);
+		      }
 		      return _data[_first[_minimum]].item;
+		    }
 		    /// \brief The minimum priority.
 		    ///
 		    /// This function returns the minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Prio prio() const {
 		      while (_first[_minimum] == -1) {
 		        Direction::increase(_minimum);
+		      }
 		      return _minimum;
+		    }
 		    /// \brief Remove the item having minimum priority.
 		    ///
 		    /// This function removes the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    void pop() {
 		      while (_first[_minimum] == -1) {
 		        Direction::increase(_minimum);
+		      }
 		      int idx = _first[_minimum];
 		      _iim[_data[idx].item] = -2;
 		      unlace(idx);
 		      relocateLast(idx);
+		    }
 		    /// \brief Remove the given item from the heap.
 		    ///
 		    /// This function removes the given item from the heap if it is
 		    /// already stored.
 		    /// \param i The item to delete.
 		    /// \pre \e i must be in the heap.
 		    void erase(const Item &i) {
 		      int idx = _iim[i];
 		      _iim[_data[idx].item] = -2;
 		      unlace(idx);
 		      relocateLast(idx);
+		    }
 		    /// \brief The priority of the given item.
 		    ///
 		    /// This function returns the priority of the given item.
 		    /// \param i The item.
 		    /// \pre \e i must be in the heap.
 		    Prio operator[](const Item &i) const {
 		      int idx = _iim[i];
 		      return _data[idx].value;
+		    }
 		    /// \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 (Direction::less(p, _data[idx].value)) {
 		        decrease(i, p);
 		      } else {
 		        increase(i, p);
+		      }
+		    }
 		    /// \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];
 		      unlace(idx);
 		      _data[idx].value = p;
 		      if (Direction::less(p, _minimum)) {
 		        _minimum = p;
+		      }
 		      lace(idx);
+		    }
 		    /// \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];
 		      unlace(idx);
 		      _data[idx].value = p;
 		      lace(idx);
+		    }
 		    /// \brief Return the state of an item.
 		    ///
 		    /// This method returns \c PRE_HEAP if the given item has never
 		    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
 		    /// and \c POST_HEAP otherwise.
 		    /// In the latter case it is possible that the item will get back
 		    /// to the heap again.
 		    /// \param i The item.
 		    State state(const Item &i) const {
 		      int idx = _iim[i];
 		      if (idx >= 0) idx = 0;
 		      return State(idx);
+		    }
 		    /// \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:
 		    struct BucketItem {
 		      BucketItem(const Item& _item, int _value)
 		        : item(_item), value(_value) {}
 		      Item item;
 		      int value;
 		      int prev, next;
 		    };
 		    ItemIntMap& _iim;
 		    std::vector<int> _first;
 		    std::vector<BucketItem> _data;
 		    mutable int _minimum;
 		  }; // class BucketHeap
 		  /// \ingroup heaps
 		  ///
 		  /// \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 is
 		  /// faster and simpler than BucketHeap. The main difference is
 		  /// that BucketHeap stores a doubly-linked list for each key while
 		  /// this class stores only simply-linked lists. It supports erasing
 		  /// only for the item having minimum priority and it does not support
 		  /// key increasing and decreasing.
 		  ///
 		  /// Note that this implementation does not conform to the
 		  /// \ref concepts::Heap "heap concept" due to the lack of some
 		  /// functionality.
 		  ///
 		  /// \tparam IM A read-writable item map with \c int values, used
 		  /// internally to handle the cross references.
 		  /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
 		  /// The default is \e min-heap. If this parameter is set to \c false,
 		  /// then the comparison is reversed, so the top(), prio() and pop()
 		  /// functions deal with the item having maximum priority instead of the
 		  /// minimum.
 		  ///
 		  /// \sa BucketHeap
 		  template <typename IM, bool MIN = true >
 		  class SimpleBucketHeap {
 		  public:
 		    /// Type of the item-int map.
 		    typedef IM ItemIntMap;
 		    /// Type of the priorities.
 		    typedef int Prio;
 		    /// Type of the items stored in the heap.
 		    typedef typename ItemIntMap::Key Item;
 		    /// Type of the item-priority pairs.
 		    typedef std::pair<Item,Prio> Pair;
 		  private:
 		    typedef _bucket_heap_bits::DirectionTraits<MIN> Direction;
 		  public:
 		    /// \brief Type to represent the states of the items.
 		    ///
 		    /// Each item has a state associated to it. It can be "in heap",
 		    /// "pre-heap" or "post-heap". The latter two are indifferent from the
 		    /// 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.
 		    };
 		  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 SimpleBucketHeap(ItemIntMap &map)
 		      : _iim(map), _free(-1), _num(0), _minimum(0) {}
 		    /// \brief The number of items stored in the heap.
 		    ///
 		    /// This function returns the number of items stored in the heap.
 		    int size() const { return _num; }
 		    /// \brief Check if the heap is empty.
 		    ///
 		    /// This function returns \c true if the heap is empty.
 		    bool empty() const { return _num == 0; }
 		    /// \brief Make the heap empty.
 		    ///
 		    /// This functon makes the heap empty.
 		    /// It does not change the cross reference map. If you want to reuse
 		    /// a heap that is not surely empty, you should first clear it and
 		    /// then you should set the cross reference map to \c PRE_HEAP
 		    /// for each item.
 		    void clear() {
 		      _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0;
+		    }
 		    /// \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) {
 		      push(p.first, p.second);
+		    }
 		    /// \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) {
 		      int idx;
 		      if (_free == -1) {
 		        idx = _data.size();
 		        _data.push_back(BucketItem(i));
 		      } else {
 		        idx = _free;
 		        _free = _data[idx].next;
 		        _data[idx].item = i;
+		      }
 		      _iim[i] = idx;
 		      if (p >= int(_first.size())) _first.resize(p + 1, -1);
 		      _data[idx].next = _first[p];
 		      _first[p] = idx;
 		      if (Direction::less(p, _minimum)) {
 		        _minimum = p;
+		      }
 		      ++_num;
+		    }
 		    /// \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 {
 		      while (_first[_minimum] == -1) {
 		        Direction::increase(_minimum);
+		      }
 		      return _data[_first[_minimum]].item;
+		    }
 		    /// \brief The minimum priority.
 		    ///
 		    /// This function returns the minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Prio prio() const {
 		      while (_first[_minimum] == -1) {
 		        Direction::increase(_minimum);
+		      }
 		      return _minimum;
+		    }
 		    /// \brief Remove the item having minimum priority.
 		    ///
 		    /// This function removes the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    void pop() {
 		      while (_first[_minimum] == -1) {
 		        Direction::increase(_minimum);
+		      }
 		      int idx = _first[_minimum];
 		      _iim[_data[idx].item] = -2;
 		      _first[_minimum] = _data[idx].next;
 		      _data[idx].next = _free;
 		      _free = idx;
 		      --_num;
+		    }
 		    /// \brief The priority of the given item.
 		    ///
 		    /// This function returns the priority of the given item.
 		    /// \param i The item.
 		    /// \pre \e i must be in the heap.
 		    /// \warning This operator is not a constant time function because
 		    /// it scans the whole data structure to find the proper value.
 		    Prio operator[](const Item &i) const {
 		      for (int k = 0; k < int(_first.size()); ++k) {
 		        int idx = _first[k];
 		        while (idx != -1) {
 		          if (_data[idx].item == i) {
 		            return k;
+		          }
 		          idx = _data[idx].next;
+		        }
+		      }
 		      return -1;
+		    }
 		    /// \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 idx = _iim[i];
 		      if (idx >= 0) idx = 0;
 		      return State(idx);
+		    }
 		  private:
 		    struct BucketItem {
 		      BucketItem(const Item& _item)
 		        : item(_item) {}
 		      Item item;
 		      int next;
 		    };
 		    ItemIntMap& _iim;
 		    std::vector<int> _first;
 		    std::vector<BucketItem> _data;
 		    int _free, _num;
 		    mutable int _minimum;
 		  }; // class SimpleBucketHeap
+		}
 		#endif

lemon/fib_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_FIB_HEAP_H
 		#define LEMON_FIB_HEAP_H
 		///\file
 		///\ingroup heaps
 		///\brief Fibonacci heap implementation.
 		#include <vector>
 		#include <utility>
 		#include <functional>
 		#include <lemon/math.h>
 		namespace lemon {
 		  /// \ingroup heaps
 		  ///
 		  /// \brief Fibonacci heap data structure.
 		  ///
 		  /// 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 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 FibHeap {
 		  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;
 		  private:
 		    class Store;
 		    std::vector<Store> _data;
 		    int _minimum;
 		    ItemIntMap &_iim;
 		    Compare _comp;
 		    int _num;
 		  public:
 		    /// \brief Type to represent the states of the items.
 		    ///
 		    /// Each item has a state associated to it. It can be "in heap",
 		    /// "pre-heap" or "post-heap". The latter two are indifferent from the
 		    /// 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.
 		    };
 		    /// \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 FibHeap(ItemIntMap &map)
 		      : _minimum(0), _iim(map), _num() {}
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    /// \param map A map that assigns \c int values to the items.
 		    /// It is used internally to handle the cross references.
 		    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
 		    /// \param comp The function object used for comparing the priorities.
 		    FibHeap(ItemIntMap &map, const Compare &comp)
 		      : _minimum(0), _iim(map), _comp(comp), _num() {}
 		    /// \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; }
 		    /// \brief Check if the heap is empty.
 		    ///
 		    /// This function returns \c true if the heap is empty.
 		    bool empty() const { return _num==0; }
 		    /// \brief Make the heap empty.
 		    ///
 		    /// This functon makes the heap empty.
 		    /// It does not change the cross reference map. If you want to reuse
 		    /// a heap that is not surely empty, you should first clear it and
 		    /// then you should set the cross reference map to \c PRE_HEAP
 		    /// for each item.
 		    void clear() {
 		      _data.clear(); _minimum = 0; _num = 0;
+		    }
 		    /// \brief Insert an item into the heap with the given priority.
 		    ///
 		    /// This function inserts the given item into the heap with the
 		    /// given priority.
 		    /// \param item The item to insert.
 		    /// \param prio The priority of the item.
 		    /// \pre \e item must not be stored in the heap.
 		    void push (const Item& item, const Prio& prio) {
 		      int i=_iim[item];
 		      if ( i < 0 ) {
 		        int s=_data.size();
 		        _iim.set( item, s );
 		        Store st;
 		        st.name=item;
 		        _data.push_back(st);
 		        i=s;
 		      } else {
 		        _data[i].parent=_data[i].child=-1;
 		        _data[i].degree=0;
 		        _data[i].in=true;
 		        _data[i].marked=false;
+		      }
 		      if ( _num ) {
 		        _data[_data[_minimum].right_neighbor].left_neighbor=i;
 		        _data[i].right_neighbor=_data[_minimum].right_neighbor;
 		        _data[_minimum].right_neighbor=i;
 		        _data[i].left_neighbor=_minimum;
 		        if ( _comp( prio, _data[_minimum].prio) ) _minimum=i;
 		      } else {
 		        _data[i].right_neighbor=_data[i].left_neighbor=i;
 		        _minimum=i;
+		      }
 		      _data[i].prio=prio;
 		      ++_num;
+		    }
 		    /// \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[_minimum].name; }
 		    /// \brief The minimum priority.
 		    ///
 		    /// This function returns the minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Prio prio() const { return _data[_minimum].prio; }
 		    /// \brief Remove the item having minimum priority.
 		    ///
 		    /// This function removes the item having minimum priority.
 		    /// \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);
 		          _minimum=_data[_minimum].child;
 		          balance();
+		        }
 		      } else {
 		        int right=_data[_minimum].right_neighbor;
 		        unlace(_minimum);
 		        _data[_minimum].in=false;
 		        if ( _data[_minimum].degree > 0 ) {
 		          int left=_data[_minimum].left_neighbor;
 		          int child=_data[_minimum].child;
 		          int last_child=_data[child].left_neighbor;
 		          makeRoot(child);
 		          _data[left].right_neighbor=child;
 		          _data[child].left_neighbor=left;
 		          _data[right].left_neighbor=last_child;
 		          _data[last_child].right_neighbor=right;
+		        }
 		        _minimum=right;
 		        balance();
 		      } // the case where there are more roots
 		      --_num;
+		    }
 		    /// \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 ) {
 		        if ( _data[i].parent!=-1 ) {
 		          int p=_data[i].parent;
 		          cut(i,p);
 		          cascade(p);
+		        }
 		        _minimum=i;     //As if its prio would be -infinity
 		        pop();
+		      }
+		    }
 		    /// \brief The priority of the given item.
 		    ///
 		    /// This function returns the priority of the given item.
 		    /// \param item The item.
 		    /// \pre \e item must be in the heap.
 		    Prio operator[](const Item& item) const {
 		      return _data[_iim[item]].prio;
+		    }
 		    /// \brief Set the priority of an item or insert it, if it is
 		    /// not stored in the heap.
 		    ///
 		    /// This method sets the priority of the given item if it is
 		    /// already stored in the heap. Otherwise it inserts the given
 		    /// item into the heap with the given priority.
 		    /// \param item The item.
 		    /// \param prio The priority.
 		    void set (const Item& item, const Prio& prio) {
 		      int i=_iim[item];
 		      if ( i >= 0 && _data[i].in ) {
 		        if ( _comp(prio, _data[i].prio) ) decrease(item, prio);
 		        if ( _comp(_data[i].prio, prio) ) increase(item, prio);
 		      } else push(item, prio);
+		    }
 		    /// \brief Decrease the priority of an item to the given value.
 		    ///
 		    /// This function decreases the priority of an item to the given value.
 		    /// \param item The item.
 		    /// \param prio The priority.
 		    /// \pre \e item must be stored in the heap with priority at least \e prio.
 		    void decrease (const Item& item, const Prio& prio) {
 		      int i=_iim[item];
 		      _data[i].prio=prio;
 		      int p=_data[i].parent;
 		      if ( p!=-1 && _comp(prio, _data[p].prio) ) {
 		        cut(i,p);
 		        cascade(p);
+		      }
 		      if ( _comp(prio, _data[_minimum].prio) ) _minimum=i;
+		    }
 		    /// \brief Increase the priority of an item to the given value.
 		    ///
 		    /// This function increases the priority of an item to the given value.
 		    /// \param item The item.
 		    /// \param prio The priority.
 		    /// \pre \e item must be stored in the heap with priority at most \e prio.
 		    void increase (const Item& item, const Prio& prio) {
 		      erase(item);
 		      push(item, prio);
+		    }
 		    /// \brief Return the state of an item.
 		    ///
 		    /// This method returns \c PRE_HEAP if the given item has never
 		    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
 		    /// and \c POST_HEAP otherwise.
 		    /// In the latter case it is possible that the item will get back
 		    /// to the heap again.
 		    /// \param item The item.
 		    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:
 		    void balance() {
 		      int maxdeg=int( std::floor( 2.08*log(double(_data.size()))))+1;
 		      std::vector<int> A(maxdeg,-1);
 		      /*
 		       *Recall that now minimum does not point to the minimum prio element.
 		       *We set minimum to this during balance().
 		       */
 		      int anchor=_data[_minimum].left_neighbor;
 		      int next=_minimum;
 		      bool end=false;
 		      do {
 		        int active=next;
 		        if ( anchor==active ) end=true;
 		        int d=_data[active].degree;
 		        next=_data[active].right_neighbor;
 		        while (A[d]!=-1) {
 		          if( _comp(_data[active].prio, _data[A[d]].prio) ) {
 		            fuse(active,A[d]);
 		          } else {
 		            fuse(A[d],active);
 		            active=A[d];
+		          }
 		          A[d]=-1;
 		          ++d;
+		        }
 		        A[d]=active;
 		      } while ( !end );
 		      while ( _data[_minimum].parent >=0 )
 		        _minimum=_data[_minimum].parent;
 		      int s=_minimum;
 		      int m=_minimum;
 		      do {
 		        if ( _comp(_data[s].prio, _data[_minimum].prio) ) _minimum=s;
 		        s=_data[s].right_neighbor;
 		      } while ( s != m );
+		    }
 		    void makeRoot(int c) {
 		      int s=c;
 		      do {
 		        _data[s].parent=-1;
 		        s=_data[s].right_neighbor;
 		      } while ( s != c );
+		    }
 		    void cut(int a, int b) {
 		      /*
 		       *Replacing a from the children of b.
 		       */
 		      --_data[b].degree;
 		      if ( _data[b].degree !=0 ) {
 		        int child=_data[b].child;
 		        if ( child==a )
 		          _data[b].child=_data[child].right_neighbor;
 		        unlace(a);
+		      }
 		      /*Lacing a to the roots.*/
 		      int right=_data[_minimum].right_neighbor;
 		      _data[_minimum].right_neighbor=a;
 		      _data[a].left_neighbor=_minimum;
 		      _data[a].right_neighbor=right;
 		      _data[right].left_neighbor=a;
 		      _data[a].parent=-1;
 		      _data[a].marked=false;
+		    }
 		    void cascade(int a) {
 		      if ( _data[a].parent!=-1 ) {
 		        int p=_data[a].parent;
 		        if ( _data[a].marked==false ) _data[a].marked=true;
 		        else {
 		          cut(a,p);
 		          cascade(p);
+		        }
+		      }
+		    }
 		    void fuse(int a, int b) {
 		      unlace(b);
 		      /*Lacing b under a.*/
 		      _data[b].parent=a;
 		      if (_data[a].degree==0) {
 		        _data[b].left_neighbor=b;
 		        _data[b].right_neighbor=b;
 		        _data[a].child=b;
 		      } else {
 		        int child=_data[a].child;
 		        int last_child=_data[child].left_neighbor;
 		        _data[child].left_neighbor=b;
 		        _data[b].right_neighbor=child;
 		        _data[last_child].right_neighbor=b;
 		        _data[b].left_neighbor=last_child;
+		      }
 		      ++_data[a].degree;
 		      _data[b].marked=false;
+		    }
 		    /*
 		     *It is invoked only if a has siblings.
 		     */
 		    void unlace(int a) {
 		      int leftn=_data[a].left_neighbor;
 		      int rightn=_data[a].right_neighbor;
 		      _data[leftn].right_neighbor=rightn;
 		      _data[rightn].left_neighbor=leftn;
+		    }
 		    class Store {
 		      friend class FibHeap;
 		      Item name;
 		      int parent;
 		      int left_neighbor;
 		      int right_neighbor;
 		      int child;
 		      int degree;
 		      bool marked;
 		      bool in;
 		      Prio prio;
 		      Store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
 		    };
 		  };
 		} //namespace lemon
 		#endif //LEMON_FIB_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

lemon/pairing_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_PAIRING_HEAP_H
 		#define LEMON_PAIRING_HEAP_H
 		///\file
 		///\ingroup heaps
 		///\brief Pairing heap implementation.
 		#include <vector>
 		#include <utility>
 		#include <functional>
 		#include <lemon/math.h>
 		namespace lemon {
 		  /// \ingroup heaps
 		  ///
 		  ///\brief Pairing Heap.
 		  ///
 		  /// This class implements the \e pairing \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 pairing 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 PairingHeap {
 		  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;
 		    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 PairingHeap(ItemIntMap &map)
 		      : _min(0), _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.
 		    PairingHeap(ItemIntMap &map, const Compare &comp)
 		      : _min(0), _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;
+		    }
 		    /// \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;
 		        _data.push_back(st);
 		        i=s;
 		      } else {
 		        _data[i].parent=_data[i].child=-1;
 		        _data[i].left_child=false;
 		        _data[i].degree=0;
 		        _data[i].in=true;
+		      }
 		      _data[i].prio=value;
 		      if ( _num_items!=0 ) {
 		        if ( _comp( value, _data[_min].prio) ) {
 		          fuse(i,_min);
 		          _min=i;
+		        }
 		        else fuse(_min,i);
+		      }
 		      else _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.
 		    const 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() {
 		      std::vector<int> trees;
 		      int i=0, child_right = 0;
 		      _data[_min].in=false;
 		      if( -1!=_data[_min].child ) {
 		        i=_data[_min].child;
 		        trees.push_back(i);
 		        _data[i].parent = -1;
 		        _data[_min].child = -1;
 		        int ch=-1;
 		        while( _data[i].child!=-1 ) {
 		          ch=_data[i].child;
 		          if( _data[ch].left_child && i==_data[ch].parent ) {
 		            break;
 		          } else {
 		            if( _data[ch].left_child ) {
 		              child_right=_data[ch].parent;
 		              _data[ch].parent = i;
 		              --_data[i].degree;
+		            }
 		            else {
 		              child_right=ch;
 		              _data[i].child=-1;
 		              _data[i].degree=0;
+		            }
 		            _data[child_right].parent = -1;
 		            trees.push_back(child_right);
 		            i = child_right;
+		          }
+		        }
 		        int num_child = trees.size();
 		        int other;
 		        for( i=0; i<num_child-1; i+=2 ) {
 		          if ( !_comp(_data[trees[i]].prio, _data[trees[i+1]].prio) ) {
 		            other=trees[i];
 		            trees[i]=trees[i+1];
 		            trees[i+1]=other;
+		          }
 		          fuse( trees[i], trees[i+1] );
+		        }
 		        i = (0==(num_child % 2)) ? num_child-2 : num_child-1;
 		        while(i>=2) {
 		          if ( _comp(_data[trees[i]].prio, _data[trees[i-2]].prio) ) {
 		            other=trees[i];
 		            trees[i]=trees[i-2];
 		            trees[i-2]=other;
+		          }
 		          fuse( trees[i-2], trees[i] );
 		          i-=2;
+		        }
 		        _min = trees[0];
+		      }
 		      else {
 		        _min = _data[_min].child;
+		      }
 		      if (_min >= 0) _data[_min].left_child = false;
 		      --_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];
 		      _data[i].prio=value;
 		      int p=_data[i].parent;
 		      if( _data[i].left_child && i!=_data[p].child ) {
 		        p=_data[p].parent;
+		      }
 		      if ( p!=-1 && _comp(value,_data[p].prio) ) {
 		        cut(i,p);
 		        if ( _comp(_data[_min].prio,value) ) {
 		          fuse(_min,i);
 		        } else {
 		          fuse(i,_min);
 		          _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:
 		    void cut(int a, int b) {
 		      int child_a;
 		      switch (_data[a].degree) {
 		        case 2:
 		          child_a = _data[_data[a].child].parent;
 		          if( _data[a].left_child ) {
 		            _data[child_a].left_child=true;
 		            _data[b].child=child_a;
 		            _data[child_a].parent=_data[a].parent;
+		          }
 		          else {
 		            _data[child_a].left_child=false;
 		            _data[child_a].parent=b;
 		            if( a!=_data[b].child )
 		              _data[_data[b].child].parent=child_a;
 		            else
 		              _data[b].child=child_a;
+		          }
 		          --_data[a].degree;
 		          _data[_data[a].child].parent=a;
 		          break;
 		        case 1:
 		          child_a = _data[a].child;
 		          if( !_data[child_a].left_child ) {
 		            --_data[a].degree;
 		            if( _data[a].left_child ) {
 		              _data[child_a].left_child=true;
 		              _data[child_a].parent=_data[a].parent;
 		              _data[b].child=child_a;
+		            }
 		            else {
 		              _data[child_a].left_child=false;
 		              _data[child_a].parent=b;
 		              if( a!=_data[b].child )
 		                _data[_data[b].child].parent=child_a;
 		              else
 		                _data[b].child=child_a;
+		            }
 		            _data[a].child=-1;
+		          }
 		          else {
 		            --_data[b].degree;
 		            if( _data[a].left_child ) {
 		              _data[b].child =
 		                (1==_data[b].degree) ? _data[a].parent : -1;
 		            } else {
 		              if (1==_data[b].degree)
 		                _data[_data[b].child].parent=b;
 		              else
 		                _data[b].child=-1;
+		            }
+		          }
 		          break;
 		        case 0:
 		          --_data[b].degree;
 		          if( _data[a].left_child ) {
 		            _data[b].child =
 		              (0!=_data[b].degree) ? _data[a].parent : -1;
 		          } else {
 		            if( 0!=_data[b].degree )
 		              _data[_data[b].child].parent=b;
 		            else
 		              _data[b].child=-1;
+		          }
 		          break;
+		      }
 		      _data[a].parent=-1;
 		      _data[a].left_child=false;
+		    }
 		    void fuse(int a, int b) {
 		      int child_a = _data[a].child;
 		      int child_b = _data[b].child;
 		      _data[a].child=b;
 		      _data[b].parent=a;
 		      _data[b].left_child=true;
 		      if( -1!=child_a ) {
 		        _data[b].child=child_a;
 		        _data[child_a].parent=b;
 		        _data[child_a].left_child=false;
 		        ++_data[b].degree;
 		        if( -1!=child_b ) {
 		           _data[b].child=child_b;
 		           _data[child_b].parent=child_a;
+		        }
+		      }
 		      else { ++_data[a].degree; }
+		    }
 		    class store {
 		      friend class PairingHeap;
 		      Item name;
 		      int parent;
 		      int child;
 		      bool left_child;
 		      int degree;
 		      bool in;
 		      Prio prio;
 		      store() : parent(-1), child(-1), left_child(false), degree(0), in(true) {}
 		    };
 		  };
 		} //namespace lemon
 		#endif //LEMON_PAIRING_HEAP_H

lemon/radix_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_RADIX_HEAP_H
 		#define LEMON_RADIX_HEAP_H
 		///\ingroup heaps
 		///\file
 		///\brief Radix heap implementation.
 		#include <vector>
 		#include <lemon/error.h>
 		namespace lemon {
 		  /// \ingroup heaps
 		  ///
 		  /// \brief Radix heap data structure.
 		  ///
 		  /// This class implements the \e radix \e heap data structure.
 		  /// It practically conforms to the \ref concepts::Heap "heap concept",
 		  /// but it has some limitations due its special implementation.
 		  /// The type of the priorities must be \c int and the priority of an
 		  /// item cannot be decreased under the priority of the last removed item.
 		  ///
 		  /// \tparam IM A read-writable item map with \c int values, used
 		  /// internally to handle the cross references.
 		  template <typename IM>
 		  class RadixHeap {
 		  public:
 		    /// Type of the item-int map.
 		    typedef IM ItemIntMap;
 		    /// Type of the priorities.
 		    typedef int Prio;
 		    /// Type of the items stored in the heap.
 		    typedef typename ItemIntMap::Key Item;
 		    /// \brief Exception thrown by RadixHeap.
 		    ///
 		    /// This exception is thrown when an item is inserted into a
 		    /// RadixHeap with a priority smaller than the last erased one.
 		    /// \see RadixHeap
 		    class PriorityUnderflowError : public Exception {
 		    public:
 		      virtual const char* what() const throw() {
 		        return "lemon::RadixHeap::PriorityUnderflowError";
+		      }
 		    };
 		    /// \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:
 		    struct RadixItem {
 		      int prev, next, box;
 		      Item item;
 		      int prio;
 		      RadixItem(Item _item, int _prio) : item(_item), prio(_prio) {}
 		    };
 		    struct RadixBox {
 		      int first;
 		      int min, size;
 		      RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
 		    };
 		    std::vector<RadixItem> _data;
 		    std::vector<RadixBox> _boxes;
 		    ItemIntMap &_iim;
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    /// \param map A map that assigns \c int values to the items.
 		    /// It is used internally to handle the cross references.
 		    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
 		    /// \param minimum The initial minimum value of the heap.
 		    /// \param capacity The initial capacity of the heap.
 		    RadixHeap(ItemIntMap &map, int minimum = 0, int capacity = 0)
 		      : _iim(map)
+		    {
 		      _boxes.push_back(RadixBox(minimum, 1));
 		      _boxes.push_back(RadixBox(minimum + 1, 1));
 		      while (lower(_boxes.size() - 1, capacity + minimum - 1)) {
 		        extend();
+		      }
+		    }
 		    /// \brief The number of items stored in the heap.
 		    ///
 		    /// This function returns the number of items stored in the heap.
 		    int size() const { return _data.size(); }
 		    /// \brief Check if the heap is empty.
 		    ///
 		    /// This function returns \c true if the heap is empty.
 		    bool empty() const { return _data.empty(); }
 		    /// \brief Make the heap empty.
 		    ///
 		    /// This functon makes the heap empty.
 		    /// It does not change the cross reference map. If you want to reuse
 		    /// a heap that is not surely empty, you should first clear it and
 		    /// then you should set the cross reference map to \c PRE_HEAP
 		    /// for each item.
 		    /// \param minimum The minimum value of the heap.
 		    /// \param capacity The capacity of the heap.
 		    void clear(int minimum = 0, int capacity = 0) {
 		      _data.clear(); _boxes.clear();
 		      _boxes.push_back(RadixBox(minimum, 1));
 		      _boxes.push_back(RadixBox(minimum + 1, 1));
 		      while (lower(_boxes.size() - 1, capacity + minimum - 1)) {
 		        extend();
+		      }
+		    }
 		  private:
 		    bool upper(int box, Prio pr) {
 		      return pr < _boxes[box].min;
+		    }
 		    bool lower(int box, Prio pr) {
 		      return pr >= _boxes[box].min + _boxes[box].size;
+		    }
 		    // Remove item from the box list
 		    void remove(int index) {
 		      if (_data[index].prev >= 0) {
 		        _data[_data[index].prev].next = _data[index].next;
 		      } else {
 		        _boxes[_data[index].box].first = _data[index].next;
+		      }
 		      if (_data[index].next >= 0) {
 		        _data[_data[index].next].prev = _data[index].prev;
+		      }
+		    }
 		    // Insert item into the box list
 		    void insert(int box, int index) {
 		      if (_boxes[box].first == -1) {
 		        _boxes[box].first = index;
 		        _data[index].next = _data[index].prev = -1;
 		      } else {
 		        _data[index].next = _boxes[box].first;
 		        _data[_boxes[box].first].prev = index;
 		        _data[index].prev = -1;
 		        _boxes[box].first = index;
+		      }
 		      _data[index].box = box;
+		    }
 		    // Add a new box to the box list
 		    void extend() {
 		      int min = _boxes.back().min + _boxes.back().size;
 		      int bs = 2 * _boxes.back().size;
 		      _boxes.push_back(RadixBox(min, bs));
+		    }
 		    // Move an item up into the proper box.
 		    void bubbleUp(int index) {
 		      if (!lower(_data[index].box, _data[index].prio)) return;
 		      remove(index);
 		      int box = findUp(_data[index].box, _data[index].prio);
 		      insert(box, index);
+		    }
 		    // Find up the proper box for the item with the given priority
 		    int findUp(int start, int pr) {
 		      while (lower(start, pr)) {
 		        if (++start == int(_boxes.size())) {
 		          extend();
+		        }
+		      }
 		      return start;
+		    }
 		    // Move an item down into the proper box
 		    void bubbleDown(int index) {
 		      if (!upper(_data[index].box, _data[index].prio)) return;
 		      remove(index);
 		      int box = findDown(_data[index].box, _data[index].prio);
 		      insert(box, index);
+		    }
 		    // Find down the proper box for the item with the given priority
 		    int findDown(int start, int pr) {
 		      while (upper(start, pr)) {
 		        if (--start < 0) throw PriorityUnderflowError();
+		      }
 		      return start;
+		    }
 		    // Find the first non-empty box
 		    int findFirst() {
 		      int first = 0;
 		      while (_boxes[first].first == -1) ++first;
 		      return first;
+		    }
 		    // Gives back the minimum priority of the given box
 		    int minValue(int box) {
 		      int min = _data[_boxes[box].first].prio;
 		      for (int k = _boxes[box].first; k != -1; k = _data[k].next) {
 		        if (_data[k].prio < min) min = _data[k].prio;
+		      }
 		      return min;
+		    }
 		    // Rearrange the items of the heap and make the first box non-empty
 		    void moveDown() {
 		      int box = findFirst();
 		      if (box == 0) return;
 		      int min = minValue(box);
 		      for (int i = 0; i <= box; ++i) {
 		        _boxes[i].min = min;
 		        min += _boxes[i].size;
+		      }
 		      int curr = _boxes[box].first, next;
 		      while (curr != -1) {
 		        next = _data[curr].next;
 		        bubbleDown(curr);
 		        curr = next;
+		      }
+		    }
 		    void relocateLast(int index) {
 		      if (index != int(_data.size()) - 1) {
 		        _data[index] = _data.back();
 		        if (_data[index].prev != -1) {
 		          _data[_data[index].prev].next = index;
 		        } else {
 		          _boxes[_data[index].box].first = index;
+		        }
 		        if (_data[index].next != -1) {
 		          _data[_data[index].next].prev = index;
+		        }
 		        _iim[_data[index].item] = index;
+		      }
 		      _data.pop_back();
+		    }
 		  public:
 		    /// \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.
 		    /// \warning This method may throw an \c UnderFlowPriorityException.
 		    void push(const Item &i, const Prio &p) {
 		      int n = _data.size();
 		      _iim.set(i, n);
 		      _data.push_back(RadixItem(i, p));
 		      while (lower(_boxes.size() - 1, p)) {
 		        extend();
+		      }
 		      int box = findDown(_boxes.size() - 1, p);
 		      insert(box, n);
+		    }
 		    /// \brief Return the item having minimum priority.
 		    ///
 		    /// This function returns the item having minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Item top() const {
 		      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
 		      return _data[_boxes[0].first].item;
+		    }
 		    /// \brief The minimum priority.
 		    ///
 		    /// This function returns the minimum priority.
 		    /// \pre The heap must be non-empty.
 		    Prio prio() const {
 		      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
 		      return _data[_boxes[0].first].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() {
 		      moveDown();
 		      int index = _boxes[0].first;
 		      _iim[_data[index].item] = POST_HEAP;
 		      remove(index);
 		      relocateLast(index);
+		    }
 		    /// \brief Remove the given item from the heap.
 		    ///
 		    /// This function removes the given item from the heap if it is
 		    /// already stored.
 		    /// \param i The item to delete.
 		    /// \pre \e i must be in the heap.
 		    void erase(const Item &i) {
 		      int index = _iim[i];
 		      _iim[i] = POST_HEAP;
 		      remove(index);
 		      relocateLast(index);
+		   }
 		    /// \brief The priority of the given item.
 		    ///
 		    /// This function returns the priority of the given item.
 		    /// \param i The item.
 		    /// \pre \e i must be in the heap.
 		    Prio operator[](const Item &i) const {
 		      int idx = _iim[i];
 		      return _data[idx].prio;
+		    }
 		    /// \brief Set the priority of an item or insert it, if it is
 		    /// not stored in the heap.
 		    ///
 		    /// This method sets the priority of the given item if it is
 		    /// already stored in the heap. Otherwise it inserts the given
 		    /// item into the heap with the given priority.
 		    /// \param i The item.
 		    /// \param p The priority.
 		    /// \pre \e i must be in the heap.
 		    /// \warning This method may throw an \c UnderFlowPriorityException.
 		    void set(const Item &i, const Prio &p) {
 		      int idx = _iim[i];
 		      if( idx < 0 ) {
 		        push(i, p);
+		      }
 		      else if( p >= _data[idx].prio ) {
 		        _data[idx].prio = p;
 		        bubbleUp(idx);
 		      } else {
 		        _data[idx].prio = p;
 		        bubbleDown(idx);
+		      }
+		    }
 		    /// \brief Decrease the priority of an item to the given value.
 		    ///
 		    /// This function decreases the priority of an item to the given value.
 		    /// \param i The item.
 		    /// \param p The priority.
 		    /// \pre \e i must be stored in the heap with priority at least \e p.
 		    /// \warning This method may throw an \c UnderFlowPriorityException.
 		    void decrease(const Item &i, const Prio &p) {
 		      int idx = _iim[i];
 		      _data[idx].prio = p;
 		      bubbleDown(idx);
+		    }
 		    /// \brief Increase the priority of an item to the given value.
 		    ///
 		    /// This function increases the priority of an item to the given value.
 		    /// \param i The item.
 		    /// \param p The priority.
 		    /// \pre \e i must be stored in the heap with priority at most \e p.
 		    void increase(const Item &i, const Prio &p) {
 		      int idx = _iim[i];
 		      _data[idx].prio = p;
 		      bubbleUp(idx);
+		    }
 		    /// \brief Return the state of an item.
 		    ///
 		    /// This method returns \c PRE_HEAP if the given item has never
 		    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
 		    /// and \c POST_HEAP otherwise.
 		    /// In the latter case it is possible that the item will get back
 		    /// to the heap again.
 		    /// \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;
+		      }
+		    }
 		  }; // class RadixHeap
 		} // namespace lemon
 		#endif // LEMON_RADIX_HEAP_H

test/bellman_ford_test.cc

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.
+		 *
 		 */
 		#include <lemon/concepts/digraph.h>
 		#include <lemon/smart_graph.h>
 		#include <lemon/list_graph.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/bellman_ford.h>
 		#include <lemon/path.h>
 		#include "graph_test.h"
 		#include "test_tools.h"
 		using namespace lemon;
 		char test_lgf[] =
 		  "@nodes\n"
 		  "label\n"
 		  "0\n"
 		  "1\n"
 		  "2\n"
 		  "3\n"
 		  "4\n"
 		  "@arcs\n"
 		  "    length\n"
 		  "0 1 3\n"
 		  "1 2 -3\n"
 		  "1 2 -5\n"
 		  "1 3 -2\n"
 		  "0 2 -1\n"
 		  "1 2 -4\n"
 		  "0 3 2\n"
 		  "4 2 -5\n"
 		  "2 3 1\n"
 		  "@attributes\n"
 		  "source 0\n"
 		  "target 3\n";
 		void checkBellmanFordCompile()
+		{
 		  typedef int Value;
 		  typedef concepts::Digraph Digraph;
 		  typedef concepts::ReadMap<Digraph::Arc,Value> LengthMap;
 		  typedef BellmanFord<Digraph, LengthMap> BF;
 		  typedef Digraph::Node Node;
 		  typedef Digraph::Arc Arc;
 		  Digraph gr;
 		  Node s, t, n;
 		  Arc e;
 		  Value l;
 		  int k;
 		  bool b;
 		  BF::DistMap d(gr);
 		  BF::PredMap p(gr);
 		  LengthMap length;
 		  concepts::Path<Digraph> pp;
+		  {
 		    BF bf_test(gr,length);
 		    const BF& const_bf_test = bf_test;
 		    bf_test.run(s);
 		    bf_test.run(s,k);
 		    bf_test.init();
 		    bf_test.addSource(s);
 		    bf_test.addSource(s, 1);
 		    b = bf_test.processNextRound();
 		    b = bf_test.processNextWeakRound();
 		    bf_test.start();
 		    bf_test.checkedStart();
 		    bf_test.limitedStart(k);
 		    l  = const_bf_test.dist(t);
 		    e  = const_bf_test.predArc(t);
 		    s  = const_bf_test.predNode(t);
 		    b  = const_bf_test.reached(t);
 		    d  = const_bf_test.distMap();
 		    p  = const_bf_test.predMap();
 		    pp = const_bf_test.path(t);
 		    for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {}
+		  }
+		  {
 		    BF::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
 		      ::SetDistMap<concepts::ReadWriteMap<Node,Value> >
 		      ::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> >
 		      ::Create bf_test(gr,length);
 		    LengthMap length_map;
 		    concepts::ReadWriteMap<Node,Arc> pred_map;
 		    concepts::ReadWriteMap<Node,Value> dist_map;
 		    bf_test
 		      .lengthMap(length_map)
 		      .predMap(pred_map)
 		      .distMap(dist_map);
 		    bf_test.run(s);
 		    bf_test.run(s,k);
 		    bf_test.init();
 		    bf_test.addSource(s);
 		    bf_test.addSource(s, 1);
 		    b = bf_test.processNextRound();
 		    b = bf_test.processNextWeakRound();
 		    bf_test.start();
 		    bf_test.checkedStart();
 		    bf_test.limitedStart(k);
 		    l  = bf_test.dist(t);
 		    e  = bf_test.predArc(t);
 		    s  = bf_test.predNode(t);
 		    b  = bf_test.reached(t);
 		    pp = bf_test.path(t);
+		  }
+		}
 		void checkBellmanFordFunctionCompile()
+		{
 		  typedef int Value;
 		  typedef concepts::Digraph Digraph;
 		  typedef Digraph::Arc Arc;
 		  typedef Digraph::Node Node;
 		  typedef concepts::ReadMap<Digraph::Arc,Value> LengthMap;
 		  Digraph g;
 		  bool b;
 		  bellmanFord(g,LengthMap()).run(Node());
 		  b = bellmanFord(g,LengthMap()).run(Node(),Node());
 		  bellmanFord(g,LengthMap())
 		    .predMap(concepts::ReadWriteMap<Node,Arc>())
 		    .distMap(concepts::ReadWriteMap<Node,Value>())
 		    .run(Node());
 		  b=bellmanFord(g,LengthMap())
 		    .predMap(concepts::ReadWriteMap<Node,Arc>())
 		    .distMap(concepts::ReadWriteMap<Node,Value>())
 		    .path(concepts::Path<Digraph>())
 		    .dist(Value())
 		    .run(Node(),Node());
+		}
 		template <typename Digraph, typename Value>
 		void checkBellmanFord() {
 		  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		  typedef typename Digraph::template ArcMap<Value> LengthMap;
 		  Digraph gr;
 		  Node s, t;
 		  LengthMap length(gr);
 		  std::istringstream input(test_lgf);
 		  digraphReader(gr, input).
 		    arcMap("length", length).
 		    node("source", s).
 		    node("target", t).
 		    run();
 		  BellmanFord<Digraph, LengthMap>
 		    bf(gr, length);
 		  bf.run(s);
 		  Path<Digraph> p = bf.path(t);
 		  check(bf.reached(t) && bf.dist(t) == -1, "Bellman-Ford found a wrong path.");
 		  check(p.length() == 3, "path() found a wrong path.");
 		  check(checkPath(gr, p), "path() found a wrong path.");
 		  check(pathSource(gr, p) == s, "path() found a wrong path.");
 		  check(pathTarget(gr, p) == t, "path() found a wrong path.");
 		  ListPath<Digraph> path;
 		  Value dist;
 		  bool reached = bellmanFord(gr,length).path(path).dist(dist).run(s,t);
 		  check(reached && dist == -1, "Bellman-Ford found a wrong path.");
 		  check(path.length() == 3, "path() found a wrong path.");
 		  check(checkPath(gr, path), "path() found a wrong path.");
 		  check(pathSource(gr, path) == s, "path() found a wrong path.");
 		  check(pathTarget(gr, path) == t, "path() found a wrong path.");
 		  for(ArcIt e(gr); e!=INVALID; ++e) {
 		    Node u=gr.source(e);
 		    Node v=gr.target(e);
 		    check(!bf.reached(u) || (bf.dist(v) - bf.dist(u) <= length[e]),
 		          "Wrong output. dist(target)-dist(source)-arc_length=" <<
 		          bf.dist(v) - bf.dist(u) - length[e]);
+		  }
 		  for(NodeIt v(gr); v!=INVALID; ++v) {
 		    if (bf.reached(v)) {
 		      check(v==s || bf.predArc(v)!=INVALID, "Wrong tree.");
 		      if (bf.predArc(v)!=INVALID ) {
 		        Arc e=bf.predArc(v);
 		        Node u=gr.source(e);
 		        check(u==bf.predNode(v),"Wrong tree.");
 		        check(bf.dist(v) - bf.dist(u) == length[e],
 		              "Wrong distance! Difference: " <<
 		              bf.dist(v) - bf.dist(u) - length[e]);
+		      }
+		    }
+		  }
+		}
 		void checkBellmanFordNegativeCycle() {
 		  DIGRAPH_TYPEDEFS(SmartDigraph);
 		  SmartDigraph gr;
 		  IntArcMap length(gr);
 		  Node n1 = gr.addNode();
 		  Node n2 = gr.addNode();
 		  Node n3 = gr.addNode();
 		  Node n4 = gr.addNode();
 		  Arc a1 = gr.addArc(n1, n2);
 		  Arc a2 = gr.addArc(n2, n2);
 		  length[a1] = 2;
 		  length[a2] = -1;
+		  {
 		    BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
 		    bf.run(n1);
 		    StaticPath<SmartDigraph> p = bf.negativeCycle();
 		    check(p.length() == 1 && p.front() == p.back() && p.front() == a2,
 		          "Wrong negative cycle.");
+		  }
 		  length[a2] = 0;
+		  {
 		    BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
 		    bf.run(n1);
 		    check(bf.negativeCycle().empty(),
 		          "Negative cycle should not be found.");
+		  }
 		  length[gr.addArc(n1, n3)] = 5;
 		  length[gr.addArc(n4, n3)] = 1;
 		  length[gr.addArc(n2, n4)] = 2;
 		  length[gr.addArc(n3, n2)] = -4;
+		  {
 		    BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
 		    bf.init();
 		    bf.addSource(n1);
 		    for (int i = 0; i < 4; ++i) {
 		      check(bf.negativeCycle().empty(),
 		            "Negative cycle should not be found.");
 		      bf.processNextRound();
+		    }
 		    StaticPath<SmartDigraph> p = bf.negativeCycle();
 		    check(p.length() == 3, "Wrong negative cycle.");
 		    check(length[p.nth(0)] + length[p.nth(1)] + length[p.nth(2)] == -1,
 		          "Wrong negative cycle.");
+		  }
+		}
 		int main() {
 		  checkBellmanFord<ListDigraph, int>();
 		  checkBellmanFord<SmartDigraph, double>();
 		  checkBellmanFordNegativeCycle();
 		  return 0;
+		}

doc/groups.dox

Show inline comments

@@ -217,57 +217,100 @@
 		  Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
 		  dijkstra.run(source, target);
 		\endcode
 		We have a length map and a maximum speed map on the arcs of a digraph.
 		The minimum time to pass the arc can be calculated as the division of
 		the two maps which can be done implicitly with the \c DivMap template
 		class. We use the implicit minimum time map as the length map of the
 		\c Dijkstra algorithm.
 		*/
 		/**
 		@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.
 		This group contains the path structures implemented in LEMON.
 		LEMON provides flexible data structures to work with paths.
 		All of them have similar interfaces and they can be copied easily with
 		assignment operators and copy constructors. This makes it easy and
 		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.
 		*/
 		/**
 		@defgroup auxdat Auxiliary Data Structures
 		@ingroup datas
 		\brief Auxiliary data structures implemented in LEMON.
 		This group contains some data structures implemented in LEMON in
 		order to make it easier to implement combinatorial algorithms.
 		*/
 		/**
 		@defgroup geomdat Geometric Data Structures
 		@ingroup auxdat
 		\brief Geometric data structures implemented in LEMON.
 		This group contains geometric data structures implemented in LEMON.
 		 - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional
 		   vector with the usual operations.
 		 - \ref lemon::dim2::Box "dim2::Box" can be used to determine the
 		   rectangular bounding box of a set of \ref lemon::dim2::Point
 		   "dim2::Point"'s.
 		*/
 		/**
 		@defgroup matrices Matrices
 		@ingroup auxdat
 		\brief Two dimensional data storages implemented in LEMON.
 		This group contains two dimensional data storages implemented in LEMON.
 		*/
 		/**
 		@defgroup algs Algorithms
 		\brief This group contains the several algorithms
 		implemented in LEMON.
 		This group contains the several algorithms
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup search Graph Search
 		@ingroup algs
 		\brief Common graph search algorithms.
@@ -289,24 +332,33 @@
 		   from a source node when arc lenghts can be either positive or negative,
 		   but the digraph should not contain directed cycles with negative total
 		   length.
 		 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
 		   for solving the \e all-pairs \e shortest \e paths \e problem when arc
 		   lenghts can be either positive or negative, but the digraph should
 		   not contain directed cycles with negative total length.
 		 - \ref Suurballe A successive shortest path algorithm for finding
 		   arc-disjoint paths between two nodes having minimum total length.
 		*/
 		/**
 		@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.
 		This group contains the algorithms for finding maximum flows and
 		feasible circulations.
 		The \e maximum \e flow \e problem is to find a flow of maximum value between
 		a single source and a single target. Formally, there is a \f$G=(V,A)\f$
 		digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
 		\f$s, t \in V\f$ source and target nodes.
 		A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
@@ -366,64 +418,40 @@
 		\brief Algorithms for finding minimum cut in graphs.
 		This group contains the algorithms for finding minimum cut in graphs.
 		The \e minimum \e cut \e problem is to find a non-empty and non-complete
 		\f$X\f$ subset of the nodes with minimum overall capacity on
 		outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
 		\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
 		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:
 		- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
 		  in directed graphs.
 		- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
 		  calculating minimum cut in undirected graphs.
 		- \ref GomoryHu "Gomory-Hu tree computation" for calculating
 		  all-pairs minimum cut in undirected graphs.
 		If you want to find minimum cut just between two distinict nodes,
 		see the \ref max_flow "maximum flow problem".
 		*/
 		/**
 		@defgroup graph_properties Connectivity and Other Graph Properties
 		@ingroup algs
 		\brief Algorithms for discovering the graph properties
 		This group contains the algorithms for discovering the graph properties
 		like connectivity, bipartiteness, euler property, simplicity etc.
 		\image html edge_biconnected_components.png
 		\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
 		*/
 		/**
 		@defgroup planar Planarity Embedding and Drawing
 		@ingroup algs
 		\brief Algorithms for planarity checking, embedding and drawing
 		This group contains the algorithms for planarity checking,
 		embedding and drawing.
 		\image html planar.png
 		\image latex planar.eps "Plane graph" width=\textwidth
 		*/
 		/**
 		@defgroup matching Matching Algorithms
 		@ingroup algs
 		\brief Algorithms for finding matchings in graphs and bipartite graphs.
 		This group contains the algorithms for calculating
 		matchings in graphs and bipartite graphs. The general matching problem is
 		finding a subset of the edges for which each node has at most one incident
 		edge.
 		There are several different algorithms for calculate matchings in
 		graphs.  The matching problems in bipartite graphs are generally
 		easier than in general graphs. The goal of the matching optimization
@@ -446,51 +474,66 @@
 		  maximum cardinality matching in general graphs.
 		- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
 		  maximum weighted matching in general graphs.
 		- \ref MaxWeightedPerfectMatching
 		  Edmond's blossom shrinking algorithm for calculating maximum weighted
 		  perfect matching in general graphs.
 		\image html bipartite_matching.png
 		\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
 		*/
 		/**
-		@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.
 		*/
 		/**
 		@defgroup auxalg Auxiliary Algorithms
 		@ingroup algs
 		\brief Auxiliary algorithms implemented in LEMON.
 		This group contains some algorithms implemented in LEMON
 		in order to make it easier to implement complex algorithms.
 		*/
 		/**
 		@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.
 		This group contains some general optimization frameworks
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup lp_group Lp and Mip Solvers
 		@ingroup gen_opt_group
 		\brief Lp and Mip solver interfaces for LEMON.
@@ -578,25 +621,25 @@
 		*/
 		/**
 		@defgroup eps_io Postscript Exporting
 		@ingroup io_group
 		\brief General \c EPS drawer and graph exporter
 		This group contains general \c EPS drawing methods and special
 		graph exporting tools.
 		*/
 		/**
-		@defgroup dimacs_group DIMACS format
+		@defgroup dimacs_group DIMACS Format
 		@ingroup io_group
 		\brief Read and write files in DIMACS format
 		Tools to read a digraph from or write it to a file in DIMACS format data.
 		*/
 		/**
 		@defgroup nauty_group NAUTY Format
 		@ingroup io_group
 		\brief Read \e Nauty format
 		Tool to read graphs from \e Nauty format data.
@@ -640,33 +683,33 @@
 		graph structures and helper classes used to implement these.
 		*/
 		/**
 		@defgroup map_concepts Map Concepts
 		@ingroup concept
 		\brief Skeleton and concept checking classes for maps
 		This group contains the skeletons and concept checking classes of maps.
 		*/
 		/**
 		@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
 		Some demo programs are listed here. Their full source codes can be found in
 		the \c demo subdirectory of the source tree.
 		In order to compile them, use the <tt>make demo</tt> or the
 		<tt>make check</tt> commands.
 		*/
 		/**
 		@defgroup tools Standalone Utility Applications
 		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

@@ -48,66 +48,73 @@
 		if HAVE_CLP
 		lemon_libemon_la_SOURCES += lemon/clp.cc
 		endif
 		if HAVE_CBC
 		lemon_libemon_la_SOURCES += lemon/cbc.cc
 		endif
 		lemon_HEADERS += \
 			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 \
 			lemon/clp.h \
 			lemon/color.h \
 			lemon/concept_check.h \
 			lemon/connectivity.h \
 			lemon/counter.h \
 			lemon/core.h \
 			lemon/cplex.h \
 			lemon/dfs.h \
 			lemon/dijkstra.h \
 			lemon/dim2.h \
 			lemon/dimacs.h \
 			lemon/edge_set.h \
 			lemon/elevator.h \
 			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 \
 			lemon/lgf_writer.h \
 			lemon/list_graph.h \
 			lemon/lp.h \
 			lemon/lp_base.h \
 			lemon/lp_skeleton.h \
 			lemon/list_graph.h \
 			lemon/maps.h \
 			lemon/matching.h \
 			lemon/math.h \
 			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/radix_sort.h \
 			lemon/random.h \
 			lemon/smart_graph.h \
 			lemon/soplex.h \
 			lemon/suurballe.h \
 			lemon/time_measure.h \
 			lemon/tolerance.h \
 			lemon/unionfind.h \
 			lemon/bits/windows.h
 		bits_HEADERS += \
 			lemon/bits/alteration_notifier.h \

lemon/bfs.h

Show inline comments

@@ -405,26 +405,26 @@
 		        delete _dist;
 		        local_dist=false;
+		      }
 		      _dist = &m;
 		      return *this;
+		    }
 		  public:
 		    ///\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.
 		    ///@{
 		    ///\brief Initializes the internal data structures.
 		    ///
 		    ///Initializes the internal data structures.
 		    void init()
+		    {
 		      create_maps();
 		      _queue.resize(countNodes(*G));
@@ -1413,26 +1413,26 @@
 		        delete _reached;
 		        local_reached = false;
+		      }
 		      _reached = &m;
 		      return *this;
+		    }
 		  public:
 		    /// \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.
 		    /// @{
 		    /// \brief Initializes the internal data structures.
 		    ///
 		    /// Initializes the internal data structures.
 		    void init() {
 		      create_maps();
 		      _list.resize(countNodes(*_digraph));
 		      _list_front = _list_back = -1;

lemon/bin_heap.h

Show inline comments

@@ -10,338 +10,338 @@
 		 * 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_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>
 		#include <functional>
 		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.
 		  ///
 		  ///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 Comp 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 binary \e heap data structure.
 		  /// It fully conforms to the \ref concepts::Heap "heap concept".
 		  ///
 		  ///\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 Comp A functor class for the ordering of the priorities.
 		  ///The default is \c std::less<PR>.
 		  ///
 		  ///\sa FibHeap
 		  ///\sa Dijkstra
-		  template <typename PR, typename IM, typename Comp = std::less<PR> >
+		  /// \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
 		    typedef Comp Compare;
 		    /// 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
 		    /// \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 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();
+		    }
 		  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);
 		        hole = par;
 		        par = parent(hole);
+		      }
 		      move(p, hole);
 		      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;
+		        }
 		        if( !less(_data[child], p) )
 		          goto ok;
 		        move(_data[child], hole);
 		        hole = child;
-		        child = second_child(hole);
+		        child = secondChild(hole);
+		      }
 		      child--;
 		      if( child<length && less(_data[child], p) ) {
 		        move(_data[child], hole);
 		        hole=child;
+		      }
 		    ok:
 		      move(p, hole);
 		      return 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.
 		    ///
-		    /// 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) {
 		      int idx = _iim[i];
 		      if( idx < 0 ) {
 		        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];
 		      if( s>=0 )
 		        s=0;
 		      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) {
 		      switch (st) {
 		      case POST_HEAP:
 		      case PRE_HEAP:
 		        if (state(i) == IN_HEAP) {
 		          erase(i);
+		        }
 		        _iim[i] = st;
 		        break;
 		      case IN_HEAP:
 		        break;
+		      }
+		    }
-		    /// \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]);
 		      _iim.set(j, idx);
 		      _data[idx].first = j;
+		    }
 		  }; // class BinHeap
 		} // namespace lemon
 		#endif // LEMON_BIN_HEAP_H

lemon/bits/edge_set_extender.h

Show inline comments

@@ -528,49 +528,49 @@
 		    // Returns the running node of the iterator
 		    Node runningNode(const IncEdgeIt &e) const {
 		      return e.direction ? v(e) : u(e);
+		    }
 		    template <typename _Value>
 		    class ArcMap
 		      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
 		      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
 		    public:
 		      ArcMap(const Graph& _g)
+		      explicit ArcMap(const Graph& _g)
 			: Parent(_g) {}
 		      ArcMap(const Graph& _g, const _Value& _v)
 			: Parent(_g, _v) {}
 		      ArcMap& operator=(const ArcMap& cmap) {
 			return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 			return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class EdgeMap
 		      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
 		      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
 		    public:
 		      EdgeMap(const Graph& _g)
+		      explicit EdgeMap(const Graph& _g)
 			: Parent(_g) {}
 		      EdgeMap(const Graph& _g, const _Value& _v)
 			: Parent(_g, _v) {}
 		      EdgeMap& operator=(const EdgeMap& cmap) {
 			return operator=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      EdgeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);

lemon/bits/graph_extender.h

Show inline comments

@@ -595,73 +595,73 @@
 		    Node runningNode(const IncEdgeIt &edge) const {
 		      return edge._direction ? v(edge) : u(edge);
+		    }
 		    // Mappable extension
 		    template <typename _Value>
 		    class NodeMap
 		      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
 		      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
 		    public:
 		      NodeMap(const Graph& graph)
+		      explicit NodeMap(const Graph& graph)
 		        : Parent(graph) {}
 		      NodeMap(const Graph& graph, const _Value& value)
 		        : Parent(graph, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class ArcMap
 		      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
 		      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
 		    public:
 		      ArcMap(const Graph& graph)
+		      explicit ArcMap(const Graph& graph)
 		        : Parent(graph) {}
 		      ArcMap(const Graph& graph, const _Value& value)
 		        : Parent(graph, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename _Value>
 		    class EdgeMap
 		      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
 		      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
 		    public:
 		      EdgeMap(const Graph& graph)
+		      explicit EdgeMap(const Graph& graph)
 		        : Parent(graph) {}
 		      EdgeMap(const Graph& graph, const _Value& value)
 		        : Parent(graph, value) {}
 		    private:
 		      EdgeMap& operator=(const EdgeMap& cmap) {
 		        return operator=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      EdgeMap& operator=(const CMap& cmap) {

lemon/circulation.h

Show inline comments

@@ -63,42 +63,49 @@
 		    /// nodes.
 		    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef SM SupplyMap;
 		    /// \brief The type of the flow and supply values.
 		    typedef typename SupplyMap::Value Value;
 		    /// \brief The type of the map that stores the flow values.
 		    ///
 		    /// 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.
 		    ///
 		    /// This function instantiates a \ref FlowMap.
 		    /// \param digraph The digraph for which we would like to define
 		    /// the flow map.
 		    static FlowMap* createFlowMap(const Digraph& digraph) {
 		      return new FlowMap(digraph);
+		    }
 		    /// \brief The elevator type used by the algorithm.
 		    ///
 		    /// 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.
 		    ///
 		    /// This function instantiates an \ref Elevator.
 		    /// \param digraph The digraph for which we would like to define
 		    /// the elevator.
 		    /// \param max_level The maximum level of the elevator.
 		    static Elevator* createElevator(const Digraph& digraph, int max_level) {
 		      return new Elevator(digraph, max_level);
+		    }
 		    /// \brief The tolerance used by the algorithm
@@ -441,43 +448,45 @@
+		    }
 		    /// \brief Returns a const reference to the elevator.
 		    ///
 		    /// Returns a const reference to the elevator.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    const Elevator& elevator() const {
 		      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.
 		    ///@{
 		    /// Initializes the internal data structures.
 		    /// Initializes the internal data structures and sets all flow values
 		    /// to the lower bound.
 		    void init()
+		    {
 		      LEMON_DEBUG(checkBoundMaps(),
 		        "Upper bounds must be greater or equal to the lower bounds");

lemon/concepts/heap.h

Show inline comments

@@ -7,189 +7,211 @@
 		 * (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_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>
 		namespace lemon {
 		  namespace concepts {
 		    /// \addtogroup concept
 		    /// @{
 		    /// \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:
 		      /// 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;
 		      /// \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,
 		      /// 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 {}
-		      /// \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) {}
 		      template <typename _Heap>
 		      struct Constraints {
 		      public:
 		        void constraints() {
 		          typedef typename _Heap::Item OwnItem;
 		          typedef typename _Heap::Prio OwnPrio;
 		          typedef typename _Heap::State OwnState;

lemon/dfs.h

Show inline comments

@@ -403,26 +403,26 @@
 		        delete _dist;
 		        local_dist=false;
+		      }
 		      _dist = &m;
 		      return *this;
+		    }
 		  public:
 		    ///\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.
 		    ///@{
 		    ///\brief Initializes the internal data structures.
 		    ///
 		    ///Initializes the internal data structures.
 		    void init()
+		    {
 		      create_maps();
@@ -1355,26 +1355,26 @@
 		        delete _reached;
 		        local_reached=false;
+		      }
 		      _reached = &m;
 		      return *this;
+		    }
 		  public:
 		    /// \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.
 		    /// @{
 		    /// \brief Initializes the internal data structures.
 		    ///
 		    /// Initializes the internal data structures.
 		    void init() {
 		      create_maps();
 		      _stack.resize(countNodes(*_digraph));

lemon/dijkstra.h

Show inline comments

@@ -580,26 +580,26 @@
 		    void finalizeNodeData(Node v,Value dst)
+		    {
 		      _processed->set(v,true);
 		      _dist->set(v, dst);
+		    }
 		  public:
 		    ///\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.
 		    ///@{
 		    ///\brief Initializes the internal data structures.
 		    ///
 		    ///Initializes the internal data structures.
 		    void init()
+		    {
 		      create_maps();
 		      _heap->clear();

lemon/dim2.h

Show inline comments

@@ -12,44 +12,37 @@
+		 *
 		 * 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_DIM2_H
 		#define LEMON_DIM2_H
 		#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 {
 		  ///Tools for handling two dimensional coordinates
 		  ///This namespace is a storage of several
 		  ///tools for handling two dimensional coordinates
 		  namespace dim2 {
-		  /// \addtogroup misc
+		  /// \addtogroup geomdat
 		  /// @{
 		  /// Two dimensional vector (plain vector)
 		  /// A simple two dimensional vector (plain vector) implementation
 		  /// with the usual vector operations.
 		  template<typename T>
 		    class Point {
 		    public:
 		      typedef T Value;

lemon/gomory_hu.h

Show inline comments

@@ -350,28 +350,28 @@
 		    friend class MinCutNodeIt;
 		    /// Iterate on the nodes of a minimum cut
 		    /// This iterator class lists the nodes of a minimum cut found by
 		    /// GomoryHu. Before using it, you must allocate a GomoryHu class
 		    /// and call its \ref GomoryHu::run() "run()" method.
 		    ///
 		    /// 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
+		    {
 		      bool _side;
 		      typename Graph::NodeIt _node_it;
 		      typename Graph::template NodeMap<bool> _cut;
 		    public:
 		      /// Constructor
 		      /// Constructor.
 		      ///
 		      MinCutNodeIt(GomoryHu const &gomory,
@@ -447,28 +447,28 @@
 		    friend class MinCutEdgeIt;
 		    /// Iterate on the edges of a minimum cut
 		    /// This iterator class lists the edges of a minimum cut found by
 		    /// GomoryHu. Before using it, you must allocate a GomoryHu class
 		    /// and call its \ref GomoryHu::run() "run()" method.
 		    ///
 		    /// 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
 		    /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)".
 		    class MinCutEdgeIt
+		    {
 		      bool _side;
 		      const Graph &_graph;
 		      typename Graph::NodeIt _node_it;
 		      typename Graph::OutArcIt _arc_it;
 		      typename Graph::template NodeMap<bool> _cut;
 		      void step()

lemon/maps.h

Show inline comments

@@ -13,33 +13,32 @@
 		 * 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_MAPS_H
 		#define LEMON_MAPS_H
 		#include <iterator>
 		#include <functional>
 		#include <vector>
 		#include <map>
 		#include <lemon/core.h>
 		///\file
 		///\ingroup maps
 		///\brief Miscellaneous property maps
 		#include <map>
 		namespace lemon {
 		  /// \addtogroup maps
 		  /// @{
 		  /// Base class of maps.
 		  /// Base class of maps. It provides the necessary type definitions
 		  /// required by the map %concepts.
 		  template<typename K, typename V>
 		  class MapBase {
 		  public:
@@ -1809,25 +1808,25 @@
 		  inline LoggerBoolMap<Iterator> loggerBoolMap(Iterator it) {
 		    return LoggerBoolMap<Iterator>(it);
+		  }
 		  /// @}
 		  /// \addtogroup graph_maps
 		  /// @{
 		  /// \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).
 		  ///
 		  /// 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.
 		  ///
 		  /// \tparam GR The graph type.
 		  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
 		  /// \c GR::Edge).
@@ -1893,70 +1892,73 @@
 		    };
 		    /// \brief Gives back the inverse of the map.
 		    ///
 		    /// Gives back the inverse of the IdMap.
 		    InverseMap inverse() const { return InverseMap(*_graph);}
 		  };
 		  /// \brief General cross reference graph map type.
 		  /// This class provides simple invertable graph maps.
 		  /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap"
 		  /// and if a key is set to a new value then store it
 		  /// in the inverse map.
 		  ///
 		  /// 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.
 		  ///
 		  /// 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.
 		  ///
 		  /// \see IterableValueMap
 		  template <typename GR, typename K, typename V>
 		  class CrossRefMap
 		    : protected ItemSetTraits<GR, K>::template Map<V>::Type {
 		  private:
 		    typedef typename ItemSetTraits<GR, K>::
 		      template Map<V>::Type Map;
-		    typedef std::map<V, K> Container;
+		    typedef std::multimap<V, K> Container;
 		    Container _inv_map;
 		  public:
 		    /// The graph type of CrossRefMap.
 		    typedef GR Graph;
 		    typedef GR Digraph;
 		    /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge).
 		    typedef K Item;
 		    /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge).
 		    typedef K Key;
 		    /// The value type of CrossRefMap.
 		    typedef V Value;
 		    /// \brief Constructor.
 		    ///
 		    /// Construct a new CrossRefMap for the given graph.
 		    explicit CrossRefMap(const Graph& graph) : Map(graph) {}
 		    /// \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.
 		    /// They are considered with multiplicity, so each value is
 		    /// traversed for each item it is assigned to.
 		    class ValueIterator
 		      : public std::iterator<std::forward_iterator_tag, Value> {
 		      friend class CrossRefMap;
 		    private:
 		      ValueIterator(typename Container::const_iterator _it)
 		        : it(_it) {}
 		    public:
 		      ValueIterator() {}
 		      ValueIterator& operator++() { ++it; return *this; }
 		      ValueIterator operator++(int) {
@@ -1991,73 +1993,88 @@
 		    /// 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());
+		    }
 		    /// \brief Sets the value associated with the given key.
 		    ///
 		    /// Sets the value associated with the given key.
 		    void set(const Key& key, const Value& val) {
 		      Value oldval = Map::operator[](key);
 		      typename Container::iterator it = _inv_map.find(oldval);
 		      if (it != _inv_map.end() && it->second == key) {
-		        _inv_map.erase(it);
+		      typename Container::iterator it;
 		      for (it = _inv_map.equal_range(oldval).first;
 		           it != _inv_map.equal_range(oldval).second; ++it) {
 		        if (it->second == key) {
 		          _inv_map.erase(it);
 		          break;
+		        }
+		      }
 		      _inv_map.insert(make_pair(val, key));
+		      _inv_map.insert(std::make_pair(val, key));
 		      Map::set(key, val);
+		    }
 		    /// \brief Returns the value associated with the given key.
 		    ///
 		    /// Returns the value associated with the given key.
 		    typename MapTraits<Map>::ConstReturnValue
 		    operator[](const Key& key) const {
 		      return Map::operator[](key);
+		    }
-		    /// \brief Gives back the item by its value.
+		    /// \brief Gives back an item by its value.
 		    ///
 		    /// Gives back the item by its value.
 		    Key operator()(const Value& key) const {
-		      typename Container::const_iterator it = _inv_map.find(key);
+		    /// This function gives back an item that is assigned to
 		    /// the given value or \c INVALID if no such item exists.
 		    /// If there are more items with the same associated value,
 		    /// only one of them is returned.
 		    Key operator()(const Value& val) const {
 		      typename Container::const_iterator it = _inv_map.find(val);
 		      return it != _inv_map.end() ? it->second : INVALID;
+		    }
 		  protected:
 		    /// \brief Erase the key from the map and the inverse map.
 		    ///
 		    /// Erase the key from the map and the inverse map. It is called by the
 		    /// \c AlterationNotifier.
 		    virtual void erase(const Key& key) {
 		      Value val = Map::operator[](key);
 		      typename Container::iterator it = _inv_map.find(val);
 		      if (it != _inv_map.end() && it->second == key) {
-		        _inv_map.erase(it);
+		      typename Container::iterator it;
 		      for (it = _inv_map.equal_range(val).first;
 		           it != _inv_map.equal_range(val).second; ++it) {
 		        if (it->second == key) {
 		          _inv_map.erase(it);
 		          break;
+		        }
+		      }
 		      Map::erase(key);
+		    }
 		    /// \brief Erase more keys from the map and the inverse map.
 		    ///
 		    /// Erase more keys from the map and the inverse map. It is called by the
 		    /// \c AlterationNotifier.
 		    virtual void erase(const std::vector<Key>& keys) {
 		      for (int i = 0; i < int(keys.size()); ++i) {
 		        Value val = Map::operator[](keys[i]);
 		        typename Container::iterator it = _inv_map.find(val);
 		        if (it != _inv_map.end() && it->second == keys[i]) {
-		          _inv_map.erase(it);
+		        typename Container::iterator it;
 		        for (it = _inv_map.equal_range(val).first;
 		             it != _inv_map.equal_range(val).second; ++it) {
 		          if (it->second == keys[i]) {
 		            _inv_map.erase(it);
 		            break;
+		          }
+		        }
+		      }
 		      Map::erase(keys);
+		    }
 		    /// \brief Clear the keys from the map and the inverse map.
 		    ///
 		    /// Clear the keys from the map and the inverse map. It is called by the
 		    /// \c AlterationNotifier.
 		    virtual void clear() {
 		      _inv_map.clear();
 		      Map::clear();
@@ -2075,26 +2092,27 @@
 		      ///
 		      /// Constructor of the InverseMap.
 		      explicit InverseMap(const CrossRefMap& inverted)
 		        : _inverted(inverted) {}
 		      /// The value type of the InverseMap.
 		      typedef typename CrossRefMap::Key Value;
 		      /// The key type of the InverseMap.
 		      typedef typename CrossRefMap::Value Key;
 		      /// \brief Subscript operator.
 		      ///
 		      /// Subscript operator. It gives back the item
 		      /// that was last assigned to the given value.
 		      /// Subscript operator. It gives back an item
 		      /// that is assigned to the given value or \c INVALID
 		      /// if no such item exists.
 		      Value operator[](const Key& key) const {
 		        return _inverted(key);
+		      }
 		    private:
 		      const CrossRefMap& _inverted;
 		    };
 		    /// \brief It gives back the read-only inverse map.
 		    ///
 		    /// It gives back the read-only inverse map.
 		    InverseMap inverse() const {
@@ -2245,25 +2263,25 @@
 		      Map::set(q, pi);
 		      _inv_map[pi] = q;
+		    }
 		    /// \brief Gives back the \e RangeId of the item
 		    ///
 		    /// Gives back the \e RangeId of the item.
 		    int operator[](const Item& item) const {
 		      return Map::operator[](item);
+		    }
 		    /// \brief Gives back the item belonging to a \e RangeId
-		    ///
 		    ///
 		    /// Gives back the item belonging to a \e RangeId.
 		    Item operator()(int id) const {
 		      return _inv_map[id];
+		    }
 		  private:
 		    typedef std::vector<Item> Container;
 		    Container _inv_map;
 		  public:
@@ -2302,24 +2320,921 @@
 		    private:
 		      const RangeIdMap& _inverted;
 		    };
 		    /// \brief Gives back the inverse of the map.
 		    ///
 		    /// Gives back the inverse of the map.
 		    const InverseMap inverse() const {
 		      return InverseMap(*this);
+		    }
 		  };
 		  /// \brief Dynamic iterable \c bool map.
 		  ///
 		  /// This class provides a special graph map type which can store a
 		  /// \c bool value for graph items (\c Node, \c Arc or \c Edge).
 		  /// For both \c true and \c false values it is possible to iterate on
 		  /// the keys.
 		  ///
 		  /// This type is a reference map, so it can be modified with the
 		  /// subscript operator.
 		  ///
 		  /// \tparam GR The graph type.
 		  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
 		  /// \c GR::Edge).
 		  ///
 		  /// \see IterableIntMap, IterableValueMap
 		  /// \see CrossRefMap
 		  template <typename GR, typename K>
 		  class IterableBoolMap
 		    : protected ItemSetTraits<GR, K>::template Map<int>::Type {
 		  private:
 		    typedef GR Graph;
 		    typedef typename ItemSetTraits<GR, K>::ItemIt KeyIt;
 		    typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Parent;
 		    std::vector<K> _array;
 		    int _sep;
 		  public:
 		    /// Indicates that the map is reference map.
 		    typedef True ReferenceMapTag;
 		    /// The key type
 		    typedef K Key;
 		    /// The value type
 		    typedef bool Value;
 		    /// The const reference type.
 		    typedef const Value& ConstReference;
 		  private:
 		    int position(const Key& key) const {
 		      return Parent::operator[](key);
+		    }
 		  public:
 		    /// \brief Reference to the value of the map.
 		    ///
 		    /// This class is similar to the \c bool type. It can be converted to
 		    /// \c bool and it provides the same operators.
 		    class Reference {
 		      friend class IterableBoolMap;
 		    private:
 		      Reference(IterableBoolMap& map, const Key& key)
 		        : _key(key), _map(map) {}
 		    public:
 		      Reference& operator=(const Reference& value) {
 		        _map.set(_key, static_cast<bool>(value));
 		         return *this;
+		      }
 		      operator bool() const {
 		        return static_cast<const IterableBoolMap&>(_map)[_key];
+		      }
 		      Reference& operator=(bool value) {
 		        _map.set(_key, value);
 		        return *this;
+		      }
 		      Reference& operator&=(bool value) {
 		        _map.set(_key, _map[_key] & value);
 		        return *this;
+		      }
 		      Reference& operator|=(bool value) {
 		        _map.set(_key, _map[_key] | value);
 		        return *this;
+		      }
 		      Reference& operator^=(bool value) {
 		        _map.set(_key, _map[_key] ^ value);
 		        return *this;
+		      }
 		    private:
 		      Key _key;
 		      IterableBoolMap& _map;
 		    };
 		    /// \brief Constructor of the map with a default value.
 		    ///
 		    /// Constructor of the map with a default value.
 		    explicit IterableBoolMap(const Graph& graph, bool def = false)
 		      : Parent(graph) {
 		      typename Parent::Notifier* nf = Parent::notifier();
 		      Key it;
 		      for (nf->first(it); it != INVALID; nf->next(it)) {
 		        Parent::set(it, _array.size());
 		        _array.push_back(it);
+		      }
 		      _sep = (def ? _array.size() : 0);
+		    }
 		    /// \brief Const subscript operator of the map.
 		    ///
 		    /// Const subscript operator of the map.
 		    bool operator[](const Key& key) const {
 		      return position(key) < _sep;
+		    }
 		    /// \brief Subscript operator of the map.
 		    ///
 		    /// Subscript operator of the map.
 		    Reference operator[](const Key& key) {
 		      return Reference(*this, key);
+		    }
 		    /// \brief Set operation of the map.
 		    ///
 		    /// Set operation of the map.
 		    void set(const Key& key, bool value) {
 		      int pos = position(key);
 		      if (value) {
 		        if (pos < _sep) return;
 		        Key tmp = _array[_sep];
 		        _array[_sep] = key;
 		        Parent::set(key, _sep);
 		        _array[pos] = tmp;
 		        Parent::set(tmp, pos);
 		        ++_sep;
 		      } else {
 		        if (pos >= _sep) return;
 		        --_sep;
 		        Key tmp = _array[_sep];
 		        _array[_sep] = key;
 		        Parent::set(key, _sep);
 		        _array[pos] = tmp;
 		        Parent::set(tmp, pos);
+		      }
+		    }
 		    /// \brief Set all items.
 		    ///
 		    /// Set all items in the map.
 		    /// \note Constant time operation.
 		    void setAll(bool value) {
 		      _sep = (value ? _array.size() : 0);
+		    }
 		    /// \brief Returns the number of the keys mapped to \c true.
 		    ///
 		    /// Returns the number of the keys mapped to \c true.
 		    int trueNum() const {
 		      return _sep;
+		    }
 		    /// \brief Returns the number of the keys mapped to \c false.
 		    ///
 		    /// Returns the number of the keys mapped to \c false.
 		    int falseNum() const {
 		      return _array.size() - _sep;
+		    }
 		    /// \brief Iterator for the keys mapped to \c true.
 		    ///
 		    /// Iterator for the keys mapped to \c true. It works
 		    /// like a graph item iterator, it can be converted to
 		    /// the key type of the map, incremented with \c ++ operator, and
 		    /// if the iterator leaves the last valid key, it will be equal to
 		    /// \c INVALID.
 		    class TrueIt : public Key {
 		    public:
 		      typedef Key Parent;
 		      /// \brief Creates an iterator.
 		      ///
 		      /// Creates an iterator. It iterates on the
 		      /// keys mapped to \c true.
 		      /// \param map The IterableBoolMap.
 		      explicit TrueIt(const IterableBoolMap& map)
 		        : Parent(map._sep > 0 ? map._array[map._sep - 1] : INVALID),
 		          _map(&map) {}
 		      /// \brief Invalid constructor \& conversion.
 		      ///
 		      /// This constructor initializes the iterator to be invalid.
 		      /// \sa Invalid for more details.
 		      TrueIt(Invalid) : Parent(INVALID), _map(0) {}
 		      /// \brief Increment operator.
 		      ///
 		      /// Increment operator.
 		      TrueIt& operator++() {
 		        int pos = _map->position(*this);
 		        Parent::operator=(pos > 0 ? _map->_array[pos - 1] : INVALID);
 		        return *this;
+		      }
 		    private:
 		      const IterableBoolMap* _map;
 		    };
 		    /// \brief Iterator for the keys mapped to \c false.
 		    ///
 		    /// Iterator for the keys mapped to \c false. It works
 		    /// like a graph item iterator, it can be converted to
 		    /// the key type of the map, incremented with \c ++ operator, and
 		    /// if the iterator leaves the last valid key, it will be equal to
 		    /// \c INVALID.
 		    class FalseIt : public Key {
 		    public:
 		      typedef Key Parent;
 		      /// \brief Creates an iterator.
 		      ///
 		      /// Creates an iterator. It iterates on the
 		      /// keys mapped to \c false.
 		      /// \param map The IterableBoolMap.
 		      explicit FalseIt(const IterableBoolMap& map)
 		        : Parent(map._sep < int(map._array.size()) ?
 		                 map._array.back() : INVALID), _map(&map) {}
 		      /// \brief Invalid constructor \& conversion.
 		      ///
 		      /// This constructor initializes the iterator to be invalid.
 		      /// \sa Invalid for more details.
 		      FalseIt(Invalid) : Parent(INVALID), _map(0) {}
 		      /// \brief Increment operator.
 		      ///
 		      /// Increment operator.
 		      FalseIt& operator++() {
 		        int pos = _map->position(*this);
 		        Parent::operator=(pos > _map->_sep ? _map->_array[pos - 1] : INVALID);
 		        return *this;
+		      }
 		    private:
 		      const IterableBoolMap* _map;
 		    };
 		    /// \brief Iterator for the keys mapped to a given value.
 		    ///
 		    /// Iterator for the keys mapped to a given value. It works
 		    /// like a graph item iterator, it can be converted to
 		    /// the key type of the map, incremented with \c ++ operator, and
 		    /// if the iterator leaves the last valid key, it will be equal to
 		    /// \c INVALID.
 		    class ItemIt : public Key {
 		    public:
 		      typedef Key Parent;
 		      /// \brief Creates an iterator with a value.
 		      ///
 		      /// Creates an iterator with a value. It iterates on the
 		      /// keys mapped to the given value.
 		      /// \param map The IterableBoolMap.
 		      /// \param value The value.
 		      ItemIt(const IterableBoolMap& map, bool value)
 		        : Parent(value ?
 		                 (map._sep > 0 ?
 		                  map._array[map._sep - 1] : INVALID) :
 		                 (map._sep < int(map._array.size()) ?
 		                  map._array.back() : INVALID)), _map(&map) {}
 		      /// \brief Invalid constructor \& conversion.
 		      ///
 		      /// This constructor initializes the iterator to be invalid.
 		      /// \sa Invalid for more details.
 		      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
 		      /// \brief Increment operator.
 		      ///
 		      /// Increment operator.
 		      ItemIt& operator++() {
 		        int pos = _map->position(*this);
 		        int _sep = pos >= _map->_sep ? _map->_sep : 0;
 		        Parent::operator=(pos > _sep ? _map->_array[pos - 1] : INVALID);
 		        return *this;
+		      }
 		    private:
 		      const IterableBoolMap* _map;
 		    };
 		  protected:
 		    virtual void add(const Key& key) {
 		      Parent::add(key);
 		      Parent::set(key, _array.size());
 		      _array.push_back(key);
+		    }
 		    virtual void add(const std::vector<Key>& keys) {
 		      Parent::add(keys);
 		      for (int i = 0; i < int(keys.size()); ++i) {
 		        Parent::set(keys[i], _array.size());
 		        _array.push_back(keys[i]);
+		      }
+		    }
 		    virtual void erase(const Key& key) {
 		      int pos = position(key);
 		      if (pos < _sep) {
 		        --_sep;
 		        Parent::set(_array[_sep], pos);
 		        _array[pos] = _array[_sep];
 		        Parent::set(_array.back(), _sep);
 		        _array[_sep] = _array.back();
 		        _array.pop_back();
 		      } else {
 		        Parent::set(_array.back(), pos);
 		        _array[pos] = _array.back();
 		        _array.pop_back();
+		      }
 		      Parent::erase(key);
+		    }
 		    virtual void erase(const std::vector<Key>& keys) {
 		      for (int i = 0; i < int(keys.size()); ++i) {
 		        int pos = position(keys[i]);
 		        if (pos < _sep) {
 		          --_sep;
 		          Parent::set(_array[_sep], pos);
 		          _array[pos] = _array[_sep];
 		          Parent::set(_array.back(), _sep);
 		          _array[_sep] = _array.back();
 		          _array.pop_back();
 		        } else {
 		          Parent::set(_array.back(), pos);
 		          _array[pos] = _array.back();
 		          _array.pop_back();
+		        }
+		      }
 		      Parent::erase(keys);
+		    }
 		    virtual void build() {
 		      Parent::build();
 		      typename Parent::Notifier* nf = Parent::notifier();
 		      Key it;
 		      for (nf->first(it); it != INVALID; nf->next(it)) {
 		        Parent::set(it, _array.size());
 		        _array.push_back(it);
+		      }
 		      _sep = 0;
+		    }
 		    virtual void clear() {
 		      _array.clear();
 		      _sep = 0;
 		      Parent::clear();
+		    }
 		  };
 		  namespace _maps_bits {
 		    template <typename Item>
 		    struct IterableIntMapNode {
 		      IterableIntMapNode() : value(-1) {}
 		      IterableIntMapNode(int _value) : value(_value) {}
 		      Item prev, next;
 		      int value;
 		    };
+		  }
 		  /// \brief Dynamic iterable integer map.
 		  ///
 		  /// This class provides a special graph map type which can store an
 		  /// integer value for graph items (\c Node, \c Arc or \c Edge).
 		  /// For each non-negative value it is possible to iterate on the keys
 		  /// mapped to the value.
 		  ///
 		  /// This type is a reference map, so it can be modified with the
 		  /// subscript operator.
 		  ///
 		  /// \note The size of the data structure depends on the largest
 		  /// value in the map.
 		  ///
 		  /// \tparam GR The graph type.
 		  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
 		  /// \c GR::Edge).
 		  ///
 		  /// \see IterableBoolMap, IterableValueMap
 		  /// \see CrossRefMap
 		  template <typename GR, typename K>
 		  class IterableIntMap
 		    : protected ItemSetTraits<GR, K>::
 		        template Map<_maps_bits::IterableIntMapNode<K> >::Type {
 		  public:
 		    typedef typename ItemSetTraits<GR, K>::
 		      template Map<_maps_bits::IterableIntMapNode<K> >::Type Parent;
 		    /// The key type
 		    typedef K Key;
 		    /// The value type
 		    typedef int Value;
 		    /// The graph type
 		    typedef GR Graph;
 		    /// \brief Constructor of the map.
 		    ///
 		    /// Constructor of the map. It sets all values to -1.
 		    explicit IterableIntMap(const Graph& graph)
 		      : Parent(graph) {}
 		    /// \brief Constructor of the map with a given value.
 		    ///
 		    /// Constructor of the map with a given value.
 		    explicit IterableIntMap(const Graph& graph, int value)
 		      : Parent(graph, _maps_bits::IterableIntMapNode<K>(value)) {
 		      if (value >= 0) {
 		        for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
 		          lace(it);
+		        }
+		      }
+		    }
 		  private:
 		    void unlace(const Key& key) {
 		      typename Parent::Value& node = Parent::operator[](key);
 		      if (node.value < 0) return;
 		      if (node.prev != INVALID) {
 		        Parent::operator[](node.prev).next = node.next;
 		      } else {
 		        _first[node.value] = node.next;
+		      }
 		      if (node.next != INVALID) {
 		        Parent::operator[](node.next).prev = node.prev;
+		      }
 		      while (!_first.empty() && _first.back() == INVALID) {
 		        _first.pop_back();
+		      }
+		    }
 		    void lace(const Key& key) {
 		      typename Parent::Value& node = Parent::operator[](key);
 		      if (node.value < 0) return;
 		      if (node.value >= int(_first.size())) {
 		        _first.resize(node.value + 1, INVALID);
+		      }
 		      node.prev = INVALID;
 		      node.next = _first[node.value];
 		      if (node.next != INVALID) {
 		        Parent::operator[](node.next).prev = key;
+		      }
 		      _first[node.value] = key;
+		    }
 		  public:
 		    /// Indicates that the map is reference map.
 		    typedef True ReferenceMapTag;
 		    /// \brief Reference to the value of the map.
 		    ///
 		    /// This class is similar to the \c int type. It can
 		    /// be converted to \c int and it has the same operators.
 		    class Reference {
 		      friend class IterableIntMap;
 		    private:
 		      Reference(IterableIntMap& map, const Key& key)
 		        : _key(key), _map(map) {}
 		    public:
 		      Reference& operator=(const Reference& value) {
 		        _map.set(_key, static_cast<const int&>(value));
 		         return *this;
+		      }
 		      operator const int&() const {
 		        return static_cast<const IterableIntMap&>(_map)[_key];
+		      }
 		      Reference& operator=(int value) {
 		        _map.set(_key, value);
 		        return *this;
+		      }
 		      Reference& operator++() {
 		        _map.set(_key, _map[_key] + 1);
 		        return *this;
+		      }
 		      int operator++(int) {
 		        int value = _map[_key];
 		        _map.set(_key, value + 1);
 		        return value;
+		      }
 		      Reference& operator--() {
 		        _map.set(_key, _map[_key] - 1);
 		        return *this;
+		      }
 		      int operator--(int) {
 		        int value = _map[_key];
 		        _map.set(_key, value - 1);
 		        return value;
+		      }
 		      Reference& operator+=(int value) {
 		        _map.set(_key, _map[_key] + value);
 		        return *this;
+		      }
 		      Reference& operator-=(int value) {
 		        _map.set(_key, _map[_key] - value);
 		        return *this;
+		      }
 		      Reference& operator*=(int value) {
 		        _map.set(_key, _map[_key] * value);
 		        return *this;
+		      }
 		      Reference& operator/=(int value) {
 		        _map.set(_key, _map[_key] / value);
 		        return *this;
+		      }
 		      Reference& operator%=(int value) {
 		        _map.set(_key, _map[_key] % value);
 		        return *this;
+		      }
 		      Reference& operator&=(int value) {
 		        _map.set(_key, _map[_key] & value);
 		        return *this;
+		      }
 		      Reference& operator|=(int value) {
 		        _map.set(_key, _map[_key] | value);
 		        return *this;
+		      }
 		      Reference& operator^=(int value) {
 		        _map.set(_key, _map[_key] ^ value);
 		        return *this;
+		      }
 		      Reference& operator<<=(int value) {
 		        _map.set(_key, _map[_key] << value);
 		        return *this;
+		      }
 		      Reference& operator>>=(int value) {
 		        _map.set(_key, _map[_key] >> value);
 		        return *this;
+		      }
 		    private:
 		      Key _key;
 		      IterableIntMap& _map;
 		    };
 		    /// The const reference type.
 		    typedef const Value& ConstReference;
 		    /// \brief Gives back the maximal value plus one.
 		    ///
 		    /// Gives back the maximal value plus one.
 		    int size() const {
 		      return _first.size();
+		    }
 		    /// \brief Set operation of the map.
 		    ///
 		    /// Set operation of the map.
 		    void set(const Key& key, const Value& value) {
 		      unlace(key);
 		      Parent::operator[](key).value = value;
 		      lace(key);
+		    }
 		    /// \brief Const subscript operator of the map.
 		    ///
 		    /// Const subscript operator of the map.
 		    const Value& operator[](const Key& key) const {
 		      return Parent::operator[](key).value;
+		    }
 		    /// \brief Subscript operator of the map.
 		    ///
 		    /// Subscript operator of the map.
 		    Reference operator[](const Key& key) {
 		      return Reference(*this, key);
+		    }
 		    /// \brief Iterator for the keys with the same value.
 		    ///
 		    /// Iterator for the keys with the same value. It works
 		    /// like a graph item iterator, it can be converted to
 		    /// the item type of the map, incremented with \c ++ operator, and
 		    /// if the iterator leaves the last valid item, it will be equal to
 		    /// \c INVALID.
 		    class ItemIt : public Key {
 		    public:
 		      typedef Key Parent;
 		      /// \brief Invalid constructor \& conversion.
 		      ///
 		      /// This constructor initializes the iterator to be invalid.
 		      /// \sa Invalid for more details.
 		      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
 		      /// \brief Creates an iterator with a value.
 		      ///
 		      /// Creates an iterator with a value. It iterates on the
 		      /// keys mapped to the given value.
 		      /// \param map The IterableIntMap.
 		      /// \param value The value.
 		      ItemIt(const IterableIntMap& map, int value) : _map(&map) {
 		        if (value < 0 || value >= int(_map->_first.size())) {
 		          Parent::operator=(INVALID);
 		        } else {
 		          Parent::operator=(_map->_first[value]);
+		        }
+		      }
 		      /// \brief Increment operator.
 		      ///
 		      /// Increment operator.
 		      ItemIt& operator++() {
 		        Parent::operator=(_map->IterableIntMap::Parent::
 		                          operator[](static_cast<Parent&>(*this)).next);
 		        return *this;
+		      }
 		    private:
 		      const IterableIntMap* _map;
 		    };
 		  protected:
 		    virtual void erase(const Key& key) {
 		      unlace(key);
 		      Parent::erase(key);
+		    }
 		    virtual void erase(const std::vector<Key>& keys) {
 		      for (int i = 0; i < int(keys.size()); ++i) {
 		        unlace(keys[i]);
+		      }
 		      Parent::erase(keys);
+		    }
 		    virtual void clear() {
 		      _first.clear();
 		      Parent::clear();
+		    }
 		  private:
 		    std::vector<Key> _first;
 		  };
 		  namespace _maps_bits {
 		    template <typename Item, typename Value>
 		    struct IterableValueMapNode {
 		      IterableValueMapNode(Value _value = Value()) : value(_value) {}
 		      Item prev, next;
 		      Value value;
 		    };
+		  }
 		  /// \brief Dynamic iterable map for comparable values.
 		  ///
 		  /// This class provides a special graph map type which can store an
 		  /// comparable value for graph items (\c Node, \c Arc or \c Edge).
 		  /// For each value it is possible to iterate on the keys mapped to
 		  /// the value.
 		  ///
 		  /// The map stores for each value a linked list with
 		  /// the items which mapped to the value, and the values are stored
 		  /// in balanced binary tree. The values of the map can be accessed
 		  /// with stl compatible forward iterator.
 		  ///
 		  /// This type is not reference map, so it cannot be modified with
 		  /// the subscript operator.
 		  ///
 		  /// \tparam GR The graph type.
 		  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
 		  /// \c GR::Edge).
 		  /// \tparam V The value type of the map. It can be any comparable
 		  /// value type.
 		  ///
 		  /// \see IterableBoolMap, IterableIntMap
 		  /// \see CrossRefMap
 		  template <typename GR, typename K, typename V>
 		  class IterableValueMap
 		    : protected ItemSetTraits<GR, K>::
 		        template Map<_maps_bits::IterableValueMapNode<K, V> >::Type {
 		  public:
 		    typedef typename ItemSetTraits<GR, K>::
 		      template Map<_maps_bits::IterableValueMapNode<K, V> >::Type Parent;
 		    /// The key type
 		    typedef K Key;
 		    /// The value type
 		    typedef V Value;
 		    /// The graph type
 		    typedef GR Graph;
 		  public:
 		    /// \brief Constructor of the map with a given value.
 		    ///
 		    /// Constructor of the map with a given value.
 		    explicit IterableValueMap(const Graph& graph,
 		                              const Value& value = Value())
 		      : Parent(graph, _maps_bits::IterableValueMapNode<K, V>(value)) {
 		      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
 		        lace(it);
+		      }
+		    }
 		  protected:
 		    void unlace(const Key& key) {
 		      typename Parent::Value& node = Parent::operator[](key);
 		      if (node.prev != INVALID) {
 		        Parent::operator[](node.prev).next = node.next;
 		      } else {
 		        if (node.next != INVALID) {
 		          _first[node.value] = node.next;
 		        } else {
 		          _first.erase(node.value);
+		        }
+		      }
 		      if (node.next != INVALID) {
 		        Parent::operator[](node.next).prev = node.prev;
+		      }
+		    }
 		    void lace(const Key& key) {
 		      typename Parent::Value& node = Parent::operator[](key);
 		      typename std::map<Value, Key>::iterator it = _first.find(node.value);
 		      if (it == _first.end()) {
 		        node.prev = node.next = INVALID;
 		        _first.insert(std::make_pair(node.value, key));
 		      } else {
 		        node.prev = INVALID;
 		        node.next = it->second;
 		        if (node.next != INVALID) {
 		          Parent::operator[](node.next).prev = key;
+		        }
 		        it->second = key;
+		      }
+		    }
 		  public:
 		    /// \brief Forward iterator for values.
 		    ///
 		    /// This iterator is an stl compatible forward
 		    /// iterator on the values of the map. The values can
 		    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
 		    class ValueIterator
 		      : public std::iterator<std::forward_iterator_tag, Value> {
 		      friend class IterableValueMap;
 		    private:
 		      ValueIterator(typename std::map<Value, Key>::const_iterator _it)
 		        : it(_it) {}
 		    public:
 		      ValueIterator() {}
 		      ValueIterator& operator++() { ++it; return *this; }
 		      ValueIterator operator++(int) {
 		        ValueIterator tmp(*this);
 		        operator++();
 		        return tmp;
+		      }
 		      const Value& operator*() const { return it->first; }
 		      const Value* operator->() const { return &(it->first); }
 		      bool operator==(ValueIterator jt) const { return it == jt.it; }
 		      bool operator!=(ValueIterator jt) const { return it != jt.it; }
 		    private:
 		      typename std::map<Value, Key>::const_iterator it;
 		    };
 		    /// \brief Returns an iterator to the first value.
 		    ///
 		    /// Returns an stl compatible iterator to the
 		    /// first value of the map. The values of the
 		    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
 		    /// range.
 		    ValueIterator beginValue() const {
 		      return ValueIterator(_first.begin());
+		    }
 		    /// \brief Returns an iterator after the last value.
 		    ///
 		    /// Returns an stl compatible iterator after the
 		    /// last value of the map. The values of the
 		    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
 		    /// range.
 		    ValueIterator endValue() const {
 		      return ValueIterator(_first.end());
+		    }
 		    /// \brief Set operation of the map.
 		    ///
 		    /// Set operation of the map.
 		    void set(const Key& key, const Value& value) {
 		      unlace(key);
 		      Parent::operator[](key).value = value;
 		      lace(key);
+		    }
 		    /// \brief Const subscript operator of the map.
 		    ///
 		    /// Const subscript operator of the map.
 		    const Value& operator[](const Key& key) const {
 		      return Parent::operator[](key).value;
+		    }
 		    /// \brief Iterator for the keys with the same value.
 		    ///
 		    /// Iterator for the keys with the same value. It works
 		    /// like a graph item iterator, it can be converted to
 		    /// the item type of the map, incremented with \c ++ operator, and
 		    /// if the iterator leaves the last valid item, it will be equal to
 		    /// \c INVALID.
 		    class ItemIt : public Key {
 		    public:
 		      typedef Key Parent;
 		      /// \brief Invalid constructor \& conversion.
 		      ///
 		      /// This constructor initializes the iterator to be invalid.
 		      /// \sa Invalid for more details.
 		      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
 		      /// \brief Creates an iterator with a value.
 		      ///
 		      /// Creates an iterator with a value. It iterates on the
 		      /// keys which have the given value.
 		      /// \param map The IterableValueMap
 		      /// \param value The value
 		      ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) {
 		        typename std::map<Value, Key>::const_iterator it =
 		          map._first.find(value);
 		        if (it == map._first.end()) {
 		          Parent::operator=(INVALID);
 		        } else {
 		          Parent::operator=(it->second);
+		        }
+		      }
 		      /// \brief Increment operator.
 		      ///
 		      /// Increment Operator.
 		      ItemIt& operator++() {
 		        Parent::operator=(_map->IterableValueMap::Parent::
 		                          operator[](static_cast<Parent&>(*this)).next);
 		        return *this;
+		      }
 		    private:
 		      const IterableValueMap* _map;
 		    };
 		  protected:
 		    virtual void add(const Key& key) {
 		      Parent::add(key);
 		      unlace(key);
+		    }
 		    virtual void add(const std::vector<Key>& keys) {
 		      Parent::add(keys);
 		      for (int i = 0; i < int(keys.size()); ++i) {
 		        lace(keys[i]);
+		      }
+		    }
 		    virtual void erase(const Key& key) {
 		      unlace(key);
 		      Parent::erase(key);
+		    }
 		    virtual void erase(const std::vector<Key>& keys) {
 		      for (int i = 0; i < int(keys.size()); ++i) {
 		        unlace(keys[i]);
+		      }
 		      Parent::erase(keys);
+		    }
 		    virtual void build() {
 		      Parent::build();
 		      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
 		        lace(it);
+		      }
+		    }
 		    virtual void clear() {
 		      _first.clear();
 		      Parent::clear();
+		    }
 		  private:
 		    std::map<Value, Key> _first;
 		  };
 		  /// \brief Map of the source nodes of arcs in a digraph.
 		  ///
 		  /// SourceMap provides access for the source node of each arc in a digraph,
 		  /// which is returned by the \c source() function of the digraph.
 		  /// \tparam GR The digraph type.
 		  /// \see TargetMap
 		  template <typename GR>
 		  class SourceMap {
 		  public:
 		    ///\e
 		    typedef typename GR::Arc Key;
@@ -2471,41 +3386,41 @@
 		  template <typename GR>
 		  inline BackwardMap<GR> backwardMap(const GR& graph) {
 		    return BackwardMap<GR>(graph);
+		  }
 		  /// \brief Map of the in-degrees of nodes in a digraph.
 		  ///
 		  /// This map returns the in-degree of a node. Once it is constructed,
 		  /// the degrees are stored in a standard \c NodeMap, so each query is done
 		  /// 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
 		  /// \ref ListDigraph::changeSource() "changeSource()",
 		  /// \ref ListDigraph::changeTarget() "changeTarget()" and
 		  /// \ref ListDigraph::reverseArc() "reverseArc()"
 		  /// of \ref ListDigraph will \e not update the degree values correctly.
 		  ///
 		  /// \sa OutDegMap
 		  template <typename GR>
 		  class InDegMap
 		    : protected ItemSetTraits<GR, typename GR::Arc>
 		      ::ItemNotifier::ObserverBase {
 		  public:
 		    /// The graph type of InDegMap
 		    typedef GR Graph;
 		    typedef GR Digraph;
 		    /// The key type
 		    typedef typename Digraph::Node Key;
 		    /// The value type
 		    typedef int Value;
 		    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
 		    ::ItemNotifier::ObserverBase Parent;
 		  private:
@@ -2601,25 +3516,25 @@
 		    const Digraph& _digraph;
 		    AutoNodeMap _deg;
 		  };
 		  /// \brief Map of the out-degrees of nodes in a digraph.
 		  ///
 		  /// This map returns the out-degree of a node. Once it is constructed,
 		  /// the degrees are stored in a standard \c NodeMap, so each query is done
 		  /// 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
 		  /// \ref ListDigraph::changeSource() "changeSource()",
 		  /// \ref ListDigraph::changeTarget() "changeTarget()" and
 		  /// \ref ListDigraph::reverseArc() "reverseArc()"
 		  /// of \ref ListDigraph will \e not update the degree values correctly.
 		  ///
 		  /// \sa InDegMap
 		  template <typename GR>
 		  class OutDegMap
 		    : protected ItemSetTraits<GR, typename GR::Arc>

lemon/min_cost_arborescence.h

Show inline comments

@@ -479,26 +479,26 @@
 		    MinCostArborescence& predMap(PredMap& m) {
 		      if (local_pred) {
 		        delete _pred;
+		      }
 		      local_pred = false;
 		      _pred = &m;
 		      return *this;
+		    }
 		    /// \name Execution Control
 		    /// The simplest way to execute the algorithm is to use
 		    /// one of the member functions called \c run(...). \n
 		    /// If you need more control on the execution,
 		    /// first you must call \ref init(), then you can add several
 		    /// 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.
 		    ///@{
 		    /// \brief Initializes the internal data structures.
 		    ///
 		    /// Initializes the internal data structures.
 		    ///
 		    void init() {
 		      createStructures();

lemon/preflow.h

Show inline comments

@@ -43,42 +43,49 @@
 		    ///
 		    /// The type of the map that stores the arc capacities.
 		    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef CAP CapacityMap;
 		    /// \brief The type of the flow values.
 		    typedef typename CapacityMap::Value Value;
 		    /// \brief The type of the map that stores the flow values.
 		    ///
 		    /// The type of the map that stores the flow values.
 		    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		#ifdef DOXYGEN
 		    typedef GR::ArcMap<Value> FlowMap;
 		#else
 		    typedef typename Digraph::template ArcMap<Value> FlowMap;
 		#endif
 		    /// \brief Instantiates a FlowMap.
 		    ///
 		    /// This function instantiates a \ref FlowMap.
 		    /// \param digraph The digraph for which we would like to define
 		    /// the flow map.
 		    static FlowMap* createFlowMap(const Digraph& digraph) {
 		      return new FlowMap(digraph);
+		    }
 		    /// \brief The elevator type used by Preflow algorithm.
 		    ///
 		    /// The elevator type used by Preflow algorithm.
 		    ///
 		    /// \sa Elevator
 		    /// \sa LinkedElevator
-		    typedef LinkedElevator<Digraph, typename Digraph::Node> Elevator;
+		    /// \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.
 		    ///
 		    /// This function instantiates an \ref Elevator.
 		    /// \param digraph The digraph for which we would like to define
 		    /// the elevator.
 		    /// \param max_level The maximum level of the elevator.
 		    static Elevator* createElevator(const Digraph& digraph, int max_level) {
 		      return new Elevator(digraph, max_level);
+		    }
 		    /// \brief The tolerance used by the algorithm
@@ -88,25 +95,25 @@
 		  };
 		  /// \ingroup max_flow
 		  ///
 		  /// \brief %Preflow algorithm class.
 		  ///
 		  /// This class provides an implementation of Goldberg-Tarjan's \e preflow
 		  /// \e push-relabel algorithm producing a \ref max_flow
 		  /// "flow of maximum value" in a digraph.
 		  /// The preflow algorithms are the fastest known maximum
-		  /// flow algorithms. The current implementation use a mixture of the
+		  /// flow algorithms. The current implementation uses a mixture of the
 		  /// \e "highest label" and the \e "bound decrease" heuristics.
 		  /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
 		  ///
 		  /// The algorithm consists of two phases. After the first phase
 		  /// the maximum flow value and the minimum cut is obtained. The
 		  /// second phase constructs a feasible maximum flow on each arc.
 		  ///
 		  /// \tparam GR The type of the digraph the algorithm runs on.
 		  /// \tparam CAP The type of the capacity map. The default map
 		  /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		#ifdef DOXYGEN
 		  template <typename GR, typename CAP, typename TR>
@@ -362,44 +369,46 @@
+		    }
 		    /// \brief Returns a const reference to the elevator.
 		    ///
 		    /// Returns a const reference to the elevator.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    const Elevator& elevator() const {
 		      return *_level;
+		    }
 		    /// \brief Sets the tolerance used by algorithm.
+		    /// \brief Sets the tolerance used by the algorithm.
 		    ///
 		    /// Sets the tolerance used by algorithm.
 		    Preflow& tolerance(const Tolerance& tolerance) const {
 		    /// Sets the tolerance object used by the algorithm.
 		    /// \return <tt>(*this)</tt>
 		    Preflow& tolerance(const Tolerance& tolerance) {
 		      _tolerance = 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 _tolerance;
+		    }
 		    /// \name Execution Control
 		    /// The simplest way to execute the preflow algorithm is to use
 		    /// \ref run() or \ref runMinCut().\n
 		    /// If you need more control on the initial solution or the execution,
 		    /// first you have to call one of the \ref init() functions, then
 		    /// If you need better control on the initial solution or the execution,
 		    /// you have to call one of the \ref init() functions first, then
 		    /// \ref startFirstPhase() and if you need it \ref startSecondPhase().
 		    ///@{
 		    /// \brief Initializes the internal data structures.
 		    ///
 		    /// Initializes the internal data structures and sets the initial
 		    /// flow to zero on each arc.
 		    void init() {
 		      createStructures();
 		      _phase = true;

test/CMakeLists.txt

Show inline comments

 		INCLUDE_DIRECTORIES(
 		  ${PROJECT_SOURCE_DIR}
 		  ${PROJECT_BINARY_DIR}
+		)
 		LINK_DIRECTORIES(
 		  ${PROJECT_BINARY_DIR}/lemon
+		)
 		SET(TESTS
 		  adaptors_test
 		  bellman_ford_test
 		  bfs_test
 		  circulation_test
 		  connectivity_test
 		  counter_test
 		  dfs_test
 		  digraph_test
 		  dijkstra_test
 		  dim_test
 		  edge_set_test
 		  error_test
 		  euler_test
 		  gomory_hu_test

test/Makefile.am

Show inline comments

 		EXTRA_DIST += \
 			test/CMakeLists.txt
 		noinst_HEADERS += \
 			test/graph_test.h \
 			test/test_tools.h
 		check_PROGRAMS += \
 			test/adaptors_test \
 			test/bellman_ford_test \
 			test/bfs_test \
 			test/circulation_test \
 			test/connectivity_test \
 			test/counter_test \
 			test/dfs_test \
 			test/digraph_test \
 			test/dijkstra_test \
 			test/dim_test \
 			test/edge_set_test \
 			test/error_test \
 			test/euler_test \
 			test/gomory_hu_test \
@@ -43,24 +44,25 @@
 		if HAVE_LP
 		check_PROGRAMS += test/lp_test
 		endif HAVE_LP
 		if HAVE_MIP
 		check_PROGRAMS += test/mip_test
 		endif HAVE_MIP
 		TESTS += $(check_PROGRAMS)
 		XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
 		test_adaptors_test_SOURCES = test/adaptors_test.cc
 		test_bellman_ford_test_SOURCES = test/bellman_ford_test.cc
 		test_bfs_test_SOURCES = test/bfs_test.cc
 		test_circulation_test_SOURCES = test/circulation_test.cc
 		test_counter_test_SOURCES = test/counter_test.cc
 		test_connectivity_test_SOURCES = test/connectivity_test.cc
 		test_dfs_test_SOURCES = test/dfs_test.cc
 		test_digraph_test_SOURCES = test/digraph_test.cc
 		test_dijkstra_test_SOURCES = test/dijkstra_test.cc
 		test_dim_test_SOURCES = test/dim_test.cc
 		test_edge_set_test_SOURCES = test/edge_set_test.cc
 		test_error_test_SOURCES = test/error_test.cc
 		test_euler_test_SOURCES = test/euler_test.cc
 		test_gomory_hu_test_SOURCES = test/gomory_hu_test.cc

test/circulation_test.cc

Show inline comments

@@ -78,24 +78,29 @@
 		            ::SetFlowMap<FlowMap>
 		            ::SetElevator<Elev>
 		            ::SetStandardElevator<LinkedElev>
 		            ::Create CirculationType;
 		  CirculationType circ_test(g, lcap, ucap, supply);
 		  const CirculationType& const_circ_test = circ_test;
 		  circ_test
 		    .lowerMap(lcap)
 		    .upperMap(ucap)
 		    .supplyMap(supply)
 		    .flowMap(flow);
 		  const CirculationType::Elevator& elev = const_circ_test.elevator();
 		  circ_test.elevator(const_cast<CirculationType::Elevator&>(elev));
 		  CirculationType::Tolerance tol = const_circ_test.tolerance();
 		  circ_test.tolerance(tol);
 		  circ_test.init();
 		  circ_test.greedyInit();
 		  circ_test.start();
 		  circ_test.run();
 		  v = const_circ_test.flow(a);
 		  const FlowMap& fm = const_circ_test.flowMap();
 		  b = const_circ_test.barrier(n);
 		  const_circ_test.barrierMap(bar);
 		  ignore_unused_variable_warning(fm);

test/heap_test.cc

Show inline comments

@@ -16,30 +16,36 @@
+		 *
 		 */
 		#include <iostream>
 		#include <fstream>
 		#include <string>
 		#include <vector>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/heap.h>
 		#include <lemon/smart_graph.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/dijkstra.h>
 		#include <lemon/maps.h>
 		#include <lemon/bin_heap.h>
 		#include <lemon/fourary_heap.h>
 		#include <lemon/kary_heap.h>
 		#include <lemon/fib_heap.h>
 		#include <lemon/pairing_heap.h>
 		#include <lemon/radix_heap.h>
 		#include <lemon/binom_heap.h>
 		#include <lemon/bucket_heap.h>
 		#include "test_tools.h"
 		using namespace lemon;
 		using namespace lemon::concepts;
 		typedef ListDigraph Digraph;
 		DIGRAPH_TYPEDEFS(Digraph);
 		char test_lgf[] =
 		  "@nodes\n"
 		  "label\n"
@@ -77,111 +83,194 @@
 		  "0       9       19      86\n"
 		  "@attributes\n"
 		  "source 3\n";
 		int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26,  1,  9,  4, 34};
 		int test_inc[] = {20, 28, 34, 16,  0, 46, 44,  0, 42, 32, 14,  8,  6, 37};
 		int test_len = sizeof(test_seq) / sizeof(test_seq[0]);
 		template <typename Heap>
 		void heapSortTest() {
 		  RangeMap<int> map(test_len, -1);
 		  Heap heap(map);
 		  std::vector<int> v(test_len);
 		  for (int i = 0; i < test_len; ++i) {
 		    v[i] = test_seq[i];
 		    heap.push(i, v[i]);
+		  }
 		  std::sort(v.begin(), v.end());
 		  for (int i = 0; i < test_len; ++i) {
-		    check(v[i] == heap.prio() ,"Wrong order in heap sort.");
+		    check(v[i] == heap.prio(), "Wrong order in heap sort.");
 		    heap.pop();
+		  }
+		}
 		template <typename Heap>
 		void heapIncreaseTest() {
 		  RangeMap<int> map(test_len, -1);
 		  Heap heap(map);
 		  std::vector<int> v(test_len);
 		  for (int i = 0; i < test_len; ++i) {
 		    v[i] = test_seq[i];
 		    heap.push(i, v[i]);
+		  }
 		  for (int i = 0; i < test_len; ++i) {
 		    v[i] += test_inc[i];
 		    heap.increase(i, v[i]);
+		  }
 		  std::sort(v.begin(), v.end());
 		  for (int i = 0; i < test_len; ++i) {
-		    check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
+		    check(v[i] == heap.prio(), "Wrong order in heap increase test.");
 		    heap.pop();
+		  }
+		}
 		template <typename Heap>
 		void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length,
 		                      Node source) {
 		  typename Dijkstra<Digraph, IntArcMap>::template SetStandardHeap<Heap>::
 		    Create dijkstra(digraph, length);
 		  dijkstra.run(source);
 		  for(ArcIt a(digraph); a != INVALID; ++a) {
 		    Node s = digraph.source(a);
 		    Node t = digraph.target(a);
 		    if (dijkstra.reached(s)) {
 		      check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
-		             "Error in a shortest path tree!");
+		             "Error in shortest path tree.");
+		    }
+		  }
 		  for(NodeIt n(digraph); n != INVALID; ++n) {
 		    if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) {
 		      Arc a = dijkstra.predArc(n);
 		      Node s = digraph.source(a);
 		      check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
-		             "Error in a shortest path tree!");
+		             "Error in shortest path tree.");
+		    }
+		  }
+		}
 		int main() {
 		  typedef int Item;
 		  typedef int Prio;
 		  typedef RangeMap<int> ItemIntMap;
 		  Digraph digraph;
 		  IntArcMap length(digraph);
 		  Node source;
 		  std::istringstream input(test_lgf);
 		  digraphReader(digraph, input).
 		    arcMap("capacity", length).
 		    node("source", source).
 		    run();
 		  // BinHeap
+		  {
 		    typedef BinHeap<Prio, ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>();
 		    heapIncreaseTest<IntHeap>();
 		    typedef BinHeap<Prio, IntNodeMap > NodeHeap;
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
 		    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+		  }
 		  // FouraryHeap
+		  {
 		    typedef FouraryHeap<Prio, ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>();
 		    heapIncreaseTest<IntHeap>();
 		    typedef FouraryHeap<Prio, IntNodeMap > NodeHeap;
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
 		    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+		  }
 		  // KaryHeap
+		  {
 		    typedef KaryHeap<Prio, ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>();
 		    heapIncreaseTest<IntHeap>();
 		    typedef KaryHeap<Prio, IntNodeMap > NodeHeap;
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
 		    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+		  }
 		  // FibHeap
+		  {
 		    typedef FibHeap<Prio, ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>();
 		    heapIncreaseTest<IntHeap>();
 		    typedef FibHeap<Prio, IntNodeMap > NodeHeap;
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
 		    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+		  }
 		  // PairingHeap
+		  {
 		    typedef PairingHeap<Prio, ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>();
 		    heapIncreaseTest<IntHeap>();
 		    typedef PairingHeap<Prio, IntNodeMap > NodeHeap;
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
 		    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+		  }
 		  // RadixHeap
+		  {
 		    typedef RadixHeap<ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>();
 		    heapIncreaseTest<IntHeap>();
 		    typedef RadixHeap<IntNodeMap > NodeHeap;
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
 		    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+		  }
 		  // BinomHeap
+		  {
 		    typedef BinomHeap<Prio, ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>();
 		    heapIncreaseTest<IntHeap>();
 		    typedef BinomHeap<Prio, IntNodeMap > NodeHeap;
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
 		    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+		  }
 		  // BucketHeap, SimpleBucketHeap
+		  {
 		    typedef BucketHeap<ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>();
 		    heapIncreaseTest<IntHeap>();
 		    typedef BucketHeap<IntNodeMap > NodeHeap;
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
 		    dijkstraHeapTest<NodeHeap>(digraph, length, source);
 		    typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap;
 		    heapSortTest<SimpleIntHeap>();
+		  }
 		  return 0;
+		}

test/maps_test.cc

Show inline comments

@@ -13,24 +13,25 @@
 		 * 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.
+		 *
 		 */
 		#include <deque>
 		#include <set>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/maps.h>
 		#include <lemon/maps.h>
 		#include <lemon/smart_graph.h>
 		#include "test_tools.h"
 		using namespace lemon;
 		using namespace lemon::concepts;
 		struct A {};
 		inline bool operator<(A, A) { return true; }
 		struct B {};
 		class C {
 		  int x;
@@ -340,14 +341,235 @@
 		    map1.set(60, true);   map2.set(60, true);
 		    check(v1.size() == 3 && v2.size() == 10 &&
 		          v1[0]==20 && v1[1]==50 && v1[2]==60 &&
 		          v2[0]==20 && v2[1]==50 && v2[2]==60,
 		          "Something is wrong with LoggerBoolMap");
 		    int i = 0;
 		    for ( LoggerBoolMap<vec::iterator>::Iterator it = map2.begin();
 		          it != map2.end(); ++it )
 		      check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");
+		  }
 		  // CrossRefMap
+		  {
 		    typedef SmartDigraph Graph;
 		    DIGRAPH_TYPEDEFS(Graph);
 		    checkConcept<ReadWriteMap<Node, int>,
 		                 CrossRefMap<Graph, Node, int> >();
 		    Graph gr;
 		    typedef CrossRefMap<Graph, Node, char> CRMap;
 		    typedef CRMap::ValueIterator ValueIt;
 		    CRMap map(gr);
 		    Node n0 = gr.addNode();
 		    Node n1 = gr.addNode();
 		    Node n2 = gr.addNode();
 		    map.set(n0, 'A');
 		    map.set(n1, 'B');
 		    map.set(n2, 'C');
 		    map.set(n2, 'A');
 		    map.set(n0, 'C');
 		    check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A',
 		          "Wrong CrossRefMap");
 		    check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap");
 		    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");
 		    check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap");
 		    ValueIt it = map.beginValue();
 		    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
 		          it == map.endValue(), "Wrong value iterator");
+		  }
 		  // Iterable bool map
+		  {
 		    typedef SmartGraph Graph;
 		    typedef SmartGraph::Node Item;
 		    typedef IterableBoolMap<SmartGraph, SmartGraph::Node> Ibm;
 		    checkConcept<ReferenceMap<Item, bool, bool&, const bool&>, Ibm>();
 		    const int num = 10;
 		    Graph g;
 		    std::vector<Item> items;
 		    for (int i = 0; i < num; ++i) {
 		      items.push_back(g.addNode());
+		    }
 		    Ibm map1(g, true);
 		    int n = 0;
 		    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
 		      check(map1[static_cast<Item>(it)], "Wrong TrueIt");
 		      ++n;
+		    }
 		    check(n == num, "Wrong number");
 		    n = 0;
 		    for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {
 		        check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");
 		        ++n;
+		    }
 		    check(n == num, "Wrong number");
 		    check(Ibm::FalseIt(map1) == INVALID, "Wrong FalseIt");
 		    check(Ibm::ItemIt(map1, false) == INVALID, "Wrong ItemIt for false");
 		    map1[items[5]] = true;
 		    n = 0;
 		    for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {
 		        check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");
 		        ++n;
+		    }
 		    check(n == num, "Wrong number");
 		    map1[items[num / 2]] = false;
 		    check(map1[items[num / 2]] == false, "Wrong map value");
 		    n = 0;
 		    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
 		        check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");
 		        ++n;
+		    }
 		    check(n == num - 1, "Wrong number");
 		    n = 0;
 		    for (Ibm::FalseIt it(map1); it != INVALID; ++it) {
 		        check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");
 		        ++n;
+		    }
 		    check(n == 1, "Wrong number");
 		    map1[items[0]] = false;
 		    check(map1[items[0]] == false, "Wrong map value");
 		    map1[items[num - 1]] = false;
 		    check(map1[items[num - 1]] == false, "Wrong map value");
 		    n = 0;
 		    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
 		        check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");
 		        ++n;
+		    }
 		    check(n == num - 3, "Wrong number");
 		    check(map1.trueNum() == num - 3, "Wrong number");
 		    n = 0;
 		    for (Ibm::FalseIt it(map1); it != INVALID; ++it) {
 		        check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");
 		        ++n;
+		    }
 		    check(n == 3, "Wrong number");
 		    check(map1.falseNum() == 3, "Wrong number");
+		  }
 		  // Iterable int map
+		  {
 		    typedef SmartGraph Graph;
 		    typedef SmartGraph::Node Item;
 		    typedef IterableIntMap<SmartGraph, SmartGraph::Node> Iim;
 		    checkConcept<ReferenceMap<Item, int, int&, const int&>, Iim>();
 		    const int num = 10;
 		    Graph g;
 		    std::vector<Item> items;
 		    for (int i = 0; i < num; ++i) {
 		      items.push_back(g.addNode());
+		    }
 		    Iim map1(g);
 		    check(map1.size() == 0, "Wrong size");
 		    for (int i = 0; i < num; ++i) {
 		      map1[items[i]] = i;
+		    }
 		    check(map1.size() == num, "Wrong size");
 		    for (int i = 0; i < num; ++i) {
 		      Iim::ItemIt it(map1, i);
 		      check(static_cast<Item>(it) == items[i], "Wrong value");
 		      ++it;
 		      check(static_cast<Item>(it) == INVALID, "Wrong value");
+		    }
 		    for (int i = 0; i < num; ++i) {
 		      map1[items[i]] = i % 2;
+		    }
 		    check(map1.size() == 2, "Wrong size");
 		    int n = 0;
 		    for (Iim::ItemIt it(map1, 0); it != INVALID; ++it) {
 		      check(map1[static_cast<Item>(it)] == 0, "Wrong value");
 		      ++n;
+		    }
 		    check(n == (num + 1) / 2, "Wrong number");
 		    for (Iim::ItemIt it(map1, 1); it != INVALID; ++it) {
 		      check(map1[static_cast<Item>(it)] == 1, "Wrong value");
 		      ++n;
+		    }
 		    check(n == num, "Wrong number");
+		  }
 		  // Iterable value map
+		  {
 		    typedef SmartGraph Graph;
 		    typedef SmartGraph::Node Item;
 		    typedef IterableValueMap<SmartGraph, SmartGraph::Node, double> Ivm;
 		    checkConcept<ReadWriteMap<Item, double>, Ivm>();
 		    const int num = 10;
 		    Graph g;
 		    std::vector<Item> items;
 		    for (int i = 0; i < num; ++i) {
 		      items.push_back(g.addNode());
+		    }
 		    Ivm map1(g, 0.0);
 		    check(distance(map1.beginValue(), map1.endValue()) == 1, "Wrong size");
 		    check(*map1.beginValue() == 0.0, "Wrong value");
 		    for (int i = 0; i < num; ++i) {
 		      map1.set(items[i], static_cast<double>(i));
+		    }
 		    check(distance(map1.beginValue(), map1.endValue()) == num, "Wrong size");
 		    for (int i = 0; i < num; ++i) {
 		      Ivm::ItemIt it(map1, static_cast<double>(i));
 		      check(static_cast<Item>(it) == items[i], "Wrong value");
 		      ++it;
 		      check(static_cast<Item>(it) == INVALID, "Wrong value");
+		    }
 		    for (Ivm::ValueIterator vit = map1.beginValue();
 		         vit != map1.endValue(); ++vit) {
 		      check(map1[static_cast<Item>(Ivm::ItemIt(map1, *vit))] == *vit,
 		            "Wrong ValueIterator");
+		    }
 		    for (int i = 0; i < num; ++i) {
 		      map1.set(items[i], static_cast<double>(i % 2));
+		    }
 		    check(distance(map1.beginValue(), map1.endValue()) == 2, "Wrong size");
 		    int n = 0;
 		    for (Ivm::ItemIt it(map1, 0.0); it != INVALID; ++it) {
 		      check(map1[static_cast<Item>(it)] == 0.0, "Wrong value");
 		      ++n;
+		    }
 		    check(n == (num + 1) / 2, "Wrong number");
 		    for (Ivm::ItemIt it(map1, 1.0); it != INVALID; ++it) {
 		      check(map1[static_cast<Item>(it)] == 1.0, "Wrong value");
 		      ++n;
+		    }
 		    check(n == num, "Wrong number");
+		  }
 		  return 0;
+		}

test/preflow_test.cc

Show inline comments

@@ -85,24 +85,29 @@
 		  FlowMap flow;
 		  CutMap cut;
 		  VType v;
 		  bool b;
 		  typedef Preflow<Digraph, CapMap>
 		            ::SetFlowMap<FlowMap>
 		            ::SetElevator<Elev>
 		            ::SetStandardElevator<LinkedElev>
 		            ::Create PreflowType;
 		  PreflowType preflow_test(g, cap, n, n);
 		  const PreflowType& const_preflow_test = preflow_test;
 		  const PreflowType::Elevator& elev = const_preflow_test.elevator();
 		  preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev));
 		  PreflowType::Tolerance tol = const_preflow_test.tolerance();
 		  preflow_test.tolerance(tol);
 		  preflow_test
 		    .capacityMap(cap)
 		    .flowMap(flow)
 		    .source(n)
 		    .target(n);
 		  preflow_test.init();
 		  preflow_test.init(cap);
 		  preflow_test.startFirstPhase();
 		  preflow_test.startSecondPhase();
 		  preflow_test.run();

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

Show inline comments

@@ -26,28 +26,28 @@
 		        -e "s/\<graph\>/_digr_aph_label_/g"\
 		        -e "s/Graphs\>/_Digr_aph_label_s/g"\
 		        -e "s/\<graphs\>/_digr_aph_label_s/g"\
 		        -e "s/\([Gg]\)raph\([a-z]\)/_\1r_aph_label_\2/g"\
 		        -e "s/\([a-z_]\)graph/\1_gr_aph_label_/g"\
 		        -e "s/Graph/_Digr_aph_label_/g"\
 		        -e "s/graph/_digr_aph_label_/g"\
 		        -e "s/UEdge/_Ed_ge_label_/g"\
 		        -e "s/u[Ee]dge/_ed_ge_label_/g"\
 		        -e "s/IncEdgeIt/_In_cEd_geIt_label_/g"\
 		        -e "s/Edge\>/_Ar_c_label_/g"\
 		        -e "s/\<edge\>/_ar_c_label_/g"\
-		        -e "s/_edge\>/_ar_c_label_/g"\
+		        -e "s/_edge\>/__ar_c_label_/g"\
 		        -e "s/Edges\>/_Ar_c_label_s/g"\
 		        -e "s/\<edges\>/_ar_c_label_s/g"\
-		        -e "s/_edges\>/_ar_c_label_s/g"\
+		        -e "s/_edges\>/__ar_c_label_s/g"\
 		        -e "s/\([Ee]\)dge\([a-z]\)/_\1d_ge_label_\2/g"\
 		        -e "s/\([a-z]\)edge/\1_ed_ge_label_/g"\
 		        -e "s/Edge/_Ar_c_label_/g"\
 		        -e "s/edge/_ar_c_label_/g"\
 		        -e "s/A[Nn]ode/_Re_d_label_/g"\
 		        -e "s/B[Nn]ode/_Blu_e_label_/g"\
 		        -e "s/A-[Nn]ode/_Re_d_label_/g"\
 		        -e "s/B-[Nn]ode/_Blu_e_label_/g"\
 		        -e "s/a[Nn]ode/_re_d_label_/g"\
 		        -e "s/b[Nn]ode/_blu_e_label_/g"\
 		        -e "s/\<UGRAPH_TYPEDEFS\([ \t]*([ \t]*\)typename[ \t]/TEMPLATE__GR_APH_TY_PEDE_FS_label_\1/g"\
 		        -e "s/\<GRAPH_TYPEDEFS\([ \t]*([ \t]*\)typename[ \t]/TEMPLATE__DIGR_APH_TY_PEDE_FS_label_\1/g"\
@@ -59,24 +59,29 @@
 		        -e "s/_gr_aph_label_/graph/g"\
 		        -e "s/_Ar_c_label_/Arc/g"\
 		        -e "s/_ar_c_label_/arc/g"\
 		        -e "s/_Ed_ge_label_/Edge/g"\
 		        -e "s/_ed_ge_label_/edge/g"\
 		        -e "s/_In_cEd_geIt_label_/IncEdgeIt/g"\
 		        -e "s/_Re_d_label_/Red/g"\
 		        -e "s/_Blu_e_label_/Blue/g"\
 		        -e "s/_re_d_label_/red/g"\
 		        -e "s/_blu_e_label_/blue/g"\
 		        -e "s/_GR_APH_TY_PEDE_FS_label_/GRAPH_TYPEDEFS/g"\
 		        -e "s/_DIGR_APH_TY_PEDE_FS_label_/DIGRAPH_TYPEDEFS/g"\
 		        -e "s/\<digraph_adaptor\.h\>/adaptors.h/g"\
 		        -e "s/\<digraph_utils\.h\>/core.h/g"\
 		        -e "s/\<digraph_reader\.h\>/lgf_reader.h/g"\
 		        -e "s/\<digraph_writer\.h\>/lgf_writer.h/g"\
 		        -e "s/\<topology\.h\>/connectivity.h/g"\
 		        -e "s/DigraphToEps/GraphToEps/g"\
 		        -e "s/digraphToEps/graphToEps/g"\
 		        -e "s/\<DefPredMap\>/SetPredMap/g"\
 		        -e "s/\<DefDistMap\>/SetDistMap/g"\
 		        -e "s/\<DefReachedMap\>/SetReachedMap/g"\
 		        -e "s/\<DefProcessedMap\>/SetProcessedMap/g"\
 		        -e "s/\<DefHeap\>/SetHeap/g"\
 		        -e "s/\<DefStandardHeap\>/SetStandradHeap/g"\
 		        -e "s/\<DefOperationTraits\>/SetOperationTraits/g"\
 		        -e "s/\<DefProcessedMapToBeDefaultMap\>/SetStandardProcessedMap/g"\
 		        -e "s/\<copyGraph\>/graphCopy/g"\
 		        -e "s/\<copyDigraph\>/digraphCopy/g"\

0 comments (0 inline)

RhodeCode

Login to your account