Index: lemon/graph_utils.h
===================================================================
--- lemon/graph_utils.h	(revision 1506)
+++ lemon/graph_utils.h	(revision 1515)
@@ -483,4 +483,6 @@
     }
 
+  protected:
+
     /// \brief Add a new key to the map.
     ///
@@ -598,4 +600,6 @@
     }
 
+  protected:
+
     /// \brief Add a new key to the map.
     ///
@@ -773,5 +777,5 @@
 
   /// \brief Returns a \ref TargetMap class
-
+  ///
   /// This function just returns an \ref TargetMap class.
   /// \relates TargetMap
@@ -814,5 +818,5 @@
 
   /// \brief Returns a \ref ForwardMap class
-
+  ///
   /// This function just returns an \ref ForwardMap class.
   /// \relates ForwardMap
@@ -862,41 +866,68 @@
   }
 
-
-
-  /// Map of the node in-degrees.
-
-  ///This map returns the in-degree of a node. Ones it is constructed,
-  ///the degrees are stored in a standard NodeMap, so each query is done
-  ///in constant time. On the other hand, the values updates automatically
-  ///whenever the graph changes.
-  ///
-  ///\sa OutDegMap
   template <typename _Graph>
-  class InDegMap  :
-    protected _Graph::template NodeMap<int>,
-    protected AlterationNotifier<typename _Graph::Edge>::ObserverBase
-  {
-    const _Graph& graph;
-  public:
+  class DegMapBase {
+  public:
+    
+    typedef _Graph Graph;
+
+  protected:
+
+    typedef typename Graph::template NodeMap<int> IntNodeMap;
+    
+  };
+
+  /// \brief Map of the node in-degrees.
+  ///
+  /// This map returns the in-degree of a node. Ones it is constructed,
+  /// the degrees are stored in a standard NodeMap, so each query is done
+  /// in constant time. On the other hand, the values updates automatically
+  /// whenever the graph changes.
+  ///
+  /// \sa OutDegMap
+
+  template <typename _Graph>
+  class InDegMap  
+    : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
+
+  public:
+    
+    typedef _Graph Graph;
     typedef int Value;
-    typedef typename _Graph::Node Key;
+    typedef typename Graph::Node Key;
+
+  private:
+
+    class AutoNodeMap : public Graph::template NodeMap<int> {
+    public:
+
+      typedef typename Graph::template NodeMap<int> Parent;
+
+      typedef typename Parent::Key Key;
+      typedef typename Parent::Value Value;
+      
+      AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
+      
+      void add(const Key& key) {
+	Parent::add(key);
+	Parent::set(key, 0);
+      }
+    };
+
+  public:
 
     /// \brief Constructor.
     ///
     /// Constructor for creating in-degree map.
-    InDegMap(const _Graph& _graph) :
-      _Graph::template NodeMap<int>(_graph,0),
-      graph(_graph)
-    {
+    InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
       AlterationNotifier<typename _Graph::Edge>
 	::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
-
-      for(typename _Graph::NodeIt n(graph);n!=INVALID;++n)
-	for(typename _Graph::InEdgeIt e(graph,n);e!=INVALID;++e)
-	  _Graph::template NodeMap<int>::operator[](graph.target(e))++;
-    }
-
-    virtual ~InDegMap() 
-    {
+      
+      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
+	deg[it] = countInEdges(graph, it);
+      }
+    }
+
+    virtual ~InDegMap() {
       AlterationNotifier<typename _Graph::Edge>::
 	ObserverBase::detach();
@@ -904,73 +935,91 @@
     
     /// Gives back the in-degree of a Node.
-    int operator[](const Key& k) const {
-      return _Graph::template NodeMap<int>::operator[](k);
+    int operator[](const Key& key) const {
+      return deg[key];
     }
 
   protected:
-    virtual void add(const typename _Graph::Node& n) {
-      _Graph::template NodeMap<int>::add(n);
-       _Graph::template NodeMap<int>::operator[](n)=0;
-    }
-    virtual void erase(const typename _Graph::Node&n) 
-    {
-      _Graph::template NodeMap<int>::erase(n);
-    }
-    virtual void add(const typename _Graph::Edge& e) {
-      _Graph::template NodeMap<int>::operator[](graph.target(e))++;
-    }
-    virtual void erase(const typename _Graph::Edge& e) {
-      _Graph::template NodeMap<int>::operator[](graph.target(e))--;
-    }
-
-    ///\e
-    
-    ///\bug Unimplemented
-    ///
-    virtual void build() {}
-    ///\e
-    
-    ///\bug Unimplemented
-    ///
-    virtual void clear() {}
-
-  };
-
-
-  /// Map of the node out-degrees.
-
-  ///This map returns the out-degree of a node. One it is constructed,
-  ///the degrees are stored in a standard NodeMap, so each query is done
-  ///in constant time. On the other hand, the values updates automatically
-  ///whenever the graph changes.
-  ///
-  ///\sa OutDegMap
+    
+    typedef typename Graph::Edge Edge;
+
+    virtual void add(const Edge& edge) {
+      ++deg[graph.target(edge)];
+    }
+
+    virtual void erase(const Edge& edge) {
+      --deg[graph.target(edge)];
+    }
+
+
+    virtual void build() {
+      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
+	deg[it] = countInEdges(graph, it);
+      }      
+    }
+
+    virtual void clear() {
+      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
+	deg[it] = 0;
+      }
+    }
+  private:
+    
+    const _Graph& graph;
+    AutoNodeMap deg;
+  };
+
+
+  /// \brief Map of the node out-degrees.
+  ///
+  /// This map returns the out-degree of a node. One it is constructed,
+  /// the degrees are stored in a standard NodeMap, so each query is done
+  /// in constant time. On the other hand, the values updates automatically
+  /// whenever the graph changes.
+  ///
+  /// \sa OutDegMap
+
   template <typename _Graph>
