COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/smart_graph.h @ 720:193d881b23ad

Last change on this file since 720:193d881b23ad was 713:57c0b110b31e, checked in by Alpar Juttner, 20 years ago

Oops: "static" and "const" does not like each other.

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