COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/smart_graph.h @ 774:4297098d9677

Last change on this file since 774:4297098d9677 was 774:4297098d9677, checked in by Alpar Juttner, 17 years ago

Merge back the whole branches/hugo++ to trunk.

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