COIN-OR::LEMON - Graph Library

Changeset 782:df2e45e09652 in lemon-0.x


Ignore:
Timestamp:
09/02/04 12:07:30 (15 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1075
Message:

--This line, and those below, will be ignored--

A hugo/sym_map_factory.h
M hugo/list_graph.h
A hugo/array_map_factory.h
A hugo/map_registry.h
M hugo/smart_graph.h
A hugo/map_defines.h
A hugo/extended_pair.h
M hugo/full_graph.h
A hugo/vector_map_factory.h

Location:
src/hugo
Files:
6 added
3 edited

Legend:

Unmodified
Added
Removed
  • src/hugo/full_graph.h

    r774 r782  
    99
    1010#include <vector>
    11 #include <limits.h>
     11#include <climits>
    1212
    1313#include <hugo/invalid.h>
     14
     15#include <hugo/map_registry.h>
     16#include <hugo/array_map_factory.h>
    1417
    1518namespace hugo {
     
    3437    int EdgeNum;
    3538  public:
    36     template <typename T> class EdgeMap;
    37     template <typename T> class NodeMap;
     39
     40    typedef FullGraph Graph;
    3841
    3942    class Node;
    4043    class Edge;
     44
    4145    class NodeIt;
    4246    class EdgeIt;
     
    4448    class InEdgeIt;
    4549   
    46     template <typename T> class NodeMap;
    47     template <typename T> class EdgeMap;
     50    CREATE_MAP_REGISTRIES;
     51    CREATE_MAPS(ArrayMapFactory);
    4852   
    4953  public:
     
    8690    Edge findEdge(Node u,Node v, Edge prev = INVALID)
    8791    {
    88       return prev.n==-1?Edge(*this,u.n,v.n):INVALID;
     92      return prev.n == -1 ? Edge(*this, u.n, v.n) : INVALID;
    8993    }
    9094   
     
    188192    };
    189193
    190     template <typename T> class NodeMap
    191     {
    192       std::vector<T> container;
    193 
    194     public:
    195       typedef T ValueType;
    196       typedef Node KeyType;
    197 
    198       NodeMap(const FullGraph &_G) : container(_G.NodeNum) { }
    199       NodeMap(const FullGraph &_G,const T &t) : container(_G.NodeNum,t) { }
    200       NodeMap(const NodeMap<T> &m) : container(m.container) { }
    201 
    202       template<typename TT> friend class NodeMap;
    203       ///\todo It can copy between different types.
    204       template<typename TT> NodeMap(const NodeMap<TT> &m)
    205         : container(m.container.size())
    206       {
    207         typename std::vector<TT>::const_iterator i;
    208         for(typename std::vector<TT>::const_iterator i=m.container.begin();
    209             i!=m.container.end();
    210             i++)
    211           container.push_back(*i);
    212       }
    213       void set(Node n, T a) { container[n.n]=a; }
    214       //'T& operator[](Node n)' would be wrong here
    215       typename std::vector<T>::reference
    216       operator[](Node n) { return container[n.n]; }
    217       //'const T& operator[](Node n)' would be wrong here
    218       typename std::vector<T>::const_reference
    219       operator[](Node n) const { return container[n.n]; }
    220 
    221       ///\warning There is no safety check at all!
    222       ///Using operator = between maps attached to different graph may
    223       ///cause serious problem.
    224       ///\todo Is this really so?
    225       ///\todo It can copy between different types.
    226       const NodeMap<T>& operator=(const NodeMap<T> &m)
    227       {
    228         container = m.container;
    229         return *this;
    230       }
    231       template<typename TT>
    232       const NodeMap<T>& operator=(const NodeMap<TT> &m)
    233       {
    234         std::copy(m.container.begin(), m.container.end(), container.begin());
    235         return *this;
    236       }
    237      
    238       void update() {}    //Useless for Dynamic Maps
    239       void update(T a) {}  //Useless for Dynamic Maps
    240     };
    241    
    242     template <typename T> class EdgeMap
    243     {
    244       std::vector<T> container;
    245 
    246     public:
    247       typedef T ValueType;
    248       typedef Edge KeyType;
    249 
    250       EdgeMap(const FullGraph &_G) : container(_G.EdgeNum) { }
    251       EdgeMap(const FullGraph &_G,const T &t) : container(_G.EdgeNum,t) { }
    252       EdgeMap(const EdgeMap<T> &m) : container(m.container) { }
    253 
    254       template<typename TT> friend class EdgeMap;
    255       ///\todo It can copy between different types.
    256       ///\todo We could use 'copy'
    257       template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
    258         container(m.container.size())
    259       {
    260         typename std::vector<TT>::const_iterator i;
    261         for(typename std::vector<TT>::const_iterator i=m.container.begin();
    262             i!=m.container.end();
    263             i++)
    264           container.push_back(*i);
    265       }
    266       void set(Edge n, T a) { container[n.n]=a; }
    267       //T get(Edge n) const { return container[n.n]; }
    268       typename std::vector<T>::reference
    269       operator[](Edge n) { return container[n.n]; }
    270       typename std::vector<T>::const_reference
    271       operator[](Edge n) const { return container[n.n]; }
    272 
    273       ///\warning There is no safety check at all!
    274       ///Using operator = between maps attached to different graph may
    275       ///cause serious problem.
    276       ///\todo Is this really so?
    277       ///\todo It can copy between different types.
    278       const EdgeMap<T>& operator=(const EdgeMap<T> &m)
    279       {
    280         container = m.container;
    281         return *this;
    282       }
    283       template<typename TT>
    284       const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
    285       {
    286         std::copy(m.container.begin(), m.container.end(), container.begin());
    287         return *this;
    288       }
    289 
    290       void update() {}
    291       void update(T a) {}
    292     };
    293 
    294194  };
    295195
  • src/hugo/list_graph.h

    r774 r782  
    99
    1010#include <vector>
    11 #include <limits.h>
     11#include <climits>
    1212
    1313#include <hugo/invalid.h>
     14
     15#include <hugo/map_registry.h>
     16#include <hugo/array_map_factory.h>
     17
     18#include <hugo/sym_map_factory.h>
     19
     20#include <hugo/map_defines.h>
     21
    1422
    1523namespace hugo {
     
    1826/// @{
    1927
    20   class SymListGraph;
     28//  class SymListGraph;
    2129
    2230  ///A list graph class.
     
    5765    int first_free_edge;
    5866   
    59   protected:
    60    
    61     template <typename Key> class DynMapBase
    62     {
    63     protected:
    64       const ListGraph* G;
    65     public:
    66       virtual void add(const Key k) = 0;
    67       virtual void erase(const Key k) = 0;
    68       DynMapBase(const ListGraph &_G) : G(&_G) {}
    69       virtual ~DynMapBase() {}
    70       friend class ListGraph;
    71     };
    72    
    73   public:
    74     template <typename T> class EdgeMap;
    75     template <typename T> class NodeMap;
     67  public:
     68   
     69    typedef ListGraph Graph;
    7670   
    7771    class Node;
    7872    class Edge;
    7973
    80     //  protected:
    81     // HELPME:
    82   protected:
    83     ///\bug It must be public because of SymEdgeMap.
    84     ///
    85     mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
    86     ///\bug It must be public because of SymEdgeMap.
    87     ///
    88     mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
    8974   
    9075  public:
     
    9479    class OutEdgeIt;
    9580    class InEdgeIt;
    96    
    97   public:
    98 
    99     ListGraph() : nodes(), first_node(-1),
    100                   first_free_node(-1), edges(), first_free_edge(-1) {}
    101     ListGraph(const ListGraph &_g) : nodes(_g.nodes), first_node(_g.first_node),
    102                                      first_free_node(_g.first_free_node),
    103                                      edges(_g.edges),
    104                                      first_free_edge(_g.first_free_edge) {}
    105    
    106     ~ListGraph()
    107     {
    108       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
    109           i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
    110       for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
    111           i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
    112     }
    113 
     81
     82    CREATE_MAP_REGISTRIES;
     83    CREATE_MAPS(ArrayMapFactory);
     84
     85  public:
     86
     87    ListGraph()
     88      : nodes(), first_node(-1),
     89        first_free_node(-1), edges(), first_free_edge(-1) {}
     90
     91    ListGraph(const ListGraph &_g)
     92      : nodes(_g.nodes), first_node(_g.first_node),
     93        first_free_node(_g.first_free_node), edges(_g.edges),
     94        first_free_edge(_g.first_free_edge) {}
     95   
    11496    int nodeNum() const { return nodes.size(); }  //FIXME: What is this?
    11597    int edgeNum() const { return edges.size(); }  //FIXME: What is this?
     
    171153
    172154      //Update dynamic maps
    173       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
    174           i!=dyn_node_maps.end(); ++i) (**i).add(nn);
     155      node_maps.add(nn);
    175156
    176157      return nn;
     
    203184
    204185      //Update dynamic maps
    205       for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
    206           i!=dyn_edge_maps.end(); ++i) (**i).add(e);
     186      edge_maps.add(e);
    207187
    208188      return e;
     
    245225      //Update dynamic maps
    246226      Edge e; e.n=n;
    247       for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
    248           i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
     227      edge_maps.erase(e);
     228
    249229    }
    250230     
     
    266246
    267247      //Update dynamic maps
    268       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
    269           i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
     248      node_maps.erase(nn);
     249
    270250    }
    271251   
    272252    void erase(Edge e) { eraseEdge(e.n); }
    273253
    274     ///\bug Dynamic maps must be updated!
    275     ///
    276254    void clear() {
    277       nodes.clear();edges.clear();
     255      edge_maps.clear();
     256      edges.clear();
     257      node_maps.clear();
     258      nodes.clear();
    278259      first_node=first_free_node=first_free_edge=-1;
    279260    }
     
    411392      //      operator bool() { return Edge::operator bool(); }     
    412393    };
    413 
    414     template <typename T> class NodeMap : public DynMapBase<Node>
    415     {
    416       std::vector<T> container;
    417 
    418     public:
    419       typedef T ValueType;
    420       typedef Node KeyType;
    421 
    422       NodeMap(const ListGraph &_G) :
    423         DynMapBase<Node>(_G), container(_G.maxNodeId())
    424       {
    425         G->dyn_node_maps.push_back(this);
    426       }
    427       NodeMap(const ListGraph &_G,const T &t) :
    428         DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
    429       {
    430         G->dyn_node_maps.push_back(this);
    431       }
    432      
    433       NodeMap(const NodeMap<T> &m) :
    434         DynMapBase<Node>(*m.G), container(m.container)
    435       {
    436         G->dyn_node_maps.push_back(this);
    437       }
    438 
    439       template<typename TT> friend class NodeMap;
    440  
    441       ///\todo It can copy between different types.
    442       ///
    443       template<typename TT> NodeMap(const NodeMap<TT> &m) :
    444         DynMapBase<Node>(*m.G), container(m.container.size())
    445 
    446       {
    447         G->dyn_node_maps.push_back(this);
    448         typename std::vector<TT>::const_iterator i;
    449         for(typename std::vector<TT>::const_iterator i=m.container.begin();
    450             i!=m.container.end();
    451             i++)
    452           container.push_back(*i);
    453       }
    454       ~NodeMap()
    455       {
    456         if(G) {
    457           std::vector<DynMapBase<Node>* >::iterator i;
    458           for(i=G->dyn_node_maps.begin();
    459               i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
    460           //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
    461           //A better way to do that: (Is this really important?)
    462           if(*i==this) {
    463             *i=G->dyn_node_maps.back();
    464             G->dyn_node_maps.pop_back();
    465           }
    466         }
    467       }
    468 
    469       void add(const Node k)
    470       {
    471         if(k.n>=int(container.size())) container.resize(k.n+1);
    472       }
    473 
    474       void erase(const Node) { }
    475      
    476       void set(Node n, T a) { container[n.n]=a; }
    477       //'T& operator[](Node n)' would be wrong here
    478       typename std::vector<T>::reference
    479       operator[](Node n) { return container[n.n]; }
    480       //'const T& operator[](Node n)' would be wrong here
    481       typename std::vector<T>::const_reference
    482       operator[](Node n) const { return container[n.n]; }
    483 
    484       ///\warning There is no safety check at all!
    485       ///Using operator = between maps attached to different graph may
    486       ///cause serious problem.
    487       ///\todo Is this really so?
    488       ///\todo It can copy between different types.
    489       const NodeMap<T>& operator=(const NodeMap<T> &m)
    490       {
    491         container = m.container;
    492         return *this;
    493       }
    494       template<typename TT>
    495       const NodeMap<T>& operator=(const NodeMap<TT> &m)
    496       {
    497         std::copy(m.container.begin(), m.container.end(), container.begin());
    498         return *this;
    499       }
    500      
    501       void update() {}    //Useless for Dynamic Maps
    502       void update(T a) {}  //Useless for Dynamic Maps
    503     };
    504    
    505     template <typename T> class EdgeMap : public DynMapBase<Edge>
    506     {
    507     protected:
    508       std::vector<T> container;
    509 
    510     public:
    511       typedef T ValueType;
    512       typedef Edge KeyType;
    513 
    514       EdgeMap(const ListGraph &_G) :
    515         DynMapBase<Edge>(_G), container(_G.maxEdgeId())
    516       {
    517         //FIXME: What if there are empty Id's?
    518         //FIXME: Can I use 'this' in a constructor?
    519         G->dyn_edge_maps.push_back(this);
    520       }
    521       EdgeMap(const ListGraph &_G,const T &t) :
    522         DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
    523       {
    524         G->dyn_edge_maps.push_back(this);
    525       }
    526       EdgeMap(const EdgeMap<T> &m) :
    527         DynMapBase<Edge>(*m.G), container(m.container)
    528       {
    529         G->dyn_edge_maps.push_back(this);
    530       }
    531 
    532       template<typename TT> friend class EdgeMap;
    533 
    534       ///\todo It can copy between different types.
    535       ///
    536       template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
    537         DynMapBase<Edge>(*m.G), container(m.container.size())
    538       {
    539         G->dyn_edge_maps.push_back(this);
    540         typename std::vector<TT>::const_iterator i;
    541         for(typename std::vector<TT>::const_iterator i=m.container.begin();
    542             i!=m.container.end();
    543             i++)
    544           container.push_back(*i);
    545       }
    546       ~EdgeMap()
    547       {
    548         if(G) {
    549           std::vector<DynMapBase<Edge>* >::iterator i;
    550           for(i=G->dyn_edge_maps.begin();
    551               i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
    552           //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
    553           //A better way to do that: (Is this really important?)
    554           if(*i==this) {
    555             *i=G->dyn_edge_maps.back();
    556             G->dyn_edge_maps.pop_back();
    557           }
    558         }
    559       }
    560      
    561       void add(const Edge k)
    562       {
    563         if(k.n>=int(container.size())) container.resize(k.n+1);
    564       }
    565       void erase(const Edge) { }
    566      
    567       void set(Edge n, T a) { container[n.n]=a; }
    568       //T get(Edge n) const { return container[n.n]; }
    569       typename std::vector<T>::reference
    570       operator[](Edge n) { return container[n.n]; }
    571       typename std::vector<T>::const_reference
    572       operator[](Edge n) const { return container[n.n]; }
    573 
    574       ///\warning There is no safety check at all!
    575       ///Using operator = between maps attached to different graph may
    576       ///cause serious problem.
    577       ///\todo Is this really so?
    578       ///\todo It can copy between different types.
    579       const EdgeMap<T>& operator=(const EdgeMap<T> &m)
    580       {
    581         container = m.container;
    582         return *this;
    583       }
    584       template<typename TT>
    585       const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
    586       {
    587         std::copy(m.container.begin(), m.container.end(), container.begin());
    588         return *this;
    589       }
    590      
    591       void update() {}    //Useless for DynMaps
    592       void update(T a) {}  //Useless for DynMaps
    593     };
    594 
    595394  };
    596395
     
    616415  ///\todo this date structure need some reconsiderations. Maybe it
    617416  ///should be implemented independently from ListGraph.
    618 
     417 
    619418  class SymListGraph : public ListGraph
    620419  {
    621420  public:
    622     template<typename T> class SymEdgeMap;
    623     template<typename T> friend class SymEdgeMap;
     421
     422    typedef SymListGraph Graph;
     423
     424    KEEP_NODE_MAP(ListGraph);
     425    KEEP_EDGE_MAP(ListGraph);
     426
     427    CREATE_SYM_EDGE_MAP_REGISTRY;
     428    CREATE_SYM_EDGE_MAP_FACTORY(ArrayMapFactory);
     429    IMPORT_SYM_EDGE_MAP(SymEdgeMapFactory);
    624430
    625431    SymListGraph() : ListGraph() { }
     
    629435    {
    630436      Edge e = ListGraph::addEdge(u,v);
    631       ListGraph::addEdge(v,u);
     437      Edge f = ListGraph::addEdge(v,u);
     438      sym_edge_maps.add(e);
     439      sym_edge_maps.add(f);
     440     
    632441      return e;
    633442    }
    634443
    635     void erase(Node n) { ListGraph::erase(n); }
     444    void erase(Node n) { ListGraph::erase(n);}
    636445    ///The oppositely directed edge.
    637446
     
    647456    ///Removes a pair of oppositely directed edges to the graph.
    648457    void erase(Edge e) {
    649       ListGraph::erase(opposite(e));
     458      Edge f = opposite(e);
     459      sym_edge_maps.erase(e);
     460      sym_edge_maps.erase(f);
     461      ListGraph::erase(f);
    650462      ListGraph::erase(e);
    651     }
    652    
    653     ///Common data storage for the edge pairs.
    654 
    655     ///This map makes it possible to store data shared by the oppositely
    656     ///directed pairs of edges.
    657     template <typename T> class SymEdgeMap : public DynMapBase<Edge>
    658     {
    659       std::vector<T> container;
    660      
    661     public:
    662       typedef T ValueType;
    663       typedef Edge KeyType;
    664 
    665       SymEdgeMap(const SymListGraph &_G) :
    666         DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
    667       {
    668         static_cast<const SymListGraph*>(G)->dyn_edge_maps.push_back(this);
    669       }
    670       SymEdgeMap(const SymListGraph &_G,const T &t) :
    671         DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
    672       {
    673         G->dyn_edge_maps.push_back(this);
    674       }
    675 
    676       SymEdgeMap(const SymEdgeMap<T> &m) :
    677         DynMapBase<SymEdge>(*m.G), container(m.container)
    678       {
    679         G->dyn_node_maps.push_back(this);
    680       }
    681 
    682       //      template<typename TT> friend class SymEdgeMap;
    683 
    684       ///\todo It can copy between different types.
    685       ///
    686 
    687       template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
    688         DynMapBase<SymEdge>(*m.G), container(m.container.size())
    689       {
    690         G->dyn_node_maps.push_back(this);
    691         typename std::vector<TT>::const_iterator i;
    692         for(typename std::vector<TT>::const_iterator i=m.container.begin();
    693             i!=m.container.end();
    694             i++)
    695           container.push_back(*i);
    696       }
    697  
    698       ~SymEdgeMap()
    699       {
    700         if(G) {
    701           std::vector<DynMapBase<Edge>* >::iterator i;
    702           for(i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.begin();
    703               i!=static_cast<const SymListGraph*>(G)->dyn_edge_maps.end()
    704                 && *i!=this; ++i) ;
    705           //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
    706           //A better way to do that: (Is this really important?)
    707           if(*i==this) {
    708             *i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.back();
    709             static_cast<const SymListGraph*>(G)->dyn_edge_maps.pop_back();
    710           }
    711         }
    712       }
    713      
    714       void add(const Edge k)
    715       {
    716         if(!k.idref()%2&&k.idref()/2>=int(container.size()))
    717           container.resize(k.idref()/2+1);
    718       }
    719       void erase(const Edge k) { }
    720      
    721       void set(Edge n, T a) { container[n.idref()/2]=a; }
    722       //T get(Edge n) const { return container[n.idref()/2]; }
    723       typename std::vector<T>::reference
    724       operator[](Edge n) { return container[n.idref()/2]; }
    725       typename std::vector<T>::const_reference
    726       operator[](Edge n) const { return container[n.idref()/2]; }
    727 
    728       ///\warning There is no safety check at all!
    729       ///Using operator = between maps attached to different graph may
    730       ///cause serious problem.
    731       ///\todo Is this really so?
    732       ///\todo It can copy between different types.
    733       const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
    734       {
    735         container = m.container;
    736         return *this;
    737       }
    738       template<typename TT>
    739       const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
    740       {
    741         std::copy(m.container.begin(), m.container.end(), container.begin());
    742         return *this;
    743       }
    744      
    745       void update() {}    //Useless for DynMaps
    746       void update(T a) {}  //Useless for DynMaps
    747 
    748     };
    749 
     463    }   
    750464  };
    751  
     465
    752466
    753467  ///A graph class containing only nodes.
     
    780494    int first_free_node;
    781495   
    782   protected:
    783    
    784     template <typename Key> class DynMapBase
    785     {
    786     protected:
    787       const NodeSet* G;
    788     public:
    789       virtual void add(const Key k) = 0;
    790       virtual void erase(const Key k) = 0;
    791       DynMapBase(const NodeSet &_G) : G(&_G) {}
    792       virtual ~DynMapBase() {}
    793       friend class NodeSet;
    794     };
    795    
    796   public:
    797     template <typename T> class EdgeMap;
    798     template <typename T> class NodeMap;
     496  public:
     497
     498    typedef NodeSet Graph;
    799499   
    800500    class Node;
    801501    class Edge;
    802502
    803     //  protected:
    804     // HELPME:
    805   protected:
    806     ///\bug It must be public because of SymEdgeMap.
    807     ///
    808     mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
    809     //mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
    810    
    811503  public:
    812504
     
    816508    class InEdgeIt;
    817509   
    818     template <typename T> class NodeMap;
    819     template <typename T> class EdgeMap;
     510    CREATE_MAP_REGISTRIES;
     511    CREATE_MAPS(ArrayMapFactory);
    820512   
    821513  public:
    822514
    823515    ///Default constructor
    824     NodeSet() : nodes(), first_node(-1),
    825                   first_free_node(-1) {}
     516    NodeSet()
     517      : nodes(), first_node(-1), first_free_node(-1) {}
    826518    ///Copy constructor
    827     NodeSet(const NodeSet &_g) : nodes(_g.nodes), first_node(_g.first_node),
    828                                      first_free_node(_g.first_free_node) {}
    829    
    830     ~NodeSet()
    831     {
    832       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
    833           i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
    834       //for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
    835       //          i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
    836     }
    837 
     519    NodeSet(const NodeSet &_g)
     520      : nodes(_g.nodes), first_node(_g.first_node),
     521        first_free_node(_g.first_free_node) {}
     522   
    838523    int nodeNum() const { return nodes.size(); }  //FIXME: What is this?
    839524    int edgeNum() const { return 0; }  //FIXME: What is this?
     
    888573
    889574      //Update dynamic maps
    890       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
    891           i!=dyn_node_maps.end(); ++i) (**i).add(nn);
     575      node_maps.add(nn);
    892576
    893577      return nn;
     
    905589
    906590      //Update dynamic maps
    907       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
    908           i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
     591      node_maps.erase(nn);
    909592    }
    910593   
     
    915598    }
    916599   
    917     ///\bug Dynamic maps must be updated!
    918     ///
    919600    void clear() {
     601      node_maps.clear();
    920602      nodes.clear();
    921603      first_node = first_free_node = -1;
     
    1013695    };
    1014696
    1015     template <typename T> class NodeMap : public DynMapBase<Node>
    1016     {
    1017       std::vector<T> container;
    1018 
    1019     public:
    1020       typedef T ValueType;
    1021       typedef Node KeyType;
    1022 
    1023       NodeMap(const NodeSet &_G) :
    1024         DynMapBase<Node>(_G), container(_G.maxNodeId())
    1025       {
    1026         G->dyn_node_maps.push_back(this);
    1027       }
    1028       NodeMap(const NodeSet &_G,const T &t) :
    1029         DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
    1030       {
    1031         G->dyn_node_maps.push_back(this);
    1032       }
    1033      
    1034       NodeMap(const NodeMap<T> &m) :
    1035         DynMapBase<Node>(*m.G), container(m.container)
    1036       {
    1037         G->dyn_node_maps.push_back(this);
    1038       }
    1039 
    1040       template<typename TT> friend class NodeMap;
    1041  
    1042       ///\todo It can copy between different types.
    1043       ///
    1044       template<typename TT> NodeMap(const NodeMap<TT> &m) :
    1045         DynMapBase<Node>(*m.G), container(m.container.size())
    1046       {
    1047         G->dyn_node_maps.push_back(this);
    1048         typename std::vector<TT>::const_iterator i;
    1049         for(typename std::vector<TT>::const_iterator i=m.container.begin();
    1050             i!=m.container.end();
    1051             i++)
    1052           container.push_back(*i);
    1053       }
    1054       ~NodeMap()
    1055       {
    1056         if(G) {
    1057           std::vector<DynMapBase<Node>* >::iterator i;
    1058           for(i=G->dyn_node_maps.begin();
    1059               i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
    1060           //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
    1061           //A better way to do that: (Is this really important?)
    1062           if(*i==this) {
    1063             *i=G->dyn_node_maps.back();
    1064             G->dyn_node_maps.pop_back();
    1065           }
    1066         }
    1067       }
    1068 
    1069       void add(const Node k)
    1070       {
    1071         if(k.n>=int(container.size())) container.resize(k.n+1);
    1072       }
    1073 
    1074       void erase(const Node) { }
    1075      
    1076       void set(Node n, T a) { container[n.n]=a; }
    1077       //'T& operator[](Node n)' would be wrong here
    1078       typename std::vector<T>::reference
    1079       operator[](Node n) { return container[n.n]; }
    1080       //'const T& operator[](Node n)' would be wrong here
    1081       typename std::vector<T>::const_reference
    1082       operator[](Node n) const { return container[n.n]; }
    1083 
    1084       ///\warning There is no safety check at all!
    1085       ///Using operator = between maps attached to different graph may
    1086       ///cause serious problem.
    1087       ///\todo Is this really so?
    1088       ///\todo It can copy between different types.
    1089       const NodeMap<T>& operator=(const NodeMap<T> &m)
    1090       {
    1091         container = m.container;
    1092         return *this;
    1093       }
    1094       template<typename TT>
    1095       const NodeMap<T>& operator=(const NodeMap<TT> &m)
    1096       {
    1097         std::copy(m.container.begin(), m.container.end(), container.begin());
    1098         return *this;
    1099       }
    1100      
    1101       void update() {}    //Useless for Dynamic Maps
    1102       void update(T a) {}  //Useless for Dynamic Maps
    1103     };
    1104    
    1105     template <typename T> class EdgeMap
    1106     {
    1107     public:
    1108       typedef T ValueType;
    1109       typedef Edge KeyType;
    1110 
    1111       EdgeMap(const NodeSet &) { }
    1112       EdgeMap(const NodeSet &,const T &) { }
    1113       EdgeMap(const EdgeMap<T> &) { }
    1114       //      template<typename TT> friend class EdgeMap;
    1115 
    1116       ///\todo It can copy between different types.
    1117       ///
    1118       template<typename TT> EdgeMap(const EdgeMap<TT> &) { }
    1119       ~EdgeMap() { }
    1120 
    1121       void add(const Edge  ) { }
    1122       void erase(const Edge) { }
    1123      
    1124       void set(Edge, T) { }
    1125       //T get(Edge n) const { return container[n.n]; }
    1126       ValueType &operator[](Edge) { return *((T*)(NULL)); }
    1127       const ValueType &operator[](Edge) const { return *((T*)(NULL)); }
    1128 
    1129       const EdgeMap<T>& operator=(const EdgeMap<T> &) { return *this; }
    1130    
    1131       template<typename TT>
    1132       const EdgeMap<T>& operator=(const EdgeMap<TT> &m) { return *this; }
    1133      
    1134       void update() {}
    1135       void update(T a) {}
    1136     };
    1137697  };
    1138698
     
    1167727
    1168728  public:
     729
    1169730    class Node;
    1170731    class Edge;
     
    1172733    class InEdgeIt;
    1173734    class SymEdge;
     735
     736    typedef EdgeSet Graph;
     737
    1174738    int id(Node v) const;
    1175739
     
    1230794    int first_free_edge;
    1231795   
    1232   protected:
    1233    
    1234     template <typename Key> class DynMapBase
    1235     {
    1236     protected:
    1237       const EdgeSet* G;
    1238     public:
    1239       virtual void add(const Key k) = 0;
    1240       virtual void erase(const Key k) = 0;
    1241       DynMapBase(const EdgeSet &_G) : G(&_G) {}
    1242       virtual ~DynMapBase() {}
    1243       friend class EdgeSet;
    1244     };
    1245    
    1246   public:
    1247     //template <typename T> class NodeMap;
    1248     template <typename T> class EdgeMap;
     796  public:
    1249797   
    1250798    class Node;
    1251799    class Edge;
    1252 
    1253     //  protected:
    1254     // HELPME:
    1255   protected:
    1256     // mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
    1257     ///\bug It must be public because of SymEdgeMap.
    1258     ///
    1259     mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
    1260    
    1261   public:
    1262800
    1263801    class NodeIt;
     
    1265803    class OutEdgeIt;
    1266804    class InEdgeIt;
    1267    
    1268     template <typename T> class NodeMap;
    1269     template <typename T> class EdgeMap;
     805
     806
     807    CREATE_EDGE_MAP_REGISTRY;
     808    CREATE_EDGE_MAP_FACTORY(ArrayMapFactory);
     809    IMPORT_EDGE_MAP(EdgeMapFactory);
     810   
    1270811   
    1271812  public:
     
    1276817    ///\param _G the base graph.
    1277818    ///\todo It looks like a copy constructor, but it isn't.
    1278     EdgeSet(NodeGraphType &_G) : G(_G),
    1279                                 nodes(_G), edges(),
    1280                                  first_free_edge(-1) { }
     819    EdgeSet(NodeGraphType &_G)
     820      : G(_G), nodes(_G), edges(),
     821        first_free_edge(-1) {}
    1281822    ///Copy constructor
    1282823
    1283824    ///Makes a copy of an EdgeSet.
    1284825    ///It will be based on the same graph.
    1285     EdgeSet(const EdgeSet &_g) : G(_g.G), nodes(_g.G), edges(_g.edges),
    1286                                  first_free_edge(_g.first_free_edge) { }
    1287    
    1288     ~EdgeSet()
    1289     {
    1290       // for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
    1291       //  i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
    1292       for(typename std::vector<DynMapBase<Edge> * >::iterator
    1293             i=dyn_edge_maps.begin();
    1294           i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
    1295     }
    1296 
     826    EdgeSet(const EdgeSet &_g)
     827      : G(_g.G), nodes(_g.G), edges(_g.edges),
     828        first_free_edge(_g.first_free_edge) {}
     829   
    1297830    int nodeNum() const { return G.nodeNum(); }  //FIXME: What is this?
    1298831    int edgeNum() const { return edges.size(); }  //FIXME: What is this?
     
    1348881
    1349882      //Update dynamic maps
    1350       for(typename std::vector<DynMapBase<Edge> * >::iterator
    1351             i=dyn_edge_maps.begin();
    1352           i!=dyn_edge_maps.end(); ++i) (**i).add(e);
     883      edge_maps.add(e);
    1353884
    1354885      return e;
     
    1390921
    1391922      //Update dynamic maps
    1392       Edge e; e.n=n;
    1393       for(typename std::vector<DynMapBase<Edge> * >::iterator
    1394             i=dyn_edge_maps.begin();
    1395           i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
     923      Edge e; e.n = n;
     924      edge_maps.erase(e);
    1396925    }
    1397926     
     
    1409938    ///Clear all edges. (Doesn't clear the nodes!)
    1410939    void clear() {
     940      edge_maps.clear();
    1411941      edges.clear();
    1412942      first_free_edge=-1;
     
    1414944
    1415945
    1416 //     //\bug Dynamic maps must be updated!
    1417 //     //
    1418 //     void clear() {
    1419 //       nodes.clear();edges.clear();
    1420 //       first_node=first_free_node=first_free_edge=-1;
    1421 //     }
    1422 
    1423   public:
    1424     template <typename T> class EdgeMap;
    1425    
    1426     ///
    1427946    class Edge {
    1428947    public:
     
    14911010      OutEdgeIt(const EdgeSet& _G,const Node v) :
    14921011        Edge(_G.nodes[v].first_out), G(&_G) { }
    1493       OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
     1012      OutEdgeIt &operator++() { n = G->edges[n].next_out; return *this; }
    14941013    };
    14951014   
     
    15061025    };
    15071026
    1508     template <typename T> class NodeMap :
    1509       public NodeGraphType::template NodeMap<T>
     1027   
     1028    template <typename V> class NodeMap
     1029      : public NodeGraphType::template NodeMap<V>
    15101030    {
    15111031      //This is a must, the constructors need it.
    1512       typedef typename NodeGraphType::template NodeMap<T> ParentNodeMap;
    1513     public:
    1514       NodeMap(const EdgeSet &_G) : ParentNodeMap(_G.G) { }
    1515       NodeMap(const EdgeSet &_G,const T &t) : ParentNodeMap(_G.G,t) { }
    1516       //It is unnecessary
    1517       NodeMap(const typename NodeGraphType::template NodeMap<T> &m) :
    1518         ParentNodeMap(m) { }
    1519 
    1520       ///\todo It can copy between different types.
    1521       ///
    1522       template<typename TT>
    1523       NodeMap(const typename NodeGraphType::template NodeMap<TT> &m)
    1524         : ParentNodeMap(m) { }
    1525     };
    1526    
    1527     ///
    1528     template <typename T> class EdgeMap : public DynMapBase<Edge>
    1529     {
    1530     protected:
    1531     public:
    1532       ///\bug It should be at least protected
    1533       ///
    1534       std::vector<T> container;
    1535 
    1536     public:
    1537       typedef T ValueType;
    1538       typedef Edge KeyType;
    1539 
    1540       EdgeMap(const EdgeSet &_G) :
    1541         DynMapBase<Edge>(_G), container(_G.maxEdgeId())
    1542       {
    1543         //FIXME: What if there are empty Id's?
    1544         //FIXME: Can I use 'this' in a constructor?
    1545         this->G->dyn_edge_maps.push_back(this);
    1546       }
    1547       EdgeMap(const EdgeSet &_G,const T &t) :
    1548         DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
    1549       {
    1550         this->G->dyn_edge_maps.push_back(this);
    1551       }
    1552       EdgeMap(const EdgeMap<T> &m) :
    1553         DynMapBase<Edge>(*m.G), container(m.container)
    1554       {
    1555         this->G->dyn_edge_maps.push_back(this);
    1556       }
    1557 
    1558       ///\todo It can copy between different types.
    1559       ///
    1560       template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
    1561         DynMapBase<Edge>(*m.G), container(m.container.size())
    1562       {
    1563         this->G->dyn_edge_maps.push_back(this);
    1564         typename std::vector<TT>::const_iterator i;
    1565         for(typename std::vector<TT>::const_iterator i=m.container.begin();
    1566             i!=m.container.end();
    1567             i++)
    1568           container.push_back(*i);
    1569       }
    1570       ~EdgeMap()
    1571       {
    1572         if(this->G) {
    1573           typename std::vector<DynMapBase<Edge>* >::iterator i;
    1574           for(i=this->G->dyn_edge_maps.begin();
    1575               i!=this->G->dyn_edge_maps.end() && *i!=this; ++i) ;
    1576           //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
    1577           //A better way to do that: (Is this really important?)
    1578           if(*i==this) {
    1579             *i=this->G->dyn_edge_maps.back();
    1580             this->G->dyn_edge_maps.pop_back();
    1581           }
    1582         }
    1583       }
    1584      
    1585       void add(const Edge k)
    1586       {
    1587         if(k.n>=int(container.size())) container.resize(k.n+1);
    1588       }
    1589       void erase(const Edge) { }
    1590      
    1591       ///\bug This doesn't work. Why?
    1592       ///      void set(Edge n, T a) { container[n.n]=a; }
    1593       void set(Edge n, T a) { container[this->G->id(n)]=a; }
    1594       //T get(Edge n) const { return container[n.n]; }
    1595       typename std::vector<T>::reference
    1596       ///\bug This doesn't work. Why?
    1597       ///      operator[](Edge n) { return container[n.n]; }
    1598       operator[](Edge n) { return container[this->G->id(n)]; }
    1599       typename std::vector<T>::const_reference
    1600       ///\bug This doesn't work. Why?
    1601       ///      operator[](Edge n) const { return container[n.n]; }
    1602       operator[](Edge n) const { return container[this->G->id(n)]; }
    1603 
    1604       ///\warning There is no safety check at all!
    1605       ///Using operator = between maps attached to different graph may
    1606       ///cause serious problem.
    1607       ///\todo Is this really so?
    1608       ///\todo It can copy between different types.
    1609       const EdgeMap<T>& operator=(const EdgeMap<T> &m)
    1610       {
    1611         container = m.container;
     1032      typedef typename NodeGraphType::template NodeMap<V> MapImpl;
     1033      typedef V Value;
     1034    public:
     1035      NodeMap() : MapImpl() {}
     1036     
     1037      NodeMap(const EdgeSet& graph)
     1038        : MapImpl(graph.G) { }
     1039
     1040      NodeMap(const EdgeSet& graph, const Value& value)
     1041        : MapImpl(graph.G, value) { }
     1042
     1043      NodeMap(const NodeMap& copy)
     1044        : MapImpl(static_cast<const MapImpl&>(copy)) {}
     1045
     1046      template<typename CMap>
     1047      NodeMap(const CMap& copy)
     1048        : MapImpl(copy) { }
     1049
     1050      NodeMap& operator=(const NodeMap& copy) {
     1051        MapImpl::operator=(static_cast<const MapImpl&>(copy));
    16121052        return *this;
    16131053      }
    1614      
    1615       template<typename TT> friend class EdgeMap;
    1616 
    1617       template<typename TT>
    1618       const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
    1619       {
    1620         std::copy(m.container.begin(), m.container.end(), container.begin());
     1054
     1055      template <typename CMap>
     1056      NodeMap& operator=(const CMap& copy) {
     1057        MapImpl::operator=(copy);
    16211058        return *this;
    16221059      }
    1623      
    1624       void update() {}    //Useless for DynMaps
    1625       void update(T a) {}  //Useless for DynMaps
    1626     };
    1627 
     1060
     1061    };
    16281062  };
    16291063
  • src/hugo/smart_graph.h

    r774 r782  
    99
    1010#include <vector>
    11 #include <limits.h>
     11#include <climits>
    1212
    1313#include <hugo/invalid.h>
     14
     15#include <hugo/array_map_factory.h>
     16#include <hugo/sym_map_factory.h>
     17#include <hugo/map_registry.h>
     18
     19#include <hugo/map_defines.h>
    1420
    1521namespace hugo {
     
    1723/// \addtogroup graphs
    1824/// @{
    19   class SymSmartGraph;
     25//  class SymSmartGraph;
    2026
    2127  ///A smart graph class.
     
    5460    std::vector<EdgeT> edges;
    5561   
    56     protected:
    57    
    58     template <typename Key> class DynMapBase
    59     {
    60     protected:
    61       const SmartGraph* G;
    62     public:
    63       virtual void add(const Key k) = 0;
    64       virtual void erase(const Key k) = 0;
    65       DynMapBase(const SmartGraph &_G) : G(&_G) {}
    66       virtual ~DynMapBase() {}
    67       friend class SmartGraph;
    68     };
    6962   
    7063  public:
    71     template <typename T> class EdgeMap;
    72     template <typename T> class NodeMap;
     64
     65    typedef SmartGraph Graph;
    7366
    7467    class Node;
    7568    class Edge;
    76 
    77     //  protected:
    78     // HELPME:
    79   protected:
    80     ///\bug It must be public because of SymEdgeMap.
    81     ///
    82     mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
    83     ///\bug It must be public because of SymEdgeMap.
    84     ///
    85     mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
    86    
    87   public:
    88 
    8969
    9070    class NodeIt;
     
    9373    class InEdgeIt;
    9474   
    95     template <typename T> class NodeMap;
    96     template <typename T> class EdgeMap;
     75    CREATE_MAP_REGISTRIES;
     76    CREATE_MAPS(ArrayMapFactory);
    9777   
    9878  public:
     
    10181    SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
    10282   
    103     ~SmartGraph()
    104     {
    105       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
    106           i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
    107       for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
    108           i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
    109     }
    110 
    11183    int nodeNum() const { return nodes.size(); }  //FIXME: What is this?
    11284    int edgeNum() const { return edges.size(); }  //FIXME: What is this?
     
    138110      nodes.push_back(NodeT()); //FIXME: Hmmm...
    139111
    140       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
    141           i!=dyn_node_maps.end(); ++i) (**i).add(n);
    142 
     112     
     113      node_maps.add(n);
    143114      return n;
    144115    }
     
    151122      nodes[u.n].first_out=nodes[v.n].first_in=e.n;
    152123
    153       for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
    154           i!=dyn_edge_maps.end(); ++i) (**i).add(e);
     124      edge_maps.add(e);
    155125
    156126      return e;
     
    173143    }
    174144   
    175     void clear() {nodes.clear();edges.clear();}
     145    void clear() {
     146      edge_maps.clear();
     147      edges.clear();
     148      node_maps.clear();
     149      nodes.clear();
     150    }
    176151
    177152    class Node {
     
    289264//       ///Validity check
    290265//       operator bool() { return Edge::operator bool(); }     
    291     };
    292 
    293     template <typename T> class NodeMap : public DynMapBase<Node>
    294     {
    295       std::vector<T> container;
    296 
    297     public:
    298       typedef T ValueType;
    299       typedef Node KeyType;
    300 
    301       NodeMap(const SmartGraph &_G) :
    302         DynMapBase<Node>(_G), container(_G.maxNodeId())
    303       {
    304         G->dyn_node_maps.push_back(this);
    305       }
    306       NodeMap(const SmartGraph &_G,const T &t) :
    307         DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
    308       {
    309         G->dyn_node_maps.push_back(this);
    310       }
    311      
    312       NodeMap(const NodeMap<T> &m) :
    313         DynMapBase<Node>(*m.G), container(m.container)
    314       {
    315         G->dyn_node_maps.push_back(this);
    316       }
    317 
    318       template<typename TT> friend class NodeMap;
    319  
    320       ///\todo It can copy between different types.
    321       ///\todo We could use 'copy'
    322       template<typename TT> NodeMap(const NodeMap<TT> &m) :
    323         DynMapBase<Node>(*m.G), container(m.container.size())
    324       {
    325         G->dyn_node_maps.push_back(this);
    326         typename std::vector<TT>::const_iterator i;
    327         for(typename std::vector<TT>::const_iterator i=m.container.begin();
    328             i!=m.container.end();
    329             i++)
    330           container.push_back(*i);
    331       }
    332       ~NodeMap()
    333       {
    334         if(G) {
    335           std::vector<DynMapBase<Node>* >::iterator i;
    336           for(i=G->dyn_node_maps.begin();
    337               i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
    338           //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
    339           //A better way to do that: (Is this really important?)
    340           if(*i==this) {
    341             *i=G->dyn_node_maps.back();
    342             G->dyn_node_maps.pop_back();
    343           }
    344         }
    345       }
    346 
    347       void add(const Node k)
    348       {
    349         if(k.n>=int(container.size())) container.resize(k.n+1);
    350       }
    351 
    352       void erase(const Node) { }
    353      
    354       void set(Node n, T a) { container[n.n]=a; }
    355       //'T& operator[](Node n)' would be wrong here
    356       typename std::vector<T>::reference
    357       operator[](Node n) { return container[n.n]; }
    358       //'const T& operator[](Node n)' would be wrong here
    359       typename std::vector<T>::const_reference
    360       operator[](Node n) const { return container[n.n]; }
    361 
    362       ///\warning There is no safety check at all!
    363       ///Using operator = between maps attached to different graph may
    364       ///cause serious problem.
    365       ///\todo Is this really so?
    366       ///\todo It can copy between different types.
    367       const NodeMap<T>& operator=(const NodeMap<T> &m)
    368       {
    369         container = m.container;
    370         return *this;
    371       }
    372       template<typename TT>
    373       const NodeMap<T>& operator=(const NodeMap<TT> &m)
    374       {
    375         std::copy(m.container.begin(), m.container.end(), container.begin());
    376         return *this;
    377       }
    378      
    379       void update() {}    //Useless for Dynamic Maps
    380       void update(T a) {}  //Useless for Dynamic Maps
    381     };
    382    
    383     template <typename T> class EdgeMap : public DynMapBase<Edge>
    384     {
    385       std::vector<T> container;
    386 
    387     public:
    388       typedef T ValueType;
    389       typedef Edge KeyType;
    390 
    391       EdgeMap(const SmartGraph &_G) :
    392         DynMapBase<Edge>(_G), container(_G.maxEdgeId())
    393       {
    394         //FIXME: What if there are empty Id's?
    395         //FIXME: Can I use 'this' in a constructor?
    396         G->dyn_edge_maps.push_back(this);
    397       }
    398       EdgeMap(const SmartGraph &_G,const T &t) :
    399         DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
    400       {
    401         G->dyn_edge_maps.push_back(this);
    402       }
    403       EdgeMap(const EdgeMap<T> &m) :
    404         DynMapBase<Edge>(*m.G), container(m.container)
    405       {
    406         G->dyn_edge_maps.push_back(this);
    407       }
    408 
    409       template<typename TT> friend class EdgeMap;
    410 
    411       ///\todo It can copy between different types.
    412       template<typename TT> EdgeMap(const EdgeMap<TT> &m)
    413         : DynMapBase<Edge>(*m.G), container(m.container.size())
    414       {
    415         G->dyn_edge_maps.push_back(this);
    416         typename std::vector<TT>::const_iterator i;
    417         for(typename std::vector<TT>::const_iterator i=m.container.begin();
    418             i!=m.container.end();
    419             i++)
    420           container.push_back(*i);
    421       }
    422       ~EdgeMap()
    423       {
    424         if(G) {
    425           std::vector<DynMapBase<Edge>* >::iterator i;
    426           for(i=G->dyn_edge_maps.begin();
    427               i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
    428           //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
    429           //A better way to do that: (Is this really important?)
    430           if(*i==this) {
    431             *i=G->dyn_edge_maps.back();
    432             G->dyn_edge_maps.pop_back();
    433           }
    434         }
    435       }
    436      
    437       void add(const Edge k)
    438       {
    439         if(k.n>=int(container.size())) container.resize(k.n+1);
    440       }
    441       void erase(const Edge) { }
    442      
    443       void set(Edge n, T a) { container[n.n]=a; }
    444       //T get(Edge n) const { return container[n.n]; }
    445       typename std::vector<T>::reference
    446       operator[](Edge n) { return container[n.n]; }
    447       typename std::vector<T>::const_reference
    448       operator[](Edge n) const { return container[n.n]; }
    449 
    450       ///\warning There is no safety check at all!
    451       ///Using operator = between maps attached to different graph may
    452       ///cause serious problem.
    453       ///\todo Is this really so?
    454       ///\todo It can copy between different types.
    455       const EdgeMap<T>& operator=(const EdgeMap<T> &m)
    456       {
    457         container = m.container;
    458         return *this;
    459       }
    460       template<typename TT>
    461       const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
    462       {
    463         std::copy(m.container.begin(), m.container.end(), container.begin());
    464         return *this;
    465       }
    466      
    467       void update() {}    //Useless for DynMaps
    468       void update(T a) {}  //Useless for DynMaps
    469266    };
    470267
     
    494291  {
    495292  public:
    496     template<typename T> class SymEdgeMap;
    497     template<typename T> friend class SymEdgeMap;
     293    typedef SymSmartGraph Graph;
     294
     295    KEEP_NODE_MAP(SmartGraph);
     296    KEEP_EDGE_MAP(SmartGraph);
     297
     298    CREATE_SYM_EDGE_MAP_REGISTRY;
     299    CREATE_SYM_EDGE_MAP_FACTORY(ArrayMapFactory);
     300    IMPORT_SYM_EDGE_MAP(SymEdgeMapFactory);
    498301
    499302    SymSmartGraph() : SmartGraph() { }
     
    518321    }
    519322   
    520     ///Common data storage for the edge pairs.
    521 
    522     ///This map makes it possible to store data shared by the oppositely
    523     ///directed pairs of edges.
    524     template <typename T> class SymEdgeMap : public DynMapBase<Edge>
    525     {
    526       std::vector<T> container;
    527      
    528     public:
    529       typedef T ValueType;
    530       typedef Edge KeyType;
    531 
    532       SymEdgeMap(const SymSmartGraph &_G) :
    533         DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
    534       {
    535         static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.push_back(this);
    536       }
    537       SymEdgeMap(const SymSmartGraph &_G,const T &t) :
    538         DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
    539       {
    540         G->dyn_edge_maps.push_back(this);
    541       }
    542 
    543       SymEdgeMap(const SymEdgeMap<T> &m) :
    544         DynMapBase<SymEdge>(*m.G), container(m.container)
    545       {
    546         G->dyn_node_maps.push_back(this);
    547       }
    548 
    549       //      template<typename TT> friend class SymEdgeMap;
    550 
    551       ///\todo It can copy between different types.
    552       ///
    553 
    554       template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m)
    555         : DynMapBase<SymEdge>(*m.G), container(m.container.size())
    556       {
    557         G->dyn_node_maps.push_back(this);
    558         typename std::vector<TT>::const_iterator i;
    559         for(typename std::vector<TT>::const_iterator i=m.container.begin();
    560             i!=m.container.end();
    561             i++)
    562           container.push_back(*i);
    563       }
    564  
    565       ~SymEdgeMap()
    566       {
    567         if(G) {
    568           std::vector<DynMapBase<Edge>* >::iterator i;
    569           for(i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.begin();
    570               i!=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.end()
    571                 && *i!=this; ++i) ;
    572           //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
    573           //A better way to do that: (Is this really important?)
    574           if(*i==this) {
    575             *i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.back();
    576             static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.pop_back();
    577           }
    578         }
    579       }
    580      
    581       void add(const Edge k)
    582       {
    583         if(!k.idref()%2&&k.idref()/2>=int(container.size()))
    584           container.resize(k.idref()/2+1);
    585       }
    586       void erase(const Edge k) { }
    587      
    588       void set(Edge n, T a) { container[n.idref()/2]=a; }
    589       //T get(Edge n) const { return container[n.idref()/2]; }
    590       typename std::vector<T>::reference
    591       operator[](Edge n) { return container[n.idref()/2]; }
    592       typename std::vector<T>::const_reference
    593       operator[](Edge n) const { return container[n.idref()/2]; }
    594 
    595       ///\warning There is no safety check at all!
    596       ///Using operator = between maps attached to different graph may
    597       ///cause serious problem.
    598       ///\todo Is this really so?
    599       ///\todo It can copy between different types.
    600       const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
    601       {
    602         container = m.container;
    603         return *this;
    604       }
    605       template<typename TT>
    606       const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
    607       {
    608         std::copy(m.container.begin(), m.container.end(), container.begin());
    609         return *this;
    610       }
    611      
    612       void update() {}    //Useless for DynMaps
    613       void update(T a) {}  //Useless for DynMaps
    614 
    615     };
    616323
    617324  };
    618325 
    619326  /// @} 
    620 
    621327} //namespace hugo
    622328
Note: See TracChangeset for help on using the changeset viewer.