COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/alpar/smart_graph.h @ 186:47cd1716870e

Last change on this file since 186:47cd1716870e was 186:47cd1716870e, checked in by Alpar Juttner, 16 years ago

.

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