# HG changeset patch
# User deba
# Date 1140632816 0
# Node ID c2992fd74dad819a42e85654910b9ff36b4497ea
# Parent  ef2d00e4689777e4e1e55e5637bfde2de2d97074
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

diff -r ef2d00e46897 -r c2992fd74dad demo/Makefile.am
--- a/demo/Makefile.am	Wed Feb 22 12:45:59 2006 +0000
+++ b/demo/Makefile.am	Wed Feb 22 18:26:56 2006 +0000
@@ -16,7 +16,7 @@
 	sub_graph_adaptor_demo \
 	descriptor_map_demo \
 	coloring \
-	grid_graph_demo \
+	grid_ugraph_demo \
 	topology_demo \
 	simann_maxcut_demo
 
@@ -43,7 +43,7 @@
 
 graph_to_eps_demo_SOURCES = graph_to_eps_demo.cc
 
-grid_graph_demo_SOURCES = grid_graph_demo.cc
+grid_ugraph_demo_SOURCES = grid_ugraph_demo.cc
 
 graph_orientation_SOURCES = graph_orientation.cc
 
diff -r ef2d00e46897 -r c2992fd74dad demo/grid_graph_demo.cc
--- a/demo/grid_graph_demo.cc	Wed Feb 22 12:45:59 2006 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,102 +0,0 @@
-/* -*- C++ -*-
- *
- * This file is a part of LEMON, a generic C++ optimization library
- *
- * Copyright (C) 2003-2006
- * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
- * (Egervary Research Group on Combinatorial Optimization, EGRES).
- *
- * Permission to use, modify and distribute this software is granted
- * provided that this copyright notice appears in all copies. For
- * precise terms see the accompanying LICENSE file.
- *
- * This software is provided "AS IS" with no warranty of any kind,
- * express or implied, and with no claim as to its suitability for any
- * purpose.
- *
- */
-
-#include <lemon/grid_graph.h>
-#include <lemon/graph_adaptor.h>
-#include <lemon/graph_to_eps.h>
-#include <lemon/bfs.h>
-#include <lemon/xy.h>
-
-#include <iostream>
-#include <fstream>
-
-///\ingroup demos
-///\file
-///\brief Labirinth example with grid graph.
-///
-///  Labirinth example with grid graph.
-///
-/// The input file is:
-///
-/// \include grid_graph_demo.in
-///
-/// The result:
-///
-/// \image html grid_graph_demo.png
-/// \image latex grid_graph_demo.eps "The labirinth" width=\textwidth
-///
-/// The source:
-///
-/// \include grid_graph_demo.cc
-
-using namespace lemon;
-using namespace std;
-
-int main() {
-  ifstream in("grid_graph_demo.in");
-  int width, height;
-  in >> width >> height;
-  int start_x, start_y;
-  in >> start_x >> start_y;
-  int stop_x, stop_y;
-  in >> stop_x >> stop_y;
-
-  GridGraph graph(width, height);
-  GridGraph::Node start = graph(start_x - 1, start_y - 1);
-  GridGraph::Node stop = graph(stop_x - 1, stop_y - 1);
-  GridGraph::NodeMap<bool> filter(graph);
-
-  for (int j = 0; j < height; ++j) {
-    in >> ws;
-    for (int i = 0; i < width; ++i) {
-      char c; in >> c;
-      filter[graph(i, j)] = (c == '.');
-    }
-  }
-
-  typedef NodeSubGraphAdaptor<GridGraph,
-    GridGraph::NodeMap<bool> > FilteredGraph;
-
-  FilteredGraph filtered(graph, filter);
-
-  Bfs<FilteredGraph> bfs(filtered);
-  std::cout << "The length of shortest path: " << 
-    bfs.run(start, stop) << std::endl;
-
-  FilteredGraph::EdgeMap<bool> path(filtered, false);
-  
-  for (GridGraph::Node node = stop; 
-       node != start; node = bfs.predNode(node)) {
-    path[bfs.predEdge(node)] = true;
-  }
-  
-  graphToEps(filtered, "grid_graph_demo.eps").scaleToA4().
-    title("Grid graph").
-    copyright("(C) 2006 LEMON Project").
-    coords(scaleMap(indexMap(graph), 10)).
-    enableParallel().
-    nodeScale(0.5).
-    drawArrows().
-    edgeColors(composeMap(ColorSet(), path)).
-    run();
-  
-  std::cout << "The shortest path is written to grid_graph_demo.eps" 
-	    << std::endl;
-
-  return 0;
-}
diff -r ef2d00e46897 -r c2992fd74dad demo/grid_graph_demo.in
--- a/demo/grid_graph_demo.in	Wed Feb 22 12:45:59 2006 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,10 +0,0 @@
-10 8
-1 1 10 8
-..X....X.X
-.XX.X.XX..
-....X..XX.
-XXXXXX.X..
-.........X
-.X.XXXXXXX
-.X...XX...
-.X.X....X.
diff -r ef2d00e46897 -r c2992fd74dad demo/grid_ugraph_demo.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/demo/grid_ugraph_demo.cc	Wed Feb 22 18:26:56 2006 +0000
@@ -0,0 +1,102 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2006
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#include <lemon/grid_ugraph.h>
+#include <lemon/graph_adaptor.h>
+#include <lemon/graph_to_eps.h>
+#include <lemon/bfs.h>
+#include <lemon/xy.h>
+
+#include <iostream>
+#include <fstream>
+
+///\ingroup demos
+///\file
+///\brief Labirinth example with grid ugraph.
+///
+///  Labirinth example with grid ugraph.
+///
+/// The input file is:
+///
+/// \include grid_ugraph_demo.in
+///
+/// The result:
+///
+/// \image html grid_ugraph_demo.png
+/// \image latex grid_ugraph_demo.eps "The labirinth" width=\textwidth
+///
+/// The source:
+///
+/// \include grid_ugraph_demo.cc
+
+using namespace lemon;
+using namespace std;
+
+int main() {
+  ifstream in("grid_ugraph_demo.in");
+  int width, height;
+  in >> width >> height;
+  int start_x, start_y;
+  in >> start_x >> start_y;
+  int stop_x, stop_y;
+  in >> stop_x >> stop_y;
+
+  GridUGraph ugraph(width, height);
+  GridUGraph::Node start = ugraph(start_x - 1, start_y - 1);
+  GridUGraph::Node stop = ugraph(stop_x - 1, stop_y - 1);
+  GridUGraph::NodeMap<bool> filter(ugraph);
+
+  for (int j = 0; j < height; ++j) {
+    in >> ws;
+    for (int i = 0; i < width; ++i) {
+      char c; in >> c;
+      filter[ugraph(i, j)] = (c == '.');
+    }
+  }
+
+  typedef NodeSubGraphAdaptor<GridUGraph,
+    GridUGraph::NodeMap<bool> > FilteredGraph;
+
+  FilteredGraph filtered(ugraph, filter);
+
+  Bfs<FilteredGraph> bfs(filtered);
+  std::cout << "The length of shortest path: " << 
+    bfs.run(start, stop) << std::endl;
+
+  FilteredGraph::EdgeMap<bool> path(filtered, false);
+  
+  for (GridUGraph::Node node = stop; 
+       node != start; node = bfs.predNode(node)) {
+    path[bfs.predEdge(node)] = true;
+  }
+  
+  graphToEps(filtered, "grid_ugraph_demo.eps").scaleToA4().
+    title("Grid ugraph").
+    copyright("(C) 2006 LEMON Project").
+    coords(scaleMap(indexMap(ugraph), 10)).
+    enableParallel().
+    nodeScale(0.5).
+    drawArrows().
+    edgeColors(composeMap(ColorSet(), path)).
+    run();
+  
+  std::cout << "The shortest path is written to grid_ugraph_demo.eps" 
+	    << std::endl;
+
+  return 0;
+}
diff -r ef2d00e46897 -r c2992fd74dad demo/grid_ugraph_demo.in
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/demo/grid_ugraph_demo.in	Wed Feb 22 18:26:56 2006 +0000
@@ -0,0 +1,10 @@
+10 8
+1 1 10 8
+..X....X.X
+.XX.X.XX..
+....X..XX.
+XXXXXX.X..
+.........X
+.X.XXXXXXX
+.X...XX...
+.X.X....X.
diff -r ef2d00e46897 -r c2992fd74dad lemon/Makefile.am
--- a/lemon/Makefile.am	Wed Feb 22 12:45:59 2006 +0000
+++ b/lemon/Makefile.am	Wed Feb 22 18:26:56 2006 +0000
@@ -40,7 +40,7 @@
 	floyd_warshall.h \
 	fredman_tarjan.h \
 	full_graph.h \
-	grid_graph.h \
+	grid_ugraph.h \
 	graph_adaptor.h \
 	graph_utils.h \
 	graph_to_eps.h \
@@ -75,6 +75,7 @@
 	time_measure.h \
 	topology.h \
 	traits.h \
+	ugraph_adaptor.h \
 	unionfind.h \
 	xy.h \
 	concept_check.h \
@@ -87,14 +88,12 @@
 	bits/alteration_notifier.h \
 	bits/array_map.h \
 	bits/default_map.h \
+	bits/static_map.h \
 	bits/vector_map.h \
-	bits/iterable_graph_extender.h \
-	bits/extendable_graph_extender.h \
-	bits/clearable_graph_extender.h \
-	bits/erasable_graph_extender.h \
+	bits/map_extender.h \
 	bits/graph_extender.h \
-	bits/map_extender.h \
-	bits/static_map.h \
+	bits/graph_adaptor_extender.h \
+	bits/edge_set_extender.h \
 	bits/item_reader.h \
 	bits/item_writer.h \
 	concept/bpugraph.h \
diff -r ef2d00e46897 -r c2992fd74dad lemon/bits/alteration_notifier.h
--- a/lemon/bits/alteration_notifier.h	Wed Feb 22 12:45:59 2006 +0000
+++ b/lemon/bits/alteration_notifier.h	Wed Feb 22 18:26:56 2006 +0000
@@ -265,8 +265,16 @@
     /// 
     void add(const Item& item) {
       typename Container::iterator it;
-      for (it = container.begin(); it != container.end(); ++it) {
-	(*it)->add(item);
+      try {
+        for (it = container.begin(); it != container.end(); ++it) {
+          (*it)->add(item);
+        }
+      } catch (...) {
+        typename Container::iterator jt;
+        for (jt = container.begin(); jt != it; ++it) {
+          (*it)->erase(item);
+        }
+        throw;
       }
     }	
 
@@ -278,8 +286,16 @@
     /// 
     void add(const std::vector<Item>& items) {
       typename Container::iterator it;
-      for (it = container.begin(); it != container.end(); ++it) {
-	(*it)->add(items);
+      try {
+        for (it = container.begin(); it != container.end(); ++it) {
+          (*it)->add(items);
+        }
+      } catch (...) {
+        typename Container::iterator jt;
+        for (jt = container.begin(); jt != it; ++it) {
+          (*it)->erase(items);
+        }
+        throw;
       }
     }	
 
@@ -316,8 +332,16 @@
     /// from an empty container.
     void build() {
       typename Container::iterator it;
-      for (it = container.begin(); it != container.end(); ++it) {
-	(*it)->build();
+      try {
+        for (it = container.begin(); it != container.end(); ++it) {
+          (*it)->build();
+        }
+      } catch (...) {
+        typename Container::iterator jt;
+        for (jt = container.begin(); jt != it; ++it) {
+          (*it)->clear();
+        }
+        throw;
       }
     }
 
@@ -335,232 +359,6 @@
     }
   };
 
-
-  /// \brief Class to extend a graph with the functionality of alteration
-  /// observing.
-  ///
-  /// AlterableGraphExtender extends the _Base graphs functionality with
-  /// the possibility of alteration observing. It defines two observer
-  /// registrys for the nodes and mapes.
-  /// 
-  /// \todo Document what "alteration observing" is. And probably find a
-  /// better (shorter) name.
-  ///
-  /// \param _Base is the base class to extend.
-  ///
-  /// \pre _Base is conform to the BaseGraphComponent concept.
-  ///
-  /// \post AlterableGraphExtender<_Base> is conform to the
-  /// AlterableGraphComponent concept.
-  ///
-  /// \author Balazs Dezso
-
-  template <typename _Base> 
-  class AlterableGraphExtender : public _Base {
-  public:
-
-    typedef AlterableGraphExtender Graph;
-    typedef _Base Parent;
-
-    typedef typename Parent::Node Node;
-    typedef typename Parent::Edge Edge;
-
-    /// The edge observer registry.
-    typedef AlterationNotifier<Edge> EdgeNotifier;
-    /// The node observer registry.
-    typedef AlterationNotifier<Node> NodeNotifier;
-
-
-  protected:
-
-    mutable EdgeNotifier edge_notifier;
-
-    mutable NodeNotifier node_notifier;
-
-  public:
-
-    /// \brief Gives back the edge alteration notifier.
-    ///
-    /// Gives back the edge alteration notifier.
-    EdgeNotifier& getNotifier(Edge) const {
-      return edge_notifier;
-    }
-
-    /// \brief Gives back the node alteration notifier.
-    ///
-    /// Gives back the node alteration notifier.
-    NodeNotifier& getNotifier(Node) const {
-      return node_notifier;
-    }
-
-    ~AlterableGraphExtender() {
-      node_notifier.clear();
-      edge_notifier.clear();
-    }
-    
-  };
-
-
-  template <typename _Base> 
-  class AlterableEdgeSetExtender : public _Base {
-  public:
-
-    typedef AlterableEdgeSetExtender Graph;
-    typedef _Base Parent;
-
-    typedef typename Parent::Edge Edge;
-
-    /// The edge observer registry.
-    typedef AlterationNotifier<Edge> EdgeNotifier;
-
-  protected:
-
-    mutable EdgeNotifier edge_notifier;
-
-  public:
-
-    /// \brief Gives back the edge alteration notifier.
-    ///
-    /// Gives back the edge alteration notifier.
-    EdgeNotifier& getNotifier(Edge) const {
-      return edge_notifier;
-    }
-
-    ~AlterableEdgeSetExtender() {
-      edge_notifier.clear();
-    }
-    
-  };
-
-  /// \brief Class to extend an undirected graph with the functionality of
-  /// alteration observing.
-  ///
-  /// \todo Document.
-  ///
-  /// \sa AlterableGraphExtender
-  ///
-  /// \bug This should be done some other way. Possibilities: template
-  /// specialization (not very easy, if at all possible); some kind of
-  /// enable_if boost technique?
-
-  template <typename _Base> 
-  class AlterableUGraphExtender
-    : public AlterableGraphExtender<_Base> {
-  public:
-
-    typedef AlterableUGraphExtender Graph;
-    typedef AlterableGraphExtender<_Base> Parent;
-
-    typedef typename Parent::UEdge UEdge;
-
-    /// The edge observer registry.
-    typedef AlterationNotifier<UEdge> UEdgeNotifier;
-
-  protected:
-
-    mutable UEdgeNotifier u_edge_notifier;
-
-  public:
-
-    using Parent::getNotifier;
-    UEdgeNotifier& getNotifier(UEdge) const {
-      return u_edge_notifier;
-    }
-
-    ~AlterableUGraphExtender() {
-      u_edge_notifier.clear();
-    }
-  };
-
-  template <typename _Base> 
-  class AlterableUEdgeSetExtender
-    : public AlterableEdgeSetExtender<_Base> {
-  public:
-
-    typedef AlterableUEdgeSetExtender Graph;
-    typedef AlterableEdgeSetExtender<_Base> Parent;
-
-    typedef typename Parent::UEdge UEdge;
-
-    typedef AlterationNotifier<UEdge> UEdgeNotifier;
-
-  protected:
-
-    mutable UEdgeNotifier u_edge_notifier;
-
-  public:
-
-    using Parent::getNotifier;
-    UEdgeNotifier& getNotifier(UEdge) const {
-      return u_edge_notifier;
-    }
-
-    ~AlterableUEdgeSetExtender() {
-      u_edge_notifier.clear();
-    }
-  };
-
-
-
-  template <typename _Base>
-  class AlterableBpUGraphExtender : public _Base {
-  public:
-
-    typedef _Base Parent;
-    typedef AlterableBpUGraphExtender 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;
-  
-  
-    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;
-    }
-
-    ~AlterableBpUGraphExtender() {
-      nodeNotifier.clear();
-      bNodeNotifier.clear();
-      aNodeNotifier.clear();
-      edgeNotifier.clear();
-      uEdgeNotifier.clear();
-    }
-
-  };
   
 /// @}
   
