COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changes in / [726:3fc2a801c39e:725:11404088d1a5] in lemon-main


Ignore:
Files:
6 deleted
27 edited

Legend:

Unmodified
Added
Removed

  • doc/groups.dox

    r715 r663  
    227227
    228228/**
     229@defgroup matrices Matrices
     230@ingroup datas
     231\brief Two dimensional data storages implemented in LEMON.
     232
     233This group contains two dimensional data storages implemented in LEMON.
     234*/
     235
     236/**
    229237@defgroup paths Path Structures
    230238@ingroup datas
    … …  
    239247any kind of path structure.
    240248
    241 \sa \ref concepts::Path "Path concept"
    242 */
    243 
    244 /**
    245 @defgroup heaps Heap Structures
    246 @ingroup datas
    247 \brief %Heap structures implemented in LEMON.
    248 
    249 This group contains the heap structures implemented in LEMON.
    250 
    251 LEMON provides several heap classes. They are efficient implementations
    252 of the abstract data type \e priority \e queue. They store items with
    253 specified values called \e priorities in such a way that finding and
    254 removing the item with minimum priority are efficient.
    255 The basic operations are adding and erasing items, changing the priority
    256 of an item, etc.
    257 
    258 Heaps are crucial in several algorithms, such as Dijkstra and Prim.
    259 The heap implementations have the same interface, thus any of them can be
    260 used easily in such algorithms.
    261 
    262 \sa \ref concepts::Heap "Heap concept"
    263 */
    264 
    265 /**
    266 @defgroup matrices Matrices
    267 @ingroup datas
    268 \brief Two dimensional data storages implemented in LEMON.
    269 
    270 This group contains two dimensional data storages implemented in LEMON.
     249\sa lemon::concepts::Path
    271250*/
    272251
    … …  
    278257This group contains some data structures implemented in LEMON in
    279258order to make it easier to implement combinatorial algorithms.
    280 */
    281 
    282 /**
    283 @defgroup geomdat Geometric Data Structures
    284 @ingroup auxdat
    285 \brief Geometric data structures implemented in LEMON.
    286 
    287 This group contains geometric data structures implemented in LEMON.
    288 
    289  - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional
    290    vector with the usual operations.
    291  - \ref lemon::dim2::Box "dim2::Box" can be used to determine the
    292    rectangular bounding box of a set of \ref lemon::dim2::Point
    293    "dim2::Point"'s.
    294 */
    295 
    296 /**
    297 @defgroup matrices Matrices
    298 @ingroup auxdat
    299 \brief Two dimensional data storages implemented in LEMON.
    300 
    301 This group contains two dimensional data storages implemented in LEMON.
    302259*/
    303260
    … …  
    342299
    343300/**
    344 @defgroup spantree Minimum Spanning Tree Algorithms
    345 @ingroup algs
    346 \brief Algorithms for finding minimum cost spanning trees and arborescences.
    347 
    348 This group contains the algorithms for finding minimum cost spanning
    349 trees and arborescences.
    350 */
    351 
    352 /**
    353301@defgroup max_flow Maximum Flow Algorithms
    354302@ingroup algs
    … …  
    428376
    429377\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    430     \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
     378    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
    431379
    432380LEMON contains several algorithms related to minimum cut problems:
    … …  
    441389If you want to find minimum cut just between two distinict nodes,
    442390see the \ref max_flow "maximum flow problem".
     391*/
     392
     393/**
     394@defgroup graph_properties Connectivity and Other Graph Properties
     395@ingroup algs
     396\brief Algorithms for discovering the graph properties
     397
     398This group contains the algorithms for discovering the graph properties
     399like connectivity, bipartiteness, euler property, simplicity etc.
     400
     401\image html edge_biconnected_components.png
     402\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
     403*/
     404
     405/**
     406@defgroup planar Planarity Embedding and Drawing
     407@ingroup algs
     408\brief Algorithms for planarity checking, embedding and drawing
     409
     410This group contains the algorithms for planarity checking,
     411embedding and drawing.
     412
     413\image html planar.png
     414\image latex planar.eps "Plane graph" width=\textwidth
    443415*/
    444416
    … …  
    484456
    485457/**
    486 @defgroup graph_properties Connectivity and Other Graph Properties
    487 @ingroup algs
    488 \brief Algorithms for discovering the graph properties
    489 
    490 This group contains the algorithms for discovering the graph properties
    491 like connectivity, bipartiteness, euler property, simplicity etc.
    492 
    493 \image html connected_components.png
    494 \image latex connected_components.eps "Connected components" width=\textwidth
    495 */
    496 
    497 /**
    498 @defgroup planar Planarity Embedding and Drawing
    499 @ingroup algs
    500 \brief Algorithms for planarity checking, embedding and drawing
    501 
    502 This group contains the algorithms for planarity checking,
    503 embedding and drawing.
    504 
    505 \image html planar.png
    506 \image latex planar.eps "Plane graph" width=\textwidth
     458@defgroup spantree Minimum Spanning Tree Algorithms
     459@ingroup algs
     460\brief Algorithms for finding minimum cost spanning trees and arborescences.
     461
     462This group contains the algorithms for finding minimum cost spanning
     463trees and arborescences.
     464*/
     465
     466/**
     467@defgroup auxalg Auxiliary Algorithms
     468@ingroup algs
     469\brief Auxiliary algorithms implemented in LEMON.
     470
     471This group contains some algorithms implemented in LEMON
     472in order to make it easier to implement complex algorithms.
    507473*/
    508474
    … …  
    514480This group contains the approximation and heuristic algorithms
    515481implemented in LEMON.
    516 */
    517 
    518 /**
    519 @defgroup auxalg Auxiliary Algorithms
    520 @ingroup algs
    521 \brief Auxiliary algorithms implemented in LEMON.
    522 
    523 This group contains some algorithms implemented in LEMON
    524 in order to make it easier to implement complex algorithms.
    525482*/
    526483
    … …  
    631588
    632589/**
    633 @defgroup dimacs_group DIMACS Format
     590@defgroup dimacs_group DIMACS format
    634591@ingroup io_group
    635592\brief Read and write files in DIMACS format
    … …  
    693650
    694651/**
     652\anchor demoprograms
     653
     654@defgroup demos Demo Programs
     655
     656Some demo programs are listed here. Their full source codes can be found in
     657the \c demo subdirectory of the source tree.
     658
     659In order to compile them, use the <tt>make demo</tt> or the
     660<tt>make check</tt> commands.
     661*/
     662
     663/**
    695664@defgroup tools Standalone Utility Applications
    696665
    … …  
    701670*/
    702671
    703 /**
    704 \anchor demoprograms
    705 
    706 @defgroup demos Demo Programs
    707 
    708 Some demo programs are listed here. Their full source codes can be found in
    709 the \c demo subdirectory of the source tree.
    710 
    711 In order to compile them, use the <tt>make demo</tt> or the
    712 <tt>make check</tt> commands.
    713 */
    714 
    715672}

  • lemon/Makefile.am

    r708 r681  
    5858        lemon/arg_parser.h \
    5959        lemon/assert.h \
    60         lemon/bellman_ford.h \
    6160        lemon/bfs.h \
    6261        lemon/bin_heap.h \
    63         lemon/binom_heap.h \
    6462        lemon/bucket_heap.h \
    6563        lemon/cbc.h \
    … …  
    8179        lemon/euler.h \
    8280        lemon/fib_heap.h \
    83         lemon/fourary_heap.h \
    8481        lemon/full_graph.h \
    8582        lemon/glpk.h \
    … …  
    8885        lemon/grid_graph.h \
    8986        lemon/hypercube_graph.h \
    90         lemon/kary_heap.h \
    9187        lemon/kruskal.h \
    9288        lemon/hao_orlin.h \
    … …  
    9793        lemon/lp_base.h \
    9894        lemon/lp_skeleton.h \
     95        lemon/list_graph.h \
    9996        lemon/maps.h \
    10097        lemon/matching.h \
    … …  
    103100        lemon/nauty_reader.h \
    104101        lemon/network_simplex.h \
    105         lemon/pairing_heap.h \
    106102        lemon/path.h \
    107103        lemon/preflow.h \

  • lemon/bfs.h

    r717 r503  
    4848    ///The type of the map that stores the predecessor
    4949    ///arcs of the shortest paths.
    50     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     50    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    5151    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    5252    ///Instantiates a \c PredMap.
    … …  
    6363
    6464    ///The type of the map that indicates which nodes are processed.
    65     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    66     ///By default it is a NullMap.
     65    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    6766    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    6867    ///Instantiates a \c ProcessedMap.
    … …  
    8382
    8483    ///The type of the map that indicates which nodes are reached.
    85     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     84    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8685    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    8786    ///Instantiates a \c ReachedMap.
    … …  
    9897
    9998    ///The type of the map that stores the distances of the nodes.
    100     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     99    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    101100    typedef typename Digraph::template NodeMap<int> DistMap;
    102101    ///Instantiates a \c DistMap.
    … …  
    227226    ///\ref named-templ-param "Named parameter" for setting
    228227    ///\c PredMap type.
    229     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     228    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    230229    template <class T>
    231230    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
    … …  
    247246    ///\ref named-templ-param "Named parameter" for setting
    248247    ///\c DistMap type.
    249     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     248    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    250249    template <class T>
    251250    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
    … …  
    267266    ///\ref named-templ-param "Named parameter" for setting
    268267    ///\c ReachedMap type.
    269     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     268    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    270269    template <class T>
    271270    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
    … …  
    287286    ///\ref named-templ-param "Named parameter" for setting
    288287    ///\c ProcessedMap type.
    289     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     288    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    290289    template <class T>
    291290    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
    … …  
    415414    ///The simplest way to execute the BFS algorithm is to use one of the
    416415    ///member functions called \ref run(Node) "run()".\n
    417     ///If you need better control on the execution, you have to call
    418     ///\ref init() first, then you can add several source nodes with
     416    ///If you need more control on the execution, first you have to call
     417    ///\ref init(), then you can add several source nodes with
    419418    ///\ref addSource(). Finally the actual path computation can be
    420419    ///performed with one of the \ref start() functions.
    … …  
    739738    ///@{
    740739
    741     ///The shortest path to the given node.
    742 
    743     ///Returns the shortest path to the given node from the root(s).
     740    ///The shortest path to a node.
     741
     742    ///Returns the shortest path to a node.
    744743    ///
    745744    ///\warning \c t should be reached from the root(s).
    … …  
    749748    Path path(Node t) const { return Path(*G, *_pred, t); }
    750749
    751     ///The distance of the given node from the root(s).
    752 
    753     ///Returns the distance of the given node from the root(s).
     750    ///The distance of a node from the root(s).
     751
     752    ///Returns the distance of a node from the root(s).
    754753    ///
    755754    ///\warning If node \c v is not reached from the root(s), then
    … …  
    760759    int dist(Node v) const { return (*_dist)[v]; }
    761760
    762     ///\brief Returns the 'previous arc' of the shortest path tree for
    763     ///the given node.
    764     ///
     761    ///Returns the 'previous arc' of the shortest path tree for a node.
     762
    765763    ///This function returns the 'previous arc' of the shortest path
    766764    ///tree for the node \c v, i.e. it returns the last arc of a
    … …  
    769767    ///
    770768    ///The shortest path tree used here is equal to the shortest path
    771     ///tree used in \ref predNode() and \ref predMap().
     769    ///tree used in \ref predNode().
    772770    ///
    773771    ///\pre Either \ref run(Node) "run()" or \ref init()
    … …  
    775773    Arc predArc(Node v) const { return (*_pred)[v];}
    776774
    777     ///\brief Returns the 'previous node' of the shortest path tree for
    778     ///the given node.
    779     ///
     775    ///Returns the 'previous node' of the shortest path tree for a node.
     776
    780777    ///This function returns the 'previous node' of the shortest path
    781778    ///tree for the node \c v, i.e. it returns the last but one node
    782     ///of a shortest path from a root to \c v. It is \c INVALID
     779    ///from a shortest path from a root to \c v. It is \c INVALID
    783780    ///if \c v is not reached from the root(s) or if \c v is a root.
    784781    ///
    785782    ///The shortest path tree used here is equal to the shortest path
    786     ///tree used in \ref predArc() and \ref predMap().
     783    ///tree used in \ref predArc().
    787784    ///
    788785    ///\pre Either \ref run(Node) "run()" or \ref init()
    … …  
    805802    ///
    806803    ///Returns a const reference to the node map that stores the predecessor
    807     ///arcs, which form the shortest path tree (forest).
     804    ///arcs, which form the shortest path tree.
    808805    ///
    809806    ///\pre Either \ref run(Node) "run()" or \ref init()
    … …  
    811808    const PredMap &predMap() const { return *_pred;}
    812809
    813     ///Checks if the given node is reached from the root(s).
     810    ///Checks if a node is reached from the root(s).
    814811
    815812    ///Returns \c true if \c v is reached from the root(s).
    … …  
    837834    ///The type of the map that stores the predecessor
    838835    ///arcs of the shortest paths.
    839     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     836    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    840837    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    841838    ///Instantiates a PredMap.
    … …  
    852849
    853850    ///The type of the map that indicates which nodes are processed.
    854     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     851    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    855852    ///By default it is a NullMap.
    856853    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    … …  
    872869
    873870    ///The type of the map that indicates which nodes are reached.
    874     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     871    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    875872    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    876873    ///Instantiates a ReachedMap.
    … …  
    887884
    888885    ///The type of the map that stores the distances of the nodes.
    889     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     886    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    890887    typedef typename Digraph::template NodeMap<int> DistMap;
    891888    ///Instantiates a DistMap.
    … …  
    902899
    903900    ///The type of the shortest paths.
    904     ///It must conform to the \ref concepts::Path "Path" concept.
     901    ///It must meet the \ref concepts::Path "Path" concept.
    905902    typedef lemon::Path<Digraph> Path;
    906903  };
    … …  
    908905  /// Default traits class used by BfsWizard
    909906
    910   /// Default traits class used by BfsWizard.
    911   /// \tparam GR The type of the digraph.
     907  /// To make it easier to use Bfs algorithm
     908  /// we have created a wizard class.
     909  /// This \ref BfsWizard class needs default traits,
     910  /// as well as the \ref Bfs class.
     911  /// The \ref BfsWizardBase is a class to be the default traits of the
     912  /// \ref BfsWizard class.
    912913  template<class GR>
    913914  class BfsWizardBase : public BfsWizardDefaultTraits<GR>
    … …  
    937938    /// Constructor.
    938939
    939     /// This constructor does not require parameters, it initiates
     940    /// This constructor does not require parameters, therefore it initiates
    940941    /// all of the attributes to \c 0.
    941942    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
    … …  
    967968    typedef TR Base;
    968969
     970    ///The type of the digraph the algorithm runs on.
    969971    typedef typename TR::Digraph Digraph;
    970972
    … …  
    974976    typedef typename Digraph::OutArcIt OutArcIt;
    975977
     978    ///\brief The type of the map that stores the predecessor
     979    ///arcs of the shortest paths.
    976980    typedef typename TR::PredMap PredMap;
     981    ///\brief The type of the map that stores the distances of the nodes.
    977982    typedef typename TR::DistMap DistMap;
     983    ///\brief The type of the map that indicates which nodes are reached.
    978984    typedef typename TR::ReachedMap ReachedMap;
     985    ///\brief The type of the map that indicates which nodes are processed.
    979986    typedef typename TR::ProcessedMap ProcessedMap;
     987    ///The type of the shortest paths
    980988    typedef typename TR::Path Path;
    981989
    … …  
    10601068      SetPredMapBase(const TR &b) : TR(b) {}
    10611069    };
    1062 
    1063     ///\brief \ref named-templ-param "Named parameter" for setting
    1064     ///the predecessor map.
    1065     ///
    1066     ///\ref named-templ-param "Named parameter" function for setting
    1067     ///the map that stores the predecessor arcs of the nodes.
     1070    ///\brief \ref named-func-param "Named parameter"
     1071    ///for setting PredMap object.
     1072    ///
     1073    ///\ref named-func-param "Named parameter"
     1074    ///for setting PredMap object.
    10681075    template<class T>
    10691076    BfsWizard<SetPredMapBase<T> > predMap(const T &t)
    … …  
    10791086      SetReachedMapBase(const TR &b) : TR(b) {}
    10801087    };
    1081 
    1082     ///\brief \ref named-templ-param "Named parameter" for setting
    1083     ///the reached map.
    1084     ///
    1085     ///\ref named-templ-param "Named parameter" function for setting
    1086     ///the map that indicates which nodes are reached.
     1088    ///\brief \ref named-func-param "Named parameter"
     1089    ///for setting ReachedMap object.
     1090    ///
     1091    /// \ref named-func-param "Named parameter"
     1092    ///for setting ReachedMap object.
    10871093    template<class T>
    10881094    BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
    … …  
    10981104      SetDistMapBase(const TR &b) : TR(b) {}
    10991105    };
    1100 
    1101     ///\brief \ref named-templ-param "Named parameter" for setting
    1102     ///the distance map.
    1103     ///
    1104     ///\ref named-templ-param "Named parameter" function for setting
    1105     ///the map that stores the distances of the nodes calculated
    1106     ///by the algorithm.
     1106    ///\brief \ref named-func-param "Named parameter"
     1107    ///for setting DistMap object.
     1108    ///
     1109    /// \ref named-func-param "Named parameter"
     1110    ///for setting DistMap object.
    11071111    template<class T>
    11081112    BfsWizard<SetDistMapBase<T> > distMap(const T &t)
    … …  
    11181122      SetProcessedMapBase(const TR &b) : TR(b) {}
    11191123    };
    1120 
    1121     ///\brief \ref named-func-param "Named parameter" for setting
    1122     ///the processed map.
    1123     ///
    1124     ///\ref named-templ-param "Named parameter" function for setting
    1125     ///the map that indicates which nodes are processed.
     1124    ///\brief \ref named-func-param "Named parameter"
     1125    ///for setting ProcessedMap object.
     1126    ///
     1127    /// \ref named-func-param "Named parameter"
     1128    ///for setting ProcessedMap object.
    11261129    template<class T>
    11271130    BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
    … …  
    12621265    ///
    12631266    /// The type of the map that indicates which nodes are reached.
    1264     /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     1267    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12651268    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12661269
    … …  
    14231426    /// The simplest way to execute the BFS algorithm is to use one of the
    14241427    /// member functions called \ref run(Node) "run()".\n
    1425     /// If you need better control on the execution, you have to call
    1426     /// \ref init() first, then you can add several source nodes with
     1428    /// If you need more control on the execution, first you have to call
     1429    /// \ref init(), then you can add several source nodes with
    14271430    /// \ref addSource(). Finally the actual path computation can be
    14281431    /// performed with one of the \ref start() functions.
    … …  
    17331736    ///@{
    17341737
    1735     /// \brief Checks if the given node is reached from the root(s).
     1738    /// \brief Checks if a node is reached from the root(s).
    17361739    ///
    17371740    /// Returns \c true if \c v is reached from the root(s).

  • lemon/bin_heap.h

    r711 r683  
    2020#define LEMON_BIN_HEAP_H
    2121
    22 ///\ingroup heaps
     22///\ingroup auxdat
    2323///\file
    24 ///\brief Binary heap implementation.
     24///\brief Binary Heap implementation.
    2525
    2626#include <vector>
    … …  
    3030namespace lemon {
    3131
    32   /// \ingroup heaps
    33   ///
    34   /// \brief Binary heap data structure.
    35   ///
    36   /// This class implements the \e binary \e heap data structure.
    37   /// It fully conforms to the \ref concepts::Heap "heap concept".
    38   ///
    39   /// \tparam PR Type of the priorities of the items.
    40   /// \tparam IM A read-writable item map with \c int values, used
    41   /// internally to handle the cross references.
    42   /// \tparam CMP A functor class for comparing the priorities.
    43   /// The default is \c std::less<PR>.
    44 #ifdef DOXYGEN
    45   template <typename PR, typename IM, typename CMP>
    46 #else
     32  ///\ingroup auxdat
     33  ///
     34  ///\brief A Binary Heap implementation.
     35  ///
     36  ///This class implements the \e binary \e heap data structure.
     37  ///
     38  ///A \e heap is a data structure for storing items with specified values
     39  ///called \e priorities in such a way that finding the item with minimum
     40  ///priority is efficient. \c CMP specifies the ordering of the priorities.
     41  ///In a heap one can change the priority of an item, add or erase an
     42  ///item, etc.
     43  ///
     44  ///\tparam PR Type of the priority of the items.
     45  ///\tparam IM A read and writable item map with int values, used internally
     46  ///to handle the cross references.
     47  ///\tparam CMP A functor class for the ordering of the priorities.
     48  ///The default is \c std::less<PR>.
     49  ///
     50  ///\sa FibHeap
     51  ///\sa Dijkstra
    4752  template <typename PR, typename IM, typename CMP = std::less<PR> >
    48 #endif
    4953  class BinHeap {
     54
    5055  public:
    51 
    52     /// Type of the item-int map.
     56    ///\e
    5357    typedef IM ItemIntMap;
    54     /// Type of the priorities.
     58    ///\e
    5559    typedef PR Prio;
    56     /// Type of the items stored in the heap.
     60    ///\e
    5761    typedef typename ItemIntMap::Key Item;
    58     /// Type of the item-priority pairs.
     62    ///\e
    5963    typedef std::pair<Item,Prio> Pair;
    60     /// Functor type for comparing the priorities.
     64    ///\e
    6165    typedef CMP Compare;
    6266
    63     /// \brief Type to represent the states of the items.
    64     ///
    65     /// Each item has a state associated to it. It can be "in heap",
    66     /// "pre-heap" or "post-heap". The latter two are indifferent from the
     67    /// \brief Type to represent the items states.
     68    ///
     69    /// Each Item element have a state associated to it. It may be "in heap",
     70    /// "pre heap" or "post heap". The latter two are indifferent from the
    6771    /// heap's point of view, but may be useful to the user.
    6872    ///
    … …  
    8185
    8286  public:
    83 
    84     /// \brief Constructor.
    85     ///
    86     /// Constructor.
    87     /// \param map A map that assigns \c int values to the items.
    88     /// It is used internally to handle the cross references.
    89     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     87    /// \brief The constructor.
     88    ///
     89    /// The constructor.
     90    /// \param map should be given to the constructor, since it is used
     91    /// internally to handle the cross references. The value of the map
     92    /// must be \c PRE_HEAP (<tt>-1</tt>) for every item.
    9093    explicit BinHeap(ItemIntMap &map) : _iim(map) {}
    9194
    92     /// \brief Constructor.
    93     ///
    94     /// Constructor.
    95     /// \param map A map that assigns \c int values to the items.
    96     /// It is used internally to handle the cross references.
    97     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    98     /// \param comp The function object used for comparing the priorities.
     95    /// \brief The constructor.
     96    ///
     97    /// The constructor.
     98    /// \param map should be given to the constructor, since it is used
     99    /// internally to handle the cross references. The value of the map
     100    /// should be PRE_HEAP (-1) for each element.
     101    ///
     102    /// \param comp The comparator function object.
    99103    BinHeap(ItemIntMap &map, const Compare &comp)
    100104      : _iim(map), _comp(comp) {}
    101105
    102106
    103     /// \brief The number of items stored in the heap.
    104     ///
    105     /// This function returns the number of items stored in the heap.
     107    /// The number of items stored in the heap.
     108    ///
     109    /// \brief Returns the number of items stored in the heap.
    106110    int size() const { return _data.size(); }
    107111
    108     /// \brief Check if the heap is empty.
    109     ///
    110     /// This function returns \c true if the heap is empty.
     112    /// \brief Checks if the heap stores no items.
     113    ///
     114    /// Returns \c true if and only if the heap stores no items.
    111115    bool empty() const { return _data.empty(); }
    112116
    113     /// \brief Make the heap empty.
    114     ///
    115     /// This functon makes the heap empty.
    116     /// It does not change the cross reference map. If you want to reuse
    117     /// a heap that is not surely empty, you should first clear it and
    118     /// then you should set the cross reference map to \c PRE_HEAP
    119     /// for each item.
     117    /// \brief Make empty this heap.
     118    ///
     119    /// Make empty this heap. It does not change the cross reference map.
     120    /// If you want to reuse what is not surely empty you should first clear
     121    /// the heap and after that you should set the cross reference map for
     122    /// each item to \c PRE_HEAP.
    120123    void clear() {
    121124      _data.clear();
    … …  
    125128    static int parent(int i) { return (i-1)/2; }
    126129
    127     static int secondChild(int i) { return 2*i+2; }
     130    static int second_child(int i) { return 2*i+2; }
    128131    bool less(const Pair &p1, const Pair &p2) const {
    129132      return _comp(p1.second, p2.second);
    130133    }
    131134
    132     int bubbleUp(int hole, Pair p) {
     135    int bubble_up(int hole, Pair p) {
    133136      int par = parent(hole);
    134137      while( hole>0 && less(p,_data[par]) ) {
    … …  
    141144    }
    142145
    143     int bubbleDown(int hole, Pair p, int length) {
    144       int child = secondChild(hole);
     146    int bubble_down(int hole, Pair p, int length) {
     147      int child = second_child(hole);
    145148      while(child < length) {
    146149        if( less(_data[child-1], _data[child]) ) {
    … …  
    151154        move(_data[child], hole);
    152155        hole = child;
    153         child = secondChild(hole);
     156        child = second_child(hole);
    154157      }
    155158      child--;
    … …  
    169172
    170173  public:
    171 
    172174    /// \brief Insert a pair of item and priority into the heap.
    173175    ///
    174     /// This function inserts \c p.first to the heap with priority
    175     /// \c p.second.
     176    /// Adds \c p.first to the heap with priority \c p.second.
    176177    /// \param p The pair to insert.
    177     /// \pre \c p.first must not be stored in the heap.
    178178    void push(const Pair &p) {
    179179      int n = _data.size();
    180180      _data.resize(n+1);
    181       bubbleUp(n, p);
    182     }
    183 
    184     /// \brief Insert an item into the heap with the given priority.
    185     ///
    186     /// This function inserts the given item into the heap with the
    187     /// given priority.
     181      bubble_up(n, p);
     182    }
     183
     184    /// \brief Insert an item into the heap with the given heap.
     185    ///
     186    /// Adds \c i to the heap with priority \c p.
    188187    /// \param i The item to insert.
    189188    /// \param p The priority of the item.
    190     /// \pre \e i must not be stored in the heap.
    191189    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
    192190
    193     /// \brief Return the item having minimum priority.
    194     ///
    195     /// This function returns the item having minimum priority.
    196     /// \pre The heap must be non-empty.
     191    /// \brief Returns the item with minimum priority relative to \c Compare.
     192    ///
     193    /// This method returns the item with minimum priority relative to \c
     194    /// Compare.
     195    /// \pre The heap must be nonempty.
    197196    Item top() const {
    198197      return _data[0].first;
    199198    }
    200199
    201     /// \brief The minimum priority.
    202     ///
    203     /// This function returns the minimum priority.
    204     /// \pre The heap must be non-empty.
     200    /// \brief Returns the minimum priority relative to \c Compare.
     201    ///
     202    /// It returns the minimum priority relative to \c Compare.
     203    /// \pre The heap must be nonempty.
    205204    Prio prio() const {
    206205      return _data[0].second;
    207206    }
    208207
    209     /// \brief Remove the item having minimum priority.
    210     ///
    211     /// This function removes the item having minimum priority.
     208    /// \brief Deletes the item with minimum priority relative to \c Compare.
     209    ///
     210    /// This method deletes the item with minimum priority relative to \c
     211    /// Compare from the heap.
    212212    /// \pre The heap must be non-empty.
    213213    void pop() {
    … …  
    215215      _iim.set(_data[0].first, POST_HEAP);
    216216      if (n > 0) {
    217         bubbleDown(0, _data[n], n);
     217        bubble_down(0, _data[n], n);
    218218      }
    219219      _data.pop_back();
    220220    }
    221221
    222     /// \brief Remove the given item from the heap.
    223     ///
    224     /// This function removes the given item from the heap if it is
    225     /// already stored.
    226     /// \param i The item to delete.
    227     /// \pre \e i must be in the heap.
     222    /// \brief Deletes \c i from the heap.
     223    ///
     224    /// This method deletes item \c i from the heap.
     225    /// \param i The item to erase.
     226    /// \pre The item should be in the heap.
    228227    void erase(const Item &i) {
    229228      int h = _iim[i];
    … …  
    231230      _iim.set(_data[h].first, POST_HEAP);
    232231      if( h < n ) {
    233         if ( bubbleUp(h, _data[n]) == h) {
    234           bubbleDown(h, _data[n], n);
     232        if ( bubble_up(h, _data[n]) == h) {
     233          bubble_down(h, _data[n], n);
    235234        }
    236235      }
    … …  
    238237    }
    239238
    240     /// \brief The priority of the given item.
    241     ///
    242     /// This function returns the priority of the given item.
    243     /// \param i The item.
    244     /// \pre \e i must be in the heap.
     239
     240    /// \brief Returns the priority of \c i.
     241    ///
     242    /// This function returns the priority of item \c i.
     243    /// \param i The item.
     244    /// \pre \c i must be in the heap.
    245245    Prio operator[](const Item &i) const {
    246246      int idx = _iim[i];
    … …  
    248248    }
    249249
    250     /// \brief Set the priority of an item or insert it, if it is
    251     /// not stored in the heap.
    252     ///
    253     /// This method sets the priority of the given item if it is
    254     /// already stored in the heap. Otherwise it inserts the given
    255     /// item into the heap with the given priority.
     250    /// \brief \c i gets to the heap with priority \c p independently
     251    /// if \c i was already there.
     252    ///
     253    /// This method calls \ref push(\c i, \c p) if \c i is not stored
     254    /// in the heap and sets the priority of \c i to \c p otherwise.
    256255    /// \param i The item.
    257256    /// \param p The priority.
    … …  
    262261      }
    263262      else if( _comp(p, _data[idx].second) ) {
    264         bubbleUp(idx, Pair(i,p));
     263        bubble_up(idx, Pair(i,p));
    265264      }
    266265      else {
    267         bubbleDown(idx, Pair(i,p), _data.size());
    268       }
    269     }
    270 
    271     /// \brief Decrease the priority of an item to the given value.
    272     ///
    273     /// This function decreases the priority of an item to the given value.
     266        bubble_down(idx, Pair(i,p), _data.size());
     267      }
     268    }
     269
     270    /// \brief Decreases the priority of \c i to \c p.
     271    ///
     272    /// This method decreases the priority of item \c i to \c p.
    274273    /// \param i The item.
    275274    /// \param p The priority.
    276     /// \pre \e i must be stored in the heap with priority at least \e p.
     275    /// \pre \c i must be stored in the heap with priority at least \c
     276    /// p relative to \c Compare.
    277277    void decrease(const Item &i, const Prio &p) {
    278278      int idx = _iim[i];
    279       bubbleUp(idx, Pair(i,p));
    280     }
    281 
    282     /// \brief Increase the priority of an item to the given value.
    283     ///
    284     /// This function increases the priority of an item to the given value.
     279      bubble_up(idx, Pair(i,p));
     280    }
     281
     282    /// \brief Increases the priority of \c i to \c p.
     283    ///
     284    /// This method sets the priority of item \c i to \c p.
    285285    /// \param i The item.
    286286    /// \param p The priority.
    287     /// \pre \e i must be stored in the heap with priority at most \e p.
     287    /// \pre \c i must be stored in the heap with priority at most \c
     288    /// p relative to \c Compare.
    288289    void increase(const Item &i, const Prio &p) {
    289290      int idx = _iim[i];
    290       bubbleDown(idx, Pair(i,p), _data.size());
    291     }
    292 
    293     /// \brief Return the state of an item.
    294     ///
    295     /// This method returns \c PRE_HEAP if the given item has never
    296     /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
    297     /// and \c POST_HEAP otherwise.
    298     /// In the latter case it is possible that the item will get back
    299     /// to the heap again.
     291      bubble_down(idx, Pair(i,p), _data.size());
     292    }
     293
     294    /// \brief Returns if \c item is in, has already been in, or has
     295    /// never been in the heap.
     296    ///
     297    /// This method returns PRE_HEAP if \c item has never been in the
     298    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
     299    /// otherwise. In the latter case it is possible that \c item will
     300    /// get back to the heap again.
    300301    /// \param i The item.
    301302    State state(const Item &i) const {
    … …  
    306307    }
    307308
    308     /// \brief Set the state of an item in the heap.
    309     ///
    310     /// This function sets the state of the given item in the heap.
    311     /// It can be used to manually clear the heap when it is important
    312     /// to achive better time complexity.
     309    /// \brief Sets the state of the \c item in the heap.
     310    ///
     311    /// Sets the state of the \c item in the heap. It can be used to
     312    /// manually clear the heap when it is important to achive the
     313    /// better time complexity.
    313314    /// \param i The item.
    314315    /// \param st The state. It should not be \c IN_HEAP.
    … …  
    327328    }
    328329
    329     /// \brief Replace an item in the heap.
    330     ///
    331     /// This function replaces item \c i with item \c j.
    332     /// Item \c i must be in the heap, while \c j must be out of the heap.
    333     /// After calling this method, item \c i will be out of the
    334     /// heap and \c j will be in the heap with the same prioriority
    335     /// as item \c i had before.
     330    /// \brief Replaces an item in the heap.
     331    ///
     332    /// The \c i item is replaced with \c j item. The \c i item should
     333    /// be in the heap, while the \c j should be out of the heap. The
     334    /// \c i item will out of the heap and \c j will be in the heap
     335    /// with the same prioriority as prevoiusly the \c i item.
    336336    void replace(const Item& i, const Item& j) {
    337337      int idx = _iim[i];

  • lemon/bits/edge_set_extender.h

    r685 r617  
    538538
    539539    public:
    540       explicit ArcMap(const Graph& _g)
     540      ArcMap(const Graph& _g)
    541541        : Parent(_g) {}
    542542      ArcMap(const Graph& _g, const _Value& _v)
    … …  
    562562
    563563    public:
    564       explicit EdgeMap(const Graph& _g)
     564      EdgeMap(const Graph& _g)
    565565        : Parent(_g) {}
    566566

  • lemon/bits/graph_extender.h

    r685 r617  
    605605
    606606    public:
    607       explicit NodeMap(const Graph& graph)
     607      NodeMap(const Graph& graph)
    608608        : Parent(graph) {}
    609609      NodeMap(const Graph& graph, const _Value& value)
    … …  
    629629
    630630    public:
    631       explicit ArcMap(const Graph& graph)
     631      ArcMap(const Graph& graph)
    632632        : Parent(graph) {}
    633633      ArcMap(const Graph& graph, const _Value& value)
    … …  
    653653
    654654    public:
    655       explicit EdgeMap(const Graph& graph)
     655      EdgeMap(const Graph& graph)
    656656        : Parent(graph) {}
    657657

  • lemon/bits/map_extender.h

    r718 r617  
    5050    typedef typename Parent::ConstReference ConstReference;
    5151
    52     typedef typename Parent::ReferenceMapTag ReferenceMapTag;
    53 
    5452    class MapIt;
    5553    class ConstMapIt;
    … …  
    194192    typedef typename Parent::ConstReference ConstReference;
    195193
    196     typedef typename Parent::ReferenceMapTag ReferenceMapTag;
    197 
    198194    class MapIt;
    199195    class ConstMapIt;

  • lemon/bucket_heap.h

    r711 r683  
    2020#define LEMON_BUCKET_HEAP_H
    2121
    22 ///\ingroup heaps
     22///\ingroup auxdat
    2323///\file
    24 ///\brief Bucket heap implementation.
     24///\brief Bucket Heap implementation.
    2525
    2626#include <vector>
    … …  
    5454  }
    5555
    56   /// \ingroup heaps
    57   ///
    58   /// \brief Bucket heap data structure.
    59   ///
    60   /// This class implements the \e bucket \e heap data structure.
    61   /// It practically conforms to the \ref concepts::Heap "heap concept",
    62   /// but it has some limitations.
    63   ///
    64   /// The bucket heap is a very simple structure. It can store only
    65   /// \c int priorities and it maintains a list of items for each priority
    66   /// in the range <tt>[0..C)</tt>. So it should only be used when the
    67   /// priorities are small. It is not intended to use as a Dijkstra heap.
    68   ///
    69   /// \tparam IM A read-writable item map with \c int values, used
    70   /// internally to handle the cross references.
    71   /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
    72   /// The default is \e min-heap. If this parameter is set to \c false,
    73   /// then the comparison is reversed, so the top(), prio() and pop()
    74   /// functions deal with the item having maximum priority instead of the
    75   /// minimum.
    76   ///
    77   /// \sa SimpleBucketHeap
     56  /// \ingroup auxdat
     57  ///
     58  /// \brief A Bucket Heap implementation.
     59  ///
     60  /// This class implements the \e bucket \e heap data structure. A \e heap
     61  /// is a data structure for storing items with specified values called \e
     62  /// priorities in such a way that finding the item with minimum priority is
     63  /// efficient. The bucket heap is very simple implementation, it can store
     64  /// only integer priorities and it stores for each priority in the
     65  /// \f$ [0..C) \f$ range a list of items. So it should be used only when
     66  /// the priorities are small. It is not intended to use as dijkstra heap.
     67  ///
     68  /// \param IM A read and write Item int map, used internally
     69  /// to handle the cross references.
     70  /// \param MIN If the given parameter is false then instead of the
     71  /// minimum value the maximum can be retrivied with the top() and
     72  /// prio() member functions.
    7873  template <typename IM, bool MIN = true>
    7974  class BucketHeap {
    8075
    8176  public:
    82 
    83     /// Type of the item-int map.
     77    /// \e
     78    typedef typename IM::Key Item;
     79    /// \e
     80    typedef int Prio;
     81    /// \e
     82    typedef std::pair<Item, Prio> Pair;
     83    /// \e
    8484    typedef IM ItemIntMap;
    85     /// Type of the priorities.
    86     typedef int Prio;
    87     /// Type of the items stored in the heap.
    88     typedef typename ItemIntMap::Key Item;
    89     /// Type of the item-priority pairs.
    90     typedef std::pair<Item,Prio> Pair;
    9185
    9286  private:
    … …  
    9690  public:
    9791
    98     /// \brief Type to represent the states of the items.
    99     ///
    100     /// Each item has a state associated to it. It can be "in heap",
    101     /// "pre-heap" or "post-heap". The latter two are indifferent from the
     92    /// \brief Type to represent the items states.
     93    ///
     94    /// Each Item element have a state associated to it. It may be "in heap",
     95    /// "pre heap" or "post heap". The latter two are indifferent from the
    10296    /// heap's point of view, but may be useful to the user.
    10397    ///
    … …  
    111105
    112106  public:
    113 
    114     /// \brief Constructor.
    115     ///
    116     /// Constructor.
    117     /// \param map A map that assigns \c int values to the items.
    118     /// It is used internally to handle the cross references.
    119     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     107    /// \brief The constructor.
     108    ///
     109    /// The constructor.
     110    /// \param map should be given to the constructor, since it is used
     111    /// internally to handle the cross references. The value of the map
     112    /// should be PRE_HEAP (-1) for each element.
    120113    explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {}
    121114
    122     /// \brief The number of items stored in the heap.
    123     ///
    124     /// This function returns the number of items stored in the heap.
     115    /// The number of items stored in the heap.
     116    ///
     117    /// \brief Returns the number of items stored in the heap.
    125118    int size() const { return _data.size(); }
    126119
    127     /// \brief Check if the heap is empty.
    128     ///
    129     /// This function returns \c true if the heap is empty.
     120    /// \brief Checks if the heap stores no items.
     121    ///
     122    /// Returns \c true if and only if the heap stores no items.
    130123    bool empty() const { return _data.empty(); }
    131124
    132     /// \brief Make the heap empty.
    133     ///
    134     /// This functon makes the heap empty.
    135     /// It does not change the cross reference map. If you want to reuse
    136     /// a heap that is not surely empty, you should first clear it and
    137     /// then you should set the cross reference map to \c PRE_HEAP
    138     /// for each item.
     125    /// \brief Make empty this heap.
     126    ///
     127    /// Make empty this heap. It does not change the cross reference
     128    /// map.  If you want to reuse a heap what is not surely empty you
     129    /// should first clear the heap and after that you should set the
     130    /// cross reference map for each item to \c PRE_HEAP.
    139131    void clear() {
    140132      _data.clear(); _first.clear(); _minimum = 0;
    … …  
    143135  private:
    144136
    145     void relocateLast(int idx) {
     137    void relocate_last(int idx) {
    146138      if (idx + 1 < int(_data.size())) {
    147139        _data[idx] = _data.back();
    … …  
    183175
    184176  public:
    185 
    186177    /// \brief Insert a pair of item and priority into the heap.
    187178    ///
    188     /// This function inserts \c p.first to the heap with priority
    189     /// \c p.second.
     179    /// Adds \c p.first to the heap with priority \c p.second.
    190180    /// \param p The pair to insert.
    191     /// \pre \c p.first must not be stored in the heap.
    192181    void push(const Pair& p) {
    193182      push(p.first, p.second);
    … …  
    196185    /// \brief Insert an item into the heap with the given priority.
    197186    ///
    198     /// This function inserts the given item into the heap with the
    199     /// given priority.
     187    /// Adds \c i to the heap with priority \c p.
    200188    /// \param i The item to insert.
    201189    /// \param p The priority of the item.
    202     /// \pre \e i must not be stored in the heap.
    203190    void push(const Item &i, const Prio &p) {
    204191      int idx = _data.size();
    … …  
    211198    }
    212199
    213     /// \brief Return the item having minimum priority.
    214     ///
    215     /// This function returns the item having minimum priority.
    216     /// \pre The heap must be non-empty.
     200    /// \brief Returns the item with minimum priority.
     201    ///
     202    /// This method returns the item with minimum priority.
     203    /// \pre The heap must be nonempty.
    217204    Item top() const {
    218205      while (_first[_minimum] == -1) {
    … …  
    222209    }
    223210
    224     /// \brief The minimum priority.
    225     ///
    226     /// This function returns the minimum priority.
    227     /// \pre The heap must be non-empty.
     211    /// \brief Returns the minimum priority.
     212    ///
     213    /// It returns the minimum priority.
     214    /// \pre The heap must be nonempty.
    228215    Prio prio() const {
    229216      while (_first[_minimum] == -1) {
    … …  
    233220    }
    234221
    235     /// \brief Remove the item having minimum priority.
    236     ///
    237     /// This function removes the item having minimum priority.
     222    /// \brief Deletes the item with minimum priority.
     223    ///
     224    /// This method deletes the item with minimum priority from the heap.
    238225    /// \pre The heap must be non-empty.
    239226    void pop() {
    … …  
    244231      _iim[_data[idx].item] = -2;
    245232      unlace(idx);
    246       relocateLast(idx);
    247     }
    248 
    249     /// \brief Remove the given item from the heap.
    250     ///
    251     /// This function removes the given item from the heap if it is
    252     /// already stored.
    253     /// \param i The item to delete.
    254     /// \pre \e i must be in the heap.
     233      relocate_last(idx);
     234    }
     235
     236    /// \brief Deletes \c i from the heap.
     237    ///
     238    /// This method deletes item \c i from the heap, if \c i was
     239    /// already stored in the heap.
     240    /// \param i The item to erase.
    255241    void erase(const Item &i) {
    256242      int idx = _iim[i];
    257243      _iim[_data[idx].item] = -2;
    258244      unlace(idx);
    259       relocateLast(idx);
    260     }
    261 
    262     /// \brief The priority of the given item.
    263     ///
    264     /// This function returns the priority of the given item.
    265     /// \param i The item.
    266     /// \pre \e i must be in the heap.
     245      relocate_last(idx);
     246    }
     247
     248
     249    /// \brief Returns the priority of \c i.
     250    ///
     251    /// This function returns the priority of item \c i.
     252    /// \pre \c i must be in the heap.
     253    /// \param i The item.
    267254    Prio operator[](const Item &i) const {
    268255      int idx = _iim[i];
    … …  
    270257    }
    271258
    272     /// \brief Set the priority of an item or insert it, if it is
    273     /// not stored in the heap.
    274     ///
    275     /// This method sets the priority of the given item if it is
    276     /// already stored in the heap. Otherwise it inserts the given
    277     /// item into the heap with the given priority.
     259    /// \brief \c i gets to the heap with priority \c p independently
     260    /// if \c i was already there.
     261    ///
     262    /// This method calls \ref push(\c i, \c p) if \c i is not stored
     263    /// in the heap and sets the priority of \c i to \c p otherwise.
    278264    /// \param i The item.
    279265    /// \param p The priority.
    … …  
    289275    }
    290276
    291     /// \brief Decrease the priority of an item to the given value.
    292     ///
    293     /// This function decreases the priority of an item to the given value.
     277    /// \brief Decreases the priority of \c i to \c p.
     278    ///
     279    /// This method decreases the priority of item \c i to \c p.
     280    /// \pre \c i must be stored in the heap with priority at least \c
     281    /// p relative to \c Compare.
    294282    /// \param i The item.
    295283    /// \param p The priority.
    296     /// \pre \e i must be stored in the heap with priority at least \e p.
    297284    void decrease(const Item &i, const Prio &p) {
    298285      int idx = _iim[i];
    … …  
    305292    }
    306293
    307     /// \brief Increase the priority of an item to the given value.
    308     ///
    309     /// This function increases the priority of an item to the given value.
     294    /// \brief Increases the priority of \c i to \c p.
     295    ///
     296    /// This method sets the priority of item \c i to \c p.
     297    /// \pre \c i must be stored in the heap with priority at most \c
     298    /// p relative to \c Compare.
    310299    /// \param i The item.
    311300    /// \param p The priority.
    312     /// \pre \e i must be stored in the heap with priority at most \e p.
    313301    void increase(const Item &i, const Prio &p) {
    314302      int idx = _iim[i];
    … …  
    318306    }
    319307
    320     /// \brief Return the state of an item.
    321     ///
    322     /// This method returns \c PRE_HEAP if the given item has never
    323     /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
    324     /// and \c POST_HEAP otherwise.
    325     /// In the latter case it is possible that the item will get back
    326     /// to the heap again.
     308    /// \brief Returns if \c item is in, has already been in, or has
     309    /// never been in the heap.
     310    ///
     311    /// This method returns PRE_HEAP if \c item has never been in the
     312    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
     313    /// otherwise. In the latter case it is possible that \c item will
     314    /// get back to the heap again.
    327315    /// \param i The item.
    328316    State state(const Item &i) const {
    … …  
    332320    }
    333321
    334     /// \brief Set the state of an item in the heap.
    335     ///
    336     /// This function sets the state of the given item in the heap.
    337     /// It can be used to manually clear the heap when it is important
    338     /// to achive better time complexity.
     322    /// \brief Sets the state of the \c item in the heap.
     323    ///
     324    /// Sets the state of the \c item in the heap. It can be used to
     325    /// manually clear the heap when it is important to achive the
     326    /// better time complexity.
    339327    /// \param i The item.
    340328    /// \param st The state. It should not be \c IN_HEAP.
    … …  
    372360  }; // class BucketHeap
    373361
    374   /// \ingroup heaps
    375   ///
    376   /// \brief Simplified bucket heap data structure.
     362  /// \ingroup auxdat
     363  ///
     364  /// \brief A Simplified Bucket Heap implementation.
    377365  ///
    378366  /// This class implements a simplified \e bucket \e heap data
    379   /// structure. It does not provide some functionality, but it is
    380   /// faster and simpler than BucketHeap. The main difference is
    381   /// that BucketHeap stores a doubly-linked list for each key while
    382   /// this class stores only simply-linked lists. It supports erasing
    383   /// only for the item having minimum priority and it does not support
    384   /// key increasing and decreasing.
    385   ///
    386   /// Note that this implementation does not conform to the
    387   /// \ref concepts::Heap "heap concept" due to the lack of some
    388   /// functionality.
    389   ///
    390   /// \tparam IM A read-writable item map with \c int values, used
    391   /// internally to handle the cross references.
    392   /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
    393   /// The default is \e min-heap. If this parameter is set to \c false,
    394   /// then the comparison is reversed, so the top(), prio() and pop()
    395   /// functions deal with the item having maximum priority instead of the
    396   /// minimum.
     367  /// structure.  It does not provide some functionality but it faster
     368  /// and simplier data structure than the BucketHeap. The main
     369  /// difference is that the BucketHeap stores for every key a double
     370  /// linked list while this class stores just simple lists. In the
     371  /// other way it does not support erasing each elements just the
     372  /// minimal and it does not supports key increasing, decreasing.
     373  ///
     374  /// \param IM A read and write Item int map, used internally
     375  /// to handle the cross references.
     376  /// \param MIN If the given parameter is false then instead of the
     377  /// minimum value the maximum can be retrivied with the top() and
     378  /// prio() member functions.
    397379  ///
    398380  /// \sa BucketHeap
    … …  
    401383
    402384  public:
    403 
    404     /// Type of the item-int map.
     385    typedef typename IM::Key Item;
     386    typedef int Prio;
     387    typedef std::pair<Item, Prio> Pair;
    405388    typedef IM ItemIntMap;
    406     /// Type of the priorities.
    407     typedef int Prio;
    408     /// Type of the items stored in the heap.
    409     typedef typename ItemIntMap::Key Item;
    410     /// Type of the item-priority pairs.
    411     typedef std::pair<Item,Prio> Pair;
    412389
    413390  private:
    … …  
    417394  public:
    418395
    419     /// \brief Type to represent the states of the items.
    420     ///
    421     /// Each item has a state associated to it. It can be "in heap",
    422     /// "pre-heap" or "post-heap". The latter two are indifferent from the
     396    /// \brief Type to represent the items states.
     397    ///
     398    /// Each Item element have a state associated to it. It may be "in heap",
     399    /// "pre heap" or "post heap". The latter two are indifferent from the
    423400    /// heap's point of view, but may be useful to the user.
    424401    ///
    … …  
    433410  public:
    434411
    435     /// \brief Constructor.
    436     ///
    437     /// Constructor.
    438     /// \param map A map that assigns \c int values to the items.
    439     /// It is used internally to handle the cross references.
    440     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     412    /// \brief The constructor.
     413    ///
     414    /// The constructor.
     415    /// \param map should be given to the constructor, since it is used
     416    /// internally to handle the cross references. The value of the map
     417    /// should be PRE_HEAP (-1) for each element.
    441418    explicit SimpleBucketHeap(ItemIntMap &map)
    442419      : _iim(map), _free(-1), _num(0), _minimum(0) {}
    443420
    444     /// \brief The number of items stored in the heap.
    445     ///
    446     /// This function returns the number of items stored in the heap.
     421    /// \brief Returns the number of items stored in the heap.
     422    ///
     423    /// The number of items stored in the heap.
    447424    int size() const { return _num; }
    448425
    449     /// \brief Check if the heap is empty.
    450     ///
    451     /// This function returns \c true if the heap is empty.
     426    /// \brief Checks if the heap stores no items.
     427    ///
     428    /// Returns \c true if and only if the heap stores no items.
    452429    bool empty() const { return _num == 0; }
    453430
    454     /// \brief Make the heap empty.
    455     ///
    456     /// This functon makes the heap empty.
    457     /// It does not change the cross reference map. If you want to reuse
    458     /// a heap that is not surely empty, you should first clear it and
    459     /// then you should set the cross reference map to \c PRE_HEAP
    460     /// for each item.
     431    /// \brief Make empty this heap.
     432    ///
     433    /// Make empty this heap. It does not change the cross reference
     434    /// map.  If you want to reuse a heap what is not surely empty you
     435    /// should first clear the heap and after that you should set the
     436    /// cross reference map for each item to \c PRE_HEAP.
    461437    void clear() {
    462438      _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0;
    … …  
    465441    /// \brief Insert a pair of item and priority into the heap.
    466442    ///
    467     /// This function inserts \c p.first to the heap with priority
    468     /// \c p.second.
     443    /// Adds \c p.first to the heap with priority \c p.second.
    469444    /// \param p The pair to insert.
    470     /// \pre \c p.first must not be stored in the heap.
    471445    void push(const Pair& p) {
    472446      push(p.first, p.second);
    … …  
    475449    /// \brief Insert an item into the heap with the given priority.
    476450    ///
    477     /// This function inserts the given item into the heap with the
    478     /// given priority.
     451    /// Adds \c i to the heap with priority \c p.
    479452    /// \param i The item to insert.
    480453    /// \param p The priority of the item.
    481     /// \pre \e i must not be stored in the heap.
    482454    void push(const Item &i, const Prio &p) {
    483455      int idx;
    … …  
    500472    }
    501473
    502     /// \brief Return the item having minimum priority.
    503     ///
    504     /// This function returns the item having minimum priority.
    505     /// \pre The heap must be non-empty.
     474    /// \brief Returns the item with minimum priority.
     475    ///
     476    /// This method returns the item with minimum priority.
     477    /// \pre The heap must be nonempty.
    506478    Item top() const {
    507479      while (_first[_minimum] == -1) {
    … …  
    511483    }
    512484
    513     /// \brief The minimum priority.
    514     ///
    515     /// This function returns the minimum priority.
    516     /// \pre The heap must be non-empty.
     485    /// \brief Returns the minimum priority.
     486    ///
     487    /// It returns the minimum priority.
     488    /// \pre The heap must be nonempty.
    517489    Prio prio() const {
    518490      while (_first[_minimum] == -1) {
    … …  
    522494    }
    523495
    524     /// \brief Remove the item having minimum priority.
    525     ///
    526     /// This function removes the item having minimum priority.
     496    /// \brief Deletes the item with minimum priority.
     497    ///
     498    /// This method deletes the item with minimum priority from the heap.
    527499    /// \pre The heap must be non-empty.
    528500    void pop() {
    … …  
    538510    }
    539511
    540     /// \brief The priority of the given item.
    541     ///
    542     /// This function returns the priority of the given item.
    543     /// \param i The item.
    544     /// \pre \e i must be in the heap.
    545     /// \warning This operator is not a constant time function because
    546     /// it scans the whole data structure to find the proper value.
     512    /// \brief Returns the priority of \c i.
     513    ///
     514    /// This function returns the priority of item \c i.
     515    /// \warning This operator is not a constant time function
     516    /// because it scans the whole data structure to find the proper
     517    /// value.
     518    /// \pre \c i must be in the heap.
     519    /// \param i The item.
    547520    Prio operator[](const Item &i) const {
    548       for (int k = 0; k < int(_first.size()); ++k) {
     521      for (int k = 0; k < _first.size(); ++k) {
    549522        int idx = _first[k];
    550523        while (idx != -1) {
    … …  
    558531    }
    559532
    560     /// \brief Return the state of an item.
    561     ///
    562     /// This method returns \c PRE_HEAP if the given item has never
    563     /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
    564     /// and \c POST_HEAP otherwise.
    565     /// In the latter case it is possible that the item will get back
    566     /// to the heap again.
     533    /// \brief Returns if \c item is in, has already been in, or has
     534    /// never been in the heap.
     535    ///
     536    /// This method returns PRE_HEAP if \c item has never been in the
     537    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
     538    /// otherwise. In the latter case it is possible that \c item will
     539    /// get back to the heap again.
    567540    /// \param i The item.
    568541    State state(const Item &i) const {

  • lemon/circulation.h

    r715 r641  
    7373    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
    7474    /// concept.
    75 #ifdef DOXYGEN
    76     typedef GR::ArcMap<Value> FlowMap;
    77 #else
    7875    typedef typename Digraph::template ArcMap<Value> FlowMap;
    79 #endif
    8076
    8177    /// \brief Instantiates a FlowMap.
    … …  
    9288    /// The elevator type used by the algorithm.
    9389    ///
    94     /// \sa Elevator, LinkedElevator
    95 #ifdef DOXYGEN
    96     typedef lemon::Elevator<GR, GR::Node> Elevator;
    97 #else
     90    /// \sa Elevator
     91    /// \sa LinkedElevator
    9892    typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
    99 #endif
    10093
    10194    /// \brief Instantiates an Elevator.
    … …  
    458451    }
    459452
    460     /// \brief Sets the tolerance used by the algorithm.
    461     ///
    462     /// Sets the tolerance object used by the algorithm.
    463     /// \return <tt>(*this)</tt>
    464     Circulation& tolerance(const Tolerance& tolerance) {
     453    /// \brief Sets the tolerance used by algorithm.
     454    ///
     455    /// Sets the tolerance used by algorithm.
     456    Circulation& tolerance(const Tolerance& tolerance) const {
    465457      _tol = tolerance;
    466458      return *this;
    … …  
    469461    /// \brief Returns a const reference to the tolerance.
    470462    ///
    471     /// Returns a const reference to the tolerance object used by
    472     /// the algorithm.
     463    /// Returns a const reference to the tolerance.
    473464    const Tolerance& tolerance() const {
    474       return _tol;
     465      return tolerance;
    475466    }
    476467
    477468    /// \name Execution Control
    478469    /// The simplest way to execute the algorithm is to call \ref run().\n
    479     /// If you need better control on the initial solution or the execution,
    480     /// you have to call one of the \ref init() functions first, then
     470    /// If you need more control on the initial solution or the execution,
     471    /// first you have to call one of the \ref init() functions, then
    481472    /// the \ref start() function.
    482473

  • lemon/concepts/heap.h

    r710 r584  
    1717 */
    1818
    19 #ifndef LEMON_CONCEPTS_HEAP_H
    20 #define LEMON_CONCEPTS_HEAP_H
    21 
    2219///\ingroup concept
    2320///\file
    2421///\brief The concept of heaps.
    2522
     23#ifndef LEMON_CONCEPTS_HEAP_H
     24#define LEMON_CONCEPTS_HEAP_H
     25
    2626#include <lemon/core.h>
    2727#include <lemon/concept_check.h>
    … …  
    3636    /// \brief The heap concept.
    3737    ///
    38     /// This concept class describes the main interface of heaps.
    39     /// The various \ref heaps "heap structures" are efficient
    40     /// implementations of the abstract data type \e priority \e queue.
    41     /// They store items with specified values called \e priorities
    42     /// in such a way that finding and removing the item with minimum
    43     /// priority are efficient. The basic operations are adding and
    44     /// erasing items, changing the priority of an item, etc.
     38    /// Concept class describing the main interface of heaps. A \e heap
     39    /// is a data structure for storing items with specified values called
     40    /// \e priorities in such a way that finding the item with minimum
     41    /// priority is efficient. In a heap one can change the priority of an
     42    /// item, add or erase an item, etc.
    4543    ///
    46     /// Heaps are crucial in several algorithms, such as Dijkstra and Prim.
    47     /// Any class that conforms to this concept can be used easily in such
    48     /// algorithms.
    49     ///
    50     /// \tparam PR Type of the priorities of the items.
    51     /// \tparam IM A read-writable item map with \c int values, used
     44    /// \tparam PR Type of the priority of the items.
     45    /// \tparam IM A read and writable item map with int values, used
    5246    /// internally to handle the cross references.
    53     /// \tparam CMP A functor class for comparing the priorities.
     47    /// \tparam Comp A functor class for the ordering of the priorities.
    5448    /// The default is \c std::less<PR>.
    5549#ifdef DOXYGEN
    56     template <typename PR, typename IM, typename CMP>
     50    template <typename PR, typename IM, typename Comp = std::less<PR> >
    5751#else
    58     template <typename PR, typename IM, typename CMP = std::less<PR> >
     52    template <typename PR, typename IM>
    5953#endif
    6054    class Heap {
    … …  
    7165      ///
    7266      /// Each item has a state associated to it. It can be "in heap",
    73       /// "pre-heap" or "post-heap". The latter two are indifferent from the
    74       /// heap's point of view, but may be useful to the user.
     67      /// "pre heap" or "post heap". The later two are indifferent
     68      /// from the point of view of the heap, but may be useful for
     69      /// the user.
    7570      ///
    7671      /// The item-int map must be initialized in such way that it assigns
    … …  
    7873      enum State {
    7974        IN_HEAP = 0,    ///< = 0. The "in heap" state constant.
    80         PRE_HEAP = -1,  ///< = -1. The "pre-heap" state constant.
    81         POST_HEAP = -2  ///< = -2. The "post-heap" state constant.
     75        PRE_HEAP = -1,  ///< = -1. The "pre heap" state constant.
     76        POST_HEAP = -2  ///< = -2. The "post heap" state constant.
    8277      };
    8378
    84       /// \brief Constructor.
    85       ///
    86       /// Constructor.
     79      /// \brief The constructor.
     80      ///
     81      /// The constructor.
    8782      /// \param map A map that assigns \c int values to keys of type
    8883      /// \c Item. It is used internally by the heap implementations to
    8984      /// handle the cross references. The assigned value must be
    90       /// \c PRE_HEAP (<tt>-1</tt>) for each item.
     85      /// \c PRE_HEAP (<tt>-1</tt>) for every item.
    9186      explicit Heap(ItemIntMap &map) {}
    9287
    93       /// \brief Constructor.
    94       ///
    95       /// Constructor.
    96       /// \param map A map that assigns \c int values to keys of type
    97       /// \c Item. It is used internally by the heap implementations to
    98       /// handle the cross references. The assigned value must be
    99       /// \c PRE_HEAP (<tt>-1</tt>) for each item.
    100       /// \param comp The function object used for comparing the priorities.
    101       explicit Heap(ItemIntMap &map, const CMP &comp) {}
    102 
    10388      /// \brief The number of items stored in the heap.
    10489      ///
    105       /// This function returns the number of items stored in the heap.
     90      /// Returns the number of items stored in the heap.
    10691      int size() const { return 0; }
    10792
    108       /// \brief Check if the heap is empty.
    109       ///
    110       /// This function returns \c true if the heap is empty.
     93      /// \brief Checks if the heap is empty.
     94      ///
     95      /// Returns \c true if the heap is empty.
    11196      bool empty() const { return false; }
    11297
    113       /// \brief Make the heap empty.
    114       ///
    115       /// This functon makes the heap empty.
    116       /// It does not change the cross reference map. If you want to reuse
    117       /// a heap that is not surely empty, you should first clear it and
    118       /// then you should set the cross reference map to \c PRE_HEAP
    119       /// for each item.
    120       void clear() {}
    121 
    122       /// \brief Insert an item into the heap with the given priority.
    123       ///
    124       /// This function inserts the given item into the heap with the
    125       /// given priority.
     98      /// \brief Makes the heap empty.
     99      ///
     100      /// Makes the heap empty.
     101      void clear();
     102
     103      /// \brief Inserts an item into the heap with the given priority.
     104      ///
     105      /// Inserts the given item into the heap with the given priority.
    126106      /// \param i The item to insert.
    127107      /// \param p The priority of the item.
    128       /// \pre \e i must not be stored in the heap.
    129108      void push(const Item &i, const Prio &p) {}
    130109
    131       /// \brief Return the item having minimum priority.
    132       ///
    133       /// This function returns the item having minimum priority.
     110      /// \brief Returns the item having minimum priority.
     111      ///
     112      /// Returns the item having minimum priority.
    134113      /// \pre The heap must be non-empty.
    135114      Item top() const {}
    … …  
    137116      /// \brief The minimum priority.
    138117      ///
    139       /// This function returns the minimum priority.
     118      /// Returns the minimum priority.
    140119      /// \pre The heap must be non-empty.
    141120      Prio prio() const {}
    142121
    143       /// \brief Remove the item having minimum priority.
    144       ///
    145       /// This function removes the item having minimum priority.
     122      /// \brief Removes the item having minimum priority.
     123      ///
     124      /// Removes the item having minimum priority.
    146125      /// \pre The heap must be non-empty.
    147126      void pop() {}
    148127
    149       /// \brief Remove the given item from the heap.
    150       ///
    151       /// This function removes the given item from the heap if it is
    152       /// already stored.
     128      /// \brief Removes an item from the heap.
     129      ///
     130      /// Removes the given item from the heap if it is already stored.
    153131      /// \param i The item to delete.
    154       /// \pre \e i must be in the heap.
    155132      void erase(const Item &i) {}
    156133
    157       /// \brief The priority of the given item.
    158       ///
    159       /// This function returns the priority of the given item.
    160       /// \param i The item.
    161       /// \pre \e i must be in the heap.
     134      /// \brief The priority of an item.
     135      ///
     136      /// Returns the priority of the given item.
     137      /// \param i The item.
     138      /// \pre \c i must be in the heap.
    162139      Prio operator[](const Item &i) const {}
    163140
    164       /// \brief Set the priority of an item or insert it, if it is
     141      /// \brief Sets the priority of an item or inserts it, if it is
    165142      /// not stored in the heap.
    166143      ///
    167144      /// This method sets the priority of the given item if it is
    168       /// already stored in the heap. Otherwise it inserts the given
    169       /// item into the heap with the given priority.
     145      /// already stored in the heap.
     146      /// Otherwise it inserts the given item with the given priority.
    170147      ///
    171148      /// \param i The item.
    … …  
    173150      void set(const Item &i, const Prio &p) {}
    174151
    175       /// \brief Decrease the priority of an item to the given value.
    176       ///
    177       /// This function decreases the priority of an item to the given value.
     152      /// \brief Decreases the priority of an item to the given value.
     153      ///
     154      /// Decreases the priority of an item to the given value.
    178155      /// \param i The item.
    179156      /// \param p The priority.
    180       /// \pre \e i must be stored in the heap with priority at least \e p.
     157      /// \pre \c i must be stored in the heap with priority at least \c p.
    181158      void decrease(const Item &i, const Prio &p) {}
    182159
    183       /// \brief Increase the priority of an item to the given value.
    184       ///
    185       /// This function increases the priority of an item to the given value.
     160      /// \brief Increases the priority of an item to the given value.
     161      ///
     162      /// Increases the priority of an item to the given value.
    186163      /// \param i The item.
    187164      /// \param p The priority.
    188       /// \pre \e i must be stored in the heap with priority at most \e p.
     165      /// \pre \c i must be stored in the heap with priority at most \c p.
    189166      void increase(const Item &i, const Prio &p) {}
    190167
    191       /// \brief Return the state of an item.
     168      /// \brief Returns if an item is in, has already been in, or has
     169      /// never been in the heap.
    192170      ///
    193171      /// This method returns \c PRE_HEAP if the given item has never
    … …  
    199177      State state(const Item &i) const {}
    200178
    201       /// \brief Set the state of an item in the heap.
    202       ///
    203       /// This function sets the state of the given item in the heap.
    204       /// It can be used to manually clear the heap when it is important
    205       /// to achive better time complexity.
     179      /// \brief Sets the state of an item in the heap.
     180      ///
     181      /// Sets the state of the given item in the heap. It can be used
     182      /// to manually clear the heap when it is important to achive the
     183      /// better time complexity.
    206184      /// \param i The item.
    207185      /// \param st The state. It should not be \c IN_HEAP.

  • lemon/concepts/maps.h

    r718 r529  
    183183      template<typename _ReferenceMap>
    184184      struct Constraints {
    185         typename enable_if<typename _ReferenceMap::ReferenceMapTag, void>::type
    186         constraints() {
     185        void constraints() {
    187186          checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();
    188187          ref = m[key];

  • lemon/dfs.h

    r717 r584  
    4848    ///The type of the map that stores the predecessor
    4949    ///arcs of the %DFS paths.
    50     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     50    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    5151    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    5252    ///Instantiates a \c PredMap.
    … …  
    6363
    6464    ///The type of the map that indicates which nodes are processed.
    65     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    66     ///By default it is a NullMap.
     65    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    6766    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    6867    ///Instantiates a \c ProcessedMap.
    … …  
    8382
    8483    ///The type of the map that indicates which nodes are reached.
    85     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     84    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8685    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    8786    ///Instantiates a \c ReachedMap.
    … …  
    9897
    9998    ///The type of the map that stores the distances of the nodes.
    100     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     99    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    101100    typedef typename Digraph::template NodeMap<int> DistMap;
    102101    ///Instantiates a \c DistMap.
    … …  
    226225    ///\ref named-templ-param "Named parameter" for setting
    227226    ///\c PredMap type.
    228     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     227    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    229228    template <class T>
    230229    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
    … …  
    246245    ///\ref named-templ-param "Named parameter" for setting
    247246    ///\c DistMap type.
    248     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     247    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    249248    template <class T>
    250249    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
    … …  
    266265    ///\ref named-templ-param "Named parameter" for setting
    267266    ///\c ReachedMap type.
    268     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     267    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    269268    template <class T>
    270269    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
    … …  
    286285    ///\ref named-templ-param "Named parameter" for setting
    287286    ///\c ProcessedMap type.
    288     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     287    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    289288    template <class T>
    290289    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
    … …  
    413412    ///The simplest way to execute the DFS algorithm is to use one of the
    414413    ///member functions called \ref run(Node) "run()".\n
    415     ///If you need better control on the execution, you have to call
    416     ///\ref init() first, then you can add a source node with \ref addSource()
     414    ///If you need more control on the execution, first you have to call
     415    ///\ref init(), then you can add a source node with \ref addSource()
    417416    ///and perform the actual computation with \ref start().
    418417    ///This procedure can be repeated if there are nodes that have not
    … …  
    671670    ///@{
    672671
    673     ///The DFS path to the given node.
    674 
    675     ///Returns the DFS path to the given node from the root(s).
     672    ///The DFS path to a node.
     673
     674    ///Returns the DFS path to a node.
    676675    ///
    677676    ///\warning \c t should be reached from the root(s).
    … …  
    681680    Path path(Node t) const { return Path(*G, *_pred, t); }
    682681
    683     ///The distance of the given node from the root(s).
    684 
    685     ///Returns the distance of the given node from the root(s).
     682    ///The distance of a node from the root(s).
     683
     684    ///Returns the distance of a node from the root(s).
    686685    ///
    687686    ///\warning If node \c v is not reached from the root(s), then
    … …  
    692691    int dist(Node v) const { return (*_dist)[v]; }
    693692
    694     ///Returns the 'previous arc' of the %DFS tree for the given node.
     693    ///Returns the 'previous arc' of the %DFS tree for a node.
    695694
    696695    ///This function returns the 'previous arc' of the %DFS tree for the
    … …  
    700699    ///
    701700    ///The %DFS tree used here is equal to the %DFS tree used in
    702     ///\ref predNode() and \ref predMap().
     701    ///\ref predNode().
    703702    ///
    704703    ///\pre Either \ref run(Node) "run()" or \ref init()
    … …  
    706705    Arc predArc(Node v) const { return (*_pred)[v];}
    707706
    708     ///Returns the 'previous node' of the %DFS tree for the given node.
     707    ///Returns the 'previous node' of the %DFS tree.
    709708
    710709    ///This function returns the 'previous node' of the %DFS
    711710    ///tree for the node \c v, i.e. it returns the last but one node
    712     ///of a %DFS path from a root to \c v. It is \c INVALID
     711    ///from a %DFS path from a root to \c v. It is \c INVALID
    713712    ///if \c v is not reached from the root(s) or if \c v is a root.
    714713    ///
    715714    ///The %DFS tree used here is equal to the %DFS tree used in
    716     ///\ref predArc() and \ref predMap().
     715    ///\ref predArc().
    717716    ///
    718717    ///\pre Either \ref run(Node) "run()" or \ref init()
    … …  
    735734    ///
    736735    ///Returns a const reference to the node map that stores the predecessor
    737     ///arcs, which form the DFS tree (forest).
     736    ///arcs, which form the DFS tree.
    738737    ///
    739738    ///\pre Either \ref run(Node) "run()" or \ref init()
    … …  
    741740    const PredMap &predMap() const { return *_pred;}
    742741
    743     ///Checks if the given node. node is reached from the root(s).
     742    ///Checks if a node is reached from the root(s).
    744743
    745744    ///Returns \c true if \c v is reached from the root(s).
    … …  
    767766    ///The type of the map that stores the predecessor
    768767    ///arcs of the %DFS paths.
    769     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     768    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    770769    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    771770    ///Instantiates a PredMap.
    … …  
    782781
    783782    ///The type of the map that indicates which nodes are processed.
    784     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     783    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    785784    ///By default it is a NullMap.
    786785    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    … …  
    802801
    803802    ///The type of the map that indicates which nodes are reached.
    804     ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     803    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    805804    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    806805    ///Instantiates a ReachedMap.
    … …  
    817816
    818817    ///The type of the map that stores the distances of the nodes.
    819     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     818    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    820819    typedef typename Digraph::template NodeMap<int> DistMap;
    821820    ///Instantiates a DistMap.
    … …  
    832831
    833832    ///The type of the DFS paths.
    834     ///It must conform to the \ref concepts::Path "Path" concept.
     833    ///It must meet the \ref concepts::Path "Path" concept.
    835834    typedef lemon::Path<Digraph> Path;
    836835  };
    … …  
    838837  /// Default traits class used by DfsWizard
    839838
    840   /// Default traits class used by DfsWizard.
    841   /// \tparam GR The type of the digraph.
     839  /// To make it easier to use Dfs algorithm
     840  /// we have created a wizard class.
     841  /// This \ref DfsWizard class needs default traits,
     842  /// as well as the \ref Dfs class.
     843  /// The \ref DfsWizardBase is a class to be the default traits of the
     844  /// \ref DfsWizard class.
    842845  template<class GR>
    843846  class DfsWizardBase : public DfsWizardDefaultTraits<GR>
    … …  
    867870    /// Constructor.
    868871
    869     /// This constructor does not require parameters, it initiates
     872    /// This constructor does not require parameters, therefore it initiates
    870873    /// all of the attributes to \c 0.
    871874    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
    … …  
    897900    typedef TR Base;
    898901
     902    ///The type of the digraph the algorithm runs on.
    899903    typedef typename TR::Digraph Digraph;
    900904
    … …  
    904908    typedef typename Digraph::OutArcIt OutArcIt;
    905909
     910    ///\brief The type of the map that stores the predecessor
     911    ///arcs of the DFS paths.
    906912    typedef typename TR::PredMap PredMap;
     913    ///\brief The type of the map that stores the distances of the nodes.
    907914    typedef typename TR::DistMap DistMap;
     915    ///\brief The type of the map that indicates which nodes are reached.
    908916    typedef typename TR::ReachedMap ReachedMap;
     917    ///\brief The type of the map that indicates which nodes are processed.
    909918    typedef typename TR::ProcessedMap ProcessedMap;
     919    ///The type of the DFS paths
    910920    typedef typename TR::Path Path;
    911921
    … …  
    9901000      SetPredMapBase(const TR &b) : TR(b) {}
    9911001    };
    992 
    993     ///\brief \ref named-templ-param "Named parameter" for setting
    994     ///the predecessor map.
    995     ///
    996     ///\ref named-templ-param "Named parameter" function for setting
    997     ///the map that stores the predecessor arcs of the nodes.
     1002    ///\brief \ref named-func-param "Named parameter"
     1003    ///for setting PredMap object.
     1004    ///
     1005    ///\ref named-func-param "Named parameter"
     1006    ///for setting PredMap object.
    9981007    template<class T>
    9991008    DfsWizard<SetPredMapBase<T> > predMap(const T &t)
    … …  
    10091018      SetReachedMapBase(const TR &b) : TR(b) {}
    10101019    };
    1011 
    1012     ///\brief \ref named-templ-param "Named parameter" for setting
    1013     ///the reached map.
    1014     ///
    1015     ///\ref named-templ-param "Named parameter" function for setting
    1016     ///the map that indicates which nodes are reached.
     1020    ///\brief \ref named-func-param "Named parameter"
     1021    ///for setting ReachedMap object.
     1022    ///
     1023    /// \ref named-func-param "Named parameter"
     1024    ///for setting ReachedMap object.
    10171025    template<class T>
    10181026    DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
    … …  
    10281036      SetDistMapBase(const TR &b) : TR(b) {}
    10291037    };
    1030 
    1031     ///\brief \ref named-templ-param "Named parameter" for setting
    1032     ///the distance map.
    1033     ///
    1034     ///\ref named-templ-param "Named parameter" function for setting
    1035     ///the map that stores the distances of the nodes calculated
    1036     ///by the algorithm.
     1038    ///\brief \ref named-func-param "Named parameter"
     1039    ///for setting DistMap object.
     1040    ///
     1041    /// \ref named-func-param "Named parameter"
     1042    ///for setting DistMap object.
    10371043    template<class T>
    10381044    DfsWizard<SetDistMapBase<T> > distMap(const T &t)
    … …  
    10481054      SetProcessedMapBase(const TR &b) : TR(b) {}
    10491055    };
    1050 
    1051     ///\brief \ref named-func-param "Named parameter" for setting
    1052     ///the processed map.
    1053     ///
    1054     ///\ref named-templ-param "Named parameter" function for setting
    1055     ///the map that indicates which nodes are processed.
     1056    ///\brief \ref named-func-param "Named parameter"
     1057    ///for setting ProcessedMap object.
     1058    ///
     1059    /// \ref named-func-param "Named parameter"
     1060    ///for setting ProcessedMap object.
    10561061    template<class T>
    10571062    DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
    … …  
    12041209    ///
    12051210    /// The type of the map that indicates which nodes are reached.
    1206     /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     1211    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12071212    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12081213
    … …  
    13651370    /// The simplest way to execute the DFS algorithm is to use one of the
    13661371    /// member functions called \ref run(Node) "run()".\n
    1367     /// If you need better control on the execution, you have to call
    1368     /// \ref init() first, then you can add a source node with \ref addSource()
     1372    /// If you need more control on the execution, first you have to call
     1373    /// \ref init(), then you can add a source node with \ref addSource()
    13691374    /// and perform the actual computation with \ref start().
    13701375    /// This procedure can be repeated if there are nodes that have not
    … …  
    16161621    ///@{
    16171622
    1618     /// \brief Checks if the given node is reached from the root(s).
     1623    /// \brief Checks if a node is reached from the root(s).
    16191624    ///
    16201625    /// Returns \c true if \c v is reached from the root(s).

  • lemon/dijkstra.h

    r717 r584  
    7171
    7272    ///The type of the map that stores the arc lengths.
    73     ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
     73    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
    7474    typedef LEN LengthMap;
    75     ///The type of the arc lengths.
     75    ///The type of the length of the arcs.
    7676    typedef typename LEN::Value Value;
    7777
    … …  
    117117    ///The type of the map that stores the predecessor
    118118    ///arcs of the shortest paths.
    119     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     119    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    120120    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    121121    ///Instantiates a \c PredMap.
    … …  
    132132
    133133    ///The type of the map that indicates which nodes are processed.
    134     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     134    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    135135    ///By default it is a NullMap.
    136136    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    … …  
    152152
    153153    ///The type of the map that stores the distances of the nodes.
    154     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     154    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    155155    typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
    156156    ///Instantiates a \c DistMap.
    … …  
    169169  /// \ingroup shortest_path
    170170  ///This class provides an efficient implementation of the %Dijkstra algorithm.
    171   ///
    172   ///The %Dijkstra algorithm solves the single-source shortest path problem
    173   ///when all arc lengths are non-negative. If there are negative lengths,
    174   ///the BellmanFord algorithm should be used instead.
    175171  ///
    176172  ///The arc lengths are passed to the algorithm using a
    … …  
    206202    typedef typename TR::Digraph Digraph;
    207203
    208     ///The type of the arc lengths.
     204    ///The type of the length of the arcs.
    209205    typedef typename TR::LengthMap::Value Value;
    210206    ///The type of the map that stores the arc lengths.
    … …  
    309305    ///\ref named-templ-param "Named parameter" for setting
    310306    ///\c PredMap type.
    311     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     307    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    312308    template <class T>
    313309    struct SetPredMap
    … …  
    330326    ///\ref named-templ-param "Named parameter" for setting
    331327    ///\c DistMap type.
    332     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     328    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    333329    template <class T>
    334330    struct SetDistMap
    … …  
    351347    ///\ref named-templ-param "Named parameter" for setting
    352348    ///\c ProcessedMap type.
    353     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     349    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    354350    template <class T>
    355351    struct SetProcessedMap
    … …  
    448444    ///\ref named-templ-param "Named parameter" for setting
    449445    ///\c OperationTraits type.
    450     /// For more information see \ref DijkstraDefaultOperationTraits.
    451446    template <class T>
    452447    struct SetOperationTraits
    … …  
    590585    ///The simplest way to execute the %Dijkstra algorithm is to use
    591586    ///one of the member functions called \ref run(Node) "run()".\n
    592     ///If you need better control on the execution, you have to call
    593     ///\ref init() first, then you can add several source nodes with
     587    ///If you need more control on the execution, first you have to call
     588    ///\ref init(), then you can add several source nodes with
    594589    ///\ref addSource(). Finally the actual path computation can be
    595590    ///performed with one of the \ref start() functions.
    … …  
    807802    ///The results of the %Dijkstra algorithm can be obtained using these
    808803    ///functions.\n
    809     ///Either \ref run(Node) "run()" or \ref init() should be called
     804    ///Either \ref run(Node) "run()" or \ref start() should be called
    810805    ///before using them.
    811806
    812807    ///@{
    813808
    814     ///The shortest path to the given node.
    815 
    816     ///Returns the shortest path to the given node from the root(s).
     809    ///The shortest path to a node.
     810
     811    ///Returns the shortest path to a node.
    817812    ///
    818813    ///\warning \c t should be reached from the root(s).
    … …  
    822817    Path path(Node t) const { return Path(*G, *_pred, t); }
    823818
    824     ///The distance of the given node from the root(s).
    825 
    826     ///Returns the distance of the given node from the root(s).
     819    ///The distance of a node from the root(s).
     820
     821    ///Returns the distance of a node from the root(s).
    827822    ///
    828823    ///\warning If node \c v is not reached from the root(s), then
    … …  
    833828    Value dist(Node v) const { return (*_dist)[v]; }
    834829
    835     ///\brief Returns the 'previous arc' of the shortest path tree for
    836     ///the given node.
    837     ///
     830    ///Returns the 'previous arc' of the shortest path tree for a node.
     831
    838832    ///This function returns the 'previous arc' of the shortest path
    839833    ///tree for the node \c v, i.e. it returns the last arc of a
    … …  
    842836    ///
    843837    ///The shortest path tree used here is equal to the shortest path
    844     ///tree used in \ref predNode() and \ref predMap().
     838    ///tree used in \ref predNode().
    845839    ///
    846840    ///\pre Either \ref run(Node) "run()" or \ref init()
    … …  
    848842    Arc predArc(Node v) const { return (*_pred)[v]; }
    849843
    850     ///\brief Returns the 'previous node' of the shortest path tree for
    851     ///the given node.
    852     ///
     844    ///Returns the 'previous node' of the shortest path tree for a node.
     845
    853846    ///This function returns the 'previous node' of the shortest path
    854847    ///tree for the node \c v, i.e. it returns the last but one node
    855     ///of a shortest path from a root to \c v. It is \c INVALID
     848    ///from a shortest path from a root to \c v. It is \c INVALID
    856849    ///if \c v is not reached from the root(s) or if \c v is a root.
    857850    ///
    858851    ///The shortest path tree used here is equal to the shortest path
    859     ///tree used in \ref predArc() and \ref predMap().
     852    ///tree used in \ref predArc().
    860853    ///
    861854    ///\pre Either \ref run(Node) "run()" or \ref init()
    … …  
    878871    ///
    879872    ///Returns a const reference to the node map that stores the predecessor
    880     ///arcs, which form the shortest path tree (forest).
     873    ///arcs, which form the shortest path tree.
    881874    ///
    882875    ///\pre Either \ref run(Node) "run()" or \ref init()
    … …  
    884877    const PredMap &predMap() const { return *_pred;}
    885878
    886     ///Checks if the given node is reached from the root(s).
     879    ///Checks if a node is reached from the root(s).
    887880
    888881    ///Returns \c true if \c v is reached from the root(s).
    … …  
    903896                                          Heap::POST_HEAP; }
    904897
    905     ///The current distance of the given node from the root(s).
    906 
    907     ///Returns the current distance of the given node from the root(s).
     898    ///The current distance of a node from the root(s).
     899
     900    ///Returns the current distance of a node from the root(s).
    908901    ///It may be decreased in the following processes.
    909902    ///
    … …  
    932925
    933926    ///The type of the map that stores the arc lengths.
    934     ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
     927    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
    935928    typedef LEN LengthMap;
    936     ///The type of the arc lengths.
     929    ///The type of the length of the arcs.
    937930    typedef typename LEN::Value Value;
    938931
    … …  
    981974    ///The type of the map that stores the predecessor
    982975    ///arcs of the shortest paths.
    983     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     976    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    984977    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    985978    ///Instantiates a PredMap.
    … …  
    996989
    997990    ///The type of the map that indicates which nodes are processed.
    998     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     991    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    999992    ///By default it is a NullMap.
    1000993    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    … …  
    10161009
    10171010    ///The type of the map that stores the distances of the nodes.
    1018     ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     1011    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    10191012    typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
    10201013    ///Instantiates a DistMap.
    … …  
    10311024
    10321025    ///The type of the shortest paths.
    1033     ///It must conform to the \ref concepts::Path "Path" concept.
     1026    ///It must meet the \ref concepts::Path "Path" concept.
    10341027    typedef lemon::Path<Digraph> Path;
    10351028  };
    … …  
    10371030  /// Default traits class used by DijkstraWizard
    10381031
    1039   /// Default traits class used by DijkstraWizard.
    1040   /// \tparam GR The type of the digraph.
    1041   /// \tparam LEN The type of the length map.
     1032  /// To make it easier to use Dijkstra algorithm
     1033  /// we have created a wizard class.
     1034  /// This \ref DijkstraWizard class needs default traits,
     1035  /// as well as the \ref Dijkstra class.
     1036  /// The \ref DijkstraWizardBase is a class to be the default traits of the
     1037  /// \ref DijkstraWizard class.
    10421038  template<typename GR, typename LEN>
    10431039  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN>
    … …  
    10981094    typedef TR Base;
    10991095
     1096    ///The type of the digraph the algorithm runs on.
    11001097    typedef typename TR::Digraph Digraph;
    11011098
    … …  
    11051102    typedef typename Digraph::OutArcIt OutArcIt;
    11061103
     1104    ///The type of the map that stores the arc lengths.
    11071105    typedef typename TR::LengthMap LengthMap;
     1106    ///The type of the length of the arcs.
    11081107    typedef typename LengthMap::Value Value;
     1108    ///\brief The type of the map that stores the predecessor
     1109    ///arcs of the shortest paths.
    11091110    typedef typename TR::PredMap PredMap;
     1111    ///The type of the map that stores the distances of the nodes.
    11101112    typedef typename TR::DistMap DistMap;
     1113    ///The type of the map that indicates which nodes are processed.
    11111114    typedef typename TR::ProcessedMap ProcessedMap;
     1115    ///The type of the shortest paths
    11121116    typedef typename TR::Path Path;
     1117    ///The heap type used by the dijkstra algorithm.
    11131118    typedef typename TR::Heap Heap;
    11141119
    … …  
    11821187      SetPredMapBase(const TR &b) : TR(b) {}
    11831188    };
    1184 
    1185     ///\brief \ref named-templ-param "Named parameter" for setting
    1186     ///the predecessor map.
    1187     ///
    1188     ///\ref named-templ-param "Named parameter" function for setting
    1189     ///the map that stores the predecessor arcs of the nodes.
     1189    ///\brief \ref named-func-param "Named parameter"
     1190    ///for setting PredMap object.
     1191    ///
     1192    ///\ref named-func-param "Named parameter"
     1193    ///for setting PredMap object.
    11901194    template<class T>
    11911195    DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
    … …  
    12011205      SetDistMapBase(const TR &b) : TR(b) {}
    12021206    };
    1203 
    1204     ///\brief \ref named-templ-param "Named parameter" for setting
    1205     ///the distance map.
    1206     ///
    1207     ///\ref named-templ-param "Named parameter" function for setting
    1208     ///the map that stores the distances of the nodes calculated
    1209     ///by the algorithm.
     1207    ///\brief \ref named-func-param "Named parameter"
     1208    ///for setting DistMap object.
     1209    ///
     1210    ///\ref named-func-param "Named parameter"
     1211    ///for setting DistMap object.
    12101212    template<class T>
    12111213    DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
    … …  
    12211223      SetProcessedMapBase(const TR &b) : TR(b) {}
    12221224    };
    1223 
    1224     ///\brief \ref named-func-param "Named parameter" for setting
    1225     ///the processed map.
    1226     ///
    1227     ///\ref named-templ-param "Named parameter" function for setting
    1228     ///the map that indicates which nodes are processed.
     1225    ///\brief \ref named-func-param "Named parameter"
     1226    ///for setting ProcessedMap object.
     1227    ///
     1228    /// \ref named-func-param "Named parameter"
     1229    ///for setting ProcessedMap object.
    12291230    template<class T>
    12301231    DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
    … …  
    12391240      SetPathBase(const TR &b) : TR(b) {}
    12401241    };
    1241 
    12421242    ///\brief \ref named-func-param "Named parameter"
    12431243    ///for getting the shortest path to the target node.

  • lemon/dim2.h

    r714 r440  
    2222#include <iostream>
    2323
    24 ///\ingroup geomdat
     24///\ingroup misc
    2525///\file
    2626///\brief A simple two dimensional vector and a bounding box implementation
     27///
     28/// The class \ref lemon::dim2::Point "dim2::Point" implements
     29/// a two dimensional vector with the usual operations.
     30///
     31/// The class \ref lemon::dim2::Box "dim2::Box" can be used to determine
     32/// the rectangular bounding box of a set of
     33/// \ref lemon::dim2::Point "dim2::Point"'s.
    2734
    2835namespace lemon {
    … …  
    3441  namespace dim2 {
    3542
    36   /// \addtogroup geomdat
     43  /// \addtogroup misc
    3744  /// @{
    3845

  • lemon/fib_heap.h

    r711 r683  
    2121
    2222///\file
    23 ///\ingroup heaps
    24 ///\brief Fibonacci heap implementation.
     23///\ingroup auxdat
     24///\brief Fibonacci Heap implementation.
    2525
    2626#include <vector>
    27 #include <utility>
    2827#include <functional>
    2928#include <lemon/math.h>
    … …  
    3130namespace lemon {
    3231
    33   /// \ingroup heaps
     32  /// \ingroup auxdat
    3433  ///
    35   /// \brief Fibonacci heap data structure.
     34  ///\brief Fibonacci Heap.
    3635  ///
    37   /// This class implements the \e Fibonacci \e heap data structure.
    38   /// It fully conforms to the \ref concepts::Heap "heap concept".
     36  ///This class implements the \e Fibonacci \e heap data structure. A \e heap
     37  ///is a data structure for storing items with specified values called \e
     38  ///priorities in such a way that finding the item with minimum priority is
     39  ///efficient. \c CMP specifies the ordering of the priorities. In a heap
     40  ///one can change the priority of an item, add or erase an item, etc.
    3941  ///
    40   /// The methods \ref increase() and \ref erase() are not efficient in a
    41   /// Fibonacci heap. In case of many calls of these operations, it is
    42   /// better to use other heap structure, e.g. \ref BinHeap "binary heap".
     42  ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
     43  ///heap. In case of many calls to these operations, it is better to use a
     44  ///\ref BinHeap "binary heap".
    4345  ///
    44   /// \tparam PR Type of the priorities of the items.
    45   /// \tparam IM A read-writable item map with \c int values, used
    46   /// internally to handle the cross references.
    47   /// \tparam CMP A functor class for comparing the priorities.
    48   /// The default is \c std::less<PR>.
     46  ///\param PRIO Type of the priority of the items.
     47  ///\param IM A read and writable Item int map, used internally
     48  ///to handle the cross references.
     49  ///\param CMP A class for the ordering of the priorities. The
     50  ///default is \c std::less<PRIO>.
     51  ///
     52  ///\sa BinHeap
     53  ///\sa Dijkstra
    4954#ifdef DOXYGEN
    50   template <typename PR, typename IM, typename CMP>
     55  template <typename PRIO, typename IM, typename CMP>
    5156#else
    52   template <typename PR, typename IM, typename CMP = std::less<PR> >
     57  template <typename PRIO, typename IM, typename CMP = std::less<PRIO> >
    5358#endif
    5459  class FibHeap {
    5560  public:
    56 
    57     /// Type of the item-int map.
     61    ///\e
    5862    typedef IM ItemIntMap;
    59     /// Type of the priorities.
    60     typedef PR Prio;
    61     /// Type of the items stored in the heap.
     63    ///\e
     64    typedef PRIO Prio;
     65    ///\e
    6266    typedef typename ItemIntMap::Key Item;
    63     /// Type of the item-priority pairs.
     67    ///\e
    6468    typedef std::pair<Item,Prio> Pair;
    65     /// Functor type for comparing the priorities.
     69    ///\e
    6670    typedef CMP Compare;
    6771
    … …  
    7781  public:
    7882
    79     /// \brief Type to represent the states of the items.
    80     ///
    81     /// Each item has a state associated to it. It can be "in heap",
    82     /// "pre-heap" or "post-heap". The latter two are indifferent from the
     83    /// \brief Type to represent the items states.
     84    ///
     85    /// Each Item element have a state associated to it. It may be "in heap",
     86    /// "pre heap" or "post heap". The latter two are indifferent from the
    8387    /// heap's point of view, but may be useful to the user.
    8488    ///
    … …  
    9195    };
    9296
    93     /// \brief Constructor.
    94     ///
    95     /// Constructor.
    96     /// \param map A map that assigns \c int values to the items.
    97     /// It is used internally to handle the cross references.
    98     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     97    /// \brief The constructor
     98    ///
     99    /// \c map should be given to the constructor, since it is
     100    ///   used internally to handle the cross references.
    99101    explicit FibHeap(ItemIntMap &map)
    100102      : _minimum(0), _iim(map), _num() {}
    101103
    102     /// \brief Constructor.
    103     ///
    104     /// Constructor.
    105     /// \param map A map that assigns \c int values to the items.
    106     /// It is used internally to handle the cross references.
    107     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    108     /// \param comp The function object used for comparing the priorities.
     104    /// \brief The constructor
     105    ///
     106    /// \c map should be given to the constructor, since it is used
     107    /// internally to handle the cross references. \c comp is an
     108    /// object for ordering of the priorities.
    109109    FibHeap(ItemIntMap &map, const Compare &comp)
    110110      : _minimum(0), _iim(map), _comp(comp), _num() {}
    … …  
    112112    /// \brief The number of items stored in the heap.
    113113    ///
    114     /// This function returns the number of items stored in the heap.
     114    /// Returns the number of items stored in the heap.
    115115    int size() const { return _num; }
    116116
    117     /// \brief Check if the heap is empty.
    118     ///
    119     /// This function returns \c true if the heap is empty.
     117    /// \brief Checks if the heap stores no items.
     118    ///
     119    ///   Returns \c true if and only if the heap stores no items.
    120120    bool empty() const { return _num==0; }
    121121
    122     /// \brief Make the heap empty.
    123     ///
    124     /// This functon makes the heap empty.
    125     /// It does not change the cross reference map. If you want to reuse
    126     /// a heap that is not surely empty, you should first clear it and
    127     /// then you should set the cross reference map to \c PRE_HEAP
    128     /// for each item.
     122    /// \brief Make empty this heap.
     123    ///
     124    /// Make empty this heap. It does not change the cross reference
     125    /// map.  If you want to reuse a heap what is not surely empty you
     126    /// should first clear the heap and after that you should set the
     127    /// cross reference map for each item to \c PRE_HEAP.
    129128    void clear() {
    130129      _data.clear(); _minimum = 0; _num = 0;
    131130    }
    132131
    133     /// \brief Insert an item into the heap with the given priority.
    134     ///
    135     /// This function inserts the given item into the heap with the
    136     /// given priority.
    137     /// \param item The item to insert.
    138     /// \param prio The priority of the item.
    139     /// \pre \e item must not be stored in the heap.
    140     void push (const Item& item, const Prio& prio) {
     132    /// \brief \c item gets to the heap with priority \c value independently
     133    /// if \c item was already there.
     134    ///
     135    /// This method calls \ref push(\c item, \c value) if \c item is not
     136    /// stored in the heap and it calls \ref decrease(\c item, \c value) or
     137    /// \ref increase(\c item, \c value) otherwise.
     138    void set (const Item& item, const Prio& value) {
     139      int i=_iim[item];
     140      if ( i >= 0 && _data[i].in ) {
     141        if ( _comp(value, _data[i].prio) ) decrease(item, value);
     142        if ( _comp(_data[i].prio, value) ) increase(item, value);
     143      } else push(item, value);
     144    }
     145
     146    /// \brief Adds \c item to the heap with priority \c value.
     147    ///
     148    /// Adds \c item to the heap with priority \c value.
     149    /// \pre \c item must not be stored in the heap.
     150    void push (const Item& item, const Prio& value) {
    141151      int i=_iim[item];
    142152      if ( i < 0 ) {
    … …  
    159169        _data[_minimum].right_neighbor=i;
    160170        _data[i].left_neighbor=_minimum;
    161         if ( _comp( prio, _data[_minimum].prio) ) _minimum=i;
     171        if ( _comp( value, _data[_minimum].prio) ) _minimum=i;
    162172      } else {
    163173        _data[i].right_neighbor=_data[i].left_neighbor=i;
    164174        _minimum=i;
    165175      }
    166       _data[i].prio=prio;
     176      _data[i].prio=value;
    167177      ++_num;
    168178    }
    169179
    170     /// \brief Return the item having minimum priority.
    171     ///
    172     /// This function returns the item having minimum priority.
    173     /// \pre The heap must be non-empty.
     180    /// \brief Returns the item with minimum priority relative to \c Compare.
     181    ///
     182    /// This method returns the item with minimum priority relative to \c
     183    /// Compare.
     184    /// \pre The heap must be nonempty.
    174185    Item top() const { return _data[_minimum].name; }
    175186
    176     /// \brief The minimum priority.
    177     ///
    178     /// This function returns the minimum priority.
    179     /// \pre The heap must be non-empty.
    180     Prio prio() const { return _data[_minimum].prio; }
    181 
    182     /// \brief Remove the item having minimum priority.
    183     ///
    184     /// This function removes the item having minimum priority.
     187    /// \brief Returns the minimum priority relative to \c Compare.
     188    ///
     189    /// It returns the minimum priority relative to \c Compare.
     190    /// \pre The heap must be nonempty.
     191    const Prio& prio() const { return _data[_minimum].prio; }
     192
     193    /// \brief Returns the priority of \c item.
     194    ///
     195    /// It returns the priority of \c item.
     196    /// \pre \c item must be in the heap.
     197    const Prio& operator[](const Item& item) const {
     198      return _data[_iim[item]].prio;
     199    }
     200
     201    /// \brief Deletes the item with minimum priority relative to \c Compare.
     202    ///
     203    /// This method deletes the item with minimum priority relative to \c
     204    /// Compare from the heap.
    185205    /// \pre The heap must be non-empty.
    186206    void pop() {
    … …  
    189209        _data[_minimum].in=false;
    190210        if ( _data[_minimum].degree!=0 ) {
    191           makeRoot(_data[_minimum].child);
     211          makeroot(_data[_minimum].child);
    192212          _minimum=_data[_minimum].child;
    193213          balance();
    … …  
    202222          int last_child=_data[child].left_neighbor;
    203223
    204           makeRoot(child);
     224          makeroot(child);
    205225
    206226          _data[left].right_neighbor=child;
    … …  
    215235    }
    216236
    217     /// \brief Remove the given item from the heap.
    218     ///
    219     /// This function removes the given item from the heap if it is
    220     /// already stored.
    221     /// \param item The item to delete.
    222     /// \pre \e item must be in the heap.
     237    /// \brief Deletes \c item from the heap.
     238    ///
     239    /// This method deletes \c item from the heap, if \c item was already
     240    /// stored in the heap. It is quite inefficient in Fibonacci heaps.
    223241    void erase (const Item& item) {
    224242      int i=_iim[item];
    … …  
    235253    }
    236254
    237     /// \brief The priority of the given item.
    238     ///
    239     /// This function returns the priority of the given item.
    240     /// \param item The item.
    241     /// \pre \e item must be in the heap.
    242     Prio operator[](const Item& item) const {
    243       return _data[_iim[item]].prio;
    244     }
    245 
    246     /// \brief Set the priority of an item or insert it, if it is
    247     /// not stored in the heap.
    248     ///
    249     /// This method sets the priority of the given item if it is
    250     /// already stored in the heap. Otherwise it inserts the given
    251     /// item into the heap with the given priority.
    252     /// \param item The item.
    253     /// \param prio The priority.
    254     void set (const Item& item, const Prio& prio) {
     255    /// \brief Decreases the priority of \c item to \c value.
     256    ///
     257    /// This method decreases the priority of \c item to \c value.
     258    /// \pre \c item must be stored in the heap with priority at least \c
     259    ///   value relative to \c Compare.
     260    void decrease (Item item, const Prio& value) {
    255261      int i=_iim[item];
    256       if ( i >= 0 && _data[i].in ) {
    257         if ( _comp(prio, _data[i].prio) ) decrease(item, prio);
    258         if ( _comp(_data[i].prio, prio) ) increase(item, prio);
    259       } else push(item, prio);
    260     }
    261 
    262     /// \brief Decrease the priority of an item to the given value.
    263     ///
    264     /// This function decreases the priority of an item to the given value.
    265     /// \param item The item.
    266     /// \param prio The priority.
    267     /// \pre \e item must be stored in the heap with priority at least \e prio.
    268     void decrease (const Item& item, const Prio& prio) {
    269       int i=_iim[item];
    270       _data[i].prio=prio;
     262      _data[i].prio=value;
    271263      int p=_data[i].parent;
    272264
    273       if ( p!=-1 && _comp(prio, _data[p].prio) ) {
     265      if ( p!=-1 && _comp(value, _data[p].prio) ) {
    274266        cut(i,p);
    275267        cascade(p);
    276268      }
    277       if ( _comp(prio, _data[_minimum].prio) ) _minimum=i;
    278     }
    279 
    280     /// \brief Increase the priority of an item to the given value.
    281     ///
    282     /// This function increases the priority of an item to the given value.
    283     /// \param item The item.
    284     /// \param prio The priority.
    285     /// \pre \e item must be stored in the heap with priority at most \e prio.
    286     void increase (const Item& item, const Prio& prio) {
     269      if ( _comp(value, _data[_minimum].prio) ) _minimum=i;
     270    }
     271
     272    /// \brief Increases the priority of \c item to \c value.
     273    ///
     274    /// This method sets the priority of \c item to \c value. Though
     275    /// there is no precondition on the priority of \c item, this
     276    /// method should be used only if it is indeed necessary to increase
     277    /// (relative to \c Compare) the priority of \c item, because this
     278    /// method is inefficient.
     279    void increase (Item item, const Prio& value) {
    287280      erase(item);
    288       push(item, prio);
    289     }
    290 
    291     /// \brief Return the state of an item.
    292     ///
    293     /// This method returns \c PRE_HEAP if the given item has never
    294     /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
    295     /// and \c POST_HEAP otherwise.
    296     /// In the latter case it is possible that the item will get back
    297     /// to the heap again.
    298     /// \param item The item.
     281      push(item, value);
     282    }
     283
     284
     285    /// \brief Returns if \c item is in, has already been in, or has never
     286    /// been in the heap.
     287    ///
     288    /// This method returns PRE_HEAP if \c item has never been in the
     289    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
     290    /// otherwise. In the latter case it is possible that \c item will
     291    /// get back to the heap again.
    299292    State state(const Item &item) const {
    300293      int i=_iim[item];
    … …  
    306299    }
    307300
    308     /// \brief Set the state of an item in the heap.
    309     ///
    310     /// This function sets the state of the given item in the heap.
    311     /// It can be used to manually clear the heap when it is important
    312     /// to achive better time complexity.
     301    /// \brief Sets the state of the \c item in the heap.
     302    ///
     303    /// Sets the state of the \c item in the heap. It can be used to
     304    /// manually clear the heap when it is important to achive the
     305    /// better time _complexity.
    313306    /// \param i The item.
    314307    /// \param st The state. It should not be \c IN_HEAP.
    … …  
    373366    }
    374367
    375     void makeRoot(int c) {
     368    void makeroot(int c) {
    376369      int s=c;
    377370      do {

  • lemon/gomory_hu.h

    r713 r596  
    360360    /// \c t.
    361361    /// \code
    362     /// GomoryHu<Graph> gom(g, capacities);
     362    /// GomoruHu<Graph> gom(g, capacities);
    363363    /// gom.run();
    364364    /// int cnt=0;
    365     /// for(GomoryHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
     365    /// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
    366366    /// \endcode
    367367    class MinCutNodeIt
    … …  
    457457    /// \c t.
    458458    /// \code
    459     /// GomoryHu<Graph> gom(g, capacities);
     459    /// GomoruHu<Graph> gom(g, capacities);
    460460    /// gom.run();
    461461    /// int value=0;
    462     /// for(GomoryHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
     462    /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
    463463    ///   value+=capacities[e];
    464464    /// \endcode

  • lemon/maps.h

    r726 r725  
    17901790  /// \code
    17911791  ///   std::vector<Node> v;
    1792   ///   dfs(g).processedMap(loggerBoolMap(std::back_inserter(v))).run(s);
     1792  ///   dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run();
    17931793  /// \endcode
    17941794  /// \code
    17951795  ///   std::vector<Node> v(countNodes(g));
    1796   ///   dfs(g).processedMap(loggerBoolMap(v.begin())).run(s);
     1796  ///   dfs(g,s).processedMap(loggerBoolMap(v.begin())).run();
    17971797  /// \endcode
    17981798  ///

  • lemon/min_cost_arborescence.h

    r713 r625  
    489489    /// The simplest way to execute the algorithm is to use
    490490    /// one of the member functions called \c run(...). \n
    491     /// If you need better control on the execution,
    492     /// you have to call \ref init() first, then you can add several
     491    /// If you need more control on the execution,
     492    /// first you must call \ref init(), then you can add several
    493493    /// source nodes with \ref addSource().
    494494    /// Finally \ref start() will perform the arborescence

  • lemon/preflow.h

    r715 r641  
    5353    /// The type of the map that stores the flow values.
    5454    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    55 #ifdef DOXYGEN
    56     typedef GR::ArcMap<Value> FlowMap;
    57 #else
    5855    typedef typename Digraph::template ArcMap<Value> FlowMap;
    59 #endif
    6056
    6157    /// \brief Instantiates a FlowMap.
    … …  
    7268    /// The elevator type used by Preflow algorithm.
    7369    ///
    74     /// \sa Elevator, LinkedElevator
    75 #ifdef DOXYGEN
    76     typedef lemon::Elevator<GR, GR::Node> Elevator;
    77 #else
    78     typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
    79 #endif
     70    /// \sa Elevator
     71    /// \sa LinkedElevator
     72    typedef LinkedElevator<Digraph, typename Digraph::Node> Elevator;
    8073
    8174    /// \brief Instantiates an Elevator.
    … …  
    10598  /// "flow of maximum value" in a digraph.
    10699  /// The preflow algorithms are the fastest known maximum
    107   /// flow algorithms. The current implementation uses a mixture of the
     100  /// flow algorithms. The current implementation use a mixture of the
    108101  /// \e "highest label" and the \e "bound decrease" heuristics.
    109102  /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
    … …  
    379372    }
    380373
    381     /// \brief Sets the tolerance used by the algorithm.
    382     ///
    383     /// Sets the tolerance object used by the algorithm.
    384     /// \return <tt>(*this)</tt>
    385     Preflow& tolerance(const Tolerance& tolerance) {
     374    /// \brief Sets the tolerance used by algorithm.
     375    ///
     376    /// Sets the tolerance used by algorithm.
     377    Preflow& tolerance(const Tolerance& tolerance) const {
    386378      _tolerance = tolerance;
    387379      return *this;
    … …  
    390382    /// \brief Returns a const reference to the tolerance.
    391383    ///
    392     /// Returns a const reference to the tolerance object used by
    393     /// the algorithm.
     384    /// Returns a const reference to the tolerance.
    394385    const Tolerance& tolerance() const {
    395       return _tolerance;
     386      return tolerance;
    396387    }
    397388
    … …  
    399390    /// The simplest way to execute the preflow algorithm is to use
    400391    /// \ref run() or \ref runMinCut().\n
    401     /// If you need better control on the initial solution or the execution,
    402     /// you have to call one of the \ref init() functions first, then
     392    /// If you need more control on the initial solution or the execution,
     393    /// first you have to call one of the \ref init() functions, then
    403394    /// \ref startFirstPhase() and if you need it \ref startSecondPhase().
    404395

  • lemon/radix_heap.h

    r711 r683  
    2020#define LEMON_RADIX_HEAP_H
    2121
    22 ///\ingroup heaps
     22///\ingroup auxdat
    2323///\file
    24 ///\brief Radix heap implementation.
     24///\brief Radix Heap implementation.
    2525
    2626#include <vector>
    … …  
    3030
    3131
    32   /// \ingroup heaps
     32  /// \ingroup auxdata
    3333  ///
    34   /// \brief Radix heap data structure.
     34  /// \brief A Radix Heap implementation.
    3535  ///
    36   /// This class implements the \e radix \e heap data structure.
    37   /// It practically conforms to the \ref concepts::Heap "heap concept",
    38   /// but it has some limitations due its special implementation.
    39   /// The type of the priorities must be \c int and the priority of an
    40   /// item cannot be decreased under the priority of the last removed item.
     36  /// This class implements the \e radix \e heap data structure. A \e heap
     37  /// is a data structure for storing items with specified values called \e
     38  /// priorities in such a way that finding the item with minimum priority is
     39  /// efficient. This heap type can store only items with \e int priority.
     40  /// In a heap one can change the priority of an item, add or erase an
     41  /// item, but the priority cannot be decreased under the last removed
     42  /// item's priority.
    4143  ///
    42   /// \tparam IM A read-writable item map with \c int values, used
    43   /// internally to handle the cross references.
     44  /// \param IM A read and writable Item int map, used internally
     45  /// to handle the cross references.
     46  ///
     47  /// \see BinHeap
     48  /// \see Dijkstra
    4449  template <typename IM>
    4550  class RadixHeap {
    4651
    4752  public:
    48 
    49     /// Type of the item-int map.
     53    typedef typename IM::Key Item;
     54    typedef int Prio;
    5055    typedef IM ItemIntMap;
    51     /// Type of the priorities.
    52     typedef int Prio;
    53     /// Type of the items stored in the heap.
    54     typedef typename ItemIntMap::Key Item;
    5556
    5657    /// \brief Exception thrown by RadixHeap.
    5758    ///
    58     /// This exception is thrown when an item is inserted into a
    59     /// RadixHeap with a priority smaller than the last erased one.
     59    /// This Exception is thrown when a smaller priority
     60    /// is inserted into the \e RadixHeap then the last time erased.
    6061    /// \see RadixHeap
    61     class PriorityUnderflowError : public Exception {
     62
     63    class UnderFlowPriorityError : public Exception {
    6264    public:
    6365      virtual const char* what() const throw() {
    64         return "lemon::RadixHeap::PriorityUnderflowError";
     66        return "lemon::RadixHeap::UnderFlowPriorityError";
    6567      }
    6668    };
    6769
    68     /// \brief Type to represent the states of the items.
    69     ///
    70     /// Each item has a state associated to it. It can be "in heap",
    71     /// "pre-heap" or "post-heap". The latter two are indifferent from the
     70    /// \brief Type to represent the items states.
     71    ///
     72    /// Each Item element have a state associated to it. It may be "in heap",
     73    /// "pre heap" or "post heap". The latter two are indifferent from the
    7274    /// heap's point of view, but may be useful to the user.
    7375    ///
    74     /// The item-int map must be initialized in such way that it assigns
    75     /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
     76    /// The ItemIntMap \e should be initialized in such way that it maps
     77    /// PRE_HEAP (-1) to any element to be put in the heap...
    7678    enum State {
    77       IN_HEAP = 0,    ///< = 0.
    78       PRE_HEAP = -1,  ///< = -1.
    79       POST_HEAP = -2  ///< = -2.
     79      IN_HEAP = 0,
     80      PRE_HEAP = -1,
     81      POST_HEAP = -2
    8082    };
    8183
    … …  
    9597    };
    9698
    97     std::vector<RadixItem> _data;
    98     std::vector<RadixBox> _boxes;
     99    std::vector<RadixItem> data;
     100    std::vector<RadixBox> boxes;
    99101
    100102    ItemIntMap &_iim;
    101103
     104
    102105  public:
    103 
    104     /// \brief Constructor.
    105     ///
    106     /// Constructor.
    107     /// \param map A map that assigns \c int values to the items.
    108     /// It is used internally to handle the cross references.
    109     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    110     /// \param minimum The initial minimum value of the heap.
    111     /// \param capacity The initial capacity of the heap.
    112     RadixHeap(ItemIntMap &map, int minimum = 0, int capacity = 0)
    113       : _iim(map)
    114     {
    115       _boxes.push_back(RadixBox(minimum, 1));
    116       _boxes.push_back(RadixBox(minimum + 1, 1));
    117       while (lower(_boxes.size() - 1, capacity + minimum - 1)) {
     106    /// \brief The constructor.
     107    ///
     108    /// The constructor.
     109    ///
     110    /// \param map It should be given to the constructor, since it is used
     111    /// internally to handle the cross references. The value of the map
     112    /// should be PRE_HEAP (-1) for each element.
     113    ///
     114    /// \param minimal The initial minimal value of the heap.
     115    /// \param capacity It determines the initial capacity of the heap.
     116    RadixHeap(ItemIntMap &map, int minimal = 0, int capacity = 0)
     117      : _iim(map) {
     118      boxes.push_back(RadixBox(minimal, 1));
     119      boxes.push_back(RadixBox(minimal + 1, 1));
     120      while (lower(boxes.size() - 1, capacity + minimal - 1)) {
    118121        extend();
    119122      }
    120123    }
    121124
    122     /// \brief The number of items stored in the heap.
    123     ///
    124     /// This function returns the number of items stored in the heap.
    125     int size() const { return _data.size(); }
    126 
    127     /// \brief Check if the heap is empty.
    128     ///
    129     /// This function returns \c true if the heap is empty.
    130     bool empty() const { return _data.empty(); }
    131 
    132     /// \brief Make the heap empty.
    133     ///
    134     /// This functon makes the heap empty.
    135     /// It does not change the cross reference map. If you want to reuse
    136     /// a heap that is not surely empty, you should first clear it and
    137     /// then you should set the cross reference map to \c PRE_HEAP
    138     /// for each item.
    139     /// \param minimum The minimum value of the heap.
    140     /// \param capacity The capacity of the heap.
    141     void clear(int minimum = 0, int capacity = 0) {
    142       _data.clear(); _boxes.clear();
    143       _boxes.push_back(RadixBox(minimum, 1));
    144       _boxes.push_back(RadixBox(minimum + 1, 1));
    145       while (lower(_boxes.size() - 1, capacity + minimum - 1)) {
     125    /// The number of items stored in the heap.
     126    ///
     127    /// \brief Returns the number of items stored in the heap.
     128    int size() const { return data.size(); }
     129    /// \brief Checks if the heap stores no items.
     130    ///
     131    /// Returns \c true if and only if the heap stores no items.
     132    bool empty() const { return data.empty(); }
     133
     134    /// \brief Make empty this heap.
     135    ///
     136    /// Make empty this heap. It does not change the cross reference
     137    /// map.  If you want to reuse a heap what is not surely empty you
     138    /// should first clear the heap and after that you should set the
     139    /// cross reference map for each item to \c PRE_HEAP.
     140    void clear(int minimal = 0, int capacity = 0) {
     141      data.clear(); boxes.clear();
     142      boxes.push_back(RadixBox(minimal, 1));
     143      boxes.push_back(RadixBox(minimal + 1, 1));
     144      while (lower(boxes.size() - 1, capacity + minimal - 1)) {
    146145        extend();
    147146      }
    … …  
    151150
    152151    bool upper(int box, Prio pr) {
    153       return pr < _boxes[box].min;
     152      return pr < boxes[box].min;
    154153    }
    155154
    156155    bool lower(int box, Prio pr) {
    157       return pr >= _boxes[box].min + _boxes[box].size;
    158     }
    159 
    160     // Remove item from the box list
     156      return pr >= boxes[box].min + boxes[box].size;
     157    }
     158
     159    /// \brief Remove item from the box list.
    161160    void remove(int index) {
    162       if (_data[index].prev >= 0) {
    163         _data[_data[index].prev].next = _data[index].next;
     161      if (data[index].prev >= 0) {
     162        data[data[index].prev].next = data[index].next;
    164163      } else {
    165         _boxes[_data[index].box].first = _data[index].next;
    166       }
    167       if (_data[index].next >= 0) {
    168         _data[_data[index].next].prev = _data[index].prev;
    169       }
    170     }
    171 
    172     // Insert item into the box list
     164        boxes[data[index].box].first = data[index].next;
     165      }
     166      if (data[index].next >= 0) {
     167        data[data[index].next].prev = data[index].prev;
     168      }
     169    }
     170
     171    /// \brief Insert item into the box list.
    173172    void insert(int box, int index) {
    174       if (_boxes[box].first == -1) {
    175         _boxes[box].first = index;
    176         _data[index].next = _data[index].prev = -1;
     173      if (boxes[box].first == -1) {
     174        boxes[box].first = index;
     175        data[index].next = data[index].prev = -1;
    177176      } else {
    178         _data[index].next = _boxes[box].first;
    179         _data[_boxes[box].first].prev = index;
    180         _data[index].prev = -1;
    181         _boxes[box].first = index;
    182       }
    183       _data[index].box = box;
    184     }
    185 
    186     // Add a new box to the box list
     177        data[index].next = boxes[box].first;
     178        data[boxes[box].first].prev = index;
     179        data[index].prev = -1;
     180        boxes[box].first = index;
     181      }
     182      data[index].box = box;
     183    }
     184
     185    /// \brief Add a new box to the box list.
    187186    void extend() {
    188       int min = _boxes.back().min + _boxes.back().size;
    189       int bs = 2 * _boxes.back().size;
    190       _boxes.push_back(RadixBox(min, bs));
    191     }
    192 
    193     // Move an item up into the proper box.
    194     void bubbleUp(int index) {
    195       if (!lower(_data[index].box, _data[index].prio)) return;
     187      int min = boxes.back().min + boxes.back().size;
     188      int bs = 2 * boxes.back().size;
     189      boxes.push_back(RadixBox(min, bs));
     190    }
     191
     192    /// \brief Move an item up into the proper box.
     193    void bubble_up(int index) {
     194      if (!lower(data[index].box, data[index].prio)) return;
    196195      remove(index);
    197       int box = findUp(_data[index].box, _data[index].prio);
     196      int box = findUp(data[index].box, data[index].prio);
    198197      insert(box, index);
    199198    }
    200199
    201     // Find up the proper box for the item with the given priority
     200    /// \brief Find up the proper box for the item with the given prio.
    202201    int findUp(int start, int pr) {
    203202      while (lower(start, pr)) {
    204         if (++start == int(_boxes.size())) {
     203        if (++start == int(boxes.size())) {
    205204          extend();
    206205        }
    … …  
    209208    }
    210209
    211     // Move an item down into the proper box
    212     void bubbleDown(int index) {
    213       if (!upper(_data[index].box, _data[index].prio)) return;
     210    /// \brief Move an item down into the proper box.
     211    void bubble_down(int index) {
     212      if (!upper(data[index].box, data[index].prio)) return;
    214213      remove(index);
    215       int box = findDown(_data[index].box, _data[index].prio);
     214      int box = findDown(data[index].box, data[index].prio);
    216215      insert(box, index);
    217216    }
    218217
    219     // Find down the proper box for the item with the given priority
     218    /// \brief Find up the proper box for the item with the given prio.
    220219    int findDown(int start, int pr) {
    221220      while (upper(start, pr)) {
    222         if (--start < 0) throw PriorityUnderflowError();
     221        if (--start < 0) throw UnderFlowPriorityError();
    223222      }
    224223      return start;
    225224    }
    226225
    227     // Find the first non-empty box
     226    /// \brief Find the first not empty box.
    228227    int findFirst() {
    229228      int first = 0;
    230       while (_boxes[first].first == -1) ++first;
     229      while (boxes[first].first == -1) ++first;
    231230      return first;
    232231    }
    233232
    234     // Gives back the minimum priority of the given box
     233    /// \brief Gives back the minimal prio of the box.
    235234    int minValue(int box) {
    236       int min = _data[_boxes[box].first].prio;
    237       for (int k = _boxes[box].first; k != -1; k = _data[k].next) {
    238         if (_data[k].prio < min) min = _data[k].prio;
     235      int min = data[boxes[box].first].prio;
     236      for (int k = boxes[box].first; k != -1; k = data[k].next) {
     237        if (data[k].prio < min) min = data[k].prio;
    239238      }
    240239      return min;
    241240    }
    242241
    243     // Rearrange the items of the heap and make the first box non-empty
     242    /// \brief Rearrange the items of the heap and makes the
     243    /// first box not empty.
    244244    void moveDown() {
    245245      int box = findFirst();
    … …  
    247247      int min = minValue(box);
    248248      for (int i = 0; i <= box; ++i) {
    249         _boxes[i].min = min;
    250         min += _boxes[i].size;
    251       }
    252       int curr = _boxes[box].first, next;
     249        boxes[i].min = min;
     250        min += boxes[i].size;
     251      }
     252      int curr = boxes[box].first, next;
    253253      while (curr != -1) {
    254         next = _data[curr].next;
    255         bubbleDown(curr);
     254        next = data[curr].next;
     255        bubble_down(curr);
    256256        curr = next;
    257257      }
    258258    }
    259259
    260     void relocateLast(int index) {
    261       if (index != int(_data.size()) - 1) {
    262         _data[index] = _data.back();
    263         if (_data[index].prev != -1) {
    264           _data[_data[index].prev].next = index;
     260    void relocate_last(int index) {
     261      if (index != int(data.size()) - 1) {
     262        data[index] = data.back();
     263        if (data[index].prev != -1) {
     264          data[data[index].prev].next = index;
    265265        } else {
    266           _boxes[_data[index].box].first = index;
     266          boxes[data[index].box].first = index;
    267267        }
    268         if (_data[index].next != -1) {
    269           _data[_data[index].next].prev = index;
     268        if (data[index].next != -1) {
     269          data[data[index].next].prev = index;
    270270        }
    271         _iim[_data[index].item] = index;
    272       }
    273       _data.pop_back();
     271        _iim[data[index].item] = index;
     272      }
     273      data.pop_back();
    274274    }
    275275
    … …  
    278278    /// \brief Insert an item into the heap with the given priority.
    279279    ///
    280     /// This function inserts the given item into the heap with the
    281     /// given priority.
     280    /// Adds \c i to the heap with priority \c p.
    282281    /// \param i The item to insert.
    283282    /// \param p The priority of the item.
    284     /// \pre \e i must not be stored in the heap.
    285     /// \warning This method may throw an \c UnderFlowPriorityException.
    286283    void push(const Item &i, const Prio &p) {
    287       int n = _data.size();
     284      int n = data.size();
    288285      _iim.set(i, n);
    289       _data.push_back(RadixItem(i, p));
    290       while (lower(_boxes.size() - 1, p)) {
     286      data.push_back(RadixItem(i, p));
     287      while (lower(boxes.size() - 1, p)) {
    291288        extend();
    292289      }
    293       int box = findDown(_boxes.size() - 1, p);
     290      int box = findDown(boxes.size() - 1, p);
    294291      insert(box, n);
    295292    }
    296293
    297     /// \brief Return the item having minimum priority.
    298     ///
    299     /// This function returns the item having minimum priority.
    300     /// \pre The heap must be non-empty.
     294    /// \brief Returns the item with minimum priority.
     295    ///
     296    /// This method returns the item with minimum priority.
     297    /// \pre The heap must be nonempty.
    301298    Item top() const {
    302299      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
    303       return _data[_boxes[0].first].item;
    304     }
    305 
    306     /// \brief The minimum priority.
    307     ///
    308     /// This function returns the minimum priority.
    309     /// \pre The heap must be non-empty.
     300      return data[boxes[0].first].item;
     301    }
     302
     303    /// \brief Returns the minimum priority.
     304    ///
     305    /// It returns the minimum priority.
     306    /// \pre The heap must be nonempty.
    310307    Prio prio() const {
    311308      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
    312       return _data[_boxes[0].first].prio;
     309      return data[boxes[0].first].prio;
    313310     }
    314311
    315     /// \brief Remove the item having minimum priority.
    316     ///
    317     /// This function removes the item having minimum priority.
     312    /// \brief Deletes the item with minimum priority.
     313    ///
     314    /// This method deletes the item with minimum priority.
    318315    /// \pre The heap must be non-empty.
    319316    void pop() {
    320317      moveDown();
    321       int index = _boxes[0].first;
    322       _iim[_data[index].item] = POST_HEAP;
     318      int index = boxes[0].first;
     319      _iim[data[index].item] = POST_HEAP;
    323320      remove(index);
    324       relocateLast(index);
    325     }
    326 
    327     /// \brief Remove the given item from the heap.
    328     ///
    329     /// This function removes the given item from the heap if it is
    330     /// already stored.
    331     /// \param i The item to delete.
    332     /// \pre \e i must be in the heap.
     321      relocate_last(index);
     322    }
     323
     324    /// \brief Deletes \c i from the heap.
     325    ///
     326    /// This method deletes item \c i from the heap, if \c i was
     327    /// already stored in the heap.
     328    /// \param i The item to erase.
    333329    void erase(const Item &i) {
    334330      int index = _iim[i];
    335331      _iim[i] = POST_HEAP;
    336332      remove(index);
    337       relocateLast(index);
     333      relocate_last(index);
    338334   }
    339335
    340     /// \brief The priority of the given item.
    341     ///
    342     /// This function returns the priority of the given item.
    343     /// \param i The item.
    344     /// \pre \e i must be in the heap.
     336    /// \brief Returns the priority of \c i.
     337    ///
     338    /// This function returns the priority of item \c i.
     339    /// \pre \c i must be in the heap.
     340    /// \param i The item.
    345341    Prio operator[](const Item &i) const {
    346342      int idx = _iim[i];
    347       return _data[idx].prio;
    348     }
    349 
    350     /// \brief Set the priority of an item or insert it, if it is
    351     /// not stored in the heap.
    352     ///
    353     /// This method sets the priority of the given item if it is
    354     /// already stored in the heap. Otherwise it inserts the given
    355     /// item into the heap with the given priority.
     343      return data[idx].prio;
     344    }
     345
     346    /// \brief \c i gets to the heap with priority \c p independently
     347    /// if \c i was already there.
     348    ///
     349    /// This method calls \ref push(\c i, \c p) if \c i is not stored
     350    /// in the heap and sets the priority of \c i to \c p otherwise.
     351    /// It may throw an \e UnderFlowPriorityException.
    356352    /// \param i The item.
    357353    /// \param p The priority.
    358     /// \pre \e i must be in the heap.
    359     /// \warning This method may throw an \c UnderFlowPriorityException.
    360354    void set(const Item &i, const Prio &p) {
    361355      int idx = _iim[i];
    … …  
    363357        push(i, p);
    364358      }
    365       else if( p >= _data[idx].prio ) {
    366         _data[idx].prio = p;
    367         bubbleUp(idx);
     359      else if( p >= data[idx].prio ) {
     360        data[idx].prio = p;
     361        bubble_up(idx);
    368362      } else {
    369         _data[idx].prio = p;
    370         bubbleDown(idx);
    371       }
    372     }
    373 
    374     /// \brief Decrease the priority of an item to the given value.
    375     ///
    376     /// This function decreases the priority of an item to the given value.
     363        data[idx].prio = p;
     364        bubble_down(idx);
     365      }
     366    }
     367
     368
     369    /// \brief Decreases the priority of \c i to \c p.
     370    ///
     371    /// This method decreases the priority of item \c i to \c p.
     372    /// \pre \c i must be stored in the heap with priority at least \c p, and
     373    /// \c should be greater or equal to the last removed item's priority.
    377374    /// \param i The item.
    378375    /// \param p The priority.
    379     /// \pre \e i must be stored in the heap with priority at least \e p.
    380     /// \warning This method may throw an \c UnderFlowPriorityException.
    381376    void decrease(const Item &i, const Prio &p) {
    382377      int idx = _iim[i];
    383       _data[idx].prio = p;
    384       bubbleDown(idx);
    385     }
    386 
    387     /// \brief Increase the priority of an item to the given value.
    388     ///
    389     /// This function increases the priority of an item to the given value.
     378      data[idx].prio = p;
     379      bubble_down(idx);
     380    }
     381
     382    /// \brief Increases the priority of \c i to \c p.
     383    ///
     384    /// This method sets the priority of item \c i to \c p.
     385    /// \pre \c i must be stored in the heap with priority at most \c p
    390386    /// \param i The item.
    391387    /// \param p The priority.
    392     /// \pre \e i must be stored in the heap with priority at most \e p.
    393388    void increase(const Item &i, const Prio &p) {
    394389      int idx = _iim[i];
    395       _data[idx].prio = p;
    396       bubbleUp(idx);
    397     }
    398 
    399     /// \brief Return the state of an item.
    400     ///
    401     /// This method returns \c PRE_HEAP if the given item has never
    402     /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
    403     /// and \c POST_HEAP otherwise.
    404     /// In the latter case it is possible that the item will get back
    405     /// to the heap again.
     390      data[idx].prio = p;
     391      bubble_up(idx);
     392    }
     393
     394    /// \brief Returns if \c item is in, has already been in, or has
     395    /// never been in the heap.
     396    ///
     397    /// This method returns PRE_HEAP if \c item has never been in the
     398    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
     399    /// otherwise. In the latter case it is possible that \c item will
     400    /// get back to the heap again.
    406401    /// \param i The item.
    407402    State state(const Item &i) const {
    … …  
    411406    }
    412407
    413     /// \brief Set the state of an item in the heap.
    414     ///
    415     /// This function sets the state of the given item in the heap.
    416     /// It can be used to manually clear the heap when it is important
    417     /// to achive better time complexity.
     408    /// \brief Sets the state of the \c item in the heap.
     409    ///
     410    /// Sets the state of the \c item in the heap. It can be used to
     411    /// manually clear the heap when it is important to achive the
     412    /// better time complexity.
    418413    /// \param i The item.
    419414    /// \param st The state. It should not be \c IN_HEAP.

  • test/CMakeLists.txt

    r698 r679  
    1010SET(TESTS
    1111  adaptors_test
    12   bellman_ford_test
    1312  bfs_test
    1413  circulation_test

  • test/Makefile.am

    r698 r649  
    88check_PROGRAMS += \
    99        test/adaptors_test \
    10         test/bellman_ford_test \
    1110        test/bfs_test \
    1211        test/circulation_test \
    … …  
    5453
    5554test_adaptors_test_SOURCES = test/adaptors_test.cc
    56 test_bellman_ford_test_SOURCES = test/bellman_ford_test.cc
    5755test_bfs_test_SOURCES = test/bfs_test.cc
    5856test_circulation_test_SOURCES = test/circulation_test.cc

  • test/circulation_test.cc

    r689 r611  
    8888    .supplyMap(supply)
    8989    .flowMap(flow);
    90  
    91   const CirculationType::Elevator& elev = const_circ_test.elevator();
    92   circ_test.elevator(const_cast<CirculationType::Elevator&>(elev));
    93   CirculationType::Tolerance tol = const_circ_test.tolerance();
    94   circ_test.tolerance(tol);
    9590
    9691  circ_test.init();

  • test/heap_test.cc

    r702 r681  
    2626
    2727#include <lemon/smart_graph.h>
     28
    2829#include <lemon/lgf_reader.h>
    2930#include <lemon/dijkstra.h>
    … …  
    3132
    3233#include <lemon/bin_heap.h>
    33 #include <lemon/fourary_heap.h>
    34 #include <lemon/kary_heap.h>
    3534#include <lemon/fib_heap.h>
    36 #include <lemon/pairing_heap.h>
    3735#include <lemon/radix_heap.h>
    38 #include <lemon/binom_heap.h>
    3936#include <lemon/bucket_heap.h>
    4037
    … …  
    9390void heapSortTest() {
    9491  RangeMap<int> map(test_len, -1);
     92
    9593  Heap heap(map);
    9694
    9795  std::vector<int> v(test_len);
     96
    9897  for (int i = 0; i < test_len; ++i) {
    9998    v[i] = test_seq[i];
    … …  
    102101  std::sort(v.begin(), v.end());
    103102  for (int i = 0; i < test_len; ++i) {
    104     check(v[i] == heap.prio(), "Wrong order in heap sort.");
     103    check(v[i] == heap.prio() ,"Wrong order in heap sort.");
    105104    heap.pop();
    106105  }
    … …  
    114113
    115114  std::vector<int> v(test_len);
     115
    116116  for (int i = 0; i < test_len; ++i) {
    117117    v[i] = test_seq[i];
    … …  
    124124  std::sort(v.begin(), v.end());
    125125  for (int i = 0; i < test_len; ++i) {
    126     check(v[i] == heap.prio(), "Wrong order in heap increase test.");
     126    check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
    127127    heap.pop();
    128128  }
    129129}
     130
     131
    130132
    131133template <typename Heap>
    … …  
    143145    if (dijkstra.reached(s)) {
    144146      check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
    145              "Error in shortest path tree.");
     147             "Error in a shortest path tree!");
    146148    }
    147149  }
    … …  
    152154      Node s = digraph.source(a);
    153155      check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
    154              "Error in shortest path tree.");
     156             "Error in a shortest path tree!");
    155157    }
    156158  }
    … …  
    174176    run();
    175177
    176   // BinHeap
    177178  {
    178179    typedef BinHeap<Prio, ItemIntMap> IntHeap;
    … …  
    186187  }
    187188
    188   // FouraryHeap
    189   {
    190     typedef FouraryHeap<Prio, ItemIntMap> IntHeap;
    191     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    192     heapSortTest<IntHeap>();
    193     heapIncreaseTest<IntHeap>();
    194 
    195     typedef FouraryHeap<Prio, IntNodeMap > NodeHeap;
    196     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    197     dijkstraHeapTest<NodeHeap>(digraph, length, source);
    198   }
    199 
    200   // KaryHeap
    201   {
    202     typedef KaryHeap<Prio, ItemIntMap> IntHeap;
    203     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    204     heapSortTest<IntHeap>();
    205     heapIncreaseTest<IntHeap>();
    206 
    207     typedef KaryHeap<Prio, IntNodeMap > NodeHeap;
    208     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    209     dijkstraHeapTest<NodeHeap>(digraph, length, source);
    210   }
    211 
    212   // FibHeap
    213189  {
    214190    typedef FibHeap<Prio, ItemIntMap> IntHeap;
    … …  
    222198  }
    223199
    224   // PairingHeap
    225   {
    226     typedef PairingHeap<Prio, ItemIntMap> IntHeap;
    227     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    228     heapSortTest<IntHeap>();
    229     heapIncreaseTest<IntHeap>();
    230 
    231     typedef PairingHeap<Prio, IntNodeMap > NodeHeap;
    232     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    233     dijkstraHeapTest<NodeHeap>(digraph, length, source);
    234   }
    235 
    236   // RadixHeap
    237200  {
    238201    typedef RadixHeap<ItemIntMap> IntHeap;
    … …  
    246209  }
    247210
    248   // BinomHeap
    249   {
    250     typedef BinomHeap<Prio, ItemIntMap> IntHeap;
    251     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    252     heapSortTest<IntHeap>();
    253     heapIncreaseTest<IntHeap>();
    254 
    255     typedef BinomHeap<Prio, IntNodeMap > NodeHeap;
    256     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    257     dijkstraHeapTest<NodeHeap>(digraph, length, source);
    258   }
    259 
    260   // BucketHeap, SimpleBucketHeap
    261211  {
    262212    typedef BucketHeap<ItemIntMap> IntHeap;
    … …  
    268218    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    269219    dijkstraHeapTest<NodeHeap>(digraph, length, source);
    270 
    271     typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap;
    272     heapSortTest<SimpleIntHeap>();
    273   }
     220  }
     221
    274222
    275223  return 0;

  • test/maps_test.cc

    r726 r724  
    580580  }
    581581
    582   // CrossRefMap
    583   {
    584     typedef SmartDigraph Graph;
    585     DIGRAPH_TYPEDEFS(Graph);
    586 
    587     checkConcept<ReadWriteMap<Node, int>,
    588                  CrossRefMap<Graph, Node, int> >();
    589    
    590     Graph gr;
    591     typedef CrossRefMap<Graph, Node, char> CRMap;
    592     typedef CRMap::ValueIterator ValueIt;
    593     CRMap map(gr);
    594    
    595     Node n0 = gr.addNode();
    596     Node n1 = gr.addNode();
    597     Node n2 = gr.addNode();
    598    
    599     map.set(n0, 'A');
    600     map.set(n1, 'B');
    601     map.set(n2, 'C');
    602     map.set(n2, 'A');
    603     map.set(n0, 'C');
    604 
    605     check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A',
    606           "Wrong CrossRefMap");
    607     check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap");
    608     check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");
    609     check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap");
    610 
    611     ValueIt it = map.beginValue();
    612     check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
    613           it == map.endValue(), "Wrong value iterator");
    614   }
    615  
    616582  // Iterable bool map
    617583  {

  • test/preflow_test.cc

    r689 r585  
    9595  PreflowType preflow_test(g, cap, n, n);
    9696  const PreflowType& const_preflow_test = preflow_test;
    97  
    98   const PreflowType::Elevator& elev = const_preflow_test.elevator();
    99   preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev));
    100   PreflowType::Tolerance tol = const_preflow_test.tolerance();
    101   preflow_test.tolerance(tol);
    10297
    10398  preflow_test

  • tools/lemon-0.x-to-1.x.sh

    r691 r574  
    3636        -e "s/Edge\>/_Ar_c_label_/g"\
    3737        -e "s/\<edge\>/_ar_c_label_/g"\
    38         -e "s/_edge\>/__ar_c_label_/g"\
     38        -e "s/_edge\>/_ar_c_label_/g"\
    3939        -e "s/Edges\>/_Ar_c_label_s/g"\
    4040        -e "s/\<edges\>/_ar_c_label_s/g"\
    41         -e "s/_edges\>/__ar_c_label_s/g"\
     41        -e "s/_edges\>/_ar_c_label_s/g"\
    4242        -e "s/\([Ee]\)dge\([a-z]\)/_\1d_ge_label_\2/g"\
    4343        -e "s/\([a-z]\)edge/\1_ed_ge_label_/g"\
    … …  
    6969        -e "s/_GR_APH_TY_PEDE_FS_label_/GRAPH_TYPEDEFS/g"\
    7070        -e "s/_DIGR_APH_TY_PEDE_FS_label_/DIGRAPH_TYPEDEFS/g"\
    71         -e "s/\<digraph_adaptor\.h\>/adaptors.h/g"\
    72         -e "s/\<digraph_utils\.h\>/core.h/g"\
    73         -e "s/\<digraph_reader\.h\>/lgf_reader.h/g"\
    74         -e "s/\<digraph_writer\.h\>/lgf_writer.h/g"\
    75         -e "s/\<topology\.h\>/connectivity.h/g"\
    7671        -e "s/DigraphToEps/GraphToEps/g"\
    7772        -e "s/digraphToEps/graphToEps/g"\
Note: See TracChangeset for help on using the changeset viewer.