COIN-OR::LEMON - Graph Library

Changeset 855:65a0521e744e in lemon-main


Ignore:
Timestamp:
09/29/09 13:32:01 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Rename heap structures (#301)

Files:
2 edited
3 moved

Legend:

Unmodified
Added
Removed
  • lemon/Makefile.am

    r708 r855  
    6161        lemon/bfs.h \
    6262        lemon/bin_heap.h \
    63         lemon/binom_heap.h \
     63        lemon/binomial_heap.h \
    6464        lemon/bucket_heap.h \
    6565        lemon/cbc.h \
     
    7373        lemon/cplex.h \
    7474        lemon/dfs.h \
     75        lemon/dheap.h \
    7576        lemon/dijkstra.h \
    7677        lemon/dim2.h \
     
    8182        lemon/euler.h \
    8283        lemon/fib_heap.h \
    83         lemon/fourary_heap.h \
    8484        lemon/full_graph.h \
    8585        lemon/glpk.h \
     
    8888        lemon/grid_graph.h \
    8989        lemon/hypercube_graph.h \
    90         lemon/kary_heap.h \
    9190        lemon/kruskal.h \
    9291        lemon/hao_orlin.h \
     
    106105        lemon/path.h \
    107106        lemon/preflow.h \
     107        lemon/quad_heap.h \
    108108        lemon/radix_heap.h \
    109109        lemon/radix_sort.h \
  • lemon/binomial_heap.h

    r707 r855  
    1717 */
    1818
    19 #ifndef LEMON_BINOM_HEAP_H
    20 #define LEMON_BINOM_HEAP_H
     19#ifndef LEMON_BINOMIAL_HEAP_H
     20#define LEMON_BINOMIAL_HEAP_H
    2121
    2222///\file
     
    5454  template <typename PR, typename IM, typename CMP = std::less<PR> >
    5555#endif
    56   class BinomHeap {
     56  class BinomialHeap {
    5757  public:
    5858    /// Type of the item-int map.
     
    9595    /// It is used internally to handle the cross references.
    9696    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    97     explicit BinomHeap(ItemIntMap &map)
     97    explicit BinomialHeap(ItemIntMap &map)
    9898      : _min(0), _head(-1), _iim(map), _num_items(0) {}
    9999
     
    105105    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    106106    /// \param comp The function object used for comparing the priorities.
    107     BinomHeap(ItemIntMap &map, const Compare &comp)
     107    BinomialHeap(ItemIntMap &map, const Compare &comp)
    108108      : _min(0), _head(-1), _iim(map), _comp(comp), _num_items(0) {}
    109109
     
    425425
    426426    class Store {
    427       friend class BinomHeap;
     427      friend class BinomialHeap;
    428428
    429429      Item name;
     
    442442} //namespace lemon
    443443
    444 #endif //LEMON_BINOM_HEAP_H
    445 
     444#endif //LEMON_BINOMIAL_HEAP_H
     445
  • lemon/dheap.h

    r706 r855  
    1717 */
    1818
    19 #ifndef LEMON_KARY_HEAP_H
    20 #define LEMON_KARY_HEAP_H
     19#ifndef LEMON_DHEAP_H
     20#define LEMON_DHEAP_H
    2121
    2222///\ingroup heaps
    2323///\file
    24 ///\brief Fourary heap implementation.
     24///\brief D-ary heap implementation.
    2525
    2626#include <vector>
     
    3232  /// \ingroup heaps
    3333  ///
    34   ///\brief K-ary heap data structure.
    35   ///
    36   /// This class implements the \e K-ary \e heap data structure.
     34  ///\brief D-ary heap data structure.
     35  ///
     36  /// This class implements the \e D-ary \e heap data structure.
    3737  /// It fully conforms to the \ref concepts::Heap "heap concept".
    3838  ///
    39   /// The \ref KaryHeap "K-ary heap" is a generalization of the
     39  /// The \ref DHeap "D-ary heap" is a generalization of the
    4040  /// \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.
     41  /// \c D children, instead of two.
     42  /// \ref BinHeap and \ref QuadHeap are specialized implementations
     43  /// of this structure for <tt>D=2</tt> and <tt>D=4</tt>, respectively.
    4444  ///
    4545  /// \tparam PR Type of the priorities of the items.
    4646  /// \tparam IM A read-writable item map with \c int values, used
    4747  /// internally to handle the cross references.
    48   /// \tparam K The degree of the heap, each node have at most \e K
     48  /// \tparam D The degree of the heap, each node have at most \e D
    4949  /// children. The default is 16. Powers of two are suggested to use
    5050  /// so that the multiplications and divisions needed to traverse the
     
    5656  ///\sa FouraryHeap
    5757#ifdef DOXYGEN
    58   template <typename PR, typename IM, int K, typename CMP>
     58  template <typename PR, typename IM, int D, typename CMP>
    5959#else
    60   template <typename PR, typename IM, int K = 16,
     60  template <typename PR, typename IM, int D = 16,
    6161            typename CMP = std::less<PR> >
    6262#endif
    63   class KaryHeap {
     63  class DHeap {
    6464  public:
    6565    /// Type of the item-int map.
     
    100100    /// It is used internally to handle the cross references.
    101101    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    102     explicit KaryHeap(ItemIntMap &map) : _iim(map) {}
     102    explicit DHeap(ItemIntMap &map) : _iim(map) {}
    103103
    104104    /// \brief Constructor.
     
    109109    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    110110    /// \param comp The function object used for comparing the priorities.
    111     KaryHeap(ItemIntMap &map, const Compare &comp)
     111    DHeap(ItemIntMap &map, const Compare &comp)
    112112      : _iim(map), _comp(comp) {}
    113113
     
    132132
    133133  private:
    134     int parent(int i) { return (i-1)/K; }
    135     int firstChild(int i) { return K*i+1; }
     134    int parent(int i) { return (i-1)/D; }
     135    int firstChild(int i) { return D*i+1; }
    136136
    137137    bool less(const Pair &p1, const Pair &p2) const {
     
    152152      if( length>1 ) {
    153153        int child = firstChild(hole);
    154         while( child+K<=length ) {
     154        while( child+D<=length ) {
    155155          int min=child;
    156           for (int i=1; i<K; ++i) {
     156          for (int i=1; i<D; ++i) {
    157157            if( less(_data[child+i], _data[min]) )
    158158              min=child+i;
     
    346346    }
    347347
    348   }; // class KaryHeap
     348  }; // class DHeap
    349349
    350350} // namespace lemon
    351351
    352 #endif // LEMON_KARY_HEAP_H
     352#endif // LEMON_DHEAP_H
  • lemon/quad_heap.h

    r706 r855  
    1717 */
    1818
    19 #ifndef LEMON_FOURARY_HEAP_H
    20 #define LEMON_FOURARY_HEAP_H
     19#ifndef LEMON_QUAD_HEAP_H
     20#define LEMON_QUAD_HEAP_H
    2121
    2222///\ingroup heaps
    2323///\file
    24 ///\brief Fourary heap implementation.
     24///\brief Fourary (quaternary) heap implementation.
    2525
    2626#include <vector>
     
    3232  /// \ingroup heaps
    3333  ///
    34   ///\brief Fourary heap data structure.
    35   ///
    36   /// This class implements the \e fourary \e heap data structure.
     34  ///\brief Fourary (quaternary) heap data structure.
     35  ///
     36  /// This class implements the \e Fourary (\e quaternary) \e heap
     37  /// data structure.
    3738  /// It fully conforms to the \ref concepts::Heap "heap concept".
    3839  ///
    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",
     40  /// The fourary heap is a specialization of the \ref DHeap "D-ary heap"
     41  /// for <tt>D=4</tt>. It is similar to the \ref BinHeap "binary heap",
    4142  /// but its nodes have at most four children, instead of two.
    4243  ///
     
    4849  ///
    4950  ///\sa BinHeap
    50   ///\sa KaryHeap
     51  ///\sa DHeap
    5152#ifdef DOXYGEN
    5253  template <typename PR, typename IM, typename CMP>
     
    5455  template <typename PR, typename IM, typename CMP = std::less<PR> >
    5556#endif
    56   class FouraryHeap {
     57  class QuadHeap {
    5758  public:
    5859    /// Type of the item-int map.
     
    9394    /// It is used internally to handle the cross references.
    9495    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    95     explicit FouraryHeap(ItemIntMap &map) : _iim(map) {}
     96    explicit QuadHeap(ItemIntMap &map) : _iim(map) {}
    9697
    9798    /// \brief Constructor.
     
    102103    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    103104    /// \param comp The function object used for comparing the priorities.
    104     FouraryHeap(ItemIntMap &map, const Compare &comp)
     105    QuadHeap(ItemIntMap &map, const Compare &comp)
    105106      : _iim(map), _comp(comp) {}
    106107
     
    336337    }
    337338
    338   }; // class FouraryHeap
     339  }; // class QuadHeap
    339340
    340341} // namespace lemon
  • test/heap_test.cc

    r702 r855  
    3131
    3232#include <lemon/bin_heap.h>
    33 #include <lemon/fourary_heap.h>
    34 #include <lemon/kary_heap.h>
     33#include <lemon/quad_heap.h>
     34#include <lemon/dheap.h>
    3535#include <lemon/fib_heap.h>
    3636#include <lemon/pairing_heap.h>
    3737#include <lemon/radix_heap.h>
    38 #include <lemon/binom_heap.h>
     38#include <lemon/binomial_heap.h>
    3939#include <lemon/bucket_heap.h>
    4040
     
    186186  }
    187187
    188   // FouraryHeap
    189   {
    190     typedef FouraryHeap<Prio, ItemIntMap> IntHeap;
    191     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    192     heapSortTest<IntHeap>();
    193     heapIncreaseTest<IntHeap>();
    194 
    195     typedef FouraryHeap<Prio, IntNodeMap > NodeHeap;
    196     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    197     dijkstraHeapTest<NodeHeap>(digraph, length, source);
    198   }
    199 
    200   // KaryHeap
    201   {
    202     typedef KaryHeap<Prio, ItemIntMap> IntHeap;
    203     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    204     heapSortTest<IntHeap>();
    205     heapIncreaseTest<IntHeap>();
    206 
    207     typedef KaryHeap<Prio, IntNodeMap > NodeHeap;
     188  // QuadHeap
     189  {
     190    typedef QuadHeap<Prio, ItemIntMap> IntHeap;
     191    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
     192    heapSortTest<IntHeap>();
     193    heapIncreaseTest<IntHeap>();
     194
     195    typedef QuadHeap<Prio, IntNodeMap > NodeHeap;
     196    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
     197    dijkstraHeapTest<NodeHeap>(digraph, length, source);
     198  }
     199
     200  // DHeap
     201  {
     202    typedef DHeap<Prio, ItemIntMap> IntHeap;
     203    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
     204    heapSortTest<IntHeap>();
     205    heapIncreaseTest<IntHeap>();
     206
     207    typedef DHeap<Prio, IntNodeMap > NodeHeap;
    208208    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    209209    dijkstraHeapTest<NodeHeap>(digraph, length, source);
     
    246246  }
    247247
    248   // BinomHeap
    249   {
    250     typedef BinomHeap<Prio, ItemIntMap> IntHeap;
    251     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    252     heapSortTest<IntHeap>();
    253     heapIncreaseTest<IntHeap>();
    254 
    255     typedef BinomHeap<Prio, IntNodeMap > NodeHeap;
     248  // BinomialHeap
     249  {
     250    typedef BinomialHeap<Prio, ItemIntMap> IntHeap;
     251    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
     252    heapSortTest<IntHeap>();
     253    heapIncreaseTest<IntHeap>();
     254
     255    typedef BinomialHeap<Prio, IntNodeMap > NodeHeap;
    256256    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    257257    dijkstraHeapTest<NodeHeap>(digraph, length, source);
Note: See TracChangeset for help on using the changeset viewer.