diff -r ef2d00e46897 -r c2992fd74dad lemon/bits/clearable_graph_extender.h
--- a/lemon/bits/clearable_graph_extender.h	Wed Feb 22 12:45:59 2006 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,123 +0,0 @@
-/* -*- C++ -*-
- *
- * This file is a part of LEMON, a generic C++ optimization library
- *
- * Copyright (C) 2003-2006
- * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
- * (Egervary Research Group on Combinatorial Optimization, EGRES).
- *
- * Permission to use, modify and distribute this software is granted
- * provided that this copyright notice appears in all copies. For
- * precise terms see the accompanying LICENSE file.
- *
- * This software is provided "AS IS" with no warranty of any kind,
- * express or implied, and with no claim as to its suitability for any
- * purpose.
- *
- */
-
-#ifndef LEMON_CLEARABLE_GRAPH_EXTENDER_H
-#define LEMON_CLEARABLE_GRAPH_EXTENDER_H
-
-#include <lemon/invalid.h>
-
-
-namespace lemon {
-
-  template <typename _Base> 
-  class ClearableGraphExtender : public _Base {
-  public:
-
-    typedef ClearableGraphExtender Graph;
-    typedef _Base Parent;
-    typedef typename Parent::Node Node;
-    typedef typename Parent::Edge Edge;
-
-    void clear() {
-      Parent::getNotifier(Node()).clear();
-      Parent::getNotifier(Edge()).clear();
-      Parent::clear();
-    }
-
-  };
-
-  template <typename _Base> 
-  class ClearableEdgeSetExtender : public _Base {
-  public:
-
-    typedef ClearableEdgeSetExtender Graph;
-    typedef _Base Parent;
-    typedef typename Parent::Node Node;
-    typedef typename Parent::Edge Edge;
-
-    void clear() {
-      Parent::getNotifier(Edge()).clear();
-      Parent::clear();
-    }
-
-  };
-
-  template <typename _Base> 
-  class ClearableUGraphExtender : public _Base {
-  public:
-
-    typedef ClearableUGraphExtender Graph;
-    typedef _Base Parent;
-    typedef typename Parent::Node Node;
-    typedef typename Parent::UEdge UEdge;
-    typedef typename Parent::Edge Edge;
-
-    void clear() {
-      Parent::getNotifier(Node()).clear();
-      Parent::getNotifier(UEdge()).clear();
-      Parent::getNotifier(Edge()).clear();
-      Parent::clear();
-    }
-  };
-
-  template <typename _Base> 
-  class ClearableUEdgeSetExtender : public _Base {
-  public:
-
-    typedef ClearableUEdgeSetExtender Graph;
-    typedef _Base Parent;
-    typedef typename Parent::Node Node;
-    typedef typename Parent::UEdge UEdge;
-    typedef typename Parent::Edge Edge;
-
-    void clear() {
-      Parent::getNotifier(UEdge()).clear();
-      Parent::getNotifier(Edge()).clear();
-      Parent::clear();
-    }
-
-  };
-
-
-  template <typename _Base>
-  class ClearableBpUGraphExtender : public _Base {
-  public:
-
-    typedef _Base Parent;
-    typedef ClearableBpUGraphExtender 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;
-
-    void clear() {
-      Parent::getNotifier(Edge()).clear();
-      Parent::getNotifier(UEdge()).clear();
-      Parent::getNotifier(Node()).clear();
-      Parent::getNotifier(BNode()).clear();
-      Parent::getNotifier(ANode()).clear();
-      Parent::clear();
-    }
-
-  };
-
-}
-
-#endif
diff -r ef2d00e46897 -r c2992fd74dad lemon/bits/default_map.h
--- a/lemon/bits/default_map.h	Wed Feb 22 12:45:59 2006 +0000
+++ b/lemon/bits/default_map.h	Wed Feb 22 18:26:56 2006 +0000
@@ -22,6 +22,7 @@
 
 #include <lemon/bits/array_map.h>
 #include <lemon/bits/vector_map.h>
+#include <lemon/bits/static_map.h>
 
 ///\ingroup graphmapfactory
 ///\file
@@ -30,7 +31,8 @@
 
 namespace lemon {
   
-#ifndef GLIBCXX_DEBUG
+  
+#ifndef _GLIBCXX_DEBUG
 
   template <typename _Graph, typename _Item, typename _Value>
   struct DefaultMapSelector {
@@ -167,483 +169,6 @@
 
   };
 
-
-  /// \e
-  template <typename _Base> 
-  class MappableGraphExtender : public _Base {
-  public:
-
-    typedef MappableGraphExtender<_Base> Graph;
-    typedef _Base Parent;
-
-    typedef typename Parent::Node Node;
-    typedef typename Parent::NodeIt NodeIt;
-
-    typedef typename Parent::Edge Edge;
-    typedef typename Parent::EdgeIt EdgeIt;
-
-    
-    template <typename _Value>
-    class NodeMap 
-      : public IterableMapExtender<DefaultMap<Graph, Node, _Value> > {
-    public:
-      typedef MappableGraphExtender 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 MappableGraphExtender 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;
-      }
-    };
-    
-  };
-
-  /// \e
-  template <typename _Base> 
-  class MappableEdgeSetExtender : public _Base {
-  public:
-
-    typedef MappableEdgeSetExtender<_Base> Graph;
-    typedef _Base Parent;
-
-    typedef typename Parent::Edge Edge;
-    typedef typename Parent::EdgeIt EdgeIt;
-
-    template <typename _Value>
-    class EdgeMap 
-      : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
-    public:
-      typedef MappableEdgeSetExtender 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;
-      }
-    };
-    
-  };
-
-  /// \e
-  template <typename _Base> 
-  class MappableUGraphExtender : 
-    public MappableGraphExtender<_Base> {
-  public:
-
-    typedef MappableUGraphExtender Graph;
-    typedef MappableGraphExtender<_Base> Parent;
-
-    typedef typename Parent::UEdge UEdge;
-
-    template <typename _Value>
-    class UEdgeMap 
-      : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
-    public:
-      typedef MappableUGraphExtender 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;
-      }
-    };
-
-
-  };
-
-  /// \e
-  template <typename _Base> 
-  class MappableUEdgeSetExtender : 
-    public MappableEdgeSetExtender<_Base> {
-  public:
-
-    typedef MappableUEdgeSetExtender Graph;
-    typedef MappableEdgeSetExtender<_Base> Parent;
-
-    typedef typename Parent::UEdge UEdge;
-
-    template <typename _Value>
-    class UEdgeMap 
-      : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
-    public:
-      typedef MappableUEdgeSetExtender 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;
-      }
-    };
-
-
-  };
-
-
-  template <typename _Base>
-  class MappableBpUGraphExtender : public _Base {
-  public:
-
-    typedef _Base Parent;
-    typedef MappableBpUGraphExtender Graph;
-
-    typedef typename Parent::Node Node;
-    typedef typename Parent::ANode ANode;
-    typedef typename Parent::BNode BNode;
-    typedef typename Parent::Edge Edge;
-    typedef typename Parent::UEdge UEdge;
-    
-    template <typename _Value>
-    class ANodeMap 
-      : public IterableMapExtender<DefaultMap<Graph, ANode, _Value> > {
-    public:
-      typedef MappableBpUGraphExtender 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 MappableBpUGraphExtender 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 Parent::NodeNotifier::ObserverBase {
-    public:
-      typedef MappableBpUGraphExtender 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) {
-	Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
-      }
-      NodeMapBase(const Graph& _g, const _Value& _v) 
-	: graph(&_g), bNodeMap(_g, _v), 
-	  aNodeMap(_g, _v) {
-	Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
-      }
-
-      virtual ~NodeMapBase() {      
-	if (Parent::NodeNotifier::ObserverBase::attached()) {
-	  Parent::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 MappableBpUGraphExtender 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 MappableBpUGraphExtender 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 MappableBpUGraphExtender 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;
-      }
-    };
-  
-  };
-
 }
 
 #endif
diff -r ef2d00e46897 -r c2992fd74dad lemon/bits/edge_set_extender.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/bits/edge_set_extender.h	Wed Feb 22 18:26:56 2006 +0000
@@ -0,0 +1,606 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2006
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+
+namespace lemon {
+
+  template <typename Base>
+  class EdgeSetExtender : public Base {
+  public:
+
+    typedef Base Parent;
+    typedef EdgeSetExtender Graph;
+
+    // Base extensions
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+
+    int maxId(Node) const {
+      return Parent::maxNodeId();
+    }
+
+    int maxId(Edge) const {
+      return Parent::maxEdgeId();
+    }
+
+    Node fromId(int id, Node) const {
+      return Parent::nodeFromId(id);
+    }
+
+    Edge fromId(int id, Edge) const {
+      return Parent::edgeFromId(id);
+    }
+
+    Node oppositeNode(const Node &n, const Edge &e) const {
+      if (n == Parent::source(e))
+	return Parent::target(e);
+      else if(n==Parent::target(e))
+	return Parent::source(e);
+      else
+	return INVALID;
+    }
+
+
+    // Alteration notifier extensions
+
+    /// The edge observer registry.
+    typedef AlterationNotifier<Edge> EdgeNotifier;
+
+  protected:
+
+    mutable EdgeNotifier edge_notifier;
+
+  public:
+
+    /// \brief Gives back the edge alteration notifier.
+    ///
+    /// Gives back the edge alteration notifier.
+    EdgeNotifier& getNotifier(Edge) const {
+      return edge_notifier;
+    }
+
+    // Iterable extensions
+
+    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((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);
+    }
+
+    using Parent::first;
+
+    // Mappable extension
+    
+    template <typename _Value>
+    class EdgeMap 
+      : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
+    public:
+      typedef EdgeSetExtender 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;
+      }
+    };
+
+
+    // Alteration extension
+
+    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();
+      Parent::clear();
+    }
+
+    void erase(const Edge& edge) {
+      getNotifier(Edge()).erase(edge);
+      Parent::erase(edge);
+    }
+
+
+    ~EdgeSetExtender() {
+      edge_notifier.clear();
+    }
+
+  };
+
+
+  template <typename Base>
+  class UEdgeSetExtender : public Base {
+
+  public:
+
+    typedef Base Parent;
+    typedef UEdgeSetExtender Graph;
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+    typedef typename Parent::UEdge UEdge;
+
+
+    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);
+    }
+
+    typedef AlterationNotifier<Edge> EdgeNotifier;
+    typedef AlterationNotifier<UEdge> UEdgeNotifier;
+
+
+  protected:
+
+    mutable EdgeNotifier edge_notifier;
+    mutable UEdgeNotifier uedge_notifier;
+
+  public:
+    
+    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 UEdgeSetExtender;
+      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);
+    }
+
+
+    template <typename _Value>
+    class EdgeMap 
+      : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
+    public:
+      typedef UEdgeSetExtender 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 UEdgeSetExtender 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
+
+    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();
+      Parent::clear();
+    }
+
+    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);
+    }
+
+
+    ~UEdgeSetExtender() {
+      getNotifier(Edge()).clear();
+      getNotifier(UEdge()).clear();
+    }
+    
+  };
+}
diff -r ef2d00e46897 -r c2992fd74dad lemon/bits/erasable_graph_extender.h
--- a/lemon/bits/erasable_graph_extender.h	Wed Feb 22 12:45:59 2006 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,138 +0,0 @@
-/* -*- C++ -*-
- *
- * This file is a part of LEMON, a generic C++ optimization library
- *
- * Copyright (C) 2003-2006
- * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
- * (Egervary Research Group on Combinatorial Optimization, EGRES).
- *
- * Permission to use, modify and distribute this software is granted
- * provided that this copyright notice appears in all copies. For
- * precise terms see the accompanying LICENSE file.
- *
- * This software is provided "AS IS" with no warranty of any kind,
- * express or implied, and with no claim as to its suitability for any
- * purpose.
- *
- */
-
-#ifndef LEMON_ERASABLE_GRAPH_EXTENDER_H
-#define LEMON_ERASABLE_GRAPH_EXTENDER_H
-
-#include <vector>
-
-#include <lemon/invalid.h>
-
-
-namespace lemon {
-
-  template <typename _Base> 
-  class ErasableGraphExtender : public _Base {
-  public:
-
-    typedef ErasableGraphExtender Graph;
-    typedef _Base Parent;
-
-    typedef typename Parent::Node Node;
-    typedef typename Parent::Edge Edge;
-
-    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);
-      }
-
-      Parent::getNotifier(Node()).erase(node);
-      Parent::erase(node);
-    }
-    
-    void erase(const Edge& edge) {
-      Parent::getNotifier(Edge()).erase(edge);
-      Parent::erase(edge);
-    }
-
-  };
-
-  template <typename _Base> 
-  class ErasableEdgeSetExtender : public _Base {
-  public:
-
-    typedef ErasableEdgeSetExtender Graph;
-    typedef _Base Parent;
-
-    typedef typename Parent::Edge Edge;
-
-    void erase(const Edge& edge) {
-      Parent::getNotifier(Edge()).erase(edge);
-      Parent::erase(edge);
-    }
-
-  };
-
-  template <typename _Base> 
-  class ErasableUGraphExtender : public _Base {
-  public:
-
-    typedef ErasableUGraphExtender Graph;
-    typedef _Base Parent;
-
-    typedef typename Parent::Node Node;
-    typedef typename Parent::UEdge UEdge;
-    typedef typename Parent::Edge Edge;
-
-    void erase(const Node& node) {
-      Edge edge;
-      Parent::firstOut(edge, node);
-      while (edge != INVALID ) {
-	erase(edge);
-	Parent::firstOut(edge, node);
-      } 
-
-      Parent::getNotifier(Node()).erase(node);
-      Parent::erase(node);
-    }
-    
-    void erase(const UEdge& uedge) {
-      std::vector<Edge> edges;
-      edges.push_back(Parent::direct(uedge,true));
-      edges.push_back(Parent::direct(uedge,false));
-      Parent::getNotifier(Edge()).erase(edges);
-      Parent::getNotifier(UEdge()).erase(uedge);
-      Parent::erase(uedge);
-    }
-
-  };
-
-  template <typename _Base> 
-  class ErasableUEdgeSetExtender : public _Base {
-  public:
-
-    typedef ErasableUEdgeSetExtender Graph;
-    typedef _Base Parent;
-
-    typedef typename Parent::Node Node;
-    typedef typename Parent::UEdge UEdge;
-    typedef typename Parent::Edge Edge;
-
-    void erase(const UEdge& uedge) {
-      std::vector<Edge> edges;
-      edges.push_back(Parent::direct(uedge,true));
-      edges.push_back(Parent::direct(uedge,false));
-      Parent::getNotifier(Edge()).erase(edges);
-      Parent::getNotifier(UEdge()).erase(uedge);
-      Parent::erase(uedge);
-    }
-
-  };
-
-}
-
-#endif
diff -r ef2d00e46897 -r c2992fd74dad lemon/bits/extendable_graph_extender.h
--- a/lemon/bits/extendable_graph_extender.h	Wed Feb 22 12:45:59 2006 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,166 +0,0 @@
-/* -*- C++ -*-
- *
- * This file is a part of LEMON, a generic C++ optimization library
- *
- * Copyright (C) 2003-2006
- * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
- * (Egervary Research Group on Combinatorial Optimization, EGRES).
- *
- * Permission to use, modify and distribute this software is granted
- * provided that this copyright notice appears in all copies. For
- * precise terms see the accompanying LICENSE file.
- *
- * This software is provided "AS IS" with no warranty of any kind,
- * express or implied, and with no claim as to its suitability for any
- * purpose.
- *
- */
-
-#ifndef LEMON_EXTENDABLE_GRAPH_EXTENDER_H
-#define LEMON_EXTENDABLE_GRAPH_EXTENDER_H
-
-namespace lemon {
-
-  template <typename _Base> 
-  class ExtendableGraphExtender : public _Base {
-  public:
-
-    typedef ExtendableGraphExtender Graph;
-    typedef _Base Parent;
-
-    typedef typename Parent::Node Node;
-    typedef typename Parent::Edge Edge;
-
-    Node addNode() {
-      Node node = Parent::addNode();
-      Parent::getNotifier(Node()).add(node);
-      return node;
-    }
-    
-    Edge addEdge(const Node& from, const Node& to) {
-      Edge edge = Parent::addEdge(from, to);
-      Parent::getNotifier(Edge()).add(edge);
-      return edge;
-    }
-
-  };
-
-  template <typename _Base> 
-  class ExtendableEdgeSetExtender : public _Base {
-  public:
-
-    typedef ExtendableEdgeSetExtender Graph;
-    typedef _Base Parent;
-
-    typedef typename Parent::Edge Edge;
-    typedef typename Parent::Node Node;
-
-    Edge addEdge(const Node& from, const Node& to) {
-      Edge edge = Parent::addEdge(from, to);
-      Parent::getNotifier(Edge()).add(edge);
-      return edge;
-    }
-
-  };
-
-  template <typename _Base> 
-  class ExtendableUGraphExtender : public _Base {
-  public:
-
-    typedef ExtendableUGraphExtender Graph;
-    typedef _Base Parent;
-
-    typedef typename Parent::Node Node;
-    typedef typename Parent::Edge Edge;
-    typedef typename Parent::UEdge UEdge;
-
-    Node addNode() {
-      Node node = Parent::addNode();
-      Parent::getNotifier(Node()).add(node);
-      return node;
-    }
-
-    UEdge addEdge(const Node& from, const Node& to) {
-      UEdge uedge = Parent::addEdge(from, to);
-      Parent::getNotifier(UEdge()).add(uedge);
-
-      std::vector<Edge> edges;
-      edges.push_back(Parent::direct(uedge, true));
-      edges.push_back(Parent::direct(uedge, false));
-      Parent::getNotifier(Edge()).add(edges);
-
-      return uedge;
-    }
-
-  };
-
-  template <typename _Base> 
-  class ExtendableUEdgeSetExtender : public _Base {
-  public:
-
-    typedef ExtendableUEdgeSetExtender Graph;
-    typedef _Base Parent;
-
-    typedef typename Parent::Node Node;
-    typedef typename Parent::Edge Edge;
-    typedef typename Parent::UEdge UEdge;
-
-    UEdge addEdge(const Node& from, const Node& to) {
-      UEdge uedge = Parent::addEdge(from, to);
-      Parent::getNotifier(UEdge()).add(uedge);
-
-      std::vector<Edge> edges;
-      edges.push_back(Parent::direct(uedge, true));
-      edges.push_back(Parent::direct(uedge, false));
-      Parent::getNotifier(Edge()).add(edges);
-
-      return uedge;
-    }
-
-  };
-
-
-  template <typename _Base>
-  class ExtendableBpUGraphExtender : public _Base {
-  public:
-
-    typedef _Base Parent;
-    typedef ExtendableBpUGraphExtender 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 addANode() {
-      Node node = Parent::addANode();
-      Parent::getNotifier(ANode()).add(node);
-      Parent::getNotifier(Node()).add(node);
-      return node;
-    }
-
-    Node addBNode() {
-      Node node = Parent::addBNode();
-      Parent::getNotifier(BNode()).add(node);
-      Parent::getNotifier(Node()).add(node);
-      return node;
-    }
-  
-    UEdge addEdge(const Node& source, const Node& target) {
-      UEdge uedge = Parent::addEdge(source, target);
-      Parent::getNotifier(UEdge()).add(uedge);
-    
-      std::vector<Edge> edges;
-      edges.push_back(Parent::direct(uedge, true));
-      edges.push_back(Parent::direct(uedge, false));
-      Parent::getNotifier(Edge()).add(edges);
-    
-      return uedge;
-    }
-
-  };
-
-}
-
-#endif
diff -r ef2d00e46897 -r c2992fd74dad lemon/bits/graph_adaptor_extender.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/bits/graph_adaptor_extender.h	Wed Feb 22 18:26:56 2006 +0000
@@ -0,0 +1,429 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2006
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_GRAPH_ADAPTOR_EXTENDER_H
+#define LEMON_GRAPH_ADAPTOR_EXTENDER_H
+
+
+namespace lemon {
+
+  template <typename Base>
+  class GraphAdaptorExtender : public Base {
+  public:
+
+    typedef Base Parent;
+    typedef GraphAdaptorExtender Graph;
+
+    // Base extensions
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+
+    int maxId(Node) const {
+      return Parent::maxNodeId();
+    }
+
+    int maxId(Edge) const {
+      return Parent::maxEdgeId();
+    }
+
+    Node fromId(int id, Node) const {
+      return Parent::nodeFromId(id);
+    }
+
+    Edge fromId(int id, Edge) const {
+      return Parent::edgeFromId(id);
+    }
+
+    Node oppositeNode(const Node &n, const Edge &e) const {
+      if (n == Parent::source(e))
+	return Parent::target(e);
+      else if(n==Parent::target(e))
+	return Parent::source(e);
+      else
+	return INVALID;
+    }
+
+    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 Base> 
+  class UGraphAdaptorExtender : public Base {
+  public:
+    
+    typedef Base Parent;
+    typedef UGraphAdaptorExtender 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);
+    }
+
+
+    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 UGraphAdaptorExtender;
+      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(static_cast<UEdge&>(*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);
+    }
+
+  };
+
+
+}
+
+
+#endif
diff -r ef2d00e46897 -r c2992fd74dad lemon/bits/graph_extender.h
--- a/lemon/bits/graph_extender.h	Wed Feb 22 12:45:59 2006 +0000
+++ b/lemon/bits/graph_extender.h	Wed Feb 22 18:26:56 2006 +0000
@@ -22,15 +22,19 @@
 #include <lemon/invalid.h>
 #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;
     typedef typename Parent::Edge Edge;
 
