COIN-OR::LEMON - Graph Library

Changeset 698:625de6f1e766 in lemon-0.x


Ignore:
Timestamp:
07/09/04 09:33:12 (15 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@949
Message:
 
Location:
src/work/deba
Files:
2 deleted
2 edited
3 copied

Legend:

Unmodified
Added
Removed
  • src/work/deba/list_graph.h

    r695 r698  
    99
    1010#include <vector>
    11 #include <limits.h>
    12 
    13 #include <hugo/invalid.h>
     11#include <climits>
     12
     13#include "invalid.h"
     14
     15#include "vector_map_factory.h"
     16#include "map_registry.h"
     17
     18#include "map_defines.h"
    1419
    1520namespace hugo {
     
    1722/// \addtogroup graphs
    1823/// @{
    19 
    20   class SymListGraph;
    2124
    2225  ///A list graph class.
     
    5962  protected:
    6063   
    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    
    7364  public:
    74     template <typename T> class EdgeMap;
    75     template <typename T> class NodeMap;
    7665   
    7766    class Node;
    7867    class Edge;
    7968
    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;
    89    
     69    typedef ListGraph Graph;
     70
    9071  public:
    9172
     
    9576    class InEdgeIt;
    9677   
     78    CREATE_MAP_REGISTRIES;
     79    CREATE_MAPS(VectorMapFactory);
     80
    9781  public:
    9882
     
    10488                                     first_free_edge(_g.first_free_edge) {}
    10589   
    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     }
    11390
    11491    int nodeNum() const { return nodes.size(); }  //FIXME: What is this?
     
    214191
    215192      //Update dynamic maps
    216       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
    217           i!=dyn_node_maps.end(); ++i) (**i).add(nn);
     193      node_maps.add(nn);
    218194
    219195      return nn;
     
    246222
    247223      //Update dynamic maps
    248       for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
    249           i!=dyn_edge_maps.end(); ++i) (**i).add(e);
     224      edge_maps.add(e);
    250225
    251226      return e;
     
    272247      //Update dynamic maps
    273248      Edge e; e.n=n;
    274       for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
    275           i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
    276249    }
    277250     
     
    293266
    294267      //Update dynamic maps
    295       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
    296           i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
    297     }
    298    
    299     void erase(Edge e) { eraseEdge(e.n); }
     268      node_maps.erase(nn);
     269     }
     270   
     271    void erase(Edge e) {
     272      edge_maps.erase(e);
     273      eraseEdge(e.n);
     274    }
    300275
    301276    ///\bug Dynamic maps must be updated!
     
    395370      InEdgeIt (Invalid i) : Edge(i) { }
    396371      InEdgeIt(const ListGraph& G,Node v) :Edge(G.nodes[v.n].first_in) {}
    397     };
    398 
    399     template <typename T> class NodeMap : public DynMapBase<Node>
    400     {
    401       std::vector<T> container;
    402 
    403     public:
    404       typedef T ValueType;
    405       typedef Node KeyType;
    406 
    407       NodeMap(const ListGraph &_G) :
    408         DynMapBase<Node>(_G), container(_G.maxNodeId())
    409       {
    410         G->dyn_node_maps.push_back(this);
    411       }
    412       NodeMap(const ListGraph &_G,const T &t) :
    413         DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
    414       {
    415         G->dyn_node_maps.push_back(this);
    416       }
    417      
    418       NodeMap(const NodeMap<T> &m) :
    419         DynMapBase<Node>(*m.G), container(m.container)
    420       {
    421         G->dyn_node_maps.push_back(this);
    422       }
    423 
    424       template<typename TT> friend class NodeMap;
    425  
    426       ///\todo It can copy between different types.
    427       ///
    428       template<typename TT> NodeMap(const NodeMap<TT> &m) :
    429         DynMapBase<Node>(*m.G), container(m.container.size())
    430 
    431       {
    432         G->dyn_node_maps.push_back(this);
    433         typename std::vector<TT>::const_iterator i;
    434         for(typename std::vector<TT>::const_iterator i=m.container.begin();
    435             i!=m.container.end();
    436             i++)
    437           container.push_back(*i);
    438       }
    439       ~NodeMap()
    440       {
    441         if(G) {
    442           std::vector<DynMapBase<Node>* >::iterator i;
    443           for(i=G->dyn_node_maps.begin();
    444               i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
    445           //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
    446           //A better way to do that: (Is this really important?)
    447           if(*i==this) {
    448             *i=G->dyn_node_maps.back();
    449             G->dyn_node_maps.pop_back();
    450           }
    451         }
    452       }
    453 
    454       void add(const Node k)
    455       {
    456         if(k.n>=int(container.size())) container.resize(k.n+1);
    457       }
    458 
    459       void erase(const Node) { }
    460      
    461       void set(Node n, T a) { container[n.n]=a; }
    462       //'T& operator[](Node n)' would be wrong here
    463       typename std::vector<T>::reference
    464       operator[](Node n) { return container[n.n]; }
    465       //'const T& operator[](Node n)' would be wrong here
    466       typename std::vector<T>::const_reference
    467       operator[](Node n) const { return container[n.n]; }
    468 
    469       ///\warning There is no safety check at all!
    470       ///Using operator = between maps attached to different graph may
    471       ///cause serious problem.
    472       ///\todo Is this really so?
    473       ///\todo It can copy between different types.
    474       const NodeMap<T>& operator=(const NodeMap<T> &m)
    475       {
    476         container = m.container;
    477         return *this;
    478       }
    479       template<typename TT>
    480       const NodeMap<T>& operator=(const NodeMap<TT> &m)
    481       {
    482         std::copy(m.container.begin(), m.container.end(), container.begin());
    483         return *this;
    484       }
    485      
    486       void update() {}    //Useless for Dynamic Maps
    487       void update(T a) {}  //Useless for Dynamic Maps
    488     };
    489    
    490     template <typename T> class EdgeMap : public DynMapBase<Edge>
    491     {
    492     protected:
    493       std::vector<T> container;
    494 
    495     public:
    496       typedef T ValueType;
    497       typedef Edge KeyType;
    498 
    499       EdgeMap(const ListGraph &_G) :
    500         DynMapBase<Edge>(_G), container(_G.maxEdgeId())
    501       {
    502         //FIXME: What if there are empty Id's?
    503         //FIXME: Can I use 'this' in a constructor?
    504         G->dyn_edge_maps.push_back(this);
    505       }
    506       EdgeMap(const ListGraph &_G,const T &t) :
    507         DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
    508       {
    509         G->dyn_edge_maps.push_back(this);
    510       }
    511       EdgeMap(const EdgeMap<T> &m) :
    512         DynMapBase<Edge>(*m.G), container(m.container)
    513       {
    514         G->dyn_edge_maps.push_back(this);
    515       }
    516 
    517       template<typename TT> friend class EdgeMap;
    518 
    519       ///\todo It can copy between different types.
    520       ///
    521       template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
    522         DynMapBase<Edge>(*m.G), container(m.container.size())
    523       {
    524         G->dyn_edge_maps.push_back(this);
    525         typename std::vector<TT>::const_iterator i;
    526         for(typename std::vector<TT>::const_iterator i=m.container.begin();
    527             i!=m.container.end();
    528             i++)
    529           container.push_back(*i);
    530       }
    531       ~EdgeMap()
    532       {
    533         if(G) {
    534           std::vector<DynMapBase<Edge>* >::iterator i;
    535           for(i=G->dyn_edge_maps.begin();
    536               i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
    537           //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
    538           //A better way to do that: (Is this really important?)
    539           if(*i==this) {
    540             *i=G->dyn_edge_maps.back();
    541             G->dyn_edge_maps.pop_back();
    542           }
    543         }
    544       }
    545      
    546       void add(const Edge k)
    547       {
    548         if(k.n>=int(container.size())) container.resize(k.n+1);
    549       }
    550       void erase(const Edge) { }
    551      
    552       void set(Edge n, T a) { container[n.n]=a; }
    553       //T get(Edge n) const { return container[n.n]; }
    554       typename std::vector<T>::reference
    555       operator[](Edge n) { return container[n.n]; }
    556       typename std::vector<T>::const_reference
    557       operator[](Edge n) const { return container[n.n]; }
    558 
    559       ///\warning There is no safety check at all!
    560       ///Using operator = between maps attached to different graph may
    561       ///cause serious problem.
    562       ///\todo Is this really so?
    563       ///\todo It can copy between different types.
    564       const EdgeMap<T>& operator=(const EdgeMap<T> &m)
    565       {
    566         container = m.container;
    567         return *this;
    568       }
    569       template<typename TT>
    570       const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
    571       {
    572         std::copy(m.container.begin(), m.container.end(), container.begin());
    573         return *this;
    574       }
    575      
    576       void update() {}    //Useless for DynMaps
    577       void update(T a) {}  //Useless for DynMaps
    578372    };
    579373
     
    601395  ///\todo this date structure need some reconsiderations. Maybe it
    602396  ///should be implemented independently from ListGraph.
    603 
    604   class SymListGraph : public ListGraph
    605   {
    606   public:
    607     template<typename T> class SymEdgeMap;
    608     template<typename T> friend class SymEdgeMap;
    609 
    610     SymListGraph() : ListGraph() { }
    611     SymListGraph(const ListGraph &_g) : ListGraph(_g) { }
    612     ///Adds a pair of oppositely directed edges to the graph.
    613     Edge addEdge(Node u, Node v)
    614     {
    615       Edge e = ListGraph::addEdge(u,v);
    616       ListGraph::addEdge(v,u);
    617       return e;
    618     }
    619 
    620     void erase(Node n) { ListGraph::erase(n); }
    621     ///The oppositely directed edge.
    622 
    623     ///Returns the oppositely directed
    624     ///pair of the edge \c e.
    625     Edge opposite(Edge e) const
    626     {
    627       Edge f;
    628       f.idref() = e.idref() - 2*(e.idref()%2) + 1;
    629       return f;
    630     }
    631    
    632     ///Removes a pair of oppositely directed edges to the graph.
    633     void erase(Edge e) {
    634       ListGraph::erase(opposite(e));
    635       ListGraph::erase(e);
    636     }
    637    
    638     ///Common data storage for the edge pairs.
    639 
    640     ///This map makes it possible to store data shared by the oppositely
    641     ///directed pairs of edges.
    642     template <typename T> class SymEdgeMap : public DynMapBase<Edge>
    643     {
    644       std::vector<T> container;
    645      
    646     public:
    647       typedef T ValueType;
    648       typedef Edge KeyType;
    649 
    650       SymEdgeMap(const SymListGraph &_G) :
    651         DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
    652       {
    653         static_cast<const SymListGraph*>(G)->dyn_edge_maps.push_back(this);
    654       }
    655       SymEdgeMap(const SymListGraph &_G,const T &t) :
    656         DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
    657       {
    658         G->dyn_edge_maps.push_back(this);
    659       }
    660 
    661       SymEdgeMap(const SymEdgeMap<T> &m) :
    662         DynMapBase<SymEdge>(*m.G), container(m.container)
    663       {
    664         G->dyn_node_maps.push_back(this);
    665       }
    666 
    667       //      template<typename TT> friend class SymEdgeMap;
    668 
    669       ///\todo It can copy between different types.
    670       ///
    671 
    672       template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
    673         DynMapBase<SymEdge>(*m.G), container(m.container.size())
    674       {
    675         G->dyn_node_maps.push_back(this);
    676         typename std::vector<TT>::const_iterator i;
    677         for(typename std::vector<TT>::const_iterator i=m.container.begin();
    678             i!=m.container.end();
    679             i++)
    680           container.push_back(*i);
    681       }
    682  
    683       ~SymEdgeMap()
    684       {
    685         if(G) {
    686           std::vector<DynMapBase<Edge>* >::iterator i;
    687           for(i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.begin();
    688               i!=static_cast<const SymListGraph*>(G)->dyn_edge_maps.end()
    689                 && *i!=this; ++i) ;
    690           //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
    691           //A better way to do that: (Is this really important?)
    692           if(*i==this) {
    693             *i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.back();
    694             static_cast<const SymListGraph*>(G)->dyn_edge_maps.pop_back();
    695           }
    696         }
    697       }
    698      
    699       void add(const Edge k)
    700       {
    701         if(!k.idref()%2&&k.idref()/2>=int(container.size()))
    702           container.resize(k.idref()/2+1);
    703       }
    704       void erase(const Edge k) { }
    705      
    706       void set(Edge n, T a) { container[n.idref()/2]=a; }
    707       //T get(Edge n) const { return container[n.idref()/2]; }
    708       typename std::vector<T>::reference
    709       operator[](Edge n) { return container[n.idref()/2]; }
    710       typename std::vector<T>::const_reference
    711       operator[](Edge n) const { return container[n.idref()/2]; }
    712 
    713       ///\warning There is no safety check at all!
    714       ///Using operator = between maps attached to different graph may
    715       ///cause serious problem.
    716       ///\todo Is this really so?
    717       ///\todo It can copy between different types.
    718       const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
    719       {
    720         container = m.container;
    721         return *this;
    722       }
    723       template<typename TT>
    724       const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
    725       {
    726         std::copy(m.container.begin(), m.container.end(), container.begin());
    727         return *this;
    728       }
    729      
    730       void update() {}    //Useless for DynMaps
    731       void update(T a) {}  //Useless for DynMaps
    732 
    733     };
    734397
    735398  };
  • src/work/deba/main.cpp

    r674 r698  
    11#include <iostream>
    22#include <cstdlib>
    3 #include "test_graph.h"
     3#include "list_graph.h"
    44
    55using namespace std;
  • src/work/deba/vector_map_factory.h

    r627 r698  
    44#include <vector>
    55
    6 #include "map_registry.h"
    7 
    86namespace hugo {
    97       
    108  template <typename MapRegistry>
    11   class VectorMapFactory {
    12   public:
     9    class VectorMapFactory {
     10    public:
    1311               
    1412    typedef typename MapRegistry::Graph Graph;
     
    1715
    1816    typedef typename MapRegistry::MapBase MapBase;
     17
    1918               
    2019    template <typename V>
     
    2322      typedef V Value;
    2423       
     24      typedef std::vector<Value> Container;
    2525      Map() {}
    2626                       
     
    3535       
    3636       
    37       Value& operator[](const Key& key) {
     37      typename Container::reference operator[](const Key& key) {
    3838        int id = graph->id(key);
    3939        return container[id];
    4040      }
    4141               
    42       const Value& operator[](const Key& key) const {
     42      typename Container::const_reference operator[](const Key& key) const {
    4343        int id = graph->id(key);
    4444        return container[id];
    4545      }
    4646       
    47       const Value& get(const Key& key) const {
    48         int id = graph->id(key);
    49         return container[id];
    50       }
    51                
    5247      void set(const Key& key, const Value& val) {
    5348        int id = graph->id(key);
     
    6459      void erase(const Key& key) {}
    6560       
     61      class const_iterator {
     62
     63      private:
     64     
     65      };
     66
     67      class iterator {
     68      public:
     69        iterator() {}
     70     
     71        std::pair<const Key&, Value&> operator*() {
     72          return std::pair<const Key&, Value&>(static_cast<Key&>(it), map[it]);
     73        }
     74
     75        iterator& operator++() { ++it; return *this; }
     76        iterator operator++(int) { iterator tmp(it); ++it; return tmp; }
     77      private:
     78        Map& map;
     79        KeyIt it;
     80      };
     81
    6682      private:
    6783      typedef std::vector<Value> Container;
    6884               
    6985      Container container;
     86
     87
    7088    };
     89
     90   
     91
    7192               
    7293  };
Note: See TracChangeset for help on using the changeset viewer.