COIN-OR::LEMON - Graph Library

Changeset 1064:40bbb450143e in lemon


Ignore:
Timestamp:
07/13/11 14:40:05 (8 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
1.1
Parents:
1054:632a72b27123 (diff), 1063:0dba9b96550a (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge #419 to branch 1.1

Files:
6 edited

Legend:

Unmodified
Added
Removed
  • lemon/Makefile.am

    r913 r1064  
    6060        lemon/bfs.h \
    6161        lemon/bin_heap.h \
     62        lemon/bucket_heap.h \
    6263        lemon/cbc.h \
    6364        lemon/circulation.h \
     
    7778        lemon/error.h \
    7879        lemon/euler.h \
     80        lemon/fib_heap.h \
    7981        lemon/full_graph.h \
    8082        lemon/glpk.h \
     
    99101        lemon/path.h \
    100102        lemon/preflow.h \
     103        lemon/radix_heap.h \
    101104        lemon/radix_sort.h \
    102105        lemon/random.h \
  • lemon/Makefile.am

    r728 r1064  
    9393        lemon/lp_base.h \
    9494        lemon/lp_skeleton.h \
    95         lemon/list_graph.h \
    9695        lemon/maps.h \
    9796        lemon/matching.h \
  • lemon/bin_heap.h

    r912 r1064  
    3434  ///\brief A Binary Heap implementation.
    3535  ///
    36   ///This class implements the \e binary \e heap data structure. 
    37   /// 
     36  ///This class implements the \e binary \e heap data structure.
     37  ///
    3838  ///A \e heap is a data structure for storing items with specified values
    3939  ///called \e priorities in such a way that finding the item with minimum
    40   ///priority is efficient. \c Comp specifies the ordering of the priorities.
     40  ///priority is efficient. \c CMP specifies the ordering of the priorities.
    4141  ///In a heap one can change the priority of an item, add or erase an
    4242  ///item, etc.
     
    4545  ///\tparam IM A read and writable item map with int values, used internally
    4646  ///to handle the cross references.
    47   ///\tparam Comp A functor class for the ordering of the priorities.
     47  ///\tparam CMP A functor class for the ordering of the priorities.
    4848  ///The default is \c std::less<PR>.
    4949  ///
    5050  ///\sa FibHeap
    5151  ///\sa Dijkstra
    52   template <typename PR, typename IM, typename Comp = std::less<PR> >
     52  template <typename PR, typename IM, typename CMP = std::less<PR> >
    5353  class BinHeap {
    5454
     
    6363    typedef std::pair<Item,Prio> Pair;
    6464    ///\e
    65     typedef Comp Compare;
     65    typedef CMP Compare;
    6666
    6767    /// \brief Type to represent the items states.
  • lemon/bits/map_extender.h

    r913 r1064  
    5050    typedef typename Parent::ConstReference ConstReference;
    5151
     52    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
     53
    5254    class MapIt;
    5355    class ConstMapIt;
     
    192194    typedef typename Parent::ConstReference ConstReference;
    193195
     196    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
     197
    194198    class MapIt;
    195199    class ConstMapIt;
  • lemon/concepts/maps.h

    r912 r1064  
    183183      template<typename _ReferenceMap>
    184184      struct Constraints {
    185         void constraints() {
     185        typename enable_if<typename _ReferenceMap::ReferenceMapTag, void>::type
     186        constraints() {
    186187          checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();
    187188          ref = m[key];
  • test/heap_test.cc

    r912 r1064  
    3232
    3333#include <lemon/bin_heap.h>
     34#include <lemon/fib_heap.h>
     35#include <lemon/radix_heap.h>
     36#include <lemon/bucket_heap.h>
    3437
    3538#include "test_tools.h"
     
    184187  }
    185188
     189  {
     190    typedef FibHeap<Prio, ItemIntMap> IntHeap;
     191    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
     192    heapSortTest<IntHeap>();
     193    heapIncreaseTest<IntHeap>();
     194
     195    typedef FibHeap<Prio, IntNodeMap > NodeHeap;
     196    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
     197    dijkstraHeapTest<NodeHeap>(digraph, length, source);
     198  }
     199
     200  {
     201    typedef RadixHeap<ItemIntMap> IntHeap;
     202    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
     203    heapSortTest<IntHeap>();
     204    heapIncreaseTest<IntHeap>();
     205
     206    typedef RadixHeap<IntNodeMap > NodeHeap;
     207    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
     208    dijkstraHeapTest<NodeHeap>(digraph, length, source);
     209  }
     210
     211  {
     212    typedef BucketHeap<ItemIntMap> IntHeap;
     213    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
     214    heapSortTest<IntHeap>();
     215    heapIncreaseTest<IntHeap>();
     216
     217    typedef BucketHeap<IntNodeMap > NodeHeap;
     218    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
     219    dijkstraHeapTest<NodeHeap>(digraph, length, source);
     220  }
     221
     222
    186223  return 0;
    187224}
Note: See TracChangeset for help on using the changeset viewer.