@@ -59,24 +63,278 @@
 	return INVALID;
     }
 
-  };
+    // Alterable extension
 
-  template <typename _Base>
-  class UGraphExtender : public _Base {
-    typedef _Base Parent;
-    typedef UGraphExtender Graph;
+    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 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;
 
       Edge(const UEdge &ue, bool _forward) :
@@ -101,16 +359,7 @@
     };
 
 
-    /// \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;
 
     /// Source of the given Edge.
@@ -118,8 +367,6 @@
       return e.forward ? Parent::source(e) : Parent::target(e);
     }
 
-    /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
-    /// or something???
     using Parent::target;
 
     /// Target of the given Edge.
@@ -127,24 +374,6 @@
       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));
-    }
-
     /// \brief Directed edge from an undirected edge.
     ///
     /// Returns a directed edge corresponding to the specified UEdge.
@@ -163,12 +392,13 @@
 
 
     using Parent::first;
+    using Parent::next;
+
     void first(Edge &e) const {
       Parent::first(e);
       e.forward=true;
     }
 
-    using Parent::next;
     void next(Edge &e) const {
       if( e.forward ) {
 	e.forward = false;
@@ -179,8 +409,6 @@
       }
     }
 
-  public:
-
     void firstOut(Edge &e, const Node &n) const {
       Parent::firstIn(e,n);
       if( UEdge(e) != INVALID ) {
@@ -229,21 +457,6 @@
       }
     }
 
-    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;
       Parent::firstOut(e, n);
@@ -251,6 +464,7 @@
       d = false;
       Parent::firstIn(e, n);
     }
+
     void nextInc(UEdge &e, bool &d) const {
       if (d) {
 	Node s = Parent::source(e);
@@ -263,14 +477,17 @@
       }
     }
 
-    // Miscellaneous stuff:
+    Node nodeFromId(int id) const {
+      return Parent::nodeFromId(id);
+    }
 
-    /// \todo these methods (id, maxEdgeId) should be moved into separate
-    /// Extender
+    Edge edgeFromId(int id) const {
+      return direct(Parent::edgeFromId(id >> 1), bool(id & 1));
+    }
 
-    // using Parent::id;
-    // Using "using" is not a good idea, cause it could be that there is
-    // no "id" in Parent...
+    UEdge uEdgeFromId(int id) const {
+      return Parent::edgeFromId(id >> 1);
+    }
 
     int id(const Node &n) const {
       return Parent::id(n);
@@ -296,16 +513,6 @@
       return Parent::maxEdgeId();
     }
 
-    int maxId(Node) const {
-      return maxNodeId();
-    }
-
-    int maxId(Edge) const {
-      return maxEdgeId();
-    }
-    int maxId(UEdge) const {
-      return maxUEdgeId();
-    }
 
     int edgeNum() const {
       return 2 * Parent::edgeNum();
@@ -315,31 +522,6 @@
       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 {
       if (prev == INVALID) {
 	UEdge edge = Parent::findEdge(source, target);
@@ -375,24 +557,486 @@
       }
       return INVALID;
     }
+  };
+
+
+  template <typename Base> 
+  class UGraphExtender : public Base {
+  public:
+    
+    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 BpUGraphExtender : public _Base {
+  template <typename Base>
+  class BpUGraphBaseExtender : public Base {
   public:
-    typedef _Base Parent;
-    typedef BpUGraphExtender Graph;
+    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);
     }
@@ -427,7 +1071,7 @@
     }
 
     class Edge : public UEdge {
-      friend class BpUGraphExtender;
+      friend class BpUGraphBaseExtender;
     protected:
       bool forward;
 
@@ -504,27 +1148,6 @@
       return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);
     }
 
-    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);
-    }
-
-    Node oppositeNode(const UEdge& edge, const Node& node) const {
-      return source(edge) == node ? 
-	target(edge) : 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);
     }
@@ -535,50 +1158,40 @@
       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));
+    bool direction(const Edge& edge) const {
+      return edge.forward;
     }
 
-    int id(const ANode& node) const {
-      return Parent::aNodeId(node);
+    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 {
+      return source(edge) == node ? 
+	target(edge) : source(edge);
     }
 
-    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);
+    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 Parent::direct(edge, !Parent::direction(edge));
+    }
 
 
     int maxId(Node) const {
@@ -591,10 +1204,10 @@
       return Parent::maxANodeId();
     }
     int maxId(Edge) const {
-      return maxEdgeId();
+      return Parent::maxEdgeId();
     }
     int maxId(UEdge) const {
-      return maxUEdgeId();
+      return Parent::maxUEdgeId();
     }
 
 
@@ -608,12 +1221,605 @@
       return Parent::fromBNodeId(id);
     }
     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();
+    }
+
+
   };
 
 }
