COIN-OR::LEMON - Graph Library

Changes in / [911:66156a3498ea:917:b4af20d02ae0] in lemon-1.2


Ignore:
Files:
3 added
7 edited

Legend:

Unmodified
Added
Removed
  • lemon/Makefile.am

    r667 r681  
    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 \
     
    100102        lemon/path.h \
    101103        lemon/preflow.h \
     104        lemon/radix_heap.h \
    102105        lemon/radix_sort.h \
    103106        lemon/random.h \
  • lemon/bin_heap.h

    r584 r683  
    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

    r617 r802  
    5050    typedef typename Parent::ConstReference ConstReference;
    5151
     52    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
     53
    5254    class MapIt;
    5355    class ConstMapIt;
     
    8385      typedef typename Map::Value Value;
    8486
    85       MapIt() {}
    86 
    87       MapIt(Invalid i) : Parent(i) { }
    88 
    89       explicit MapIt(Map& _map) : map(_map) {
    90         map.notifier()->first(*this);
     87      MapIt() : map(NULL) {}
     88
     89      MapIt(Invalid i) : Parent(i), map(NULL) {}
     90
     91      explicit MapIt(Map& _map) : map(&_map) {
     92        map->notifier()->first(*this);
    9193      }
    9294
    9395      MapIt(const Map& _map, const Item& item)
     96        : Parent(item), map(&_map) {}
     97
     98      MapIt& operator++() {
     99        map->notifier()->next(*this);
     100        return *this;
     101      }
     102
     103      typename MapTraits<Map>::ConstReturnValue operator*() const {
     104        return (*map)[*this];
     105      }
     106
     107      typename MapTraits<Map>::ReturnValue operator*() {
     108        return (*map)[*this];
     109      }
     110
     111      void set(const Value& value) {
     112        map->set(*this, value);
     113      }
     114
     115    protected:
     116      Map* map;
     117
     118    };
     119
     120    class ConstMapIt : public Item {
     121      typedef Item Parent;
     122
     123    public:
     124
     125      typedef typename Map::Value Value;
     126
     127      ConstMapIt() : map(NULL) {}
     128
     129      ConstMapIt(Invalid i) : Parent(i), map(NULL) {}
     130
     131      explicit ConstMapIt(Map& _map) : map(&_map) {
     132        map->notifier()->first(*this);
     133      }
     134
     135      ConstMapIt(const Map& _map, const Item& item)
    94136        : Parent(item), map(_map) {}
    95137
    96       MapIt& operator++() {
    97         map.notifier()->next(*this);
     138      ConstMapIt& operator++() {
     139        map->notifier()->next(*this);
    98140        return *this;
    99141      }
     
    103145      }
    104146
    105       typename MapTraits<Map>::ReturnValue operator*() {
    106         return map[*this];
    107       }
    108 
    109       void set(const Value& value) {
    110         map.set(*this, value);
    111       }
    112 
    113     protected:
    114       Map& map;
    115 
    116     };
    117 
    118     class ConstMapIt : public Item {
    119       typedef Item Parent;
    120 
    121     public:
    122 
    123       typedef typename Map::Value Value;
    124 
    125       ConstMapIt() {}
    126 
    127       ConstMapIt(Invalid i) : Parent(i) { }
    128 
    129       explicit ConstMapIt(Map& _map) : map(_map) {
    130         map.notifier()->first(*this);
    131       }
    132 
    133       ConstMapIt(const Map& _map, const Item& item)
    134         : Parent(item), map(_map) {}
    135 
    136       ConstMapIt& operator++() {
    137         map.notifier()->next(*this);
    138         return *this;
    139       }
    140 
    141       typename MapTraits<Map>::ConstReturnValue operator*() const {
    142         return map[*this];
    143       }
    144 
    145     protected:
    146       const Map& map;
     147    protected:
     148      const Map* map;
    147149    };
    148150
     
    151153
    152154    public:
    153 
    154       ItemIt() {}
    155 
    156       ItemIt(Invalid i) : Parent(i) { }
    157 
    158       explicit ItemIt(Map& _map) : map(_map) {
    159         map.notifier()->first(*this);
     155      ItemIt() : map(NULL) {}
     156
     157
     158      ItemIt(Invalid i) : Parent(i), map(NULL) {}
     159
     160      explicit ItemIt(Map& _map) : map(&_map) {
     161        map->notifier()->first(*this);
    160162      }
    161163
    162164      ItemIt(const Map& _map, const Item& item)
    163         : Parent(item), map(_map) {}
     165        : Parent(item), map(&_map) {}
    164166
    165167      ItemIt& operator++() {
    166         map.notifier()->next(*this);
    167         return *this;
    168       }
    169 
    170     protected:
    171       const Map& map;
     168        map->notifier()->next(*this);
     169        return *this;
     170      }
     171
     172    protected:
     173      const Map* map;
    172174
    173175    };
     
    192194    typedef typename Parent::ConstReference ConstReference;
    193195
     196    typedef typename Parent::ReferenceMapTag ReferenceMapTag;
     197
    194198    class MapIt;
    195199    class ConstMapIt;
     
    228232      typedef typename Map::Value Value;
    229233
    230       MapIt() {}
    231 
    232       MapIt(Invalid i) : Parent(i) { }
    233 
    234       explicit MapIt(Map& _map) : map(_map) {
    235         map.graph.first(*this);
     234      MapIt() : map(NULL) {}
     235
     236      MapIt(Invalid i) : Parent(i), map(NULL) { }
     237
     238      explicit MapIt(Map& _map) : map(&_map) {
     239        map->graph.first(*this);
    236240      }
    237241
    238242      MapIt(const Map& _map, const Item& item)
    239         : Parent(item), map(_map) {}
     243        : Parent(item), map(&_map) {}
    240244
    241245      MapIt& operator++() {
    242         map.graph.next(*this);
     246        map->graph.next(*this);
    243247        return *this;
    244248      }
    245249
    246250      typename MapTraits<Map>::ConstReturnValue operator*() const {
    247         return map[*this];
     251        return (*map)[*this];
    248252      }
    249253
    250254      typename MapTraits<Map>::ReturnValue operator*() {
    251         return map[*this];
     255        return (*map)[*this];
    252256      }
    253257
    254258      void set(const Value& value) {
    255         map.set(*this, value);
    256       }
    257 
    258     protected:
    259       Map& map;
     259        map->set(*this, value);
     260      }
     261
     262    protected:
     263      Map* map;
    260264
    261265    };
     
    268272      typedef typename Map::Value Value;
    269273
    270       ConstMapIt() {}
    271 
    272       ConstMapIt(Invalid i) : Parent(i) { }
    273 
    274       explicit ConstMapIt(Map& _map) : map(_map) {
    275         map.graph.first(*this);
     274      ConstMapIt() : map(NULL) {}
     275
     276      ConstMapIt(Invalid i) : Parent(i), map(NULL) { }
     277
     278      explicit ConstMapIt(Map& _map) : map(&_map) {
     279        map->graph.first(*this);
    276280      }
    277281
    278282      ConstMapIt(const Map& _map, const Item& item)
    279         : Parent(item), map(_map) {}
     283        : Parent(item), map(&_map) {}
    280284
    281285      ConstMapIt& operator++() {
    282         map.graph.next(*this);
     286        map->graph.next(*this);
    283287        return *this;
    284288      }
    285289
    286290      typename MapTraits<Map>::ConstReturnValue operator*() const {
    287         return map[*this];
    288       }
    289 
    290     protected:
    291       const Map& map;
     291        return (*map)[*this];
     292      }
     293
     294    protected:
     295      const Map* map;
    292296    };
    293297
     
    296300
    297301    public:
    298 
    299       ItemIt() {}
    300 
    301       ItemIt(Invalid i) : Parent(i) { }
    302 
    303       explicit ItemIt(Map& _map) : map(_map) {
    304         map.graph.first(*this);
     302      ItemIt() : map(NULL) {}
     303
     304
     305      ItemIt(Invalid i) : Parent(i), map(NULL) { }
     306
     307      explicit ItemIt(Map& _map) : map(&_map) {
     308        map->graph.first(*this);
    305309      }
    306310
    307311      ItemIt(const Map& _map, const Item& item)
    308         : Parent(item), map(_map) {}
     312        : Parent(item), map(&_map) {}
    309313
    310314      ItemIt& operator++() {
    311         map.graph.next(*this);
    312         return *this;
    313       }
    314 
    315     protected:
    316       const Map& map;
     315        map->graph.next(*this);
     316        return *this;
     317      }
     318
     319    protected:
     320      const Map* map;
    317321
    318322    };
  • lemon/concepts/maps.h

    r529 r718  
    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];
  • lemon/glpk.h

    r650 r832  
    2626#include <lemon/lp_base.h>
    2727
    28 // forward declaration
    29 #if !defined _GLP_PROB && !defined GLP_PROB
    30 #define _GLP_PROB
    31 #define GLP_PROB
    32 typedef struct { double _opaque_prob; } glp_prob;
    33 /* LP/MIP problem object */
    34 #endif
    35 
    3628namespace lemon {
    3729
     30  namespace _solver_bits {
     31    class VoidPtr {
     32    private:
     33      void *_ptr;     
     34    public:
     35      VoidPtr() : _ptr(0) {}
     36
     37      template <typename T>
     38      VoidPtr(T* ptr) : _ptr(reinterpret_cast<void*>(ptr)) {}
     39
     40      template <typename T>
     41      VoidPtr& operator=(T* ptr) {
     42        _ptr = reinterpret_cast<void*>(ptr);
     43        return *this;
     44      }
     45
     46      template <typename T>
     47      operator T*() const { return reinterpret_cast<T*>(_ptr); }
     48    };
     49  }
    3850
    3951  /// \brief Base interface for the GLPK LP and MIP solver
     
    4456  protected:
    4557
    46     typedef glp_prob LPX;
    47     glp_prob* lp;
     58    _solver_bits::VoidPtr lp;
    4859
    4960    GlpkBase();
     
    123134
    124135    ///Pointer to the underlying GLPK data structure.
    125     LPX *lpx() {return lp;}
     136    _solver_bits::VoidPtr lpx() {return lp;}
    126137    ///Const pointer to the underlying GLPK data structure.
    127     const LPX *lpx() const {return lp;}
     138    _solver_bits::VoidPtr lpx() const {return lp;}
    128139
    129140    ///Returns the constraint identifier understood by GLPK.
  • lemon/path.h

    r559 r802  
    7171    template <typename CPath>
    7272    Path(const CPath& cpath) {
    73       copyPath(*this, cpath);
     73      pathCopy(cpath, *this);
    7474    }
    7575
     
    7979    template <typename CPath>
    8080    Path& operator=(const CPath& cpath) {
    81       copyPath(*this, cpath);
     81      pathCopy(cpath, *this);
    8282      return *this;
    8383    }
     
    259259    template <typename CPath>
    260260    SimplePath(const CPath& cpath) {
    261       copyPath(*this, cpath);
     261      pathCopy(cpath, *this);
    262262    }
    263263
     
    268268    template <typename CPath>
    269269    SimplePath& operator=(const CPath& cpath) {
    270       copyPath(*this, cpath);
     270      pathCopy(cpath, *this);
    271271      return *this;
    272272    }
     
    438438    template <typename CPath>
    439439    ListPath(const CPath& cpath) : first(0), last(0) {
    440       copyPath(*this, cpath);
     440      pathCopy(cpath, *this);
    441441    }
    442442
     
    454454    template <typename CPath>
    455455    ListPath& operator=(const CPath& cpath) {
    456       copyPath(*this, cpath);
     456      pathCopy(cpath, *this);
    457457      return *this;
    458458    }
     
    764764    template <typename CPath>
    765765    StaticPath(const CPath& cpath) : arcs(0) {
    766       copyPath(*this, cpath);
     766      pathCopy(cpath, *this);
    767767    }
    768768
     
    780780    template <typename CPath>
    781781    StaticPath& operator=(const CPath& cpath) {
    782       copyPath(*this, cpath);
     782      pathCopy(cpath, *this);
    783783      return *this;
    784784    }
     
    929929    };
    930930
    931     template <typename Target, typename Source,
    932               bool buildEnable = BuildTagIndicator<Target>::value>
     931    template <typename From, typename To,
     932              bool buildEnable = BuildTagIndicator<To>::value>
    933933    struct PathCopySelectorForward {
    934       static void copy(Target& target, const Source& source) {
    935         target.clear();
    936         for (typename Source::ArcIt it(source); it != INVALID; ++it) {
    937           target.addBack(it);
     934      static void copy(const From& from, To& to) {
     935        to.clear();
     936        for (typename From::ArcIt it(from); it != INVALID; ++it) {
     937          to.addBack(it);
    938938        }
    939939      }
    940940    };
    941941
    942     template <typename Target, typename Source>
    943     struct PathCopySelectorForward<Target, Source, true> {
    944       static void copy(Target& target, const Source& source) {
    945         target.clear();
    946         target.build(source);
    947       }
    948     };
    949 
    950     template <typename Target, typename Source,
    951               bool buildEnable = BuildTagIndicator<Target>::value>
     942    template <typename From, typename To>
     943    struct PathCopySelectorForward<From, To, true> {
     944      static void copy(const From& from, To& to) {
     945        to.clear();
     946        to.build(from);
     947      }
     948    };
     949
     950    template <typename From, typename To,
     951              bool buildEnable = BuildTagIndicator<To>::value>
    952952    struct PathCopySelectorBackward {
    953       static void copy(Target& target, const Source& source) {
    954         target.clear();
    955         for (typename Source::RevArcIt it(source); it != INVALID; ++it) {
    956           target.addFront(it);
     953      static void copy(const From& from, To& to) {
     954        to.clear();
     955        for (typename From::RevArcIt it(from); it != INVALID; ++it) {
     956          to.addFront(it);
    957957        }
    958958      }
    959959    };
    960960
    961     template <typename Target, typename Source>
    962     struct PathCopySelectorBackward<Target, Source, true> {
    963       static void copy(Target& target, const Source& source) {
    964         target.clear();
    965         target.buildRev(source);
     961    template <typename From, typename To>
     962    struct PathCopySelectorBackward<From, To, true> {
     963      static void copy(const From& from, To& to) {
     964        to.clear();
     965        to.buildRev(from);
    966966      }
    967967    };
    968968
    969969   
    970     template <typename Target, typename Source,
    971               bool revEnable = RevPathTagIndicator<Source>::value>
     970    template <typename From, typename To,
     971              bool revEnable = RevPathTagIndicator<From>::value>
    972972    struct PathCopySelector {
    973       static void copy(Target& target, const Source& source) {
    974         PathCopySelectorForward<Target, Source>::copy(target, source);
     973      static void copy(const From& from, To& to) {
     974        PathCopySelectorForward<From, To>::copy(from, to);
    975975      }     
    976976    };
    977977
    978     template <typename Target, typename Source>
    979     struct PathCopySelector<Target, Source, true> {
    980       static void copy(Target& target, const Source& source) {
    981         PathCopySelectorBackward<Target, Source>::copy(target, source);
     978    template <typename From, typename To>
     979    struct PathCopySelector<From, To, true> {
     980      static void copy(const From& from, To& to) {
     981        PathCopySelectorBackward<From, To>::copy(from, to);
    982982      }     
    983983    };
     
    988988  /// \brief Make a copy of a path.
    989989  ///
    990   ///  This function makes a copy of a path.
    991   template <typename Target, typename Source>
    992   void copyPath(Target& target, const Source& source) {
    993     checkConcept<concepts::PathDumper<typename Source::Digraph>, Source>();
    994     _path_bits::PathCopySelector<Target, Source>::copy(target, source);
     990  /// This function makes a copy of a path.
     991  template <typename From, typename To>
     992  void pathCopy(const From& from, To& to) {
     993    checkConcept<concepts::PathDumper<typename From::Digraph>, From>();
     994    _path_bits::PathCopySelector<From, To>::copy(from, to);
     995  }
     996
     997  /// \brief Deprecated version of \ref pathCopy().
     998  ///
     999  /// Deprecated version of \ref pathCopy() (only for reverse compatibility).
     1000  template <typename To, typename From>
     1001  void copyPath(To& to, const From& from) {
     1002    pathCopy(from, to);
    9951003  }
    9961004
     
    10161024  /// \brief The source of a path
    10171025  ///
    1018   /// This function returns the source of the given path.
     1026  /// This function returns the source node of the given path.
     1027  /// If the path is empty, then it returns \c INVALID.
    10191028  template <typename Digraph, typename Path>
    10201029  typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
    1021     return digraph.source(path.front());
     1030    return path.empty() ? INVALID : digraph.source(path.front());
    10221031  }
    10231032
    10241033  /// \brief The target of a path
    10251034  ///
    1026   /// This function returns the target of the given path.
     1035  /// This function returns the target node of the given path.
     1036  /// If the path is empty, then it returns \c INVALID.
    10271037  template <typename Digraph, typename Path>
    10281038  typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
    1029     return digraph.target(path.back());
     1039    return path.empty() ? INVALID : digraph.target(path.back());
    10301040  }
    10311041
  • test/heap_test.cc

    r440 r681  
    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.