COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/leda_graph_wrapper.h @ 381:d72470496fbe

Last change on this file since 381:d72470496fbe was 198:5cec393baade, checked in by marci, 20 years ago

max cardinality bipartite matching demo, something to play with it

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