# HG changeset patch
# User Alpar Juttner <alpar@cs.elte.hu>
# Date 1253862392 -7200
# Node ID ece80147fb08a669ca882837b0569f5ade5270a7
# Parent 98a30824fe36884df74899663c07eb29b0efd435# Parent 6d5f547e5bfb8131568ad50ea406129a056ac9ed
Merge
diff -r 98a30824fe36 -r ece80147fb08 doc/groups.dox
--- a/doc/groups.dox Fri Jul 24 11:07:52 2009 +0200
+++ b/doc/groups.dox Fri Sep 25 09:06:32 2009 +0200
@@ -238,7 +238,36 @@
efficient to have e.g. the Dijkstra algorithm to store its result in
any kind of path structure.
-\sa lemon::concepts::Path
+\sa \ref concepts::Path "Path concept"
+*/
+
+/**
+@defgroup heaps Heap Structures
+@ingroup datas
+\brief %Heap structures implemented in LEMON.
+
+This group contains the heap structures implemented in LEMON.
+
+LEMON provides several heap classes. They are efficient implementations
+of the abstract data type \e priority \e queue. They store items with
+specified values called \e priorities in such a way that finding and
+removing the item with minimum priority are efficient.
+The basic operations are adding and erasing items, changing the priority
+of an item, etc.
+
+Heaps are crucial in several algorithms, such as Dijkstra and Prim.
+The heap implementations have the same interface, thus any of them can be
+used easily in such algorithms.
+
+\sa \ref concepts::Heap "Heap concept"
+*/
+
+/**
+@defgroup matrices Matrices
+@ingroup datas
+\brief Two dimensional data storages implemented in LEMON.
+
+This group contains two dimensional data storages implemented in LEMON.
*/
/**
diff -r 98a30824fe36 -r ece80147fb08 lemon/Makefile.am
--- a/lemon/Makefile.am Fri Jul 24 11:07:52 2009 +0200
+++ b/lemon/Makefile.am Fri Sep 25 09:06:32 2009 +0200
@@ -57,8 +57,10 @@
lemon/adaptors.h \
lemon/arg_parser.h \
lemon/assert.h \
+ lemon/bellman_ford.h \
lemon/bfs.h \
lemon/bin_heap.h \
+ lemon/binom_heap.h \
lemon/bucket_heap.h \
lemon/cbc.h \
lemon/circulation.h \
@@ -78,12 +80,14 @@
lemon/error.h \
lemon/euler.h \
lemon/fib_heap.h \
+ lemon/fourary_heap.h \
lemon/full_graph.h \
lemon/glpk.h \
lemon/gomory_hu.h \
lemon/graph_to_eps.h \
lemon/grid_graph.h \
lemon/hypercube_graph.h \
+ lemon/kary_heap.h \
lemon/kruskal.h \
lemon/hao_orlin.h \
lemon/lgf_reader.h \
@@ -92,13 +96,13 @@
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 \
diff -r 98a30824fe36 -r ece80147fb08 lemon/bellman_ford.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/bellman_ford.h Fri Sep 25 09:06:32 2009 +0200
@@ -0,0 +1,1100 @@
+/* -*- 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 = ↦
+ 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 = ↦
+ 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 = ↦
+ 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
+
diff -r 98a30824fe36 -r ece80147fb08 lemon/bin_heap.h
--- a/lemon/bin_heap.h Fri Jul 24 11:07:52 2009 +0200
+++ b/lemon/bin_heap.h Fri Sep 25 09:06:32 2009 +0200
@@ -19,9 +19,9 @@
#ifndef LEMON_BIN_HEAP_H
#define LEMON_BIN_HEAP_H
-///\ingroup auxdat
+///\ingroup heaps
///\file
-///\brief Binary Heap implementation.
+///\brief Binary heap implementation.
#include <vector>
#include <utility>
@@ -29,45 +29,41 @@
namespace lemon {
- ///\ingroup auxdat
+ /// \ingroup heaps
///
- ///\brief A Binary Heap implementation.
+ /// \brief Binary heap data structure.
///
- ///This class implements the \e binary \e heap data structure.
+ /// This class implements the \e binary \e heap data structure.
+ /// It fully conforms to the \ref concepts::Heap "heap concept".
///
- ///A \e heap is a data structure for storing items with specified values
- ///called \e priorities in such a way that finding the item with minimum
- ///priority is efficient. \c CMP specifies the ordering of the priorities.
- ///In a heap one can change the priority of an item, add or erase an
- ///item, etc.
- ///
- ///\tparam PR Type of the priority of the items.
- ///\tparam IM A read and writable item map with int values, used internally
- ///to handle the cross references.
- ///\tparam CMP A functor class for the ordering of the priorities.
- ///The default is \c std::less<PR>.
- ///
- ///\sa FibHeap
- ///\sa Dijkstra
+ /// \tparam PR Type of the priorities of the items.
+ /// \tparam IM A read-writable item map with \c int values, used
+ /// internally to handle the cross references.
+ /// \tparam CMP A functor class for comparing the priorities.
+ /// The default is \c std::less<PR>.
+#ifdef DOXYGEN
+ template <typename PR, typename IM, typename CMP>
+#else
template <typename PR, typename IM, typename CMP = std::less<PR> >
+#endif
class BinHeap {
+ public:
- public:
- ///\e
+ /// Type of the item-int map.
typedef IM ItemIntMap;
- ///\e
+ /// Type of the priorities.
typedef PR Prio;
- ///\e
+ /// Type of the items stored in the heap.
typedef typename ItemIntMap::Key Item;
- ///\e
+ /// Type of the item-priority pairs.
typedef std::pair<Item,Prio> Pair;
- ///\e
+ /// Functor type for comparing the priorities.
typedef CMP Compare;
- /// \brief Type to represent the items states.
+ /// \brief Type to represent the states of the items.
///
- /// Each Item element have a state associated to it. It may be "in heap",
- /// "pre heap" or "post heap". The latter two are indifferent from the
+ /// Each item has a state associated to it. It can be "in heap",
+ /// "pre-heap" or "post-heap". The latter two are indifferent from the
/// heap's point of view, but may be useful to the user.
///
/// The item-int map must be initialized in such way that it assigns
@@ -84,42 +80,43 @@
ItemIntMap &_iim;
public:
- /// \brief The constructor.
+
+ /// \brief Constructor.
///
- /// The constructor.
- /// \param map should be given to the constructor, since it is used
- /// internally to handle the cross references. The value of the map
- /// must be \c PRE_HEAP (<tt>-1</tt>) for every item.
+ /// Constructor.
+ /// \param map A map that assigns \c int values to the items.
+ /// It is used internally to handle the cross references.
+ /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
explicit BinHeap(ItemIntMap &map) : _iim(map) {}
- /// \brief The constructor.
+ /// \brief Constructor.
///
- /// The constructor.
- /// \param map should be given to the constructor, since it is used
- /// internally to handle the cross references. The value of the map
- /// should be PRE_HEAP (-1) for each element.
- ///
- /// \param comp The comparator function object.
+ /// Constructor.
+ /// \param map A map that assigns \c int values to the items.
+ /// It is used internally to handle the cross references.
+ /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
+ /// \param comp The function object used for comparing the priorities.
BinHeap(ItemIntMap &map, const Compare &comp)
: _iim(map), _comp(comp) {}
- /// The number of items stored in the heap.
+ /// \brief The number of items stored in the heap.
///
- /// \brief Returns the number of items stored in the heap.
+ /// This function returns the number of items stored in the heap.
int size() const { return _data.size(); }
- /// \brief Checks if the heap stores no items.
+ /// \brief Check if the heap is empty.
///
- /// Returns \c true if and only if the heap stores no items.
+ /// This function returns \c true if the heap is empty.
bool empty() const { return _data.empty(); }
- /// \brief Make empty this heap.
+ /// \brief Make the heap empty.
///
- /// Make empty this heap. It does not change the cross reference map.
- /// If you want to reuse what is not surely empty you should first clear
- /// the heap and after that you should set the cross reference map for
- /// each item to \c PRE_HEAP.
+ /// This functon makes the heap empty.
+ /// It does not change the cross reference map. If you want to reuse
+ /// a heap that is not surely empty, you should first clear it and
+ /// then you should set the cross reference map to \c PRE_HEAP
+ /// for each item.
void clear() {
_data.clear();
}
@@ -127,12 +124,12 @@
private:
static int parent(int i) { return (i-1)/2; }
- static int second_child(int i) { return 2*i+2; }
+ static int secondChild(int i) { return 2*i+2; }
bool less(const Pair &p1, const Pair &p2) const {
return _comp(p1.second, p2.second);
}
- int bubble_up(int hole, Pair p) {
+ int bubbleUp(int hole, Pair p) {
int par = parent(hole);
while( hole>0 && less(p,_data[par]) ) {
move(_data[par],hole);
@@ -143,8 +140,8 @@
return hole;
}
- int bubble_down(int hole, Pair p, int length) {
- int child = second_child(hole);
+ int bubbleDown(int hole, Pair p, int length) {
+ int child = secondChild(hole);
while(child < length) {
if( less(_data[child-1], _data[child]) ) {
--child;
@@ -153,7 +150,7 @@
goto ok;
move(_data[child], hole);
hole = child;
- child = second_child(hole);
+ child = secondChild(hole);
}
child--;
if( child<length && less(_data[child], p) ) {
@@ -171,87 +168,91 @@
}
public:
+
/// \brief Insert a pair of item and priority into the heap.
///
- /// Adds \c p.first to the heap with priority \c p.second.
+ /// This function inserts \c p.first to the heap with priority
+ /// \c p.second.
/// \param p The pair to insert.
+ /// \pre \c p.first must not be stored in the heap.
void push(const Pair &p) {
int n = _data.size();
_data.resize(n+1);
- bubble_up(n, p);
+ bubbleUp(n, p);
}
- /// \brief Insert an item into the heap with the given heap.
+ /// \brief Insert an item into the heap with the given priority.
///
- /// Adds \c i to the heap with priority \c p.
+ /// This function inserts the given item into the heap with the
+ /// given priority.
/// \param i The item to insert.
/// \param p The priority of the item.
+ /// \pre \e i must not be stored in the heap.
void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
- /// \brief Returns the item with minimum priority relative to \c Compare.
+ /// \brief Return the item having minimum priority.
///
- /// This method returns the item with minimum priority relative to \c
- /// Compare.
- /// \pre The heap must be nonempty.
+ /// This function returns the item having minimum priority.
+ /// \pre The heap must be non-empty.
Item top() const {
return _data[0].first;
}
- /// \brief Returns the minimum priority relative to \c Compare.
+ /// \brief The minimum priority.
///
- /// It returns the minimum priority relative to \c Compare.
- /// \pre The heap must be nonempty.
+ /// This function returns the minimum priority.
+ /// \pre The heap must be non-empty.
Prio prio() const {
return _data[0].second;
}
- /// \brief Deletes the item with minimum priority relative to \c Compare.
+ /// \brief Remove the item having minimum priority.
///
- /// This method deletes the item with minimum priority relative to \c
- /// Compare from the heap.
+ /// This function removes the item having minimum priority.
/// \pre The heap must be non-empty.
void pop() {
int n = _data.size()-1;
_iim.set(_data[0].first, POST_HEAP);
if (n > 0) {
- bubble_down(0, _data[n], n);
+ bubbleDown(0, _data[n], n);
}
_data.pop_back();
}
- /// \brief Deletes \c i from the heap.
+ /// \brief Remove the given item from the heap.
///
- /// This method deletes item \c i from the heap.
- /// \param i The item to erase.
- /// \pre The item should be in the heap.
+ /// This function removes the given item from the heap if it is
+ /// already stored.
+ /// \param i The item to delete.
+ /// \pre \e i must be in the heap.
void erase(const Item &i) {
int h = _iim[i];
int n = _data.size()-1;
_iim.set(_data[h].first, POST_HEAP);
if( h < n ) {
- if ( bubble_up(h, _data[n]) == h) {
- bubble_down(h, _data[n], n);
+ if ( bubbleUp(h, _data[n]) == h) {
+ bubbleDown(h, _data[n], n);
}
}
_data.pop_back();
}
-
- /// \brief Returns the priority of \c i.
+ /// \brief The priority of the given item.
///
- /// This function returns the priority of item \c i.
+ /// This function returns the priority of the given item.
/// \param i The item.
- /// \pre \c i must be in the heap.
+ /// \pre \e i must be in the heap.
Prio operator[](const Item &i) const {
int idx = _iim[i];
return _data[idx].second;
}
- /// \brief \c i gets to the heap with priority \c p independently
- /// if \c i was already there.
+ /// \brief Set the priority of an item or insert it, if it is
+ /// not stored in the heap.
///
- /// This method calls \ref push(\c i, \c p) if \c i is not stored
- /// in the heap and sets the priority of \c i to \c p otherwise.
+ /// This method sets the priority of the given item if it is
+ /// already stored in the heap. Otherwise it inserts the given
+ /// item into the heap with the given priority.
/// \param i The item.
/// \param p The priority.
void set(const Item &i, const Prio &p) {
@@ -260,44 +261,42 @@
push(i,p);
}
else if( _comp(p, _data[idx].second) ) {
- bubble_up(idx, Pair(i,p));
+ bubbleUp(idx, Pair(i,p));
}
else {
- bubble_down(idx, Pair(i,p), _data.size());
+ bubbleDown(idx, Pair(i,p), _data.size());
}
}
- /// \brief Decreases the priority of \c i to \c p.
+ /// \brief Decrease the priority of an item to the given value.
///
- /// This method decreases the priority of item \c i to \c p.
+ /// This function decreases the priority of an item to the given value.
/// \param i The item.
/// \param p The priority.
- /// \pre \c i must be stored in the heap with priority at least \c
- /// p relative to \c Compare.
+ /// \pre \e i must be stored in the heap with priority at least \e p.
void decrease(const Item &i, const Prio &p) {
int idx = _iim[i];
- bubble_up(idx, Pair(i,p));
+ bubbleUp(idx, Pair(i,p));
}
- /// \brief Increases the priority of \c i to \c p.
+ /// \brief Increase the priority of an item to the given value.
///
- /// This method sets the priority of item \c i to \c p.
+ /// This function increases the priority of an item to the given value.
/// \param i The item.
/// \param p The priority.
- /// \pre \c i must be stored in the heap with priority at most \c
- /// p relative to \c Compare.
+ /// \pre \e i must be stored in the heap with priority at most \e p.
void increase(const Item &i, const Prio &p) {
int idx = _iim[i];
- bubble_down(idx, Pair(i,p), _data.size());
+ bubbleDown(idx, Pair(i,p), _data.size());
}
- /// \brief Returns if \c item is in, has already been in, or has
- /// never been in the heap.
+ /// \brief Return the state of an item.
///
- /// This method returns PRE_HEAP if \c item has never been in the
- /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
- /// otherwise. In the latter case it is possible that \c item will
- /// get back to the heap again.
+ /// This method returns \c PRE_HEAP if the given item has never
+ /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
+ /// and \c POST_HEAP otherwise.
+ /// In the latter case it is possible that the item will get back
+ /// to the heap again.
/// \param i The item.
State state(const Item &i) const {
int s = _iim[i];
@@ -306,11 +305,11 @@
return State(s);
}
- /// \brief Sets the state of the \c item in the heap.
+ /// \brief Set the state of an item in the heap.
///
- /// Sets the state of the \c item in the heap. It can be used to
- /// manually clear the heap when it is important to achive the
- /// better time complexity.
+ /// This function sets the state of the given item in the heap.
+ /// It can be used to manually clear the heap when it is important
+ /// to achive better time complexity.
/// \param i The item.
/// \param st The state. It should not be \c IN_HEAP.
void state(const Item& i, State st) {
@@ -327,12 +326,13 @@
}
}
- /// \brief Replaces an item in the heap.
+ /// \brief Replace an item in the heap.
///
- /// The \c i item is replaced with \c j item. The \c i item should
- /// be in the heap, while the \c j should be out of the heap. The
- /// \c i item will out of the heap and \c j will be in the heap
- /// with the same prioriority as prevoiusly the \c i item.
+ /// This function replaces item \c i with item \c j.
+ /// Item \c i must be in the heap, while \c j must be out of the heap.
+ /// After calling this method, item \c i will be out of the
+ /// heap and \c j will be in the heap with the same prioriority
+ /// as item \c i had before.
void replace(const Item& i, const Item& j) {
int idx = _iim[i];
_iim.set(i, _iim[j]);
diff -r 98a30824fe36 -r ece80147fb08 lemon/binom_heap.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/binom_heap.h Fri Sep 25 09:06:32 2009 +0200
@@ -0,0 +1,445 @@
+/* -*- 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
+
diff -r 98a30824fe36 -r ece80147fb08 lemon/bits/edge_set_extender.h
--- a/lemon/bits/edge_set_extender.h Fri Jul 24 11:07:52 2009 +0200
+++ b/lemon/bits/edge_set_extender.h Fri Sep 25 09:06:32 2009 +0200
@@ -537,7 +537,7 @@
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) {}
@@ -561,7 +561,7 @@
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)
diff -r 98a30824fe36 -r ece80147fb08 lemon/bits/graph_extender.h
--- a/lemon/bits/graph_extender.h Fri Jul 24 11:07:52 2009 +0200
+++ b/lemon/bits/graph_extender.h Fri Sep 25 09:06:32 2009 +0200
@@ -604,7 +604,7 @@
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) {}
@@ -628,7 +628,7 @@
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) {}
@@ -652,7 +652,7 @@
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)
diff -r 98a30824fe36 -r ece80147fb08 lemon/bucket_heap.h
--- a/lemon/bucket_heap.h Fri Jul 24 11:07:52 2009 +0200
+++ b/lemon/bucket_heap.h Fri Sep 25 09:06:32 2009 +0200
@@ -19,9 +19,9 @@
#ifndef LEMON_BUCKET_HEAP_H
#define LEMON_BUCKET_HEAP_H
-///\ingroup auxdat
+///\ingroup heaps
///\file
-///\brief Bucket Heap implementation.
+///\brief Bucket heap implementation.
#include <vector>
#include <utility>
@@ -53,35 +53,41 @@
}
- /// \ingroup auxdat
+ /// \ingroup heaps
///
- /// \brief A Bucket Heap implementation.
+ /// \brief Bucket heap data structure.
///
- /// This class implements the \e bucket \e heap data structure. A \e heap
- /// is a data structure for storing items with specified values called \e
- /// priorities in such a way that finding the item with minimum priority is
- /// efficient. The bucket heap is very simple implementation, it can store
- /// only integer priorities and it stores for each priority in the
- /// \f$ [0..C) \f$ range a list of items. So it should be used only when
- /// the priorities are small. It is not intended to use as dijkstra heap.
+ /// This class implements the \e bucket \e heap data structure.
+ /// It practically conforms to the \ref concepts::Heap "heap concept",
+ /// but it has some limitations.
///
- /// \param IM A read and write Item int map, used internally
- /// to handle the cross references.
- /// \param MIN If the given parameter is false then instead of the
- /// minimum value the maximum can be retrivied with the top() and
- /// prio() member functions.
+ /// The bucket heap is a very simple structure. It can store only
+ /// \c int priorities and it maintains a list of items for each priority
+ /// in the range <tt>[0..C)</tt>. So it should only be used when the
+ /// priorities are small. It is not intended to use as a Dijkstra heap.
+ ///
+ /// \tparam IM A read-writable item map with \c int values, used
+ /// internally to handle the cross references.
+ /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
+ /// The default is \e min-heap. If this parameter is set to \c false,
+ /// then the comparison is reversed, so the top(), prio() and pop()
+ /// functions deal with the item having maximum priority instead of the
+ /// minimum.
+ ///
+ /// \sa SimpleBucketHeap
template <typename IM, bool MIN = true>
class BucketHeap {
public:
- /// \e
- typedef typename IM::Key Item;
- /// \e
+
+ /// Type of the item-int map.
+ typedef IM ItemIntMap;
+ /// Type of the priorities.
typedef int Prio;
- /// \e
- typedef std::pair<Item, Prio> Pair;
- /// \e
- typedef IM ItemIntMap;
+ /// Type of the items stored in the heap.
+ typedef typename ItemIntMap::Key Item;
+ /// Type of the item-priority pairs.
+ typedef std::pair<Item,Prio> Pair;
private:
@@ -89,10 +95,10 @@
public:
- /// \brief Type to represent the items states.
+ /// \brief Type to represent the states of the items.
///
- /// Each Item element have a state associated to it. It may be "in heap",
- /// "pre heap" or "post heap". The latter two are indifferent from the
+ /// Each item has a state associated to it. It can be "in heap",
+ /// "pre-heap" or "post-heap". The latter two are indifferent from the
/// heap's point of view, but may be useful to the user.
///
/// The item-int map must be initialized in such way that it assigns
@@ -104,37 +110,39 @@
};
public:
- /// \brief The constructor.
+
+ /// \brief Constructor.
///
- /// The constructor.
- /// \param map should be given to the constructor, since it is used
- /// internally to handle the cross references. The value of the map
- /// should be PRE_HEAP (-1) for each element.
+ /// Constructor.
+ /// \param map A map that assigns \c int values to the items.
+ /// It is used internally to handle the cross references.
+ /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {}
- /// The number of items stored in the heap.
+ /// \brief The number of items stored in the heap.
///
- /// \brief Returns the number of items stored in the heap.
+ /// This function returns the number of items stored in the heap.
int size() const { return _data.size(); }
- /// \brief Checks if the heap stores no items.
+ /// \brief Check if the heap is empty.
///
- /// Returns \c true if and only if the heap stores no items.
+ /// This function returns \c true if the heap is empty.
bool empty() const { return _data.empty(); }
- /// \brief Make empty this heap.
+ /// \brief Make the heap empty.
///
- /// Make empty this heap. It does not change the cross reference
- /// map. If you want to reuse a heap what is not surely empty you
- /// should first clear the heap and after that you should set the
- /// cross reference map for each item to \c PRE_HEAP.
+ /// This functon makes the heap empty.
+ /// It does not change the cross reference map. If you want to reuse
+ /// a heap that is not surely empty, you should first clear it and
+ /// then you should set the cross reference map to \c PRE_HEAP
+ /// for each item.
void clear() {
_data.clear(); _first.clear(); _minimum = 0;
}
private:
- void relocate_last(int idx) {
+ void relocateLast(int idx) {
if (idx + 1 < int(_data.size())) {
_data[idx] = _data.back();
if (_data[idx].prev != -1) {
@@ -174,19 +182,24 @@
}
public:
+
/// \brief Insert a pair of item and priority into the heap.
///
- /// Adds \c p.first to the heap with priority \c p.second.
+ /// This function inserts \c p.first to the heap with priority
+ /// \c p.second.
/// \param p The pair to insert.
+ /// \pre \c p.first must not be stored in the heap.
void push(const Pair& p) {
push(p.first, p.second);
}
/// \brief Insert an item into the heap with the given priority.
///
- /// Adds \c i to the heap with priority \c p.
+ /// This function inserts the given item into the heap with the
+ /// given priority.
/// \param i The item to insert.
/// \param p The priority of the item.
+ /// \pre \e i must not be stored in the heap.
void push(const Item &i, const Prio &p) {
int idx = _data.size();
_iim[i] = idx;
@@ -197,10 +210,10 @@
}
}
- /// \brief Returns the item with minimum priority.
+ /// \brief Return the item having minimum priority.
///
- /// This method returns the item with minimum priority.
- /// \pre The heap must be nonempty.
+ /// This function returns the item having minimum priority.
+ /// \pre The heap must be non-empty.
Item top() const {
while (_first[_minimum] == -1) {
Direction::increase(_minimum);
@@ -208,10 +221,10 @@
return _data[_first[_minimum]].item;
}
- /// \brief Returns the minimum priority.
+ /// \brief The minimum priority.
///
- /// It returns the minimum priority.
- /// \pre The heap must be nonempty.
+ /// This function returns the minimum priority.
+ /// \pre The heap must be non-empty.
Prio prio() const {
while (_first[_minimum] == -1) {
Direction::increase(_minimum);
@@ -219,9 +232,9 @@
return _minimum;
}
- /// \brief Deletes the item with minimum priority.
+ /// \brief Remove the item having minimum priority.
///
- /// This method deletes the item with minimum priority from the heap.
+ /// This function removes the item having minimum priority.
/// \pre The heap must be non-empty.
void pop() {
while (_first[_minimum] == -1) {
@@ -230,37 +243,38 @@
int idx = _first[_minimum];
_iim[_data[idx].item] = -2;
unlace(idx);
- relocate_last(idx);
+ relocateLast(idx);
}
- /// \brief Deletes \c i from the heap.
+ /// \brief Remove the given item from the heap.
///
- /// This method deletes item \c i from the heap, if \c i was
- /// already stored in the heap.
- /// \param i The item to erase.
+ /// This function removes the given item from the heap if it is
+ /// already stored.
+ /// \param i The item to delete.
+ /// \pre \e i must be in the heap.
void erase(const Item &i) {
int idx = _iim[i];
_iim[_data[idx].item] = -2;
unlace(idx);
- relocate_last(idx);
+ relocateLast(idx);
}
-
- /// \brief Returns the priority of \c i.
+ /// \brief The priority of the given item.
///
- /// This function returns the priority of item \c i.
- /// \pre \c i must be in the heap.
+ /// This function returns the priority of the given item.
/// \param i The item.
+ /// \pre \e i must be in the heap.
Prio operator[](const Item &i) const {
int idx = _iim[i];
return _data[idx].value;
}
- /// \brief \c i gets to the heap with priority \c p independently
- /// if \c i was already there.
+ /// \brief Set the priority of an item or insert it, if it is
+ /// not stored in the heap.
///
- /// This method calls \ref push(\c i, \c p) if \c i is not stored
- /// in the heap and sets the priority of \c i to \c p otherwise.
+ /// This method sets the priority of the given item if it is
+ /// already stored in the heap. Otherwise it inserts the given
+ /// item into the heap with the given priority.
/// \param i The item.
/// \param p The priority.
void set(const Item &i, const Prio &p) {
@@ -274,13 +288,12 @@
}
}
- /// \brief Decreases the priority of \c i to \c p.
+ /// \brief Decrease the priority of an item to the given value.
///
- /// This method decreases the priority of item \c i to \c p.
- /// \pre \c i must be stored in the heap with priority at least \c
- /// p relative to \c Compare.
+ /// This function decreases the priority of an item to the given value.
/// \param i The item.
/// \param p The priority.
+ /// \pre \e i must be stored in the heap with priority at least \e p.
void decrease(const Item &i, const Prio &p) {
int idx = _iim[i];
unlace(idx);
@@ -291,13 +304,12 @@
lace(idx);
}
- /// \brief Increases the priority of \c i to \c p.
+ /// \brief Increase the priority of an item to the given value.
///
- /// This method sets the priority of item \c i to \c p.
- /// \pre \c i must be stored in the heap with priority at most \c
- /// p relative to \c Compare.
+ /// This function increases the priority of an item to the given value.
/// \param i The item.
/// \param p The priority.
+ /// \pre \e i must be stored in the heap with priority at most \e p.
void increase(const Item &i, const Prio &p) {
int idx = _iim[i];
unlace(idx);
@@ -305,13 +317,13 @@
lace(idx);
}
- /// \brief Returns if \c item is in, has already been in, or has
- /// never been in the heap.
+ /// \brief Return the state of an item.
///
- /// This method returns PRE_HEAP if \c item has never been in the
- /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
- /// otherwise. In the latter case it is possible that \c item will
- /// get back to the heap again.
+ /// This method returns \c PRE_HEAP if the given item has never
+ /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
+ /// and \c POST_HEAP otherwise.
+ /// In the latter case it is possible that the item will get back
+ /// to the heap again.
/// \param i The item.
State state(const Item &i) const {
int idx = _iim[i];
@@ -319,11 +331,11 @@
return State(idx);
}
- /// \brief Sets the state of the \c item in the heap.
+ /// \brief Set the state of an item in the heap.
///
- /// Sets the state of the \c item in the heap. It can be used to
- /// manually clear the heap when it is important to achive the
- /// better time complexity.
+ /// This function sets the state of the given item in the heap.
+ /// It can be used to manually clear the heap when it is important
+ /// to achive better time complexity.
/// \param i The item.
/// \param st The state. It should not be \c IN_HEAP.
void state(const Item& i, State st) {
@@ -359,33 +371,44 @@
}; // class BucketHeap
- /// \ingroup auxdat
+ /// \ingroup heaps
///
- /// \brief A Simplified Bucket Heap implementation.
+ /// \brief Simplified bucket heap data structure.
///
/// This class implements a simplified \e bucket \e heap data
- /// structure. It does not provide some functionality but it faster
- /// and simplier data structure than the BucketHeap. The main
- /// difference is that the BucketHeap stores for every key a double
- /// linked list while this class stores just simple lists. In the
- /// other way it does not support erasing each elements just the
- /// minimal and it does not supports key increasing, decreasing.
+ /// structure. It does not provide some functionality, but it is
+ /// faster and simpler than BucketHeap. The main difference is
+ /// that BucketHeap stores a doubly-linked list for each key while
+ /// this class stores only simply-linked lists. It supports erasing
+ /// only for the item having minimum priority and it does not support
+ /// key increasing and decreasing.
///
- /// \param IM A read and write Item int map, used internally
- /// to handle the cross references.
- /// \param MIN If the given parameter is false then instead of the
- /// minimum value the maximum can be retrivied with the top() and
- /// prio() member functions.
+ /// Note that this implementation does not conform to the
+ /// \ref concepts::Heap "heap concept" due to the lack of some
+ /// functionality.
+ ///
+ /// \tparam IM A read-writable item map with \c int values, used
+ /// internally to handle the cross references.
+ /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
+ /// The default is \e min-heap. If this parameter is set to \c false,
+ /// then the comparison is reversed, so the top(), prio() and pop()
+ /// functions deal with the item having maximum priority instead of the
+ /// minimum.
///
/// \sa BucketHeap
template <typename IM, bool MIN = true >
class SimpleBucketHeap {
public:
- typedef typename IM::Key Item;
+
+ /// Type of the item-int map.
+ typedef IM ItemIntMap;
+ /// Type of the priorities.
typedef int Prio;
- typedef std::pair<Item, Prio> Pair;
- typedef IM ItemIntMap;
+ /// Type of the items stored in the heap.
+ typedef typename ItemIntMap::Key Item;
+ /// Type of the item-priority pairs.
+ typedef std::pair<Item,Prio> Pair;
private:
@@ -393,10 +416,10 @@
public:
- /// \brief Type to represent the items states.
+ /// \brief Type to represent the states of the items.
///
- /// Each Item element have a state associated to it. It may be "in heap",
- /// "pre heap" or "post heap". The latter two are indifferent from the
+ /// Each item has a state associated to it. It can be "in heap",
+ /// "pre-heap" or "post-heap". The latter two are indifferent from the
/// heap's point of view, but may be useful to the user.
///
/// The item-int map must be initialized in such way that it assigns
@@ -409,48 +432,53 @@
public:
- /// \brief The constructor.
+ /// \brief Constructor.
///
- /// The constructor.
- /// \param map should be given to the constructor, since it is used
- /// internally to handle the cross references. The value of the map
- /// should be PRE_HEAP (-1) for each element.
+ /// Constructor.
+ /// \param map A map that assigns \c int values to the items.
+ /// It is used internally to handle the cross references.
+ /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
explicit SimpleBucketHeap(ItemIntMap &map)
: _iim(map), _free(-1), _num(0), _minimum(0) {}
- /// \brief Returns the number of items stored in the heap.
+ /// \brief The number of items stored in the heap.
///
- /// The number of items stored in the heap.
+ /// This function returns the number of items stored in the heap.
int size() const { return _num; }
- /// \brief Checks if the heap stores no items.
+ /// \brief Check if the heap is empty.
///
- /// Returns \c true if and only if the heap stores no items.
+ /// This function returns \c true if the heap is empty.
bool empty() const { return _num == 0; }
- /// \brief Make empty this heap.
+ /// \brief Make the heap empty.
///
- /// Make empty this heap. It does not change the cross reference
- /// map. If you want to reuse a heap what is not surely empty you
- /// should first clear the heap and after that you should set the
- /// cross reference map for each item to \c PRE_HEAP.
+ /// This functon makes the heap empty.
+ /// It does not change the cross reference map. If you want to reuse
+ /// a heap that is not surely empty, you should first clear it and
+ /// then you should set the cross reference map to \c PRE_HEAP
+ /// for each item.
void clear() {
_data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0;
}
/// \brief Insert a pair of item and priority into the heap.
///
- /// Adds \c p.first to the heap with priority \c p.second.
+ /// This function inserts \c p.first to the heap with priority
+ /// \c p.second.
/// \param p The pair to insert.
+ /// \pre \c p.first must not be stored in the heap.
void push(const Pair& p) {
push(p.first, p.second);
}
/// \brief Insert an item into the heap with the given priority.
///
- /// Adds \c i to the heap with priority \c p.
+ /// This function inserts the given item into the heap with the
+ /// given priority.
/// \param i The item to insert.
/// \param p The priority of the item.
+ /// \pre \e i must not be stored in the heap.
void push(const Item &i, const Prio &p) {
int idx;
if (_free == -1) {
@@ -471,10 +499,10 @@
++_num;
}
- /// \brief Returns the item with minimum priority.
+ /// \brief Return the item having minimum priority.
///
- /// This method returns the item with minimum priority.
- /// \pre The heap must be nonempty.
+ /// This function returns the item having minimum priority.
+ /// \pre The heap must be non-empty.
Item top() const {
while (_first[_minimum] == -1) {
Direction::increase(_minimum);
@@ -482,10 +510,10 @@
return _data[_first[_minimum]].item;
}
- /// \brief Returns the minimum priority.
+ /// \brief The minimum priority.
///
- /// It returns the minimum priority.
- /// \pre The heap must be nonempty.
+ /// This function returns the minimum priority.
+ /// \pre The heap must be non-empty.
Prio prio() const {
while (_first[_minimum] == -1) {
Direction::increase(_minimum);
@@ -493,9 +521,9 @@
return _minimum;
}
- /// \brief Deletes the item with minimum priority.
+ /// \brief Remove the item having minimum priority.
///
- /// This method deletes the item with minimum priority from the heap.
+ /// This function removes the item having minimum priority.
/// \pre The heap must be non-empty.
void pop() {
while (_first[_minimum] == -1) {
@@ -509,16 +537,15 @@
--_num;
}
- /// \brief Returns the priority of \c i.
+ /// \brief The priority of the given item.
///
- /// This function returns the priority of item \c i.
- /// \warning This operator is not a constant time function
- /// because it scans the whole data structure to find the proper
- /// value.
- /// \pre \c i must be in the heap.
+ /// This function returns the priority of the given item.
/// \param i The item.
+ /// \pre \e i must be in the heap.
+ /// \warning This operator is not a constant time function because
+ /// it scans the whole data structure to find the proper value.
Prio operator[](const Item &i) const {
- for (int k = 0; k < _first.size(); ++k) {
+ for (int k = 0; k < int(_first.size()); ++k) {
int idx = _first[k];
while (idx != -1) {
if (_data[idx].item == i) {
@@ -530,13 +557,13 @@
return -1;
}
- /// \brief Returns if \c item is in, has already been in, or has
- /// never been in the heap.
+ /// \brief Return the state of an item.
///
- /// This method returns PRE_HEAP if \c item has never been in the
- /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
- /// otherwise. In the latter case it is possible that \c item will
- /// get back to the heap again.
+ /// This method returns \c PRE_HEAP if the given item has never
+ /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
+ /// and \c POST_HEAP otherwise.
+ /// In the latter case it is possible that the item will get back
+ /// to the heap again.
/// \param i The item.
State state(const Item &i) const {
int idx = _iim[i];
diff -r 98a30824fe36 -r ece80147fb08 lemon/circulation.h
--- a/lemon/circulation.h Fri Jul 24 11:07:52 2009 +0200
+++ b/lemon/circulation.h Fri Sep 25 09:06:32 2009 +0200
@@ -457,19 +457,21 @@
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
diff -r 98a30824fe36 -r ece80147fb08 lemon/concepts/heap.h
--- a/lemon/concepts/heap.h Fri Jul 24 11:07:52 2009 +0200
+++ b/lemon/concepts/heap.h Fri Sep 25 09:06:32 2009 +0200
@@ -16,13 +16,13 @@
*
*/
+#ifndef LEMON_CONCEPTS_HEAP_H
+#define LEMON_CONCEPTS_HEAP_H
+
///\ingroup concept
///\file
///\brief The concept of heaps.
-#ifndef LEMON_CONCEPTS_HEAP_H
-#define LEMON_CONCEPTS_HEAP_H
-
#include <lemon/core.h>
#include <lemon/concept_check.h>
@@ -35,21 +35,27 @@
/// \brief The heap concept.
///
- /// Concept class describing the main interface of heaps. A \e heap
- /// is a data structure for storing items with specified values called
- /// \e priorities in such a way that finding the item with minimum
- /// priority is efficient. In a heap one can change the priority of an
- /// item, add or erase an item, etc.
+ /// This concept class describes the main interface of heaps.
+ /// The various \ref heaps "heap structures" are efficient
+ /// implementations of the abstract data type \e priority \e queue.
+ /// They store items with specified values called \e priorities
+ /// in such a way that finding and removing the item with minimum
+ /// priority are efficient. The basic operations are adding and
+ /// erasing items, changing the priority of an item, etc.
///
- /// \tparam PR Type of the priority of the items.
- /// \tparam IM A read and writable item map with int values, used
+ /// Heaps are crucial in several algorithms, such as Dijkstra and Prim.
+ /// Any class that conforms to this concept can be used easily in such
+ /// algorithms.
+ ///
+ /// \tparam PR Type of the priorities of the items.
+ /// \tparam IM A read-writable item map with \c int values, used
/// internally to handle the cross references.
- /// \tparam Comp A functor class for the ordering of the priorities.
+ /// \tparam CMP A functor class for comparing the priorities.
/// The default is \c std::less<PR>.
#ifdef DOXYGEN
- template <typename PR, typename IM, typename Comp = std::less<PR> >
+ template <typename PR, typename IM, typename CMP>
#else
- template <typename PR, typename IM>
+ template <typename PR, typename IM, typename CMP = std::less<PR> >
#endif
class Heap {
public:
@@ -64,109 +70,125 @@
/// \brief Type to represent the states of the items.
///
/// Each item has a state associated to it. It can be "in heap",
- /// "pre heap" or "post heap". The later two are indifferent
- /// from the point of view of the heap, but may be useful for
- /// the user.
+ /// "pre-heap" or "post-heap". The latter two are indifferent from the
+ /// heap's point of view, but may be useful to the user.
///
/// The item-int map must be initialized in such way that it assigns
/// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
enum State {
IN_HEAP = 0, ///< = 0. The "in heap" state constant.
- PRE_HEAP = -1, ///< = -1. The "pre heap" state constant.
- POST_HEAP = -2 ///< = -2. The "post heap" state constant.
+ PRE_HEAP = -1, ///< = -1. The "pre-heap" state constant.
+ POST_HEAP = -2 ///< = -2. The "post-heap" state constant.
};
- /// \brief The constructor.
+ /// \brief Constructor.
///
- /// The constructor.
+ /// Constructor.
/// \param map A map that assigns \c int values to keys of type
/// \c Item. It is used internally by the heap implementations to
/// handle the cross references. The assigned value must be
- /// \c PRE_HEAP (<tt>-1</tt>) for every item.
+ /// \c PRE_HEAP (<tt>-1</tt>) for each item.
explicit Heap(ItemIntMap &map) {}
+ /// \brief Constructor.
+ ///
+ /// Constructor.
+ /// \param map A map that assigns \c int values to keys of type
+ /// \c Item. It is used internally by the heap implementations to
+ /// handle the cross references. The assigned value must be
+ /// \c PRE_HEAP (<tt>-1</tt>) for each item.
+ /// \param comp The function object used for comparing the priorities.
+ explicit Heap(ItemIntMap &map, const CMP &comp) {}
+
/// \brief The number of items stored in the heap.
///
- /// Returns the number of items stored in the heap.
+ /// This function returns the number of items stored in the heap.
int size() const { return 0; }
- /// \brief Checks if the heap is empty.
+ /// \brief Check if the heap is empty.
///
- /// Returns \c true if the heap is empty.
+ /// This function returns \c true if the heap is empty.
bool empty() const { return false; }
- /// \brief Makes the heap empty.
+ /// \brief Make the heap empty.
///
- /// Makes the heap empty.
- void clear();
+ /// This functon makes the heap empty.
+ /// It does not change the cross reference map. If you want to reuse
+ /// a heap that is not surely empty, you should first clear it and
+ /// then you should set the cross reference map to \c PRE_HEAP
+ /// for each item.
+ void clear() {}
- /// \brief Inserts an item into the heap with the given priority.
+ /// \brief Insert an item into the heap with the given priority.
///
- /// Inserts the given item into the heap with the given priority.
+ /// This function inserts the given item into the heap with the
+ /// given priority.
/// \param i The item to insert.
/// \param p The priority of the item.
+ /// \pre \e i must not be stored in the heap.
void push(const Item &i, const Prio &p) {}
- /// \brief Returns the item having minimum priority.
+ /// \brief Return the item having minimum priority.
///
- /// Returns the item having minimum priority.
+ /// This function returns the item having minimum priority.
/// \pre The heap must be non-empty.
Item top() const {}
/// \brief The minimum priority.
///
- /// Returns the minimum priority.
+ /// This function returns the minimum priority.
/// \pre The heap must be non-empty.
Prio prio() const {}
- /// \brief Removes the item having minimum priority.
+ /// \brief Remove the item having minimum priority.
///
- /// Removes the item having minimum priority.
+ /// This function removes the item having minimum priority.
/// \pre The heap must be non-empty.
void pop() {}
- /// \brief Removes an item from the heap.
+ /// \brief Remove the given item from the heap.
///
- /// Removes the given item from the heap if it is already stored.
+ /// This function removes the given item from the heap if it is
+ /// already stored.
/// \param i The item to delete.
+ /// \pre \e i must be in the heap.
void erase(const Item &i) {}
- /// \brief The priority of an item.
+ /// \brief The priority of the given item.
///
- /// Returns the priority of the given item.
+ /// This function returns the priority of the given item.
/// \param i The item.
- /// \pre \c i must be in the heap.
+ /// \pre \e i must be in the heap.
Prio operator[](const Item &i) const {}
- /// \brief Sets the priority of an item or inserts it, if it is
+ /// \brief Set the priority of an item or insert it, if it is
/// not stored in the heap.
///
/// This method sets the priority of the given item if it is
- /// already stored in the heap.
- /// Otherwise it inserts the given item with the given priority.
+ /// already stored in the heap. Otherwise it inserts the given
+ /// item into the heap with the given priority.
///
/// \param i The item.
/// \param p The priority.
void set(const Item &i, const Prio &p) {}
- /// \brief Decreases the priority of an item to the given value.
+ /// \brief Decrease the priority of an item to the given value.
///
- /// Decreases the priority of an item to the given value.
+ /// This function decreases the priority of an item to the given value.
/// \param i The item.
/// \param p The priority.
- /// \pre \c i must be stored in the heap with priority at least \c p.
+ /// \pre \e i must be stored in the heap with priority at least \e p.
void decrease(const Item &i, const Prio &p) {}
- /// \brief Increases the priority of an item to the given value.
+ /// \brief Increase the priority of an item to the given value.
///
- /// Increases the priority of an item to the given value.
+ /// This function increases the priority of an item to the given value.
/// \param i The item.
/// \param p The priority.
- /// \pre \c i must be stored in the heap with priority at most \c p.
+ /// \pre \e i must be stored in the heap with priority at most \e p.
void increase(const Item &i, const Prio &p) {}
- /// \brief Returns if an item is in, has already been in, or has
- /// never been in the heap.
+ /// \brief Return the state of an item.
///
/// This method returns \c PRE_HEAP if the given item has never
/// been in the heap, \c IN_HEAP if it is in the heap at the moment,
@@ -176,11 +198,11 @@
/// \param i The item.
State state(const Item &i) const {}
- /// \brief Sets the state of an item in the heap.
+ /// \brief Set the state of an item in the heap.
///
- /// Sets the state of the given item in the heap. It can be used
- /// to manually clear the heap when it is important to achive the
- /// better time complexity.
+ /// This function sets the state of the given item in the heap.
+ /// It can be used to manually clear the heap when it is important
+ /// to achive better time complexity.
/// \param i The item.
/// \param st The state. It should not be \c IN_HEAP.
void state(const Item& i, State st) {}
diff -r 98a30824fe36 -r ece80147fb08 lemon/fib_heap.h
--- a/lemon/fib_heap.h Fri Jul 24 11:07:52 2009 +0200
+++ b/lemon/fib_heap.h Fri Sep 25 09:06:32 2009 +0200
@@ -20,53 +20,49 @@
#define LEMON_FIB_HEAP_H
///\file
-///\ingroup auxdat
-///\brief Fibonacci Heap implementation.
+///\ingroup heaps
+///\brief Fibonacci heap implementation.
#include <vector>
+#include <utility>
#include <functional>
#include <lemon/math.h>
namespace lemon {
- /// \ingroup auxdat
+ /// \ingroup heaps
///
- ///\brief Fibonacci Heap.
+ /// \brief Fibonacci heap data structure.
///
- ///This class implements the \e Fibonacci \e heap data structure. A \e heap
- ///is a data structure for storing items with specified values called \e
- ///priorities in such a way that finding the item with minimum priority is
- ///efficient. \c CMP specifies the ordering of the priorities. In a heap
- ///one can change the priority of an item, add or erase an item, etc.
+ /// This class implements the \e Fibonacci \e heap data structure.
+ /// It fully conforms to the \ref concepts::Heap "heap concept".
///
- ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
- ///heap. In case of many calls to these operations, it is better to use a
- ///\ref BinHeap "binary heap".
+ /// The methods \ref increase() and \ref erase() are not efficient in a
+ /// Fibonacci heap. In case of many calls of these operations, it is
+ /// better to use other heap structure, e.g. \ref BinHeap "binary heap".
///
- ///\param PRIO Type of the priority of the items.
- ///\param IM A read and writable Item int map, used internally
- ///to handle the cross references.
- ///\param CMP A class for the ordering of the priorities. The
- ///default is \c std::less<PRIO>.
- ///
- ///\sa BinHeap
- ///\sa Dijkstra
+ /// \tparam PR Type of the priorities of the items.
+ /// \tparam IM A read-writable item map with \c int values, used
+ /// internally to handle the cross references.
+ /// \tparam CMP A functor class for comparing the priorities.
+ /// The default is \c std::less<PR>.
#ifdef DOXYGEN
- template <typename PRIO, typename IM, typename CMP>
+ template <typename PR, typename IM, typename CMP>
#else
- template <typename PRIO, typename IM, typename CMP = std::less<PRIO> >
+ template <typename PR, typename IM, typename CMP = std::less<PR> >
#endif
class FibHeap {
public:
- ///\e
+
+ /// Type of the item-int map.
typedef IM ItemIntMap;
- ///\e
- typedef PRIO Prio;
- ///\e
+ /// Type of the priorities.
+ typedef PR Prio;
+ /// Type of the items stored in the heap.
typedef typename ItemIntMap::Key Item;
- ///\e
+ /// Type of the item-priority pairs.
typedef std::pair<Item,Prio> Pair;
- ///\e
+ /// Functor type for comparing the priorities.
typedef CMP Compare;
private:
@@ -80,10 +76,10 @@
public:
- /// \brief Type to represent the items states.
+ /// \brief Type to represent the states of the items.
///
- /// Each Item element have a state associated to it. It may be "in heap",
- /// "pre heap" or "post heap". The latter two are indifferent from the
+ /// Each item has a state associated to it. It can be "in heap",
+ /// "pre-heap" or "post-heap". The latter two are indifferent from the
/// heap's point of view, but may be useful to the user.
///
/// The item-int map must be initialized in such way that it assigns
@@ -94,60 +90,54 @@
POST_HEAP = -2 ///< = -2.
};
- /// \brief The constructor
+ /// \brief Constructor.
///
- /// \c map should be given to the constructor, since it is
- /// used internally to handle the cross references.
+ /// Constructor.
+ /// \param map A map that assigns \c int values to the items.
+ /// It is used internally to handle the cross references.
+ /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
explicit FibHeap(ItemIntMap &map)
: _minimum(0), _iim(map), _num() {}
- /// \brief The constructor
+ /// \brief Constructor.
///
- /// \c map should be given to the constructor, since it is used
- /// internally to handle the cross references. \c comp is an
- /// object for ordering of the priorities.
+ /// Constructor.
+ /// \param map A map that assigns \c int values to the items.
+ /// It is used internally to handle the cross references.
+ /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
+ /// \param comp The function object used for comparing the priorities.
FibHeap(ItemIntMap &map, const Compare &comp)
: _minimum(0), _iim(map), _comp(comp), _num() {}
/// \brief The number of items stored in the heap.
///
- /// Returns the number of items stored in the heap.
+ /// This function returns the number of items stored in the heap.
int size() const { return _num; }
- /// \brief Checks if the heap stores no items.
+ /// \brief Check if the heap is empty.
///
- /// Returns \c true if and only if the heap stores no items.
+ /// This function returns \c true if the heap is empty.
bool empty() const { return _num==0; }
- /// \brief Make empty this heap.
+ /// \brief Make the heap empty.
///
- /// Make empty this heap. It does not change the cross reference
- /// map. If you want to reuse a heap what is not surely empty you
- /// should first clear the heap and after that you should set the
- /// cross reference map for each item to \c PRE_HEAP.
+ /// This functon makes the heap empty.
+ /// It does not change the cross reference map. If you want to reuse
+ /// a heap that is not surely empty, you should first clear it and
+ /// then you should set the cross reference map to \c PRE_HEAP
+ /// for each item.
void clear() {
_data.clear(); _minimum = 0; _num = 0;
}
- /// \brief \c item gets to the heap with priority \c value independently
- /// if \c item was already there.
+ /// \brief Insert an item into the heap with the given priority.
///
- /// This method calls \ref push(\c item, \c value) if \c item is not
- /// stored in the heap and it calls \ref decrease(\c item, \c value) or
- /// \ref increase(\c item, \c value) otherwise.
- void set (const Item& item, const Prio& value) {
- int i=_iim[item];
- if ( i >= 0 && _data[i].in ) {
- if ( _comp(value, _data[i].prio) ) decrease(item, value);
- if ( _comp(_data[i].prio, value) ) increase(item, value);
- } else push(item, value);
- }
-
- /// \brief Adds \c item to the heap with priority \c value.
- ///
- /// Adds \c item to the heap with priority \c value.
- /// \pre \c item must not be stored in the heap.
- void push (const Item& item, const Prio& value) {
+ /// This function inserts the given item into the heap with the
+ /// given priority.
+ /// \param item The item to insert.
+ /// \param prio The priority of the item.
+ /// \pre \e item must not be stored in the heap.
+ void push (const Item& item, const Prio& prio) {
int i=_iim[item];
if ( i < 0 ) {
int s=_data.size();
@@ -168,47 +158,37 @@
_data[i].right_neighbor=_data[_minimum].right_neighbor;
_data[_minimum].right_neighbor=i;
_data[i].left_neighbor=_minimum;
- if ( _comp( value, _data[_minimum].prio) ) _minimum=i;
+ if ( _comp( prio, _data[_minimum].prio) ) _minimum=i;
} else {
_data[i].right_neighbor=_data[i].left_neighbor=i;
_minimum=i;
}
- _data[i].prio=value;
+ _data[i].prio=prio;
++_num;
}
- /// \brief Returns the item with minimum priority relative to \c Compare.
+ /// \brief Return the item having minimum priority.
///
- /// This method returns the item with minimum priority relative to \c
- /// Compare.
- /// \pre The heap must be nonempty.
+ /// This function returns the item having minimum priority.
+ /// \pre The heap must be non-empty.
Item top() const { return _data[_minimum].name; }
- /// \brief Returns the minimum priority relative to \c Compare.
+ /// \brief The minimum priority.
///
- /// It returns the minimum priority relative to \c Compare.
- /// \pre The heap must be nonempty.
- const Prio& prio() const { return _data[_minimum].prio; }
+ /// This function returns the minimum priority.
+ /// \pre The heap must be non-empty.
+ Prio prio() const { return _data[_minimum].prio; }
- /// \brief Returns the priority of \c item.
+ /// \brief Remove the item having minimum priority.
///
- /// It returns the priority of \c item.
- /// \pre \c item must be in the heap.
- const Prio& operator[](const Item& item) const {
- return _data[_iim[item]].prio;
- }
-
- /// \brief Deletes the item with minimum priority relative to \c Compare.
- ///
- /// This method deletes the item with minimum priority relative to \c
- /// Compare from the heap.
+ /// This function removes the item having minimum priority.
/// \pre The heap must be non-empty.
void pop() {
/*The first case is that there are only one root.*/
if ( _data[_minimum].left_neighbor==_minimum ) {
_data[_minimum].in=false;
if ( _data[_minimum].degree!=0 ) {
- makeroot(_data[_minimum].child);
+ makeRoot(_data[_minimum].child);
_minimum=_data[_minimum].child;
balance();
}
@@ -221,7 +201,7 @@
int child=_data[_minimum].child;
int last_child=_data[child].left_neighbor;
- makeroot(child);
+ makeRoot(child);
_data[left].right_neighbor=child;
_data[child].left_neighbor=left;
@@ -234,10 +214,12 @@
--_num;
}
- /// \brief Deletes \c item from the heap.
+ /// \brief Remove the given item from the heap.
///
- /// This method deletes \c item from the heap, if \c item was already
- /// stored in the heap. It is quite inefficient in Fibonacci heaps.
+ /// This function removes the given item from the heap if it is
+ /// already stored.
+ /// \param item The item to delete.
+ /// \pre \e item must be in the heap.
void erase (const Item& item) {
int i=_iim[item];
@@ -252,43 +234,68 @@
}
}
- /// \brief Decreases the priority of \c item to \c value.
+ /// \brief The priority of the given item.
///
- /// This method decreases the priority of \c item to \c value.
- /// \pre \c item must be stored in the heap with priority at least \c
- /// value relative to \c Compare.
- void decrease (Item item, const Prio& value) {
+ /// This function returns the priority of the given item.
+ /// \param item The item.
+ /// \pre \e item must be in the heap.
+ Prio operator[](const Item& item) const {
+ return _data[_iim[item]].prio;
+ }
+
+ /// \brief Set the priority of an item or insert it, if it is
+ /// not stored in the heap.
+ ///
+ /// This method sets the priority of the given item if it is
+ /// already stored in the heap. Otherwise it inserts the given
+ /// item into the heap with the given priority.
+ /// \param item The item.
+ /// \param prio The priority.
+ void set (const Item& item, const Prio& prio) {
int i=_iim[item];
- _data[i].prio=value;
+ if ( i >= 0 && _data[i].in ) {
+ if ( _comp(prio, _data[i].prio) ) decrease(item, prio);
+ if ( _comp(_data[i].prio, prio) ) increase(item, prio);
+ } else push(item, prio);
+ }
+
+ /// \brief Decrease the priority of an item to the given value.
+ ///
+ /// This function decreases the priority of an item to the given value.
+ /// \param item The item.
+ /// \param prio The priority.
+ /// \pre \e item must be stored in the heap with priority at least \e prio.
+ void decrease (const Item& item, const Prio& prio) {
+ int i=_iim[item];
+ _data[i].prio=prio;
int p=_data[i].parent;
- if ( p!=-1 && _comp(value, _data[p].prio) ) {
+ if ( p!=-1 && _comp(prio, _data[p].prio) ) {
cut(i,p);
cascade(p);
}
- if ( _comp(value, _data[_minimum].prio) ) _minimum=i;
+ if ( _comp(prio, _data[_minimum].prio) ) _minimum=i;
}
- /// \brief Increases the priority of \c item to \c value.
+ /// \brief Increase the priority of an item to the given value.
///
- /// This method sets the priority of \c item to \c value. Though
- /// there is no precondition on the priority of \c item, this
- /// method should be used only if it is indeed necessary to increase
- /// (relative to \c Compare) the priority of \c item, because this
- /// method is inefficient.
- void increase (Item item, const Prio& value) {
+ /// This function increases the priority of an item to the given value.
+ /// \param item The item.
+ /// \param prio The priority.
+ /// \pre \e item must be stored in the heap with priority at most \e prio.
+ void increase (const Item& item, const Prio& prio) {
erase(item);
- push(item, value);
+ push(item, prio);
}
-
- /// \brief Returns if \c item is in, has already been in, or has never
- /// been in the heap.
+ /// \brief Return the state of an item.
///
- /// This method returns PRE_HEAP if \c item has never been in the
- /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
- /// otherwise. In the latter case it is possible that \c item will
- /// get back to the heap again.
+ /// This method returns \c PRE_HEAP if the given item has never
+ /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
+ /// and \c POST_HEAP otherwise.
+ /// In the latter case it is possible that the item will get back
+ /// to the heap again.
+ /// \param item The item.
State state(const Item &item) const {
int i=_iim[item];
if( i>=0 ) {
@@ -298,11 +305,11 @@
return State(i);
}
- /// \brief Sets the state of the \c item in the heap.
+ /// \brief Set the state of an item in the heap.
///
- /// Sets the state of the \c item in the heap. It can be used to
- /// manually clear the heap when it is important to achive the
- /// better time _complexity.
+ /// This function sets the state of the given item in the heap.
+ /// It can be used to manually clear the heap when it is important
+ /// to achive better time complexity.
/// \param i The item.
/// \param st The state. It should not be \c IN_HEAP.
void state(const Item& i, State st) {
@@ -365,7 +372,7 @@
} while ( s != m );
}
- void makeroot(int c) {
+ void makeRoot(int c) {
int s=c;
do {
_data[s].parent=-1;
diff -r 98a30824fe36 -r ece80147fb08 lemon/fourary_heap.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/fourary_heap.h Fri Sep 25 09:06:32 2009 +0200
@@ -0,0 +1,342 @@
+/* -*- 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
diff -r 98a30824fe36 -r ece80147fb08 lemon/kary_heap.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/kary_heap.h Fri Sep 25 09:06:32 2009 +0200
@@ -0,0 +1,352 @@
+/* -*- 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
diff -r 98a30824fe36 -r ece80147fb08 lemon/maps.h
--- a/lemon/maps.h Fri Jul 24 11:07:52 2009 +0200
+++ b/lemon/maps.h Fri Sep 25 09:06:32 2009 +0200
@@ -22,6 +22,7 @@
#include <iterator>
#include <functional>
#include <vector>
+#include <map>
#include <lemon/core.h>
@@ -29,8 +30,6 @@
///\ingroup maps
///\brief Miscellaneous property maps
-#include <map>
-
namespace lemon {
/// \addtogroup maps
@@ -1818,7 +1817,7 @@
/// \brief Provides an immutable and unique id for each item in a graph.
///
/// IdMap provides a unique and immutable id for each item of the
- /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is
+ /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is
/// - \b unique: different items get different ids,
/// - \b immutable: the id of an item does not change (even if you
/// delete other nodes).
@@ -1902,13 +1901,14 @@
/// \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).
@@ -1923,7 +1923,7 @@
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:
@@ -1948,6 +1948,8 @@
/// 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;
@@ -2000,11 +2002,15 @@
/// 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);
}
@@ -2016,11 +2022,14 @@
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;
}
@@ -2032,9 +2041,13 @@
/// \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);
}
@@ -2046,9 +2059,13 @@
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);
@@ -2084,8 +2101,9 @@
/// \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);
}
@@ -2254,7 +2272,7 @@
}
/// \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];
@@ -2311,6 +2329,903 @@
}
};
+ /// \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,
@@ -2480,7 +3395,7 @@
/// in constant time. On the other hand, the values are updated automatically
/// whenever the digraph changes.
///
- /// \warning Besides \c addNode() and \c addArc(), a digraph structure
+ /// \warning Besides \c addNode() and \c addArc(), a digraph structure
/// may provide alternative ways to modify the digraph.
/// The correct behavior of InDegMap is not guarantied if these additional
/// features are used. For example the functions
@@ -2496,7 +3411,7 @@
::ItemNotifier::ObserverBase {
public:
-
+
/// The graph type of InDegMap
typedef GR Graph;
typedef GR Digraph;
@@ -2610,7 +3525,7 @@
/// in constant time. On the other hand, the values are updated automatically
/// whenever the digraph changes.
///
- /// \warning Besides \c addNode() and \c addArc(), a digraph structure
+ /// \warning Besides \c addNode() and \c addArc(), a digraph structure
/// may provide alternative ways to modify the digraph.
/// The correct behavior of OutDegMap is not guarantied if these additional
/// features are used. For example the functions
diff -r 98a30824fe36 -r ece80147fb08 lemon/pairing_heap.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/pairing_heap.h Fri Sep 25 09:06:32 2009 +0200
@@ -0,0 +1,474 @@
+/* -*- 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
+
diff -r 98a30824fe36 -r ece80147fb08 lemon/preflow.h
--- a/lemon/preflow.h Fri Jul 24 11:07:52 2009 +0200
+++ b/lemon/preflow.h Fri Sep 25 09:06:32 2009 +0200
@@ -104,7 +104,7 @@
/// \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$.
///
@@ -378,19 +378,21 @@
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
diff -r 98a30824fe36 -r ece80147fb08 lemon/radix_heap.h
--- a/lemon/radix_heap.h Fri Jul 24 11:07:52 2009 +0200
+++ b/lemon/radix_heap.h Fri Sep 25 09:06:32 2009 +0200
@@ -19,9 +19,9 @@
#ifndef LEMON_RADIX_HEAP_H
#define LEMON_RADIX_HEAP_H
-///\ingroup auxdat
+///\ingroup heaps
///\file
-///\brief Radix Heap implementation.
+///\brief Radix heap implementation.
#include <vector>
#include <lemon/error.h>
@@ -29,56 +29,54 @@
namespace lemon {
- /// \ingroup auxdata
+ /// \ingroup heaps
///
- /// \brief A Radix Heap implementation.
+ /// \brief Radix heap data structure.
///
- /// This class implements the \e radix \e heap data structure. A \e heap
- /// is a data structure for storing items with specified values called \e
- /// priorities in such a way that finding the item with minimum priority is
- /// efficient. This heap type can store only items with \e int priority.
- /// In a heap one can change the priority of an item, add or erase an
- /// item, but the priority cannot be decreased under the last removed
- /// item's priority.
+ /// 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.
///
- /// \param IM A read and writable Item int map, used internally
- /// to handle the cross references.
- ///
- /// \see BinHeap
- /// \see Dijkstra
+ /// \tparam IM A read-writable item map with \c int values, used
+ /// internally to handle the cross references.
template <typename IM>
class RadixHeap {
public:
- typedef typename IM::Key Item;
+
+ /// Type of the item-int map.
+ typedef IM ItemIntMap;
+ /// Type of the priorities.
typedef int Prio;
- typedef IM ItemIntMap;
+ /// Type of the items stored in the heap.
+ typedef typename ItemIntMap::Key Item;
/// \brief Exception thrown by RadixHeap.
///
- /// This Exception is thrown when a smaller priority
- /// is inserted into the \e RadixHeap then the last time erased.
+ /// This exception is thrown when an item is inserted into a
+ /// RadixHeap with a priority smaller than the last erased one.
/// \see RadixHeap
-
- class UnderFlowPriorityError : public Exception {
+ class PriorityUnderflowError : public Exception {
public:
virtual const char* what() const throw() {
- return "lemon::RadixHeap::UnderFlowPriorityError";
+ return "lemon::RadixHeap::PriorityUnderflowError";
}
};
- /// \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 ItemIntMap \e should be initialized in such way that it maps
- /// PRE_HEAP (-1) to any element to be put in the heap...
+ /// 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,
- PRE_HEAP = -1,
- POST_HEAP = -2
+ IN_HEAP = 0, ///< = 0.
+ PRE_HEAP = -1, ///< = -1.
+ POST_HEAP = -2 ///< = -2.
};
private:
@@ -96,52 +94,55 @@
RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
};
- std::vector<RadixItem> data;
- std::vector<RadixBox> boxes;
+ std::vector<RadixItem> _data;
+ std::vector<RadixBox> _boxes;
ItemIntMap &_iim;
+ public:
- public:
- /// \brief The constructor.
+ /// \brief Constructor.
///
- /// The constructor.
- ///
- /// \param map It should be given to the constructor, since it is used
- /// internally to handle the cross references. The value of the map
- /// should be PRE_HEAP (-1) for each element.
- ///
- /// \param minimal The initial minimal value of the heap.
- /// \param capacity It determines the initial capacity of the heap.
- RadixHeap(ItemIntMap &map, int minimal = 0, int capacity = 0)
- : _iim(map) {
- boxes.push_back(RadixBox(minimal, 1));
- boxes.push_back(RadixBox(minimal + 1, 1));
- while (lower(boxes.size() - 1, capacity + minimal - 1)) {
+ /// 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();
}
}
- /// 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.
- int size() const { return data.size(); }
- /// \brief Checks if the heap stores no items.
+ /// This function returns the number of items stored in the heap.
+ int size() const { return _data.size(); }
+
+ /// \brief Check if the heap is empty.
///
- /// Returns \c true if and only if the heap stores no items.
- bool empty() const { return data.empty(); }
+ /// This function returns \c true if the heap is empty.
+ bool empty() const { return _data.empty(); }
- /// \brief Make empty this heap.
+ /// \brief Make the heap empty.
///
- /// Make empty this heap. It does not change the cross reference
- /// map. If you want to reuse a heap what is not surely empty you
- /// should first clear the heap and after that you should set the
- /// cross reference map for each item to \c PRE_HEAP.
- void clear(int minimal = 0, int capacity = 0) {
- data.clear(); boxes.clear();
- boxes.push_back(RadixBox(minimal, 1));
- boxes.push_back(RadixBox(minimal + 1, 1));
- while (lower(boxes.size() - 1, capacity + minimal - 1)) {
+ /// 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();
}
}
@@ -149,255 +150,259 @@
private:
bool upper(int box, Prio pr) {
- return pr < boxes[box].min;
+ return pr < _boxes[box].min;
}
bool lower(int box, Prio pr) {
- return pr >= boxes[box].min + boxes[box].size;
+ return pr >= _boxes[box].min + _boxes[box].size;
}
- /// \brief Remove item from the box list.
+ // Remove item from the box list
void remove(int index) {
- if (data[index].prev >= 0) {
- data[data[index].prev].next = data[index].next;
+ if (_data[index].prev >= 0) {
+ _data[_data[index].prev].next = _data[index].next;
} else {
- boxes[data[index].box].first = data[index].next;
+ _boxes[_data[index].box].first = _data[index].next;
}
- if (data[index].next >= 0) {
- data[data[index].next].prev = data[index].prev;
+ if (_data[index].next >= 0) {
+ _data[_data[index].next].prev = _data[index].prev;
}
}
- /// \brief Insert item into the box list.
+ // Insert item into the box list
void insert(int box, int index) {
- if (boxes[box].first == -1) {
- boxes[box].first = index;
- data[index].next = data[index].prev = -1;
+ if (_boxes[box].first == -1) {
+ _boxes[box].first = index;
+ _data[index].next = _data[index].prev = -1;
} else {
- data[index].next = boxes[box].first;
- data[boxes[box].first].prev = index;
- data[index].prev = -1;
- boxes[box].first = index;
+ _data[index].next = _boxes[box].first;
+ _data[_boxes[box].first].prev = index;
+ _data[index].prev = -1;
+ _boxes[box].first = index;
}
- data[index].box = box;
+ _data[index].box = box;
}
- /// \brief Add a new box to the box list.
+ // 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));
+ int min = _boxes.back().min + _boxes.back().size;
+ int bs = 2 * _boxes.back().size;
+ _boxes.push_back(RadixBox(min, bs));
}
- /// \brief Move an item up into the proper box.
- void bubble_up(int index) {
- if (!lower(data[index].box, data[index].prio)) return;
+ // 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);
+ int box = findUp(_data[index].box, _data[index].prio);
insert(box, index);
}
- /// \brief Find up the proper box for the item with the given prio.
+ // 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())) {
+ if (++start == int(_boxes.size())) {
extend();
}
}
return start;
}
- /// \brief Move an item down into the proper box.
- void bubble_down(int index) {
- if (!upper(data[index].box, data[index].prio)) return;
+ // 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);
+ int box = findDown(_data[index].box, _data[index].prio);
insert(box, index);
}
- /// \brief Find up the proper box for the item with the given prio.
+ // 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 UnderFlowPriorityError();
+ if (--start < 0) throw PriorityUnderflowError();
}
return start;
}
- /// \brief Find the first not empty box.
+ // Find the first non-empty box
int findFirst() {
int first = 0;
- while (boxes[first].first == -1) ++first;
+ while (_boxes[first].first == -1) ++first;
return first;
}
- /// \brief Gives back the minimal prio of the box.
+ // 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;
+ 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;
}
- /// \brief Rearrange the items of the heap and makes the
- /// first box not empty.
+ // 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;
+ _boxes[i].min = min;
+ min += _boxes[i].size;
}
- int curr = boxes[box].first, next;
+ int curr = _boxes[box].first, next;
while (curr != -1) {
- next = data[curr].next;
- bubble_down(curr);
+ next = _data[curr].next;
+ bubbleDown(curr);
curr = next;
}
}
- void relocate_last(int index) {
- if (index != int(data.size()) - 1) {
- data[index] = data.back();
- if (data[index].prev != -1) {
- data[data[index].prev].next = index;
+ 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;
+ _boxes[_data[index].box].first = index;
}
- if (data[index].next != -1) {
- data[data[index].next].prev = index;
+ if (_data[index].next != -1) {
+ _data[_data[index].next].prev = index;
}
- _iim[data[index].item] = index;
+ _iim[_data[index].item] = index;
}
- data.pop_back();
+ _data.pop_back();
}
public:
/// \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.
+ /// \warning This method may throw an \c UnderFlowPriorityException.
void push(const Item &i, const Prio &p) {
- int n = data.size();
+ int n = _data.size();
_iim.set(i, n);
- data.push_back(RadixItem(i, p));
- while (lower(boxes.size() - 1, p)) {
+ _data.push_back(RadixItem(i, p));
+ while (lower(_boxes.size() - 1, p)) {
extend();
}
- int box = findDown(boxes.size() - 1, p);
+ int box = findDown(_boxes.size() - 1, p);
insert(box, n);
}
- /// \brief Returns the item with minimum priority.
+ /// \brief Return the item having minimum priority.
///
- /// This method returns the item with minimum priority.
- /// \pre The heap must be nonempty.
+ /// This function returns the item having minimum priority.
+ /// \pre The heap must be non-empty.
Item top() const {
const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
- return data[boxes[0].first].item;
+ return _data[_boxes[0].first].item;
}
- /// \brief Returns the minimum priority.
+ /// \brief The minimum priority.
///
- /// It returns the minimum priority.
- /// \pre The heap must be nonempty.
+ /// This function returns the minimum priority.
+ /// \pre The heap must be non-empty.
Prio prio() const {
const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
- return data[boxes[0].first].prio;
+ return _data[_boxes[0].first].prio;
}
- /// \brief Deletes the item with minimum priority.
+ /// \brief Remove the item having minimum priority.
///
- /// This method deletes the item with 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;
+ int index = _boxes[0].first;
+ _iim[_data[index].item] = POST_HEAP;
remove(index);
- relocate_last(index);
+ relocateLast(index);
}
- /// \brief Deletes \c i from the heap.
+ /// \brief Remove the given item from the heap.
///
- /// This method deletes item \c i from the heap, if \c i was
- /// already stored in the heap.
- /// \param i The item to erase.
+ /// This function removes the given item from the heap if it is
+ /// already stored.
+ /// \param i The item to delete.
+ /// \pre \e i must be in the heap.
void erase(const Item &i) {
int index = _iim[i];
_iim[i] = POST_HEAP;
remove(index);
- relocate_last(index);
+ relocateLast(index);
}
- /// \brief Returns the priority of \c i.
+ /// \brief The priority of the given item.
///
- /// This function returns the priority of item \c i.
- /// \pre \c i must be in the heap.
+ /// This function returns the priority of the given item.
/// \param i The item.
+ /// \pre \e i must be in the heap.
Prio operator[](const Item &i) const {
int idx = _iim[i];
- return data[idx].prio;
+ return _data[idx].prio;
}
- /// \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.
- /// It may throw an \e UnderFlowPriorityException.
+ /// 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;
- bubble_up(idx);
+ else if( p >= _data[idx].prio ) {
+ _data[idx].prio = p;
+ bubbleUp(idx);
} else {
- data[idx].prio = p;
- bubble_down(idx);
+ _data[idx].prio = p;
+ bubbleDown(idx);
}
}
-
- /// \brief Decreases the priority of \c i to \c p.
+ /// \brief Decrease the priority of an item to the given value.
///
- /// This method decreases the priority of item \c i to \c p.
- /// \pre \c i must be stored in the heap with priority at least \c p, and
- /// \c should be greater or equal to the last removed item's priority.
+ /// 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;
- bubble_down(idx);
+ _data[idx].prio = p;
+ bubbleDown(idx);
}
- /// \brief Increases the priority of \c i to \c p.
+ /// \brief Increase the priority of an item to the given value.
///
- /// This method sets the priority of item \c i to \c p.
- /// \pre \c i must be stored in the heap with priority at most \c p
+ /// 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;
- bubble_up(idx);
+ _data[idx].prio = p;
+ bubbleUp(idx);
}
- /// \brief Returns if \c item is in, has already been in, or has
- /// never been in the heap.
+ /// \brief Return the state of an item.
///
- /// This method returns PRE_HEAP if \c item has never been in the
- /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
- /// otherwise. In the latter case it is possible that \c item will
- /// get back to the heap again.
+ /// This method returns \c PRE_HEAP if the given item has never
+ /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
+ /// and \c POST_HEAP otherwise.
+ /// In the latter case it is possible that the item will get back
+ /// to the heap again.
/// \param i The item.
State state(const Item &i) const {
int s = _iim[i];
@@ -405,11 +410,11 @@
return State(s);
}
- /// \brief Sets the state of the \c item in the heap.
+ /// \brief Set the state of an item in the heap.
///
- /// Sets the state of the \c item in the heap. It can be used to
- /// manually clear the heap when it is important to achive the
- /// better time complexity.
+ /// This function sets the state of the given item in the heap.
+ /// It can be used to manually clear the heap when it is important
+ /// to achive better time complexity.
/// \param i The item.
/// \param st The state. It should not be \c IN_HEAP.
void state(const Item& i, State st) {
diff -r 98a30824fe36 -r ece80147fb08 test/CMakeLists.txt
--- a/test/CMakeLists.txt Fri Jul 24 11:07:52 2009 +0200
+++ b/test/CMakeLists.txt Fri Sep 25 09:06:32 2009 +0200
@@ -9,6 +9,7 @@
SET(TESTS
adaptors_test
+ bellman_ford_test
bfs_test
circulation_test
connectivity_test
diff -r 98a30824fe36 -r ece80147fb08 test/Makefile.am
--- a/test/Makefile.am Fri Jul 24 11:07:52 2009 +0200
+++ b/test/Makefile.am Fri Sep 25 09:06:32 2009 +0200
@@ -7,6 +7,7 @@
check_PROGRAMS += \
test/adaptors_test \
+ test/bellman_ford_test \
test/bfs_test \
test/circulation_test \
test/connectivity_test \
@@ -52,6 +53,7 @@
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
diff -r 98a30824fe36 -r ece80147fb08 test/bellman_ford_test.cc
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/test/bellman_ford_test.cc Fri Sep 25 09:06:32 2009 +0200
@@ -0,0 +1,283 @@
+/* -*- 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;
+}
diff -r 98a30824fe36 -r ece80147fb08 test/circulation_test.cc
--- a/test/circulation_test.cc Fri Jul 24 11:07:52 2009 +0200
+++ b/test/circulation_test.cc Fri Sep 25 09:06:32 2009 +0200
@@ -87,6 +87,11 @@
.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();
diff -r 98a30824fe36 -r ece80147fb08 test/heap_test.cc
--- a/test/heap_test.cc Fri Jul 24 11:07:52 2009 +0200
+++ b/test/heap_test.cc Fri Sep 25 09:06:32 2009 +0200
@@ -25,14 +25,17 @@
#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"
@@ -89,18 +92,16 @@
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();
}
}
@@ -112,7 +113,6 @@
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]);
@@ -123,13 +123,11 @@
}
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) {
@@ -144,7 +142,7 @@
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.");
}
}
@@ -153,7 +151,7 @@
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.");
}
}
@@ -175,6 +173,7 @@
node("source", source).
run();
+ // BinHeap
{
typedef BinHeap<Prio, ItemIntMap> IntHeap;
checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
@@ -186,6 +185,31 @@
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>();
@@ -197,6 +221,19 @@
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>();
@@ -208,6 +245,19 @@
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>();
@@ -217,8 +267,10 @@
typedef BucketHeap<IntNodeMap > NodeHeap;
checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
dijkstraHeapTest<NodeHeap>(digraph, length, source);
+
+ typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap;
+ heapSortTest<SimpleIntHeap>();
}
-
return 0;
}
diff -r 98a30824fe36 -r ece80147fb08 test/maps_test.cc
--- a/test/maps_test.cc Fri Jul 24 11:07:52 2009 +0200
+++ b/test/maps_test.cc Fri Sep 25 09:06:32 2009 +0200
@@ -22,6 +22,7 @@
#include <lemon/concept_check.h>
#include <lemon/concepts/maps.h>
#include <lemon/maps.h>
+#include <lemon/smart_graph.h>
#include "test_tools.h"
@@ -349,5 +350,226 @@
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;
}
diff -r 98a30824fe36 -r ece80147fb08 test/preflow_test.cc
--- a/test/preflow_test.cc Fri Jul 24 11:07:52 2009 +0200
+++ b/test/preflow_test.cc Fri Sep 25 09:06:32 2009 +0200
@@ -94,6 +94,11 @@
::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)
diff -r 98a30824fe36 -r ece80147fb08 tools/lemon-0.x-to-1.x.sh
--- a/tools/lemon-0.x-to-1.x.sh Fri Jul 24 11:07:52 2009 +0200
+++ b/tools/lemon-0.x-to-1.x.sh Fri Sep 25 09:06:32 2009 +0200
@@ -35,10 +35,10 @@
-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"\
@@ -68,6 +68,11 @@
-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"\