COIN-OR::LEMON - Graph Library

Changeset 750:bb3392fe91f2 in lemon


Ignore:
Timestamp:
07/09/09 04:07:08 (9 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Message:

Improve and unify the doc + names in the new heaps (#301)

Location:
lemon
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • lemon/binom_heap.h

    r748 r750  
    1 /* -*- C++ -*- 
     1/* -*- mode: C++; indent-tabs-mode: nil; -*- 
    22 * 
    3  * This file is a part of LEMON, a generic C++ optimization library 
     3 * This file is a part of LEMON, a generic C++ optimization library. 
    44 * 
    5  * Copyright (C) 2003-2008 
     5 * Copyright (C) 2003-2009 
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES). 
     
    2121 
    2222///\file 
    23 ///\ingroup auxdat 
     23///\ingroup heaps 
    2424///\brief Binomial Heap implementation. 
    2525 
    2626#include <vector> 
     27#include <utility> 
    2728#include <functional> 
    2829#include <lemon/math.h> 
     
    3132namespace lemon { 
    3233 
    33   /// \ingroup auxdat 
     34  /// \ingroup heaps 
    3435  /// 
    35   ///\brief Binomial Heap. 
     36  ///\brief Binomial heap data structure. 
    3637  /// 
    37   ///This class implements the \e Binomial \e heap data structure. A \e heap 
    38   ///is a data structure for storing items with specified values called \e 
    39   ///priorities in such a way that finding the item with minimum priority is 
    40   ///efficient. \c Compare specifies the ordering of the priorities. In a heap 
    41   ///one can change the priority of an item, add or erase an item, etc. 
     38  /// This class implements the \e binomial \e heap data structure. 
     39  /// It fully conforms to the \ref concepts::Heap "heap concept". 
    4240  /// 
    43   ///The methods \ref increase and \ref erase are not efficient in a Binomial 
    44   ///heap. In case of many calls to these operations, it is better to use a 
    45   ///\ref BinHeap "binary heap". 
     41  /// The methods \ref increase() and \ref erase() are not efficient 
     42  /// in a binomial heap. In case of many calls of these operations, 
     43  /// it is better to use other heap structure, e.g. \ref BinHeap 
     44  /// "binary heap". 
    4645  /// 
    47   ///\param _Prio Type of the priority of the items. 
    48   ///\param _ItemIntMap A read and writable Item int map, used internally 
    49   ///to handle the cross references. 
    50   ///\param _Compare A class for the ordering of the priorities. The 
    51   ///default is \c std::less<_Prio>. 
    52   /// 
    53   ///\sa BinHeap 
    54   ///\sa Dijkstra 
    55   ///\author Dorian Batha 
    56  
     46  /// \tparam PR Type of the priorities of the items. 
     47  /// \tparam IM A read-writable item map with \c int values, used 
     48  /// internally to handle the cross references. 
     49  /// \tparam CMP A functor class for comparing the priorities. 
     50  /// The default is \c std::less<PR>. 
    5751#ifdef DOXYGEN 
    58   template <typename _Prio, 
    59             typename _ItemIntMap, 
    60             typename _Compare> 
     52  template <typename PR, typename IM, typename CMP> 
    6153#else 
    62   template <typename _Prio, 
    63             typename _ItemIntMap, 
    64             typename _Compare = std::less<_Prio> > 
     54  template <typename PR, typename IM, typename CMP = std::less<PR> > 
    6555#endif 
    6656  class BinomHeap { 
    6757  public: 
    68     typedef _ItemIntMap ItemIntMap; 
    69     typedef _Prio Prio; 
     58    /// Type of the item-int map. 
     59    typedef IM ItemIntMap; 
     60    /// Type of the priorities. 
     61    typedef PR Prio; 
     62    /// Type of the items stored in the heap. 
    7063    typedef typename ItemIntMap::Key Item; 
    71     typedef std::pair<Item,Prio> Pair; 
    72     typedef _Compare Compare; 
     64    /// Functor type for comparing the priorities. 
     65    typedef CMP Compare; 
     66 
     67    /// \brief Type to represent the states of the items. 
     68    /// 
     69    /// Each item has a state associated to it. It can be "in heap", 
     70    /// "pre-heap" or "post-heap". The latter two are indifferent from the 
     71    /// heap's point of view, but may be useful to the user. 
     72    /// 
     73    /// The item-int map must be initialized in such way that it assigns 
     74    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. 
     75    enum State { 
     76      IN_HEAP = 0,    ///< = 0. 
     77      PRE_HEAP = -1,  ///< = -1. 
     78      POST_HEAP = -2  ///< = -2. 
     79    }; 
    7380 
    7481  private: 
    7582    class store; 
    7683 
    77     std::vector<store> container; 
    78     int minimum, head; 
    79     ItemIntMap &iimap; 
    80     Compare comp; 
    81     int num_items; 
     84    std::vector<store> _data; 
     85    int _min, _head; 
     86    ItemIntMap &_iim; 
     87    Compare _comp; 
     88    int _num_items; 
    8289 
    8390  public: 
    84     ///Status of the nodes 
    85     enum State { 
    86       ///The node is in the heap 
    87       IN_HEAP = 0, 
    88       ///The node has never been in the heap 
    89       PRE_HEAP = -1, 
    90       ///The node was in the heap but it got out of it 
    91       POST_HEAP = -2 
    92     }; 
    93  
    94     /// \brief The constructor 
    95     /// 
    96     /// \c _iimap should be given to the constructor, since it is 
    97     ///   used internally to handle the cross references. 
    98     explicit BinomHeap(ItemIntMap &_iimap) 
    99       : minimum(0), head(-1), iimap(_iimap), num_items() {} 
    100  
    101     /// \brief The constructor 
    102     /// 
    103     /// \c _iimap should be given to the constructor, since it is used 
    104     /// internally to handle the cross references. \c _comp is an 
    105     /// object for ordering of the priorities. 
    106     BinomHeap(ItemIntMap &_iimap, const Compare &_comp) 
    107       : minimum(0), head(-1), iimap(_iimap), comp(_comp), num_items() {} 
     91    /// \brief Constructor. 
     92    /// 
     93    /// Constructor. 
     94    /// \param map A map that assigns \c int values to the items. 
     95    /// It is used internally to handle the cross references. 
     96    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 
     97    explicit BinomHeap(ItemIntMap &map) 
     98      : _min(0), _head(-1), _iim(map), _num_items(0) {} 
     99 
     100    /// \brief Constructor. 
     101    /// 
     102    /// Constructor. 
     103    /// \param map A map that assigns \c int values to the items. 
     104    /// It is used internally to handle the cross references. 
     105    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 
     106    /// \param comp The function object used for comparing the priorities. 
     107    BinomHeap(ItemIntMap &map, const Compare &comp) 
     108      : _min(0), _head(-1), _iim(map), _comp(comp), _num_items(0) {} 
    108109 
    109110    /// \brief The number of items stored in the heap. 
    110111    /// 
    111     /// Returns the number of items stored in the heap. 
    112     int size() const { return num_items; } 
    113  
    114     /// \brief Checks if the heap stores no items. 
    115     /// 
    116     ///   Returns \c true if and only if the heap stores no items. 
    117     bool empty() const { return num_items==0; } 
    118  
    119     /// \brief Make empty this heap. 
    120     /// 
    121     /// Make empty this heap. It does not change the cross reference 
    122     /// map.  If you want to reuse a heap what is not surely empty you 
    123     /// should first clear the heap and after that you should set the 
    124     /// cross reference map for each item to \c PRE_HEAP. 
     112    /// This function returns the number of items stored in the heap. 
     113    int size() const { return _num_items; } 
     114 
     115    /// \brief Check if the heap is empty. 
     116    /// 
     117    /// This function returns \c true if the heap is empty. 
     118    bool empty() const { return _num_items==0; } 
     119 
     120    /// \brief Make the heap empty. 
     121    /// 
     122    /// This functon makes the heap empty. 
     123    /// It does not change the cross reference map. If you want to reuse 
     124    /// a heap that is not surely empty, you should first clear it and 
     125    /// then you should set the cross reference map to \c PRE_HEAP 
     126    /// for each item. 
    125127    void clear() { 
    126       container.clear(); minimum=0; num_items=0; head=-1; 
    127     } 
    128  
    129     /// \brief \c item gets to the heap with priority \c value independently 
    130     /// if \c item was already there. 
    131     /// 
    132     /// This method calls \ref push(\c item, \c value) if \c item is not 
    133     /// stored in the heap and it calls \ref decrease(\c item, \c value) or 
    134     /// \ref increase(\c item, \c value) otherwise. 
     128      _data.clear(); _min=0; _num_items=0; _head=-1; 
     129    } 
     130 
     131    /// \brief Set the priority of an item or insert it, if it is 
     132    /// not stored in the heap. 
     133    /// 
     134    /// This method sets the priority of the given item if it is 
     135    /// already stored in the heap. Otherwise it inserts the given 
     136    /// item into the heap with the given priority. 
     137    /// \param item The item. 
     138    /// \param value The priority. 
    135139    void set (const Item& item, const Prio& value) { 
    136       int i=iimap[item]; 
    137       if ( i >= 0 && container[i].in ) { 
    138         if ( comp(value, container[i].prio) ) decrease(item, value); 
    139         if ( comp(container[i].prio, value) ) increase(item, value); 
     140      int i=_iim[item]; 
     141      if ( i >= 0 && _data[i].in ) { 
     142        if ( _comp(value, _data[i].prio) ) decrease(item, value); 
     143        if ( _comp(_data[i].prio, value) ) increase(item, value); 
    140144      } else push(item, value); 
    141145    } 
    142146 
    143     /// \brief Adds \c item to the heap with priority \c value. 
    144     /// 
    145     /// Adds \c item to the heap with priority \c value. 
    146     /// \pre \c item must not be stored in the heap. 
     147    /// \brief Insert an item into the heap with the given priority. 
     148    /// 
     149    /// This function inserts the given item into the heap with the 
     150    /// given priority. 
     151    /// \param item The item to insert. 
     152    /// \param value The priority of the item. 
     153    /// \pre \e item must not be stored in the heap. 
    147154    void push (const Item& item, const Prio& value) { 
    148       int i=iimap[item]; 
     155      int i=_iim[item]; 
    149156      if ( i<0 ) { 
    150         int s=container.size(); 
    151         iimap.set( item,s ); 
     157        int s=_data.size(); 
     158        _iim.set( item,s ); 
    152159        store st; 
    153160        st.name=item; 
    154         container.push_back(st); 
     161        _data.push_back(st); 
    155162        i=s; 
    156163      } 
    157164      else { 
    158         container[i].parent=container[i].right_neighbor=container[i].child=-1; 
    159         container[i].degree=0; 
    160         container[i].in=true; 
    161       } 
    162       container[i].prio=value; 
    163  
    164       if( 0==num_items ) { head=i; minimum=i; } 
     165        _data[i].parent=_data[i].right_neighbor=_data[i].child=-1; 
     166        _data[i].degree=0; 
     167        _data[i].in=true; 
     168      } 
     169      _data[i].prio=value; 
     170 
     171      if( 0==_num_items ) { _head=i; _min=i; } 
    165172      else { merge(i); } 
    166173 
    167       minimum = find_min(); 
    168  
    169       ++num_items; 
    170     } 
    171  
    172     /// \brief Returns the item with minimum priority relative to \c Compare. 
    173     /// 
    174     /// This method returns the item with minimum priority relative to \c 
    175     /// Compare. 
    176     /// \pre The heap must be nonempty. 
    177     Item top() const { return container[minimum].name; } 
    178  
    179     /// \brief Returns the minimum priority relative to \c Compare. 
    180     /// 
    181     /// It returns the minimum priority relative to \c Compare. 
    182     /// \pre The heap must be nonempty. 
    183     const Prio& prio() const { return container[minimum].prio; } 
    184  
    185     /// \brief Returns the priority of \c item. 
    186     /// 
    187     /// It returns the priority of \c item. 
    188     /// \pre \c item must be in the heap. 
     174      _min = findMin(); 
     175 
     176      ++_num_items; 
     177    } 
     178 
     179    /// \brief Return the item having minimum priority. 
     180    /// 
     181    /// This function returns the item having minimum priority. 
     182    /// \pre The heap must be non-empty. 
     183    Item top() const { return _data[_min].name; } 
     184 
     185    /// \brief The minimum priority. 
     186    /// 
     187    /// This function returns the minimum priority. 
     188    /// \pre The heap must be non-empty. 
     189    Prio prio() const { return _data[_min].prio; } 
     190 
     191    /// \brief The priority of the given item. 
     192    /// 
     193    /// This function returns the priority of the given item. 
     194    /// \param item The item. 
     195    /// \pre \e item must be in the heap. 
    189196    const Prio& operator[](const Item& item) const { 
    190       return container[iimap[item]].prio; 
    191     } 
    192  
    193     /// \brief Deletes the item with minimum priority relative to \c Compare. 
    194     /// 
    195     /// This method deletes the item with minimum priority relative to \c 
    196     /// Compare from the heap. 
     197      return _data[_iim[item]].prio; 
     198    } 
     199 
     200    /// \brief Remove the item having minimum priority. 
     201    /// 
     202    /// This function removes the item having minimum priority. 
    197203    /// \pre The heap must be non-empty. 
    198204    void pop() { 
    199       container[minimum].in=false; 
     205      _data[_min].in=false; 
    200206 
    201207      int head_child=-1; 
    202       if ( container[minimum].child!=-1 ) { 
    203         int child=container[minimum].child; 
     208      if ( _data[_min].child!=-1 ) { 
     209        int child=_data[_min].child; 
    204210        int neighb; 
    205211        int prev=-1; 
    206212        while( child!=-1 ) { 
    207           neighb=container[child].right_neighbor; 
    208           container[child].parent=-1; 
    209           container[child].right_neighbor=prev; 
     213          neighb=_data[child].right_neighbor; 
     214          _data[child].parent=-1; 
     215          _data[child].right_neighbor=prev; 
    210216          head_child=child; 
    211217          prev=child; 
     
    215221 
    216222      // The first case is that there are only one root. 
    217       if ( -1==container[head].right_neighbor ) { 
    218         head=head_child; 
     223      if ( -1==_data[_head].right_neighbor ) { 
     224        _head=head_child; 
    219225      } 
    220226      // The case where there are more roots. 
    221227      else { 
    222         if( head!=minimum )  { unlace(minimum); } 
    223         else { head=container[head].right_neighbor; } 
     228        if( _head!=_min )  { unlace(_min); } 
     229        else { _head=_data[_head].right_neighbor; } 
    224230 
    225231        merge(head_child); 
    226232      } 
    227       minimum=find_min(); 
    228       --num_items; 
    229     } 
    230  
    231     /// \brief Deletes \c item from the heap. 
    232     /// 
    233     /// This method deletes \c item from the heap, if \c item was already 
    234     /// stored in the heap. It is quite inefficient in Binomial heaps. 
     233      _min=findMin(); 
     234      --_num_items; 
     235    } 
     236 
     237    /// \brief Remove the given item from the heap. 
     238    /// 
     239    /// This function removes the given item from the heap if it is 
     240    /// already stored. 
     241    /// \param item The item to delete. 
     242    /// \pre \e item must be in the heap. 
    235243    void erase (const Item& item) { 
    236       int i=iimap[item]; 
    237       if ( i >= 0 && container[i].in ) { 
    238         decrease( item, container[minimum].prio-1 ); 
     244      int i=_iim[item]; 
     245      if ( i >= 0 && _data[i].in ) { 
     246        decrease( item, _data[_min].prio-1 ); 
    239247        pop(); 
    240248      } 
    241249    } 
    242250 
    243     /// \brief Decreases the priority of \c item to \c value. 
    244     /// 
    245     /// This method decreases the priority of \c item to \c value. 
    246     /// \pre \c item must be stored in the heap with priority at least \c 
    247     ///   value relative to \c Compare. 
     251    /// \brief Decrease the priority of an item to the given value. 
     252    /// 
     253    /// This function decreases the priority of an item to the given value. 
     254    /// \param item The item. 
     255    /// \param value The priority. 
     256    /// \pre \e item must be stored in the heap with priority at least \e value. 
    248257    void decrease (Item item, const Prio& value) { 
    249       int i=iimap[item]; 
    250  
    251       if( comp( value,container[i].prio ) ) { 
    252         container[i].prio=value; 
    253  
    254         int p_loc=container[i].parent, loc=i; 
     258      int i=_iim[item]; 
     259 
     260      if( _comp( value,_data[i].prio ) ) { 
     261        _data[i].prio=value; 
     262 
     263        int p_loc=_data[i].parent, loc=i; 
    255264        int parent, child, neighb; 
    256265 
    257         while( -1!=p_loc && comp(container[loc].prio,container[p_loc].prio) ) { 
     266        while( -1!=p_loc && _comp(_data[loc].prio,_data[p_loc].prio) ) { 
    258267 
    259268          // parent set for other loc_child 
    260           child=container[loc].child; 
     269          child=_data[loc].child; 
    261270          while( -1!=child ) { 
    262             container[child].parent=p_loc; 
    263             child=container[child].right_neighbor; 
     271            _data[child].parent=p_loc; 
     272            child=_data[child].right_neighbor; 
    264273          } 
    265274 
    266275          // parent set for other p_loc_child 
    267           child=container[p_loc].child; 
     276          child=_data[p_loc].child; 
    268277          while( -1!=child ) { 
    269             container[child].parent=loc; 
    270             child=container[child].right_neighbor; 
    271           } 
    272  
    273           child=container[p_loc].child; 
    274           container[p_loc].child=container[loc].child; 
     278            _data[child].parent=loc; 
     279            child=_data[child].right_neighbor; 
     280          } 
     281 
     282          child=_data[p_loc].child; 
     283          _data[p_loc].child=_data[loc].child; 
    275284          if( child==loc ) 
    276285            child=p_loc; 
    277           container[loc].child=child; 
     286          _data[loc].child=child; 
    278287 
    279288          // left_neighb set for p_loc 
    280           if( container[loc].child!=p_loc ) { 
    281             while( container[child].right_neighbor!=loc ) 
    282               child=container[child].right_neighbor; 
    283             container[child].right_neighbor=p_loc; 
     289          if( _data[loc].child!=p_loc ) { 
     290            while( _data[child].right_neighbor!=loc ) 
     291              child=_data[child].right_neighbor; 
     292            _data[child].right_neighbor=p_loc; 
    284293          } 
    285294 
    286295          // left_neighb set for loc 
    287           parent=container[p_loc].parent; 
    288           if( -1!=parent ) child=container[parent].child; 
    289           else child=head; 
     296          parent=_data[p_loc].parent; 
     297          if( -1!=parent ) child=_data[parent].child; 
     298          else child=_head; 
    290299 
    291300          if( child!=p_loc ) { 
    292             while( container[child].right_neighbor!=p_loc ) 
    293               child=container[child].right_neighbor; 
    294             container[child].right_neighbor=loc; 
    295           } 
    296  
    297           neighb=container[p_loc].right_neighbor; 
    298           container[p_loc].right_neighbor=container[loc].right_neighbor; 
    299           container[loc].right_neighbor=neighb; 
    300  
    301           container[p_loc].parent=loc; 
    302           container[loc].parent=parent; 
    303  
    304           if( -1!=parent && container[parent].child==p_loc ) 
    305             container[parent].child=loc; 
     301            while( _data[child].right_neighbor!=p_loc ) 
     302              child=_data[child].right_neighbor; 
     303            _data[child].right_neighbor=loc; 
     304          } 
     305 
     306          neighb=_data[p_loc].right_neighbor; 
     307          _data[p_loc].right_neighbor=_data[loc].right_neighbor; 
     308          _data[loc].right_neighbor=neighb; 
     309 
     310          _data[p_loc].parent=loc; 
     311          _data[loc].parent=parent; 
     312 
     313          if( -1!=parent && _data[parent].child==p_loc ) 
     314            _data[parent].child=loc; 
    306315 
    307316          /*if new parent will be the first root*/ 
    308           if( head==p_loc ) 
    309             head=loc; 
    310  
    311           p_loc=container[loc].parent; 
    312         } 
    313       } 
    314       if( comp(value,container[minimum].prio) ) { 
    315         minimum=i; 
    316       } 
    317     } 
    318  
    319     /// \brief Increases the priority of \c item to \c value. 
    320     /// 
    321     /// This method sets the priority of \c item to \c value. Though 
    322     /// there is no precondition on the priority of \c item, this 
    323     /// method should be used only if it is indeed necessary to increase 
    324     /// (relative to \c Compare) the priority of \c item, because this 
    325     /// method is inefficient. 
     317          if( _head==p_loc ) 
     318            _head=loc; 
     319 
     320          p_loc=_data[loc].parent; 
     321        } 
     322      } 
     323      if( _comp(value,_data[_min].prio) ) { 
     324        _min=i; 
     325      } 
     326    } 
     327 
     328    /// \brief Increase the priority of an item to the given value. 
     329    /// 
     330    /// This function increases the priority of an item to the given value. 
     331    /// \param item The item. 
     332    /// \param value The priority. 
     333    /// \pre \e item must be stored in the heap with priority at most \e value. 
    326334    void increase (Item item, const Prio& value) { 
    327335      erase(item); 
     
    329337    } 
    330338 
    331  
    332     /// \brief Returns if \c item is in, has already been in, or has never 
    333     /// been in the heap. 
    334     /// 
    335     /// This method returns PRE_HEAP if \c item has never been in the 
    336     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP 
    337     /// otherwise. In the latter case it is possible that \c item will 
    338     /// get back to the heap again. 
     339    /// \brief Return the state of an item. 
     340    /// 
     341    /// This method returns \c PRE_HEAP if the given item has never 
     342    /// been in the heap, \c IN_HEAP if it is in the heap at the moment, 
     343    /// and \c POST_HEAP otherwise. 
     344    /// In the latter case it is possible that the item will get back 
     345    /// to the heap again. 
     346    /// \param item The item. 
    339347    State state(const Item &item) const { 
    340       int i=iimap[item]; 
     348      int i=_iim[item]; 
    341349      if( i>=0 ) { 
    342         if ( container[i].in ) i=0; 
     350        if ( _data[i].in ) i=0; 
    343351        else i=-2; 
    344352      } 
     
    346354    } 
    347355 
    348     /// \brief Sets the state of the \c item in the heap. 
    349     /// 
    350     /// Sets the state of the \c item in the heap. It can be used to 
    351     /// manually clear the heap when it is important to achive the 
    352     /// better time complexity. 
     356    /// \brief Set the state of an item in the heap. 
     357    /// 
     358    /// This function sets the state of the given item in the heap. 
     359    /// It can be used to manually clear the heap when it is important 
     360    /// to achive better time complexity. 
    353361    /// \param i The item. 
    354362    /// \param st The state. It should not be \c IN_HEAP. 
     
    360368          erase(i); 
    361369        } 
    362         iimap[i] = st; 
     370        _iim[i] = st; 
    363371        break; 
    364372      case IN_HEAP: 
     
    368376 
    369377  private: 
    370     int find_min() { 
     378    int findMin() { 
    371379      int min_loc=-1, min_val; 
    372       int x=head; 
     380      int x=_head; 
    373381      if( x!=-1 ) { 
    374         min_val=container[x].prio; 
     382        min_val=_data[x].prio; 
    375383        min_loc=x; 
    376         x=container[x].right_neighbor; 
     384        x=_data[x].right_neighbor; 
    377385 
    378386        while( x!=-1 ) { 
    379           if( comp( container[x].prio,min_val ) ) { 
    380             min_val=container[x].prio; 
     387          if( _comp( _data[x].prio,min_val ) ) { 
     388            min_val=_data[x].prio; 
    381389            min_loc=x; 
    382390          } 
    383           x=container[x].right_neighbor; 
     391          x=_data[x].right_neighbor; 
    384392        } 
    385393      } 
     
    390398      interleave(a); 
    391399 
    392       int x=head; 
     400      int x=_head; 
    393401      if( -1!=x ) { 
    394         int x_prev=-1, x_next=container[x].right_neighbor; 
     402        int x_prev=-1, x_next=_data[x].right_neighbor; 
    395403        while( -1!=x_next ) { 
    396           if( container[x].degree!=container[x_next].degree || ( -1!=container[x_next].right_neighbor && container[container[x_next].right_neighbor].degree==container[x].degree ) ) { 
     404          if( _data[x].degree!=_data[x_next].degree || ( -1!=_data[x_next].right_neighbor && _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) { 
    397405            x_prev=x; 
    398406            x=x_next; 
    399407          } 
    400408          else { 
    401             if( comp(container[x].prio,container[x_next].prio) ) { 
    402               container[x].right_neighbor=container[x_next].right_neighbor; 
     409            if( _comp(_data[x].prio,_data[x_next].prio) ) { 
     410              _data[x].right_neighbor=_data[x_next].right_neighbor; 
    403411              fuse(x_next,x); 
    404412            } 
    405413            else { 
    406               if( -1==x_prev ) { head=x_next; } 
     414              if( -1==x_prev ) { _head=x_next; } 
    407415              else { 
    408                 container[x_prev].right_neighbor=x_next; 
     416                _data[x_prev].right_neighbor=x_next; 
    409417              } 
    410418              fuse(x,x_next); 
     
    412420            } 
    413421          } 
    414           x_next=container[x].right_neighbor; 
     422          x_next=_data[x].right_neighbor; 
    415423        } 
    416424      } 
     
    420428      int other=-1, head_other=-1; 
    421429 
    422       while( -1!=a || -1!=head ) { 
     430      while( -1!=a || -1!=_head ) { 
    423431        if( -1==a ) { 
    424432          if( -1==head_other ) { 
    425             head_other=head; 
     433            head_other=_head; 
    426434          } 
    427435          else { 
    428             container[other].right_neighbor=head; 
    429           } 
    430           head=-1; 
    431         } 
    432         else if( -1==head ) { 
     436            _data[other].right_neighbor=_head; 
     437          } 
     438          _head=-1; 
     439        } 
     440        else if( -1==_head ) { 
    433441          if( -1==head_other ) { 
    434442            head_other=a; 
    435443          } 
    436444          else { 
    437             container[other].right_neighbor=a; 
     445            _data[other].right_neighbor=a; 
    438446          } 
    439447          a=-1; 
    440448        } 
    441449        else { 
    442           if( container[a].degree<container[head].degree ) { 
     450          if( _data[a].degree<_data[_head].degree ) { 
    443451            if( -1==head_other ) { 
    444452              head_other=a; 
    445453            } 
    446454            else { 
    447               container[other].right_neighbor=a; 
     455              _data[other].right_neighbor=a; 
    448456            } 
    449457            other=a; 
    450             a=container[a].right_neighbor; 
     458            a=_data[a].right_neighbor; 
    451459          } 
    452460          else { 
    453461            if( -1==head_other ) { 
    454               head_other=head; 
     462              head_other=_head; 
    455463            } 
    456464            else { 
    457               container[other].right_neighbor=head; 
     465              _data[other].right_neighbor=_head; 
    458466            } 
    459             other=head; 
    460             head=container[head].right_neighbor; 
    461           } 
    462         } 
    463       } 
    464       head=head_other; 
     467            other=_head; 
     468            _head=_data[_head].right_neighbor; 
     469          } 
     470        } 
     471      } 
     472      _head=head_other; 
    465473    } 
    466474 
    467475    // Lacing a under b 
    468476    void fuse(int a, int b) { 
    469       container[a].parent=b; 
    470       container[a].right_neighbor=container[b].child; 
    471       container[b].child=a; 
    472  
    473       ++container[b].degree; 
     477      _data[a].parent=b; 
     478      _data[a].right_neighbor=_data[b].child; 
     479      _data[b].child=a; 
     480 
     481      ++_data[b].degree; 
    474482    } 
    475483 
    476484    // It is invoked only if a has siblings. 
    477485    void unlace(int a) { 
    478       int neighb=container[a].right_neighbor; 
    479       int other=head; 
    480  
    481       while( container[other].right_neighbor!=a ) 
    482         other=container[other].right_neighbor; 
    483       container[other].right_neighbor=neighb; 
     486      int neighb=_data[a].right_neighbor; 
     487      int other=_head; 
     488 
     489      while( _data[other].right_neighbor!=a ) 
     490        other=_data[other].right_neighbor; 
     491      _data[other].right_neighbor=neighb; 
    484492    } 
    485493 
  • lemon/fourary_heap.h

    r748 r750  
    1 /* -*- C++ -*- 
    2  * 
    3  * This file is a part of LEMON, a generic C++ optimization library 
    4  * 
    5  * Copyright (C) 2003-2008 
     1/* -*- mode: C++; indent-tabs-mode: nil; -*- 
     2 * 
     3 * This file is a part of LEMON, a generic C++ optimization library. 
     4 * 
     5 * Copyright (C) 2003-2009 
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES). 
     
    2020#define LEMON_FOURARY_HEAP_H 
    2121 
    22 ///\ingroup auxdat 
     22///\ingroup heaps 
    2323///\file 
    24 ///\brief 4ary Heap implementation. 
    25  
    26 #include <iostream> 
     24///\brief Fourary heap implementation. 
     25 
    2726#include <vector> 
    2827#include <utility> 
     
    3130namespace lemon { 
    3231 
    33   ///\ingroup auxdat 
    34   /// 
    35   ///\brief A 4ary Heap implementation. 
    36   /// 
    37   ///This class implements the \e 4ary \e heap data structure. A \e heap 
    38   ///is a data structure for storing items with specified values called \e 
    39   ///priorities in such a way that finding the item with minimum priority is 
    40   ///efficient. \c Compare specifies the ordering of the priorities. In a heap 
    41   ///one can change the priority of an item, add or erase an item, etc. 
    42   /// 
    43   ///\param _Prio Type of the priority of the items. 
    44   ///\param _ItemIntMap A read and writable Item int map, used internally 
    45   ///to handle the cross references. 
    46   ///\param _Compare A class for the ordering of the priorities. The 
    47   ///default is \c std::less<_Prio>. 
    48   /// 
    49   ///\sa FibHeap 
    50   ///\sa Dijkstra 
    51   ///\author Dorian Batha 
    52  
    53   template <typename _Prio, typename _ItemIntMap, 
    54             typename _Compare = std::less<_Prio> > 
    55  
     32  /// \ingroup heaps 
     33  /// 
     34  ///\brief Fourary heap data structure. 
     35  /// 
     36  /// This class implements the \e fourary \e heap data structure. 
     37  /// It fully conforms to the \ref concepts::Heap "heap concept". 
     38  /// 
     39  /// The fourary heap is a specialization of the \ref KaryHeap "K-ary heap" 
     40  /// for <tt>K=4</tt>. It is similar to the \ref BinHeap "binary heap", 
     41  /// but its nodes have at most four children, instead of two. 
     42  /// 
     43  /// \tparam PR Type of the priorities of the items. 
     44  /// \tparam IM A read-writable item map with \c int values, used 
     45  /// internally to handle the cross references. 
     46  /// \tparam CMP A functor class for comparing the priorities. 
     47  /// The default is \c std::less<PR>. 
     48  /// 
     49  ///\sa BinHeap 
     50  ///\sa KaryHeap 
     51#ifdef DOXYGEN 
     52  template <typename PR, typename IM, typename CMP> 
     53#else 
     54  template <typename PR, typename IM, typename CMP = std::less<PR> > 
     55#endif 
    5656  class FouraryHeap { 
    57  
    5857  public: 
    59     ///\e 
    60     typedef _ItemIntMap ItemIntMap; 
    61     ///\e 
    62     typedef _Prio Prio; 
    63     ///\e 
     58    /// Type of the item-int map. 
     59    typedef IM ItemIntMap; 
     60    /// Type of the priorities. 
     61    typedef PR Prio; 
     62    /// Type of the items stored in the heap. 
    6463    typedef typename ItemIntMap::Key Item; 
    65     ///\e 
     64    /// Type of the item-priority pairs. 
    6665    typedef std::pair<Item,Prio> Pair; 
    67     ///\e 
    68     typedef _Compare Compare; 
    69  
    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 
     66    /// Functor type for comparing the priorities. 
     67    typedef CMP Compare; 
     68 
     69    /// \brief Type to represent the states of the items. 
     70    /// 
     71    /// Each item has a state associated to it. It can be "in heap", 
     72    /// "pre-heap" or "post-heap". The latter two are indifferent from the 
    7473    /// heap's point of view, but may be useful to the user. 
    7574    /// 
    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... 
     75    /// The item-int map must be initialized in such way that it assigns 
     76    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. 
    7877    enum State { 
    79       IN_HEAP = 0, 
    80       PRE_HEAP = -1, 
    81       POST_HEAP = -2 
     78      IN_HEAP = 0,    ///< = 0. 
     79      PRE_HEAP = -1,  ///< = -1. 
     80      POST_HEAP = -2  ///< = -2. 
    8281    }; 
    8382 
    8483  private: 
    85     std::vector<Pair> data; 
    86     Compare comp; 
    87     ItemIntMap &iim; 
     84    std::vector<Pair> _data; 
     85    Compare _comp; 
     86    ItemIntMap &_iim; 
    8887 
    8988  public: 
    90     /// \brief The constructor. 
    91     /// 
    92     /// The constructor. 
    93     /// \param _iim should be given to the constructor, since it is used 
    94     /// internally to handle the cross references. The value of the map 
    95     /// should be PRE_HEAP (-1) for each element. 
    96     explicit FouraryHeap(ItemIntMap &_iim) : iim(_iim) {} 
    97  
    98     /// \brief The constructor. 
    99     /// 
    100     /// The constructor. 
    101     /// \param _iim should be given to the constructor, since it is used 
    102     /// internally to handle the cross references. The value of the map 
    103     /// should be PRE_HEAP (-1) for each element. 
    104     /// 
    105     /// \param _comp The comparator function object. 
    106     FouraryHeap(ItemIntMap &_iim, const Compare &_comp) 
    107       : iim(_iim), comp(_comp) {} 
    108  
    109     /// The number of items stored in the heap. 
    110     /// 
    111     /// \brief Returns the number of items stored in the heap. 
    112     int size() const { return data.size(); } 
    113  
    114     /// \brief Checks if the heap stores no items. 
    115     /// 
    116     /// Returns \c true if and only if the heap stores no items. 
    117     bool empty() const { return data.empty(); } 
    118  
    119     /// \brief Make empty this heap. 
    120     /// 
    121     /// Make empty this heap. It does not change the cross reference map. 
    122     /// If you want to reuse what is not surely empty you should first clear 
    123     /// the heap and after that you should set the cross reference map for 
    124     /// each item to \c PRE_HEAP. 
    125     void clear() { data.clear(); } 
     89    /// \brief Constructor. 
     90    /// 
     91    /// Constructor. 
     92    /// \param map A map that assigns \c int values to the items. 
     93    /// It is used internally to handle the cross references. 
     94    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 
     95    explicit FouraryHeap(ItemIntMap &map) : _iim(map) {} 
     96 
     97    /// \brief Constructor. 
     98    /// 
     99    /// Constructor. 
     100    /// \param map A map that assigns \c int values to the items. 
     101    /// It is used internally to handle the cross references. 
     102    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 
     103    /// \param comp The function object used for comparing the priorities. 
     104    FouraryHeap(ItemIntMap &map, const Compare &comp) 
     105      : _iim(map), _comp(comp) {} 
     106 
     107    /// \brief The number of items stored in the heap. 
     108    /// 
     109    /// This function returns the number of items stored in the heap. 
     110    int size() const { return _data.size(); } 
     111 
     112    /// \brief Check if the heap is empty. 
     113    /// 
     114    /// This function returns \c true if the heap is empty. 
     115    bool empty() const { return _data.empty(); } 
     116 
     117    /// \brief Make the heap empty. 
     118    /// 
     119    /// This functon makes the heap empty. 
     120    /// It does not change the cross reference map. If you want to reuse 
     121    /// a heap that is not surely empty, you should first clear it and 
     122    /// then you should set the cross reference map to \c PRE_HEAP 
     123    /// for each item. 
     124    void clear() { _data.clear(); } 
    126125 
    127126  private: 
     
    130129 
    131130    bool less(const Pair &p1, const Pair &p2) const { 
    132       return comp(p1.second, p2.second); 
    133     } 
    134  
    135     int find_min(const int child, const int length) { 
     131      return _comp(p1.second, p2.second); 
     132    } 
     133 
     134    int findMin(const int child, const int length) { 
    136135      int min=child; 
    137136      if( child+3<length ) { 
    138         if( less(data[child+3], data[min]) ) 
     137        if( less(_data[child+3], _data[min]) ) 
    139138          min=child+3; 
    140         if( less(data[child+2], data[min]) ) 
     139        if( less(_data[child+2], _data[min]) ) 
    141140          min=child+2; 
    142         if( less(data[child+1], data[min]) ) 
     141        if( less(_data[child+1], _data[min]) ) 
    143142          min=child+1; 
    144143      } 
    145144      else if( child+2<length ) { 
    146         if( less(data[child+2], data[min]) ) 
     145        if( less(_data[child+2], _data[min]) ) 
    147146          min=child+2; 
    148         if( less(data[child+1], data[min]) ) 
     147        if( less(_data[child+1], _data[min]) ) 
    149148          min=child+1; 
    150149      } 
    151150      else if( child+1<length ) { 
    152         if( less(data[child+1], data[min]) ) 
     151        if( less(_data[child+1], _data[min]) ) 
    153152          min=child+1; 
    154153      } 
     
    156155    } 
    157156 
    158     void bubble_up(int hole, Pair p) { 
     157    void bubbleUp(int hole, Pair p) { 
    159158      int par = parent(hole); 
    160       while( hole>0 && less(p,data[par]) ) { 
    161         move(data[par],hole); 
     159      while( hole>0 && less(p,_data[par]) ) { 
     160        move(_data[par],hole); 
    162161        hole = par; 
    163162        par = parent(hole); 
     
    166165    } 
    167166 
    168     void bubble_down(int hole, Pair p, int length) { 
     167    void bubbleDown(int hole, Pair p, int length) { 
    169168      int child = firstChild(hole); 
    170169      while( child<length && length>1 ) { 
    171         child = find_min(child,length); 
    172         if( !less(data[child], p) ) 
     170        child = findMin(child,length); 
     171        if( !less(_data[child], p) ) 
    173172          goto ok; 
    174         move(data[child], hole); 
     173        move(_data[child], hole); 
    175174        hole = child; 
    176175        child = firstChild(hole); 
     
    181180 
    182181    void move(const Pair &p, int i) { 
    183       data[i] = p; 
    184       iim.set(p.first, i); 
     182      _data[i] = p; 
     183      _iim.set(p.first, i); 
    185184    } 
    186185 
    187186  public: 
    188  
    189187    /// \brief Insert a pair of item and priority into the heap. 
    190188    /// 
    191     /// Adds \c p.first to the heap with priority \c p.second. 
     189    /// This function inserts \c p.first to the heap with priority 
     190    /// \c p.second. 
    192191    /// \param p The pair to insert. 
     192    /// \pre \c p.first must not be stored in the heap. 
    193193    void push(const Pair &p) { 
    194       int n = data.size(); 
    195       data.resize(n+1); 
    196       bubble_up(n, p); 
    197     } 
    198  
    199     /// \brief Insert an item into the heap with the given heap. 
    200     /// 
    201     /// Adds \c i to the heap with priority \c p. 
     194      int n = _data.size(); 
     195      _data.resize(n+1); 
     196      bubbleUp(n, p); 
     197    } 
     198 
     199    /// \brief Insert an item into the heap with the given priority. 
     200    /// 
     201    /// This function inserts the given item into the heap with the 
     202    /// given priority. 
    202203    /// \param i The item to insert. 
    203204    /// \param p The priority of the item. 
     205    /// \pre \e i must not be stored in the heap. 
    204206    void push(const Item &i, const Prio &p) { push(Pair(i,p)); } 
    205207 
    206     /// \brief Returns the item with minimum priority relative to \c Compare. 
    207     /// 
    208     /// This method returns the item with minimum priority relative to \c 
    209     /// Compare. 
    210     /// \pre The heap must be nonempty. 
    211     Item top() const { return data[0].first; } 
    212  
    213     /// \brief Returns the minimum priority relative to \c Compare. 
    214     /// 
    215     /// It returns the minimum priority relative to \c Compare. 
    216     /// \pre The heap must be nonempty. 
    217     Prio prio() const { return data[0].second; } 
    218  
    219     /// \brief Deletes the item with minimum priority relative to \c Compare. 
    220     /// 
    221     /// This method deletes the item with minimum priority relative to \c 
    222     /// Compare from the heap. 
     208    /// \brief Return the item having minimum priority. 
     209    /// 
     210    /// This function returns the item having minimum priority. 
     211    /// \pre The heap must be non-empty. 
     212    Item top() const { return _data[0].first; } 
     213 
     214    /// \brief The minimum priority. 
     215    /// 
     216    /// This function returns the minimum priority. 
     217    /// \pre The heap must be non-empty. 
     218    Prio prio() const { return _data[0].second; } 
     219 
     220    /// \brief Remove the item having minimum priority. 
     221    /// 
     222    /// This function removes the item having minimum priority. 
    223223    /// \pre The heap must be non-empty. 
    224224    void pop() { 
    225       int n = data.size()-1; 
    226       iim.set(data[0].first, POST_HEAP); 
    227       if (n>0) bubble_down(0, data[n], n); 
    228       data.pop_back(); 
    229     } 
    230  
    231     /// \brief Deletes \c i from the heap. 
    232     /// 
    233     /// This method deletes item \c i from the heap. 
    234     /// \param i The item to erase. 
    235     /// \pre The item should be in the heap. 
     225      int n = _data.size()-1; 
     226      _iim.set(_data[0].first, POST_HEAP); 
     227      if (n>0) bubbleDown(0, _data[n], n); 
     228      _data.pop_back(); 
     229    } 
     230 
     231    /// \brief Remove the given item from the heap. 
     232    /// 
     233    /// This function removes the given item from the heap if it is 
     234    /// already stored. 
     235    /// \param i The item to delete. 
     236    /// \pre \e i must be in the heap. 
    236237    void erase(const Item &i) { 
    237       int h = iim[i]; 
    238       int n = data.size()-1; 
    239       iim.set(data[h].first, POST_HEAP); 
     238      int h = _iim[i]; 
     239      int n = _data.size()-1; 
     240      _iim.set(_data[h].first, POST_HEAP); 
    240241      if( h<n ) { 
    241         if( less(data[parent(h)], data[n]) ) 
    242           bubble_down(h, data[n], n); 
     242        if( less(_data[parent(h)], _data[n]) ) 
     243          bubbleDown(h, _data[n], n); 
    243244        else 
    244           bubble_up(h, data[n]); 
    245       } 
    246       data.pop_back(); 
    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. 
     245          bubbleUp(h, _data[n]); 
     246      } 
     247      _data.pop_back(); 
     248    } 
     249 
     250    /// \brief The priority of the given item. 
     251    /// 
     252    /// This function returns the priority of the given item. 
     253    /// \param i The item. 
     254    /// \pre \e i must be in the heap. 
    254255    Prio operator[](const Item &i) const { 
    255       int idx = iim[i]; 
    256       return data[idx].second; 
    257     } 
    258  
    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. 
     256      int idx = _iim[i]; 
     257      return _data[idx].second; 
     258    } 
     259 
     260    /// \brief Set the priority of an item or insert it, if it is 
     261    /// not stored in the heap. 
     262    /// 
     263    /// This method sets the priority of the given item if it is 
     264    /// already stored in the heap. Otherwise it inserts the given 
     265    /// item into the heap with the given priority. 
    264266    /// \param i The item. 
    265267    /// \param p The priority. 
    266268    void set(const Item &i, const Prio &p) { 
    267       int idx = iim[i]; 
     269      int idx = _iim[i]; 
    268270      if( idx < 0 ) 
    269271        push(i,p); 
    270       else if( comp(p, data[idx].second) ) 
    271         bubble_up(idx, Pair(i,p)); 
     272      else if( _comp(p, _data[idx].second) ) 
     273        bubbleUp(idx, Pair(i,p)); 
    272274      else 
    273         bubble_down(idx, Pair(i,p), data.size()); 
    274     } 
    275  
    276     /// \brief Decreases the priority of \c i to \c p. 
    277     /// 
    278     /// This method decreases the priority of item \c i to \c p. 
    279     /// \pre \c i must be stored in the heap with priority at least \c 
    280     /// p relative to \c Compare. 
     275        bubbleDown(idx, Pair(i,p), _data.size()); 
     276    } 
     277 
     278    /// \brief Decrease the priority of an item to the given value. 
     279    /// 
     280    /// This function decreases the priority of an item to the given value. 
    281281    /// \param i The item. 
    282282    /// \param p The priority. 
     283    /// \pre \e i must be stored in the heap with priority at least \e p. 
    283284    void decrease(const Item &i, const Prio &p) { 
    284       int idx = iim[i]; 
    285       bubble_up(idx, Pair(i,p)); 
    286     } 
    287  
    288     /// \brief Increases the priority of \c i to \c p. 
    289     /// 
    290     /// This method sets the priority of item \c i to \c p. 
    291     /// \pre \c i must be stored in the heap with priority at most \c 
    292     /// p relative to \c Compare. 
     285      int idx = _iim[i]; 
     286      bubbleUp(idx, Pair(i,p)); 
     287    } 
     288 
     289    /// \brief Increase the priority of an item to the given value. 
     290    /// 
     291    /// This function increases the priority of an item to the given value. 
    293292    /// \param i The item. 
    294293    /// \param p The priority. 
     294    /// \pre \e i must be stored in the heap with priority at most \e p. 
    295295    void increase(const Item &i, const Prio &p) { 
    296       int idx = iim[i]; 
    297       bubble_down(idx, Pair(i,p), data.size()); 
    298     } 
    299  
    300     /// \brief Returns if \c item is in, has already been in, or has 
    301     /// never been in the heap. 
    302     /// 
    303     /// This method returns PRE_HEAP if \c item has never been in the 
    304     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP 
    305     /// otherwise. In the latter case it is possible that \c item will 
    306     /// get back to the heap again. 
     296      int idx = _iim[i]; 
     297      bubbleDown(idx, Pair(i,p), _data.size()); 
     298    } 
     299 
     300    /// \brief Return the state of an item. 
     301    /// 
     302    /// This method returns \c PRE_HEAP if the given item has never 
     303    /// been in the heap, \c IN_HEAP if it is in the heap at the moment, 
     304    /// and \c POST_HEAP otherwise. 
     305    /// In the latter case it is possible that the item will get back 
     306    /// to the heap again. 
    307307    /// \param i The item. 
    308308    State state(const Item &i) const { 
    309       int s = iim[i]; 
     309      int s = _iim[i]; 
    310310      if (s>=0) s=0; 
    311311      return State(s); 
    312312    } 
    313313 
    314     /// \brief Sets the state of the \c item in the heap. 
    315     /// 
    316     /// Sets the state of the \c item in the heap. It can be used to 
    317     /// manually clear the heap when it is important to achive the 
    318     /// better time complexity. 
     314    /// \brief Set the state of an item in the heap. 
     315    /// 
     316    /// This function sets the state of the given item in the heap. 
     317    /// It can be used to manually clear the heap when it is important 
     318    /// to achive better time complexity. 
    319319    /// \param i The item. 
    320320    /// \param st The state. It should not be \c IN_HEAP. 
     
    324324        case PRE_HEAP: 
    325325          if (state(i) == IN_HEAP) erase(i); 
    326           iim[i] = st; 
     326          _iim[i] = st; 
    327327          break; 
    328328        case IN_HEAP: 
     
    331331    } 
    332332 
    333     /// \brief Replaces an item in the heap. 
    334     /// 
    335     /// The \c i item is replaced with \c j item. The \c i item should 
    336     /// be in the heap, while the \c j should be out of the heap. The 
    337     /// \c i item will out of the heap and \c j will be in the heap 
    338     /// with the same prioriority as prevoiusly the \c i item. 
     333    /// \brief Replace an item in the heap. 
     334    /// 
     335    /// This function replaces item \c i with item \c j. 
     336    /// Item \c i must be in the heap, while \c j must be out of the heap. 
     337    /// After calling this method, item \c i will be out of the 
     338    /// heap and \c j will be in the heap with the same prioriority 
     339    /// as item \c i had before. 
    339340    void replace(const Item& i, const Item& j) { 
    340       int idx = iim[i]; 
    341       iim.set(i, iim[j]); 
    342       iim.set(j, idx); 
    343       data[idx].first = j; 
     341      int idx = _iim[i]; 
     342      _iim.set(i, _iim[j]); 
     343      _iim.set(j, idx); 
     344      _data[idx].first = j; 
    344345    } 
    345346 
  • lemon/kary_heap.h

    r748 r750  
    1 /* -*- C++ -*- 
    2  * 
    3  * This file is a part of LEMON, a generic C++ optimization library 
    4  * 
    5  * Copyright (C) 2003-2008 
     1/* -*- mode: C++; indent-tabs-mode: nil; -*- 
     2 * 
     3 * This file is a part of LEMON, a generic C++ optimization library. 
     4 * 
     5 * Copyright (C) 2003-2009 
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES). 
     
    2020#define LEMON_KARY_HEAP_H 
    2121 
    22 ///\ingroup auxdat 
     22///\ingroup heaps 
    2323///\file 
    24 ///\brief Kary Heap implementation. 
    25  
    26 #include <iostream> 
     24///\brief Fourary heap implementation. 
     25 
    2726#include <vector> 
    2827#include <utility> 
     
    3130namespace lemon { 
    3231 
    33   ///\ingroup auxdat 
    34   /// 
    35   ///\brief A Kary Heap implementation. 
    36   /// 
    37   ///This class implements the \e Kary \e heap data structure. A \e heap 
    38   ///is a data structure for storing items with specified values called \e 
    39   ///priorities in such a way that finding the item with minimum priority is 
    40   ///efficient. \c Compare specifies the ordering of the priorities. In a heap 
    41   ///one can change the priority of an item, add or erase an item, etc. 
    42   /// 
    43   ///\param _Prio Type of the priority of the items. 
    44   ///\param _ItemIntMap A read and writable Item int map, used internally 
    45   ///to handle the cross references. 
    46   ///\param _Compare A class for the ordering of the priorities. The 
    47   ///default is \c std::less<_Prio>. 
    48   /// 
    49   ///\sa FibHeap 
    50   ///\sa Dijkstra 
    51   ///\author Dorian Batha 
    52  
    53   template <typename _Prio, typename _ItemIntMap, 
    54             typename _Compare = std::less<_Prio> > 
    55  
     32  /// \ingroup heaps 
     33  /// 
     34  ///\brief K-ary heap data structure. 
     35  /// 
     36  /// This class implements the \e K-ary \e heap data structure. 
     37  /// It fully conforms to the \ref concepts::Heap "heap concept". 
     38  /// 
     39  /// The \ref KaryHeap "K-ary heap" is a generalization of the 
     40  /// \ref BinHeap "binary heap" structure, its nodes have at most 
     41  /// \c K children, instead of two. 
     42  /// \ref BinHeap and \ref FouraryHeap are specialized implementations 
     43  /// of this structure for <tt>K=2</tt> and <tt>K=4</tt>, respectively. 
     44  /// 
     45  /// \tparam PR Type of the priorities of the items. 
     46  /// \tparam IM A read-writable item map with \c int values, used 
     47  /// internally to handle the cross references. 
     48  /// \tparam CMP A functor class for comparing the priorities. 
     49  /// The default is \c std::less<PR>. 
     50  /// 
     51  ///\sa BinHeap 
     52  ///\sa FouraryHeap 
     53#ifdef DOXYGEN 
     54  template <typename PR, typename IM, typename CMP> 
     55#else 
     56  template <typename PR, typename IM, typename CMP = std::less<PR> > 
     57#endif 
    5658  class KaryHeap { 
    57  
    5859  public: 
    59     ///\e 
    60     typedef _ItemIntMap ItemIntMap; 
    61     ///\e 
    62     typedef _Prio Prio; 
    63     ///\e 
     60    /// Type of the item-int map. 
     61    typedef IM ItemIntMap; 
     62    /// Type of the priorities. 
     63    typedef PR Prio; 
     64    /// Type of the items stored in the heap. 
    6465    typedef typename ItemIntMap::Key Item; 
    65     ///\e 
     66    /// Type of the item-priority pairs. 
    6667    typedef std::pair<Item,Prio> Pair; 
    67     ///\e 
    68     typedef _Compare Compare; 
    69     ///\e 
    70  
    71     /// \brief Type to represent the items states. 
    72     /// 
    73     /// Each Item element have a state associated to it. It may be "in heap", 
    74     /// "pre heap" or "post heap". The latter two are indifferent from the 
     68    /// Functor type for comparing the priorities. 
     69    typedef CMP Compare; 
     70 
     71    /// \brief Type to represent the states of the items. 
     72    /// 
     73    /// Each item has a state associated to it. It can be "in heap", 
     74    /// "pre-heap" or "post-heap". The latter two are indifferent from the 
    7575    /// heap's point of view, but may be useful to the user. 
    7676    /// 
    77     /// The ItemIntMap \e should be initialized in such way that it maps 
    78     /// PRE_HEAP (-1) to any element to be put in the heap... 
     77    /// The item-int map must be initialized in such way that it assigns 
     78    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. 
    7979    enum State { 
    80       IN_HEAP = 0, 
    81       PRE_HEAP = -1, 
    82       POST_HEAP = -2 
     80      IN_HEAP = 0,    ///< = 0. 
     81      PRE_HEAP = -1,  ///< = -1. 
     82      POST_HEAP = -2  ///< = -2. 
    8383    }; 
    8484 
    8585  private: 
    86     std::vector<Pair> data; 
    87     Compare comp; 
    88     ItemIntMap &iim; 
    89     int K; 
     86    std::vector<Pair> _data; 
     87    Compare _comp; 
     88    ItemIntMap &_iim; 
     89    int _K; 
    9090 
    9191  public: 
    92     /// \brief The constructor. 
    93     /// 
    94     /// The constructor. 
    95     /// \param _iim should be given to the constructor, since it is used 
    96     /// internally to handle the cross references. The value of the map 
    97     /// should be PRE_HEAP (-1) for each element. 
    98     explicit KaryHeap(ItemIntMap &_iim, const int &_K=32) : iim(_iim), K(_K) {} 
    99  
    100     /// \brief The constructor. 
    101     /// 
    102     /// The constructor. 
    103     /// \param _iim should be given to the constructor, since it is used 
    104     /// internally to handle the cross references. The value of the map 
    105     /// should be PRE_HEAP (-1) for each element. 
    106     /// 
    107     /// \param _comp The comparator function object. 
    108     KaryHeap(ItemIntMap &_iim, const Compare &_comp, const int &_K=32) 
    109       : iim(_iim), comp(_comp), K(_K) {} 
    110  
    111  
    112     /// The number of items stored in the heap. 
    113     /// 
    114     /// \brief Returns the number of items stored in the heap. 
    115     int size() const { return data.size(); } 
    116  
    117     /// \brief Checks if the heap stores no items. 
    118     /// 
    119     /// Returns \c true if and only if the heap stores no items. 
    120     bool empty() const { return data.empty(); } 
    121  
    122     /// \brief Make empty this heap. 
    123     /// 
    124     /// Make empty this heap. It does not change the cross reference map. 
    125     /// If you want to reuse what is not surely empty you should first clear 
    126     /// the heap and after that you should set the cross reference map for 
    127     /// each item to \c PRE_HEAP. 
    128     void clear() { data.clear(); } 
     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    explicit KaryHeap(ItemIntMap &map, int K=32) : _iim(map), _K(K) {} 
     99 
     100    /// \brief Constructor. 
     101    /// 
     102    /// Constructor. 
     103    /// \param map A map that assigns \c int values to the items. 
     104    /// It is used internally to handle the cross references. 
     105    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 
     106    /// \param comp The function object used for comparing the priorities. 
     107    KaryHeap(ItemIntMap &map, const Compare &comp, int K=32) 
     108      : _iim(map), _comp(comp), _K(K) {} 
     109 
     110    /// \brief The number of items stored in the heap. 
     111    /// 
     112    /// This function returns the number of items stored in the heap. 
     113    int size() const { return _data.size(); } 
     114 
     115    /// \brief Check if the heap is empty. 
     116    /// 
     117    /// This function returns \c true if the heap is empty. 
     118    bool empty() const { return _data.empty(); } 
     119 
     120    /// \brief Make the heap empty. 
     121    /// 
     122    /// This functon makes the heap empty. 
     123    /// It does not change the cross reference map. If you want to reuse 
     124    /// a heap that is not surely empty, you should first clear it and 
     125    /// then you should set the cross reference map to \c PRE_HEAP 
     126    /// for each item. 
     127    void clear() { _data.clear(); } 
    129128 
    130129  private: 
    131     int parent(int i) { return (i-1)/K; } 
    132     int first_child(int i) { return K*i+1; } 
     130    int parent(int i) { return (i-1)/_K; } 
     131    int firstChild(int i) { return _K*i+1; } 
    133132 
    134133    bool less(const Pair &p1, const Pair &p2) const { 
    135       return comp(p1.second, p2.second); 
    136     } 
    137  
    138     int find_min(const int child, const int length) { 
     134      return _comp(p1.second, p2.second); 
     135    } 
     136 
     137    int findMin(const int child, const int length) { 
    139138      int min=child, i=1; 
    140       while( i<K && child+i<length ) { 
    141         if( less(data[child+i], data[min]) ) 
     139      while( i<_K && child+i<length ) { 
     140        if( less(_data[child+i], _data[min]) ) 
    142141          min=child+i; 
    143142        ++i; 
     
    146145    } 
    147146 
    148     void bubble_up(int hole, Pair p) { 
     147    void bubbleUp(int hole, Pair p) { 
    149148      int par = parent(hole); 
    150       while( hole>0 && less(p,data[par]) ) { 
    151         move(data[par],hole); 
     149      while( hole>0 && less(p,_data[par]) ) { 
     150        move(_data[par],hole); 
    152151        hole = par; 
    153152        par = parent(hole); 
     
    156155    } 
    157156 
    158     void bubble_down(int hole, Pair p, int length) { 
     157    void bubbleDown(int hole, Pair p, int length) { 
    159158      if( length>1 ) { 
    160         int child = first_child(hole); 
     159        int child = firstChild(hole); 
    161160        while( child<length ) { 
    162           child = find_min(child, length); 
    163           if( !less(data[child], p) ) 
     161          child = findMin(child, length); 
     162          if( !less(_data[child], p) ) 
    164163            goto ok; 
    165           move(data[child], hole); 
     164          move(_data[child], hole); 
    166165          hole = child; 
    167           child = first_child(hole); 
     166          child = firstChild(hole); 
    168167        } 
    169168      } 
     
    173172 
    174173    void move(const Pair &p, int i) { 
    175       data[i] = p; 
    176       iim.set(p.first, i); 
     174      _data[i] = p; 
     175      _iim.set(p.first, i); 
    177176    } 
    178177 
     
    180179    /// \brief Insert a pair of item and priority into the heap. 
    181180    /// 
    182     /// Adds \c p.first to the heap with priority \c p.second. 
     181    /// This function inserts \c p.first to the heap with priority 
     182    /// \c p.second. 
    183183    /// \param p The pair to insert. 
     184    /// \pre \c p.first must not be stored in the heap. 
    184185    void push(const Pair &p) { 
    185       int n = data.size(); 
    186       data.resize(n+1); 
    187       bubble_up(n, p); 
    188     } 
    189  
    190     /// \brief Insert an item into the heap with the given heap. 
    191     /// 
    192     /// Adds \c i to the heap with priority \c p. 
     186      int n = _data.size(); 
     187      _data.resize(n+1); 
     188      bubbleUp(n, p); 
     189    } 
     190 
     191    /// \brief Insert an item into the heap with the given priority. 
     192    /// 
     193    /// This function inserts the given item into the heap with the 
     194    /// given priority. 
    193195    /// \param i The item to insert. 
    194196    /// \param p The priority of the item. 
     197    /// \pre \e i must not be stored in the heap. 
    195198    void push(const Item &i, const Prio &p) { push(Pair(i,p)); } 
    196199 
    197     /// \brief Returns the item with minimum priority relative to \c Compare. 
    198     /// 
    199     /// This method returns the item with minimum priority relative to \c 
    200     /// Compare. 
    201     /// \pre The heap must be nonempty. 
    202     Item top() const { return data[0].first; } 
    203  
    204     /// \brief Returns the minimum priority relative to \c Compare. 
    205     /// 
    206     /// It returns the minimum priority relative to \c Compare. 
    207     /// \pre The heap must be nonempty. 
    208     Prio prio() const { return data[0].second; } 
    209  
    210     /// \brief Deletes the item with minimum priority relative to \c Compare. 
    211     /// 
    212     /// This method deletes the item with minimum priority relative to \c 
    213     /// Compare from the heap. 
     200    /// \brief Return the item having minimum priority. 
     201    /// 
     202    /// This function returns the item having minimum priority. 
     203    /// \pre The heap must be non-empty. 
     204    Item top() const { return _data[0].first; } 
     205 
     206    /// \brief The minimum priority. 
     207    /// 
     208    /// This function returns the minimum priority. 
     209    /// \pre The heap must be non-empty. 
     210    Prio prio() const { return _data[0].second; } 
     211 
     212    /// \brief Remove the item having minimum priority. 
     213    /// 
     214    /// This function removes the item having minimum priority. 
    214215    /// \pre The heap must be non-empty. 
    215216    void pop() { 
    216       int n = data.size()-1; 
    217       iim.set(data[0].first, POST_HEAP); 
    218       if (n>0) bubble_down(0, data[n], n); 
    219       data.pop_back(); 
    220     } 
    221  
    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. 
     217      int n = _data.size()-1; 
     218      _iim.set(_data[0].first, POST_HEAP); 
     219      if (n>0) bubbleDown(0, _data[n], n); 
     220      _data.pop_back(); 
     221    } 
     222 
     223    /// \brief Remove the given item from the heap. 
     224    /// 
     225    /// This function removes the given item from the heap if it is 
     226    /// already stored. 
     227    /// \param i The item to delete. 
     228    /// \pre \e i must be in the heap. 
    227229    void erase(const Item &i) { 
    228       int h = iim[i]; 
    229       int n = data.size()-1; 
    230       iim.set(data[h].first, POST_HEAP); 
     230      int h = _iim[i]; 
     231      int n = _data.size()-1; 
     232      _iim.set(_data[h].first, POST_HEAP); 
    231233      if( h<n ) { 
    232         if( less(data[parent(h)], data[n]) ) 
    233           bubble_down(h, data[n], n); 
     234        if( less(_data[parent(h)], _data[n]) ) 
     235          bubbleDown(h, _data[n], n); 
    234236        else 
    235           bubble_up(h, data[n]); 
    236       } 
    237       data.pop_back(); 
    238     } 
    239  
    240  
    241     /// \brief Returns the priority of \c i. 
    242     /// 
    243     /// This function returns the priority of item \c i. 
    244     /// \pre \c i must be in the heap. 
    245     /// \param i The item. 
     237          bubbleUp(h, _data[n]); 
     238      } 
     239      _data.pop_back(); 
     240    } 
     241 
     242    /// \brief The priority of the given item. 
     243    /// 
     244    /// This function returns the priority of the given item. 
     245    /// \param i The item. 
     246    /// \pre \e i must be in the heap. 
    246247    Prio operator[](const Item &i) const { 
    247       int idx = iim[i]; 
    248       return data[idx].second; 
    249     } 
    250  
    251     /// \brief \c i gets to the heap with priority \c p independently 
    252     /// if \c i was already there. 
    253     /// 
    254     /// This method calls \ref push(\c i, \c p) if \c i is not stored 
    255     /// in the heap and sets the priority of \c i to \c p otherwise. 
     248      int idx = _iim[i]; 
     249      return _data[idx].second; 
     250    } 
     251 
     252    /// \brief Set the priority of an item or insert it, if it is 
     253    /// not stored in the heap. 
     254    /// 
     255    /// This method sets the priority of the given item if it is 
     256    /// already stored in the heap. Otherwise it inserts the given 
     257    /// item into the heap with the given priority. 
    256258    /// \param i The item. 
    257259    /// \param p The priority. 
    258260    void set(const Item &i, const Prio &p) { 
    259       int idx = iim[i]; 
     261      int idx = _iim[i]; 
    260262      if( idx<0 ) 
    261263        push(i,p); 
    262       else if( comp(p, data[idx].second) ) 
    263         bubble_up(idx, Pair(i,p)); 
     264      else if( _comp(p, _data[idx].second) ) 
     265        bubbleUp(idx, Pair(i,p)); 
    264266      else 
    265         bubble_down(idx, Pair(i,p), data.size()); 
    266     } 
    267  
    268     /// \brief Decreases the priority of \c i to \c p. 
    269     /// 
    270     /// This method decreases the priority of item \c i to \c p. 
    271     /// \pre \c i must be stored in the heap with priority at least \c 
    272     /// p relative to \c Compare. 
     267        bubbleDown(idx, Pair(i,p), _data.size()); 
     268    } 
     269 
     270    /// \brief Decrease the priority of an item to the given value. 
     271    /// 
     272    /// This function decreases the priority of an item to the given value. 
    273273    /// \param i The item. 
    274274    /// \param p The priority. 
     275    /// \pre \e i must be stored in the heap with priority at least \e p. 
    275276    void decrease(const Item &i, const Prio &p) { 
    276       int idx = iim[i]; 
    277       bubble_up(idx, Pair(i,p)); 
    278     } 
    279  
    280     /// \brief Increases the priority of \c i to \c p. 
    281     /// 
    282     /// This method sets the priority of item \c i to \c p. 
    283     /// \pre \c i must be stored in the heap with priority at most \c 
    284     /// p relative to \c Compare. 
     277      int idx = _iim[i]; 
     278      bubbleUp(idx, Pair(i,p)); 
     279    } 
     280 
     281    /// \brief Increase the priority of an item to the given value. 
     282    /// 
     283    /// This function increases the priority of an item to the given value. 
    285284    /// \param i The item. 
    286285    /// \param p The priority. 
     286    /// \pre \e i must be stored in the heap with priority at most \e p. 
    287287    void increase(const Item &i, const Prio &p) { 
    288       int idx = iim[i]; 
    289       bubble_down(idx, Pair(i,p), data.size()); 
    290     } 
    291  
    292     /// \brief Returns if \c item is in, has already been in, or has 
    293     /// never been in the heap. 
    294     /// 
    295     /// This method returns PRE_HEAP if \c item has never been in the 
    296     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP 
    297     /// otherwise. In the latter case it is possible that \c item will 
    298     /// get back to the heap again. 
     288      int idx = _iim[i]; 
     289      bubbleDown(idx, Pair(i,p), _data.size()); 
     290    } 
     291 
     292    /// \brief Return the state of an item. 
     293    /// 
     294    /// This method returns \c PRE_HEAP if the given item has never 
     295    /// been in the heap, \c IN_HEAP if it is in the heap at the moment, 
     296    /// and \c POST_HEAP otherwise. 
     297    /// In the latter case it is possible that the item will get back 
     298    /// to the heap again. 
    299299    /// \param i The item. 
    300300    State state(const Item &i) const { 
    301       int s = iim[i]; 
     301      int s = _iim[i]; 
    302302      if (s>=0) s=0; 
    303303      return State(s); 
    304304    } 
    305305 
    306     /// \brief Sets the state of the \c item in the heap. 
    307     /// 
    308     /// Sets the state of the \c item in the heap. It can be used to 
    309     /// manually clear the heap when it is important to achive the 
    310     /// better time complexity. 
     306    /// \brief Set the state of an item in the heap. 
     307    /// 
     308    /// This function sets the state of the given item in the heap. 
     309    /// It can be used to manually clear the heap when it is important 
     310    /// to achive better time complexity. 
    311311    /// \param i The item. 
    312312    /// \param st The state. It should not be \c IN_HEAP. 
    313313    void state(const Item& i, State st) { 
    314314      switch (st) { 
    315       case POST_HEAP: 
    316       case PRE_HEAP: 
    317         if (state(i) == IN_HEAP) erase(i); 
    318         iim[i] = st; 
    319         break; 
    320       case IN_HEAP: 
    321         break; 
    322       } 
    323     } 
    324  
    325     /// \brief Replaces an item in the heap. 
    326     /// 
    327     /// The \c i item is replaced with \c j item. The \c i item should 
    328     /// be in the heap, while the \c j should be out of the heap. The 
    329     /// \c i item will out of the heap and \c j will be in the heap 
    330     /// with the same prioriority as prevoiusly the \c i item. 
     315        case POST_HEAP: 
     316        case PRE_HEAP: 
     317          if (state(i) == IN_HEAP) erase(i); 
     318          _iim[i] = st; 
     319          break; 
     320        case IN_HEAP: 
     321          break; 
     322      } 
     323    } 
     324 
     325    /// \brief Replace an item in the heap. 
     326    /// 
     327    /// This function replaces item \c i with item \c j. 
     328    /// Item \c i must be in the heap, while \c j must be out of the heap. 
     329    /// After calling this method, item \c i will be out of the 
     330    /// heap and \c j will be in the heap with the same prioriority 
     331    /// as item \c i had before. 
    331332    void replace(const Item& i, const Item& j) { 
    332       int idx=iim[i]; 
    333       iim.set(i, iim[j]); 
    334       iim.set(j, idx); 
    335       data[idx].first=j; 
     333      int idx=_iim[i]; 
     334      _iim.set(i, _iim[j]); 
     335      _iim.set(j, idx); 
     336      _data[idx].first=j; 
    336337    } 
    337338 
  • lemon/pairing_heap.h

    r749 r750  
    1 /* -*- C++ -*- 
     1/* -*- mode: C++; indent-tabs-mode: nil; -*- 
    22 * 
    3  * This file is a part of LEMON, a generic C++ optimization library 
     3 * This file is a part of LEMON, a generic C++ optimization library. 
    44 * 
    5  * Copyright (C) 2003-2008 
     5 * Copyright (C) 2003-2009 
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES). 
     
    2121 
    2222///\file 
    23 ///\ingroup auxdat 
    24 ///\brief Pairing Heap implementation. 
     23///\ingroup heaps 
     24///\brief Pairing heap implementation. 
    2525 
    2626#include <vector> 
     27#include <utility> 
    2728#include <functional> 
    2829#include <lemon/math.h> 
     
    3031namespace lemon { 
    3132 
    32   /// \ingroup auxdat 
     33  /// \ingroup heaps 
    3334  /// 
    3435  ///\brief Pairing Heap. 
    3536  /// 
    36   ///This class implements the \e Pairing \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 Compare specifies the ordering of the priorities. In a heap 
    40   ///one can change the priority of an item, add or erase an item, etc. 
     37  /// This class implements the \e pairing \e heap data structure. 
     38  /// It fully conforms to the \ref concepts::Heap "heap concept". 
    4139  /// 
    42   ///The methods \ref increase and \ref erase are not efficient in a Pairing 
    43   ///heap. In case of many calls to these operations, it is better to use a 
    44   ///\ref BinHeap "binary heap". 
     40  /// The methods \ref increase() and \ref erase() are not efficient 
     41  /// in a pairing heap. In case of many calls of these operations, 
     42  /// it is better to use other heap structure, e.g. \ref BinHeap 
     43  /// "binary heap". 
    4544  /// 
    46   ///\param _Prio Type of the priority of the items. 
    47   ///\param _ItemIntMap A read and writable Item int map, used internally 
    48   ///to handle the cross references. 
    49   ///\param _Compare A class for the ordering of the priorities. The 
    50   ///default is \c std::less<_Prio>. 
    51   /// 
    52   ///\sa BinHeap 
    53   ///\sa Dijkstra 
    54   ///\author Dorian Batha 
    55  
     45  /// \tparam PR Type of the priorities of the items. 
     46  /// \tparam IM A read-writable item map with \c int values, used 
     47  /// internally to handle the cross references. 
     48  /// \tparam CMP A functor class for comparing the priorities. 
     49  /// The default is \c std::less<PR>. 
    5650#ifdef DOXYGEN 
    57   template <typename _Prio, 
    58             typename _ItemIntMap, 
    59             typename _Compare> 
     51  template <typename PR, typename IM, typename CMP> 
    6052#else 
    61   template <typename _Prio, 
    62             typename _ItemIntMap, 
    63             typename _Compare = std::less<_Prio> > 
     53  template <typename PR, typename IM, typename CMP = std::less<PR> > 
    6454#endif 
    6555  class PairingHeap { 
    6656  public: 
    67     typedef _ItemIntMap ItemIntMap; 
    68     typedef _Prio Prio; 
     57    /// Type of the item-int map. 
     58    typedef IM ItemIntMap; 
     59    /// Type of the priorities. 
     60    typedef PR Prio; 
     61    /// Type of the items stored in the heap. 
    6962    typedef typename ItemIntMap::Key Item; 
    70     typedef std::pair<Item,Prio> Pair; 
    71     typedef _Compare Compare; 
     63    /// Functor type for comparing the priorities. 
     64    typedef CMP Compare; 
     65 
     66    /// \brief Type to represent the states of the items. 
     67    /// 
     68    /// Each item has a state associated to it. It can be "in heap", 
     69    /// "pre-heap" or "post-heap". The latter two are indifferent from the 
     70    /// heap's point of view, but may be useful to the user. 
     71    /// 
     72    /// The item-int map must be initialized in such way that it assigns 
     73    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. 
     74    enum State { 
     75      IN_HEAP = 0,    ///< = 0. 
     76      PRE_HEAP = -1,  ///< = -1. 
     77      POST_HEAP = -2  ///< = -2. 
     78    }; 
    7279 
    7380  private: 
    7481    class store; 
    7582 
    76     std::vector<store> container; 
    77     int minimum; 
    78     ItemIntMap &iimap; 
    79     Compare comp; 
    80     int num_items; 
     83    std::vector<store> _data; 
     84    int _min; 
     85    ItemIntMap &_iim; 
     86    Compare _comp; 
     87    int _num_items; 
    8188 
    8289  public: 
    83     ///Status of the nodes 
    84     enum State { 
    85       ///The node is in the heap 
    86       IN_HEAP = 0, 
    87       ///The node has never been in the heap 
    88       PRE_HEAP = -1, 
    89       ///The node was in the heap but it got out of it 
    90       POST_HEAP = -2 
    91     }; 
    92  
    93     /// \brief The constructor 
    94     /// 
    95     /// \c _iimap should be given to the constructor, since it is 
    96     ///   used internally to handle the cross references. 
    97     explicit PairingHeap(ItemIntMap &_iimap) 
    98       : minimum(0), iimap(_iimap), num_items(0) {} 
    99  
    100     /// \brief The constructor 
    101     /// 
    102     /// \c _iimap should be given to the constructor, since it is used 
    103     /// internally to handle the cross references. \c _comp is an 
    104     /// object for ordering of the priorities. 
    105     PairingHeap(ItemIntMap &_iimap, const Compare &_comp) 
    106       : minimum(0), iimap(_iimap), comp(_comp), num_items(0) {} 
     90    /// \brief Constructor. 
     91    /// 
     92    /// Constructor. 
     93    /// \param map A map that assigns \c int values to the items. 
     94    /// It is used internally to handle the cross references. 
     95    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 
     96    explicit PairingHeap(ItemIntMap &map) 
     97      : _min(0), _iim(map), _num_items(0) {} 
     98 
     99    /// \brief Constructor. 
     100    /// 
     101    /// Constructor. 
     102    /// \param map A map that assigns \c int values to the items. 
     103    /// It is used internally to handle the cross references. 
     104    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 
     105    /// \param comp The function object used for comparing the priorities. 
     106    PairingHeap(ItemIntMap &map, const Compare &comp) 
     107      : _min(0), _iim(map), _comp(comp), _num_items(0) {} 
    107108 
    108109    /// \brief The number of items stored in the heap. 
    109110    /// 
    110     /// Returns the number of items stored in the heap. 
    111     int size() const { return num_items; } 
    112  
    113     /// \brief Checks if the heap stores no items. 
    114     /// 
    115     ///   Returns \c true if and only if the heap stores no items. 
    116     bool empty() const { return num_items==0; } 
    117  
    118     /// \brief Make empty this heap. 
    119     /// 
    120     /// Make empty this heap. It does not change the cross reference 
    121     /// map.  If you want to reuse a heap what is not surely empty you 
    122     /// should first clear the heap and after that you should set the 
    123     /// cross reference map for each item to \c PRE_HEAP. 
     111    /// This function returns the number of items stored in the heap. 
     112    int size() const { return _num_items; } 
     113 
     114    /// \brief Check if the heap is empty. 
     115    /// 
     116    /// This function returns \c true if the heap is empty. 
     117    bool empty() const { return _num_items==0; } 
     118 
     119    /// \brief Make the heap empty. 
     120    /// 
     121    /// This functon makes the heap empty. 
     122    /// It does not change the cross reference map. If you want to reuse 
     123    /// a heap that is not surely empty, you should first clear it and 
     124    /// then you should set the cross reference map to \c PRE_HEAP 
     125    /// for each item. 
    124126    void clear() { 
    125       container.clear(); 
    126       minimum = 0; 
    127       num_items = 0; 
    128     } 
    129  
    130     /// \brief \c item gets to the heap with priority \c value independently 
    131     /// if \c item was already there. 
    132     /// 
    133     /// This method calls \ref push(\c item, \c value) if \c item is not 
    134     /// stored in the heap and it calls \ref decrease(\c item, \c value) or 
    135     /// \ref increase(\c item, \c value) otherwise. 
     127      _data.clear(); 
     128      _min = 0; 
     129      _num_items = 0; 
     130    } 
     131 
     132    /// \brief Set the priority of an item or insert it, if it is 
     133    /// not stored in the heap. 
     134    /// 
     135    /// This method sets the priority of the given item if it is 
     136    /// already stored in the heap. Otherwise it inserts the given 
     137    /// item into the heap with the given priority. 
     138    /// \param item The item. 
     139    /// \param value The priority. 
    136140    void set (const Item& item, const Prio& value) { 
    137       int i=iimap[item]; 
    138       if ( i>=0 && container[i].in ) { 
    139         if ( comp(value, container[i].prio) ) decrease(item, value); 
    140         if ( comp(container[i].prio, value) ) increase(item, value); 
     141      int i=_iim[item]; 
     142      if ( i>=0 && _data[i].in ) { 
     143        if ( _comp(value, _data[i].prio) ) decrease(item, value); 
     144        if ( _comp(_data[i].prio, value) ) increase(item, value); 
    141145      } else push(item, value); 
    142146    } 
    143147 
    144     /// \brief Adds \c item to the heap with priority \c value. 
    145     /// 
    146     /// Adds \c item to the heap with priority \c value. 
    147     /// \pre \c item must not be stored in the heap. 
     148    /// \brief Insert an item into the heap with the given priority. 
     149    /// 
     150    /// This function inserts the given item into the heap with the 
     151    /// given priority. 
     152    /// \param item The item to insert. 
     153    /// \param value The priority of the item. 
     154    /// \pre \e item must not be stored in the heap. 
    148155    void push (const Item& item, const Prio& value) { 
    149       int i=iimap[item]; 
     156      int i=_iim[item]; 
    150157      if( i<0 ) { 
    151         int s=container.size(); 
    152         iimap.set(item, s); 
     158        int s=_data.size(); 
     159        _iim.set(item, s); 
    153160        store st; 
    154161        st.name=item; 
    155         container.push_back(st); 
     162        _data.push_back(st); 
    156163        i=s; 
    157164      } else { 
    158         container[i].parent=container[i].child=-1; 
    159         container[i].left_child=false; 
    160         container[i].degree=0; 
    161         container[i].in=true; 
    162       } 
    163  
    164       container[i].prio=value; 
    165  
    166       if ( num_items!=0 ) { 
    167         if ( comp( value, container[minimum].prio) ) { 
    168           fuse(i,minimum); 
    169           minimum=i; 
    170         } 
    171         else fuse(minimum,i); 
    172       } 
    173       else minimum=i; 
    174  
    175       ++num_items; 
    176     } 
    177  
    178     /// \brief Returns the item with minimum priority relative to \c Compare. 
    179     /// 
    180     /// This method returns the item with minimum priority relative to \c 
    181     /// Compare. 
    182     /// \pre The heap must be nonempty. 
    183     Item top() const { return container[minimum].name; } 
    184  
    185     /// \brief Returns the minimum priority relative to \c Compare. 
    186     /// 
    187     /// It returns the minimum priority relative to \c Compare. 
    188     /// \pre The heap must be nonempty. 
    189     const Prio& prio() const { return container[minimum].prio; } 
    190  
    191     /// \brief Returns the priority of \c item. 
    192     /// 
    193     /// It returns the priority of \c item. 
    194     /// \pre \c item must be in the heap. 
     165        _data[i].parent=_data[i].child=-1; 
     166        _data[i].left_child=false; 
     167        _data[i].degree=0; 
     168        _data[i].in=true; 
     169      } 
     170 
     171      _data[i].prio=value; 
     172 
     173      if ( _num_items!=0 ) { 
     174        if ( _comp( value, _data[_min].prio) ) { 
     175          fuse(i,_min); 
     176          _min=i; 
     177        } 
     178        else fuse(_min,i); 
     179      } 
     180      else _min=i; 
     181 
     182      ++_num_items; 
     183    } 
     184 
     185    /// \brief Return the item having minimum priority. 
     186    /// 
     187    /// This function returns the item having minimum priority. 
     188    /// \pre The heap must be non-empty. 
     189    Item top() const { return _data[_min].name; } 
     190 
     191    /// \brief The minimum priority. 
     192    /// 
     193    /// This function returns the minimum priority. 
     194    /// \pre The heap must be non-empty. 
     195    const Prio& prio() const { return _data[_min].prio; } 
     196 
     197    /// \brief The priority of the given item. 
     198    /// 
     199    /// This function returns the priority of the given item. 
     200    /// \param item The item. 
     201    /// \pre \e item must be in the heap. 
    195202    const Prio& operator[](const Item& item) const { 
    196       return container[iimap[item]].prio; 
    197     } 
    198  
    199     /// \brief Deletes the item with minimum priority relative to \c Compare. 
    200     /// 
    201     /// This method deletes the item with minimum priority relative to \c 
    202     /// Compare from the heap. 
     203      return _data[_iim[item]].prio; 
     204    } 
     205 
     206    /// \brief Remove the item having minimum priority. 
     207    /// 
     208    /// This function removes the item having minimum priority. 
    203209    /// \pre The heap must be non-empty. 
    204210    void pop() { 
    205       int TreeArray[num_items]; 
     211      int TreeArray[_num_items]; 
    206212      int i=0, num_child=0, child_right = 0; 
    207       container[minimum].in=false; 
    208  
    209       if( -1!=container[minimum].child ) { 
    210         i=container[minimum].child; 
     213      _data[_min].in=false; 
     214 
     215      if( -1!=_data[_min].child ) { 
     216        i=_data[_min].child; 
    211217        TreeArray[num_child] = i; 
    212         container[i].parent = -1; 
    213         container[minimum].child = -1; 
     218        _data[i].parent = -1; 
     219        _data[_min].child = -1; 
    214220 
    215221        ++num_child; 
    216222        int ch=-1; 
    217         while( container[i].child!=-1 ) { 
    218           ch=container[i].child; 
    219           if( container[ch].left_child && i==container[ch].parent ) { 
     223        while( _data[i].child!=-1 ) { 
     224          ch=_data[i].child; 
     225          if( _data[ch].left_child && i==_data[ch].parent ) { 
    220226            i=ch; 
    221227            //break; 
    222228          } else { 
    223             if( container[ch].left_child ) { 
    224               child_right=container[ch].parent; 
    225               container[ch].parent = i; 
    226               --container[i].degree; 
     229            if( _data[ch].left_child ) { 
     230              child_right=_data[ch].parent; 
     231              _data[ch].parent = i; 
     232              --_data[i].degree; 
    227233            } 
    228234            else { 
    229235              child_right=ch; 
    230               container[i].child=-1; 
    231               container[i].degree=0; 
     236              _data[i].child=-1; 
     237              _data[i].degree=0; 
    232238            } 
    233             container[child_right].parent = -1; 
     239            _data[child_right].parent = -1; 
    234240            TreeArray[num_child] = child_right; 
    235241            i = child_right; 
     
    240246        int other; 
    241247        for( i=0; i<num_child-1; i+=2 ) { 
    242           if ( !comp(container[TreeArray[i]].prio, 
    243                      container[TreeArray[i+1]].prio) ) { 
     248          if ( !_comp(_data[TreeArray[i]].prio, 
     249                     _data[TreeArray[i+1]].prio) ) { 
    244250            other=TreeArray[i]; 
    245251            TreeArray[i]=TreeArray[i+1]; 
     
    251257        i = (0==(num_child % 2)) ? num_child-2 : num_child-1; 
    252258        while(i>=2) { 
    253           if ( comp(container[TreeArray[i]].prio, 
    254                     container[TreeArray[i-2]].prio) ) { 
     259          if ( _comp(_data[TreeArray[i]].prio, 
     260                    _data[TreeArray[i-2]].prio) ) { 
    255261            other=TreeArray[i]; 
    256262            TreeArray[i]=TreeArray[i-2]; 
     
    260266          i-=2; 
    261267        } 
    262         minimum = TreeArray[0]; 
     268        _min = TreeArray[0]; 
    263269      } 
    264270 
    265271      if ( 0==num_child ) { 
    266         minimum = container[minimum].child; 
    267       } 
    268  
    269       if (minimum >= 0) container[minimum].left_child = false; 
    270  
    271       --num_items; 
    272     } 
    273  
    274     /// \brief Deletes \c item from the heap. 
    275     /// 
    276     /// This method deletes \c item from the heap, if \c item was already 
    277     /// stored in the heap. It is quite inefficient in Pairing heaps. 
     272        _min = _data[_min].child; 
     273      } 
     274 
     275      if (_min >= 0) _data[_min].left_child = false; 
     276 
     277      --_num_items; 
     278    } 
     279 
     280    /// \brief Remove the given item from the heap. 
     281    /// 
     282    /// This function removes the given item from the heap if it is 
     283    /// already stored. 
     284    /// \param item The item to delete. 
     285    /// \pre \e item must be in the heap. 
    278286    void erase (const Item& item) { 
    279       int i=iimap[item]; 
    280       if ( i>=0 && container[i].in ) { 
    281         decrease( item, container[minimum].prio-1 ); 
     287      int i=_iim[item]; 
     288      if ( i>=0 && _data[i].in ) { 
     289        decrease( item, _data[_min].prio-1 ); 
    282290        pop(); 
    283291      } 
    284292    } 
    285293 
    286     /// \brief Decreases the priority of \c item to \c value. 
    287     /// 
    288     /// This method decreases the priority of \c item to \c value. 
    289     /// \pre \c item must be stored in the heap with priority at least \c 
    290     ///   value relative to \c Compare. 
     294    /// \brief Decrease the priority of an item to the given value. 
     295    /// 
     296    /// This function decreases the priority of an item to the given value. 
     297    /// \param item The item. 
     298    /// \param value The priority. 
     299    /// \pre \e item must be stored in the heap with priority at least \e value. 
    291300    void decrease (Item item, const Prio& value) { 
    292       int i=iimap[item]; 
    293       container[i].prio=value; 
    294       int p=container[i].parent; 
    295  
    296       if( container[i].left_child && i!=container[p].child ) { 
    297         p=container[p].parent; 
    298       } 
    299  
    300       if ( p!=-1 && comp(value,container[p].prio) ) { 
     301      int i=_iim[item]; 
     302      _data[i].prio=value; 
     303      int p=_data[i].parent; 
     304 
     305      if( _data[i].left_child && i!=_data[p].child ) { 
     306        p=_data[p].parent; 
     307      } 
     308 
     309      if ( p!=-1 && _comp(value,_data[p].prio) ) { 
    301310        cut(i,p); 
    302         if ( comp(container[minimum].prio,value) ) { 
    303           fuse(minimum,i); 
     311        if ( _comp(_data[_min].prio,value) ) { 
     312          fuse(_min,i); 
    304313        } else { 
    305           fuse(i,minimum); 
    306           minimum=i; 
    307         } 
    308       } 
    309     } 
    310  
    311     /// \brief Increases the priority of \c item to \c value. 
    312     /// 
    313     /// This method sets the priority of \c item to \c value. Though 
    314     /// there is no precondition on the priority of \c item, this 
    315     /// method should be used only if it is indeed necessary to increase 
    316     /// (relative to \c Compare) the priority of \c item, because this 
    317     /// method is inefficient. 
     314          fuse(i,_min); 
     315          _min=i; 
     316        } 
     317      } 
     318    } 
     319 
     320    /// \brief Increase the priority of an item to the given value. 
     321    /// 
     322    /// This function increases the priority of an item to the given value. 
     323    /// \param item The item. 
     324    /// \param value The priority. 
     325    /// \pre \e item must be stored in the heap with priority at most \e value. 
    318326    void increase (Item item, const Prio& value) { 
    319327      erase(item); 
     
    321329    } 
    322330 
    323     /// \brief Returns if \c item is in, has already been in, or has never 
    324     /// been in the heap. 
    325     /// 
    326     /// This method returns PRE_HEAP if \c item has never been in the 
    327     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP 
    328     /// otherwise. In the latter case it is possible that \c item will 
    329     /// get back to the heap again. 
     331    /// \brief Return the state of an item. 
     332    /// 
     333    /// This method returns \c PRE_HEAP if the given item has never 
     334    /// been in the heap, \c IN_HEAP if it is in the heap at the moment, 
     335    /// and \c POST_HEAP otherwise. 
     336    /// In the latter case it is possible that the item will get back 
     337    /// to the heap again. 
     338    /// \param item The item. 
    330339    State state(const Item &item) const { 
    331       int i=iimap[item]; 
     340      int i=_iim[item]; 
    332341      if( i>=0 ) { 
    333         if( container[i].in ) i=0; 
     342        if( _data[i].in ) i=0; 
    334343        else i=-2; 
    335344      } 
     
    337346    } 
    338347 
    339     /// \brief Sets the state of the \c item in the heap. 
    340     /// 
    341     /// Sets the state of the \c item in the heap. It can be used to 
    342     /// manually clear the heap when it is important to achive the 
    343     /// better time complexity. 
     348    /// \brief Set the state of an item in the heap. 
     349    /// 
     350    /// This function sets the state of the given item in the heap. 
     351    /// It can be used to manually clear the heap when it is important 
     352    /// to achive better time complexity. 
    344353    /// \param i The item. 
    345354    /// \param st The state. It should not be \c IN_HEAP. 
     
    349358      case PRE_HEAP: 
    350359        if (state(i) == IN_HEAP) erase(i); 
    351         iimap[i]=st; 
     360        _iim[i]=st; 
    352361        break; 
    353362      case IN_HEAP: 
     
    360369    void cut(int a, int b) { 
    361370      int child_a; 
    362       switch (container[a].degree) { 
     371      switch (_data[a].degree) { 
    363372        case 2: 
    364           child_a = container[container[a].child].parent; 
    365           if( container[a].left_child ) { 
    366             container[child_a].left_child=true; 
    367             container[b].child=child_a; 
    368             container[child_a].parent=container[a].parent; 
     373          child_a = _data[_data[a].child].parent; 
     374          if( _data[a].left_child ) { 
     375            _data[child_a].left_child=true; 
     376            _data[b].child=child_a; 
     377            _data[child_a].parent=_data[a].parent; 
    369378          } 
    370379          else { 
    371             container[child_a].left_child=false; 
    372             container[child_a].parent=b; 
    373             if( a!=container[b].child ) 
    374               container[container[b].child].parent=child_a; 
     380            _data[child_a].left_child=false; 
     381            _data[child_a].parent=b; 
     382            if( a!=_data[b].child ) 
     383              _data[_data[b].child].parent=child_a; 
    375384            else 
    376               container[b].child=child_a; 
    377           } 
    378           --container[a].degree; 
    379           container[container[a].child].parent=a; 
     385              _data[b].child=child_a; 
     386          } 
     387          --_data[a].degree; 
     388          _data[_data[a].child].parent=a; 
    380389          break; 
    381390 
    382391        case 1: 
    383           child_a = container[a].child; 
    384           if( !container[child_a].left_child ) { 
    385             --container[a].degree; 
    386             if( container[a].left_child ) { 
    387               container[child_a].left_child=true; 
    388               container[child_a].parent=container[a].parent; 
    389               container[b].child=child_a; 
     392          child_a = _data[a].child; 
     393          if( !_data[child_a].left_child ) { 
     394            --_data[a].degree; 
     395            if( _data[a].left_child ) { 
     396              _data[child_a].left_child=true; 
     397              _data[child_a].parent=_data[a].parent; 
     398              _data[b].child=child_a; 
    390399            } 
    391400            else { 
    392               container[child_a].left_child=false; 
    393               container[child_a].parent=b; 
    394               if( a!=container[b].child ) 
    395                 container[container[b].child].parent=child_a; 
     401              _data[child_a].left_child=false; 
     402              _data[child_a].parent=b; 
     403              if( a!=_data[b].child ) 
     404                _data[_data[b].child].parent=child_a; 
    396405              else 
    397                 container[b].child=child_a; 
     406                _data[b].child=child_a; 
    398407            } 
    399             container[a].child=-1; 
     408            _data[a].child=-1; 
    400409          } 
    401410          else { 
    402             --container[b].degree; 
    403             if( container[a].left_child ) { 
    404               container[b].child = 
    405                 (1==container[b].degree) ? container[a].parent : -1; 
     411            --_data[b].degree; 
     412            if( _data[a].left_child ) { 
     413              _data[b].child = 
     414                (1==_data[b].degree) ? _data[a].parent : -1; 
    406415            } else { 
    407               if (1==container[b].degree) 
    408                 container[container[b].child].parent=b; 
     416              if (1==_data[b].degree) 
     417                _data[_data[b].child].parent=b; 
    409418              else 
    410                 container[b].child=-1; 
     419                _data[b].child=-1; 
    411420            } 
    412421          } 
     
    414423 
    415424        case 0: 
    416           --container[b].degree; 
    417           if( container[a].left_child ) { 
    418             container[b].child = 
    419               (0!=container[b].degree) ? container[a].parent : -1; 
     425          --_data[b].degree; 
     426          if( _data[a].left_child ) { 
     427            _data[b].child = 
     428              (0!=_data[b].degree) ? _data[a].parent : -1; 
    420429          } else { 
    421             if( 0!=container[b].degree ) 
    422               container[container[b].child].parent=b; 
     430            if( 0!=_data[b].degree ) 
     431              _data[_data[b].child].parent=b; 
    423432            else 
    424               container[b].child=-1; 
     433              _data[b].child=-1; 
    425434          } 
    426435          break; 
    427436      } 
    428       container[a].parent=-1; 
    429       container[a].left_child=false; 
     437      _data[a].parent=-1; 
     438      _data[a].left_child=false; 
    430439    } 
    431440 
    432441    void fuse(int a, int b) { 
    433       int child_a = container[a].child; 
    434       int child_b = container[b].child; 
    435       container[a].child=b; 
    436       container[b].parent=a; 
    437       container[b].left_child=true; 
     442      int child_a = _data[a].child; 
     443      int child_b = _data[b].child; 
     444      _data[a].child=b; 
     445      _data[b].parent=a; 
     446      _data[b].left_child=true; 
    438447 
    439448      if( -1!=child_a ) { 
    440         container[b].child=child_a; 
    441         container[child_a].parent=b; 
    442         container[child_a].left_child=false; 
    443         ++container[b].degree; 
     449        _data[b].child=child_a; 
     450        _data[child_a].parent=b; 
     451        _data[child_a].left_child=false; 
     452        ++_data[b].degree; 
    444453 
    445454        if( -1!=child_b ) { 
    446            container[b].child=child_b; 
    447            container[child_b].parent=child_a; 
    448         } 
    449       } 
    450       else { ++container[a].degree; } 
     455           _data[b].child=child_b; 
     456           _data[child_b].parent=child_a; 
     457        } 
     458      } 
     459      else { ++_data[a].degree; } 
    451460    } 
    452461 
Note: See TracChangeset for help on using the changeset viewer.