COIN-OR::LEMON - Graph Library

Changeset 1414:01d9d6bc1284 in lemon-0.x for src


Ignore:
Timestamp:
05/14/05 19:20:40 (19 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1884
Message:

Handling simultan edge adding.
Fixed bug: directed edge maps for undir graphs

Location:
src/lemon/bits
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/bits/alteration_notifier.h

    r1359 r1414  
    3030  /// @{
    3131
    32   /// Registry class to register objects observes alterations in the graph.
    33 
     32  /// \brief Registry class to register objects observes alterations in
     33  /// the graph.
     34  ///
    3435  /// This class is a registry for the objects which observe the
    3536  /// alterations in a container. The alteration observers can be attached
     
    3940  ///
    4041  /// The most important application of the alteration observing is the
    41   /// dynamic map implementation when the observers are observing the
    42   /// alterations in the graph.
     42  /// dynamic map implementation.
    4343  ///
    4444  /// \param _Item The item type what the observers are observing, usually
     
    7575      friend class AlterationNotifier;
    7676
    77       /// Default constructor.
    78 
     77      /// \brief Default constructor.
     78      ///
    7979      /// Default constructor for ObserverBase.
    8080      ///
     
    8383      virtual ~ObserverBase() {}
    8484
    85       /// Attaches the observer into an AlterationNotifier.
    86 
     85      /// \brief Attaches the observer into an AlterationNotifier.
     86      ///
    8787      /// This member attaches the observer into an AlterationNotifier.
    8888      ///
     
    9292      }
    9393
    94       /// Detaches the observer into an AlterationNotifier.
    95 
     94      /// \brief Detaches the observer into an AlterationNotifier.
     95      ///
    9696      /// This member detaches the observer from an AlterationNotifier.
    9797      ///
     
    132132      /// subclasses.
    133133       
    134       virtual void add(const Item&) = 0;       
    135 
     134      virtual void add(const Item&) = 0;
     135
     136      /// \brief The member function to notificate the observer about
     137      /// simulitem is added to the container.
     138      ///
     139      /// The add() member function notificates the observer about an item
     140      /// is added to the container. It have to be overrided in the
     141      /// subclasses.
     142
     143      virtual void add(const std::vector<Item>& items) {
     144        for (int i = 0; i < (int)items.size(); ++i) {
     145          add(items[i]);
     146        }
     147      }
    136148
    137149      /// \brief The member function to notificate the observer about an
     
    143155       
    144156      virtual void erase(const Item&) = 0;
     157
     158      virtual void erase(const std::vector<Item>& items) {
     159        for (int i = 0; i < (int)items.size(); ++i) {
     160          add(items[i]);
     161        }
     162      }
    145163
    146164      /// \brief The member function to notificate the observer about the
     
    229247  public:
    230248       
    231     /// Notifies all the registered observers about an Item added to the container.
    232                
    233     /// It notifies all the registered observers about an Item added to the container.
     249    /// \brief Notifies all the registered observers about an Item added to
     250    /// the container.
     251    ///
     252    /// It notifies all the registered observers about an Item added to
     253    /// the container.
    234254    ///
    235     void add(const Item& key) {
    236       typename Container::iterator it;
    237       for (it = container.begin(); it != container.end(); ++it) {
    238         (*it)->add(key);
     255    void add(const Item& item) {
     256      typename Container::iterator it;
     257      for (it = container.begin(); it != container.end(); ++it) {
     258        (*it)->add(item);
    239259      }
    240260    }   
    241261
    242     /// Notifies all the registered observers about an Item erased from the container.
    243                
    244     /// It notifies all the registered observers about an Item erased from the container.
     262    /// \brief Notifies all the registered observers about more Item added to
     263    /// the container.
     264    ///
     265    /// It notifies all the registered observers about more Item added to
     266    /// the container.
     267    ///
     268    void add(const std::vector<Item>& items) {
     269      typename Container::iterator it;
     270      for (it = container.begin(); it != container.end(); ++it) {
     271        (*it)->add(items);
     272      }
     273    }   
     274
     275    /// \brief Notifies all the registered observers about an Item erased from
     276    /// the container.
     277    ///
     278    /// It notifies all the registered observers about an Item erased from
     279    /// the container.
    245280    ///
    246281    void erase(const Item& key) {
     
    250285      }
    251286    }
     287
     288    /// \brief Notifies all the registered observers about more Item erased 
     289    /// from the container.
     290    ///
     291    /// It notifies all the registered observers about more Item erased from
     292    /// the container.
     293    ///
     294    void erase(const std::vector<Item>& items) {
     295      typename Container::iterator it;
     296      for (it = container.begin(); it != container.end(); ++it) {
     297        (*it)->erase(items);
     298      }
     299    }
    252300   
    253301
    254     /// Notifies all the registered observers about the container is built.
    255                
     302    /// \brief Notifies all the registered observers about the container is
     303    /// built.
     304    ///         
    256305    /// Notifies all the registered observers about the container is built
    257306    /// from an empty container.
     
    264313
    265314
    266     /// Notifies all the registered observers about all Items are erased.
    267 
     315    /// \brief Notifies all the registered observers about all Items are
     316    /// erased.
     317    ///
    268318    /// Notifies all the registered observers about all Items are erased
    269319    /// from the container.
  • src/lemon/bits/array_map.h

    r1374 r1414  
    11/* -*- C++ -*-
    2  * src/lemon/array_map.h - Part of LEMON, a generic C++ optimization library
     2 * src/lemon/bits/array_map.h - Part of LEMON, a generic C++ optimization library
    33 *
    44 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     
    3232  /// @{
    3333       
    34   /** The ArrayMap template class is graph map structure what
    35    * automatically updates the map when a key is added to or erased from
    36    * the map. This map factory uses the allocators to implement
    37    * the container functionality.
    38    *
    39    * The template parameter is the AlterationNotifier that the maps
    40    * will belong to and the Value.
    41    */
     34  /// The ArrayMap template class is graph map structure what
     35  /// automatically updates the map when a key is added to or erased from
     36  /// the map. This map factory uses the allocators to implement
     37  /// the container functionality.
     38  ///
     39  /// The template parameter is the AlterationNotifier that the maps
     40  /// will belong to and the Value.
     41   
    4242
    4343  template <typename _Graph,
     
    6969  public:
    7070
    71     /** Graph and Registry initialized map constructor.
    72      */
     71    /// Graph and Registry initialized map constructor.
     72     
    7373    ArrayMap(const Graph& _g) : graph(&_g) {
    7474      Item it;
     
    9595    }
    9696
    97     /** Constructor to copy a map of the same map type.
    98      */
     97    /// Constructor to copy a map of the same map type.
     98     
    9999    ArrayMap(const ArrayMap& copy) : Parent() {
    100100      if (copy.attached()) {
     
    115115    using Parent::attached;
    116116
    117     /** Assign operator to copy a map of the same map type.
    118      */
     117    /// Assign operator to copy a map of the same map type.
     118     
    119119    ArrayMap& operator=(const ArrayMap& copy) {
    120120      if (&copy == this) return *this;
     
    142142    }
    143143
    144     /** The destructor of the map.
    145      */
     144    /// The destructor of the map.
     145     
    146146    virtual ~ArrayMap() {     
    147147      if (attached()) {
     
    152152       
    153153       
    154     /**
    155      * The subscript operator. The map can be subscripted by the
    156      * actual keys of the graph.
    157      */
     154    ///The subscript operator. The map can be subscripted by the
     155    ///actual keys of the graph.
     156     
    158157    Value& operator[](const Key& key) {
    159158      int id = graph->id(key);
     
    161160    }
    162161               
    163     /**
    164      * The const subscript operator. The map can be subscripted by the
    165      * actual keys of the graph.
    166      */
     162
     163    ///The const subscript operator. The map can be subscripted by the
     164    ///actual keys of the graph.
     165     
    167166    const Value& operator[](const Key& key) const {
    168167      int id = graph->id(key);
     
    170169    }
    171170       
    172     /** Setter function of the map. Equivalent with map[key] = val.
    173      * This is a compatibility feature with the not dereferable maps.
    174      */
     171    /// Setter function of the map. Equivalent with map[key] = val.
     172    /// This is a compatibility feature with the not dereferable maps.
     173     
    175174    void set(const Key& key, const Value& val) {
    176175      (*this)[key] = val;
    177176    }
    178177               
    179     /** Add a new key to the map. It called by the map registry.
    180      */
     178    /// Add a new key to the map. It called by the map registry.
     179     
    181180    void add(const Key& key) {
    182181      int id = graph->id(key);
     
    201200      allocator.construct(&(values[id]), Value());
    202201    }
    203                
    204     /** Erase a key from the map. It called by the map registry.
    205      */
     202
     203    void add(const std::vector<Key>& keys) {
     204      int max_id = -1;
     205      for (int i = 0; i < (int)keys.size(); ++i) {
     206        int id = graph->id(keys[i]);
     207        if (id > max_id) {
     208          max_id = id;
     209        }
     210      }
     211      if (max_id >= capacity) {
     212        int new_capacity = (capacity == 0 ? 1 : capacity);
     213        while (new_capacity <= max_id) {
     214          new_capacity <<= 1;
     215        }
     216        Value* new_values = allocator.allocate(new_capacity);
     217        Item it;
     218        for (graph->first(it); it != INVALID; graph->next(it)) {
     219          int id = graph->id(it);
     220          bool found = false;
     221          for (int i = 0; i < (int)keys.size(); ++i) {
     222            int jd = graph->id(keys[i]);
     223            if (id == jd) {
     224              found = true;
     225              break;
     226            }
     227          }
     228          if (found) continue;
     229          allocator.construct(&(new_values[id]), values[id]);
     230          allocator.destroy(&(values[id]));
     231        }
     232        if (capacity != 0) allocator.deallocate(values, capacity);
     233        values = new_values;
     234        capacity = new_capacity;
     235      }
     236      for (int i = 0; i < (int)keys.size(); ++i) {
     237        int id = graph->id(keys[i]);
     238        allocator.construct(&(values[id]), Value());
     239      }
     240    }
     241               
     242    /// Erase a key from the map. It called by the map registry.
     243     
    206244    void erase(const Key& key) {
    207245      int id = graph->id(key);
    208246      allocator.destroy(&(values[id]));
     247    }
     248
     249    void erase(const std::vector<Key>& keys) {
     250      for (int i = 0; i < (int)keys.size(); ++i) {
     251        int id = graph->id(keys[i]);
     252        allocator.destroy(&(values[id]));
     253      }
    209254    }
    210255
     
    222267        Item it;
    223268        for (graph->first(it); it != INVALID; graph->next(it)) {
    224           int id = graph->id(it);;
     269          int id = graph->id(it);
    225270          allocator.destroy(&(values[id]));
    226271        }                                                               
     
    233278      return graph;
    234279    }
    235 
    236 //     /// The stl compatible pair iterator of the map.
    237 //     typedef MapIterator<ArrayMap> Iterator;
    238 //     /// The stl compatible const pair iterator of the map.
    239 //     typedef MapConstIterator<ArrayMap> ConstIterator;
    240 
    241 //     /** Returns the begin iterator of the map.
    242 //      */
    243 //     Iterator begin() {
    244 //       return Iterator(*this, KeyIt(*MapBase::getGraph()));
    245 //     }
    246 
    247 //     /** Returns the end iterator of the map.
    248 //      */
    249 //     Iterator end() {
    250 //       return Iterator(*this, INVALID);
    251 //     }
    252 
    253 //     /** Returns the begin ConstIterator of the map.
    254 //      */
    255 //     ConstIterator begin() const {
    256 //       return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
    257 //     }
    258 
    259 //     /** Returns the end const_iterator of the map.
    260 //      */
    261 //     ConstIterator end() const {
    262 //       return ConstIterator(*this, INVALID);
    263 //     }
    264 
    265 //     /// The KeySet of the Map.
    266 //     typedef MapConstKeySet<ArrayMap> ConstKeySet;
    267 
    268 //     /// KeySet getter function.
    269 //     ConstKeySet keySet() const {
    270 //       return ConstKeySet(*this);
    271 //     }
    272 
    273 //     /// The ConstValueSet of the Map.
    274 //     typedef MapConstValueSet<ArrayMap> ConstValueSet;
    275 
    276 //     /// ConstValueSet getter function.
    277 //     ConstValueSet valueSet() const {
    278 //       return ConstValueSet(*this);
    279 //     }
    280 
    281 //     /// The ValueSet of the Map.
    282 //     typedef MapValueSet<ArrayMap> ValueSet;
    283 
    284 //     /// ValueSet getter function.
    285 //     ValueSet valueSet() {
    286 //       return ValueSet(*this);
    287 //     }
    288280
    289281  private:
  • src/lemon/bits/erasable_graph_extender.h

    r1307 r1414  
    33#ifndef LEMON_ERASABLE_GRAPH_EXTENDER_H
    44#define LEMON_ERASABLE_GRAPH_EXTENDER_H
     5
     6#include <vector>
    57
    68#include <lemon/invalid.h>
     
    6870   
    6971    void erase(const UndirEdge& uedge) {
    70       Parent::getNotifier(Edge()).erase(Edge(uedge,true));
    71       Parent::getNotifier(Edge()).erase(Edge(uedge,false));
     72      std::vector<Edge> edges;
     73      edges.push_back(Edge(uedge,true));
     74      edges.push_back(Edge(uedge,false));
     75      Parent::getNotifier(Edge()).erase(edges);
    7276      Parent::getNotifier(UndirEdge()).erase(uedge);
    7377      Parent::erase(uedge);
  • src/lemon/bits/extendable_graph_extender.h

    r1307 r1414  
    5151      Parent::getNotifier(UndirEdge()).add(uedge);
    5252
    53       Edge edge_forward(uedge, true);
    54       Edge edge_backward(uedge, false);
    55       Parent::getNotifier(Edge()).add(edge_forward);
    56       Parent::getNotifier(Edge()).add(edge_backward);
     53      std::vector<Edge> edges;
     54      edges.push_back(Edge(uedge, true));
     55      edges.push_back(Edge(uedge, false));
     56      Parent::getNotifier(Edge()).add(edges);
    5757
    5858      return uedge;
Note: See TracChangeset for help on using the changeset viewer.