src/include/smart_graph.h
author alpar
Fri, 16 Apr 2004 21:18:40 +0000
changeset 342 c98125b3f47c
parent 253 f45703336699
child 353 eeae2f4a0d74
permissions -rw-r--r--
An example for a readable/writeable but non-referrable map
without get() and set().
alpar@105
     1
// -*- mode:C++ -*-
alpar@105
     2
alpar@185
     3
#ifndef HUGO_SMART_GRAPH_H
alpar@185
     4
#define HUGO_SMART_GRAPH_H
alpar@104
     5
alpar@242
     6
///\file
alpar@242
     7
///\brief SmartGraph and SymSmartGraph classes.
alpar@242
     8
alpar@104
     9
#include <vector>
alpar@129
    10
#include <limits.h>
alpar@104
    11
alpar@253
    12
#include "invalid.h"
alpar@157
    13
alpar@105
    14
namespace hugo {
alpar@104
    15
alpar@185
    16
  class SymSmartGraph;
alpar@185
    17
alpar@186
    18
  ///A smart graph class.
alpar@186
    19
alpar@186
    20
  ///This is a simple and fast graph implementation.
alpar@186
    21
  ///It is also quite memory efficient, but at the price
alpar@186
    22
  ///that <b> it does not support node and edge deletion</b>.
alpar@242
    23
  ///It conforms to the graph interface documented under
alpar@186
    24
  ///the description of \ref GraphSkeleton.
alpar@186
    25
  ///\sa \ref GraphSkeleton.
alpar@104
    26
  class SmartGraph {
alpar@104
    27
alpar@104
    28
    struct NodeT 
alpar@104
    29
    {
alpar@104
    30
      int first_in,first_out;      
alpar@157
    31
      NodeT() : first_in(-1), first_out(-1) {}
alpar@104
    32
    };
alpar@104
    33
    struct EdgeT 
alpar@104
    34
    {
alpar@104
    35
      int head, tail, next_in, next_out;      
alpar@104
    36
      //FIXME: is this necessary?
alpar@157
    37
      EdgeT() : next_in(-1), next_out(-1) {}  
alpar@104
    38
    };
alpar@104
    39
alpar@104
    40
    std::vector<NodeT> nodes;
alpar@129
    41
alpar@104
    42
    std::vector<EdgeT> edges;
alpar@104
    43
    
alpar@185
    44
    protected:
alpar@185
    45
    
alpar@108
    46
    template <typename Key> class DynMapBase
alpar@108
    47
    {
alpar@108
    48
    protected:
alpar@185
    49
      const SmartGraph* G; 
alpar@108
    50
    public:
alpar@108
    51
      virtual void add(const Key k) = NULL;
alpar@108
    52
      virtual void erase(const Key k) = NULL;
alpar@157
    53
      DynMapBase(const SmartGraph &_G) : G(&_G) {}
alpar@108
    54
      virtual ~DynMapBase() {}
alpar@108
    55
      friend class SmartGraph;
alpar@108
    56
    };
alpar@185
    57
    
alpar@104
    58
  public:
alpar@185
    59
    template <typename T> class EdgeMap;
alpar@185
    60
    template <typename T> class EdgeMap;
alpar@104
    61
alpar@164
    62
    class Node;
alpar@164
    63
    class Edge;
alpar@108
    64
alpar@185
    65
    //  protected:
alpar@185
    66
    // HELPME:
alpar@186
    67
  protected:
alpar@185
    68
    ///\bug It must be public because of SymEdgeMap.
alpar@185
    69
    ///
alpar@164
    70
    mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
alpar@185
    71
    ///\bug It must be public because of SymEdgeMap.
alpar@185
    72
    ///
alpar@164
    73
    mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
alpar@108
    74
    
alpar@108
    75
  public:
alpar@108
    76
alpar@164
    77
    class NodeIt;
alpar@164
    78
    class EdgeIt;
alpar@104
    79
    class OutEdgeIt;
alpar@104
    80
    class InEdgeIt;
alpar@104
    81
    
alpar@105
    82
    template <typename T> class NodeMap;
alpar@104
    83
    template <typename T> class EdgeMap;
alpar@104
    84
    
alpar@104
    85
  public:
alpar@104
    86
alpar@104
    87
    SmartGraph() : nodes(), edges() { }
alpar@136
    88
    SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
alpar@104
    89
    
alpar@108
    90
    ~SmartGraph()
alpar@108
    91
    {
alpar@164
    92
      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
alpar@108
    93
	  i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
alpar@164
    94
      for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
alpar@108
    95
	  i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
alpar@108
    96
    }
alpar@104
    97
alpar@104
    98
    int nodeNum() const { return nodes.size(); }  //FIXME: What is this?
alpar@104
    99
    int edgeNum() const { return edges.size(); }  //FIXME: What is this?
alpar@104
   100
alpar@186
   101
    ///\bug This function does something different than
alpar@186
   102
    ///its name would suggests...
alpar@108
   103
    int maxNodeId() const { return nodes.size(); }  //FIXME: What is this?
alpar@186
   104
    ///\bug This function does something different than
alpar@186
   105
    ///its name would suggests...
alpar@108
   106
    int maxEdgeId() const { return edges.size(); }  //FIXME: What is this?
alpar@108
   107
alpar@164
   108
    Node tail(Edge e) const { return edges[e.n].tail; }
alpar@164
   109
    Node head(Edge e) const { return edges[e.n].head; }
alpar@104
   110
marci@174
   111
    Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
marci@174
   112
    Node aNode(InEdgeIt e) const { return edges[e.n].head; }
alpar@104
   113
marci@174
   114
    Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
marci@174
   115
    Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
alpar@104
   116
alpar@164
   117
    NodeIt& first(NodeIt& v) const { 
alpar@164
   118
      v=NodeIt(*this); return v; }
alpar@164
   119
    EdgeIt& first(EdgeIt& e) const { 
alpar@164
   120
      e=EdgeIt(*this); return e; }
alpar@164
   121
    OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 
alpar@104
   122
      e=OutEdgeIt(*this,v); return e; }
alpar@164
   123
    InEdgeIt& first(InEdgeIt& e, const Node v) const { 
alpar@104
   124
      e=InEdgeIt(*this,v); return e; }
alpar@104
   125
alpar@104
   126
    template< typename It >
alpar@177
   127
    It first() const { It e; first(e); return e; }
alpar@104
   128
alpar@104
   129
    template< typename It >
alpar@177
   130
    It first(Node v) const { It e; first(e,v); return e; }
alpar@104
   131
alpar@164
   132
    bool valid(Edge e) const { return e.n!=-1; }
alpar@164
   133
    bool valid(Node n) const { return n.n!=-1; }
alpar@104
   134
    
alpar@164
   135
    void setInvalid(Edge &e) { e.n=-1; }
alpar@164
   136
    void setInvalid(Node &n) { n.n=-1; }
alpar@129
   137
    
alpar@157
   138
    template <typename It> It getNext(It it) const
alpar@157
   139
    { It tmp(it); return next(tmp); }
alpar@104
   140
marci@174
   141
    NodeIt& next(NodeIt& it) const { 
marci@174
   142
      it.n=(it.n+2)%(nodes.size()+1)-1; 
marci@174
   143
      return it; 
marci@174
   144
    }
alpar@157
   145
    OutEdgeIt& next(OutEdgeIt& it) const
alpar@104
   146
    { it.n=edges[it.n].next_out; return it; }
alpar@157
   147
    InEdgeIt& next(InEdgeIt& it) const
alpar@104
   148
    { it.n=edges[it.n].next_in; return it; }
alpar@164
   149
    EdgeIt& next(EdgeIt& it) const { --it.n; return it; }
alpar@104
   150
alpar@164
   151
    int id(Node v) const { return v.n; }
alpar@164
   152
    int id(Edge e) const { return e.n; }
alpar@104
   153
alpar@164
   154
    Node addNode() {
alpar@164
   155
      Node n; n.n=nodes.size();
alpar@104
   156
      nodes.push_back(NodeT()); //FIXME: Hmmm...
alpar@108
   157
alpar@164
   158
      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
alpar@108
   159
	  i!=dyn_node_maps.end(); ++i) (**i).add(n.n);
alpar@108
   160
alpar@104
   161
      return n;
alpar@104
   162
    }
