1.1 --- a/lemon/graph_utils.h Fri Jun 24 21:03:08 2005 +0000
1.2 +++ b/lemon/graph_utils.h Mon Jun 27 10:49:37 2005 +0000
1.3 @@ -482,6 +482,8 @@
1.4 return Map::operator[](key);
1.5 }
1.6
1.7 + protected:
1.8 +
1.9 /// \brief Add a new key to the map.
1.10 ///
1.11 /// Add a new key to the map. It is called by the
1.12 @@ -597,6 +599,8 @@
1.13 build();
1.14 }
1.15
1.16 + protected:
1.17 +
1.18 /// \brief Add a new key to the map.
1.19 ///
1.20 /// Add a new key to the map. It is called by the
1.21 @@ -772,7 +776,7 @@
1.22 };
1.23
1.24 /// \brief Returns a \ref TargetMap class
1.25 -
1.26 + ///
1.27 /// This function just returns an \ref TargetMap class.
1.28 /// \relates TargetMap
1.29 template <typename Graph>
1.30 @@ -813,7 +817,7 @@
1.31 };
1.32
1.33 /// \brief Returns a \ref ForwardMap class
1.34 -
1.35 + ///
1.36 /// This function just returns an \ref ForwardMap class.
1.37 /// \relates ForwardMap
1.38 template <typename Graph>
1.39 @@ -861,158 +865,201 @@
1.40 return BackwardMap<Graph>(graph);
1.41 }
1.42
1.43 + template <typename _Graph>
1.44 + class DegMapBase {
1.45 + public:
1.46 +
1.47 + typedef _Graph Graph;
1.48
1.49 + protected:
1.50
1.51 - /// Map of the node in-degrees.
1.52 + typedef typename Graph::template NodeMap<int> IntNodeMap;
1.53 +
1.54 + };
1.55
1.56 - ///This map returns the in-degree of a node. Ones it is constructed,
1.57 - ///the degrees are stored in a standard NodeMap, so each query is done
1.58 - ///in constant time. On the other hand, the values updates automatically
1.59 - ///whenever the graph changes.
1.60 + /// \brief Map of the node in-degrees.
1.61 ///
1.62 - ///\sa OutDegMap
1.63 + /// This map returns the in-degree of a node. Ones it is constructed,
1.64 + /// the degrees are stored in a standard NodeMap, so each query is done
1.65 + /// in constant time. On the other hand, the values updates automatically
1.66 + /// whenever the graph changes.
1.67 + ///
1.68 + /// \sa OutDegMap
1.69 +
1.70 template <typename _Graph>
1.71 - class InDegMap :
1.72 - protected _Graph::template NodeMap<int>,
1.73 - protected AlterationNotifier<typename _Graph::Edge>::ObserverBase
1.74 - {
1.75 - const _Graph& graph;
1.76 + class InDegMap
1.77 + : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
1.78 +
1.79 public:
1.80 +
1.81 + typedef _Graph Graph;
1.82 typedef int Value;
1.83 - typedef typename _Graph::Node Key;
1.84 + typedef typename Graph::Node Key;
1.85 +
1.86 + private:
1.87 +
1.88 + class AutoNodeMap : public Graph::template NodeMap<int> {
1.89 + public:
1.90 +
1.91 + typedef typename Graph::template NodeMap<int> Parent;
1.92 +
1.93 + typedef typename Parent::Key Key;
1.94 + typedef typename Parent::Value Value;
1.95 +
1.96 + AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1.97 +
1.98 + void add(const Key& key) {
1.99 + Parent::add(key);
1.100 + Parent::set(key, 0);
1.101 + }
1.102 + };
1.103 +
1.104 + public:
1.105
1.106 /// \brief Constructor.
1.107 ///
1.108 /// Constructor for creating in-degree map.
1.109 - InDegMap(const _Graph& _graph) :
1.110 - _Graph::template NodeMap<int>(_graph,0),
1.111 - graph(_graph)
1.112 - {
1.113 + InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1.114 AlterationNotifier<typename _Graph::Edge>
1.115 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
1.116 -
1.117 - for(typename _Graph::NodeIt n(graph);n!=INVALID;++n)
1.118 - for(typename _Graph::InEdgeIt e(graph,n);e!=INVALID;++e)
1.119 - _Graph::template NodeMap<int>::operator[](graph.target(e))++;
1.120 +
1.121 + for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1.122 + deg[it] = countInEdges(graph, it);
1.123 + }
1.124 }
1.125
1.126 - virtual ~InDegMap()
1.127 - {
1.128 + virtual ~InDegMap() {
1.129 AlterationNotifier<typename _Graph::Edge>::
1.130 ObserverBase::detach();
1.131 }
1.132
1.133 /// Gives back the in-degree of a Node.
1.134 - int operator[](const Key& k) const {
1.135 - return _Graph::template NodeMap<int>::operator[](k);
1.136 + int operator[](const Key& key) const {
1.137 + return deg[key];
1.138 }
1.139
1.140 protected:
1.141 - virtual void add(const typename _Graph::Node& n) {
1.142 - _Graph::template NodeMap<int>::add(n);
1.143 - _Graph::template NodeMap<int>::operator[](n)=0;
1.144 - }
1.145 - virtual void erase(const typename _Graph::Node&n)
1.146 - {
1.147 - _Graph::template NodeMap<int>::erase(n);
1.148 - }
1.149 - virtual void add(const typename _Graph::Edge& e) {
1.150 - _Graph::template NodeMap<int>::operator[](graph.target(e))++;
1.151 - }
1.152 - virtual void erase(const typename _Graph::Edge& e) {
1.153 - _Graph::template NodeMap<int>::operator[](graph.target(e))--;
1.154 +
1.155 + typedef typename Graph::Edge Edge;
1.156 +
1.157 + virtual void add(const Edge& edge) {
1.158 + ++deg[graph.target(edge)];
1.159 }
1.160
1.161 - ///\e
1.162 + virtual void erase(const Edge& edge) {
1.163 + --deg[graph.target(edge)];
1.164 + }
1.165 +
1.166 +
1.167 + virtual void build() {
1.168 + for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1.169 + deg[it] = countInEdges(graph, it);
1.170 + }
1.171 + }
1.172 +
1.173 + virtual void clear() {
1.174 + for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1.175 + deg[it] = 0;
1.176 + }
1.177 + }
1.178 + private:
1.179
1.180 - ///\bug Unimplemented
1.181 - ///
1.182 - virtual void build() {}
1.183 - ///\e
1.184 -
1.185 - ///\bug Unimplemented
1.186 - ///
1.187 - virtual void clear() {}
1.188 -
1.189 + const _Graph& graph;
1.190 + AutoNodeMap deg;
1.191 };
1.192
1.193
1.194 - /// Map of the node out-degrees.
1.195 + /// \brief Map of the node out-degrees.
1.196 + ///
1.197 + /// This map returns the out-degree of a node. One it is constructed,
1.198 + /// the degrees are stored in a standard NodeMap, so each query is done
1.199 + /// in constant time. On the other hand, the values updates automatically
1.200 + /// whenever the graph changes.
1.201 + ///
1.202 + /// \sa OutDegMap
1.203
1.204 - ///This map returns the out-degree of a node. One it is constructed,
1.205 - ///the degrees are stored in a standard NodeMap, so each query is done
1.206 - ///in constant time. On the other hand, the values updates automatically
1.207 - ///whenever the graph changes.
1.208 - ///
1.209 - ///\sa OutDegMap
1.210 template <typename _Graph>
1.211 - class OutDegMap :
1.212 - protected _Graph::template NodeMap<int>,
1.213 - protected AlterationNotifier<typename _Graph::Edge>::ObserverBase
1.214 - {
1.215 - const _Graph& graph;
1.216 + class OutDegMap
1.217 + : protected AlterationNotifier<typename _Graph::Edge>::ObserverBase {
1.218 +
1.219 public:
1.220 +
1.221 + typedef _Graph Graph;
1.222 typedef int Value;
1.223 - typedef typename _Graph::Node Key;
1.224 + typedef typename Graph::Node Key;
1.225 +
1.226 + private:
1.227 +
1.228 + class AutoNodeMap : public Graph::template NodeMap<int> {
1.229 + public:
1.230 +
1.231 + typedef typename Graph::template NodeMap<int> Parent;
1.232 +
1.233 + typedef typename Parent::Key Key;
1.234 + typedef typename Parent::Value Value;
1.235 +
1.236 + AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1.237 +
1.238 + void add(const Key& key) {
1.239 + Parent::add(key);
1.240 + Parent::set(key, 0);
1.241 + }
1.242 + };
1.243 +
1.244 + public:
1.245
1.246 /// \brief Constructor.
1.247 ///
1.248 /// Constructor for creating out-degree map.
1.249 - OutDegMap(const _Graph& _graph) :
1.250 - _Graph::template NodeMap<int>(_graph,0),
1.251 - graph(_graph)
1.252 - {
1.253 + OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1.254 AlterationNotifier<typename _Graph::Edge>
1.255 ::ObserverBase::attach(graph.getNotifier(typename _Graph::Edge()));
1.256 -
1.257 - for(typename _Graph::NodeIt n(graph);n!=INVALID;++n)
1.258 - for(typename _Graph::InEdgeIt e(graph,n);e!=INVALID;++e)
1.259 - _Graph::template NodeMap<int>::operator[](graph.source(e))++;
1.260 +
1.261 + for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1.262 + deg[it] = countOutEdges(graph, it);
1.263 + }
1.264 }
1.265
1.266 - ~OutDegMap()
1.267 - {
1.268 + virtual ~OutDegMap() {
1.269 AlterationNotifier<typename _Graph::Edge>::
1.270 ObserverBase::detach();
1.271 }
1.272
1.273 /// Gives back the in-degree of a Node.
1.274 - int operator[](const Key& k) const {
1.275 - return _Graph::template NodeMap<int>::operator[](k);
1.276 + int operator[](const Key& key) const {
1.277 + return deg[key];
1.278 }
1.279
1.280 protected:
1.281 - virtual void add(const typename _Graph::Node& n) {
1.282 - _Graph::template NodeMap<int>::add(n);
1.283 - _Graph::template NodeMap<int>::operator[](n)=0;
1.284 - }
1.285 - virtual void erase(const typename _Graph::Node&n)
1.286 - {
1.287 - _Graph::template NodeMap<int>::erase(n);
1.288 - }
1.289 - virtual void add(const typename _Graph::Edge& e) {
1.290 - _Graph::template NodeMap<int>::operator[](graph.source(e))++;
1.291 - }
1.292 - virtual void erase(const typename _Graph::Edge& e) {
1.293 - _Graph::template NodeMap<int>::operator[](graph.source(e))--;
1.294 +
1.295 + typedef typename Graph::Edge Edge;
1.296 +
1.297 + virtual void add(const Edge& edge) {
1.298 + ++deg[graph.source(edge)];
1.299 }
1.300
1.301 - ///\e
1.302 + virtual void erase(const Edge& edge) {
1.303 + --deg[graph.source(edge)];
1.304 + }
1.305 +
1.306 +
1.307 + virtual void build() {
1.308 + for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1.309 + deg[it] = countOutEdges(graph, it);
1.310 + }
1.311 + }
1.312 +
1.313 + virtual void clear() {
1.314 + for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1.315 + deg[it] = 0;
1.316 + }
1.317 + }
1.318 + private:
1.319
1.320 - ///\bug Unimplemented
1.321 - ///
1.322 - virtual void build() {}
1.323 - ///\e
1.324 -
1.325 - ///\bug Unimplemented
1.326 - ///
1.327 - virtual void clear() {}
1.328 -
1.329 + const _Graph& graph;
1.330 + AutoNodeMap deg;
1.331 };
1.332
1.333 -
1.334 -
1.335 -
1.336 /// @}
1.337
1.338 } //END OF NAMESPACE LEMON