COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/smart_graph.h @ 753:f5382a084c07

Last change on this file since 753:f5382a084c07 was 753:f5382a084c07, checked in by Alpar Juttner, 17 years ago

doc change - one more todo (saveState()).

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