1.1 --- a/lemon/graph_utils.h	Wed Jun 08 16:12:29 2005 +0000
     1.2 +++ b/lemon/graph_utils.h	Wed Jun 08 16:36:01 2005 +0000
     1.3 @@ -854,6 +854,74 @@
     1.4    }
     1.5  
     1.6  
     1.7 +
     1.8 +  /* ***************************************************************** */
     1.9 +
    1.10 +  /// Provides O(1) time node-degree queries.
    1.11 +
    1.12 +  ///\todo Undocumented
    1.13 +  ///
    1.14 +  template <typename _Graph>
    1.15 +  class InDegMap  :
    1.16 +    protected _Graph::AlterationNotifier<typename _Graph::Node>::
    1.17 +    ObserverBase,
    1.18 +    protected _Graph::AlterationNotifier<typename _Graph::Edge>::
    1.19 +    ObserverBase
    1.20 +  {
    1.21 +    typename _Graph::template NodeMap<int> deg;
    1.22 +    const _Graph* graph;
    1.23 +  public:
    1.24 +    typedef int Value;
    1.25 +    typedef typename _Graph::Node Key;
    1.26 +
    1.27 +    /// \brief Constructor.
    1.28 +    ///
    1.29 +    /// Constructor for creating in-degree map.
    1.30 +    InDegMap(const _Graph& _graph) : graph(_graph), deg(graph,0)
    1.31 +    {
    1.32 +      typename _Graph::AlterationNotifier<typename _Graph::Node>::ObserverBase::
    1.33 +	attach(graph->getNotifier(typename _Graph::Node()));
    1.34 +      typename _Graph::AlterationNotifier<typename _Graph::Edge>::ObserverBase::
    1.35 +	attach(graph->getNotifier(typename _Graph::Edge()));
    1.36 +
    1.37 +      for(typename _Graph::NodeIt n(g);n!=INVALID;++n)
    1.38 +	for(typename _Graph::InEdgeIt e(g,n);e!=INVALID;++e)
    1.39 +	  deg[e]++;
    1.40 +    }
    1.41 +
    1.42 +    ~InDegMap() 
    1.43 +    {
    1.44 +      typename _Graph::AlterationNotifier<typename _Graph::Node>::
    1.45 +	ObserverBase::detach();
    1.46 +      typename _Graph::AlterationNotifier<typename _Graph::Edge>::
    1.47 +	ObserverBase::detach();
    1.48 +    }
    1.49 +    
    1.50 +    /// Gives back the in degree of a Node.
    1.51 +    int operator[](const Key& k) const { return deg[k];}
    1.52 +
    1.53 +  protected:
    1.54 +    virtual void add(const typename _Graph::Node& n) {
    1.55 +      ///\bug Which 'add' comes before to other?
    1.56 +      deg[n]=0;
    1.57 +    };
    1.58 +    virtual void erase(const typename _Graph::Node&) 
    1.59 +    {
    1.60 +    }
    1.61 +    virtual void add(const typename _Graph::Edge& n) {
    1.62 +      deg[graph.target(e)]++;
    1.63 +    };
    1.64 +    virtual void erase(const typename _Graph::Edge&) 
    1.65 +    {
    1.66 +      deg[graph.target(e)]--;
    1.67 +    }
    1.68 +
    1.69 +
    1.70 +  };
    1.71 +
    1.72 +
    1.73 +
    1.74 +
    1.75    /// @}
    1.76  
    1.77  } //END OF NAMESPACE LEMON