COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 782:df2e45e09652 in lemon-0.x for src/hugo/smart_graph.h


Ignore:
Timestamp:
09/02/04 12:07:30 (20 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

File:
1 edited

Legend:

Unmodified
Added
Removed

  • 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.