COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/alpar/smart_graph.h @ 146:c4adf922624f

Last change on this file since 146:c4adf922624f was 136:e342e66d9762, checked in by Alpar Juttner, 17 years ago

Zoli listaja

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    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!=INVALID_EDGE; }
131    bool valid(EachEdgeIt e) const { return e.n<int(edges.size()); }
132    bool valid(NodeIt n) const { return n.n<int(nodes.size()); }
133   
134    void setInvalid(EdgeIt &e) { e.n=INVALID_EDGE; }
135    void setInvalid(NodeIt &n) { n.n=INVALID_NODE; }
136   
137    template <typename It> It next(It it) const
138      //    { It tmp(it); return goNext(tmp); }
139    { It tmp; tmp.n=it.n+1; return tmp; }
140
141    NodeIt& goNext(NodeIt& it) const { ++it.n; return it; }
142    OutEdgeIt& goNext(OutEdgeIt& it) const
143    { it.n=edges[it.n].next_out; return it; }
144    InEdgeIt& goNext(InEdgeIt& it) const
145    { it.n=edges[it.n].next_in; return it; }
146    EachEdgeIt& goNext(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.n);
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    public:
190      NodeIt() {}
191      NodeIt(int nn) {n=nn;}
192      bool operator==(const NodeIt i) const {return n==i.n;}
193      bool operator!=(const NodeIt i) const {return n!=i.n;}
194    };
195   
196    class EachNodeIt : public NodeIt {
197      friend class SmartGraph;
198    public:
199      EachNodeIt(const SmartGraph& G) : NodeIt(0) { }
200      EachNodeIt() : NodeIt() { }
201    };
202
203    class EdgeIt {
204      friend class SmartGraph;
205      template <typename T> friend class EdgeMap;
206      template <typename T> friend class DynEdgeMap;
207     
208      friend class NodeIt;
209      friend class EachNodeIt;
210    protected:
211      int n;
212      friend int SmartGraph::id(EdgeIt e) const;
213    public:
214      EdgeIt() { }
215      EdgeIt(int nn) {n=nn;}
216      bool operator==(const EdgeIt i) const {return n==i.n;}
217      bool operator!=(const EdgeIt i) const {return n!=i.n;}
218    };
219   
220    class EachEdgeIt : public EdgeIt {
221      friend class SmartGraph;
222    public:
223      EachEdgeIt(const SmartGraph& G) : EdgeIt(0) { }
224      EachEdgeIt() : EdgeIt() { }
225    };
226   
227    class OutEdgeIt : public EdgeIt {
228      friend class SmartGraph;
229    public:
230      OutEdgeIt() : EdgeIt() { }
231      OutEdgeIt(const SmartGraph& G,const NodeIt v)
232        : EdgeIt(G.nodes[v.n].first_out) {}
233    };
234   
235    class InEdgeIt : public EdgeIt {
236      friend class SmartGraph;
237    public:
238      InEdgeIt() : EdgeIt() { }
239      InEdgeIt(const SmartGraph& G,NodeIt v) :EdgeIt(G.nodes[v.n].first_in){}
240    };
241
242    // Map types
243
244    template <typename T>
245    class NodeMap {
246      const SmartGraph& G;
247      std::vector<T> container;
248    public:
249      typedef T ValueType;
250      typedef NodeIt KeyType;
251      NodeMap(const SmartGraph& _G) : G(_G), container(G.maxNodeId()) { }
252      NodeMap(const SmartGraph& _G, T a) :
253        G(_G), container(G.maxNodeId(), a) { }
254      void set(NodeIt n, T a) { container[n.n]=a; }
255      T get(NodeIt n) const { return container[n.n]; }
256      T& operator[](NodeIt n) { return container[n.n]; }
257      const T& operator[](NodeIt n) const { return container[n.n]; }
258      void update() { container.resize(G.maxNodeId()); }
259      void update(T a) { container.resize(G.maxNodeId(), a); }
260    };
261
262    template <typename T>
263    class EdgeMap {
264      const SmartGraph& G;
265      std::vector<T> container;
266    public:
267      typedef T ValueType;
268      typedef EdgeIt KeyType;
269      EdgeMap(const SmartGraph& _G) : G(_G), container(G.maxEdgeId()) { }
270      EdgeMap(const SmartGraph& _G, T a) :
271        G(_G), container(G.maxEdgeId(), a) { }
272      void set(EdgeIt e, T a) { container[e.n]=a; }
273      T get(EdgeIt e) const { return container[e.n]; }
274      T& operator[](EdgeIt e) { return container[e.n]; }
275      const T& operator[](EdgeIt e) const { return container[e.n]; }
276      void update() { container.resize(G.maxEdgeId()); }
277      void update(T a) { container.resize(G.maxEdgeId(), a); }
278    };
279
280    template <typename T> class DynNodeMap : public DynMapBase<NodeIt>
281    {
282      std::vector<T> container;
283
284    public:
285      typedef T ValueType;
286      typedef NodeIt KeyType;
287
288      DynNodeMap(SmartGraph &_G) :
289        DynMapBase<NodeIt>(_G), container(_G.maxNodeId())
290      {
291        //FIXME: What if there are empty Id's?
292        //FIXME: Can I use 'this' in a constructor?
293        G->dyn_node_maps.push_back(this);
294      }
295      ~DynNodeMap()
296      {
297        if(G) {
298          std::vector<DynMapBase<NodeIt>* >::iterator i;
299          for(i=G->dyn_node_maps.begin();
300              i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
301          //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
302          //A better way to do that: (Is this really important?)
303          if(*i==this) {
304            *i=G->dyn_node_maps.back();
305            G->dyn_node_maps.pop_back();
306          }
307        }
308      }
309
310      void add(const NodeIt k)
311      {
312        if(k.n>=container.size()) container.resize(k.n+1);
313      }
314      void erase(const NodeIt k)
315      {
316        //FIXME: Please implement me.
317      }
318     
319      void set(NodeIt n, T a) { container[n.n]=a; }
320      T get(NodeIt n) const { return container[n.n]; }
321      T& operator[](NodeIt n) { return container[n.n]; }
322      const T& operator[](NodeIt n) const { return container[n.n]; }
323
324      void update() {}    //Useless for DynMaps
325      void update(T a) {}  //Useless for DynMaps
326    };
327   
328    template <typename T> class DynEdgeMap : public DynMapBase<EdgeIt>
329    {
330      std::vector<T> container;
331
332    public:
333      typedef T ValueType;
334      typedef EdgeIt KeyType;
335
336      DynEdgeMap(SmartGraph &_G) :
337        DynMapBase<EdgeIt>(_G), container(_G.maxEdgeId())
338      {
339        //FIXME: What if there are empty Id's?
340        //FIXME: Can I use 'this' in a constructor?
341        G->dyn_edge_maps.push_back(this);
342      }
343      ~DynEdgeMap()
344      {
345        if(G) {
346          std::vector<DynMapBase<EdgeIt>* >::iterator i;
347          for(i=G->dyn_edge_maps.begin();
348              i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
349          //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
350          //A better way to do that: (Is this really important?)
351          if(*i==this) {
352            *i=G->dyn_edge_maps.back();
353            G->dyn_edge_maps.pop_back();
354          }
355        }
356      }
357     
358      void add(const EdgeIt k)
359      {
360        if(k.n>=int(container.size())) container.resize(k.n+1);
361      }
362      void erase(const EdgeIt k)
363      {
364        //FIXME: Please implement me.
365      }
366     
367      void set(EdgeIt n, T a) { container[n.n]=a; }
368      T get(EdgeIt n) const { return container[n.n]; }
369      T& operator[](EdgeIt n) { return container[n.n]; }
370      const T& operator[](EdgeIt n) const { return container[n.n]; }
371
372      void update() {}    //Useless for DynMaps
373      void update(T a) {}  //Useless for DynMaps
374    };
375       
376  };
377} //namespace hugo
378
379#endif //SMART_GRAPH_H
Note: See TracBrowser for help on using the repository browser.