Index: doc/images/edge_disjoint.eps
===================================================================
--- doc/images/edge_disjoint.eps	(revision 2079)
+++ doc/images/edge_disjoint.eps	(revision 2079)
@@ -0,0 +1,116 @@
+%!PS-Adobe-2.0 EPSF-2.0
+%%Title: edge disjoint path
+%%Copyright: (C) 2006 LEMON Project
+%%Creator: LEMON, graphToEps()
+%%CreationDate: Fri May 12 01:53:21 2006
+%%BoundingBox: -290 -170 470 230
+%%EndComments
+/lb { setlinewidth setrgbcolor newpath moveto
+      4 2 roll 1 index 1 index curveto stroke } bind def
+/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
+/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
+/sq { newpath 2 index 1 index add 2 index 2 index add moveto
+      2 index 1 index sub 2 index 2 index add lineto
+      2 index 1 index sub 2 index 2 index sub lineto
+      2 index 1 index add 2 index 2 index sub lineto
+      closepath pop pop pop} bind def
+/di { newpath 2 index 1 index add 2 index moveto
+      2 index             2 index 2 index add lineto
+      2 index 1 index sub 2 index             lineto
+      2 index             2 index 2 index sub lineto
+      closepath pop pop pop} bind def
+/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
+     setrgbcolor 1.1 div c fill
+   } bind def
+/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
+     setrgbcolor 1.1 div sq fill
+   } bind def
+/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
+     setrgbcolor 1.1 div di fill
+   } bind def
+/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
+  newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub
+  lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto
+  5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke
+  5 index 5 index 5 index c fill
+  setrgbcolor 1.1 div c fill
+  } bind def
+/nmale {
+  0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
+  newpath 5 index 5 index moveto
+  5 index 4 index 1 mul 1.5 mul add
+  5 index 5 index 3 sqrt 1.5 mul mul add
+  1 index 1 index lineto
+  1 index 1 index 7 index sub moveto
+  1 index 1 index lineto
+  exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto
+  stroke
+  5 index 5 index 5 index c fill
+  setrgbcolor 1.1 div c fill
+  } bind def
+/arrl 1 def
+/arrw 0.3 def
+/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
+/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
+       /w exch def /len exch def
+       newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
+       len w sub arrl sub dx dy lrl
+       arrw dy dx neg lrl
+       dx arrl w add mul dy w 2 div arrw add mul sub
+       dy arrl w add mul dx w 2 div arrw add mul add rlineto
+       dx arrl w add mul neg dy w 2 div arrw add mul sub
+       dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
+       arrw dy dx neg lrl
+       len w sub arrl sub neg dx dy lrl
+       closepath fill } bind def
+/cshow { 2 index 2 index moveto dup stringwidth pop
+         neg 2 div fosi .35 mul neg rmoveto show pop pop} def
+
+gsave
+10 dup scale
+%Edges:
+gsave
+15.6433 0.3 0.841178 -0.540758 -27 5 1 0 0 arr
+19.5913 0.3 0.874157 0.485643 -27 5 1 0 0 arr
+10.1803 0.3 0.98387 -0.178885 -20 17 1 0 0 arr
+20.587 0.3 0.972806 0.231621 -18 -14 1 0 0 arr
+15.7631 0.3 0.95448 -0.298275 -13 -4 0 0 0 arr
+15.9706 0.3 0.707107 -0.707107 -9 15 1 0 0 arr
+16.4642 0.3 0.916157 0.400819 -13 -4 1 0 0 arr
+14.5242 0.3 0.966235 -0.257663 -12 7 0 0 0 arr
+10.6619 0.3 0.857493 0.514496 -9 15 1 0 0 arr
+22.4094 0.3 0.939793 -0.341743 3 3 1 0 0 arr
+27.1602 0.3 0.958798 -0.284088 1 21 1 0 0 arr
+25.9258 0.3 0.928477 0.371391 3 3 1 0 0 arr
+25.9072 0.3 0.743294 0.668965 25 -15 1 0 0 arr
+20.5407 0.3 0.928477 0.371391 25 -5 1 0 0 arr
+18.7231 0.3 0.861934 -0.50702 28 13 1 0 0 arr
+14.2315 0.3 0.393919 0.919145 39 -11 0 0 0 arr
+10.6619 0.3 0.514496 -0.857493 39 13 1 0 0 arr
+20.0238 0.3 0.428086 -0.903738 -27 5 1 0 0 arr
+21.8035 0.3 0.964764 -0.263117 3 -9 1 0 0 arr
+14.1328 0.3 0.991228 0.132164 -27 5 0 0 0 arr
+13.5602 0.3 0.961524 0.274721 25 -15 0 0 0 arr
+10 0.3 1 0 28 13 1 0 0 arr
+12.8924 0.3 0.503871 0.863779 -27 5 1 0 0 arr
+grestore
+%Nodes:
+gsave
+-27 5 1 1 1 1 nc
+-13 -4 1 1 1 1 nc
+-9 15 1 1 1 1 nc
+3 -9 1 1 1 1 nc
+3 3 1 1 1 1 nc
+1 21 1 1 1 1 nc
+25 -5 1 1 1 1 nc
+28 13 1 1 1 1 nc
+45 3 1 1 1 1 nc
+-18 -14 1 1 1 1 nc
+25 -15 1 1 1 1 nc
+-12 7 1 1 1 1 nc
+39 -11 1 1 1 1 nc
+39 13 1 1 1 1 nc
+-20 17 1 1 1 1 nc
+grestore
+grestore
+showpage
Index: doc/images/node_disjoint.eps
===================================================================
--- doc/images/node_disjoint.eps	(revision 2079)
+++ doc/images/node_disjoint.eps	(revision 2079)
@@ -0,0 +1,146 @@
+%!PS-Adobe-2.0 EPSF-2.0
+%%Title: node disjoint path
+%%Copyright: (C) 2006 LEMON Project
+%%Creator: LEMON, graphToEps()
+%%CreationDate: Fri May 12 01:53:21 2006
+%%BoundingBox: -290 -170 520 230
+%%EndComments
+/lb { setlinewidth setrgbcolor newpath moveto
+      4 2 roll 1 index 1 index curveto stroke } bind def
+/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
+/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
+/sq { newpath 2 index 1 index add 2 index 2 index add moveto
+      2 index 1 index sub 2 index 2 index add lineto
+      2 index 1 index sub 2 index 2 index sub lineto
+      2 index 1 index add 2 index 2 index sub lineto
+      closepath pop pop pop} bind def
+/di { newpath 2 index 1 index add 2 index moveto
+      2 index             2 index 2 index add lineto
+      2 index 1 index sub 2 index             lineto
+      2 index             2 index 2 index sub lineto
+      closepath pop pop pop} bind def
+/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
+     setrgbcolor 1.1 div c fill
+   } bind def
+/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
+     setrgbcolor 1.1 div sq fill
+   } bind def
+/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
+     setrgbcolor 1.1 div di fill
+   } bind def
+/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
+  newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub
+  lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto
+  5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke
+  5 index 5 index 5 index c fill
+  setrgbcolor 1.1 div c fill
+  } bind def
+/nmale {
+  0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
+  newpath 5 index 5 index moveto
+  5 index 4 index 1 mul 1.5 mul add
+  5 index 5 index 3 sqrt 1.5 mul mul add
+  1 index 1 index lineto
+  1 index 1 index 7 index sub moveto
+  1 index 1 index lineto
+  exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto
+  stroke
+  5 index 5 index 5 index c fill
+  setrgbcolor 1.1 div c fill
+  } bind def
+/arrl 1 def
+/arrw 0.3 def
+/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
+/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
+       /w exch def /len exch def
+       newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
+       len w sub arrl sub dx dy lrl
+       arrw dy dx neg lrl
+       dx arrl w add mul dy w 2 div arrw add mul sub
+       dy arrl w add mul dx w 2 div arrw add mul add rlineto
+       dx arrl w add mul neg dy w 2 div arrw add mul sub
+       dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
+       arrw dy dx neg lrl
+       len w sub arrl sub neg dx dy lrl
+       closepath fill } bind def
+/cshow { 2 index 2 index moveto dup stringwidth pop
+         neg 2 div fosi .35 mul neg rmoveto show pop pop} def
+
+gsave
+10 dup scale
+%Edges:
+gsave
+4 0.3 1 0 -27 5 0 0 0 arr
+4 0.3 1 0 -13 -4 1 0 0 arr
+4 0.3 1 0 -9 15 1 0 0 arr
+4 0.3 1 0 3 -9 1 0 0 arr
+4 0.3 1 0 3 3 1 0 0 arr
+4 0.3 1 0 1 21 1 0 0 arr
+4 0.3 1 0 25 -5 1 0 0 arr
+4 0.3 1 0 28 13 1 0 0 arr
+4 0.3 1 0 45 3 0 0 0 arr
+4 0.3 1 0 -18 -14 1 0 0 arr
+4 0.3 1 0 25 -15 1 0 0 arr
+4 0.3 1 0 -12 7 0 0 0 arr
+4 0.3 1 0 39 -11 0 0 0 arr
+4 0.3 1 0 39 13 0 0 0 arr
+4 0.3 1 0 -20 17 1 0 0 arr
+11.7279 0.3 0.707107 -0.707107 -22 5 1 0 0 arr
+15.4012 0.3 0.792624 0.609711 -22 5 0 0 0 arr
+5.32455 0.3 0.948683 -0.316228 -15 17 1 0 0 arr
+15.7631 0.3 0.95448 0.298275 -13 -14 1 0 0 arr
+11.083 0.3 0.910366 -0.413803 -8 -4 0 0 0 arr
+12.8924 0.3 0.503871 -0.863779 -4 15 0 0 0 arr
+12.0384 0.3 0.843661 0.536875 -8 -4 1 0 0 arr
+9.77033 0.3 0.928477 -0.371391 -7 7 0 0 0 arr
+6.81025 0.3 0.640184 0.768221 -4 15 1 0 0 arr
+17.7883 0.3 0.904819 -0.425797 8 3 1 0 0 arr
+22.4094 0.3 0.939793 -0.341743 6 21 1 0 0 arr
+21.3607 0.3 0.894427 0.447214 8 3 0 0 0 arr
+22.4307 0.3 0.640184 0.768221 30 -15 1 0 0 arr
+16 0.3 0.882353 0.470588 30 -5 1 0 0 arr
+14.6205 0.3 0.768221 -0.640184 33 13 1 0 0 arr
+13.0357 0.3 0.071247 0.997459 44 -11 0 0 0 arr
+9.04987 0.3 0.0995037 -0.995037 44 13 0 0 0 arr
+18.4165 0.3 0.20601 -0.97855 -22 5 1 0 0 arr
+17.0278 0.3 0.94299 -0.33282 8 -9 1 0 0 arr
+9.19804 0.3 0.980581 0.196116 -22 5 0 0 0 arr
+8.84886 0.3 0.913812 0.406138 30 -15 0 0 0 arr
+5 0.3 1 0 33 13 0 0 0 arr
+11.1655 0.3 0.164399 0.986394 -22 5 1 0 0 arr
+grestore
+%Nodes:
+gsave
+-27 5 1 1 1 1 nc
+-22 5 1 1 1 1 nc
+-13 -4 1 1 1 1 nc
+-8 -4 1 1 1 1 nc
+-9 15 1 1 1 1 nc
+-4 15 1 1 1 1 nc
+3 -9 1 1 1 1 nc
+8 -9 1 1 1 1 nc
+3 3 1 1 1 1 nc
+8 3 1 1 1 1 nc
+1 21 1 1 1 1 nc
+6 21 1 1 1 1 nc
+25 -5 1 1 1 1 nc
+30 -5 1 1 1 1 nc
+28 13 1 1 1 1 nc
+33 13 1 1 1 1 nc
+45 3 1 1 1 1 nc
+50 3 1 1 1 1 nc
+-18 -14 1 1 1 1 nc
+-13 -14 1 1 1 1 nc
+25 -15 1 1 1 1 nc
+30 -15 1 1 1 1 nc
+-12 7 1 1 1 1 nc
+-7 7 1 1 1 1 nc
+39 -11 1 1 1 1 nc
+44 -11 1 1 1 1 nc
+39 13 1 1 1 1 nc
+44 13 1 1 1 1 nc
+-20 17 1 1 1 1 nc
+-15 17 1 1 1 1 nc
+grestore
+grestore
+showpage
Index: lemon/graph_adaptor.h
===================================================================
--- lemon/graph_adaptor.h	(revision 2042)
+++ lemon/graph_adaptor.h	(revision 2079)
@@ -37,5 +37,5 @@
 #include <lemon/tolerance.h>
 
