COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/leda/leda_graph_wrapper.h @ 419:69e961722628

Last change on this file since 419:69e961722628 was 419:69e961722628, checked in by marci, 20 years ago

comparison with leda algorithms, wrapper for leda graphs

File size: 9.8 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    /// The base type of the node iterators.
57    class Node {
58      friend class LedaGraphWrapper;
59      //friend class Edge;
60      friend class EdgeIt;
61      friend class InEdgeIt;
62      friend class OutEdgeIt;
63    protected:
64      template <typename T> friend class NodeMap;
65      leda_node _n;
66      Node(leda_node __n) : _n(__n) { }
67    public:
68      /// @warning The default constructor sets the iterator
69      /// to an undefined value.
70      Node() {}   //FIXME
71      /// Initialize the iterator to be invalid
72      Node(Invalid) : _n(0) { }
73      //Node(const Node &) {}
74      bool operator==(Node n) const { return _n==n._n; } //FIXME
75      bool operator!=(Node n) const { return _n!=n._n; } //FIXME
76      operator leda_node () { return _n; }
77    };
78   
79    /// This iterator goes through each node.
80    class NodeIt : public Node {
81    public:
82      /// @warning The default constructor sets the iterator
83      /// to an undefined value.
84      NodeIt() {} //FIXME
85      /// Initialize the iterator to be invalid
86      NodeIt(Invalid i) : Node(i) {}
87      /// Sets the iterator to the first node of \c G.
88      NodeIt(const LedaGraphWrapper &G) : Node(G._graph->first_node()) { }
89      //NodeIt(const NodeIt &) {} //FIXME
90    };
91   
92    /// The base type of the edge iterators.
93    class Edge {
94      friend class LedaGraphWrapper;
95    protected:
96      template <typename T> friend class EdgeMap;
97      leda_edge _e;
98      Edge(leda_edge __e) : _e(__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) : _e(0) {}
105      //Edge(const Edge &) {}
106      bool operator==(Edge e) const { return _e==e._e; } //FIXME
107      bool operator!=(Edge e) const { return _e!=e._e; } //FIXME
108      operator leda_edge () { return _e; }
109    };
110   
111    /// This iterator goes trought the outgoing edges of a certain graph.
112   
113    class OutEdgeIt : public Edge {
114    public:
115      /// @warning The default constructor sets the iterator
116      /// to an undefined value.
117      OutEdgeIt() {}
118      /// Initialize the iterator to be invalid
119      OutEdgeIt(Invalid i) : Edge(i) {}
120      /// This constructor sets the iterator to first outgoing edge.
121   
122      /// This constructor set the iterator to the first outgoing edge of
123      /// node
124      ///@param n the node
125      ///@param G the graph
126      OutEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G._graph->first_adj_edge(n._n)) { }
127    };
128
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._graph->first_in_edge(n._n)) { }
137    };
138
139    //  class SymEdgeIt : public Edge {};
140    class EdgeIt : public Edge {
141    public:
142      /// @warning The default constructor sets the iterator
143      /// to an undefined value.
144      EdgeIt() {}
145      /// Initialize the iterator to be invalid
146      EdgeIt(Invalid i) : Edge(i) {}
147      EdgeIt(const LedaGraphWrapper & G) : Edge(G._graph->first_edge()) { }
148    };
149
150    /// First node of the graph.
151
152    /// \post \c i and the return value will be the first node.
153    ///
154    NodeIt &first(NodeIt &i) const { i=NodeIt(*this); return i; }
155
156    /// The first outgoing edge.
157    InEdgeIt &first(InEdgeIt &i, Node n) const {
158      i=InEdgeIt(*this, n);
159      return i;
160    }
161    /// The first incoming edge.
162    OutEdgeIt &first(OutEdgeIt &i, Node n) const {
163      i=OutEdgeIt(*this, n);
164      return i;
165    }
166    //  SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
167    /// The first edge of the Graph.
168    EdgeIt &first(EdgeIt &i) const {     
169      i=EdgeIt(*this);
170      return i; }
171
172//     Node getNext(Node) const {}
173//     InEdgeIt getNext(InEdgeIt) const {}
174//     OutEdgeIt getNext(OutEdgeIt) const {}
175//     //SymEdgeIt getNext(SymEdgeIt) const {}
176//     EdgeIt getNext(EdgeIt) const {}
177
178    /// Go to the next node.
179    NodeIt &next(NodeIt &i) const {
180      i._n=_graph->succ_node(i._n);
181      return i;
182    }
183    /// Go to the next incoming edge.
184    InEdgeIt &next(InEdgeIt &i) const {
185      i._e=_graph->in_succ(i._e);
186      return i;
187    }
188    /// Go to the next outgoing edge.
189    OutEdgeIt &next(OutEdgeIt &i) const {
190      i._e=_graph->adj_succ(i._e);
191      return i;
192    }
193    //SymEdgeIt &next(SymEdgeIt &) const {}
194    /// Go to the next edge.
195    EdgeIt &next(EdgeIt &i) const {     
196      i._e=_graph->succ_edge(i._e);
197      return i;
198    }
199
200//     template< typename It >
201//     It first() const {
202//       It e;
203//       first(e);
204//       return e;
205//     }
206
207//     template< typename It >
208//     It first(Node v) const {
209//       It e;
210//       first(e, v);
211//       return e;
212//     }
213
214    ///Gives back the head node of an edge.
215    Node head(Edge e) const {
216      return Node(_graph->target(e._e));
217    }
218    ///Gives back the tail node of an edge.
219    Node tail(Edge e) const {
220      return Node(_graph->source(e._e));
221    }
222 
223    Node aNode(InEdgeIt e) const { return head(e); }
224    Node aNode(OutEdgeIt e) const { return tail(e); }
225    //   Node aNode(SymEdgeIt) const {}
226
227    Node bNode(InEdgeIt e) const { return tail(e); }
228    Node bNode(OutEdgeIt e) const { return head(e); }
229    //   Node bNode(SymEdgeIt) const {}
230
231    /// Checks if a node iterator is valid
232    bool valid(Node n) const { return n._n; }
233    /// Checks if an edge iterator is valid
234    bool valid(Edge e) const { return e._e; }
235
236    ///Gives back the \e id of a node.
237    int id(Node n) const { return n._n->id(); }
238    ///Gives back the \e id of an edge.
239    int id(Edge e) const { return e._e->id(); }
240
241    //void setInvalid(Node &) const {};
242    //void setInvalid(Edge &) const {};
243 
244    Node addNode() const { return Node(_graph->new_node()); }
245    Edge addEdge(Node tail, Node head) const {
246      return Edge(_graph->new_edge(tail._n, head._n));
247    }
248   
249    void erase(Node n) const { _graph->del_node(n._n); }
250    void erase(Edge e) const { _graph->del_edge(e._e); }
251
252    void clear() const { _graph->clear(); }
253
254    int nodeNum() const { return _graph->number_of_nodes(); }
255    int edgeNum() const { return _graph->number_of_edges(); }
256
257    ///Read/write map from the nodes to type \c T.
258    template<typename T> class NodeMap
259    {
260      leda_node_map<T> leda_stuff;
261    public:
262      typedef T ValueType;
263      typedef Node KeyType;
264
265      NodeMap(const LedaGraphWrapper &G) : leda_stuff(*(G._graph)) {}
266      NodeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G._graph), t) {}
267
268      void set(Node i, T t) { leda_stuff[i._n]=t; }
269      T get(Node i) const { return leda_stuff[i._n]; }  //FIXME: Is it necessary
270      T &operator[](Node i) { return leda_stuff[i._n]; }
271      const T &operator[](Node i) const { return leda_stuff[i._n]; }
272
273      void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
274      //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G._graph)*/, a); }   //FIXME: Is it necessary
275    };
276
277    ///Read/write map from the edges to type \c T.
278    template<typename T> class EdgeMap
279    {
280      leda_edge_map<T> leda_stuff;
281    public:
282      typedef T ValueType;
283      typedef Edge KeyType;
284
285      EdgeMap(const LedaGraphWrapper &G) : leda_stuff(*(G._graph)) {}
286      EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G._graph), t) {}
287
288      void set(Edge i, T t) { leda_stuff[i._e]=t; }
289      T get(Edge i) const { return leda_stuff[i._e]; }  //FIXME: Is it necessary
290      T &operator[](Edge i) { return leda_stuff[i._e]; }
291      const T &operator[](Edge i) const { return leda_stuff[i._e]; }
292
293      void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
294      //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G._graph)*/, a); }   //FIXME: Is it necessary
295    };
296
297  };
298
299  // @}
300
301} //namespace hugo
302
303
304
305// class EmptyBipGraph : public EmptyGraph
306// {
307//   class ANode {};
308//   class BNode {};
309
310//   ANode &next(ANode &) {}
311//   BNode &next(BNode &) {}
312
313//   ANode &getFirst(ANode &) const {}
314//   BNode &getFirst(BNode &) const {}
315
316//   enum NodeClass { A = 0, B = 1 };
317//   NodeClass getClass(Node n) {}
318
319// }
320
321#endif // HUGO_LEDA_GRAPH_WRAPPER_H
Note: See TracBrowser for help on using the repository browser.