Changeset 1979:c2992fd74dad in lemon-0.x for lemon/bits/graph_extender.h

Timestamp:

02/22/06 19:26:56 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2569

Message:

Mergeing extendermerge branch
Changes:

the extender system
resize for static size graph
UGraphExtender => UndirectGraphExtender?

UGraphExtenders with changed meaning

Some UGraphExtender /SubUGraphExtenders, DirectUGraphExtender/
GridGraph? => GridUGraph
radix sort to ansi compatible

File:

• lemon/bits/graph_extender.h (modified) (19 diffs)

lemon/bits/graph_extender.h

@@ -23 +23 @@
 #include <lemon/error.h>
 
+#include <lemon/bits/default_map.h>
+
 namespace lemon {
 
-  template <typename _Base>
-  class GraphExtender : public _Base {
+  template <typename Base>
+  class GraphExtender : public Base {
   public:
 
-    typedef _Base Parent;
+    typedef Base Parent;
     typedef GraphExtender Graph;
+
+    // Base extensions
 
     typedef typename Parent::Node Node;
@@ -60 +64 @@
     }
 
+    // Alterable extension
+
+    typedef AlterationNotifier<Node> NodeNotifier;
+    typedef AlterationNotifier<Edge> EdgeNotifier;
+
+
+  protected:
+
+    mutable NodeNotifier node_notifier;
+    mutable EdgeNotifier edge_notifier;
+
+  public:
+
+    NodeNotifier& getNotifier(Node) const {
+      return node_notifier;
+    }
+    
+    EdgeNotifier& getNotifier(Edge) const {
+      return edge_notifier;
+    }
+
+    class NodeIt : public Node { 
+      const Graph* graph;
+    public:
+
+      NodeIt() {}
+
+      NodeIt(Invalid i) : Node(i) { }
+
+      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
+        _graph.first(*static_cast<Node*>(this));
+      }
+
+      NodeIt(const Graph& _graph, const Node& node) 
+        : Node(node), graph(&_graph) {}
+
+      NodeIt& operator++() { 
+        graph->next(*this);
+        return *this; 
+      }
+
+    };
+
+
+    class EdgeIt : public Edge { 
+      const Graph* graph;
+    public:
+
+      EdgeIt() { }
+
+      EdgeIt(Invalid i) : Edge(i) { }
+
+      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
+        _graph.first(*static_cast<Edge*>(this));
+      }
+
+      EdgeIt(const Graph& _graph, const Edge& e) : 
+        Edge(e), graph(&_graph) { }
+
+      EdgeIt& operator++() { 
+        graph->next(*this);
+        return *this; 
+      }
+
+    };
+
+
+    class OutEdgeIt : public Edge { 
+      const Graph* graph;
+    public:
+
+      OutEdgeIt() { }
+
+      OutEdgeIt(Invalid i) : Edge(i) { }
+
+      OutEdgeIt(const Graph& _graph, const Node& node) 
+        : graph(&_graph) {
+        _graph.firstOut(*this, node);
+      }
+
+      OutEdgeIt(const Graph& _graph, const Edge& edge) 
+        : Edge(edge), graph(&_graph) {}
+
+      OutEdgeIt& operator++() { 
+        graph->nextOut(*this);
+        return *this; 
+      }
+
+    };
+
+
+    class InEdgeIt : public Edge { 
+      const Graph* graph;
+    public:
+
+      InEdgeIt() { }
+
+      InEdgeIt(Invalid i) : Edge(i) { }
+
+      InEdgeIt(const Graph& _graph, const Node& node) 
+        : graph(&_graph) {
+        _graph.firstIn(*this, node);
+      }
+
+      InEdgeIt(const Graph& _graph, const Edge& edge) : 
+        Edge(edge), graph(&_graph) {}
+
+      InEdgeIt& operator++() { 
+        graph->nextIn(*this);
+        return *this; 
+      }
+
+    };
+
+    /// \brief Base node of the iterator
+    ///
+    /// Returns the base node (ie. the source in this case) of the iterator
+    Node baseNode(const OutEdgeIt &e) const {
+      return Parent::source(e);
+    }
+    /// \brief Running node of the iterator
+    ///
+    /// Returns the running node (ie. the target in this case) of the
+    /// iterator
+    Node runningNode(const OutEdgeIt &e) const {
+      return Parent::target(e);
+    }
+
+    /// \brief Base node of the iterator
+    ///
+    /// Returns the base node (ie. the target in this case) of the iterator
+    Node baseNode(const InEdgeIt &e) const {
+      return Parent::target(e);
+    }
+    /// \brief Running node of the iterator
+    ///
+    /// Returns the running node (ie. the source in this case) of the
+    /// iterator
+    Node runningNode(const InEdgeIt &e) const {
+      return Parent::source(e);
+    }
+
+    
+    template <typename _Value>
+    class NodeMap 
+      : public IterableMapExtender<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) {}
+
+      NodeMap& operator=(const NodeMap& cmap) {
+        return operator=<NodeMap>(cmap);
+      }
+
+
+      /// \brief Template assign operator.
+      ///
+      /// The given parameter should be conform to the ReadMap
+      /// concecpt and could be indiced by the current item set of
+      /// the NodeMap. In this case the value for each item
+      /// is assigned by the value of the given ReadMap. 
+      template <typename 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)) {
+          Parent::set(it, cmap[it]);
+        }
+        return *this;
+      }
+
+    };
+
+    template <typename _Value>
+    class EdgeMap 
+      : public IterableMapExtender<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) {}
+
+      EdgeMap& operator=(const EdgeMap& cmap) {
+        return operator=<EdgeMap>(cmap);
+      }
+
+      template <typename CMap>
+      EdgeMap& operator=(const CMap& cmap) {
+        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
+        const typename Parent::Graph* graph = Parent::getGraph();
+        Edge it;
+        for (graph->first(it); it != INVALID; graph->next(it)) {
+          Parent::set(it, cmap[it]);
+        }
+        return *this;
+      }
+    };
+
+
+    Node addNode() {
+      Node node = Parent::addNode();
+      getNotifier(Node()).add(node);
+      return node;
+    }
+    
+    Edge addEdge(const Node& from, const Node& to) {
+      Edge edge = Parent::addEdge(from, to);
+      getNotifier(Edge()).add(edge);
+      return edge;
+    }
+
+    void clear() {
+      getNotifier(Edge()).clear();
+      getNotifier(Node()).clear();
+      Parent::clear();
+    }
+
+
+    void erase(const Node& node) {
+      Edge edge;
+      Parent::firstOut(edge, node);
+      while (edge != INVALID ) {
+        erase(edge);
+        Parent::firstOut(edge, node);
+      } 
+
+      Parent::firstIn(edge, node);
+      while (edge != INVALID ) {
+        erase(edge);
+        Parent::firstIn(edge, node);
+      }
+
+      getNotifier(Node()).erase(node);
+      Parent::erase(node);
+    }
+    
+    void erase(const Edge& edge) {
+      getNotifier(Edge()).erase(edge);
+      Parent::erase(edge);
+    }
+
+
+    ~GraphExtender() {
+      getNotifier(Edge()).clear();
+      getNotifier(Node()).clear();
+    }
   };
 