-#include <iostream>
+#include <algorithm>
 
 namespace lemon {
@@ -257,7 +257,6 @@
   /// RevGraphAdaptor<ListGraph> ga(g);
   ///\endcode
-  ///implements the graph obtained from \c g by 
+  /// implements the graph obtained from \c g by 
   /// reversing the orientation of its edges.
-
   template<typename _Graph>
   class RevGraphAdaptor : 
@@ -984,11 +983,11 @@
   }
 
-  template <typename _Graph, typename Enable = void>
+  template <typename _Graph>
   class UndirGraphAdaptorBase : 
-    public UGraphBaseExtender<GraphAdaptorBase<_Graph> > {
+    public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
   public:
     typedef _Graph Graph;
     typedef UndirGraphAdaptorBase Adaptor;
-    typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;
+    typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
 
   protected:
@@ -1104,35 +1103,47 @@
   };
 
+  template <typename _Graph, typename Enable = void>
+  class AlterableUndirGraphAdaptor 
+    : public UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > {
+  public:
+    typedef UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > Parent;
+    
+  protected:
+
+    AlterableUndirGraphAdaptor() : Parent() {}
+
+  public:
+
+    typedef typename Parent::EdgeNotifier UEdgeNotifier;
+    typedef InvalidType EdgeNotifier;
+
+  };
+
   template <typename _Graph>
