COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/leda/leda_graph_wrapper.h @ 446:77ef5c7a57d9

Last change on this file since 446:77ef5c7a57d9 was 446:77ef5c7a57d9, checked in by marci, 17 years ago

comparison for matchings with leda

File size: 9.9 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    public: //FIXME
67      Node(leda_node __n) : _n(__n) { }
68    public:
69      /// @warning The default constructor sets the iterator
70      /// to an undefined value.
71      Node() {}   //FIXME
72      /// Initialize the iterator to be invalid
73      Node(Invalid) : _n(0) { }
74      //Node(const Node &) {}
75      bool operator==(Node n) const { return _n==n._n; } //FIXME
76      bool operator!=(Node n) const { return _n!=n._n; } //FIXME
77      operator leda_node () { return _n; }
78    };
79   
80    /// This iterator goes through each node.
81    class NodeIt : public Node {
82    public:
83      /// @warning The default constructor sets the iterator
84      /// to an undefined value.
85      NodeIt() {} //FIXME
86      /// Initialize the iterator to be invalid
87      NodeIt(Invalid i) : Node(i) {}
88      /// Sets the iterator to the first node of \c G.
89      NodeIt(const LedaGraphWrapper &G) : Node(G._graph->first_node()) { }
90      //NodeIt(const NodeIt &) {} //FIXME
91    };
92   
93    /// The base type of the edge iterators.
94    class Edge {
95      friend class LedaGraphWrapper;
96    protected:
97      template <typename T> friend class EdgeMap;
98      leda_edge _e;
99    public: //FIXME
100      Edge(leda_edge __e) : _e(__e) { }
101    public:
102      /// @warning The default constructor sets the iterator
103      /// to an undefined value.
104      Edge() {}   //FIXME
105      /// Initialize the iterator to be invalid
106      Edge(Invalid) : _e(0) {}
107      //Edge(const Edge &) {}
108      bool operator==(Edge e) const { return _e==e._e; } //FIXME
109      bool operator!=(Edge e) const { return _e!=e._e; } //FIXME
110      operator leda_edge () { return _e; }
111    };
112   
113    /// This iterator goes trought the outgoing edges of a certain graph.
114   
115    class OutEdgeIt : public Edge {
116    public:
117      /// @warning The default constructor sets the iterator
118      /// to an undefined value.
119      OutEdgeIt() {}
120      /// Initialize the iterator to be invalid
121      OutEdgeIt(Invalid i) : Edge(i) {}
122      /// This constructor sets the iterator to first outgoing edge.
123   
124      /// This constructor set the iterator to the first outgoing edge of
125      /// node
126      ///@param n the node
127      ///@param G the graph
128      OutEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G._graph->first_adj_edge(n._n)) { }
129    };
130
131    class InEdgeIt : public Edge {
132    public:
133      /// @warning The default constructor sets the iterator
134      /// to an undefined value.
135      InEdgeIt() {}
136      /// Initialize the iterator to be invalid
137      InEdgeIt(Invalid i) : Edge(i) {}
138      InEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G._graph->first_in_edge(n._n)) { }
139    };
140
141    //  class SymEdgeIt : public Edge {};
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._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._n=_graph->succ_node(i._n);
183      return i;
184    }
185    /// Go to the next incoming edge.
186    InEdgeIt &next(InEdgeIt &i) const {
187      i._e=_graph->in_succ(i._e);
188      return i;
189    }
190    /// Go to the next outgoing edge.
191    OutEdgeIt &next(OutEdgeIt &i) const {
192      i._e=_graph->adj_succ(i._e);
193      return i;
194    }
195    //SymEdgeIt &next(SymEdgeIt &) const {}
196    /// Go to the next edge.
197    EdgeIt &next(EdgeIt &i) const {     
198      i._e=_graph->succ_edge(i._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(_graph->target(e._e));
219    }
220    ///Gives back the tail node of an edge.
221    Node tail(Edge e) const {
222      return Node(_graph->source(e._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._n; }
235    /// Checks if an edge iterator is valid
236    bool valid(Edge e) const { return e._e; }
237
238    ///Gives back the \e id of a node.
239    int id(Node n) const { return n._n->id(); }
240    ///Gives back the \e id of an edge.
241    int id(Edge e) const { return e._e->id(); }
242
243    //void setInvalid(Node &) const {};
244    //void setInvalid(Edge &) const {};
245 
246    Node addNode() const { return Node(_graph->new_node()); }
247    Edge addEdge(Node tail, Node head) const {
248      return Edge(_graph->new_edge(tail._n, head._n));
249    }
250   
251    void erase(Node n) const { _graph->del_node(n._n); }
252    void erase(Edge e) const { _graph->del_edge(e._e); }
253
254    void clear() const { _graph->clear(); }
255
256    int nodeNum() const { return _graph->number_of_nodes(); }
257    int edgeNum() const { return _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._graph)) {}
268      NodeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G._graph), t) {}
269
270      void set(Node i, T t) { leda_stuff[i._n]=t; }
271      T get(Node i) const { return leda_stuff[i._n]; }  //FIXME: Is it necessary
272      T &operator[](Node i) { return leda_stuff[i._n]; }
273      const T &operator[](Node i) const { return leda_stuff[i._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._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._graph)) {}
288      EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G._graph), t) {}
289
290      void set(Edge i, T t) { leda_stuff[i._e]=t; }
291      T get(Edge i) const { return leda_stuff[i._e]; }  //FIXME: Is it necessary
292      T &operator[](Edge i) { return leda_stuff[i._e]; }
293      const T &operator[](Edge i) const { return leda_stuff[i._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._graph)*/, a); }   //FIXME: Is it necessary
297    };
298
299  };
300
301  // @}
302
303} //namespace hugo
304
305
306
307// class EmptyBipGraph : public EmptyGraph
308// {
309//   class ANode {};
310//   class BNode {};
311
312//   ANode &next(ANode &) {}
313//   BNode &next(BNode &) {}
314
315//   ANode &getFirst(ANode &) const {}
316//   BNode &getFirst(BNode &) const {}
317
318//   enum NodeClass { A = 0, B = 1 };
319//   NodeClass getClass(Node n) {}
320
321// }
322
323#endif // HUGO_LEDA_GRAPH_WRAPPER_H
Note: See TracBrowser for help on using the repository browser.