COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/j_graph.h @ 224:5bc1c83257f8

Last change on this file since 224:5bc1c83257f8 was 131:9aca797b87e8, checked in by jacint, 20 years ago

Alpar SmartGraph?-janak atirasa

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