COIN-OR::LEMON - Graph Library

Changeset 1703:eb90e3d6bddc in lemon-0.x


Ignore:
Timestamp:
10/05/05 15:15:47 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2230
Message:

Proper sized map type

Location:
lemon
Files:
1 added
6 edited

Legend:

Unmodified
Added
Removed
  • lemon/bits/array_map.h

    r1669 r1703  
    4949    typedef _Item Item;
    5050  public:
     51    typedef True AdaptibleTag;
    5152               
    5253    /// The graph type of the maps.
     
    7071  public:
    7172
     73    /// \brief Graph and Registry initialized map constructor.
     74    ///
    7275    /// Graph and Registry initialized map constructor.
    7376    ArrayMap(const Graph& _g) : graph(&_g) {
     
    8184    }
    8285
    83     /// Constructor to use default value to initialize the map.
    84 
    85     /// It constrates a map and initialize all of the the map.
    86 
     86    /// \brief Constructor to use default value to initialize the map.
     87    ///
     88    /// It constructs a map and initialize all of the the map.
    8789    ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) {
    8890      Item it;
     
    9597    }
    9698
    97     /// Constructor to copy a map of the same map type.
    98      
     99    /// \brief Constructor to copy a map of the same map type.
     100    ///
     101    /// Constructor to copy a map of the same map type.     
    99102    ArrayMap(const ArrayMap& copy) : Parent(), graph(copy.graph) {
    100103      if (copy.attached()) {
     
    138141  public:
    139142
    140     ///The subscript operator. The map can be subscripted by the
    141     ///actual keys of the graph.
    142      
     143    /// \brief The subscript operator.
     144    ///
     145    /// The subscript operator. The map can be subscripted by the
     146    /// actual keys of the graph.
    143147    Value& operator[](const Key& key) {
    144148      int id = graph->id(key);
     
    146150    }
    147151               
    148 
    149     ///The const subscript operator. The map can be subscripted by the
    150     ///actual keys of the graph.
    151    
     152    /// \brief The const subscript operator.
     153    ///
     154    /// The const subscript operator. The map can be subscripted by the
     155    /// actual keys of the graph.
    152156    const Value& operator[](const Key& key) const {
    153157      int id = graph->id(key);
    154158      return values[id];
    155159    }
    156        
     160
     161    /// \brief Setter function of the map.
     162    ///
    157163    /// Setter function of the map. Equivalent with map[key] = val.
    158164    /// This is a compatibility feature with the not dereferable maps.
    159      
    160165    void set(const Key& key, const Value& val) {
    161166      (*this)[key] = val;
     
    163168
    164169  protected:
    165    
     170
    166171    /// Add a new key to the map. It called by the map registry.
    167      
    168     void add(const Key& key) {
     172        
     173    virtual void add(const Key& key) {
    169174      int id = graph->id(key);
    170175      if (id >= capacity) {
     
    189194    }
    190195
    191     void add(const std::vector<Key>& keys) {
     196    virtual void add(const std::vector<Key>& keys) {
    192197      int max_id = -1;
    193198      for (int i = 0; i < (int)keys.size(); ++i) {
     
    230235    /// Erase a key from the map. It called by the map registry.
    231236     
    232     void erase(const Key& key) {
     237    virtual void erase(const Key& key) {
    233238      int id = graph->id(key);
    234239      allocator.destroy(&(values[id]));
    235240    }
    236241
    237     void erase(const std::vector<Key>& keys) {
     242    virtual void erase(const std::vector<Key>& keys) {
    238243      for (int i = 0; i < (int)keys.size(); ++i) {
    239244        int id = graph->id(keys[i]);
     
    242247    }
    243248
    244     void build() {
     249    virtual void build() {
    245250      allocate_memory();
    246251      Item it;
     
    251256    }
    252257
    253     void clear() {     
     258    virtual void clear() {     
    254259      if (capacity != 0) {
    255260        Item it;
  • lemon/bits/default_map.h

    r1672 r1703  
    2929namespace lemon {
    3030
    31   /// \addtogroup graphmapfactory
    32   /// @{
    3331
    3432  template <typename _Graph, typename _Item, typename _Value>
     
    269267  };
    270268
    271   /// @}
    272269}
    273270
  • lemon/bits/vector_map.h

    r1669 r1703  
    4545  ///
    4646  /// \param Registry The AlterationNotifier that will notify this map.
    47   /// \param IdMap The IdMap type of the graph items.
     47  /// \param Item The item type of the graph items.
    4848  /// \param Value The value type of the map.
    4949  ///
    5050  /// \author Balazs Dezso
    5151       
    52 
    5352  template <
    5453    typename _Graph,
     
    5857  class VectorMap : public AlterationNotifier<_Item>::ObserverBase {
    5958  public:
     59
     60    typedef True AdaptibleTag;
    6061               
    6162    /// The graph type of the map.
     
    9495    typedef True FullTypeTag;
    9596
    96     /// Constructor to attach the new map into the registry.
    97 
    98     /// It construates a map and attachs it into the registry.
     97    /// \brief Constructor to attach the new map into the registry.
     98    ///
     99    /// It constructs a map and attachs it into the registry.
    99100    /// It adds all the items of the graph to the map.
    100      
    101101    VectorMap(const Graph& _g) : graph(&_g) {
    102102      attach(_g.getNotifier(_Item()));
     
    104104    }
    105105
    106     /// Constructor uses given value to initialize the map.
    107 
    108     /// It construates a map uses a given value to initialize the map.
     106    /// \brief Constructor uses given value to initialize the map.
     107    ///
     108    /// It constructs a map uses a given value to initialize the map.
    109109    /// It adds all the items of the graph to the map.
    110      
    111110    VectorMap(const Graph& _g, const Value& _v) : graph(&_g) {
    112111      attach(_g.getNotifier(_Item()));
     
    114113    }
    115114
     115    /// \brief Copy constructor
     116    ///
     117    /// Copy constructor.
    116118    VectorMap(const VectorMap& _copy)
    117119      : Parent(), graph(_copy.getGraph()) {
     
    122124    }
    123125
     126    /// \brief Destrcutor
     127    ///
     128    /// Destructor.
    124129    virtual ~VectorMap() {
    125130      if (attached()) {
     
    145150  public:
    146151
    147     /// The subcript operator.
    148 
     152    /// \brief The subcript operator.
     153    ///
    149154    /// The subscript operator. The map can be subscripted by the
    150     /// actual items of the graph.
    151      
     155    /// actual items of the graph.     
    152156    Reference operator[](const Key& key) {
    153157      return container[graph->id(key)];
    154158    }
    155159               
    156     /// The const subcript operator.
    157 
     160    /// \brief The const subcript operator.
     161    ///
    158162    /// The const subscript operator. The map can be subscripted by the
    159163    /// actual items of the graph.
    160      
    161164    ConstReference operator[](const Key& key) const {
    162165      return container[graph->id(key)];
     
    164167
    165168
    166     /// The setter function of the map.
    167 
     169    /// \brief The setter function of the map.
     170    ///
    168171    /// It the same as operator[](key) = value expression.
    169     ///
    170172    void set(const Key& key, const Value& value) {
    171173      (*this)[key] = value;
     
    177179    ///         
    178180    /// It adds a new key to the map. It called by the observer registry
    179     /// and it overrides the add() member function of the observer base.
    180      
    181     void add(const Key& key) {
     181    /// and it overrides the add() member function of the observer base.     
     182    virtual void add(const Key& key) {
    182183      int id = graph->id(key);
    183184      if (id >= (int)container.size()) {
     
    186187    }
    187188
    188     /// Erases a key from the map.
    189                
     189    /// \brief Erase a key from the map.
     190    ///
    190191    /// Erase a key from the map. It called by the observer registry
    191192    /// and it overrides the erase() member function of the observer base.     
    192     void erase(const Key&) {}
    193 
    194     /// Buildes the map.
    195                
     193    virtual void erase(const Key&) {}
     194
     195    /// \brief Buildes the map.
     196    ///
    196197    /// It buildes the map. It called by the observer registry
    197198    /// and it overrides the build() member function of the observer base.
    198 
    199     void build() {
     199    virtual void build() {
    200200      container.resize(graph->maxId(_Item()) + 1);
    201201    }
    202202
    203     /// Clear the map.
    204 
     203    /// \brief Clear the map.
     204    ///
    205205    /// It erase all items from the map. It called by the observer registry
    206206    /// and it overrides the clear() member function of the observer base.     
    207     void clear() {
     207    virtual void clear() {
    208208      container.clear();
    209209    }
  • lemon/full_graph.h

    r1692 r1703  
    2323#include <lemon/bits/iterable_graph_extender.h>
    2424#include <lemon/bits/alteration_notifier.h>
    25 #include <lemon/bits/default_map.h>
     25#include <lemon/bits/static_map.h>
    2626
    2727#include <lemon/bits/undir_graph_extender.h>
     
    196196  typedef IterableGraphExtender<AlterableFullGraphBase>
    197197  IterableFullGraphBase;
    198   typedef MappableGraphExtender<
     198  typedef StaticMappableGraphExtender<
    199199    IterableGraphExtender<
    200200    AlterableGraphExtender<FullGraphBase> > > ExtendedFullGraphBase;
     
    299299    /// the next edge from \c u to \c v after \c prev.
    300300    /// \return The found edge or INVALID if there is no such an edge.
    301     Edge findEdge(Node u,Node v, Edge prev = INVALID)
    302     {
    303       return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
    304     }
     301    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
     302      if (prev.id != -1 || u.id <= v.id) return -1;
     303      return Edge(u.id * (u.id - 1) / 2 + v.id);
     304    }
     305
     306    typedef True FindEdgeTag;
    305307   
    306308     
     
    329331      Edge(int _id) : id(_id) {}
    330332
    331       Edge(const UndirFullGraphBase& _graph, int source, int target)
    332         : id(_graph._nodeNum * target+source) {}
    333333    public:
    334334      Edge() { }
     
    340340
    341341    void first(Node& node) const {
    342       node.id = _nodeNum-1;
     342      node.id = _nodeNum - 1;
    343343    }
    344344
     
    348348
    349349    void first(Edge& edge) const {
    350       edge.id = _edgeNum-1;
     350      edge.id = _edgeNum - 1;
    351351    }
    352352
     
    356356
    357357    void firstOut(Edge& edge, const Node& node) const {     
    358       edge.id = node.id != 0 ? node.id * (node.id - 1) / 2 : -1;
     358      int src = node.id;
     359      int trg = 0;
     360      edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
    359361    }
    360362
    361363    /// \todo with specialized iterators we can make faster iterating
    362     void nextOut(Edge& e) const {
    363       int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
    364       int target = e.id - (source) * (source - 1) / 2;
    365       ++target;
    366       e.id = target < source ? source * (source - 1) / 2 + target : -1;
     364    void nextOut(Edge& edge) const {
     365      int src = source(edge).id;
     366      int trg = target(edge).id;
     367      ++trg;
     368      edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
    367369    }
    368370
    369371    void firstIn(Edge& edge, const Node& node) const {
    370       edge.id = node.id * (node.id + 1) / 2 - 1;
    371     }
    372    
    373     void nextIn(Edge& e) const {
    374       int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
    375       int target = e.id - (source) * (source - 1) / 2; ++target;
    376       ++source;
    377       e.id = source < _nodeNum ? source * (source - 1) / 2 + target : -1;
     372      int src = node.id + 1;
     373      int trg = node.id;
     374      edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
     375    }
     376   
     377    void nextIn(Edge& edge) const {
     378      int src = source(edge).id;
     379      int trg = target(edge).id;
     380      ++src;
     381      edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
    378382    }
    379383
    380384  };
    381385
    382   typedef MappableUndirGraphExtender<
     386  typedef StaticMappableUndirGraphExtender<
    383387    IterableUndirGraphExtender<
    384388    AlterableUndirGraphExtender<
  • lemon/grid_graph.h

    r1693 r1703  
    2424#include <lemon/bits/iterable_graph_extender.h>
    2525#include <lemon/bits/alteration_notifier.h>
    26 #include <lemon/bits/default_map.h>
     26#include <lemon/bits/static_map.h>
    2727
    2828#include <lemon/bits/undir_graph_extender.h>
     
    340340
    341341
    342   typedef MappableUndirGraphExtender<
     342  typedef StaticMappableUndirGraphExtender<
    343343    IterableUndirGraphExtender<
    344344    AlterableUndirGraphExtender<
  • lemon/hypercube_graph.h

    r1693 r1703  
    233233
    234234
    235   typedef MappableGraphExtender<
     235  typedef StaticMappableGraphExtender<
    236236    IterableGraphExtender<
    237237    AlterableGraphExtender<
Note: See TracChangeset for help on using the changeset viewer.