COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/leda/leda_graph_wrapper.h @ 769:eb61fbc64c16

Last change on this file since 769:eb61fbc64c16 was 650:588ff2ca55bd, checked in by marci, 20 years ago

a

File size: 12.1 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 <hugo/invalid.h>
18
19namespace hugo {
20
21  /// \brief A graph wrapper structure for wrapping LEDA graphs in HUGO.
22  ///
23  /// This graph wrapper class wraps LEDA graphs and LEDA parametrized graphs
24  /// to satisfy HUGO graph concepts.
25  /// Then the generic HUGOlib algorithms and wrappers can be used
26  /// with LEDA graphs.
27  /// \ingroup gwrapper
28  template<typename Graph>
29  class LedaGraphWrapper
30  {
31  protected:
32    Graph* l_graph;
33    LedaGraphWrapper() : l_graph(0) { }
34    void setGraph(Graph& _l_graph) { l_graph=&_l_graph; }
35  public:
36
37    /// Constructor for wrapping LEDA graphs.
38    LedaGraphWrapper(Graph& _l_graph) : l_graph(&_l_graph) { }
39    /// Copy constructor
40    LedaGraphWrapper(const LedaGraphWrapper &g) : l_graph(g.l_graph) { }
41
42    template <typename T> class NodeMap;
43    template <typename T> class EdgeMap;
44    template <typename T> class NodeMapWrapper;
45    template <typename T> class EdgeMapWrapper;
46
47    class Node;
48    class NodeIt;
49    class Edge;
50    class EdgeIt;
51    class OutEdgeIt;
52    class InEdgeIt;
53
54    /// Trivial node-iterator
55    class Node {
56      friend class LedaGraphWrapper<Graph>;
57      //friend class Edge;
58      friend class EdgeIt;
59      friend class InEdgeIt;
60      friend class OutEdgeIt;
61    protected:
62      template <typename T> friend class NodeMap;
63      leda_node l_n;
64    public: //FIXME
65      Node(leda_node _l_n) : l_n(_l_n) { }
66    public:
67      /// @warning The default constructor sets the iterator
68      /// to an undefined value.
69      Node() { }   //FIXME
70      /// Initialize the iterator to be invalid
71      Node(Invalid) : l_n(0) { }
72      //Node(const Node &) {}
73      bool operator==(Node n) const { return l_n==n.l_n; } //FIXME
74      bool operator!=(Node n) const { return l_n!=n.l_n; } //FIXME
75      operator leda_node () { return l_n; }
76    };
77   
78    /// This iterator goes through each node.
79    class NodeIt : public Node {
80    public:
81      /// @warning The default constructor sets the iterator
82      /// to an undefined value.
83      NodeIt() { } //FIXME
84      /// Initialize the iterator to be invalid
85      NodeIt(Invalid i) : Node(i) { }
86      /// Sets the iterator to the first node of \c G.
87      NodeIt(const LedaGraphWrapper &G) : Node(G.l_graph->first_node()) { }
88      //NodeIt(const NodeIt &) {} //FIXME
89    };
90   
91    /// Trivial edge-iterator.
92    class Edge {
93      friend class LedaGraphWrapper;
94    protected:
95      template <typename T> friend class EdgeMap;
96      leda_edge l_e;
97    public: //FIXME
98      Edge(leda_edge _l_e) : l_e(_l_e) { }
99    public:
100      /// @warning The default constructor sets the iterator
101      /// to an undefined value.
102      Edge() { }   //FIXME
103      /// Initialize the iterator to be invalid
104      Edge(Invalid) : l_e(0) { }
105      //Edge(const Edge &) {}
106      bool operator==(Edge e) const { return l_e==e.l_e; } //FIXME
107      bool operator!=(Edge e) const { return l_e!=e.l_e; } //FIXME
108      operator leda_edge () { return l_e; }
109    };
110   
111    /// This iterator goes trought the outgoing edges of a certain node.
112    class OutEdgeIt : public Edge {
113    public:
114      /// @warning The default constructor sets the iterator
115      /// to an undefined value.
116      OutEdgeIt() { }
117      /// Initialize the iterator to be invalid
118      OutEdgeIt(Invalid i) : Edge(i) { }
119      /// This constructor sets the iterator to first outgoing edge.
120   
121      /// This constructor set the iterator to the first outgoing edge of
122      /// node
123      ///@param n the node
124      ///@param G the graph
125      OutEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G.l_graph->first_adj_edge(n.l_n)) { }
126    };
127
128    /// This iterator goes trought the incoming edges of a certain node.
129    class InEdgeIt : public Edge {
130    public:
131      /// @warning The default constructor sets the iterator
132      /// to an undefined value.
133      InEdgeIt() { }
134      /// Initialize the iterator to be invalid
135      InEdgeIt(Invalid i) : Edge(i) { }
136      InEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G.l_graph->first_in_edge(n.l_n)) { }
137    };
138
139    //  class SymEdgeIt : public Edge {};
140   
141    /// This iterator goes trought the edges of the graph.
142    class EdgeIt : public Edge {
143    public:
144      /// @warning The default constructor sets the iterator
145      /// to an undefined value.
146      EdgeIt() { }
147      /// Initialize the iterator to be invalid
148      EdgeIt(Invalid i) : Edge(i) { }
149      EdgeIt(const LedaGraphWrapper & G) : Edge(G.l_graph->first_edge()) { }
150    };
151
152    /// First node of the graph.
153    ///
154    /// \post \c i and the return value will be the first node.
155    ///
156    NodeIt &first(NodeIt &i) const { i=NodeIt(*this); return i; }
157
158    /// The first outgoing edge.
159    InEdgeIt &first(InEdgeIt &i, Node n) const {
160      i=InEdgeIt(*this, n);
161      return i;
162    }
163    /// The first incoming edge.
164    OutEdgeIt &first(OutEdgeIt &i, Node n) const {
165      i=OutEdgeIt(*this, n);
166      return i;
167    }
168    //  SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
169    /// The first edge of the graph.
170    EdgeIt &first(EdgeIt &i) const {     
171      i=EdgeIt(*this);
172      return i; }
173
174//     Node getNext(Node) const {}
175//     InEdgeIt getNext(InEdgeIt) const {}
176//     OutEdgeIt getNext(OutEdgeIt) const {}
177//     //SymEdgeIt getNext(SymEdgeIt) const {}
178//     EdgeIt getNext(EdgeIt) const {}
179
180    /// Go to the next node.
181    NodeIt &next(NodeIt &i) const {
182      i.l_n=l_graph->succ_node(i.l_n);
183      return i;
184    }
185    /// Go to the next incoming edge.
186    InEdgeIt &next(InEdgeIt &i) const {
187      i.l_e=l_graph->in_succ(i.l_e);
188      return i;
189    }
190    /// Go to the next outgoing edge.
191    OutEdgeIt &next(OutEdgeIt &i) const {
192      i.l_e=l_graph->adj_succ(i.l_e);
193      return i;
194    }
195    //SymEdgeIt &next(SymEdgeIt &) const {}
196    /// Go to the next edge.
197    EdgeIt &next(EdgeIt &i) const {     
198      i.l_e=l_graph->succ_edge(i.l_e);
199      return i;
200    }
201
202//     template< typename It >
203//     It first() const {
204//       It e;
205//       first(e);
206//       return e;
207//     }
208
209//     template< typename It >
210//     It first(Node v) const {
211//       It e;
212//       first(e, v);
213//       return e;
214//     }
215
216    ///Gives back the head node of an edge.
217    Node head(Edge e) const {
218      return Node(l_graph->target(e.l_e));
219    }
220    ///Gives back the tail node of an edge.
221    Node tail(Edge e) const {
222      return Node(l_graph->source(e.l_e));
223    }
224 
225    Node aNode(InEdgeIt e) const { return head(e); }
226    Node aNode(OutEdgeIt e) const { return tail(e); }
227    //   Node aNode(SymEdgeIt) const {}
228
229    Node bNode(InEdgeIt e) const { return tail(e); }
230    Node bNode(OutEdgeIt e) const { return head(e); }
231    //   Node bNode(SymEdgeIt) const {}
232
233    /// Checks if a node iterator is valid
234    bool valid(Node n) const { return n.l_n; }
235    /// Checks if an edge iterator is valid
236    bool valid(Edge e) const { return e.l_e; }
237
238    ///Gives back the \e id of a node.
239    int id(Node n) const { return n.l_n->id(); }
240    ///Gives back the \e id of an edge.
241    int id(Edge e) const { return e.l_e->id(); }
242
243    //void setInvalid(Node &) const {};
244    //void setInvalid(Edge &) const {};
245 
246    Node addNode() const { return Node(l_graph->new_node()); }
247    Edge addEdge(Node tail, Node head) const {
248      return Edge(l_graph->new_edge(tail.l_n, head.l_n));
249    }
250   
251    void erase(Node n) const { l_graph->del_node(n.l_n); }
252    void erase(Edge e) const { l_graph->del_edge(e.l_e); }
253
254    void clear() const { l_graph->clear(); }
255
256    int nodeNum() const { return l_graph->number_of_nodes(); }
257    int edgeNum() const { return l_graph->number_of_edges(); }
258
259    /// Read/write map from the nodes to type \c T.
260    template<typename T> class NodeMap
261    {
262      leda_node_map<T> leda_stuff;
263    public:
264      typedef T ValueType;
265      typedef Node KeyType;
266
267      NodeMap(const LedaGraphWrapper &G) : leda_stuff(*(G.l_graph)) {}
268      NodeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}
269
270      void set(Node i, T t) { leda_stuff[i.l_n]=t; }
271      T get(Node i) const { return leda_stuff[i.l_n]; }  //FIXME: Is it necessary
272      T &operator[](Node i) { return leda_stuff[i.l_n]; }
273      const T &operator[](Node i) const { return leda_stuff[i.l_n]; }
274
275      void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
276      //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); }   //FIXME: Is it necessary
277    };
278
279    /// Read/write map from the edges to type \c T.
280    template<typename T> class EdgeMap
281    {
282      leda_edge_map<T> leda_stuff;
283    public:
284      typedef T ValueType;
285      typedef Edge KeyType;
286
287      EdgeMap(const LedaGraphWrapper &G) : leda_stuff(*(G.l_graph)) {}
288      EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}
289
290      void set(Edge i, T t) { leda_stuff[i.l_e]=t; }
291      T get(Edge i) const { return leda_stuff[i.l_e]; }  //FIXME: Is it necessary
292      T &operator[](Edge i) { return leda_stuff[i.l_e]; }
293      const T &operator[](Edge i) const { return leda_stuff[i.l_e]; }
294
295      void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
296      //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); }   //FIXME: Is it necessary
297    };
298
299
300    /// This class is to wrap existing
301    /// LEDA node-maps to HUGO ones.
302    template<typename T> class NodeMapWrapper
303    {
304      leda_node_array<T>* leda_stuff;
305    public:
306      typedef T ValueType;
307      typedef Node KeyType;
308
309      NodeMapWrapper(leda_node_array<T>& _leda_stuff) :
310        leda_stuff(&_leda_stuff) { }
311      //NodeMap(leda_node_map& &G, T t) : leda_stuff(*(G.l_graph), t) {}
312
313      void set(Node i, T t) { (*leda_stuff)[i.l_n]=t; }
314      //T get(Node i) const { return (*leda_stuff)[i.l_n]; }  //FIXME: Is it necessary
315      T &operator[](Node i) { return (*leda_stuff)[i.l_n]; }
316      const T &operator[](Node i) const { return (*leda_stuff)[i.l_n]; }
317
318      void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
319      //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); }   //FIXME: Is it necessary
320    };
321
322    /// This class is to wrap existing
323    /// LEDA edge-maps to HUGO ones.
324    template<typename T> class EdgeMapWrapper
325    {
326      leda_edge_array<T>* leda_stuff;
327    public:
328      typedef T ValueType;
329      typedef Edge KeyType;
330
331      EdgeMapWrapper(leda_edge_array<T>& _leda_stuff) :
332        leda_stuff(_leda_stuff) { }
333      //EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}
334
335      void set(Edge i, T t) { (*leda_stuff)[i.l_e]=t; }
336      //T get(Edge i) const { return (*leda_stuff)[i.l_e]; }  //FIXME: Is it necessary
337      T &operator[](Edge i) { return (*leda_stuff)[i.l_e]; }
338      const T &operator[](Edge i) const { return (*leda_stuff)[i.l_e]; }
339
340      void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
341      //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); }   //FIXME: Is it necessary
342    };
343
344    /// This class is used for access node-data of
345    /// LEDA parametrized graphs.
346    template<typename T>
347    class NodeDataMap : public NodeMapWrapper<T>
348    {
349    public:
350      NodeDataMap(LedaGraphWrapper<Graph>& LGW) :
351        NodeMapWrapper<T>(*(LGW._g_graph).node_data()) { }
352    };
353
354    /// This class is used for access edge-data of
355    /// LEDA parametrized graphs.
356    template<typename T>
357    class EdgeDataMap : public EdgeMapWrapper<T>
358    {
359    public:
360      EdgeDataMap(LedaGraphWrapper<Graph>& LGW) :
361        EdgeMapWrapper<T>(*(LGW._g_graph).edge_data()) { }
362    };
363
364  };
365
366
367  /// \brief LEDA graph template.
368  ///
369  /// This graph stucture uses LEDA graphs for physical storage.
370  /// \ingroup graphs
371  template<typename Graph>
372  class LedaGraph : public LedaGraphWrapper<Graph> {
373    typedef LedaGraphWrapper<Graph> Parent;
374  protected:
375    Graph gr;
376  public:
377    LedaGraph() {
378      Parent::setGraph(gr);
379    }
380  };
381
382} //namespace hugo
383
384#endif // HUGO_LEDA_GRAPH_WRAPPER_H
Note: See TracBrowser for help on using the repository browser.