-  class OutDegMap  :
-    protected _Graph::template NodeMap<int>,
-    protected AlterationNotifier<typename _Graph::Edge>::ObserverBase
-  {
-    const _Graph& graph;
-  public:
+  class OutDegMap  
+    : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
+
+  public:
+    
+    typedef _Graph Graph;
     typedef int Value;
-    typedef typename _Graph::Node Key;
+    typedef typename Graph::Node Key;
+
+  private:
+
+    class AutoNodeMap : public Graph::template NodeMap<int> {
+    public:
+
+      typedef typename Graph::template NodeMap<int> Parent;
+
+      typedef typename Parent::Key Key;
+      typedef typename Parent::Value Value;
+      
+      AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
+      
+      void add(const Key& key) {
+	Parent::add(key);
+	Parent::set(key, 0);
+      }
+    };
+
+  public:
 
     /// \brief Constructor.
     ///
     /// Constructor for creating out-degree map.
-    OutDegMap(const _Graph& _graph) :
-      _Graph::template NodeMap<int>(_graph,0),
-      graph(_graph)
-    {
+    OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
       AlterationNotifier<typename _Graph::Edge>
 	::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
-
-      for(typename _Graph::NodeIt n(graph);n!=INVALID;++n)
-	for(typename _Graph::InEdgeIt e(graph,n);e!=INVALID;++e)
-	  _Graph::template NodeMap<int>::operator[](graph.source(e))++;
-    }
-
-    ~OutDegMap() 
-    {
+      
+      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
+	deg[it] = countOutEdges(graph, it);
+      }
+    }
+
+    virtual ~OutDegMap() {
       AlterationNotifier<typename _Graph::Edge>::
 	ObserverBase::detach();
@@ -978,39 +1027,37 @@
     
     /// Gives back the in-degree of a Node.
-    int operator[](const Key& k) const {
-      return _Graph::template NodeMap<int>::operator[](k);
+    int operator[](const Key& key) const {
+      return deg[key];
     }
 
   protected:
-    virtual void add(const typename _Graph::Node& n) {
-      _Graph::template NodeMap<int>::add(n);
-       _Graph::template NodeMap<int>::operator[](n)=0;
-    }
-    virtual void erase(const typename _Graph::Node&n) 
-    {
-      _Graph::template NodeMap<int>::erase(n);
-    }
-    virtual void add(const typename _Graph::Edge& e) {
-      _Graph::template NodeMap<int>::operator[](graph.source(e))++;
-    }
-    virtual void erase(const typename _Graph::Edge& e) {
-      _Graph::template NodeMap<int>::operator[](graph.source(e))--;
-    }
-
-    ///\e
-    
-    ///\bug Unimplemented
-    ///
-    virtual void build() {}
-    ///\e
-    
-    ///\bug Unimplemented
-    ///
-    virtual void clear() {}
-
-  };
-
-
-
+    
+    typedef typename Graph::Edge Edge;
+
+    virtual void add(const Edge& edge) {
+      ++deg[graph.source(edge)];
+    }
+
+    virtual void erase(const Edge& edge) {
+      --deg[graph.source(edge)];
+    }
+
+
+    virtual void build() {
+      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
+	deg[it] = countOutEdges(graph, it);
+      }      
+    }
+
+    virtual void clear() {
+      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
+	deg[it] = 0;
+      }
+    }
+  private:
+    
+    const _Graph& graph;
+    AutoNodeMap deg;
+  };
 
   /// @}
