Changeset 1515:dd7616b51333 in lemon-0.x for lemon/graph_utils.h

Timestamp:

06/27/05 12:49:37 (19 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

InDegMap? and OutDegMap? fixed

File:

• lemon/graph_utils.h (modified) (7 diffs)

lemon/graph_utils.h

@@ -483 +483 @@
     }
 
+  protected:
+
     /// \brief Add a new key to the map.
     ///
@@ -598 +600 @@
     }
 
+  protected:
+
     /// \brief Add a new key to the map.
     ///
@@ -773 +777 @@
 
   /// \brief Returns a \ref TargetMap class
-
+  ///
   /// This function just returns an \ref TargetMap class.
   /// \relates TargetMap
@@ -814 +818 @@
 
   /// \brief Returns a \ref ForwardMap class
-
+  ///
   /// This function just returns an \ref ForwardMap class.
   /// \relates ForwardMap
@@ -862 +866 @@
   }
 
-
-
-  /// Map of the node in-degrees.
-
-  ///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;
-  public:
+  class DegMapBase {
+  public:
+    
+    typedef _Graph Graph;
+
+  protected:
+
+    typedef typename Graph::template NodeMap<int> IntNodeMap;
+    
+  };
+
+  /// \brief Map of the node in-degrees.
+  ///
+  /// 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 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))++;
-    }
-
-    virtual ~InDegMap() 
-    {
+      
+      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
+        deg[it] = countInEdges(graph, it);
+      }
+    }
+
+    virtual ~InDegMap() {
       AlterationNotifier<typename _Graph::Edge>::
         ObserverBase::detach();
@@ -904 +935 @@
     
     /// 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))--;
-    }
-
-    ///\e
-    
-    ///\bug Unimplemented
-    ///
-    virtual void build() {}
-    ///\e
-    
-    ///\bug Unimplemented
-    ///
-    virtual void clear() {}
-
-  };
-
-
-  /// 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
+    
+    typedef typename Graph::Edge Edge;
+
+    virtual void add(const Edge& edge) {
+      ++deg[graph.target(edge)];
+    }
+
+    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:
+    
+    const _Graph& graph;
+    AutoNodeMap deg;
+  };
+
+
+  /// \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
+
   template <typename _Graph>
-  class OutDegMap  :
-    protected _Graph::template NodeMap<int>,
-    protected AlterationNotifier<typename _Graph::Edge>::ObserverBase
-  {
-    const _Graph& graph;
-  public:
+  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))++;
-    }
-
-    ~OutDegMap() 
-    {
+      
+      for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
+        deg[it] = countOutEdges(graph, it);
+      }
+    }
+
+    virtual ~OutDegMap() {
       AlterationNotifier<typename _Graph::Edge>::
         ObserverBase::detach();
@@ -978 +1027 @@
     
     /// 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))--;
-    }
-
-    ///\e
-    
-    ///\bug Unimplemented
-    ///
-    virtual void build() {}
-    ///\e
-    
-    ///\bug Unimplemented
-    ///
-    virtual void clear() {}
-
-  };
-
-
-
+    
+    typedef typename Graph::Edge Edge;
+
+    virtual void add(const Edge& edge) {
+      ++deg[graph.source(edge)];
+    }
+
+    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:
+    
+    const _Graph& graph;
+    AutoNodeMap deg;
+  };
 
   /// @}