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,11 @@ lemon/adaptors.h \ lemon/arg_parser.h \ lemon/assert.h \ + lemon/bellman_ford.h \ lemon/bfs.h \ lemon/bin_heap.h \ + lemon/binom_heap.h \ + lemon/bucket_heap.h \ lemon/cbc.h \ lemon/circulation.h \ lemon/clp.h \ @@ -76,12 +79,15 @@ lemon/elevator.h \ lemon/error.h \ lemon/euler.h \ + lemon/fib_heap.h \ + lemon/fourary_heap.h \ lemon/full_graph.h \ lemon/glpk.h \ lemon/gomory_hu.h \ lemon/graph_to_eps.h \ lemon/grid_graph.h \ lemon/hypercube_graph.h \ + lemon/kary_heap.h \ lemon/kruskal.h \ lemon/hao_orlin.h \ lemon/lgf_reader.h \ @@ -90,15 +96,16 @@ lemon/lp.h \ lemon/lp_base.h \ lemon/lp_skeleton.h \ - lemon/list_graph.h \ lemon/maps.h \ lemon/matching.h \ lemon/math.h \ lemon/min_cost_arborescence.h \ lemon/nauty_reader.h \ lemon/network_simplex.h \ + lemon/pairing_heap.h \ lemon/path.h \ lemon/preflow.h \ + lemon/radix_heap.h \ lemon/radix_sort.h \ lemon/random.h \ lemon/smart_graph.h \ 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 @@ -414,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. @@ -1422,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. 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. - /// - ///A \e heap is a data structure for storing items with specified values - ///called \e priorities in such a way that finding the item with minimum - ///priority is efficient. \c Comp specifies the ordering of the priorities. - ///In a heap one can change the priority of an item, add or erase an - ///item, etc. + /// This class implements the \e binary \e heap data structure. + /// It fully conforms to the \ref concepts::Heap "heap concept". /// - ///\tparam PR Type of the priority of the items. - ///\tparam IM A read and writable item map with int values, used internally - ///to handle the cross references. - ///\tparam Comp A functor class for the ordering of the priorities. - ///The default is \c std::less. - /// - ///\sa FibHeap - ///\sa Dijkstra - template > + /// \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 - typedef Comp Compare; + /// Functor type for comparing the priorities. + typedef CMP Compare; - /// \brief Type to represent the items states. + /// \brief Type to represent the states of the items. /// - /// Each Item element have a state associated to it. It may be "in heap", - /// "pre heap" or "post heap". The latter two are indifferent from the + /// Each item has a state associated to it. It can be "in heap", + /// "pre-heap" or "post-heap". The latter two are indifferent from the /// heap's point of view, but may be useful to the user. /// /// The item-int map must be initialized in such way that it assigns @@ -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/bucket_heap.h b/lemon/bucket_heap.h new file mode 100644 --- /dev/null +++ b/lemon/bucket_heap.h @@ -0,0 +1,594 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2009 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#ifndef LEMON_BUCKET_HEAP_H +#define LEMON_BUCKET_HEAP_H + +///\ingroup heaps +///\file +///\brief Bucket heap implementation. + +#include +#include +#include + +namespace lemon { + + namespace _bucket_heap_bits { + + template + struct DirectionTraits { + static bool less(int left, int right) { + return left < right; + } + static void increase(int& value) { + ++value; + } + }; + + template <> + struct DirectionTraits { + static bool less(int left, int right) { + return left > right; + } + static void increase(int& value) { + --value; + } + }; + + } + + /// \ingroup heaps + /// + /// \brief Bucket heap data structure. + /// + /// This class implements the \e bucket \e heap data structure. + /// It practically conforms to the \ref concepts::Heap "heap concept", + /// but it has some limitations. + /// + /// The bucket heap is a very simple structure. It can store only + /// \c int priorities and it maintains a list of items for each priority + /// in the range [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: + + /// Type of the item-int map. + typedef IM ItemIntMap; + /// Type of the priorities. + typedef int Prio; + /// Type of the items stored in the heap. + typedef typename ItemIntMap::Key Item; + /// Type of the item-priority pairs. + typedef std::pair Pair; + + private: + + typedef _bucket_heap_bits::DirectionTraits Direction; + + public: + + /// \brief Type to represent the states of the items. + /// + /// Each item has a state associated to it. It can be "in heap", + /// "pre-heap" or "post-heap". The latter two are indifferent from the + /// heap's point of view, but may be useful to the user. + /// + /// The item-int map must be initialized in such way that it assigns + /// \c PRE_HEAP (-1) to any element to be put in the heap. + enum State { + IN_HEAP = 0, ///< = 0. + PRE_HEAP = -1, ///< = -1. + POST_HEAP = -2 ///< = -2. + }; + + public: + + /// \brief Constructor. + /// + /// Constructor. + /// \param map A map that assigns \c int values to the items. + /// It is used internally to handle the cross references. + /// The assigned value must be \c PRE_HEAP (-1) for each item. + explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {} + + /// \brief The number of items stored in the heap. + /// + /// This function returns the number of items stored in the heap. + int size() const { return _data.size(); } + + /// \brief Check if the heap is empty. + /// + /// This function returns \c true if the heap is empty. + bool empty() const { return _data.empty(); } + + /// \brief Make the heap empty. + /// + /// This functon makes the heap empty. + /// It does not change the cross reference map. If you want to reuse + /// a heap that is not surely empty, you should first clear it and + /// then you should set the cross reference map to \c PRE_HEAP + /// for each item. + void clear() { + _data.clear(); _first.clear(); _minimum = 0; + } + + private: + + void relocateLast(int idx) { + if (idx + 1 < int(_data.size())) { + _data[idx] = _data.back(); + if (_data[idx].prev != -1) { + _data[_data[idx].prev].next = idx; + } else { + _first[_data[idx].value] = idx; + } + if (_data[idx].next != -1) { + _data[_data[idx].next].prev = idx; + } + _iim[_data[idx].item] = idx; + } + _data.pop_back(); + } + + void unlace(int idx) { + if (_data[idx].prev != -1) { + _data[_data[idx].prev].next = _data[idx].next; + } else { + _first[_data[idx].value] = _data[idx].next; + } + if (_data[idx].next != -1) { + _data[_data[idx].next].prev = _data[idx].prev; + } + } + + void lace(int idx) { + if (int(_first.size()) <= _data[idx].value) { + _first.resize(_data[idx].value + 1, -1); + } + _data[idx].next = _first[_data[idx].value]; + if (_data[idx].next != -1) { + _data[_data[idx].next].prev = idx; + } + _first[_data[idx].value] = idx; + _data[idx].prev = -1; + } + + public: + + /// \brief Insert a pair of item and priority into the heap. + /// + /// This function inserts \c p.first to the heap with priority + /// \c p.second. + /// \param p The pair to insert. + /// \pre \c p.first must not be stored in the heap. + void push(const Pair& p) { + push(p.first, p.second); + } + + /// \brief Insert an item into the heap with the given priority. + /// + /// This function inserts the given item into the heap with the + /// given priority. + /// \param i The item to insert. + /// \param p The priority of the item. + /// \pre \e i must not be stored in the heap. + void push(const Item &i, const Prio &p) { + int idx = _data.size(); + _iim[i] = idx; + _data.push_back(BucketItem(i, p)); + lace(idx); + if (Direction::less(p, _minimum)) { + _minimum = p; + } + } + + /// \brief Return the item having minimum priority. + /// + /// This function returns the item having minimum priority. + /// \pre The heap must be non-empty. + Item top() const { + while (_first[_minimum] == -1) { + Direction::increase(_minimum); + } + return _data[_first[_minimum]].item; + } + + /// \brief The minimum priority. + /// + /// This function returns the minimum priority. + /// \pre The heap must be non-empty. + Prio prio() const { + while (_first[_minimum] == -1) { + Direction::increase(_minimum); + } + return _minimum; + } + + /// \brief Remove the item having minimum priority. + /// + /// This function removes the item having minimum priority. + /// \pre The heap must be non-empty. + void pop() { + while (_first[_minimum] == -1) { + Direction::increase(_minimum); + } + int idx = _first[_minimum]; + _iim[_data[idx].item] = -2; + unlace(idx); + relocateLast(idx); + } + + /// \brief Remove the given item from the heap. + /// + /// This function removes the given item from the heap if it is + /// already stored. + /// \param i The item to delete. + /// \pre \e i must be in the heap. + void erase(const Item &i) { + int idx = _iim[i]; + _iim[_data[idx].item] = -2; + unlace(idx); + relocateLast(idx); + } + + /// \brief The priority of the given item. + /// + /// This function returns the priority of the given item. + /// \param i The item. + /// \pre \e i must be in the heap. + Prio operator[](const Item &i) const { + int idx = _iim[i]; + return _data[idx].value; + } + + /// \brief Set the priority of an item or insert it, if it is + /// not stored in the heap. + /// + /// This method sets the priority of the given item if it is + /// already stored in the heap. Otherwise it inserts the given + /// item into the heap with the given priority. + /// \param i The item. + /// \param p The priority. + void set(const Item &i, const Prio &p) { + int idx = _iim[i]; + if (idx < 0) { + push(i, p); + } else if (Direction::less(p, _data[idx].value)) { + decrease(i, p); + } else { + increase(i, p); + } + } + + /// \brief Decrease the priority of an item to the given value. + /// + /// This function decreases the priority of an item to the given value. + /// \param i The item. + /// \param p The priority. + /// \pre \e i must be stored in the heap with priority at least \e p. + void decrease(const Item &i, const Prio &p) { + int idx = _iim[i]; + unlace(idx); + _data[idx].value = p; + if (Direction::less(p, _minimum)) { + _minimum = p; + } + lace(idx); + } + + /// \brief Increase the priority of an item to the given value. + /// + /// This function increases the priority of an item to the given value. + /// \param i The item. + /// \param p The priority. + /// \pre \e i must be stored in the heap with priority at most \e p. + void increase(const Item &i, const Prio &p) { + int idx = _iim[i]; + unlace(idx); + _data[idx].value = p; + lace(idx); + } + + /// \brief Return the state of an item. + /// + /// This method returns \c PRE_HEAP if the given item has never + /// been in the heap, \c IN_HEAP if it is in the heap at the moment, + /// and \c POST_HEAP otherwise. + /// In the latter case it is possible that the item will get back + /// to the heap again. + /// \param i The item. + State state(const Item &i) const { + int idx = _iim[i]; + if (idx >= 0) idx = 0; + return State(idx); + } + + /// \brief Set the state of an item in the heap. + /// + /// This function sets the state of the given item in the heap. + /// It can be used to manually clear the heap when it is important + /// to achive better time complexity. + /// \param i The item. + /// \param st The state. It should not be \c IN_HEAP. + void state(const Item& i, State st) { + switch (st) { + case POST_HEAP: + case PRE_HEAP: + if (state(i) == IN_HEAP) { + erase(i); + } + _iim[i] = st; + break; + case IN_HEAP: + break; + } + } + + private: + + struct BucketItem { + BucketItem(const Item& _item, int _value) + : item(_item), value(_value) {} + + Item item; + int value; + + int prev, next; + }; + + ItemIntMap& _iim; + std::vector _first; + std::vector _data; + mutable int _minimum; + + }; // class BucketHeap + + /// \ingroup heaps + /// + /// \brief Simplified bucket heap data structure. + /// + /// This class implements a simplified \e bucket \e heap data + /// structure. It does not provide some functionality, but it is + /// faster and simpler than BucketHeap. The main difference is + /// that BucketHeap stores a doubly-linked list for each key while + /// this class stores only simply-linked lists. It supports erasing + /// only for the item having minimum priority and it does not support + /// key increasing and decreasing. + /// + /// Note that this implementation does not conform to the + /// \ref concepts::Heap "heap concept" due to the lack of some + /// functionality. + /// + /// \tparam IM A read-writable item map with \c int values, used + /// internally to handle the cross references. + /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap. + /// The default is \e min-heap. If this parameter is set to \c false, + /// then the comparison is reversed, so the top(), prio() and pop() + /// functions deal with the item having maximum priority instead of the + /// minimum. + /// + /// \sa BucketHeap + template + class SimpleBucketHeap { + + public: + + /// Type of the item-int map. + typedef IM ItemIntMap; + /// Type of the priorities. + typedef int Prio; + /// Type of the items stored in the heap. + typedef typename ItemIntMap::Key Item; + /// Type of the item-priority pairs. + typedef std::pair Pair; + + private: + + typedef _bucket_heap_bits::DirectionTraits Direction; + + public: + + /// \brief Type to represent the states of the items. + /// + /// Each item has a state associated to it. It can be "in heap", + /// "pre-heap" or "post-heap". The latter two are indifferent from the + /// heap's point of view, but may be useful to the user. + /// + /// The item-int map must be initialized in such way that it assigns + /// \c PRE_HEAP (-1) to any element to be put in the heap. + enum State { + IN_HEAP = 0, ///< = 0. + PRE_HEAP = -1, ///< = -1. + POST_HEAP = -2 ///< = -2. + }; + + public: + + /// \brief Constructor. + /// + /// Constructor. + /// \param map A map that assigns \c int values to the items. + /// It is used internally to handle the cross references. + /// The assigned value must be \c PRE_HEAP (-1) for each item. + explicit SimpleBucketHeap(ItemIntMap &map) + : _iim(map), _free(-1), _num(0), _minimum(0) {} + + /// \brief The number of items stored in the heap. + /// + /// This function returns the number of items stored in the heap. + int size() const { return _num; } + + /// \brief Check if the heap is empty. + /// + /// This function returns \c true if the heap is empty. + bool empty() const { return _num == 0; } + + /// \brief Make the heap empty. + /// + /// This functon makes the heap empty. + /// It does not change the cross reference map. If you want to reuse + /// a heap that is not surely empty, you should first clear it and + /// then you should set the cross reference map to \c PRE_HEAP + /// for each item. + void clear() { + _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0; + } + + /// \brief Insert a pair of item and priority into the heap. + /// + /// This function inserts \c p.first to the heap with priority + /// \c p.second. + /// \param p The pair to insert. + /// \pre \c p.first must not be stored in the heap. + void push(const Pair& p) { + push(p.first, p.second); + } + + /// \brief Insert an item into the heap with the given priority. + /// + /// This function inserts the given item into the heap with the + /// given priority. + /// \param i The item to insert. + /// \param p The priority of the item. + /// \pre \e i must not be stored in the heap. + void push(const Item &i, const Prio &p) { + int idx; + if (_free == -1) { + idx = _data.size(); + _data.push_back(BucketItem(i)); + } else { + idx = _free; + _free = _data[idx].next; + _data[idx].item = i; + } + _iim[i] = idx; + if (p >= int(_first.size())) _first.resize(p + 1, -1); + _data[idx].next = _first[p]; + _first[p] = idx; + if (Direction::less(p, _minimum)) { + _minimum = p; + } + ++_num; + } + + /// \brief Return the item having minimum priority. + /// + /// This function returns the item having minimum priority. + /// \pre The heap must be non-empty. + Item top() const { + while (_first[_minimum] == -1) { + Direction::increase(_minimum); + } + return _data[_first[_minimum]].item; + } + + /// \brief The minimum priority. + /// + /// This function returns the minimum priority. + /// \pre The heap must be non-empty. + Prio prio() const { + while (_first[_minimum] == -1) { + Direction::increase(_minimum); + } + return _minimum; + } + + /// \brief Remove the item having minimum priority. + /// + /// This function removes the item having minimum priority. + /// \pre The heap must be non-empty. + void pop() { + while (_first[_minimum] == -1) { + Direction::increase(_minimum); + } + int idx = _first[_minimum]; + _iim[_data[idx].item] = -2; + _first[_minimum] = _data[idx].next; + _data[idx].next = _free; + _free = idx; + --_num; + } + + /// \brief The priority of the given item. + /// + /// This function returns the priority of the given item. + /// \param i The item. + /// \pre \e i must be in the heap. + /// \warning This operator is not a constant time function because + /// it scans the whole data structure to find the proper value. + Prio operator[](const Item &i) const { + for (int k = 0; k < int(_first.size()); ++k) { + int idx = _first[k]; + while (idx != -1) { + if (_data[idx].item == i) { + return k; + } + idx = _data[idx].next; + } + } + return -1; + } + + /// \brief Return the state of an item. + /// + /// This method returns \c PRE_HEAP if the given item has never + /// been in the heap, \c IN_HEAP if it is in the heap at the moment, + /// and \c POST_HEAP otherwise. + /// In the latter case it is possible that the item will get back + /// to the heap again. + /// \param i The item. + State state(const Item &i) const { + int idx = _iim[i]; + if (idx >= 0) idx = 0; + return State(idx); + } + + private: + + struct BucketItem { + BucketItem(const Item& _item) + : item(_item) {} + + Item item; + int next; + }; + + ItemIntMap& _iim; + std::vector _first; + std::vector _data; + int _free, _num; + mutable int _minimum; + + }; // class SimpleBucketHeap + +} + +#endif 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/dfs.h b/lemon/dfs.h --- a/lemon/dfs.h +++ b/lemon/dfs.h @@ -412,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. @@ -1364,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. diff --git a/lemon/dijkstra.h b/lemon/dijkstra.h --- a/lemon/dijkstra.h +++ b/lemon/dijkstra.h @@ -589,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. 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 new file mode 100644 --- /dev/null +++ b/lemon/fib_heap.h @@ -0,0 +1,475 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2009 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#ifndef LEMON_FIB_HEAP_H +#define LEMON_FIB_HEAP_H + +///\file +///\ingroup heaps +///\brief Fibonacci heap implementation. + +#include +#include +#include +#include + +namespace lemon { + + /// \ingroup heaps + /// + /// \brief Fibonacci heap data structure. + /// + /// This class implements the \e Fibonacci \e heap data structure. + /// It fully conforms to the \ref concepts::Heap "heap concept". + /// + /// The methods \ref increase() and \ref erase() are not efficient in a + /// Fibonacci heap. In case of many calls of these operations, it is + /// better to use other heap structure, e.g. \ref BinHeap "binary heap". + /// + /// \tparam PR Type of the priorities of the items. + /// \tparam IM A read-writable item map with \c int values, used + /// internally to handle the cross references. + /// \tparam CMP A functor class for comparing the priorities. + /// The default is \c std::less. +#ifdef DOXYGEN + template +#else + template > +#endif + class FibHeap { + public: + + /// Type of the item-int map. + typedef IM ItemIntMap; + /// Type of the priorities. + typedef PR Prio; + /// Type of the items stored in the heap. + typedef typename ItemIntMap::Key Item; + /// Type of the item-priority pairs. + typedef std::pair Pair; + /// Functor type for comparing the priorities. + typedef CMP Compare; + + private: + class Store; + + std::vector _data; + int _minimum; + ItemIntMap &_iim; + Compare _comp; + int _num; + + public: + + /// \brief Type to represent the states of the items. + /// + /// Each item has a state associated to it. It can be "in heap", + /// "pre-heap" or "post-heap". The latter two are indifferent from the + /// heap's point of view, but may be useful to the user. + /// + /// The item-int map must be initialized in such way that it assigns + /// \c PRE_HEAP (-1) to any element to be put in the heap. + enum State { + IN_HEAP = 0, ///< = 0. + PRE_HEAP = -1, ///< = -1. + POST_HEAP = -2 ///< = -2. + }; + + /// \brief Constructor. + /// + /// Constructor. + /// \param map A map that assigns \c int values to the items. + /// It is used internally to handle the cross references. + /// The assigned value must be \c PRE_HEAP (-1) for each item. + explicit FibHeap(ItemIntMap &map) + : _minimum(0), _iim(map), _num() {} + + /// \brief Constructor. + /// + /// Constructor. + /// \param map A map that assigns \c int values to the items. + /// It is used internally to handle the cross references. + /// The assigned value must be \c PRE_HEAP (-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. + /// + /// This function returns the number of items stored in the heap. + int size() const { return _num; } + + /// \brief Check if the heap is empty. + /// + /// This function returns \c true if the heap is empty. + bool empty() const { return _num==0; } + + /// \brief Make the heap empty. + /// + /// This functon makes the heap empty. + /// It does not change the cross reference map. If you want to reuse + /// a heap that is not surely empty, you should first clear it and + /// then you should set the cross reference map to \c PRE_HEAP + /// for each item. + void clear() { + _data.clear(); _minimum = 0; _num = 0; + } + + /// \brief Insert an item into the heap with the given priority. + /// + /// This function inserts the given item into the heap with the + /// given priority. + /// \param item The item to insert. + /// \param prio The priority of the item. + /// \pre \e item must not be stored in the heap. + void push (const Item& item, const Prio& prio) { + int i=_iim[item]; + if ( i < 0 ) { + int s=_data.size(); + _iim.set( item, s ); + Store st; + st.name=item; + _data.push_back(st); + i=s; + } else { + _data[i].parent=_data[i].child=-1; + _data[i].degree=0; + _data[i].in=true; + _data[i].marked=false; + } + + if ( _num ) { + _data[_data[_minimum].right_neighbor].left_neighbor=i; + _data[i].right_neighbor=_data[_minimum].right_neighbor; + _data[_minimum].right_neighbor=i; + _data[i].left_neighbor=_minimum; + if ( _comp( prio, _data[_minimum].prio) ) _minimum=i; + } else { + _data[i].right_neighbor=_data[i].left_neighbor=i; + _minimum=i; + } + _data[i].prio=prio; + ++_num; + } + + /// \brief Return the item having minimum priority. + /// + /// This function returns the item having minimum priority. + /// \pre The heap must be non-empty. + Item top() const { return _data[_minimum].name; } + + /// \brief The minimum priority. + /// + /// This function returns the minimum priority. + /// \pre The heap must be non-empty. + Prio prio() const { return _data[_minimum].prio; } + + /// \brief Remove the item having minimum priority. + /// + /// This function removes the item having minimum priority. + /// \pre The heap must be non-empty. + void pop() { + /*The first case is that there are only one root.*/ + if ( _data[_minimum].left_neighbor==_minimum ) { + _data[_minimum].in=false; + if ( _data[_minimum].degree!=0 ) { + makeRoot(_data[_minimum].child); + _minimum=_data[_minimum].child; + balance(); + } + } else { + int right=_data[_minimum].right_neighbor; + unlace(_minimum); + _data[_minimum].in=false; + if ( _data[_minimum].degree > 0 ) { + int left=_data[_minimum].left_neighbor; + int child=_data[_minimum].child; + int last_child=_data[child].left_neighbor; + + makeRoot(child); + + _data[left].right_neighbor=child; + _data[child].left_neighbor=left; + _data[right].left_neighbor=last_child; + _data[last_child].right_neighbor=right; + } + _minimum=right; + balance(); + } // the case where there are more roots + --_num; + } + + /// \brief Remove the given item from the heap. + /// + /// This function removes the given item from the heap if it is + /// already stored. + /// \param item The item to delete. + /// \pre \e item must be in the heap. + void erase (const Item& item) { + int i=_iim[item]; + + if ( i >= 0 && _data[i].in ) { + if ( _data[i].parent!=-1 ) { + int p=_data[i].parent; + cut(i,p); + cascade(p); + } + _minimum=i; //As if its prio would be -infinity + pop(); + } + } + + /// \brief The priority of the given item. + /// + /// This function returns the priority of the given item. + /// \param item The item. + /// \pre \e item must be in the heap. + Prio operator[](const Item& item) const { + return _data[_iim[item]].prio; + } + + /// \brief Set the priority of an item or insert it, if it is + /// not stored in the heap. + /// + /// This method sets the priority of the given item if it is + /// already stored in the heap. Otherwise it inserts the given + /// item into the heap with the given priority. + /// \param item The item. + /// \param prio The priority. + void set (const Item& item, const Prio& prio) { + int i=_iim[item]; + if ( i >= 0 && _data[i].in ) { + if ( _comp(prio, _data[i].prio) ) decrease(item, prio); + if ( _comp(_data[i].prio, prio) ) increase(item, prio); + } else push(item, prio); + } + + /// \brief Decrease the priority of an item to the given value. + /// + /// This function decreases the priority of an item to the given value. + /// \param item The item. + /// \param prio The priority. + /// \pre \e item must be stored in the heap with priority at least \e prio. + void decrease (const Item& item, const Prio& prio) { + int i=_iim[item]; + _data[i].prio=prio; + int p=_data[i].parent; + + if ( p!=-1 && _comp(prio, _data[p].prio) ) { + cut(i,p); + cascade(p); + } + if ( _comp(prio, _data[_minimum].prio) ) _minimum=i; + } + + /// \brief Increase the priority of an item to the given value. + /// + /// This function increases the priority of an item to the given value. + /// \param item The item. + /// \param prio The priority. + /// \pre \e item must be stored in the heap with priority at most \e prio. + void increase (const Item& item, const Prio& prio) { + erase(item); + push(item, prio); + } + + /// \brief Return the state of an item. + /// + /// This method returns \c PRE_HEAP if the given item has never + /// been in the heap, \c IN_HEAP if it is in the heap at the moment, + /// and \c POST_HEAP otherwise. + /// In the latter case it is possible that the item will get back + /// to the heap again. + /// \param item The item. + State state(const Item &item) const { + int i=_iim[item]; + if( i>=0 ) { + if ( _data[i].in ) i=0; + else i=-2; + } + return State(i); + } + + /// \brief Set the state of an item in the heap. + /// + /// This function sets the state of the given item in the heap. + /// It can be used to manually clear the heap when it is important + /// to achive better time complexity. + /// \param i The item. + /// \param st The state. It should not be \c IN_HEAP. + void state(const Item& i, State st) { + switch (st) { + case POST_HEAP: + case PRE_HEAP: + if (state(i) == IN_HEAP) { + erase(i); + } + _iim[i] = st; + break; + case IN_HEAP: + break; + } + } + + private: + + void balance() { + + int maxdeg=int( std::floor( 2.08*log(double(_data.size()))))+1; + + std::vector A(maxdeg,-1); + + /* + *Recall that now minimum does not point to the minimum prio element. + *We set minimum to this during balance(). + */ + int anchor=_data[_minimum].left_neighbor; + int next=_minimum; + bool end=false; + + do { + int active=next; + if ( anchor==active ) end=true; + int d=_data[active].degree; + next=_data[active].right_neighbor; + + while (A[d]!=-1) { + if( _comp(_data[active].prio, _data[A[d]].prio) ) { + fuse(active,A[d]); + } else { + fuse(A[d],active); + active=A[d]; + } + A[d]=-1; + ++d; + } + A[d]=active; + } while ( !end ); + + + while ( _data[_minimum].parent >=0 ) + _minimum=_data[_minimum].parent; + int s=_minimum; + int m=_minimum; + do { + if ( _comp(_data[s].prio, _data[_minimum].prio) ) _minimum=s; + s=_data[s].right_neighbor; + } while ( s != m ); + } + + void makeRoot(int c) { + int s=c; + do { + _data[s].parent=-1; + s=_data[s].right_neighbor; + } while ( s != c ); + } + + void cut(int a, int b) { + /* + *Replacing a from the children of b. + */ + --_data[b].degree; + + if ( _data[b].degree !=0 ) { + int child=_data[b].child; + if ( child==a ) + _data[b].child=_data[child].right_neighbor; + unlace(a); + } + + + /*Lacing a to the roots.*/ + int right=_data[_minimum].right_neighbor; + _data[_minimum].right_neighbor=a; + _data[a].left_neighbor=_minimum; + _data[a].right_neighbor=right; + _data[right].left_neighbor=a; + + _data[a].parent=-1; + _data[a].marked=false; + } + + void cascade(int a) { + if ( _data[a].parent!=-1 ) { + int p=_data[a].parent; + + if ( _data[a].marked==false ) _data[a].marked=true; + else { + cut(a,p); + cascade(p); + } + } + } + + void fuse(int a, int b) { + unlace(b); + + /*Lacing b under a.*/ + _data[b].parent=a; + + if (_data[a].degree==0) { + _data[b].left_neighbor=b; + _data[b].right_neighbor=b; + _data[a].child=b; + } else { + int child=_data[a].child; + int last_child=_data[child].left_neighbor; + _data[child].left_neighbor=b; + _data[b].right_neighbor=child; + _data[last_child].right_neighbor=b; + _data[b].left_neighbor=last_child; + } + + ++_data[a].degree; + + _data[b].marked=false; + } + + /* + *It is invoked only if a has siblings. + */ + void unlace(int a) { + int leftn=_data[a].left_neighbor; + int rightn=_data[a].right_neighbor; + _data[leftn].right_neighbor=rightn; + _data[rightn].left_neighbor=leftn; + } + + + class Store { + friend class FibHeap; + + Item name; + int parent; + int left_neighbor; + int right_neighbor; + int child; + int degree; + bool marked; + bool in; + Prio prio; + + Store() : parent(-1), child(-1), degree(), marked(false), in(true) {} + }; + }; + +} //namespace lemon + +#endif //LEMON_FIB_HEAP_H + 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 @@ -22,6 +22,7 @@ #include #include #include +#include #include @@ -29,8 +30,6 @@ ///\ingroup maps ///\brief Miscellaneous property maps -#include - namespace lemon { /// \addtogroup maps @@ -1818,7 +1817,7 @@ /// \brief Provides an immutable and unique id for each item in a graph. /// /// IdMap provides a unique and immutable id for each item of the - /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is + /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is /// - \b unique: different items get different ids, /// - \b immutable: the id of an item does not change (even if you /// delete other nodes). @@ -1902,13 +1901,14 @@ /// \brief General cross reference graph map type. /// This class provides simple invertable graph maps. - /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap" - /// and if a key is set to a new value then store it - /// in the inverse map. - /// + /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap) + /// and if a key is set to a new value, then stores it in the inverse map. /// The values of the map can be accessed /// with stl compatible forward iterator. /// + /// This type is not reference map, so it cannot be modified with + /// the subscript operator. + /// /// \tparam GR The graph type. /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or /// \c GR::Edge). @@ -1923,7 +1923,7 @@ typedef typename ItemSetTraits:: template Map::Type Map; - typedef std::map Container; + typedef std::multimap Container; Container _inv_map; public: @@ -1948,6 +1948,8 @@ /// This iterator is an stl compatible forward /// iterator on the values of the map. The values can /// be accessed in the [beginValue, endValue) range. + /// They are considered with multiplicity, so each value is + /// traversed for each item it is assigned to. class ValueIterator : public std::iterator { friend class CrossRefMap; @@ -2000,11 +2002,15 @@ /// Sets the value associated with the given key. void set(const Key& key, const Value& val) { Value oldval = Map::operator[](key); - typename Container::iterator it = _inv_map.find(oldval); - if (it != _inv_map.end() && it->second == key) { - _inv_map.erase(it); + typename Container::iterator it; + for (it = _inv_map.equal_range(oldval).first; + it != _inv_map.equal_range(oldval).second; ++it) { + if (it->second == key) { + _inv_map.erase(it); + break; + } } - _inv_map.insert(make_pair(val, key)); + _inv_map.insert(std::make_pair(val, key)); Map::set(key, val); } @@ -2016,11 +2022,14 @@ return Map::operator[](key); } - /// \brief Gives back the item by its value. + /// \brief Gives back an item by its value. /// - /// Gives back the item by its value. - Key operator()(const Value& key) const { - typename Container::const_iterator it = _inv_map.find(key); + /// This function gives back an item that is assigned to + /// the given value or \c INVALID if no such item exists. + /// If there are more items with the same associated value, + /// only one of them is returned. + Key operator()(const Value& val) const { + typename Container::const_iterator it = _inv_map.find(val); return it != _inv_map.end() ? it->second : INVALID; } @@ -2032,9 +2041,13 @@ /// \c AlterationNotifier. virtual void erase(const Key& key) { Value val = Map::operator[](key); - typename Container::iterator it = _inv_map.find(val); - if (it != _inv_map.end() && it->second == key) { - _inv_map.erase(it); + typename Container::iterator it; + for (it = _inv_map.equal_range(val).first; + it != _inv_map.equal_range(val).second; ++it) { + if (it->second == key) { + _inv_map.erase(it); + break; + } } Map::erase(key); } @@ -2046,9 +2059,13 @@ virtual void erase(const std::vector& keys) { for (int i = 0; i < int(keys.size()); ++i) { Value val = Map::operator[](keys[i]); - typename Container::iterator it = _inv_map.find(val); - if (it != _inv_map.end() && it->second == keys[i]) { - _inv_map.erase(it); + typename Container::iterator it; + for (it = _inv_map.equal_range(val).first; + it != _inv_map.equal_range(val).second; ++it) { + if (it->second == keys[i]) { + _inv_map.erase(it); + break; + } } } Map::erase(keys); @@ -2084,8 +2101,9 @@ /// \brief Subscript operator. /// - /// Subscript operator. It gives back the item - /// that was last assigned to the given value. + /// Subscript operator. It gives back an item + /// that is assigned to the given value or \c INVALID + /// if no such item exists. Value operator[](const Key& key) const { return _inverted(key); } @@ -2254,7 +2272,7 @@ } /// \brief Gives back the item belonging to a \e RangeId - /// + /// /// Gives back the item belonging to a \e RangeId. Item operator()(int id) const { return _inv_map[id]; @@ -2311,6 +2329,903 @@ } }; + /// \brief Dynamic iterable \c bool map. + /// + /// This class provides a special graph map type which can store a + /// \c bool value for graph items (\c Node, \c Arc or \c Edge). + /// For both \c true and \c false values it is possible to iterate on + /// the keys. + /// + /// This type is a reference map, so it can be modified with the + /// subscript operator. + /// + /// \tparam GR The graph type. + /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or + /// \c GR::Edge). + /// + /// \see IterableIntMap, IterableValueMap + /// \see CrossRefMap + template + class IterableBoolMap + : protected ItemSetTraits::template Map::Type { + private: + typedef GR Graph; + + typedef typename ItemSetTraits::ItemIt KeyIt; + typedef typename ItemSetTraits::template Map::Type Parent; + + std::vector _array; + int _sep; + + public: + + /// Indicates that the map is reference map. + typedef True ReferenceMapTag; + + /// The key type + typedef K Key; + /// The value type + typedef bool Value; + /// The const reference type. + typedef const Value& ConstReference; + + private: + + int position(const Key& key) const { + return Parent::operator[](key); + } + + public: + + /// \brief Reference to the value of the map. + /// + /// This class is similar to the \c bool type. It can be converted to + /// \c bool and it provides the same operators. + class Reference { + friend class IterableBoolMap; + private: + Reference(IterableBoolMap& map, const Key& key) + : _key(key), _map(map) {} + public: + + Reference& operator=(const Reference& value) { + _map.set(_key, static_cast(value)); + return *this; + } + + operator bool() const { + return static_cast(_map)[_key]; + } + + Reference& operator=(bool value) { + _map.set(_key, value); + return *this; + } + Reference& operator&=(bool value) { + _map.set(_key, _map[_key] & value); + return *this; + } + Reference& operator|=(bool value) { + _map.set(_key, _map[_key] | value); + return *this; + } + Reference& operator^=(bool value) { + _map.set(_key, _map[_key] ^ value); + return *this; + } + private: + Key _key; + IterableBoolMap& _map; + }; + + /// \brief Constructor of the map with a default value. + /// + /// Constructor of the map with a default value. + explicit IterableBoolMap(const Graph& graph, bool def = false) + : Parent(graph) { + typename Parent::Notifier* nf = Parent::notifier(); + Key it; + for (nf->first(it); it != INVALID; nf->next(it)) { + Parent::set(it, _array.size()); + _array.push_back(it); + } + _sep = (def ? _array.size() : 0); + } + + /// \brief Const subscript operator of the map. + /// + /// Const subscript operator of the map. + bool operator[](const Key& key) const { + return position(key) < _sep; + } + + /// \brief Subscript operator of the map. + /// + /// Subscript operator of the map. + Reference operator[](const Key& key) { + return Reference(*this, key); + } + + /// \brief Set operation of the map. + /// + /// Set operation of the map. + void set(const Key& key, bool value) { + int pos = position(key); + if (value) { + if (pos < _sep) return; + Key tmp = _array[_sep]; + _array[_sep] = key; + Parent::set(key, _sep); + _array[pos] = tmp; + Parent::set(tmp, pos); + ++_sep; + } else { + if (pos >= _sep) return; + --_sep; + Key tmp = _array[_sep]; + _array[_sep] = key; + Parent::set(key, _sep); + _array[pos] = tmp; + Parent::set(tmp, pos); + } + } + + /// \brief Set all items. + /// + /// Set all items in the map. + /// \note Constant time operation. + void setAll(bool value) { + _sep = (value ? _array.size() : 0); + } + + /// \brief Returns the number of the keys mapped to \c true. + /// + /// Returns the number of the keys mapped to \c true. + int trueNum() const { + return _sep; + } + + /// \brief Returns the number of the keys mapped to \c false. + /// + /// Returns the number of the keys mapped to \c false. + int falseNum() const { + return _array.size() - _sep; + } + + /// \brief Iterator for the keys mapped to \c true. + /// + /// Iterator for the keys mapped to \c true. It works + /// like a graph item iterator, it can be converted to + /// the key type of the map, incremented with \c ++ operator, and + /// if the iterator leaves the last valid key, it will be equal to + /// \c INVALID. + class TrueIt : public Key { + public: + typedef Key Parent; + + /// \brief Creates an iterator. + /// + /// Creates an iterator. It iterates on the + /// keys mapped to \c true. + /// \param map The IterableBoolMap. + explicit TrueIt(const IterableBoolMap& map) + : Parent(map._sep > 0 ? map._array[map._sep - 1] : INVALID), + _map(&map) {} + + /// \brief Invalid constructor \& conversion. + /// + /// This constructor initializes the iterator to be invalid. + /// \sa Invalid for more details. + TrueIt(Invalid) : Parent(INVALID), _map(0) {} + + /// \brief Increment operator. + /// + /// Increment operator. + TrueIt& operator++() { + int pos = _map->position(*this); + Parent::operator=(pos > 0 ? _map->_array[pos - 1] : INVALID); + return *this; + } + + private: + const IterableBoolMap* _map; + }; + + /// \brief Iterator for the keys mapped to \c false. + /// + /// Iterator for the keys mapped to \c false. It works + /// like a graph item iterator, it can be converted to + /// the key type of the map, incremented with \c ++ operator, and + /// if the iterator leaves the last valid key, it will be equal to + /// \c INVALID. + class FalseIt : public Key { + public: + typedef Key Parent; + + /// \brief Creates an iterator. + /// + /// Creates an iterator. It iterates on the + /// keys mapped to \c false. + /// \param map The IterableBoolMap. + explicit FalseIt(const IterableBoolMap& map) + : Parent(map._sep < int(map._array.size()) ? + map._array.back() : INVALID), _map(&map) {} + + /// \brief Invalid constructor \& conversion. + /// + /// This constructor initializes the iterator to be invalid. + /// \sa Invalid for more details. + FalseIt(Invalid) : Parent(INVALID), _map(0) {} + + /// \brief Increment operator. + /// + /// Increment operator. + FalseIt& operator++() { + int pos = _map->position(*this); + Parent::operator=(pos > _map->_sep ? _map->_array[pos - 1] : INVALID); + return *this; + } + + private: + const IterableBoolMap* _map; + }; + + /// \brief Iterator for the keys mapped to a given value. + /// + /// Iterator for the keys mapped to a given value. It works + /// like a graph item iterator, it can be converted to + /// the key type of the map, incremented with \c ++ operator, and + /// if the iterator leaves the last valid key, it will be equal to + /// \c INVALID. + class ItemIt : public Key { + public: + typedef Key Parent; + + /// \brief Creates an iterator with a value. + /// + /// Creates an iterator with a value. It iterates on the + /// keys mapped to the given value. + /// \param map The IterableBoolMap. + /// \param value The value. + ItemIt(const IterableBoolMap& map, bool value) + : Parent(value ? + (map._sep > 0 ? + map._array[map._sep - 1] : INVALID) : + (map._sep < int(map._array.size()) ? + map._array.back() : INVALID)), _map(&map) {} + + /// \brief Invalid constructor \& conversion. + /// + /// This constructor initializes the iterator to be invalid. + /// \sa Invalid for more details. + ItemIt(Invalid) : Parent(INVALID), _map(0) {} + + /// \brief Increment operator. + /// + /// Increment operator. + ItemIt& operator++() { + int pos = _map->position(*this); + int _sep = pos >= _map->_sep ? _map->_sep : 0; + Parent::operator=(pos > _sep ? _map->_array[pos - 1] : INVALID); + return *this; + } + + private: + const IterableBoolMap* _map; + }; + + protected: + + virtual void add(const Key& key) { + Parent::add(key); + Parent::set(key, _array.size()); + _array.push_back(key); + } + + virtual void add(const std::vector& keys) { + Parent::add(keys); + for (int i = 0; i < int(keys.size()); ++i) { + Parent::set(keys[i], _array.size()); + _array.push_back(keys[i]); + } + } + + virtual void erase(const Key& key) { + int pos = position(key); + if (pos < _sep) { + --_sep; + Parent::set(_array[_sep], pos); + _array[pos] = _array[_sep]; + Parent::set(_array.back(), _sep); + _array[_sep] = _array.back(); + _array.pop_back(); + } else { + Parent::set(_array.back(), pos); + _array[pos] = _array.back(); + _array.pop_back(); + } + Parent::erase(key); + } + + virtual void erase(const std::vector& keys) { + for (int i = 0; i < int(keys.size()); ++i) { + int pos = position(keys[i]); + if (pos < _sep) { + --_sep; + Parent::set(_array[_sep], pos); + _array[pos] = _array[_sep]; + Parent::set(_array.back(), _sep); + _array[_sep] = _array.back(); + _array.pop_back(); + } else { + Parent::set(_array.back(), pos); + _array[pos] = _array.back(); + _array.pop_back(); + } + } + Parent::erase(keys); + } + + virtual void build() { + Parent::build(); + typename Parent::Notifier* nf = Parent::notifier(); + Key it; + for (nf->first(it); it != INVALID; nf->next(it)) { + Parent::set(it, _array.size()); + _array.push_back(it); + } + _sep = 0; + } + + virtual void clear() { + _array.clear(); + _sep = 0; + Parent::clear(); + } + + }; + + + namespace _maps_bits { + template + struct IterableIntMapNode { + IterableIntMapNode() : value(-1) {} + IterableIntMapNode(int _value) : value(_value) {} + Item prev, next; + int value; + }; + } + + /// \brief Dynamic iterable integer map. + /// + /// This class provides a special graph map type which can store an + /// integer value for graph items (\c Node, \c Arc or \c Edge). + /// For each non-negative value it is possible to iterate on the keys + /// mapped to the value. + /// + /// This type is a reference map, so it can be modified with the + /// subscript operator. + /// + /// \note The size of the data structure depends on the largest + /// value in the map. + /// + /// \tparam GR The graph type. + /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or + /// \c GR::Edge). + /// + /// \see IterableBoolMap, IterableValueMap + /// \see CrossRefMap + template + class IterableIntMap + : protected ItemSetTraits:: + template Map<_maps_bits::IterableIntMapNode >::Type { + public: + typedef typename ItemSetTraits:: + template Map<_maps_bits::IterableIntMapNode >::Type Parent; + + /// The key type + typedef K Key; + /// The value type + typedef int Value; + /// The graph type + typedef GR Graph; + + /// \brief Constructor of the map. + /// + /// Constructor of the map. It sets all values to -1. + explicit IterableIntMap(const Graph& graph) + : Parent(graph) {} + + /// \brief Constructor of the map with a given value. + /// + /// Constructor of the map with a given value. + explicit IterableIntMap(const Graph& graph, int value) + : Parent(graph, _maps_bits::IterableIntMapNode(value)) { + if (value >= 0) { + for (typename Parent::ItemIt it(*this); it != INVALID; ++it) { + lace(it); + } + } + } + + private: + + void unlace(const Key& key) { + typename Parent::Value& node = Parent::operator[](key); + if (node.value < 0) return; + if (node.prev != INVALID) { + Parent::operator[](node.prev).next = node.next; + } else { + _first[node.value] = node.next; + } + if (node.next != INVALID) { + Parent::operator[](node.next).prev = node.prev; + } + while (!_first.empty() && _first.back() == INVALID) { + _first.pop_back(); + } + } + + void lace(const Key& key) { + typename Parent::Value& node = Parent::operator[](key); + if (node.value < 0) return; + if (node.value >= int(_first.size())) { + _first.resize(node.value + 1, INVALID); + } + node.prev = INVALID; + node.next = _first[node.value]; + if (node.next != INVALID) { + Parent::operator[](node.next).prev = key; + } + _first[node.value] = key; + } + + public: + + /// Indicates that the map is reference map. + typedef True ReferenceMapTag; + + /// \brief Reference to the value of the map. + /// + /// This class is similar to the \c int type. It can + /// be converted to \c int and it has the same operators. + class Reference { + friend class IterableIntMap; + private: + Reference(IterableIntMap& map, const Key& key) + : _key(key), _map(map) {} + public: + + Reference& operator=(const Reference& value) { + _map.set(_key, static_cast(value)); + return *this; + } + + operator const int&() const { + return static_cast(_map)[_key]; + } + + Reference& operator=(int value) { + _map.set(_key, value); + return *this; + } + Reference& operator++() { + _map.set(_key, _map[_key] + 1); + return *this; + } + int operator++(int) { + int value = _map[_key]; + _map.set(_key, value + 1); + return value; + } + Reference& operator--() { + _map.set(_key, _map[_key] - 1); + return *this; + } + int operator--(int) { + int value = _map[_key]; + _map.set(_key, value - 1); + return value; + } + Reference& operator+=(int value) { + _map.set(_key, _map[_key] + value); + return *this; + } + Reference& operator-=(int value) { + _map.set(_key, _map[_key] - value); + return *this; + } + Reference& operator*=(int value) { + _map.set(_key, _map[_key] * value); + return *this; + } + Reference& operator/=(int value) { + _map.set(_key, _map[_key] / value); + return *this; + } + Reference& operator%=(int value) { + _map.set(_key, _map[_key] % value); + return *this; + } + Reference& operator&=(int value) { + _map.set(_key, _map[_key] & value); + return *this; + } + Reference& operator|=(int value) { + _map.set(_key, _map[_key] | value); + return *this; + } + Reference& operator^=(int value) { + _map.set(_key, _map[_key] ^ value); + return *this; + } + Reference& operator<<=(int value) { + _map.set(_key, _map[_key] << value); + return *this; + } + Reference& operator>>=(int value) { + _map.set(_key, _map[_key] >> value); + return *this; + } + + private: + Key _key; + IterableIntMap& _map; + }; + + /// The const reference type. + typedef const Value& ConstReference; + + /// \brief Gives back the maximal value plus one. + /// + /// Gives back the maximal value plus one. + int size() const { + return _first.size(); + } + + /// \brief Set operation of the map. + /// + /// Set operation of the map. + void set(const Key& key, const Value& value) { + unlace(key); + Parent::operator[](key).value = value; + lace(key); + } + + /// \brief Const subscript operator of the map. + /// + /// Const subscript operator of the map. + const Value& operator[](const Key& key) const { + return Parent::operator[](key).value; + } + + /// \brief Subscript operator of the map. + /// + /// Subscript operator of the map. + Reference operator[](const Key& key) { + return Reference(*this, key); + } + + /// \brief Iterator for the keys with the same value. + /// + /// Iterator for the keys with the same value. It works + /// like a graph item iterator, it can be converted to + /// the item type of the map, incremented with \c ++ operator, and + /// if the iterator leaves the last valid item, it will be equal to + /// \c INVALID. + class ItemIt : public Key { + public: + typedef Key Parent; + + /// \brief Invalid constructor \& conversion. + /// + /// This constructor initializes the iterator to be invalid. + /// \sa Invalid for more details. + ItemIt(Invalid) : Parent(INVALID), _map(0) {} + + /// \brief Creates an iterator with a value. + /// + /// Creates an iterator with a value. It iterates on the + /// keys mapped to the given value. + /// \param map The IterableIntMap. + /// \param value The value. + ItemIt(const IterableIntMap& map, int value) : _map(&map) { + if (value < 0 || value >= int(_map->_first.size())) { + Parent::operator=(INVALID); + } else { + Parent::operator=(_map->_first[value]); + } + } + + /// \brief Increment operator. + /// + /// Increment operator. + ItemIt& operator++() { + Parent::operator=(_map->IterableIntMap::Parent:: + operator[](static_cast(*this)).next); + return *this; + } + + private: + const IterableIntMap* _map; + }; + + protected: + + virtual void erase(const Key& key) { + unlace(key); + Parent::erase(key); + } + + virtual void erase(const std::vector& keys) { + for (int i = 0; i < int(keys.size()); ++i) { + unlace(keys[i]); + } + Parent::erase(keys); + } + + virtual void clear() { + _first.clear(); + Parent::clear(); + } + + private: + std::vector _first; + }; + + namespace _maps_bits { + template + struct IterableValueMapNode { + IterableValueMapNode(Value _value = Value()) : value(_value) {} + Item prev, next; + Value value; + }; + } + + /// \brief Dynamic iterable map for comparable values. + /// + /// This class provides a special graph map type which can store an + /// comparable value for graph items (\c Node, \c Arc or \c Edge). + /// For each value it is possible to iterate on the keys mapped to + /// the value. + /// + /// The map stores for each value a linked list with + /// the items which mapped to the value, and the values are stored + /// in balanced binary tree. The values of the map can be accessed + /// with stl compatible forward iterator. + /// + /// This type is not reference map, so it cannot be modified with + /// the subscript operator. + /// + /// \tparam GR The graph type. + /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or + /// \c GR::Edge). + /// \tparam V The value type of the map. It can be any comparable + /// value type. + /// + /// \see IterableBoolMap, IterableIntMap + /// \see CrossRefMap + template + class IterableValueMap + : protected ItemSetTraits:: + template Map<_maps_bits::IterableValueMapNode >::Type { + public: + typedef typename ItemSetTraits:: + template Map<_maps_bits::IterableValueMapNode >::Type Parent; + + /// The key type + typedef K Key; + /// The value type + typedef V Value; + /// The graph type + typedef GR Graph; + + public: + + /// \brief Constructor of the map with a given value. + /// + /// Constructor of the map with a given value. + explicit IterableValueMap(const Graph& graph, + const Value& value = Value()) + : Parent(graph, _maps_bits::IterableValueMapNode(value)) { + for (typename Parent::ItemIt it(*this); it != INVALID; ++it) { + lace(it); + } + } + + protected: + + void unlace(const Key& key) { + typename Parent::Value& node = Parent::operator[](key); + if (node.prev != INVALID) { + Parent::operator[](node.prev).next = node.next; + } else { + if (node.next != INVALID) { + _first[node.value] = node.next; + } else { + _first.erase(node.value); + } + } + if (node.next != INVALID) { + Parent::operator[](node.next).prev = node.prev; + } + } + + void lace(const Key& key) { + typename Parent::Value& node = Parent::operator[](key); + typename std::map::iterator it = _first.find(node.value); + if (it == _first.end()) { + node.prev = node.next = INVALID; + _first.insert(std::make_pair(node.value, key)); + } else { + node.prev = INVALID; + node.next = it->second; + if (node.next != INVALID) { + Parent::operator[](node.next).prev = key; + } + it->second = key; + } + } + + public: + + /// \brief Forward iterator for values. + /// + /// This iterator is an stl compatible forward + /// iterator on the values of the map. The values can + /// be accessed in the [beginValue, endValue) range. + class ValueIterator + : public std::iterator { + friend class IterableValueMap; + private: + ValueIterator(typename std::map::const_iterator _it) + : it(_it) {} + public: + + ValueIterator() {} + + ValueIterator& operator++() { ++it; return *this; } + ValueIterator operator++(int) { + ValueIterator tmp(*this); + operator++(); + return tmp; + } + + const Value& operator*() const { return it->first; } + const Value* operator->() const { return &(it->first); } + + bool operator==(ValueIterator jt) const { return it == jt.it; } + bool operator!=(ValueIterator jt) const { return it != jt.it; } + + private: + typename std::map::const_iterator it; + }; + + /// \brief Returns an iterator to the first value. + /// + /// Returns an stl compatible iterator to the + /// first value of the map. The values of the + /// map can be accessed in the [beginValue, endValue) + /// range. + ValueIterator beginValue() const { + return ValueIterator(_first.begin()); + } + + /// \brief Returns an iterator after the last value. + /// + /// Returns an stl compatible iterator after the + /// last value of the map. The values of the + /// map can be accessed in the [beginValue, endValue) + /// range. + ValueIterator endValue() const { + return ValueIterator(_first.end()); + } + + /// \brief Set operation of the map. + /// + /// Set operation of the map. + void set(const Key& key, const Value& value) { + unlace(key); + Parent::operator[](key).value = value; + lace(key); + } + + /// \brief Const subscript operator of the map. + /// + /// Const subscript operator of the map. + const Value& operator[](const Key& key) const { + return Parent::operator[](key).value; + } + + /// \brief Iterator for the keys with the same value. + /// + /// Iterator for the keys with the same value. It works + /// like a graph item iterator, it can be converted to + /// the item type of the map, incremented with \c ++ operator, and + /// if the iterator leaves the last valid item, it will be equal to + /// \c INVALID. + class ItemIt : public Key { + public: + typedef Key Parent; + + /// \brief Invalid constructor \& conversion. + /// + /// This constructor initializes the iterator to be invalid. + /// \sa Invalid for more details. + ItemIt(Invalid) : Parent(INVALID), _map(0) {} + + /// \brief Creates an iterator with a value. + /// + /// Creates an iterator with a value. It iterates on the + /// keys which have the given value. + /// \param map The IterableValueMap + /// \param value The value + ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) { + typename std::map::const_iterator it = + map._first.find(value); + if (it == map._first.end()) { + Parent::operator=(INVALID); + } else { + Parent::operator=(it->second); + } + } + + /// \brief Increment operator. + /// + /// Increment Operator. + ItemIt& operator++() { + Parent::operator=(_map->IterableValueMap::Parent:: + operator[](static_cast(*this)).next); + return *this; + } + + + private: + const IterableValueMap* _map; + }; + + protected: + + virtual void add(const Key& key) { + Parent::add(key); + unlace(key); + } + + virtual void add(const std::vector& keys) { + Parent::add(keys); + for (int i = 0; i < int(keys.size()); ++i) { + lace(keys[i]); + } + } + + virtual void erase(const Key& key) { + unlace(key); + Parent::erase(key); + } + + virtual void erase(const std::vector& keys) { + for (int i = 0; i < int(keys.size()); ++i) { + unlace(keys[i]); + } + Parent::erase(keys); + } + + virtual void build() { + Parent::build(); + for (typename Parent::ItemIt it(*this); it != INVALID; ++it) { + lace(it); + } + } + + virtual void clear() { + _first.clear(); + Parent::clear(); + } + + private: + std::map _first; + }; + /// \brief Map of the source nodes of arcs in a digraph. /// /// SourceMap provides access for the source node of each arc in a digraph, @@ -2480,7 +3395,7 @@ /// in constant time. On the other hand, the values are updated automatically /// whenever the digraph changes. /// - /// \warning Besides \c addNode() and \c addArc(), a digraph structure + /// \warning Besides \c addNode() and \c addArc(), a digraph structure /// may provide alternative ways to modify the digraph. /// The correct behavior of InDegMap is not guarantied if these additional /// features are used. For example the functions @@ -2496,7 +3411,7 @@ ::ItemNotifier::ObserverBase { public: - + /// The graph type of InDegMap typedef GR Graph; typedef GR Digraph; @@ -2610,7 +3525,7 @@ /// in constant time. On the other hand, the values are updated automatically /// whenever the digraph changes. /// - /// \warning Besides \c addNode() and \c addArc(), a digraph structure + /// \warning Besides \c addNode() and \c addArc(), a digraph structure /// may provide alternative ways to modify the digraph. /// The correct behavior of OutDegMap is not guarantied if these additional /// features are used. For example the functions diff --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 new file mode 100644 --- /dev/null +++ b/lemon/radix_heap.h @@ -0,0 +1,438 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2009 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#ifndef LEMON_RADIX_HEAP_H +#define LEMON_RADIX_HEAP_H + +///\ingroup heaps +///\file +///\brief Radix heap implementation. + +#include +#include + +namespace lemon { + + + /// \ingroup heaps + /// + /// \brief Radix heap data structure. + /// + /// This class implements the \e radix \e heap data structure. + /// It practically conforms to the \ref concepts::Heap "heap concept", + /// but it has some limitations due its special implementation. + /// The type of the priorities must be \c int and the priority of an + /// item cannot be decreased under the priority of the last removed item. + /// + /// \tparam IM A read-writable item map with \c int values, used + /// internally to handle the cross references. + template + class RadixHeap { + + public: + + /// Type of the item-int map. + typedef IM ItemIntMap; + /// Type of the priorities. + typedef int Prio; + /// Type of the items stored in the heap. + typedef typename ItemIntMap::Key Item; + + /// \brief Exception thrown by RadixHeap. + /// + /// This exception is thrown when an item is inserted into a + /// RadixHeap with a priority smaller than the last erased one. + /// \see RadixHeap + class PriorityUnderflowError : public Exception { + public: + virtual const char* what() const throw() { + return "lemon::RadixHeap::PriorityUnderflowError"; + } + }; + + /// \brief Type to represent the states of the items. + /// + /// Each item has a state associated to it. It can be "in heap", + /// "pre-heap" or "post-heap". The latter two are indifferent from the + /// heap's point of view, but may be useful to the user. + /// + /// The item-int map must be initialized in such way that it assigns + /// \c PRE_HEAP (-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: + + struct RadixItem { + int prev, next, box; + Item item; + int prio; + RadixItem(Item _item, int _prio) : item(_item), prio(_prio) {} + }; + + struct RadixBox { + int first; + int min, size; + RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {} + }; + + std::vector _data; + std::vector _boxes; + + ItemIntMap &_iim; + + public: + + /// \brief Constructor. + /// + /// Constructor. + /// \param map A map that assigns \c int values to the items. + /// It is used internally to handle the cross references. + /// The assigned value must be \c PRE_HEAP (-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(); + } + } + + /// \brief The number of items stored in the heap. + /// + /// This function returns the number of items stored in the heap. + int size() const { return _data.size(); } + + /// \brief Check if the heap is empty. + /// + /// This function returns \c true if the heap is empty. + bool empty() const { return _data.empty(); } + + /// \brief Make the heap empty. + /// + /// This functon makes the heap empty. + /// It does not change the cross reference map. If you want to reuse + /// a heap that is not surely empty, you should first clear it and + /// then you should set the cross reference map to \c PRE_HEAP + /// for each item. + /// \param minimum The minimum value of the heap. + /// \param capacity The capacity of the heap. + void clear(int minimum = 0, int capacity = 0) { + _data.clear(); _boxes.clear(); + _boxes.push_back(RadixBox(minimum, 1)); + _boxes.push_back(RadixBox(minimum + 1, 1)); + while (lower(_boxes.size() - 1, capacity + minimum - 1)) { + extend(); + } + } + + private: + + bool upper(int box, Prio pr) { + return pr < _boxes[box].min; + } + + bool lower(int box, Prio pr) { + return pr >= _boxes[box].min + _boxes[box].size; + } + + // Remove item from the box list + void remove(int index) { + if (_data[index].prev >= 0) { + _data[_data[index].prev].next = _data[index].next; + } else { + _boxes[_data[index].box].first = _data[index].next; + } + if (_data[index].next >= 0) { + _data[_data[index].next].prev = _data[index].prev; + } + } + + // Insert item into the box list + void insert(int box, int index) { + if (_boxes[box].first == -1) { + _boxes[box].first = index; + _data[index].next = _data[index].prev = -1; + } else { + _data[index].next = _boxes[box].first; + _data[_boxes[box].first].prev = index; + _data[index].prev = -1; + _boxes[box].first = index; + } + _data[index].box = box; + } + + // Add a new box to the box list + void extend() { + int min = _boxes.back().min + _boxes.back().size; + int bs = 2 * _boxes.back().size; + _boxes.push_back(RadixBox(min, bs)); + } + + // Move an item up into the proper box. + void bubbleUp(int index) { + if (!lower(_data[index].box, _data[index].prio)) return; + remove(index); + int box = findUp(_data[index].box, _data[index].prio); + insert(box, index); + } + + // Find up the proper box for the item with the given priority + int findUp(int start, int pr) { + while (lower(start, pr)) { + if (++start == int(_boxes.size())) { + extend(); + } + } + return start; + } + + // Move an item down into the proper box + void bubbleDown(int index) { + if (!upper(_data[index].box, _data[index].prio)) return; + remove(index); + int box = findDown(_data[index].box, _data[index].prio); + insert(box, index); + } + + // Find down the proper box for the item with the given priority + int findDown(int start, int pr) { + while (upper(start, pr)) { + if (--start < 0) throw PriorityUnderflowError(); + } + return start; + } + + // Find the first non-empty box + int findFirst() { + int first = 0; + while (_boxes[first].first == -1) ++first; + return first; + } + + // Gives back the minimum priority of the given box + int minValue(int box) { + int min = _data[_boxes[box].first].prio; + for (int k = _boxes[box].first; k != -1; k = _data[k].next) { + if (_data[k].prio < min) min = _data[k].prio; + } + return min; + } + + // Rearrange the items of the heap and make the first box non-empty + void moveDown() { + int box = findFirst(); + if (box == 0) return; + int min = minValue(box); + for (int i = 0; i <= box; ++i) { + _boxes[i].min = min; + min += _boxes[i].size; + } + int curr = _boxes[box].first, next; + while (curr != -1) { + next = _data[curr].next; + bubbleDown(curr); + curr = next; + } + } + + void relocateLast(int index) { + if (index != int(_data.size()) - 1) { + _data[index] = _data.back(); + if (_data[index].prev != -1) { + _data[_data[index].prev].next = index; + } else { + _boxes[_data[index].box].first = index; + } + if (_data[index].next != -1) { + _data[_data[index].next].prev = index; + } + _iim[_data[index].item] = index; + } + _data.pop_back(); + } + + public: + + /// \brief Insert an item into the heap with the given priority. + /// + /// This function inserts the given item into the heap with the + /// given priority. + /// \param i The item to insert. + /// \param p The priority of the item. + /// \pre \e i must not be stored in the heap. + /// \warning This method may throw an \c UnderFlowPriorityException. + void push(const Item &i, const Prio &p) { + int n = _data.size(); + _iim.set(i, n); + _data.push_back(RadixItem(i, p)); + while (lower(_boxes.size() - 1, p)) { + extend(); + } + int box = findDown(_boxes.size() - 1, p); + insert(box, n); + } + + /// \brief Return the item having minimum priority. + /// + /// This function returns the item having minimum priority. + /// \pre The heap must be non-empty. + Item top() const { + const_cast&>(*this).moveDown(); + return _data[_boxes[0].first].item; + } + + /// \brief The minimum priority. + /// + /// This function returns the minimum priority. + /// \pre The heap must be non-empty. + Prio prio() const { + const_cast&>(*this).moveDown(); + return _data[_boxes[0].first].prio; + } + + /// \brief Remove the item having minimum priority. + /// + /// This function removes the item having minimum priority. + /// \pre The heap must be non-empty. + void pop() { + moveDown(); + int index = _boxes[0].first; + _iim[_data[index].item] = POST_HEAP; + remove(index); + relocateLast(index); + } + + /// \brief Remove the given item from the heap. + /// + /// This function removes the given item from the heap if it is + /// already stored. + /// \param i The item to delete. + /// \pre \e i must be in the heap. + void erase(const Item &i) { + int index = _iim[i]; + _iim[i] = POST_HEAP; + remove(index); + relocateLast(index); + } + + /// \brief The priority of the given item. + /// + /// This function returns the priority of the given item. + /// \param i The item. + /// \pre \e i must be in the heap. + Prio operator[](const Item &i) const { + int idx = _iim[i]; + return _data[idx].prio; + } + + /// \brief Set the priority of an item or insert it, if it is + /// not stored in the heap. + /// + /// This method sets the priority of the given item if it is + /// already stored in the heap. Otherwise it inserts the given + /// item into the heap with the given priority. + /// \param i The item. + /// \param p The priority. + /// \pre \e i must be in the heap. + /// \warning This method may throw an \c UnderFlowPriorityException. + void set(const Item &i, const Prio &p) { + int idx = _iim[i]; + if( idx < 0 ) { + push(i, p); + } + else if( p >= _data[idx].prio ) { + _data[idx].prio = p; + bubbleUp(idx); + } else { + _data[idx].prio = p; + bubbleDown(idx); + } + } + + /// \brief Decrease the priority of an item to the given value. + /// + /// This function decreases the priority of an item to the given value. + /// \param i The item. + /// \param p The priority. + /// \pre \e i must be stored in the heap with priority at least \e p. + /// \warning This method may throw an \c UnderFlowPriorityException. + void decrease(const Item &i, const Prio &p) { + int idx = _iim[i]; + _data[idx].prio = p; + bubbleDown(idx); + } + + /// \brief Increase the priority of an item to the given value. + /// + /// This function increases the priority of an item to the given value. + /// \param i The item. + /// \param p The priority. + /// \pre \e i must be stored in the heap with priority at most \e p. + void increase(const Item &i, const Prio &p) { + int idx = _iim[i]; + _data[idx].prio = p; + bubbleUp(idx); + } + + /// \brief Return the state of an item. + /// + /// This method returns \c PRE_HEAP if the given item has never + /// been in the heap, \c IN_HEAP if it is in the heap at the moment, + /// and \c POST_HEAP otherwise. + /// In the latter case it is possible that the item will get back + /// to the heap again. + /// \param i The item. + State state(const Item &i) const { + int s = _iim[i]; + if( s >= 0 ) s = 0; + return State(s); + } + + /// \brief Set the state of an item in the heap. + /// + /// This function sets the state of the given item in the heap. + /// It can be used to manually clear the heap when it is important + /// to achive better time complexity. + /// \param i The item. + /// \param st The state. It should not be \c IN_HEAP. + void state(const Item& i, State st) { + switch (st) { + case POST_HEAP: + case PRE_HEAP: + if (state(i) == IN_HEAP) { + erase(i); + } + _iim[i] = st; + break; + case IN_HEAP: + break; + } + } + + }; // class RadixHeap + +} // namespace lemon + +#endif // LEMON_RADIX_HEAP_H 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,12 +25,18 @@ #include #include - #include #include #include #include +#include +#include +#include +#include +#include +#include +#include #include "test_tools.h" @@ -86,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(); } } @@ -109,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]); @@ -120,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) { @@ -141,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."); } } @@ -150,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."); } } @@ -172,6 +173,7 @@ node("source", source). run(); + // BinHeap { typedef BinHeap IntHeap; checkConcept, IntHeap>(); @@ -183,5 +185,92 @@ 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>(); + heapSortTest(); + heapIncreaseTest(); + + typedef FibHeap NodeHeap; + checkConcept, NodeHeap>(); + 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>(); + heapSortTest(); + heapIncreaseTest(); + + typedef RadixHeap NodeHeap; + checkConcept, NodeHeap>(); + 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>(); + heapSortTest(); + heapIncreaseTest(); + + 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 @@ -22,6 +22,7 @@ #include #include #include +#include #include "test_tools.h" @@ -349,5 +350,226 @@ check(v1[i++] == *it, "Something is wrong with LoggerBoolMap"); } + // CrossRefMap + { + typedef SmartDigraph Graph; + DIGRAPH_TYPEDEFS(Graph); + + checkConcept, + 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; + typedef SmartGraph::Node Item; + + typedef IterableBoolMap Ibm; + checkConcept, Ibm>(); + + const int num = 10; + Graph g; + std::vector items; + for (int i = 0; i < num; ++i) { + items.push_back(g.addNode()); + } + + Ibm map1(g, true); + int n = 0; + for (Ibm::TrueIt it(map1); it != INVALID; ++it) { + check(map1[static_cast(it)], "Wrong TrueIt"); + ++n; + } + check(n == num, "Wrong number"); + + n = 0; + for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) { + check(map1[static_cast(it)], "Wrong ItemIt for true"); + ++n; + } + check(n == num, "Wrong number"); + check(Ibm::FalseIt(map1) == INVALID, "Wrong FalseIt"); + check(Ibm::ItemIt(map1, false) == INVALID, "Wrong ItemIt for false"); + + map1[items[5]] = true; + + n = 0; + for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) { + check(map1[static_cast(it)], "Wrong ItemIt for true"); + ++n; + } + check(n == num, "Wrong number"); + + map1[items[num / 2]] = false; + check(map1[items[num / 2]] == false, "Wrong map value"); + + n = 0; + for (Ibm::TrueIt it(map1); it != INVALID; ++it) { + check(map1[static_cast(it)], "Wrong TrueIt for true"); + ++n; + } + check(n == num - 1, "Wrong number"); + + n = 0; + for (Ibm::FalseIt it(map1); it != INVALID; ++it) { + check(!map1[static_cast(it)], "Wrong FalseIt for true"); + ++n; + } + check(n == 1, "Wrong number"); + + map1[items[0]] = false; + check(map1[items[0]] == false, "Wrong map value"); + + map1[items[num - 1]] = false; + check(map1[items[num - 1]] == false, "Wrong map value"); + + n = 0; + for (Ibm::TrueIt it(map1); it != INVALID; ++it) { + check(map1[static_cast(it)], "Wrong TrueIt for true"); + ++n; + } + check(n == num - 3, "Wrong number"); + check(map1.trueNum() == num - 3, "Wrong number"); + + n = 0; + for (Ibm::FalseIt it(map1); it != INVALID; ++it) { + check(!map1[static_cast(it)], "Wrong FalseIt for true"); + ++n; + } + check(n == 3, "Wrong number"); + check(map1.falseNum() == 3, "Wrong number"); + } + + // Iterable int map + { + typedef SmartGraph Graph; + typedef SmartGraph::Node Item; + typedef IterableIntMap Iim; + + checkConcept, Iim>(); + + const int num = 10; + Graph g; + std::vector items; + for (int i = 0; i < num; ++i) { + items.push_back(g.addNode()); + } + + Iim map1(g); + check(map1.size() == 0, "Wrong size"); + + for (int i = 0; i < num; ++i) { + map1[items[i]] = i; + } + check(map1.size() == num, "Wrong size"); + + for (int i = 0; i < num; ++i) { + Iim::ItemIt it(map1, i); + check(static_cast(it) == items[i], "Wrong value"); + ++it; + check(static_cast(it) == INVALID, "Wrong value"); + } + + for (int i = 0; i < num; ++i) { + map1[items[i]] = i % 2; + } + check(map1.size() == 2, "Wrong size"); + + int n = 0; + for (Iim::ItemIt it(map1, 0); it != INVALID; ++it) { + check(map1[static_cast(it)] == 0, "Wrong value"); + ++n; + } + check(n == (num + 1) / 2, "Wrong number"); + + for (Iim::ItemIt it(map1, 1); it != INVALID; ++it) { + check(map1[static_cast(it)] == 1, "Wrong value"); + ++n; + } + check(n == num, "Wrong number"); + + } + + // Iterable value map + { + typedef SmartGraph Graph; + typedef SmartGraph::Node Item; + typedef IterableValueMap Ivm; + + checkConcept, Ivm>(); + + const int num = 10; + Graph g; + std::vector items; + for (int i = 0; i < num; ++i) { + items.push_back(g.addNode()); + } + + Ivm map1(g, 0.0); + check(distance(map1.beginValue(), map1.endValue()) == 1, "Wrong size"); + check(*map1.beginValue() == 0.0, "Wrong value"); + + for (int i = 0; i < num; ++i) { + map1.set(items[i], static_cast(i)); + } + check(distance(map1.beginValue(), map1.endValue()) == num, "Wrong size"); + + for (int i = 0; i < num; ++i) { + Ivm::ItemIt it(map1, static_cast(i)); + check(static_cast(it) == items[i], "Wrong value"); + ++it; + check(static_cast(it) == INVALID, "Wrong value"); + } + + for (Ivm::ValueIterator vit = map1.beginValue(); + vit != map1.endValue(); ++vit) { + check(map1[static_cast(Ivm::ItemIt(map1, *vit))] == *vit, + "Wrong ValueIterator"); + } + + for (int i = 0; i < num; ++i) { + map1.set(items[i], static_cast(i % 2)); + } + check(distance(map1.beginValue(), map1.endValue()) == 2, "Wrong size"); + + int n = 0; + for (Ivm::ItemIt it(map1, 0.0); it != INVALID; ++it) { + check(map1[static_cast(it)] == 0.0, "Wrong value"); + ++n; + } + check(n == (num + 1) / 2, "Wrong number"); + + for (Ivm::ItemIt it(map1, 1.0); it != INVALID; ++it) { + check(map1[static_cast(it)] == 1.0, "Wrong value"); + ++n; + } + check(n == num, "Wrong number"); + + } return 0; } 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"\