COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/alpar/smart_graph.h @ 129:1630a5b631c8

Last change on this file since 129:1630a5b631c8 was 129:1630a5b631c8, checked in by Alpar Juttner, 16 years ago

setInvalid() functions added.

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