-  template <typename _Base>
-  class UGraphExtender : public _Base {
-    typedef _Base Parent;
-    typedef UGraphExtender Graph;
+  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 UGraphExtender;
+      friend class UGraphBaseExtender;
 
     protected:
-      // FIXME: Marci use opposite logic in his graph adaptors. It would
-      // be reasonable to syncronize...
       bool forward;
 
@@ -102 +360 @@
 
 
-    /// \brief Edge of opposite direction.
-    ///
-    /// Returns the Edge of opposite direction.
-    Edge oppositeEdge(const Edge &e) const {
-      return Edge(e,!e.forward);
-    }
-
-  public:
-    /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
-    /// or something???
+
     using Parent::source;
 
@@ -119 +368 @@
     }
 
-    /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
-    /// or something???
     using Parent::target;
 
@@ -126 +373 @@
     Node target(const Edge &e) const {
       return e.forward ? Parent::target(e) : Parent::source(e);
-    }
-
-    Node oppositeNode(const Node &n, const UEdge &e) const {
-      if( n == Parent::source(e))
-        return Parent::target(e);
-      else if( n == Parent::target(e))
-        return Parent::source(e);
-      else
-        return INVALID;
-    }
-
-    /// \brief Directed edge from an undirected edge and a source node.
-    ///
-    /// Returns a (directed) Edge corresponding to the specified UEdge
-    /// and source Node.
-    ///
-    Edge direct(const UEdge &ue, const Node &s) const {
-      return Edge(ue, s == source(ue));
     }
 
@@ -164 +393 @@
 
     using Parent::first;
+    using Parent::next;
+
     void first(Edge &e) const {
       Parent::first(e);
@@ -169 +400 @@
     }
 
-    using Parent::next;
     void next(Edge &e) const {
       if( e.forward ) {
@@ -179 +409 @@
       }
     }
-
-  public:
 
     void firstOut(Edge &e, const Node &n) const {
@@ -230 +458 @@
     }
 
-    void firstInc(UEdge &e, const Node &n) const {
-      Parent::firstOut(e, n);
-      if (e != INVALID) return;
-      Parent::firstIn(e, n);
-    }
-    void nextInc(UEdge &e, const Node &n) const {
-      if (Parent::source(e) == n) {
-        Parent::nextOut(e);
-        if (e != INVALID) return;
-        Parent::firstIn(e, n);
-      } else {
-        Parent::nextIn(e);
-      }
-    }
-
     void firstInc(UEdge &e, bool &d, const Node &n) const {
       d = true;
@@ -252 +465 @@
       Parent::firstIn(e, n);
     }
