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[0].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[0].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[0].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