COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/alpar/smart_graph.h @ 185:259540358bbf

Last change on this file since 185:259540358bbf was 185:259540358bbf, checked in by Alpar Juttner, 16 years ago

Dynamic maps became the defaults.
Maps got copy constructors and operator=. Also work between different types.
SymSmartGraph? added
smart_graph_demo.cc was extended.

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