COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
Files:
6 deleted
19 edited

Legend:

Unmodified
Added
Removed

  • doc/groups.dox

    r762 r761  
    239239any kind of path structure.
    240240
    241 \sa \ref concepts::Path "Path concept"
    242 */
    243 
    244 /**
    245 @defgroup heaps Heap Structures
    246 @ingroup datas
    247 \brief %Heap structures implemented in LEMON.
    248 
    249 This group contains the heap structures implemented in LEMON.
    250 
    251 LEMON provides several heap classes. They are efficient implementations
    252 of the abstract data type \e priority \e queue. They store items with
    253 specified values called \e priorities in such a way that finding and
    254 removing the item with minimum priority are efficient.
    255 The basic operations are adding and erasing items, changing the priority
    256 of an item, etc.
    257 
    258 Heaps are crucial in several algorithms, such as Dijkstra and Prim.
    259 The heap implementations have the same interface, thus any of them can be
    260 used easily in such algorithms.
    261 
    262 \sa \ref concepts::Heap "Heap concept"
    263 */
    264 
    265 /**
    266 @defgroup matrices Matrices
    267 @ingroup datas
    268 \brief Two dimensional data storages implemented in LEMON.
    269 
    270 This group contains two dimensional data storages implemented in LEMON.
     241\sa lemon::concepts::Path
    271242*/
    272243

  • lemon/Makefile.am

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

  • lemon/bin_heap.h

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

  • lemon/bits/edge_set_extender.h

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

  • lemon/bits/graph_extender.h

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

  • lemon/bucket_heap.h

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

  • lemon/circulation.h

    r762 r760  
    458458    }
    459459
    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) {
     460    /// \brief Sets the tolerance used by algorithm.
     461    ///
     462    /// Sets the tolerance used by algorithm.
     463    Circulation& tolerance(const Tolerance& tolerance) const {
    465464      _tol = tolerance;
    466465      return *this;
    … …  
    469468    /// \brief Returns a const reference to the tolerance.
    470469    ///
    471     /// Returns a const reference to the tolerance object used by
    472     /// the algorithm.
     470    /// Returns a const reference to the tolerance.
    473471    const Tolerance& tolerance() const {
    474       return _tol;
     472      return tolerance;
    475473    }
    476474

  • lemon/concepts/heap.h

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

  • lemon/fib_heap.h

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

  • lemon/maps.h

    r742 r664  
    2323#include <functional>
    2424#include <vector>
    25 #include <map>
    2625
    2726#include <lemon/core.h>
    … …  
    3029///\ingroup maps
    3130///\brief Miscellaneous property maps
     31
     32#include <map>
    3233
    3334namespace lemon {
    … …  
    18181819  ///
    18191820  /// IdMap provides a unique and immutable id for each item of the
    1820   /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is
     1821  /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is 
    18211822  ///  - \b unique: different items get different ids,
    18221823  ///  - \b immutable: the id of an item does not change (even if you
    … …  
    19021903
    19031904  /// This class provides simple invertable graph maps.
    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.
     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  ///
    19061909  /// The values of the map can be accessed
    19071910  /// 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::multimap<V, K> Container;
     1926    typedef std::map<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.
    19531951    class ValueIterator
    19541952      : public std::iterator<std::forward_iterator_tag, Value> {
    … …  
    20032001    void set(const Key& key, const Value& val) {
    20042002      Value oldval = Map::operator[](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         }
     2003      typename Container::iterator it = _inv_map.find(oldval);
     2004      if (it != _inv_map.end() && it->second == key) {
     2005        _inv_map.erase(it);
    20122006      }
    2013       _inv_map.insert(std::make_pair(val, key));
     2007      _inv_map.insert(make_pair(val, key));
    20142008      Map::set(key, val);
    20152009    }
    … …  
    20232017    }
    20242018
    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);
     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);
    20332024      return it != _inv_map.end() ? it->second : INVALID;
    20342025    }
    … …  
    20422033    virtual void erase(const Key& key) {
    20432034      Value val = Map::operator[](key);
    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         }
     2035      typename Container::iterator it = _inv_map.find(val);
     2036      if (it != _inv_map.end() && it->second == key) {
     2037        _inv_map.erase(it);
    20512038      }
    20522039      Map::erase(key);
    … …  
    20602047      for (int i = 0; i < int(keys.size()); ++i) {
    20612048        Value val = Map::operator[](keys[i]);
    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           }
     2049        typename Container::iterator it = _inv_map.find(val);
     2050        if (it != _inv_map.end() && it->second == keys[i]) {
     2051          _inv_map.erase(it);
    20692052        }
    20702053      }
    … …  
    21022085      /// \brief Subscript operator.
    21032086      ///
    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.
     2087      /// Subscript operator. It gives back the item
     2088      /// that was last assigned to the given value.
    21072089      Value operator[](const Key& key) const {
    21082090        return _inverted(key);
    … …  
    22732255
    22742256    /// \brief Gives back the item belonging to a \e RangeId
    2275     ///
     2257    /// 
    22762258    /// Gives back the item belonging to a \e RangeId.
    22772259    Item operator()(int id) const {
    … …  
    23302312  };
    23312313
    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 
    32292314  /// \brief Map of the source nodes of arcs in a digraph.
    32302315  ///
    … …  
    33962481  /// whenever the digraph changes.
    33972482  ///
    3398   /// \warning Besides \c addNode() and \c addArc(), a digraph structure
     2483  /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
    33992484  /// may provide alternative ways to modify the digraph.
    34002485  /// The correct behavior of InDegMap is not guarantied if these additional
    … …  
    34122497
    34132498  public:
    3414 
     2499   
    34152500    /// The graph type of InDegMap
    34162501    typedef GR Graph;
    … …  
    35262611  /// whenever the digraph changes.
    35272612  ///
    3528   /// \warning Besides \c addNode() and \c addArc(), a digraph structure
     2613  /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
    35292614  /// may provide alternative ways to modify the digraph.
    35302615  /// The correct behavior of OutDegMap is not guarantied if these additional

  • lemon/preflow.h

    r762 r760  
    105105  /// "flow of maximum value" in a digraph.
    106106  /// The preflow algorithms are the fastest known maximum
    107   /// flow algorithms. The current implementation uses a mixture of the
     107  /// flow algorithms. The current implementation use 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 the algorithm.
    382     ///
    383     /// Sets the tolerance object used by the algorithm.
    384     /// \return <tt>(*this)</tt>
    385     Preflow& tolerance(const Tolerance& tolerance) {
     381    /// \brief Sets the tolerance used by algorithm.
     382    ///
     383    /// Sets the tolerance used by algorithm.
     384    Preflow& tolerance(const Tolerance& tolerance) const {
    386385      _tolerance = tolerance;
    387386      return *this;
    … …  
    390389    /// \brief Returns a const reference to the tolerance.
    391390    ///
    392     /// Returns a const reference to the tolerance object used by
    393     /// the algorithm.
     391    /// Returns a const reference to the tolerance.
    394392    const Tolerance& tolerance() const {
    395       return _tolerance;
     393      return tolerance;
    396394    }
    397395

  • lemon/radix_heap.h

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

  • test/CMakeLists.txt

    r745 r726  
    1010SET(TESTS
    1111  adaptors_test
    12   bellman_ford_test
    1312  bfs_test
    1413  circulation_test

  • test/Makefile.am

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

  • test/circulation_test.cc

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

  • test/heap_test.cc

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

  • test/maps_test.cc

    r742 r554  
    2323#include <lemon/concepts/maps.h>
    2424#include <lemon/maps.h>
    25 #include <lemon/smart_graph.h>
    2625
    2726#include "test_tools.h"
    … …  
    351350  }
    352351
    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   }
    574352  return 0;
    575353}

  • test/preflow_test.cc

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

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

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