1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/include/smart_graph.h Mon Mar 29 08:16:18 2004 +0000
1.3 @@ -0,0 +1,649 @@
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