-  class UndirGraphAdaptorBase<
-    _Graph, typename enable_if<
-    typename _Graph::EdgeNotifier::Notifier>::type > 
-      : public UGraphBaseExtender<GraphAdaptorBase<_Graph> > {
-  public:
-
+  class AlterableUndirGraphAdaptor<
+    _Graph, 
+    typename enable_if<typename _Graph::EdgeNotifier::Notifier>::type > 
+    : public UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > {
+  public:
+
+    typedef UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > Parent;
     typedef _Graph Graph;
-    typedef UndirGraphAdaptorBase Adaptor;
-    typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;
-
+    typedef typename _Graph::Edge GraphEdge;
+    
   protected:
 
-    UndirGraphAdaptorBase() 
-      : edge_notifier(*this), edge_notifier_proxy(edge_notifier) {}
+    AlterableUndirGraphAdaptor() 
+      : Parent(), edge_notifier(*this), edge_notifier_proxy(*this) {}
 
     void setGraph(_Graph& graph) {
       Parent::setGraph(graph);
-      edge_notifier_proxy.setUEdgeNotifier(graph.getNotifier(UEdge()));
-    }
-
-  public:
-
-    ~UndirGraphAdaptorBase() {
+      edge_notifier_proxy.setNotifier(graph.getNotifier(GraphEdge()));
+    }
+
+  public:
+
+    ~AlterableUndirGraphAdaptor() {
       edge_notifier.clear();
     }
-
-    int maxId(typename Parent::Edge) const {
-      return Parent::maxEdgeId();
-    }
-
 
     typedef typename Parent::UEdge UEdge;
@@ -1143,17 +1154,18 @@
     using Parent::getNotifier;
 
-    typedef AlterationNotifier<UndirGraphAdaptorBase, Edge> EdgeNotifier;
+    typedef AlterationNotifier<AlterableUndirGraphAdaptor, 
+                               Edge> EdgeNotifier;
     EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
 
   protected:
 
-    class NotifierProxy : public UEdgeNotifier::ObserverBase {
+    class NotifierProxy : public Graph::EdgeNotifier::ObserverBase {
     public:
 
-      typedef typename UEdgeNotifier::ObserverBase Parent;
-      typedef UndirGraphAdaptorBase AdaptorBase;
-      
-      NotifierProxy(EdgeNotifier& _edge_notifier)
-        : Parent(), edge_notifier(_edge_notifier) {
+      typedef typename Graph::EdgeNotifier::ObserverBase Parent;
+      typedef AlterableUndirGraphAdaptor AdaptorBase;
+      
+      NotifierProxy(const AdaptorBase& _adaptor)
+        : Parent(), adaptor(&_adaptor) {
       }
 
@@ -1164,6 +1176,6 @@
       }
 
-      void setUEdgeNotifier(UEdgeNotifier& _uedge_notifier) {
-        Parent::attach(_uedge_notifier);
+      void setNotifier(typename Graph::EdgeNotifier& notifier) {
+        Parent::attach(notifier);
       }
 
@@ -1171,40 +1183,40 @@
     protected:
 
-      virtual void add(const UEdge& uedge) {
+      virtual void add(const GraphEdge& ge) {
         std::vector<Edge> edges;
-        edges.push_back(AdaptorBase::Parent::direct(uedge, true));
-        edges.push_back(AdaptorBase::Parent::direct(uedge, false));
-        edge_notifier.add(edges);
-      }
-      virtual void add(const std::vector<UEdge>& uedges) {
+        edges.push_back(AdaptorBase::Parent::direct(ge, true));
+        edges.push_back(AdaptorBase::Parent::direct(ge, false));
+        adaptor->getNotifier(Edge()).add(edges);
+      }
+      virtual void add(const std::vector<GraphEdge>& ge) {
         std::vector<Edge> edges;
-        for (int i = 0; i < (int)uedges.size(); ++i) { 
-          edges.push_back(AdaptorBase::Parent::direct(uedges[i], true));
-          edges.push_back(AdaptorBase::Parent::direct(uedges[i], false));
-        }
-        edge_notifier.add(edges);
-      }
-      virtual void erase(const UEdge& uedge) {
+        for (int i = 0; i < (int)ge.size(); ++i) { 
+          edges.push_back(AdaptorBase::Parent::direct(ge[i], true));
+          edges.push_back(AdaptorBase::Parent::direct(ge[i], false));
+        }
+        adaptor->getNotifier(Edge()).add(edges);
+      }
+      virtual void erase(const GraphEdge& ge) {
         std::vector<Edge> edges;
-        edges.push_back(AdaptorBase::Parent::direct(uedge, true));
-        edges.push_back(AdaptorBase::Parent::direct(uedge, false));
-        edge_notifier.erase(edges);
-      }
-      virtual void erase(const std::vector<UEdge>& uedges) {
+        edges.push_back(AdaptorBase::Parent::direct(ge, true));
+        edges.push_back(AdaptorBase::Parent::direct(ge, false));
+        adaptor->getNotifier(Edge()).erase(edges);
+      }
+      virtual void erase(const std::vector<GraphEdge>& ge) {
         std::vector<Edge> edges;
-        for (int i = 0; i < (int)uedges.size(); ++i) { 
-          edges.push_back(AdaptorBase::Parent::direct(uedges[i], true));
-          edges.push_back(AdaptorBase::Parent::direct(uedges[i], false));
-        }
-        edge_notifier.erase(edges);
+        for (int i = 0; i < (int)ge.size(); ++i) { 
+          edges.push_back(AdaptorBase::Parent::direct(ge[i], true));
+          edges.push_back(AdaptorBase::Parent::direct(ge[i], false));
+        }
+        adaptor->getNotifier(Edge()).erase(edges);
       }
       virtual void build() {
-        edge_notifier.build();
+        adaptor->getNotifier(Edge()).build();
       }
       virtual void clear() {
-        edge_notifier.clear();
-      }
-
-      EdgeNotifier& edge_notifier;
+        adaptor->getNotifier(Edge()).clear();
+      }
+
+      const AdaptorBase* adaptor;
     };
 
@@ -1213,109 +1225,9 @@
     NotifierProxy edge_notifier_proxy;
 
-  private:
-    
-    template <typename _Value>
-    class EdgeMapBase {
-    private:
-      
-      typedef typename _Graph::template EdgeMap<_Value> MapImpl;
-      
-    public:
-
-      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
-
-      typedef _Value Value;
-      typedef Edge Key;
-      
-      EdgeMapBase(const Adaptor& adaptor) :
-	forward_map(*adaptor.graph), backward_map(*adaptor.graph) {}
-
-      EdgeMapBase(const Adaptor& adaptor, const Value& v) 
-        : forward_map(*adaptor.graph, v), backward_map(*adaptor.graph, v) {}
-      
-      void set(const Edge& e, const Value& a) { 
-	if (Parent::direction(e)) {
-	  forward_map.set(e, a); 
-        } else { 
-	  backward_map.set(e, a);
-        } 
-      }
-
-      typename MapTraits<MapImpl>::ConstReturnValue operator[](Edge e) const { 
-	if (Parent::direction(e)) {
-	  return forward_map[e]; 
-	} else { 
-	  return backward_map[e]; 
-        }
-      }
-
-      typename MapTraits<MapImpl>::ReturnValue operator[](Edge e) { 
-	if (Parent::direction(e)) {
-	  return forward_map[e]; 
-	} else { 
-	  return backward_map[e]; 
-        }
-      }
-
-    protected:
-
-      MapImpl forward_map, backward_map; 
-
-    };
-
-  public:
-
-    template <typename _Value>
-    class EdgeMap 
-      : public SubMapExtender<Adaptor, EdgeMapBase<_Value> > 
-    {
-    public:
-      typedef Adaptor Graph;
-      typedef SubMapExtender<Adaptor, EdgeMapBase<_Value> > Parent;
-    
-      EdgeMap(const Graph& graph) 
-	: Parent(graph) {}
-      EdgeMap(const Graph& graph, const _Value& value) 
-	: Parent(graph, value) {}
-    
-      EdgeMap& operator=(const EdgeMap& cmap) {
-	return operator=<EdgeMap>(cmap);
-      }
-    
-      template <typename CMap>
-      EdgeMap& operator=(const CMap& cmap) {
-        Parent::operator=(cmap);
-	return *this;
-      }
-    };
-        
-    template <typename _Value>
-    class UEdgeMap : public Graph::template EdgeMap<_Value> {
-    public:
-      
-      typedef typename Graph::template EdgeMap<_Value> Parent;
-      
-      explicit UEdgeMap(const Adaptor& ga) 
-	: Parent(*ga.graph) {}
-
-      UEdgeMap(const Adaptor& 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) {
-        Parent::operator=(cmap);
-        return *this;
-      }
-
-    };
-      
   };
 
-  ///\brief An undirected graph is made from a directed graph by an adaptor
-  ///\ingroup graph_adaptors
+
+  /// \brief An undirected graph is made from a directed graph by an adaptor
+  /// \ingroup graph_adaptors
   ///
   /// Undocumented, untested!!!
@@ -1324,11 +1236,8 @@
   /// \author Marton Makai
   template<typename _Graph>
-  class UndirGraphAdaptor : 
-    public UGraphAdaptorExtender<
-    UndirGraphAdaptorBase<_Graph> > {
+  class UndirGraphAdaptor : public AlterableUndirGraphAdaptor<_Graph> {
   public:
     typedef _Graph Graph;
-    typedef UGraphAdaptorExtender<
-      UndirGraphAdaptorBase<_Graph> > Parent;
+    typedef AlterableUndirGraphAdaptor<_Graph> Parent;
   protected:
     UndirGraphAdaptor() { }
@@ -1695,369 +1604,975 @@
   };
 
-//   template <typename _Graph>
-//   class SplitGraphAdaptorBase 
-//     : public GraphAdaptorBase<_Graph> {
-//   public:
-//     typedef GraphAdaptorBase<_Graph> Parent;
-
-//     class Node;
-//     class Edge;
-//     template <typename T> class NodeMap;
-//     template <typename T> class EdgeMap;
-    
-
-//     class Node : public Parent::Node {
-//       friend class SplitGraphAdaptorBase;
-//       template <typename T> friend class NodeMap;
-//       typedef typename Parent::Node NodeParent;
-//     private:
-
-//       bool entry;
-//       Node(typename Parent::Node _node, bool _entry)
-// 	: Parent::Node(_node), entry(_entry) {}
-      
-//     public:
-//       Node() {}
-//       Node(Invalid) : NodeParent(INVALID), entry(true) {}
-
-//       bool operator==(const Node& node) const {
-// 	return NodeParent::operator==(node) && entry == node.entry;
-//       }
-      
-//       bool operator!=(const Node& node) const {
-// 	return !(*this == node);
-//       }
-      
-//       bool operator<(const Node& node) const {
-// 	return NodeParent::operator<(node) || 
-// 	  (NodeParent::operator==(node) && entry < node.entry);
-//       }
-//     };
-
-//     /// \todo May we want VARIANT/union type
-//     class Edge : public Parent::Edge {
-//       friend class SplitGraphAdaptorBase;
-//       template <typename T> friend class EdgeMap;
-//     private:
-//       typedef typename Parent::Edge EdgeParent;
-//       typedef typename Parent::Node NodeParent;
-//       NodeParent bind;
-
-//       Edge(const EdgeParent& edge, const NodeParent& node)
-// 	: EdgeParent(edge), bind(node) {}
-//     public:
-//       Edge() {}
-//       Edge(Invalid) : EdgeParent(INVALID), bind(INVALID) {}
-
-//       bool operator==(const Edge& edge) const {
-// 	return EdgeParent::operator==(edge) && bind == edge.bind;
-//       }
-      
-//       bool operator!=(const Edge& edge) const {
-// 	return !(*this == edge);
-//       }
-      
-//       bool operator<(const Edge& edge) const {
-// 	return EdgeParent::operator<(edge) || 
-// 	  (EdgeParent::operator==(edge) && bind < edge.bind);
-//       }
-//     };
-
-//     void first(Node& node) const {
-//       Parent::first(node);
-//       node.entry = true;
-//     } 
-
-//     void next(Node& node) const {
-//       if (node.entry) {
-// 	node.entry = false;
-//       } else {
-// 	node.entry = true;
-// 	Parent::next(node);
-//       }
-//     }
-
-//     void first(Edge& edge) const {
-//       Parent::first(edge);
-//       if ((typename Parent::Edge&)edge == INVALID) {
-// 	Parent::first(edge.bind);
-//       } else {
-// 	edge.bind = INVALID;
-//       }
-//     }
-
-//     void next(Edge& edge) const {
-//       if ((typename Parent::Edge&)edge != INVALID) {
-// 	Parent::next(edge);
-// 	if ((typename Parent::Edge&)edge == INVALID) {
-// 	  Parent::first(edge.bind);
-// 	}
-//       } else {
-// 	Parent::next(edge.bind);
-//       }      
-//     }
-
-//     void firstIn(Edge& edge, const Node& node) const {
-//       if (node.entry) {
-// 	Parent::firstIn(edge, node);
-// 	edge.bind = INVALID;
-//       } else {
-// 	(typename Parent::Edge&)edge = INVALID;
-// 	edge.bind = node;
-//       }
-//     }
-
-//     void nextIn(Edge& edge) const {
-//       if ((typename Parent::Edge&)edge != INVALID) {
-// 	Parent::nextIn(edge);
-//       } else {
-// 	edge.bind = INVALID;
-//       }      
-//     }
-
-//     void firstOut(Edge& edge, const Node& node) const {
-//       if (!node.entry) {
-// 	Parent::firstOut(edge, node);
-// 	edge.bind = INVALID;
-//       } else {
-// 	(typename Parent::Edge&)edge = INVALID;
-// 	edge.bind = node;
-//       }
-//     }
-
-//     void nextOut(Edge& edge) const {
-//       if ((typename Parent::Edge&)edge != INVALID) {
-// 	Parent::nextOut(edge);
-//       } else {
-// 	edge.bind = INVALID;
-//       }
-//     }
-
-//     Node source(const Edge& edge) const {
-//       if ((typename Parent::Edge&)edge != INVALID) {
-// 	return Node(Parent::source(edge), false);
-//       } else {
-// 	return Node(edge.bind, true);
-//       }
-//     }
-
-//     Node target(const Edge& edge) const {
-//       if ((typename Parent::Edge&)edge != INVALID) {
-// 	return Node(Parent::target(edge), true);
-//       } else {
-// 	return Node(edge.bind, false);
-//       }
-//     }
-
-//     static bool entryNode(const Node& node) {
-//       return node.entry;
-//     }
-
-//     static bool exitNode(const Node& node) {
-//       return !node.entry;
-//     }
-
-//     static Node getEntry(const typename Parent::Node& node) {
-//       return Node(node, true);
-//     }
-
-//     static Node getExit(const typename Parent::Node& node) {
-//       return Node(node, false);
-//     }
-
-//     static bool originalEdge(const Edge& edge) {
-//       return (typename Parent::Edge&)edge != INVALID;
-//     }
-
-//     static bool bindingEdge(const Edge& edge) {
-//       return edge.bind != INVALID;
-//     }
-
-//     static Node getBindedNode(const Edge& edge) {
-//       return edge.bind;
-//     }
-
-//     int nodeNum() const {
-//       return Parent::nodeNum() * 2;
-//     }
-
-//     typedef True EdgeNumTag;
-    
-//     int edgeNum() const {
-//       return countEdges() + Parent::nodeNum();
-//     }
-
-//     Edge findEdge(const Node& source, const Node& target, 
-// 		  const Edge& prev = INVALID) const {
-//       if (exitNode(source) && entryNode(target)) {
-// 	return Parent::findEdge(source, target, prev);
-//       } else {
-// 	if (prev == INVALID && entryNode(source) && exitNode(target) && 
-// 	    (typename Parent::Node&)source == (typename Parent::Node&)target) {
-// 	  return Edge(INVALID, source);
-// 	} else {
-// 	  return INVALID;
-// 	}
-//       }
-//     }
-    
-//     template <typename T>
-//     class NodeMap : public MapBase<Node, T> {
-//       typedef typename Parent::template NodeMap<T> NodeImpl;
-//     public:
-//       NodeMap(const SplitGraphAdaptorBase& _graph) 
-// 	: entry(_graph), exit(_graph) {}
-//       NodeMap(const SplitGraphAdaptorBase& _graph, const T& t) 
-// 	: entry(_graph, t), exit(_graph, t) {}
-      
-//       void set(const Node& key, const T& val) {
-// 	if (key.entry) { entry.set(key, val); }
-// 	else {exit.set(key, val); }
-//       }
-      
-//       typename MapTraits<NodeImpl>::ReturnValue 
-//       operator[](const Node& key) {
-// 	if (key.entry) { return entry[key]; }
-// 	else { return exit[key]; }
-//       }
-
-//       typename MapTraits<NodeImpl>::ConstReturnValue
-//       operator[](const Node& key) const {
-// 	if (key.entry) { return entry[key]; }
-// 	else { return exit[key]; }
-//       }
-
-//     private:
-//       NodeImpl entry, exit;
-//     };
-
-//     template <typename T>
-//     class EdgeMap : public MapBase<Edge, T> {
-//       typedef typename Parent::template NodeMap<T> NodeImpl;
-//       typedef typename Parent::template EdgeMap<T> EdgeImpl;
-//     public:
-//       EdgeMap(const SplitGraphAdaptorBase& _graph) 
-// 	: bind(_graph), orig(_graph) {}
-//       EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t) 
-// 	: bind(_graph, t), orig(_graph, t) {}
-      
-//       void set(const Edge& key, const T& val) {
-// 	if ((typename Parent::Edge&)key != INVALID) { orig.set(key, val); }
-// 	else {bind.set(key.bind, val); }
-//       }
-      
-//       typename MapTraits<EdgeImpl>::ReturnValue
-//       operator[](const Edge& key) {
-// 	if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
-// 	else {return bind[key.bind]; }
-//       }
-
-//       typename MapTraits<EdgeImpl>::ConstReturnValue
-//       operator[](const Edge& key) const {
-// 	if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
-// 	else {return bind[key.bind]; }
-//       }
-
-//     private:
-//       typename Parent::template NodeMap<T> bind;
-//       typename Parent::template EdgeMap<T> orig;
-//     };
-
-//     template <typename EntryMap, typename ExitMap>
-//     class CombinedNodeMap : public MapBase<Node, typename EntryMap::Value> {
-//     public:
-//       typedef MapBase<Node, typename EntryMap::Value> Parent;
-
-//       typedef typename Parent::Key Key;
-//       typedef typename Parent::Value Value;
-
-//       CombinedNodeMap(EntryMap& _entryMap, ExitMap& _exitMap) 
-// 	: entryMap(_entryMap), exitMap(_exitMap) {}
-
-//       Value& operator[](const Key& key) {
-// 	if (key.entry) {
-// 	  return entryMap[key];
-// 	} else {
-// 	  return exitMap[key];
-// 	}
-//       }
-
-//       Value operator[](const Key& key) const {
-// 	if (key.entry) {
-// 	  return entryMap[key];
-// 	} else {
-// 	  return exitMap[key];
-// 	}
-//       }
-
-//       void set(const Key& key, const Value& value) {
-// 	if (key.entry) {
-// 	  entryMap.set(key, value);
-// 	} else {
-// 	  exitMap.set(key, value);
-// 	}
-//       }
-      
-//     private:
-      
-//       EntryMap& entryMap;
-//       ExitMap& exitMap;
-      
-//     };
-
-//     template <typename EdgeMap, typename NodeMap>
-//     class CombinedEdgeMap : public MapBase<Edge, typename EdgeMap::Value> {
-//     public:
-//       typedef MapBase<Edge, typename EdgeMap::Value> Parent;
-
-//       typedef typename Parent::Key Key;
-//       typedef typename Parent::Value Value;
-
-//       CombinedEdgeMap(EdgeMap& _edgeMap, NodeMap& _nodeMap) 
-// 	: edgeMap(_edgeMap), nodeMap(_nodeMap) {}
-
-//       void set(const Edge& edge, const Value& val) {
-// 	if (SplitGraphAdaptorBase::originalEdge(edge)) {
-// 	  edgeMap.set(edge, val);
-// 	} else {
-// 	  nodeMap.set(SplitGraphAdaptorBase::bindedNode(edge), val);
-// 	}
-//       }
-
-//       Value operator[](const Key& edge) const {
-// 	if (SplitGraphAdaptorBase::originalEdge(edge)) {
-// 	  return edgeMap[edge];
-// 	} else {
-// 	  return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
-// 	}
-//       }      
-
-//       Value& operator[](const Key& edge) {
-// 	if (SplitGraphAdaptorBase::originalEdge(edge)) {
-// 	  return edgeMap[edge];
-// 	} else {
-// 	  return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
-// 	}
-//       }      
-      
-//     private:
-//       EdgeMap& edgeMap;
-//       NodeMap& nodeMap;
-//     };
-
-//   };
-
-//   template <typename _Graph>
-//   class SplitGraphAdaptor 
-//     : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
-//   public:
-//     typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
-
-//     SplitGraphAdaptor(_Graph& graph) {
-//       Parent::setGraph(graph);
-//     }
-
-
-//   };
+  /// \brief Base class for split graph adaptor
+  ///
+  /// Base class of split graph adaptor. In most case you do not need to
+  /// use it directly but the documented member functions of this class can 
+  /// be used with the SplitGraphAdaptor class.
+  /// \sa SplitGraphAdaptor
+  template <typename _Graph>
+  class SplitGraphAdaptorBase 
+    : public GraphAdaptorBase<const _Graph> {
+  public:
+
+    typedef _Graph Graph;
+
+    typedef GraphAdaptorBase<const _Graph> Parent;
+
+    typedef typename Graph::Node GraphNode;
+    typedef typename Graph::Edge GraphEdge;
+
+    class Node;
+    class Edge;
+
+    template <typename T> class NodeMap;
+    template <typename T> class EdgeMap;
+    
+
+    class Node : public GraphNode {
+      friend class SplitGraphAdaptorBase;
+      template <typename T> friend class NodeMap;
+    private:
+
+      bool in_node;
+      Node(GraphNode _node, bool _in_node)
+	: GraphNode(_node), in_node(_in_node) {}
+      
+    public:
+
+      Node() {}
+      Node(Invalid) : GraphNode(INVALID), in_node(true) {}
+
+      bool operator==(const Node& node) const {
+	return GraphNode::operator==(node) && in_node == node.in_node;
+      }
+      
+      bool operator!=(const Node& node) const {
+	return !(*this == node);
+      }
+      
+      bool operator<(const Node& node) const {
+	return GraphNode::operator<(node) || 
+	  (GraphNode::operator==(node) && in_node < node.in_node);
+      }
+    };
+
+    class Edge {
+      friend class SplitGraphAdaptorBase;
+      template <typename T> friend class EdgeMap;
+    private:
+      typedef BiVariant<GraphEdge, GraphNode> EdgeImpl;
+
+      explicit Edge(const GraphEdge& edge) : item(edge) {}
+      explicit Edge(const GraphNode& node) : item(node) {}
+      
+      EdgeImpl item;
+
+    public:
+      Edge() {}
+      Edge(Invalid) : item(GraphEdge(INVALID)) {}
+
+      bool operator==(const Edge& edge) const {
+        if (item.firstState()) {
+          if (edge.item.firstState()) {
+            return item.first() == edge.item.first();
+          }
+        } else {
+          if (edge.item.secondState()) {
+            return item.second() == edge.item.second();
+          }
+        }
+        return false;
+      }
+      
+      bool operator!=(const Edge& edge) const {
+	return !(*this == edge);
+      }
+      
+      bool operator<(const Edge& edge) const {
+        if (item.firstState()) {
+          if (edge.item.firstState()) {
+            return item.first() < edge.item.first();
+          }
+          return false;
+        } else {
+          if (edge.item.secondState()) {
+            return item.second() < edge.item.second();
+          }
+          return true;
+        }
+      }
+
+      operator GraphEdge() const { return item.first(); }
+      operator GraphNode() const { return item.second(); }
+
+    };
+
+    void first(Node& node) const {
+      Parent::first(node);
+      node.in_node = true;
+    }
+
+    void next(Node& node) const {
+      if (node.in_node) {
+	node.in_node = false;
+      } else {
+	node.in_node = true;
+	Parent::next(node);
+      }
+    }
+
+    void first(Edge& edge) const {
+      edge.item.setSecond();
+      Parent::first(edge.item.second());
+      if (edge.item.second() == INVALID) {
+        edge.item.setFirst();
+	Parent::first(edge.item.first());
+      }
+    }
+
+    void next(Edge& edge) const {
+      if (edge.item.secondState()) {
+	Parent::next(edge.item.second());
+        if (edge.item.second() == INVALID) {
+          edge.item.setFirst();
+          Parent::first(edge.item.first());
+        }
+      } else {
+	Parent::next(edge.item.first());
+      }      
+    }
+
+    void firstOut(Edge& edge, const Node& node) const {
+      if (node.in_node) {
+        edge.item.setSecond(node);
+      } else {
+        edge.item.setFirst();
+	Parent::firstOut(edge.item.first(), node);
+      }
+    }
+
+    void nextOut(Edge& edge) const {
+      if (!edge.item.firstState()) {
+	edge.item.setFirst(INVALID);
+      } else {
+	Parent::nextOut(edge.item.first());
+      }      
+    }
+
+    void firstIn(Edge& edge, const Node& node) const {
+      if (!node.in_node) {
+        edge.item.setSecond(node);        
+      } else {
+        edge.item.setFirst();
+	Parent::firstIn(edge.item.first(), node);
+      }
+    }
+
+    void nextIn(Edge& edge) const {
+      if (!edge.item.firstState()) {
+	edge.item.setFirst(INVALID);
+      } else {
+	Parent::nextIn(edge.item.first());
+      }
+    }
+
+    Node source(const Edge& edge) const {
+      if (edge.item.firstState()) {
+	return Node(Parent::source(edge.item.first()), false);
+      } else {
+	return Node(edge.item.second(), true);
+      }
+    }
+
+    Node target(const Edge& edge) const {
+      if (edge.item.firstState()) {
+	return Node(Parent::target(edge.item.first()), true);
+      } else {
+	return Node(edge.item.second(), false);
+      }
+    }
+
+    int id(const Node& node) const {
+      return (Parent::id(node) << 1) | (node.in_node ? 0 : 1);
+    }
+    Node nodeFromId(int id) const {
+      return Node(Parent::nodeFromId(id >> 1), (id & 1) == 0);
+    }
+    int maxNodeId() const {
+      return 2 * Parent::maxNodeId() + 1;
+    }
+
+    int id(const Edge& edge) const {
+      if (edge.item.firstState()) {
+        return Parent::id(edge.item.first()) << 1;
+      } else {
+        return (Parent::id(edge.item.second()) << 1) | 1;
+      }
+    }
+    Edge edgeFromId(int id) const {
+      if ((id & 1) == 0) {
+        return Edge(Parent::edgeFromId(id >> 1));
+      } else {
+        return Edge(Parent::nodeFromId(id >> 1));
+      }
+    }
+    int maxEdgeId() const {
+      return std::max(Parent::maxNodeId() << 1, 
+                      (Parent::maxEdgeId() << 1) | 1);
+    }
+
+    /// \brief Returns true when the node is in-node.
+    ///
+    /// Returns true when the node is in-node.
+    static bool inNode(const Node& node) {
+      return node.in_node;
+    }
+
+    /// \brief Returns true when the node is out-node.
+    ///
+    /// Returns true when the node is out-node.
+    static bool outNode(const Node& node) {
+      return !node.in_node;
+    }
+
+    /// \brief Returns true when the edge is edge in the original graph.
+    ///
+    /// Returns true when the edge is edge in the original graph.
+    static bool origEdge(const Edge& edge) {
+      return edge.item.firstState();
+    }
+
+    /// \brief Returns true when the edge binds an in-node and an out-node.
+    ///
+    /// Returns true when the edge binds an in-node and an out-node.
+    static bool bindEdge(const Edge& edge) {
+      return edge.item.secondState();
+    }
+
+    /// \brief Gives back the in-node created from the \c node.
+    ///
+    /// Gives back the in-node created from the \c node.
+    static Node inNode(const GraphNode& node) {
+      return Node(node, true);
+    }
+
+    /// \brief Gives back the out-node created from the \c node.
+    ///
+    /// Gives back the out-node created from the \c node.
+    static Node outNode(const GraphNode& node) {
+      return Node(node, false);
+    }
+
+    /// \brief Gives back the edge binds the two part of the node.
+    /// 
+    /// Gives back the edge binds the two part of the node.
+    static Edge edge(const GraphNode& node) {
+      return Edge(node);
+    }
+
+    /// \brief Gives back the edge of the original edge.
+    /// 
+    /// Gives back the edge of the original edge.
+    static Edge edge(const GraphEdge& edge) {
+      return Edge(edge);
+    }
+
+    typedef True NodeNumTag;
+
+    int nodeNum() const {
+      return  2 * countNodes(*Parent::graph);
+    }
+
+    typedef True EdgeNumTag;
+    
+    int edgeNum() const {
+      return countEdges(*Parent::graph) + countNodes(*Parent::graph);
+    }
+
+    typedef True FindEdgeTag;
+
+    Edge findEdge(const Node& source, const Node& target, 
+		  const Edge& prev = INVALID) const {
+      if (inNode(source)) {
+        if (outNode(target)) {
+          if ((GraphNode&)source == (GraphNode&)target && prev == INVALID) {
+            return Edge(source);
+          }
+        }
+      } else {
+        if (inNode(target)) {
+          return Edge(findEdge(*Parent::graph, source, target, prev));
+        }
+      }
+      return INVALID;
+    }
+    
+    template <typename T>
+    class NodeMap : public MapBase<Node, T> {
+      typedef typename Parent::template NodeMap<T> NodeImpl;
+    public:
+      NodeMap(const SplitGraphAdaptorBase& _graph) 
+	: inNodeMap(_graph), outNodeMap(_graph) {}
+      NodeMap(const SplitGraphAdaptorBase& _graph, const T& t) 
+	: inNodeMap(_graph, t), outNodeMap(_graph, t) {}
+      
+      void set(const Node& key, const T& val) {
+	if (SplitGraphAdaptorBase::inNode(key)) { inNodeMap.set(key, val); }
+	else {outNodeMap.set(key, val); }
+      }
+      
+      typename MapTraits<NodeImpl>::ReturnValue 
+      operator[](const Node& key) {
+	if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; }
+	else { return outNodeMap[key]; }
+      }
+
+      typename MapTraits<NodeImpl>::ConstReturnValue
+      operator[](const Node& key) const {
+	if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; }
+	else { return outNodeMap[key]; }
+      }
+
+    private:
+      NodeImpl inNodeMap, outNodeMap;
+    };
+
+    template <typename T>
+    class EdgeMap : public MapBase<Edge, T> {
+      typedef typename Parent::template EdgeMap<T> EdgeMapImpl;
+      typedef typename Parent::template NodeMap<T> NodeMapImpl;
+    public:
+
+      EdgeMap(const SplitGraphAdaptorBase& _graph) 
+	: edge_map(_graph), node_map(_graph) {}
+      EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t) 
+	: edge_map(_graph, t), node_map(_graph, t) {}
+      
+      void set(const Edge& key, const T& val) {
+	if (SplitGraphAdaptorBase::origEdge(key)) { 
+          edge_map.set(key.item.first(), val); 
+        } else {
+          node_map.set(key.item.second(), val); 
+        }
+      }
+      
+      typename MapTraits<EdgeMapImpl>::ReturnValue
+      operator[](const Edge& key) {
+	if (SplitGraphAdaptorBase::origEdge(key)) { 
+          return edge_map[key.item.first()];
+        } else {
+          return node_map[key.item.second()];
+        }
+      }
+
+      typename MapTraits<EdgeMapImpl>::ConstReturnValue
+      operator[](const Edge& key) const {
+	if (SplitGraphAdaptorBase::origEdge(key)) { 
+          return edge_map[key.item.first()];
+        } else {
+          return node_map[key.item.second()];
+        }
+      }
+
+    private:
+      typename Parent::template EdgeMap<T> edge_map;
+      typename Parent::template NodeMap<T> node_map;
+    };
+
+
+  };
+
+  template <typename _Graph, typename NodeEnable = void, 
+            typename EdgeEnable = void>
+  class AlterableSplitGraphAdaptor 
+    : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
+  public:
+
+    typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
+    typedef _Graph Graph;
+
+    typedef typename Graph::Node GraphNode;
+    typedef typename Graph::Node GraphEdge;
+
+  protected:
+
+    AlterableSplitGraphAdaptor() : Parent() {}
+
+  public:
+    
+    typedef InvalidType NodeNotifier;
+    typedef InvalidType EdgeNotifier;
+
+  };
+
+  template <typename _Graph, typename EdgeEnable>
+  class AlterableSplitGraphAdaptor<
+    _Graph,
+    typename enable_if<typename _Graph::NodeNotifier::Notifier>::type,
+    EdgeEnable> 
+      : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
+  public:
+
+    typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
+    typedef _Graph Graph;
+
+    typedef typename Graph::Node GraphNode;
+    typedef typename Graph::Edge GraphEdge;
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+ 
+  protected:
+
+    AlterableSplitGraphAdaptor() 
+      : Parent(), node_notifier(*this), node_notifier_proxy(*this) {}
+
+    void setGraph(_Graph& graph) {
+      Parent::setGraph(graph);
+      node_notifier_proxy.setNotifier(graph.getNotifier(GraphNode()));
+    }
+
+  public:
+
+    ~AlterableSplitGraphAdaptor() {
+      node_notifier.clear();
+    }
+
+    typedef AlterationNotifier<AlterableSplitGraphAdaptor, Node> NodeNotifier;
+    typedef InvalidType EdgeNotifier;
+
+    NodeNotifier& getNotifier(Node) const { return node_notifier; }
+
+  protected:
+
+    class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase {
+    public:
+
+      typedef typename Graph::NodeNotifier::ObserverBase Parent;
+      typedef AlterableSplitGraphAdaptor AdaptorBase;
+      
+      NodeNotifierProxy(const AdaptorBase& _adaptor)
+        : Parent(), adaptor(&_adaptor) {
+      }
+
+      virtual ~NodeNotifierProxy() {
+        if (Parent::attached()) {
+          Parent::detach();
+        }
+      }
+
+      void setNotifier(typename Graph::NodeNotifier& graph_notifier) {
+        Parent::attach(graph_notifier);
+      }
+
+      
+    protected:
+
+      virtual void add(const GraphNode& gn) {
+        std::vector<Node> nodes;
+        nodes.push_back(AdaptorBase::Parent::inNode(gn));
+        nodes.push_back(AdaptorBase::Parent::outNode(gn));
+        adaptor->getNotifier(Node()).add(nodes);
+      }
+
+      virtual void add(const std::vector<GraphNode>& gn) {
+        std::vector<Node> nodes;
+        for (int i = 0; i < (int)gn.size(); ++i) {
+          nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
+          nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
+        }
+        adaptor->getNotifier(Node()).add(nodes);
+      }
+
+      virtual void erase(const GraphNode& gn) {
+        std::vector<Node> nodes;
+        nodes.push_back(AdaptorBase::Parent::inNode(gn));
+        nodes.push_back(AdaptorBase::Parent::outNode(gn));
+        adaptor->getNotifier(Node()).erase(nodes);
+      }
+
+      virtual void erase(const std::vector<GraphNode>& gn) {
+        std::vector<Node> nodes;
+        for (int i = 0; i < (int)gn.size(); ++i) {
+          nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
+          nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
+        }
+        adaptor->getNotifier(Node()).erase(nodes);
+      }
+      virtual void build() {
+        adaptor->getNotifier(Node()).build();
+      }
+      virtual void clear() {
+        adaptor->getNotifier(Node()).clear();
+      }
+
+      const AdaptorBase* adaptor;
+    };
+
+
+    mutable NodeNotifier node_notifier;
+
+    NodeNotifierProxy node_notifier_proxy;
+
+  };
+
+  template <typename _Graph>
+  class AlterableSplitGraphAdaptor<
+    _Graph,
+    typename enable_if<typename _Graph::NodeNotifier::Notifier>::type,
+    typename enable_if<typename _Graph::EdgeNotifier::Notifier>::type> 
+      : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
+  public:
+
+    typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
+    typedef _Graph Graph;
+
+    typedef typename Graph::Node GraphNode;
+    typedef typename Graph::Edge GraphEdge;
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+ 
+  protected:
+    
+    AlterableSplitGraphAdaptor() 
+      : Parent(), node_notifier(*this), edge_notifier(*this), 
+        node_notifier_proxy(*this), edge_notifier_proxy(*this) {}
+    
+    void setGraph(_Graph& graph) {
+      Parent::setGraph(graph);
+      node_notifier_proxy.setNotifier(graph.getNotifier(GraphNode()));
+      edge_notifier_proxy.setNotifier(graph.getNotifier(GraphEdge()));
+    }
+
+  public:
+
+    ~AlterableSplitGraphAdaptor() {
+      node_notifier.clear();
+      edge_notifier.clear();
+    }
+
+    typedef AlterationNotifier<AlterableSplitGraphAdaptor, Node> NodeNotifier;
+    typedef AlterationNotifier<AlterableSplitGraphAdaptor, Edge> EdgeNotifier;
+
+    NodeNotifier& getNotifier(Node) const { return node_notifier; }
+    EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
+
+  protected:
+
+    class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase {
+    public:
+      
+      typedef typename Graph::NodeNotifier::ObserverBase Parent;
+      typedef AlterableSplitGraphAdaptor AdaptorBase;
+      
+      NodeNotifierProxy(const AdaptorBase& _adaptor)
+        : Parent(), adaptor(&_adaptor) {
+      }
+
+      virtual ~NodeNotifierProxy() {
+        if (Parent::attached()) {
+          Parent::detach();
+        }
+      }
+
+      void setNotifier(typename Graph::NodeNotifier& graph_notifier) {
+        Parent::attach(graph_notifier);
+      }
+
+      
+    protected:
+
+      virtual void add(const GraphNode& gn) {
+        std::vector<Node> nodes;
+        nodes.push_back(AdaptorBase::Parent::inNode(gn));
+        nodes.push_back(AdaptorBase::Parent::outNode(gn));
+        adaptor->getNotifier(Node()).add(nodes);
+        adaptor->getNotifier(Edge()).add(AdaptorBase::Parent::edge(gn));
+      }
+      virtual void add(const std::vector<GraphNode>& gn) {
+        std::vector<Node> nodes;
+        std::vector<Edge> edges;
+        for (int i = 0; i < (int)gn.size(); ++i) {
+          edges.push_back(AdaptorBase::Parent::edge(gn[i]));
+          nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
+          nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
+        }
+        adaptor->getNotifier(Node()).add(nodes);
+        adaptor->getNotifier(Edge()).add(edges);
+      }
+      virtual void erase(const GraphNode& gn) {
+        adaptor->getNotifier(Edge()).erase(AdaptorBase::Parent::edge(gn));
+        std::vector<Node> nodes;
+        nodes.push_back(AdaptorBase::Parent::inNode(gn));
+        nodes.push_back(AdaptorBase::Parent::outNode(gn));
+        adaptor->getNotifier(Node()).erase(nodes);
+      }
+      virtual void erase(const std::vector<GraphNode>& gn) {
+        std::vector<Node> nodes;
+        std::vector<Edge> edges;
+        for (int i = 0; i < (int)gn.size(); ++i) {
+          edges.push_back(AdaptorBase::Parent::edge(gn[i]));
+          nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
+          nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
+        }
+        adaptor->getNotifier(Edge()).erase(edges);
+        adaptor->getNotifier(Node()).erase(nodes);
+      }
+      virtual void build() {
+        std::vector<Edge> edges;
+        const typename Parent::Notifier* notifier = Parent::getNotifier();
+        GraphNode it;
+        for (notifier->first(it); it != INVALID; notifier->next(it)) {
+          edges.push_back(AdaptorBase::Parent::edge(it));
+        }
+        adaptor->getNotifier(Node()).build();
+        adaptor->getNotifier(Edge()).add(edges);        
+      }
+      virtual void clear() {
+        std::vector<Edge> edges;
+        const typename Parent::Notifier* notifier = Parent::getNotifier();
+        GraphNode it;
+        for (notifier->first(it); it != INVALID; notifier->next(it)) {
+          edges.push_back(AdaptorBase::Parent::edge(it));
+        }
+        adaptor->getNotifier(Edge()).erase(edges);        
+        adaptor->getNotifier(Node()).clear();
+      }
+
+      const AdaptorBase* adaptor;
+    };
+
+    class EdgeNotifierProxy : public Graph::EdgeNotifier::ObserverBase {
+    public:
+
+      typedef typename Graph::EdgeNotifier::ObserverBase Parent;
+      typedef AlterableSplitGraphAdaptor AdaptorBase;
+      
+      EdgeNotifierProxy(const AdaptorBase& _adaptor)
+        : Parent(), adaptor(&_adaptor) {
+      }
+
+      virtual ~EdgeNotifierProxy() {
+        if (Parent::attached()) {
+          Parent::detach();
+        }
+      }
+
+      void setNotifier(typename Graph::EdgeNotifier& graph_notifier) {
+        Parent::attach(graph_notifier);
+      }
+
+      
+    protected:
+
+      virtual void add(const GraphEdge& ge) {
+        adaptor->getNotifier(Edge()).add(AdaptorBase::edge(ge));
+      }
+      virtual void add(const std::vector<GraphEdge>& ge) {
+        std::vector<Edge> edges;
+        for (int i = 0; i < (int)ge.size(); ++i) {
+          edges.push_back(AdaptorBase::edge(ge[i]));
+        }
+        adaptor->getNotifier(Edge()).add(edges);
+      }
+      virtual void erase(const GraphEdge& ge) {
+        adaptor->getNotifier(Edge()).erase(AdaptorBase::edge(ge));
+      }
+      virtual void erase(const std::vector<GraphEdge>& ge) {
+        std::vector<Edge> edges;
+        for (int i = 0; i < (int)ge.size(); ++i) {
+          edges.push_back(AdaptorBase::edge(ge[i]));
+        }
+        adaptor->getNotifier(Edge()).erase(edges);
+      }
+      virtual void build() {
+        std::vector<Edge> edges;
+        const typename Parent::Notifier* notifier = Parent::getNotifier();
+        GraphEdge it;
+        for (notifier->first(it); it != INVALID; notifier->next(it)) {
+          edges.push_back(AdaptorBase::Parent::edge(it));
+        }
+        adaptor->getNotifier(Edge()).add(edges);
+      }
+      virtual void clear() {
+        std::vector<Edge> edges;
+        const typename Parent::Notifier* notifier = Parent::getNotifier();
+        GraphEdge it;
+        for (notifier->first(it); it != INVALID; notifier->next(it)) {
+          edges.push_back(AdaptorBase::Parent::edge(it));
+        }
+        adaptor->getNotifier(Edge()).erase(edges);
+      }
+
+      const AdaptorBase* adaptor;
+    };
+
+
+    mutable NodeNotifier node_notifier;
+    mutable EdgeNotifier edge_notifier;
+
+    NodeNotifierProxy node_notifier_proxy;
+    EdgeNotifierProxy edge_notifier_proxy;
+
+  };
+
+  /// \ingroup graph_adaptors
+  ///
+  /// \brief SplitGraphAdaptor class
+  /// 
+  /// This is an graph adaptor which splits all node into an in-node
+  /// and an out-node. Formaly, the adaptor replaces each \f$ u \f$
+  /// node in the graph with two node, \f$ u_{in} \f$ node and 
+  /// \f$ u_{out} \f$ node. If there is an \f$ (v, u) \f$ edge in the 
+  /// original graph the new target of the edge will be \f$ u_{in} \f$ and
+  /// similarly the source of the original \f$ (u, v) \f$ edge will be
+  /// \f$ u_{out} \f$.  The adaptor will add for each node in the 
+  /// original graph an additional edge which will connect 
+  /// \f$ (u_{in}, u_{out}) \f$.
+  ///
+  /// The aim of this class is to run algorithm with node costs if the 
+  /// algorithm can use directly just edge costs. In this case we should use
+  /// a \c SplitGraphAdaptor and set the node cost of the graph to the
+  /// bind edge in the adapted graph.
+  /// 
+  /// By example a maximum flow algoritm can compute how many edge
+  /// disjoint paths are in the graph. But we would like to know how
+  /// many node disjoint paths are in the graph. First we have to
+  /// adapt the graph with the \c SplitGraphAdaptor. Then run the flow
+  /// algorithm on the adapted graph. The bottleneck of the flow will
+  /// be the bind edges which bounds the flow with the count of the
+  /// node disjoint paths.
+  ///
+  ///\code
+  ///
+  /// typedef SplitGraphAdaptor<SmartGraph> SGraph;
+  ///
+  /// SGraph sgraph(graph);
+  ///
+  /// typedef ConstMap<SGraph::Edge, int> SCapacity;
+  /// SCapacity scapacity(1);
+  ///
+  /// SGraph::EdgeMap<int> sflow(sgraph);
+  ///
+  /// Preflow<SGraph, int, SCapacity> 
+  ///   spreflow(sgraph, SGraph::outNode(source),SGraph::inNode(target),  
+  ///            scapacity, sflow);
+  ///                                            
+  /// spreflow.run();
+  ///
+  ///\endcode
+  ///
+  /// The result of the mamixum flow on the original graph
+  /// shows the next figure:
+  ///
+  /// \image html edge_disjoint.png
+  /// \image latex edge_disjoint.eps "Edge disjoint paths" width=\textwidth
+  /// 
+  /// And the maximum flow on the adapted graph:
+  ///
+  /// \image html node_disjoint.png
+  /// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth
+  ///
+  /// The second solution contains just 3 disjoint paths while the first 4.
+  ///
+  /// This graph adaptor is fully conform to the 
+  /// \ref concept::StaticGraph "StaticGraph" concept and
+  /// contains some additional member functions and types. The 
+  /// documentation of some member functions may be found just in the
+  /// SplitGraphAdaptorBase class.
+  ///
+  /// \sa SplitGraphAdaptorBase
+  template <typename _Graph>
+  class SplitGraphAdaptor : public AlterableSplitGraphAdaptor<_Graph> {
+  public:
+    typedef AlterableSplitGraphAdaptor<_Graph> Parent;
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+
+    /// \brief Constructor of the adaptor.
+    ///
+    /// Constructor of the adaptor.
+    SplitGraphAdaptor(_Graph& graph) {
+      Parent::setGraph(graph);
+    }
+
+    /// \brief NodeMap combined from two original NodeMap
+    ///
+    /// This class adapt two of the original graph NodeMap to
+    /// get a node map on the adapted graph.
+    template <typename InNodeMap, typename OutNodeMap>
+    class CombinedNodeMap {
+    public:
+
+      typedef Node Key;
+      typedef typename InNodeMap::Value Value;
+
+      /// \brief Constructor
+      ///
+      /// Constructor.
+      CombinedNodeMap(InNodeMap& _inNodeMap, OutNodeMap& _outNodeMap) 
+	: inNodeMap(_inNodeMap), outNodeMap(_outNodeMap) {}
+
+      /// \brief The subscript operator.
+      ///
+      /// The subscript operator.
+      Value& operator[](const Key& key) {
+	if (Parent::inNode(key)) {
+	  return inNodeMap[key];
+	} else {
+	  return outNodeMap[key];
+	}
+      }
+
+      /// \brief The const subscript operator.
+      ///
+      /// The const subscript operator.
+      Value operator[](const Key& key) const {
+	if (Parent::inNode(key)) {
+	  return inNodeMap[key];
+	} else {
+	  return outNodeMap[key];
+	}
+      }
+
+      /// \brief The setter function of the map.
+      /// 
+      /// The setter function of the map.
+      void set(const Key& key, const Value& value) {
+	if (Parent::inNode(key)) {
+	  inNodeMap.set(key, value);
+	} else {
+	  outNodeMap.set(key, value);
+	}
+      }
+      
+    private:
+      
+      InNodeMap& inNodeMap;
+      OutNodeMap& outNodeMap;
+      
+    };
+
+
+    /// \brief Just gives back a combined node map.
+    /// 
+    /// Just gives back a combined node map.
+    template <typename InNodeMap, typename OutNodeMap>
+    static CombinedNodeMap<InNodeMap, OutNodeMap> 
+    combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
+      return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
+    }
+
+    template <typename InNodeMap, typename OutNodeMap>
+    static CombinedNodeMap<const InNodeMap, OutNodeMap> 
+    combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
+      return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
+    }
+
+    template <typename InNodeMap, typename OutNodeMap>
+    static CombinedNodeMap<InNodeMap, const OutNodeMap> 
+    combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
+      return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
+    }
+
+    template <typename InNodeMap, typename OutNodeMap>
+    static CombinedNodeMap<const InNodeMap, const OutNodeMap> 
+    combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
+      return CombinedNodeMap<const InNodeMap, 
+        const OutNodeMap>(in_map, out_map);
+    }
+
+    /// \brief EdgeMap combined from an original EdgeMap and NodeMap
+    ///
+    /// This class adapt an original graph EdgeMap and NodeMap to
+    /// get an edge map on the adapted graph.
+    template <typename GraphEdgeMap, typename GraphNodeMap>
+    class CombinedEdgeMap 
+      : public MapBase<Edge, typename GraphEdgeMap::Value> {
+    public:
+      typedef MapBase<Edge, typename GraphEdgeMap::Value> Parent;
+
+      typedef typename Parent::Key Key;
+      typedef typename Parent::Value Value;
+
+      /// \brief Constructor
+      ///
+      /// Constructor.
+      CombinedEdgeMap(GraphEdgeMap& _edge_map, GraphNodeMap& _node_map) 
+	: edge_map(_edge_map), node_map(_node_map) {}
+
+      /// \brief The subscript operator.
+      ///
+      /// The subscript operator.
+      void set(const Edge& edge, const Value& val) {
+	if (Parent::origEdge(edge)) {
+	  edge_map.set(edge, val);
+	} else {
+	  node_map.set(edge, val);
+	}
+      }
+
+      /// \brief The const subscript operator.
+      ///
+      /// The const subscript operator.
+      Value operator[](const Key& edge) const {
+	if (Parent::origEdge(edge)) {
+	  return edge_map[edge];
+	} else {
+	  return node_map[edge];
+	}
+      }      
+
+      /// \brief The const subscript operator.
+      ///
+      /// The const subscript operator.
+      Value& operator[](const Key& edge) {
+	if (Parent::origEdge(edge)) {
+	  return edge_map[edge];
+	} else {
+	  return node_map[edge];
+	}
+      }      
+      
+    private:
+      GraphEdgeMap& edge_map;
+      GraphNodeMap& node_map;
+    };
+                    
+    /// \brief Just gives back a combined edge map.
+    /// 
+    /// Just gives back a combined edge map.
+    template <typename GraphEdgeMap, typename GraphNodeMap>
+    static CombinedEdgeMap<GraphEdgeMap, GraphNodeMap> 
+    combinedEdgeMap(GraphEdgeMap& edge_map, GraphNodeMap& node_map) {
+      return CombinedEdgeMap<GraphEdgeMap, GraphNodeMap>(edge_map, node_map);
+    }
+
+    template <typename GraphEdgeMap, typename GraphNodeMap>
+    static CombinedEdgeMap<const GraphEdgeMap, GraphNodeMap> 
+    combinedEdgeMap(const GraphEdgeMap& edge_map, GraphNodeMap& node_map) {
+      return CombinedEdgeMap<const GraphEdgeMap, 
+        GraphNodeMap>(edge_map, node_map);
+    }
+
+    template <typename GraphEdgeMap, typename GraphNodeMap>
+    static CombinedEdgeMap<GraphEdgeMap, const GraphNodeMap> 
+    combinedEdgeMap(GraphEdgeMap& edge_map, const GraphNodeMap& node_map) {
+      return CombinedEdgeMap<GraphEdgeMap, 
+        const GraphNodeMap>(edge_map, node_map);
+    }
+
+    template <typename GraphEdgeMap, typename GraphNodeMap>
+    static CombinedEdgeMap<const GraphEdgeMap, const GraphNodeMap> 
+    combinedEdgeMap(const GraphEdgeMap& edge_map, 
+                    const GraphNodeMap& node_map) {
+      return CombinedEdgeMap<const GraphEdgeMap, 
+        const GraphNodeMap>(edge_map, node_map);
+    }
+
+  };
+
 
 } //namespace lemon
