Changeset 1999:2ff283124dfc for lemon – LEMON

lemon/Makefile.am

-                      r1993
+                      r1999
         bits/alteration_notifier.h \
         bits/array_map.h \
+        bits/base_extender.h \
         bits/default_map.h \
-        bits/static_map.h \
         bits/vector_map.h \
         bits/map_extender.h \

lemon/bits/alteration_notifier.h

-                      r1996
+                      r1999
  */
 #ifndef LEMON_ALTERATION_NOTIFIER_H
 #define LEMON_ALTERATION_NOTIFIER_H
+#ifndef LEMON_BITS_ALTERATION_NOTIFIER_H
+#define LEMON_BITS_ALTERATION_NOTIFIER_H
 #include <vector>
+#include <algorithm>
+#include <lemon/bits/utility.h>
 ///\ingroup graphbits
 ///\file
 ///\brief Observer registry for graph alteration observers.
+///\brief Observer notifier for graph alteration observers.
 namespace lemon {
+  /// \addtogroup graphbits
+  /// @{
+  /// \brief Registry class to register objects observes alterations in
+  /// the graph.
+  ///
+  /// This class is a registry for the objects which observe the
+  /// alterations in a container. The alteration observers can be attached
+  /// to and detached from the registry. The observers have to inherit
+  /// from the \ref AlterationNotifier::ObserverBase and override
+  /// the virtual functions in that.
+  ///
+  /// The most important application of the alteration observing is the
+  /// dynamic map implementation.
+  ///
+  /// \param _Item The item type what the observers are observing, usually
+  /// edge or node.
+  /// \ingroup graphbits
+  ///
+  /// \brief Notifier class to notify observes about alterations in
+  /// a container.
+  ///
+  /// The simple graph's can be refered as two containers, one node container
+  /// and one edge container. But they are not standard containers they
+  /// does not store values directly they are just key continars for more
+  /// value containers which are the node and edge maps.
+  ///
+  /// The graph's node and edge sets can be changed as we add or erase
+  /// nodes and edges in the graph. Lemon would like to handle easily
+  /// that the node and edge maps should contain values for all nodes or
+  /// edges. If we want to check on every indicing if the map contains
+  /// the current indicing key that cause a drawback in the performance
+  /// in the library. We use an other solution we notify all maps about
+  /// an alteration in the graph, which cause only drawback on the
+  /// alteration of the graph.
+  ///
+  /// This class provides an interface to the container. The \e first() and \e
+  /// next() member functions make possible to iterate on the keys of the
+  /// container. The \e id() function returns an integer id for each key.
+  /// The \e maxId() function gives back an upper bound of the ids.
+  ///
+  /// For the proper functonality of this class, we should notify it
+  /// about each alteration in the container. The alterations have four type
+  /// as \e add(), \e erase(), \e build() and \e clear(). The \e add() and
+  /// \e erase() signals that only one or few items added or erased to or
+  /// from the graph. If all items are erased from the graph or from an empty
+  /// graph a new graph is builded then it can be signaled with the
+  /// clear() and build() members. Important rule that if we erase items
+  /// from graph we should first signal the alteration and after that erase
+  /// them from the container, on the other way on item addition we should
+  /// first extend the container and just after that signal the alteration.
+  ///
+  /// The alteration can be observed with a class inherited from the
+  /// \e ObserverBase nested class. The signals can be handled with
+  /// overriding the virtual functions defined in the base class.
+  /// The observer base can be attached to the notifier with the
+  /// \e attach() member and can be detached with detach() function.
+  ///
+  /// Alteration observers try to be exception safe. This can be achived
+  /// when the observers does not throw exception on \e erase() and
+  /// \e clear(). Less strict condition is that the \e erase() should
+  /// not throw exception after an \e add() with the same parameter and
+  /// the \e clear() should not throw exception after a \e build().
+  ///
+  /// There are some place when the alteration observing is not completly
+  /// reliable. If we want to carry out the node degree in the graph
+  /// as in the \ref InDegMap and we use the reverseEdge that cause
+  /// unreliable functionality. Because the alteration observing signals
+  /// only erasing and adding but not the reversing it will stores bad
+  /// degrees. The sub graph adaptors cannot signal the alterations because
+  /// just a setting in the filter map can modify the graph and this cannot
+  /// be watched in any way.
+  ///
+  /// \param _Container The container which is observed.
+  /// \param _Item The item type which is obserbved.
   ///
   /// \author Balazs Dezso
   template <typename _Item>
+  template <typename _Container, typename _Item>
   class AlterationNotifier {
   public:
 …
     typedef True Notifier;
+    typedef _Container Container;
     typedef _Item Item;
     /// ObserverBase is the base class for the observers.
+    /// \brief ObserverBase is the base class for the observers.
+    ///
     /// ObserverBase is the abstract base class for the observers.
     /// It will be notified about an item was inserted into or
 …
     class ObserverBase {
     protected:
       typedef AlterationNotifier Registry;
+      typedef AlterationNotifier Notifier;
       friend class AlterationNotifier;
 …
       /// Default constructor for ObserverBase.
       ///
+      ObserverBase() : registry(0) {}
+      ObserverBase() : notifier(0) {}
+      /// \brief Constructor which attach the observer into notifier.
+      ///
+      /// Constructor which attach the observer into notifier.
+      ObserverBase(AlterationNotifier& _notifier) {
+        attach(_notifier);
+      }
+      /// \brief Constructor which attach the obserever to the same notifier.
+      ///
+      /// Constructor which attach the obserever to the same notifier as
+      /// the other observer is attached to.
       ObserverBase(const ObserverBase& copy) {
         if (copy.attached()) {
           copy.getRegistry()->attach(*this);
+          attach(*copy.getNotifier());
+        }
+      }
+      virtual ~ObserverBase() {}
+      /// \brief Destructor
+      virtual ~ObserverBase() {
+        if (attached()) {
+          detach();
+        }
+      }
       /// \brief Attaches the observer into an AlterationNotifier.
 …
       /// This member attaches the observer into an AlterationNotifier.
       ///
       void attach(AlterationNotifier& r) {
         registry = &r;
         registry->attach(*this);
+      void attach(AlterationNotifier& _notifier) {
+        notifier = &_notifier;
+        notifier->attach(*this);
+      }
 …
       ///
       void detach() {
+        if (registry) {
+          registry->detach(*this);
+        }
+      }
+      /// Gives back a pointer to the registry what the map attached into.
+      /// This function gives back a pointer to the registry what the map
+        notifier->detach(*this);
+      }
+      /// \brief Gives back a pointer to the notifier which the map
       /// attached into.
       ///
+      Registry* getRegistry() const { return const_cast<Registry*>(registry); }
+      /// This function gives back a pointer to the notifier which the map
+      /// attached into.
+      ///
+      Notifier* getNotifier() const { return const_cast<Notifier*>(notifier); }
       /// Gives back true when the observer is attached into a registry.
       bool attached() const { return registry != 0; }
+      /// Gives back true when the observer is attached into a notifier.
+      bool attached() const { return notifier != 0; }
     private:
 …
     protected:
       Registry* registry;
       int registry_index;
+      Notifier* notifier;
+      int notifier_index;
       /// \brief The member function to notificate the observer about an
 …
       virtual void add(const std::vector<Item>& items) {
+        for (int i = 0; i < (int)items.size(); ++i) {
+          add(items[i]);
+        }
+        int i;
+        try {
+          for (i = 0; i < (int)items.size(); ++i) {
+            add(items[i]);
+          }
+        } catch (...) {
+          for (int j = 0; j < i; ++j) {
+            add(items[j]);
+          }
+          throw;
+        }
+      }
 …
       /// subclasses.
       virtual void erase(const std::vector<Item>& items) {
         for (int i = 0; i < (int)items.size(); ++i) {
           erase(items[i]);
+        }
+        for (int i = 0; i < (int)items.size(); ++i) {
+          erase(items[i]);
+        }
+      }
 …
       /// overrided in the subclasses.
+      virtual void build() = 0;
+      virtual void build() {
+        Item it;
+        try {
+          for (notifier->first(it); it != INVALID; notifier->next(it)) {
+            add(it);
+          }
+        } catch (...) {
+          Item jt;
+          for (notifier->first(jt); jt != it; notifier->next(jt)) {
+            erase(jt);
+          }
+          throw;
+        }
+      }
       /// \brief The member function to notificate the observer about all
 …
       /// The clear() member function notificates the observer about all
       /// items are erased from the container. It have to be overrided in
+      /// the subclasses.
+      virtual void clear() = 0;
+      /// the subclasses.
+      virtual void clear() {
+        Item it;
+        for (notifier->first(it); it != INVALID; notifier->next(it)) {
+          erase(it);
+        }
+      }
     };
   protected:
+    typedef std::vector<ObserverBase*> Container;
     Container container;
+    const Container* container;
+    typedef std::vector<ObserverBase*> Observers;
+    Observers observers;
   public:
+    /// Default constructor.
+    /// \brief Default constructor.
     ///
     /// The default constructor of the AlterationNotifier.
+    /// It creates an empty registry.
+    AlterationNotifier() {}
+    /// Copy Constructor of the AlterationNotifier.
+    /// It creates an empty notifier.
+    AlterationNotifier()
+      : container(0) {}
+    /// \brief Constructor.
+    ///
+    /// Constructor with the observed container parameter.
+    AlterationNotifier(const Container& _container)
+      : container(&_container) {}
+    /// \brief Copy Constructor of the AlterationNotifier.
+    ///
     /// Copy constructor of the AlterationNotifier.
+    /// It creates only an empty registry because the copiable
+    /// registry's observers have to be registered still into that registry.
+    AlterationNotifier(const AlterationNotifier&) {}
+    /// Assign operator.
+    /// It creates only an empty notifier because the copiable
+    /// notifier's observers have to be registered still into that notifier.
+    AlterationNotifier(const AlterationNotifier& _notifier)
+      : container(_notifier.container) {}
+    /// \brief Destructor.
+    ///
+    /// Destructor of the AlterationNotifier.
+    ///
+    ~AlterationNotifier() {
+      typename Observers::iterator it;
+      for (it = observers.begin(); it != observers.end(); ++it) {
+        (*it)->notifier = 0;
+      }
+    }
+    /// \brief Sets the container.
+    ///
+    /// Sets the container.
+    void setContainer(const Container& _container) {
+      container = &_container;
+    }
+  protected:
+    AlterationNotifier& operator=(const AlterationNotifier&);
+  public:
+    /// \brief First item in the container.
+    ///
+    /// Returns the first item in the container. It is
+    /// for start the iteration on the container.
+    void first(Item& item) const {
+      container->first(item);
+    }
+    /// \brief Next item in the container.
+    ///
+    /// Returns the next item in the container. It is
+    /// for iterate on the container.
+    void next(Item& item) const {
+      container->next(item);
+    }
+    /// \brief Returns the id of the item.
+    ///
+    /// Returns the id of the item provided by the container.
+    int id(const Item& item) const {
+      return container->id(item);
+    }
+    /// \brief Returns the maximum id of the container.
+    ///
+    /// Returns the maximum id of the container.
+    int maxId() const {
+      return container->maxId(Item());
+    }
-    /// Assign operator for the AlterationNotifier.
-    /// It makes the notifier only empty because the copiable
-    /// notifier's observers have to be registered still into that registry.
-    AlterationNotifier& operator=(const AlterationNotifier&) {
-      typename Container::iterator it;
-      for (it = container.begin(); it != container.end(); ++it) {
-        (*it)->registry = 0;
+      }
+    }
-    /// Destructor.
-    /// Destructor of the AlterationNotifier.
-    ///
-    ~AlterationNotifier() {
-      typename Container::iterator it;
-      for (it = container.begin(); it != container.end(); ++it) {
-        (*it)->registry = 0;
+      }
+    }
   protected:
     void attach(ObserverBase& observer) {
       container.push_back(&observer);
       observer.registry = this;
       observer.registry_index = container.size()-1;
+      observers.push_back(&observer);
+      observer.notifier = this;
+      observer.notifier_index = observers.size() - 1;
+    }
     void detach(ObserverBase& base) {
       container.back()->registry_index = base.registry_index;
       container[base.registry_index] = container.back();
       container.pop_back();
       base.registry = 0;
+    void detach(ObserverBase& observer) {
+      observers.back()->notifier_index = observer.notifier_index;
+      observers[observer.notifier_index] = observers.back();
+      observers.pop_back();
+      observer.notifier = 0;
+    }
   public:
     /// \brief Notifies all the registered observers about an Item added to
     /// the container.
     ///
     /// It notifies all the registered observers about an Item added to
+    /// \brief Notifies all the registed observers about an item added to
+    /// the container.
+    ///
+    /// It notifies all the registed observers about an item added to
     /// the container.
     ///
     void add(const Item& item) {
       typename Container::iterator it;
+      typename Observers::iterator it;
       try {
         for (it = container.begin(); it != container.end(); ++it) {
+        for (it = observers.begin(); it != observers.end(); ++it) {
           (*it)->add(item);
+        }
       } catch (...) {
         typename Container::iterator jt;
         for (jt = container.begin(); jt != it; ++it) {
+        typename Observers::iterator jt;
+        for (jt = observers.begin(); jt != it; ++jt) {
           (*it)->erase(item);
+        }
 …
+    }
     /// \brief Notifies all the registered observers about more Item added to
     /// the container.
     ///
     /// It notifies all the registered observers about more Item added to
+    /// \brief Notifies all the registed observers about more item added to
+    /// the container.
+    ///
+    /// It notifies all the registed observers about more item added to
     /// the container.
     ///
     void add(const std::vector<Item>& items) {
       typename Container::iterator it;
+      typename Observers::iterator it;
       try {
         for (it = container.begin(); it != container.end(); ++it) {
+        for (it = observers.begin(); it != observers.end(); ++it) {
           (*it)->add(items);
+        }
       } catch (...) {
         typename Container::iterator jt;
         for (jt = container.begin(); jt != it; ++it) {
+        typename Observers::iterator jt;
+        for (jt = observers.begin(); jt != it; ++jt) {
           (*it)->erase(items);
+        }
 …
+    }
     /// \brief Notifies all the registered observers about an Item erased from
+    /// \brief Notifies all the registed observers about an item erased from
     /// the container.
     ///
     /// It notifies all the registered observers about an Item erased from
+    /// It notifies all the registed observers about an item erased from
     /// the container.
     ///
     void erase(const Item& key) {
       typename Container::iterator it;
       for (it = container.begin(); it != container.end(); ++it) {
+      typename Observers::iterator it;
+      for (it = observers.begin(); it != observers.end(); ++it) {
         (*it)->erase(key);
+      }
+    }
     /// \brief Notifies all the registered observers about more Item erased
+    /// \brief Notifies all the registed observers about more item erased
     /// from the container.
     ///
     /// It notifies all the registered observers about more Item erased from
+    /// It notifies all the registed observers about more item erased from
     /// the container.
     ///
     void erase(const std::vector<Item>& items) {
       typename Container::iterator it;
       for (it = container.begin(); it != container.end(); ++it) {
+      typename Observers::iterator it;
+      for (it = observers.begin(); it != observers.end(); ++it) {
         (*it)->erase(items);
+      }
+    }
     /// \brief Notifies all the registered observers about the container is
+    /// \brief Notifies all the registed observers about the container is
     /// built.
     ///
     /// Notifies all the registered observers about the container is built
+    /// Notifies all the registed observers about the container is built
     /// from an empty container.
     void build() {
       typename Container::iterator it;
+      typename Observers::iterator it;
       try {
         for (it = container.begin(); it != container.end(); ++it) {
+        for (it = observers.begin(); it != observers.end(); ++it) {
           (*it)->build();
+        }
       } catch (...) {
         typename Container::iterator jt;
         for (jt = container.begin(); jt != it; ++it) {
+        typename Observers::iterator jt;
+        for (jt = observers.begin(); jt != it; ++jt) {
           (*it)->clear();
+        }
 …
     /// \brief Notifies all the registered observers about all Items are
+    /// \brief Notifies all the registed observers about all items are
     /// erased.
     ///
     /// Notifies all the registered observers about all Items are erased
+    /// Notifies all the registed observers about all items are erased
     /// from the container.
     void clear() {
       typename Container::iterator it;
       for (it = container.begin(); it != container.end(); ++it) {
+      typename Observers::iterator it;
+      for (it = observers.begin(); it != observers.end(); ++it) {
         (*it)->clear();
+      }
 …
   };
-/// @}
+}

lemon/bits/array_map.h

-                      r1996
+                      r1999
 #include <memory>
+#include <lemon/bits/map_extender.h>
+#include <lemon/bits/traits.h>
 #include <lemon/bits/alteration_notifier.h>
-#include <lemon/concept_check.h>
-#include <lemon/concept/maps.h>
 /// \ingroup graphbits
 /// \file
+/// \brief Graph maps that construct and destruct
+/// their elements dynamically.
+/// \brief Graph map based on the array storage.
 namespace lemon {
 …
   ///
   /// The ArrayMap template class is graph map structure what
   /// automatically indates the map when a key is added to or erased from
+  /// automatically updates the map when a key is added to or erased from
   /// the map. This map uses the allocators to implement
   /// the container functionality.
   ///
+  /// The template parameter is the AlterationNotifier that the maps
+  /// will belong to and the Value.
+  template <typename _Graph,
+            typename _Item,
+            typename _Value>
+  class ArrayMap : public AlterationNotifier<_Item>::ObserverBase {
+    typedef _Item Item;
+  /// The template parameter is the Graph the current Item type and
+  /// the Value type of the map.
+  template <typename _Graph, typename _Item, typename _Value>
+  class ArrayMap
+    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
   public:
     /// The graph type of the maps.
     typedef _Graph Graph;
+    /// The item type of the map.
+    typedef _Item Item;
     /// The reference map tag.
     typedef True ReferenceMapTag;
 …
     /// The value type of the map.
     typedef _Value Value;
     /// The const reference type of the map.
     typedef const _Value& ConstReference;
 …
     typedef _Value& Reference;
+    typedef const Value ConstValue;
+    typedef Value* Pointer;
+    typedef const Value* ConstPointer;
+    typedef AlterationNotifier<_Item> Registry;
+    /// The notifier type.
+    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
     /// The MapBase of the Map which imlements the core regisitry function.
     typedef typename Registry::ObserverBase Parent;
+    typedef typename Notifier::ObserverBase Parent;
   private:
     typedef std::allocator<Value> Allocator;
   public:
 …
     ///
     /// Graph initialized map constructor.
+    ArrayMap(const Graph& _g) : graph(&_g) {
+    ArrayMap(const Graph& graph) {
+      Parent::attach(graph.getNotifier(Item()));
+      allocate_memory();
+      Notifier* notifier = Parent::getNotifier();
       Item it;
+      attach(_g.getNotifier(Item()));
+      allocate_memory();
+      for (graph->first(it); it != INVALID; graph->next(it)) {
+        int id = graph->id(it);;
+      for (notifier->first(it); it != INVALID; notifier->next(it)) {
+        int id = notifier->id(it);;
         allocator.construct(&(values[id]), Value());
+      }
 …
     ///
     /// It constructs a map and initialize all of the the map.
+    ArrayMap(const Graph& _g, const Value& _v) : graph(&_g) {
+    ArrayMap(const Graph& graph, const Value& value) {
+      Parent::attach(graph.getNotifier(Item()));
+      allocate_memory();
+      Notifier* notifier = Parent::getNotifier();
       Item it;
+      attach(_g.getNotifier(_Item()));
+      allocate_memory();
+      for (graph->first(it); it != INVALID; graph->next(it)) {
+        int id = graph->id(it);;
+        allocator.construct(&(values[id]), _v);
+      for (notifier->first(it); it != INVALID; notifier->next(it)) {
+        int id = notifier->id(it);;
+        allocator.construct(&(values[id]), value);
+      }
+    }
 …
     ///
     /// Constructor to copy a map of the same map type.
     ArrayMap(const ArrayMap& copy) : Parent(), graph(copy.graph) {
+    ArrayMap(const ArrayMap& copy) : Parent() {
       if (copy.attached()) {
         attach(*copy.getRegistry());
+        attach(*copy.getNotifier());
+      }
       capacity = copy.capacity;
       if (capacity == 0) return;
       values = allocator.allocate(capacity);
+      Notifier* notifier = Parent::getNotifier();
       Item it;
       for (graph->first(it); it != INVALID; graph->next(it)) {
         int id = graph->id(it);;
+      for (notifier->first(it); it != INVALID; notifier->next(it)) {
+        int id = notifier->id(it);;
         allocator.construct(&(values[id]), copy.values[id]);
+      }
 …
     using Parent::attached;
-    const Graph* getGraph() {
-      return graph;
+    }
   public:
 …
     /// actual keys of the graph.
     Value& operator[](const Key& key) {
       int id = graph->id(key);
+      int id = Parent::getNotifier()->id(key);
       return values[id];
+    }
 …
     /// actual keys of the graph.
     const Value& operator[](const Key& key) const {
       int id = graph->id(key);
+      int id = Parent::getNotifier()->id(key);
       return values[id];
+    }
 …
   protected:
+    /// Add a new key to the map. It called by the map registry.
+    /// \brief Adds a new key to the map.
+    ///
+    /// It adds a new key to the map. It called by the observer notifier
+    /// and it overrides the add() member function of the observer base.
     virtual void add(const Key& key) {
+      int id = graph->id(key);
+      Notifier* notifier = Parent::getNotifier();
+      int id = notifier->id(key);
       if (id >= capacity) {
         int new_capacity = (capacity == 0 ? 1 : capacity);
 …
         Value* new_values = allocator.allocate(new_capacity);
         Item it;
         for (graph->first(it); it != INVALID; graph->next(it)) {
           int jd = graph->id(it);;
+        for (notifier->first(it); it != INVALID; notifier->next(it)) {
+          int jd = notifier->id(it);;
           if (id != jd) {
             allocator.construct(&(new_values[jd]), values[jd]);
 …
+    }
+    /// \brief Adds more new keys to the map.
+    ///
+    /// It adds more new keys to the map. It called by the observer notifier
+    /// and it overrides the add() member function of the observer base.
     virtual void add(const std::vector<Key>& keys) {
+      Notifier* notifier = Parent::getNotifier();
       int max_id = -1;
       for (int i = 0; i < (int)keys.size(); ++i) {
         int id = graph->id(keys[i]);
+        int id = notifier->id(keys[i]);
         if (id > max_id) {
           max_id = id;
 …
         Value* new_values = allocator.allocate(new_capacity);
         Item it;
         for (graph->first(it); it != INVALID; graph->next(it)) {
           int id = graph->id(it);
+        for (notifier->first(it); it != INVALID; notifier->next(it)) {
+          int id = notifier->id(it);
           bool found = false;
           for (int i = 0; i < (int)keys.size(); ++i) {
             int jd = graph->id(keys[i]);
+            int jd = notifier->id(keys[i]);
             if (id == jd) {
               found = true;
 …
+      }
       for (int i = 0; i < (int)keys.size(); ++i) {
         int id = graph->id(keys[i]);
+        int id = notifier->id(keys[i]);
         allocator.construct(&(values[id]), Value());
+      }
+    }
+    /// Erase a key from the map. It called by the map registry.
+    /// \brief Erase a key from the map.
+    ///
+    /// Erase a key from the map. It called by the observer notifier
+    /// and it overrides the erase() member function of the observer base.
     virtual void erase(const Key& key) {
       int id = graph->id(key);
+      int id = Parent::getNotifier()->id(key);
       allocator.destroy(&(values[id]));
+    }
+    /// \brief Erase more keys from the map.
+    ///
+    /// Erase more keys from the map. It called by the observer notifier
+    /// and it overrides the erase() member function of the observer base.
     virtual void erase(const std::vector<Key>& keys) {
       for (int i = 0; i < (int)keys.size(); ++i) {
         int id = graph->id(keys[i]);
+        int id = Parent::getNotifier()->id(keys[i]);
         allocator.destroy(&(values[id]));
+      }
+    }
+    /// \brief Buildes the map.
+    ///
+    /// It buildes the map. It called by the observer notifier
+    /// and it overrides the build() member function of the observer base.
     virtual void build() {
+      Notifier* notifier = Parent::getNotifier();
       allocate_memory();
       Item it;
       for (graph->first(it); it != INVALID; graph->next(it)) {
         int id = graph->id(it);;
+      for (notifier->first(it); it != INVALID; notifier->next(it)) {
+        int id = notifier->id(it);;
         allocator.construct(&(values[id]), Value());
+      }
+    }
+    /// \brief Clear the map.
+    ///
+    /// It erase all items from the map. It called by the observer notifier
+    /// and it overrides the clear() member function of the observer base.
     virtual void clear() {
+      Notifier* notifier = Parent::getNotifier();
       if (capacity != 0) {
         Item it;
         for (graph->first(it); it != INVALID; graph->next(it)) {
           int id = graph->id(it);
+        for (notifier->first(it); it != INVALID; notifier->next(it)) {
+          int id = notifier->id(it);
           allocator.destroy(&(values[id]));
+        }
 …
     void allocate_memory() {
       int max_id = graph->maxId(_Item());
+      int max_id = Parent::getNotifier()->maxId();
       if (max_id == -1) {
         capacity = 0;
 …
+    }
-    const Graph* graph;
     int capacity;
     Value* values;

lemon/bits/default_map.h

-                      r1996
+                      r1999
  */
 #ifndef LEMON_DEFAULT_MAP_H
 #define LEMON_DEFAULT_MAP_H
+#ifndef LEMON_BITS_DEFAULT_MAP_H
+#define LEMON_BITS_DEFAULT_MAP_H
 #include <lemon/bits/array_map.h>
 #include <lemon/bits/vector_map.h>
-#include <lemon/bits/static_map.h>
 ///\ingroup graphbits
 ///\file
+///\brief Graph maps that construct and destruct
+///their elements dynamically.
+///\brief Graph maps that construct and destruct their elements dynamically.
 namespace lemon {
 …
   /// \e
+  template <
+    typename _Graph,
+    typename _Item,
+    typename _Value>
+  template <typename _Graph, typename _Item, typename _Value>
   class DefaultMap
     : public DefaultMapSelector<_Graph, _Item, _Value>::Map {
 …
     typedef typename Parent::Value Value;
+    DefaultMap(const Graph& _g) : Parent(_g) {}
+    DefaultMap(const Graph& _g, const Value& _v) : Parent(_g, _v) {}
+    DefaultMap(const Graph& graph) : Parent(graph) {}
+    DefaultMap(const Graph& graph, const Value& value)
+      : Parent(graph, value) {}
   };

lemon/bits/edge_set_extender.h

-                      r1996
+                      r1999
     /// The edge observer registry.
     typedef AlterationNotifier<Edge> EdgeNotifier;
+    typedef AlterationNotifier<EdgeSetExtender, Edge> EdgeNotifier;
   protected:
 …
     template <typename _Value>
     class EdgeMap
       : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
+      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
     public:
       typedef EdgeSetExtender Graph;
       typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
+      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
       EdgeMap(const Graph& _g)
 …
+    }
+    EdgeSetExtender() {
+      edge_notifier.setContainer(*this);
+    }
     ~EdgeSetExtender() {
 …
+    }
     typedef AlterationNotifier<Edge> EdgeNotifier;
     typedef AlterationNotifier<UEdge> UEdgeNotifier;
+    typedef AlterationNotifier<UEdgeSetExtender, Edge> EdgeNotifier;
+    typedef AlterationNotifier<UEdgeSetExtender, UEdge> UEdgeNotifier;
 …
     template <typename _Value>
     class EdgeMap
       : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
+      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
     public:
       typedef UEdgeSetExtender Graph;
       typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
+      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
       EdgeMap(const Graph& _g)
 …
     template <typename _Value>
     class UEdgeMap
       : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
+      : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
     public:
       typedef UEdgeSetExtender Graph;
       typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
+      typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
       UEdgeMap(const Graph& _g)
 …
+    UEdgeSetExtender() {
+      edge_notifier.setContainer(*this);
+      uedge_notifier.setContainer(*this);
+    }
     ~UEdgeSetExtender() {
       getNotifier(Edge()).clear();
       getNotifier(UEdge()).clear();
+      uedge_notifier.clear();
+      edge_notifier.clear();
+    }

lemon/bits/graph_extender.h

-                      r1996
+                      r1999
 #include <lemon/error.h>
+#include <lemon/bits/map_extender.h>
 #include <lemon/bits/default_map.h>
+#include <lemon/concept_check.h>
+#include <lemon/concept/maps.h>
 ///\ingroup graphbits
 …
     // Alterable extension
     typedef AlterationNotifier<Node> NodeNotifier;
     typedef AlterationNotifier<Edge> EdgeNotifier;
+    typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
+    typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;
 …
     template <typename _Value>
     class NodeMap
       : public IterableMapExtender<DefaultMap<Graph, Node, _Value> > {
+      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
     public:
       typedef GraphExtender Graph;
       typedef IterableMapExtender<DefaultMap<Graph, Node, _Value> > Parent;
       NodeMap(const Graph& _g)
         : Parent(_g) {}
       NodeMap(const Graph& _g, const _Value& _v)
         : Parent(_g, _v) {}
+      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
+      NodeMap(const Graph& graph)
+        : Parent(graph) {}
+      NodeMap(const Graph& graph, const _Value& value)
+        : Parent(graph, value) {}
       NodeMap& operator=(const NodeMap& cmap) {
 …
       NodeMap& operator=(const CMap& cmap) {
         checkConcept<concept::ReadMap<Node, _Value>, CMap>();
         const typename Parent::Graph* graph = Parent::getGraph();
+        const typename Parent::Notifier* notifier = Parent::getNotifier();
         Node it;
         for (graph->first(it); it != INVALID; graph->next(it)) {
+        for (notifier->first(it); it != INVALID; notifier->next(it)) {
           Parent::set(it, cmap[it]);
+        }
 …
     template <typename _Value>
     class EdgeMap
       : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
+      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
     public:
       typedef GraphExtender Graph;
       typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
       EdgeMap(const Graph& _g)
         : Parent(_g) {}
       EdgeMap(const Graph& _g, const _Value& _v)
         : Parent(_g, _v) {}
+      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
+      EdgeMap(const Graph& graph)
+        : Parent(graph) {}
+      EdgeMap(const Graph& graph, const _Value& value)
+        : Parent(graph, value) {}
       EdgeMap& operator=(const EdgeMap& cmap) {
 …
       EdgeMap& operator=(const CMap& cmap) {
         checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
         const typename Parent::Graph* graph = Parent::getGraph();
+        const typename Parent::Notifier* notifier = Parent::getNotifier();
         Edge it;
         for (graph->first(it); it != INVALID; graph->next(it)) {
+        for (notifier->first(it); it != INVALID; notifier->next(it)) {
           Parent::set(it, cmap[it]);
+        }
 …
+    }
+    GraphExtender() {
+      node_notifier.setContainer(*this);
+      edge_notifier.setContainer(*this);
+    }
     ~GraphExtender() {
       getNotifier(Edge()).clear();
       getNotifier(Node()).clear();
+      edge_notifier.clear();
+      node_notifier.clear();
+    }
   };
-  /// \ingroup graphbits
-  ///
-  /// \brief BaseExtender for the UGraphs
-  template <typename Base>
-  class UGraphBaseExtender : public Base {
-  public:
-    typedef Base Parent;
-    typedef typename Parent::Edge UEdge;
-    typedef typename Parent::Node Node;
-    typedef True UndirectedTag;
-    class Edge : public UEdge {
-      friend class UGraphBaseExtender;
-    protected:
-      bool forward;
-      Edge(const UEdge &ue, bool _forward) :
-        UEdge(ue), forward(_forward) {}
-    public:
-      Edge() {}
-      /// Invalid edge constructor
-      Edge(Invalid i) : UEdge(i), forward(true) {}
-      bool operator==(const Edge &that) const {
-        return forward==that.forward && UEdge(*this)==UEdge(that);
+      }
-      bool operator!=(const Edge &that) const {
-        return forward!=that.forward || UEdge(*this)!=UEdge(that);
+      }
-      bool operator<(const Edge &that) const {
-        return forward<that.forward ||
-          (!(that.forward<forward) && UEdge(*this)<UEdge(that));
+      }
-    };
-    using Parent::source;
-    /// Source of the given Edge.
-    Node source(const Edge &e) const {
-      return e.forward ? Parent::source(e) : Parent::target(e);
+    }
-    using Parent::target;
-    /// Target of the given Edge.
-    Node target(const Edge &e) const {
-      return e.forward ? Parent::target(e) : Parent::source(e);
+    }
-    /// \brief Directed edge from an undirected edge.
-    ///
-    /// Returns a directed edge corresponding to the specified UEdge.
-    /// If the given bool is true the given undirected edge and the
-    /// returned edge have the same source node.
-    static Edge direct(const UEdge &ue, bool d) {
-      return Edge(ue, d);
+    }
-    /// Returns whether the given directed edge is same orientation as the
-    /// corresponding undirected edge.
-    ///
-    /// \todo reference to the corresponding point of the undirected graph
-    /// concept. "What does the direction of an undirected edge mean?"
-    static bool direction(const Edge &e) { return e.forward; }
-    using Parent::first;
-    using Parent::next;
-    void first(Edge &e) const {
-      Parent::first(e);
-      e.forward=true;
+    }
-    void next(Edge &e) const {
-      if( e.forward ) {
-        e.forward = false;
+      }
-      else {
-        Parent::next(e);
-        e.forward = true;
+      }
+    }
-    void firstOut(Edge &e, const Node &n) const {
-      Parent::firstIn(e,n);
-      if( UEdge(e) != INVALID ) {
-        e.forward = false;
+      }
-      else {
-        Parent::firstOut(e,n);
-        e.forward = true;
+      }
+    }
-    void nextOut(Edge &e) const {
-      if( ! e.forward ) {
-        Node n = Parent::target(e);
-        Parent::nextIn(e);
-        if( UEdge(e) == INVALID ) {
-          Parent::firstOut(e, n);
-          e.forward = true;
+        }
+      }
-      else {
-        Parent::nextOut(e);
+      }
+    }
-    void firstIn(Edge &e, const Node &n) const {
-      Parent::firstOut(e,n);
-      if( UEdge(e) != INVALID ) {
-        e.forward = false;
+      }
-      else {
-        Parent::firstIn(e,n);
-        e.forward = true;
+      }
+    }
-    void nextIn(Edge &e) const {
-      if( ! e.forward ) {
-        Node n = Parent::source(e);
-        Parent::nextOut(e);
-        if( UEdge(e) == INVALID ) {
-          Parent::firstIn(e, n);
-          e.forward = true;
+        }
+      }
-      else {
-        Parent::nextIn(e);
+      }
+    }
-    void firstInc(UEdge &e, bool &d, const Node &n) const {
-      d = true;
-      Parent::firstOut(e, n);
-      if (e != INVALID) return;
-      d = false;
-      Parent::firstIn(e, n);
+    }
-    void nextInc(UEdge &e, bool &d) const {
-      if (d) {
-        Node s = Parent::source(e);
-        Parent::nextOut(e);
-        if (e != INVALID) return;
-        d = false;
-        Parent::firstIn(e, s);
-      } else {
-        Parent::nextIn(e);
+      }
+    }
-    Node nodeFromId(int id) const {
-      return Parent::nodeFromId(id);
+    }
-    Edge edgeFromId(int id) const {
-      return direct(Parent::edgeFromId(id >> 1), bool(id & 1));
+    }
-    UEdge uEdgeFromId(int id) const {
-      return Parent::edgeFromId(id >> 1);
+    }
-    int id(const Node &n) const {
-      return Parent::id(n);
+    }
-    int id(const UEdge &e) const {
-      return Parent::id(e);
+    }
-    int id(const Edge &e) const {
-      return 2 * Parent::id(e) + int(e.forward);
+    }
-    int maxNodeId() const {
-      return Parent::maxNodeId();
+    }
-    int maxEdgeId() const {
-      return 2 * Parent::maxEdgeId() + 1;
+    }
-    int maxUEdgeId() const {
-      return Parent::maxEdgeId();
+    }
-    int edgeNum() const {
-      return 2 * Parent::edgeNum();
+    }
-    int uEdgeNum() const {
-      return Parent::edgeNum();
+    }
-    Edge findEdge(Node source, Node target, Edge prev) const {
-      if (prev == INVALID) {
-        UEdge edge = Parent::findEdge(source, target);
-        if (edge != INVALID) return direct(edge, true);
-        edge = Parent::findEdge(target, source);
-        if (edge != INVALID) return direct(edge, false);
-      } else if (direction(prev)) {
-        UEdge edge = Parent::findEdge(source, target, prev);
-        if (edge != INVALID) return direct(edge, true);
-        edge = Parent::findEdge(target, source);
-        if (edge != INVALID) return direct(edge, false);
-      } else {
-        UEdge edge = Parent::findEdge(target, source, prev);
-        if (edge != INVALID) return direct(edge, false);
+      }
-      return INVALID;
+    }
-    UEdge findUEdge(Node source, Node target, UEdge prev) const {
-      if (prev == INVALID) {
-        UEdge edge = Parent::findEdge(source, target);
-        if (edge != INVALID) return edge;
-        edge = Parent::findEdge(target, source);
-        if (edge != INVALID) return edge;
-      } else if (Parent::source(prev) == source) {
-        UEdge edge = Parent::findEdge(source, target, prev);
-        if (edge != INVALID) return edge;
-        edge = Parent::findEdge(target, source);
-        if (edge != INVALID) return edge;
-      } else {
-        UEdge edge = Parent::findEdge(target, source, prev);
-        if (edge != INVALID) return edge;
+      }
-      return INVALID;
+    }
-  };
   /// \ingroup graphbits
 …
     // Alterable extension
     typedef AlterationNotifier<Node> NodeNotifier;
     typedef AlterationNotifier<Edge> EdgeNotifier;
     typedef AlterationNotifier<UEdge> UEdgeNotifier;
+    typedef AlterationNotifier<UGraphExtender, Node> NodeNotifier;
+    typedef AlterationNotifier<UGraphExtender, Edge> EdgeNotifier;
+    typedef AlterationNotifier<UGraphExtender, UEdge> UEdgeNotifier;
 …
     template <typename _Value>
     class NodeMap
       : public IterableMapExtender<DefaultMap<Graph, Node, _Value> > {
+      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
     public:
       typedef UGraphExtender Graph;
       typedef IterableMapExtender<DefaultMap<Graph, Node, _Value> > Parent;
       NodeMap(const Graph& _g)
         : Parent(_g) {}
       NodeMap(const Graph& _g, const _Value& _v)
         : Parent(_g, _v) {}
+      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
+      NodeMap(const Graph& graph)
+        : Parent(graph) {}
+      NodeMap(const Graph& graph, const _Value& value)
+        : Parent(graph, value) {}
       NodeMap& operator=(const NodeMap& cmap) {
 …
       NodeMap& operator=(const CMap& cmap) {
         checkConcept<concept::ReadMap<Node, _Value>, CMap>();
         const typename Parent::Graph* graph = Parent::getGraph();
+        const typename Parent::Notifier* notifier = Parent::getNotifier();
         Node it;
         for (graph->first(it); it != INVALID; graph->next(it)) {
+        for (notifier->first(it); it != INVALID; notifier->next(it)) {
           Parent::set(it, cmap[it]);
+        }
 …
     template <typename _Value>
     class EdgeMap
       : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
+      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
     public:
       typedef UGraphExtender Graph;
       typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
       EdgeMap(const Graph& _g)
         : Parent(_g) {}
       EdgeMap(const Graph& _g, const _Value& _v)
         : Parent(_g, _v) {}
+      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
+      EdgeMap(const Graph& graph)
+        : Parent(graph) {}
+      EdgeMap(const Graph& graph, const _Value& value)
+        : Parent(graph, value) {}
       EdgeMap& operator=(const EdgeMap& cmap) {
 …
       EdgeMap& operator=(const CMap& cmap) {
         checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
         const typename Parent::Graph* graph = Parent::getGraph();
+        const typename Parent::Notifier* notifier = Parent::getNotifier();
         Edge it;
         for (graph->first(it); it != INVALID; graph->next(it)) {
+        for (notifier->first(it); it != INVALID; notifier->next(it)) {
           Parent::set(it, cmap[it]);
+        }
 …
     template <typename _Value>
     class UEdgeMap
       : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
+      : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
     public:
       typedef UGraphExtender Graph;
       typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
       UEdgeMap(const Graph& _g)
         : Parent(_g) {}
       UEdgeMap(const Graph& _g, const _Value& _v)
         : Parent(_g, _v) {}
+      typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
+      UEdgeMap(const Graph& graph)
+        : Parent(graph) {}
+      UEdgeMap(const Graph& graph, const _Value& value)
+        : Parent(graph, value) {}
       UEdgeMap& operator=(const UEdgeMap& cmap) {
 …
       UEdgeMap& operator=(const CMap& cmap) {
         checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
         const typename Parent::Graph* graph = Parent::getGraph();
         UEdge it;
         for (graph->first(it); it != INVALID; graph->next(it)) {
+        const typename Parent::Notifier* notifier = Parent::getNotifier();
+        Edge it;
+        for (notifier->first(it); it != INVALID; notifier->next(it)) {
           Parent::set(it, cmap[it]);
+        }
 …
+    }
+    UGraphExtender() {
+      node_notifier.setContainer(*this);
+      edge_notifier.setContainer(*this);
+      uedge_notifier.setContainer(*this);
+    }
     ~UGraphExtender() {
+      getNotifier(Edge()).clear();
+      getNotifier(UEdge()).clear();
+      getNotifier(Node()).clear();
+    }
+  };
+  /// \ingroup graphbits
+  ///
+  /// \brief BaseExtender for the BpUGraphs
+  template <typename Base>
+  class BpUGraphBaseExtender : public Base {
+  public:
+    typedef Base Parent;
+    typedef BpUGraphBaseExtender Graph;
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge UEdge;
+    using Parent::first;
+    using Parent::next;
+    using Parent::id;
+    class ANode : public Node {
+      friend class BpUGraphBaseExtender;
+    public:
+      ANode() {}
+      ANode(const Node& node) : Node(node) {
+        LEMON_ASSERT(Parent::aNode(node) || node == INVALID,
+                     typename Parent::NodeSetError());
+      }
+      ANode(Invalid) : Node(INVALID) {}
+    };
+    void first(ANode& node) const {
+      Parent::firstANode(static_cast<Node&>(node));
+    }
+    void next(ANode& node) const {
+      Parent::nextANode(static_cast<Node&>(node));
+    }
+    int id(const ANode& node) const {
+      return Parent::aNodeId(node);
+    }
+    class BNode : public Node {
+      friend class BpUGraphBaseExtender;
+    public:
+      BNode() {}
+      BNode(const Node& node) : Node(node) {
+        LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
+                     typename Parent::NodeSetError());
+      }
+      BNode(Invalid) : Node(INVALID) {}
+    };
+    void first(BNode& node) const {
+      Parent::firstBNode(static_cast<Node&>(node));
+    }
+    void next(BNode& node) const {
+      Parent::nextBNode(static_cast<Node&>(node));
+    }
+    int id(const BNode& node) const {
+      return Parent::aNodeId(node);
+    }
+    Node source(const UEdge& edge) const {
+      return aNode(edge);
+    }
+    Node target(const UEdge& edge) const {
+      return bNode(edge);
+    }
+    void firstInc(UEdge& edge, bool& direction, const Node& node) const {
+      if (Parent::aNode(node)) {
+        Parent::firstOut(edge, node);
+        direction = true;
+      } else {
+        Parent::firstIn(edge, node);
+        direction = static_cast<UEdge&>(edge) == INVALID;
+      }
+    }
+    void nextInc(UEdge& edge, bool& direction) const {
+      if (direction) {
+        Parent::nextOut(edge);
+      } else {
+        Parent::nextIn(edge);
+        if (edge == INVALID) direction = true;
+      }
+    }
+    int maxUEdgeId() const {
+      return Parent::maxEdgeId();
+    }
+    UEdge uEdgeFromId(int id) const {
+      return Parent::edgeFromId(id);
+    }
+    class Edge : public UEdge {
+      friend class BpUGraphBaseExtender;
+    protected:
+      bool forward;
+      Edge(const UEdge& edge, bool _forward)
+        : UEdge(edge), forward(_forward) {}
+    public:
+      Edge() {}
+      Edge (Invalid) : UEdge(INVALID), forward(true) {}
+      bool operator==(const Edge& i) const {
+        return UEdge::operator==(i) && forward == i.forward;
+      }
+      bool operator!=(const Edge& i) const {
+        return UEdge::operator!=(i) || forward != i.forward;
+      }
+      bool operator<(const Edge& i) const {
+        return UEdge::operator<(i) ||
+          (!(i.forward<forward) && UEdge(*this)<UEdge(i));
+      }
+    };
+    void first(Edge& edge) const {
+      Parent::first(static_cast<UEdge&>(edge));
+      edge.forward = true;
+    }
+    void next(Edge& edge) const {
+      if (!edge.forward) {
+        Parent::next(static_cast<UEdge&>(edge));
+      }
+      edge.forward = !edge.forward;
+    }
+    void firstOut(Edge& edge, const Node& node) const {
+      if (Parent::aNode(node)) {
+        Parent::firstOut(edge, node);
+        edge.forward = true;
+      } else {
+        Parent::firstIn(edge, node);
+        edge.forward = static_cast<UEdge&>(edge) == INVALID;
+      }
+    }
+    void nextOut(Edge& edge) const {
+      if (edge.forward) {
+        Parent::nextOut(edge);
+      } else {
+        Parent::nextIn(edge);
+        edge.forward = static_cast<UEdge&>(edge) == INVALID;
+      }
+    }
+    void firstIn(Edge& edge, const Node& node) const {
+      if (Parent::bNode(node)) {
+        Parent::firstIn(edge, node);
+        edge.forward = true;
+      } else {
+        Parent::firstOut(edge, node);
+        edge.forward = static_cast<UEdge&>(edge) == INVALID;
+      }
+    }
+    void nextIn(Edge& edge) const {
+      if (edge.forward) {
+        Parent::nextIn(edge);
+      } else {
+        Parent::nextOut(edge);
+        edge.forward = static_cast<UEdge&>(edge) == INVALID;
+      }
+    }
+    Node source(const Edge& edge) const {
+      return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);
+    }
+    Node target(const Edge& edge) const {
+      return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);
+    }
+    int id(const Edge& edge) const {
+      return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1);
+    }
+    Edge edgeFromId(int id) const {
+      return Edge(Parent::fromId(id >> 1, UEdge()), (id & 1) == 0);
+    }
+    int maxEdgeId() const {
+      return (Parent::maxId(UEdge()) << 1) + 1;
+    }
+    bool direction(const Edge& edge) const {
+      return edge.forward;
+    }
+    Edge direct(const UEdge& edge, bool direction) const {
+      return Edge(edge, direction);
+    }
+      uedge_notifier.clear();
+      edge_notifier.clear();
+      node_notifier.clear();
+    }
   };
 …
+    }
     typedef AlterationNotifier<Node> NodeNotifier;
     typedef AlterationNotifier<BNode> BNodeNotifier;
     typedef AlterationNotifier<ANode> ANodeNotifier;
     typedef AlterationNotifier<Edge> EdgeNotifier;
     typedef AlterationNotifier<UEdge> UEdgeNotifier;
+    typedef AlterationNotifier<BpUGraphExtender, ANode> ANodeNotifier;
+    typedef AlterationNotifier<BpUGraphExtender, BNode> BNodeNotifier;
+    typedef AlterationNotifier<BpUGraphExtender, Node> NodeNotifier;
+    typedef AlterationNotifier<BpUGraphExtender, Edge> EdgeNotifier;
+    typedef AlterationNotifier<BpUGraphExtender, UEdge> UEdgeNotifier;
   protected:
     mutable NodeNotifier nodeNotifier;
     mutable BNodeNotifier bNodeNotifier;
     mutable ANodeNotifier aNodeNotifier;
     mutable EdgeNotifier edgeNotifier;
     mutable UEdgeNotifier uEdgeNotifier;
+    mutable ANodeNotifier anode_notifier;
+    mutable BNodeNotifier bnode_notifier;
+    mutable NodeNotifier node_notifier;
+    mutable EdgeNotifier edge_notifier;
+    mutable UEdgeNotifier uedge_notifier;
   public:
     NodeNotifier& getNotifier(Node) const {
+      return nodeNotifier;
+      return node_notifier;
+    }
+    ANodeNotifier& getNotifier(ANode) const {
+      return anode_notifier;
+    }
     BNodeNotifier& getNotifier(BNode) const {
+      return bNodeNotifier;
+    }
+    ANodeNotifier& getNotifier(ANode) const {
+      return aNodeNotifier;
+      return bnode_notifier;
+    }
     EdgeNotifier& getNotifier(Edge) const {
       return edgeNotifier;
+      return edge_notifier;
+    }
     UEdgeNotifier& getNotifier(UEdge) const {
       return uEdgeNotifier;
+      return uedge_notifier;
+    }
 …
     template <typename _Value>
     class ANodeMap
       : public IterableMapExtender<DefaultMap<Graph, ANode, _Value> > {
+      : public MapExtender<DefaultMap<Graph, ANode, _Value> > {
     public:
       typedef BpUGraphExtender Graph;
+      typedef IterableMapExtender<DefaultMap<Graph, ANode, _Value> >
+      Parent;
+      ANodeMap(const Graph& _g)
+        : Parent(_g) {}
+      ANodeMap(const Graph& _g, const _Value& _v)
+        : Parent(_g, _v) {}
+      typedef MapExtender<DefaultMap<Graph, ANode, _Value> > Parent;
+      ANodeMap(const Graph& graph)
+        : Parent(graph) {}
+      ANodeMap(const Graph& graph, const _Value& value)
+        : Parent(graph, value) {}
       ANodeMap& operator=(const ANodeMap& cmap) {
 …
     template <typename _Value>
     class BNodeMap
       : public IterableMapExtender<DefaultMap<Graph, BNode, _Value> > {
+      : public MapExtender<DefaultMap<Graph, BNode, _Value> > {
     public:
       typedef BpUGraphExtender Graph;
+      typedef IterableMapExtender<DefaultMap<Graph, BNode, _Value> >
+      Parent;
+      BNodeMap(const Graph& _g)
+        : Parent(_g) {}
+      BNodeMap(const Graph& _g, const _Value& _v)
+        : Parent(_g, _v) {}
+      typedef MapExtender<DefaultMap<Graph, BNode, _Value> > Parent;
+      BNodeMap(const Graph& graph)
+        : Parent(graph) {}
+      BNodeMap(const Graph& graph, const _Value& value)
+        : Parent(graph, value) {}
       BNodeMap& operator=(const BNodeMap& cmap) {
 …
       /// The reference type of the map;
+      typedef typename BNodeMap<_Value>::Reference Reference;
+      /// The pointer type of the map;
+      typedef typename BNodeMap<_Value>::Pointer Pointer;
+      /// The const value type of the map.
+      typedef const Value ConstValue;
+      typedef typename ANodeMap<_Value>::Reference Reference;
       /// The const reference type of the map;
+      typedef typename BNodeMap<_Value>::ConstReference ConstReference;
+      /// The pointer type of the map;
+      typedef typename BNodeMap<_Value>::ConstPointer ConstPointer;
+      typedef typename ANodeMap<_Value>::ConstReference ConstReference;
       typedef True ReferenceMapTag;
       NodeMapBase(const Graph& _g)
         : aNodeMap(_g), bNodeMap(_g) {}
       NodeMapBase(const Graph& _g, const _Value& _v)
         : aNodeMap(_g, _v), bNodeMap(_g, _v) {}
+      NodeMapBase(const Graph& graph)
+        : aNodeMap(graph), bNodeMap(graph) {}
+      NodeMapBase(const Graph& graph, const _Value& value)
+        : aNodeMap(graph, value), bNodeMap(graph, value) {}
       ConstReference operator[](const Key& node) const {
 …
     template <typename _Value>
     class NodeMap
       : public IterableMapExtender<NodeMapBase<_Value> > {
+      : public MapExtender<NodeMapBase<_Value> > {
     public:
       typedef BpUGraphExtender Graph;
       typedef IterableMapExtender< NodeMapBase<_Value> > Parent;
       NodeMap(const Graph& _g)
         : Parent(_g) {}
       NodeMap(const Graph& _g, const _Value& _v)
         : Parent(_g, _v) {}
+      typedef MapExtender< NodeMapBase<_Value> > Parent;
+      NodeMap(const Graph& graph)
+        : Parent(graph) {}
+      NodeMap(const Graph& graph, const _Value& value)
+        : Parent(graph, value) {}
       NodeMap& operator=(const NodeMap& cmap) {
 …
       NodeMap& operator=(const CMap& cmap) {
         checkConcept<concept::ReadMap<Node, _Value>, CMap>();
         const typename Parent::Graph* graph = Parent::getGraph();
         Node it;
         for (graph->first(it); it != INVALID; graph->next(it)) {
+        const typename Parent::Notifier* notifier = Parent::getNotifier();
+        Edge it;
+        for (notifier->first(it); it != INVALID; notifier->next(it)) {
           Parent::set(it, cmap[it]);
+        }
 …
     template <typename _Value>
     class EdgeMap
       : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
+      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
     public:
       typedef BpUGraphExtender Graph;
       typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
       EdgeMap(const Graph& _g)
         : Parent(_g) {}
       EdgeMap(const Graph& _g, const _Value& _v)
         : Parent(_g, _v) {}
+      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
+      EdgeMap(const Graph& graph)
+        : Parent(graph) {}
+      EdgeMap(const Graph& graph, const _Value& value)
+        : Parent(graph, value) {}
       EdgeMap& operator=(const EdgeMap& cmap) {
 …
       EdgeMap& operator=(const CMap& cmap) {
         checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
         const typename Parent::Graph* graph = Parent::getGraph();
+        const typename Parent::Notifier* notifier = Parent::getNotifier();
         Edge it;
         for (graph->first(it); it != INVALID; graph->next(it)) {
+        for (notifier->first(it); it != INVALID; notifier->next(it)) {
           Parent::set(it, cmap[it]);
+        }
 …
     template <typename _Value>
     class UEdgeMap
       : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
+      : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
     public:
       typedef BpUGraphExtender Graph;
+      typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> >
+      Parent;
+      UEdgeMap(const Graph& _g)
+        : Parent(_g) {}
+      UEdgeMap(const Graph& _g, const _Value& _v)
+        : Parent(_g, _v) {}
+      typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
+      UEdgeMap(const Graph& graph)
+        : Parent(graph) {}
+      UEdgeMap(const Graph& graph, const _Value& value)
+        : Parent(graph, value) {}
       UEdgeMap& operator=(const UEdgeMap& cmap) {
 …
       UEdgeMap& operator=(const CMap& cmap) {
         checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
         const typename Parent::Graph* graph = Parent::getGraph();
         UEdge it;
         for (graph->first(it); it != INVALID; graph->next(it)) {
+        const typename Parent::Notifier* notifier = Parent::getNotifier();
+        Edge it;
+        for (notifier->first(it); it != INVALID; notifier->next(it)) {
           Parent::set(it, cmap[it]);
+        }
 …
+    BpUGraphExtender() {
+      anode_notifier.setContainer(*this);
+      bnode_notifier.setContainer(*this);
+      node_notifier.setContainer(*this);
+      edge_notifier.setContainer(*this);
+      uedge_notifier.setContainer(*this);
+    }
     ~BpUGraphExtender() {
       getNotifier(Edge()).clear();
       getNotifier(UEdge()).clear();
       getNotifier(Node()).clear();
       getNotifier(BNode()).clear();
       getNotifier(ANode()).clear();
+      uedge_notifier.clear();
+      edge_notifier.clear();
+      node_notifier.clear();
+      anode_notifier.clear();
+      bnode_notifier.clear();
+    }

lemon/bits/map_extender.h

-                      r1996
+                      r1999
   /// \ingroup graphbits
+  ///
+  /// \brief Extender for maps
   template <typename _Map>
   class IterableMapExtender : public _Map {
+  class MapExtender : public _Map {
   public:
     typedef _Map Parent;
     typedef IterableMapExtender Map;
+    typedef MapExtender Map;
 …
     friend class ConstMapIt;
-  protected:
-    using Parent::getGraph;
   public:
+    IterableMapExtender(const Graph& graph) : Parent(graph) {}
+    MapExtender(const Graph& graph)
+      : Parent(graph) {}
     IterableMapExtender(const Graph& graph, const Value& value)
+    MapExtender(const Graph& graph, const Value& value)
       : Parent(graph, value) {}
     class MapIt : public ItemSetTraits<Graph, Item>::ItemIt {
+    class MapIt : public Item {
     public:
+      typedef typename ItemSetTraits<Graph, Item>::ItemIt Parent;
+      typedef Item Parent;
       typedef typename Map::Value Value;
+      MapIt(Map& _map) : Parent(*_map.getGraph()), map(_map) {}
+      MapIt() {}
+      MapIt(Invalid i) : Parent(i) { }
+      explicit MapIt(Map& _map) : map(_map) {
+        map.getNotifier()->first(*this);
+      }
+      MapIt(const Map& _map, const Item& item)
+        : Parent(item), map(_map) {}
+      MapIt& operator++() {
+        map.getNotifier()->next(*this);
+        return *this;
+      }
       typename MapTraits<Map>::ConstReturnValue operator*() const {
 …
     };
     class ConstMapIt : public ItemSetTraits<Graph, Key>::ItemIt {
+    class ConstMapIt : public Item {
     public:
       typedef typename ItemSetTraits<Graph, Key>::ItemIt Parent;
+      typedef Item Parent;
       typedef typename Map::Value Value;
+      ConstMapIt() {}
+      ConstMapIt(const Map& _map) : Parent(*_map.getGraph()), map(_map) {}
+      ConstMapIt(Invalid i) : Parent(i) { }
+      explicit ConstMapIt(Map& _map) : map(_map) {
+        map.getNotifier()->first(*this);
+      }
+      ConstMapIt(const Map& _map, const Item& item)
+        : Parent(item), map(_map) {}
+      ConstMapIt& operator++() {
+        map.getNotifier()->next(*this);
+        return *this;
+      }
       typename MapTraits<Map>::ConstReturnValue operator*() const {
         return map[*this];
+      }
     protected:
       const Map& map;
     };
     class ItemIt : public ItemSetTraits<Graph, Key>::ItemIt {
+    class ItemIt : Item {
     public:
+      typedef typename ItemSetTraits<Graph, Key>::ItemIt Parent;
+      typedef Item Parent;
+      ItemIt() {}
+      ItemIt(Map& _map) : Parent(*_map.getGraph()) {}
+      ItemIt(Invalid i) : Parent(i) { }
+      explicit ItemIt(Map& _map) : map(_map) {
+        map->getNotifier()->first(*this);
+      }
+      ItemIt(const Map& _map, const Item& item)
+        : Parent(item), map(_map) {}
+      ItemIt& operator++() {
+        map.getNotifier()->next(*this);
+        return *this;
+      }
+    protected:
+      const Map& map;
     };

lemon/bits/vector_map.h

-                      r1996
+                      r1999
  */
 #ifndef LEMON_VECTOR_MAP_H
 #define LEMON_VECTOR_MAP_H
+#ifndef LEMON_BITS_VECTOR_MAP_H
+#define LEMON_BITS_VECTOR_MAP_H
 #include <vector>
 #include <algorithm>
+#include <lemon/bits/traits.h>
 #include <lemon/bits/utility.h>
+#include <lemon/bits/map_extender.h>
 #include <lemon/bits/alteration_notifier.h>
+#include <lemon/concept_check.h>
+#include <lemon/concept/maps.h>
+/// \ingroup graphbits
+///\ingroup graphbits
 ///
 ///\file
 ///\brief Vector based graph maps.
 namespace lemon {
 …
   ///
   /// The VectorMap template class is graph map structure what
   /// automatically indates the map when a key is added to or erased from
+  /// automatically updates the map when a key is added to or erased from
   /// the map. This map factory uses the allocators to implement
   /// the container functionality. This map factory
   /// uses the std::vector to implement the container function.
   ///
   /// \param Registry The AlterationNotifier that will notify this map.
+  /// \param Notifier The AlterationNotifier that will notify this map.
   /// \param Item The item type of the graph items.
   /// \param Value The value type of the map.
   ///
+  /// \author Balazs Dezso
+  template <
+    typename _Graph,
+    typename _Item,
+    typename _Value
+    >
+  class VectorMap : public AlterationNotifier<_Item>::ObserverBase {
+  /// \author Balazs Dezso
+  template <typename _Graph, typename _Item, typename _Value>
+  class VectorMap
+    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
   private:
 …
     /// The graph type of the map.
     typedef _Graph Graph;
+    /// The item type of the map.
+    typedef _Item Item;
     /// The reference map tag.
     typedef True ReferenceMapTag;
 …
     typedef _Value Value;
+    typedef AlterationNotifier<_Item> Registry;
+    /// The notifier type.
+    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
     /// The map type.
     typedef VectorMap Map;
     /// The base class of the map.
     typedef typename Registry::ObserverBase Parent;
+    typedef typename Notifier::ObserverBase Parent;
     /// The reference type of the map;
     typedef typename Container::reference Reference;
-    /// The pointer type of the map;
-    typedef typename Container::pointer Pointer;
-    /// The const value type of the map.
-    typedef const Value ConstValue;
     /// The const reference type of the map;
     typedef typename Container::const_reference ConstReference;
+    /// The pointer type of the map;
+    typedef typename Container::const_pointer ConstPointer;
+    /// \brief Constructor to attach the new map into the registry.
+    ///
+    /// It constructs a map and attachs it into the registry.
+    /// \brief Constructor to attach the new map into the notifier.
+    ///
+    /// It constructs a map and attachs it into the notifier.
     /// It adds all the items of the graph to the map.
     VectorMap(const Graph& _g) : graph(&_g) {
       attach(_g.getNotifier(_Item()));
       build();
+    VectorMap(const Graph& graph) {
+      Parent::attach(graph.getNotifier(Item()));
+      container.resize(Parent::getNotifier()->maxId() + 1);
+    }
 …
     /// It constructs a map uses a given value to initialize the map.
     /// It adds all the items of the graph to the map.
     VectorMap(const Graph& _g, const Value& _v) : graph(&_g) {
       attach(_g.getNotifier(_Item()));
       container.resize(graph->maxId(_Item()) + 1, _v);
+    VectorMap(const Graph& graph, const Value& value) {
+      Parent::attach(graph.getNotifier(Item()));
+      container.resize(Parent::getNotifier()->maxId() + 1, value);
+    }
 …
     ///
     /// Copy constructor.
+    VectorMap(const VectorMap& _copy)
+      : Parent(), graph(_copy.getGraph()) {
+    VectorMap(const VectorMap& _copy) : Parent() {
       if (_copy.attached()) {
         attach(*_copy.getRegistry());
+        Parent::attach(*_copy.getNotifier());
         container = _copy.container;
+      }
+    }
-    /// \brief Destrcutor
-    ///
-    /// Destructor.
-    virtual ~VectorMap() {
-      if (attached()) {
-        detach();
+      }
+    }
   private:
     VectorMap& operator=(const VectorMap&);
-  protected:
-    using Parent::attach;
-    using Parent::detach;
-    using Parent::attached;
-    const Graph* getGraph() const {
-      return graph;
+    }
   public:
 …
     /// actual items of the graph.
     Reference operator[](const Key& key) {
       return container[graph->id(key)];
+      return container[Parent::getNotifier()->id(key)];
+    }
 …
     /// actual items of the graph.
     ConstReference operator[](const Key& key) const {
       return container[graph->id(key)];
+      return container[Parent::getNotifier()->id(key)];
+    }
 …
     /// \brief Adds a new key to the map.
     ///
     /// It adds a new key to the map. It called by the observer registry
+    /// It adds a new key to the map. It called by the observer notifier
     /// and it overrides the add() member function of the observer base.
     virtual void add(const Key& key) {
       int id = graph->id(key);
+      int id = Parent::getNotifier()->id(key);
       if (id >= (int)container.size()) {
         container.resize(id + 1);
 …
     /// \brief Adds more new keys to the map.
     ///
     /// It adds more new keys to the map. It called by the observer registry
+    /// It adds more new keys to the map. It called by the observer notifier
     /// and it overrides the add() member function of the observer base.
     virtual void add(const std::vector<Key>& keys) {
+      int max = container.size() - 1;
       for (int i = 0; i < (int)keys.size(); ++i) {
+        add(keys[i]);
+      }
+        int id = Parent::getNotifier()->id(keys[i]);
+        if (id >= max) {
+          max = id;
+        }
+      }
+      container.resize(max + 1);
+    }
     /// \brief Erase a key from the map.
     ///
     /// Erase a key from the map. It called by the observer registry
+    /// Erase a key from the map. It called by the observer notifier
     /// and it overrides the erase() member function of the observer base.
+    virtual void erase(const Key&) {}
+    virtual void erase(const Key& key) {
+      container[Parent::getNotifier()->id(key)] = Value();
+    }
     /// \brief Erase more keys from the map.
     ///
     /// Erase more keys from the map. It called by the observer registry
+    /// Erase more keys from the map. It called by the observer notifier
     /// and it overrides the erase() member function of the observer base.
+    virtual void erase(const std::vector<Key>&) {}
+    virtual void erase(const std::vector<Key>& keys) {
+      for (int i = 0; i < (int)keys.size(); ++i) {
+        container[Parent::getNotifier()->id(keys[i])] = Value();
+      }
+    }
     /// \brief Buildes the map.
     ///
     /// It buildes the map. It called by the observer registry
+    /// It buildes the map. It called by the observer notifier
     /// and it overrides the build() member function of the observer base.
     virtual void build() {
+      container.resize(graph->maxId(_Item()) + 1);
+      int size = Parent::getNotifier()->maxId() + 1;
+      container.reserve(size);
+      container.resize(size);
+    }
     /// \brief Clear the map.
     ///
     /// It erase all items from the map. It called by the observer registry
+    /// It erase all items from the map. It called by the observer notifier
     /// and it overrides the clear() member function of the observer base.
     virtual void clear() {
 …
     Container container;
-    const Graph *graph;
   };

lemon/concept/graph_component.h

-                      r1993
+                      r1999
     /// be registered into the notifier and whenever an alteration
     /// occured in the graph all the observers will notified about it.
     class AlterableGraphComponent : virtual public BaseGraphComponent {
+    class AlterableGraphComponent : virtual public BaseIterableGraphComponent {
     public:
       /// The edge observer registry.
+      typedef AlterationNotifier<Edge> EdgeNotifier;
+      typedef AlterationNotifier<AlterableGraphComponent, Edge>
+      EdgeNotifier;
       /// The node observer registry.
+      typedef AlterationNotifier<Node> NodeNotifier;
+      typedef AlterationNotifier<AlterableGraphComponent, Node>
+      NodeNotifier;
       /// \brief Gives back the edge alteration notifier.

lemon/dag_shortest_path.h

r1993	r1999
330	330	typedef typename _Traits::OperationTraits OperationTraits;
331	331	/// \brief The Node weight map.
332		typedef typename Graph::NodeMap<Value> WeightMap;
	332	typedef typename Graph::template NodeMap<Value> WeightMap;
333	333	private:
334	334	/// Pointer to the underlying graph

lemon/edge_set.h

-                      r1990
+                      r1999
     typedef typename Parent::NodesImplBase NodesImplBase;
+    void eraseNode(const Node&) {
+    void eraseNode(const Node& node) {
+      if (Parent::InEdgeIt(*this, node) == INVALID &&
+          Parent::OutEdgeIt(*this, node) == INVALID) {
+        return;
+      }
       throw UnsupportedOperation();
+    }
 …
     typedef typename Parent::NodesImplBase NodesImplBase;
+    void eraseNode(const Node&) {
+    void eraseNode(const Node& node) {
+      if (Parent::IncEdgeIt(*this, node) == INVALID) {
+        return;
+      }
       throw UnsupportedOperation();
+    }

lemon/full_graph.h

-                      r1995
+                      r1999
 #include <cmath>
+#include <lemon/bits/base_extender.h>
 #include <lemon/bits/graph_extender.h>
 #include <lemon/bits/invalid.h>

lemon/graph_adaptor.h

-                      r1993
+                      r1999
 #include <lemon/maps.h>
+#include <lemon/bits/base_extender.h>
 #include <lemon/bits/graph_adaptor_extender.h>
 #include <lemon/bits/graph_extender.h>
 …
     UndirGraphAdaptorBase()
       : Parent(), edge_notifier(), edge_notifier_proxy(edge_notifier) {}
+      : edge_notifier(*this), edge_notifier_proxy(edge_notifier) {}
     void setGraph(_Graph& graph) {
 …
     ~UndirGraphAdaptorBase() {
+      getNotifier(Edge()).clear();
+      edge_notifier.clear();
+    }
+    int maxId(typename Parent::Edge) const {
+      return Parent::maxEdgeId();
+    }
 …
     using Parent::getNotifier;
     typedef AlterationNotifier<Edge> EdgeNotifier;
+    typedef AlterationNotifier<UndirGraphAdaptorBase, Edge> EdgeNotifier;
     EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }

lemon/graph_utils.h

-                      r1993
+                      r1999
       Map::build();
       Item it;
       const typename Map::Graph* graph = Map::getGraph();
       for (graph->first(it); it != INVALID; graph->next(it)) {
+      const typename Map::Notifier* notifier = Map::getNotifier();
+      for (notifier->first(it); it != INVALID; notifier->next(it)) {
         Map::set(it, invMap.size());
         invMap.push_back(it);
 …
   template <typename _Graph>
   class InDegMap
+    : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
+    : protected ItemSetTraits<_Graph, typename _Graph::Edge>
+      ::ItemNotifier::ObserverBase {
   public:
 …
     typedef int Value;
     typedef typename Graph::Node Key;
+    typedef typename ItemSetTraits<_Graph, typename _Graph::Edge>
+    ::ItemNotifier::ObserverBase Parent;
   private:
 …
     /// Constructor for creating in-degree map.
     InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
+      AlterationNotifier<typename _Graph::Edge>
+        ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
+      Parent::attach(graph.getNotifier(typename _Graph::Edge()));
       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
         deg[it] = countInEdges(graph, it);
+      }
+    }
-    virtual ~InDegMap() {
-      AlterationNotifier<typename _Graph::Edge>::
-        ObserverBase::detach();
+    }
 …
   template <typename _Graph>
   class OutDegMap
+    : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
+  public:
+    : protected ItemSetTraits<_Graph, typename _Graph::Edge>
+      ::ItemNotifier::ObserverBase {
+  public:
+    typedef typename ItemSetTraits<_Graph, typename _Graph::Edge>
+    ::ItemNotifier::ObserverBase Parent;
     typedef _Graph Graph;
 …
     /// Constructor for creating out-degree map.
     OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
+      AlterationNotifier<typename _Graph::Edge>
+        ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
+      Parent::attach(graph.getNotifier(typename _Graph::Edge()));
       for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
 …
+    }
-    virtual ~OutDegMap() {
-      AlterationNotifier<typename _Graph::Edge>::
-        ObserverBase::detach();
+    }
     /// Gives back the out-degree of a Node.
     int operator[](const Key& key) const {

lemon/grid_ugraph.h

r1993	r1999
24	24	#include <lemon/bits/utility.h>
25	25
	26	#include <lemon/bits/base_extender.h>
26	27	#include <lemon/bits/graph_extender.h>
27	28

lemon/list_graph.h

-                      r1995
+                      r1999
 ///\brief ListGraph, ListUGraph classes.
+#include <lemon/bits/base_extender.h>
 #include <lemon/bits/graph_extender.h>
 …
   ///\sa concept::ErasableGraph.
+  class ListGraph : public ExtendedListGraphBase
+  {
+  class ListGraph : public ExtendedListGraphBase {
   public:
+    typedef ExtendedListGraphBase Parent;
     /// Changes the target of \c e to \c n
 …
     ///\warning Edge and node deletions cannot be restored.
     ///\warning Snapshots cannot be nested.
     class Snapshot : protected AlterationNotifier<Node>::ObserverBase,
                      protected AlterationNotifier<Edge>::ObserverBase
+    class Snapshot : protected Parent::NodeNotifier::ObserverBase,
+                     protected Parent::EdgeNotifier::ObserverBase
+    {
     public:
 …
       protected:
+    protected:
       ListGraph *g;
 …
       void regist(ListGraph &_g) {
         g=&_g;
+        AlterationNotifier<Node>::ObserverBase::
+          attach(g->getNotifier(Node()));
+        AlterationNotifier<Edge>::ObserverBase::
+          attach(g->getNotifier(Edge()));
+        Parent::NodeNotifier::ObserverBase::attach(g->getNotifier(Node()));
+        Parent::EdgeNotifier::ObserverBase::attach(g->getNotifier(Edge()));
+      }
       void deregist() {
+        AlterationNotifier<Node>::ObserverBase::
+          detach();
+        AlterationNotifier<Edge>::ObserverBase::
+          detach();
+        Parent::NodeNotifier::ObserverBase::detach();
+        Parent::EdgeNotifier::ObserverBase::detach();
         g=0;
+      }

lemon/matrix_maps.h

-                      r1993
+                      r1999
   template <typename _Graph, typename _Item, typename _Value>
   class DynamicMatrixMap
+    : protected AlterationNotifier<_Item>::ObserverBase {
+  public:
+    typedef typename AlterationNotifier<_Item>::ObserverBase Parent;
+    : protected ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
+  public:
+    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase
+    Parent;
     typedef _Graph Graph;
 …
     /// Creates an item matrix for the given graph.
     DynamicMatrixMap(const Graph& _graph)
       : graph(_graph), values(size(_graph.maxId(Key()) + 1)) {
       Parent::attach(graph.getNotifier(Key()));
+      : values(size(_graph.maxId(Key()) + 1)) {
+      Parent::attach(_graph.getNotifier(Key()));
+    }
 …
     /// pairs of keys the given parameter.
     DynamicMatrixMap(const Graph& _graph, const Value& _val)
+      : graph(_graph), values(size(_graph.maxId(Key()) + 1), _val) {
+      Parent::attach(graph.getNotifier(Key()));
+    }
+    ~DynamicMatrixMap() {
+      if (Parent::attached()) {
+        Parent::detach();
+      }
+      : values(size(_graph.maxId(Key()) + 1), _val) {
+      Parent::attach(_graph.getNotifier(Key()));
+    }
 …
     /// Gives back the value assigned to the \c first - \c second ordered pair.
     ConstReference operator()(const Key& first, const Key& second) const {
+      return values[index(graph.id(first), graph.id(second))];
+      return values[index(Parent::getNotifier()->id(first),
+                          Parent::getNotifier()->id(second))];
+    }
 …
     /// Gives back the value assigned to the \c first - \c second ordered pair.
     Reference operator()(const Key& first, const Key& second) {
+      return values[index(graph.id(first), graph.id(second))];
+      return values[index(Parent::getNotifier()->id(first),
+                          Parent::getNotifier()->id(second))];
+    }
 …
     /// Setter function for the matrix map.
     void set(const Key& first, const Key& second, const Value& val) {
+      values[index(graph.id(first), graph.id(second))] = val;
+      values[index(Parent::getNotifier()->id(first),
+                   Parent::getNotifier()->id(second))] = val;
+    }
 …
     virtual void add(const Key& key) {
       if (size(graph.id(key) + 1) >= (int)values.size()) {
         values.resize(size(graph.id(key) + 1));
+      if (size(Parent::getNotifier()->id(key) + 1) >= (int)values.size()) {
+        values.resize(size(Parent::getNotifier()->id(key) + 1));
+      }
+    }
 …
     virtual void build() {
       values.resize(size(graph.maxId(Key()) + 1));
+      values.resize(size(Parent::getNotifier()->maxId() + 1));
+    }
 …
   private:
-    const Graph& graph;
     std::vector<Value> values;
   };
 …
   template <typename _Graph, typename _Item, typename _Value>
   class DynamicSymMatrixMap
+    : protected AlterationNotifier<_Item>::ObserverBase {
+  public:
+    typedef typename AlterationNotifier<_Item>::ObserverBase Parent;
+    : protected ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
+  public:
+    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase
+    Parent;
     typedef _Graph Graph;
 …
     /// Creates an item matrix for the given graph.
     DynamicSymMatrixMap(const Graph& _graph)
       : graph(_graph), values(size(_graph.maxId(Key()) + 1)) {
       Parent::attach(graph.getNotifier(Key()));
+      : values(size(_graph.maxId(Key()) + 1)) {
+      Parent::attach(_graph.getNotifier(Key()));
+    }
 …
     /// pairs of keys the given parameter.
     DynamicSymMatrixMap(const Graph& _graph, const Value& _val)
+      : graph(_graph), values(size(_graph.maxId(Key()) + 1), _val) {
+      Parent::attach(graph.getNotifier(Key()));
+    }
+    ~DynamicSymMatrixMap() {
+      if (Parent::attached()) {
+        Parent::detach();
+      }
+      : values(size(_graph.maxId(Key()) + 1), _val) {
+      Parent::attach(_graph.getNotifier(Key()));
+    }
 …
     /// pair.
     ConstReference operator()(const Key& first, const Key& second) const {
+      return values[index(graph.id(first), graph.id(second))];
+      return values[index(Parent::getNotifier()->id(first),
+                          Parent::getNotifier()->id(second))];
+    }
 …
     /// pair.
     Reference operator()(const Key& first, const Key& second) {
+      return values[index(graph.id(first), graph.id(second))];
+      return values[index(Parent::getNotifier()->id(first),
+                          Parent::getNotifier()->id(second))];
+    }
 …
     /// Setter function for the matrix map.
     void set(const Key& first, const Key& second, const Value& val) {
+      values[index(graph.id(first), graph.id(second))] = val;
+      values[index(Parent::getNotifier()->id(first),
+                   Parent::getNotifier()->id(second))] = val;
+    }
 …
     virtual void add(const Key& key) {
       if (size(graph.id(key) + 1) >= (int)values.size()) {
         values.resize(size(graph.id(key) + 1));
+      if (size(Parent::getNotifier()->id(key) + 1) >= (int)values.size()) {
+        values.resize(size(Parent::getNotifier()->id(key) + 1));
+      }
+    }
 …
     virtual void build() {
       values.resize(size(graph.maxId(Key()) + 1));
+      values.resize(size(Parent::getNotifier()->maxId() + 1));
+    }
 …
   private:
-    const Graph& graph;
     std::vector<Value> values;
   };

lemon/smart_graph.h

r1995	r1999
28	28	#include <lemon/bits/invalid.h>
29	29
	30	#include <lemon/bits/base_extender.h>
30	31	#include <lemon/bits/graph_extender.h>
31	32

lemon/xy.h

-                      r1993
+                      r1999
     };
+  ///Returns an xy
+  ///Returns an xy
+  ///\relates xy
+  template <typename T>
+  inline xy<T> make_xy(const T& x, const T& y) {
+    return xy<T>(x, y);
+  }
   ///Returns a vector multiplied by a scalar

Context Navigation

Changeset 1999:2ff283124dfc in lemon-0.x for lemon

Legend:

lemon/Makefile.am

lemon/bits/alteration_notifier.h

lemon/bits/array_map.h

lemon/bits/default_map.h

lemon/bits/edge_set_extender.h

lemon/bits/graph_extender.h

lemon/bits/map_extender.h

lemon/bits/vector_map.h

lemon/concept/graph_component.h

lemon/dag_shortest_path.h

lemon/edge_set.h

lemon/full_graph.h

lemon/graph_adaptor.h

lemon/graph_utils.h

lemon/grid_ugraph.h

lemon/list_graph.h

lemon/matrix_maps.h

lemon/smart_graph.h

lemon/xy.h

Download in other formats: