Index: doc/groups.dox =================================================================== --- doc/groups.dox (revision 762) +++ doc/groups.dox (revision 710) @@ -227,4 +227,12 @@ /** +@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 @@ -239,34 +247,5 @@ any kind of path structure. -\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. +\sa lemon::concepts::Path */ @@ -278,26 +257,4 @@ This group contains some data structures implemented in LEMON in order to make it easier to implement combinatorial algorithms. -*/ - -/** -@defgroup geomdat Geometric Data Structures -@ingroup auxdat -\brief Geometric data structures implemented in LEMON. - -This group contains geometric data structures implemented in LEMON. - - - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional - vector with the usual operations. - - \ref lemon::dim2::Box "dim2::Box" can be used to determine the - rectangular bounding box of a set of \ref lemon::dim2::Point - "dim2::Point"'s. -*/ - -/** -@defgroup matrices Matrices -@ingroup auxdat -\brief Two dimensional data storages implemented in LEMON. - -This group contains two dimensional data storages implemented in LEMON. */ @@ -342,13 +299,4 @@ /** -@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 @@ -428,5 +376,5 @@ \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: @@ -441,4 +389,28 @@ If you want to find minimum cut just between two distinict nodes, see the \ref max_flow "maximum flow problem". +*/ + +/** +@defgroup graph_properties Connectivity and Other Graph Properties +@ingroup algs +\brief Algorithms for discovering the graph properties + +This group contains the algorithms for discovering the graph properties +like connectivity, bipartiteness, euler property, simplicity etc. + +\image html edge_biconnected_components.png +\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth +*/ + +/** +@defgroup planar Planarity Embedding and Drawing +@ingroup algs +\brief Algorithms for planarity checking, embedding and drawing + +This group contains the algorithms for planarity checking, +embedding and drawing. + +\image html planar.png +\image latex planar.eps "Plane graph" width=\textwidth */ @@ -484,25 +456,19 @@ /** -@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 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 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 auxalg Auxiliary Algorithms +@ingroup algs +\brief Auxiliary algorithms implemented in LEMON. + +This group contains some algorithms implemented in LEMON +in order to make it easier to implement complex algorithms. */ @@ -514,13 +480,4 @@ This group contains the approximation and heuristic algorithms implemented in LEMON. -*/ - -/** -@defgroup auxalg Auxiliary Algorithms -@ingroup algs -\brief Auxiliary algorithms implemented in LEMON. - -This group contains some algorithms implemented in LEMON -in order to make it easier to implement complex algorithms. */ @@ -631,5 +588,5 @@ /** -@defgroup dimacs_group DIMACS Format +@defgroup dimacs_group DIMACS format @ingroup io_group \brief Read and write files in DIMACS format @@ -693,4 +650,16 @@ /** +\anchor demoprograms + +@defgroup demos Demo Programs + +Some demo programs are listed here. Their full source codes can be found in +the \c demo subdirectory of the source tree. + +In order to compile them, use the make demo or the +make check commands. +*/ + +/** @defgroup tools Standalone Utility Applications @@ -701,15 +670,3 @@ */ -/** -\anchor demoprograms - -@defgroup demos Demo Programs - -Some demo programs are listed here. Their full source codes can be found in -the \c demo subdirectory of the source tree. - -In order to compile them, use the make demo or the -make check commands. -*/ - } Index: lemon/Makefile.am =================================================================== --- lemon/Makefile.am (revision 755) +++ lemon/Makefile.am (revision 728) @@ -58,8 +58,6 @@ 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 \ @@ -81,5 +79,4 @@ lemon/euler.h \ lemon/fib_heap.h \ - lemon/fourary_heap.h \ lemon/full_graph.h \ lemon/glpk.h \ @@ -88,5 +85,4 @@ lemon/grid_graph.h \ lemon/hypercube_graph.h \ - lemon/kary_heap.h \ lemon/kruskal.h \ lemon/hao_orlin.h \ @@ -97,4 +93,5 @@ lemon/lp_base.h \ lemon/lp_skeleton.h \ + lemon/list_graph.h \ lemon/maps.h \ lemon/matching.h \ @@ -103,5 +100,4 @@ lemon/nauty_reader.h \ lemon/network_simplex.h \ - lemon/pairing_heap.h \ lemon/path.h \ lemon/preflow.h \ Index: mon/bellman_ford.h =================================================================== --- lemon/bellman_ford.h (revision 746) +++ (revision ) @@ -1,1100 +1,0 @@ -/* -*- 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 - Index: lemon/bfs.h =================================================================== --- lemon/bfs.h (revision 764) +++ lemon/bfs.h (revision 525) @@ -48,5 +48,5 @@ ///The type of the map that stores the predecessor ///arcs of the shortest paths. - ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap PredMap; ///Instantiates a \c PredMap. @@ -63,6 +63,5 @@ ///The type of the map that indicates which nodes are processed. - ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. - ///By default it is a NullMap. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. typedef NullMap ProcessedMap; ///Instantiates a \c ProcessedMap. @@ -83,5 +82,5 @@ ///The type of the map that indicates which nodes are reached. - ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; ///Instantiates a \c ReachedMap. @@ -98,5 +97,5 @@ ///The type of the map that stores the distances of the nodes. - ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap DistMap; ///Instantiates a \c DistMap. @@ -227,5 +226,5 @@ ///\ref named-templ-param "Named parameter" for setting ///\c PredMap type. - ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. template struct SetPredMap : public Bfs< Digraph, SetPredMapTraits > { @@ -247,5 +246,5 @@ ///\ref named-templ-param "Named parameter" for setting ///\c DistMap type. - ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. template struct SetDistMap : public Bfs< Digraph, SetDistMapTraits > { @@ -267,5 +266,5 @@ ///\ref named-templ-param "Named parameter" for setting ///\c ReachedMap type. - ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. template struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits > { @@ -287,5 +286,5 @@ ///\ref named-templ-param "Named parameter" for setting ///\c ProcessedMap type. - ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. template struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits > { @@ -415,6 +414,6 @@ ///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 better control on the execution, you have to call - ///\ref init() first, then you can add several source nodes with + ///If you need more control on the execution, first you have to call + ///\ref init(), 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. @@ -739,7 +738,7 @@ ///@{ - ///The shortest path to the given node. - - ///Returns the shortest path to the given node from the root(s). + ///The shortest path to a node. + + ///Returns the shortest path to a node. /// ///\warning \c t should be reached from the root(s). @@ -749,7 +748,7 @@ Path path(Node t) const { return Path(*G, *_pred, t); } - ///The distance of the given node from the root(s). - - ///Returns the distance of the given node from the root(s). + ///The distance of a node from the root(s). + + ///Returns the distance of a node from the root(s). /// ///\warning If node \c v is not reached from the root(s), then @@ -760,7 +759,6 @@ int dist(Node v) const { return (*_dist)[v]; } - ///\brief Returns the 'previous arc' of the shortest path tree for - ///the given node. - /// + ///Returns the 'previous arc' of the shortest path tree for a node. + ///This function returns the 'previous arc' of the shortest path ///tree for the node \c v, i.e. it returns the last arc of a @@ -769,5 +767,5 @@ /// ///The shortest path tree used here is equal to the shortest path - ///tree used in \ref predNode() and \ref predMap(). + ///tree used in \ref predNode(). /// ///\pre Either \ref run(Node) "run()" or \ref init() @@ -775,14 +773,13 @@ Arc predArc(Node v) const { return (*_pred)[v];} - ///\brief Returns the 'previous node' of the shortest path tree for - ///the given node. - /// + ///Returns the 'previous node' of the shortest path tree for a node. + ///This function returns the 'previous node' of the shortest path ///tree for the node \c v, i.e. it returns the last but one node - ///of a shortest path from a root to \c v. It is \c INVALID + ///from 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 \ref predMap(). + ///tree used in \ref predArc(). /// ///\pre Either \ref run(Node) "run()" or \ref init() @@ -805,5 +802,5 @@ /// ///Returns a const reference to the node map that stores the predecessor - ///arcs, which form the shortest path tree (forest). + ///arcs, which form the shortest path tree. /// ///\pre Either \ref run(Node) "run()" or \ref init() @@ -811,5 +808,5 @@ const PredMap &predMap() const { return *_pred;} - ///Checks if the given node is reached from the root(s). + ///Checks if a node is reached from the root(s). ///Returns \c true if \c v is reached from the root(s). @@ -837,5 +834,5 @@ ///The type of the map that stores the predecessor ///arcs of the shortest paths. - ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap PredMap; ///Instantiates a PredMap. @@ -852,5 +849,5 @@ ///The type of the map that indicates which nodes are processed. - ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. typedef NullMap ProcessedMap; @@ -872,5 +869,5 @@ ///The type of the map that indicates which nodes are reached. - ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; ///Instantiates a ReachedMap. @@ -887,5 +884,5 @@ ///The type of the map that stores the distances of the nodes. - ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap DistMap; ///Instantiates a DistMap. @@ -902,5 +899,5 @@ ///The type of the shortest paths. - ///It must conform to the \ref concepts::Path "Path" concept. + ///It must meet the \ref concepts::Path "Path" concept. typedef lemon::Path Path; }; @@ -908,6 +905,10 @@ /// Default traits class used by BfsWizard - /// Default traits class used by BfsWizard. - /// \tparam GR The type of the digraph. + /// To make it easier to use Bfs algorithm + /// we have created a wizard class. + /// This \ref BfsWizard class needs default traits, + /// as well as the \ref Bfs class. + /// The \ref BfsWizardBase is a class to be the default traits of the + /// \ref BfsWizard class. template class BfsWizardBase : public BfsWizardDefaultTraits @@ -937,5 +938,5 @@ /// Constructor. - /// This constructor does not require parameters, it initiates + /// This constructor does not require parameters, therefore it initiates /// all of the attributes to \c 0. BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), @@ -967,4 +968,5 @@ typedef TR Base; + ///The type of the digraph the algorithm runs on. typedef typename TR::Digraph Digraph; @@ -974,8 +976,14 @@ typedef typename Digraph::OutArcIt OutArcIt; + ///\brief The type of the map that stores the predecessor + ///arcs of the shortest paths. typedef typename TR::PredMap PredMap; + ///\brief The type of the map that stores the distances of the nodes. typedef typename TR::DistMap DistMap; + ///\brief The type of the map that indicates which nodes are reached. typedef typename TR::ReachedMap ReachedMap; + ///\brief The type of the map that indicates which nodes are processed. typedef typename TR::ProcessedMap ProcessedMap; + ///The type of the shortest paths typedef typename TR::Path Path; @@ -1060,10 +1068,9 @@ SetPredMapBase(const TR &b) : TR(b) {} }; - - ///\brief \ref named-templ-param "Named parameter" for setting - ///the predecessor map. - /// - ///\ref named-templ-param "Named parameter" function for setting - ///the map that stores the predecessor arcs of the nodes. + ///\brief \ref named-func-param "Named parameter" + ///for setting PredMap object. + /// + ///\ref named-func-param "Named parameter" + ///for setting PredMap object. template BfsWizard > predMap(const T &t) @@ -1079,10 +1086,9 @@ SetReachedMapBase(const TR &b) : TR(b) {} }; - - ///\brief \ref named-templ-param "Named parameter" for setting - ///the reached map. - /// - ///\ref named-templ-param "Named parameter" function for setting - ///the map that indicates which nodes are reached. + ///\brief \ref named-func-param "Named parameter" + ///for setting ReachedMap object. + /// + /// \ref named-func-param "Named parameter" + ///for setting ReachedMap object. template BfsWizard > reachedMap(const T &t) @@ -1098,11 +1104,9 @@ SetDistMapBase(const TR &b) : TR(b) {} }; - - ///\brief \ref named-templ-param "Named parameter" for setting - ///the distance map. - /// - ///\ref named-templ-param "Named parameter" function for setting - ///the map that stores the distances of the nodes calculated - ///by the algorithm. + ///\brief \ref named-func-param "Named parameter" + ///for setting DistMap object. + /// + /// \ref named-func-param "Named parameter" + ///for setting DistMap object. template BfsWizard > distMap(const T &t) @@ -1118,10 +1122,9 @@ SetProcessedMapBase(const TR &b) : TR(b) {} }; - - ///\brief \ref named-func-param "Named parameter" for setting - ///the processed map. - /// - ///\ref named-templ-param "Named parameter" function for setting - ///the map that indicates which nodes are processed. + ///\brief \ref named-func-param "Named parameter" + ///for setting ProcessedMap object. + /// + /// \ref named-func-param "Named parameter" + ///for setting ProcessedMap object. template BfsWizard > processedMap(const T &t) @@ -1262,5 +1265,5 @@ /// /// The type of the map that indicates which nodes are reached. - /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; @@ -1423,6 +1426,6 @@ /// 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 better control on the execution, you have to call - /// \ref init() first, then you can add several source nodes with + /// If you need more control on the execution, first you have to call + /// \ref init(), 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. @@ -1733,5 +1736,5 @@ ///@{ - /// \brief Checks if the given node is reached from the root(s). + /// \brief Checks if a node is reached from the root(s). /// /// Returns \c true if \c v is reached from the root(s). Index: lemon/bin_heap.h =================================================================== --- lemon/bin_heap.h (revision 758) +++ lemon/bin_heap.h (revision 730) @@ -20,7 +20,7 @@ #define LEMON_BIN_HEAP_H -///\ingroup heaps +///\ingroup auxdat ///\file -///\brief Binary heap implementation. +///\brief Binary Heap implementation. #include @@ -30,39 +30,43 @@ namespace lemon { - /// \ingroup heaps - /// - /// \brief Binary heap data structure. - /// - /// 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 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 + ///\ingroup auxdat + /// + ///\brief A Binary Heap implementation. + /// + ///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 CMP specifies the ordering of the priorities. + ///In a heap one can change the priority of an item, add or erase an + ///item, etc. + /// + ///\tparam PR Type of the priority of the items. + ///\tparam IM A read and writable item map with int values, used internally + ///to handle the cross references. + ///\tparam CMP A functor class for the ordering of the priorities. + ///The default is \c std::less. + /// + ///\sa FibHeap + ///\sa Dijkstra template > -#endif class BinHeap { + public: - - /// Type of the item-int map. + ///\e typedef IM ItemIntMap; - /// Type of the priorities. + ///\e typedef PR Prio; - /// Type of the items stored in the heap. + ///\e typedef typename ItemIntMap::Key Item; - /// Type of the item-priority pairs. + ///\e typedef std::pair Pair; - /// Functor type for comparing the priorities. + ///\e 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 + /// \brief Type to represent the items states. + /// + /// 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 /// heap's point of view, but may be useful to the user. /// @@ -81,41 +85,40 @@ 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. + /// \brief The 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. explicit BinHeap(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. + /// \brief The 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. BinHeap(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. + /// The number of items stored in the heap. + /// + /// \brief Returns the number of items stored in the heap. int size() const { return _data.size(); } - /// \brief Check if the heap is empty. - /// - /// This function returns \c true if the heap is empty. + /// \brief Checks if the heap stores no items. + /// + /// Returns \c true if and only if the heap stores no items. 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. + /// \brief Make empty this heap. + /// + /// 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. void clear() { _data.clear(); @@ -125,10 +128,10 @@ static int parent(int i) { return (i-1)/2; } - static int secondChild(int i) { return 2*i+2; } + static int second_child(int i) { return 2*i+2; } bool less(const Pair &p1, const Pair &p2) const { return _comp(p1.second, p2.second); } - int bubbleUp(int hole, Pair p) { + int bubble_up(int hole, Pair p) { int par = parent(hole); while( hole>0 && less(p,_data[par]) ) { @@ -141,6 +144,6 @@ } - int bubbleDown(int hole, Pair p, int length) { - int child = secondChild(hole); + int bubble_down(int hole, Pair p, int length) { + int child = second_child(hole); while(child < length) { if( less(_data[child-1], _data[child]) ) { @@ -151,5 +154,5 @@ move(_data[child], hole); hole = child; - child = secondChild(hole); + child = second_child(hole); } child--; @@ -169,45 +172,42 @@ 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. + /// Adds \c p.first to the heap with priority \c p.second. /// \param p The pair to insert. - /// \pre \c p.first must not be stored in the heap. void push(const Pair &p) { int n = _data.size(); _data.resize(n+1); - bubbleUp(n, p); - } - - /// \brief Insert an item into the heap with the given priority. - /// - /// This function inserts the given item into the heap with the - /// given priority. + bubble_up(n, p); + } + + /// \brief Insert an item into the heap with the given heap. + /// + /// Adds \c i to the heap with priority \c p. /// \param i The item to insert. /// \param p The priority of the item. - /// \pre \e i must not be stored in the heap. void push(const Item &i, const Prio &p) { push(Pair(i,p)); } - /// \brief Return the item having minimum priority. - /// - /// This function returns the item having minimum priority. - /// \pre The heap must be non-empty. + /// \brief Returns the item with minimum priority relative to \c Compare. + /// + /// This method returns the item with minimum priority relative to \c + /// Compare. + /// \pre The heap must be nonempty. Item top() const { return _data.first; } - /// \brief The minimum priority. - /// - /// This function returns the minimum priority. - /// \pre The heap must be non-empty. + /// \brief Returns the minimum priority relative to \c Compare. + /// + /// It returns the minimum priority relative to \c Compare. + /// \pre The heap must be nonempty. Prio prio() const { return _data.second; } - /// \brief Remove the item having minimum priority. - /// - /// This function removes the item having minimum priority. + /// \brief Deletes the item with minimum priority relative to \c Compare. + /// + /// This method deletes the item with minimum priority relative to \c + /// Compare from the heap. /// \pre The heap must be non-empty. void pop() { @@ -215,15 +215,14 @@ _iim.set(_data.first, POST_HEAP); if (n > 0) { - bubbleDown(0, _data[n], n); + bubble_down(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. + /// \brief Deletes \c i 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. void erase(const Item &i) { int h = _iim[i]; @@ -231,6 +230,6 @@ _iim.set(_data[h].first, POST_HEAP); if( h < n ) { - if ( bubbleUp(h, _data[n]) == h) { - bubbleDown(h, _data[n], n); + if ( bubble_up(h, _data[n]) == h) { + bubble_down(h, _data[n], n); } } @@ -238,9 +237,10 @@ } - /// \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. + + /// \brief Returns the priority of \c i. + /// + /// This function returns the priority of item \c i. + /// \param i The item. + /// \pre \c i must be in the heap. Prio operator[](const Item &i) const { int idx = _iim[i]; @@ -248,10 +248,9 @@ } - /// \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. + /// \brief \c i gets to the heap with priority \c p independently + /// if \c i was already there. + /// + /// 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. /// \param i The item. /// \param p The priority. @@ -262,40 +261,42 @@ } else if( _comp(p, _data[idx].second) ) { - bubbleUp(idx, Pair(i,p)); + bubble_up(idx, Pair(i,p)); } else { - bubbleDown(idx, Pair(i,p), _data.size()); - } - } - - /// \brief Decrease the priority of an item to the given value. - /// - /// This function decreases the priority of an item to the given value. + bubble_down(idx, Pair(i,p), _data.size()); + } + } + + /// \brief Decreases the priority of \c i to \c p. + /// + /// This method decreases the priority of item \c i to \c p. /// \param i The item. /// \param p The priority. - /// \pre \e i must be stored in the heap with priority at least \e p. + /// \pre \c i must be stored in the heap with priority at least \c + /// p relative to \c Compare. void decrease(const Item &i, const Prio &p) { int idx = _iim[i]; - bubbleUp(idx, Pair(i,p)); - } - - /// \brief Increase the priority of an item to the given value. - /// - /// This function increases the priority of an item to the given value. + bubble_up(idx, Pair(i,p)); + } + + /// \brief Increases the priority of \c i to \c p. + /// + /// This method sets the priority of item \c i to \c p. /// \param i The item. /// \param p The priority. - /// \pre \e i must be stored in the heap with priority at most \e p. + /// \pre \c i must be stored in the heap with priority at most \c + /// p relative to \c Compare. void increase(const Item &i, const Prio &p) { int idx = _iim[i]; - bubbleDown(idx, Pair(i,p), _data.size()); - } - - /// \brief Return the state of an item. - /// - /// This method returns \c PRE_HEAP if the given item has never - /// been in the heap, \c IN_HEAP if it is in the heap at the moment, - /// and \c POST_HEAP otherwise. - /// In the latter case it is possible that the item will get back - /// to the heap again. + bubble_down(idx, Pair(i,p), _data.size()); + } + + /// \brief Returns if \c item is in, has already been in, or has + /// never been in the heap. + /// + /// 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. /// \param i The item. State state(const Item &i) const { @@ -306,9 +307,9 @@ } - /// \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. + /// \brief Sets the state of the \c 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. /// \param i The item. /// \param st The state. It should not be \c IN_HEAP. @@ -327,11 +328,10 @@ } - /// \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. + /// \brief Replaces 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. void replace(const Item& i, const Item& j) { int idx = _iim[i]; Index: mon/binom_heap.h =================================================================== --- lemon/binom_heap.h (revision 754) +++ (revision ) @@ -1,445 +1,0 @@ -/* -*- 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 - Index: lemon/bits/edge_set_extender.h =================================================================== --- lemon/bits/edge_set_extender.h (revision 732) +++ lemon/bits/edge_set_extender.h (revision 664) @@ -538,5 +538,5 @@ public: - explicit ArcMap(const Graph& _g) + ArcMap(const Graph& _g) : Parent(_g) {} ArcMap(const Graph& _g, const _Value& _v) @@ -562,5 +562,5 @@ public: - explicit EdgeMap(const Graph& _g) + EdgeMap(const Graph& _g) : Parent(_g) {} Index: lemon/bits/graph_extender.h =================================================================== --- lemon/bits/graph_extender.h (revision 732) +++ lemon/bits/graph_extender.h (revision 664) @@ -605,5 +605,5 @@ public: - explicit NodeMap(const Graph& graph) + NodeMap(const Graph& graph) : Parent(graph) {} NodeMap(const Graph& graph, const _Value& value) @@ -629,5 +629,5 @@ public: - explicit ArcMap(const Graph& graph) + ArcMap(const Graph& graph) : Parent(graph) {} ArcMap(const Graph& graph, const _Value& value) @@ -653,5 +653,5 @@ public: - explicit EdgeMap(const Graph& graph) + EdgeMap(const Graph& graph) : Parent(graph) {} Index: lemon/bits/map_extender.h =================================================================== --- lemon/bits/map_extender.h (revision 664) +++ lemon/bits/map_extender.h (revision 765) @@ -50,4 +50,6 @@ typedef typename Parent::ConstReference ConstReference; + typedef typename Parent::ReferenceMapTag ReferenceMapTag; + class MapIt; class ConstMapIt; @@ -192,4 +194,6 @@ typedef typename Parent::ConstReference ConstReference; + typedef typename Parent::ReferenceMapTag ReferenceMapTag; + class MapIt; class ConstMapIt; Index: lemon/bucket_heap.h =================================================================== --- lemon/bucket_heap.h (revision 758) +++ lemon/bucket_heap.h (revision 730) @@ -20,7 +20,7 @@ #define LEMON_BUCKET_HEAP_H -///\ingroup heaps +///\ingroup auxdat ///\file -///\brief Bucket heap implementation. +///\brief Bucket Heap implementation. #include @@ -54,39 +54,33 @@ } - /// \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 + /// \ingroup auxdat + /// + /// \brief A Bucket Heap implementation. + /// + /// This class implements the \e bucket \e heap data structure. A \e heap + /// is a data structure for storing items with specified values called \e + /// priorities in such a way that finding the item with minimum priority is + /// efficient. The bucket heap is very simple implementation, it can store + /// only integer priorities and it stores for each priority in the + /// \f$[0..C) \f$ range a list of items. So it should be used only when + /// the priorities are small. It is not intended to use as dijkstra heap. + /// + /// \param IM A read and write Item int map, used internally + /// to handle the cross references. + /// \param MIN If the given parameter is false then instead of the + /// minimum value the maximum can be retrivied with the top() and + /// prio() member functions. template class BucketHeap { public: - - /// Type of the item-int map. + /// \e + typedef typename IM::Key Item; + /// \e + typedef int Prio; + /// \e + typedef std::pair Pair; + /// \e 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: @@ -96,8 +90,8 @@ 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 + /// \brief Type to represent the items states. + /// + /// 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 /// heap's point of view, but may be useful to the user. /// @@ -111,30 +105,28 @@ 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. + /// \brief The 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. 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. + /// The number of items stored in the heap. + /// + /// \brief Returns the number of items stored in the heap. int size() const { return _data.size(); } - /// \brief Check if the heap is empty. - /// - /// This function returns \c true if the heap is empty. + /// \brief Checks if the heap stores no items. + /// + /// Returns \c true if and only if the heap stores no items. 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. + /// \brief Make empty this heap. + /// + /// Make empty this heap. It does not change the cross reference + /// map. If you want to reuse a heap what is not surely empty you + /// should first clear the heap and after that you should set the + /// cross reference map for each item to \c PRE_HEAP. void clear() { _data.clear(); _first.clear(); _minimum = 0; @@ -143,5 +135,5 @@ private: - void relocateLast(int idx) { + void relocate_last(int idx) { if (idx + 1 < int(_data.size())) { _data[idx] = _data.back(); @@ -183,11 +175,8 @@ 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. + /// Adds \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); @@ -196,9 +185,7 @@ /// \brief Insert an item into the heap with the given priority. /// - /// This function inserts the given item into the heap with the - /// given priority. + /// Adds \c i to the heap with priority \c p. /// \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(); @@ -211,8 +198,8 @@ } - /// \brief Return the item having minimum priority. - /// - /// This function returns the item having minimum priority. - /// \pre The heap must be non-empty. + /// \brief Returns the item with minimum priority. + /// + /// This method returns the item with minimum priority. + /// \pre The heap must be nonempty. Item top() const { while (_first[_minimum] == -1) { @@ -222,8 +209,8 @@ } - /// \brief The minimum priority. - /// - /// This function returns the minimum priority. - /// \pre The heap must be non-empty. + /// \brief Returns the minimum priority. + /// + /// It returns the minimum priority. + /// \pre The heap must be nonempty. Prio prio() const { while (_first[_minimum] == -1) { @@ -233,7 +220,7 @@ } - /// \brief Remove the item having minimum priority. - /// - /// This function removes the item having minimum priority. + /// \brief Deletes the item with minimum priority. + /// + /// This method deletes the item with minimum priority from the heap. /// \pre The heap must be non-empty. void pop() { @@ -244,25 +231,25 @@ _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. + relocate_last(idx); + } + + /// \brief Deletes \c i from the heap. + /// + /// This method deletes item \c i from the heap, if \c i was + /// already stored in the heap. + /// \param i The item to erase. 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. + relocate_last(idx); + } + + + /// \brief Returns the priority of \c i. + /// + /// This function returns the priority of item \c i. + /// \pre \c i must be in the heap. + /// \param i The item. Prio operator[](const Item &i) const { int idx = _iim[i]; @@ -270,10 +257,9 @@ } - /// \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. + /// \brief \c i gets to the heap with priority \c p independently + /// if \c i was already there. + /// + /// 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. /// \param i The item. /// \param p The priority. @@ -289,10 +275,11 @@ } - /// \brief Decrease the priority of an item to the given value. - /// - /// This function decreases the priority of an item to the given value. + /// \brief Decreases the priority of \c i to \c p. + /// + /// This method decreases the priority of item \c i to \c p. + /// \pre \c i must be stored in the heap with priority at least \c + /// p relative to \c Compare. /// \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]; @@ -305,10 +292,11 @@ } - /// \brief Increase the priority of an item to the given value. - /// - /// This function increases the priority of an item to the given value. + /// \brief Increases the priority of \c i to \c p. + /// + /// This method sets the priority of item \c i to \c p. + /// \pre \c i must be stored in the heap with priority at most \c + /// p relative to \c Compare. /// \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]; @@ -318,11 +306,11 @@ } - /// \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. + /// \brief Returns if \c item is in, has already been in, or has + /// never been in the heap. + /// + /// 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. /// \param i The item. State state(const Item &i) const { @@ -332,9 +320,9 @@ } - /// \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. + /// \brief Sets the state of the \c 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. /// \param i The item. /// \param st The state. It should not be \c IN_HEAP. @@ -372,27 +360,21 @@ }; // class BucketHeap - /// \ingroup heaps - /// - /// \brief Simplified bucket heap data structure. + /// \ingroup auxdat + /// + /// \brief A Simplified Bucket Heap implementation. /// /// 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. + /// structure. It does not provide some functionality but it faster + /// and simplier data structure than the BucketHeap. The main + /// difference is that the BucketHeap stores for every key a double + /// linked list while this class stores just simple lists. In the + /// other way it does not support erasing each elements just the + /// minimal and it does not supports key increasing, decreasing. + /// + /// \param IM A read and write Item int map, used internally + /// to handle the cross references. + /// \param MIN If the given parameter is false then instead of the + /// minimum value the maximum can be retrivied with the top() and + /// prio() member functions. /// /// \sa BucketHeap @@ -401,13 +383,8 @@ public: - - /// Type of the item-int map. + typedef typename IM::Key Item; + typedef int Prio; + typedef std::pair Pair; 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: @@ -417,8 +394,8 @@ 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 + /// \brief Type to represent the items states. + /// + /// 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 /// heap's point of view, but may be useful to the user. /// @@ -433,30 +410,29 @@ 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. + /// \brief The 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. 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. + /// \brief Returns the number of items stored in the heap. + /// + /// 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. + /// \brief Checks if the heap stores no items. + /// + /// Returns \c true if and only if the heap stores no items. 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. + /// \brief Make empty this heap. + /// + /// Make empty this heap. It does not change the cross reference + /// map. If you want to reuse a heap what is not surely empty you + /// should first clear the heap and after that you should set the + /// cross reference map for each item to \c PRE_HEAP. void clear() { _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0; @@ -465,8 +441,6 @@ /// \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. + /// Adds \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); @@ -475,9 +449,7 @@ /// \brief Insert an item into the heap with the given priority. /// - /// This function inserts the given item into the heap with the - /// given priority. + /// Adds \c i to the heap with priority \c p. /// \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; @@ -500,8 +472,8 @@ } - /// \brief Return the item having minimum priority. - /// - /// This function returns the item having minimum priority. - /// \pre The heap must be non-empty. + /// \brief Returns the item with minimum priority. + /// + /// This method returns the item with minimum priority. + /// \pre The heap must be nonempty. Item top() const { while (_first[_minimum] == -1) { @@ -511,8 +483,8 @@ } - /// \brief The minimum priority. - /// - /// This function returns the minimum priority. - /// \pre The heap must be non-empty. + /// \brief Returns the minimum priority. + /// + /// It returns the minimum priority. + /// \pre The heap must be nonempty. Prio prio() const { while (_first[_minimum] == -1) { @@ -522,7 +494,7 @@ } - /// \brief Remove the item having minimum priority. - /// - /// This function removes the item having minimum priority. + /// \brief Deletes the item with minimum priority. + /// + /// This method deletes the item with minimum priority from the heap. /// \pre The heap must be non-empty. void pop() { @@ -538,13 +510,14 @@ } - /// \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. + /// \brief Returns the priority of \c i. + /// + /// This function returns the priority of item \c i. + /// \warning This operator is not a constant time function + /// because it scans the whole data structure to find the proper + /// value. + /// \pre \c i must be in the heap. + /// \param i The item. Prio operator[](const Item &i) const { - for (int k = 0; k < int(_first.size()); ++k) { + for (int k = 0; k < _first.size(); ++k) { int idx = _first[k]; while (idx != -1) { @@ -558,11 +531,11 @@ } - /// \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. + /// \brief Returns if \c item is in, has already been in, or has + /// never been in the heap. + /// + /// 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. /// \param i The item. State state(const Item &i) const { Index: lemon/circulation.h =================================================================== --- lemon/circulation.h (revision 762) +++ lemon/circulation.h (revision 688) @@ -73,9 +73,5 @@ /// 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. @@ -92,10 +88,7 @@ /// The elevator type used by the algorithm. /// - /// \sa Elevator, LinkedElevator -#ifdef DOXYGEN - typedef lemon::Elevator Elevator; -#else + /// \sa Elevator + /// \sa LinkedElevator typedef lemon::Elevator Elevator; -#endif /// \brief Instantiates an Elevator. @@ -458,9 +451,8 @@ } - /// \brief Sets the tolerance used by the algorithm. - /// - /// Sets the tolerance object used by the algorithm. - /// \return (*this) - Circulation& tolerance(const Tolerance& tolerance) { + /// \brief Sets the tolerance used by algorithm. + /// + /// Sets the tolerance used by algorithm. + Circulation& tolerance(const Tolerance& tolerance) const { _tol = tolerance; return *this; @@ -469,14 +461,13 @@ /// \brief Returns a const reference to the tolerance. /// - /// Returns a const reference to the tolerance object used by - /// the algorithm. + /// Returns a const reference to the tolerance. const Tolerance& tolerance() const { - return _tol; + return tolerance; } /// \name Execution Control /// The simplest way to execute the algorithm is to call \ref run().\n - /// If you need better control on the initial solution or the execution, - /// you have to call one of the \ref init() functions first, then + /// If you need more control on the initial solution or the execution, + /// first you have to call one of the \ref init() functions, then /// the \ref start() function. Index: lemon/concepts/heap.h =================================================================== --- lemon/concepts/heap.h (revision 757) +++ lemon/concepts/heap.h (revision 631) @@ -17,11 +17,11 @@ */ -#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 @@ -36,25 +36,19 @@ /// \brief The heap concept. /// - /// 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. + /// 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. /// - /// 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 + /// \tparam PR Type of the priority of the items. + /// \tparam IM A read and writable item map with int values, used /// internally to handle the cross references. - /// \tparam CMP A functor class for comparing the priorities. + /// \tparam Comp A functor class for the ordering of the priorities. /// The default is \c std::less. #ifdef DOXYGEN - template + template > #else - template > + template #endif class Heap { @@ -71,6 +65,7 @@ /// /// 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. + /// "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. /// /// The item-int map must be initialized in such way that it assigns @@ -78,58 +73,42 @@ 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 Constructor. - /// - /// Constructor. + /// \brief The constructor. + /// + /// The 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. + /// \c PRE_HEAP (-1) for every 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. /// - /// This function returns the number of items stored in the heap. + /// Returns the number of items stored in the heap. int size() const { return 0; } - /// \brief Check if the heap is empty. - /// - /// This function returns \c true if the heap is empty. + /// \brief Checks if the heap is empty. + /// + /// Returns \c true if the heap is empty. bool empty() const { return false; } - /// \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() {} - - /// \brief Insert an item into the heap with the given priority. - /// - /// This function inserts the given item into the heap with the - /// given priority. + /// \brief Makes the heap empty. + /// + /// Makes the heap empty. + void clear(); + + /// \brief Inserts an item into the heap with the given priority. + /// + /// 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 Return the item having minimum priority. - /// - /// This function returns the item having minimum priority. + /// \brief Returns the item having minimum priority. + /// + /// Returns the item having minimum priority. /// \pre The heap must be non-empty. Item top() const {} @@ -137,35 +116,33 @@ /// \brief The minimum priority. /// - /// This function returns the minimum priority. + /// Returns the minimum priority. /// \pre The heap must be non-empty. Prio prio() const {} - /// \brief Remove the item having minimum priority. - /// - /// This function removes the item having minimum priority. + /// \brief Removes the item having minimum priority. + /// + /// Removes the item having minimum priority. /// \pre The heap must be non-empty. void pop() {} - /// \brief Remove the given item from the heap. - /// - /// This function removes the given item from the heap if it is - /// already stored. + /// \brief Removes an item from the heap. + /// + /// 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 the given item. - /// - /// This function returns the priority of the given item. - /// \param i The item. - /// \pre \e i must be in the heap. + /// \brief The priority of an item. + /// + /// Returns the priority of the given item. + /// \param i The item. + /// \pre \c i must be in the heap. Prio operator[](const Item &i) const {} - /// \brief Set the priority of an item or insert it, if it is + /// \brief Sets the priority of an item or inserts 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. + /// already stored in the heap. + /// Otherwise it inserts the given item with the given priority. /// /// \param i The item. @@ -173,21 +150,22 @@ void set(const Item &i, const Prio &p) {} - /// \brief Decrease the priority of an item to the given value. - /// - /// This function decreases the priority of an item to the given value. + /// \brief Decreases the priority of an item to the given value. + /// + /// 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. + /// \pre \c i must be stored in the heap with priority at least \c p. void decrease(const Item &i, const Prio &p) {} - /// \brief Increase the priority of an item to the given value. - /// - /// This function increases the priority of an item to the given value. + /// \brief Increases the priority of an item to the given value. + /// + /// 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. + /// \pre \c i must be stored in the heap with priority at most \c p. void increase(const Item &i, const Prio &p) {} - /// \brief Return the state of an item. + /// \brief Returns if an item is in, has already been in, or has + /// never been in the heap. /// /// This method returns \c PRE_HEAP if the given item has never @@ -199,9 +177,9 @@ State state(const Item &i) const {} - /// \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. + /// \brief Sets 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. /// \param i The item. /// \param st The state. It should not be \c IN_HEAP. Index: lemon/concepts/maps.h =================================================================== --- lemon/concepts/maps.h (revision 576) +++ lemon/concepts/maps.h (revision 765) @@ -183,5 +183,6 @@ template struct Constraints { - void constraints() { + typename enable_if::type + constraints() { checkConcept, _ReferenceMap >(); ref = m[key]; Index: lemon/dfs.h =================================================================== --- lemon/dfs.h (revision 764) +++ lemon/dfs.h (revision 631) @@ -48,5 +48,5 @@ ///The type of the map that stores the predecessor ///arcs of the %DFS paths. - ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap PredMap; ///Instantiates a \c PredMap. @@ -63,6 +63,5 @@ ///The type of the map that indicates which nodes are processed. - ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. - ///By default it is a NullMap. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. typedef NullMap ProcessedMap; ///Instantiates a \c ProcessedMap. @@ -83,5 +82,5 @@ ///The type of the map that indicates which nodes are reached. - ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; ///Instantiates a \c ReachedMap. @@ -98,5 +97,5 @@ ///The type of the map that stores the distances of the nodes. - ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap DistMap; ///Instantiates a \c DistMap. @@ -226,5 +225,5 @@ ///\ref named-templ-param "Named parameter" for setting ///\c PredMap type. - ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. template struct SetPredMap : public Dfs > { @@ -246,5 +245,5 @@ ///\ref named-templ-param "Named parameter" for setting ///\c DistMap type. - ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. template struct SetDistMap : public Dfs< Digraph, SetDistMapTraits > { @@ -266,5 +265,5 @@ ///\ref named-templ-param "Named parameter" for setting ///\c ReachedMap type. - ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. template struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits > { @@ -286,5 +285,5 @@ ///\ref named-templ-param "Named parameter" for setting ///\c ProcessedMap type. - ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. template struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits > { @@ -413,6 +412,6 @@ ///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 better control on the execution, you have to call - ///\ref init() first, then you can add a source node with \ref addSource() + ///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() ///and perform the actual computation with \ref start(). ///This procedure can be repeated if there are nodes that have not @@ -671,7 +670,7 @@ ///@{ - ///The DFS path to the given node. - - ///Returns the DFS path to the given node from the root(s). + ///The DFS path to a node. + + ///Returns the DFS path to a node. /// ///\warning \c t should be reached from the root(s). @@ -681,7 +680,7 @@ Path path(Node t) const { return Path(*G, *_pred, t); } - ///The distance of the given node from the root(s). - - ///Returns the distance of the given node from the root(s). + ///The distance of a node from the root(s). + + ///Returns the distance of a node from the root(s). /// ///\warning If node \c v is not reached from the root(s), then @@ -692,5 +691,5 @@ int dist(Node v) const { return (*_dist)[v]; } - ///Returns the 'previous arc' of the %DFS tree for the given node. + ///Returns the 'previous arc' of the %DFS tree for a node. ///This function returns the 'previous arc' of the %DFS tree for the @@ -700,5 +699,5 @@ /// ///The %DFS tree used here is equal to the %DFS tree used in - ///\ref predNode() and \ref predMap(). + ///\ref predNode(). /// ///\pre Either \ref run(Node) "run()" or \ref init() @@ -706,13 +705,13 @@ Arc predArc(Node v) const { return (*_pred)[v];} - ///Returns the 'previous node' of the %DFS tree for the given node. + ///Returns the 'previous node' of the %DFS tree. ///This function returns the 'previous node' of the %DFS ///tree for the node \c v, i.e. it returns the last but one node - ///of a %DFS path from a root to \c v. It is \c INVALID + ///from a %DFS path from a root to \c v. It is \c INVALID ///if \c v is not reached from the root(s) or if \c v is a root. /// ///The %DFS tree used here is equal to the %DFS tree used in - ///\ref predArc() and \ref predMap(). + ///\ref predArc(). /// ///\pre Either \ref run(Node) "run()" or \ref init() @@ -735,5 +734,5 @@ /// ///Returns a const reference to the node map that stores the predecessor - ///arcs, which form the DFS tree (forest). + ///arcs, which form the DFS tree. /// ///\pre Either \ref run(Node) "run()" or \ref init() @@ -741,5 +740,5 @@ const PredMap &predMap() const { return *_pred;} - ///Checks if the given node. node is reached from the root(s). + ///Checks if a node is reached from the root(s). ///Returns \c true if \c v is reached from the root(s). @@ -767,5 +766,5 @@ ///The type of the map that stores the predecessor ///arcs of the %DFS paths. - ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap PredMap; ///Instantiates a PredMap. @@ -782,5 +781,5 @@ ///The type of the map that indicates which nodes are processed. - ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. typedef NullMap ProcessedMap; @@ -802,5 +801,5 @@ ///The type of the map that indicates which nodes are reached. - ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; ///Instantiates a ReachedMap. @@ -817,5 +816,5 @@ ///The type of the map that stores the distances of the nodes. - ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap DistMap; ///Instantiates a DistMap. @@ -832,5 +831,5 @@ ///The type of the DFS paths. - ///It must conform to the \ref concepts::Path "Path" concept. + ///It must meet the \ref concepts::Path "Path" concept. typedef lemon::Path Path; }; @@ -838,6 +837,10 @@ /// Default traits class used by DfsWizard - /// Default traits class used by DfsWizard. - /// \tparam GR The type of the digraph. + /// To make it easier to use Dfs algorithm + /// we have created a wizard class. + /// This \ref DfsWizard class needs default traits, + /// as well as the \ref Dfs class. + /// The \ref DfsWizardBase is a class to be the default traits of the + /// \ref DfsWizard class. template class DfsWizardBase : public DfsWizardDefaultTraits @@ -867,5 +870,5 @@ /// Constructor. - /// This constructor does not require parameters, it initiates + /// This constructor does not require parameters, therefore it initiates /// all of the attributes to \c 0. DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), @@ -897,4 +900,5 @@ typedef TR Base; + ///The type of the digraph the algorithm runs on. typedef typename TR::Digraph Digraph; @@ -904,8 +908,14 @@ typedef typename Digraph::OutArcIt OutArcIt; + ///\brief The type of the map that stores the predecessor + ///arcs of the DFS paths. typedef typename TR::PredMap PredMap; + ///\brief The type of the map that stores the distances of the nodes. typedef typename TR::DistMap DistMap; + ///\brief The type of the map that indicates which nodes are reached. typedef typename TR::ReachedMap ReachedMap; + ///\brief The type of the map that indicates which nodes are processed. typedef typename TR::ProcessedMap ProcessedMap; + ///The type of the DFS paths typedef typename TR::Path Path; @@ -990,10 +1000,9 @@ SetPredMapBase(const TR &b) : TR(b) {} }; - - ///\brief \ref named-templ-param "Named parameter" for setting - ///the predecessor map. - /// - ///\ref named-templ-param "Named parameter" function for setting - ///the map that stores the predecessor arcs of the nodes. + ///\brief \ref named-func-param "Named parameter" + ///for setting PredMap object. + /// + ///\ref named-func-param "Named parameter" + ///for setting PredMap object. template DfsWizard > predMap(const T &t) @@ -1009,10 +1018,9 @@ SetReachedMapBase(const TR &b) : TR(b) {} }; - - ///\brief \ref named-templ-param "Named parameter" for setting - ///the reached map. - /// - ///\ref named-templ-param "Named parameter" function for setting - ///the map that indicates which nodes are reached. + ///\brief \ref named-func-param "Named parameter" + ///for setting ReachedMap object. + /// + /// \ref named-func-param "Named parameter" + ///for setting ReachedMap object. template DfsWizard > reachedMap(const T &t) @@ -1028,11 +1036,9 @@ SetDistMapBase(const TR &b) : TR(b) {} }; - - ///\brief \ref named-templ-param "Named parameter" for setting - ///the distance map. - /// - ///\ref named-templ-param "Named parameter" function for setting - ///the map that stores the distances of the nodes calculated - ///by the algorithm. + ///\brief \ref named-func-param "Named parameter" + ///for setting DistMap object. + /// + /// \ref named-func-param "Named parameter" + ///for setting DistMap object. template DfsWizard > distMap(const T &t) @@ -1048,10 +1054,9 @@ SetProcessedMapBase(const TR &b) : TR(b) {} }; - - ///\brief \ref named-func-param "Named parameter" for setting - ///the processed map. - /// - ///\ref named-templ-param "Named parameter" function for setting - ///the map that indicates which nodes are processed. + ///\brief \ref named-func-param "Named parameter" + ///for setting ProcessedMap object. + /// + /// \ref named-func-param "Named parameter" + ///for setting ProcessedMap object. template DfsWizard > processedMap(const T &t) @@ -1204,5 +1209,5 @@ /// /// The type of the map that indicates which nodes are reached. - /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; @@ -1365,6 +1370,6 @@ /// 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 better control on the execution, you have to call - /// \ref init() first, then you can add a source node with \ref addSource() + /// 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() /// and perform the actual computation with \ref start(). /// This procedure can be repeated if there are nodes that have not @@ -1616,5 +1621,5 @@ ///@{ - /// \brief Checks if the given node is reached from the root(s). + /// \brief Checks if a node is reached from the root(s). /// /// Returns \c true if \c v is reached from the root(s). Index: lemon/dijkstra.h =================================================================== --- lemon/dijkstra.h (revision 764) +++ lemon/dijkstra.h (revision 631) @@ -71,7 +71,7 @@ ///The type of the map that stores the arc lengths. - ///It must conform to the \ref concepts::ReadMap "ReadMap" concept. + ///It must meet the \ref concepts::ReadMap "ReadMap" concept. typedef LEN LengthMap; - ///The type of the arc lengths. + ///The type of the length of the arcs. typedef typename LEN::Value Value; @@ -117,5 +117,5 @@ ///The type of the map that stores the predecessor ///arcs of the shortest paths. - ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap PredMap; ///Instantiates a \c PredMap. @@ -132,5 +132,5 @@ ///The type of the map that indicates which nodes are processed. - ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. typedef NullMap ProcessedMap; @@ -152,5 +152,5 @@ ///The type of the map that stores the distances of the nodes. - ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap DistMap; ///Instantiates a \c DistMap. @@ -169,8 +169,4 @@ /// \ingroup shortest_path ///This class provides an efficient implementation of the %Dijkstra algorithm. - /// - ///The %Dijkstra algorithm solves the single-source shortest path problem - ///when all arc lengths are non-negative. If there are negative lengths, - ///the BellmanFord algorithm should be used instead. /// ///The arc lengths are passed to the algorithm using a @@ -206,5 +202,5 @@ typedef typename TR::Digraph Digraph; - ///The type of the arc lengths. + ///The type of the length of the arcs. typedef typename TR::LengthMap::Value Value; ///The type of the map that stores the arc lengths. @@ -309,5 +305,5 @@ ///\ref named-templ-param "Named parameter" for setting ///\c PredMap type. - ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. template struct SetPredMap @@ -330,5 +326,5 @@ ///\ref named-templ-param "Named parameter" for setting ///\c DistMap type. - ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. template struct SetDistMap @@ -351,5 +347,5 @@ ///\ref named-templ-param "Named parameter" for setting ///\c ProcessedMap type. - ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. template struct SetProcessedMap @@ -448,5 +444,4 @@ ///\ref named-templ-param "Named parameter" for setting ///\c OperationTraits type. - /// For more information see \ref DijkstraDefaultOperationTraits. template struct SetOperationTraits @@ -590,6 +585,6 @@ ///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 better control on the execution, you have to call - ///\ref init() first, then you can add several source nodes with + ///If you need more control on the execution, first you have to call + ///\ref init(), 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. @@ -807,12 +802,12 @@ ///The results of the %Dijkstra algorithm can be obtained using these ///functions.\n - ///Either \ref run(Node) "run()" or \ref init() should be called + ///Either \ref run(Node) "run()" or \ref start() should be called ///before using them. ///@{ - ///The shortest path to the given node. - - ///Returns the shortest path to the given node from the root(s). + ///The shortest path to a node. + + ///Returns the shortest path to a node. /// ///\warning \c t should be reached from the root(s). @@ -822,7 +817,7 @@ Path path(Node t) const { return Path(*G, *_pred, t); } - ///The distance of the given node from the root(s). - - ///Returns the distance of the given node from the root(s). + ///The distance of a node from the root(s). + + ///Returns the distance of a node from the root(s). /// ///\warning If node \c v is not reached from the root(s), then @@ -833,7 +828,6 @@ Value dist(Node v) const { return (*_dist)[v]; } - ///\brief Returns the 'previous arc' of the shortest path tree for - ///the given node. - /// + ///Returns the 'previous arc' of the shortest path tree for a node. + ///This function returns the 'previous arc' of the shortest path ///tree for the node \c v, i.e. it returns the last arc of a @@ -842,5 +836,5 @@ /// ///The shortest path tree used here is equal to the shortest path - ///tree used in \ref predNode() and \ref predMap(). + ///tree used in \ref predNode(). /// ///\pre Either \ref run(Node) "run()" or \ref init() @@ -848,14 +842,13 @@ Arc predArc(Node v) const { return (*_pred)[v]; } - ///\brief Returns the 'previous node' of the shortest path tree for - ///the given node. - /// + ///Returns the 'previous node' of the shortest path tree for a node. + ///This function returns the 'previous node' of the shortest path ///tree for the node \c v, i.e. it returns the last but one node - ///of a shortest path from a root to \c v. It is \c INVALID + ///from 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 \ref predMap(). + ///tree used in \ref predArc(). /// ///\pre Either \ref run(Node) "run()" or \ref init() @@ -878,5 +871,5 @@ /// ///Returns a const reference to the node map that stores the predecessor - ///arcs, which form the shortest path tree (forest). + ///arcs, which form the shortest path tree. /// ///\pre Either \ref run(Node) "run()" or \ref init() @@ -884,5 +877,5 @@ const PredMap &predMap() const { return *_pred;} - ///Checks if the given node is reached from the root(s). + ///Checks if a node is reached from the root(s). ///Returns \c true if \c v is reached from the root(s). @@ -903,7 +896,7 @@ Heap::POST_HEAP; } - ///The current distance of the given node from the root(s). - - ///Returns the current distance of the given node from the root(s). + ///The current distance of a node from the root(s). + + ///Returns the current distance of a node from the root(s). ///It may be decreased in the following processes. /// @@ -932,7 +925,7 @@ ///The type of the map that stores the arc lengths. - ///It must conform to the \ref concepts::ReadMap "ReadMap" concept. + ///It must meet the \ref concepts::ReadMap "ReadMap" concept. typedef LEN LengthMap; - ///The type of the arc lengths. + ///The type of the length of the arcs. typedef typename LEN::Value Value; @@ -981,5 +974,5 @@ ///The type of the map that stores the predecessor ///arcs of the shortest paths. - ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap PredMap; ///Instantiates a PredMap. @@ -996,5 +989,5 @@ ///The type of the map that indicates which nodes are processed. - ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. typedef NullMap ProcessedMap; @@ -1016,5 +1009,5 @@ ///The type of the map that stores the distances of the nodes. - ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap DistMap; ///Instantiates a DistMap. @@ -1031,5 +1024,5 @@ ///The type of the shortest paths. - ///It must conform to the \ref concepts::Path "Path" concept. + ///It must meet the \ref concepts::Path "Path" concept. typedef lemon::Path Path; }; @@ -1037,7 +1030,10 @@ /// Default traits class used by DijkstraWizard - /// Default traits class used by DijkstraWizard. - /// \tparam GR The type of the digraph. - /// \tparam LEN The type of the length map. + /// To make it easier to use Dijkstra algorithm + /// we have created a wizard class. + /// This \ref DijkstraWizard class needs default traits, + /// as well as the \ref Dijkstra class. + /// The \ref DijkstraWizardBase is a class to be the default traits of the + /// \ref DijkstraWizard class. template class DijkstraWizardBase : public DijkstraWizardDefaultTraits @@ -1098,4 +1094,5 @@ typedef TR Base; + ///The type of the digraph the algorithm runs on. typedef typename TR::Digraph Digraph; @@ -1105,10 +1102,18 @@ typedef typename Digraph::OutArcIt OutArcIt; + ///The type of the map that stores the arc lengths. typedef typename TR::LengthMap LengthMap; + ///The type of the length of the arcs. typedef typename LengthMap::Value Value; + ///\brief The type of the map that stores the predecessor + ///arcs of the shortest paths. typedef typename TR::PredMap PredMap; + ///The type of the map that stores the distances of the nodes. typedef typename TR::DistMap DistMap; + ///The type of the map that indicates which nodes are processed. typedef typename TR::ProcessedMap ProcessedMap; + ///The type of the shortest paths typedef typename TR::Path Path; + ///The heap type used by the dijkstra algorithm. typedef typename TR::Heap Heap; @@ -1182,10 +1187,9 @@ SetPredMapBase(const TR &b) : TR(b) {} }; - - ///\brief \ref named-templ-param "Named parameter" for setting - ///the predecessor map. - /// - ///\ref named-templ-param "Named parameter" function for setting - ///the map that stores the predecessor arcs of the nodes. + ///\brief \ref named-func-param "Named parameter" + ///for setting PredMap object. + /// + ///\ref named-func-param "Named parameter" + ///for setting PredMap object. template DijkstraWizard > predMap(const T &t) @@ -1201,11 +1205,9 @@ SetDistMapBase(const TR &b) : TR(b) {} }; - - ///\brief \ref named-templ-param "Named parameter" for setting - ///the distance map. - /// - ///\ref named-templ-param "Named parameter" function for setting - ///the map that stores the distances of the nodes calculated - ///by the algorithm. + ///\brief \ref named-func-param "Named parameter" + ///for setting DistMap object. + /// + ///\ref named-func-param "Named parameter" + ///for setting DistMap object. template DijkstraWizard > distMap(const T &t) @@ -1221,10 +1223,9 @@ SetProcessedMapBase(const TR &b) : TR(b) {} }; - - ///\brief \ref named-func-param "Named parameter" for setting - ///the processed map. - /// - ///\ref named-templ-param "Named parameter" function for setting - ///the map that indicates which nodes are processed. + ///\brief \ref named-func-param "Named parameter" + ///for setting ProcessedMap object. + /// + /// \ref named-func-param "Named parameter" + ///for setting ProcessedMap object. template DijkstraWizard > processedMap(const T &t) @@ -1239,5 +1240,4 @@ SetPathBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" ///for getting the shortest path to the target node. Index: lemon/dim2.h =================================================================== --- lemon/dim2.h (revision 761) +++ lemon/dim2.h (revision 463) @@ -22,7 +22,14 @@ #include -///\ingroup geomdat +///\ingroup misc ///\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 { @@ -34,5 +41,5 @@ namespace dim2 { - /// \addtogroup geomdat + /// \addtogroup misc /// @{ Index: lemon/fib_heap.h =================================================================== --- lemon/fib_heap.h (revision 758) +++ lemon/fib_heap.h (revision 730) @@ -21,9 +21,8 @@ ///\file -///\ingroup heaps -///\brief Fibonacci heap implementation. +///\ingroup auxdat +///\brief Fibonacci Heap implementation. #include -#include #include #include @@ -31,37 +30,42 @@ namespace lemon { - /// \ingroup heaps + /// \ingroup auxdat /// - /// \brief Fibonacci heap data structure. + ///\brief Fibonacci Heap. /// - /// This class implements the \e Fibonacci \e heap data structure. - /// It fully conforms to the \ref concepts::Heap "heap concept". + ///This class implements the \e Fibonacci \e heap data structure. A \e heap + ///is a data structure for storing items with specified values called \e + ///priorities in such a way that finding the item with minimum priority is + ///efficient. \c CMP specifies the ordering of the priorities. In a heap + ///one can change the priority of an item, add or erase an item, etc. /// - /// 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". + ///The methods \ref increase and \ref erase are not efficient in a Fibonacci + ///heap. In case of many calls to these operations, it is better to use a + ///\ref BinHeap "binary heap". /// - /// \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. + ///\param PRIO Type of the priority of the items. + ///\param IM A read and writable Item int map, used internally + ///to handle the cross references. + ///\param CMP A class for the ordering of the priorities. The + ///default is \c std::less. + /// + ///\sa BinHeap + ///\sa Dijkstra #ifdef DOXYGEN - template + template #else - template > + template > #endif class FibHeap { public: - - /// Type of the item-int map. + ///\e typedef IM ItemIntMap; - /// Type of the priorities. - typedef PR Prio; - /// Type of the items stored in the heap. + ///\e + typedef PRIO Prio; + ///\e typedef typename ItemIntMap::Key Item; - /// Type of the item-priority pairs. + ///\e typedef std::pair Pair; - /// Functor type for comparing the priorities. + ///\e typedef CMP Compare; @@ -77,8 +81,8 @@ 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 + /// \brief Type to represent the items states. + /// + /// 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 /// heap's point of view, but may be useful to the user. /// @@ -91,20 +95,16 @@ }; - /// \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. + /// \brief The constructor + /// + /// \c map should be given to the constructor, since it is + /// used internally to handle the cross references. 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. + /// \brief The constructor + /// + /// \c map should be given to the constructor, since it is used + /// internally to handle the cross references. \c comp is an + /// object for ordering of the priorities. FibHeap(ItemIntMap &map, const Compare &comp) : _minimum(0), _iim(map), _comp(comp), _num() {} @@ -112,31 +112,41 @@ /// \brief The number of items stored in the heap. /// - /// This function returns the number of items stored in the heap. + /// 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. + /// \brief Checks if the heap stores no items. + /// + /// Returns \c true if and only if the heap stores no items. 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. + /// \brief Make empty this heap. + /// + /// Make empty this heap. It does not change the cross reference + /// map. If you want to reuse a heap what is not surely empty you + /// should first clear the heap and after that you should set the + /// cross reference map for each item to \c PRE_HEAP. void clear() { _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) { + /// \brief \c item gets to the heap with priority \c value independently + /// if \c item was already there. + /// + /// This method calls \ref push(\c item, \c value) if \c item is not + /// stored in the heap and it calls \ref decrease(\c item, \c value) or + /// \ref increase(\c item, \c value) otherwise. + void set (const Item& item, const Prio& value) { + int i=_iim[item]; + if ( i >= 0 && _data[i].in ) { + if ( _comp(value, _data[i].prio) ) decrease(item, value); + if ( _comp(_data[i].prio, value) ) increase(item, value); + } else push(item, value); + } + + /// \brief Adds \c item to the heap with priority \c value. + /// + /// Adds \c item to the heap with priority \c value. + /// \pre \c item must not be stored in the heap. + void push (const Item& item, const Prio& value) { int i=_iim[item]; if ( i < 0 ) { @@ -159,28 +169,38 @@ _data[_minimum].right_neighbor=i; _data[i].left_neighbor=_minimum; - if ( _comp( prio, _data[_minimum].prio) ) _minimum=i; + if ( _comp( value, _data[_minimum].prio) ) _minimum=i; } else { _data[i].right_neighbor=_data[i].left_neighbor=i; _minimum=i; } - _data[i].prio=prio; + _data[i].prio=value; ++_num; } - /// \brief Return the item having minimum priority. - /// - /// This function returns the item having minimum priority. - /// \pre The heap must be non-empty. + /// \brief Returns the item with minimum priority relative to \c Compare. + /// + /// This method returns the item with minimum priority relative to \c + /// Compare. + /// \pre The heap must be nonempty. 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. + /// \brief Returns the minimum priority relative to \c Compare. + /// + /// It returns the minimum priority relative to \c Compare. + /// \pre The heap must be nonempty. + const Prio& prio() const { return _data[_minimum].prio; } + + /// \brief Returns the priority of \c item. + /// + /// It returns the priority of \c item. + /// \pre \c item must be in the heap. + const Prio& operator[](const Item& item) const { + return _data[_iim[item]].prio; + } + + /// \brief Deletes the item with minimum priority relative to \c Compare. + /// + /// This method deletes the item with minimum priority relative to \c + /// Compare from the heap. /// \pre The heap must be non-empty. void pop() { @@ -189,5 +209,5 @@ _data[_minimum].in=false; if ( _data[_minimum].degree!=0 ) { - makeRoot(_data[_minimum].child); + makeroot(_data[_minimum].child); _minimum=_data[_minimum].child; balance(); @@ -202,5 +222,5 @@ int last_child=_data[child].left_neighbor; - makeRoot(child); + makeroot(child); _data[left].right_neighbor=child; @@ -215,10 +235,8 @@ } - /// \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. + /// \brief Deletes \c item from the heap. + /// + /// This method deletes \c item from the heap, if \c item was already + /// stored in the heap. It is quite inefficient in Fibonacci heaps. void erase (const Item& item) { int i=_iim[item]; @@ -235,66 +253,41 @@ } - /// \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) { + /// \brief Decreases the priority of \c item to \c value. + /// + /// This method decreases the priority of \c item to \c value. + /// \pre \c item must be stored in the heap with priority at least \c + /// value relative to \c Compare. + void decrease (Item item, const Prio& value) { 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; + _data[i].prio=value; int p=_data[i].parent; - if ( p!=-1 && _comp(prio, _data[p].prio) ) { + if ( p!=-1 && _comp(value, _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) { + if ( _comp(value, _data[_minimum].prio) ) _minimum=i; + } + + /// \brief Increases the priority of \c item to \c value. + /// + /// This method sets the priority of \c item to \c value. Though + /// there is no precondition on the priority of \c item, this + /// method should be used only if it is indeed necessary to increase + /// (relative to \c Compare) the priority of \c item, because this + /// method is inefficient. + void increase (Item item, const Prio& value) { 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. + push(item, value); + } + + + /// \brief Returns if \c item is in, has already been in, or has never + /// been in the heap. + /// + /// 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. State state(const Item &item) const { int i=_iim[item]; @@ -306,9 +299,9 @@ } - /// \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. + /// \brief Sets the state of the \c 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. /// \param i The item. /// \param st The state. It should not be \c IN_HEAP. @@ -373,5 +366,5 @@ } - void makeRoot(int c) { + void makeroot(int c) { int s=c; do { Index: mon/fourary_heap.h =================================================================== --- lemon/fourary_heap.h (revision 753) +++ (revision ) @@ -1,342 +1,0 @@ -/* -*- 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 Index: lemon/gomory_hu.h =================================================================== --- lemon/gomory_hu.h (revision 760) +++ lemon/gomory_hu.h (revision 643) @@ -360,8 +360,8 @@ /// \c t. /// \code - /// GomoryHu gom(g, capacities); + /// GomoruHu gom(g, capacities); /// gom.run(); /// int cnt=0; - /// for(GomoryHu::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt; + /// for(GomoruHu::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt; /// \endcode class MinCutNodeIt @@ -457,8 +457,8 @@ /// \c t. /// \code - /// GomoryHu gom(g, capacities); + /// GomoruHu gom(g, capacities); /// gom.run(); /// int value=0; - /// for(GomoryHu::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e) + /// for(GomoruHu::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e) /// value+=capacities[e]; /// \endcode Index: mon/kary_heap.h =================================================================== --- lemon/kary_heap.h (revision 753) +++ (revision ) @@ -1,352 +1,0 @@ -/* -*- 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 Index: lemon/maps.h =================================================================== --- lemon/maps.h (revision 764) +++ lemon/maps.h (revision 664) @@ -23,5 +23,4 @@ #include #include -#include #include @@ -30,4 +29,6 @@ ///\ingroup maps ///\brief Miscellaneous property maps + +#include namespace lemon { @@ -1790,9 +1791,9 @@ /// \code /// std::vector v; - /// dfs(g).processedMap(loggerBoolMap(std::back_inserter(v))).run(s); + /// dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run(); /// \endcode /// \code /// std::vector v(countNodes(g)); - /// dfs(g).processedMap(loggerBoolMap(v.begin())).run(s); + /// dfs(g,s).processedMap(loggerBoolMap(v.begin())).run(); /// \endcode /// @@ -1818,5 +1819,5 @@ /// /// 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 @@ -1902,11 +1903,10 @@ /// This class provides simple invertable graph maps. - /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap) - /// and if a key is set to a new value, then stores it in the inverse map. + /// 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. + /// /// 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. @@ -1924,5 +1924,5 @@ template Map::Type Map; - typedef std::multimap Container; + typedef std::map Container; Container _inv_map; @@ -1949,6 +1949,4 @@ /// 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 { @@ -2003,13 +2001,9 @@ void set(const Key& key, const Value& val) { Value oldval = Map::operator[](key); - 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; - } + typename Container::iterator it = _inv_map.find(oldval); + if (it != _inv_map.end() && it->second == key) { + _inv_map.erase(it); } - _inv_map.insert(std::make_pair(val, key)); + _inv_map.insert(make_pair(val, key)); Map::set(key, val); } @@ -2023,12 +2017,9 @@ } - /// \brief Gives back an item by its value. - /// - /// 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); + /// \brief Gives back the 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); return it != _inv_map.end() ? it->second : INVALID; } @@ -2042,11 +2033,7 @@ virtual void erase(const Key& key) { Value val = Map::operator[](key); - 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; - } + typename Container::iterator it = _inv_map.find(val); + if (it != _inv_map.end() && it->second == key) { + _inv_map.erase(it); } Map::erase(key); @@ -2060,11 +2047,7 @@ for (int i = 0; i < int(keys.size()); ++i) { Value val = Map::operator[](keys[i]); - 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; - } + typename Container::iterator it = _inv_map.find(val); + if (it != _inv_map.end() && it->second == keys[i]) { + _inv_map.erase(it); } } @@ -2102,7 +2085,6 @@ /// \brief Subscript operator. /// - /// Subscript operator. It gives back an item - /// that is assigned to the given value or \c INVALID - /// if no such item exists. + /// Subscript operator. It gives back the item + /// that was last assigned to the given value. Value operator[](const Key& key) const { return _inverted(key); @@ -2273,5 +2255,5 @@ /// \brief Gives back the item belonging to a \e RangeId - /// + /// /// Gives back the item belonging to a \e RangeId. Item operator()(int id) const { @@ -2330,901 +2312,4 @@ }; - /// \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. /// @@ -3396,5 +2481,5 @@ /// 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 @@ -3412,5 +2497,5 @@ public: - + /// The graph type of InDegMap typedef GR Graph; @@ -3526,5 +2611,5 @@ /// 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 Index: lemon/min_cost_arborescence.h =================================================================== --- lemon/min_cost_arborescence.h (revision 760) +++ lemon/min_cost_arborescence.h (revision 672) @@ -489,6 +489,6 @@ /// The simplest way to execute the algorithm is to use /// one of the member functions called \c run(...). \n - /// If you need better control on the execution, - /// you have to call \ref init() first, then you can add several + /// If you need more control on the execution, + /// first you must call \ref init(), then you can add several /// source nodes with \ref addSource(). /// Finally \ref start() will perform the arborescence Index: mon/pairing_heap.h =================================================================== --- lemon/pairing_heap.h (revision 752) +++ (revision ) @@ -1,474 +1,0 @@ -/* -*- 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; - } - 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 - Index: lemon/preflow.h =================================================================== --- lemon/preflow.h (revision 762) +++ lemon/preflow.h (revision 688) @@ -53,9 +53,5 @@ /// 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. @@ -72,10 +68,7 @@ /// The elevator type used by Preflow algorithm. /// - /// \sa Elevator, LinkedElevator -#ifdef DOXYGEN - typedef lemon::Elevator Elevator; -#else - typedef lemon::Elevator Elevator; -#endif + /// \sa Elevator + /// \sa LinkedElevator + typedef LinkedElevator Elevator; /// \brief Instantiates an Elevator. @@ -105,5 +98,5 @@ /// "flow of maximum value" in a digraph. /// The preflow algorithms are the fastest known maximum - /// flow algorithms. The current implementation uses a mixture of the + /// flow algorithms. The current implementation use 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$. @@ -379,9 +372,8 @@ } - /// \brief Sets the tolerance used by the algorithm. - /// - /// Sets the tolerance object used by the algorithm. - /// \return (*this) - Preflow& tolerance(const Tolerance& tolerance) { + /// \brief Sets the tolerance used by algorithm. + /// + /// Sets the tolerance used by algorithm. + Preflow& tolerance(const Tolerance& tolerance) const { _tolerance = tolerance; return *this; @@ -390,8 +382,7 @@ /// \brief Returns a const reference to the tolerance. /// - /// Returns a const reference to the tolerance object used by - /// the algorithm. + /// Returns a const reference to the tolerance. const Tolerance& tolerance() const { - return _tolerance; + return tolerance; } @@ -399,6 +390,6 @@ /// The simplest way to execute the preflow algorithm is to use /// \ref run() or \ref runMinCut().\n - /// If you need better control on the initial solution or the execution, - /// you have to call one of the \ref init() functions first, then + /// If you need more control on the initial solution or the execution, + /// first you have to call one of the \ref init() functions, then /// \ref startFirstPhase() and if you need it \ref startSecondPhase(). Index: lemon/radix_heap.h =================================================================== --- lemon/radix_heap.h (revision 758) +++ lemon/radix_heap.h (revision 730) @@ -20,7 +20,7 @@ #define LEMON_RADIX_HEAP_H -///\ingroup heaps +///\ingroup auxdat ///\file -///\brief Radix heap implementation. +///\brief Radix Heap implementation. #include @@ -30,52 +30,54 @@ - /// \ingroup heaps + /// \ingroup auxdata /// - /// \brief Radix heap data structure. + /// \brief A Radix Heap implementation. /// - /// 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. + /// This class implements the \e radix \e heap data structure. A \e heap + /// is a data structure for storing items with specified values called \e + /// priorities in such a way that finding the item with minimum priority is + /// efficient. This heap type can store only items with \e int priority. + /// In a heap one can change the priority of an item, add or erase an + /// item, but the priority cannot be decreased under the last removed + /// item's priority. /// - /// \tparam IM A read-writable item map with \c int values, used - /// internally to handle the cross references. + /// \param IM A read and writable Item int map, used internally + /// to handle the cross references. + /// + /// \see BinHeap + /// \see Dijkstra template class RadixHeap { public: - - /// Type of the item-int map. + typedef typename IM::Key Item; + typedef int Prio; 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. + /// This Exception is thrown when a smaller priority + /// is inserted into the \e RadixHeap then the last time erased. /// \see RadixHeap - class PriorityUnderflowError : public Exception { + + class UnderFlowPriorityError : public Exception { public: virtual const char* what() const throw() { - return "lemon::RadixHeap::PriorityUnderflowError"; + return "lemon::RadixHeap::UnderFlowPriorityError"; } }; - /// \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 + /// \brief Type to represent the items states. + /// + /// 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 /// 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. + /// The ItemIntMap \e should be initialized in such way that it maps + /// 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. + IN_HEAP = 0, + PRE_HEAP = -1, + POST_HEAP = -2 }; @@ -95,53 +97,50 @@ }; - std::vector _data; - std::vector _boxes; + 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)) { + /// \brief The constructor. + /// + /// The constructor. + /// + /// \param map It should be given to the constructor, since it is used + /// internally to handle the cross references. The value of the map + /// should be PRE_HEAP (-1) for each element. + /// + /// \param minimal The initial minimal value of the heap. + /// \param capacity It determines the initial capacity of the heap. + RadixHeap(ItemIntMap &map, int minimal = 0, int capacity = 0) + : _iim(map) { + boxes.push_back(RadixBox(minimal, 1)); + boxes.push_back(RadixBox(minimal + 1, 1)); + while (lower(boxes.size() - 1, capacity + minimal - 1)) { 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)) { + /// The number of items stored in the heap. + /// + /// \brief Returns the number of items stored in the heap. + int size() const { return data.size(); } + /// \brief Checks if the heap stores no items. + /// + /// Returns \c true if and only if the heap stores no items. + bool empty() const { return data.empty(); } + + /// \brief Make empty this heap. + /// + /// Make empty this heap. It does not change the cross reference + /// map. If you want to reuse a heap what is not surely empty you + /// should first clear the heap and after that you should set the + /// cross reference map for each item to \c PRE_HEAP. + void clear(int minimal = 0, int capacity = 0) { + data.clear(); boxes.clear(); + boxes.push_back(RadixBox(minimal, 1)); + boxes.push_back(RadixBox(minimal + 1, 1)); + while (lower(boxes.size() - 1, capacity + minimal - 1)) { extend(); } @@ -151,56 +150,56 @@ bool upper(int box, Prio pr) { - return pr < _boxes[box].min; + return pr < boxes[box].min; } bool lower(int box, Prio pr) { - return pr >= _boxes[box].min + _boxes[box].size; - } - - // Remove item from the box list + return pr >= boxes[box].min + boxes[box].size; + } + + /// \brief Remove item from the box list. void remove(int index) { - if (_data[index].prev >= 0) { - _data[_data[index].prev].next = _data[index].next; + if (data[index].prev >= 0) { + data[data[index].prev].next = data[index].next; } else { - _boxes[_data[index].box].first = _data[index].next; - } - if (_data[index].next >= 0) { - _data[_data[index].next].prev = _data[index].prev; - } - } - - // Insert item into the box list + boxes[data[index].box].first = data[index].next; + } + if (data[index].next >= 0) { + data[data[index].next].prev = data[index].prev; + } + } + + /// \brief Insert item into the box list. void insert(int box, int index) { - if (_boxes[box].first == -1) { - _boxes[box].first = index; - _data[index].next = _data[index].prev = -1; + if (boxes[box].first == -1) { + boxes[box].first = index; + data[index].next = data[index].prev = -1; } else { - _data[index].next = _boxes[box].first; - _data[_boxes[box].first].prev = index; - _data[index].prev = -1; - _boxes[box].first = index; - } - _data[index].box = box; - } - - // Add a new box to the box list + data[index].next = boxes[box].first; + data[boxes[box].first].prev = index; + data[index].prev = -1; + boxes[box].first = index; + } + data[index].box = box; + } + + /// \brief 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; + int min = boxes.back().min + boxes.back().size; + int bs = 2 * boxes.back().size; + boxes.push_back(RadixBox(min, bs)); + } + + /// \brief Move an item up into the proper box. + void bubble_up(int index) { + if (!lower(data[index].box, data[index].prio)) return; remove(index); - int box = findUp(_data[index].box, _data[index].prio); + int box = findUp(data[index].box, data[index].prio); insert(box, index); } - // Find up the proper box for the item with the given priority + /// \brief Find up the proper box for the item with the given prio. int findUp(int start, int pr) { while (lower(start, pr)) { - if (++start == int(_boxes.size())) { + if (++start == int(boxes.size())) { extend(); } @@ -209,37 +208,38 @@ } - // Move an item down into the proper box - void bubbleDown(int index) { - if (!upper(_data[index].box, _data[index].prio)) return; + /// \brief Move an item down into the proper box. + void bubble_down(int index) { + if (!upper(data[index].box, data[index].prio)) return; remove(index); - int box = findDown(_data[index].box, _data[index].prio); + int box = findDown(data[index].box, data[index].prio); insert(box, index); } - // Find down the proper box for the item with the given priority + /// \brief Find up the proper box for the item with the given prio. int findDown(int start, int pr) { while (upper(start, pr)) { - if (--start < 0) throw PriorityUnderflowError(); + if (--start < 0) throw UnderFlowPriorityError(); } return start; } - // Find the first non-empty box + /// \brief Find the first not empty box. int findFirst() { int first = 0; - while (_boxes[first].first == -1) ++first; + while (boxes[first].first == -1) ++first; return first; } - // Gives back the minimum priority of the given box + /// \brief Gives back the minimal prio of the box. int minValue(int box) { - int min = _data[_boxes[box].first].prio; - for (int k = _boxes[box].first; k != -1; k = _data[k].next) { - if (_data[k].prio < min) min = _data[k].prio; + int min = data[boxes[box].first].prio; + for (int k = boxes[box].first; k != -1; k = data[k].next) { + if (data[k].prio < min) min = data[k].prio; } return min; } - // Rearrange the items of the heap and make the first box non-empty + /// \brief Rearrange the items of the heap and makes the + /// first box not empty. void moveDown() { int box = findFirst(); @@ -247,29 +247,29 @@ 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; + boxes[i].min = min; + min += boxes[i].size; + } + int curr = boxes[box].first, next; while (curr != -1) { - next = _data[curr].next; - bubbleDown(curr); + next = data[curr].next; + bubble_down(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; + void relocate_last(int index) { + if (index != int(data.size()) - 1) { + data[index] = data.back(); + if (data[index].prev != -1) { + data[data[index].prev].next = index; } else { - _boxes[_data[index].box].first = index; + boxes[data[index].box].first = index; } - if (_data[index].next != -1) { - _data[_data[index].next].prev = index; + if (data[index].next != -1) { + data[data[index].next].prev = index; } - _iim[_data[index].item] = index; - } - _data.pop_back(); + _iim[data[index].item] = index; + } + data.pop_back(); } @@ -278,84 +278,78 @@ /// \brief Insert an item into the heap with the given priority. /// - /// This function inserts the given item into the heap with the - /// given priority. + /// Adds \c i to the heap with priority \c p. /// \param i The item to insert. /// \param p The priority of the item. - /// \pre \e i must not be stored in the heap. - /// \warning This method may throw an \c UnderFlowPriorityException. void push(const Item &i, const Prio &p) { - int n = _data.size(); + int n = data.size(); _iim.set(i, n); - _data.push_back(RadixItem(i, p)); - while (lower(_boxes.size() - 1, p)) { + data.push_back(RadixItem(i, p)); + while (lower(boxes.size() - 1, p)) { extend(); } - int box = findDown(_boxes.size() - 1, p); + int box = findDown(boxes.size() - 1, p); insert(box, n); } - /// \brief Return the item having minimum priority. - /// - /// This function returns the item having minimum priority. - /// \pre The heap must be non-empty. + /// \brief Returns the item with minimum priority. + /// + /// This method returns the item with minimum priority. + /// \pre The heap must be nonempty. Item top() const { const_cast&>(*this).moveDown(); - return _data[_boxes.first].item; - } - - /// \brief The minimum priority. - /// - /// This function returns the minimum priority. - /// \pre The heap must be non-empty. + return data[boxes.first].item; + } + + /// \brief Returns the minimum priority. + /// + /// It returns the minimum priority. + /// \pre The heap must be nonempty. Prio prio() const { const_cast&>(*this).moveDown(); - return _data[_boxes.first].prio; + return data[boxes.first].prio; } - /// \brief Remove the item having minimum priority. - /// - /// This function removes the item having minimum priority. + /// \brief Deletes the item with minimum priority. + /// + /// This method deletes the item with minimum priority. /// \pre The heap must be non-empty. void pop() { moveDown(); - int index = _boxes.first; - _iim[_data[index].item] = POST_HEAP; + int index = boxes.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. + relocate_last(index); + } + + /// \brief Deletes \c i from the heap. + /// + /// This method deletes item \c i from the heap, if \c i was + /// already stored in the heap. + /// \param i The item to erase. void erase(const Item &i) { int index = _iim[i]; _iim[i] = POST_HEAP; remove(index); - relocateLast(index); + relocate_last(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. + /// \brief Returns the priority of \c i. + /// + /// This function returns the priority of item \c i. + /// \pre \c i must be in the heap. + /// \param i The item. 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. + return data[idx].prio; + } + + /// \brief \c i gets to the heap with priority \c p independently + /// if \c i was already there. + /// + /// This method calls \ref push(\c i, \c p) if \c i is not stored + /// in the heap and sets the priority of \c i to \c p otherwise. + /// It may throw an \e UnderFlowPriorityException. /// \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]; @@ -363,45 +357,46 @@ push(i, p); } - else if( p >= _data[idx].prio ) { - _data[idx].prio = p; - bubbleUp(idx); + else if( p >= data[idx].prio ) { + data[idx].prio = p; + bubble_up(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. + data[idx].prio = p; + bubble_down(idx); + } + } + + + /// \brief Decreases the priority of \c i to \c p. + /// + /// This method decreases the priority of item \c i to \c p. + /// \pre \c i must be stored in the heap with priority at least \c p, and + /// \c should be greater or equal to the last removed item's priority. /// \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. + data[idx].prio = p; + bubble_down(idx); + } + + /// \brief Increases the priority of \c i to \c p. + /// + /// This method sets the priority of item \c i to \c p. + /// \pre \c i must be stored in the heap with priority at most \c p /// \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. + data[idx].prio = p; + bubble_up(idx); + } + + /// \brief Returns if \c item is in, has already been in, or has + /// never been in the heap. + /// + /// 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. /// \param i The item. State state(const Item &i) const { @@ -411,9 +406,9 @@ } - /// \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. + /// \brief Sets the state of the \c 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. /// \param i The item. /// \param st The state. It should not be \c IN_HEAP. Index: test/CMakeLists.txt =================================================================== --- test/CMakeLists.txt (revision 745) +++ test/CMakeLists.txt (revision 726) @@ -10,5 +10,4 @@ SET(TESTS adaptors_test - bellman_ford_test bfs_test circulation_test Index: test/Makefile.am =================================================================== --- test/Makefile.am (revision 745) +++ test/Makefile.am (revision 696) @@ -8,5 +8,4 @@ check_PROGRAMS += \ test/adaptors_test \ - test/bellman_ford_test \ test/bfs_test \ test/circulation_test \ @@ -54,5 +53,4 @@ 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 Index: st/bellman_ford_test.cc =================================================================== --- test/bellman_ford_test.cc (revision 746) +++ (revision ) @@ -1,283 +1,0 @@ -/* -*- 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; -} Index: test/circulation_test.cc =================================================================== --- test/circulation_test.cc (revision 736) +++ test/circulation_test.cc (revision 658) @@ -88,9 +88,4 @@ .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(); Index: test/heap_test.cc =================================================================== --- test/heap_test.cc (revision 749) +++ test/heap_test.cc (revision 728) @@ -26,4 +26,5 @@ #include + #include #include @@ -31,10 +32,6 @@ #include -#include -#include #include -#include #include -#include #include @@ -93,7 +90,9 @@ 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]; @@ -102,5 +101,5 @@ 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(); } @@ -114,4 +113,5 @@ std::vector v(test_len); + for (int i = 0; i < test_len; ++i) { v[i] = test_seq[i]; @@ -124,8 +124,10 @@ 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 @@ -143,5 +145,5 @@ if (dijkstra.reached(s)) { check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a], - "Error in shortest path tree."); + "Error in a shortest path tree!"); } } @@ -152,5 +154,5 @@ Node s = digraph.source(a); check( dijkstra.dist(n) - dijkstra.dist(s) == length[a], - "Error in shortest path tree."); + "Error in a shortest path tree!"); } } @@ -174,5 +176,4 @@ run(); - // BinHeap { typedef BinHeap IntHeap; @@ -186,29 +187,4 @@ } - // 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; @@ -222,17 +198,4 @@ } - // PairingHeap - { - typedef PairingHeap IntHeap; - checkConcept, IntHeap>(); - heapSortTest(); - heapIncreaseTest(); - - typedef PairingHeap NodeHeap; - checkConcept, NodeHeap>(); - dijkstraHeapTest(digraph, length, source); - } - - // RadixHeap { typedef RadixHeap IntHeap; @@ -246,17 +209,4 @@ } - // BinomHeap - { - typedef BinomHeap IntHeap; - checkConcept, IntHeap>(); - heapSortTest(); - heapIncreaseTest(); - - typedef BinomHeap NodeHeap; - checkConcept, NodeHeap>(); - dijkstraHeapTest(digraph, length, source); - } - - // BucketHeap, SimpleBucketHeap { typedef BucketHeap IntHeap; @@ -268,8 +218,6 @@ checkConcept, NodeHeap>(); dijkstraHeapTest(digraph, length, source); - - typedef SimpleBucketHeap SimpleIntHeap; - heapSortTest(); - } + } + return 0; Index: test/maps_test.cc =================================================================== --- test/maps_test.cc (revision 742) +++ test/maps_test.cc (revision 554) @@ -23,5 +23,4 @@ #include #include -#include #include "test_tools.h" @@ -351,225 +350,4 @@ } - // 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] = 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] = false; - check(map1[items] == 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; } Index: test/preflow_test.cc =================================================================== --- test/preflow_test.cc (revision 736) +++ test/preflow_test.cc (revision 632) @@ -95,9 +95,4 @@ 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 Index: tools/lemon-0.x-to-1.x.sh =================================================================== --- tools/lemon-0.x-to-1.x.sh (revision 738) +++ tools/lemon-0.x-to-1.x.sh (revision 621) @@ -36,8 +36,8 @@ -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"\ @@ -69,9 +69,4 @@ -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"\