COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/alpar/smart_graph.h @ 550:9e7613fa6d27

Last change on this file since 550:9e7613fa6d27 was 399:11d69d6502e4, checked in by Alpar Juttner, 21 years ago

The diffs in src/include/smart_graph.h between 528:529 was merged into
this file.

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