COIN-OR::LEMON - Graph Library

Changeset 185:259540358bbf in lemon-0.x


Ignore:
Timestamp:
03/13/04 23:53:07 (20 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@261
Message:

Dynamic maps became the defaults.
Maps got copy constructors and operator=. Also work between different types.
SymSmartGraph? added
smart_graph_demo.cc was extended.

Location:
src/work/alpar
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/work/alpar/smart_graph.h

    r177 r185  
    11// -*- mode:C++ -*-
    22
    3 #ifndef SMART_GRAPH_H
    4 #define SMART_GRAPH_H
     3#ifndef HUGO_SMART_GRAPH_H
     4#define HUGO_SMART_GRAPH_H
    55
    66#include <vector>
     
    1111namespace hugo {
    1212
     13  class SymSmartGraph;
     14
     15  //  template<typename T> class SymSmartGraph::SymEdgeMap;
     16 
    1317  class SmartGraph {
    1418
     
    2933    std::vector<EdgeT> edges;
    3034   
     35    protected:
     36   
    3137    template <typename Key> class DynMapBase
    3238    {
    3339    protected:
    34       SmartGraph* G;
     40      const SmartGraph* G;
    3541    public:
    3642      virtual void add(const Key k) = NULL;
     
    4046      friend class SmartGraph;
    4147    };
     48   
    4249  public:
    43     template <typename T> class DynEdgeMap;
    44     template <typename T> class DynEdgeMap;
     50    template <typename T> class EdgeMap;
     51    template <typename T> class EdgeMap;
    4552
    4653    class Node;
    4754    class Edge;
    4855
    49   protected:
     56    //  protected:
     57    // HELPME:
     58  public:
     59    ///\bug It must be public because of SymEdgeMap.
     60    ///
    5061    mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
     62    ///\bug It must be public because of SymEdgeMap.
     63    ///
    5164    mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
    5265   
     
    169182      friend class SmartGraph;
    170183      template <typename T> friend class NodeMap;
    171       template <typename T> friend class DynNodeMap;
    172184     
    173185      friend class Edge;
     
    198210      friend class SmartGraph;
    199211      template <typename T> friend class EdgeMap;
    200       template <typename T> friend class DynEdgeMap;
     212
     213      //template <typename T> friend class SymSmartGraph::SymEdgeMap;     
     214      //friend Edge SymSmartGraph::opposite(Edge) const;
    201215     
    202216      friend class Node;
     
    213227      bool operator!=(const Edge i) const {return n!=i.n;}
    214228      bool operator<(const Edge i) const {return n<i.n;}
     229      ///\bug This is a workaround until somebody tells me how to
     230      ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
     231      int &idref() {return n;}
     232      const int &idref() const {return n;}
    215233    };
    216234   
     
    221239      EdgeIt (Invalid i) : Edge(i) { }
    222240      EdgeIt() : Edge() { }
     241      ///\bug This is a workaround until somebody tells me how to
     242      ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
     243      int &idref() {return n;}
    223244    };
    224245   
     
    243264    // Map types
    244265
    245     template <typename T>
    246     class NodeMap {
    247       const SmartGraph& G;
     266//     // Static Maps are not necessary.
     267//     template <typename T>
     268//     class NodeMap {
     269//       const SmartGraph& G;
     270//       std::vector<T> container;
     271//     public:
     272//       typedef T ValueType;
     273//       typedef Node KeyType;
     274//       NodeMap(const SmartGraph& _G) : G(_G), container(G.maxNodeId()) { }
     275//       NodeMap(const SmartGraph& _G, T a) :
     276//      G(_G), container(G.maxNodeId(), a) { }
     277//       void set(Node n, T a) { container[n.n]=a; }
     278//       T get(Node n) const { return container[n.n]; }
     279//       T& operator[](Node n) { return container[n.n]; }
     280//       const T& operator[](Node n) const { return container[n.n]; }
     281//       void update() { container.resize(G.maxNodeId()); }
     282//       void update(T a) { container.resize(G.maxNodeId(), a); }
     283//     };
     284
     285//     template <typename T>
     286//     class EdgeMap {
     287//       const SmartGraph& G;
     288//       std::vector<T> container;
     289//     public:
     290//       typedef T ValueType;
     291//       typedef Edge KeyType;
     292//       EdgeMap(const SmartGraph& _G) : G(_G), container(G.maxEdgeId()) { }
     293//       EdgeMap(const SmartGraph& _G, T a) :
     294//      G(_G), container(G.maxEdgeId(), a) { }
     295//       void set(Edge e, T a) { container[e.n]=a; }
     296//       T get(Edge e) const { return container[e.n]; }
     297//       T& operator[](Edge e) { return container[e.n]; }
     298//       const T& operator[](Edge e) const { return container[e.n]; }
     299//       void update() { container.resize(G.maxEdgeId()); }
     300//       void update(T a) { container.resize(G.maxEdgeId(), a); }
     301//     };
     302
     303    template <typename T> class NodeMap : public DynMapBase<Node>
     304    {
    248305      std::vector<T> container;
     306
    249307    public:
    250308      typedef T ValueType;
    251309      typedef Node KeyType;
    252       NodeMap(const SmartGraph& _G) : G(_G), container(G.maxNodeId()) { }
    253       NodeMap(const SmartGraph& _G, T a) :
    254         G(_G), container(G.maxNodeId(), a) { }
    255       void set(Node n, T a) { container[n.n]=a; }
    256       T get(Node n) const { return container[n.n]; }
    257       T& operator[](Node n) { return container[n.n]; }
    258       const T& operator[](Node n) const { return container[n.n]; }
    259       void update() { container.resize(G.maxNodeId()); }
    260       void update(T a) { container.resize(G.maxNodeId(), a); }
    261     };
    262 
    263     template <typename T>
    264     class EdgeMap {
    265       const SmartGraph& G;
    266       std::vector<T> container;
    267     public:
    268       typedef T ValueType;
    269       typedef Edge KeyType;
    270       EdgeMap(const SmartGraph& _G) : G(_G), container(G.maxEdgeId()) { }
    271       EdgeMap(const SmartGraph& _G, T a) :
    272         G(_G), container(G.maxEdgeId(), a) { }
    273       void set(Edge e, T a) { container[e.n]=a; }
    274       T get(Edge e) const { return container[e.n]; }
    275       T& operator[](Edge e) { return container[e.n]; }
    276       const T& operator[](Edge e) const { return container[e.n]; }
    277       void update() { container.resize(G.maxEdgeId()); }
    278       void update(T a) { container.resize(G.maxEdgeId(), a); }
    279     };
    280 
    281     template <typename T> class DynNodeMap : public DynMapBase<Node>
    282     {
    283       std::vector<T> container;
    284 
    285     public:
    286       typedef T ValueType;
    287       typedef Node KeyType;
    288 
    289       DynNodeMap(const SmartGraph &_G) :
     310
     311      NodeMap(const SmartGraph &_G) :
    290312        DynMapBase<Node>(_G), container(_G.maxNodeId())
    291313      {
    292         //FIXME: What if there are empty Id's?
    293         //FIXME: Can I use 'this' in a constructor?
    294314        G->dyn_node_maps.push_back(this);
    295315      }
    296       ~DynNodeMap()
     316      NodeMap(const SmartGraph &_G,const T &t) :
     317        DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
     318      {
     319        G->dyn_node_maps.push_back(this);
     320      }
     321     
     322      NodeMap(const NodeMap<T> &m) :
     323        DynMapBase<Node>(*m.G), container(m.container)
     324      {
     325        G->dyn_node_maps.push_back(this);
     326      }
     327
     328      template<typename TT> friend class NodeMap;
     329 
     330      ///\todo It can copy between different types.
     331      ///
     332      template<typename TT> NodeMap(const NodeMap<TT> &m) :
     333        DynMapBase<Node>(*m.G)
     334      {
     335        G->dyn_node_maps.push_back(this);
     336        typename std::vector<TT>::const_iterator i;
     337        for(typename std::vector<TT>::const_iterator i=m.container.begin();
     338            i!=m.container.end();
     339            i++)
     340          container.push_back(*i);
     341      }
     342      ~NodeMap()
    297343      {
    298344        if(G) {
     
    311357      void add(const Node k)
    312358      {
    313         if(k.n>=container.size()) container.resize(k.n+1);
    314       }
    315 
    316 //       void erase(const Node k)
    317 //       {
    318 //      //FIXME: Please implement me.
    319 //       }
    320 //       void erase(const Edge k)
    321 //       {
    322 //      //FIXME: Please implement me.
    323 //       }
     359        if(k.n>=int(container.size())) container.resize(k.n+1);
     360      }
     361
     362      void erase(const Node k) { }
    324363     
    325364      void set(Node n, T a) { container[n.n]=a; }
     
    328367      const T& operator[](Node n) const { return container[n.n]; }
    329368
     369      ///\warning There is no safety check at all!
     370      ///Using operator = between maps attached to different graph may
     371      ///cause serious problem.
     372      ///\todo Is this really so?
     373      ///\todo It can copy between different types.
     374      const NodeMap<T>& operator=(const NodeMap<T> &m)
     375      {
     376        container = m.container;
     377        return *this;
     378      }
     379      template<typename TT>
     380      const NodeMap<T>& operator=(const NodeMap<TT> &m)
     381      {
     382        copy(m.container.begin(), m.container.end(), container.begin());
     383        return *this;
     384      }
     385     
    330386      void update() {}    //Useless for DynMaps
    331387      void update(T a) {}  //Useless for DynMaps
    332388    };
    333389   
    334     template <typename T> class DynEdgeMap : public DynMapBase<Edge>
     390    template <typename T> class EdgeMap : public DynMapBase<Edge>
    335391    {
    336392      std::vector<T> container;
     
    340396      typedef Edge KeyType;
    341397
    342       DynEdgeMap(const SmartGraph &_G) :
     398      EdgeMap(const SmartGraph &_G) :
    343399        DynMapBase<Edge>(_G), container(_G.maxEdgeId())
    344400      {
     
    347403        G->dyn_edge_maps.push_back(this);
    348404      }
    349       ~DynEdgeMap()
     405      EdgeMap(const SmartGraph &_G,const T &t) :
     406        DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
     407      {
     408        G->dyn_edge_maps.push_back(this);
     409      }
     410      EdgeMap(const EdgeMap<T> &m) :
     411        DynMapBase<Edge>(*m.G), container(m.container)
     412      {
     413        G->dyn_node_maps.push_back(this);
     414      }
     415
     416      template<typename TT> friend class EdgeMap;
     417
     418      ///\todo It can copy between different types.
     419      ///
     420      template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
     421        DynMapBase<Edge>(*m.G)
     422      {
     423        G->dyn_node_maps.push_back(this);
     424        typename std::vector<TT>::const_iterator i;
     425        for(typename std::vector<TT>::const_iterator i=m.container.begin();
     426            i!=m.container.end();
     427            i++)
     428          container.push_back(*i);
     429      }
     430      ~EdgeMap()
    350431      {
    351432        if(G) {
     
    366447        if(k.n>=int(container.size())) container.resize(k.n+1);
    367448      }
    368       void erase(const Edge k)
    369       {
    370         //FIXME: Please implement me.
    371       }
     449      void erase(const Edge k) { }
    372450     
    373451      void set(Edge n, T a) { container[n.n]=a; }
     
    376454      const T& operator[](Edge n) const { return container[n.n]; }
    377455
     456      ///\warning There is no safety check at all!
     457      ///Using operator = between maps attached to different graph may
     458      ///cause serious problem.
     459      ///\todo Is this really so?
     460      ///\todo It can copy between different types.
     461      const EdgeMap<T>& operator=(const EdgeMap<T> &m)
     462      {
     463        container = m.container;
     464        return *this;
     465      }
     466      template<typename TT>
     467      const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
     468      {
     469        copy(m.container.begin(), m.container.end(), container.begin());
     470        return *this;
     471      }
     472     
    378473      void update() {}    //Useless for DynMaps
    379474      void update(T a) {}  //Useless for DynMaps
    380475    };
    381        
     476
    382477  };
     478
     479  ///Graph for bidirectional edges.
     480
     481  ///The purpose of this graph structure is to handle graphs
     482  ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
     483  ///of oppositely directed edges. You can define edge maps which
     484  ///stores a common value for the edge pairs. The usual edge maps can be used
     485  ///as well.
     486  ///
     487  ///The oppositely directed edge can also be obtained easily.
     488
     489  class SymSmartGraph : public SmartGraph
     490  {
     491  public:
     492    SymSmartGraph() : SmartGraph() { }
     493    SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
     494    Edge addEdge(Node u, Node v)
     495    {
     496      Edge e = SmartGraph::addEdge(u,v);
     497      SmartGraph::addEdge(v,u);
     498      return e;
     499    }
     500
     501    Edge opposite(Edge e) const
     502    {
     503      Edge f;
     504      f.idref() = e.idref() - 2*(e.idref()%2) + 1;
     505      return f;
     506    }
     507   
     508    template <typename T> class SymEdgeMap : public DynMapBase<Edge>
     509    {
     510      std::vector<T> container;
     511     
     512    public:
     513      typedef T ValueType;
     514      typedef Edge KeyType;
     515
     516      SymEdgeMap(const SmartGraph &_G) :
     517        DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
     518      {
     519        G->dyn_edge_maps.push_back(this);
     520      }
     521      SymEdgeMap(const SmartGraph &_G,const T &t) :
     522        DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
     523      {
     524        G->dyn_edge_maps.push_back(this);
     525      }
     526
     527      SymEdgeMap(const SymEdgeMap<T> &m) :
     528        DynMapBase<SymEdge>(*m.G), container(m.container)
     529      {
     530        G->dyn_node_maps.push_back(this);
     531      }
     532
     533      //      template<typename TT> friend class SymEdgeMap;
     534
     535      ///\todo It can copy between different types.
     536      ///
     537
     538      template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
     539        DynMapBase<SymEdge>(*m.G)
     540      {
     541        G->dyn_node_maps.push_back(this);
     542        typename std::vector<TT>::const_iterator i;
     543        for(typename std::vector<TT>::const_iterator i=m.container.begin();
     544            i!=m.container.end();
     545            i++)
     546          container.push_back(*i);
     547      }
     548 
     549      ~SymEdgeMap()
     550      {
     551        if(G) {
     552          std::vector<DynMapBase<Edge>* >::iterator i;
     553          for(i=G->dyn_edge_maps.begin();
     554              i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
     555          //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
     556          //A better way to do that: (Is this really important?)
     557          if(*i==this) {
     558            *i=G->dyn_edge_maps.back();
     559            G->dyn_edge_maps.pop_back();
     560          }
     561        }
     562      }
     563     
     564      void add(const Edge k)
     565      {
     566        if(!k.idref()%2&&k.idref()/2>=int(container.size()))
     567          container.resize(k.idref()/2+1);
     568      }
     569      void erase(const Edge k) { }
     570     
     571      void set(Edge n, T a) { container[n.idref()/2]=a; }
     572      T get(Edge n) const { return container[n.idref()/2]; }
     573      T& operator[](Edge n) { return container[n.idref()/2]; }
     574      const T& operator[](Edge n) const { return container[n.idref()/2]; }
     575
     576      ///\warning There is no safety check at all!
     577      ///Using operator = between maps attached to different graph may
     578      ///cause serious problem.
     579      ///\todo Is this really so?
     580      ///\todo It can copy between different types.
     581      const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
     582      {
     583        container = m.container;
     584        return *this;
     585      }
     586      template<typename TT>
     587      const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
     588      {
     589        copy(m.container.begin(), m.container.end(), container.begin());
     590        return *this;
     591      }
     592     
     593      void update() {}    //Useless for DynMaps
     594      void update(T a) {}  //Useless for DynMaps
     595
     596    };
     597
     598  };
     599 
     600 
    383601} //namespace hugo
    384602
  • src/work/alpar/smart_graph_demo.cc

    r164 r185  
    77using namespace hugo;
    88
    9 //typedef SmartGraph Graph;
    10 typedef EmptyGraph Graph;
     9typedef SmartGraph Graph;
     10//typedef GraphSkeleton Graph;
    1111
    1212
     
    2727 
    2828  Graph G;
    29   NodeIt n;
     29 
     30  {
     31    NodeIt n;
    3032
     33    for(int i=0;i<10;i++) G.addNode();
     34    for(G.first(n);G.valid(n);G.next(n))
     35      for(NodeIt m(G);m!=INVALID;G.next(m))
     36        if(n!=m) G.addEdge(n,m);
     37   
     38    OutEdgeIt e = safeFirstOut(G,n);
     39    OutEdgeIt f = safeFirstOut(G,NodeIt(G));
     40   
     41   
     42    InEdgeIt i(INVALID), j;
     43    InEdgeIt ii(i);
     44    ii=G.first(i,n);
     45    ii=G.next(i);
     46   
     47    OutEdgeIt o(INVALID), oo;
     48    OutEdgeIt ooo(oo);
     49    oo=G.first(o,n);
     50    oo=G.next(o);
     51   
     52    EdgeIt ei(INVALID), eie;
     53    EdgeIt eiee(ei);
     54    eie=G.first(ei);
     55    eie=G.next(ei);
     56   
     57    Edge eee(i);
     58    eee=o;
     59    eee=eie;
     60   
     61   
     62    bool tm;
     63    tm = G.valid(n) && G.valid(i) && G.valid(o) && G.valid(ei);
     64   
     65    std::vector<InEdgeIt> v(10);
     66    std::vector<InEdgeIt> w(10,INVALID);
     67   
     68  }
     69 
     70  // Test of maps
    3171
     72  G.clear();
     73 
    3274  for(int i=0;i<10;i++) G.addNode();
    33   for(G.first(n);G.valid(n);G.next(n))
    34     for(NodeIt m(G);m!=INVALID;G.next(m))
    35       if(n!=m) G.addEdge(n,m);
     75  for(NodeIt i(G);G.valid(i);G.next(i))
     76    for(NodeIt j(G);G.valid(j);G.next(j))
     77      if(i<j) G.addEdge(i,j);           //The iterators are comparable
     78 
     79  Graph::NodeMap<int> n(G);
     80  int count=0;
     81  for(NodeIt i(G);G.valid(i);G.next(i)) n[i]=count++;
     82 
     83  Graph::NodeMap<int> nn=n;
     84  Graph::NodeMap<double> dd=n;
    3685
    37   OutEdgeIt e = safeFirstOut(G,n);
    38   OutEdgeIt f = safeFirstOut(G,NodeIt(G));
     86  n = nn;
    3987 
     88  dd = nn;
     89 
     90  Graph::EdgeMap<int> emap(G);
    4091
    41   InEdgeIt i(INVALID), j;
    42   InEdgeIt ii(i);
    43   ii=G.first(i,n);
    44   ii=G.next(i);
     92  // Test of SymSmartGraph
    4593 
    46   OutEdgeIt o(INVALID), oo;
    47   OutEdgeIt ooo(oo);
    48   oo=G.first(o,n);
    49   oo=G.next(o);
     94  {
     95    typedef SymSmartGraph Graph;
     96    typedef Graph::Edge Edge;
     97    typedef Graph::InEdgeIt InEdgeIt;
     98    typedef Graph::OutEdgeIt OutEdgeIt;
     99    typedef Graph::EdgeIt EdgeIt;
     100    typedef Graph::Node Node;
     101    typedef Graph::NodeIt NodeIt;
     102
     103    Graph G;
     104
     105    for(int i=0;i<10;i++) G.addNode();
     106    for(NodeIt i(G);G.valid(i);G.next(i))
     107      for(NodeIt j(G);G.valid(j);G.next(j))
     108        if(i<j) G.addEdge(i,j);           //The iterators are comparable
    50109 
    51   EdgeIt ei(INVALID), eie;
    52   EdgeIt eiee(ei);
    53   eie=G.first(ei);
    54   eie=G.next(ei);
    55 
    56   Edge eee(i);
    57   eee=o;
    58   eee=eie;
    59  
    60  
    61   bool tm;
    62   tm = G.valid(n) && G.valid(i) && G.valid(o) && G.valid(ei);
    63 
    64   std::vector<InEdgeIt> v(10);
    65   std::vector<InEdgeIt> w(10,INVALID);
     110    Graph::EdgeMap<int> em(G);
     111    Graph::SymEdgeMap<int> sm(G);
     112    for(EdgeIt e(G);G.valid(e);G.next(e)) em[e]=G.id(e);
     113    for(EdgeIt e(G);G.valid(e);G.next(e))
     114      if(G.tail(e)<G.head(e)) sm[e]=G.id(e);
     115   
     116    for(EdgeIt e(G);G.valid(e);G.next(e))
     117      std::cout << G.id(G.tail(e)) << "->" << G.id(G.head(e))
     118                << ": id=" << G.id(e) << " oppid=" << G.id(G.opposite(e))
     119                << " em=" << em[e]
     120                << " sm=" << sm[e] << "\n";
     121   
     122  }
    66123 
    67124}
Note: See TracChangeset for help on using the changeset viewer.