COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/alpar/smart_graph.h @ 157:ee17030e5f47

Last change on this file since 157:ee17030e5f47 was 157:ee17030e5f47, checked in by Alpar Juttner, 16 years ago

One more step toward the standars interface.

File size: 11.3 KB
Line 
1// -*- mode:C++ -*-
2
3#ifndef SMART_GRAPH_H
4#define SMART_GRAPH_H
5
6#include <vector>
7#include <limits.h>
8
9struct _Invalid {} Invalid;
10
11namespace hugo {
12
13  class SmartGraph {
14
15//     static const int INVALID=-1;
16//     static const int INVALID_NODE=INT_MAX;
17
18    struct NodeT
19    {
20      int first_in,first_out;     
21      NodeT() : first_in(-1), first_out(-1) {}
22    };
23    struct EdgeT
24    {
25      int head, tail, next_in, next_out;     
26      //FIXME: is this necessary?
27      EdgeT() : next_in(-1), next_out(-1) {} 
28    };
29
30    std::vector<NodeT> nodes;
31
32    std::vector<EdgeT> edges;
33   
34    template <typename Key> class DynMapBase
35    {
36    protected:
37      SmartGraph* G;
38    public:
39      virtual void add(const Key k) = NULL;
40      virtual void erase(const Key k) = NULL;
41      DynMapBase(const SmartGraph &_G) : G(&_G) {}
42      virtual ~DynMapBase() {}
43      friend class SmartGraph;
44    };
45  public:
46    template <typename T> class DynEdgeMap;
47    template <typename T> class DynEdgeMap;
48
49    class NodeIt;
50    class EdgeIt;
51
52  protected:
53    mutable std::vector<DynMapBase<NodeIt> * > dyn_node_maps;
54    mutable std::vector<DynMapBase<EdgeIt> * > dyn_edge_maps;
55   
56  public:
57
58    class EachNodeIt;
59    class EachEdgeIt;
60    class OutEdgeIt;
61    class InEdgeIt;
62   
63    //     class NodeIt { int n; };
64    //     class EachNodeIt : public NodeIt { };
65    //     class EdgeIt { int n; };
66    //     class EachEdgeIt : public EdgeIt {};
67    //     class OutEdgeIt : public EdgeIt {};
68    //     class InEdgeIt : public EdgeIt {};
69    //     class SymEdgeIt;
70   
71    template <typename T> class NodeMap;
72    template <typename T> class EdgeMap;
73   
74  public:
75
76    /* default constructor */
77
78    SmartGraph() : nodes(), edges() { }
79    SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
80   
81    ~SmartGraph()
82    {
83      for(std::vector<DynMapBase<NodeIt> * >::iterator i=dyn_node_maps.begin();
84          i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
85      for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();
86          i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
87    }
88
89    int nodeNum() const { return nodes.size(); }  //FIXME: What is this?
90    int edgeNum() const { return edges.size(); }  //FIXME: What is this?
91
92    int maxNodeId() const { return nodes.size(); }  //FIXME: What is this?
93    int maxEdgeId() const { return edges.size(); }  //FIXME: What is this?
94
95   
96    NodeIt tail(EdgeIt e) const { return edges[e.n].tail; }
97    NodeIt head(EdgeIt e) const { return edges[e.n].head; }
98
99//     NodeIt aNode(const OutEdgeIt& e) const { return tail(e); }
100//     NodeIt aNode(const InEdgeIt& e) const { return head(e); }
101//     //NodeIt aNode(const SymEdgeIt& e) const { return e.aNode(); }
102
103//     NodeIt bNode(const OutEdgeIt& e) const { return head(e); }
104//     NodeIt bNode(const InEdgeIt& e) const { return tail(e); }
105//     //NodeIt bNode(const SymEdgeIt& e) const { return e.bNode(); }
106
107    EachNodeIt& getFirst(EachNodeIt& v) const {
108      v=EachNodeIt(*this); return v; }
109    EachEdgeIt& getFirst(EachEdgeIt& e) const {
110      e=EachEdgeIt(*this); return e; }
111    OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt v) const {
112      e=OutEdgeIt(*this,v); return e; }
113    InEdgeIt& getFirst(InEdgeIt& e, const NodeIt v) const {
114      e=InEdgeIt(*this,v); return e; }
115
116    template< typename It >
117    It first() const {
118      It e;
119      getFirst(e);
120      return e;
121    }
122
123    template< typename It >
124    It first(NodeIt v) const {
125      It e;
126      getFirst(e, v);
127      return e;
128    }
129
130    bool valid(EdgeIt e) const { return e.n!=-1; }
131    //    bool valid(EachEdgeIt e) const { return e.n<int(edges.size()); }
132    bool valid(NodeIt n) const { return n.n!=-1; }
133   
134    void setInvalid(EdgeIt &e) { e.n=-1; }
135    void setInvalid(NodeIt &n) { n.n=-1; }
136   
137    template <typename It> It getNext(It it) const
138    { It tmp(it); return next(tmp); }
139    //{ It tmp; tmp.n=it.n+1; return tmp; }
140
141    NodeIt& next(NodeIt& it) const { it.n=(it.n+2)%nodes.size()-1; return it; }
142    OutEdgeIt& next(OutEdgeIt& it) const
143    { it.n=edges[it.n].next_out; return it; }
144    InEdgeIt& next(InEdgeIt& it) const
145    { it.n=edges[it.n].next_in; return it; }
146    EachEdgeIt& next(EachEdgeIt& it) const { --it.n; return it; }
147
148    int id(NodeIt v) const { return v.n; }
149    int id(EdgeIt e) const { return e.n; }
150
151    NodeIt addNode() {
152      NodeIt n; n.n=nodes.size();
153      nodes.push_back(NodeT()); //FIXME: Hmmm...
154
155      for(std::vector<DynMapBase<NodeIt> * >::iterator i=dyn_node_maps.begin();
156          i!=dyn_node_maps.end(); ++i) (**i).add(n.n);
157
158      return n;
159    }
160   
161    EdgeIt addEdge(NodeIt u, NodeIt v) {
162      EdgeIt e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
163      edges[e.n].tail=u.n; edges[e.n].head=v.n;
164      edges[e.n].next_out=nodes[u.n].first_out;
165      edges[e.n].next_in=nodes[v.n].first_in;
166      nodes[u.n].first_out=nodes[v.n].first_in=e.n;
167
168      for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();
169          i!=dyn_edge_maps.end(); ++i) (**i).add(e);
170
171      return e;
172    }
173
174    void clear() {nodes.clear();edges.clear();}
175
176    class NodeIt {
177      friend class SmartGraph;
178      template <typename T> friend class NodeMap;
179      template <typename T> friend class DynNodeMap;
180     
181      friend class EdgeIt;
182      friend class OutEdgeIt;
183      friend class InEdgeIt;
184      friend class SymEdgeIt;
185
186    protected:
187      int n;
188      friend int SmartGraph::id(NodeIt v) const;
189      NodeIt(int nn) {n=nn;}
190    public:
191      NodeIt() {}
192      NodeIt (_Invalid i) { n=-1; }
193      bool operator==(const NodeIt i) const {return n==i.n;}
194      bool operator!=(const NodeIt i) const {return n!=i.n;}
195      bool operator<(const NodeIt i) const {return n<i.n;}
196    };
197   
198    class EachNodeIt : public NodeIt {
199      friend class SmartGraph;
200    public:
201      EachNodeIt(const SmartGraph& G) : NodeIt(G.nodes.size()?0:-1) { }
202      EachNodeIt() : NodeIt() { }
203    };
204
205    class EdgeIt {
206      friend class SmartGraph;
207      template <typename T> friend class EdgeMap;
208      template <typename T> friend class DynEdgeMap;
209     
210      friend class NodeIt;
211      friend class EachNodeIt;
212    protected:
213      int n;
214      friend int SmartGraph::id(EdgeIt e) const;
215
216      EdgeIt(int nn) {n=nn;}
217    public:
218      EdgeIt() { }
219      EdgeIt (_Invalid i) { n=-1; }
220      bool operator==(const EdgeIt i) const {return n==i.n;}
221      bool operator!=(const EdgeIt i) const {return n!=i.n;}
222      bool operator<(const EdgeIt i) const {return n<i.n;}
223    };
224   
225    class EachEdgeIt : public EdgeIt {
226      friend class SmartGraph;
227    public:
228      EachEdgeIt(const SmartGraph& G) : EdgeIt(G.edges.size()-1) { }
229      EachEdgeIt (_Invalid i) : EdgeIt(i) { }
230      EachEdgeIt() : EdgeIt() { }
231    };
232   
233    class OutEdgeIt : public EdgeIt {
234      friend class SmartGraph;
235    public:
236      OutEdgeIt() : EdgeIt() { }
237      OutEdgeIt (_Invalid i) : EdgeIt(i) { }
238
239      OutEdgeIt(const SmartGraph& G,const NodeIt v)
240        : EdgeIt(G.nodes[v.n].first_out) {}
241    };
242   
243    class InEdgeIt : public EdgeIt {
244      friend class SmartGraph;
245    public:
246      InEdgeIt() : EdgeIt() { }
247      InEdgeIt (_Invalid i) : EdgeIt(i) { }
248      InEdgeIt(const SmartGraph& G,NodeIt v) :EdgeIt(G.nodes[v.n].first_in){}
249    };
250
251    // Map types
252
253    template <typename T>
254    class NodeMap {
255      const SmartGraph& G;
256      std::vector<T> container;
257    public:
258      typedef T ValueType;
259      typedef NodeIt KeyType;
260      NodeMap(const SmartGraph& _G) : G(_G), container(G.maxNodeId()) { }
261      NodeMap(const SmartGraph& _G, T a) :
262        G(_G), container(G.maxNodeId(), a) { }
263      void set(NodeIt n, T a) { container[n.n]=a; }
264      T get(NodeIt n) const { return container[n.n]; }
265      T& operator[](NodeIt n) { return container[n.n]; }
266      const T& operator[](NodeIt n) const { return container[n.n]; }
267      void update() { container.resize(G.maxNodeId()); }
268      void update(T a) { container.resize(G.maxNodeId(), a); }
269    };
270
271    template <typename T>
272    class EdgeMap {
273      const SmartGraph& G;
274      std::vector<T> container;
275    public:
276      typedef T ValueType;
277      typedef EdgeIt KeyType;
278      EdgeMap(const SmartGraph& _G) : G(_G), container(G.maxEdgeId()) { }
279      EdgeMap(const SmartGraph& _G, T a) :
280        G(_G), container(G.maxEdgeId(), a) { }
281      void set(EdgeIt e, T a) { container[e.n]=a; }
282      T get(EdgeIt e) const { return container[e.n]; }
283      T& operator[](EdgeIt e) { return container[e.n]; }
284      const T& operator[](EdgeIt e) const { return container[e.n]; }
285      void update() { container.resize(G.maxEdgeId()); }
286      void update(T a) { container.resize(G.maxEdgeId(), a); }
287    };
288
289    template <typename T> class DynNodeMap : public DynMapBase<NodeIt>
290    {
291      std::vector<T> container;
292
293    public:
294      typedef T ValueType;
295      typedef NodeIt KeyType;
296
297      DynNodeMap(const SmartGraph &_G) :
298        DynMapBase<NodeIt>(_G), container(_G.maxNodeId())
299      {
300        //FIXME: What if there are empty Id's?
301        //FIXME: Can I use 'this' in a constructor?
302        G->dyn_node_maps.push_back(this);
303      }
304      ~DynNodeMap()
305      {
306        if(G) {
307          std::vector<DynMapBase<NodeIt>* >::iterator i;
308          for(i=G->dyn_node_maps.begin();
309              i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
310          //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
311          //A better way to do that: (Is this really important?)
312          if(*i==this) {
313            *i=G->dyn_node_maps.back();
314            G->dyn_node_maps.pop_back();
315          }
316        }
317      }
318
319      void add(const NodeIt k)
320      {
321        if(k.n>=container.size()) container.resize(k.n+1);
322      }
323//       void erase(const NodeIt k)
324//       {
325//      //FIXME: Please implement me.
326//       }
327//       void erase(const EdgeIt k)
328//       {
329//      //FIXME: Please implement me.
330//       }
331     
332      void set(NodeIt n, T a) { container[n.n]=a; }
333      T get(NodeIt n) const { return container[n.n]; }
334      T& operator[](NodeIt n) { return container[n.n]; }
335      const T& operator[](NodeIt n) const { return container[n.n]; }
336
337      void update() {}    //Useless for DynMaps
338      void update(T a) {}  //Useless for DynMaps
339    };
340   
341    template <typename T> class DynEdgeMap : public DynMapBase<EdgeIt>
342    {
343      std::vector<T> container;
344
345    public:
346      typedef T ValueType;
347      typedef EdgeIt KeyType;
348
349      DynEdgeMap(const SmartGraph &_G) :
350        DynMapBase<EdgeIt>(_G), container(_G.maxEdgeId())
351      {
352        //FIXME: What if there are empty Id's?
353        //FIXME: Can I use 'this' in a constructor?
354        G->dyn_edge_maps.push_back(this);
355      }
356      ~DynEdgeMap()
357      {
358        if(G) {
359          std::vector<DynMapBase<EdgeIt>* >::iterator i;
360          for(i=G->dyn_edge_maps.begin();
361              i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
362          //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
363          //A better way to do that: (Is this really important?)
364          if(*i==this) {
365            *i=G->dyn_edge_maps.back();
366            G->dyn_edge_maps.pop_back();
367          }
368        }
369      }
370     
371      void add(const EdgeIt k)
372      {
373        if(k.n>=int(container.size())) container.resize(k.n+1);
374      }
375      void erase(const EdgeIt k)
376      {
377        //FIXME: Please implement me.
378      }
379     
380      void set(EdgeIt n, T a) { container[n.n]=a; }
381      T get(EdgeIt n) const { return container[n.n]; }
382      T& operator[](EdgeIt n) { return container[n.n]; }
383      const T& operator[](EdgeIt n) const { return container[n.n]; }
384
385      void update() {}    //Useless for DynMaps
386      void update(T a) {}  //Useless for DynMaps
387    };
388       
389  };
390} //namespace hugo
391
392
393
394
395#endif //SMART_GRAPH_H
Note: See TracBrowser for help on using the repository browser.