Changeset 1459:2ee881cf30a8 in lemon-0.x

Timestamp:

06/09/05 11:49:56 (18 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

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

Message:

• InDegMap? fixed
• OutDegMap? added
• test cases added for them both

Files:

• lemon/graph_utils.h (modified) (3 diffs)
• test/graph_utils_test.cc (modified) (2 diffs)

lemon/graph_utils.h

@@ -25 +25 @@
 #include <lemon/utility.h>
 #include <lemon/maps.h>
+#include <lemon/bits/alteration_notifier.h>
 
 ///\ingroup gutils
@@ -856 +857 @@
 
 
-  /* ***************************************************************** */
-
-  /// Provides O(1) time node-degree queries.
-
-  ///\todo Undocumented
-  ///
+  /// 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 AlterationNotifier<typename _Graph::Node>::
-    ObserverBase,
-    protected _Graph::template AlterationNotifier<typename _Graph::Edge>::
-    ObserverBase
+    protected _Graph::template NodeMap<int>,
+    protected AlterationNotifier<typename _Graph::Edge>::ObserverBase
   {
-    typename _Graph::template NodeMap<int> deg;
-    const _Graph* graph;
+    const _Graph& graph;
   public:
     typedef int Value;
@@ -878 +878 @@
     ///
     /// Constructor for creating in-degree map.
-    InDegMap(const _Graph& _graph) : graph(_graph), deg(graph,0)
+    InDegMap(const _Graph& _graph) :
+      _Graph::NodeMap<int>(_graph,0),
+      graph(_graph)
     {
-      typename _Graph::template AlterationNotifier<typename _Graph::Node>
-        ::ObserverBase::attach(graph->getNotifier(typename _Graph::Node()));
-      typename _Graph::template AlterationNotifier<typename _Graph::Edge>
-        ::ObserverBase::attach(graph->getNotifier(typename _Graph::Edge()));
+      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)
-          deg[e]++;
-    }
-
-    ~InDegMap() 
+          _Graph::template NodeMap<int>::operator[](graph.target(e))++;
+    }
+
+    virtual ~InDegMap() 
     {
-      typename _Graph::template AlterationNotifier<typename _Graph::Node>::
+      AlterationNotifier<typename _Graph::Edge>::
         ObserverBase::detach();
-      typename _Graph::template AlterationNotifier<typename _Graph::Edge>::
-        ObserverBase::detach();
-    }
-    
-    /// Gives back the in degree of a Node.
-    int operator[](const Key& k) const { return deg[k];}
+    }
+    
+    /// Gives back the in-degree of a Node.
+    int operator[](const Key& k) const {
+      return _Graph::template NodeMap<int>::operator[](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&) 
+      _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) {
-      deg[graph.target(e)]++;
+      _Graph::template NodeMap<int>::operator[](graph.target(e))++;
     }
     virtual void erase(const typename _Graph::Edge& e) {
-      deg[graph.target(e)]--;
-    }
-
+      _Graph::template NodeMap<int>::operator[](graph.target(e))--;
+    }
+
+    virtual void build() {}
+    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
+  template <typename _Graph>
+  class OutDegMap  :
+    protected _Graph::template NodeMap<int>,
+    protected AlterationNotifier<typename _Graph::Edge>::ObserverBase
+  {
+    const _Graph& graph;
+  public:
+    typedef int Value;
+    typedef typename _Graph::Node Key;
+
+    /// \brief Constructor.
+    ///
+    /// Constructor for creating out-degree map.
+    OutDegMap(const _Graph& _graph) :
+      _Graph::NodeMap<int>(_graph,0),
+      graph(_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() 
+    {
+      AlterationNotifier<typename _Graph::Edge>::
+        ObserverBase::detach();
+    }
+    
+    /// Gives back the in-degree of a Node.
+    int operator[](const Key& k) const {
+      return _Graph::template NodeMap<int>::operator[](k);
+    }
+
+  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))--;
+    }
+
+    virtual void build() {}
+    virtual void clear() {}
 
   };

test/graph_utils_test.cc

@@ -16 +16 @@
 using namespace lemon;
 
+template<class Graph>
+void checkSnapDeg() 
+{
+  Graph g;
+  typename Graph::Node n1=g.addNode();
+  typename Graph::Node n2=g.addNode();
+   
+  InDegMap<Graph> ind(g);
+ 
+  g.addEdge(n1,n2);
+  
+  typename Graph::SnapShot snap(g);
+  
+  OutDegMap<Graph> outd(g);
+  
+  check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
+  check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
+
+  g.addEdge(n1,n2);
+  g.addEdge(n2,n1);
+ 
+  check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value.");
+  check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value.");
+
+  snap.restore();
+
+  check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
+  check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
+  
+}
 
 int main() {
@@ -32 +62 @@
   }
 
+  //check In/OutDegMap (and SnapShot feature)
+
+  checkSnapDeg<ListGraph>();
+  checkSnapDeg<SmartGraph>();
+  
+
+  ///Everything is OK
   std::cout << __FILE__ ": All tests passed.\n";