COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/leda/leda_graph_wrapper.h @ 617:dc17013b0e52

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

bip matching comparison

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 <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
44    class Node;
45    class NodeIt;
46    class Edge;
47    class EdgeIt;
48    class OutEdgeIt;
49    class InEdgeIt;
50
51    /// The base type of the node iterators.
52    class Node {
53      friend class LedaGraphWrapper<Graph>;
54      //friend class Edge;
55      friend class EdgeIt;
56      friend class InEdgeIt;
57      friend class OutEdgeIt;
58    protected:
59      template <typename T> friend class NodeMap;
60      leda_node l_n;
61    public: //FIXME
62      Node(leda_node _l_n) : l_n(_l_n) { }
63    public:
64      /// @warning The default constructor sets the iterator
65      /// to an undefined value.
66      Node() {}   //FIXME
67      /// Initialize the iterator to be invalid
68      Node(Invalid) : l_n(0) { }
69      //Node(const Node &) {}
70      bool operator==(Node n) const { return l_n==n.l_n; } //FIXME
71      bool operator!=(Node n) const { return l_n!=n.l_n; } //FIXME
72      operator leda_node () { return l_n; }
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.l_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 l_e;
94    public: //FIXME
95      Edge(leda_edge _l_e) : l_e(_l_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) : l_e(0) {}
102      //Edge(const Edge &) {}
103      bool operator==(Edge e) const { return l_e==e.l_e; } //FIXME
104      bool operator!=(Edge e) const { return l_e!=e.l_e; } //FIXME
105      operator leda_edge () { return l_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.l_graph->first_adj_edge(n.l_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.l_graph->first_in_edge(n.l_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.l_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.l_n=l_graph->succ_node(i.l_n);
178      return i;
179    }
180    /// Go to the next incoming edge.
181    InEdgeIt &next(InEdgeIt &i) const {
182      i.l_e=l_graph->in_succ(i.l_e);
183      return i;
184    }
185    /// Go to the next outgoing edge.
186    OutEdgeIt &next(OutEdgeIt &i) const {
187      i.l_e=l_graph->adj_succ(i.l_e);
188      return i;
189    }
190    //SymEdgeIt &next(SymEdgeIt &) const {}
191    /// Go to the next edge.
192    EdgeIt &next(EdgeIt &i) const {     
193      i.l_e=l_graph->succ_edge(i.l_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(l_graph->target(e.l_e));
214    }
215    ///Gives back the tail node of an edge.
216    Node tail(Edge e) const {
217      return Node(l_graph->source(e.l_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.l_n; }
230    /// Checks if an edge iterator is valid
231    bool valid(Edge e) const { return e.l_e; }
232
233    ///Gives back the \e id of a node.
234    int id(Node n) const { return n.l_n->id(); }
235    ///Gives back the \e id of an edge.
236    int id(Edge e) const { return e.l_e->id(); }
237
238    //void setInvalid(Node &) const {};
239    //void setInvalid(Edge &) const {};
240 
241    Node addNode() const { return Node(l_graph->new_node()); }
242    Edge addEdge(Node tail, Node head) const {
243      return Edge(l_graph->new_edge(tail.l_n, head.l_n));
244    }
245   
246    void erase(Node n) const { l_graph->del_node(n.l_n); }
247    void erase(Edge e) const { l_graph->del_edge(e.l_e); }
248
249    void clear() const { l_graph->clear(); }
250
251    int nodeNum() const { return l_graph->number_of_nodes(); }
252    int edgeNum() const { return l_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.l_graph)) {}
263      NodeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}
264
265      void set(Node i, T t) { leda_stuff[i.l_n]=t; }
266      T get(Node i) const { return leda_stuff[i.l_n]; }  //FIXME: Is it necessary
267      T &operator[](Node i) { return leda_stuff[i.l_n]; }
268      const T &operator[](Node i) const { return leda_stuff[i.l_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.l_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.l_graph)) {}
283      EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}
284
285      void set(Edge i, T t) { leda_stuff[i.l_e]=t; }
286      T get(Edge i) const { return leda_stuff[i.l_e]; }  //FIXME: Is it necessary
287      T &operator[](Edge i) { return leda_stuff[i.l_e]; }
288      const T &operator[](Edge i) const { return leda_stuff[i.l_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.l_graph)*/, a); }   //FIXME: Is it necessary
292    };
293
294  };
295
296
297  /// \brief LEDA graph template.
298  ///
299  /// This graph stucture uses LEDA graphs for physical storage.
300  /// \ingroup graphs
301  template<typename Graph>
302  class LedaGraph : public LedaGraphWrapper<Graph> {
303    typedef LedaGraphWrapper<Graph> Parent;
304  protected:
305    Graph gr;
306  public:
307    LedaGraph() {
308      Parent::setGraph(gr);
309    }
310  };
311
312} //namespace hugo
313
314#endif // HUGO_LEDA_GRAPH_WRAPPER_H
Note: See TracBrowser for help on using the repository browser.