1.1 --- a/src/work/alpar/smart_graph.h Sat Mar 13 22:49:54 2004 +0000
1.2 +++ b/src/work/alpar/smart_graph.h Sat Mar 13 22:53:07 2004 +0000
1.3 @@ -1,7 +1,7 @@
1.4 // -*- mode:C++ -*-
1.5
1.6 -#ifndef SMART_GRAPH_H
1.7 -#define SMART_GRAPH_H
1.8 +#ifndef HUGO_SMART_GRAPH_H
1.9 +#define HUGO_SMART_GRAPH_H
1.10
1.11 #include <vector>
1.12 #include <limits.h>
1.13 @@ -10,6 +10,10 @@
1.14
1.15 namespace hugo {
1.16
1.17 + class SymSmartGraph;
1.18 +
1.19 + // template<typename T> class SymSmartGraph::SymEdgeMap;
1.20 +
1.21 class SmartGraph {
1.22
1.23 struct NodeT
1.24 @@ -28,10 +32,12 @@
1.25
1.26 std::vector<EdgeT> edges;
1.27
1.28 + protected:
1.29 +
1.30 template <typename Key> class DynMapBase
1.31 {
1.32 protected:
1.33 - SmartGraph* G;
1.34 + const SmartGraph* G;
1.35 public:
1.36 virtual void add(const Key k) = NULL;
1.37 virtual void erase(const Key k) = NULL;
1.38 @@ -39,15 +45,22 @@
1.39 virtual ~DynMapBase() {}
1.40 friend class SmartGraph;
1.41 };
1.42 +
1.43 public:
1.44 - template <typename T> class DynEdgeMap;
1.45 - template <typename T> class DynEdgeMap;
1.46 + template <typename T> class EdgeMap;
1.47 + template <typename T> class EdgeMap;
1.48
1.49 class Node;
1.50 class Edge;
1.51
1.52 - protected:
1.53 + // protected:
1.54 + // HELPME:
1.55 + public:
1.56 + ///\bug It must be public because of SymEdgeMap.
1.57 + ///
1.58 mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
1.59 + ///\bug It must be public because of SymEdgeMap.
1.60 + ///
1.61 mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
1.62
1.63 public:
1.64 @@ -168,7 +181,6 @@
1.65 class Node {
1.66 friend class SmartGraph;
1.67 template <typename T> friend class NodeMap;
1.68 - template <typename T> friend class DynNodeMap;
1.69
1.70 friend class Edge;
1.71 friend class OutEdgeIt;
1.72 @@ -197,7 +209,9 @@
1.73 class Edge {
1.74 friend class SmartGraph;
1.75 template <typename T> friend class EdgeMap;
1.76 - template <typename T> friend class DynEdgeMap;
1.77 +
1.78 + //template <typename T> friend class SymSmartGraph::SymEdgeMap;
1.79 + //friend Edge SymSmartGraph::opposite(Edge) const;
1.80
1.81 friend class Node;
1.82 friend class NodeIt;
1.83 @@ -212,6 +226,10 @@
1.84 bool operator==(const Edge i) const {return n==i.n;}
1.85 bool operator!=(const Edge i) const {return n!=i.n;}
1.86 bool operator<(const Edge i) const {return n<i.n;}
1.87 + ///\bug This is a workaround until somebody tells me how to
1.88 + ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
1.89 + int &idref() {return n;}
1.90 + const int &idref() const {return n;}
1.91 };
1.92
1.93 class EdgeIt : public Edge {
1.94 @@ -220,6 +238,9 @@
1.95 EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
1.96 EdgeIt (Invalid i) : Edge(i) { }
1.97 EdgeIt() : Edge() { }
1.98 + ///\bug This is a workaround until somebody tells me how to
1.99 + ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
1.100 + int &idref() {return n;}
1.101 };
1.102
1.103 class OutEdgeIt : public Edge {
1.104 @@ -242,43 +263,44 @@
1.105
1.106 // Map types
1.107
1.108 - template <typename T>
1.109 - class NodeMap {
1.110 - const SmartGraph& G;
1.111 - std::vector<T> container;
1.112 - public:
1.113 - typedef T ValueType;
1.114 - typedef Node KeyType;
1.115 - NodeMap(const SmartGraph& _G) : G(_G), container(G.maxNodeId()) { }
1.116 - NodeMap(const SmartGraph& _G, T a) :
1.117 - G(_G), container(G.maxNodeId(), a) { }
1.118 - void set(Node n, T a) { container[n.n]=a; }
1.119 - T get(Node n) const { return container[n.n]; }
1.120 - T& operator[](Node n) { return container[n.n]; }
1.121 - const T& operator[](Node n) const { return container[n.n]; }
1.122 - void update() { container.resize(G.maxNodeId()); }
1.123 - void update(T a) { container.resize(G.maxNodeId(), a); }
1.124 - };
1.125 +// // Static Maps are not necessary.
1.126 +// template <typename T>
1.127 +// class NodeMap {
1.128 +// const SmartGraph& G;
1.129 +// std::vector<T> container;
1.130 +// public:
1.131 +// typedef T ValueType;
1.132 +// typedef Node KeyType;
1.133 +// NodeMap(const SmartGraph& _G) : G(_G), container(G.maxNodeId()) { }
1.134 +// NodeMap(const SmartGraph& _G, T a) :
1.135 +// G(_G), container(G.maxNodeId(), a) { }
1.136 +// void set(Node n, T a) { container[n.n]=a; }
1.137 +// T get(Node n) const { return container[n.n]; }
1.138 +// T& operator[](Node n) { return container[n.n]; }
1.139 +// const T& operator[](Node n) const { return container[n.n]; }
1.140 +// void update() { container.resize(G.maxNodeId()); }
1.141 +// void update(T a) { container.resize(G.maxNodeId(), a); }
1.142 +// };
1.143
1.144 - template <typename T>
1.145 - class EdgeMap {
1.146 - const SmartGraph& G;
1.147 - std::vector<T> container;
1.148 - public:
1.149 - typedef T ValueType;
1.150 - typedef Edge KeyType;
1.151 - EdgeMap(const SmartGraph& _G) : G(_G), container(G.maxEdgeId()) { }
1.152 - EdgeMap(const SmartGraph& _G, T a) :
1.153 - G(_G), container(G.maxEdgeId(), a) { }
1.154 - void set(Edge e, T a) { container[e.n]=a; }
1.155 - T get(Edge e) const { return container[e.n]; }
1.156 - T& operator[](Edge e) { return container[e.n]; }
1.157 - const T& operator[](Edge e) const { return container[e.n]; }
1.158 - void update() { container.resize(G.maxEdgeId()); }
1.159 - void update(T a) { container.resize(G.maxEdgeId(), a); }
1.160 - };
1.161 +// template <typename T>
1.162 +// class EdgeMap {
1.163 +// const SmartGraph& G;
1.164 +// std::vector<T> container;
1.165 +// public:
1.166 +// typedef T ValueType;
1.167 +// typedef Edge KeyType;
1.168 +// EdgeMap(const SmartGraph& _G) : G(_G), container(G.maxEdgeId()) { }
1.169 +// EdgeMap(const SmartGraph& _G, T a) :
1.170 +// G(_G), container(G.maxEdgeId(), a) { }
1.171 +// void set(Edge e, T a) { container[e.n]=a; }
1.172 +// T get(Edge e) const { return container[e.n]; }
1.173 +// T& operator[](Edge e) { return container[e.n]; }
1.174 +// const T& operator[](Edge e) const { return container[e.n]; }
1.175 +// void update() { container.resize(G.maxEdgeId()); }
1.176 +// void update(T a) { container.resize(G.maxEdgeId(), a); }
1.177 +// };
1.178
1.179 - template <typename T> class DynNodeMap : public DynMapBase<Node>
1.180 + template <typename T> class NodeMap : public DynMapBase<Node>
1.181 {
1.182 std::vector<T> container;
1.183
1.184 @@ -286,14 +308,38 @@
1.185 typedef T ValueType;
1.186 typedef Node KeyType;
1.187
1.188 - DynNodeMap(const SmartGraph &_G) :
1.189 + NodeMap(const SmartGraph &_G) :
1.190 DynMapBase<Node>(_G), container(_G.maxNodeId())
1.191 {
1.192 - //FIXME: What if there are empty Id's?
1.193 - //FIXME: Can I use 'this' in a constructor?
1.194 G->dyn_node_maps.push_back(this);
1.195 }
1.196 - ~DynNodeMap()
1.197 + NodeMap(const SmartGraph &_G,const T &t) :
1.198 + DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
1.199 + {
1.200 + G->dyn_node_maps.push_back(this);
1.201 + }
1.202 +
1.203 + NodeMap(const NodeMap<T> &m) :
1.204 + DynMapBase<Node>(*m.G), container(m.container)
1.205 + {
1.206 + G->dyn_node_maps.push_back(this);
1.207 + }
1.208 +
1.209 + template<typename TT> friend class NodeMap;
1.210 +
1.211 + ///\todo It can copy between different types.
1.212 + ///
1.213 + template<typename TT> NodeMap(const NodeMap<TT> &m) :
1.214 + DynMapBase<Node>(*m.G)
1.215 + {
1.216 + G->dyn_node_maps.push_back(this);
1.217 + typename std::vector<TT>::const_iterator i;
1.218 + for(typename std::vector<TT>::const_iterator i=m.container.begin();
1.219 + i!=m.container.end();
1.220 + i++)
1.221 + container.push_back(*i);
1.222 + }
1.223 + ~NodeMap()
1.224 {
1.225 if(G) {
1.226 std::vector<DynMapBase<Node>* >::iterator i;
1.227 @@ -310,28 +356,38 @@
1.228
1.229 void add(const Node k)
1.230 {
1.231 - if(k.n>=container.size()) container.resize(k.n+1);
1.232 + if(k.n>=int(container.size())) container.resize(k.n+1);
1.233 }
1.234
1.235 -// void erase(const Node k)
1.236 -// {
1.237 -// //FIXME: Please implement me.
1.238 -// }
1.239 -// void erase(const Edge k)
1.240 -// {
1.241 -// //FIXME: Please implement me.
1.242 -// }
1.243 + void erase(const Node k) { }
1.244
1.245 void set(Node n, T a) { container[n.n]=a; }
1.246 T get(Node n) const { return container[n.n]; }
1.247 T& operator[](Node n) { return container[n.n]; }
1.248 const T& operator[](Node n) const { return container[n.n]; }
1.249
1.250 + ///\warning There is no safety check at all!
1.251 + ///Using operator = between maps attached to different graph may
1.252 + ///cause serious problem.
1.253 + ///\todo Is this really so?
1.254 + ///\todo It can copy between different types.
1.255 + const NodeMap<T>& operator=(const NodeMap<T> &m)
1.256 + {
1.257 + container = m.container;
1.258 + return *this;
1.259 + }
1.260 + template<typename TT>
1.261 + const NodeMap<T>& operator=(const NodeMap<TT> &m)
1.262 + {
1.263 + copy(m.container.begin(), m.container.end(), container.begin());
1.264 + return *this;
1.265 + }
1.266 +
1.267 void update() {} //Useless for DynMaps
1.268 void update(T a) {} //Useless for DynMaps
1.269 };
1.270
1.271 - template <typename T> class DynEdgeMap : public DynMapBase<Edge>
1.272 + template <typename T> class EdgeMap : public DynMapBase<Edge>
1.273 {
1.274 std::vector<T> container;
1.275
1.276 @@ -339,14 +395,39 @@
1.277 typedef T ValueType;
1.278 typedef Edge KeyType;
1.279
1.280 - DynEdgeMap(const SmartGraph &_G) :
1.281 + EdgeMap(const SmartGraph &_G) :
1.282 DynMapBase<Edge>(_G), container(_G.maxEdgeId())
1.283 {
1.284 //FIXME: What if there are empty Id's?
1.285 //FIXME: Can I use 'this' in a constructor?
1.286 G->dyn_edge_maps.push_back(this);
1.287 }
1.288 - ~DynEdgeMap()
1.289 + EdgeMap(const SmartGraph &_G,const T &t) :
1.290 + DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
1.291 + {
1.292 + G->dyn_edge_maps.push_back(this);
1.293 + }
1.294 + EdgeMap(const EdgeMap<T> &m) :
1.295 + DynMapBase<Edge>(*m.G), container(m.container)
1.296 + {
1.297 + G->dyn_node_maps.push_back(this);
1.298 + }
1.299 +
1.300 + template<typename TT> friend class EdgeMap;
1.301 +
1.302 + ///\todo It can copy between different types.
1.303 + ///
1.304 + template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
1.305 + DynMapBase<Edge>(*m.G)
1.306 + {
1.307 + G->dyn_node_maps.push_back(this);
1.308 + typename std::vector<TT>::const_iterator i;
1.309 + for(typename std::vector<TT>::const_iterator i=m.container.begin();
1.310 + i!=m.container.end();
1.311 + i++)
1.312 + container.push_back(*i);
1.313 + }
1.314 + ~EdgeMap()
1.315 {
1.316 if(G) {
1.317 std::vector<DynMapBase<Edge>* >::iterator i;
1.318 @@ -365,21 +446,158 @@
1.319 {
1.320 if(k.n>=int(container.size())) container.resize(k.n+1);
1.321 }
1.322 - void erase(const Edge k)
1.323 - {
1.324 - //FIXME: Please implement me.
1.325 - }
1.326 + void erase(const Edge k) { }
1.327
1.328 void set(Edge n, T a) { container[n.n]=a; }
1.329 T get(Edge n) const { return container[n.n]; }
1.330 T& operator[](Edge n) { return container[n.n]; }
1.331 const T& operator[](Edge n) const { return container[n.n]; }
1.332
1.333 + ///\warning There is no safety check at all!
1.334 + ///Using operator = between maps attached to different graph may
1.335 + ///cause serious problem.
1.336 + ///\todo Is this really so?
1.337 + ///\todo It can copy between different types.
1.338 + const EdgeMap<T>& operator=(const EdgeMap<T> &m)
1.339 + {
1.340 + container = m.container;
1.341 + return *this;
1.342 + }
1.343 + template<typename TT>
1.344 + const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
1.345 + {
1.346 + copy(m.container.begin(), m.container.end(), container.begin());
1.347 + return *this;
1.348 + }
1.349 +
1.350 void update() {} //Useless for DynMaps
1.351 void update(T a) {} //Useless for DynMaps
1.352 };
1.353 -
1.354 +
1.355 };
1.356 +
1.357 + ///Graph for bidirectional edges.
1.358 +
1.359 + ///The purpose of this graph structure is to handle graphs
1.360 + ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
1.361 + ///of oppositely directed edges. You can define edge maps which
1.362 + ///stores a common value for the edge pairs. The usual edge maps can be used
1.363 + ///as well.
1.364 + ///
1.365 + ///The oppositely directed edge can also be obtained easily.
1.366 +
1.367 + class SymSmartGraph : public SmartGraph
1.368 + {
1.369 + public:
1.370 + SymSmartGraph() : SmartGraph() { }
1.371 + SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
1.372 + Edge addEdge(Node u, Node v)
1.373 + {
1.374 + Edge e = SmartGraph::addEdge(u,v);
1.375 + SmartGraph::addEdge(v,u);
1.376 + return e;
1.377 + }
1.378 +
1.379 + Edge opposite(Edge e) const
1.380 + {
1.381 + Edge f;
1.382 + f.idref() = e.idref() - 2*(e.idref()%2) + 1;
1.383 + return f;
1.384 + }
1.385 +
1.386 + template <typename T> class SymEdgeMap : public DynMapBase<Edge>
1.387 + {
1.388 + std::vector<T> container;
1.389 +
1.390 + public:
1.391 + typedef T ValueType;
1.392 + typedef Edge KeyType;
1.393 +
1.394 + SymEdgeMap(const SmartGraph &_G) :
1.395 + DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
1.396 + {
1.397 + G->dyn_edge_maps.push_back(this);
1.398 + }
1.399 + SymEdgeMap(const SmartGraph &_G,const T &t) :
1.400 + DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
1.401 + {
1.402 + G->dyn_edge_maps.push_back(this);
1.403 + }
1.404 +
1.405 + SymEdgeMap(const SymEdgeMap<T> &m) :
1.406 + DynMapBase<SymEdge>(*m.G), container(m.container)
1.407 + {
1.408 + G->dyn_node_maps.push_back(this);
1.409 + }
1.410 +
1.411 + // template<typename TT> friend class SymEdgeMap;
1.412 +
1.413 + ///\todo It can copy between different types.
1.414 + ///
1.415 +
1.416 + template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
1.417 + DynMapBase<SymEdge>(*m.G)
1.418 + {
1.419 + G->dyn_node_maps.push_back(this);
1.420 + typename std::vector<TT>::const_iterator i;
1.421 + for(typename std::vector<TT>::const_iterator i=m.container.begin();
1.422 + i!=m.container.end();
1.423 + i++)
1.424 + container.push_back(*i);
1.425 + }
1.426 +
1.427 + ~SymEdgeMap()
1.428 + {
1.429 + if(G) {
1.430 + std::vector<DynMapBase<Edge>* >::iterator i;
1.431 + for(i=G->dyn_edge_maps.begin();
1.432 + i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
1.433 + //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
1.434 + //A better way to do that: (Is this really important?)
1.435 + if(*i==this) {
1.436 + *i=G->dyn_edge_maps.back();
1.437 + G->dyn_edge_maps.pop_back();
1.438 + }
1.439 + }
1.440 + }
1.441 +
1.442 + void add(const Edge k)
1.443 + {
1.444 + if(!k.idref()%2&&k.idref()/2>=int(container.size()))
1.445 + container.resize(k.idref()/2+1);
1.446 + }
1.447 + void erase(const Edge k) { }
1.448 +
1.449 + void set(Edge n, T a) { container[n.idref()/2]=a; }
1.450 + T get(Edge n) const { return container[n.idref()/2]; }
1.451 + T& operator[](Edge n) { return container[n.idref()/2]; }
1.452 + const T& operator[](Edge n) const { return container[n.idref()/2]; }
1.453 +
1.454 + ///\warning There is no safety check at all!
1.455 + ///Using operator = between maps attached to different graph may
1.456 + ///cause serious problem.
1.457 + ///\todo Is this really so?
1.458 + ///\todo It can copy between different types.
1.459 + const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
1.460 + {
1.461 + container = m.container;
1.462 + return *this;
1.463 + }
1.464 + template<typename TT>
1.465 + const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
1.466 + {
1.467 + copy(m.container.begin(), m.container.end(), container.begin());
1.468 + return *this;
1.469 + }
1.470 +
1.471 + void update() {} //Useless for DynMaps
1.472 + void update(T a) {} //Useless for DynMaps
1.473 +
1.474 + };
1.475 +
1.476 + };
1.477 +
1.478 +
1.479 } //namespace hugo
1.480
1.481