+
     void nextInc(UEdge &e, bool &d) const {
       if (d) {
@@ -264 +478 @@
     }
 
-    // Miscellaneous stuff:
-
-    /// \todo these methods (id, maxEdgeId) should be moved into separate
-    /// Extender
-
-    // using Parent::id;
-    // Using "using" is not a good idea, cause it could be that there is
-    // no "id" in Parent...
+    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 {
@@ -297 +514 @@
     }
 
-    int maxId(Node) const {
-      return maxNodeId();
-    }
-
-    int maxId(Edge) const {
-      return maxEdgeId();
-    }
-    int maxId(UEdge) const {
-      return maxUEdgeId();
-    }
 
     int edgeNum() const {
@@ -315 +522 @@
       return Parent::edgeNum();
     }
-
-    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);
-    }
-
-    Node fromId(int id, Node) const {
-      return nodeFromId(id);
-    }
-
-    Edge fromId(int id, Edge) const {
-      return edgeFromId(id);
-    }
-
-    UEdge fromId(int id, UEdge) const {
-      return uEdgeFromId(id);
-    }
-
 
     Edge findEdge(Node source, Node target, Edge prev) const {
@@ -376 +558 @@
       return INVALID;
     }
-
   };
 
 
-  template <typename _Base>
-  class BpUGraphExtender : public _Base {
+  template <typename Base> 
+  class UGraphExtender : public Base {
   public:
-    typedef _Base Parent;
-    typedef BpUGraphExtender Graph;
+    
+    typedef Base Parent;
+    typedef UGraphExtender Graph;
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+    typedef typename Parent::UEdge UEdge;
+
+    // UGraph extension    
+
+    int maxId(Node) const {
+      return Parent::maxNodeId();
+    }
+
+    int maxId(Edge) const {
+      return Parent::maxEdgeId();
+    }
+
+    int maxId(UEdge) const {
+      return Parent::maxUEdgeId();
+    }
+
+    Node fromId(int id, Node) const {
+      return Parent::nodeFromId(id);
+    }
+
+    Edge fromId(int id, Edge) const {
+      return Parent::edgeFromId(id);
+    }
+
+    UEdge fromId(int id, UEdge) const {
+      return Parent::uEdgeFromId(id);
+    }
+
+    Node oppositeNode(const Node &n, const UEdge &e) const {
+      if( n == Parent::source(e))
+        return Parent::target(e);
+      else if( n == Parent::target(e))
+        return Parent::source(e);
+      else
+        return INVALID;
+    }
+
+    Edge oppositeEdge(const Edge &e) const {
+      return Parent::direct(e, !Parent::direction(e));
+    }
+
+    using Parent::direct;
+    Edge direct(const UEdge &ue, const Node &s) const {
+      return Parent::direct(ue, Parent::source(ue) == s);
+    }
+
+    // Alterable extension
+
+    typedef AlterationNotifier<Node> NodeNotifier;
+    typedef AlterationNotifier<Edge> EdgeNotifier;
+    typedef AlterationNotifier<UEdge> UEdgeNotifier;
+
+
+  protected:
+
+    mutable NodeNotifier node_notifier;
+    mutable EdgeNotifier edge_notifier;
+    mutable UEdgeNotifier uedge_notifier;
+
+  public:
+
+    NodeNotifier& getNotifier(Node) const {
+      return node_notifier;
+    }
+    
+    EdgeNotifier& getNotifier(Edge) const {
+      return edge_notifier;
+    }
+
+    UEdgeNotifier& getNotifier(UEdge) const {
+      return uedge_notifier;
+    }
+
+
+
+    class NodeIt : public Node { 
+      const Graph* graph;
+    public:
+
+      NodeIt() {}
+
+      NodeIt(Invalid i) : Node(i) { }
+
+      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
+        _graph.first(*static_cast<Node*>(this));
+      }
+
+      NodeIt(const Graph& _graph, const Node& node) 
+        : Node(node), graph(&_graph) {}
+
+      NodeIt& operator++() { 
+        graph->next(*this);
+        return *this; 
+      }
+
+    };
+
+
+    class EdgeIt : public Edge { 
+      const Graph* graph;
+    public:
+
+      EdgeIt() { }
+
+      EdgeIt(Invalid i) : Edge(i) { }
+
+      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
+        _graph.first(*static_cast<Edge*>(this));
+      }
+
+      EdgeIt(const Graph& _graph, const Edge& e) : 
+        Edge(e), graph(&_graph) { }
+
+      EdgeIt& operator++() { 
+        graph->next(*this);
+        return *this; 
+      }
+
+    };
+
+
+    class OutEdgeIt : public Edge { 
+      const Graph* graph;
+    public:
+
+      OutEdgeIt() { }
+
+      OutEdgeIt(Invalid i) : Edge(i) { }
+
+      OutEdgeIt(const Graph& _graph, const Node& node) 
+        : graph(&_graph) {
+        _graph.firstOut(*this, node);
+      }
+
+      OutEdgeIt(const Graph& _graph, const Edge& edge) 
+        : Edge(edge), graph(&_graph) {}
+
+      OutEdgeIt& operator++() { 
+        graph->nextOut(*this);
+        return *this; 
+      }
+
+    };
+
+
+    class InEdgeIt : public Edge { 
+      const Graph* graph;
+    public:
+
+      InEdgeIt() { }
+
+      InEdgeIt(Invalid i) : Edge(i) { }
+
+      InEdgeIt(const Graph& _graph, const Node& node) 
+        : graph(&_graph) {
+        _graph.firstIn(*this, node);
+      }
+
+      InEdgeIt(const Graph& _graph, const Edge& edge) : 
+        Edge(edge), graph(&_graph) {}
+
+      InEdgeIt& operator++() { 
+        graph->nextIn(*this);
+        return *this; 
+      }
+
+    };
+
+
+    class UEdgeIt : public Parent::UEdge { 
+      const Graph* graph;
+    public:
+
+      UEdgeIt() { }
+
+      UEdgeIt(Invalid i) : UEdge(i) { }
+
+      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
+        _graph.first(*static_cast<UEdge*>(this));
+      }
+
+      UEdgeIt(const Graph& _graph, const UEdge& e) : 
+        UEdge(e), graph(&_graph) { }
+
+      UEdgeIt& operator++() { 
+        graph->next(*this);
+        return *this; 
+      }
+
+    };
+
+    class IncEdgeIt : public Parent::UEdge {
+      friend class UGraphExtender;
+      const Graph* graph;
+      bool direction;
+    public:
+
+      IncEdgeIt() { }
+
+      IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
+
+      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
+        _graph.firstInc(*this, direction, n);
+      }
+
+      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
+        : graph(&_graph), UEdge(ue) {
+        direction = (_graph.source(ue) == n);
+      }
+
+      IncEdgeIt& operator++() {
+        graph->nextInc(*this, direction);
+        return *this; 
+      }
+    };
+
+    /// \brief Base node of the iterator
+    ///
+    /// Returns the base node (ie. the source in this case) of the iterator
+    Node baseNode(const OutEdgeIt &e) const {
+      return Parent::source((Edge)e);
+    }
+    /// \brief Running node of the iterator
+    ///
+    /// Returns the running node (ie. the target in this case) of the
+    /// iterator
+    Node runningNode(const OutEdgeIt &e) const {
+      return Parent::target((Edge)e);
+    }
+
+    /// \brief Base node of the iterator
+    ///
+    /// Returns the base node (ie. the target in this case) of the iterator
+    Node baseNode(const InEdgeIt &e) const {
+      return Parent::target((Edge)e);
+    }
+    /// \brief Running node of the iterator
+    ///
+    /// Returns the running node (ie. the source in this case) of the
+    /// iterator
+    Node runningNode(const InEdgeIt &e) const {
+      return Parent::source((Edge)e);
+    }
+
+    /// Base node of the iterator
+    ///
+    /// Returns the base node of the iterator
+    Node baseNode(const IncEdgeIt &e) const {
+      return e.direction ? source(e) : target(e);
+    }
+    /// Running node of the iterator
+    ///
+    /// Returns the running node of the iterator
+    Node runningNode(const IncEdgeIt &e) const {
+      return e.direction ? target(e) : source(e);
+    }
+
+    // Mappable extension
+
+    template <typename _Value>
+    class NodeMap 
+      : public IterableMapExtender<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) {}
+
+      NodeMap& operator=(const NodeMap& cmap) {
+        return operator=<NodeMap>(cmap);
+      }
+
+
+      /// \brief Template assign operator.
+      ///
+      /// The given parameter should be conform to the ReadMap
+      /// concecpt and could be indiced by the current item set of
+      /// the NodeMap. In this case the value for each item
+      /// is assigned by the value of the given ReadMap. 
+      template <typename 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)) {
+          Parent::set(it, cmap[it]);
+        }
+        return *this;
+      }
+
+    };
+
+    template <typename _Value>
+    class EdgeMap 
+      : public IterableMapExtender<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) {}
+
+      EdgeMap& operator=(const EdgeMap& cmap) {
+        return operator=<EdgeMap>(cmap);
+      }
+
+      template <typename CMap>
+      EdgeMap& operator=(const CMap& cmap) {
+        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
+        const typename Parent::Graph* graph = Parent::getGraph();
+        Edge it;
+        for (graph->first(it); it != INVALID; graph->next(it)) {
+          Parent::set(it, cmap[it]);
+        }
+        return *this;
+      }
+    };
+
+
+    template <typename _Value>
+    class UEdgeMap 
+      : public IterableMapExtender<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) {}
+
+      UEdgeMap& operator=(const UEdgeMap& cmap) {
+        return operator=<UEdgeMap>(cmap);
+      }
+
+      template <typename 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)) {
+          Parent::set(it, cmap[it]);
+        }
+        return *this;
+      }
+    };
+
+    // Alteration extension
+
+    Node addNode() {
+      Node node = Parent::addNode();
+      getNotifier(Node()).add(node);
+      return node;
+    }
+
+    UEdge addEdge(const Node& from, const Node& to) {
+      UEdge uedge = Parent::addEdge(from, to);
+      getNotifier(UEdge()).add(uedge);
+      getNotifier(Edge()).add(Parent::direct(uedge, true));
+      getNotifier(Edge()).add(Parent::direct(uedge, false));
+      return uedge;
+    }
+    
+    void clear() {
+      getNotifier(Edge()).clear();
+      getNotifier(UEdge()).clear();
+      getNotifier(Node()).clear();
+      Parent::clear();
+    }
+
+    void erase(const Node& node) {
+      Edge edge;
+      Parent::firstOut(edge, node);
+      while (edge != INVALID ) {
+        erase(edge);
+        Parent::firstOut(edge, node);
+      } 
+
+      Parent::firstIn(edge, node);
+      while (edge != INVALID ) {
+        erase(edge);
+        Parent::firstIn(edge, node);
+      }
+
+      getNotifier(Node()).erase(node);
+      Parent::erase(node);
+    }
+
+    void erase(const UEdge& uedge) {
+      getNotifier(Edge()).erase(Parent::direct(uedge, true));
+      getNotifier(Edge()).erase(Parent::direct(uedge, false));
+      getNotifier(UEdge()).erase(uedge);
+      Parent::erase(uedge);
+    }
+
+    ~UGraphExtender() {
+      getNotifier(Edge()).clear();
+      getNotifier(UEdge()).clear();
+      getNotifier(Node()).clear();
+    }
+
+  };
+
+
+  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 {
@@ -428 +1072 @@
 
     class Edge : public UEdge {
-      friend class BpUGraphExtender;
+      friend class BpUGraphBaseExtender;
     protected:
       bool forward;
@@ -505 +1149 @@
     }
 
+    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, const Node& node) const {
-      return Edge(edge, node == Parent::source(edge));
-    }
-
     Edge direct(const UEdge& edge, bool direction) const {
       return Edge(edge, direction);
     }