diff -r ef2d00e46897 -r c2992fd74dad lemon/bits/iterable_graph_extender.h
--- a/lemon/bits/iterable_graph_extender.h	Wed Feb 22 12:45:59 2006 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,533 +0,0 @@
-/* -*- C++ -*-
- *
- * This file is a part of LEMON, a generic C++ optimization library
- *
- * Copyright (C) 2003-2006
- * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
- * (Egervary Research Group on Combinatorial Optimization, EGRES).
- *
- * Permission to use, modify and distribute this software is granted
- * provided that this copyright notice appears in all copies. For
- * precise terms see the accompanying LICENSE file.
- *
- * This software is provided "AS IS" with no warranty of any kind,
- * express or implied, and with no claim as to its suitability for any
- * purpose.
- *
- */
-
-#ifndef LEMON_ITERABLE_GRAPH_EXTENDER_H
-#define LEMON_ITERABLE_GRAPH_EXTENDER_H
-
-#include <lemon/invalid.h>
-#include <lemon/utility.h>
-
-namespace lemon {
-  
-  template <typename _Base>
-  class IterableGraphExtender : public _Base {
-  public:
-
-    /// Indicates that the graph is undirected.
-
-    ///\todo Better name?
-    ///
-    ///\bug Should it be here?
-    typedef False UTag;
-
-    typedef _Base Parent;
-    typedef IterableGraphExtender<_Base> Graph;
-
-    typedef typename Parent::Node Node;
-    typedef typename Parent::Edge Edge;
-
-
-    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((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);
-    }
-
-    using Parent::first;
-
-    /// \brief The opposite node on the given edge.
-    ///
-    /// Gives back the opposite on the given edge.
-    Node oppositeNode(const Node& n, const Edge& e) const {
-      if (Parent::source(e) == n) {
-	return Parent::target(e);
-      } else {
-	return Parent::source(e);
-      }
-    }
-
-  private:
-
-    // void first(NodeIt &) const;
-    // void first(EdgeIt &) const;
-    // void first(OutEdgeIt &) const;
-    // void first(InEdgeIt &) const;
-
-  };
-
-
-
-
-
-  
-  template <typename _Base>
-  class IterableUGraphExtender : public IterableGraphExtender<_Base> {
-  public:
-
-    /// Indicates that the graph is undirected.
-
-    ///\todo Better name?
-    ///
-    ///\bug Should it be here?
-    ///\bug Should be tested in the concept checker whether it is defined
-    ///correctly.
-    typedef True UTag;
-
-    typedef IterableGraphExtender<_Base> Parent;
-    typedef IterableUGraphExtender<_Base> Graph;
-    typedef typename Parent::Node Node;
-    typedef typename Parent::Edge Edge;
-    typedef typename Parent::UEdge UEdge;
-
-    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 { 
-      const Graph* graph;
-      bool direction;
-      friend class IterableUGraphExtender;
-    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; 
-      }
-    };
-
-    using Parent::baseNode;
-    using Parent::runningNode;
-
-    /// 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);
-    }
-
-    /// \brief The opposite node on the given undirected edge.
-    ///
-    /// Gives back the opposite on the given undirected edge.
-    Node oppositeNode(const Node& n, const UEdge& e) const {
-      if (Parent::source(e) == n) {
-	return Parent::target(e);
-      } else {
-	return Parent::source(e);
-      }
-    }
-
-  };
-
-
-  template <typename _Base>
-  class IterableBpUGraphExtender : public _Base {
-  public:
-    typedef _Base Parent;
-    typedef IterableBpUGraphExtender Graph;
-   
-    typedef typename Parent::Node Node;
-    typedef typename Parent::ANode ANode;
-    typedef typename Parent::BNode BNode;
-    typedef typename Parent::Edge Edge;
-    typedef typename Parent::UEdge UEdge;
-  
-    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 IterableBpUGraphExtender;
-      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 IterableBpUGraphExtender;
-      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 IterableBpUGraphExtender;
-      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 IterableBpUGraphExtender;
-      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 IterableBpUGraphExtender;
-      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 IterableBpUGraphExtender;
-      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 IterableBpUGraphExtender;
-      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);
-    }
-  
-  };
-
-}
-
-#endif // LEMON_GRAPH_EXTENDER_H
diff -r ef2d00e46897 -r c2992fd74dad lemon/bits/static_map.h
--- a/lemon/bits/static_map.h	Wed Feb 22 12:45:59 2006 +0000
+++ b/lemon/bits/static_map.h	Wed Feb 22 18:26:56 2006 +0000
@@ -56,11 +56,11 @@
   class StaticMap : public AlterationNotifier<_Item>::ObserverBase {
   public:
 
-    /// \brief Exception class for unsinported exceptions.
-    class UnsinportedOperation : public lemon::LogicError {
+    /// \brief Exception class for unsupported exceptions.
+    class UnsupportedOperation : public lemon::LogicError {
     public:
       virtual const char* exceptionName() const {
-	return "lemon::StaticMap::UnsinportedOperation";
+	return "lemon::StaticMap::UnsupportedOperation";
       }
     };
 
@@ -187,7 +187,7 @@
     /// and it overrides the add() member function of the observer base.
      
     void add(const Key&) {
-      throw UnsinportedOperation();
+      throw UnsupportedOperation();
     }
 
     /// \brief Erases a key from the map.
@@ -195,7 +195,7 @@
     /// Erase a key from the map. It called by the observer registry
     /// and it overrides the erase() member function of the observer base.     
     void erase(const Key&) {
-      throw UnsinportedOperation();
+      throw UnsupportedOperation();
     }
 
     /// Buildes the map.
@@ -224,396 +224,6 @@
 
   };
 
-  /// \e
-  template <typename _Base> 
-  class StaticMappableGraphExtender : public _Base {
-  public:
-
-    typedef StaticMappableGraphExtender<_Base> Graph;
-    typedef _Base Parent;
-
-    typedef typename Parent::Node Node;
-    typedef typename Parent::NodeIt NodeIt;
-
-    typedef typename Parent::Edge Edge;
-    typedef typename Parent::EdgeIt EdgeIt;
-
-    
-    template <typename _Value>
-    class NodeMap 
-      : public IterableMapExtender<StaticMap<Graph, Node, _Value> > {
-    public:
-      typedef StaticMappableGraphExtender Graph;
-      typedef IterableMapExtender<StaticMap<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<StaticMap<Graph, Edge, _Value> > {
-    public:
-      typedef StaticMappableGraphExtender Graph;
-      typedef IterableMapExtender<StaticMap<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;
-      }
-    };
-    
-  };
-
-  /// \e
-  template <typename _Base> 
-  class StaticMappableUGraphExtender : 
-    public StaticMappableGraphExtender<_Base> {
-  public:
-
-    typedef StaticMappableUGraphExtender Graph;
-    typedef StaticMappableGraphExtender<_Base> Parent;
-
-    typedef typename Parent::UEdge UEdge;
-
-    template <typename _Value>
-    class UEdgeMap 
-      : public IterableMapExtender<StaticMap<Graph, UEdge, _Value> > {
-    public:
-      typedef StaticMappableUGraphExtender Graph;
-      typedef IterableMapExtender<
-	StaticMap<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;
-      }
-    };
-
-  };
-
-  template <typename _Base>
-  class StaticMappableBpUGraphExtender : public _Base {
-  public:
-
-    typedef _Base Parent;
-    typedef StaticMappableBpUGraphExtender Graph;
-
-    typedef typename Parent::Node Node;
-    typedef typename Parent::ANode ANode;
-    typedef typename Parent::BNode BNode;
-    typedef typename Parent::Edge Edge;
-    typedef typename Parent::UEdge UEdge;
-    
-    template <typename _Value>
-    class ANodeMap 
-      : public IterableMapExtender<StaticMap<Graph, ANode, _Value> > {
-    public:
-      typedef StaticMappableBpUGraphExtender Graph;
-      typedef IterableMapExtender<StaticMap<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<StaticMap<Graph, BNode, _Value> > {
-    public:
-      typedef StaticMappableBpUGraphExtender Graph;
-      typedef IterableMapExtender<StaticMap<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 Parent::NodeNotifier::ObserverBase {
-    public:
-      typedef StaticMappableBpUGraphExtender 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) {
-	Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
-      }
-      NodeMapBase(const Graph& _g, const _Value& _v) 
-	: graph(&_g), bNodeMap(_g, _v), 
-	  aNodeMap(_g, _v) {
-	Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
-      }
-
-      virtual ~NodeMapBase() {      
-	if (Parent::NodeNotifier::ObserverBase::attached()) {
-	  Parent::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 StaticMappableBpUGraphExtender 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<StaticMap<Graph, Edge, _Value> > {
-    public:
-      typedef StaticMappableBpUGraphExtender Graph;
-      typedef IterableMapExtender<StaticMap<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<StaticMap<Graph, UEdge, _Value> > {
-    public:
-      typedef StaticMappableBpUGraphExtender Graph;
-      typedef IterableMapExtender<StaticMap<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;
-      }
-    };
-  
-  };
-
 }
 
 #endif
diff -r ef2d00e46897 -r c2992fd74dad lemon/concept/bpugraph.h
--- a/lemon/concept/bpugraph.h	Wed Feb 22 12:45:59 2006 +0000
+++ b/lemon/concept/bpugraph.h	Wed Feb 22 18:26:56 2006 +0000
@@ -70,7 +70,7 @@
     public:
       /// \todo undocumented
       ///
-      typedef True UTag;
+      typedef True UndirectedTag;
 
       /// \brief The base type of node iterators, 
       /// or in other words, the trivial node iterator.
diff -r ef2d00e46897 -r c2992fd74dad lemon/concept/graph.h
--- a/lemon/concept/graph.h	Wed Feb 22 12:45:59 2006 +0000
+++ b/lemon/concept/graph.h	Wed Feb 22 18:26:56 2006 +0000
@@ -44,8 +44,6 @@
          public IterableGraphComponent, public MappableGraphComponent {
     public:
 
-      typedef False UTag;
-      
       typedef BaseGraphComponent::Node Node;
       typedef BaseGraphComponent::Edge Edge;
 
@@ -123,10 +121,6 @@
     public:
       ///\e
 
-      ///\todo undocumented
-      ///
-      typedef False UTag;
-
       /// Defalult constructor.
 
       /// Defalult constructor.
diff -r ef2d00e46897 -r c2992fd74dad lemon/concept/ugraph.h
--- a/lemon/concept/ugraph.h	Wed Feb 22 12:45:59 2006 +0000
+++ b/lemon/concept/ugraph.h	Wed Feb 22 18:26:56 2006 +0000
@@ -245,7 +245,7 @@
 
       ///\todo undocumented
       ///
-      typedef True UTag;
+      typedef True UndirectedTag;
 
       /// \brief The base type of node iterators, 
       /// or in other words, the trivial node iterator.
diff -r ef2d00e46897 -r c2992fd74dad lemon/edge_set.h
--- a/lemon/edge_set.h	Wed Feb 22 12:45:59 2006 +0000
+++ b/lemon/edge_set.h	Wed Feb 22 18:26:56 2006 +0000
@@ -19,13 +19,8 @@
 #ifndef LEMON_EDGE_SET_H
 #define LEMON_EDGE_SET_H
 
-#include <lemon/bits/erasable_graph_extender.h>
-#include <lemon/bits/clearable_graph_extender.h>
-#include <lemon/bits/extendable_graph_extender.h>
-#include <lemon/bits/iterable_graph_extender.h>
-#include <lemon/bits/alteration_notifier.h>
-#include <lemon/bits/default_map.h>
-#include <lemon/bits/graph_extender.h>
+
+#include <lemon/bits/edge_set_extender.h>
 
 /// \ingroup graphs
 /// \file
@@ -229,26 +224,11 @@
   /// In the edge extension and removing it conforms to the 
   /// \ref concept::ErasableGraph "ErasableGraph" concept.
   template <typename _Graph>
-  class ListEdgeSet :
-    public ErasableEdgeSetExtender<
-    ClearableEdgeSetExtender<
-    ExtendableEdgeSetExtender<
-    MappableEdgeSetExtender<
-    IterableGraphExtender<
-    AlterableEdgeSetExtender<
-    GraphExtender<
-    ListEdgeSetBase<_Graph> > > > > > > > {
+  class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<_Graph> > {
 
   public:
 
-    typedef ErasableEdgeSetExtender<
-      ClearableEdgeSetExtender<
-      ExtendableEdgeSetExtender<
-      MappableEdgeSetExtender<
-      IterableGraphExtender<
-      AlterableEdgeSetExtender<
-      GraphExtender<
-      ListEdgeSetBase<_Graph> > > > > > > > Parent;
+    typedef EdgeSetExtender<ListEdgeSetBase<_Graph> > Parent;
     
     typedef typename Parent::Node Node;
     typedef typename Parent::Edge Edge;
@@ -336,26 +316,13 @@
   /// In the edge extension and removing it conforms to the 
   /// \ref concept::ErasableUGraph "ErasableUGraph" concept.
   template <typename _Graph>
-  class ListUEdgeSet :
-    public ErasableUEdgeSetExtender<
-    ClearableUEdgeSetExtender<
-    ExtendableUEdgeSetExtender<
-    MappableUEdgeSetExtender<
-    IterableUGraphExtender<
-    AlterableUEdgeSetExtender<
-    UGraphExtender<
-    ListEdgeSetBase<_Graph> > > > > > > > {
+  class ListUEdgeSet 
+    : public UEdgeSetExtender<UGraphBaseExtender<ListEdgeSetBase<_Graph> > > {
 
   public:
 
-    typedef ErasableUEdgeSetExtender<
-      ClearableUEdgeSetExtender<
-      ExtendableUEdgeSetExtender<
-      MappableUEdgeSetExtender<
-      IterableUGraphExtender<
-      AlterableUEdgeSetExtender<
-      UGraphExtender<
-      ListEdgeSetBase<_Graph> > > > > > > > Parent;
+    typedef UEdgeSetExtender<UGraphBaseExtender<
+      ListEdgeSetBase<_Graph> > > Parent;
     
     typedef typename Parent::Node Node;
     typedef typename Parent::Edge Edge;
@@ -567,24 +534,11 @@
   /// In the edge extension and removing it conforms to the 
   /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
   template <typename _Graph>
-  class SmartEdgeSet :
-    public ClearableEdgeSetExtender<
-    ExtendableEdgeSetExtender<
-    MappableEdgeSetExtender<
-    IterableGraphExtender<
-    AlterableEdgeSetExtender<
-    GraphExtender<
-    SmartEdgeSetBase<_Graph> > > > > > > {
+  class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<_Graph> > {
 
   public:
 
-    typedef ClearableEdgeSetExtender<
-      ExtendableEdgeSetExtender<
-      MappableEdgeSetExtender<
-      IterableGraphExtender<
-      AlterableEdgeSetExtender<
-      GraphExtender<
-      SmartEdgeSetBase<_Graph> > > > > > > Parent;
+    typedef EdgeSetExtender<SmartEdgeSetBase<_Graph> > Parent;
     
     typedef typename Parent::Node Node;
     typedef typename Parent::Edge Edge;
@@ -671,24 +625,13 @@
   /// In the edge extension and removing it conforms to the 
   /// \ref concept::ExtendableUGraph "ExtendableUGraph" concept.
   template <typename _Graph>
-  class SmartUEdgeSet :
-    public ClearableUEdgeSetExtender<
-    ExtendableUEdgeSetExtender<
-    MappableUEdgeSetExtender<
-    IterableUGraphExtender<
-    AlterableUEdgeSetExtender<
-    UGraphExtender<
-    SmartEdgeSetBase<_Graph> > > > > > > {
+  class SmartUEdgeSet 
+    : public UEdgeSetExtender<UGraphBaseExtender<SmartEdgeSetBase<_Graph> > > {
 
   public:
 
-    typedef ClearableUEdgeSetExtender<
-      ExtendableUEdgeSetExtender<
-      MappableUEdgeSetExtender<
-      IterableUGraphExtender<
-      AlterableUEdgeSetExtender<
-      UGraphExtender<
-      SmartEdgeSetBase<_Graph> > > > > > > Parent;
+    typedef UEdgeSetExtender<UGraphBaseExtender<
+      SmartEdgeSetBase<_Graph> > > Parent;
     
     typedef typename Parent::Node Node;
     typedef typename Parent::Edge Edge;
diff -r ef2d00e46897 -r c2992fd74dad lemon/euler.h
--- a/lemon/euler.h	Wed Feb 22 12:45:59 2006 +0000
+++ b/lemon/euler.h	Wed Feb 22 18:26:56 2006 +0000
@@ -233,7 +233,7 @@
 #ifdef DOXYGEN
   bool
 #else
-  typename enable_if<typename Graph::UTag,bool>::type
+  typename enable_if<UndirectedTagIndicator<Graph>,bool>::type
   euler(const Graph &g) 
   {
     for(typename Graph::NodeIt n(g);n!=INVALID;++n)
@@ -241,7 +241,7 @@
     return connected(g);
   }
   template<class Graph>
-  typename disable_if<typename Graph::UTag,bool>::type
+  typename disable_if<UndirectedTagIndicator<Graph>,bool>::type
 #endif
   euler(const Graph &g) 
   {
diff -r ef2d00e46897 -r c2992fd74dad lemon/fredman_tarjan.h
--- a/lemon/fredman_tarjan.h	Wed Feb 22 12:45:59 2006 +0000
+++ b/lemon/fredman_tarjan.h	Wed Feb 22 18:26:56 2006 +0000
@@ -504,7 +504,7 @@
       Create ft(graph,cost);
     ft.treeMap(tree);
     ft.run();
-  };
+  }
 
 } //END OF NAMESPACE LEMON
 
diff -r ef2d00e46897 -r c2992fd74dad lemon/full_graph.h
--- a/lemon/full_graph.h	Wed Feb 22 12:45:59 2006 +0000
+++ b/lemon/full_graph.h	Wed Feb 22 18:26:56 2006 +0000
@@ -22,11 +22,9 @@
 #include <cmath>
 
 
-#include <lemon/bits/iterable_graph_extender.h>
-#include <lemon/bits/alteration_notifier.h>
-#include <lemon/bits/static_map.h>
 #include <lemon/bits/graph_extender.h>
 
+
 #include <lemon/invalid.h>
 #include <lemon/utility.h>
 
@@ -191,10 +189,7 @@
 
   };
 
-  typedef StaticMappableGraphExtender<
-    IterableGraphExtender<
-    AlterableGraphExtender<
-    GraphExtender<FullGraphBase> > > > ExtendedFullGraphBase;
+  typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase;
 
   /// \ingroup graphs
   ///
@@ -211,7 +206,21 @@
   class FullGraph : public ExtendedFullGraphBase {
   public:
 
+    typedef ExtendedFullGraphBase Parent;
+
+    /// \brief Constructor
+    ///
     FullGraph(int n) { construct(n); }
+
+    /// \brief Resize the graph
+    ///
+    void resize(int n) {
+      Parent::getNotifier(Edge()).clear();
+      Parent::getNotifier(Node()).clear();
+      construct(n);
+      Parent::getNotifier(Node()).build();
+      Parent::getNotifier(Edge()).build();
+    }
   };
 
 
@@ -379,10 +388,8 @@
 
   };
 
-  typedef StaticMappableUGraphExtender<
-    IterableUGraphExtender<
-    AlterableUGraphExtender<
-    UGraphExtender<FullUGraphBase> > > > ExtendedFullUGraphBase;
+  typedef UGraphExtender<UGraphBaseExtender<FullUGraphBase> > 
+  ExtendedFullUGraphBase;
 
   /// \ingroup graphs
   ///
@@ -401,7 +408,23 @@
   /// \author Balazs Dezso
   class FullUGraph : public ExtendedFullUGraphBase {
   public:
+
+    typedef ExtendedFullUGraphBase Parent;
+
+    /// \brief Constructor
     FullUGraph(int n) { construct(n); }
+
+    /// \brief Resize the graph
+    ///
+    void resize(int n) {
+      Parent::getNotifier(Edge()).clear();
+      Parent::getNotifier(UEdge()).clear();
+      Parent::getNotifier(Node()).clear();
+      construct(n);
+      Parent::getNotifier(Node()).build();
+      Parent::getNotifier(UEdge()).build();
+      Parent::getNotifier(Edge()).build();
+    }
   };
 
 
@@ -577,12 +600,8 @@
   };
 
 
-  typedef StaticMappableBpUGraphExtender<
-    IterableBpUGraphExtender<
-    AlterableBpUGraphExtender<
-    BpUGraphExtender <
-    FullBpUGraphBase> > > >
-  ExtendedFullBpUGraphBase;
+  typedef BpUGraphExtender< BpUGraphBaseExtender<
+    FullBpUGraphBase> > ExtendedFullBpUGraphBase;
 
 
   /// \ingroup graphs
@@ -599,10 +618,23 @@
   class FullBpUGraph : 
     public ExtendedFullBpUGraphBase {
   public:
+
     typedef ExtendedFullBpUGraphBase Parent;
+
     FullBpUGraph(int aNodeNum, int bNodeNum) {
       Parent::construct(aNodeNum, bNodeNum);
     }
+    /// \brief Resize the graph
+    ///
+    void resize(int n, int m) {
+      Parent::getNotifier(Edge()).clear();
+      Parent::getNotifier(UEdge()).clear();
+      Parent::getNotifier(Node()).clear();
+      construct(n, m);
+      Parent::getNotifier(Node()).build();
+      Parent::getNotifier(UEdge()).build();
+      Parent::getNotifier(Edge()).build();
+    }
   };
 
 } //namespace lemon
diff -r ef2d00e46897 -r c2992fd74dad lemon/graph_adaptor.h
--- a/lemon/graph_adaptor.h	Wed Feb 22 12:45:59 2006 +0000
+++ b/lemon/graph_adaptor.h	Wed Feb 22 18:26:56 2006 +0000
@@ -29,13 +29,10 @@
 
 #include <lemon/invalid.h>
 #include <lemon/maps.h>
-#include <lemon/bits/erasable_graph_extender.h>
-#include <lemon/bits/clearable_graph_extender.h>
-#include <lemon/bits/extendable_graph_extender.h>
-#include <lemon/bits/iterable_graph_extender.h>
-#include <lemon/bits/alteration_notifier.h>
-#include <lemon/bits/default_map.h>
+
+#include <lemon/bits/graph_adaptor_extender.h>
 #include <lemon/bits/graph_extender.h>
+
 #include <iostream>
 
 namespace lemon {
@@ -117,10 +114,6 @@
     int id(const Node& v) const { return graph->id(v); }
     int id(const Edge& e) const { return graph->id(e); }
     
-    Edge oppositeNode(const Edge& e) const { 
-      return Edge(graph->opposite(e)); 
-    }
-
     template <typename _Value>
     class NodeMap : public _Graph::template NodeMap<_Value> {
     public:
@@ -145,10 +138,10 @@
 
   template <typename _Graph>
   class GraphAdaptor :
-    public IterableGraphExtender<GraphAdaptorBase<_Graph> > { 
+    public GraphAdaptorExtender<GraphAdaptorBase<_Graph> > { 
   public:
     typedef _Graph Graph;
-    typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;
+    typedef GraphAdaptorExtender<GraphAdaptorBase<_Graph> > Parent;
   protected:
     GraphAdaptor() : Parent() { }
 
@@ -198,10 +191,10 @@
 
   template<typename _Graph>
   class RevGraphAdaptor : 
-    public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {
+    public GraphAdaptorExtender<RevGraphAdaptorBase<_Graph> > {
   public:
     typedef _Graph Graph;
-    typedef IterableGraphExtender<
+    typedef GraphAdaptorExtender<
       RevGraphAdaptorBase<_Graph> > Parent;
   protected:
     RevGraphAdaptor() { }
@@ -322,6 +315,7 @@
     ///
     bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
 
+    typedef False FindEdgeTag;
     typedef False NodeNumTag;
     typedef False EdgeNumTag;
   };
@@ -428,6 +422,7 @@
     ///
     bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
 
+    typedef False FindEdgeTag;
     typedef False NodeNumTag;
     typedef False EdgeNumTag;
   };
@@ -496,11 +491,11 @@
   template<typename _Graph, typename NodeFilterMap, 
 	   typename EdgeFilterMap, bool checked = true>
   class SubGraphAdaptor : 
-    public IterableGraphExtender<
+    public GraphAdaptorExtender<
     SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
   public:
     typedef _Graph Graph;
-    typedef IterableGraphExtender<
+    typedef GraphAdaptorExtender<
       SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
   protected:
     SubGraphAdaptor() { }
@@ -703,13 +698,13 @@
   };
 
   template <typename _Graph>
-  class UGraphAdaptorBase : 
-    public UGraphExtender<GraphAdaptorBase<_Graph> > {
+  class UndirectGraphAdaptorBase : 
+    public UGraphBaseExtender<GraphAdaptorBase<_Graph> > {
   public:
     typedef _Graph Graph;
-    typedef UGraphExtender<GraphAdaptorBase<_Graph> > Parent;
+    typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;
   protected:
-    UGraphAdaptorBase() : Parent() { }
+    UndirectGraphAdaptorBase() : Parent() { }
   public:
     typedef typename Parent::UEdge UEdge;
     typedef typename Parent::Edge Edge;
@@ -717,17 +712,17 @@
     template <typename T>
     class EdgeMap {
     protected:
-      const UGraphAdaptorBase<_Graph>* g;
+      const UndirectGraphAdaptorBase<_Graph>* g;
       template <typename TT> friend class EdgeMap;
       typename _Graph::template EdgeMap<T> forward_map, backward_map; 
     public:
       typedef T Value;
       typedef Edge Key;
       
-      EdgeMap(const UGraphAdaptorBase<_Graph>& _g) : g(&_g), 
+      EdgeMap(const UndirectGraphAdaptorBase<_Graph>& _g) : g(&_g), 
 	forward_map(*(g->graph)), backward_map(*(g->graph)) { }
 
-      EdgeMap(const UGraphAdaptorBase<_Graph>& _g, T a) : g(&_g), 
+      EdgeMap(const UndirectGraphAdaptorBase<_Graph>& _g, T a) : g(&_g), 
 	forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
       
       void set(Edge e, T a) { 
@@ -753,10 +748,10 @@
       typedef T Value;
       typedef UEdge Key;
       
-      UEdgeMap(const UGraphAdaptorBase<_Graph>& g) : 
+      UEdgeMap(const UndirectGraphAdaptorBase<_Graph>& g) : 
 	map(*(g.graph)) { }
 
-      UEdgeMap(const UGraphAdaptorBase<_Graph>& g, T a) : 
+      UEdgeMap(const UndirectGraphAdaptorBase<_Graph>& g, T a) : 
 	map(*(g.graph), a) { }
       
       void set(UEdge e, T a) { 
@@ -778,17 +773,17 @@
   /// 
   /// \author Marton Makai
   template<typename _Graph>
-  class UGraphAdaptor : 
-    public IterableUGraphExtender<
-    UGraphAdaptorBase<_Graph> > {
+  class UndirectGraphAdaptor : 
+    public UGraphAdaptorExtender<
+    UndirectGraphAdaptorBase<_Graph> > {
   public:
     typedef _Graph Graph;
-    typedef IterableUGraphExtender<
-      UGraphAdaptorBase<_Graph> > Parent;
+    typedef UGraphAdaptorExtender<
+      UndirectGraphAdaptorBase<_Graph> > Parent;
   protected:
-    UGraphAdaptor() { }
+    UndirectGraphAdaptor() { }
   public:
-    UGraphAdaptor(_Graph& _graph) { 
+    UndirectGraphAdaptor(_Graph& _graph) { 
       setGraph(_graph);
     }
   };
@@ -1083,11 +1078,11 @@
   template<typename _Graph, 
 	   typename ForwardFilterMap, typename BackwardFilterMap>
   class SubBidirGraphAdaptor : 
-    public IterableGraphExtender<
+    public GraphAdaptorExtender<
     SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
   public:
     typedef _Graph Graph;
-    typedef IterableGraphExtender<
+    typedef GraphAdaptorExtender<
       SubBidirGraphAdaptorBase<
       _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
   protected:
@@ -1341,11 +1336,11 @@
   ///
   template <typename _Graph, typename FirstOutEdgesMap>
   class ErasingFirstGraphAdaptor : 
-    public IterableGraphExtender<
+    public GraphAdaptorExtender<
     ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
   public:
     typedef _Graph Graph;
-    typedef IterableGraphExtender<
+    typedef GraphAdaptorExtender<
       ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
     ErasingFirstGraphAdaptor(Graph& _graph, 
 			     FirstOutEdgesMap& _first_out_edges) { 
@@ -1711,9 +1706,9 @@
 
   template <typename _Graph>
   class SplitGraphAdaptor 
-    : public IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > {
+    : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
   public:
-    typedef IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > Parent;
+    typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
 
     SplitGraphAdaptor(_Graph& graph) {
       Parent::setGraph(graph);
diff -r ef2d00e46897 -r c2992fd74dad lemon/grid_graph.h
--- a/lemon/grid_graph.h	Wed Feb 22 12:45:59 2006 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,522 +0,0 @@
-/* -*- C++ -*-
- *
- * This file is a part of LEMON, a generic C++ optimization library
- *
- * Copyright (C) 2003-2006
- * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
- * (Egervary Research Group on Combinatorial Optimization, EGRES).
- *
- * Permission to use, modify and distribute this software is granted
- * provided that this copyright notice appears in all copies. For
- * precise terms see the accompanying LICENSE file.
- *
- * This software is provided "AS IS" with no warranty of any kind,
- * express or implied, and with no claim as to its suitability for any
- * purpose.
- *
- */
-
-#ifndef GRID_GRAPH_H
-#define GRID_GRAPH_H
-
-#include <iostream>
-#include <lemon/invalid.h>
-#include <lemon/utility.h>
-
-#include <lemon/bits/iterable_graph_extender.h>
-#include <lemon/bits/alteration_notifier.h>
-#include <lemon/bits/static_map.h>
-#include <lemon/bits/graph_extender.h>
-
-#include <lemon/xy.h>
-
-///\ingroup graphs
-///\file
-///\brief GridGraph class.
-
-namespace lemon {
-
-  /// \brief Base graph for GridGraph.
-  ///
-  /// Base graph for grid graph. It describes some member functions
-  /// which can be used in the GridGraph.
-  ///
-  /// \warning Always use the GridGraph instead of this.
-  /// \see GridGraph
-  class GridGraphBase {
-
-  public:
-
-    typedef GridGraphBase Graph;
-
-    class Node;
-    class Edge;
-
-  public:
-
-    GridGraphBase() {}
-
-  protected:
-
-    /// \brief Creates a grid graph with the given size.
-    ///
-    /// Creates a grid graph with the given size.
-    void construct(int width, int height) {
-      _height = height; _width = width;
-      _nodeNum = height * width; _edgeNum = 2 * _nodeNum - width - height;
-      _edgeLimit = _nodeNum - width;
-    }
-
-    /// \brief Gives back the edge goes down from the node.
-    ///
-    /// Gives back the edge goes down from the node. If there is not
-    /// outgoing edge then it gives back INVALID.
-    Edge _down(Node n) const {
-      if (n.id < _nodeNum - _width) {
-	return Edge(n.id);
-      } else {
-	return INVALID;
-      }
-    }
-
-    /// \brief Gives back the edge comes from up into the node.
-    ///
-    /// Gives back the edge comes from up into the node. If there is not
-    /// incoming edge then it gives back INVALID.
-    Edge _up(Node n) const {
-      if (n.id >= _width) {
-	return Edge(n.id - _width);
-      } else {
-	return INVALID;
-      }
-    }
-
-    /// \brief Gives back the edge goes right from the node.
-    ///
-    /// Gives back the edge goes right from the node. If there is not
-    /// outgoing edge then it gives back INVALID.
-    Edge _right(Node n) const {
-      if (n.id % _width < _width - 1) {
-	return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1);
-      } else {
-	return INVALID;
-      }
-    }
-
-    /// \brief Gives back the edge comes from left into the node.
-    ///
-    /// Gives back the edge comes left up into the node. If there is not
-    /// incoming edge then it gives back INVALID.
-    Edge _left(Node n) const {
-      if (n.id % _width > 0) {
-	return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1;
-      } else {
-	return INVALID;
-      }
-    }
-
-
-  public:
-    
-    /// \brief The node on the given position.
-    /// 
-    /// Gives back the node on the given position.
-    Node operator()(int i, int j) const {
-      return Node(i + j * _width);
-    }
-
-    /// \brief Gives back the row index of the node.
-    ///
-    /// Gives back the row index of the node.
-    int row(Node n) const {
-      return n.id / _width;
-    }
-    
-    /// \brief Gives back the coloumn index of the node.
-    ///
-    /// Gives back the coloumn index of the node.
-    int col(Node n) const {
-      return n.id % _width;    
-    }
-
-    /// \brief Gives back the width of the graph.
-    ///
-    /// Gives back the width of the graph.
-    int width() const {
-      return _width;
-    }
-
-    /// \brief Gives back the height of the graph.
-    ///
-    /// Gives back the height of the graph.
-    int height() const {
-      return _height;
-    }
-
-    typedef True NodeNumTag;
-    typedef True EdgeNumTag;
-
-    ///Number of nodes.
-    int nodeNum() const { return _nodeNum; }
-    ///Number of edges.
-    int edgeNum() const { return _edgeNum; }
-
-    /// Maximum node ID.
-    
-    /// Maximum node ID.
-    ///\sa id(Node)
-    int maxNodeId() const { return nodeNum() - 1; }
-    /// Maximum edge ID.
-    
-    /// Maximum edge ID.
-    ///\sa id(Edge)
-    int maxEdgeId() const { return edgeNum() - 1; }
-
-    /// \brief Gives back the source node of an edge.
-    ///    
-    /// Gives back the source node of an edge.
-    Node source(Edge e) const {
-      if (e.id < _edgeLimit) {
-	return e.id;
-      } else {
-	return (e.id - _edgeLimit) % (_width - 1) +
-	  (e.id - _edgeLimit) / (_width - 1) * _width;
-      }
-    }
-
-    /// \brief Gives back the target node of an edge.
-    ///    
-    /// Gives back the target node of an edge.
-    Node target(Edge e) const {
-      if (e.id < _edgeLimit) {
-	return e.id + _width;
-      } else {
-	return (e.id - _edgeLimit) % (_width - 1) +
-	  (e.id - _edgeLimit) / (_width - 1) * _width + 1;
-      }
-    }
-
-    /// Node ID.
-    
-    /// The ID of a valid Node is a nonnegative integer not greater than
-    /// \ref maxNodeId(). The range of the ID's is not surely continuous
-    /// and the greatest node ID can be actually less then \ref maxNodeId().
-    ///
-    /// The ID of the \ref INVALID node is -1.
-    ///\return The ID of the node \c v. 
-
-    static int id(Node v) { return v.id; }
-    /// Edge ID.
-    
-    /// The ID of a valid Edge is a nonnegative integer not greater than
-    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
-    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
-    ///
-    /// The ID of the \ref INVALID edge is -1.
-    ///\return The ID of the edge \c e. 
-    static int id(Edge e) { return e.id; }
-
-    static Node nodeFromId(int id) { return Node(id);}
-    
-    static Edge edgeFromId(int id) { return Edge(id);}
-
-    typedef True FindEdgeTag;
-
-    /// Finds an edge between two nodes.
-    
-    /// Finds an edge from node \c u to node \c v.
-    ///
-    /// If \c prev is \ref INVALID (this is the default value), then
-    /// It finds the first edge from \c u to \c v. Otherwise it looks for
-    /// the next edge from \c u to \c v after \c prev.
-    /// \return The found edge or INVALID if there is no such an edge.
-    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
-      if (prev != INVALID) return INVALID;
-      if (v.id - u.id == _width) return Edge(u.id);
-      if (v.id - u.id == 1 && u.id % _width < _width - 1) {
-	return Edge(u.id / _width * (_width - 1) +
-		    u.id % _width + _edgeLimit);
-      }
-      return INVALID;
-    }
-    
-      
-    class Node {
-      friend class GridGraphBase;
-
-    protected:
-      int id;
-      Node(int _id) { id = _id;}
-    public:
-      Node() {}
-      Node (Invalid) { id = -1; }
-      bool operator==(const Node node) const {return id == node.id;}
-      bool operator!=(const Node node) const {return id != node.id;}
-      bool operator<(const Node node) const {return id < node.id;}
-    };
-    
-
-
-    class Edge {
-      friend class GridGraphBase;
-      
-    protected:
-      int id; 
-
-      Edge(int _id) : id(_id) {}
-
-    public:
-      Edge() { }
-      Edge (Invalid) { id = -1; }
-      bool operator==(const Edge edge) const {return id == edge.id;}
-      bool operator!=(const Edge edge) const {return id != edge.id;}
-      bool operator<(const Edge edge) const {return id < edge.id;}
-    };
-
-    void first(Node& node) const {
-      node.id = nodeNum() - 1;
-    }
-
-    static void next(Node& node) {
-      --node.id;
-    }
-
-    void first(Edge& edge) const {
-      edge.id = edgeNum() - 1;
-    }
-
-    static void next(Edge& edge) {
-      --edge.id;
-    }
-
-    void firstOut(Edge& edge, const Node& node) const {
-      if (node.id < _nodeNum - _width) {
-	edge.id = node.id;
-      } else if (node.id % _width < _width - 1) {
-	edge.id = _edgeLimit + node.id % _width +
-	  (node.id / _width) * (_width - 1);
-      } else {
-	edge.id = -1;
-      }
-    }
-
-    void nextOut(Edge& edge) const {
-      if (edge.id >= _edgeLimit) {
-	edge.id = -1;
-      } else if (edge.id % _width < _width - 1) {
-	edge.id = _edgeLimit + edge.id % _width +
-	  (edge.id / _width) * (_width - 1);
-      } else {
-	edge.id = -1;
-      }
-    }
-
-    void firstIn(Edge& edge, const Node& node) const {
-      if (node.id >= _width) {
-	edge.id = node.id - _width;
-      } else if (node.id % _width > 0) {
-	edge.id = _edgeLimit + node.id % _width +
-	  (node.id / _width) * (_width - 1) - 1;
-      } else {
-	edge.id = -1;
-      }
-    }
-    
-    void nextIn(Edge& edge) const {
-      if (edge.id >= _edgeLimit) {
-	edge.id = -1;
-      } else if (edge.id % _width > 0) {
-	edge.id = _edgeLimit + edge.id % _width +
-	  (edge.id / _width + 1) * (_width - 1) - 1;
-      } else {
-	edge.id = -1;
-      }
-    }
-
-  private:
-    int _width, _height;
-    int _nodeNum, _edgeNum;
-    int _edgeLimit;
-  };
-
-
-  typedef StaticMappableUGraphExtender<
-    IterableUGraphExtender<
-    AlterableUGraphExtender<
-    UGraphExtender<GridGraphBase> > > > ExtendedGridGraphBase;
-
-  /// \ingroup graphs
-  ///
-  /// \brief Grid graph class
-  ///
-  /// This class implements a special graph type. The nodes of the
-  /// graph can be indiced by two integer \c (i,j) value where \c i
-  /// is in the \c [0,width) range and j is in the [0, height) range.
-  /// Two nodes are connected in the graph if the indices differ only
-  /// on one position and only one is the difference. 
-  ///
-  /// The graph can be indiced in the following way:
-  ///\code
-  /// GridGraph graph(w, h);
-  /// GridGraph::NodeMap<int> val(graph); 
-  /// for (int i = 0; i < graph.width(); ++i) {
-  ///   for (int j = 0; j < graph.height(); ++j) {
-  ///     val[graph(i, j)] = i + j;
-  ///   }
-  /// }
-  ///\endcode
-  ///
-  /// The graph type is fully conform to the \ref concept::UGraph
-  /// "Undirected Graph" concept.
-  ///
-  /// \author Balazs Dezso
-  /// \see GridGraphBase
-  class GridGraph : public ExtendedGridGraphBase {
-  public:
-
-    /// \brief Map to get the indices of the nodes as xy<int>.
-    ///
-    /// Map to get the indices of the nodes as xy<int>.
-    class IndexMap {
-    public:
-      typedef True NeedCopy;
-      /// \brief The key type of the map
-      typedef GridGraph::Node Key;
-      /// \brief The value type of the map
-      typedef xy<int> Value;
-
-      /// \brief Constructor
-      ///
-      /// Constructor
-      IndexMap(const GridGraph& _graph) : graph(_graph) {}
-
-      /// \brief The subscript operator
-      ///
-      /// The subscript operator.
-      Value operator[](Key key) const {
-	return xy<int>(graph.row(key), graph.col(key));
-      }
-
-    private:
-      const GridGraph& graph;
-    };
-
-    /// \brief Map to get the row of the nodes.
-    ///
-    /// Map to get the row of the nodes.
-    class RowMap {
-    public:
-      typedef True NeedCopy;
-      /// \brief The key type of the map
-      typedef GridGraph::Node Key;
-      /// \brief The value type of the map
-      typedef int Value;
-
-      /// \brief Constructor
-      ///
-      /// Constructor
-      RowMap(const GridGraph& _graph) : graph(_graph) {}
-
-      /// \brief The subscript operator
-      ///
-      /// The subscript operator.
-      Value operator[](Key key) const {
-	return graph.row(key);
-      }
-
-    private:
-      const GridGraph& graph;
-    };
-
-    /// \brief Map to get the column of the nodes.
-    ///
-    /// Map to get the column of the nodes.
-    class ColMap {
-    public:
-      typedef True NeedCopy;
-      /// \brief The key type of the map
-      typedef GridGraph::Node Key;
-      /// \brief The value type of the map
-      typedef int Value;
-
-      /// \brief Constructor
-      ///
-      /// Constructor
-      ColMap(const GridGraph& _graph) : graph(_graph) {}
-
-      /// \brief The subscript operator
-      ///
-      /// The subscript operator.
-      Value operator[](Key key) const {
-	return graph.col(key);
-      }
-
-    private:
-      const GridGraph& graph;
-    };
-
-    /// \brief Constructor
-    ///
-    /// 
-    GridGraph(int n, int m) { construct(n, m); }
-    
-    /// \brief Gives back the edge goes down from the node.
-    ///
-    /// Gives back the edge goes down from the node. If there is not
-    /// outgoing edge then it gives back INVALID.
-    Edge down(Node n) const {
-      UEdge ue = _down(n);
-      return ue != INVALID ? direct(ue, true) : INVALID;
-    }
-    
-    /// \brief Gives back the edge goes up from the node.
-    ///
-    /// Gives back the edge goes up from the node. If there is not
-    /// outgoing edge then it gives back INVALID.
-    Edge up(Node n) const {
-      UEdge ue = _up(n);
-      return ue != INVALID ? direct(ue, false) : INVALID;
-    }
-
-    /// \brief Gives back the edge goes right from the node.
-    ///
-    /// Gives back the edge goes right from the node. If there is not
-    /// outgoing edge then it gives back INVALID.
-    Edge right(Node n) const {
-      UEdge ue = _right(n);
-      return ue != INVALID ? direct(ue, true) : INVALID;
-    }
-
-    /// \brief Gives back the edge goes left from the node.
-    ///
-    /// Gives back the edge goes left from the node. If there is not
-    /// outgoing edge then it gives back INVALID.
-    Edge left(Node n) const {
-      UEdge ue = _left(n);
-      return ue != INVALID ? direct(ue, false) : INVALID;
-    }
-    
-  };
-
-  /// \brief Index map of the grid graph
-  ///
-  /// Just returns an IndexMap for the grid graph.
-  GridGraph::IndexMap indexMap(const GridGraph& graph) {
-    return GridGraph::IndexMap(graph);
-  }
-
-  /// \brief Row map of the grid graph
-  ///
-  /// Just returns a RowMap for the grid graph.
-  GridGraph::RowMap rowMap(const GridGraph& graph) {
-    return GridGraph::RowMap(graph);
-  }
-
-  /// \brief Column map of the grid graph
-  ///
-  /// Just returns a ColMap for the grid graph.
-  GridGraph::ColMap colMap(const GridGraph& graph) {
-    return GridGraph::ColMap(graph);
-  }
-}
-#endif
diff -r ef2d00e46897 -r c2992fd74dad lemon/grid_ugraph.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/grid_ugraph.h	Wed Feb 22 18:26:56 2006 +0000
@@ -0,0 +1,536 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2006
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef GRID_UGRAPH_H
+#define GRID_UGRAPH_H
+
+#include <iostream>
+#include <lemon/invalid.h>
+#include <lemon/utility.h>
+
+#include <lemon/bits/graph_extender.h>
+
+#include <lemon/xy.h>
+
+///\ingroup graphs
+///\file
+///\brief GridUGraph class.
+
+namespace lemon {
+
+  /// \brief Base graph for GridUGraph.
+  ///
+  /// Base graph for grid graph. It describes some member functions
+  /// which can be used in the GridUGraph.
+  ///
+  /// \warning Always use the GridUGraph instead of this.
+  /// \see GridUGraph
+  class GridUGraphBase {
+
+  public:
+
+    typedef GridUGraphBase UGraph;
+
+    class Node;
+    class Edge;
+
+  public:
+
+    GridUGraphBase() {}
+
+  protected:
+
+    /// \brief Creates a grid graph with the given size.
+    ///
+    /// Creates a grid graph with the given size.
+    void construct(int width, int height) {
+      _height = height; _width = width;
+      _nodeNum = height * width; _edgeNum = 2 * _nodeNum - width - height;
+      _edgeLimit = _nodeNum - width;
+    }
+
+    /// \brief Gives back the edge goes down from the node.
+    ///
+    /// Gives back the edge goes down from the node. If there is not
+    /// outgoing edge then it gives back INVALID.
+    Edge _down(Node n) const {
+      if (n.id < _nodeNum - _width) {
+	return Edge(n.id);
+      } else {
+	return INVALID;
+      }
+    }
+
+    /// \brief Gives back the edge comes from up into the node.
+    ///
+    /// Gives back the edge comes from up into the node. If there is not
+    /// incoming edge then it gives back INVALID.
+    Edge _up(Node n) const {
+      if (n.id >= _width) {
+	return Edge(n.id - _width);
+      } else {
+	return INVALID;
+      }
+    }
+
+    /// \brief Gives back the edge goes right from the node.
+    ///
+    /// Gives back the edge goes right from the node. If there is not
+    /// outgoing edge then it gives back INVALID.
+    Edge _right(Node n) const {
+      if (n.id % _width < _width - 1) {
+	return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1);
+      } else {
+	return INVALID;
+      }
+    }
+
+    /// \brief Gives back the edge comes from left into the node.
+    ///
+    /// Gives back the edge comes left up into the node. If there is not
+    /// incoming edge then it gives back INVALID.
+    Edge _left(Node n) const {
+      if (n.id % _width > 0) {
+	return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1;
+      } else {
+	return INVALID;
+      }
+    }
+
+  public:
+
+    class IndexError : public RuntimeError {
+    public:
+      virtual const char* exceptionName() const {
+        return "lemon::GridUGraph::IndexError";
+      }  
+    };
+
+    
+    /// \brief The node on the given position.
+    /// 
+    /// Gives back the node on the given position.
+    Node operator()(int i, int j) const {
+      LEMON_ASSERT(0 <= i && i < width() && 0 <= j  && j < height(), IndexError());
+      return Node(i + j * _width);
+    }
+
+    /// \brief Gives back the row index of the node.
+    ///
+    /// Gives back the row index of the node.
+    int row(Node n) const {
+      return n.id / _width;
+    }
+    
+    /// \brief Gives back the coloumn index of the node.
+    ///
+    /// Gives back the coloumn index of the node.
+    int col(Node n) const {
+      return n.id % _width;    
+    }
+
+    /// \brief Gives back the width of the graph.
+    ///
+    /// Gives back the width of the graph.
+    int width() const {
+      return _width;
+    }
+
+    /// \brief Gives back the height of the graph.
+    ///
+    /// Gives back the height of the graph.
+    int height() const {
+      return _height;
+    }
+
+    typedef True NodeNumTag;
+    typedef True EdgeNumTag;
+
+    ///Number of nodes.
+    int nodeNum() const { return _nodeNum; }
+    ///Number of edges.
+    int edgeNum() const { return _edgeNum; }
+
+    /// Maximum node ID.
+    
+    /// Maximum node ID.
+    ///\sa id(Node)
+    int maxNodeId() const { return nodeNum() - 1; }
+    /// Maximum edge ID.
+    
+    /// Maximum edge ID.
+    ///\sa id(Edge)
+    int maxEdgeId() const { return edgeNum() - 1; }
+
+    /// \brief Gives back the source node of an edge.
+    ///    
+    /// Gives back the source node of an edge.
+    Node source(Edge e) const {
+      if (e.id < _edgeLimit) {
+	return e.id;
+      } else {
+	return (e.id - _edgeLimit) % (_width - 1) +
+	  (e.id - _edgeLimit) / (_width - 1) * _width;
+      }
+    }
+
+    /// \brief Gives back the target node of an edge.
+    ///    
+    /// Gives back the target node of an edge.
+    Node target(Edge e) const {
+      if (e.id < _edgeLimit) {
+	return e.id + _width;
+      } else {
+	return (e.id - _edgeLimit) % (_width - 1) +
+	  (e.id - _edgeLimit) / (_width - 1) * _width + 1;
+      }
+    }
+
+    /// Node ID.
+    
+    /// The ID of a valid Node is a nonnegative integer not greater than
+    /// \ref maxNodeId(). The range of the ID's is not surely continuous
+    /// and the greatest node ID can be actually less then \ref maxNodeId().
+    ///
+    /// The ID of the \ref INVALID node is -1.
+    ///\return The ID of the node \c v. 
+
+    static int id(Node v) { return v.id; }
+    /// Edge ID.
+    
+    /// The ID of a valid Edge is a nonnegative integer not greater than
+    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
+    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
+    ///
+    /// The ID of the \ref INVALID edge is -1.
+    ///\return The ID of the edge \c e. 
+    static int id(Edge e) { return e.id; }
+
+    static Node nodeFromId(int id) { return Node(id);}
+    
+    static Edge edgeFromId(int id) { return Edge(id);}
+
+    typedef True FindEdgeTag;
+
+    /// Finds an edge between two nodes.
+    
+    /// Finds an edge from node \c u to node \c v.
+    ///
+    /// If \c prev is \ref INVALID (this is the default value), then
+    /// It finds the first edge from \c u to \c v. Otherwise it looks for
+    /// the next edge from \c u to \c v after \c prev.
+    /// \return The found edge or INVALID if there is no such an edge.
+    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
+      if (prev != INVALID) return INVALID;
+      if (v.id - u.id == _width) return Edge(u.id);
+      if (v.id - u.id == 1 && u.id % _width < _width - 1) {
+	return Edge(u.id / _width * (_width - 1) +
+		    u.id % _width + _edgeLimit);
+      }
+      return INVALID;
+    }
+    
+      
+    class Node {
+      friend class GridUGraphBase;
+
+    protected:
+      int id;
+      Node(int _id) { id = _id;}
+    public:
+      Node() {}
+      Node (Invalid) { id = -1; }
+      bool operator==(const Node node) const {return id == node.id;}
+      bool operator!=(const Node node) const {return id != node.id;}
+      bool operator<(const Node node) const {return id < node.id;}
+    };
+    
+
+
+    class Edge {
+      friend class GridUGraphBase;
+      
+    protected:
+      int id; 
+
+      Edge(int _id) : id(_id) {}
+
+    public:
+      Edge() { }
+      Edge (Invalid) { id = -1; }
+      bool operator==(const Edge edge) const {return id == edge.id;}
+      bool operator!=(const Edge edge) const {return id != edge.id;}
+      bool operator<(const Edge edge) const {return id < edge.id;}
+    };
+
+    void first(Node& node) const {
+      node.id = nodeNum() - 1;
+    }
+
+    static void next(Node& node) {
+      --node.id;
+    }
+
+    void first(Edge& edge) const {
+      edge.id = edgeNum() - 1;
+    }
+
+    static void next(Edge& edge) {
+      --edge.id;
+    }
+
+    void firstOut(Edge& edge, const Node& node) const {
+      if (node.id < _nodeNum - _width) {
+	edge.id = node.id;
+      } else if (node.id % _width < _width - 1) {
+	edge.id = _edgeLimit + node.id % _width +
+	  (node.id / _width) * (_width - 1);
+      } else {
+	edge.id = -1;
+      }
+    }
+
+    void nextOut(Edge& edge) const {
+      if (edge.id >= _edgeLimit) {
+	edge.id = -1;
+      } else if (edge.id % _width < _width - 1) {
+	edge.id = _edgeLimit + edge.id % _width +
+	  (edge.id / _width) * (_width - 1);
+      } else {
+	edge.id = -1;
+      }
+    }
+
+    void firstIn(Edge& edge, const Node& node) const {
+      if (node.id >= _width) {
+	edge.id = node.id - _width;
+      } else if (node.id % _width > 0) {
+	edge.id = _edgeLimit + node.id % _width +
+	  (node.id / _width) * (_width - 1) - 1;
+      } else {
+	edge.id = -1;
+      }
+    }
+    
+    void nextIn(Edge& edge) const {
+      if (edge.id >= _edgeLimit) {
+	edge.id = -1;
+      } else if (edge.id % _width > 0) {
+	edge.id = _edgeLimit + edge.id % _width +
+	  (edge.id / _width + 1) * (_width - 1) - 1;
+      } else {
+	edge.id = -1;
+      }
+    }
+
+  private:
+    int _width, _height;
+    int _nodeNum, _edgeNum;
+    int _edgeLimit;
+  };
+
+
+  typedef UGraphExtender<UGraphBaseExtender<
+    GridUGraphBase> > ExtendedGridUGraphBase;
+
+  /// \ingroup graphs
+  ///
+  /// \brief Grid graph class
+  ///
+  /// This class implements a special graph type. The nodes of the
+  /// graph can be indiced by two integer \c (i,j) value where \c i
+  /// is in the \c [0,width) range and j is in the [0, height) range.
+  /// Two nodes are connected in the graph if the indices differ only
+  /// on one position and only one is the difference. 
+  ///
+  /// The graph can be indiced in the following way:
+  ///\code
+  /// GridUGraph graph(w, h);
+  /// GridUGraph::NodeMap<int> val(graph); 
+  /// for (int i = 0; i < graph.width(); ++i) {
+  ///   for (int j = 0; j < graph.height(); ++j) {
+  ///     val[graph(i, j)] = i + j;
+  ///   }
+  /// }
+  ///\endcode
+  ///
+  /// The graph type is fully conform to the \ref concept::UUGraph
+  /// "Undirected UGraph" concept.
+  ///
+  /// \author Balazs Dezso
+  /// \see GridUGraphBase
+  class GridUGraph : public ExtendedGridUGraphBase {
+  public:
+
+    typedef ExtendedGridUGraphBase Parent;
+
+    /// \brief Map to get the indices of the nodes as xy<int>.
+    ///
+    /// Map to get the indices of the nodes as xy<int>.
+    class IndexMap {
+    public:
+      /// \brief The key type of the map
+      typedef GridUGraph::Node Key;
+      /// \brief The value type of the map
+      typedef xy<int> Value;
+
+      /// \brief Constructor
+      ///
+      /// Constructor
+      IndexMap(const GridUGraph& _graph) : graph(_graph) {}
+
+      /// \brief The subscript operator
+      ///
+      /// The subscript operator.
+      Value operator[](Key key) const {
+	return xy<int>(graph.row(key), graph.col(key));
+      }
+
+    private:
+      const GridUGraph& graph;
+    };
+
+    /// \brief Map to get the row of the nodes.
+    ///
+    /// Map to get the row of the nodes.
+    class RowMap {
+    public:
+      /// \brief The key type of the map
+      typedef GridUGraph::Node Key;
+      /// \brief The value type of the map
+      typedef int Value;
+
+      /// \brief Constructor
+      ///
+      /// Constructor
+      RowMap(const GridUGraph& _graph) : graph(_graph) {}
+
+      /// \brief The subscript operator
+      ///
+      /// The subscript operator.
+      Value operator[](Key key) const {
+	return graph.row(key);
+      }
+
+    private:
+      const GridUGraph& graph;
+    };
+
+    /// \brief Map to get the column of the nodes.
+    ///
+    /// Map to get the column of the nodes.
+    class ColMap {
+    public:
+      /// \brief The key type of the map
+      typedef GridUGraph::Node Key;
+      /// \brief The value type of the map
+      typedef int Value;
+
+      /// \brief Constructor
+      ///
+      /// Constructor
+      ColMap(const GridUGraph& _graph) : graph(_graph) {}
+
+      /// \brief The subscript operator
+      ///
+      /// The subscript operator.
+      Value operator[](Key key) const {
+	return graph.col(key);
+      }
+
+    private:
+      const GridUGraph& graph;
+    };
+
+    /// \brief Constructor
+    ///
+    /// 
+    GridUGraph(int n, int m) { construct(n, m); }
+
+    /// \brief Resize the graph
+    ///
+    void resize(int n, int m) {
+      Parent::getNotifier(Edge()).clear();
+      Parent::getNotifier(UEdge()).clear();
+      Parent::getNotifier(Node()).clear();
+      construct(n, m);
+      Parent::getNotifier(Node()).build();
+      Parent::getNotifier(UEdge()).build();
+      Parent::getNotifier(Edge()).build();
+    }
+    
+    /// \brief Gives back the edge goes down from the node.
+    ///
+    /// Gives back the edge goes down from the node. If there is not
+    /// outgoing edge then it gives back INVALID.
+    Edge down(Node n) const {
+      UEdge ue = _down(n);
+      return ue != INVALID ? direct(ue, true) : INVALID;
+    }
+    
+    /// \brief Gives back the edge goes up from the node.
+    ///
+    /// Gives back the edge goes up from the node. If there is not
+    /// outgoing edge then it gives back INVALID.
+    Edge up(Node n) const {
+      UEdge ue = _up(n);
+      return ue != INVALID ? direct(ue, false) : INVALID;
+    }
+
+    /// \brief Gives back the edge goes right from the node.
+    ///
+    /// Gives back the edge goes right from the node. If there is not
+    /// outgoing edge then it gives back INVALID.
+    Edge right(Node n) const {
+      UEdge ue = _right(n);
+      return ue != INVALID ? direct(ue, true) : INVALID;
+    }
+
+    /// \brief Gives back the edge goes left from the node.
+    ///
+    /// Gives back the edge goes left from the node. If there is not
+    /// outgoing edge then it gives back INVALID.
+    Edge left(Node n) const {
+      UEdge ue = _left(n);
+      return ue != INVALID ? direct(ue, false) : INVALID;
+    }
+    
+  };
+
+  /// \brief Index map of the grid graph
+  ///
+  /// Just returns an IndexMap for the grid graph.
+  GridUGraph::IndexMap indexMap(const GridUGraph& graph) {
+    return GridUGraph::IndexMap(graph);
+  }
+
+  /// \brief Row map of the grid graph
+  ///
+  /// Just returns a RowMap for the grid graph.
+  GridUGraph::RowMap rowMap(const GridUGraph& graph) {
+    return GridUGraph::RowMap(graph);
+  }
+
+  /// \brief Column map of the grid graph
+  ///
+  /// Just returns a ColMap for the grid graph.
+  GridUGraph::ColMap colMap(const GridUGraph& graph) {
+    return GridUGraph::ColMap(graph);
+  }
+}
+#endif
diff -r ef2d00e46897 -r c2992fd74dad lemon/hypercube_graph.h
--- a/lemon/hypercube_graph.h	Wed Feb 22 12:45:59 2006 +0000
+++ b/lemon/hypercube_graph.h	Wed Feb 22 18:26:56 2006 +0000
@@ -25,9 +25,6 @@
 #include <lemon/utility.h>
 #include <lemon/error.h>
 
-#include <lemon/bits/iterable_graph_extender.h>
-#include <lemon/bits/alteration_notifier.h>
-#include <lemon/bits/static_map.h>
 #include <lemon/bits/graph_extender.h>
 
 ///\ingroup graphs
@@ -236,11 +233,7 @@
   };
 
 
-  typedef StaticMappableGraphExtender<
-    IterableGraphExtender<
-    AlterableGraphExtender<
-    GraphExtender<
-    HyperCubeGraphBase> > > > ExtendedHyperCubeGraphBase;
+  typedef GraphExtender<HyperCubeGraphBase> ExtendedHyperCubeGraphBase;
 
   /// \ingroup graphs
   ///
diff -r ef2d00e46897 -r c2992fd74dad lemon/kruskal.h
--- a/lemon/kruskal.h	Wed Feb 22 12:45:59 2006 +0000
+++ b/lemon/kruskal.h	Wed Feb 22 18:26:56 2006 +0000
@@ -23,6 +23,7 @@
 #include <vector>
 #include <lemon/unionfind.h>
 #include <lemon/utility.h>
+#include <lemon/traits.h>
 
 /**
 @defgroup spantree Minimum Cost Spanning Tree Algorithms
@@ -228,7 +229,7 @@
     };
 
     template<class _GR>
-    typename enable_if<typename _GR::UTag,void>::type
+    typename enable_if<UndirectedTagIndicator<_GR>,void>::type
     fillWithEdges(const _GR& g, const Map& m,dummy<0> = 0) 
     {
       for(typename GR::UEdgeIt e(g);e!=INVALID;++e) 
@@ -236,7 +237,7 @@
     }
 
     template<class _GR>
-    typename disable_if<typename _GR::UTag,void>::type
+    typename disable_if<UndirectedTagIndicator<_GR>,void>::type
     fillWithEdges(const _GR& g, const Map& m,dummy<1> = 1) 
     {
       for(typename GR::EdgeIt e(g);e!=INVALID;++e) 
diff -r ef2d00e46897 -r c2992fd74dad lemon/list_graph.h
--- a/lemon/list_graph.h	Wed Feb 22 12:45:59 2006 +0000
+++ b/lemon/list_graph.h	Wed Feb 22 18:26:56 2006 +0000
@@ -23,16 +23,11 @@
 ///\file
 ///\brief ListGraph, ListUGraph classes.
 
-#include <lemon/bits/erasable_graph_extender.h>
-#include <lemon/bits/clearable_graph_extender.h>
-#include <lemon/bits/extendable_graph_extender.h>
-#include <lemon/bits/iterable_graph_extender.h>
-#include <lemon/bits/alteration_notifier.h>
-#include <lemon/bits/default_map.h>
 #include <lemon/bits/graph_extender.h>
 
 #include <lemon/error.h>
 
+#include <vector>
 #include <list>
 
 namespace lemon {
@@ -311,13 +306,7 @@
 
   };
 
-  typedef ErasableGraphExtender<
-    ClearableGraphExtender<
-    ExtendableGraphExtender<
-    MappableGraphExtender<
-    IterableGraphExtender<
-    AlterableGraphExtender<
-    GraphExtender<ListGraphBase> > > > > > > ExtendedListGraphBase;
+  typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
 
   /// \addtogroup graphs
   /// @{
@@ -578,13 +567,8 @@
 
   /**************** Undirected List Graph ****************/
 
-  typedef ErasableUGraphExtender<
-    ClearableUGraphExtender<
-    ExtendableUGraphExtender<
-    MappableUGraphExtender<
-    IterableUGraphExtender<
-    AlterableUGraphExtender<
-    UGraphExtender<ListGraphBase> > > > > > > ExtendedListUGraphBase;
+  typedef UGraphExtender<UGraphBaseExtender<
+    ListGraphBase> > ExtendedListUGraphBase;
 
   /// \addtogroup graphs
   /// @{
diff -r ef2d00e46897 -r c2992fd74dad lemon/prim.h
--- a/lemon/prim.h	Wed Feb 22 12:45:59 2006 +0000
+++ b/lemon/prim.h	Wed Feb 22 18:26:56 2006 +0000
@@ -788,7 +788,7 @@
       Create prm(graph,cost);
     prm.treeMap(tree);
     prm.run();
-  };
+  }
 
 } //END OF NAMESPACE LEMON
 
diff -r ef2d00e46897 -r c2992fd74dad lemon/radix_sort.h
--- a/lemon/radix_sort.h	Wed Feb 22 12:45:59 2006 +0000
+++ b/lemon/radix_sort.h	Wed Feb 22 18:26:56 2006 +0000
@@ -264,7 +264,7 @@
 		       int byte, Functor functor) {
     const int size = 
       (unsigned int)std::numeric_limits<unsigned char>::max() + 1;
-    int counter[size];
+    std::vector<int> counter(size);
     for (int i = 0; i < size; ++i) {
       counter[i] = 0;
     }
@@ -290,7 +290,7 @@
 			     int byte, Functor functor) {
     const int size = 
       (unsigned int)std::numeric_limits<unsigned char>::max() + 1;
-    int counter[size];
+    std::vector<int> counter(size);
     for (int i = 0; i < size; ++i) {
       counter[i] = 0;
     }
diff -r ef2d00e46897 -r c2992fd74dad lemon/smart_graph.h
--- a/lemon/smart_graph.h	Wed Feb 22 12:45:59 2006 +0000
+++ b/lemon/smart_graph.h	Wed Feb 22 18:26:56 2006 +0000
@@ -27,16 +27,13 @@
 
 #include <lemon/invalid.h>
 
-#include <lemon/bits/clearable_graph_extender.h>
-#include <lemon/bits/extendable_graph_extender.h>
-#include <lemon/bits/iterable_graph_extender.h>
-#include <lemon/bits/alteration_notifier.h>
-#include <lemon/bits/default_map.h>
 #include <lemon/bits/graph_extender.h>
 
 #include <lemon/utility.h>
 #include <lemon/error.h>
 
+#include <lemon/bits/graph_extender.h>
+
 namespace lemon {
 
   class SmartGraph;
@@ -222,12 +219,7 @@
 
   };
 
-  typedef ClearableGraphExtender<
-    ExtendableGraphExtender<
-    MappableGraphExtender<
-    IterableGraphExtender<
-    AlterableGraphExtender<
-    GraphExtender<SmartGraphBase> > > > > > ExtendedSmartGraphBase;
+  typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase;
 
   /// \ingroup graphs
 
@@ -244,7 +236,9 @@
   ///\author Alpar Juttner
   class SmartGraph : public ExtendedSmartGraphBase {
   public:
-    
+
+    typedef ExtendedSmartGraphBase Parent;
+
     class Snapshot;
     friend class Snapshot;
 
@@ -355,12 +349,8 @@
 
   /**************** Undirected List Graph ****************/
 
-  typedef ClearableUGraphExtender<
-    ExtendableUGraphExtender<
-    MappableUGraphExtender<
-    IterableUGraphExtender<
-    AlterableUGraphExtender<
-    UGraphExtender<SmartGraphBase> > > > > > ExtendedSmartUGraphBase;
+  typedef UGraphExtender<UGraphBaseExtender<SmartGraphBase> >
+  ExtendedSmartUGraphBase;
 
   /// \ingroup graphs
   ///
@@ -587,14 +577,8 @@
   };
 
 
-  typedef ClearableBpUGraphExtender<
-    ExtendableBpUGraphExtender<
-    MappableBpUGraphExtender<
-    IterableBpUGraphExtender<
-    AlterableBpUGraphExtender<
-    BpUGraphExtender <
-    SmartBpUGraphBase> > > > > >
-  ExtendedSmartBpUGraphBase;
+  typedef BpUGraphExtender< BpUGraphBaseExtender<
+    SmartBpUGraphBase> > ExtendedSmartBpUGraphBase;
 
   /// \ingroup graphs
   ///
diff -r ef2d00e46897 -r c2992fd74dad lemon/sub_graph.h
--- a/lemon/sub_graph.h	Wed Feb 22 12:45:59 2006 +0000
+++ b/lemon/sub_graph.h	Wed Feb 22 18:26:56 2006 +0000
@@ -386,9 +386,9 @@
   /// \see EdgeSubGraphBase
   template <typename Graph>
   class SubGraph 
-    : public IterableGraphExtender< SubGraphBase<Graph> > {
+    : public GraphAdaptorExtender< SubGraphBase<Graph> > {
   public:
-    typedef IterableGraphExtender< SubGraphBase<Graph> > Parent;
+    typedef GraphAdaptorExtender< SubGraphBase<Graph> > Parent;
   public:
     /// \brief Constructor for sub-graph.
     ///
@@ -683,9 +683,9 @@
   /// \see EdgeSubGraphBase
   template <typename Graph>
   class EdgeSubGraph 
-    : public IterableGraphExtender< EdgeSubGraphBase<Graph> > {
+    : public GraphAdaptorExtender< EdgeSubGraphBase<Graph> > {
   public:
-    typedef IterableGraphExtender< EdgeSubGraphBase<Graph> > Parent;
+    typedef GraphAdaptorExtender< EdgeSubGraphBase<Graph> > Parent;
   public:
     /// \brief Constructor for sub-graph.
     ///
diff -r ef2d00e46897 -r c2992fd74dad lemon/topology.h
--- a/lemon/topology.h	Wed Feb 22 12:45:59 2006 +0000
+++ b/lemon/topology.h	Wed Feb 22 18:26:56 2006 +0000
@@ -1417,7 +1417,7 @@
       if(bfs.dist(graph.source(i))==bfs.dist(graph.target(i)))return false;
     }
     return true;
-  };
+  }
   
   /// \ingroup topology
   ///
@@ -1459,7 +1459,7 @@
       if(bfs.dist(graph.source(i)) == bfs.dist(graph.target(i)))return false;
     }
     return true;
-  };
+  }
    
 } //namespace lemon
 
diff -r ef2d00e46897 -r c2992fd74dad lemon/traits.h
--- a/lemon/traits.h	Wed Feb 22 12:45:59 2006 +0000
+++ b/lemon/traits.h	Wed Feb 22 18:26:56 2006 +0000
@@ -209,6 +209,19 @@
     static const bool value = true;
   };
 
+  template <typename Graph, typename Enable = void>
+  struct UndirectedTagIndicator {
+    static const bool value = false;
+  };
+
+  template <typename Graph>
+  struct UndirectedTagIndicator<
+    Graph, 
+    typename enable_if<typename Graph::UndirectedTag, void>::type
+  > {
+    static const bool value = true;
+  };
+
 
 
 }
diff -r ef2d00e46897 -r c2992fd74dad lemon/ugraph_adaptor.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/ugraph_adaptor.h	Wed Feb 22 18:26:56 2006 +0000
@@ -0,0 +1,803 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2006
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_UGRAPH_ADAPTOR_H
+#define LEMON_UGRAPH_ADAPTOR_H
+
+///\ingroup graph_adaptors
+///\file
+///\brief Several graph adaptors.
+///
+///This file contains several useful ugraph adaptor functions.
+///
+///\author Balazs Dezso
+
+#include <lemon/invalid.h>
+#include <lemon/maps.h>
+
+#include <lemon/bits/graph_adaptor_extender.h>
+
+#include <lemon/traits.h>
+
+#include <iostream>
+
+namespace lemon {
+
+  /// \ingroup graph_adaptors
+  ///
+  /// \brief Base type for the Graph Adaptors
+  ///
+  /// \warning Graph adaptors are in even more experimental state than the 
+  /// other parts of the lib. Use them at you own risk.
+  ///
+  /// This is the base type for most of LEMON graph adaptors. 
+  /// This class implements a trivial graph adaptor i.e. it only wraps the 
+  /// functions and types of the graph. The purpose of this class is to 
+  /// make easier implementing graph adaptors. E.g. if an adaptor is 
+  /// considered which differs from the wrapped graph only in some of its 
+  /// functions or types, then it can be derived from GraphAdaptor, and only 
+  /// the differences should be implemented.
+  ///
+  /// \author Balazs Dezso 
+  template<typename _UGraph>
+  class UGraphAdaptorBase {
+  public:
+    typedef _UGraph Graph;
+    typedef Graph ParentGraph;
+
+  protected:
+    Graph* graph;
+
+    UGraphAdaptorBase() : graph(0) {}
+
+    void setGraph(Graph& _graph) { graph=&_graph; }
+
+    Graph& getGraph() { return *graph; }
+    const Graph& getGraph() const { return *graph; }
+
+  public:
+    UGraphAdaptorBase(Graph& _graph) : graph(&_graph) {}
+ 
+    typedef typename Graph::Node Node;
+    typedef typename Graph::Edge Edge;
+    typedef typename Graph::UEdge UEdge;
+   
+    void first(Node& i) const { graph->first(i); }
+    void first(Edge& i) const { graph->first(i); }
+    void first(UEdge& i) const { graph->first(i); }
+    void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
+    void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
+    void firstInc(UEdge &i, bool &d, const Node &n) const {
+      graph->firstInc(i, d, n);
+    }
+
+    void next(Node& i) const { graph->next(i); }
+    void next(Edge& i) const { graph->next(i); }
+    void next(UEdge& i) const { graph->next(i); }
+    void nextIn(Edge& i) const { graph->nextIn(i); }
+    void nextOut(Edge& i) const { graph->nextOut(i); }
+    void nextInc(UEdge &i, bool &d) const { graph->nextInc(i, d); }
+
+
+    Node source(const UEdge& e) const { return graph->source(e); }
+    Node target(const UEdge& e) const { return graph->target(e); }
+
+    Node source(const Edge& e) const { return graph->source(e); }
+    Node target(const Edge& e) const { return graph->target(e); }
+
+    typedef NodeNumTagIndicator<Graph> NodeNumTag;
+    int nodeNum() const { return graph->nodeNum(); }
+    
+    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
+    int edgeNum() const { return graph->edgeNum(); }
+
+    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
+    Edge findEdge(const Node& source, const Node& target, 
+		  const Edge& prev = INVALID) {
+      return graph->findEdge(source, target, prev);
+    }
+
+    UEdge findUEdge(const Node& source, const Node& target, 
+                    const UEdge& prev = INVALID) {
+      return graph->findUEdge(source, target, prev);
+    }
+  
+    Node addNode() const { return graph->addNode(); }
+    UEdge addEdge(const Node& source, const Node& target) const { 
+      return graph->addEdge(source, target); 
+    }
+
+    void erase(const Node& i) const { graph->erase(i); }
+    void erase(const Edge& i) const { graph->erase(i); }
+  
+    void clear() const { graph->clear(); }
+    
+    int id(const Node& v) const { return graph->id(v); }
+    int id(const UEdge& e) const { return graph->id(e); }
+
+    bool direction(const Edge& e) const { return graph->direction(e); }
+    Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); }
+    Edge direct(const UEdge& e, const Node& n) const { 
+      return graph->direct(e, n); 
+    }
+
+    Node oppositeNode(const Node& n, const Edge& e) const { 
+      return graph->oppositeNode(n, e); 
+    }
+
+    Edge oppositeEdge(const Edge& e) const { 
+      return graph->oppositeEdge(e); 
+    }
+
+
+    template <typename _Value>
+    class NodeMap : public Graph::template NodeMap<_Value> {
+    public:
+      typedef typename Graph::template NodeMap<_Value> Parent;
+      explicit NodeMap(const UGraphAdaptorBase<Graph>& ga) 
+	: Parent(*ga.graph) {}
+      NodeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
+	: Parent(*ga.graph, value) {}
+
+      NodeMap& operator=(const NodeMap& cmap) {
+	return operator=<NodeMap>(cmap);
+      }
+
+      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 Graph::template EdgeMap<_Value> {
+    public:
+      typedef typename Graph::template EdgeMap<_Value> Parent;
+      explicit EdgeMap(const UGraphAdaptorBase<Graph>& ga) 
+	: Parent(*ga.graph) {}
+      EdgeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
+	: Parent(*ga.graph, value) {}
+
+      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 Graph::template UEdgeMap<_Value> {
+    public:
+      typedef typename Graph::template UEdgeMap<_Value> Parent;
+      explicit UEdgeMap(const UGraphAdaptorBase<Graph>& ga) 
+	: Parent(*ga.graph) {}
+      UEdgeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
+	: Parent(*ga.graph, value) {}
+
+      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;
+      }
+    };
+
+  };
+
+  /// \ingroup graph_adaptors
+  template <typename _UGraph>
+  class UGraphAdaptor 
+    : public UGraphAdaptorExtender< UGraphAdaptorBase<_UGraph> > { 
+  public:
+    typedef _UGraph Graph;
+    typedef UGraphAdaptorExtender<UGraphAdaptorBase<_UGraph> > Parent;
+  protected:
+    UGraphAdaptor() : Parent() {}
+
+  public:
+    explicit UGraphAdaptor(Graph& _graph) { setGraph(_graph); }
+  };
+
+  template <typename _UGraph, typename NodeFilterMap, 
+	    typename UEdgeFilterMap, bool checked = true>
+  class SubUGraphAdaptorBase : public UGraphAdaptorBase<_UGraph> {
+  public:
+    typedef _UGraph Graph;
+    typedef UGraphAdaptorBase<_UGraph> Parent;
+  protected:
+
+    NodeFilterMap* node_filter_map;
+    UEdgeFilterMap* uedge_filter_map;
+
+    SubUGraphAdaptorBase() 
+      : Parent(), node_filter_map(0), uedge_filter_map(0) { }
+
+    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
+      node_filter_map=&_node_filter_map;
+    }
+    void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) {
+      uedge_filter_map=&_uedge_filter_map;
+    }
+
+  public:
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+    typedef typename Parent::UEdge UEdge;
+
+    void first(Node& i) const { 
+      Parent::first(i); 
+      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
+    }
+
+    void first(Edge& i) const { 
+      Parent::first(i); 
+      while (i!=INVALID && (!(*uedge_filter_map)[i] 
+	     || !(*node_filter_map)[Parent::source(i)]
+	     || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 
+    }
+
+    void first(UEdge& i) const { 
+      Parent::first(i); 
+      while (i!=INVALID && (!(*uedge_filter_map)[i] 
+	     || !(*node_filter_map)[Parent::source(i)]
+	     || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 
+    }
+
+    void firstIn(Edge& i, const Node& n) const { 
+      Parent::firstIn(i, n); 
+      while (i!=INVALID && (!(*uedge_filter_map)[i] 
+	     || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 
+    }
+
+    void firstOut(Edge& i, const Node& n) const { 
+      Parent::firstOut(i, n); 
+      while (i!=INVALID && (!(*uedge_filter_map)[i] 
+	     || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 
+    }
+
+    void firstInc(UEdge& i, bool& d, const Node& n) const { 
+      Parent::firstInc(i, d, n); 
+      while (i!=INVALID && (!(*uedge_filter_map)[i] 
+            || !(*node_filter_map)[Parent::target(i)])) Parent::nextInc(i, d); 
+    }
+
+    void next(Node& i) const { 
+      Parent::next(i); 
+      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
+    }
+
+    void next(Edge& i) const { 
+      Parent::next(i); 
+      while (i!=INVALID && (!(*uedge_filter_map)[i] 
+	     || !(*node_filter_map)[Parent::source(i)]
+	     || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 
+    }
+
+    void next(UEdge& i) const { 
+      Parent::next(i); 
+      while (i!=INVALID && (!(*uedge_filter_map)[i] 
+	     || !(*node_filter_map)[Parent::source(i)]
+	     || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 
+    }
+
+    void nextIn(Edge& i) const { 
+      Parent::nextIn(i); 
+      while (i!=INVALID && (!(*uedge_filter_map)[i] 
+	     || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 
+    }
+
+    void nextOut(Edge& i) const { 
+      Parent::nextOut(i); 
+      while (i!=INVALID && (!(*uedge_filter_map)[i] 
+	     || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 
+    }
+
+    void nextInc(UEdge& i, bool& d) const { 
+      Parent::nextInc(i, d); 
+      while (i!=INVALID && (!(*uedge_filter_map)[i] 
+            || !(*node_filter_map)[Parent::source(i)])) Parent::nextInc(i, d); 
+    }
+
+    ///\e
+
+    /// This function hides \c n in the graph, i.e. the iteration 
+    /// jumps over it. This is done by simply setting the value of \c n  
+    /// to be false in the corresponding node-map.
+    void hide(const Node& n) const { node_filter_map->set(n, false); }
+
+    ///\e
+
+    /// This function hides \c e in the graph, i.e. the iteration 
+    /// jumps over it. This is done by simply setting the value of \c e  
+    /// to be false in the corresponding edge-map.
+    void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
+
+    ///\e
+
+    /// The value of \c n is set to be true in the node-map which stores 
+    /// hide information. If \c n was hidden previuosly, then it is shown 
+    /// again
+     void unHide(const Node& n) const { node_filter_map->set(n, true); }
+
+    ///\e
+
+    /// The value of \c e is set to be true in the edge-map which stores 
+    /// hide information. If \c e was hidden previuosly, then it is shown 
+    /// again
+    void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }
+
+    /// Returns true if \c n is hidden.
+    
+    ///\e
+    ///
+    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
+
+    /// Returns true if \c n is hidden.
+    
+    ///\e
+    ///
+    bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
+
+    typedef False NodeNumTag;
+    typedef False EdgeNumTag;
+  };
+
+  template <typename _UGraph, typename NodeFilterMap, typename UEdgeFilterMap>
+  class SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, false> 
+    : public UGraphAdaptorBase<_UGraph> {
+  public:
+    typedef _UGraph Graph;
+    typedef UGraphAdaptorBase<_UGraph> Parent;
+  protected:
+    NodeFilterMap* node_filter_map;
+    UEdgeFilterMap* uedge_filter_map;
+    SubUGraphAdaptorBase() : Parent(), 
+			    node_filter_map(0), uedge_filter_map(0) { }
+
+    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
+      node_filter_map=&_node_filter_map;
+    }
+    void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) {
+      uedge_filter_map=&_uedge_filter_map;
+    }
+
+  public:
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+    typedef typename Parent::UEdge UEdge;
+
+    void first(Node& i) const { 
+      Parent::first(i); 
+      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
+    }
+
+    void first(Edge& i) const { 
+      Parent::first(i); 
+      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i); 
+    }
+
+    void first(UEdge& i) const { 
+      Parent::first(i); 
+      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i); 
+    }
+
+    void firstIn(Edge& i, const Node& n) const { 
+      Parent::firstIn(i, n); 
+      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextIn(i); 
+    }
+
+    void firstOut(Edge& i, const Node& n) const { 
+      Parent::firstOut(i, n); 
+      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextOut(i); 
+    }
+
+    void firstInc(UEdge& i, bool& d, const Node& n) const { 
+      Parent::firstInc(i, d, n); 
+      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextInc(i, d); 
+    }
+
+    void next(Node& i) const { 
+      Parent::next(i); 
+      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
+    }
+    void next(Edge& i) const { 
+      Parent::next(i); 
+      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i); 
+    }
+    void next(UEdge& i) const { 
+      Parent::next(i); 
+      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i); 
+    }
+    void nextIn(Edge& i) const { 
+      Parent::nextIn(i); 
+      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextIn(i); 
+    }
+
+    void nextOut(Edge& i) const { 
+      Parent::nextOut(i); 
+      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextOut(i); 
+    }
+    void nextInc(UEdge& i, bool& d) const { 
+      Parent::nextInc(i, d); 
+      while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextInc(i, d); 
+    }
+
+    ///\e
+
+    /// This function hides \c n in the graph, i.e. the iteration 
+    /// jumps over it. This is done by simply setting the value of \c n  
+    /// to be false in the corresponding node-map.
+    void hide(const Node& n) const { node_filter_map->set(n, false); }
+
+    ///\e
+
+    /// This function hides \c e in the graph, i.e. the iteration 
+    /// jumps over it. This is done by simply setting the value of \c e  
+    /// to be false in the corresponding edge-map.
+    void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
+
+    ///\e
+
+    /// The value of \c n is set to be true in the node-map which stores 
+    /// hide information. If \c n was hidden previuosly, then it is shown 
+    /// again
+     void unHide(const Node& n) const { node_filter_map->set(n, true); }
+
+    ///\e
+
+    /// The value of \c e is set to be true in the edge-map which stores 
+    /// hide information. If \c e was hidden previuosly, then it is shown 
+    /// again
+    void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }
+
+    /// Returns true if \c n is hidden.
+    
+    ///\e
+    ///
+    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
+
+    /// Returns true if \c n is hidden.
+    
+    ///\e
+    ///
+    bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
+
+    typedef False NodeNumTag;
+    typedef False EdgeNumTag;
+  };
+
+  /// \ingroup graph_adaptors
+  ///
+  /// \brief A graph adaptor for hiding nodes and edges from an undirected 
+  /// graph.
+  /// 
+  /// \warning Graph adaptors are in even more experimental state than the
+  /// other parts of the lib. Use them at you own risk.
+  /// 
+  /// SubUGraphAdaptor shows the undirected graph with filtered node-set and 
+  /// edge-set. If the \c checked parameter is true then it filters the edgeset
+  /// to do not get invalid edges without source or target.
+  /// 
+  /// If the \c checked template parameter is false then we have to note that 
+  /// the node-iterator cares only the filter on the node-set, and the 
+  /// edge-iterator cares only the filter on the edge-set.
+  /// This way the edge-map
+  /// should filter all edges which's source or target is filtered by the 
+  /// node-filter.
+  ///
+  /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
+  /// \c Graph::Node that is why \c g.id(n) can be applied.
+  /// 
+  /// For examples see also the documentation of NodeSubUGraphAdaptor and 
+  /// EdgeSubUGraphAdaptor.
+  /// 
+  /// \author Marton Makai
+
+  template<typename _UGraph, typename NodeFilterMap, 
+	   typename UEdgeFilterMap, bool checked = true>
+  class SubUGraphAdaptor : 
+    public UGraphAdaptorExtender<
+    SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, checked> > {
+  public:
+    typedef _UGraph Graph;
+    typedef UGraphAdaptorExtender<
+      SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap> > Parent;
+  protected:
+    SubUGraphAdaptor() { }
+  public:
+    SubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map, 
+		    UEdgeFilterMap& _uedge_filter_map) { 
+      setGraph(_graph);
+      setNodeFilterMap(_node_filter_map);
+      setUEdgeFilterMap(_uedge_filter_map);
+    }
+  };
+
+  /// \ingroup graph_adaptors
+  ///
+  /// \brief An adaptor for hiding nodes from an undorected graph.
+  ///
+  /// \warning Graph adaptors are in even more experimental state
+  /// than the other
+  /// parts of the lib. Use them at you own risk.
+  ///
+  /// An adaptor for hiding nodes from an undirected graph.
+  /// This adaptor specializes SubUGraphAdaptor in the way that only
+  /// the node-set 
+  /// can be filtered. In usual case the checked parameter is true, we get the
+  /// induced subgraph. But if the checked parameter is false then we can only
+  /// filter only isolated nodes.
+  /// \author Marton Makai
+  template<typename _UGraph, typename NodeFilterMap, bool checked = true>
+  class NodeSubUGraphAdaptor : 
+    public SubUGraphAdaptor<_UGraph, NodeFilterMap, 
+                            ConstMap<typename _UGraph::UEdge, bool>, checked> {
+  public:
+    typedef SubUGraphAdaptor<_UGraph, NodeFilterMap, 
+                             ConstMap<typename _UGraph::UEdge, bool> > Parent;
+    typedef _UGraph Graph;
+  protected:
+    ConstMap<typename _UGraph::Edge, bool> const_true_map;
+  public:
+    NodeSubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) : 
+      Parent(), const_true_map(true) { 
+      Parent::setGraph(_graph);
+      Parent::setNodeFilterMap(_node_filter_map);
+      Parent::setUEdgeFilterMap(const_true_map);
+    }
+  };
+
+  template<typename UGraph, typename NodeFilterMap>
+  NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>
+  nodeSubUGraphAdaptor(const UGraph& graph, NodeFilterMap& nfm) {
+    return NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>(graph, nfm);
+  }
+
+  template<typename UGraph, typename NodeFilterMap>
+  NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>
+  nodeSubUGraphAdaptor(const UGraph& graph, const NodeFilterMap& nfm) {
+    return NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>(graph, nfm);
+  }
+
+
+  /// \brief An adaptor for hiding undirected edges from an undirected graph.
+  ///
+  /// \warning Graph adaptors are in even more experimental state
+  /// than the other parts of the lib. Use them at you own risk.
+  ///
+  /// An adaptor for hiding undirected edges from an undirected graph.
+  /// This adaptor specializes SubUGraphAdaptor in the way that
+  /// only the edge-set 
+  /// can be filtered.
+  ///
+  ///\author Marton Makai
+  template<typename _UGraph, typename UEdgeFilterMap>
+  class EdgeSubUGraphAdaptor : 
+    public SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>, 
+                            UEdgeFilterMap, false> {
+  public:
+    typedef SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>, 
+                             UEdgeFilterMap, false> Parent;
+    typedef _UGraph Graph;
+  protected:
+    ConstMap<typename Graph::Node, bool> const_true_map;
+  public:
+    EdgeSubUGraphAdaptor(Graph& _graph, UEdgeFilterMap& _uedge_filter_map) : 
+      Parent(), const_true_map(true) { 
+      Parent::setGraph(_graph);
+      Parent::setNodeFilterMap(const_true_map);
+      Parent::setUEdgeFilterMap(_uedge_filter_map);
+    }
+  };
+
+  template<typename UGraph, typename EdgeFilterMap>
+  EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>
+  edgeSubUGraphAdaptor(const UGraph& graph, EdgeFilterMap& efm) {
+    return EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>(graph, efm);
+  }
+
+  template<typename UGraph, typename EdgeFilterMap>
+  EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>
+  edgeSubUGraphAdaptor(const UGraph& graph, const EdgeFilterMap& efm) {
+    return EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>(graph, efm);
+  }
+
+  template <typename _UGraph, typename _DirectionMap>
+  class DirectUGraphAdaptorBase {
+  public:
+    
+    typedef _UGraph Graph;
+    typedef _DirectionMap DirectionMap;
+
+    typedef typename _UGraph::Node Node;
+    typedef typename _UGraph::UEdge Edge;
+   
+    void first(Node& i) const { graph->first(i); }
+    void first(Edge& i) const { graph->first(i); }
+    void firstIn(Edge& i, const Node& n) const {
+      bool d;
+      graph->firstInc(i, d, n);
+      while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);
+    }
+    void firstOut(Edge& i, const Node& n ) const { 
+      bool d;
+      graph->firstInc(i, d, n);
+      while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);
+    }
+
+    void next(Node& i) const { graph->next(i); }
+    void next(Edge& i) const { graph->next(i); }
+    void nextIn(Edge& i) const {
+      bool d = !(*direction)[i];
+      graph->nextInc(i, d);
+      while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);
+    }
+    void nextOut(Edge& i) const {
+      bool d = (*direction)[i];
+      graph->nextInc(i, d);
+      while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);
+    }
+
+    Node source(const Edge& e) const { 
+      return (*direction)[e] ? graph->source(e) : graph->target(e); 
+    }
+    Node target(const Edge& e) const { 
+      return (*direction)[e] ? graph->target(e) : graph->source(e); 
+    }
+
+    typedef NodeNumTagIndicator<Graph> NodeNumTag;
+    int nodeNum() const { return graph->nodeNum(); }
+    
+    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
+    int edgeNum() const { return graph->uEdgeNum(); }
+
+    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
+    Edge findEdge(const Node& source, const Node& target, 
+		  const Edge& prev = INVALID) {
+      Edge edge = prev;
+      bool d = edge == INVALID ? true : (*direction)[edge];
+      if (d) {
+        edge = graph->findUEdge(source, target, edge);
+        while (edge != INVALID && !(*direction)[edge]) {
+          graph->findUEdge(source, target, edge);
+        }
+        if (edge != INVALID) return edge;
+      }
+      graph->findUEdge(target, source, edge);
+      while (edge != INVALID && (*direction)[edge]) {
+        graph->findUEdge(source, target, edge);
+      }
+      return edge;
+    }
+  
+    Node addNode() const { 
+      return Node(graph->addNode()); 
+    }
+
+    Edge addEdge(const Node& source, const Node& target) const {
+      Edge edge = graph->addEdge(source, target);
+      (*direction)[edge] = graph->source(edge) == source;
+      return edge; 
+    }
+
+    void erase(const Node& i) const { graph->erase(i); }
+    void erase(const Edge& i) const { graph->erase(i); }
+  
+    void clear() const { graph->clear(); }
+    
+    int id(const Node& v) const { return graph->id(v); }
+    int id(const Edge& e) const { return graph->id(e); }
+
+    void reverseEdge(const Edge& edge) {
+      direction->set(edge, !(*direction)[edge]);
+    }
+
+    template <typename _Value>
+    class NodeMap : public _UGraph::template NodeMap<_Value> {
+    public:
+      typedef typename _UGraph::template NodeMap<_Value> Parent;
+      explicit NodeMap(const DirectUGraphAdaptorBase& ga) 
+	: Parent(*ga.graph) { }
+      NodeMap(const DirectUGraphAdaptorBase& ga, const _Value& value)
+	: Parent(*ga.graph, value) { }
+    };
+
+    template <typename _Value>
+    class EdgeMap : public _UGraph::template UEdgeMap<_Value> {
+    public:
+      typedef typename _UGraph::template EdgeMap<_Value> Parent;
+      explicit EdgeMap(const DirectUGraphAdaptorBase& ga) 
+	: Parent(*ga.graph) { }
+      EdgeMap(const DirectUGraphAdaptorBase& ga, const _Value& value)
+	: Parent(*ga.graph, value) { }
+    };
+
+    
+
+  protected:
+    Graph* graph;
+    DirectionMap* direction;
+
+    void setDirectionMap(DirectionMap& _direction) {
+      direction = &_direction;
+    }
+
+    void setGraph(Graph& _graph) {
+      graph = &_graph;
+    }
+
+  };
+
+
+  template<typename _Graph, typename DirectionMap> 
+  class DirectUGraphAdaptor : 
+    public GraphAdaptorExtender<
+    DirectUGraphAdaptorBase<_Graph, DirectionMap> > {
+  public:
+    typedef _Graph Graph;
+    typedef GraphAdaptorExtender<
+      DirectUGraphAdaptorBase<_Graph, DirectionMap> > Parent;
+  protected:
+    DirectUGraphAdaptor() { }
+  public:
+    DirectUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) { 
+      setGraph(_graph);
+      setDirectionMap(_direction_map);
+    }
+  };
+
+  template<typename UGraph, typename DirectionMap>
+  DirectUGraphAdaptor<const UGraph, DirectionMap>
+  directUGraphAdaptor(const UGraph& graph, DirectionMap& dm) {
+    return DirectUGraphAdaptor<const UGraph, DirectionMap>(graph, dm);
+  }
+
+  template<typename UGraph, typename DirectionMap>
+  DirectUGraphAdaptor<const UGraph, const DirectionMap>
+  directUGraphAdaptor(const UGraph& graph, const DirectionMap& dm) {
+    return DirectUGraphAdaptor<const UGraph, const DirectionMap>(graph, dm);
+  }
+
+}
+
+#endif
diff -r ef2d00e46897 -r c2992fd74dad test/graph_adaptor_test.cc
--- a/test/graph_adaptor_test.cc	Wed Feb 22 12:45:59 2006 +0000
+++ b/test/graph_adaptor_test.cc	Wed Feb 22 18:26:56 2006 +0000
@@ -67,9 +67,7 @@
       Graph::NodeMap<Graph::Edge> > >(); 
 
     /// \bug why does not compile with StaticGraph
-    checkConcept<BaseIterableUGraphConcept, UGraphAdaptor<ListGraph> >();
-    checkConcept<IterableUGraphConcept, UGraphAdaptor<ListGraph> >();
-    checkConcept<MappableUGraphConcept, UGraphAdaptor<ListGraph> >();
+    checkConcept<UGraph, UndirectGraphAdaptor<ListGraph> >();
   }
   std::cout << __FILE__ ": All tests passed.\n";
 
diff -r ef2d00e46897 -r c2992fd74dad test/ugraph_test.cc
--- a/test/ugraph_test.cc	Wed Feb 22 12:45:59 2006 +0000
+++ b/test/ugraph_test.cc	Wed Feb 22 18:26:56 2006 +0000
@@ -21,7 +21,7 @@
 #include <lemon/list_graph.h>
 #include <lemon/smart_graph.h>
 #include <lemon/full_graph.h>
-#include <lemon/grid_graph.h>
+#include <lemon/grid_ugraph.h>
 
 #include <lemon/graph_utils.h>
 
@@ -32,25 +32,6 @@
 using namespace lemon::concept;
 
 void check_concepts() {
-  typedef UGraphExtender<ListGraphBase> ListUGraphBase;
-
-  typedef IterableUGraphExtender<
-    AlterableUGraphExtender<ListUGraphBase> > IterableListUGraph;
-
-  typedef MappableUGraphExtender<IterableListUGraph>
-    MappableListUGraph;
-
-  typedef ErasableUGraphExtender<
-    ClearableUGraphExtender<
-    ExtendableUGraphExtender<MappableListUGraph> > > Graph;
-
-  checkConcept<BaseIterableUGraphConcept, Graph>();
-  checkConcept<IterableUGraphConcept, Graph>();
-  checkConcept<MappableUGraphConcept, Graph>();
-
-  checkConcept<UGraph, Graph>();
-  checkConcept<ErasableUGraph, Graph>();
-
   checkConcept<UGraph, ListUGraph>();
   checkConcept<ErasableUGraph, ListUGraph>();
 
@@ -61,7 +42,7 @@
 
   checkConcept<UGraph, UGraph>();
 
-  checkConcept<UGraph, GridGraph>();
+  checkConcept<UGraph, GridUGraph>();
 }
 
 template <typename Graph>
@@ -150,7 +131,7 @@
   check_item_counts(g,3,2);
 }
 
-void checkGridGraph(const GridGraph& g, int w, int h) {
+void checkGridUGraph(const GridUGraph& g, int w, int h) {
   check(g.width() == w, "Wrong width");
   check(g.height() == h, "Wrong height");
 
@@ -206,9 +187,9 @@
   }
 
   {
-    GridGraph g(5, 6);
+    GridUGraph g(5, 6);
     check_item_counts(g, 30, 49);
-    checkGridGraph(g, 5, 6);
+    checkGridUGraph(g, 5, 6);
   }
 
   std::cout << __FILE__ ": All tests passed.\n";