alpar@108
   163
    
alpar@164
   164
    Edge addEdge(Node u, Node v) {
alpar@164
   165
      Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
alpar@104
   166
      edges[e.n].tail=u.n; edges[e.n].head=v.n;
alpar@104
   167
      edges[e.n].next_out=nodes[u.n].first_out;
alpar@104
   168
      edges[e.n].next_in=nodes[v.n].first_in;
alpar@104
   169
      nodes[u.n].first_out=nodes[v.n].first_in=e.n;
alpar@108
   170
alpar@164
   171
      for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
alpar@157
   172
	  i!=dyn_edge_maps.end(); ++i) (**i).add(e);
alpar@108
   173
alpar@104
   174
      return e;
alpar@104
   175
    }
alpar@104
   176
alpar@104
   177
    void clear() {nodes.clear();edges.clear();}
alpar@104
   178
alpar@164
   179
    class Node {
alpar@104
   180
      friend class SmartGraph;
alpar@104
   181
      template <typename T> friend class NodeMap;
alpar@104
   182
      
alpar@164
   183
      friend class Edge;
alpar@104
   184
      friend class OutEdgeIt;
alpar@104
   185
      friend class InEdgeIt;
alpar@164
   186
      friend class SymEdge;
alpar@104
   187
alpar@104
   188
    protected:
alpar@104
   189
      int n;
alpar@164
   190
      friend int SmartGraph::id(Node v) const; 
alpar@164
   191
      Node(int nn) {n=nn;}
alpar@104
   192
    public:
alpar@164
   193
      Node() {}
alpar@164
   194
      Node (Invalid i) { n=-1; }
alpar@164
   195
      bool operator==(const Node i) const {return n==i.n;}
alpar@164
   196
      bool operator!=(const Node i) const {return n!=i.n;}
alpar@164
   197
      bool operator<(const Node i) const {return n<i.n;}
alpar@104
   198
    };
