COIN-OR::LEMON - Graph Library

Changes in / [741:10c9c3a35b83:742:8e68671af789] in lemon-main


Ignore:
Files:
7 added
29 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r735 r742  
    227227
    228228/**
    229 @defgroup matrices Matrices
    230 @ingroup datas
    231 \brief Two dimensional data storages implemented in LEMON.
    232 
    233 This group contains two dimensional data storages implemented in LEMON.
    234 */
    235 
    236 /**
    237229@defgroup paths Path Structures
    238230@ingroup datas
     
    247239any kind of path structure.
    248240
    249 \sa lemon::concepts::Path
     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
     249This group contains the heap structures implemented in LEMON.
     250
     251LEMON provides several heap classes. They are efficient implementations
     252of the abstract data type \e priority \e queue. They store items with
     253specified values called \e priorities in such a way that finding and
     254removing the item with minimum priority are efficient.
     255The basic operations are adding and erasing items, changing the priority
     256of an item, etc.
     257
     258Heaps are crucial in several algorithms, such as Dijkstra and Prim.
     259The heap implementations have the same interface, thus any of them can be
     260used 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
     270This group contains two dimensional data storages implemented in LEMON.
    250271*/
    251272
     
    257278This group contains some data structures implemented in LEMON in
    258279order 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
     287This 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
     301This group contains two dimensional data storages implemented in LEMON.
    259302*/
    260303
     
    299342
    300343/**
     344@defgroup spantree Minimum Spanning Tree Algorithms
     345@ingroup algs
     346\brief Algorithms for finding minimum cost spanning trees and arborescences.
     347
     348This group contains the algorithms for finding minimum cost spanning
     349trees and arborescences.
     350*/
     351
     352/**
    301353@defgroup max_flow Maximum Flow Algorithms
    302354@ingroup algs
     
    376428
    377429\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    378     \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
     430    \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
    379431
    380432LEMON contains several algorithms related to minimum cut problems:
     
    389441If you want to find minimum cut just between two distinict nodes,
    390442see 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 
    398 This group contains the algorithms for discovering the graph properties
    399 like 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 
    410 This group contains the algorithms for planarity checking,
    411 embedding and drawing.
    412 
    413 \image html planar.png
    414 \image latex planar.eps "Plane graph" width=\textwidth
    415443*/
    416444
     
    456484
    457485/**
    458 @defgroup spantree Minimum Spanning Tree Algorithms
    459 @ingroup algs
    460 \brief Algorithms for finding minimum cost spanning trees and arborescences.
    461 
    462 This group contains the algorithms for finding minimum cost spanning
    463 trees and arborescences.
     486@defgroup graph_properties Connectivity and Other Graph Properties
     487@ingroup algs
     488\brief Algorithms for discovering the graph properties
     489
     490This group contains the algorithms for discovering the graph properties
     491like 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
     502This group contains the algorithms for planarity checking,
     503embedding and drawing.
     504
     505\image html planar.png
     506\image latex planar.eps "Plane graph" width=\textwidth
     507*/
     508
     509/**
     510@defgroup approx Approximation Algorithms
     511@ingroup algs
     512\brief Approximation algorithms.
     513
     514This group contains the approximation and heuristic algorithms
     515implemented in LEMON.
    464516*/
    465517
     
    471523This group contains some algorithms implemented in LEMON
    472524in order to make it easier to implement complex algorithms.
    473 */
    474 
    475 /**
    476 @defgroup approx Approximation Algorithms
    477 @ingroup algs
    478 \brief Approximation algorithms.
    479 
    480 This group contains the approximation and heuristic algorithms
    481 implemented in LEMON.
    482525*/
    483526
     
    588631
    589632/**
    590 @defgroup dimacs_group DIMACS format
     633@defgroup dimacs_group DIMACS Format
    591634@ingroup io_group
    592635\brief Read and write files in DIMACS format
     
    650693
    651694/**
     695@defgroup tools Standalone Utility Applications
     696
     697Some utility applications are listed here.
     698
     699The standard compilation procedure (<tt>./configure;make</tt>) will compile
     700them, as well.
     701*/
     702
     703/**
    652704\anchor demoprograms
    653705
     
    661713*/
    662714
    663 /**
    664 @defgroup tools Standalone Utility Applications
    665 
    666 Some utility applications are listed here.
    667 
    668 The standard compilation procedure (<tt>./configure;make</tt>) will compile
    669 them, as well.
    670 */
    671 
    672715}
  • lemon/Makefile.am

    r686 r708  
    5858        lemon/arg_parser.h \
    5959        lemon/assert.h \
     60        lemon/bellman_ford.h \
    6061        lemon/bfs.h \
    6162        lemon/bin_heap.h \
     63        lemon/binom_heap.h \
    6264        lemon/bucket_heap.h \
    6365        lemon/cbc.h \
     
    7981        lemon/euler.h \
    8082        lemon/fib_heap.h \
     83        lemon/fourary_heap.h \
    8184        lemon/full_graph.h \
    8285        lemon/glpk.h \
     
    8588        lemon/grid_graph.h \
    8689        lemon/hypercube_graph.h \
     90        lemon/kary_heap.h \
    8791        lemon/kruskal.h \
    8892        lemon/hao_orlin.h \
     
    99103        lemon/nauty_reader.h \
    100104        lemon/network_simplex.h \
     105        lemon/pairing_heap.h \
    101106        lemon/path.h \
    102107        lemon/preflow.h \
  • lemon/bfs.h

    r503 r717  
    4848    ///The type of the map that stores the predecessor
    4949    ///arcs of the shortest paths.
    50     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     50    ///It must conform to 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 meet the \ref concepts::WriteMap "WriteMap" concept.
     65    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     66    ///By default it is a NullMap.
    6667    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    6768    ///Instantiates a \c ProcessedMap.
     
    8283
    8384    ///The type of the map that indicates which nodes are reached.
    84     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     85    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8586    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    8687    ///Instantiates a \c ReachedMap.
     
    9798
    9899    ///The type of the map that stores the distances of the nodes.
    99     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     100    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    100101    typedef typename Digraph::template NodeMap<int> DistMap;
    101102    ///Instantiates a \c DistMap.
     
    226227    ///\ref named-templ-param "Named parameter" for setting
    227228    ///\c PredMap type.
    228     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     229    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    229230    template <class T>
    230231    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
     
    246247    ///\ref named-templ-param "Named parameter" for setting
    247248    ///\c DistMap type.
    248     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     249    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    249250    template <class T>
    250251    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
     
    266267    ///\ref named-templ-param "Named parameter" for setting
    267268    ///\c ReachedMap type.
    268     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     269    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    269270    template <class T>
    270271    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
     
    286287    ///\ref named-templ-param "Named parameter" for setting
    287288    ///\c ProcessedMap type.
    288     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     289    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    289290    template <class T>
    290291    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
     
    414415    ///The simplest way to execute the BFS algorithm is to use one of the
    415416    ///member functions called \ref run(Node) "run()".\n
    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
     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
    418419    ///\ref addSource(). Finally the actual path computation can be
    419420    ///performed with one of the \ref start() functions.
     
    738739    ///@{
    739740
    740     ///The shortest path to a node.
    741 
    742     ///Returns the shortest path to a node.
     741    ///The shortest path to the given node.
     742
     743    ///Returns the shortest path to the given node from the root(s).
    743744    ///
    744745    ///\warning \c t should be reached from the root(s).
     
    748749    Path path(Node t) const { return Path(*G, *_pred, t); }
    749750
    750     ///The distance of a node from the root(s).
    751 
    752     ///Returns the distance of a node from the root(s).
     751    ///The distance of the given node from the root(s).
     752
     753    ///Returns the distance of the given node from the root(s).
    753754    ///
    754755    ///\warning If node \c v is not reached from the root(s), then
     
    759760    int dist(Node v) const { return (*_dist)[v]; }
    760761
    761     ///Returns the 'previous arc' of the shortest path tree for a node.
    762 
     762    ///\brief Returns the 'previous arc' of the shortest path tree for
     763    ///the given node.
     764    ///
    763765    ///This function returns the 'previous arc' of the shortest path
    764766    ///tree for the node \c v, i.e. it returns the last arc of a
     
    767769    ///
    768770    ///The shortest path tree used here is equal to the shortest path
    769     ///tree used in \ref predNode().
     771    ///tree used in \ref predNode() and \ref predMap().
    770772    ///
    771773    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    773775    Arc predArc(Node v) const { return (*_pred)[v];}
    774776
    775     ///Returns the 'previous node' of the shortest path tree for a node.
    776 
     777    ///\brief Returns the 'previous node' of the shortest path tree for
     778    ///the given node.
     779    ///
    777780    ///This function returns the 'previous node' of the shortest path
    778781    ///tree for the node \c v, i.e. it returns the last but one node
    779     ///from a shortest path from a root to \c v. It is \c INVALID
     782    ///of a shortest path from a root to \c v. It is \c INVALID
    780783    ///if \c v is not reached from the root(s) or if \c v is a root.
    781784    ///
    782785    ///The shortest path tree used here is equal to the shortest path
    783     ///tree used in \ref predArc().
     786    ///tree used in \ref predArc() and \ref predMap().
    784787    ///
    785788    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    802805    ///
    803806    ///Returns a const reference to the node map that stores the predecessor
    804     ///arcs, which form the shortest path tree.
     807    ///arcs, which form the shortest path tree (forest).
    805808    ///
    806809    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    808811    const PredMap &predMap() const { return *_pred;}
    809812
    810     ///Checks if a node is reached from the root(s).
     813    ///Checks if the given node is reached from the root(s).
    811814
    812815    ///Returns \c true if \c v is reached from the root(s).
     
    834837    ///The type of the map that stores the predecessor
    835838    ///arcs of the shortest paths.
    836     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     839    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    837840    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    838841    ///Instantiates a PredMap.
     
    849852
    850853    ///The type of the map that indicates which nodes are processed.
    851     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     854    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    852855    ///By default it is a NullMap.
    853856    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     
    869872
    870873    ///The type of the map that indicates which nodes are reached.
    871     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     874    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    872875    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    873876    ///Instantiates a ReachedMap.
     
    884887
    885888    ///The type of the map that stores the distances of the nodes.
    886     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     889    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    887890    typedef typename Digraph::template NodeMap<int> DistMap;
    888891    ///Instantiates a DistMap.
     
    899902
    900903    ///The type of the shortest paths.
    901     ///It must meet the \ref concepts::Path "Path" concept.
     904    ///It must conform to the \ref concepts::Path "Path" concept.
    902905    typedef lemon::Path<Digraph> Path;
    903906  };
     
    905908  /// Default traits class used by BfsWizard
    906909
    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.
     910  /// Default traits class used by BfsWizard.
     911  /// \tparam GR The type of the digraph.
    913912  template<class GR>
    914913  class BfsWizardBase : public BfsWizardDefaultTraits<GR>
     
    938937    /// Constructor.
    939938
    940     /// This constructor does not require parameters, therefore it initiates
     939    /// This constructor does not require parameters, it initiates
    941940    /// all of the attributes to \c 0.
    942941    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
     
    968967    typedef TR Base;
    969968
    970     ///The type of the digraph the algorithm runs on.
    971969    typedef typename TR::Digraph Digraph;
    972970
     
    976974    typedef typename Digraph::OutArcIt OutArcIt;
    977975
    978     ///\brief The type of the map that stores the predecessor
    979     ///arcs of the shortest paths.
    980976    typedef typename TR::PredMap PredMap;
    981     ///\brief The type of the map that stores the distances of the nodes.
    982977    typedef typename TR::DistMap DistMap;
    983     ///\brief The type of the map that indicates which nodes are reached.
    984978    typedef typename TR::ReachedMap ReachedMap;
    985     ///\brief The type of the map that indicates which nodes are processed.
    986979    typedef typename TR::ProcessedMap ProcessedMap;
    987     ///The type of the shortest paths
    988980    typedef typename TR::Path Path;
    989981
     
    10681060      SetPredMapBase(const TR &b) : TR(b) {}
    10691061    };
    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.
     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.
    10751068    template<class T>
    10761069    BfsWizard<SetPredMapBase<T> > predMap(const T &t)
     
    10861079      SetReachedMapBase(const TR &b) : TR(b) {}
    10871080    };
    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.
     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.
    10931087    template<class T>
    10941088    BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
     
    11041098      SetDistMapBase(const TR &b) : TR(b) {}
    11051099    };
    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.
     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.
    11111107    template<class T>
    11121108    BfsWizard<SetDistMapBase<T> > distMap(const T &t)
     
    11221118      SetProcessedMapBase(const TR &b) : TR(b) {}
    11231119    };
    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.
     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.
    11291126    template<class T>
    11301127    BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
     
    12651262    ///
    12661263    /// The type of the map that indicates which nodes are reached.
    1267     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     1264    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12681265    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12691266
     
    14261423    /// The simplest way to execute the BFS algorithm is to use one of the
    14271424    /// member functions called \ref run(Node) "run()".\n
    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
     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
    14301427    /// \ref addSource(). Finally the actual path computation can be
    14311428    /// performed with one of the \ref start() functions.
     
    17361733    ///@{
    17371734
    1738     /// \brief Checks if a node is reached from the root(s).
     1735    /// \brief Checks if the given node is reached from the root(s).
    17391736    ///
    17401737    /// Returns \c true if \c v is reached from the root(s).
  • lemon/bin_heap.h

    r683 r711  
    2020#define LEMON_BIN_HEAP_H
    2121
    22 ///\ingroup auxdat
     22///\ingroup heaps
    2323///\file
    24 ///\brief Binary Heap implementation.
     24///\brief Binary heap implementation.
    2525
    2626#include <vector>
     
    3030namespace lemon {
    3131
    32   ///\ingroup auxdat
     32  /// \ingroup heaps
    3333  ///
    34   ///\brief A Binary Heap implementation.
     34  /// \brief Binary heap data structure.
    3535  ///
    36   ///This class implements the \e binary \e heap data structure.
     36  /// This class implements the \e binary \e heap data structure.
     37  /// It fully conforms to the \ref concepts::Heap "heap concept".
    3738  ///
    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
     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
    5247  template <typename PR, typename IM, typename CMP = std::less<PR> >
     48#endif
    5349  class BinHeap {
    54 
    5550  public:
    56     ///\e
     51
     52    /// Type of the item-int map.
    5753    typedef IM ItemIntMap;
    58     ///\e
     54    /// Type of the priorities.
    5955    typedef PR Prio;
    60     ///\e
     56    /// Type of the items stored in the heap.
    6157    typedef typename ItemIntMap::Key Item;
    62     ///\e
     58    /// Type of the item-priority pairs.
    6359    typedef std::pair<Item,Prio> Pair;
    64     ///\e
     60    /// Functor type for comparing the priorities.
    6561    typedef CMP Compare;
    6662
    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
     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
    7167    /// heap's point of view, but may be useful to the user.
    7268    ///
     
    8581
    8682  public:
    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.
     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.
    9390    explicit BinHeap(ItemIntMap &map) : _iim(map) {}
    9491
    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.
     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.
    10399    BinHeap(ItemIntMap &map, const Compare &comp)
    104100      : _iim(map), _comp(comp) {}
    105101
    106102
    107     /// The number of items stored in the heap.
    108     ///
    109     /// \brief Returns the number of items stored in the heap.
     103    /// \brief The number of items stored in the heap.
     104    ///
     105    /// This function returns the number of items stored in the heap.
    110106    int size() const { return _data.size(); }
    111107
    112     /// \brief Checks if the heap stores no items.
    113     ///
    114     /// Returns \c true if and only if the heap stores no items.
     108    /// \brief Check if the heap is empty.
     109    ///
     110    /// This function returns \c true if the heap is empty.
    115111    bool empty() const { return _data.empty(); }
    116112
    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.
     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.
    123120    void clear() {
    124121      _data.clear();
     
    128125    static int parent(int i) { return (i-1)/2; }
    129126
    130     static int second_child(int i) { return 2*i+2; }
     127    static int secondChild(int i) { return 2*i+2; }
    131128    bool less(const Pair &p1, const Pair &p2) const {
    132129      return _comp(p1.second, p2.second);
    133130    }
    134131
    135     int bubble_up(int hole, Pair p) {
     132    int bubbleUp(int hole, Pair p) {
    136133      int par = parent(hole);
    137134      while( hole>0 && less(p,_data[par]) ) {
     
    144141    }
    145142
    146     int bubble_down(int hole, Pair p, int length) {
    147       int child = second_child(hole);
     143    int bubbleDown(int hole, Pair p, int length) {
     144      int child = secondChild(hole);
    148145      while(child < length) {
    149146        if( less(_data[child-1], _data[child]) ) {
     
    154151        move(_data[child], hole);
    155152        hole = child;
    156         child = second_child(hole);
     153        child = secondChild(hole);
    157154      }
    158155      child--;
     
    172169
    173170  public:
     171
    174172    /// \brief Insert a pair of item and priority into the heap.
    175173    ///
    176     /// Adds \c p.first to the heap with priority \c p.second.
     174    /// This function inserts \c p.first to the heap with priority
     175    /// \c p.second.
    177176    /// \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       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.
     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.
    187188    /// \param i The item to insert.
    188189    /// \param p The priority of the item.
     190    /// \pre \e i must not be stored in the heap.
    189191    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
    190192
    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.
     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.
    196197    Item top() const {
    197198      return _data[0].first;
    198199    }
    199200
    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.
     201    /// \brief The minimum priority.
     202    ///
     203    /// This function returns the minimum priority.
     204    /// \pre The heap must be non-empty.
    204205    Prio prio() const {
    205206      return _data[0].second;
    206207    }
    207208
    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.
     209    /// \brief Remove the item having minimum priority.
     210    ///
     211    /// This function removes the item having minimum priority.
    212212    /// \pre The heap must be non-empty.
    213213    void pop() {
     
    215215      _iim.set(_data[0].first, POST_HEAP);
    216216      if (n > 0) {
    217         bubble_down(0, _data[n], n);
     217        bubbleDown(0, _data[n], n);
    218218      }
    219219      _data.pop_back();
    220220    }
    221221
    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.
     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.
    227228    void erase(const Item &i) {
    228229      int h = _iim[i];
     
    230231      _iim.set(_data[h].first, POST_HEAP);
    231232      if( h < n ) {
    232         if ( bubble_up(h, _data[n]) == h) {
    233           bubble_down(h, _data[n], n);
     233        if ( bubbleUp(h, _data[n]) == h) {
     234          bubbleDown(h, _data[n], n);
    234235        }
    235236      }
     
    237238    }
    238239
    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.
     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.
    245245    Prio operator[](const Item &i) const {
    246246      int idx = _iim[i];
     
    248248    }
    249249
    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.
     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.
    255256    /// \param i The item.
    256257    /// \param p The priority.
     
    261262      }
    262263      else if( _comp(p, _data[idx].second) ) {
    263         bubble_up(idx, Pair(i,p));
     264        bubbleUp(idx, Pair(i,p));
    264265      }
    265266      else {
    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.
     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.
    273274    /// \param i The item.
    274275    /// \param p The priority.
    275     /// \pre \c i must be stored in the heap with priority at least \c
    276     /// p relative to \c Compare.
     276    /// \pre \e i must be stored in the heap with priority at least \e p.
    277277    void decrease(const Item &i, const Prio &p) {
    278278      int idx = _iim[i];
    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.
     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.
    285285    /// \param i The item.
    286286    /// \param p The priority.
    287     /// \pre \c i must be stored in the heap with priority at most \c
    288     /// p relative to \c Compare.
     287    /// \pre \e i must be stored in the heap with priority at most \e p.
    289288    void increase(const Item &i, const Prio &p) {
    290289      int idx = _iim[i];
    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.
     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.
    301300    /// \param i The item.
    302301    State state(const Item &i) const {
     
    307306    }
    308307
    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.
     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.
    314313    /// \param i The item.
    315314    /// \param st The state. It should not be \c IN_HEAP.
     
    328327    }
    329328
    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.
     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.
    336336    void replace(const Item& i, const Item& j) {
    337337      int idx = _iim[i];
  • lemon/bits/map_extender.h

    r617 r718  
    5050    typedef typename Parent::ConstReference ConstReference;
    5151
     52    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
     53
    5254    class MapIt;
    5355    class ConstMapIt;
     
    192194    typedef typename Parent::ConstReference ConstReference;
    193195
     196    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
     197
    194198    class MapIt;
    195199    class ConstMapIt;
  • lemon/bucket_heap.h

    r683 r711  
    2020#define LEMON_BUCKET_HEAP_H
    2121
    22 ///\ingroup auxdat
     22///\ingroup heaps
    2323///\file
    24 ///\brief Bucket Heap implementation.
     24///\brief Bucket heap implementation.
    2525
    2626#include <vector>
     
    5454  }
    5555
    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.
     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
    7378  template <typename IM, bool MIN = true>
    7479  class BucketHeap {
    7580
    7681  public:
    77     /// \e
    78     typedef typename IM::Key Item;
    79     /// \e
     82
     83    /// Type of the item-int map.
     84    typedef IM ItemIntMap;
     85    /// Type of the priorities.
    8086    typedef int Prio;
    81     /// \e
    82     typedef std::pair<Item, Prio> Pair;
    83     /// \e
    84     typedef IM ItemIntMap;
     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;
    8591
    8692  private:
     
    9096  public:
    9197
    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
     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
    96102    /// heap's point of view, but may be useful to the user.
    97103    ///
     
    105111
    106112  public:
    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.
     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.
    113120    explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {}
    114121
    115     /// The number of items stored in the heap.
    116     ///
    117     /// \brief Returns the number of items stored in the heap.
     122    /// \brief The number of items stored in the heap.
     123    ///
     124    /// This function returns the number of items stored in the heap.
    118125    int size() const { return _data.size(); }
    119126
    120     /// \brief Checks if the heap stores no items.
    121     ///
    122     /// Returns \c true if and only if the heap stores no items.
     127    /// \brief Check if the heap is empty.
     128    ///
     129    /// This function returns \c true if the heap is empty.
    123130    bool empty() const { return _data.empty(); }
    124131
    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.
     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.
    131139    void clear() {
    132140      _data.clear(); _first.clear(); _minimum = 0;
     
    135143  private:
    136144
    137     void relocate_last(int idx) {
     145    void relocateLast(int idx) {
    138146      if (idx + 1 < int(_data.size())) {
    139147        _data[idx] = _data.back();
     
    175183
    176184  public:
     185
    177186    /// \brief Insert a pair of item and priority into the heap.
    178187    ///
    179     /// Adds \c p.first to the heap with priority \c p.second.
     188    /// This function inserts \c p.first to the heap with priority
     189    /// \c p.second.
    180190    /// \param p The pair to insert.
     191    /// \pre \c p.first must not be stored in the heap.
    181192    void push(const Pair& p) {
    182193      push(p.first, p.second);
     
    185196    /// \brief Insert an item into the heap with the given priority.
    186197    ///
    187     /// Adds \c i to the heap with priority \c p.
     198    /// This function inserts the given item into the heap with the
     199    /// given priority.
    188200    /// \param i The item to insert.
    189201    /// \param p The priority of the item.
     202    /// \pre \e i must not be stored in the heap.
    190203    void push(const Item &i, const Prio &p) {
    191204      int idx = _data.size();
     
    198211    }
    199212
    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.
     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.
    204217    Item top() const {
    205218      while (_first[_minimum] == -1) {
     
    209222    }
    210223
    211     /// \brief Returns the minimum priority.
    212     ///
    213     /// It returns the minimum priority.
    214     /// \pre The heap must be nonempty.
     224    /// \brief The minimum priority.
     225    ///
     226    /// This function returns the minimum priority.
     227    /// \pre The heap must be non-empty.
    215228    Prio prio() const {
    216229      while (_first[_minimum] == -1) {
     
    220233    }
    221234
    222     /// \brief Deletes the item with minimum priority.
    223     ///
    224     /// This method deletes the item with minimum priority from the heap.
     235    /// \brief Remove the item having minimum priority.
     236    ///
     237    /// This function removes the item having minimum priority.
    225238    /// \pre The heap must be non-empty.
    226239    void pop() {
     
    231244      _iim[_data[idx].item] = -2;
    232245      unlace(idx);
    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.
     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.
    241255    void erase(const Item &i) {
    242256      int idx = _iim[i];
    243257      _iim[_data[idx].item] = -2;
    244258      unlace(idx);
    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.
     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.
    254267    Prio operator[](const Item &i) const {
    255268      int idx = _iim[i];
     
    257270    }
    258271
    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.
     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.
    264278    /// \param i The item.
    265279    /// \param p The priority.
     
    275289    }
    276290
    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.
     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.
    282294    /// \param i The item.
    283295    /// \param p The priority.
     296    /// \pre \e i must be stored in the heap with priority at least \e p.
    284297    void decrease(const Item &i, const Prio &p) {
    285298      int idx = _iim[i];
     
    292305    }
    293306
    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.
     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.
    299310    /// \param i The item.
    300311    /// \param p The priority.
     312    /// \pre \e i must be stored in the heap with priority at most \e p.
    301313    void increase(const Item &i, const Prio &p) {
    302314      int idx = _iim[i];
     
    306318    }
    307319
    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.
     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.
    315327    /// \param i The item.
    316328    State state(const Item &i) const {
     
    320332    }
    321333
    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.
     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.
    327339    /// \param i The item.
    328340    /// \param st The state. It should not be \c IN_HEAP.
     
    360372  }; // class BucketHeap
    361373
    362   /// \ingroup auxdat
    363   ///
    364   /// \brief A Simplified Bucket Heap implementation.
     374  /// \ingroup heaps
     375  ///
     376  /// \brief Simplified bucket heap data structure.
    365377  ///
    366378  /// This class implements a simplified \e bucket \e heap data
    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.
     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.
    379397  ///
    380398  /// \sa BucketHeap
     
    383401
    384402  public:
    385     typedef typename IM::Key Item;
     403
     404    /// Type of the item-int map.
     405    typedef IM ItemIntMap;
     406    /// Type of the priorities.
    386407    typedef int Prio;
    387     typedef std::pair<Item, Prio> Pair;
    388     typedef IM ItemIntMap;
     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;
    389412
    390413  private:
     
    394417  public:
    395418
    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
     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
    400423    /// heap's point of view, but may be useful to the user.
    401424    ///
     
    410433  public:
    411434
    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.
     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.
    418441    explicit SimpleBucketHeap(ItemIntMap &map)
    419442      : _iim(map), _free(-1), _num(0), _minimum(0) {}
    420443
    421     /// \brief Returns the number of items stored in the heap.
    422     ///
    423     /// The number of items stored in the heap.
     444    /// \brief The number of items stored in the heap.
     445    ///
     446    /// This function returns the number of items stored in the heap.
    424447    int size() const { return _num; }
    425448
    426     /// \brief Checks if the heap stores no items.
    427     ///
    428     /// Returns \c true if and only if the heap stores no items.
     449    /// \brief Check if the heap is empty.
     450    ///
     451    /// This function returns \c true if the heap is empty.
    429452    bool empty() const { return _num == 0; }
    430453
    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.
     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.
    437461    void clear() {
    438462      _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0;
     
    441465    /// \brief Insert a pair of item and priority into the heap.
    442466    ///
    443     /// Adds \c p.first to the heap with priority \c p.second.
     467    /// This function inserts \c p.first to the heap with priority
     468    /// \c p.second.
    444469    /// \param p The pair to insert.
     470    /// \pre \c p.first must not be stored in the heap.
    445471    void push(const Pair& p) {
    446472      push(p.first, p.second);
     
    449475    /// \brief Insert an item into the heap with the given priority.
    450476    ///
    451     /// Adds \c i to the heap with priority \c p.
     477    /// This function inserts the given item into the heap with the
     478    /// given priority.
    452479    /// \param i The item to insert.
    453480    /// \param p The priority of the item.
     481    /// \pre \e i must not be stored in the heap.
    454482    void push(const Item &i, const Prio &p) {
    455483      int idx;
     
    472500    }
    473501
    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.
     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.
    478506    Item top() const {
    479507      while (_first[_minimum] == -1) {
     
    483511    }
    484512
    485     /// \brief Returns the minimum priority.
    486     ///
    487     /// It returns the minimum priority.
    488     /// \pre The heap must be nonempty.
     513    /// \brief The minimum priority.
     514    ///
     515    /// This function returns the minimum priority.
     516    /// \pre The heap must be non-empty.
    489517    Prio prio() const {
    490518      while (_first[_minimum] == -1) {
     
    494522    }
    495523
    496     /// \brief Deletes the item with minimum priority.
    497     ///
    498     /// This method deletes the item with minimum priority from the heap.
     524    /// \brief Remove the item having minimum priority.
     525    ///
     526    /// This function removes the item having minimum priority.
    499527    /// \pre The heap must be non-empty.
    500528    void pop() {
     
    510538    }
    511539
    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.
     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.
    520547    Prio operator[](const Item &i) const {
    521       for (int k = 0; k < _first.size(); ++k) {
     548      for (int k = 0; k < int(_first.size()); ++k) {
    522549        int idx = _first[k];
    523550        while (idx != -1) {
     
    531558    }
    532559
    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.
     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.
    540567    /// \param i The item.
    541568    State state(const Item &i) const {
  • lemon/circulation.h

    r641 r715  
    7373    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
    7474    /// concept.
     75#ifdef DOXYGEN
     76    typedef GR::ArcMap<Value> FlowMap;
     77#else
    7578    typedef typename Digraph::template ArcMap<Value> FlowMap;
     79#endif
    7680
    7781    /// \brief Instantiates a FlowMap.
     
    8892    /// The elevator type used by the algorithm.
    8993    ///
    90     /// \sa Elevator
    91     /// \sa LinkedElevator
     94    /// \sa Elevator, LinkedElevator
     95#ifdef DOXYGEN
     96    typedef lemon::Elevator<GR, GR::Node> Elevator;
     97#else
    9298    typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
     99#endif
    93100
    94101    /// \brief Instantiates an Elevator.
     
    451458    }
    452459
    453     /// \brief Sets the tolerance used by algorithm.
    454     ///
    455     /// Sets the tolerance used by algorithm.
    456     Circulation& tolerance(const Tolerance& tolerance) const {
     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) {
    457465      _tol = tolerance;
    458466      return *this;
     
    461469    /// \brief Returns a const reference to the tolerance.
    462470    ///
    463     /// Returns a const reference to the tolerance.
     471    /// Returns a const reference to the tolerance object used by
     472    /// the algorithm.
    464473    const Tolerance& tolerance() const {
    465       return tolerance;
     474      return _tol;
    466475    }
    467476
    468477    /// \name Execution Control
    469478    /// The simplest way to execute the algorithm is to call \ref run().\n
    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
     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
    472481    /// the \ref start() function.
    473482
  • lemon/concepts/heap.h

    r584 r710  
    1717 */
    1818
     19#ifndef LEMON_CONCEPTS_HEAP_H
     20#define LEMON_CONCEPTS_HEAP_H
     21
    1922///\ingroup concept
    2023///\file
    2124///\brief The concept of heaps.
    2225
    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     /// 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.
     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.
    4345    ///
    44     /// \tparam PR Type of the priority of the items.
    45     /// \tparam IM A read and writable item map with int values, used
     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
    4652    /// internally to handle the cross references.
    47     /// \tparam Comp A functor class for the ordering of the priorities.
     53    /// \tparam CMP A functor class for comparing the priorities.
    4854    /// The default is \c std::less<PR>.
    4955#ifdef DOXYGEN
    50     template <typename PR, typename IM, typename Comp = std::less<PR> >
     56    template <typename PR, typename IM, typename CMP>
    5157#else
    52     template <typename PR, typename IM>
     58    template <typename PR, typename IM, typename CMP = std::less<PR> >
    5359#endif
    5460    class Heap {
     
    6571      ///
    6672      /// Each item has a state associated to it. It can be "in heap",
    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.
     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.
    7075      ///
    7176      /// The item-int map must be initialized in such way that it assigns
     
    7378      enum State {
    7479        IN_HEAP = 0,    ///< = 0. The "in heap" state constant.
    75         PRE_HEAP = -1,  ///< = -1. The "pre heap" state constant.
    76         POST_HEAP = -2  ///< = -2. The "post heap" state constant.
     80        PRE_HEAP = -1,  ///< = -1. The "pre-heap" state constant.
     81        POST_HEAP = -2  ///< = -2. The "post-heap" state constant.
    7782      };
    7883
    79       /// \brief The constructor.
    80       ///
    81       /// The constructor.
     84      /// \brief Constructor.
     85      ///
     86      /// Constructor.
    8287      /// \param map A map that assigns \c int values to keys of type
    8388      /// \c Item. It is used internally by the heap implementations to
    8489      /// handle the cross references. The assigned value must be
    85       /// \c PRE_HEAP (<tt>-1</tt>) for every item.
     90      /// \c PRE_HEAP (<tt>-1</tt>) for each item.
    8691      explicit Heap(ItemIntMap &map) {}
    8792
     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
    88103      /// \brief The number of items stored in the heap.
    89104      ///
    90       /// Returns the number of items stored in the heap.
     105      /// This function returns the number of items stored in the heap.
    91106      int size() const { return 0; }
    92107
    93       /// \brief Checks if the heap is empty.
    94       ///
    95       /// Returns \c true if the heap is empty.
     108      /// \brief Check if the heap is empty.
     109      ///
     110      /// This function returns \c true if the heap is empty.
    96111      bool empty() const { return false; }
    97112
    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.
     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.
    106126      /// \param i The item to insert.
    107127      /// \param p The priority of the item.
     128      /// \pre \e i must not be stored in the heap.
    108129      void push(const Item &i, const Prio &p) {}
    109130
    110       /// \brief Returns the item having minimum priority.
    111       ///
    112       /// Returns the item having minimum priority.
     131      /// \brief Return the item having minimum priority.
     132      ///
     133      /// This function returns the item having minimum priority.
    113134      /// \pre The heap must be non-empty.
    114135      Item top() const {}
     
    116137      /// \brief The minimum priority.
    117138      ///
    118       /// Returns the minimum priority.
     139      /// This function returns the minimum priority.
    119140      /// \pre The heap must be non-empty.
    120141      Prio prio() const {}
    121142
    122       /// \brief Removes the item having minimum priority.
    123       ///
    124       /// Removes the item having minimum priority.
     143      /// \brief Remove the item having minimum priority.
     144      ///
     145      /// This function removes the item having minimum priority.
    125146      /// \pre The heap must be non-empty.
    126147      void pop() {}
    127148
    128       /// \brief Removes an item from the heap.
    129       ///
    130       /// Removes the given item from the heap if it is already stored.
     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.
    131153      /// \param i The item to delete.
     154      /// \pre \e i must be in the heap.
    132155      void erase(const Item &i) {}
    133156
    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.
     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.
    139162      Prio operator[](const Item &i) const {}
    140163
    141       /// \brief Sets the priority of an item or inserts it, if it is
     164      /// \brief Set the priority of an item or insert it, if it is
    142165      /// not stored in the heap.
    143166      ///
    144167      /// This method sets the priority of the given item if it is
    145       /// already stored in the heap.
    146       /// Otherwise it inserts the given item with the given priority.
     168      /// already stored in the heap. Otherwise it inserts the given
     169      /// item into the heap with the given priority.
    147170      ///
    148171      /// \param i The item.
     
    150173      void set(const Item &i, const Prio &p) {}
    151174
    152       /// \brief Decreases the priority of an item to the given value.
    153       ///
    154       /// Decreases the priority of an item to the given value.
     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.
    155178      /// \param i The item.
    156179      /// \param p The priority.
    157       /// \pre \c i must be stored in the heap with priority at least \c p.
     180      /// \pre \e i must be stored in the heap with priority at least \e p.
    158181      void decrease(const Item &i, const Prio &p) {}
    159182
    160       /// \brief Increases the priority of an item to the given value.
    161       ///
    162       /// Increases the priority of an item to the given value.
     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.
    163186      /// \param i The item.
    164187      /// \param p The priority.
    165       /// \pre \c i must be stored in the heap with priority at most \c p.
     188      /// \pre \e i must be stored in the heap with priority at most \e p.
    166189      void increase(const Item &i, const Prio &p) {}
    167190
    168       /// \brief Returns if an item is in, has already been in, or has
    169       /// never been in the heap.
     191      /// \brief Return the state of an item.
    170192      ///
    171193      /// This method returns \c PRE_HEAP if the given item has never
     
    177199      State state(const Item &i) const {}
    178200
    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.
     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.
    184206      /// \param i The item.
    185207      /// \param st The state. It should not be \c IN_HEAP.
  • lemon/concepts/maps.h

    r529 r718  
    183183      template<typename _ReferenceMap>
    184184      struct Constraints {
    185         void constraints() {
     185        typename enable_if<typename _ReferenceMap::ReferenceMapTag, void>::type
     186        constraints() {
    186187          checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();
    187188          ref = m[key];
  • lemon/dfs.h

    r584 r717  
    4848    ///The type of the map that stores the predecessor
    4949    ///arcs of the %DFS paths.
    50     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     50    ///It must conform to 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 meet the \ref concepts::WriteMap "WriteMap" concept.
     65    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     66    ///By default it is a NullMap.
    6667    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    6768    ///Instantiates a \c ProcessedMap.
     
    8283
    8384    ///The type of the map that indicates which nodes are reached.
    84     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     85    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8586    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    8687    ///Instantiates a \c ReachedMap.
     
    9798
    9899    ///The type of the map that stores the distances of the nodes.
    99     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     100    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    100101    typedef typename Digraph::template NodeMap<int> DistMap;
    101102    ///Instantiates a \c DistMap.
     
    225226    ///\ref named-templ-param "Named parameter" for setting
    226227    ///\c PredMap type.
    227     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     228    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    228229    template <class T>
    229230    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
     
    245246    ///\ref named-templ-param "Named parameter" for setting
    246247    ///\c DistMap type.
    247     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     248    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    248249    template <class T>
    249250    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
     
    265266    ///\ref named-templ-param "Named parameter" for setting
    266267    ///\c ReachedMap type.
    267     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     268    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    268269    template <class T>
    269270    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
     
    285286    ///\ref named-templ-param "Named parameter" for setting
    286287    ///\c ProcessedMap type.
    287     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     288    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    288289    template <class T>
    289290    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
     
    412413    ///The simplest way to execute the DFS algorithm is to use one of the
    413414    ///member functions called \ref run(Node) "run()".\n
    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()
     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()
    416417    ///and perform the actual computation with \ref start().
    417418    ///This procedure can be repeated if there are nodes that have not
     
    670671    ///@{
    671672
    672     ///The DFS path to a node.
    673 
    674     ///Returns the DFS path to a node.
     673    ///The DFS path to the given node.
     674
     675    ///Returns the DFS path to the given node from the root(s).
    675676    ///
    676677    ///\warning \c t should be reached from the root(s).
     
    680681    Path path(Node t) const { return Path(*G, *_pred, t); }
    681682
    682     ///The distance of a node from the root(s).
    683 
    684     ///Returns the distance of a node from the root(s).
     683    ///The distance of the given node from the root(s).
     684
     685    ///Returns the distance of the given node from the root(s).
    685686    ///
    686687    ///\warning If node \c v is not reached from the root(s), then
     
    691692    int dist(Node v) const { return (*_dist)[v]; }
    692693
    693     ///Returns the 'previous arc' of the %DFS tree for a node.
     694    ///Returns the 'previous arc' of the %DFS tree for the given node.
    694695
    695696    ///This function returns the 'previous arc' of the %DFS tree for the
     
    699700    ///
    700701    ///The %DFS tree used here is equal to the %DFS tree used in
    701     ///\ref predNode().
     702    ///\ref predNode() and \ref predMap().
    702703    ///
    703704    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    705706    Arc predArc(Node v) const { return (*_pred)[v];}
    706707
    707     ///Returns the 'previous node' of the %DFS tree.
     708    ///Returns the 'previous node' of the %DFS tree for the given node.
    708709
    709710    ///This function returns the 'previous node' of the %DFS
    710711    ///tree for the node \c v, i.e. it returns the last but one node
    711     ///from a %DFS path from a root to \c v. It is \c INVALID
     712    ///of a %DFS path from a root to \c v. It is \c INVALID
    712713    ///if \c v is not reached from the root(s) or if \c v is a root.
    713714    ///
    714715    ///The %DFS tree used here is equal to the %DFS tree used in
    715     ///\ref predArc().
     716    ///\ref predArc() and \ref predMap().
    716717    ///
    717718    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    734735    ///
    735736    ///Returns a const reference to the node map that stores the predecessor
    736     ///arcs, which form the DFS tree.
     737    ///arcs, which form the DFS tree (forest).
    737738    ///
    738739    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    740741    const PredMap &predMap() const { return *_pred;}
    741742
    742     ///Checks if a node is reached from the root(s).
     743    ///Checks if the given node. node is reached from the root(s).
    743744
    744745    ///Returns \c true if \c v is reached from the root(s).
     
    766767    ///The type of the map that stores the predecessor
    767768    ///arcs of the %DFS paths.
    768     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     769    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    769770    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    770771    ///Instantiates a PredMap.
     
    781782
    782783    ///The type of the map that indicates which nodes are processed.
    783     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     784    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    784785    ///By default it is a NullMap.
    785786    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     
    801802
    802803    ///The type of the map that indicates which nodes are reached.
    803     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     804    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    804805    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    805806    ///Instantiates a ReachedMap.
     
    816817
    817818    ///The type of the map that stores the distances of the nodes.
    818     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     819    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    819820    typedef typename Digraph::template NodeMap<int> DistMap;
    820821    ///Instantiates a DistMap.
     
    831832
    832833    ///The type of the DFS paths.
    833     ///It must meet the \ref concepts::Path "Path" concept.
     834    ///It must conform to the \ref concepts::Path "Path" concept.
    834835    typedef lemon::Path<Digraph> Path;
    835836  };
     
    837838  /// Default traits class used by DfsWizard
    838839
    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.
     840  /// Default traits class used by DfsWizard.
     841  /// \tparam GR The type of the digraph.
    845842  template<class GR>
    846843  class DfsWizardBase : public DfsWizardDefaultTraits<GR>
     
    870867    /// Constructor.
    871868
    872     /// This constructor does not require parameters, therefore it initiates
     869    /// This constructor does not require parameters, it initiates
    873870    /// all of the attributes to \c 0.
    874871    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
     
    900897    typedef TR Base;
    901898
    902     ///The type of the digraph the algorithm runs on.
    903899    typedef typename TR::Digraph Digraph;
    904900
     
    908904    typedef typename Digraph::OutArcIt OutArcIt;
    909905
    910     ///\brief The type of the map that stores the predecessor
    911     ///arcs of the DFS paths.
    912906    typedef typename TR::PredMap PredMap;
    913     ///\brief The type of the map that stores the distances of the nodes.
    914907    typedef typename TR::DistMap DistMap;
    915     ///\brief The type of the map that indicates which nodes are reached.
    916908    typedef typename TR::ReachedMap ReachedMap;
    917     ///\brief The type of the map that indicates which nodes are processed.
    918909    typedef typename TR::ProcessedMap ProcessedMap;
    919     ///The type of the DFS paths
    920910    typedef typename TR::Path Path;
    921911
     
    1000990      SetPredMapBase(const TR &b) : TR(b) {}
    1001991    };
    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.
     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.
    1007998    template<class T>
    1008999    DfsWizard<SetPredMapBase<T> > predMap(const T &t)
     
    10181009      SetReachedMapBase(const TR &b) : TR(b) {}
    10191010    };
    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.
     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.
    10251017    template<class T>
    10261018    DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
     
    10361028      SetDistMapBase(const TR &b) : TR(b) {}
    10371029    };
    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.
     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.
    10431037    template<class T>
    10441038    DfsWizard<SetDistMapBase<T> > distMap(const T &t)
     
    10541048      SetProcessedMapBase(const TR &b) : TR(b) {}
    10551049    };
    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.
     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.
    10611056    template<class T>
    10621057    DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
     
    12091204    ///
    12101205    /// The type of the map that indicates which nodes are reached.
    1211     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     1206    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12121207    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12131208
     
    13701365    /// The simplest way to execute the DFS algorithm is to use one of the
    13711366    /// member functions called \ref run(Node) "run()".\n
    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()
     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()
    13741369    /// and perform the actual computation with \ref start().
    13751370    /// This procedure can be repeated if there are nodes that have not
     
    16211616    ///@{
    16221617
    1623     /// \brief Checks if a node is reached from the root(s).
     1618    /// \brief Checks if the given node is reached from the root(s).
    16241619    ///
    16251620    /// Returns \c true if \c v is reached from the root(s).
  • lemon/dijkstra.h

    r584 r717  
    7171
    7272    ///The type of the map that stores the arc lengths.
    73     ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
     73    ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    7474    typedef LEN LengthMap;
    75     ///The type of the length of the arcs.
     75    ///The type of the arc lengths.
    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 meet the \ref concepts::WriteMap "WriteMap" concept.
     119    ///It must conform to 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 meet the \ref concepts::WriteMap "WriteMap" concept.
     134    ///It must conform to 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 meet the \ref concepts::WriteMap "WriteMap" concept.
     154    ///It must conform to 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.
    171175  ///
    172176  ///The arc lengths are passed to the algorithm using a
     
    202206    typedef typename TR::Digraph Digraph;
    203207
    204     ///The type of the length of the arcs.
     208    ///The type of the arc lengths.
    205209    typedef typename TR::LengthMap::Value Value;
    206210    ///The type of the map that stores the arc lengths.
     
    305309    ///\ref named-templ-param "Named parameter" for setting
    306310    ///\c PredMap type.
    307     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     311    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    308312    template <class T>
    309313    struct SetPredMap
     
    326330    ///\ref named-templ-param "Named parameter" for setting
    327331    ///\c DistMap type.
    328     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     332    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    329333    template <class T>
    330334    struct SetDistMap
     
    347351    ///\ref named-templ-param "Named parameter" for setting
    348352    ///\c ProcessedMap type.
    349     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     353    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    350354    template <class T>
    351355    struct SetProcessedMap
     
    444448    ///\ref named-templ-param "Named parameter" for setting
    445449    ///\c OperationTraits type.
     450    /// For more information see \ref DijkstraDefaultOperationTraits.
    446451    template <class T>
    447452    struct SetOperationTraits
     
    585590    ///The simplest way to execute the %Dijkstra algorithm is to use
    586591    ///one of the member functions called \ref run(Node) "run()".\n
    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
     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
    589594    ///\ref addSource(). Finally the actual path computation can be
    590595    ///performed with one of the \ref start() functions.
     
    802807    ///The results of the %Dijkstra algorithm can be obtained using these
    803808    ///functions.\n
    804     ///Either \ref run(Node) "run()" or \ref start() should be called
     809    ///Either \ref run(Node) "run()" or \ref init() should be called
    805810    ///before using them.
    806811
    807812    ///@{
    808813
    809     ///The shortest path to a node.
    810 
    811     ///Returns the shortest path to a node.
     814    ///The shortest path to the given node.
     815
     816    ///Returns the shortest path to the given node from the root(s).
    812817    ///
    813818    ///\warning \c t should be reached from the root(s).
     
    817822    Path path(Node t) const { return Path(*G, *_pred, t); }
    818823
    819     ///The distance of a node from the root(s).
    820 
    821     ///Returns the distance of a node from the root(s).
     824    ///The distance of the given node from the root(s).
     825
     826    ///Returns the distance of the given node from the root(s).
    822827    ///
    823828    ///\warning If node \c v is not reached from the root(s), then
     
    828833    Value dist(Node v) const { return (*_dist)[v]; }
    829834
    830     ///Returns the 'previous arc' of the shortest path tree for a node.
    831 
     835    ///\brief Returns the 'previous arc' of the shortest path tree for
     836    ///the given node.
     837    ///
    832838    ///This function returns the 'previous arc' of the shortest path
    833839    ///tree for the node \c v, i.e. it returns the last arc of a
     
    836842    ///
    837843    ///The shortest path tree used here is equal to the shortest path
    838     ///tree used in \ref predNode().
     844    ///tree used in \ref predNode() and \ref predMap().
    839845    ///
    840846    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    842848    Arc predArc(Node v) const { return (*_pred)[v]; }
    843849
    844     ///Returns the 'previous node' of the shortest path tree for a node.
    845 
     850    ///\brief Returns the 'previous node' of the shortest path tree for
     851    ///the given node.
     852    ///
    846853    ///This function returns the 'previous node' of the shortest path
    847854    ///tree for the node \c v, i.e. it returns the last but one node
    848     ///from a shortest path from a root to \c v. It is \c INVALID
     855    ///of a shortest path from a root to \c v. It is \c INVALID
    849856    ///if \c v is not reached from the root(s) or if \c v is a root.
    850857    ///
    851858    ///The shortest path tree used here is equal to the shortest path
    852     ///tree used in \ref predArc().
     859    ///tree used in \ref predArc() and \ref predMap().
    853860    ///
    854861    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    871878    ///
    872879    ///Returns a const reference to the node map that stores the predecessor
    873     ///arcs, which form the shortest path tree.
     880    ///arcs, which form the shortest path tree (forest).
    874881    ///
    875882    ///\pre Either \ref run(Node) "run()" or \ref init()
     
    877884    const PredMap &predMap() const { return *_pred;}
    878885
    879     ///Checks if a node is reached from the root(s).
     886    ///Checks if the given node is reached from the root(s).
    880887
    881888    ///Returns \c true if \c v is reached from the root(s).
     
    896903                                          Heap::POST_HEAP; }
    897904
    898     ///The current distance of a node from the root(s).
    899 
    900     ///Returns the current distance of a node from the root(s).
     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).
    901908    ///It may be decreased in the following processes.
    902909    ///
     
    925932
    926933    ///The type of the map that stores the arc lengths.
    927     ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
     934    ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    928935    typedef LEN LengthMap;
    929     ///The type of the length of the arcs.
     936    ///The type of the arc lengths.
    930937    typedef typename LEN::Value Value;
    931938
     
    974981    ///The type of the map that stores the predecessor
    975982    ///arcs of the shortest paths.
    976     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     983    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    977984    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    978985    ///Instantiates a PredMap.
     
    989996
    990997    ///The type of the map that indicates which nodes are processed.
    991     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     998    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    992999    ///By default it is a NullMap.
    9931000    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     
    10091016
    10101017    ///The type of the map that stores the distances of the nodes.
    1011     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     1018    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    10121019    typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
    10131020    ///Instantiates a DistMap.
     
    10241031
    10251032    ///The type of the shortest paths.
    1026     ///It must meet the \ref concepts::Path "Path" concept.
     1033    ///It must conform to the \ref concepts::Path "Path" concept.
    10271034    typedef lemon::Path<Digraph> Path;
    10281035  };
     
    10301037  /// Default traits class used by DijkstraWizard
    10311038
    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.
     1039  /// Default traits class used by DijkstraWizard.
     1040  /// \tparam GR The type of the digraph.
     1041  /// \tparam LEN The type of the length map.
    10381042  template<typename GR, typename LEN>
    10391043  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN>
     
    10941098    typedef TR Base;
    10951099
    1096     ///The type of the digraph the algorithm runs on.
    10971100    typedef typename TR::Digraph Digraph;
    10981101
     
    11021105    typedef typename Digraph::OutArcIt OutArcIt;
    11031106
    1104     ///The type of the map that stores the arc lengths.
    11051107    typedef typename TR::LengthMap LengthMap;
    1106     ///The type of the length of the arcs.
    11071108    typedef typename LengthMap::Value Value;
    1108     ///\brief The type of the map that stores the predecessor
    1109     ///arcs of the shortest paths.
    11101109    typedef typename TR::PredMap PredMap;
    1111     ///The type of the map that stores the distances of the nodes.
    11121110    typedef typename TR::DistMap DistMap;
    1113     ///The type of the map that indicates which nodes are processed.
    11141111    typedef typename TR::ProcessedMap ProcessedMap;
    1115     ///The type of the shortest paths
    11161112    typedef typename TR::Path Path;
    1117     ///The heap type used by the dijkstra algorithm.
    11181113    typedef typename TR::Heap Heap;
    11191114
     
    11871182      SetPredMapBase(const TR &b) : TR(b) {}
    11881183    };
    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.
     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.
    11941190    template<class T>
    11951191    DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
     
    12051201      SetDistMapBase(const TR &b) : TR(b) {}
    12061202    };
    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.
     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.
    12121210    template<class T>
    12131211    DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
     
    12231221      SetProcessedMapBase(const TR &b) : TR(b) {}
    12241222    };
    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.
     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.
    12301229    template<class T>
    12311230    DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
     
    12401239      SetPathBase(const TR &b) : TR(b) {}
    12411240    };
     1241
    12421242    ///\brief \ref named-func-param "Named parameter"
    12431243    ///for getting the shortest path to the target node.
  • lemon/dim2.h

    r440 r714  
    2222#include <iostream>
    2323
    24 ///\ingroup misc
     24///\ingroup geomdat
    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.
    3427
    3528namespace lemon {
     
    4134  namespace dim2 {
    4235
    43   /// \addtogroup misc
     36  /// \addtogroup geomdat
    4437  /// @{
    4538
  • lemon/fib_heap.h

    r683 r711  
    2121
    2222///\file
    23 ///\ingroup auxdat
    24 ///\brief Fibonacci Heap implementation.
     23///\ingroup heaps
     24///\brief Fibonacci heap implementation.
    2525
    2626#include <vector>
     27#include <utility>
    2728#include <functional>
    2829#include <lemon/math.h>
     
    3031namespace lemon {
    3132
    32   /// \ingroup auxdat
     33  /// \ingroup heaps
    3334  ///
    34   ///\brief Fibonacci Heap.
     35  /// \brief Fibonacci heap data structure.
    3536  ///
    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.
     37  /// This class implements the \e Fibonacci \e heap data structure.
     38  /// It fully conforms to the \ref concepts::Heap "heap concept".
    4139  ///
    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".
     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".
    4543  ///
    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
     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>.
    5449#ifdef DOXYGEN
    55   template <typename PRIO, typename IM, typename CMP>
     50  template <typename PR, typename IM, typename CMP>
    5651#else
    57   template <typename PRIO, typename IM, typename CMP = std::less<PRIO> >
     52  template <typename PR, typename IM, typename CMP = std::less<PR> >
    5853#endif
    5954  class FibHeap {
    6055  public:
    61     ///\e
     56
     57    /// Type of the item-int map.
    6258    typedef IM ItemIntMap;
    63     ///\e
    64     typedef PRIO Prio;
    65     ///\e
     59    /// Type of the priorities.
     60    typedef PR Prio;
     61    /// Type of the items stored in the heap.
    6662    typedef typename ItemIntMap::Key Item;
    67     ///\e
     63    /// Type of the item-priority pairs.
    6864    typedef std::pair<Item,Prio> Pair;
    69     ///\e
     65    /// Functor type for comparing the priorities.
    7066    typedef CMP Compare;
    7167
     
    8177  public:
    8278
    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
     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
    8783    /// heap's point of view, but may be useful to the user.
    8884    ///
     
    9591    };
    9692
    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.
     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.
    10199    explicit FibHeap(ItemIntMap &map)
    102100      : _minimum(0), _iim(map), _num() {}
    103101
    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.
     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.
    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     /// Returns the number of items stored in the heap.
     114    /// This function returns the number of items stored in the heap.
    115115    int size() const { return _num; }
    116116
    117     /// \brief Checks if the heap stores no items.
    118     ///
    119     ///   Returns \c true if and only if the heap stores no items.
     117    /// \brief Check if the heap is empty.
     118    ///
     119    /// This function returns \c true if the heap is empty.
    120120    bool empty() const { return _num==0; }
    121121
    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.
     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.
    128129    void clear() {
    129130      _data.clear(); _minimum = 0; _num = 0;
    130131    }
    131132
    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) {
     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) {
    151141      int i=_iim[item];
    152142      if ( i < 0 ) {
     
    169159        _data[_minimum].right_neighbor=i;
    170160        _data[i].left_neighbor=_minimum;
    171         if ( _comp( value, _data[_minimum].prio) ) _minimum=i;
     161        if ( _comp( prio, _data[_minimum].prio) ) _minimum=i;
    172162      } else {
    173163        _data[i].right_neighbor=_data[i].left_neighbor=i;
    174164        _minimum=i;
    175165      }
    176       _data[i].prio=value;
     166      _data[i].prio=prio;
    177167      ++_num;
    178168    }
    179169
    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.
     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.
    185174    Item top() const { return _data[_minimum].name; }
    186175
    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.
     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.
    205185    /// \pre The heap must be non-empty.
    206186    void pop() {
     
    209189        _data[_minimum].in=false;
    210190        if ( _data[_minimum].degree!=0 ) {
    211           makeroot(_data[_minimum].child);
     191          makeRoot(_data[_minimum].child);
    212192          _minimum=_data[_minimum].child;
    213193          balance();
     
    222202          int last_child=_data[child].left_neighbor;
    223203
    224           makeroot(child);
     204          makeRoot(child);
    225205
    226206          _data[left].right_neighbor=child;
     
    235215    }
    236216
    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.
     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.
    241223    void erase (const Item& item) {
    242224      int i=_iim[item];
     
    253235    }
    254236
    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) {
     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) {
    261255      int i=_iim[item];
    262       _data[i].prio=value;
     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;
    263271      int p=_data[i].parent;
    264272
    265       if ( p!=-1 && _comp(value, _data[p].prio) ) {
     273      if ( p!=-1 && _comp(prio, _data[p].prio) ) {
    266274        cut(i,p);
    267275        cascade(p);
    268276      }
    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) {
     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) {
    280287      erase(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.
     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.
    292299    State state(const Item &item) const {
    293300      int i=_iim[item];
     
    299306    }
    300307
    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.
     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.
    306313    /// \param i The item.
    307314    /// \param st The state. It should not be \c IN_HEAP.
     
    366373    }
    367374
    368     void makeroot(int c) {
     375    void makeRoot(int c) {
    369376      int s=c;
    370377      do {
  • lemon/gomory_hu.h

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

    r684 r726  
    2323#include <functional>
    2424#include <vector>
     25#include <map>
    2526
    2627#include <lemon/core.h>
     
    2930///\ingroup maps
    3031///\brief Miscellaneous property maps
    31 
    32 #include <map>
    3332
    3433namespace lemon {
     
    5857  /// but data written to it is not required (i.e. it will be sent to
    5958  /// <tt>/dev/null</tt>).
    60   /// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     59  /// It conforms to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    6160  ///
    6261  /// \sa ConstMap
     
    9190  ///
    9291  /// In other aspects it is equivalent to \c NullMap.
    93   /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
     92  /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap"
    9493  /// concept, but it absorbs the data written to it.
    9594  ///
     
    160159  ///
    161160  /// In other aspects it is equivalent to \c NullMap.
    162   /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
     161  /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap"
    163162  /// concept, but it absorbs the data written to it.
    164163  ///
     
    234233  /// It can be used with some data structures, for example
    235234  /// \c UnionFind, \c BinHeap, when the used items are small
    236   /// integers. This map conforms the \ref concepts::ReferenceMap
     235  /// integers. This map conforms to the \ref concepts::ReferenceMap
    237236  /// "ReferenceMap" concept.
    238237  ///
     
    342341  /// stored actually. This value can be different from the default
    343342  /// contructed value (i.e. \c %Value()).
    344   /// This type conforms the \ref concepts::ReferenceMap "ReferenceMap"
     343  /// This type conforms to the \ref concepts::ReferenceMap "ReferenceMap"
    345344  /// concept.
    346345  ///
     
    708707  /// The \c Key type of it is inherited from \c M and the \c Value
    709708  /// type is \c V.
    710   /// This type conforms the \ref concepts::ReadMap "ReadMap" concept.
     709  /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
    711710  ///
    712711  /// The simplest way of using this map is through the convertMap()
     
    17911790  /// \code
    17921791  ///   std::vector<Node> v;
    1793   ///   dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run();
     1792  ///   dfs(g).processedMap(loggerBoolMap(std::back_inserter(v))).run(s);
    17941793  /// \endcode
    17951794  /// \code
    17961795  ///   std::vector<Node> v(countNodes(g));
    1797   ///   dfs(g,s).processedMap(loggerBoolMap(v.begin())).run();
     1796  ///   dfs(g).processedMap(loggerBoolMap(v.begin())).run(s);
    17981797  /// \endcode
    17991798  ///
     
    18191818  ///
    18201819  /// IdMap provides a unique and immutable id for each item of the
    1821   /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is 
     1820  /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is
    18221821  ///  - \b unique: different items get different ids,
    18231822  ///  - \b immutable: the id of an item does not change (even if you
     
    18271826  /// the items stored in the graph, which is returned by the \c id()
    18281827  /// function of the graph. This map can be inverted with its member
    1829   /// class \c InverseMap or with the \c operator() member.
     1828  /// class \c InverseMap or with the \c operator()() member.
    18301829  ///
    18311830  /// \tparam GR The graph type.
     
    18671866  public:
    18681867
    1869     /// \brief This class represents the inverse of its owner (IdMap).
    1870     ///
    1871     /// This class represents the inverse of its owner (IdMap).
     1868    /// \brief The inverse map type of IdMap.
     1869    ///
     1870    /// The inverse map type of IdMap. The subscript operator gives back
     1871    /// an item by its id.
     1872    /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
    18721873    /// \see inverse()
    18731874    class InverseMap {
     
    18841885      explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
    18851886
    1886       /// \brief Gives back the given item from its id.
     1887      /// \brief Gives back an item by its id.
    18871888      ///
    1888       /// Gives back the given item from its id.
     1889      /// Gives back an item by its id.
    18891890      Item operator[](int id) const { return _graph->fromId(id, Item());}
    18901891
     
    18991900  };
    19001901
     1902  /// \brief Returns an \c IdMap class.
     1903  ///
     1904  /// This function just returns an \c IdMap class.
     1905  /// \relates IdMap
     1906  template <typename K, typename GR>
     1907  inline IdMap<GR, K> idMap(const GR& graph) {
     1908    return IdMap<GR, K>(graph);
     1909  }
    19011910
    19021911  /// \brief General cross reference graph map type.
     
    19051914  /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
    19061915  /// and if a key is set to a new value, then stores it in the inverse map.
    1907   /// The values of the map can be accessed
    1908   /// with stl compatible forward iterator.
     1916  /// The graph items can be accessed by their values either using
     1917  /// \c InverseMap or \c operator()(), and the values of the map can be
     1918  /// accessed with an STL compatible forward iterator (\c ValueIt).
     1919  ///
     1920  /// This map is intended to be used when all associated values are
     1921  /// different (the map is actually invertable) or there are only a few
     1922  /// items with the same value.
     1923  /// Otherwise consider to use \c IterableValueMap, which is more
     1924  /// suitable and more efficient for such cases. It provides iterators
     1925  /// to traverse the items with the same associated value, however
     1926  /// it does not have \c InverseMap.
    19091927  ///
    19101928  /// This type is not reference map, so it cannot be modified with
     
    19471965    /// \brief Forward iterator for values.
    19481966    ///
    1949     /// This iterator is an stl compatible forward
     1967    /// This iterator is an STL compatible forward
    19501968    /// iterator on the values of the map. The values can
    19511969    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
    19521970    /// They are considered with multiplicity, so each value is
    19531971    /// traversed for each item it is assigned to.
    1954     class ValueIterator
     1972    class ValueIt
    19551973      : public std::iterator<std::forward_iterator_tag, Value> {
    19561974      friend class CrossRefMap;
    19571975    private:
    1958       ValueIterator(typename Container::const_iterator _it)
     1976      ValueIt(typename Container::const_iterator _it)
    19591977        : it(_it) {}
    19601978    public:
    19611979
    1962       ValueIterator() {}
    1963 
    1964       ValueIterator& operator++() { ++it; return *this; }
    1965       ValueIterator operator++(int) {
    1966         ValueIterator tmp(*this);
     1980      /// Constructor
     1981      ValueIt() {}
     1982
     1983      /// \e
     1984      ValueIt& operator++() { ++it; return *this; }
     1985      /// \e
     1986      ValueIt operator++(int) {
     1987        ValueIt tmp(*this);
    19671988        operator++();
    19681989        return tmp;
    19691990      }
    19701991
     1992      /// \e
    19711993      const Value& operator*() const { return it->first; }
     1994      /// \e
    19721995      const Value* operator->() const { return &(it->first); }
    19731996
    1974       bool operator==(ValueIterator jt) const { return it == jt.it; }
    1975       bool operator!=(ValueIterator jt) const { return it != jt.it; }
     1997      /// \e
     1998      bool operator==(ValueIt jt) const { return it == jt.it; }
     1999      /// \e
     2000      bool operator!=(ValueIt jt) const { return it != jt.it; }
    19762001
    19772002    private:
    19782003      typename Container::const_iterator it;
    19792004    };
     2005   
     2006    /// Alias for \c ValueIt
     2007    typedef ValueIt ValueIterator;
    19802008
    19812009    /// \brief Returns an iterator to the first value.
    19822010    ///
    1983     /// Returns an stl compatible iterator to the
     2011    /// Returns an STL compatible iterator to the
    19842012    /// first value of the map. The values of the
    19852013    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
    19862014    /// range.
    1987     ValueIterator beginValue() const {
    1988       return ValueIterator(_inv_map.begin());
     2015    ValueIt beginValue() const {
     2016      return ValueIt(_inv_map.begin());
    19892017    }
    19902018
    19912019    /// \brief Returns an iterator after the last value.
    19922020    ///
    1993     /// Returns an stl compatible iterator after the
     2021    /// Returns an STL compatible iterator after the
    19942022    /// last value of the map. The values of the
    19952023    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
    19962024    /// range.
    1997     ValueIterator endValue() const {
    1998       return ValueIterator(_inv_map.end());
     2025    ValueIt endValue() const {
     2026      return ValueIt(_inv_map.end());
    19992027    }
    20002028
     
    20332061      typename Container::const_iterator it = _inv_map.find(val);
    20342062      return it != _inv_map.end() ? it->second : INVALID;
     2063    }
     2064   
     2065    /// \brief Returns the number of items with the given value.
     2066    ///
     2067    /// This function returns the number of items with the given value
     2068    /// associated with it.
     2069    int count(const Value &val) const {
     2070      return _inv_map.count(val);
    20352071    }
    20362072
     
    20842120  public:
    20852121
    2086     /// \brief The inverse map type.
    2087     ///
    2088     /// The inverse of this map. The subscript operator of the map
    2089     /// gives back the item that was last assigned to the value.
     2122    /// \brief The inverse map type of CrossRefMap.
     2123    ///
     2124    /// The inverse map type of CrossRefMap. The subscript operator gives
     2125    /// back an item by its value.
     2126    /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
     2127    /// \see inverse()
    20902128    class InverseMap {
    20912129    public:
     
    21142152    };
    21152153
    2116     /// \brief It gives back the read-only inverse map.
    2117     ///
    2118     /// It gives back the read-only inverse map.
     2154    /// \brief Gives back the inverse of the map.
     2155    ///
     2156    /// Gives back the inverse of the CrossRefMap.
    21192157    InverseMap inverse() const {
    21202158      return InverseMap(*this);
     
    21232161  };
    21242162
    2125   /// \brief Provides continuous and unique ID for the
     2163  /// \brief Provides continuous and unique id for the
    21262164  /// items of a graph.
    21272165  ///
    21282166  /// RangeIdMap provides a unique and continuous
    2129   /// ID for each item of a given type (\c Node, \c Arc or
     2167  /// id for each item of a given type (\c Node, \c Arc or
    21302168  /// \c Edge) in a graph. This id is
    21312169  ///  - \b unique: different items get different ids,
     
    21382176  /// the \c id() function of the graph or \ref IdMap.
    21392177  /// This map can be inverted with its member class \c InverseMap,
    2140   /// or with the \c operator() member.
     2178  /// or with the \c operator()() member.
    21412179  ///
    21422180  /// \tparam GR The graph type.
     
    22662304    }
    22672305
    2268     /// \brief Gives back the \e RangeId of the item
    2269     ///
    2270     /// Gives back the \e RangeId of the item.
     2306    /// \brief Gives back the \e range \e id of the item
     2307    ///
     2308    /// Gives back the \e range \e id of the item.
    22712309    int operator[](const Item& item) const {
    22722310      return Map::operator[](item);
    22732311    }
    22742312
    2275     /// \brief Gives back the item belonging to a \e RangeId
    2276     /// 
    2277     /// Gives back the item belonging to a \e RangeId.
     2313    /// \brief Gives back the item belonging to a \e range \e id
     2314    ///
     2315    /// Gives back the item belonging to the given \e range \e id.
    22782316    Item operator()(int id) const {
    22792317      return _inv_map[id];
     
    22892327    /// \brief The inverse map type of RangeIdMap.
    22902328    ///
    2291     /// The inverse map type of RangeIdMap.
     2329    /// The inverse map type of RangeIdMap. The subscript operator gives
     2330    /// back an item by its \e range \e id.
     2331    /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
    22922332    class InverseMap {
    22932333    public:
     
    23072347      ///
    23082348      /// Subscript operator. It gives back the item
    2309       /// that the descriptor currently belongs to.
     2349      /// that the given \e range \e id currently belongs to.
    23102350      Value operator[](const Key& key) const {
    23112351        return _inverted(key);
     
    23252365    /// \brief Gives back the inverse of the map.
    23262366    ///
    2327     /// Gives back the inverse of the map.
     2367    /// Gives back the inverse of the RangeIdMap.
    23282368    const InverseMap inverse() const {
    23292369      return InverseMap(*this);
    23302370    }
     2371  };
     2372
     2373  /// \brief Returns a \c RangeIdMap class.
     2374  ///
     2375  /// This function just returns an \c RangeIdMap class.
     2376  /// \relates RangeIdMap
     2377  template <typename K, typename GR>
     2378  inline RangeIdMap<GR, K> rangeIdMap(const GR& graph) {
     2379    return RangeIdMap<GR, K>(graph);
     2380  }
     2381 
     2382  /// \brief Dynamic iterable \c bool map.
     2383  ///
     2384  /// This class provides a special graph map type which can store a
     2385  /// \c bool value for graph items (\c Node, \c Arc or \c Edge).
     2386  /// For both \c true and \c false values it is possible to iterate on
     2387  /// the keys mapped to the value.
     2388  ///
     2389  /// This type is a reference map, so it can be modified with the
     2390  /// subscript operator.
     2391  ///
     2392  /// \tparam GR The graph type.
     2393  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
     2394  /// \c GR::Edge).
     2395  ///
     2396  /// \see IterableIntMap, IterableValueMap
     2397  /// \see CrossRefMap
     2398  template <typename GR, typename K>
     2399  class IterableBoolMap
     2400    : protected ItemSetTraits<GR, K>::template Map<int>::Type {
     2401  private:
     2402    typedef GR Graph;
     2403
     2404    typedef typename ItemSetTraits<GR, K>::ItemIt KeyIt;
     2405    typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Parent;
     2406
     2407    std::vector<K> _array;
     2408    int _sep;
     2409
     2410  public:
     2411
     2412    /// Indicates that the map is reference map.
     2413    typedef True ReferenceMapTag;
     2414
     2415    /// The key type
     2416    typedef K Key;
     2417    /// The value type
     2418    typedef bool Value;
     2419    /// The const reference type.
     2420    typedef const Value& ConstReference;
     2421
     2422  private:
     2423
     2424    int position(const Key& key) const {
     2425      return Parent::operator[](key);
     2426    }
     2427
     2428  public:
     2429
     2430    /// \brief Reference to the value of the map.
     2431    ///
     2432    /// This class is similar to the \c bool type. It can be converted to
     2433    /// \c bool and it provides the same operators.
     2434    class Reference {
     2435      friend class IterableBoolMap;
     2436    private:
     2437      Reference(IterableBoolMap& map, const Key& key)
     2438        : _key(key), _map(map) {}
     2439    public:
     2440
     2441      Reference& operator=(const Reference& value) {
     2442        _map.set(_key, static_cast<bool>(value));
     2443         return *this;
     2444      }
     2445
     2446      operator bool() const {
     2447        return static_cast<const IterableBoolMap&>(_map)[_key];
     2448      }
     2449
     2450      Reference& operator=(bool value) {
     2451        _map.set(_key, value);
     2452        return *this;
     2453      }
     2454      Reference& operator&=(bool value) {
     2455        _map.set(_key, _map[_key] & value);
     2456        return *this;
     2457      }
     2458      Reference& operator|=(bool value) {
     2459        _map.set(_key, _map[_key] | value);
     2460        return *this;
     2461      }
     2462      Reference& operator^=(bool value) {
     2463        _map.set(_key, _map[_key] ^ value);
     2464        return *this;
     2465      }
     2466    private:
     2467      Key _key;
     2468      IterableBoolMap& _map;
     2469    };
     2470
     2471    /// \brief Constructor of the map with a default value.
     2472    ///
     2473    /// Constructor of the map with a default value.
     2474    explicit IterableBoolMap(const Graph& graph, bool def = false)
     2475      : Parent(graph) {
     2476      typename Parent::Notifier* nf = Parent::notifier();
     2477      Key it;
     2478      for (nf->first(it); it != INVALID; nf->next(it)) {
     2479        Parent::set(it, _array.size());
     2480        _array.push_back(it);
     2481      }
     2482      _sep = (def ? _array.size() : 0);
     2483    }
     2484
     2485    /// \brief Const subscript operator of the map.
     2486    ///
     2487    /// Const subscript operator of the map.
     2488    bool operator[](const Key& key) const {
     2489      return position(key) < _sep;
     2490    }
     2491
     2492    /// \brief Subscript operator of the map.
     2493    ///
     2494    /// Subscript operator of the map.
     2495    Reference operator[](const Key& key) {
     2496      return Reference(*this, key);
     2497    }
     2498
     2499    /// \brief Set operation of the map.
     2500    ///
     2501    /// Set operation of the map.
     2502    void set(const Key& key, bool value) {
     2503      int pos = position(key);
     2504      if (value) {
     2505        if (pos < _sep) return;
     2506        Key tmp = _array[_sep];
     2507        _array[_sep] = key;
     2508        Parent::set(key, _sep);
     2509        _array[pos] = tmp;
     2510        Parent::set(tmp, pos);
     2511        ++_sep;
     2512      } else {
     2513        if (pos >= _sep) return;
     2514        --_sep;
     2515        Key tmp = _array[_sep];
     2516        _array[_sep] = key;
     2517        Parent::set(key, _sep);
     2518        _array[pos] = tmp;
     2519        Parent::set(tmp, pos);
     2520      }
     2521    }
     2522
     2523    /// \brief Set all items.
     2524    ///
     2525    /// Set all items in the map.
     2526    /// \note Constant time operation.
     2527    void setAll(bool value) {
     2528      _sep = (value ? _array.size() : 0);
     2529    }
     2530
     2531    /// \brief Returns the number of the keys mapped to \c true.
     2532    ///
     2533    /// Returns the number of the keys mapped to \c true.
     2534    int trueNum() const {
     2535      return _sep;
     2536    }
     2537
     2538    /// \brief Returns the number of the keys mapped to \c false.
     2539    ///
     2540    /// Returns the number of the keys mapped to \c false.
     2541    int falseNum() const {
     2542      return _array.size() - _sep;
     2543    }
     2544
     2545    /// \brief Iterator for the keys mapped to \c true.
     2546    ///
     2547    /// Iterator for the keys mapped to \c true. It works
     2548    /// like a graph item iterator, it can be converted to
     2549    /// the key type of the map, incremented with \c ++ operator, and
     2550    /// if the iterator leaves the last valid key, it will be equal to
     2551    /// \c INVALID.
     2552    class TrueIt : public Key {
     2553    public:
     2554      typedef Key Parent;
     2555
     2556      /// \brief Creates an iterator.
     2557      ///
     2558      /// Creates an iterator. It iterates on the
     2559      /// keys mapped to \c true.
     2560      /// \param map The IterableBoolMap.
     2561      explicit TrueIt(const IterableBoolMap& map)
     2562        : Parent(map._sep > 0 ? map._array[map._sep - 1] : INVALID),
     2563          _map(&map) {}
     2564
     2565      /// \brief Invalid constructor \& conversion.
     2566      ///
     2567      /// This constructor initializes the iterator to be invalid.
     2568      /// \sa Invalid for more details.
     2569      TrueIt(Invalid) : Parent(INVALID), _map(0) {}
     2570
     2571      /// \brief Increment operator.
     2572      ///
     2573      /// Increment operator.
     2574      TrueIt& operator++() {
     2575        int pos = _map->position(*this);
     2576        Parent::operator=(pos > 0 ? _map->_array[pos - 1] : INVALID);
     2577        return *this;
     2578      }
     2579
     2580    private:
     2581      const IterableBoolMap* _map;
     2582    };
     2583
     2584    /// \brief Iterator for the keys mapped to \c false.
     2585    ///
     2586    /// Iterator for the keys mapped to \c false. It works
     2587    /// like a graph item iterator, it can be converted to
     2588    /// the key type of the map, incremented with \c ++ operator, and
     2589    /// if the iterator leaves the last valid key, it will be equal to
     2590    /// \c INVALID.
     2591    class FalseIt : public Key {
     2592    public:
     2593      typedef Key Parent;
     2594
     2595      /// \brief Creates an iterator.
     2596      ///
     2597      /// Creates an iterator. It iterates on the
     2598      /// keys mapped to \c false.
     2599      /// \param map The IterableBoolMap.
     2600      explicit FalseIt(const IterableBoolMap& map)
     2601        : Parent(map._sep < int(map._array.size()) ?
     2602                 map._array.back() : INVALID), _map(&map) {}
     2603
     2604      /// \brief Invalid constructor \& conversion.
     2605      ///
     2606      /// This constructor initializes the iterator to be invalid.
     2607      /// \sa Invalid for more details.
     2608      FalseIt(Invalid) : Parent(INVALID), _map(0) {}
     2609
     2610      /// \brief Increment operator.
     2611      ///
     2612      /// Increment operator.
     2613      FalseIt& operator++() {
     2614        int pos = _map->position(*this);
     2615        Parent::operator=(pos > _map->_sep ? _map->_array[pos - 1] : INVALID);
     2616        return *this;
     2617      }
     2618
     2619    private:
     2620      const IterableBoolMap* _map;
     2621    };
     2622
     2623    /// \brief Iterator for the keys mapped to a given value.
     2624    ///
     2625    /// Iterator for the keys mapped to a given value. It works
     2626    /// like a graph item iterator, it can be converted to
     2627    /// the key type of the map, incremented with \c ++ operator, and
     2628    /// if the iterator leaves the last valid key, it will be equal to
     2629    /// \c INVALID.
     2630    class ItemIt : public Key {
     2631    public:
     2632      typedef Key Parent;
     2633
     2634      /// \brief Creates an iterator with a value.
     2635      ///
     2636      /// Creates an iterator with a value. It iterates on the
     2637      /// keys mapped to the given value.
     2638      /// \param map The IterableBoolMap.
     2639      /// \param value The value.
     2640      ItemIt(const IterableBoolMap& map, bool value)
     2641        : Parent(value ?
     2642                 (map._sep > 0 ?
     2643                  map._array[map._sep - 1] : INVALID) :
     2644                 (map._sep < int(map._array.size()) ?
     2645                  map._array.back() : INVALID)), _map(&map) {}
     2646
     2647      /// \brief Invalid constructor \& conversion.
     2648      ///
     2649      /// This constructor initializes the iterator to be invalid.
     2650      /// \sa Invalid for more details.
     2651      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
     2652
     2653      /// \brief Increment operator.
     2654      ///
     2655      /// Increment operator.
     2656      ItemIt& operator++() {
     2657        int pos = _map->position(*this);
     2658        int _sep = pos >= _map->_sep ? _map->_sep : 0;
     2659        Parent::operator=(pos > _sep ? _map->_array[pos - 1] : INVALID);
     2660        return *this;
     2661      }
     2662
     2663    private:
     2664      const IterableBoolMap* _map;
     2665    };
     2666
     2667  protected:
     2668
     2669    virtual void add(const Key& key) {
     2670      Parent::add(key);
     2671      Parent::set(key, _array.size());
     2672      _array.push_back(key);
     2673    }
     2674
     2675    virtual void add(const std::vector<Key>& keys) {
     2676      Parent::add(keys);
     2677      for (int i = 0; i < int(keys.size()); ++i) {
     2678        Parent::set(keys[i], _array.size());
     2679        _array.push_back(keys[i]);
     2680      }
     2681    }
     2682
     2683    virtual void erase(const Key& key) {
     2684      int pos = position(key);
     2685      if (pos < _sep) {
     2686        --_sep;
     2687        Parent::set(_array[_sep], pos);
     2688        _array[pos] = _array[_sep];
     2689        Parent::set(_array.back(), _sep);
     2690        _array[_sep] = _array.back();
     2691        _array.pop_back();
     2692      } else {
     2693        Parent::set(_array.back(), pos);
     2694        _array[pos] = _array.back();
     2695        _array.pop_back();
     2696      }
     2697      Parent::erase(key);
     2698    }
     2699
     2700    virtual void erase(const std::vector<Key>& keys) {
     2701      for (int i = 0; i < int(keys.size()); ++i) {
     2702        int pos = position(keys[i]);
     2703        if (pos < _sep) {
     2704          --_sep;
     2705          Parent::set(_array[_sep], pos);
     2706          _array[pos] = _array[_sep];
     2707          Parent::set(_array.back(), _sep);
     2708          _array[_sep] = _array.back();
     2709          _array.pop_back();
     2710        } else {
     2711          Parent::set(_array.back(), pos);
     2712          _array[pos] = _array.back();
     2713          _array.pop_back();
     2714        }
     2715      }
     2716      Parent::erase(keys);
     2717    }
     2718
     2719    virtual void build() {
     2720      Parent::build();
     2721      typename Parent::Notifier* nf = Parent::notifier();
     2722      Key it;
     2723      for (nf->first(it); it != INVALID; nf->next(it)) {
     2724        Parent::set(it, _array.size());
     2725        _array.push_back(it);
     2726      }
     2727      _sep = 0;
     2728    }
     2729
     2730    virtual void clear() {
     2731      _array.clear();
     2732      _sep = 0;
     2733      Parent::clear();
     2734    }
     2735
     2736  };
     2737
     2738
     2739  namespace _maps_bits {
     2740    template <typename Item>
     2741    struct IterableIntMapNode {
     2742      IterableIntMapNode() : value(-1) {}
     2743      IterableIntMapNode(int _value) : value(_value) {}
     2744      Item prev, next;
     2745      int value;
     2746    };
     2747  }
     2748
     2749  /// \brief Dynamic iterable integer map.
     2750  ///
     2751  /// This class provides a special graph map type which can store an
     2752  /// integer value for graph items (\c Node, \c Arc or \c Edge).
     2753  /// For each non-negative value it is possible to iterate on the keys
     2754  /// mapped to the value.
     2755  ///
     2756  /// This map is intended to be used with small integer values, for which
     2757  /// it is efficient, and supports iteration only for non-negative values.
     2758  /// If you need large values and/or iteration for negative integers,
     2759  /// consider to use \ref IterableValueMap instead.
     2760  ///
     2761  /// This type is a reference map, so it can be modified with the
     2762  /// subscript operator.
     2763  ///
     2764  /// \note The size of the data structure depends on the largest
     2765  /// value in the map.
     2766  ///
     2767  /// \tparam GR The graph type.
     2768  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
     2769  /// \c GR::Edge).
     2770  ///
     2771  /// \see IterableBoolMap, IterableValueMap
     2772  /// \see CrossRefMap
     2773  template <typename GR, typename K>
     2774  class IterableIntMap
     2775    : protected ItemSetTraits<GR, K>::
     2776        template Map<_maps_bits::IterableIntMapNode<K> >::Type {
     2777  public:
     2778    typedef typename ItemSetTraits<GR, K>::
     2779      template Map<_maps_bits::IterableIntMapNode<K> >::Type Parent;
     2780
     2781    /// The key type
     2782    typedef K Key;
     2783    /// The value type
     2784    typedef int Value;
     2785    /// The graph type
     2786    typedef GR Graph;
     2787
     2788    /// \brief Constructor of the map.
     2789    ///
     2790    /// Constructor of the map. It sets all values to -1.
     2791    explicit IterableIntMap(const Graph& graph)
     2792      : Parent(graph) {}
     2793
     2794    /// \brief Constructor of the map with a given value.
     2795    ///
     2796    /// Constructor of the map with a given value.
     2797    explicit IterableIntMap(const Graph& graph, int value)
     2798      : Parent(graph, _maps_bits::IterableIntMapNode<K>(value)) {
     2799      if (value >= 0) {
     2800        for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
     2801          lace(it);
     2802        }
     2803      }
     2804    }
     2805
     2806  private:
     2807
     2808    void unlace(const Key& key) {
     2809      typename Parent::Value& node = Parent::operator[](key);
     2810      if (node.value < 0) return;
     2811      if (node.prev != INVALID) {
     2812        Parent::operator[](node.prev).next = node.next;
     2813      } else {
     2814        _first[node.value] = node.next;
     2815      }
     2816      if (node.next != INVALID) {
     2817        Parent::operator[](node.next).prev = node.prev;
     2818      }
     2819      while (!_first.empty() && _first.back() == INVALID) {
     2820        _first.pop_back();
     2821      }
     2822    }
     2823
     2824    void lace(const Key& key) {
     2825      typename Parent::Value& node = Parent::operator[](key);
     2826      if (node.value < 0) return;
     2827      if (node.value >= int(_first.size())) {
     2828        _first.resize(node.value + 1, INVALID);
     2829      }
     2830      node.prev = INVALID;
     2831      node.next = _first[node.value];
     2832      if (node.next != INVALID) {
     2833        Parent::operator[](node.next).prev = key;
     2834      }
     2835      _first[node.value] = key;
     2836    }
     2837
     2838  public:
     2839
     2840    /// Indicates that the map is reference map.
     2841    typedef True ReferenceMapTag;
     2842
     2843    /// \brief Reference to the value of the map.
     2844    ///
     2845    /// This class is similar to the \c int type. It can
     2846    /// be converted to \c int and it has the same operators.
     2847    class Reference {
     2848      friend class IterableIntMap;
     2849    private:
     2850      Reference(IterableIntMap& map, const Key& key)
     2851        : _key(key), _map(map) {}
     2852    public:
     2853
     2854      Reference& operator=(const Reference& value) {
     2855        _map.set(_key, static_cast<const int&>(value));
     2856         return *this;
     2857      }
     2858
     2859      operator const int&() const {
     2860        return static_cast<const IterableIntMap&>(_map)[_key];
     2861      }
     2862
     2863      Reference& operator=(int value) {
     2864        _map.set(_key, value);
     2865        return *this;
     2866      }
     2867      Reference& operator++() {
     2868        _map.set(_key, _map[_key] + 1);
     2869        return *this;
     2870      }
     2871      int operator++(int) {
     2872        int value = _map[_key];
     2873        _map.set(_key, value + 1);
     2874        return value;
     2875      }
     2876      Reference& operator--() {
     2877        _map.set(_key, _map[_key] - 1);
     2878        return *this;
     2879      }
     2880      int operator--(int) {
     2881        int value = _map[_key];
     2882        _map.set(_key, value - 1);
     2883        return value;
     2884      }
     2885      Reference& operator+=(int value) {
     2886        _map.set(_key, _map[_key] + value);
     2887        return *this;
     2888      }
     2889      Reference& operator-=(int value) {
     2890        _map.set(_key, _map[_key] - value);
     2891        return *this;
     2892      }
     2893      Reference& operator*=(int value) {
     2894        _map.set(_key, _map[_key] * value);
     2895        return *this;
     2896      }
     2897      Reference& operator/=(int value) {
     2898        _map.set(_key, _map[_key] / value);
     2899        return *this;
     2900      }
     2901      Reference& operator%=(int value) {
     2902        _map.set(_key, _map[_key] % value);
     2903        return *this;
     2904      }
     2905      Reference& operator&=(int value) {
     2906        _map.set(_key, _map[_key] & value);
     2907        return *this;
     2908      }
     2909      Reference& operator|=(int value) {
     2910        _map.set(_key, _map[_key] | value);
     2911        return *this;
     2912      }
     2913      Reference& operator^=(int value) {
     2914        _map.set(_key, _map[_key] ^ value);
     2915        return *this;
     2916      }
     2917      Reference& operator<<=(int value) {
     2918        _map.set(_key, _map[_key] << value);
     2919        return *this;
     2920      }
     2921      Reference& operator>>=(int value) {
     2922        _map.set(_key, _map[_key] >> value);
     2923        return *this;
     2924      }
     2925
     2926    private:
     2927      Key _key;
     2928      IterableIntMap& _map;
     2929    };
     2930
     2931    /// The const reference type.
     2932    typedef const Value& ConstReference;
     2933
     2934    /// \brief Gives back the maximal value plus one.
     2935    ///
     2936    /// Gives back the maximal value plus one.
     2937    int size() const {
     2938      return _first.size();
     2939    }
     2940
     2941    /// \brief Set operation of the map.
     2942    ///
     2943    /// Set operation of the map.
     2944    void set(const Key& key, const Value& value) {
     2945      unlace(key);
     2946      Parent::operator[](key).value = value;
     2947      lace(key);
     2948    }
     2949
     2950    /// \brief Const subscript operator of the map.
     2951    ///
     2952    /// Const subscript operator of the map.
     2953    const Value& operator[](const Key& key) const {
     2954      return Parent::operator[](key).value;
     2955    }
     2956
     2957    /// \brief Subscript operator of the map.
     2958    ///
     2959    /// Subscript operator of the map.
     2960    Reference operator[](const Key& key) {
     2961      return Reference(*this, key);
     2962    }
     2963
     2964    /// \brief Iterator for the keys with the same value.
     2965    ///
     2966    /// Iterator for the keys with the same value. It works
     2967    /// like a graph item iterator, it can be converted to
     2968    /// the item type of the map, incremented with \c ++ operator, and
     2969    /// if the iterator leaves the last valid item, it will be equal to
     2970    /// \c INVALID.
     2971    class ItemIt : public Key {
     2972    public:
     2973      typedef Key Parent;
     2974
     2975      /// \brief Invalid constructor \& conversion.
     2976      ///
     2977      /// This constructor initializes the iterator to be invalid.
     2978      /// \sa Invalid for more details.
     2979      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
     2980
     2981      /// \brief Creates an iterator with a value.
     2982      ///
     2983      /// Creates an iterator with a value. It iterates on the
     2984      /// keys mapped to the given value.
     2985      /// \param map The IterableIntMap.
     2986      /// \param value The value.
     2987      ItemIt(const IterableIntMap& map, int value) : _map(&map) {
     2988        if (value < 0 || value >= int(_map->_first.size())) {
     2989          Parent::operator=(INVALID);
     2990        } else {
     2991          Parent::operator=(_map->_first[value]);
     2992        }
     2993      }
     2994
     2995      /// \brief Increment operator.
     2996      ///
     2997      /// Increment operator.
     2998      ItemIt& operator++() {
     2999        Parent::operator=(_map->IterableIntMap::Parent::
     3000                          operator[](static_cast<Parent&>(*this)).next);
     3001        return *this;
     3002      }
     3003
     3004    private:
     3005      const IterableIntMap* _map;
     3006    };
     3007
     3008  protected:
     3009
     3010    virtual void erase(const Key& key) {
     3011      unlace(key);
     3012      Parent::erase(key);
     3013    }
     3014
     3015    virtual void erase(const std::vector<Key>& keys) {
     3016      for (int i = 0; i < int(keys.size()); ++i) {
     3017        unlace(keys[i]);
     3018      }
     3019      Parent::erase(keys);
     3020    }
     3021
     3022    virtual void clear() {
     3023      _first.clear();
     3024      Parent::clear();
     3025    }
     3026
     3027  private:
     3028    std::vector<Key> _first;
     3029  };
     3030
     3031  namespace _maps_bits {
     3032    template <typename Item, typename Value>
     3033    struct IterableValueMapNode {
     3034      IterableValueMapNode(Value _value = Value()) : value(_value) {}
     3035      Item prev, next;
     3036      Value value;
     3037    };
     3038  }
     3039
     3040  /// \brief Dynamic iterable map for comparable values.
     3041  ///
     3042  /// This class provides a special graph map type which can store a
     3043  /// comparable value for graph items (\c Node, \c Arc or \c Edge).
     3044  /// For each value it is possible to iterate on the keys mapped to
     3045  /// the value (\c ItemIt), and the values of the map can be accessed
     3046  /// with an STL compatible forward iterator (\c ValueIt).
     3047  /// The map stores a linked list for each value, which contains
     3048  /// the items mapped to the value, and the used values are stored
     3049  /// in balanced binary tree (\c std::map).
     3050  ///
     3051  /// \ref IterableBoolMap and \ref IterableIntMap are similar classes
     3052  /// specialized for \c bool and \c int values, respectively.
     3053  ///
     3054  /// This type is not reference map, so it cannot be modified with
     3055  /// the subscript operator.
     3056  ///
     3057  /// \tparam GR The graph type.
     3058  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
     3059  /// \c GR::Edge).
     3060  /// \tparam V The value type of the map. It can be any comparable
     3061  /// value type.
     3062  ///
     3063  /// \see IterableBoolMap, IterableIntMap
     3064  /// \see CrossRefMap
     3065  template <typename GR, typename K, typename V>
     3066  class IterableValueMap
     3067    : protected ItemSetTraits<GR, K>::
     3068        template Map<_maps_bits::IterableValueMapNode<K, V> >::Type {
     3069  public:
     3070    typedef typename ItemSetTraits<GR, K>::
     3071      template Map<_maps_bits::IterableValueMapNode<K, V> >::Type Parent;
     3072
     3073    /// The key type
     3074    typedef K Key;
     3075    /// The value type
     3076    typedef V Value;
     3077    /// The graph type
     3078    typedef GR Graph;
     3079
     3080  public:
     3081
     3082    /// \brief Constructor of the map with a given value.
     3083    ///
     3084    /// Constructor of the map with a given value.
     3085    explicit IterableValueMap(const Graph& graph,
     3086                              const Value& value = Value())
     3087      : Parent(graph, _maps_bits::IterableValueMapNode<K, V>(value)) {
     3088      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
     3089        lace(it);
     3090      }
     3091    }
     3092
     3093  protected:
     3094
     3095    void unlace(const Key& key) {
     3096      typename Parent::Value& node = Parent::operator[](key);
     3097      if (node.prev != INVALID) {
     3098        Parent::operator[](node.prev).next = node.next;
     3099      } else {
     3100        if (node.next != INVALID) {
     3101          _first[node.value] = node.next;
     3102        } else {
     3103          _first.erase(node.value);
     3104        }
     3105      }
     3106      if (node.next != INVALID) {
     3107        Parent::operator[](node.next).prev = node.prev;
     3108      }
     3109    }
     3110
     3111    void lace(const Key& key) {
     3112      typename Parent::Value& node = Parent::operator[](key);
     3113      typename std::map<Value, Key>::iterator it = _first.find(node.value);
     3114      if (it == _first.end()) {
     3115        node.prev = node.next = INVALID;
     3116        _first.insert(std::make_pair(node.value, key));
     3117      } else {
     3118        node.prev = INVALID;
     3119        node.next = it->second;
     3120        if (node.next != INVALID) {
     3121          Parent::operator[](node.next).prev = key;
     3122        }
     3123        it->second = key;
     3124      }
     3125    }
     3126
     3127  public:
     3128
     3129    /// \brief Forward iterator for values.
     3130    ///
     3131    /// This iterator is an STL compatible forward
     3132    /// iterator on the values of the map. The values can
     3133    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
     3134    class ValueIt
     3135      : public std::iterator<std::forward_iterator_tag, Value> {
     3136      friend class IterableValueMap;
     3137    private:
     3138      ValueIt(typename std::map<Value, Key>::const_iterator _it)
     3139        : it(_it) {}
     3140    public:
     3141
     3142      /// Constructor
     3143      ValueIt() {}
     3144
     3145      /// \e
     3146      ValueIt& operator++() { ++it; return *this; }
     3147      /// \e
     3148      ValueIt operator++(int) {
     3149        ValueIt tmp(*this);
     3150        operator++();
     3151        return tmp;
     3152      }
     3153
     3154      /// \e
     3155      const Value& operator*() const { return it->first; }
     3156      /// \e
     3157      const Value* operator->() const { return &(it->first); }
     3158
     3159      /// \e
     3160      bool operator==(ValueIt jt) const { return it == jt.it; }
     3161      /// \e
     3162      bool operator!=(ValueIt jt) const { return it != jt.it; }
     3163
     3164    private:
     3165      typename std::map<Value, Key>::const_iterator it;
     3166    };
     3167
     3168    /// \brief Returns an iterator to the first value.
     3169    ///
     3170    /// Returns an STL compatible iterator to the
     3171    /// first value of the map. The values of the
     3172    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
     3173    /// range.
     3174    ValueIt beginValue() const {
     3175      return ValueIt(_first.begin());
     3176    }
     3177
     3178    /// \brief Returns an iterator after the last value.
     3179    ///
     3180    /// Returns an STL compatible iterator after the
     3181    /// last value of the map. The values of the
     3182    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
     3183    /// range.
     3184    ValueIt endValue() const {
     3185      return ValueIt(_first.end());
     3186    }
     3187
     3188    /// \brief Set operation of the map.
     3189    ///
     3190    /// Set operation of the map.
     3191    void set(const Key& key, const Value& value) {
     3192      unlace(key);
     3193      Parent::operator[](key).value = value;
     3194      lace(key);
     3195    }
     3196
     3197    /// \brief Const subscript operator of the map.
     3198    ///
     3199    /// Const subscript operator of the map.
     3200    const Value& operator[](const Key& key) const {
     3201      return Parent::operator[](key).value;
     3202    }
     3203
     3204    /// \brief Iterator for the keys with the same value.
     3205    ///
     3206    /// Iterator for the keys with the same value. It works
     3207    /// like a graph item iterator, it can be converted to
     3208    /// the item type of the map, incremented with \c ++ operator, and
     3209    /// if the iterator leaves the last valid item, it will be equal to
     3210    /// \c INVALID.
     3211    class ItemIt : public Key {
     3212    public:
     3213      typedef Key Parent;
     3214
     3215      /// \brief Invalid constructor \& conversion.
     3216      ///
     3217      /// This constructor initializes the iterator to be invalid.
     3218      /// \sa Invalid for more details.
     3219      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
     3220
     3221      /// \brief Creates an iterator with a value.
     3222      ///
     3223      /// Creates an iterator with a value. It iterates on the
     3224      /// keys which have the given value.
     3225      /// \param map The IterableValueMap
     3226      /// \param value The value
     3227      ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) {
     3228        typename std::map<Value, Key>::const_iterator it =
     3229          map._first.find(value);
     3230        if (it == map._first.end()) {
     3231          Parent::operator=(INVALID);
     3232        } else {
     3233          Parent::operator=(it->second);
     3234        }
     3235      }
     3236
     3237      /// \brief Increment operator.
     3238      ///
     3239      /// Increment Operator.
     3240      ItemIt& operator++() {
     3241        Parent::operator=(_map->IterableValueMap::Parent::
     3242                          operator[](static_cast<Parent&>(*this)).next);
     3243        return *this;
     3244      }
     3245
     3246
     3247    private:
     3248      const IterableValueMap* _map;
     3249    };
     3250
     3251  protected:
     3252
     3253    virtual void add(const Key& key) {
     3254      Parent::add(key);
     3255      unlace(key);
     3256    }
     3257
     3258    virtual void add(const std::vector<Key>& keys) {
     3259      Parent::add(keys);
     3260      for (int i = 0; i < int(keys.size()); ++i) {
     3261        lace(keys[i]);
     3262      }
     3263    }
     3264
     3265    virtual void erase(const Key& key) {
     3266      unlace(key);
     3267      Parent::erase(key);
     3268    }
     3269
     3270    virtual void erase(const std::vector<Key>& keys) {
     3271      for (int i = 0; i < int(keys.size()); ++i) {
     3272        unlace(keys[i]);
     3273      }
     3274      Parent::erase(keys);
     3275    }
     3276
     3277    virtual void build() {
     3278      Parent::build();
     3279      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
     3280        lace(it);
     3281      }
     3282    }
     3283
     3284    virtual void clear() {
     3285      _first.clear();
     3286      Parent::clear();
     3287    }
     3288
     3289  private:
     3290    std::map<Value, Key> _first;
    23313291  };
    23323292
     
    23413301  public:
    23423302
    2343     ///\e
     3303    /// The key type (the \c Arc type of the digraph).
    23443304    typedef typename GR::Arc Key;
    2345     ///\e
     3305    /// The value type (the \c Node type of the digraph).
    23463306    typedef typename GR::Node Value;
    23473307
     
    23823342  public:
    23833343
    2384     ///\e
     3344    /// The key type (the \c Arc type of the digraph).
    23853345    typedef typename GR::Arc Key;
    2386     ///\e
     3346    /// The value type (the \c Node type of the digraph).
    23873347    typedef typename GR::Node Value;
    23883348
     
    24243384  public:
    24253385
     3386    /// The key type (the \c Edge type of the digraph).
     3387    typedef typename GR::Edge Key;
     3388    /// The value type (the \c Arc type of the digraph).
    24263389    typedef typename GR::Arc Value;
    2427     typedef typename GR::Edge Key;
    24283390
    24293391    /// \brief Constructor
     
    24643426  public:
    24653427
     3428    /// The key type (the \c Edge type of the digraph).
     3429    typedef typename GR::Edge Key;
     3430    /// The value type (the \c Arc type of the digraph).
    24663431    typedef typename GR::Arc Value;
    2467     typedef typename GR::Edge Key;
    24683432
    24693433    /// \brief Constructor
     
    25003464  /// whenever the digraph changes.
    25013465  ///
    2502   /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
     3466  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
    25033467  /// may provide alternative ways to modify the digraph.
    25043468  /// The correct behavior of InDegMap is not guarantied if these additional
     
    25163480
    25173481  public:
    2518    
     3482
    25193483    /// The graph type of InDegMap
    25203484    typedef GR Graph;
     
    26303594  /// whenever the digraph changes.
    26313595  ///
    2632   /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
     3596  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
    26333597  /// may provide alternative ways to modify the digraph.
    26343598  /// The correct behavior of OutDegMap is not guarantied if these additional
  • lemon/min_cost_arborescence.h

    r625 r713  
    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 more control on the execution,
    492     /// first you must call \ref init(), then you can add several
     491    /// If you need better control on the execution,
     492    /// you have to call \ref init() first, then you can add several
    493493    /// source nodes with \ref addSource().
    494494    /// Finally \ref start() will perform the arborescence
  • lemon/network_simplex.h

    r663 r730  
    162162    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
    163163
    164     typedef std::vector<Arc> ArcVector;
    165     typedef std::vector<Node> NodeVector;
    166164    typedef std::vector<int> IntVector;
    167165    typedef std::vector<bool> BoolVector;
     
    365363        Cost c, min = 0;
    366364        int cnt = _block_size;
    367         int e, min_arc = _next_arc;
     365        int e;
    368366        for (e = _next_arc; e < _search_arc_num; ++e) {
    369367          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    370368          if (c < min) {
    371369            min = c;
    372             min_arc = e;
     370            _in_arc = e;
    373371          }
    374372          if (--cnt == 0) {
    375             if (min < 0) break;
     373            if (min < 0) goto search_end;
    376374            cnt = _block_size;
    377375          }
    378376        }
    379         if (min == 0 || cnt > 0) {
    380           for (e = 0; e < _next_arc; ++e) {
    381             c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    382             if (c < min) {
    383               min = c;
    384               min_arc = e;
    385             }
    386             if (--cnt == 0) {
    387               if (min < 0) break;
    388               cnt = _block_size;
    389             }
     377        for (e = 0; e < _next_arc; ++e) {
     378          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     379          if (c < min) {
     380            min = c;
     381            _in_arc = e;
     382          }
     383          if (--cnt == 0) {
     384            if (min < 0) goto search_end;
     385            cnt = _block_size;
    390386          }
    391387        }
    392388        if (min >= 0) return false;
    393         _in_arc = min_arc;
     389
     390      search_end:
    394391        _next_arc = e;
    395392        return true;
     
    429426      {
    430427        // The main parameters of the pivot rule
    431         const double LIST_LENGTH_FACTOR = 1.0;
     428        const double LIST_LENGTH_FACTOR = 0.25;
    432429        const int MIN_LIST_LENGTH = 10;
    433430        const double MINOR_LIMIT_FACTOR = 0.1;
     
    446443      bool findEnteringArc() {
    447444        Cost min, c;
    448         int e, min_arc = _next_arc;
     445        int e;
    449446        if (_curr_length > 0 && _minor_count < _minor_limit) {
    450447          // Minor iteration: select the best eligible arc from the
     
    457454            if (c < min) {
    458455              min = c;
    459               min_arc = e;
     456              _in_arc = e;
    460457            }
    461             if (c >= 0) {
     458            else if (c >= 0) {
    462459              _candidates[i--] = _candidates[--_curr_length];
    463460            }
    464461          }
    465           if (min < 0) {
    466             _in_arc = min_arc;
    467             return true;
    468           }
     462          if (min < 0) return true;
    469463        }
    470464
     
    478472            if (c < min) {
    479473              min = c;
    480               min_arc = e;
     474              _in_arc = e;
    481475            }
    482             if (_curr_length == _list_length) break;
    483           }
    484         }
    485         if (_curr_length < _list_length) {
    486           for (e = 0; e < _next_arc; ++e) {
    487             c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    488             if (c < 0) {
    489               _candidates[_curr_length++] = e;
    490               if (c < min) {
    491                 min = c;
    492                 min_arc = e;
    493               }
    494               if (_curr_length == _list_length) break;
     476            if (_curr_length == _list_length) goto search_end;
     477          }
     478        }
     479        for (e = 0; e < _next_arc; ++e) {
     480          c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     481          if (c < 0) {
     482            _candidates[_curr_length++] = e;
     483            if (c < min) {
     484              min = c;
     485              _in_arc = e;
    495486            }
     487            if (_curr_length == _list_length) goto search_end;
    496488          }
    497489        }
    498490        if (_curr_length == 0) return false;
     491     
     492      search_end:       
    499493        _minor_count = 1;
    500         _in_arc = min_arc;
    501494        _next_arc = e;
    502495        return true;
     
    550543      {
    551544        // The main parameters of the pivot rule
    552         const double BLOCK_SIZE_FACTOR = 1.5;
     545        const double BLOCK_SIZE_FACTOR = 1.0;
    553546        const int MIN_BLOCK_SIZE = 10;
    554547        const double HEAD_LENGTH_FACTOR = 0.1;
     
    579572        // Extend the list
    580573        int cnt = _block_size;
    581         int last_arc = 0;
    582574        int limit = _head_length;
    583575
    584         for (int e = _next_arc; e < _search_arc_num; ++e) {
     576        for (e = _next_arc; e < _search_arc_num; ++e) {
    585577          _cand_cost[e] = _state[e] *
    586578            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    587579          if (_cand_cost[e] < 0) {
    588580            _candidates[_curr_length++] = e;
    589             last_arc = e;
    590581          }
    591582          if (--cnt == 0) {
    592             if (_curr_length > limit) break;
     583            if (_curr_length > limit) goto search_end;
    593584            limit = 0;
    594585            cnt = _block_size;
    595586          }
    596587        }
    597         if (_curr_length <= limit) {
    598           for (int e = 0; e < _next_arc; ++e) {
    599             _cand_cost[e] = _state[e] *
    600               (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
    601             if (_cand_cost[e] < 0) {
    602               _candidates[_curr_length++] = e;
    603               last_arc = e;
    604             }
    605             if (--cnt == 0) {
    606               if (_curr_length > limit) break;
    607               limit = 0;
    608               cnt = _block_size;
    609             }
     588        for (e = 0; e < _next_arc; ++e) {
     589          _cand_cost[e] = _state[e] *
     590            (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
     591          if (_cand_cost[e] < 0) {
     592            _candidates[_curr_length++] = e;
     593          }
     594          if (--cnt == 0) {
     595            if (_curr_length > limit) goto search_end;
     596            limit = 0;
     597            cnt = _block_size;
    610598          }
    611599        }
    612600        if (_curr_length == 0) return false;
    613         _next_arc = last_arc + 1;
     601       
     602      search_end:
    614603
    615604        // Make heap of the candidate list (approximating a partial sort)
     
    619608        // Pop the first element of the heap
    620609        _in_arc = _candidates[0];
     610        _next_arc = e;
    621611        pop_heap( _candidates.begin(), _candidates.begin() + _curr_length,
    622612                  _sort_func );
     
    634624    ///
    635625    /// \param graph The digraph the algorithm runs on.
    636     NetworkSimplex(const GR& graph) :
     626    /// \param arc_mixing Indicate if the arcs have to be stored in a
     627    /// mixed order in the internal data structure.
     628    /// In special cases, it could lead to better overall performance,
     629    /// but it is usually slower. Therefore it is disabled by default.
     630    NetworkSimplex(const GR& graph, bool arc_mixing = false) :
    637631      _graph(graph), _node_id(graph), _arc_id(graph),
    638632      INF(std::numeric_limits<Value>::has_infinity ?
     
    672666      _state.resize(max_arc_num);
    673667
    674       // Copy the graph (store the arcs in a mixed order)
     668      // Copy the graph
    675669      int i = 0;
    676670      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
    677671        _node_id[n] = i;
    678672      }
    679       int k = std::max(int(std::sqrt(double(_arc_num))), 10);
    680       i = 0;
    681       for (ArcIt a(_graph); a != INVALID; ++a) {
    682         _arc_id[a] = i;
    683         _source[i] = _node_id[_graph.source(a)];
    684         _target[i] = _node_id[_graph.target(a)];
    685         if ((i += k) >= _arc_num) i = (i % k) + 1;
     673      if (arc_mixing) {
     674        // Store the arcs in a mixed order
     675        int k = std::max(int(std::sqrt(double(_arc_num))), 10);
     676        int i = 0, j = 0;
     677        for (ArcIt a(_graph); a != INVALID; ++a) {
     678          _arc_id[a] = i;
     679          _source[i] = _node_id[_graph.source(a)];
     680          _target[i] = _node_id[_graph.target(a)];
     681          if ((i += k) >= _arc_num) i = ++j;
     682        }
     683      } else {
     684        // Store the arcs in the original order
     685        int i = 0;
     686        for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
     687          _arc_id[a] = i;
     688          _source[i] = _node_id[_graph.source(a)];
     689          _target[i] = _node_id[_graph.target(a)];
     690        }
    686691      }
    687692     
    688       // Initialize maps
    689       for (int i = 0; i != _node_num; ++i) {
    690         _supply[i] = 0;
    691       }
    692       for (int i = 0; i != _arc_num; ++i) {
    693         _lower[i] = 0;
    694         _upper[i] = INF;
    695         _cost[i] = 1;
    696       }
    697       _have_lower = false;
    698       _stype = GEQ;
     693      // Reset parameters
     694      reset();
    699695    }
    700696
     
    769765    /// If neither this function nor \ref stSupply() is used before
    770766    /// calling \ref run(), the supply of each node will be set to zero.
    771     /// (It makes sense only if non-zero lower bounds are given.)
    772767    ///
    773768    /// \param map A node map storing the supply values.
     
    790785    /// If neither this function nor \ref supplyMap() is used before
    791786    /// calling \ref run(), the supply of each node will be set to zero.
    792     /// (It makes sense only if non-zero lower bounds are given.)
    793787    ///
    794788    /// Using this function has the same effect as using \ref supplyMap()
  • lemon/preflow.h

    r641 r715  
    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
    5558    typedef typename Digraph::template ArcMap<Value> FlowMap;
     59#endif
    5660
    5761    /// \brief Instantiates a FlowMap.
     
    6872    /// The elevator type used by Preflow algorithm.
    6973    ///
    70     /// \sa Elevator
    71     /// \sa LinkedElevator
    72     typedef LinkedElevator<Digraph, typename Digraph::Node> Elevator;
     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
    7380
    7481    /// \brief Instantiates an Elevator.
     
    98105  /// "flow of maximum value" in a digraph.
    99106  /// The preflow algorithms are the fastest known maximum
    100   /// flow algorithms. The current implementation use a mixture of the
     107  /// flow algorithms. The current implementation uses a mixture of the
    101108  /// \e "highest label" and the \e "bound decrease" heuristics.
    102109  /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
     
    372379    }
    373380
    374     /// \brief Sets the tolerance used by algorithm.
    375     ///
    376     /// Sets the tolerance used by algorithm.
    377     Preflow& tolerance(const Tolerance& tolerance) const {
     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) {
    378386      _tolerance = tolerance;
    379387      return *this;
     
    382390    /// \brief Returns a const reference to the tolerance.
    383391    ///
    384     /// Returns a const reference to the tolerance.
     392    /// Returns a const reference to the tolerance object used by
     393    /// the algorithm.
    385394    const Tolerance& tolerance() const {
    386       return tolerance;
     395      return _tolerance;
    387396    }
    388397
     
    390399    /// The simplest way to execute the preflow algorithm is to use
    391400    /// \ref run() or \ref runMinCut().\n
    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
     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
    394403    /// \ref startFirstPhase() and if you need it \ref startSecondPhase().
    395404
  • lemon/radix_heap.h

    r683 r711  
    2020#define LEMON_RADIX_HEAP_H
    2121
    22 ///\ingroup auxdat
     22///\ingroup heaps
    2323///\file
    24 ///\brief Radix Heap implementation.
     24///\brief Radix heap implementation.
    2525
    2626#include <vector>
     
    3030
    3131
    32   /// \ingroup auxdata
     32  /// \ingroup heaps
    3333  ///
    34   /// \brief A Radix Heap implementation.
     34  /// \brief Radix heap data structure.
    3535  ///
    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.
     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.
    4341  ///
    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
     42  /// \tparam IM A read-writable item map with \c int values, used
     43  /// internally to handle the cross references.
    4944  template <typename IM>
    5045  class RadixHeap {
    5146
    5247  public:
    53     typedef typename IM::Key Item;
     48
     49    /// Type of the item-int map.
     50    typedef IM ItemIntMap;
     51    /// Type of the priorities.
    5452    typedef int Prio;
    55     typedef IM ItemIntMap;
     53    /// Type of the items stored in the heap.
     54    typedef typename ItemIntMap::Key Item;
    5655
    5756    /// \brief Exception thrown by RadixHeap.
    5857    ///
    59     /// This Exception is thrown when a smaller priority
    60     /// is inserted into the \e RadixHeap then the last time erased.
     58    /// This exception is thrown when an item is inserted into a
     59    /// RadixHeap with a priority smaller than the last erased one.
    6160    /// \see RadixHeap
    62 
    63     class UnderFlowPriorityError : public Exception {
     61    class PriorityUnderflowError : public Exception {
    6462    public:
    6563      virtual const char* what() const throw() {
    66         return "lemon::RadixHeap::UnderFlowPriorityError";
     64        return "lemon::RadixHeap::PriorityUnderflowError";
    6765      }
    6866    };
    6967
    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
     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
    7472    /// heap's point of view, but may be useful to the user.
    7573    ///
    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...
     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.
    7876    enum State {
    79       IN_HEAP = 0,
    80       PRE_HEAP = -1,
    81       POST_HEAP = -2
     77      IN_HEAP = 0,    ///< = 0.
     78      PRE_HEAP = -1,  ///< = -1.
     79      POST_HEAP = -2  ///< = -2.
    8280    };
    8381
     
    9795    };
    9896
    99     std::vector<RadixItem> data;
    100     std::vector<RadixBox> boxes;
     97    std::vector<RadixItem> _data;
     98    std::vector<RadixBox> _boxes;
    10199
    102100    ItemIntMap &_iim;
    103101
    104 
    105102  public:
    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)) {
     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)) {
    121118        extend();
    122119      }
    123120    }
    124121
    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)) {
     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)) {
    145146        extend();
    146147      }
     
    150151
    151152    bool upper(int box, Prio pr) {
    152       return pr < boxes[box].min;
     153      return pr < _boxes[box].min;
    153154    }
    154155
    155156    bool lower(int box, Prio pr) {
    156       return pr >= boxes[box].min + boxes[box].size;
    157     }
    158 
    159     /// \brief Remove item from the box list.
     157      return pr >= _boxes[box].min + _boxes[box].size;
     158    }
     159
     160    // Remove item from the box list
    160161    void remove(int index) {
    161       if (data[index].prev >= 0) {
    162         data[data[index].prev].next = data[index].next;
     162      if (_data[index].prev >= 0) {
     163        _data[_data[index].prev].next = _data[index].next;
    163164      } else {
    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.
     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
    172173    void insert(int box, int index) {
    173       if (boxes[box].first == -1) {
    174         boxes[box].first = index;
    175         data[index].next = data[index].prev = -1;
     174      if (_boxes[box].first == -1) {
     175        _boxes[box].first = index;
     176        _data[index].next = _data[index].prev = -1;
    176177      } else {
    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.
     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
    186187    void extend() {
    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;
     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;
    195196      remove(index);
    196       int box = findUp(data[index].box, data[index].prio);
     197      int box = findUp(_data[index].box, _data[index].prio);
    197198      insert(box, index);
    198199    }
    199200
    200     /// \brief Find up the proper box for the item with the given prio.
     201    // Find up the proper box for the item with the given priority
    201202    int findUp(int start, int pr) {
    202203      while (lower(start, pr)) {
    203         if (++start == int(boxes.size())) {
     204        if (++start == int(_boxes.size())) {
    204205          extend();
    205206        }
     
    208209    }
    209210
    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;
     211    // Move an item down into the proper box
     212    void bubbleDown(int index) {
     213      if (!upper(_data[index].box, _data[index].prio)) return;
    213214      remove(index);
    214       int box = findDown(data[index].box, data[index].prio);
     215      int box = findDown(_data[index].box, _data[index].prio);
    215216      insert(box, index);
    216217    }
    217218
    218     /// \brief Find up the proper box for the item with the given prio.
     219    // Find down the proper box for the item with the given priority
    219220    int findDown(int start, int pr) {
    220221      while (upper(start, pr)) {
    221         if (--start < 0) throw UnderFlowPriorityError();
     222        if (--start < 0) throw PriorityUnderflowError();
    222223      }
    223224      return start;
    224225    }
    225226
    226     /// \brief Find the first not empty box.
     227    // Find the first non-empty box
    227228    int findFirst() {
    228229      int first = 0;
    229       while (boxes[first].first == -1) ++first;
     230      while (_boxes[first].first == -1) ++first;
    230231      return first;
    231232    }
    232233
    233     /// \brief Gives back the minimal prio of the box.
     234    // Gives back the minimum priority of the given box
    234235    int minValue(int box) {
    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;
     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;
    238239      }
    239240      return min;
    240241    }
    241242
    242     /// \brief Rearrange the items of the heap and makes the
    243     /// first box not empty.
     243    // Rearrange the items of the heap and make the first box non-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         bubble_down(curr);
     254        next = _data[curr].next;
     255        bubbleDown(curr);
    256256        curr = next;
    257257      }
    258258    }
    259259
    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;
     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;
    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     /// Adds \c i to the heap with priority \c p.
     280    /// This function inserts the given item into the heap with the
     281    /// given priority.
    281282    /// \param i The item to insert.
    282283    /// \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.
    283286    void push(const Item &i, const Prio &p) {
    284       int n = data.size();
     287      int n = _data.size();
    285288      _iim.set(i, n);
    286       data.push_back(RadixItem(i, p));
    287       while (lower(boxes.size() - 1, p)) {
     289      _data.push_back(RadixItem(i, p));
     290      while (lower(_boxes.size() - 1, p)) {
    288291        extend();
    289292      }
    290       int box = findDown(boxes.size() - 1, p);
     293      int box = findDown(_boxes.size() - 1, p);
    291294      insert(box, n);
    292295    }
    293296
    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.
     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.
    298301    Item top() const {
    299302      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
    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.
     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.
    307310    Prio prio() const {
    308311      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
    309       return data[boxes[0].first].prio;
     312      return _data[_boxes[0].first].prio;
    310313     }
    311314
    312     /// \brief Deletes the item with minimum priority.
    313     ///
    314     /// This method deletes the item with minimum priority.
     315    /// \brief Remove the item having minimum priority.
     316    ///
     317    /// This function removes the item having minimum priority.
    315318    /// \pre The heap must be non-empty.
    316319    void pop() {
    317320      moveDown();
    318       int index = boxes[0].first;
    319       _iim[data[index].item] = POST_HEAP;
     321      int index = _boxes[0].first;
     322      _iim[_data[index].item] = POST_HEAP;
    320323      remove(index);
    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.
     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.
    329333    void erase(const Item &i) {
    330334      int index = _iim[i];
    331335      _iim[i] = POST_HEAP;
    332336      remove(index);
    333       relocate_last(index);
     337      relocateLast(index);
    334338   }
    335339
    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.
     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.
    341345    Prio operator[](const Item &i) const {
    342346      int idx = _iim[i];
    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.
     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.
    352356    /// \param i The item.
    353357    /// \param p The priority.
     358    /// \pre \e i must be in the heap.
     359    /// \warning This method may throw an \c UnderFlowPriorityException.
    354360    void set(const Item &i, const Prio &p) {
    355361      int idx = _iim[i];
     
    357363        push(i, p);
    358364      }
    359       else if( p >= data[idx].prio ) {
    360         data[idx].prio = p;
    361         bubble_up(idx);
     365      else if( p >= _data[idx].prio ) {
     366        _data[idx].prio = p;
     367        bubbleUp(idx);
    362368      } else {
    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.
     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.
    374377    /// \param i The item.
    375378    /// \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.
    376381    void decrease(const Item &i, const Prio &p) {
    377382      int idx = _iim[i];
    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
     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.
    386390    /// \param i The item.
    387391    /// \param p The priority.
     392    /// \pre \e i must be stored in the heap with priority at most \e p.
    388393    void increase(const Item &i, const Prio &p) {
    389394      int idx = _iim[i];
    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.
     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.
    401406    /// \param i The item.
    402407    State state(const Item &i) const {
     
    406411    }
    407412
    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.
     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.
    413418    /// \param i The item.
    414419    /// \param st The state. It should not be \c IN_HEAP.
  • scripts/chg-len.py

    r422 r733  
    11#! /usr/bin/env python
     2#
     3# This file is a part of LEMON, a generic C++ optimization library.
     4#
     5# Copyright (C) 2003-2009
     6# Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7# (Egervary Research Group on Combinatorial Optimization, EGRES).
     8#
     9# Permission to use, modify and distribute this software is granted
     10# provided that this copyright notice appears in all copies. For
     11# precise terms see the accompanying LICENSE file.
     12#
     13# This software is provided "AS IS" with no warranty of any kind,
     14# express or implied, and with no claim as to its suitability for any
     15# purpose.
    216
    317import sys
  • scripts/mk-release.sh

    r564 r733  
    11#!/bin/bash
     2#
     3# This file is a part of LEMON, a generic C++ optimization library.
     4#
     5# Copyright (C) 2003-2009
     6# Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7# (Egervary Research Group on Combinatorial Optimization, EGRES).
     8#
     9# Permission to use, modify and distribute this software is granted
     10# provided that this copyright notice appears in all copies. For
     11# precise terms see the accompanying LICENSE file.
     12#
     13# This software is provided "AS IS" with no warranty of any kind,
     14# express or implied, and with no claim as to its suitability for any
     15# purpose.
    216
    317set -e
  • scripts/unify-sources.sh

    r655 r733  
    11#!/bin/bash
     2#
     3# This file is a part of LEMON, a generic C++ optimization library.
     4#
     5# Copyright (C) 2003-2009
     6# Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7# (Egervary Research Group on Combinatorial Optimization, EGRES).
     8#
     9# Permission to use, modify and distribute this software is granted
     10# provided that this copyright notice appears in all copies. For
     11# precise terms see the accompanying LICENSE file.
     12#
     13# This software is provided "AS IS" with no warranty of any kind,
     14# express or implied, and with no claim as to its suitability for any
     15# purpose.
    216
    317YEAR=`date +%Y`
  • test/CMakeLists.txt

    r679 r698  
    1010SET(TESTS
    1111  adaptors_test
     12  bellman_ford_test
    1213  bfs_test
    1314  circulation_test
  • test/Makefile.am

    r649 r698  
    88check_PROGRAMS += \
    99        test/adaptors_test \
     10        test/bellman_ford_test \
    1011        test/bfs_test \
    1112        test/circulation_test \
     
    5354
    5455test_adaptors_test_SOURCES = test/adaptors_test.cc
     56test_bellman_ford_test_SOURCES = test/bellman_ford_test.cc
    5557test_bfs_test_SOURCES = test/bfs_test.cc
    5658test_circulation_test_SOURCES = test/circulation_test.cc
  • test/circulation_test.cc

    r611 r689  
    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);
    9095
    9196  circ_test.init();
  • test/heap_test.cc

    r681 r702  
    2626
    2727#include <lemon/smart_graph.h>
    28 
    2928#include <lemon/lgf_reader.h>
    3029#include <lemon/dijkstra.h>
     
    3231
    3332#include <lemon/bin_heap.h>
     33#include <lemon/fourary_heap.h>
     34#include <lemon/kary_heap.h>
    3435#include <lemon/fib_heap.h>
     36#include <lemon/pairing_heap.h>
    3537#include <lemon/radix_heap.h>
     38#include <lemon/binom_heap.h>
    3639#include <lemon/bucket_heap.h>
    3740
     
    9093void heapSortTest() {
    9194  RangeMap<int> map(test_len, -1);
    92 
    9395  Heap heap(map);
    9496
    9597  std::vector<int> v(test_len);
    96 
    9798  for (int i = 0; i < test_len; ++i) {
    9899    v[i] = test_seq[i];
     
    101102  std::sort(v.begin(), v.end());
    102103  for (int i = 0; i < test_len; ++i) {
    103     check(v[i] == heap.prio() ,"Wrong order in heap sort.");
     104    check(v[i] == heap.prio(), "Wrong order in heap sort.");
    104105    heap.pop();
    105106  }
     
    113114
    114115  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 
    132130
    133131template <typename Heap>
     
    145143    if (dijkstra.reached(s)) {
    146144      check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
    147              "Error in a shortest path tree!");
     145             "Error in shortest path tree.");
    148146    }
    149147  }
     
    154152      Node s = digraph.source(a);
    155153      check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
    156              "Error in a shortest path tree!");
     154             "Error in shortest path tree.");
    157155    }
    158156  }
     
    176174    run();
    177175
     176  // BinHeap
    178177  {
    179178    typedef BinHeap<Prio, ItemIntMap> IntHeap;
     
    187186  }
    188187
     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
    189213  {
    190214    typedef FibHeap<Prio, ItemIntMap> IntHeap;
     
    198222  }
    199223
     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
    200237  {
    201238    typedef RadixHeap<ItemIntMap> IntHeap;
     
    209246  }
    210247
     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
    211261  {
    212262    typedef BucketHeap<ItemIntMap> IntHeap;
     
    218268    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    219269    dijkstraHeapTest<NodeHeap>(digraph, length, source);
    220   }
    221 
     270
     271    typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap;
     272    heapSortTest<SimpleIntHeap>();
     273  }
    222274
    223275  return 0;
  • test/maps_test.cc

    r684 r726  
    2424#include <lemon/maps.h>
    2525#include <lemon/list_graph.h>
     26#include <lemon/smart_graph.h>
     27#include <lemon/adaptors.h>
     28#include <lemon/dfs.h>
    2629
    2730#include "test_tools.h"
     
    6164typedef ReadWriteMap<A, bool> BoolWriteMap;
    6265typedef ReferenceMap<A, bool, bool&, const bool&> BoolRefMap;
     66
     67template<typename Map1, typename Map2, typename ItemIt>
     68void compareMap(const Map1& map1, const Map2& map2, ItemIt it) {
     69  for (; it != INVALID; ++it)
     70    check(map1[it] == map2[it], "The maps are not equal");
     71}
    6372
    6473int main()
     
    330339  {
    331340    typedef std::vector<int> vec;
     341    checkConcept<WriteMap<int, bool>, LoggerBoolMap<vec::iterator> >();
     342    checkConcept<WriteMap<int, bool>,
     343                 LoggerBoolMap<std::back_insert_iterator<vec> > >();
     344
    332345    vec v1;
    333346    vec v2(10);
     
    349362          it != map2.end(); ++it )
    350363      check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");
     364   
     365    typedef ListDigraph Graph;
     366    DIGRAPH_TYPEDEFS(Graph);
     367    Graph gr;
     368
     369    Node n0 = gr.addNode();
     370    Node n1 = gr.addNode();
     371    Node n2 = gr.addNode();
     372    Node n3 = gr.addNode();
     373   
     374    gr.addArc(n3, n0);
     375    gr.addArc(n3, n2);
     376    gr.addArc(n0, n2);
     377    gr.addArc(n2, n1);
     378    gr.addArc(n0, n1);
     379   
     380    {
     381      std::vector<Node> v;
     382      dfs(gr).processedMap(loggerBoolMap(std::back_inserter(v))).run();
     383
     384      check(v.size()==4 && v[0]==n1 && v[1]==n2 && v[2]==n0 && v[3]==n3,
     385            "Something is wrong with LoggerBoolMap");
     386    }
     387    {
     388      std::vector<Node> v(countNodes(gr));
     389      dfs(gr).processedMap(loggerBoolMap(v.begin())).run();
     390     
     391      check(v.size()==4 && v[0]==n1 && v[1]==n2 && v[2]==n0 && v[3]==n3,
     392            "Something is wrong with LoggerBoolMap");
     393    }
     394  }
     395 
     396  // IdMap, RangeIdMap
     397  {
     398    typedef ListDigraph Graph;
     399    DIGRAPH_TYPEDEFS(Graph);
     400
     401    checkConcept<ReadMap<Node, int>, IdMap<Graph, Node> >();
     402    checkConcept<ReadMap<Arc, int>, IdMap<Graph, Arc> >();
     403    checkConcept<ReadMap<Node, int>, RangeIdMap<Graph, Node> >();
     404    checkConcept<ReadMap<Arc, int>, RangeIdMap<Graph, Arc> >();
     405   
     406    Graph gr;
     407    IdMap<Graph, Node> nmap(gr);
     408    IdMap<Graph, Arc> amap(gr);
     409    RangeIdMap<Graph, Node> nrmap(gr);
     410    RangeIdMap<Graph, Arc> armap(gr);
     411   
     412    Node n0 = gr.addNode();
     413    Node n1 = gr.addNode();
     414    Node n2 = gr.addNode();
     415   
     416    Arc a0 = gr.addArc(n0, n1);
     417    Arc a1 = gr.addArc(n0, n2);
     418    Arc a2 = gr.addArc(n2, n1);
     419    Arc a3 = gr.addArc(n2, n0);
     420