COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/alpar/smart_graph.h @ 115:3d9681ef6116

Last change on this file since 115:3d9681ef6116 was 115:3d9681ef6116, checked in by Alpar Juttner, 21 years ago

.

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