diff --git a/doc/groups.dox b/doc/groups.dox --- a/doc/groups.dox +++ b/doc/groups.dox @@ -226,14 +226,6 @@ */ /** -@defgroup matrices Matrices -@ingroup datas -\brief Two dimensional data storages implemented in LEMON. - -This group contains two dimensional data storages implemented in LEMON. -*/ - -/** @defgroup paths Path Structures @ingroup datas \brief %Path structures implemented in LEMON. @@ -246,7 +238,36 @@ efficient to have e.g. the Dijkstra algorithm to store its result in any kind of path structure. -\sa lemon::concepts::Path +\sa \ref concepts::Path "Path concept" +*/ + +/** +@defgroup heaps Heap Structures +@ingroup datas +\brief %Heap structures implemented in LEMON. + +This group contains the heap structures implemented in LEMON. + +LEMON provides several heap classes. They are efficient implementations +of the abstract data type \e priority \e queue. They store items with +specified values called \e priorities in such a way that finding and +removing the item with minimum priority are efficient. +The basic operations are adding and erasing items, changing the priority +of an item, etc. + +Heaps are crucial in several algorithms, such as Dijkstra and Prim. +The heap implementations have the same interface, thus any of them can be +used easily in such algorithms. + +\sa \ref concepts::Heap "Heap concept" +*/ + +/** +@defgroup matrices Matrices +@ingroup datas +\brief Two dimensional data storages implemented in LEMON. + +This group contains two dimensional data storages implemented in LEMON. */ /** @@ -259,6 +280,28 @@ */ /** +@defgroup geomdat Geometric Data Structures +@ingroup auxdat +\brief Geometric data structures implemented in LEMON. + +This group contains geometric data structures implemented in LEMON. + + - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional + vector with the usual operations. + - \ref lemon::dim2::Box "dim2::Box" can be used to determine the + rectangular bounding box of a set of \ref lemon::dim2::Point + "dim2::Point"'s. +*/ + +/** +@defgroup matrices Matrices +@ingroup auxdat +\brief Two dimensional data storages implemented in LEMON. + +This group contains two dimensional data storages implemented in LEMON. +*/ + +/** @defgroup algs Algorithms \brief This group contains the several algorithms implemented in LEMON. @@ -298,6 +341,15 @@ */ /** +@defgroup spantree Minimum Spanning Tree Algorithms +@ingroup algs +\brief Algorithms for finding minimum cost spanning trees and arborescences. + +This group contains the algorithms for finding minimum cost spanning +trees and arborescences. +*/ + +/** @defgroup max_flow Maximum Flow Algorithms @ingroup algs \brief Algorithms for finding maximum flows. @@ -375,7 +427,7 @@ cut is the \f$X\f$ solution of the next optimization problem: \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}} - \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f] + \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f] LEMON contains several algorithms related to minimum cut problems: @@ -391,30 +443,6 @@ */ /** -@defgroup graph_properties Connectivity and Other Graph Properties -@ingroup algs -\brief Algorithms for discovering the graph properties - -This group contains the algorithms for discovering the graph properties -like connectivity, bipartiteness, euler property, simplicity etc. - -\image html edge_biconnected_components.png -\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth -*/ - -/** -@defgroup planar Planarity Embedding and Drawing -@ingroup algs -\brief Algorithms for planarity checking, embedding and drawing - -This group contains the algorithms for planarity checking, -embedding and drawing. - -\image html planar.png -\image latex planar.eps "Plane graph" width=\textwidth -*/ - -/** @defgroup matching Matching Algorithms @ingroup algs \brief Algorithms for finding matchings in graphs and bipartite graphs. @@ -455,12 +483,36 @@ */ /** -@defgroup spantree Minimum Spanning Tree Algorithms +@defgroup graph_properties Connectivity and Other Graph Properties @ingroup algs -\brief Algorithms for finding minimum cost spanning trees and arborescences. +\brief Algorithms for discovering the graph properties -This group contains the algorithms for finding minimum cost spanning -trees and arborescences. +This group contains the algorithms for discovering the graph properties +like connectivity, bipartiteness, euler property, simplicity etc. + +\image html connected_components.png +\image latex connected_components.eps "Connected components" width=\textwidth +*/ + +/** +@defgroup planar Planarity Embedding and Drawing +@ingroup algs +\brief Algorithms for planarity checking, embedding and drawing + +This group contains the algorithms for planarity checking, +embedding and drawing. + +\image html planar.png +\image latex planar.eps "Plane graph" width=\textwidth +*/ + +/** +@defgroup approx Approximation Algorithms +@ingroup algs +\brief Approximation algorithms. + +This group contains the approximation and heuristic algorithms +implemented in LEMON. */ /** @@ -473,15 +525,6 @@ */ /** -@defgroup approx Approximation Algorithms -@ingroup algs -\brief Approximation algorithms. - -This group contains the approximation and heuristic algorithms -implemented in LEMON. -*/ - -/** @defgroup gen_opt_group General Optimization Tools \brief This group contains some general optimization frameworks implemented in LEMON. @@ -587,7 +630,7 @@ */ /** -@defgroup dimacs_group DIMACS format +@defgroup dimacs_group DIMACS Format @ingroup io_group \brief Read and write files in DIMACS format @@ -649,6 +692,15 @@ */ /** +@defgroup tools Standalone Utility Applications + +Some utility applications are listed here. + +The standard compilation procedure (./configure;make) will compile +them, as well. +*/ + +/** \anchor demoprograms @defgroup demos Demo Programs @@ -660,13 +712,4 @@ make check commands. */ -/** -@defgroup tools Standalone Utility Applications - -Some utility applications are listed here. - -The standard compilation procedure (./configure;make) will compile -them, as well. -*/ - } diff --git a/lemon/Makefile.am b/lemon/Makefile.am --- a/lemon/Makefile.am +++ b/lemon/Makefile.am @@ -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 --git a/lemon/bellman_ford.h b/lemon/bellman_ford.h new file mode 100644 --- /dev/null +++ b/lemon/bellman_ford.h @@ -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 +#include +#include +#include +#include + +#include + +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::has_infinity> + struct BellmanFordDefaultOperationTraits { + /// \e + typedef V Value; + /// \brief Gives back the zero value of the type. + static Value zero() { + return static_cast(0); + } + /// \brief Gives back the positive infinity value of the type. + static Value infinity() { + return std::numeric_limits::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 + struct BellmanFordDefaultOperationTraits { + typedef V Value; + static Value zero() { + return static_cast(0); + } + static Value infinity() { + return std::numeric_limits::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 + 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 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 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 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 + /// O(ne). + /// + /// 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". +#ifdef DOXYGEN + template +#else + template , + typename TR=BellmanFordDefaultTraits > +#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 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 MaskMap; + MaskMap *_mask; + + std::vector _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 + 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 + struct SetPredMap + : public BellmanFord< Digraph, LengthMap, SetPredMapTraits > { + typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits > Create; + }; + + template + 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 + struct SetDistMap + : public BellmanFord< Digraph, LengthMap, SetDistMapTraits > { + typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits > Create; + }; + + template + 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 + struct SetOperationTraits + : public BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits > { + typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits > + 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 (*this) + 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 (*this) + 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 (*this) + 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 + /// k+1 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 nextProcess; + std::vector 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 + /// k+1 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 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(*this) == static_cast(it); + } + bool operator!=(const ActiveIt& it) const { + return static_cast(*this) != static_cast(it); + } + bool operator<(const ActiveIt& it) const { + return static_cast(*this) < static_cast(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 negativeCycle() { + typename Digraph::template NodeMap state(*_gr, -1); + lemon::Path 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 + 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 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 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 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 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 + class BellmanFordWizardBase + : public BellmanFordWizardDefaultTraits { + + typedef BellmanFordWizardDefaultTraits 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(const_cast(&gr))), + _length(reinterpret_cast(const_cast(&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 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 + bf(*reinterpret_cast(Base::_graph), + *reinterpret_cast(Base::_length)); + if (Base::_pred) bf.predMap(*reinterpret_cast(Base::_pred)); + if (Base::_dist) bf.distMap(*reinterpret_cast(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 + bf(*reinterpret_cast(Base::_graph), + *reinterpret_cast(Base::_length)); + if (Base::_pred) bf.predMap(*reinterpret_cast(Base::_pred)); + if (Base::_dist) bf.distMap(*reinterpret_cast(Base::_dist)); + bf.run(s); + if (Base::_path) *reinterpret_cast(Base::_path) = bf.path(t); + if (Base::_di) *reinterpret_cast(Base::_di) = bf.dist(t); + return bf.reached(t); + } + + template + 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 + BellmanFordWizard > predMap(const T &t) { + Base::_pred=reinterpret_cast(const_cast(&t)); + return BellmanFordWizard >(*this); + } + + template + 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 + BellmanFordWizard > distMap(const T &t) { + Base::_dist=reinterpret_cast(const_cast(&t)); + return BellmanFordWizard >(*this); + } + + template + 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 + BellmanFordWizard > path(const T &t) + { + Base::_path=reinterpret_cast(const_cast(&t)); + return BellmanFordWizard >(*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(const_cast(&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 + BellmanFordWizard > + bellmanFord(const GR& digraph, + const LEN& length) + { + return BellmanFordWizard >(digraph, length); + } + +} //END OF NAMESPACE LEMON + +#endif + diff --git a/lemon/bfs.h b/lemon/bfs.h --- a/lemon/bfs.h +++ b/lemon/bfs.h @@ -47,7 +47,7 @@ /// ///The type of the map that stores the predecessor ///arcs of the shortest paths. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap PredMap; ///Instantiates a \c PredMap. @@ -62,7 +62,8 @@ ///The type of the map that indicates which nodes are processed. ///The type of the map that indicates which nodes are processed. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///By default it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a \c ProcessedMap. @@ -81,7 +82,7 @@ ///The type of the map that indicates which nodes are reached. ///The type of the map that indicates which nodes are reached. - ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; ///Instantiates a \c ReachedMap. @@ -96,7 +97,7 @@ ///The type of the map that stores the distances of the nodes. ///The type of the map that stores the distances of the nodes. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap DistMap; ///Instantiates a \c DistMap. @@ -225,7 +226,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///\c PredMap type. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetPredMap : public Bfs< Digraph, SetPredMapTraits > { typedef Bfs< Digraph, SetPredMapTraits > Create; @@ -245,7 +246,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///\c DistMap type. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetDistMap : public Bfs< Digraph, SetDistMapTraits > { typedef Bfs< Digraph, SetDistMapTraits > Create; @@ -265,7 +266,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///\c ReachedMap type. - ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. template struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits > { typedef Bfs< Digraph, SetReachedMapTraits > Create; @@ -285,7 +286,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///\c ProcessedMap type. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits > { typedef Bfs< Digraph, SetProcessedMapTraits > Create; @@ -413,8 +414,8 @@ ///\name Execution Control ///The simplest way to execute the BFS algorithm is to use one of the ///member functions called \ref run(Node) "run()".\n - ///If you need more control on the execution, first you have to call - ///\ref init(), then you can add several source nodes with + ///If you need better control on the execution, you have to call + ///\ref init() first, then you can add several source nodes with ///\ref addSource(). Finally the actual path computation can be ///performed with one of the \ref start() functions. @@ -737,9 +738,9 @@ ///@{ - ///The shortest path to a node. + ///The shortest path to the given node. - ///Returns the shortest path to a node. + ///Returns the shortest path to the given node from the root(s). /// ///\warning \c t should be reached from the root(s). /// @@ -747,9 +748,9 @@ ///must be called before using this function. Path path(Node t) const { return Path(*G, *_pred, t); } - ///The distance of a node from the root(s). + ///The distance of the given node from the root(s). - ///Returns the distance of a node from the root(s). + ///Returns the distance of the given node from the root(s). /// ///\warning If node \c v is not reached from the root(s), then ///the return value of this function is undefined. @@ -758,29 +759,31 @@ ///must be called before using this function. int dist(Node v) const { return (*_dist)[v]; } - ///Returns the 'previous arc' of the shortest path tree for a node. - + ///\brief Returns the 'previous arc' of the shortest path tree for + ///the given node. + /// ///This function returns the 'previous arc' of the shortest path ///tree for the node \c v, i.e. it returns the last arc of a ///shortest path from a root to \c v. It is \c INVALID if \c v ///is not reached from the root(s) or if \c v is a root. /// ///The shortest path tree used here is equal to the shortest path - ///tree used in \ref predNode(). + ///tree used in \ref predNode() and \ref predMap(). /// ///\pre Either \ref run(Node) "run()" or \ref init() ///must be called before using this function. Arc predArc(Node v) const { return (*_pred)[v];} - ///Returns the 'previous node' of the shortest path tree for a node. - + ///\brief Returns the 'previous node' of the shortest path tree for + ///the given node. + /// ///This function returns the 'previous node' of the shortest path ///tree for the node \c v, i.e. it returns the last but one node - ///from a shortest path from a root to \c v. It is \c INVALID + ///of a shortest path from a root to \c v. It is \c INVALID ///if \c v is not reached from the root(s) or if \c v is a root. /// ///The shortest path tree used here is equal to the shortest path - ///tree used in \ref predArc(). + ///tree used in \ref predArc() and \ref predMap(). /// ///\pre Either \ref run(Node) "run()" or \ref init() ///must be called before using this function. @@ -801,13 +804,13 @@ ///predecessor arcs. /// ///Returns a const reference to the node map that stores the predecessor - ///arcs, which form the shortest path tree. + ///arcs, which form the shortest path tree (forest). /// ///\pre Either \ref run(Node) "run()" or \ref init() ///must be called before using this function. const PredMap &predMap() const { return *_pred;} - ///Checks if a node is reached from the root(s). + ///Checks if the given node is reached from the root(s). ///Returns \c true if \c v is reached from the root(s). /// @@ -833,7 +836,7 @@ /// ///The type of the map that stores the predecessor ///arcs of the shortest paths. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap PredMap; ///Instantiates a PredMap. @@ -848,7 +851,7 @@ ///The type of the map that indicates which nodes are processed. ///The type of the map that indicates which nodes are processed. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a ProcessedMap. @@ -868,7 +871,7 @@ ///The type of the map that indicates which nodes are reached. ///The type of the map that indicates which nodes are reached. - ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; ///Instantiates a ReachedMap. @@ -883,7 +886,7 @@ ///The type of the map that stores the distances of the nodes. ///The type of the map that stores the distances of the nodes. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap DistMap; ///Instantiates a DistMap. @@ -898,18 +901,14 @@ ///The type of the shortest paths. ///The type of the shortest paths. - ///It must meet the \ref concepts::Path "Path" concept. + ///It must conform to the \ref concepts::Path "Path" concept. typedef lemon::Path Path; }; /// Default traits class used by BfsWizard - /// To make it easier to use Bfs algorithm - /// we have created a wizard class. - /// This \ref BfsWizard class needs default traits, - /// as well as the \ref Bfs class. - /// The \ref BfsWizardBase is a class to be the default traits of the - /// \ref BfsWizard class. + /// Default traits class used by BfsWizard. + /// \tparam GR The type of the digraph. template class BfsWizardBase : public BfsWizardDefaultTraits { @@ -937,7 +936,7 @@ public: /// Constructor. - /// This constructor does not require parameters, therefore it initiates + /// This constructor does not require parameters, it initiates /// all of the attributes to \c 0. BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {} @@ -967,7 +966,6 @@ { typedef TR Base; - ///The type of the digraph the algorithm runs on. typedef typename TR::Digraph Digraph; typedef typename Digraph::Node Node; @@ -975,16 +973,10 @@ typedef typename Digraph::Arc Arc; typedef typename Digraph::OutArcIt OutArcIt; - ///\brief The type of the map that stores the predecessor - ///arcs of the shortest paths. typedef typename TR::PredMap PredMap; - ///\brief The type of the map that stores the distances of the nodes. typedef typename TR::DistMap DistMap; - ///\brief The type of the map that indicates which nodes are reached. typedef typename TR::ReachedMap ReachedMap; - ///\brief The type of the map that indicates which nodes are processed. typedef typename TR::ProcessedMap ProcessedMap; - ///The type of the shortest paths typedef typename TR::Path Path; public: @@ -1067,11 +1059,12 @@ static PredMap *createPredMap(const Digraph &) { return 0; }; SetPredMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting PredMap object. + + ///\brief \ref named-templ-param "Named parameter" for setting + ///the predecessor map. /// - ///\ref named-func-param "Named parameter" - ///for setting PredMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that stores the predecessor arcs of the nodes. template BfsWizard > predMap(const T &t) { @@ -1085,11 +1078,12 @@ static ReachedMap *createReachedMap(const Digraph &) { return 0; }; SetReachedMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting ReachedMap object. + + ///\brief \ref named-templ-param "Named parameter" for setting + ///the reached map. /// - /// \ref named-func-param "Named parameter" - ///for setting ReachedMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that indicates which nodes are reached. template BfsWizard > reachedMap(const T &t) { @@ -1103,11 +1097,13 @@ static DistMap *createDistMap(const Digraph &) { return 0; }; SetDistMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting DistMap object. + + ///\brief \ref named-templ-param "Named parameter" for setting + ///the distance map. /// - /// \ref named-func-param "Named parameter" - ///for setting DistMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that stores the distances of the nodes calculated + ///by the algorithm. template BfsWizard > distMap(const T &t) { @@ -1121,11 +1117,12 @@ static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; SetProcessedMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting ProcessedMap object. + + ///\brief \ref named-func-param "Named parameter" for setting + ///the processed map. /// - /// \ref named-func-param "Named parameter" - ///for setting ProcessedMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that indicates which nodes are processed. template BfsWizard > processedMap(const T &t) { @@ -1264,7 +1261,7 @@ /// \brief The type of the map that indicates which nodes are reached. /// /// The type of the map that indicates which nodes are reached. - /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; /// \brief Instantiates a ReachedMap. @@ -1425,8 +1422,8 @@ /// \name Execution Control /// The simplest way to execute the BFS algorithm is to use one of the /// member functions called \ref run(Node) "run()".\n - /// If you need more control on the execution, first you have to call - /// \ref init(), then you can add several source nodes with + /// If you need better control on the execution, you have to call + /// \ref init() first, then you can add several source nodes with /// \ref addSource(). Finally the actual path computation can be /// performed with one of the \ref start() functions. @@ -1735,7 +1732,7 @@ ///@{ - /// \brief Checks if a node is reached from the root(s). + /// \brief Checks if the given node is reached from the root(s). /// /// Returns \c true if \c v is reached from the root(s). /// diff --git a/lemon/bin_heap.h b/lemon/bin_heap.h --- a/lemon/bin_heap.h +++ b/lemon/bin_heap.h @@ -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 #include @@ -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. - /// - ///\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. +#ifdef DOXYGEN + template +#else template > +#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 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 (-1) 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 (-1) 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 (-1) 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 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 --git a/lemon/binom_heap.h b/lemon/binom_heap.h new file mode 100644 --- /dev/null +++ b/lemon/binom_heap.h @@ -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 +#include +#include +#include +#include + +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. +#ifdef DOXYGEN + template +#else + template > +#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 (-1) 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 _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 (-1) 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 (-1) 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 --git a/lemon/bits/edge_set_extender.h b/lemon/bits/edge_set_extender.h --- a/lemon/bits/edge_set_extender.h +++ b/lemon/bits/edge_set_extender.h @@ -537,7 +537,7 @@ typedef MapExtender > 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 > Parent; public: - EdgeMap(const Graph& _g) + explicit EdgeMap(const Graph& _g) : Parent(_g) {} EdgeMap(const Graph& _g, const _Value& _v) diff --git a/lemon/bits/graph_extender.h b/lemon/bits/graph_extender.h --- a/lemon/bits/graph_extender.h +++ b/lemon/bits/graph_extender.h @@ -604,7 +604,7 @@ typedef MapExtender > 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 > 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 > Parent; public: - EdgeMap(const Graph& graph) + explicit EdgeMap(const Graph& graph) : Parent(graph) {} EdgeMap(const Graph& graph, const _Value& value) diff --git a/lemon/bits/map_extender.h b/lemon/bits/map_extender.h --- a/lemon/bits/map_extender.h +++ b/lemon/bits/map_extender.h @@ -49,6 +49,8 @@ typedef typename Parent::Reference Reference; typedef typename Parent::ConstReference ConstReference; + typedef typename Parent::ReferenceMapTag ReferenceMapTag; + class MapIt; class ConstMapIt; @@ -191,6 +193,8 @@ typedef typename Parent::Reference Reference; typedef typename Parent::ConstReference ConstReference; + typedef typename Parent::ReferenceMapTag ReferenceMapTag; + class MapIt; class ConstMapIt; diff --git a/lemon/bucket_heap.h b/lemon/bucket_heap.h --- a/lemon/bucket_heap.h +++ b/lemon/bucket_heap.h @@ -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 #include @@ -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 [0..C). 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 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 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 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 (-1) 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 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 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 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 (-1) 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 --git a/lemon/circulation.h b/lemon/circulation.h --- a/lemon/circulation.h +++ b/lemon/circulation.h @@ -72,7 +72,11 @@ /// The type of the map that stores the flow values. /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" /// concept. +#ifdef DOXYGEN + typedef GR::ArcMap FlowMap; +#else typedef typename Digraph::template ArcMap FlowMap; +#endif /// \brief Instantiates a FlowMap. /// @@ -87,9 +91,12 @@ /// /// The elevator type used by the algorithm. /// - /// \sa Elevator - /// \sa LinkedElevator + /// \sa Elevator, LinkedElevator +#ifdef DOXYGEN + typedef lemon::Elevator Elevator; +#else typedef lemon::Elevator Elevator; +#endif /// \brief Instantiates an Elevator. /// @@ -450,25 +457,27 @@ return *_level; } - /// \brief Sets the tolerance used by algorithm. + /// \brief Sets the tolerance used by the algorithm. /// - /// Sets the tolerance used by algorithm. - Circulation& tolerance(const Tolerance& tolerance) const { + /// Sets the tolerance object used by the algorithm. + /// \return (*this) + Circulation& tolerance(const Tolerance& tolerance) { _tol = tolerance; return *this; } /// \brief Returns a const reference to the tolerance. /// - /// Returns a const reference to the tolerance. + /// Returns a const reference to the tolerance object used by + /// the algorithm. const Tolerance& tolerance() const { - return tolerance; + return _tol; } /// \name Execution Control /// The simplest way to execute the algorithm is to call \ref run().\n - /// If you need more control on the initial solution or the execution, - /// first you have to call one of the \ref init() functions, then + /// If you need better control on the initial solution or the execution, + /// you have to call one of the \ref init() functions first, then /// the \ref start() function. ///@{ diff --git a/lemon/concepts/heap.h b/lemon/concepts/heap.h --- a/lemon/concepts/heap.h +++ b/lemon/concepts/heap.h @@ -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 #include @@ -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. #ifdef DOXYGEN - template > + template #else - template + template > #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 (-1) 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 (-1) for every item. + /// \c PRE_HEAP (-1) 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 (-1) 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 --git a/lemon/concepts/maps.h b/lemon/concepts/maps.h --- a/lemon/concepts/maps.h +++ b/lemon/concepts/maps.h @@ -182,7 +182,8 @@ template struct Constraints { - void constraints() { + typename enable_if::type + constraints() { checkConcept, _ReferenceMap >(); ref = m[key]; m[key] = val; diff --git a/lemon/dfs.h b/lemon/dfs.h --- a/lemon/dfs.h +++ b/lemon/dfs.h @@ -47,7 +47,7 @@ /// ///The type of the map that stores the predecessor ///arcs of the %DFS paths. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap PredMap; ///Instantiates a \c PredMap. @@ -62,7 +62,8 @@ ///The type of the map that indicates which nodes are processed. ///The type of the map that indicates which nodes are processed. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///By default it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a \c ProcessedMap. @@ -81,7 +82,7 @@ ///The type of the map that indicates which nodes are reached. ///The type of the map that indicates which nodes are reached. - ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; ///Instantiates a \c ReachedMap. @@ -96,7 +97,7 @@ ///The type of the map that stores the distances of the nodes. ///The type of the map that stores the distances of the nodes. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap DistMap; ///Instantiates a \c DistMap. @@ -224,7 +225,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///\c PredMap type. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetPredMap : public Dfs > { typedef Dfs > Create; @@ -244,7 +245,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///\c DistMap type. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetDistMap : public Dfs< Digraph, SetDistMapTraits > { typedef Dfs > Create; @@ -264,7 +265,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///\c ReachedMap type. - ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. template struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits > { typedef Dfs< Digraph, SetReachedMapTraits > Create; @@ -284,7 +285,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///\c ProcessedMap type. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits > { typedef Dfs< Digraph, SetProcessedMapTraits > Create; @@ -411,8 +412,8 @@ ///\name Execution Control ///The simplest way to execute the DFS algorithm is to use one of the ///member functions called \ref run(Node) "run()".\n - ///If you need more control on the execution, first you have to call - ///\ref init(), then you can add a source node with \ref addSource() + ///If you need better control on the execution, you have to call + ///\ref init() first, then you can add a source node with \ref addSource() ///and perform the actual computation with \ref start(). ///This procedure can be repeated if there are nodes that have not ///been reached. @@ -669,9 +670,9 @@ ///@{ - ///The DFS path to a node. + ///The DFS path to the given node. - ///Returns the DFS path to a node. + ///Returns the DFS path to the given node from the root(s). /// ///\warning \c t should be reached from the root(s). /// @@ -679,9 +680,9 @@ ///must be called before using this function. Path path(Node t) const { return Path(*G, *_pred, t); } - ///The distance of a node from the root(s). + ///The distance of the given node from the root(s). - ///Returns the distance of a node from the root(s). + ///Returns the distance of the given node from the root(s). /// ///\warning If node \c v is not reached from the root(s), then ///the return value of this function is undefined. @@ -690,7 +691,7 @@ ///must be called before using this function. int dist(Node v) const { return (*_dist)[v]; } - ///Returns the 'previous arc' of the %DFS tree for a node. + ///Returns the 'previous arc' of the %DFS tree for the given node. ///This function returns the 'previous arc' of the %DFS tree for the ///node \c v, i.e. it returns the last arc of a %DFS path from a @@ -698,21 +699,21 @@ ///root(s) or if \c v is a root. /// ///The %DFS tree used here is equal to the %DFS tree used in - ///\ref predNode(). + ///\ref predNode() and \ref predMap(). /// ///\pre Either \ref run(Node) "run()" or \ref init() ///must be called before using this function. Arc predArc(Node v) const { return (*_pred)[v];} - ///Returns the 'previous node' of the %DFS tree. + ///Returns the 'previous node' of the %DFS tree for the given node. ///This function returns the 'previous node' of the %DFS ///tree for the node \c v, i.e. it returns the last but one node - ///from a %DFS path from a root to \c v. It is \c INVALID + ///of a %DFS path from a root to \c v. It is \c INVALID ///if \c v is not reached from the root(s) or if \c v is a root. /// ///The %DFS tree used here is equal to the %DFS tree used in - ///\ref predArc(). + ///\ref predArc() and \ref predMap(). /// ///\pre Either \ref run(Node) "run()" or \ref init() ///must be called before using this function. @@ -733,13 +734,13 @@ ///predecessor arcs. /// ///Returns a const reference to the node map that stores the predecessor - ///arcs, which form the DFS tree. + ///arcs, which form the DFS tree (forest). /// ///\pre Either \ref run(Node) "run()" or \ref init() ///must be called before using this function. const PredMap &predMap() const { return *_pred;} - ///Checks if a node is reached from the root(s). + ///Checks if the given node. node is reached from the root(s). ///Returns \c true if \c v is reached from the root(s). /// @@ -765,7 +766,7 @@ /// ///The type of the map that stores the predecessor ///arcs of the %DFS paths. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap PredMap; ///Instantiates a PredMap. @@ -780,7 +781,7 @@ ///The type of the map that indicates which nodes are processed. ///The type of the map that indicates which nodes are processed. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a ProcessedMap. @@ -800,7 +801,7 @@ ///The type of the map that indicates which nodes are reached. ///The type of the map that indicates which nodes are reached. - ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; ///Instantiates a ReachedMap. @@ -815,7 +816,7 @@ ///The type of the map that stores the distances of the nodes. ///The type of the map that stores the distances of the nodes. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap DistMap; ///Instantiates a DistMap. @@ -830,18 +831,14 @@ ///The type of the DFS paths. ///The type of the DFS paths. - ///It must meet the \ref concepts::Path "Path" concept. + ///It must conform to the \ref concepts::Path "Path" concept. typedef lemon::Path Path; }; /// Default traits class used by DfsWizard - /// To make it easier to use Dfs algorithm - /// we have created a wizard class. - /// This \ref DfsWizard class needs default traits, - /// as well as the \ref Dfs class. - /// The \ref DfsWizardBase is a class to be the default traits of the - /// \ref DfsWizard class. + /// Default traits class used by DfsWizard. + /// \tparam GR The type of the digraph. template class DfsWizardBase : public DfsWizardDefaultTraits { @@ -869,7 +866,7 @@ public: /// Constructor. - /// This constructor does not require parameters, therefore it initiates + /// This constructor does not require parameters, it initiates /// all of the attributes to \c 0. DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {} @@ -899,7 +896,6 @@ { typedef TR Base; - ///The type of the digraph the algorithm runs on. typedef typename TR::Digraph Digraph; typedef typename Digraph::Node Node; @@ -907,16 +903,10 @@ typedef typename Digraph::Arc Arc; typedef typename Digraph::OutArcIt OutArcIt; - ///\brief The type of the map that stores the predecessor - ///arcs of the DFS paths. typedef typename TR::PredMap PredMap; - ///\brief The type of the map that stores the distances of the nodes. typedef typename TR::DistMap DistMap; - ///\brief The type of the map that indicates which nodes are reached. typedef typename TR::ReachedMap ReachedMap; - ///\brief The type of the map that indicates which nodes are processed. typedef typename TR::ProcessedMap ProcessedMap; - ///The type of the DFS paths typedef typename TR::Path Path; public: @@ -999,11 +989,12 @@ static PredMap *createPredMap(const Digraph &) { return 0; }; SetPredMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting PredMap object. + + ///\brief \ref named-templ-param "Named parameter" for setting + ///the predecessor map. /// - ///\ref named-func-param "Named parameter" - ///for setting PredMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that stores the predecessor arcs of the nodes. template DfsWizard > predMap(const T &t) { @@ -1017,11 +1008,12 @@ static ReachedMap *createReachedMap(const Digraph &) { return 0; }; SetReachedMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting ReachedMap object. + + ///\brief \ref named-templ-param "Named parameter" for setting + ///the reached map. /// - /// \ref named-func-param "Named parameter" - ///for setting ReachedMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that indicates which nodes are reached. template DfsWizard > reachedMap(const T &t) { @@ -1035,11 +1027,13 @@ static DistMap *createDistMap(const Digraph &) { return 0; }; SetDistMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting DistMap object. + + ///\brief \ref named-templ-param "Named parameter" for setting + ///the distance map. /// - /// \ref named-func-param "Named parameter" - ///for setting DistMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that stores the distances of the nodes calculated + ///by the algorithm. template DfsWizard > distMap(const T &t) { @@ -1053,11 +1047,12 @@ static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; SetProcessedMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting ProcessedMap object. + + ///\brief \ref named-func-param "Named parameter" for setting + ///the processed map. /// - /// \ref named-func-param "Named parameter" - ///for setting ProcessedMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that indicates which nodes are processed. template DfsWizard > processedMap(const T &t) { @@ -1208,7 +1203,7 @@ /// \brief The type of the map that indicates which nodes are reached. /// /// The type of the map that indicates which nodes are reached. - /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; /// \brief Instantiates a ReachedMap. @@ -1369,8 +1364,8 @@ /// \name Execution Control /// The simplest way to execute the DFS algorithm is to use one of the /// member functions called \ref run(Node) "run()".\n - /// If you need more control on the execution, first you have to call - /// \ref init(), then you can add a source node with \ref addSource() + /// If you need better control on the execution, you have to call + /// \ref init() first, then you can add a source node with \ref addSource() /// and perform the actual computation with \ref start(). /// This procedure can be repeated if there are nodes that have not /// been reached. @@ -1620,7 +1615,7 @@ ///@{ - /// \brief Checks if a node is reached from the root(s). + /// \brief Checks if the given node is reached from the root(s). /// /// Returns \c true if \c v is reached from the root(s). /// diff --git a/lemon/dijkstra.h b/lemon/dijkstra.h --- a/lemon/dijkstra.h +++ b/lemon/dijkstra.h @@ -70,9 +70,9 @@ ///The type of the map that stores the arc lengths. ///The type of the map that stores the arc lengths. - ///It must meet the \ref concepts::ReadMap "ReadMap" concept. + ///It must conform to the \ref concepts::ReadMap "ReadMap" concept. typedef LEN LengthMap; - ///The type of the length of the arcs. + ///The type of the arc lengths. typedef typename LEN::Value Value; /// Operation traits for %Dijkstra algorithm. @@ -116,7 +116,7 @@ /// ///The type of the map that stores the predecessor ///arcs of the shortest paths. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap PredMap; ///Instantiates a \c PredMap. @@ -131,7 +131,7 @@ ///The type of the map that indicates which nodes are processed. ///The type of the map that indicates which nodes are processed. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a \c ProcessedMap. @@ -151,7 +151,7 @@ ///The type of the map that stores the distances of the nodes. ///The type of the map that stores the distances of the nodes. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap DistMap; ///Instantiates a \c DistMap. @@ -169,6 +169,10 @@ /// \ingroup shortest_path ///This class provides an efficient implementation of the %Dijkstra algorithm. /// + ///The %Dijkstra algorithm solves the single-source shortest path problem + ///when all arc lengths are non-negative. If there are negative lengths, + ///the BellmanFord algorithm should be used instead. + /// ///The arc lengths are passed to the algorithm using a ///\ref concepts::ReadMap "ReadMap", ///so it is easy to change it to any kind of length. @@ -201,7 +205,7 @@ ///The type of the digraph the algorithm runs on. typedef typename TR::Digraph Digraph; - ///The type of the length of the arcs. + ///The type of the arc lengths. typedef typename TR::LengthMap::Value Value; ///The type of the map that stores the arc lengths. typedef typename TR::LengthMap LengthMap; @@ -304,7 +308,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///\c PredMap type. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetPredMap : public Dijkstra< Digraph, LengthMap, SetPredMapTraits > { @@ -325,7 +329,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///\c DistMap type. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetDistMap : public Dijkstra< Digraph, LengthMap, SetDistMapTraits > { @@ -346,7 +350,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///\c ProcessedMap type. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetProcessedMap : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits > { @@ -443,6 +447,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///\c OperationTraits type. + /// For more information see \ref DijkstraDefaultOperationTraits. template struct SetOperationTraits : public Dijkstra > { @@ -584,8 +589,8 @@ ///\name Execution Control ///The simplest way to execute the %Dijkstra algorithm is to use ///one of the member functions called \ref run(Node) "run()".\n - ///If you need more control on the execution, first you have to call - ///\ref init(), then you can add several source nodes with + ///If you need better control on the execution, you have to call + ///\ref init() first, then you can add several source nodes with ///\ref addSource(). Finally the actual path computation can be ///performed with one of the \ref start() functions. @@ -801,14 +806,14 @@ ///\name Query Functions ///The results of the %Dijkstra algorithm can be obtained using these ///functions.\n - ///Either \ref run(Node) "run()" or \ref start() should be called + ///Either \ref run(Node) "run()" or \ref init() should be called ///before using them. ///@{ - ///The shortest path to a node. + ///The shortest path to the given node. - ///Returns the shortest path to a node. + ///Returns the shortest path to the given node from the root(s). /// ///\warning \c t should be reached from the root(s). /// @@ -816,9 +821,9 @@ ///must be called before using this function. Path path(Node t) const { return Path(*G, *_pred, t); } - ///The distance of a node from the root(s). + ///The distance of the given node from the root(s). - ///Returns the distance of a node from the root(s). + ///Returns the distance of the given node from the root(s). /// ///\warning If node \c v is not reached from the root(s), then ///the return value of this function is undefined. @@ -827,29 +832,31 @@ ///must be called before using this function. Value dist(Node v) const { return (*_dist)[v]; } - ///Returns the 'previous arc' of the shortest path tree for a node. - + ///\brief Returns the 'previous arc' of the shortest path tree for + ///the given node. + /// ///This function returns the 'previous arc' of the shortest path ///tree for the node \c v, i.e. it returns the last arc of a ///shortest path from a root to \c v. It is \c INVALID if \c v ///is not reached from the root(s) or if \c v is a root. /// ///The shortest path tree used here is equal to the shortest path - ///tree used in \ref predNode(). + ///tree used in \ref predNode() and \ref predMap(). /// ///\pre Either \ref run(Node) "run()" or \ref init() ///must be called before using this function. Arc predArc(Node v) const { return (*_pred)[v]; } - ///Returns the 'previous node' of the shortest path tree for a node. - + ///\brief Returns the 'previous node' of the shortest path tree for + ///the given node. + /// ///This function returns the 'previous node' of the shortest path ///tree for the node \c v, i.e. it returns the last but one node - ///from a shortest path from a root to \c v. It is \c INVALID + ///of a shortest path from a root to \c v. It is \c INVALID ///if \c v is not reached from the root(s) or if \c v is a root. /// ///The shortest path tree used here is equal to the shortest path - ///tree used in \ref predArc(). + ///tree used in \ref predArc() and \ref predMap(). /// ///\pre Either \ref run(Node) "run()" or \ref init() ///must be called before using this function. @@ -870,13 +877,13 @@ ///predecessor arcs. /// ///Returns a const reference to the node map that stores the predecessor - ///arcs, which form the shortest path tree. + ///arcs, which form the shortest path tree (forest). /// ///\pre Either \ref run(Node) "run()" or \ref init() ///must be called before using this function. const PredMap &predMap() const { return *_pred;} - ///Checks if a node is reached from the root(s). + ///Checks if the given node is reached from the root(s). ///Returns \c true if \c v is reached from the root(s). /// @@ -895,9 +902,9 @@ bool processed(Node v) const { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; } - ///The current distance of a node from the root(s). + ///The current distance of the given node from the root(s). - ///Returns the current distance of a node from the root(s). + ///Returns the current distance of the given node from the root(s). ///It may be decreased in the following processes. /// ///\pre Either \ref run(Node) "run()" or \ref init() @@ -924,9 +931,9 @@ ///The type of the map that stores the arc lengths. ///The type of the map that stores the arc lengths. - ///It must meet the \ref concepts::ReadMap "ReadMap" concept. + ///It must conform to the \ref concepts::ReadMap "ReadMap" concept. typedef LEN LengthMap; - ///The type of the length of the arcs. + ///The type of the arc lengths. typedef typename LEN::Value Value; /// Operation traits for Dijkstra algorithm. @@ -973,7 +980,7 @@ /// ///The type of the map that stores the predecessor ///arcs of the shortest paths. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap PredMap; ///Instantiates a PredMap. @@ -988,7 +995,7 @@ ///The type of the map that indicates which nodes are processed. ///The type of the map that indicates which nodes are processed. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a ProcessedMap. @@ -1008,7 +1015,7 @@ ///The type of the map that stores the distances of the nodes. ///The type of the map that stores the distances of the nodes. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap DistMap; ///Instantiates a DistMap. @@ -1023,18 +1030,15 @@ ///The type of the shortest paths. ///The type of the shortest paths. - ///It must meet the \ref concepts::Path "Path" concept. + ///It must conform to the \ref concepts::Path "Path" concept. typedef lemon::Path Path; }; /// Default traits class used by DijkstraWizard - /// To make it easier to use Dijkstra algorithm - /// we have created a wizard class. - /// This \ref DijkstraWizard class needs default traits, - /// as well as the \ref Dijkstra class. - /// The \ref DijkstraWizardBase is a class to be the default traits of the - /// \ref DijkstraWizard class. + /// Default traits class used by DijkstraWizard. + /// \tparam GR The type of the digraph. + /// \tparam LEN The type of the length map. template class DijkstraWizardBase : public DijkstraWizardDefaultTraits { @@ -1093,7 +1097,6 @@ { typedef TR Base; - ///The type of the digraph the algorithm runs on. typedef typename TR::Digraph Digraph; typedef typename Digraph::Node Node; @@ -1101,20 +1104,12 @@ typedef typename Digraph::Arc Arc; typedef typename Digraph::OutArcIt OutArcIt; - ///The type of the map that stores the arc lengths. typedef typename TR::LengthMap LengthMap; - ///The type of the length of the arcs. typedef typename LengthMap::Value Value; - ///\brief The type of the map that stores the predecessor - ///arcs of the shortest paths. typedef typename TR::PredMap PredMap; - ///The type of the map that stores the distances of the nodes. typedef typename TR::DistMap DistMap; - ///The type of the map that indicates which nodes are processed. typedef typename TR::ProcessedMap ProcessedMap; - ///The type of the shortest paths typedef typename TR::Path Path; - ///The heap type used by the dijkstra algorithm. typedef typename TR::Heap Heap; public: @@ -1186,11 +1181,12 @@ static PredMap *createPredMap(const Digraph &) { return 0; }; SetPredMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting PredMap object. + + ///\brief \ref named-templ-param "Named parameter" for setting + ///the predecessor map. /// - ///\ref named-func-param "Named parameter" - ///for setting PredMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that stores the predecessor arcs of the nodes. template DijkstraWizard > predMap(const T &t) { @@ -1204,11 +1200,13 @@ static DistMap *createDistMap(const Digraph &) { return 0; }; SetDistMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting DistMap object. + + ///\brief \ref named-templ-param "Named parameter" for setting + ///the distance map. /// - ///\ref named-func-param "Named parameter" - ///for setting DistMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that stores the distances of the nodes calculated + ///by the algorithm. template DijkstraWizard > distMap(const T &t) { @@ -1222,11 +1220,12 @@ static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; SetProcessedMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting ProcessedMap object. + + ///\brief \ref named-func-param "Named parameter" for setting + ///the processed map. /// - /// \ref named-func-param "Named parameter" - ///for setting ProcessedMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that indicates which nodes are processed. template DijkstraWizard > processedMap(const T &t) { @@ -1239,6 +1238,7 @@ typedef T Path; SetPathBase(const TR &b) : TR(b) {} }; + ///\brief \ref named-func-param "Named parameter" ///for getting the shortest path to the target node. /// diff --git a/lemon/dim2.h b/lemon/dim2.h --- a/lemon/dim2.h +++ b/lemon/dim2.h @@ -21,16 +21,9 @@ #include -///\ingroup misc +///\ingroup geomdat ///\file ///\brief A simple two dimensional vector and a bounding box implementation -/// -/// The class \ref lemon::dim2::Point "dim2::Point" implements -/// a two dimensional vector with the usual operations. -/// -/// The class \ref lemon::dim2::Box "dim2::Box" can be used to determine -/// the rectangular bounding box of a set of -/// \ref lemon::dim2::Point "dim2::Point"'s. namespace lemon { @@ -40,7 +33,7 @@ ///tools for handling two dimensional coordinates namespace dim2 { - /// \addtogroup misc + /// \addtogroup geomdat /// @{ /// Two dimensional vector (plain vector) diff --git a/lemon/fib_heap.h b/lemon/fib_heap.h --- a/lemon/fib_heap.h +++ b/lemon/fib_heap.h @@ -20,53 +20,49 @@ #define LEMON_FIB_HEAP_H ///\file -///\ingroup auxdat -///\brief Fibonacci Heap implementation. +///\ingroup heaps +///\brief Fibonacci heap implementation. #include +#include #include #include 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. - /// - ///\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. #ifdef DOXYGEN - template + template #else - template > + template > #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 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 (-1) 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 (-1) 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 --git a/lemon/fourary_heap.h b/lemon/fourary_heap.h new file mode 100644 --- /dev/null +++ b/lemon/fourary_heap.h @@ -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 +#include +#include + +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 K=4. 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. + /// + ///\sa BinHeap + ///\sa KaryHeap +#ifdef DOXYGEN + template +#else + template > +#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 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 (-1) 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 _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 (-1) 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 (-1) 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+30) 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=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 --git a/lemon/gomory_hu.h b/lemon/gomory_hu.h --- a/lemon/gomory_hu.h +++ b/lemon/gomory_hu.h @@ -359,10 +359,10 @@ /// This example counts the nodes in the minimum cut separating \c s from /// \c t. /// \code - /// GomoruHu gom(g, capacities); + /// GomoryHu gom(g, capacities); /// gom.run(); /// int cnt=0; - /// for(GomoruHu::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt; + /// for(GomoryHu::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt; /// \endcode class MinCutNodeIt { @@ -456,10 +456,10 @@ /// This example computes the value of the minimum cut separating \c s from /// \c t. /// \code - /// GomoruHu gom(g, capacities); + /// GomoryHu gom(g, capacities); /// gom.run(); /// int value=0; - /// for(GomoruHu::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e) + /// for(GomoryHu::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e) /// value+=capacities[e]; /// \endcode /// The result will be the same as the value returned by diff --git a/lemon/kary_heap.h b/lemon/kary_heap.h new file mode 100644 --- /dev/null +++ b/lemon/kary_heap.h @@ -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 +#include +#include + +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 K=2 and K=4, 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. + /// + ///\sa BinHeap + ///\sa FouraryHeap +#ifdef DOXYGEN + template +#else + template > +#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 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 (-1) 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 _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 (-1) 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 (-1) 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; i0) 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=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 --git a/lemon/maps.h b/lemon/maps.h --- a/lemon/maps.h +++ b/lemon/maps.h @@ -1789,11 +1789,11 @@ /// order of Dfs algorithm, as the following examples show. /// \code /// std::vector v; - /// dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run(); + /// dfs(g).processedMap(loggerBoolMap(std::back_inserter(v))).run(s); /// \endcode /// \code /// std::vector v(countNodes(g)); - /// dfs(g,s).processedMap(loggerBoolMap(v.begin())).run(); + /// dfs(g).processedMap(loggerBoolMap(v.begin())).run(s); /// \endcode /// /// \note The container of the iterator must contain enough space diff --git a/lemon/min_cost_arborescence.h b/lemon/min_cost_arborescence.h --- a/lemon/min_cost_arborescence.h +++ b/lemon/min_cost_arborescence.h @@ -488,8 +488,8 @@ /// \name Execution Control /// The simplest way to execute the algorithm is to use /// one of the member functions called \c run(...). \n - /// If you need more control on the execution, - /// first you must call \ref init(), then you can add several + /// If you need better control on the execution, + /// you have to call \ref init() first, then you can add several /// source nodes with \ref addSource(). /// Finally \ref start() will perform the arborescence /// computation. diff --git a/lemon/pairing_heap.h b/lemon/pairing_heap.h new file mode 100644 --- /dev/null +++ b/lemon/pairing_heap.h @@ -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 +#include +#include +#include + +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. +#ifdef DOXYGEN + template +#else + template > +#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 (-1) 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 _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 (-1) 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 (-1) 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 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=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 --git a/lemon/preflow.h b/lemon/preflow.h --- a/lemon/preflow.h +++ b/lemon/preflow.h @@ -52,7 +52,11 @@ /// /// The type of the map that stores the flow values. /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. +#ifdef DOXYGEN + typedef GR::ArcMap FlowMap; +#else typedef typename Digraph::template ArcMap FlowMap; +#endif /// \brief Instantiates a FlowMap. /// @@ -67,9 +71,12 @@ /// /// The elevator type used by Preflow algorithm. /// - /// \sa Elevator - /// \sa LinkedElevator - typedef LinkedElevator Elevator; + /// \sa Elevator, LinkedElevator +#ifdef DOXYGEN + typedef lemon::Elevator Elevator; +#else + typedef lemon::Elevator Elevator; +#endif /// \brief Instantiates an Elevator. /// @@ -97,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$. /// @@ -371,26 +378,28 @@ 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 (*this) + Preflow& tolerance(const Tolerance& tolerance) { _tolerance = tolerance; return *this; } /// \brief Returns a const reference to the tolerance. /// - /// Returns a const reference to the tolerance. + /// Returns a const reference to the tolerance object used by + /// the algorithm. const Tolerance& tolerance() const { - return tolerance; + return _tolerance; } /// \name Execution Control /// The simplest way to execute the preflow algorithm is to use /// \ref run() or \ref runMinCut().\n - /// If you need more control on the initial solution or the execution, - /// first you have to call one of the \ref init() functions, then + /// If you need better control on the initial solution or the execution, + /// you have to call one of the \ref init() functions first, then /// \ref startFirstPhase() and if you need it \ref startSecondPhase(). ///@{ diff --git a/lemon/radix_heap.h b/lemon/radix_heap.h --- a/lemon/radix_heap.h +++ b/lemon/radix_heap.h @@ -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 #include @@ -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 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 (-1) 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 data; - std::vector boxes; + std::vector _data; + std::vector _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 (-1) 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&>(*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&>(*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 --git a/test/CMakeLists.txt b/test/CMakeLists.txt --- a/test/CMakeLists.txt +++ b/test/CMakeLists.txt @@ -9,6 +9,7 @@ SET(TESTS adaptors_test + bellman_ford_test bfs_test circulation_test connectivity_test diff --git a/test/Makefile.am b/test/Makefile.am --- a/test/Makefile.am +++ b/test/Makefile.am @@ -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 --git a/test/bellman_ford_test.cc b/test/bellman_ford_test.cc new file mode 100644 --- /dev/null +++ b/test/bellman_ford_test.cc @@ -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 +#include +#include +#include +#include +#include + +#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 LengthMap; + typedef BellmanFord 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 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 > + ::SetDistMap > + ::SetOperationTraits > + ::Create bf_test(gr,length); + + LengthMap length_map; + concepts::ReadWriteMap pred_map; + concepts::ReadWriteMap 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 LengthMap; + + Digraph g; + bool b; + bellmanFord(g,LengthMap()).run(Node()); + b = bellmanFord(g,LengthMap()).run(Node(),Node()); + bellmanFord(g,LengthMap()) + .predMap(concepts::ReadWriteMap()) + .distMap(concepts::ReadWriteMap()) + .run(Node()); + b=bellmanFord(g,LengthMap()) + .predMap(concepts::ReadWriteMap()) + .distMap(concepts::ReadWriteMap()) + .path(concepts::Path()) + .dist(Value()) + .run(Node(),Node()); +} + + +template +void checkBellmanFord() { + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); + typedef typename Digraph::template ArcMap 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 + bf(gr, length); + bf.run(s); + Path 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 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 bf(gr, length); + bf.run(n1); + StaticPath p = bf.negativeCycle(); + check(p.length() == 1 && p.front() == p.back() && p.front() == a2, + "Wrong negative cycle."); + } + + length[a2] = 0; + + { + BellmanFord 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 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 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(); + checkBellmanFord(); + checkBellmanFordNegativeCycle(); + return 0; +} diff --git a/test/circulation_test.cc b/test/circulation_test.cc --- a/test/circulation_test.cc +++ b/test/circulation_test.cc @@ -87,6 +87,11 @@ .upperMap(ucap) .supplyMap(supply) .flowMap(flow); + + const CirculationType::Elevator& elev = const_circ_test.elevator(); + circ_test.elevator(const_cast(elev)); + CirculationType::Tolerance tol = const_circ_test.tolerance(); + circ_test.tolerance(tol); circ_test.init(); circ_test.greedyInit(); diff --git a/test/heap_test.cc b/test/heap_test.cc --- a/test/heap_test.cc +++ b/test/heap_test.cc @@ -25,14 +25,17 @@ #include #include - #include #include #include #include +#include +#include #include +#include #include +#include #include #include "test_tools.h" @@ -89,18 +92,16 @@ template void heapSortTest() { RangeMap map(test_len, -1); - Heap heap(map); std::vector 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 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 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 IntHeap; checkConcept, IntHeap>(); @@ -186,6 +185,31 @@ dijkstraHeapTest(digraph, length, source); } + // FouraryHeap + { + typedef FouraryHeap IntHeap; + checkConcept, IntHeap>(); + heapSortTest(); + heapIncreaseTest(); + + typedef FouraryHeap NodeHeap; + checkConcept, NodeHeap>(); + dijkstraHeapTest(digraph, length, source); + } + + // KaryHeap + { + typedef KaryHeap IntHeap; + checkConcept, IntHeap>(); + heapSortTest(); + heapIncreaseTest(); + + typedef KaryHeap NodeHeap; + checkConcept, NodeHeap>(); + dijkstraHeapTest(digraph, length, source); + } + + // FibHeap { typedef FibHeap IntHeap; checkConcept, IntHeap>(); @@ -197,6 +221,19 @@ dijkstraHeapTest(digraph, length, source); } + // PairingHeap + { + typedef PairingHeap IntHeap; + checkConcept, IntHeap>(); + heapSortTest(); + heapIncreaseTest(); + + typedef PairingHeap NodeHeap; + checkConcept, NodeHeap>(); + dijkstraHeapTest(digraph, length, source); + } + + // RadixHeap { typedef RadixHeap IntHeap; checkConcept, IntHeap>(); @@ -208,6 +245,19 @@ dijkstraHeapTest(digraph, length, source); } + // BinomHeap + { + typedef BinomHeap IntHeap; + checkConcept, IntHeap>(); + heapSortTest(); + heapIncreaseTest(); + + typedef BinomHeap NodeHeap; + checkConcept, NodeHeap>(); + dijkstraHeapTest(digraph, length, source); + } + + // BucketHeap, SimpleBucketHeap { typedef BucketHeap IntHeap; checkConcept, IntHeap>(); @@ -217,8 +267,10 @@ typedef BucketHeap NodeHeap; checkConcept, NodeHeap>(); dijkstraHeapTest(digraph, length, source); + + typedef SimpleBucketHeap SimpleIntHeap; + heapSortTest(); } - return 0; } diff --git a/test/maps_test.cc b/test/maps_test.cc --- a/test/maps_test.cc +++ b/test/maps_test.cc @@ -579,6 +579,40 @@ it == map.endValue(), "Wrong value iterator"); } + // CrossRefMap + { + typedef SmartDigraph Graph; + DIGRAPH_TYPEDEFS(Graph); + + checkConcept, + CrossRefMap >(); + + Graph gr; + typedef CrossRefMap 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; diff --git a/test/preflow_test.cc b/test/preflow_test.cc --- a/test/preflow_test.cc +++ b/test/preflow_test.cc @@ -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(elev)); + PreflowType::Tolerance tol = const_preflow_test.tolerance(); + preflow_test.tolerance(tol); preflow_test .capacityMap(cap) diff --git a/tools/lemon-0.x-to-1.x.sh b/tools/lemon-0.x-to-1.x.sh --- a/tools/lemon-0.x-to-1.x.sh +++ b/tools/lemon-0.x-to-1.x.sh @@ -35,10 +35,10 @@ -e "s/IncEdgeIt/_In_cEd_geIt_label_/g"\ -e "s/Edge\>/_Ar_c_label_/g"\ -e "s/\/_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/\/_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/\/adaptors.h/g"\ + -e "s/\/core.h/g"\ + -e "s/\/lgf_reader.h/g"\ + -e "s/\/lgf_writer.h/g"\ + -e "s/\/connectivity.h/g"\ -e "s/DigraphToEps/GraphToEps/g"\ -e "s/digraphToEps/graphToEps/g"\ -e "s/\/SetPredMap/g"\