COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/leda/leda_graph_wrapper.h @ 461:a11ddf8a6614

Last change on this file since 461:a11ddf8a6614 was 461:a11ddf8a6614, checked in by marci, 17 years ago

bug ellen

File size: 10.0 KB
Line 
1// -*- c++ -*-
2#ifndef HUGO_LEDA_GRAPH_WRAPPER_H
3#define HUGO_LEDA_GRAPH_WRAPPER_H
4
5#include <LEDA/graph.h>
6#include <LEDA/node_array.h>
7#include <LEDA/edge_array.h>
8#include <LEDA/node_map.h>
9#include <LEDA/edge_map.h>
10//#include <LEDA/graph_alg.h>
11//#include <LEDA/dimacs.h>
12
13//#if defined(LEDA_NAMESPACE)
14//using namespace leda;
15//#endif
16
17#include <invalid.h>
18
19/// The namespace of HugoLib
20namespace hugo {
21
22  // @defgroup empty_graph The LedaGraphWrapper class
23  // @{
24
25  /// A graph wrapperstructure for wrapping LEDA graphs in HUGO.
26 
27  /// This graph wrapper class wraps LEDA graph and LEDA parametrized graph
28  /// and then the generic algorithms and wrappers of HUGO can be used
29  /// with LEDA graphs.
30  /// This class provides all the common features of a grapf structure,
31  /// however completely without implementations or real data structures
32  /// behind the interface.
33  /// All graph algorithms should compile with this class, but it will not
34  /// run properly, of course.
35  ///
36  /// It can be used for checking the interface compatibility,
37  /// or it can serve as a skeleton of a new graph structure.
38  ///
39  /// Also, you will find here the full documentation of a certain graph
40  /// feature, the documentation of a real graph imlementation
41  /// like @ref ListGraph or
42  /// @ref SmartGraph will just refer to this structure.
43  template<typename Graph>
44  class LedaGraphWrapper
45  {
46    Graph* _graph;
47  public:
48   
49        //LedaGraphWrapper() { }
50    LedaGraphWrapper(Graph& __graph) : _graph(&__graph) { }
51    LedaGraphWrapper(const LedaGraphWrapper &G) : _graph(G._graph) { }
52
53    template <typename T> class NodeMap;
54    template <typename T> class EdgeMap;
55
56    class Node;
57    class NodeIt;
58    class Edge;
59    class EdgeIt;
60    class OutEdgeIt;
61    class InEdgeIt;
62
63    /// The base type of the node iterators.
64    class Node {
65      friend class LedaGraphWrapper<Graph>;
66      //friend class Edge;
67      friend class EdgeIt;
68      friend class InEdgeIt;
69      friend class OutEdgeIt;
70    protected:
71      template <typename T> friend class NodeMap;
72      leda_node _n;
73    public: //FIXME
74      Node(leda_node __n) : _n(__n) { }
75    public:
76      /// @warning The default constructor sets the iterator
77      /// to an undefined value.
78      Node() {}   //FIXME
79      /// Initialize the iterator to be invalid
80      Node(Invalid) : _n(0) { }
81      //Node(const Node &) {}
82      bool operator==(Node n) const { return _n==n._n; } //FIXME
83      bool operator!=(Node n) const { return _n!=n._n; } //FIXME
84      operator leda_node () { return _n; }
85    };
86   
87    /// This iterator goes through each node.
88    class NodeIt : public Node {
89    public:
90      /// @warning The default constructor sets the iterator
91      /// to an undefined value.
92      NodeIt() {} //FIXME
93      /// Initialize the iterator to be invalid
94      NodeIt(Invalid i) : Node(i) {}
95      /// Sets the iterator to the first node of \c G.
96      NodeIt(const LedaGraphWrapper &G) : Node(G._graph->first_node()) { }
97      //NodeIt(const NodeIt &) {} //FIXME
98    };
99   
100    /// The base type of the edge iterators.
101    class Edge {
102      friend class LedaGraphWrapper;
103    protected:
104      template <typename T> friend class EdgeMap;
105      leda_edge _e;
106    public: //FIXME
107      Edge(leda_edge __e) : _e(__e) { }
108    public:
109      /// @warning The default constructor sets the iterator
110      /// to an undefined value.
111      Edge() {}   //FIXME
112      /// Initialize the iterator to be invalid
113      Edge(Invalid) : _e(0) {}
114      //Edge(const Edge &) {}
115      bool operator==(Edge e) const { return _e==e._e; } //FIXME
116      bool operator!=(Edge e) const { return _e!=e._e; } //FIXME
117      operator leda_edge () { return _e; }
118    };
119   
120    /// This iterator goes trought the outgoing edges of a certain graph.
121   
122    class OutEdgeIt : public Edge {
123    public:
124      /// @warning The default constructor sets the iterator
125      /// to an undefined value.
126      OutEdgeIt() {}
127      /// Initialize the iterator to be invalid
128      OutEdgeIt(Invalid i) : Edge(i) {}
129      /// This constructor sets the iterator to first outgoing edge.
130   
131      /// This constructor set the iterator to the first outgoing edge of
132      /// node
133      ///@param n the node
134      ///@param G the graph
135      OutEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G._graph->first_adj_edge(n._n)) { }
136    };
137
138    class InEdgeIt : public Edge {
139    public:
140      /// @warning The default constructor sets the iterator
141      /// to an undefined value.
142      InEdgeIt() {}
143      /// Initialize the iterator to be invalid
144      InEdgeIt(Invalid i) : Edge(i) {}
145      InEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G._graph->first_in_edge(n._n)) { }
146    };
147
148    //  class SymEdgeIt : public Edge {};
149    class EdgeIt : public Edge {
150    public:
151      /// @warning The default constructor sets the iterator
152      /// to an undefined value.
153      EdgeIt() {}
154      /// Initialize the iterator to be invalid
155      EdgeIt(Invalid i) : Edge(i) {}
156      EdgeIt(const LedaGraphWrapper & G) : Edge(G._graph->first_edge()) { }
157    };
158
159    /// First node of the graph.
160
161    /// \post \c i and the return value will be the first node.
162    ///
163    NodeIt &first(NodeIt &i) const { i=NodeIt(*this); return i; }
164
165    /// The first outgoing edge.
166    InEdgeIt &first(InEdgeIt &i, Node n) const {
167      i=InEdgeIt(*this, n);
168      return i;
169    }
170    /// The first incoming edge.
171    OutEdgeIt &first(OutEdgeIt &i, Node n) const {
172      i=OutEdgeIt(*this, n);
173      return i;
174    }
175    //  SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
176    /// The first edge of the Graph.
177    EdgeIt &first(EdgeIt &i) const {     
178      i=EdgeIt(*this);
179      return i; }
180
181//     Node getNext(Node) const {}
182//     InEdgeIt getNext(InEdgeIt) const {}
183//     OutEdgeIt getNext(OutEdgeIt) const {}
184//     //SymEdgeIt getNext(SymEdgeIt) const {}
185//     EdgeIt getNext(EdgeIt) const {}
186
187    /// Go to the next node.
188    NodeIt &next(NodeIt &i) const {
189      i._n=_graph->succ_node(i._n);
190      return i;
191    }
192    /// Go to the next incoming edge.
193    InEdgeIt &next(InEdgeIt &i) const {
194      i._e=_graph->in_succ(i._e);
195      return i;
196    }
197    /// Go to the next outgoing edge.
198    OutEdgeIt &next(OutEdgeIt &i) const {
199      i._e=_graph->adj_succ(i._e);
200      return i;
201    }
202    //SymEdgeIt &next(SymEdgeIt &) const {}
203    /// Go to the next edge.
204    EdgeIt &next(EdgeIt &i) const {     
205      i._e=_graph->succ_edge(i._e);
206      return i;
207    }
208
209//     template< typename It >
210//     It first() const {
211//       It e;
212//       first(e);
213//       return e;
214//     }
215
216//     template< typename It >
217//     It first(Node v) const {
218//       It e;
219//       first(e, v);
220//       return e;
221//     }
222
223    ///Gives back the head node of an edge.
224    Node head(Edge e) const {
225      return Node(_graph->target(e._e));
226    }
227    ///Gives back the tail node of an edge.
228    Node tail(Edge e) const {
229      return Node(_graph->source(e._e));
230    }
231 
232    Node aNode(InEdgeIt e) const { return head(e); }
233    Node aNode(OutEdgeIt e) const { return tail(e); }
234    //   Node aNode(SymEdgeIt) const {}
235
236    Node bNode(InEdgeIt e) const { return tail(e); }
237    Node bNode(OutEdgeIt e) const { return head(e); }
238    //   Node bNode(SymEdgeIt) const {}
239
240    /// Checks if a node iterator is valid
241    bool valid(Node n) const { return n._n; }
242    /// Checks if an edge iterator is valid
243    bool valid(Edge e) const { return e._e; }
244
245    ///Gives back the \e id of a node.
246    int id(Node n) const { return n._n->id(); }
247    ///Gives back the \e id of an edge.
248    int id(Edge e) const { return e._e->id(); }
249
250    //void setInvalid(Node &) const {};
251    //void setInvalid(Edge &) const {};
252 
253    Node addNode() const { return Node(_graph->new_node()); }
254    Edge addEdge(Node tail, Node head) const {
255      return Edge(_graph->new_edge(tail._n, head._n));
256    }
257   
258    void erase(Node n) const { _graph->del_node(n._n); }
259    void erase(Edge e) const { _graph->del_edge(e._e); }
260
261    void clear() const { _graph->clear(); }
262
263    int nodeNum() const { return _graph->number_of_nodes(); }
264    int edgeNum() const { return _graph->number_of_edges(); }
265
266    ///Read/write map from the nodes to type \c T.
267    template<typename T> class NodeMap
268    {
269      leda_node_map<T> leda_stuff;
270    public:
271      typedef T ValueType;
272      typedef Node KeyType;
273
274      NodeMap(const LedaGraphWrapper &G) : leda_stuff(*(G._graph)) {}
275      NodeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G._graph), t) {}
276
277      void set(Node i, T t) { leda_stuff[i._n]=t; }
278      T get(Node i) const { return leda_stuff[i._n]; }  //FIXME: Is it necessary
279      T &operator[](Node i) { return leda_stuff[i._n]; }
280      const T &operator[](Node i) const { return leda_stuff[i._n]; }
281
282      void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
283      //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G._graph)*/, a); }   //FIXME: Is it necessary
284    };
285
286    ///Read/write map from the edges to type \c T.
287    template<typename T> class EdgeMap
288    {
289      leda_edge_map<T> leda_stuff;
290    public:
291      typedef T ValueType;
292      typedef Edge KeyType;
293
294      EdgeMap(const LedaGraphWrapper &G) : leda_stuff(*(G._graph)) {}
295      EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G._graph), t) {}
296
297      void set(Edge i, T t) { leda_stuff[i._e]=t; }
298      T get(Edge i) const { return leda_stuff[i._e]; }  //FIXME: Is it necessary
299      T &operator[](Edge i) { return leda_stuff[i._e]; }
300      const T &operator[](Edge i) const { return leda_stuff[i._e]; }
301
302      void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
303      //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G._graph)*/, a); }   //FIXME: Is it necessary
304    };
305
306  };
307
308  // @}
309
310} //namespace hugo
311
312
313
314// class EmptyBipGraph : public EmptyGraph
315// {
316//   class ANode {};
317//   class BNode {};
318
319//   ANode &next(ANode &) {}
320//   BNode &next(BNode &) {}
321
322//   ANode &getFirst(ANode &) const {}
323//   BNode &getFirst(BNode &) const {}
324
325//   enum NodeClass { A = 0, B = 1 };
326//   NodeClass getClass(Node n) {}
327
328// }
329
330#endif // HUGO_LEDA_GRAPH_WRAPPER_H
Note: See TracBrowser for help on using the repository browser.