1 // -*- c++ -*- |
|
2 #ifndef LEMON_LEDA_GRAPH_WRAPPER_H |
|
3 #define LEMON_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 <lemon/invalid.h> |
|
18 |
|
19 namespace lemon { |
|
20 |
|
21 /// \brief A graph wrapper structure for wrapping LEDA graphs in LEMON. |
|
22 /// |
|
23 /// This graph wrapper class wraps LEDA graphs and LEDA parametrized graphs |
|
24 /// to satisfy LEMON graph concepts. |
|
25 /// Then the generic LEMON 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 /// Constructor for wrapping LEDA graphs. |
|
38 LedaGraphWrapper(Graph& _l_graph) : l_graph(&_l_graph) { } |
|
39 /// Copy constructor |
|
40 LedaGraphWrapper(const LedaGraphWrapper &g) : l_graph(g.l_graph) { } |
|
41 |
|
42 template <typename T> class NodeMap; |
|
43 template <typename T> class EdgeMap; |
|
44 template <typename T> class NodeMapWrapper; |
|
45 template <typename T> class EdgeMapWrapper; |
|
46 |
|
47 class Node; |
|
48 class NodeIt; |
|
49 class Edge; |
|
50 class EdgeIt; |
|
51 class OutEdgeIt; |
|
52 class InEdgeIt; |
|
53 |
|
54 /// Trivial node-iterator |
|
55 class Node { |
|
56 friend class LedaGraphWrapper<Graph>; |
|
57 //friend class Edge; |
|
58 friend class EdgeIt; |
|
59 friend class InEdgeIt; |
|
60 friend class OutEdgeIt; |
|
61 protected: |
|
62 template <typename T> friend class NodeMap; |
|
63 leda_node l_n; |
|
64 public: //FIXME |
|
65 Node(leda_node _l_n) : l_n(_l_n) { } |
|
66 public: |
|
67 /// @warning The default constructor sets the iterator |
|
68 /// to an undefined value. |
|
69 Node() { } //FIXME |
|
70 /// Initialize the iterator to be invalid |
|
71 Node(Invalid) : l_n(0) { } |
|
72 //Node(const Node &) {} |
|
73 bool operator==(Node n) const { return l_n==n.l_n; } //FIXME |
|
74 bool operator!=(Node n) const { return l_n!=n.l_n; } //FIXME |
|
75 operator leda_node () { return l_n; } |
|
76 }; |
|
77 |
|
78 /// This iterator goes through each node. |
|
79 class NodeIt : public Node { |
|
80 public: |
|
81 /// @warning The default constructor sets the iterator |
|
82 /// to an undefined value. |
|
83 NodeIt() { } //FIXME |
|
84 /// Initialize the iterator to be invalid |
|
85 NodeIt(Invalid i) : Node(i) { } |
|
86 /// Sets the iterator to the first node of \c G. |
|
87 NodeIt(const LedaGraphWrapper &G) : Node(G.l_graph->first_node()) { } |
|
88 //NodeIt(const NodeIt &) {} //FIXME |
|
89 }; |
|
90 |
|
91 /// Trivial edge-iterator. |
|
92 class Edge { |
|
93 friend class LedaGraphWrapper; |
|
94 protected: |
|
95 template <typename T> friend class EdgeMap; |
|
96 leda_edge l_e; |
|
97 public: //FIXME |
|
98 Edge(leda_edge _l_e) : l_e(_l_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) : l_e(0) { } |
|
105 //Edge(const Edge &) {} |
|
106 bool operator==(Edge e) const { return l_e==e.l_e; } //FIXME |
|
107 bool operator!=(Edge e) const { return l_e!=e.l_e; } //FIXME |
|
108 operator leda_edge () { return l_e; } |
|
109 }; |
|
110 |
|
111 /// This iterator goes trought the outgoing edges of a certain node. |
|
112 class OutEdgeIt : public Edge { |
|
113 public: |
|
114 /// @warning The default constructor sets the iterator |
|
115 /// to an undefined value. |
|
116 OutEdgeIt() { } |
|
117 /// Initialize the iterator to be invalid |
|
118 OutEdgeIt(Invalid i) : Edge(i) { } |
|
119 /// This constructor sets the iterator to first outgoing edge. |
|
120 |
|
121 /// This constructor set the iterator to the first outgoing edge of |
|
122 /// node |
|
123 ///@param n the node |
|
124 ///@param G the graph |
|
125 OutEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G.l_graph->first_adj_edge(n.l_n)) { } |
|
126 }; |
|
127 |
|
128 /// This iterator goes trought the incoming edges of a certain node. |
|
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.l_graph->first_in_edge(n.l_n)) { } |
|
137 }; |
|
138 |
|
139 // class SymEdgeIt : public Edge {}; |
|
140 |
|
141 /// This iterator goes trought the edges of the graph. |
|
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.l_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.l_n=l_graph->succ_node(i.l_n); |
|
183 return i; |
|
184 } |
|
185 /// Go to the next incoming edge. |
|
186 InEdgeIt &next(InEdgeIt &i) const { |
|
187 i.l_e=l_graph->in_succ(i.l_e); |
|
188 return i; |
|
189 } |
|
190 /// Go to the next outgoing edge. |
|
191 OutEdgeIt &next(OutEdgeIt &i) const { |
|
192 i.l_e=l_graph->adj_succ(i.l_e); |
|
193 return i; |
|
194 } |
|
195 //SymEdgeIt &next(SymEdgeIt &) const {} |
|
196 /// Go to the next edge. |
|
197 EdgeIt &next(EdgeIt &i) const { |
|
198 i.l_e=l_graph->succ_edge(i.l_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 target node of an edge. |
|
217 Node target(Edge e) const { |
|
218 return Node(l_graph->target(e.l_e)); |
|
219 } |
|
220 ///Gives back the source node of an edge. |
|
221 Node source(Edge e) const { |
|
222 return Node(l_graph->source(e.l_e)); |
|
223 } |
|
224 |
|
225 Node aNode(InEdgeIt e) const { return target(e); } |
|
226 Node aNode(OutEdgeIt e) const { return source(e); } |
|
227 // Node aNode(SymEdgeIt) const {} |
|
228 |
|
229 Node bNode(InEdgeIt e) const { return source(e); } |
|
230 Node bNode(OutEdgeIt e) const { return target(e); } |
|
231 // Node bNode(SymEdgeIt) const {} |
|
232 |
|
233 /// Checks if a node iterator is valid |
|
234 bool valid(Node n) const { return n.l_n; } |
|
235 /// Checks if an edge iterator is valid |
|
236 bool valid(Edge e) const { return e.l_e; } |
|
237 |
|
238 ///Gives back the \e id of a node. |
|
239 int id(Node n) const { return n.l_n->id(); } |
|
240 ///Gives back the \e id of an edge. |
|
241 int id(Edge e) const { return e.l_e->id(); } |
|
242 |
|
243 //void setInvalid(Node &) const {}; |
|
244 //void setInvalid(Edge &) const {}; |
|
245 |
|
246 Node addNode() const { return Node(l_graph->new_node()); } |
|
247 Edge addEdge(Node source, Node target) const { |
|
248 return Edge(l_graph->new_edge(source.l_n, target.l_n)); |
|
249 } |
|
250 |
|
251 void erase(Node n) const { l_graph->del_node(n.l_n); } |
|
252 void erase(Edge e) const { l_graph->del_edge(e.l_e); } |
|
253 |
|
254 void clear() const { l_graph->clear(); } |
|
255 |
|
256 int nodeNum() const { return l_graph->number_of_nodes(); } |
|
257 int edgeNum() const { return l_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 Value; |
|
265 typedef Node Key; |
|
266 |
|
267 NodeMap(const LedaGraphWrapper &G) : leda_stuff(*(G.l_graph)) {} |
|
268 NodeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {} |
|
269 |
|
270 void set(Node i, T t) { leda_stuff[i.l_n]=t; } |
|
271 T get(Node i) const { return leda_stuff[i.l_n]; } //FIXME: Is it necessary |
|
272 T &operator[](Node i) { return leda_stuff[i.l_n]; } |
|
273 const T &operator[](Node i) const { return leda_stuff[i.l_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.l_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 Value; |
|
285 typedef Edge Key; |
|
286 |
|
287 EdgeMap(const LedaGraphWrapper &G) : leda_stuff(*(G.l_graph)) {} |
|
288 EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {} |
|
289 |
|
290 void set(Edge i, T t) { leda_stuff[i.l_e]=t; } |
|
291 T get(Edge i) const { return leda_stuff[i.l_e]; } //FIXME: Is it necessary |
|
292 T &operator[](Edge i) { return leda_stuff[i.l_e]; } |
|
293 const T &operator[](Edge i) const { return leda_stuff[i.l_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.l_graph)*/, a); } //FIXME: Is it necessary |
|
297 }; |
|
298 |
|
299 |
|
300 /// This class is to wrap existing |
|
301 /// LEDA node-maps to LEMON ones. |
|
302 template<typename T> class NodeMapWrapper |
|
303 { |
|
304 leda_node_array<T>* leda_stuff; |
|
305 public: |
|
306 typedef T Value; |
|
307 typedef Node Key; |
|
308 |
|
309 NodeMapWrapper(leda_node_array<T>& _leda_stuff) : |
|
310 leda_stuff(&_leda_stuff) { } |
|
311 //NodeMap(leda_node_map& &G, T t) : leda_stuff(*(G.l_graph), t) {} |
|
312 |
|
313 void set(Node i, T t) { (*leda_stuff)[i.l_n]=t; } |
|
314 //T get(Node i) const { return (*leda_stuff)[i.l_n]; } //FIXME: Is it necessary |
|
315 T &operator[](Node i) { return (*leda_stuff)[i.l_n]; } |
|
316 const T &operator[](Node i) const { return (*leda_stuff)[i.l_n]; } |
|
317 |
|
318 void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ } |
|
319 //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); } //FIXME: Is it necessary |
|
320 }; |
|
321 |
|
322 /// This class is to wrap existing |
|
323 /// LEDA edge-maps to LEMON ones. |
|
324 template<typename T> class EdgeMapWrapper |
|
325 { |
|
326 leda_edge_array<T>* leda_stuff; |
|
327 public: |
|
328 typedef T Value; |
|
329 typedef Edge Key; |
|
330 |
|
331 EdgeMapWrapper(leda_edge_array<T>& _leda_stuff) : |
|
332 leda_stuff(_leda_stuff) { } |
|
333 //EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {} |
|
334 |
|
335 void set(Edge i, T t) { (*leda_stuff)[i.l_e]=t; } |
|
336 //T get(Edge i) const { return (*leda_stuff)[i.l_e]; } //FIXME: Is it necessary |
|
337 T &operator[](Edge i) { return (*leda_stuff)[i.l_e]; } |
|
338 const T &operator[](Edge i) const { return (*leda_stuff)[i.l_e]; } |
|
339 |
|
340 void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ } |
|
341 //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); } //FIXME: Is it necessary |
|
342 }; |
|
343 |
|
344 /// This class is used for access node-data of |
|
345 /// LEDA parametrized graphs. |
|
346 template<typename T> |
|
347 class NodeDataMap : public NodeMapWrapper<T> |
|
348 { |
|
349 public: |
|
350 NodeDataMap(LedaGraphWrapper<Graph>& LGW) : |
|
351 NodeMapWrapper<T>(*(LGW._g_graph).node_data()) { } |
|
352 }; |
|
353 |
|
354 /// This class is used for access edge-data of |
|
355 /// LEDA parametrized graphs. |
|
356 template<typename T> |
|
357 class EdgeDataMap : public EdgeMapWrapper<T> |
|
358 { |
|
359 public: |
|
360 EdgeDataMap(LedaGraphWrapper<Graph>& LGW) : |
|
361 EdgeMapWrapper<T>(*(LGW._g_graph).edge_data()) { } |
|
362 }; |
|
363 |
|
364 }; |
|
365 |
|
366 |
|
367 /// \brief LEDA graph template. |
|
368 /// |
|
369 /// This graph stucture uses LEDA graphs for physical storage. |
|
370 /// \ingroup graphs |
|
371 template<typename Graph> |
|
372 class LedaGraph : public LedaGraphWrapper<Graph> { |
|
373 typedef LedaGraphWrapper<Graph> Parent; |
|
374 protected: |
|
375 Graph gr; |
|
376 public: |
|
377 LedaGraph() { |
|
378 Parent::setGraph(gr); |
|
379 } |
|
380 }; |
|
381 |
|
382 } //namespace lemon |
|
383 |
|
384 #endif // LEMON_LEDA_GRAPH_WRAPPER_H |
|