+  };
+
+  template <typename Base>
+  class BpUGraphExtender : public Base {
+  public:
+    typedef Base Parent;
+    typedef BpUGraphExtender Graph;
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::BNode BNode;
+    typedef typename Parent::ANode ANode;
+    typedef typename Parent::Edge Edge;
+    typedef typename Parent::UEdge UEdge;
 
     Node oppositeNode(const UEdge& edge, const Node& node) const {
@@ -522 +1185 @@
     }
 
+    using Parent::direct;
+    Edge direct(const UEdge& edge, const Node& node) const {
+      return Edge(edge, node == Parent::source(edge));
+    }
+
     Edge oppositeEdge(const Edge& edge) const {
-      return Edge(edge, !edge.forward);
-    }
-
-    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;
-    }
-
-    class ANode : public Node {
-      friend class BpUGraphExtender;
-    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 BpUGraphExtender;
-    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);
-    }
-
+      return Parent::direct(edge, !Parent::direction(edge));
+    }
 
 
@@ -592 +1205 @@
     }
     int maxId(Edge) const {
-      return maxEdgeId();
+      return Parent::maxEdgeId();
     }
     int maxId(UEdge) const {
-      return maxUEdgeId();
+      return Parent::maxUEdgeId();
     }
 
@@ -609 +1222 @@
     }
     Edge fromId(int id, Edge) const {
-      return edgeFromId(id);
+      return Parent::edgeFromId(id);
     }
     UEdge fromId(int id, UEdge) const {
-      return uEdgeFromId(id);
-    }
+      return Parent::uEdgeFromId(id);
+    }  
+  
+    typedef AlterationNotifier<Node> NodeNotifier;
+    typedef AlterationNotifier<BNode> BNodeNotifier;
+    typedef AlterationNotifier<ANode> ANodeNotifier;
+    typedef AlterationNotifier<Edge> EdgeNotifier;
+    typedef AlterationNotifier<UEdge> UEdgeNotifier;
+
+  protected:
+
+    mutable NodeNotifier nodeNotifier;
+    mutable BNodeNotifier bNodeNotifier;
+    mutable ANodeNotifier aNodeNotifier;
+    mutable EdgeNotifier edgeNotifier;
+    mutable UEdgeNotifier uEdgeNotifier;
+
+  public:
+
+    NodeNotifier& getNotifier(Node) const {
+      return nodeNotifier;
+    }
+
+    BNodeNotifier& getNotifier(BNode) const {
+      return bNodeNotifier;
+    }
+
+    ANodeNotifier& getNotifier(ANode) const {
+      return aNodeNotifier;
+    }
+
+    EdgeNotifier& getNotifier(Edge) const {
+      return edgeNotifier;
+    }
+
+    UEdgeNotifier& getNotifier(UEdge) const {
+      return uEdgeNotifier;
+    }
+
+    ~BpUGraphExtender() {
+      getNotifier(UEdge()).clear();
+      getNotifier(Edge()).clear();
+      getNotifier(ANode()).clear();
+      getNotifier(BNode()).clear();
+      getNotifier(Node()).clear();
+    }
+
+  
+    class NodeIt : public Node { 
+      const Graph* graph;
+    public:
+    
+      NodeIt() { }
+    
+      NodeIt(Invalid i) : Node(INVALID) { }
+    
+      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
+        graph->first(static_cast<Node&>(*this));
+      }
+
+      NodeIt(const Graph& _graph, const Node& node) 
+        : Node(node), graph(&_graph) { }
+    
+      NodeIt& operator++() { 
+        graph->next(*this);
+        return *this; 
+      }
+
+    };
+
+    class ANodeIt : public Node { 
+      friend class BpUGraphExtender;
+      const Graph* graph;
+    public:
+    
+      ANodeIt() { }
+    
+      ANodeIt(Invalid i) : Node(INVALID) { }
+    
+      explicit ANodeIt(const Graph& _graph) : graph(&_graph) {
+        graph->firstANode(static_cast<Node&>(*this));
+      }
+
+      ANodeIt(const Graph& _graph, const Node& node) 
+        : Node(node), graph(&_graph) {}
+    
+      ANodeIt& operator++() { 
+        graph->nextANode(*this);
+        return *this; 
+      }
+    };
+
+    class BNodeIt : public Node { 
+      friend class BpUGraphExtender;
+      const Graph* graph;
+    public:
+    
+      BNodeIt() { }
+    
+      BNodeIt(Invalid i) : Node(INVALID) { }
+    
+      explicit BNodeIt(const Graph& _graph) : graph(&_graph) {
+        graph->firstBNode(static_cast<Node&>(*this));
+      }
+
+      BNodeIt(const Graph& _graph, const Node& node) 
+        : Node(node), graph(&_graph) {}
+    
+      BNodeIt& operator++() { 
+        graph->nextBNode(*this);
+        return *this; 
+      }
+    };
+
+    class EdgeIt : public Edge { 
+      friend class BpUGraphExtender;
+      const Graph* graph;
+    public:
+    
+      EdgeIt() { }
+    
+      EdgeIt(Invalid i) : Edge(INVALID) { }
+    
+      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
+        graph->first(static_cast<Edge&>(*this));
+      }
+
+      EdgeIt(const Graph& _graph, const Edge& edge) 
+        : Edge(edge), graph(&_graph) { }
+    
+      EdgeIt& operator++() { 
+        graph->next(*this);
+        return *this; 
+      }
+
+    };
+
+    class UEdgeIt : public UEdge { 
+      friend class BpUGraphExtender;
+      const Graph* graph;
+    public:
+    
+      UEdgeIt() { }
+    
+      UEdgeIt(Invalid i) : UEdge(INVALID) { }
+    
+      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
+        graph->first(static_cast<UEdge&>(*this));
+      }
+
+      UEdgeIt(const Graph& _graph, const UEdge& edge) 
+        : UEdge(edge), graph(&_graph) { }
+    
+      UEdgeIt& operator++() { 
+        graph->next(*this);
+        return *this; 
+      }
+    };
+
+    class OutEdgeIt : public Edge { 
+      friend class BpUGraphExtender;
+      const Graph* graph;
+    public:
+    
+      OutEdgeIt() { }
+    
+      OutEdgeIt(Invalid i) : Edge(i) { }
+    
+      OutEdgeIt(const Graph& _graph, const Node& node) 
+        : graph(&_graph) {
+        graph->firstOut(*this, node);
+      }
+    
+      OutEdgeIt(const Graph& _graph, const Edge& edge) 
+        : Edge(edge), graph(&_graph) {}
+    
+      OutEdgeIt& operator++() { 
+        graph->nextOut(*this);
+        return *this; 
+      }
+
+    };
+
+
+    class InEdgeIt : public Edge { 
+      friend class BpUGraphExtender;
+      const Graph* graph;
+    public:
+    
+      InEdgeIt() { }
+    
+      InEdgeIt(Invalid i) : Edge(i) { }
+    
+      InEdgeIt(const Graph& _graph, const Node& node) 
+        : graph(&_graph) {
+        graph->firstIn(*this, node);
+      }
+    
+      InEdgeIt(const Graph& _graph, const Edge& edge) : 
+        Edge(edge), graph(&_graph) {}
+    
+      InEdgeIt& operator++() { 
+        graph->nextIn(*this);
+        return *this; 
+      }
+
+    };
+  
+    /// \brief Base node of the iterator
+    ///
+    /// Returns the base node (ie. the source in this case) of the iterator
+    Node baseNode(const OutEdgeIt &e) const {
+      return Parent::source((Edge&)e);
+    }
+    /// \brief Running node of the iterator
+    ///
+    /// Returns the running node (ie. the target in this case) of the
+    /// iterator
+    Node runningNode(const OutEdgeIt &e) const {
+      return Parent::target((Edge&)e);
+    }
+  
+    /// \brief Base node of the iterator
+    ///
+    /// Returns the base node (ie. the target in this case) of the iterator
+    Node baseNode(const InEdgeIt &e) const {
+      return Parent::target((Edge&)e);
+    }
+    /// \brief Running node of the iterator
+    ///
+    /// Returns the running node (ie. the source in this case) of the
+    /// iterator
+    Node runningNode(const InEdgeIt &e) const {
+      return Parent::source((Edge&)e);
+    }
+  
+    class IncEdgeIt : public Parent::UEdge { 
+      friend class BpUGraphExtender;
+      const Graph* graph;
+      bool direction;
+    public:
+    
+      IncEdgeIt() { }
+    
+      IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }
+    
+      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
+        graph->firstInc(*this, direction, n);
+      }
+
+      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
+        : graph(&_graph), UEdge(ue) {
+        direction = (graph->source(ue) == n);
+      }
+
+      IncEdgeIt& operator++() {
+        graph->nextInc(*this, direction);
+        return *this; 
+      }
+    };
+  
+
+    /// Base node of the iterator
+    ///
+    /// Returns the base node of the iterator
+    Node baseNode(const IncEdgeIt &e) const {
+      return e.direction ? source(e) : target(e);
+    }
+
+    /// Running node of the iterator
+    ///
+    /// Returns the running node of the iterator
+    Node runningNode(const IncEdgeIt &e) const {
+      return e.direction ? target(e) : source(e);
+    }
+
+    template <typename _Value>
+    class ANodeMap 
+      : public IterableMapExtender<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) {}
+    
+      ANodeMap& operator=(const ANodeMap& cmap) {
+        return operator=<ANodeMap>(cmap);
+      }
+    
+
+      /// \brief Template assign operator.
+      ///
+      /// The given parameter should be conform to the ReadMap
+      /// concept and could be indiced by the current item set of
+      /// the ANodeMap. In this case the value for each item
+      /// is assigned by the value of the given ReadMap. 
+      template <typename CMap>
+      ANodeMap& operator=(const CMap& cmap) {
+        checkConcept<concept::ReadMap<ANode, _Value>, CMap>();
+        const typename Parent::Graph* graph = Parent::getGraph();
+        ANode it;
+        for (graph->first(it); it != INVALID; graph->next(it)) {
+          Parent::set(it, cmap[it]);
+        }
+        return *this;
+      }
+    
+    };
+
+    template <typename _Value>
+    class BNodeMap 
+      : public IterableMapExtender<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) {}
+    
+      BNodeMap& operator=(const BNodeMap& cmap) {
+        return operator=<BNodeMap>(cmap);
+      }
+    
+
+      /// \brief Template assign operator.
+      ///
+      /// The given parameter should be conform to the ReadMap
+      /// concept and could be indiced by the current item set of
+      /// the BNodeMap. In this case the value for each item
+      /// is assigned by the value of the given ReadMap. 
+      template <typename CMap>
+      BNodeMap& operator=(const CMap& cmap) {
+        checkConcept<concept::ReadMap<BNode, _Value>, CMap>();
+        const typename Parent::Graph* graph = Parent::getGraph();
+        BNode it;
+        for (graph->first(it); it != INVALID; graph->next(it)) {
+          Parent::set(it, cmap[it]);
+        }
+        return *this;
+      }
+    
+    };
+
+  protected:
+
+    template <typename _Value>
+    class NodeMapBase : public NodeNotifier::ObserverBase {
+    public:
+      typedef BpUGraphExtender Graph;
+
+      typedef Node Key;
+      typedef _Value Value;
+
+      /// 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;
+      /// 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 True ReferenceMapTag;
+
+      NodeMapBase(const Graph& _g) 
+        : graph(&_g), bNodeMap(_g), aNodeMap(_g) {
+        NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
+      }
+      NodeMapBase(const Graph& _g, const _Value& _v) 
+        : graph(&_g), bNodeMap(_g, _v), 
+          aNodeMap(_g, _v) {
+        NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
+      }
+
+      virtual ~NodeMapBase() {      
+        if (NodeNotifier::ObserverBase::attached()) {
+          NodeNotifier::ObserverBase::detach();
+        }
+      }
+    
+      ConstReference operator[](const Key& node) const {
+        if (Parent::aNode(node)) {
+          return aNodeMap[node];
+        } else {
+          return bNodeMap[node];
+        }
+      } 
+
+      Reference operator[](const Key& node) {
+        if (Parent::aNode(node)) {
+          return aNodeMap[node];
+        } else {
+          return bNodeMap[node];
+        }
+      }
+
+      void set(const Key& node, const Value& value) {
+        if (Parent::aNode(node)) {
+          aNodeMap.set(node, value);
+        } else {
+          bNodeMap.set(node, value);
+        }
+      }
+
+    protected:
+      
+      virtual void add(const Node&) {}
+      virtual void add(const std::vector<Node>&) {}
+      virtual void erase(const Node&) {}
+      virtual void erase(const std::vector<Node>&) {}
+      virtual void clear() {}
+      virtual void build() {}
+
+      const Graph* getGraph() const { return graph; }
+      
+    private:
+      const Graph* graph;
+      BNodeMap<_Value> bNodeMap;
+      ANodeMap<_Value> aNodeMap;
+    };
+    
+  public:
+
+    template <typename _Value>
+    class NodeMap 
+      : public IterableMapExtender<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) {}
+    
+      NodeMap& operator=(const NodeMap& cmap) {
+        return operator=<NodeMap>(cmap);
+      }
+    
+
+      /// \brief Template assign operator.
+      ///
+      /// The given parameter should be conform to the ReadMap
+      /// concept and could be indiced by the current item set of
+      /// the NodeMap. In this case the value for each item
+      /// is assigned by the value of the given ReadMap. 
+      template <typename 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)) {
+          Parent::set(it, cmap[it]);
+        }
+        return *this;
+      }
+    
+    };
+
+
+
+    template <typename _Value>
+    class EdgeMap 
+      : public IterableMapExtender<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) {}
+    
+      EdgeMap& operator=(const EdgeMap& cmap) {
+        return operator=<EdgeMap>(cmap);
+      }
+    
+      template <typename CMap>
+      EdgeMap& operator=(const CMap& cmap) {
+        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
+        const typename Parent::Graph* graph = Parent::getGraph();
+        Edge it;
+        for (graph->first(it); it != INVALID; graph->next(it)) {
+          Parent::set(it, cmap[it]);
+        }
+        return *this;
+      }
+    };
+
+    template <typename _Value>
+    class UEdgeMap 
+      : public IterableMapExtender<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) {}
+    
+      UEdgeMap& operator=(const UEdgeMap& cmap) {
+        return operator=<UEdgeMap>(cmap);
+      }
+    
+      template <typename 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)) {
+          Parent::set(it, cmap[it]);
+        }
+        return *this;
+      }
+    };
+
+  
+    Node addANode() {
+      Node node = Parent::addANode();
+      getNotifier(ANode()).add(node);
+      getNotifier(Node()).add(node);
+      return node;
+    }
+
+    Node addBNode() {
+      Node node = Parent::addBNode();
+      getNotifier(BNode()).add(node);
+      getNotifier(Node()).add(node);
+      return node;
+    }
+  
+    UEdge addEdge(const Node& source, const Node& target) {
+      UEdge uedge = Parent::addEdge(source, target);
+      getNotifier(UEdge()).add(uedge);
+    
+      std::vector<Edge> edges;
+      edges.push_back(direct(uedge, true));
+      edges.push_back(direct(uedge, false));
+      getNotifier(Edge()).add(edges);
+    
+      return uedge;
+    }
+
+    void clear() {
+      getNotifier(Edge()).clear();
+      getNotifier(UEdge()).clear();
+      getNotifier(Node()).clear();
+      getNotifier(BNode()).clear();
+      getNotifier(ANode()).clear();
+      Parent::clear();
+    }
+
+    void erase(const Node& node) {
+      UEdge uedge;
+      bool dir;
+      Parent::firstInc(uedge, dir, node);
+      while (uedge != INVALID ) {
+        erase(uedge);
+        Parent::firstInc(uedge, dir, node);
+      } 
+
+      getNotifier(Node()).erase(node);
+      Parent::erase(node);
+    }
+    
+    void erase(const UEdge& uedge) {
+      std::vector<Edge> edges;
+      edges.push_back(direct(uedge, true));
+      edges.push_back(direct(uedge, false));
+      getNotifier(Edge()).erase(edges);
+      getNotifier(UEdge()).erase(uedge);
+      Parent::erase(uedge);
+    }
+
+
+    ~BpUGraphExtender() {
+      getNotifier(Edge()).clear();
+      getNotifier(UEdge()).clear();
+      getNotifier(Node()).clear();
+      getNotifier(BNode()).clear();
+      getNotifier(ANode()).clear();
+    }
+
 
   };