COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/alpar/smart_graph.h @ 174:44700ed9ffaa

Last change on this file since 174:44700ed9ffaa was 174:44700ed9ffaa, checked in by marci, 16 years ago

towards on ListGraph?, SmartGraph? compatibility

File size: 11.2 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
9#include <invalid.h>
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 Node;
50    class Edge;
51
52  protected:
53    mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
54    mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
55   
56  public:
57
58    class NodeIt;
59    class EdgeIt;
60    class OutEdgeIt;
61    class InEdgeIt;
62   
63    //     class Node { int n; };
64    //     class NodeIt : public Node { };
65    //     class Edge { int n; };
66    //     class EdgeIt : public Edge {};
67    //     class OutEdgeIt : public Edge {};
68    //     class InEdgeIt : public Edge {};
69    //     class SymEdge;
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<Node> * >::iterator i=dyn_node_maps.begin();
84          i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
85      for(std::vector<DynMapBase<Edge> * >::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    Node tail(Edge e) const { return edges[e.n].tail; }
97    Node head(Edge e) const { return edges[e.n].head; }
98
99    // Marci
100    Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
101    Node aNode(InEdgeIt e) const { return edges[e.n].head; }
102//     //Node aNode(const SymEdge& e) const { return e.aNode(); }
103
104    // Marci
105    Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
106    Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
107//     //Node bNode(const SymEdge& e) const { return e.bNode(); }
108
109    NodeIt& first(NodeIt& v) const {
110      v=NodeIt(*this); return v; }
111    EdgeIt& first(EdgeIt& e) const {
112      e=EdgeIt(*this); return e; }
113    OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
114      e=OutEdgeIt(*this,v); return e; }
115    InEdgeIt& first(InEdgeIt& e, const Node v) const {
116      e=InEdgeIt(*this,v); return e; }
117
118    template< typename It >
119    It first() const {
120      It e;
121      //Marci
122      /*getF*/first(e);
123      return e;
124    }
125
126    template< typename It >
127    It first(Node v) const {
128      It e;
129      //Marci
130      /*getF*/first(e, v);
131      return e;
132    }
133
134    bool valid(Edge e) const { return e.n!=-1; }
135    //    bool valid(EdgeIt e) const { return e.n<int(edges.size()); }
136    bool valid(Node n) const { return n.n!=-1; }
137   
138    void setInvalid(Edge &e) { e.n=-1; }
139    void setInvalid(Node &n) { n.n=-1; }
140   
141    template <typename It> It getNext(It it) const
142    { It tmp(it); return next(tmp); }
143    //{ It tmp; tmp.n=it.n+1; return tmp; }
144
145    //FIXME correction Marci: I changed to NodeIt from Node
146    //NodeIt& next(NodeIt& it) const { it.n=(it.n+2)%nodes.size()-1; return it; }
147    NodeIt& next(NodeIt& it) const {
148      it.n=(it.n+2)%(nodes.size()+1)-1;
149      return it;
150    }
151    OutEdgeIt& next(OutEdgeIt& it) const
152    { it.n=edges[it.n].next_out; return it; }
153    InEdgeIt& next(InEdgeIt& it) const
154    { it.n=edges[it.n].next_in; return it; }
155    EdgeIt& next(EdgeIt& it) const { --it.n; return it; }
156
157    int id(Node v) const { return v.n; }
158    int id(Edge e) const { return e.n; }
159
160    Node addNode() {
161      Node n; n.n=nodes.size();
162      nodes.push_back(NodeT()); //FIXME: Hmmm...
163
164      for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
165          i!=dyn_node_maps.end(); ++i) (**i).add(n.n);
166
167      return n;
168    }
169   
170    Edge addEdge(Node u, Node v) {
171      Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
172      edges[e.n].tail=u.n; edges[e.n].head=v.n;
173      edges[e.n].next_out=nodes[u.n].first_out;
174      edges[e.n].next_in=nodes[v.n].first_in;
175      nodes[u.n].first_out=nodes[v.n].first_in=e.n;
176
177      for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
178          i!=dyn_edge_maps.end(); ++i) (**i).add(e);
179
180      return e;
181    }
182
183    void clear() {nodes.clear();edges.clear();}
184
185    class Node {
186      friend class SmartGraph;
187      template <typename T> friend class NodeMap;
188      template <typename T> friend class DynNodeMap;
189     
190      friend class Edge;
191      friend class OutEdgeIt;
192      friend class InEdgeIt;
193      friend class SymEdge;
194
195    protected:
196      int n;
197      friend int SmartGraph::id(Node v) const;
198      Node(int nn) {n=nn;}
199    public:
200      Node() {}
201      Node (Invalid i) { n=-1; }
202      bool operator==(const Node i) const {return n==i.n;}
203      bool operator!=(const Node i) const {return n!=i.n;}
204      bool operator<(const Node i) const {return n<i.n;}
205    };
206   
207    class NodeIt : public Node {
208      friend class SmartGraph;
209    public:
210      NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
211      NodeIt() : Node() { }
212    };
213
214    class Edge {
215      friend class SmartGraph;
216      template <typename T> friend class EdgeMap;
217      template <typename T> friend class DynEdgeMap;
218     
219      friend class Node;
220      friend class NodeIt;
221    protected:
222      int n;
223      friend int SmartGraph::id(Edge e) const;
224
225      Edge(int nn) {n=nn;}
226    public:
227      Edge() { }
228      // Marci: kiszedtem az Invalid i-bol az i-t
229      Edge (Invalid) { n=-1; }
230      bool operator==(const Edge i) const {return n==i.n;}
231      bool operator!=(const Edge i) const {return n!=i.n;}
232      bool operator<(const Edge i) const {return n<i.n;}
233    };
234   
235    class EdgeIt : public Edge {
236      friend class SmartGraph;
237    public:
238      EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
239      EdgeIt (Invalid i) : Edge(i) { }
240      EdgeIt() : Edge() { }
241    };
242   
243    class OutEdgeIt : public Edge {
244      friend class SmartGraph;
245    public:
246      OutEdgeIt() : Edge() { }
247      OutEdgeIt (Invalid i) : Edge(i) { }
248
249      OutEdgeIt(const SmartGraph& G,const Node v)
250        : Edge(G.nodes[v.n].first_out) {}
251    };
252   
253    class InEdgeIt : public Edge {
254      friend class SmartGraph;
255    public:
256      InEdgeIt() : Edge() { }
257      InEdgeIt (Invalid i) : Edge(i) { }
258      InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
259    };
260
261    // Map types
262
263    template <typename T>
264    class NodeMap {
265      const SmartGraph& G;
266      std::vector<T> container;
267    public:
268      typedef T ValueType;
269      typedef Node KeyType;
270      NodeMap(const SmartGraph& _G) : G(_G), container(G.maxNodeId()) { }
271      NodeMap(const SmartGraph& _G, T a) :
272        G(_G), container(G.maxNodeId(), a) { }
273      void set(Node n, T a) { container[n.n]=a; }
274      T get(Node n) const { return container[n.n]; }
275      T& operator[](Node n) { return container[n.n]; }
276      const T& operator[](Node n) const { return container[n.n]; }
277      void update() { container.resize(G.maxNodeId()); }
278      void update(T a) { container.resize(G.maxNodeId(), a); }
279    };
280
281    template <typename T>
282    class EdgeMap {
283      const SmartGraph& G;
284      std::vector<T> container;
285    public:
286      typedef T ValueType;
287      typedef Edge KeyType;
288      EdgeMap(const SmartGraph& _G) : G(_G), container(G.maxEdgeId()) { }
289      EdgeMap(const SmartGraph& _G, T a) :
290        G(_G), container(G.maxEdgeId(), a) { }
291      void set(Edge e, T a) { container[e.n]=a; }
292      T get(Edge e) const { return container[e.n]; }
293      T& operator[](Edge e) { return container[e.n]; }
294      const T& operator[](Edge e) const { return container[e.n]; }
295      void update() { container.resize(G.maxEdgeId()); }
296      void update(T a) { container.resize(G.maxEdgeId(), a); }
297    };
298
299    template <typename T> class DynNodeMap : public DynMapBase<Node>
300    {
301      std::vector<T> container;
302
303    public:
304      typedef T ValueType;
305      typedef Node KeyType;
306
307      DynNodeMap(const SmartGraph &_G) :
308        DynMapBase<Node>(_G), container(_G.maxNodeId())
309      {
310        //FIXME: What if there are empty Id's?
311        //FIXME: Can I use 'this' in a constructor?
312        G->dyn_node_maps.push_back(this);
313      }
314      ~DynNodeMap()
315      {
316        if(G) {
317          std::vector<DynMapBase<Node>* >::iterator i;
318          for(i=G->dyn_node_maps.begin();
319              i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
320          //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
321          //A better way to do that: (Is this really important?)
322          if(*i==this) {
323            *i=G->dyn_node_maps.back();
324            G->dyn_node_maps.pop_back();
325          }
326        }
327      }
328
329      void add(const Node k)
330      {
331        if(k.n>=container.size()) container.resize(k.n+1);
332      }
333//       void erase(const Node k)
334//       {
335//      //FIXME: Please implement me.
336//       }
337//       void erase(const Edge k)
338//       {
339//      //FIXME: Please implement me.
340//       }
341     
342      void set(Node n, T a) { container[n.n]=a; }
343      T get(Node n) const { return container[n.n]; }
344      T& operator[](Node n) { return container[n.n]; }
345      const T& operator[](Node n) const { return container[n.n]; }
346
347      void update() {}    //Useless for DynMaps
348      void update(T a) {}  //Useless for DynMaps
349    };
350   
351    template <typename T> class DynEdgeMap : public DynMapBase<Edge>
352    {
353      std::vector<T> container;
354
355    public:
356      typedef T ValueType;
357      typedef Edge KeyType;
358
359      DynEdgeMap(const SmartGraph &_G) :
360        DynMapBase<Edge>(_G), container(_G.maxEdgeId())
361      {
362        //FIXME: What if there are empty Id's?
363        //FIXME: Can I use 'this' in a constructor?
364        G->dyn_edge_maps.push_back(this);
365      }
366      ~DynEdgeMap()
367      {
368        if(G) {
369          std::vector<DynMapBase<Edge>* >::iterator i;
370          for(i=G->dyn_edge_maps.begin();
371              i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
372          //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
373          //A better way to do that: (Is this really important?)
374          if(*i==this) {
375            *i=G->dyn_edge_maps.back();
376            G->dyn_edge_maps.pop_back();
377          }
378        }
379      }
380     
381      void add(const Edge k)
382      {
383        if(k.n>=int(container.size())) container.resize(k.n+1);
384      }
385      void erase(const Edge k)
386      {
387        //FIXME: Please implement me.
388      }
389     
390      void set(Edge n, T a) { container[n.n]=a; }
391      T get(Edge n) const { return container[n.n]; }
392      T& operator[](Edge n) { return container[n.n]; }
393      const T& operator[](Edge n) const { return container[n.n]; }
394
395      void update() {}    //Useless for DynMaps
396      void update(T a) {}  //Useless for DynMaps
397    };
398       
399  };
400} //namespace hugo
401
402
403
404
405#endif //SMART_GRAPH_H
Note: See TracBrowser for help on using the repository browser.