# HG changeset patch
# User deba
# Date 1119869377 0
# Node ID dd7616b513338f4a2bb0282c256f395eed2f45fb
# Parent  c9b9bc63db4eb419a4a05022fa5d7fbfc8246bae
InDegMap and OutDegMap fixed

diff -r c9b9bc63db4e -r dd7616b51333 lemon/graph_utils.h
--- a/lemon/graph_utils.h	Fri Jun 24 21:03:08 2005 +0000
+++ b/lemon/graph_utils.h	Mon Jun 27 10:49:37 2005 +0000
@@ -482,6 +482,8 @@
       return Map::operator[](key);
     }
 
+  protected:
+
     /// \brief Add a new key to the map.
     ///
     /// Add a new key to the map. It is called by the
@@ -597,6 +599,8 @@
       build();
     }
 
+  protected:
+
     /// \brief Add a new key to the map.
     ///
     /// Add a new key to the map. It is called by the
@@ -772,7 +776,7 @@
   };
 
   /// \brief Returns a \ref TargetMap class
-
+  ///
   /// This function just returns an \ref TargetMap class.
   /// \relates TargetMap
   template <typename Graph>
@@ -813,7 +817,7 @@
   };
 
   /// \brief Returns a \ref ForwardMap class
-
+  ///
   /// This function just returns an \ref ForwardMap class.
   /// \relates ForwardMap
   template <typename Graph>
@@ -861,158 +865,201 @@
     return BackwardMap<Graph>(graph);
   }
 
+  template <typename _Graph>
+  class DegMapBase {
+  public:
+    
+    typedef _Graph Graph;
 
+  protected:
 
-  /// Map of the node in-degrees.
+    typedef typename Graph::template NodeMap<int> IntNodeMap;
+    
+  };
 
-  ///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.
+  /// \brief Map of the node in-degrees.
   ///
-  ///\sa OutDegMap
+  /// 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;
+  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))++;
+      
+      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
+	deg[it] = countInEdges(graph, it);
+      }
     }
 
-    virtual ~InDegMap() 
-    {
+    virtual ~InDegMap() {
       AlterationNotifier<typename _Graph::Edge>::
 	ObserverBase::detach();
     }
     
     /// 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))--;
+    
+    typedef typename Graph::Edge Edge;
+
+    virtual void add(const Edge& edge) {
+      ++deg[graph.target(edge)];
     }
 
-    ///\e
+    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:
     
-    ///\bug Unimplemented
-    ///
-    virtual void build() {}
-    ///\e
-    
-    ///\bug Unimplemented
-    ///
-    virtual void clear() {}
-
+    const _Graph& graph;
+    AutoNodeMap deg;
   };
 
 
-  /// Map of the node out-degrees.
+  /// \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
 
-  ///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;
+  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))++;
+      
+      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
+	deg[it] = countOutEdges(graph, it);
+      }
     }
 
-    ~OutDegMap() 
-    {
+    virtual ~OutDegMap() {
       AlterationNotifier<typename _Graph::Edge>::
 	ObserverBase::detach();
     }
     
     /// 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))--;
+    
+    typedef typename Graph::Edge Edge;
+
+    virtual void add(const Edge& edge) {
+      ++deg[graph.source(edge)];
     }
 
-    ///\e
+    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:
     
-    ///\bug Unimplemented
-    ///
-    virtual void build() {}
-    ///\e
-    
-    ///\bug Unimplemented
-    ///
-    virtual void clear() {}
-
+    const _Graph& graph;
+    AutoNodeMap deg;
   };
 
-
-
-
   /// @}
 
 } //END OF NAMESPACE LEMON