COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/leda_graph_wrapper.h @ 189:04becc472709

Last change on this file since 189:04becc472709 was 189:04becc472709, checked in by marci, 20 years ago

LedaGraph? -> LedaGraphWrapper?

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