COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/include/smart_graph.h @ 407:e34e1bc610cf

Last change on this file since 407:e34e1bc610cf was 407:e34e1bc610cf, checked in by Alpar Juttner, 16 years ago

The doc modules clearly needs some restructuring...

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