1.1 --- a/lemon/graph_utils.h Thu Jun 09 09:49:48 2005 +0000
1.2 +++ b/lemon/graph_utils.h Thu Jun 09 09:49:56 2005 +0000
1.3 @@ -24,6 +24,7 @@
1.4 #include <lemon/invalid.h>
1.5 #include <lemon/utility.h>
1.6 #include <lemon/maps.h>
1.7 +#include <lemon/bits/alteration_notifier.h>
1.8
1.9 ///\ingroup gutils
1.10 ///\file
1.11 @@ -855,21 +856,20 @@
1.12
1.13
1.14
1.15 - /* ***************************************************************** */
1.16 + /// Map of the node in-degrees.
1.17
1.18 - /// Provides O(1) time node-degree queries.
1.19 -
1.20 - ///\todo Undocumented
1.21 + ///This map returns the in-degree of a node. Ones it is constructed,
1.22 + ///the degrees are stored in a standard NodeMap, so each query is done
1.23 + ///in constant time. On the other hand, the values updates automatically
1.24 + ///whenever the graph changes.
1.25 ///
1.26 + ///\sa OutDegMap
1.27 template <typename _Graph>
1.28 class InDegMap :
1.29 - protected _Graph::template AlterationNotifier<typename _Graph::Node>::
1.30 - ObserverBase,
1.31 - protected _Graph::template AlterationNotifier<typename _Graph::Edge>::
1.32 - ObserverBase
1.33 + protected _Graph::template NodeMap<int>,
1.34 + protected AlterationNotifier<typename _Graph::Edge>::ObserverBase
1.35 {
1.36 - typename _Graph::template NodeMap<int> deg;
1.37 - const _Graph* graph;
1.38 + const _Graph& graph;
1.39 public:
1.40 typedef int Value;
1.41 typedef typename _Graph::Node Key;
1.42 @@ -877,44 +877,113 @@
1.43 /// \brief Constructor.
1.44 ///
1.45 /// Constructor for creating in-degree map.
1.46 - InDegMap(const _Graph& _graph) : graph(_graph), deg(graph,0)
1.47 + InDegMap(const _Graph& _graph) :
1.48 + _Graph::NodeMap<int>(_graph,0),
1.49 + graph(_graph)
1.50 {
1.51 - typename _Graph::template AlterationNotifier<typename _Graph::Node>
1.52 - ::ObserverBase::attach(graph->getNotifier(typename _Graph::Node()));
1.53 - typename _Graph::template AlterationNotifier<typename _Graph::Edge>
1.54 - ::ObserverBase::attach(graph->getNotifier(typename _Graph::Edge()));
1.55 + AlterationNotifier<typename _Graph::Edge>
1.56 + ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
1.57
1.58 for(typename _Graph::NodeIt n(graph);n!=INVALID;++n)
1.59 for(typename _Graph::InEdgeIt e(graph,n);e!=INVALID;++e)
1.60 - deg[e]++;
1.61 + _Graph::template NodeMap<int>::operator[](graph.target(e))++;
1.62 }
1.63
1.64 - ~InDegMap()
1.65 + virtual ~InDegMap()
1.66 {
1.67 - typename _Graph::template AlterationNotifier<typename _Graph::Node>::
1.68 - ObserverBase::detach();
1.69 - typename _Graph::template AlterationNotifier<typename _Graph::Edge>::
1.70 + AlterationNotifier<typename _Graph::Edge>::
1.71 ObserverBase::detach();
1.72 }
1.73
1.74 - /// Gives back the in degree of a Node.
1.75 - int operator[](const Key& k) const { return deg[k];}
1.76 + /// Gives back the in-degree of a Node.
1.77 + int operator[](const Key& k) const {
1.78 + return _Graph::template NodeMap<int>::operator[](k);
1.79 + }
1.80
1.81 protected:
1.82 virtual void add(const typename _Graph::Node& n) {
1.83 - ///\bug Which 'add' comes before to other?
1.84 - deg[n]=0;
1.85 + _Graph::template NodeMap<int>::add(n);
1.86 + _Graph::template NodeMap<int>::operator[](n)=0;
1.87 }
1.88 - virtual void erase(const typename _Graph::Node&)
1.89 + virtual void erase(const typename _Graph::Node&n)
1.90 {
1.91 + _Graph::template NodeMap<int>::erase(n);
1.92 }
1.93 virtual void add(const typename _Graph::Edge& e) {
1.94 - deg[graph.target(e)]++;
1.95 + _Graph::template NodeMap<int>::operator[](graph.target(e))++;
1.96 }
1.97 virtual void erase(const typename _Graph::Edge& e) {
1.98 - deg[graph.target(e)]--;
1.99 + _Graph::template NodeMap<int>::operator[](graph.target(e))--;
1.100 }
1.101
1.102 + virtual void build() {}
1.103 + virtual void clear() {}
1.104 +
1.105 + };
1.106 +
1.107 +
1.108 + /// Map of the node out-degrees.
1.109 +
1.110 + ///This map returns the out-degree of a node. One it is constructed,
1.111 + ///the degrees are stored in a standard NodeMap, so each query is done
1.112 + ///in constant time. On the other hand, the values updates automatically
1.113 + ///whenever the graph changes.
1.114 + ///
1.115 + ///\sa OutDegMap
1.116 + template <typename _Graph>
1.117 + class OutDegMap :
1.118 + protected _Graph::template NodeMap<int>,
1.119 + protected AlterationNotifier<typename _Graph::Edge>::ObserverBase
1.120 + {
1.121 + const _Graph& graph;
1.122 + public:
1.123 + typedef int Value;
1.124 + typedef typename _Graph::Node Key;
1.125 +
1.126 + /// \brief Constructor.
1.127 + ///
1.128 + /// Constructor for creating out-degree map.
1.129 + OutDegMap(const _Graph& _graph) :
1.130 + _Graph::NodeMap<int>(_graph,0),
1.131 + graph(_graph)
1.132 + {
1.133 + AlterationNotifier<typename _Graph::Edge>
1.134 + ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
1.135 +
1.136 + for(typename _Graph::NodeIt n(graph);n!=INVALID;++n)
1.137 + for(typename _Graph::InEdgeIt e(graph,n);e!=INVALID;++e)
1.138 + _Graph::template NodeMap<int>::operator[](graph.source(e))++;
1.139 + }
1.140 +
1.141 + ~OutDegMap()
1.142 + {
1.143 + AlterationNotifier<typename _Graph::Edge>::
1.144 + ObserverBase::detach();
1.145 + }
1.146 +
1.147 + /// Gives back the in-degree of a Node.
1.148 + int operator[](const Key& k) const {
1.149 + return _Graph::template NodeMap<int>::operator[](k);
1.150 + }
1.151 +
1.152 + protected:
1.153 + virtual void add(const typename _Graph::Node& n) {
1.154 + _Graph::template NodeMap<int>::add(n);
1.155 + _Graph::template NodeMap<int>::operator[](n)=0;
1.156 + }
1.157 + virtual void erase(const typename _Graph::Node&n)
1.158 + {
1.159 + _Graph::template NodeMap<int>::erase(n);
1.160 + }
1.161 + virtual void add(const typename _Graph::Edge& e) {
1.162 + _Graph::template NodeMap<int>::operator[](graph.source(e))++;
1.163 + }
1.164 + virtual void erase(const typename _Graph::Edge& e) {
1.165 + _Graph::template NodeMap<int>::operator[](graph.source(e))--;
1.166 + }
1.167 +
1.168 + virtual void build() {}
1.169 + virtual void clear() {}
1.170
1.171 };
1.172
2.1 --- a/test/graph_utils_test.cc Thu Jun 09 09:49:48 2005 +0000
2.2 +++ b/test/graph_utils_test.cc Thu Jun 09 09:49:56 2005 +0000
2.3 @@ -15,6 +15,36 @@
2.4
2.5 using namespace lemon;
2.6
2.7 +template<class Graph>
2.8 +void checkSnapDeg()
2.9 +{
2.10 + Graph g;
2.11 + typename Graph::Node n1=g.addNode();
2.12 + typename Graph::Node n2=g.addNode();
2.13 +
2.14 + InDegMap<Graph> ind(g);
2.15 +
2.16 + g.addEdge(n1,n2);
2.17 +
2.18 + typename Graph::SnapShot snap(g);
2.19 +
2.20 + OutDegMap<Graph> outd(g);
2.21 +
2.22 + check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
2.23 + check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
2.24 +
2.25 + g.addEdge(n1,n2);
2.26 + g.addEdge(n2,n1);
2.27 +
2.28 + check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value.");
2.29 + check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value.");
2.30 +
2.31 + snap.restore();
2.32 +
2.33 + check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
2.34 + check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
2.35 +
2.36 +}
2.37
2.38 int main() {
2.39 ///\file
2.40 @@ -31,6 +61,13 @@
2.41 check(countEdges(fg) == num*num, "FullGraph: wrong edge number.");
2.42 }
2.43
2.44 + //check In/OutDegMap (and SnapShot feature)
2.45 +
2.46 + checkSnapDeg<ListGraph>();
2.47 + checkSnapDeg<SmartGraph>();
2.48 +
2.49 +
2.50 + ///Everything is OK
2.51 std::cout << __FILE__ ": All tests passed.\n";
2.52
2.53 return 0;