For the future "node_set" and "edge_set" structures.
authoralpar
Sun, 25 Apr 2004 14:20:36 +0000
changeset 395b619f369a9ef
parent 394 3a34c5626e52
child 396 639c9daed784
For the future "node_set" and "edge_set" structures.
src/work/alpar/smart_graph.h
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/work/alpar/smart_graph.h	Sun Apr 25 14:20:36 2004 +0000
     1.3 @@ -0,0 +1,594 @@
     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 +    template <typename T> class NodeMap;
    1.86 +    template <typename T> class EdgeMap;
    1.87 +    
    1.88 +  public:
    1.89 +
    1.90 +    SmartGraph() : nodes(), edges() { }
    1.91 +    SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
    1.92 +    
    1.93 +    ~SmartGraph()
    1.94 +    {
    1.95 +      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
    1.96 +	  i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
    1.97 +      for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
    1.98 +	  i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
    1.99 +    }
   1.100 +
   1.101 +    int nodeNum() const { return nodes.size(); }  //FIXME: What is this?
   1.102 +    int edgeNum() const { return edges.size(); }  //FIXME: What is this?
   1.103 +
   1.104 +    ///\bug This function does something different than
   1.105 +    ///its name would suggests...
   1.106 +    int maxNodeId() const { return nodes.size(); }  //FIXME: What is this?
   1.107 +    ///\bug This function does something different than
   1.108 +    ///its name would suggests...
   1.109 +    int maxEdgeId() const { return edges.size(); }  //FIXME: What is this?
   1.110 +
   1.111 +    Node tail(Edge e) const { return edges[e.n].tail; }
   1.112 +    Node head(Edge e) const { return edges[e.n].head; }
   1.113 +
   1.114 +    Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
   1.115 +    Node aNode(InEdgeIt e) const { return edges[e.n].head; }
   1.116 +
   1.117 +    Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
   1.118 +    Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
   1.119 +
   1.120 +    NodeIt& first(NodeIt& v) const { 
   1.121 +      v=NodeIt(*this); return v; }
   1.122 +    EdgeIt& first(EdgeIt& e) const { 
   1.123 +      e=EdgeIt(*this); return e; }
   1.124 +    OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 
   1.125 +      e=OutEdgeIt(*this,v); return e; }
   1.126 +    InEdgeIt& first(InEdgeIt& e, const Node v) const { 
   1.127 +      e=InEdgeIt(*this,v); return e; }
   1.128 +
   1.129 +//     template< typename It >
   1.130 +//     It first() const { It e; first(e); return e; }
   1.131 +
   1.132 +//     template< typename It >
   1.133 +//     It first(Node v) const { It e; first(e,v); return e; }
   1.134 +
   1.135 +    bool valid(Edge e) const { return e.n!=-1; }
   1.136 +    bool valid(Node n) const { return n.n!=-1; }
   1.137 +    
   1.138 +    void setInvalid(Edge &e) { e.n=-1; }
   1.139 +    void setInvalid(Node &n) { n.n=-1; }
   1.140 +    
   1.141 +    template <typename It> It getNext(It it) const
   1.142 +    { It tmp(it); return next(tmp); }
   1.143 +
   1.144 +    NodeIt& next(NodeIt& it) const { 
   1.145 +      it.n=(it.n+2)%(nodes.size()+1)-1; 
   1.146 +      return it; 
   1.147 +    }
   1.148 +    OutEdgeIt& next(OutEdgeIt& it) const
   1.149 +    { it.n=edges[it.n].next_out; return it; }
   1.150 +    InEdgeIt& next(InEdgeIt& it) const
   1.151 +    { it.n=edges[it.n].next_in; return it; }
   1.152 +    EdgeIt& next(EdgeIt& it) const { --it.n; return it; }
   1.153 +
   1.154 +    int id(Node v) const { return v.n; }
   1.155 +    int id(Edge e) const { return e.n; }
   1.156 +
   1.157 +    Node addNode() {
   1.158 +      Node n; n.n=nodes.size();
   1.159 +      nodes.push_back(NodeT()); //FIXME: Hmmm...
   1.160 +
   1.161 +      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
   1.162 +	  i!=dyn_node_maps.end(); ++i) (**i).add(n.n);
   1.163 +
   1.164 +      return n;
   1.165 +    }
   1.166 +    
   1.167 +    Edge addEdge(Node u, Node v) {
   1.168 +      Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
   1.169 +      edges[e.n].tail=u.n; edges[e.n].head=v.n;
   1.170 +      edges[e.n].next_out=nodes[u.n].first_out;
   1.171 +      edges[e.n].next_in=nodes[v.n].first_in;
   1.172 +      nodes[u.n].first_out=nodes[v.n].first_in=e.n;
   1.173 +
   1.174 +      for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
   1.175 +	  i!=dyn_edge_maps.end(); ++i) (**i).add(e);
   1.176 +
   1.177 +      return e;
   1.178 +    }
   1.179 +
   1.180 +    void clear() {nodes.clear();edges.clear();}
   1.181 +
   1.182 +    class Node {
   1.183 +      friend class SmartGraph;
   1.184 +      template <typename T> friend class NodeMap;
   1.185 +      
   1.186 +      friend class Edge;
   1.187 +      friend class OutEdgeIt;
   1.188 +      friend class InEdgeIt;
   1.189 +      friend class SymEdge;
   1.190 +
   1.191 +    protected:
   1.192 +      int n;
   1.193 +      friend int SmartGraph::id(Node v) const; 
   1.194 +      Node(int nn) {n=nn;}
   1.195 +    public:
   1.196 +      Node() {}
   1.197 +      Node (Invalid i) { n=-1; }
   1.198 +      bool operator==(const Node i) const {return n==i.n;}
   1.199 +      bool operator!=(const Node i) const {return n!=i.n;}
   1.200 +      bool operator<(const Node i) const {return n<i.n;}
   1.201 +    };
   1.202 +    
   1.203 +    class NodeIt : public Node {
   1.204 +      friend class SmartGraph;
   1.205 +    public:
   1.206 +      NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
   1.207 +      NodeIt() : Node() { }
   1.208 +    };
   1.209 +
   1.210 +    class Edge {
   1.211 +      friend class SmartGraph;
   1.212 +      template <typename T> friend class EdgeMap;
   1.213 +
   1.214 +      //template <typename T> friend class SymSmartGraph::SymEdgeMap;      
   1.215 +      //friend Edge SymSmartGraph::opposite(Edge) const;
   1.216 +      
   1.217 +      friend class Node;
   1.218 +      friend class NodeIt;
   1.219 +    protected:
   1.220 +      int n;
   1.221 +      friend int SmartGraph::id(Edge e) const;
   1.222 +
   1.223 +      Edge(int nn) {n=nn;}
   1.224 +    public:
   1.225 +      Edge() { }
   1.226 +      Edge (Invalid) { n=-1; }
   1.227 +      bool operator==(const Edge i) const {return n==i.n;}
   1.228 +      bool operator!=(const Edge i) const {return n!=i.n;}
   1.229 +      bool operator<(const Edge i) const {return n<i.n;}
   1.230 +      ///\bug This is a workaround until somebody tells me how to
   1.231 +      ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
   1.232 +      int &idref() {return n;}
   1.233 +      const int &idref() const {return n;}
   1.234 +    };
   1.235 +    
   1.236 +    class EdgeIt : public Edge {
   1.237 +      friend class SmartGraph;
   1.238 +    public:
   1.239 +      EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
   1.240 +      EdgeIt (Invalid i) : Edge(i) { }
   1.241 +      EdgeIt() : Edge() { }
   1.242 +      ///\bug This is a workaround until somebody tells me how to
   1.243 +      ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
   1.244 +      int &idref() {return n;}
   1.245 +    };
   1.246 +    
   1.247 +    class OutEdgeIt : public Edge {
   1.248 +      friend class SmartGraph;
   1.249 +    public: 
   1.250 +      OutEdgeIt() : Edge() { }
   1.251 +      OutEdgeIt (Invalid i) : Edge(i) { }
   1.252 +
   1.253 +      OutEdgeIt(const SmartGraph& G,const Node v)
   1.254 +	: Edge(G.nodes[v.n].first_out) {}
   1.255 +    };
   1.256 +    
   1.257 +    class InEdgeIt : public Edge {
   1.258 +      friend class SmartGraph;
   1.259 +    public: 
   1.260 +      InEdgeIt() : Edge() { }
   1.261 +      InEdgeIt (Invalid i) : Edge(i) { }
   1.262 +      InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
   1.263 +    };
   1.264 +
   1.265 +    template <typename T> class NodeMap : public DynMapBase<Node>
   1.266 +    {
   1.267 +      std::vector<T> container;
   1.268 +
   1.269 +    public:
   1.270 +      typedef T ValueType;
   1.271 +      typedef Node KeyType;
   1.272 +
   1.273 +      NodeMap(const SmartGraph &_G) :
   1.274 +	DynMapBase<Node>(_G), container(_G.maxNodeId())
   1.275 +      {
   1.276 +	G->dyn_node_maps.push_back(this);
   1.277 +      }
   1.278 +      NodeMap(const SmartGraph &_G,const T &t) :
   1.279 +	DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
   1.280 +      {
   1.281 +	G->dyn_node_maps.push_back(this);
   1.282 +      }
   1.283 +      
   1.284 +      NodeMap(const NodeMap<T> &m) :
   1.285 + 	DynMapBase<Node>(*m.G), container(m.container)
   1.286 +      {
   1.287 + 	G->dyn_node_maps.push_back(this);
   1.288 +      }
   1.289 +
   1.290 +      template<typename TT> friend class NodeMap;
   1.291 + 
   1.292 +      ///\todo It can copy between different types.
   1.293 +      ///
   1.294 +      template<typename TT> NodeMap(const NodeMap<TT> &m) :
   1.295 +	DynMapBase<Node>(*m.G)
   1.296 +      {
   1.297 +	G->dyn_node_maps.push_back(this);
   1.298 +	typename std::vector<TT>::const_iterator i;
   1.299 +	for(typename std::vector<TT>::const_iterator i=m.container.begin();
   1.300 +	    i!=m.container.end();
   1.301 +	    i++)
   1.302 +	  container.push_back(*i);
   1.303 +      }
   1.304 +      ~NodeMap()
   1.305 +      {
   1.306 +	if(G) {
   1.307 +	  std::vector<DynMapBase<Node>* >::iterator i;
   1.308 +	  for(i=G->dyn_node_maps.begin();
   1.309 +	      i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
   1.310 +	  //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
   1.311 +	  //A better way to do that: (Is this really important?)
   1.312 +	  if(*i==this) {
   1.313 +	    *i=G->dyn_node_maps.back();
   1.314 +	    G->dyn_node_maps.pop_back();
   1.315 +	  }
   1.316 +	}
   1.317 +      }
   1.318 +
   1.319 +      void add(const Node k) 
   1.320 +      {
   1.321 +	if(k.n>=int(container.size())) container.resize(k.n+1);
   1.322 +      }
   1.323 +
   1.324 +      void erase(const Node) { }
   1.325 +      
   1.326 +      void set(Node n, T a) { container[n.n]=a; }
   1.327 +      //'T& operator[](Node n)' would be wrong here
   1.328 +      typename std::vector<T>::reference
   1.329 +      operator[](Node n) { return container[n.n]; }
   1.330 +      //'const T& operator[](Node n)' would be wrong here
   1.331 +      typename std::vector<T>::const_reference 
   1.332 +      operator[](Node n) const { return container[n.n]; }
   1.333 +
   1.334 +      ///\warning There is no safety check at all!
   1.335 +      ///Using operator = between maps attached to different graph may
   1.336 +      ///cause serious problem.
   1.337 +      ///\todo Is this really so?
   1.338 +      ///\todo It can copy between different types.
   1.339 +      const NodeMap<T>& operator=(const NodeMap<T> &m)
   1.340 +      {
   1.341 +	container = m.container;
   1.342 +	return *this;
   1.343 +      }
   1.344 +      template<typename TT>
   1.345 +      const NodeMap<T>& operator=(const NodeMap<TT> &m)
   1.346 +      {
   1.347 +	copy(m.container.begin(), m.container.end(), container.begin());
   1.348 +	return *this;
   1.349 +      }
   1.350 +      
   1.351 +      void update() {}    //Useless for Dynamic Maps
   1.352 +      void update(T a) {}  //Useless for Dynamic Maps
   1.353 +    };
   1.354 +    
   1.355 +    template <typename T> class EdgeMap : public DynMapBase<Edge>
   1.356 +    {
   1.357 +      std::vector<T> container;
   1.358 +
   1.359 +    public:
   1.360 +      typedef T ValueType;
   1.361 +      typedef Edge KeyType;
   1.362 +
   1.363 +      EdgeMap(const SmartGraph &_G) :
   1.364 +	DynMapBase<Edge>(_G), container(_G.maxEdgeId())
   1.365 +      {
   1.366 +	//FIXME: What if there are empty Id's?
   1.367 +	//FIXME: Can I use 'this' in a constructor?
   1.368 +	G->dyn_edge_maps.push_back(this);
   1.369 +      }
   1.370 +      EdgeMap(const SmartGraph &_G,const T &t) :
   1.371 +	DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
   1.372 +      {
   1.373 +	G->dyn_edge_maps.push_back(this);
   1.374 +      } 
   1.375 +      EdgeMap(const EdgeMap<T> &m) :
   1.376 + 	DynMapBase<Edge>(*m.G), container(m.container)
   1.377 +      {
   1.378 + 	G->dyn_node_maps.push_back(this);
   1.379 +      }
   1.380 +
   1.381 +      template<typename TT> friend class EdgeMap;
   1.382 +
   1.383 +      ///\todo It can copy between different types.
   1.384 +      ///
   1.385 +      template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
   1.386 +	DynMapBase<Edge>(*m.G)
   1.387 +      {
   1.388 +	G->dyn_node_maps.push_back(this);
   1.389 +	typename std::vector<TT>::const_iterator i;
   1.390 +	for(typename std::vector<TT>::const_iterator i=m.container.begin();
   1.391 +	    i!=m.container.end();
   1.392 +	    i++)
   1.393 +	  container.push_back(*i);
   1.394 +      }
   1.395 +      ~EdgeMap()
   1.396 +      {
   1.397 +	if(G) {
   1.398 +	  std::vector<DynMapBase<Edge>* >::iterator i;
   1.399 +	  for(i=G->dyn_edge_maps.begin();
   1.400 +	      i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
   1.401 +	  //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
   1.402 +	  //A better way to do that: (Is this really important?)
   1.403 +	  if(*i==this) {
   1.404 +	    *i=G->dyn_edge_maps.back();
   1.405 +	    G->dyn_edge_maps.pop_back();
   1.406 +	  }
   1.407 +	}
   1.408 +      }
   1.409 +      
   1.410 +      void add(const Edge k) 
   1.411 +      {
   1.412 +	if(k.n>=int(container.size())) container.resize(k.n+1);
   1.413 +      }
   1.414 +      void erase(const Edge) { }
   1.415 +      
   1.416 +      void set(Edge n, T a) { container[n.n]=a; }
   1.417 +      //T get(Edge n) const { return container[n.n]; }
   1.418 +      typename std::vector<T>::reference
   1.419 +      operator[](Edge n) { return container[n.n]; }
   1.420 +      typename std::vector<T>::const_reference
   1.421 +      operator[](Edge n) const { return container[n.n]; }
   1.422 +
   1.423 +      ///\warning There is no safety check at all!
   1.424 +      ///Using operator = between maps attached to different graph may
   1.425 +      ///cause serious problem.
   1.426 +      ///\todo Is this really so?
   1.427 +      ///\todo It can copy between different types.
   1.428 +      const EdgeMap<T>& operator=(const EdgeMap<T> &m)
   1.429 +      {
   1.430 +	container = m.container;
   1.431 +	return *this;
   1.432 +      }
   1.433 +      template<typename TT>
   1.434 +      const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
   1.435 +      {
   1.436 +	copy(m.container.begin(), m.container.end(), container.begin());
   1.437 +	return *this;
   1.438 +      }
   1.439 +      
   1.440 +      void update() {}    //Useless for DynMaps
   1.441 +      void update(T a) {}  //Useless for DynMaps
   1.442 +    };
   1.443 +
   1.444 +  };
   1.445 +
   1.446 +  ///Graph for bidirectional edges.
   1.447 +
   1.448 +  ///The purpose of this graph structure is to handle graphs
   1.449 +  ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
   1.450 +  ///of oppositely directed edges.
   1.451 +  ///There is a new edge map type called
   1.452 +  ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"
   1.453 +  ///that complements this
   1.454 +  ///feature by
   1.455 +  ///storing shared values for the edge pairs. The usual
   1.456 +  ///\ref GraphSkeleton::EdgeMap "EdgeMap"
   1.457 +  ///can be used
   1.458 +  ///as well.
   1.459 +  ///
   1.460 +  ///The oppositely directed edge can also be obtained easily
   1.461 +  ///using \ref opposite.
   1.462 +  ///\warning It shares the similarity with \ref SmartGraph that
   1.463 +  ///it is not possible to delete edges or nodes from the graph.
   1.464 +  //\sa \ref SmartGraph.
   1.465 +
   1.466 +  class SymSmartGraph : public SmartGraph
   1.467 +  {
   1.468 +  public:
   1.469 +    template<typename T> class SymEdgeMap;
   1.470 +    template<typename T> friend class SymEdgeMap;
   1.471 +
   1.472 +    SymSmartGraph() : SmartGraph() { }
   1.473 +    SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
   1.474 +    Edge addEdge(Node u, Node v)
   1.475 +    {
   1.476 +      Edge e = SmartGraph::addEdge(u,v);
   1.477 +      SmartGraph::addEdge(v,u);
   1.478 +      return e;
   1.479 +    }
   1.480 +
   1.481 +    ///The oppositely directed edge.
   1.482 +
   1.483 +    ///Returns the oppositely directed
   1.484 +    ///pair of the edge \c e.
   1.485 +    Edge opposite(Edge e) const
   1.486 +    {
   1.487 +      Edge f;
   1.488 +      f.idref() = e.idref() - 2*(e.idref()%2) + 1;
   1.489 +      return f;
   1.490 +    }
   1.491 +    
   1.492 +    ///Common data storage for the edge pairs.
   1.493 +
   1.494 +    ///This map makes it possible to store data shared by the oppositely
   1.495 +    ///directed pairs of edges.
   1.496 +    template <typename T> class SymEdgeMap : public DynMapBase<Edge>
   1.497 +    {
   1.498 +      std::vector<T> container;
   1.499 +      
   1.500 +    public:
   1.501 +      typedef T ValueType;
   1.502 +      typedef Edge KeyType;
   1.503 +
   1.504 +      SymEdgeMap(const SymSmartGraph &_G) :
   1.505 +	DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
   1.506 +      {
   1.507 +	static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.push_back(this);
   1.508 +      }
   1.509 +      SymEdgeMap(const SymSmartGraph &_G,const T &t) :
   1.510 +	DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
   1.511 +      {
   1.512 +	G->dyn_edge_maps.push_back(this);
   1.513 +      }
   1.514 +
   1.515 +      SymEdgeMap(const SymEdgeMap<T> &m) :
   1.516 + 	DynMapBase<SymEdge>(*m.G), container(m.container)
   1.517 +      {
   1.518 + 	G->dyn_node_maps.push_back(this);
   1.519 +      }
   1.520 +
   1.521 +      //      template<typename TT> friend class SymEdgeMap;
   1.522 +
   1.523 +      ///\todo It can copy between different types.
   1.524 +      ///
   1.525 +
   1.526 +      template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
   1.527 +	DynMapBase<SymEdge>(*m.G)
   1.528 +      {
   1.529 +	G->dyn_node_maps.push_back(this);
   1.530 +	typename std::vector<TT>::const_iterator i;
   1.531 +	for(typename std::vector<TT>::const_iterator i=m.container.begin();
   1.532 +	    i!=m.container.end();
   1.533 +	    i++)
   1.534 +	  container.push_back(*i);
   1.535 +      }
   1.536 + 
   1.537 +      ~SymEdgeMap()
   1.538 +      {
   1.539 +	if(G) {
   1.540 +	  std::vector<DynMapBase<Edge>* >::iterator i;
   1.541 +	  for(i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.begin();
   1.542 +	      i!=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.end()
   1.543 +		&& *i!=this; ++i) ;
   1.544 +	  //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
   1.545 +	  //A better way to do that: (Is this really important?)
   1.546 +	  if(*i==this) {
   1.547 +	    *i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.back();
   1.548 +	    static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.pop_back();
   1.549 +	  }
   1.550 +	}
   1.551 +      }
   1.552 +      
   1.553 +      void add(const Edge k) 
   1.554 +      {
   1.555 +	if(!k.idref()%2&&k.idref()/2>=int(container.size()))
   1.556 +	  container.resize(k.idref()/2+1);
   1.557 +      }
   1.558 +      void erase(const Edge k) { }
   1.559 +      
   1.560 +      void set(Edge n, T a) { container[n.idref()/2]=a; }
   1.561 +      //T get(Edge n) const { return container[n.idref()/2]; }
   1.562 +      typename std::vector<T>::reference
   1.563 +      operator[](Edge n) { return container[n.idref()/2]; }
   1.564 +      typename std::vector<T>::const_reference
   1.565 +      operator[](Edge n) const { return container[n.idref()/2]; }
   1.566 +
   1.567 +      ///\warning There is no safety check at all!
   1.568 +      ///Using operator = between maps attached to different graph may
   1.569 +      ///cause serious problem.
   1.570 +      ///\todo Is this really so?
   1.571 +      ///\todo It can copy between different types.
   1.572 +      const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
   1.573 +      {
   1.574 +	container = m.container;
   1.575 +	return *this;
   1.576 +      }
   1.577 +      template<typename TT>
   1.578 +      const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
   1.579 +      {
   1.580 +	copy(m.container.begin(), m.container.end(), container.begin());
   1.581 +	return *this;
   1.582 +      }
   1.583 +      
   1.584 +      void update() {}    //Useless for DynMaps
   1.585 +      void update(T a) {}  //Useless for DynMaps
   1.586 +
   1.587 +    };
   1.588 +
   1.589 +  };
   1.590 +  
   1.591 +  
   1.592 +} //namespace hugo
   1.593 +
   1.594 +
   1.595 +
   1.596 +
   1.597 +#endif //SMART_GRAPH_H