/* ***************************************************************** */

   /// 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)]--;

     }

   };