Changeset 1453:08c8db58080e in lemon-0.x

Timestamp:

06/08/05 18:36:01 (19 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1933

Message:

InDegMap? added

File:

• lemon/graph_utils.h (modified) (1 diff)

lemon/graph_utils.h

@@ -855 +855 @@
 
 
+
+  /* ***************************************************************** */
+
+  /// 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)]--;
+    }
+
+
+  };
+
+
+
+
   /// @}