COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/include/smart_graph.h @ 456:02c28d3cf97b

Last change on this file since 456:02c28d3cf97b was 456:02c28d3cf97b, checked in by Alpar Juttner, 20 years ago

Doxygen options changed.
\author's added.

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