COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/leda/leda_graph_wrapper.h @ 646:bd7a69231cf8

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

max_flow.h: status flags for actMinCut
leda_graph_wrapper.h: NodeMapWrapper?, EdgeMapWrapper?

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