# HG changeset patch
# User alpar
# Date 1118248561 0
# Node ID 08c8db58080ee13cca8e73bcff5218baa37edd1d
# Parent  9a9acf30dbae996c4610e62a0f949d8224877766
InDegMap added

diff -r 9a9acf30dbae -r 08c8db58080e lemon/graph_utils.h
--- a/lemon/graph_utils.h	Wed Jun 08 16:12:29 2005 +0000
+++ b/lemon/graph_utils.h	Wed Jun 08 16:36:01 2005 +0000
@@ -854,6 +854,74 @@
   }
 
 
+
+  /* ***************************************************************** */
+
+  /// Provides O(1) time node-degree queries.
+
+  ///\todo Undocumented
+  ///
+  template <typename _Graph>
+  class InDegMap  :
+    protected _Graph::AlterationNotifier<typename _Graph::Node>::
+    ObserverBase,
+    protected _Graph::AlterationNotifier<typename _Graph::Edge>::
+    ObserverBase
+  {
+    typename _Graph::template NodeMap<int> deg;
+    const _Graph* graph;
+  public:
+    typedef int Value;
+    typedef typename _Graph::Node Key;
+
+    /// \brief Constructor.
+    ///
+    /// Constructor for creating in-degree map.
+    InDegMap(const _Graph& _graph) : graph(_graph), deg(graph,0)
+    {
+      typename _Graph::AlterationNotifier<typename _Graph::Node>::ObserverBase::
+	attach(graph->getNotifier(typename _Graph::Node()));
+      typename _Graph::AlterationNotifier<typename _Graph::Edge>::ObserverBase::
+	attach(graph->getNotifier(typename _Graph::Edge()));
+
+      for(typename _Graph::NodeIt n(g);n!=INVALID;++n)
+	for(typename _Graph::InEdgeIt e(g,n);e!=INVALID;++e)
+	  deg[e]++;
+    }
+
+    ~InDegMap() 
+    {
+      typename _Graph::AlterationNotifier<typename _Graph::Node>::
+	ObserverBase::detach();
+      typename _Graph::AlterationNotifier<typename _Graph::Edge>::
+	ObserverBase::detach();
+    }
+    
+    /// Gives back the in degree of a Node.
+    int operator[](const Key& k) const { return deg[k];}
+
+  protected:
+    virtual void add(const typename _Graph::Node& n) {
+      ///\bug Which 'add' comes before to other?
+      deg[n]=0;
+    };
+    virtual void erase(const typename _Graph::Node&) 
+    {
+    }
+    virtual void add(const typename _Graph::Edge& n) {
+      deg[graph.target(e)]++;
+    };
+    virtual void erase(const typename _Graph::Edge&) 
+    {
+      deg[graph.target(e)]--;
+    }
+
+
+  };
+
+
+
+
   /// @}
 
 } //END OF NAMESPACE LEMON