alpar@104
   199
    
alpar@164
   200
    class NodeIt : public Node {
alpar@104
   201
      friend class SmartGraph;
alpar@104
   202
    public:
alpar@164
   203
      NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
alpar@164
   204
      NodeIt() : Node() { }
alpar@104
   205
    };
alpar@104
   206
alpar@164
   207
    class Edge {
alpar@104
   208
      friend class SmartGraph;
alpar@104
   209
      template <typename T> friend class EdgeMap;
alpar@185
   210
alpar@185
   211
      //template <typename T> friend class SymSmartGraph::SymEdgeMap;      
alpar@185
   212
      //friend Edge SymSmartGraph::opposite(Edge) const;
alpar@104
   213
      
alpar@164
   214
      friend class Node;
alpar@104
   215
      friend class NodeIt;
alpar@104
   216
    protected:
alpar@104
   217
      int n;
alpar@164
   218
      friend int SmartGraph::id(Edge e) const;
alpar@157
   219
alpar@164
   220
      Edge(int nn) {n=nn;}
alpar@104
   221
    public:
alpar@164
   222
      Edge() { }
marci@174
   223
      Edge (Invalid) { n=-1; }
alpar@164
   224
      bool operator==(const Edge i) const {return n==i.n;}
alpar@164
   225
      bool operator!=(const Edge i) const {return n!=i.n;}
alpar@164
   226
      bool operator<(const Edge i) const {return n<i.n;}
alpar@185
   227
      ///\bug This is a workaround until somebody tells me how to
alpar@185
   228
      ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
alpar@185
   229
      int &idref() {return n;}
alpar@185
   230
      const int &idref() const {return n;}
alpar@104
   231
    };
alpar@104
   232
    
alpar@164
   233
    class EdgeIt : public Edge {
alpar@104
   234
      friend class SmartGraph;
alpar@104
   235
    public:
alpar@164
   236
      EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
alpar@164
   237
      EdgeIt (Invalid i) : Edge(i) { }
alpar@164
   238
      EdgeIt() : Edge() { }
alpar@185
   239
      ///\bug This is a workaround until somebody tells me how to
alpar@185
   240
      ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
alpar@185
   241
      int &idref() {return n;}
alpar@104
   242
    };
alpar@104
   243
    
alpar@164
   244
    class OutEdgeIt : public Edge {
alpar@104
   245
      friend class SmartGraph;
alpar@104
   246
    public: 
alpar@164
   247
      OutEdgeIt() : Edge() { }
alpar@164
   248
      OutEdgeIt (Invalid i) : Edge(i) { }
alpar@157
   249
alpar@164
   250
      OutEdgeIt(const SmartGraph& G,const Node v)
alpar@164
   251
	: Edge(G.nodes[v.n].first_out) {}
alpar@104
   252
    };
