COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/smart_graph.h @ 539:fb261e3a9a0f

Last change on this file since 539:fb261e3a9a0f was 539:fb261e3a9a0f, checked in by Akos Ladanyi, 20 years ago

Rename 'include' to 'hugo' (for automake)

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