COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/alpar/smart_graph.h @ 209:9a37b8d02d74

Last change on this file since 209:9a37b8d02d74 was 209:9a37b8d02d74, checked in by Alpar Juttner, 21 years ago

get() -> operator[]()

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