alpar@104
   253
    
alpar@164
   254
    class InEdgeIt : public Edge {
alpar@104
   255
      friend class SmartGraph;
alpar@104
   256
    public: 
alpar@164
   257
      InEdgeIt() : Edge() { }
alpar@164
   258
      InEdgeIt (Invalid i) : Edge(i) { }
alpar@164
   259
      InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
alpar@104
   260
    };
alpar@105
   261
alpar@185
   262
    template <typename T> class NodeMap : public DynMapBase<Node>
alpar@108
   263
    {
alpar@108
   264
      std::vector<T> container;
alpar@105
   265
alpar@108
   266
    public:
alpar@108
   267
      typedef T ValueType;
alpar@164
   268
      typedef Node KeyType;
alpar@105
   269
alpar@185
   270
      NodeMap(const SmartGraph &_G) :
alpar@164
   271
	DynMapBase<Node>(_G), container(_G.maxNodeId())
alpar@108
   272
      {
alpar@108
   273
	G->dyn_node_maps.push_back(this);
alpar@108
   274
      }
alpar@185
   275
      NodeMap(const SmartGraph &_G,const T &t) :
alpar@185
   276
	DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
alpar@185
   277
      {
alpar@185
   278
	G->dyn_node_maps.push_back(this);
alpar@185
   279
      }
alpar@185
   280
      
alpar@185
   281
      NodeMap(const NodeMap<T> &m) :
alpar@185
   282
 	DynMapBase<Node>(*m.G), container(m.container)
alpar@185
   283
      {
alpar@185
   284
 	G->dyn_node_maps.push_back(this);
alpar@185
   285
      }
alpar@185
   286
alpar@185
   287
      template<typename TT> friend class NodeMap;
alpar@185
   288
 
alpar@185
   289
      ///\todo It can copy between different types.
alpar@185
   290
      ///
alpar@185
   291
      template<typename TT> NodeMap(const NodeMap<TT> &m) :
alpar@185
   292
	DynMapBase<Node>(*m.G)
alpar@185
   293
      {
alpar@185
   294
	G->dyn_node_maps.push_back(this);
alpar@185
   295
	typename std::vector<TT>::const_iterator i;
alpar@185
   296
	for(typename std::vector<TT>::const_iterator i=m.container.begin();
alpar@185
   297
	    i!=m.container.end();
alpar@185
   298
	    i++)
alpar@185
   299
	  container.push_back(*i);
alpar@185
   300
      }
alpar@185
   301
      ~NodeMap()
alpar@108
   302
      {
alpar@108
   303
	if(G) {
alpar@164
   304
	  std::vector<DynMapBase<Node>* >::iterator i;
alpar@108
   305
	  for(i=G->dyn_node_maps.begin();
alpar@108
   306
	      i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
alpar@115
   307
	  //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
alpar@115
   308
	  //A better way to do that: (Is this really important?)
alpar@115
   309
	  if(*i==this) {
alpar@116
   310
	    *i=G->dyn_node_maps.back();
alpar@115
   311
	    G->dyn_node_maps.pop_back();
alpar@115
   312
	  }
alpar@108
   313
	}
alpar@108
   314
      }
alpar@105
   315
alpar@164
   316
      void add(const Node k) 
alpar@108
   317
      {
alpar@185
   318
	if(k.n>=int(container.size())) container.resize(k.n+1);
alpar@108
   319
      }
alpar@177
   320
alpar@215
   321
      void erase(const Node) { }
alpar@108
   322
      
alpar@164
   323
      void set(Node n, T a) { container[n.n]=a; }
alpar@285
   324
      //'T& operator[](Node n)' would be wrong here
alpar@215
   325
      typename std::vector<T>::reference
alpar@215
   326
      operator[](Node n) { return container[n.n]; }
alpar@285
   327
      //'const T& operator[](Node n)' would be wrong here
alpar@215
   328
      typename std::vector<T>::const_reference 
alpar@215
   329
      operator[](Node n) const { return container[n.n]; }
alpar@108
   330
alpar@185
   331
      ///\warning There is no safety check at all!
alpar@185
   332
      ///Using operator = between maps attached to different graph may
alpar@185
   333
      ///cause serious problem.
alpar@185
   334
      ///\todo Is this really so?
alpar@185
   335
      ///\todo It can copy between different types.
alpar@185
   336
      const NodeMap<T>& operator=(const NodeMap<T> &m)
alpar@185
   337
      {
alpar@185
   338
	container = m.container;
alpar@185
   339
	return *this;
alpar@185
   340
      }
alpar@185
   341
      template<typename TT>
alpar@185
   342
      const NodeMap<T>& operator=(const NodeMap<TT> &m)
alpar@185
   343
      {
alpar@185
   344
	copy(m.container.begin(), m.container.end(), container.begin());
alpar@185
   345
	return *this;
alpar@185
   346
      }
alpar@185
   347
      
alpar@285
   348
      void update() {}    //Useless for Dynamic Maps
alpar@285
   349
      void update(T a) {}  //Useless for Dynamic Maps
alpar@108
   350
    };
alpar@108
   351
    
alpar@185
   352
    template <typename T> class EdgeMap : public DynMapBase<Edge>
alpar@108
   353
    {
alpar@108
   354
      std::vector<T> container;
alpar@108
   355
alpar@108
   356
    public:
alpar@108
   357
      typedef T ValueType;
alpar@164
   358
      typedef Edge KeyType;
alpar@108
   359
alpar@185
   360
      EdgeMap(const SmartGraph &_G) :
alpar@164
   361
	DynMapBase<Edge>(_G), container(_G.maxEdgeId())
alpar@108
   362
      {
alpar@108
   363
	//FIXME: What if there are empty Id's?
alpar@115
   364
	//FIXME: Can I use 'this' in a constructor?
alpar@108
   365
	G->dyn_edge_maps.push_back(this);
alpar@108
   366
      }
alpar@185
   367
      EdgeMap(const SmartGraph &_G,const T &t) :
alpar@185
   368
	DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
alpar@185
   369
      {
alpar@185
   370
	G->dyn_edge_maps.push_back(this);
alpar@185
   371
      } 
alpar@185
   372
      EdgeMap(const EdgeMap<T> &m) :
alpar@185
   373
 	DynMapBase<Edge>(*m.G), container(m.container)
alpar@185
   374
      {
alpar@185
   375
 	G->dyn_node_maps.push_back(this);
alpar@185
   376
      }
alpar@185
   377
alpar@185
   378
      template<typename TT> friend class EdgeMap;
alpar@185
   379
alpar@185
   380
      ///\todo It can copy between different types.
alpar@185
   381
      ///
alpar@185
   382
      template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
alpar@185
   383
	DynMapBase<Edge>(*m.G)
alpar@185
   384
      {
alpar@185
   385
	G->dyn_node_maps.push_back(this);
alpar@185
   386
	typename std::vector<TT>::const_iterator i;
alpar@185
   387
	for(typename std::vector<TT>::const_iterator i=m.container.begin();
alpar@185
   388
	    i!=m.container.end();
alpar@185
   389
	    i++)
alpar@185
   390
	  container.push_back(*i);
alpar@185
   391
      }
alpar@185
   392
      ~EdgeMap()
alpar@108
   393
      {
alpar@108
   394
	if(G) {
alpar@164
   395
	  std::vector<DynMapBase<Edge>* >::iterator i;
alpar@108
   396
	  for(i=G->dyn_edge_maps.begin();
alpar@108
   397
	      i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
alpar@115
   398
	  //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
alpar@115
   399
	  //A better way to do that: (Is this really important?)
alpar@115
   400
	  if(*i==this) {
alpar@116
   401
	    *i=G->dyn_edge_maps.back();
alpar@115
   402
	    G->dyn_edge_maps.pop_back();
alpar@115
   403
	  }
alpar@108
   404
	}
alpar@108
   405
      }
alpar@115
   406
      
alpar@164
   407
      void add(const Edge k) 
alpar@108
   408
      {
alpar@108
   409
	if(k.n>=int(container.size())) container.resize(k.n+1);
alpar@108
   410
      }
alpar@215
   411
      void erase(const Edge) { }
alpar@108
   412
      
alpar@164
   413
      void set(Edge n, T a) { container[n.n]=a; }
alpar@209
   414
      //T get(Edge n) const { return container[n.n]; }
alpar@215
   415
      typename std::vector<T>::reference
alpar@215
   416
      operator[](Edge n) { return container[n.n]; }
alpar@215
   417
      typename std::vector<T>::const_reference
alpar@215
   418
      operator[](Edge n) const { return container[n.n]; }
alpar@108
   419
alpar@185
   420
      ///\warning There is no safety check at all!
alpar@185
   421
      ///Using operator = between maps attached to different graph may
alpar@185
   422
      ///cause serious problem.
alpar@185
   423
      ///\todo Is this really so?
alpar@185
   424
      ///\todo It can copy between different types.
alpar@185
   425
      const EdgeMap<T>& operator=(const EdgeMap<T> &m)
alpar@185
   426
      {
alpar@185
   427
	container = m.container;
alpar@185
   428
	return *this;
alpar@185
   429
      }
alpar@185
   430
      template<typename TT>
alpar@185
   431
      const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
alpar@185
   432
      {
alpar@185
   433
	copy(m.container.begin(), m.container.end(), container.begin());
alpar@185
   434
	return *this;
alpar@185
   435
      }
alpar@185
   436
      
alpar@108
   437
      void update() {}    //Useless for DynMaps
alpar@108
   438
      void update(T a) {}  //Useless for DynMaps
alpar@108
   439
    };
alpar@185
   440
alpar@104
   441
  };
alpar@185
   442
alpar@185
   443
  ///Graph for bidirectional edges.
alpar@185
   444
alpar@185
   445
  ///The purpose of this graph structure is to handle graphs
alpar@185
   446
  ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
alpar@186
   447
  ///of oppositely directed edges.
alpar@186
   448
  ///There is a new edge map type called
alpar@186
   449
  ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"
alpar@186
   450
  ///that complements this
alpar@186
   451
  ///feature by
alpar@186
   452
  ///storing shared values for the edge pairs. The usual
alpar@186
   453
  ///\ref GraphSkeleton::EdgeMap "EdgeMap"
alpar@186
   454
  ///can be used
alpar@185
   455
  ///as well.
alpar@185
   456
  ///
alpar@186
   457
  ///The oppositely directed edge can also be obtained easily
alpar@186
   458
  ///using \ref opposite.
alpar@186
   459
  ///\warning It shares the similarity with \ref SmartGraph that
alpar@186
   460
  ///it is not possible to delete edges or nodes from the graph.
alpar@186
   461
  //\sa \ref SmartGraph.
alpar@185
   462
alpar@185
   463
  class SymSmartGraph : public SmartGraph
alpar@185
   464
  {
alpar@185
   465
  public:
alpar@186
   466
    template<typename T> class SymEdgeMap;
alpar@186
   467
    template<typename T> friend class SymEdgeMap;
alpar@186
   468
alpar@185
   469
    SymSmartGraph() : SmartGraph() { }
alpar@185
   470
    SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
alpar@185
   471
    Edge addEdge(Node u, Node v)
alpar@185
   472
    {
alpar@185
   473
      Edge e = SmartGraph::addEdge(u,v);
alpar@185
   474
      SmartGraph::addEdge(v,u);
alpar@185
   475
      return e;
alpar@185
   476
    }
alpar@185
   477
alpar@186
   478
    ///The oppositely directed edge.
alpar@186
   479
alpar@186
   480
    ///Returns the oppositely directed
alpar@186
   481
    ///pair of the edge \c e.
alpar@185
   482
    Edge opposite(Edge e) const
alpar@185
   483
    {
alpar@185
   484
      Edge f;
alpar@185
   485
      f.idref() = e.idref() - 2*(e.idref()%2) + 1;
alpar@185
   486
      return f;
alpar@185
   487
    }
alpar@185
   488
    
alpar@186
   489
    ///Common data storage for the edge pairs.
alpar@186
   490
alpar@186
   491
    ///This map makes it possible to store data shared by the oppositely
alpar@186
   492
    ///directed pairs of edges.
alpar@185
   493
    template <typename T> class SymEdgeMap : public DynMapBase<Edge>
alpar@185
   494
    {
alpar@185
   495
      std::vector<T> container;
alpar@185
   496
      
alpar@185
   497
    public:
alpar@185
   498
      typedef T ValueType;
alpar@185
   499
      typedef Edge KeyType;
alpar@185
   500
alpar@186
   501
      SymEdgeMap(const SymSmartGraph &_G) :
alpar@185
   502
	DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
alpar@185
   503
      {
alpar@186
   504
	static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.push_back(this);
alpar@185
   505
      }
alpar@186
   506
      SymEdgeMap(const SymSmartGraph &_G,const T &t) :
alpar@185
   507
	DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
alpar@185
   508
      {
alpar@185
   509
	G->dyn_edge_maps.push_back(this);
alpar@185
   510
      }
alpar@185
   511
alpar@185
   512
      SymEdgeMap(const SymEdgeMap<T> &m) :
alpar@185
   513
 	DynMapBase<SymEdge>(*m.G), container(m.container)
alpar@185
   514
      {
alpar@185
   515
 	G->dyn_node_maps.push_back(this);
alpar@185
   516
      }
alpar@185
   517
alpar@185
   518
      //      template<typename TT> friend class SymEdgeMap;
alpar@185
   519
alpar@185
   520
      ///\todo It can copy between different types.
alpar@185
   521
      ///
alpar@185
   522
alpar@185
   523
      template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
alpar@185
   524
	DynMapBase<SymEdge>(*m.G)
alpar@185
   525
      {
alpar@185
   526
	G->dyn_node_maps.push_back(this);
alpar@185
   527
	typename std::vector<TT>::const_iterator i;
alpar@185
   528
	for(typename std::vector<TT>::const_iterator i=m.container.begin();
alpar@185
   529
	    i!=m.container.end();
alpar@185
   530
	    i++)
alpar@185
   531
	  container.push_back(*i);
alpar@185
   532
      }
alpar@185
   533
 
alpar@185
   534
      ~SymEdgeMap()
alpar@185
   535
      {
alpar@185
   536
	if(G) {
alpar@185
   537
	  std::vector<DynMapBase<Edge>* >::iterator i;
alpar@186
   538
	  for(i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.begin();
alpar@186
   539
	      i!=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.end()
alpar@186
   540
		&& *i!=this; ++i) ;
alpar@185
   541
	  //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
alpar@185
   542
	  //A better way to do that: (Is this really important?)
alpar@185
   543
	  if(*i==this) {
alpar@186
   544
	    *i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.back();
alpar@186
   545
	    static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.pop_back();
alpar@185
   546
	  }
alpar@185
   547
	}
alpar@185
   548
      }
alpar@185
   549
      
alpar@185
   550
      void add(const Edge k) 
alpar@185
   551
      {
alpar@185
   552
	if(!k.idref()%2&&k.idref()/2>=int(container.size()))
alpar@185
   553
	  container.resize(k.idref()/2+1);
alpar@185
   554
      }
alpar@185
   555
      void erase(const Edge k) { }
alpar@185
   556
      
alpar@185
   557
      void set(Edge n, T a) { container[n.idref()/2]=a; }
alpar@209
   558
      //T get(Edge n) const { return container[n.idref()/2]; }
alpar@215
   559
      typename std::vector<T>::reference
alpar@215
   560
      operator[](Edge n) { return container[n.idref()/2]; }
alpar@215
   561
      typename std::vector<T>::const_reference
alpar@215
   562
      operator[](Edge n) const { return container[n.idref()/2]; }
alpar@185
   563
alpar@185
   564
      ///\warning There is no safety check at all!
alpar@185
   565
      ///Using operator = between maps attached to different graph may
alpar@185
   566
      ///cause serious problem.
alpar@185
   567
      ///\todo Is this really so?
alpar@185
   568
      ///\todo It can copy between different types.
alpar@185
   569
      const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
alpar@185
   570
      {
alpar@185
   571
	container = m.container;
alpar@185
   572
	return *this;
alpar@185
   573
      }
alpar@185
   574
      template<typename TT>
alpar@185
   575
      const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
alpar@185
   576
      {
alpar@185
   577
	copy(m.container.begin(), m.container.end(), container.begin());
alpar@185
   578
	return *this;
alpar@185
   579
      }
alpar@185
   580
      
alpar@185
   581
      void update() {}    //Useless for DynMaps
alpar@185
   582
      void update(T a) {}  //Useless for DynMaps
alpar@185
   583
alpar@185
   584
    };
alpar@185
   585
alpar@185
   586
  };
alpar@185
   587
  
alpar@185
   588
  
alpar@105
   589
} //namespace hugo
alpar@104
   590
alpar@157
   591
alpar@157
   592
alpar@157
   593
alpar@104
   594
#endif //SMART_GRAPH_H