1.1 --- a/src/work/alpar/smart_graph.h Fri Mar 26 23:34:45 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,649 +0,0 @@
1.4 -// -*- mode:C++ -*-
1.5 -
1.6 -#ifndef HUGO_SMART_GRAPH_H
1.7 -#define HUGO_SMART_GRAPH_H
1.8 -
1.9 -///\file
1.10 -///\brief SmartGraph and SymSmartGraph classes.
1.11 -
1.12 -#include <vector>
1.13 -#include <limits.h>
1.14 -
1.15 -#include <invalid.h>
1.16 -
1.17 -namespace hugo {
1.18 -
1.19 - class SymSmartGraph;
1.20 -
1.21 - ///A smart graph class.
1.22 -
1.23 - ///This is a simple and fast graph implementation.
1.24 - ///It is also quite memory efficient, but at the price
1.25 - ///that <b> it does not support node and edge deletion</b>.
1.26 - ///It conforms to the graph interface documented under
1.27 - ///the description of \ref GraphSkeleton.
1.28 - ///\sa \ref GraphSkeleton.
1.29 - class SmartGraph {
1.30 -
1.31 - struct NodeT
1.32 - {
1.33 - int first_in,first_out;
1.34 - NodeT() : first_in(-1), first_out(-1) {}
1.35 - };
1.36 - struct EdgeT
1.37 - {
1.38 - int head, tail, next_in, next_out;
1.39 - //FIXME: is this necessary?
1.40 - EdgeT() : next_in(-1), next_out(-1) {}
1.41 - };
1.42 -
1.43 - std::vector<NodeT> nodes;
1.44 -
1.45 - std::vector<EdgeT> edges;
1.46 -
1.47 - protected:
1.48 -
1.49 - template <typename Key> class DynMapBase
1.50 - {
1.51 - protected:
1.52 - const SmartGraph* G;
1.53 - public:
1.54 - virtual void add(const Key k) = NULL;
1.55 - virtual void erase(const Key k) = NULL;
1.56 - DynMapBase(const SmartGraph &_G) : G(&_G) {}
1.57 - virtual ~DynMapBase() {}
1.58 - friend class SmartGraph;
1.59 - };
1.60 -
1.61 - public:
1.62 - template <typename T> class EdgeMap;
1.63 - template <typename T> class EdgeMap;
1.64 -
1.65 - class Node;
1.66 - class Edge;
1.67 -
1.68 - // protected:
1.69 - // HELPME:
1.70 - protected:
1.71 - ///\bug It must be public because of SymEdgeMap.
1.72 - ///
1.73 - mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
1.74 - ///\bug It must be public because of SymEdgeMap.
1.75 - ///
1.76 - mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
1.77 -
1.78 - public:
1.79 -
1.80 - class NodeIt;
1.81 - class EdgeIt;
1.82 - class OutEdgeIt;
1.83 - class InEdgeIt;
1.84 -
1.85 - // class Node { int n; };
1.86 - // class NodeIt : public Node { };
1.87 - // class Edge { int n; };
1.88 - // class EdgeIt : public Edge {};
1.89 - // class OutEdgeIt : public Edge {};
1.90 - // class InEdgeIt : public Edge {};
1.91 - // class SymEdge;
1.92 -
1.93 - template <typename T> class NodeMap;
1.94 - template <typename T> class EdgeMap;
1.95 -
1.96 - public:
1.97 -
1.98 - /* default constructor */
1.99 -
1.100 - SmartGraph() : nodes(), edges() { }
1.101 - SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
1.102 -
1.103 - ~SmartGraph()
1.104 - {
1.105 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1.106 - i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
1.107 - for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
1.108 - i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
1.109 - }
1.110 -
1.111 - int nodeNum() const { return nodes.size(); } //FIXME: What is this?
1.112 - int edgeNum() const { return edges.size(); } //FIXME: What is this?
1.113 -
1.114 - ///\bug This function does something different than
1.115 - ///its name would suggests...
1.116 - int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
1.117 - ///\bug This function does something different than
1.118 - ///its name would suggests...
1.119 - int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
1.120 -
1.121 - Node tail(Edge e) const { return edges[e.n].tail; }
1.122 - Node head(Edge e) const { return edges[e.n].head; }
1.123 -
1.124 - // Marci
1.125 - Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
1.126 - Node aNode(InEdgeIt e) const { return edges[e.n].head; }
1.127 -// //Node aNode(const SymEdge& e) const { return e.aNode(); }
1.128 -
1.129 - // Marci
1.130 - Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
1.131 - Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
1.132 -// //Node bNode(const SymEdge& e) const { return e.bNode(); }
1.133 -
1.134 - NodeIt& first(NodeIt& v) const {
1.135 - v=NodeIt(*this); return v; }
1.136 - EdgeIt& first(EdgeIt& e) const {
1.137 - e=EdgeIt(*this); return e; }
1.138 - OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
1.139 - e=OutEdgeIt(*this,v); return e; }
1.140 - InEdgeIt& first(InEdgeIt& e, const Node v) const {
1.141 - e=InEdgeIt(*this,v); return e; }
1.142 -
1.143 - template< typename It >
1.144 - It first() const { It e; first(e); return e; }
1.145 -
1.146 - template< typename It >
1.147 - It first(Node v) const { It e; first(e,v); return e; }
1.148 -
1.149 - bool valid(Edge e) const { return e.n!=-1; }
1.150 - bool valid(Node n) const { return n.n!=-1; }
1.151 -
1.152 - void setInvalid(Edge &e) { e.n=-1; }
1.153 - void setInvalid(Node &n) { n.n=-1; }
1.154 -
1.155 - template <typename It> It getNext(It it) const
1.156 - { It tmp(it); return next(tmp); }
1.157 -
1.158 - NodeIt& next(NodeIt& it) const {
1.159 - it.n=(it.n+2)%(nodes.size()+1)-1;
1.160 - return it;
1.161 - }
1.162 - OutEdgeIt& next(OutEdgeIt& it) const
1.163 - { it.n=edges[it.n].next_out; return it; }
1.164 - InEdgeIt& next(InEdgeIt& it) const
1.165 - { it.n=edges[it.n].next_in; return it; }
1.166 - EdgeIt& next(EdgeIt& it) const { --it.n; return it; }
1.167 -
1.168 - int id(Node v) const { return v.n; }
1.169 - int id(Edge e) const { return e.n; }
1.170 -
1.171 - Node addNode() {
1.172 - Node n; n.n=nodes.size();
1.173 - nodes.push_back(NodeT()); //FIXME: Hmmm...
1.174 -
1.175 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1.176 - i!=dyn_node_maps.end(); ++i) (**i).add(n.n);
1.177 -
1.178 - return n;
1.179 - }
1.180 -
1.181 - Edge addEdge(Node u, Node v) {
1.182 - Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
1.183 - edges[e.n].tail=u.n; edges[e.n].head=v.n;
1.184 - edges[e.n].next_out=nodes[u.n].first_out;
1.185 - edges[e.n].next_in=nodes[v.n].first_in;
1.186 - nodes[u.n].first_out=nodes[v.n].first_in=e.n;
1.187 -
1.188 - for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
1.189 - i!=dyn_edge_maps.end(); ++i) (**i).add(e);
1.190 -
1.191 - return e;
1.192 - }
1.193 -
1.194 - void clear() {nodes.clear();edges.clear();}
1.195 -
1.196 - class Node {
1.197 - friend class SmartGraph;
1.198 - template <typename T> friend class NodeMap;
1.199 -
1.200 - friend class Edge;
1.201 - friend class OutEdgeIt;
1.202 - friend class InEdgeIt;
1.203 - friend class SymEdge;
1.204 -
1.205 - protected:
1.206 - int n;
1.207 - friend int SmartGraph::id(Node v) const;
1.208 - Node(int nn) {n=nn;}
1.209 - public:
1.210 - Node() {}
1.211 - Node (Invalid i) { n=-1; }
1.212 - bool operator==(const Node i) const {return n==i.n;}
1.213 - bool operator!=(const Node i) const {return n!=i.n;}
1.214 - bool operator<(const Node i) const {return n<i.n;}
1.215 - };
1.216 -
1.217 - class NodeIt : public Node {
1.218 - friend class SmartGraph;
1.219 - public:
1.220 - NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
1.221 - NodeIt() : Node() { }
1.222 - };
1.223 -
1.224 - class Edge {
1.225 - friend class SmartGraph;
1.226 - template <typename T> friend class EdgeMap;
1.227 -
1.228 - //template <typename T> friend class SymSmartGraph::SymEdgeMap;
1.229 - //friend Edge SymSmartGraph::opposite(Edge) const;
1.230 -
1.231 - friend class Node;
1.232 - friend class NodeIt;
1.233 - protected:
1.234 - int n;
1.235 - friend int SmartGraph::id(Edge e) const;
1.236 -
1.237 - Edge(int nn) {n=nn;}
1.238 - public:
1.239 - Edge() { }
1.240 - Edge (Invalid) { n=-1; }
1.241 - bool operator==(const Edge i) const {return n==i.n;}
1.242 - bool operator!=(const Edge i) const {return n!=i.n;}
1.243 - bool operator<(const Edge i) const {return n<i.n;}
1.244 - ///\bug This is a workaround until somebody tells me how to
1.245 - ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
1.246 - int &idref() {return n;}
1.247 - const int &idref() const {return n;}
1.248 - };
1.249 -
1.250 - class EdgeIt : public Edge {
1.251 - friend class SmartGraph;
1.252 - public:
1.253 - EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
1.254 - EdgeIt (Invalid i) : Edge(i) { }
1.255 - EdgeIt() : Edge() { }
1.256 - ///\bug This is a workaround until somebody tells me how to
1.257 - ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
1.258 - int &idref() {return n;}
1.259 - };
1.260 -
1.261 - class OutEdgeIt : public Edge {
1.262 - friend class SmartGraph;
1.263 - public:
1.264 - OutEdgeIt() : Edge() { }
1.265 - OutEdgeIt (Invalid i) : Edge(i) { }
1.266 -
1.267 - OutEdgeIt(const SmartGraph& G,const Node v)
1.268 - : Edge(G.nodes[v.n].first_out) {}
1.269 - };
1.270 -
1.271 - class InEdgeIt : public Edge {
1.272 - friend class SmartGraph;
1.273 - public:
1.274 - InEdgeIt() : Edge() { }
1.275 - InEdgeIt (Invalid i) : Edge(i) { }
1.276 - InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
1.277 - };
1.278 -
1.279 - // Map types
1.280 -
1.281 -// // Static Maps are not necessary.
1.282 -// template <typename T>
1.283 -// class NodeMap {
1.284 -// const SmartGraph& G;
1.285 -// std::vector<T> container;
1.286 -// public:
1.287 -// typedef T ValueType;
1.288 -// typedef Node KeyType;
1.289 -// NodeMap(const SmartGraph& _G) : G(_G), container(G.maxNodeId()) { }
1.290 -// NodeMap(const SmartGraph& _G, T a) :
1.291 -// G(_G), container(G.maxNodeId(), a) { }
1.292 -// void set(Node n, T a) { container[n.n]=a; }
1.293 -// T get(Node n) const { return container[n.n]; }
1.294 -// T& operator[](Node n) { return container[n.n]; }
1.295 -// const T& operator[](Node n) const { return container[n.n]; }
1.296 -// void update() { container.resize(G.maxNodeId()); }
1.297 -// void update(T a) { container.resize(G.maxNodeId(), a); }
1.298 -// };
1.299 -
1.300 -// template <typename T>
1.301 -// class EdgeMap {
1.302 -// const SmartGraph& G;
1.303 -// std::vector<T> container;
1.304 -// public:
1.305 -// typedef T ValueType;
1.306 -// typedef Edge KeyType;
1.307 -// EdgeMap(const SmartGraph& _G) : G(_G), container(G.maxEdgeId()) { }
1.308 -// EdgeMap(const SmartGraph& _G, T a) :
1.309 -// G(_G), container(G.maxEdgeId(), a) { }
1.310 -// void set(Edge e, T a) { container[e.n]=a; }
1.311 -// T get(Edge e) const { return container[e.n]; }
1.312 -// T& operator[](Edge e) { return container[e.n]; }
1.313 -// const T& operator[](Edge e) const { return container[e.n]; }
1.314 -// void update() { container.resize(G.maxEdgeId()); }
1.315 -// void update(T a) { container.resize(G.maxEdgeId(), a); }
1.316 -// };
1.317 -
1.318 - template <typename T> class NodeMap : public DynMapBase<Node>
1.319 - {
1.320 - std::vector<T> container;
1.321 -
1.322 - public:
1.323 - typedef T ValueType;
1.324 - typedef Node KeyType;
1.325 -
1.326 - NodeMap(const SmartGraph &_G) :
1.327 - DynMapBase<Node>(_G), container(_G.maxNodeId())
1.328 - {
1.329 - G->dyn_node_maps.push_back(this);
1.330 - }
1.331 - NodeMap(const SmartGraph &_G,const T &t) :
1.332 - DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
1.333 - {
1.334 - G->dyn_node_maps.push_back(this);
1.335 - }
1.336 -
1.337 - NodeMap(const NodeMap<T> &m) :
1.338 - DynMapBase<Node>(*m.G), container(m.container)
1.339 - {
1.340 - G->dyn_node_maps.push_back(this);
1.341 - }
1.342 -
1.343 - template<typename TT> friend class NodeMap;
1.344 -
1.345 - ///\todo It can copy between different types.
1.346 - ///
1.347 - template<typename TT> NodeMap(const NodeMap<TT> &m) :
1.348 - DynMapBase<Node>(*m.G)
1.349 - {
1.350 - G->dyn_node_maps.push_back(this);
1.351 - typename std::vector<TT>::const_iterator i;
1.352 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
1.353 - i!=m.container.end();
1.354 - i++)
1.355 - container.push_back(*i);
1.356 - }
1.357 - ~NodeMap()
1.358 - {
1.359 - if(G) {
1.360 - std::vector<DynMapBase<Node>* >::iterator i;
1.361 - for(i=G->dyn_node_maps.begin();
1.362 - i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
1.363 - //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
1.364 - //A better way to do that: (Is this really important?)
1.365 - if(*i==this) {
1.366 - *i=G->dyn_node_maps.back();
1.367 - G->dyn_node_maps.pop_back();
1.368 - }
1.369 - }
1.370 - }
1.371 -
1.372 - void add(const Node k)
1.373 - {
1.374 - if(k.n>=int(container.size())) container.resize(k.n+1);
1.375 - }
1.376 -
1.377 - void erase(const Node) { }
1.378 -
1.379 - void set(Node n, T a) { container[n.n]=a; }
1.380 - //T get(Node n) const { return container[n.n]; }
1.381 - //Hajjaj:
1.382 - //T& operator[](Node n) { return container[n.n]; }
1.383 - typename std::vector<T>::reference
1.384 - operator[](Node n) { return container[n.n]; }
1.385 - //const T& operator[](Node n) const { return container[n.n]; }
1.386 - typename std::vector<T>::const_reference
1.387 - operator[](Node n) const { return container[n.n]; }
1.388 -
1.389 - ///\warning There is no safety check at all!
1.390 - ///Using operator = between maps attached to different graph may
1.391 - ///cause serious problem.
1.392 - ///\todo Is this really so?
1.393 - ///\todo It can copy between different types.
1.394 - const NodeMap<T>& operator=(const NodeMap<T> &m)
1.395 - {
1.396 - container = m.container;
1.397 - return *this;
1.398 - }
1.399 - template<typename TT>
1.400 - const NodeMap<T>& operator=(const NodeMap<TT> &m)
1.401 - {
1.402 - copy(m.container.begin(), m.container.end(), container.begin());
1.403 - return *this;
1.404 - }
1.405 -
1.406 - void update() {} //Useless for DynMaps
1.407 - void update(T a) {} //Useless for DynMaps
1.408 - };
1.409 -
1.410 - template <typename T> class EdgeMap : public DynMapBase<Edge>
1.411 - {
1.412 - std::vector<T> container;
1.413 -
1.414 - public:
1.415 - typedef T ValueType;
1.416 - typedef Edge KeyType;
1.417 -
1.418 - EdgeMap(const SmartGraph &_G) :
1.419 - DynMapBase<Edge>(_G), container(_G.maxEdgeId())
1.420 - {
1.421 - //FIXME: What if there are empty Id's?
1.422 - //FIXME: Can I use 'this' in a constructor?
1.423 - G->dyn_edge_maps.push_back(this);
1.424 - }
1.425 - EdgeMap(const SmartGraph &_G,const T &t) :
1.426 - DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
1.427 - {
1.428 - G->dyn_edge_maps.push_back(this);
1.429 - }
1.430 - EdgeMap(const EdgeMap<T> &m) :
1.431 - DynMapBase<Edge>(*m.G), container(m.container)
1.432 - {
1.433 - G->dyn_node_maps.push_back(this);
1.434 - }
1.435 -
1.436 - template<typename TT> friend class EdgeMap;
1.437 -
1.438 - ///\todo It can copy between different types.
1.439 - ///
1.440 - template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
1.441 - DynMapBase<Edge>(*m.G)
1.442 - {
1.443 - G->dyn_node_maps.push_back(this);
1.444 - typename std::vector<TT>::const_iterator i;
1.445 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
1.446 - i!=m.container.end();
1.447 - i++)
1.448 - container.push_back(*i);
1.449 - }
1.450 - ~EdgeMap()
1.451 - {
1.452 - if(G) {
1.453 - std::vector<DynMapBase<Edge>* >::iterator i;
1.454 - for(i=G->dyn_edge_maps.begin();
1.455 - i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
1.456 - //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
1.457 - //A better way to do that: (Is this really important?)
1.458 - if(*i==this) {
1.459 - *i=G->dyn_edge_maps.back();
1.460 - G->dyn_edge_maps.pop_back();
1.461 - }
1.462 - }
1.463 - }
1.464 -
1.465 - void add(const Edge k)
1.466 - {
1.467 - if(k.n>=int(container.size())) container.resize(k.n+1);
1.468 - }
1.469 - void erase(const Edge) { }
1.470 -
1.471 - void set(Edge n, T a) { container[n.n]=a; }
1.472 - //T get(Edge n) const { return container[n.n]; }
1.473 - typename std::vector<T>::reference
1.474 - operator[](Edge n) { return container[n.n]; }
1.475 - typename std::vector<T>::const_reference
1.476 - operator[](Edge n) const { return container[n.n]; }
1.477 -
1.478 - ///\warning There is no safety check at all!
1.479 - ///Using operator = between maps attached to different graph may
1.480 - ///cause serious problem.
1.481 - ///\todo Is this really so?
1.482 - ///\todo It can copy between different types.
1.483 - const EdgeMap<T>& operator=(const EdgeMap<T> &m)
1.484 - {
1.485 - container = m.container;
1.486 - return *this;
1.487 - }
1.488 - template<typename TT>
1.489 - const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
1.490 - {
1.491 - copy(m.container.begin(), m.container.end(), container.begin());
1.492 - return *this;
1.493 - }
1.494 -
1.495 - void update() {} //Useless for DynMaps
1.496 - void update(T a) {} //Useless for DynMaps
1.497 - };
1.498 -
1.499 - };
1.500 -
1.501 - ///Graph for bidirectional edges.
1.502 -
1.503 - ///The purpose of this graph structure is to handle graphs
1.504 - ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
1.505 - ///of oppositely directed edges.
1.506 - ///There is a new edge map type called
1.507 - ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"
1.508 - ///that complements this
1.509 - ///feature by
1.510 - ///storing shared values for the edge pairs. The usual
1.511 - ///\ref GraphSkeleton::EdgeMap "EdgeMap"
1.512 - ///can be used
1.513 - ///as well.
1.514 - ///
1.515 - ///The oppositely directed edge can also be obtained easily
1.516 - ///using \ref opposite.
1.517 - ///\warning It shares the similarity with \ref SmartGraph that
1.518 - ///it is not possible to delete edges or nodes from the graph.
1.519 - //\sa \ref SmartGraph.
1.520 -
1.521 - class SymSmartGraph : public SmartGraph
1.522 - {
1.523 - public:
1.524 - template<typename T> class SymEdgeMap;
1.525 - template<typename T> friend class SymEdgeMap;
1.526 -
1.527 - SymSmartGraph() : SmartGraph() { }
1.528 - SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
1.529 - Edge addEdge(Node u, Node v)
1.530 - {
1.531 - Edge e = SmartGraph::addEdge(u,v);
1.532 - SmartGraph::addEdge(v,u);
1.533 - return e;
1.534 - }
1.535 -
1.536 - ///The oppositely directed edge.
1.537 -
1.538 - ///Returns the oppositely directed
1.539 - ///pair of the edge \c e.
1.540 - Edge opposite(Edge e) const
1.541 - {
1.542 - Edge f;
1.543 - f.idref() = e.idref() - 2*(e.idref()%2) + 1;
1.544 - return f;
1.545 - }
1.546 -
1.547 - ///Common data storage for the edge pairs.
1.548 -
1.549 - ///This map makes it possible to store data shared by the oppositely
1.550 - ///directed pairs of edges.
1.551 - template <typename T> class SymEdgeMap : public DynMapBase<Edge>
1.552 - {
1.553 - std::vector<T> container;
1.554 -
1.555 - public:
1.556 - typedef T ValueType;
1.557 - typedef Edge KeyType;
1.558 -
1.559 - SymEdgeMap(const SymSmartGraph &_G) :
1.560 - DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
1.561 - {
1.562 - static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.push_back(this);
1.563 - }
1.564 - SymEdgeMap(const SymSmartGraph &_G,const T &t) :
1.565 - DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
1.566 - {
1.567 - G->dyn_edge_maps.push_back(this);
1.568 - }
1.569 -
1.570 - SymEdgeMap(const SymEdgeMap<T> &m) :
1.571 - DynMapBase<SymEdge>(*m.G), container(m.container)
1.572 - {
1.573 - G->dyn_node_maps.push_back(this);
1.574 - }
1.575 -
1.576 - // template<typename TT> friend class SymEdgeMap;
1.577 -
1.578 - ///\todo It can copy between different types.
1.579 - ///
1.580 -
1.581 - template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
1.582 - DynMapBase<SymEdge>(*m.G)
1.583 - {
1.584 - G->dyn_node_maps.push_back(this);
1.585 - typename std::vector<TT>::const_iterator i;
1.586 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
1.587 - i!=m.container.end();
1.588 - i++)
1.589 - container.push_back(*i);
1.590 - }
1.591 -
1.592 - ~SymEdgeMap()
1.593 - {
1.594 - if(G) {
1.595 - std::vector<DynMapBase<Edge>* >::iterator i;
1.596 - for(i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.begin();
1.597 - i!=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.end()
1.598 - && *i!=this; ++i) ;
1.599 - //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
1.600 - //A better way to do that: (Is this really important?)
1.601 - if(*i==this) {
1.602 - *i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.back();
1.603 - static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.pop_back();
1.604 - }
1.605 - }
1.606 - }
1.607 -
1.608 - void add(const Edge k)
1.609 - {
1.610 - if(!k.idref()%2&&k.idref()/2>=int(container.size()))
1.611 - container.resize(k.idref()/2+1);
1.612 - }
1.613 - void erase(const Edge k) { }
1.614 -
1.615 - void set(Edge n, T a) { container[n.idref()/2]=a; }
1.616 - //T get(Edge n) const { return container[n.idref()/2]; }
1.617 - typename std::vector<T>::reference
1.618 - operator[](Edge n) { return container[n.idref()/2]; }
1.619 - typename std::vector<T>::const_reference
1.620 - operator[](Edge n) const { return container[n.idref()/2]; }
1.621 -
1.622 - ///\warning There is no safety check at all!
1.623 - ///Using operator = between maps attached to different graph may
1.624 - ///cause serious problem.
1.625 - ///\todo Is this really so?
1.626 - ///\todo It can copy between different types.
1.627 - const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
1.628 - {
1.629 - container = m.container;
1.630 - return *this;
1.631 - }
1.632 - template<typename TT>
1.633 - const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
1.634 - {
1.635 - copy(m.container.begin(), m.container.end(), container.begin());
1.636 - return *this;
1.637 - }
1.638 -
1.639 - void update() {} //Useless for DynMaps
1.640 - void update(T a) {} //Useless for DynMaps
1.641 -
1.642 - };
1.643 -
1.644 - };
1.645 -
1.646 -
1.647 -} //namespace hugo
1.648 -
1.649 -
1.650 -
1.651 -
1.652 -#endif //SMART_GRAPH_H