COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changes in / [714:98a30824fe36:715:ece80147fb08] in lemon-main


Ignore:
Files:
6 added
19 edited

Legend:

Unmodified
Added
Removed

  • doc/groups.dox

    r714 r715  
    239239any kind of path structure.
    240240
    241 \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.
    242271*/
    243272

  • lemon/Makefile.am

    r681 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 \
    … …  
    9397        lemon/lp_base.h \
    9498        lemon/lp_skeleton.h \
    95         lemon/list_graph.h \
    9699        lemon/maps.h \
    97100        lemon/matching.h \
    … …  
    100103        lemon/nauty_reader.h \
    101104        lemon/network_simplex.h \
     105        lemon/pairing_heap.h \
    102106        lemon/path.h \
    103107        lemon/preflow.h \

  • 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/edge_set_extender.h

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

  • lemon/bits/graph_extender.h

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

  • 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

    r713 r715  
    458458    }
    459459
    460     /// \brief Sets the tolerance used by algorithm.
    461     ///
    462     /// Sets the tolerance used by algorithm.
    463     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) {
    464465      _tol = tolerance;
    465466      return *this;
    … …  
    468469    /// \brief Returns a const reference to the tolerance.
    469470    ///
    470     /// Returns a const reference to the tolerance.
     471    /// Returns a const reference to the tolerance object used by
     472    /// the algorithm.
    471473    const Tolerance& tolerance() const {
    472       return tolerance;
     474      return _tol;
    473475    }
    474476

  • 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/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/maps.h

    r617 r695  
    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 {
    … …  
    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
    … …  
    19031902
    19041903  /// This class provides simple invertable graph maps.
    1905   /// It wraps an arbitrary \ref concepts::ReadWriteMap "ReadWriteMap"
    1906   /// and if a key is set to a new value then store it
    1907   /// in the inverse map.
    1908   ///
     1904  /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
     1905  /// and if a key is set to a new value, then stores it in the inverse map.
    19091906  /// The values of the map can be accessed
    19101907  /// with stl compatible forward iterator.
     1908  ///
     1909  /// This type is not reference map, so it cannot be modified with
     1910  /// the subscript operator.
    19111911  ///
    19121912  /// \tparam GR The graph type.
    … …  
    19241924      template Map<V>::Type Map;
    19251925
    1926     typedef std::map<V, K> Container;
     1926    typedef std::multimap<V, K> Container;
    19271927    Container _inv_map;
    19281928
    … …  
    19491949    /// iterator on the values of the map. The values can
    19501950    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
     1951    /// They are considered with multiplicity, so each value is
     1952    /// traversed for each item it is assigned to.
    19511953    class ValueIterator
    19521954      : public std::iterator<std::forward_iterator_tag, Value> {
    … …  
    20012003    void set(const Key& key, const Value& val) {
    20022004      Value oldval = Map::operator[](key);
    2003       typename Container::iterator it = _inv_map.find(oldval);
    2004       if (it != _inv_map.end() && it->second == key) {
    2005         _inv_map.erase(it);
    2006       }
    2007       _inv_map.insert(make_pair(val, key));
     2005      typename Container::iterator it;
     2006      for (it = _inv_map.equal_range(oldval).first;
     2007           it != _inv_map.equal_range(oldval).second; ++it) {
     2008        if (it->second == key) {
     2009          _inv_map.erase(it);
     2010          break;
     2011        }
     2012      }
     2013      _inv_map.insert(std::make_pair(val, key));
    20082014      Map::set(key, val);
    20092015    }
    … …  
    20172023    }
    20182024
    2019     /// \brief Gives back the item by its value.
    2020     ///
    2021     /// Gives back the item by its value.
    2022     Key operator()(const Value& key) const {
    2023       typename Container::const_iterator it = _inv_map.find(key);
     2025    /// \brief Gives back an item by its value.
     2026    ///
     2027    /// This function gives back an item that is assigned to
     2028    /// the given value or \c INVALID if no such item exists.
     2029    /// If there are more items with the same associated value,
     2030    /// only one of them is returned.
     2031    Key operator()(const Value& val) const {
     2032      typename Container::const_iterator it = _inv_map.find(val);
    20242033      return it != _inv_map.end() ? it->second : INVALID;
    20252034    }
    … …  
    20332042    virtual void erase(const Key& key) {
    20342043      Value val = Map::operator[](key);
    2035       typename Container::iterator it = _inv_map.find(val);
    2036       if (it != _inv_map.end() && it->second == key) {
    2037         _inv_map.erase(it);
     2044      typename Container::iterator it;
     2045      for (it = _inv_map.equal_range(val).first;
     2046           it != _inv_map.equal_range(val).second; ++it) {
     2047        if (it->second == key) {
     2048          _inv_map.erase(it);
     2049          break;
     2050        }
    20382051      }
    20392052      Map::erase(key);
    … …  
    20472060      for (int i = 0; i < int(keys.size()); ++i) {
    20482061        Value val = Map::operator[](keys[i]);
    2049         typename Container::iterator it = _inv_map.find(val);
    2050         if (it != _inv_map.end() && it->second == keys[i]) {
    2051           _inv_map.erase(it);
     2062        typename Container::iterator it;
     2063        for (it = _inv_map.equal_range(val).first;
     2064             it != _inv_map.equal_range(val).second; ++it) {
     2065          if (it->second == keys[i]) {
     2066            _inv_map.erase(it);
     2067            break;
     2068          }
    20522069        }
    20532070      }
    … …  
    20852102      /// \brief Subscript operator.
    20862103      ///
    2087       /// Subscript operator. It gives back the item
    2088       /// that was last assigned to the given value.
     2104      /// Subscript operator. It gives back an item
     2105      /// that is assigned to the given value or \c INVALID
     2106      /// if no such item exists.
    20892107      Value operator[](const Key& key) const {
    20902108        return _inverted(key);
    … …  
    22552273
    22562274    /// \brief Gives back the item belonging to a \e RangeId
    2257     /// 
     2275    ///
    22582276    /// Gives back the item belonging to a \e RangeId.
    22592277    Item operator()(int id) const {
    … …  
    23122330  };
    23132331
     2332  /// \brief Dynamic iterable \c bool map.
     2333  ///
     2334  /// This class provides a special graph map type which can store a
     2335  /// \c bool value for graph items (\c Node, \c Arc or \c Edge).
     2336  /// For both \c true and \c false values it is possible to iterate on
     2337  /// the keys.
     2338  ///
     2339  /// This type is a reference map, so it can be modified with the
     2340  /// subscript operator.
     2341  ///
     2342  /// \tparam GR The graph type.
     2343  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
     2344  /// \c GR::Edge).
     2345  ///
     2346  /// \see IterableIntMap, IterableValueMap
     2347  /// \see CrossRefMap
     2348  template <typename GR, typename K>
     2349  class IterableBoolMap
     2350    : protected ItemSetTraits<GR, K>::template Map<int>::Type {
     2351  private:
     2352    typedef GR Graph;
     2353
     2354    typedef typename ItemSetTraits<GR, K>::ItemIt KeyIt;
     2355    typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Parent;
     2356
     2357    std::vector<K> _array;
     2358    int _sep;
     2359
     2360  public:
     2361
     2362    /// Indicates that the map is reference map.
     2363    typedef True ReferenceMapTag;
     2364
     2365    /// The key type
     2366    typedef K Key;
     2367    /// The value type
     2368    typedef bool Value;
     2369    /// The const reference type.
     2370    typedef const Value& ConstReference;
     2371
     2372  private:
     2373
     2374    int position(const Key& key) const {
     2375      return Parent::operator[](key);
     2376    }
     2377
     2378  public:
     2379
     2380    /// \brief Reference to the value of the map.
     2381    ///
     2382    /// This class is similar to the \c bool type. It can be converted to
     2383    /// \c bool and it provides the same operators.
     2384    class Reference {
     2385      friend class IterableBoolMap;
     2386    private:
     2387      Reference(IterableBoolMap& map, const Key& key)
     2388        : _key(key), _map(map) {}
     2389    public:
     2390
     2391      Reference& operator=(const Reference& value) {
     2392        _map.set(_key, static_cast<bool>(value));
     2393         return *this;
     2394      }
     2395
     2396      operator bool() const {
     2397        return static_cast<const IterableBoolMap&>(_map)[_key];
     2398      }
     2399
     2400      Reference& operator=(bool value) {
     2401        _map.set(_key, value);
     2402        return *this;
     2403      }
     2404      Reference& operator&=(bool value) {
     2405        _map.set(_key, _map[_key] & value);
     2406        return *this;
     2407      }
     2408      Reference& operator|=(bool value) {
     2409        _map.set(_key, _map[_key] | value);
     2410        return *this;
     2411      }
     2412      Reference& operator^=(bool value) {
     2413        _map.set(_key, _map[_key] ^ value);
     2414        return *this;
     2415      }
     2416    private:
     2417      Key _key;
     2418      IterableBoolMap& _map;
     2419    };
     2420
     2421    /// \brief Constructor of the map with a default value.
     2422    ///
     2423    /// Constructor of the map with a default value.
     2424    explicit IterableBoolMap(const Graph& graph, bool def = false)
     2425      : Parent(graph) {
     2426      typename Parent::Notifier* nf = Parent::notifier();
     2427      Key it;
     2428      for (nf->first(it); it != INVALID; nf->next(it)) {
     2429        Parent::set(it, _array.size());
     2430        _array.push_back(it);
     2431      }
     2432      _sep = (def ? _array.size() : 0);
     2433    }
     2434
     2435    /// \brief Const subscript operator of the map.
     2436    ///
     2437    /// Const subscript operator of the map.
     2438    bool operator[](const Key& key) const {
     2439      return position(key) < _sep;
     2440    }
     2441
     2442    /// \brief Subscript operator of the map.
     2443    ///
     2444    /// Subscript operator of the map.
     2445    Reference operator[](const Key& key) {
     2446      return Reference(*this, key);
     2447    }
     2448
     2449    /// \brief Set operation of the map.
     2450    ///
     2451    /// Set operation of the map.
     2452    void set(const Key& key, bool value) {
     2453      int pos = position(key);
     2454      if (value) {
     2455        if (pos < _sep) return;
     2456        Key tmp = _array[_sep];
     2457        _array[_sep] = key;
     2458        Parent::set(key, _sep);
     2459        _array[pos] = tmp;
     2460        Parent::set(tmp, pos);
     2461        ++_sep;
     2462      } else {
     2463        if (pos >= _sep) return;
     2464        --_sep;
     2465        Key tmp = _array[_sep];
     2466        _array[_sep] = key;
     2467        Parent::set(key, _sep);
     2468        _array[pos] = tmp;
     2469        Parent::set(tmp, pos);
     2470      }
     2471    }
     2472
     2473    /// \brief Set all items.
     2474    ///
     2475    /// Set all items in the map.
     2476    /// \note Constant time operation.
     2477    void setAll(bool value) {
     2478      _sep = (value ? _array.size() : 0);
     2479    }
     2480
     2481    /// \brief Returns the number of the keys mapped to \c true.
     2482    ///
     2483    /// Returns the number of the keys mapped to \c true.
     2484    int trueNum() const {
     2485      return _sep;
     2486    }
     2487
     2488    /// \brief Returns the number of the keys mapped to \c false.
     2489    ///
     2490    /// Returns the number of the keys mapped to \c false.
     2491    int falseNum() const {
     2492      return _array.size() - _sep;
     2493    }
     2494
     2495    /// \brief Iterator for the keys mapped to \c true.
     2496    ///
     2497    /// Iterator for the keys mapped to \c true. It works
     2498    /// like a graph item iterator, it can be converted to
     2499    /// the key type of the map, incremented with \c ++ operator, and
     2500    /// if the iterator leaves the last valid key, it will be equal to
     2501    /// \c INVALID.
     2502    class TrueIt : public Key {
     2503    public:
     2504      typedef Key Parent;
     2505
     2506      /// \brief Creates an iterator.
     2507      ///
     2508      /// Creates an iterator. It iterates on the
     2509      /// keys mapped to \c true.
     2510      /// \param map The IterableBoolMap.
     2511      explicit TrueIt(const IterableBoolMap& map)
     2512        : Parent(map._sep > 0 ? map._array[map._sep - 1] : INVALID),
     2513          _map(&map) {}
     2514
     2515      /// \brief Invalid constructor \& conversion.
     2516      ///
     2517      /// This constructor initializes the iterator to be invalid.
     2518      /// \sa Invalid for more details.
     2519      TrueIt(Invalid) : Parent(INVALID), _map(0) {}
     2520
     2521      /// \brief Increment operator.
     2522      ///
     2523      /// Increment operator.
     2524      TrueIt& operator++() {
     2525        int pos = _map->position(*this);
     2526        Parent::operator=(pos > 0 ? _map->_array[pos - 1] : INVALID);
     2527        return *this;
     2528      }
     2529
     2530    private:
     2531      const IterableBoolMap* _map;
     2532    };
     2533
     2534    /// \brief Iterator for the keys mapped to \c false.
     2535    ///
     2536    /// Iterator for the keys mapped to \c false. It works
     2537    /// like a graph item iterator, it can be converted to
     2538    /// the key type of the map, incremented with \c ++ operator, and
     2539    /// if the iterator leaves the last valid key, it will be equal to
     2540    /// \c INVALID.
     2541    class FalseIt : public Key {
     2542    public:
     2543      typedef Key Parent;
     2544
     2545      /// \brief Creates an iterator.
     2546      ///
     2547      /// Creates an iterator. It iterates on the
     2548      /// keys mapped to \c false.
     2549      /// \param map The IterableBoolMap.
     2550      explicit FalseIt(const IterableBoolMap& map)
     2551        : Parent(map._sep < int(map._array.size()) ?
     2552                 map._array.back() : INVALID), _map(&map) {}
     2553
     2554      /// \brief Invalid constructor \& conversion.
     2555      ///
     2556      /// This constructor initializes the iterator to be invalid.
     2557      /// \sa Invalid for more details.
     2558      FalseIt(Invalid) : Parent(INVALID), _map(0) {}
     2559
     2560      /// \brief Increment operator.
     2561      ///
     2562      /// Increment operator.
     2563      FalseIt& operator++() {
     2564        int pos = _map->position(*this);
     2565        Parent::operator=(pos > _map->_sep ? _map->_array[pos - 1] : INVALID);
     2566        return *this;
     2567      }
     2568
     2569    private:
     2570      const IterableBoolMap* _map;
     2571    };
     2572
     2573    /// \brief Iterator for the keys mapped to a given value.
     2574    ///
     2575    /// Iterator for the keys mapped to a given value. It works
     2576    /// like a graph item iterator, it can be converted to
     2577    /// the key type of the map, incremented with \c ++ operator, and
     2578    /// if the iterator leaves the last valid key, it will be equal to
     2579    /// \c INVALID.
     2580    class ItemIt : public Key {
     2581    public:
     2582      typedef Key Parent;
     2583
     2584      /// \brief Creates an iterator with a value.
     2585      ///
     2586      /// Creates an iterator with a value. It iterates on the
     2587      /// keys mapped to the given value.
     2588      /// \param map The IterableBoolMap.
     2589      /// \param value The value.
     2590      ItemIt(const IterableBoolMap& map, bool value)
     2591        : Parent(value ?
     2592                 (map._sep > 0 ?
     2593                  map._array[map._sep - 1] : INVALID) :
     2594                 (map._sep < int(map._array.size()) ?
     2595                  map._array.back() : INVALID)), _map(&map) {}
     2596
     2597      /// \brief Invalid constructor \& conversion.
     2598      ///
     2599      /// This constructor initializes the iterator to be invalid.
     2600      /// \sa Invalid for more details.
     2601      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
     2602
     2603      /// \brief Increment operator.
     2604      ///
     2605      /// Increment operator.
     2606      ItemIt& operator++() {
     2607        int pos = _map->position(*this);
     2608        int _sep = pos >= _map->_sep ? _map->_sep : 0;
     2609        Parent::operator=(pos > _sep ? _map->_array[pos - 1] : INVALID);
     2610        return *this;
     2611      }
     2612
     2613    private:
     2614      const IterableBoolMap* _map;
     2615    };
     2616
     2617  protected:
     2618
     2619    virtual void add(const Key& key) {
     2620      Parent::add(key);
     2621      Parent::set(key, _array.size());
     2622      _array.push_back(key);
     2623    }
     2624
     2625    virtual void add(const std::vector<Key>& keys) {
     2626      Parent::add(keys);
     2627      for (int i = 0; i < int(keys.size()); ++i) {
     2628        Parent::set(keys[i], _array.size());
     2629        _array.push_back(keys[i]);
     2630      }
     2631    }
     2632
     2633    virtual void erase(const Key& key) {
     2634      int pos = position(key);
     2635      if (pos < _sep) {
     2636        --_sep;
     2637        Parent::set(_array[_sep], pos);
     2638        _array[pos] = _array[_sep];
     2639        Parent::set(_array.back(), _sep);
     2640        _array[_sep] = _array.back();
     2641        _array.pop_back();
     2642      } else {
     2643        Parent::set(_array.back(), pos);
     2644        _array[pos] = _array.back();
     2645        _array.pop_back();
     2646      }
     2647      Parent::erase(key);
     2648    }
     2649
     2650    virtual void erase(const std::vector<Key>& keys) {
     2651      for (int i = 0; i < int(keys.size()); ++i) {
     2652        int pos = position(keys[i]);
     2653        if (pos < _sep) {
     2654          --_sep;
     2655          Parent::set(_array[_sep], pos);
     2656          _array[pos] = _array[_sep];
     2657          Parent::set(_array.back(), _sep);
     2658          _array[_sep] = _array.back();
     2659          _array.pop_back();
     2660        } else {
     2661          Parent::set(_array.back(), pos);
     2662          _array[pos] = _array.back();
     2663          _array.pop_back();
     2664        }
     2665      }
     2666      Parent::erase(keys);
     2667    }
     2668
     2669    virtual void build() {
     2670      Parent::build();
     2671      typename Parent::Notifier* nf = Parent::notifier();
     2672      Key it;
     2673      for (nf->first(it); it != INVALID; nf->next(it)) {
     2674        Parent::set(it, _array.size());
     2675        _array.push_back(it);
     2676      }
     2677      _sep = 0;
     2678    }
     2679
     2680    virtual void clear() {
     2681      _array.clear();
     2682      _sep = 0;
     2683      Parent::clear();
     2684    }
     2685
     2686  };
     2687
     2688
     2689  namespace _maps_bits {
     2690    template <typename Item>
     2691    struct IterableIntMapNode {
     2692      IterableIntMapNode() : value(-1) {}
     2693      IterableIntMapNode(int _value) : value(_value) {}
     2694      Item prev, next;
     2695      int value;
     2696    };
     2697  }
     2698
     2699  /// \brief Dynamic iterable integer map.
     2700  ///
     2701  /// This class provides a special graph map type which can store an
     2702  /// integer value for graph items (\c Node, \c Arc or \c Edge).
     2703  /// For each non-negative value it is possible to iterate on the keys
     2704  /// mapped to the value.
     2705  ///
     2706  /// This type is a reference map, so it can be modified with the
     2707  /// subscript operator.
     2708  ///
     2709  /// \note The size of the data structure depends on the largest
     2710  /// value in the map.
     2711  ///
     2712  /// \tparam GR The graph type.
     2713  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
     2714  /// \c GR::Edge).
     2715  ///
     2716  /// \see IterableBoolMap, IterableValueMap
     2717  /// \see CrossRefMap
     2718  template <typename GR, typename K>
     2719  class IterableIntMap
     2720    : protected ItemSetTraits<GR, K>::
     2721        template Map<_maps_bits::IterableIntMapNode<K> >::Type {
     2722  public:
     2723    typedef typename ItemSetTraits<GR, K>::
     2724      template Map<_maps_bits::IterableIntMapNode<K> >::Type Parent;
     2725
     2726    /// The key type
     2727    typedef K Key;
     2728    /// The value type
     2729    typedef int Value;
     2730    /// The graph type
     2731    typedef GR Graph;
     2732
     2733    /// \brief Constructor of the map.
     2734    ///
     2735    /// Constructor of the map. It sets all values to -1.
     2736    explicit IterableIntMap(const Graph& graph)
     2737      : Parent(graph) {}
     2738
     2739    /// \brief Constructor of the map with a given value.
     2740    ///
     2741    /// Constructor of the map with a given value.
     2742    explicit IterableIntMap(const Graph& graph, int value)
     2743      : Parent(graph, _maps_bits::IterableIntMapNode<K>(value)) {
     2744      if (value >= 0) {
     2745        for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
     2746          lace(it);
     2747        }
     2748      }
     2749    }
     2750
     2751  private:
     2752
     2753    void unlace(const Key& key) {
     2754      typename Parent::Value& node = Parent::operator[](key);
     2755      if (node.value < 0) return;
     2756      if (node.prev != INVALID) {
     2757        Parent::operator[](node.prev).next = node.next;
     2758      } else {
     2759        _first[node.value] = node.next;
     2760      }
     2761      if (node.next != INVALID) {
     2762        Parent::operator[](node.next).prev = node.prev;
     2763      }
     2764      while (!_first.empty() && _first.back() == INVALID) {
     2765        _first.pop_back();
     2766      }
     2767    }
     2768
     2769    void lace(const Key& key) {
     2770      typename Parent::Value& node = Parent::operator[](key);
     2771      if (node.value < 0) return;
     2772      if (node.value >= int(_first.size())) {
     2773        _first.resize(node.value + 1, INVALID);
     2774      }
     2775      node.prev = INVALID;
     2776      node.next = _first[node.value];
     2777      if (node.next != INVALID) {
     2778        Parent::operator[](node.next).prev = key;
     2779      }
     2780      _first[node.value] = key;
     2781    }
     2782
     2783  public:
     2784
     2785    /// Indicates that the map is reference map.
     2786    typedef True ReferenceMapTag;
     2787
     2788    /// \brief Reference to the value of the map.
     2789    ///
     2790    /// This class is similar to the \c int type. It can
     2791    /// be converted to \c int and it has the same operators.
     2792    class Reference {
     2793      friend class IterableIntMap;
     2794    private:
     2795      Reference(IterableIntMap& map, const Key& key)
     2796        : _key(key), _map(map) {}
     2797    public:
     2798
     2799      Reference& operator=(const Reference& value) {
     2800        _map.set(_key, static_cast<const int&>(value));
     2801         return *this;
     2802      }
     2803
     2804      operator const int&() const {
     2805        return static_cast<const IterableIntMap&>(_map)[_key];
     2806      }
     2807
     2808      Reference& operator=(int value) {
     2809        _map.set(_key, value);
     2810        return *this;
     2811      }
     2812      Reference& operator++() {
     2813        _map.set(_key, _map[_key] + 1);
     2814        return *this;
     2815      }
     2816      int operator++(int) {
     2817        int value = _map[_key];
     2818        _map.set(_key, value + 1);
     2819        return value;
     2820      }
     2821      Reference& operator--() {
     2822        _map.set(_key, _map[_key] - 1);
     2823        return *this;
     2824      }
     2825      int operator--(int) {
     2826        int value = _map[_key];
     2827        _map.set(_key, value - 1);
     2828        return value;
     2829      }
     2830      Reference& operator+=(int value) {
     2831        _map.set(_key, _map[_key] + value);
     2832        return *this;
     2833      }
     2834      Reference& operator-=(int value) {
     2835        _map.set(_key, _map[_key] - value);
     2836        return *this;
     2837      }
     2838      Reference& operator*=(int value) {
     2839        _map.set(_key, _map[_key] * value);
     2840        return *this;
     2841      }
     2842      Reference& operator/=(int value) {
     2843        _map.set(_key, _map[_key] / value);
     2844        return *this;
     2845      }
     2846      Reference& operator%=(int value) {
     2847        _map.set(_key, _map[_key] % value);
     2848        return *this;
     2849      }
     2850      Reference& operator&=(int value) {
     2851        _map.set(_key, _map[_key] & value);
     2852        return *this;
     2853      }
     2854      Reference& operator|=(int value) {
     2855        _map.set(_key, _map[_key] | value);
     2856        return *this;
     2857      }
     2858      Reference& operator^=(int value) {
     2859        _map.set(_key, _map[_key] ^ value);
     2860        return *this;
     2861      }
     2862      Reference& operator<<=(int value) {
     2863        _map.set(_key, _map[_key] << value);
     2864        return *this;
     2865      }
     2866      Reference& operator>>=(int value) {
     2867        _map.set(_key, _map[_key] >> value);
     2868        return *this;
     2869      }
     2870
     2871    private:
     2872      Key _key;
     2873      IterableIntMap& _map;
     2874    };
     2875
     2876    /// The const reference type.
     2877    typedef const Value& ConstReference;
     2878
     2879    /// \brief Gives back the maximal value plus one.
     2880    ///
     2881    /// Gives back the maximal value plus one.
     2882    int size() const {
     2883      return _first.size();
     2884    }
     2885
     2886    /// \brief Set operation of the map.
     2887    ///
     2888    /// Set operation of the map.
     2889    void set(const Key& key, const Value& value) {
     2890      unlace(key);
     2891      Parent::operator[](key).value = value;
     2892      lace(key);
     2893    }
     2894
     2895    /// \brief Const subscript operator of the map.
     2896    ///
     2897    /// Const subscript operator of the map.
     2898    const Value& operator[](const Key& key) const {
     2899      return Parent::operator[](key).value;
     2900    }
     2901
     2902    /// \brief Subscript operator of the map.
     2903    ///
     2904    /// Subscript operator of the map.
     2905    Reference operator[](const Key& key) {
     2906      return Reference(*this, key);
     2907    }
     2908
     2909    /// \brief Iterator for the keys with the same value.
     2910    ///
     2911    /// Iterator for the keys with the same value. It works
     2912    /// like a graph item iterator, it can be converted to
     2913    /// the item type of the map, incremented with \c ++ operator, and
     2914    /// if the iterator leaves the last valid item, it will be equal to
     2915    /// \c INVALID.
     2916    class ItemIt : public Key {
     2917    public:
     2918      typedef Key Parent;
     2919
     2920      /// \brief Invalid constructor \& conversion.
     2921      ///
     2922      /// This constructor initializes the iterator to be invalid.
     2923      /// \sa Invalid for more details.
     2924      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
     2925
     2926      /// \brief Creates an iterator with a value.
     2927      ///
     2928      /// Creates an iterator with a value. It iterates on the
     2929      /// keys mapped to the given value.
     2930      /// \param map The IterableIntMap.
     2931      /// \param value The value.
     2932      ItemIt(const IterableIntMap& map, int value) : _map(&map) {
     2933        if (value < 0 || value >= int(_map->_first.size())) {
     2934          Parent::operator=(INVALID);
     2935        } else {
     2936          Parent::operator=(_map->_first[value]);
     2937        }
     2938      }
     2939
     2940      /// \brief Increment operator.
     2941      ///
     2942      /// Increment operator.
     2943      ItemIt& operator++() {
     2944        Parent::operator=(_map->IterableIntMap::Parent::
     2945                          operator[](static_cast<Parent&>(*this)).next);
     2946        return *this;
     2947      }
     2948
     2949    private:
     2950      const IterableIntMap* _map;
     2951    };
     2952
     2953  protected:
     2954
     2955    virtual void erase(const Key& key) {
     2956      unlace(key);
     2957      Parent::erase(key);
     2958    }
     2959
     2960    virtual void erase(const std::vector<Key>& keys) {
     2961      for (int i = 0; i < int(keys.size()); ++i) {
     2962        unlace(keys[i]);
     2963      }
     2964      Parent::erase(keys);
     2965    }
     2966
     2967    virtual void clear() {
     2968      _first.clear();
     2969      Parent::clear();
     2970    }
     2971
     2972  private:
     2973    std::vector<Key> _first;
     2974  };
     2975
     2976  namespace _maps_bits {
     2977    template <typename Item, typename Value>
     2978    struct IterableValueMapNode {
     2979      IterableValueMapNode(Value _value = Value()) : value(_value) {}
     2980      Item prev, next;
     2981      Value value;
     2982    };
     2983  }
     2984
     2985  /// \brief Dynamic iterable map for comparable values.
     2986  ///
     2987  /// This class provides a special graph map type which can store an
     2988  /// comparable value for graph items (\c Node, \c Arc or \c Edge).
     2989  /// For each value it is possible to iterate on the keys mapped to
     2990  /// the value.
     2991  ///
     2992  /// The map stores for each value a linked list with
     2993  /// the items which mapped to the value, and the values are stored
     2994  /// in balanced binary tree. The values of the map can be accessed
     2995  /// with stl compatible forward iterator.
     2996  ///
     2997  /// This type is not reference map, so it cannot be modified with
     2998  /// the subscript operator.
     2999  ///
     3000  /// \tparam GR The graph type.
     3001  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
     3002  /// \c GR::Edge).
     3003  /// \tparam V The value type of the map. It can be any comparable
     3004  /// value type.
     3005  ///
     3006  /// \see IterableBoolMap, IterableIntMap
     3007  /// \see CrossRefMap
     3008  template <typename GR, typename K, typename V>
     3009  class IterableValueMap
     3010    : protected ItemSetTraits<GR, K>::
     3011        template Map<_maps_bits::IterableValueMapNode<K, V> >::Type {
     3012  public:
     3013    typedef typename ItemSetTraits<GR, K>::
     3014      template Map<_maps_bits::IterableValueMapNode<K, V> >::Type Parent;
     3015
     3016    /// The key type
     3017    typedef K Key;
     3018    /// The value type
     3019    typedef V Value;
     3020    /// The graph type
     3021    typedef GR Graph;
     3022
     3023  public:
     3024
     3025    /// \brief Constructor of the map with a given value.
     3026    ///
     3027    /// Constructor of the map with a given value.
     3028    explicit IterableValueMap(const Graph& graph,
     3029                              const Value& value = Value())
     3030      : Parent(graph, _maps_bits::IterableValueMapNode<K, V>(value)) {
     3031      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
     3032        lace(it);
     3033      }
     3034    }
     3035
     3036  protected:
     3037
     3038    void unlace(const Key& key) {
     3039      typename Parent::Value& node = Parent::operator[](key);
     3040      if (node.prev != INVALID) {
     3041        Parent::operator[](node.prev).next = node.next;
     3042      } else {
     3043        if (node.next != INVALID) {
     3044          _first[node.value] = node.next;
     3045        } else {
     3046          _first.erase(node.value);
     3047        }
     3048      }
     3049      if (node.next != INVALID) {
     3050        Parent::operator[](node.next).prev = node.prev;
     3051      }
     3052    }
     3053
     3054    void lace(const Key& key) {
     3055      typename Parent::Value& node = Parent::operator[](key);
     3056      typename std::map<Value, Key>::iterator it = _first.find(node.value);
     3057      if (it == _first.end()) {
     3058        node.prev = node.next = INVALID;
     3059        _first.insert(std::make_pair(node.value, key));
     3060      } else {
     3061        node.prev = INVALID;
     3062        node.next = it->second;
     3063        if (node.next != INVALID) {
     3064          Parent::operator[](node.next).prev = key;
     3065        }
     3066        it->second = key;
     3067      }
     3068    }
     3069
     3070  public:
     3071
     3072    /// \brief Forward iterator for values.
     3073    ///
     3074    /// This iterator is an stl compatible forward
     3075    /// iterator on the values of the map. The values can
     3076    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
     3077    class ValueIterator
     3078      : public std::iterator<std::forward_iterator_tag, Value> {
     3079      friend class IterableValueMap;
     3080    private:
     3081      ValueIterator(typename std::map<Value, Key>::const_iterator _it)
     3082        : it(_it) {}
     3083    public:
     3084
     3085      ValueIterator() {}
     3086
     3087      ValueIterator& operator++() { ++it; return *this; }
     3088      ValueIterator operator++(int) {
     3089        ValueIterator tmp(*this);
     3090        operator++();
     3091        return tmp;
     3092      }
     3093
     3094      const Value& operator*() const { return it->first; }
     3095      const Value* operator->() const { return &(it->first); }
     3096
     3097      bool operator==(ValueIterator jt) const { return it == jt.it; }
     3098      bool operator!=(ValueIterator jt) const { return it != jt.it; }
     3099
     3100    private:
     3101      typename std::map<Value, Key>::const_iterator it;
     3102    };
     3103
     3104    /// \brief Returns an iterator to the first value.
     3105    ///
     3106    /// Returns an stl compatible iterator to the
     3107    /// first value of the map. The values of the
     3108    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
     3109    /// range.
     3110    ValueIterator beginValue() const {
     3111      return ValueIterator(_first.begin());
     3112    }
     3113
     3114    /// \brief Returns an iterator after the last value.
     3115    ///
     3116    /// Returns an stl compatible iterator after the
     3117    /// last value of the map. The values of the
     3118    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
     3119    /// range.
     3120    ValueIterator endValue() const {
     3121      return ValueIterator(_first.end());
     3122    }
     3123
     3124    /// \brief Set operation of the map.
     3125    ///
     3126    /// Set operation of the map.
     3127    void set(const Key& key, const Value& value) {
     3128      unlace(key);
     3129      Parent::operator[](key).value = value;
     3130      lace(key);
     3131    }
     3132
     3133    /// \brief Const subscript operator of the map.
     3134    ///
     3135    /// Const subscript operator of the map.
     3136    const Value& operator[](const Key& key) const {
     3137      return Parent::operator[](key).value;
     3138    }
     3139
     3140    /// \brief Iterator for the keys with the same value.
     3141    ///
     3142    /// Iterator for the keys with the same value. It works
     3143    /// like a graph item iterator, it can be converted to
     3144    /// the item type of the map, incremented with \c ++ operator, and
     3145    /// if the iterator leaves the last valid item, it will be equal to
     3146    /// \c INVALID.
     3147    class ItemIt : public Key {
     3148    public:
     3149      typedef Key Parent;
     3150
     3151      /// \brief Invalid constructor \& conversion.
     3152      ///
     3153      /// This constructor initializes the iterator to be invalid.
     3154      /// \sa Invalid for more details.
     3155      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
     3156
     3157      /// \brief Creates an iterator with a value.
     3158      ///
     3159      /// Creates an iterator with a value. It iterates on the
     3160      /// keys which have the given value.
     3161      /// \param map The IterableValueMap
     3162      /// \param value The value
     3163      ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) {
     3164        typename std::map<Value, Key>::const_iterator it =
     3165          map._first.find(value);
     3166        if (it == map._first.end()) {
     3167          Parent::operator=(INVALID);
     3168        } else {
     3169          Parent::operator=(it->second);
     3170        }
     3171      }
     3172
     3173      /// \brief Increment operator.
     3174      ///
     3175      /// Increment Operator.
     3176      ItemIt& operator++() {
     3177        Parent::operator=(_map->IterableValueMap::Parent::
     3178                          operator[](static_cast<Parent&>(*this)).next);
     3179        return *this;
     3180      }
     3181
     3182
     3183    private:
     3184      const IterableValueMap* _map;
     3185    };
     3186
     3187  protected:
     3188
     3189    virtual void add(const Key& key) {
     3190      Parent::add(key);
     3191      unlace(key);
     3192    }
     3193
     3194    virtual void add(const std::vector<Key>& keys) {
     3195      Parent::add(keys);
     3196      for (int i = 0; i < int(keys.size()); ++i) {
     3197        lace(keys[i]);
     3198      }
     3199    }
     3200
     3201    virtual void erase(const Key& key) {
     3202      unlace(key);
     3203      Parent::erase(key);
     3204    }
     3205
     3206    virtual void erase(const std::vector<Key>& keys) {
     3207      for (int i = 0; i < int(keys.size()); ++i) {
     3208        unlace(keys[i]);
     3209      }
     3210      Parent::erase(keys);
     3211    }
     3212
     3213    virtual void build() {
     3214      Parent::build();
     3215      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
     3216        lace(it);
     3217      }
     3218    }
     3219
     3220    virtual void clear() {
     3221      _first.clear();
     3222      Parent::clear();
     3223    }
     3224
     3225  private:
     3226    std::map<Value, Key> _first;
     3227  };
     3228
    23143229  /// \brief Map of the source nodes of arcs in a digraph.
    23153230  ///
    … …  
    24813396  /// whenever the digraph changes.
    24823397  ///
    2483   /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
     3398  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
    24843399  /// may provide alternative ways to modify the digraph.
    24853400  /// The correct behavior of InDegMap is not guarantied if these additional
    … …  
    24973412
    24983413  public:
    2499    
     3414
    25003415    /// The graph type of InDegMap
    25013416    typedef GR Graph;
    … …  
    26113526  /// whenever the digraph changes.
    26123527  ///
    2613   /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
     3528  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
    26143529  /// may provide alternative ways to modify the digraph.
    26153530  /// The correct behavior of OutDegMap is not guarantied if these additional

  • lemon/preflow.h

    r713 r715  
    105105  /// "flow of maximum value" in a digraph.
    106106  /// The preflow algorithms are the fastest known maximum
    107   /// flow algorithms. The current implementation use a mixture of the
     107  /// flow algorithms. The current implementation uses a mixture of the
    108108  /// \e "highest label" and the \e "bound decrease" heuristics.
    109109  /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
    … …  
    379379    }
    380380
    381     /// \brief Sets the tolerance used by algorithm.
    382     ///
    383     /// Sets the tolerance used by algorithm.
    384     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) {
    385386      _tolerance = tolerance;
    386387      return *this;
    … …  
    389390    /// \brief Returns a const reference to the tolerance.
    390391    ///
    391     /// Returns a const reference to the tolerance.
     392    /// Returns a const reference to the tolerance object used by
     393    /// the algorithm.
    392394    const Tolerance& tolerance() const {
    393       return tolerance;
     395      return _tolerance;
    394396    }
    395397

  • 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.

  • 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

    r477 r695  
    2323#include <lemon/concepts/maps.h>
    2424#include <lemon/maps.h>
     25#include <lemon/smart_graph.h>
    2526
    2627#include "test_tools.h"
    … …  
    350351  }
    351352
     353  // CrossRefMap
     354  {
     355    typedef SmartDigraph Graph;
     356    DIGRAPH_TYPEDEFS(Graph);
     357
     358    checkConcept<ReadWriteMap<Node, int>,
     359                 CrossRefMap<Graph, Node, int> >();
     360   
     361    Graph gr;
     362    typedef CrossRefMap<Graph, Node, char> CRMap;
     363    typedef CRMap::ValueIterator ValueIt;
     364    CRMap map(gr);
     365   
     366    Node n0 = gr.addNode();
     367    Node n1 = gr.addNode();
     368    Node n2 = gr.addNode();
     369   
     370    map.set(n0, 'A');
     371    map.set(n1, 'B');
     372    map.set(n2, 'C');
     373    map.set(n2, 'A');
     374    map.set(n0, 'C');
     375
     376    check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A',
     377          "Wrong CrossRefMap");
     378    check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap");
     379    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");
     380    check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap");
     381
     382    ValueIt it = map.beginValue();
     383    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
     384          it == map.endValue(), "Wrong value iterator");
     385  }
     386 
     387  // Iterable bool map
     388  {
     389    typedef SmartGraph Graph;
     390    typedef SmartGraph::Node Item;
     391
     392    typedef IterableBoolMap<SmartGraph, SmartGraph::Node> Ibm;
     393    checkConcept<ReferenceMap<Item, bool, bool&, const bool&>, Ibm>();
     394
     395    const int num = 10;
     396    Graph g;
     397    std::vector<Item> items;
     398    for (int i = 0; i < num; ++i) {
     399      items.push_back(g.addNode());
     400    }
     401
     402    Ibm map1(g, true);
     403    int n = 0;
     404    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
     405      check(map1[static_cast<Item>(it)], "Wrong TrueIt");
     406      ++n;
     407    }
     408    check(n == num, "Wrong number");
     409
     410    n = 0;
     411    for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {
     412        check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");
     413        ++n;
     414    }
     415    check(n == num, "Wrong number");
     416    check(Ibm::FalseIt(map1) == INVALID, "Wrong FalseIt");
     417    check(Ibm::ItemIt(map1, false) == INVALID, "Wrong ItemIt for false");
     418
     419    map1[items[5]] = true;
     420
     421    n = 0;
     422    for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {
     423        check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");
     424        ++n;
     425    }
     426    check(n == num, "Wrong number");
     427
     428    map1[items[num / 2]] = false;
     429    check(map1[items[num / 2]] == false, "Wrong map value");
     430
     431    n = 0;
     432    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
     433        check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");
     434        ++n;
     435    }
     436    check(n == num - 1, "Wrong number");
     437
     438    n = 0;
     439    for (Ibm::FalseIt it(map1); it != INVALID; ++it) {
     440        check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");
     441        ++n;
     442    }
     443    check(n == 1, "Wrong number");
     444
     445    map1[items[0]] = false;
     446    check(map1[items[0]] == false, "Wrong map value");
     447
     448    map1[items[num - 1]] = false;
     449    check(map1[items[num - 1]] == false, "Wrong map value");
     450
     451    n = 0;
     452    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
     453        check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");
     454        ++n;
     455    }
     456    check(n == num - 3, "Wrong number");
     457    check(map1.trueNum() == num - 3, "Wrong number");
     458
     459    n = 0;
     460    for (Ibm::FalseIt it(map1); it != INVALID; ++it) {
     461        check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");
     462        ++n;
     463    }
     464    check(n == 3, "Wrong number");
     465    check(map1.falseNum() == 3, "Wrong number");
     466  }
     467
     468  // Iterable int map
     469  {
     470    typedef SmartGraph Graph;
     471    typedef SmartGraph::Node Item;
     472    typedef IterableIntMap<SmartGraph, SmartGraph::Node> Iim;
     473
     474    checkConcept<ReferenceMap<Item, int, int&, const int&>, Iim>();
     475
     476    const int num = 10;
     477    Graph g;
     478    std::vector<Item> items;
     479    for (int i = 0; i < num; ++i) {
     480      items.push_back(g.addNode());
     481    }
     482
     483    Iim map1(g);
     484    check(map1.size() == 0, "Wrong size");
     485
     486    for (int i = 0; i < num; ++i) {
     487      map1[items[i]] = i;
     488    }
     489    check(map1.size() == num, "Wrong size");
     490
     491    for (int i = 0; i < num; ++i) {
     492      Iim::ItemIt it(map1, i);
     493      check(static_cast<Item>(it) == items[i], "Wrong value");
     494      ++it;
     495      check(static_cast<Item>(it) == INVALID, "Wrong value");
     496    }
     497
     498    for (int i = 0; i < num; ++i) {
     499      map1[items[i]] = i % 2;
     500    }
     501    check(map1.size() == 2, "Wrong size");
     502
     503    int n = 0;
     504    for (Iim::ItemIt it(map1, 0); it != INVALID; ++it) {
     505      check(map1[static_cast<Item>(it)] == 0, "Wrong value");
     506      ++n;
     507    }
     508    check(n == (num + 1) / 2, "Wrong number");
     509
     510    for (Iim::ItemIt it(map1, 1); it != INVALID; ++it) {
     511      check(map1[static_cast<Item>(it)] == 1, "Wrong value");
     512      ++n;
     513    }
     514    check(n == num, "Wrong number");
     515
     516  }
     517
     518  // Iterable value map
     519  {
     520    typedef SmartGraph Graph;
     521    typedef SmartGraph::Node Item;
     522    typedef IterableValueMap<SmartGraph, SmartGraph::Node, double> Ivm;
     523
     524    checkConcept<ReadWriteMap<Item, double>, Ivm>();
     525
     526    const int num = 10;
     527    Graph g;
     528    std::vector<Item> items;
     529    for (int i = 0; i < num; ++i) {
     530      items.push_back(g.addNode());
     531    }
     532
     533    Ivm map1(g, 0.0);
     534    check(distance(map1.beginValue(), map1.endValue()) == 1, "Wrong size");
     535    check(*map1.beginValue() == 0.0, "Wrong value");
     536
     537    for (int i = 0; i < num; ++i) {
     538      map1.set(items[i], static_cast<double>(i));
     539    }
     540    check(distance(map1.beginValue(), map1.endValue()) == num, "Wrong size");
     541
     542    for (int i = 0; i < num; ++i) {
     543      Ivm::ItemIt it(map1, static_cast<double>(i));
     544      check(static_cast<Item>(it) == items[i], "Wrong value");
     545      ++it;
     546      check(static_cast<Item>(it) == INVALID, "Wrong value");
     547    }
     548
     549    for (Ivm::ValueIterator vit = map1.beginValue();
     550         vit != map1.endValue(); ++vit) {
     551      check(map1[static_cast<Item>(Ivm::ItemIt(map1, *vit))] == *vit,
     552            "Wrong ValueIterator");
     553    }
     554
     555    for (int i = 0; i < num; ++i) {
     556      map1.set(items[i], static_cast<double>(i % 2));
     557    }
     558    check(distance(map1.beginValue(), map1.endValue()) == 2, "Wrong size");
     559
     560    int n = 0;
     561    for (Ivm::ItemIt it(map1, 0.0); it != INVALID; ++it) {
     562      check(map1[static_cast<Item>(it)] == 0.0, "Wrong value");
     563      ++n;
     564    }
     565    check(n == (num + 1) / 2, "Wrong number");
     566
     567    for (Ivm::ItemIt it(map1, 1.0); it != INVALID; ++it) {
     568      check(map1[static_cast<Item>(it)] == 1.0, "Wrong value");
     569      ++n;
     570    }
     571    check(n == num, "Wrong number");
     572
     573  }
    352574  return 0;
    353575}

  • test/preflow_test.cc

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

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

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