marci@189
|
1 |
// -*- c++ -*-
|
marci@189
|
2 |
#ifndef HUGO_LEDA_GRAPH_WRAPPER_H
|
marci@189
|
3 |
#define HUGO_LEDA_GRAPH_WRAPPER_H
|
marci@189
|
4 |
|
marci@189
|
5 |
#include <LEDA/graph.h>
|
marci@189
|
6 |
#include <LEDA/node_array.h>
|
marci@189
|
7 |
#include <LEDA/edge_array.h>
|
marci@189
|
8 |
#include <LEDA/node_map.h>
|
marci@189
|
9 |
#include <LEDA/edge_map.h>
|
marci@189
|
10 |
//#include <LEDA/graph_alg.h>
|
marci@189
|
11 |
//#include <LEDA/dimacs.h>
|
marci@189
|
12 |
|
marci@189
|
13 |
//#if defined(LEDA_NAMESPACE)
|
marci@189
|
14 |
//using namespace leda;
|
marci@189
|
15 |
//#endif
|
marci@189
|
16 |
|
marci@616
|
17 |
#include <hugo/invalid.h>
|
marci@189
|
18 |
|
marci@189
|
19 |
namespace hugo {
|
marci@189
|
20 |
|
marci@617
|
21 |
/// \brief A graph wrapper structure for wrapping LEDA graphs in HUGO.
|
marci@617
|
22 |
///
|
marci@617
|
23 |
/// This graph wrapper class wraps LEDA graphs and LEDA parametrized graphs
|
marci@617
|
24 |
/// to satisfy HUGO graph concepts.
|
marci@617
|
25 |
/// Then the generic HUGOlib algorithms and wrappers can be used
|
marci@409
|
26 |
/// with LEDA graphs.
|
marci@617
|
27 |
/// \ingroup gwrapper
|
marci@189
|
28 |
template<typename Graph>
|
marci@189
|
29 |
class LedaGraphWrapper
|
marci@189
|
30 |
{
|
marci@473
|
31 |
protected:
|
marci@617
|
32 |
Graph* l_graph;
|
marci@617
|
33 |
LedaGraphWrapper() : l_graph(0) { }
|
marci@617
|
34 |
void setGraph(Graph& _l_graph) { l_graph=&_l_graph; }
|
marci@189
|
35 |
public:
|
marci@189
|
36 |
|
marci@189
|
37 |
//LedaGraphWrapper() { }
|
marci@617
|
38 |
LedaGraphWrapper(Graph& _l_graph) : l_graph(&_l_graph) { }
|
marci@617
|
39 |
LedaGraphWrapper(const LedaGraphWrapper &G) : l_graph(G.l_graph) { }
|
marci@189
|
40 |
|
marci@189
|
41 |
template <typename T> class NodeMap;
|
marci@189
|
42 |
template <typename T> class EdgeMap;
|
marci@646
|
43 |
template <typename T> class NodeMapWrapper;
|
marci@646
|
44 |
template <typename T> class EdgeMapWrapper;
|
marci@189
|
45 |
|
marci@461
|
46 |
class Node;
|
marci@461
|
47 |
class NodeIt;
|
marci@461
|
48 |
class Edge;
|
marci@461
|
49 |
class EdgeIt;
|
marci@461
|
50 |
class OutEdgeIt;
|
marci@461
|
51 |
class InEdgeIt;
|
marci@461
|
52 |
|
marci@189
|
53 |
/// The base type of the node iterators.
|
marci@189
|
54 |
class Node {
|
marci@461
|
55 |
friend class LedaGraphWrapper<Graph>;
|
marci@189
|
56 |
//friend class Edge;
|
marci@189
|
57 |
friend class EdgeIt;
|
marci@189
|
58 |
friend class InEdgeIt;
|
marci@189
|
59 |
friend class OutEdgeIt;
|
marci@189
|
60 |
protected:
|
marci@189
|
61 |
template <typename T> friend class NodeMap;
|
marci@617
|
62 |
leda_node l_n;
|
marci@446
|
63 |
public: //FIXME
|
marci@617
|
64 |
Node(leda_node _l_n) : l_n(_l_n) { }
|
marci@189
|
65 |
public:
|
marci@189
|
66 |
/// @warning The default constructor sets the iterator
|
marci@189
|
67 |
/// to an undefined value.
|
marci@189
|
68 |
Node() {} //FIXME
|
marci@189
|
69 |
/// Initialize the iterator to be invalid
|
marci@617
|
70 |
Node(Invalid) : l_n(0) { }
|
marci@189
|
71 |
//Node(const Node &) {}
|
marci@617
|
72 |
bool operator==(Node n) const { return l_n==n.l_n; } //FIXME
|
marci@617
|
73 |
bool operator!=(Node n) const { return l_n!=n.l_n; } //FIXME
|
marci@617
|
74 |
operator leda_node () { return l_n; }
|
marci@189
|
75 |
};
|
marci@189
|
76 |
|
marci@189
|
77 |
/// This iterator goes through each node.
|
marci@189
|
78 |
class NodeIt : public Node {
|
marci@189
|
79 |
public:
|
marci@189
|
80 |
/// @warning The default constructor sets the iterator
|
marci@189
|
81 |
/// to an undefined value.
|
marci@189
|
82 |
NodeIt() {} //FIXME
|
marci@189
|
83 |
/// Initialize the iterator to be invalid
|
marci@189
|
84 |
NodeIt(Invalid i) : Node(i) {}
|
marci@189
|
85 |
/// Sets the iterator to the first node of \c G.
|
marci@617
|
86 |
NodeIt(const LedaGraphWrapper &G) : Node(G.l_graph->first_node()) { }
|
marci@189
|
87 |
//NodeIt(const NodeIt &) {} //FIXME
|
marci@189
|
88 |
};
|
marci@189
|
89 |
|
marci@189
|
90 |
/// The base type of the edge iterators.
|
marci@189
|
91 |
class Edge {
|
marci@189
|
92 |
friend class LedaGraphWrapper;
|
marci@189
|
93 |
protected:
|
marci@189
|
94 |
template <typename T> friend class EdgeMap;
|
marci@617
|
95 |
leda_edge l_e;
|
marci@446
|
96 |
public: //FIXME
|
marci@617
|
97 |
Edge(leda_edge _l_e) : l_e(_l_e) { }
|
marci@189
|
98 |
public:
|
marci@189
|
99 |
/// @warning The default constructor sets the iterator
|
marci@189
|
100 |
/// to an undefined value.
|
marci@189
|
101 |
Edge() {} //FIXME
|
marci@189
|
102 |
/// Initialize the iterator to be invalid
|
marci@617
|
103 |
Edge(Invalid) : l_e(0) {}
|
marci@189
|
104 |
//Edge(const Edge &) {}
|
marci@617
|
105 |
bool operator==(Edge e) const { return l_e==e.l_e; } //FIXME
|
marci@617
|
106 |
bool operator!=(Edge e) const { return l_e!=e.l_e; } //FIXME
|
marci@617
|
107 |
operator leda_edge () { return l_e; }
|
marci@189
|
108 |
};
|
marci@189
|
109 |
|
marci@189
|
110 |
/// This iterator goes trought the outgoing edges of a certain graph.
|
marci@189
|
111 |
|
marci@189
|
112 |
class OutEdgeIt : public Edge {
|
marci@189
|
113 |
public:
|
marci@189
|
114 |
/// @warning The default constructor sets the iterator
|
marci@189
|
115 |
/// to an undefined value.
|
marci@189
|
116 |
OutEdgeIt() {}
|
marci@189
|
117 |
/// Initialize the iterator to be invalid
|
marci@189
|
118 |
OutEdgeIt(Invalid i) : Edge(i) {}
|
marci@189
|
119 |
/// This constructor sets the iterator to first outgoing edge.
|
marci@189
|
120 |
|
marci@189
|
121 |
/// This constructor set the iterator to the first outgoing edge of
|
marci@189
|
122 |
/// node
|
marci@189
|
123 |
///@param n the node
|
marci@189
|
124 |
///@param G the graph
|
marci@617
|
125 |
OutEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G.l_graph->first_adj_edge(n.l_n)) { }
|
marci@189
|
126 |
};
|
marci@189
|
127 |
|
marci@189
|
128 |
class InEdgeIt : public Edge {
|
marci@189
|
129 |
public:
|
marci@189
|
130 |
/// @warning The default constructor sets the iterator
|
marci@189
|
131 |
/// to an undefined value.
|
marci@189
|
132 |
InEdgeIt() {}
|
marci@189
|
133 |
/// Initialize the iterator to be invalid
|
marci@189
|
134 |
InEdgeIt(Invalid i) : Edge(i) {}
|
marci@617
|
135 |
InEdgeIt(const LedaGraphWrapper & G, Node n) : Edge(G.l_graph->first_in_edge(n.l_n)) { }
|
marci@189
|
136 |
};
|
marci@189
|
137 |
|
marci@189
|
138 |
// class SymEdgeIt : public Edge {};
|
marci@189
|
139 |
class EdgeIt : public Edge {
|
marci@189
|
140 |
public:
|
marci@189
|
141 |
/// @warning The default constructor sets the iterator
|
marci@189
|
142 |
/// to an undefined value.
|
marci@189
|
143 |
EdgeIt() {}
|
marci@189
|
144 |
/// Initialize the iterator to be invalid
|
marci@189
|
145 |
EdgeIt(Invalid i) : Edge(i) {}
|
marci@617
|
146 |
EdgeIt(const LedaGraphWrapper & G) : Edge(G.l_graph->first_edge()) { }
|
marci@189
|
147 |
};
|
marci@189
|
148 |
|
marci@189
|
149 |
/// First node of the graph.
|
marci@189
|
150 |
|
marci@189
|
151 |
/// \post \c i and the return value will be the first node.
|
marci@189
|
152 |
///
|
marci@189
|
153 |
NodeIt &first(NodeIt &i) const { i=NodeIt(*this); return i; }
|
marci@189
|
154 |
|
marci@189
|
155 |
/// The first outgoing edge.
|
marci@189
|
156 |
InEdgeIt &first(InEdgeIt &i, Node n) const {
|
marci@189
|
157 |
i=InEdgeIt(*this, n);
|
marci@189
|
158 |
return i;
|
marci@189
|
159 |
}
|
marci@189
|
160 |
/// The first incoming edge.
|
marci@189
|
161 |
OutEdgeIt &first(OutEdgeIt &i, Node n) const {
|
marci@189
|
162 |
i=OutEdgeIt(*this, n);
|
marci@189
|
163 |
return i;
|
marci@189
|
164 |
}
|
marci@189
|
165 |
// SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
|
marci@189
|
166 |
/// The first edge of the Graph.
|
marci@189
|
167 |
EdgeIt &first(EdgeIt &i) const {
|
marci@189
|
168 |
i=EdgeIt(*this);
|
marci@189
|
169 |
return i; }
|
marci@189
|
170 |
|
marci@189
|
171 |
// Node getNext(Node) const {}
|
marci@189
|
172 |
// InEdgeIt getNext(InEdgeIt) const {}
|
marci@189
|
173 |
// OutEdgeIt getNext(OutEdgeIt) const {}
|
marci@189
|
174 |
// //SymEdgeIt getNext(SymEdgeIt) const {}
|
marci@189
|
175 |
// EdgeIt getNext(EdgeIt) const {}
|
marci@189
|
176 |
|
marci@189
|
177 |
/// Go to the next node.
|
marci@189
|
178 |
NodeIt &next(NodeIt &i) const {
|
marci@617
|
179 |
i.l_n=l_graph->succ_node(i.l_n);
|
marci@189
|
180 |
return i;
|
marci@189
|
181 |
}
|
marci@189
|
182 |
/// Go to the next incoming edge.
|
marci@189
|
183 |
InEdgeIt &next(InEdgeIt &i) const {
|
marci@617
|
184 |
i.l_e=l_graph->in_succ(i.l_e);
|
marci@189
|
185 |
return i;
|
marci@189
|
186 |
}
|
marci@189
|
187 |
/// Go to the next outgoing edge.
|
marci@189
|
188 |
OutEdgeIt &next(OutEdgeIt &i) const {
|
marci@617
|
189 |
i.l_e=l_graph->adj_succ(i.l_e);
|
marci@189
|
190 |
return i;
|
marci@189
|
191 |
}
|
marci@189
|
192 |
//SymEdgeIt &next(SymEdgeIt &) const {}
|
marci@189
|
193 |
/// Go to the next edge.
|
marci@189
|
194 |
EdgeIt &next(EdgeIt &i) const {
|
marci@617
|
195 |
i.l_e=l_graph->succ_edge(i.l_e);
|
marci@189
|
196 |
return i;
|
marci@189
|
197 |
}
|
marci@189
|
198 |
|
marci@409
|
199 |
// template< typename It >
|
marci@409
|
200 |
// It first() const {
|
marci@409
|
201 |
// It e;
|
marci@409
|
202 |
// first(e);
|
marci@409
|
203 |
// return e;
|
marci@409
|
204 |
// }
|
marci@189
|
205 |
|
marci@409
|
206 |
// template< typename It >
|
marci@409
|
207 |
// It first(Node v) const {
|
marci@409
|
208 |
// It e;
|
marci@409
|
209 |
// first(e, v);
|
marci@409
|
210 |
// return e;
|
marci@409
|
211 |
// }
|
marci@189
|
212 |
|
marci@189
|
213 |
///Gives back the head node of an edge.
|
marci@189
|
214 |
Node head(Edge e) const {
|
marci@617
|
215 |
return Node(l_graph->target(e.l_e));
|
marci@189
|
216 |
}
|
marci@189
|
217 |
///Gives back the tail node of an edge.
|
marci@189
|
218 |
Node tail(Edge e) const {
|
marci@617
|
219 |
return Node(l_graph->source(e.l_e));
|
marci@189
|
220 |
}
|
marci@189
|
221 |
|
marci@189
|
222 |
Node aNode(InEdgeIt e) const { return head(e); }
|
marci@189
|
223 |
Node aNode(OutEdgeIt e) const { return tail(e); }
|
marci@189
|
224 |
// Node aNode(SymEdgeIt) const {}
|
marci@189
|
225 |
|
marci@189
|
226 |
Node bNode(InEdgeIt e) const { return tail(e); }
|
marci@189
|
227 |
Node bNode(OutEdgeIt e) const { return head(e); }
|
marci@189
|
228 |
// Node bNode(SymEdgeIt) const {}
|
marci@189
|
229 |
|
marci@189
|
230 |
/// Checks if a node iterator is valid
|
marci@617
|
231 |
bool valid(Node n) const { return n.l_n; }
|
marci@189
|
232 |
/// Checks if an edge iterator is valid
|
marci@617
|
233 |
bool valid(Edge e) const { return e.l_e; }
|
marci@189
|
234 |
|
marci@189
|
235 |
///Gives back the \e id of a node.
|
marci@617
|
236 |
int id(Node n) const { return n.l_n->id(); }
|
marci@189
|
237 |
///Gives back the \e id of an edge.
|
marci@617
|
238 |
int id(Edge e) const { return e.l_e->id(); }
|
marci@189
|
239 |
|
marci@189
|
240 |
//void setInvalid(Node &) const {};
|
marci@189
|
241 |
//void setInvalid(Edge &) const {};
|
marci@189
|
242 |
|
marci@617
|
243 |
Node addNode() const { return Node(l_graph->new_node()); }
|
marci@189
|
244 |
Edge addEdge(Node tail, Node head) const {
|
marci@617
|
245 |
return Edge(l_graph->new_edge(tail.l_n, head.l_n));
|
marci@189
|
246 |
}
|
marci@189
|
247 |
|
marci@617
|
248 |
void erase(Node n) const { l_graph->del_node(n.l_n); }
|
marci@617
|
249 |
void erase(Edge e) const { l_graph->del_edge(e.l_e); }
|
marci@189
|
250 |
|
marci@617
|
251 |
void clear() const { l_graph->clear(); }
|
marci@189
|
252 |
|
marci@617
|
253 |
int nodeNum() const { return l_graph->number_of_nodes(); }
|
marci@617
|
254 |
int edgeNum() const { return l_graph->number_of_edges(); }
|
marci@189
|
255 |
|
marci@189
|
256 |
///Read/write map from the nodes to type \c T.
|
marci@189
|
257 |
template<typename T> class NodeMap
|
marci@189
|
258 |
{
|
marci@189
|
259 |
leda_node_map<T> leda_stuff;
|
marci@189
|
260 |
public:
|
marci@189
|
261 |
typedef T ValueType;
|
marci@189
|
262 |
typedef Node KeyType;
|
marci@189
|
263 |
|
marci@617
|
264 |
NodeMap(const LedaGraphWrapper &G) : leda_stuff(*(G.l_graph)) {}
|
marci@617
|
265 |
NodeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}
|
marci@189
|
266 |
|
marci@617
|
267 |
void set(Node i, T t) { leda_stuff[i.l_n]=t; }
|
marci@617
|
268 |
T get(Node i) const { return leda_stuff[i.l_n]; } //FIXME: Is it necessary
|
marci@617
|
269 |
T &operator[](Node i) { return leda_stuff[i.l_n]; }
|
marci@617
|
270 |
const T &operator[](Node i) const { return leda_stuff[i.l_n]; }
|
marci@189
|
271 |
|
marci@189
|
272 |
void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
|
marci@617
|
273 |
//void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); } //FIXME: Is it necessary
|
marci@189
|
274 |
};
|
marci@189
|
275 |
|
marci@189
|
276 |
///Read/write map from the edges to type \c T.
|
marci@189
|
277 |
template<typename T> class EdgeMap
|
marci@189
|
278 |
{
|
marci@189
|
279 |
leda_edge_map<T> leda_stuff;
|
marci@189
|
280 |
public:
|
marci@189
|
281 |
typedef T ValueType;
|
marci@189
|
282 |
typedef Edge KeyType;
|
marci@189
|
283 |
|
marci@617
|
284 |
EdgeMap(const LedaGraphWrapper &G) : leda_stuff(*(G.l_graph)) {}
|
marci@617
|
285 |
EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}
|
marci@189
|
286 |
|
marci@617
|
287 |
void set(Edge i, T t) { leda_stuff[i.l_e]=t; }
|
marci@617
|
288 |
T get(Edge i) const { return leda_stuff[i.l_e]; } //FIXME: Is it necessary
|
marci@617
|
289 |
T &operator[](Edge i) { return leda_stuff[i.l_e]; }
|
marci@617
|
290 |
const T &operator[](Edge i) const { return leda_stuff[i.l_e]; }
|
marci@189
|
291 |
|
marci@189
|
292 |
void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
|
marci@617
|
293 |
//void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); } //FIXME: Is it necessary
|
marci@189
|
294 |
};
|
marci@189
|
295 |
|
marci@646
|
296 |
|
marci@646
|
297 |
///Read/write map from the nodes to type \c T.
|
marci@646
|
298 |
template<typename T> class NodeMapWrapper
|
marci@646
|
299 |
{
|
marci@646
|
300 |
leda_node_map<T>* leda_stuff;
|
marci@646
|
301 |
public:
|
marci@646
|
302 |
typedef T ValueType;
|
marci@646
|
303 |
typedef Node KeyType;
|
marci@646
|
304 |
|
marci@646
|
305 |
NodeMapWrapper(leda_node_map<T>& _leda_stuff) :
|
marci@646
|
306 |
leda_stuff(&_leda_stuff) { }
|
marci@646
|
307 |
//NodeMap(leda_node_map& &G, T t) : leda_stuff(*(G.l_graph), t) {}
|
marci@646
|
308 |
|
marci@646
|
309 |
void set(Node i, T t) { (*leda_stuff)[i.l_n]=t; }
|
marci@646
|
310 |
T get(Node i) const { return (*leda_stuff)[i.l_n]; } //FIXME: Is it necessary
|
marci@646
|
311 |
T &operator[](Node i) { return (*leda_stuff)[i.l_n]; }
|
marci@646
|
312 |
const T &operator[](Node i) const { return (*leda_stuff)[i.l_n]; }
|
marci@646
|
313 |
|
marci@646
|
314 |
void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
|
marci@646
|
315 |
//void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); } //FIXME: Is it necessary
|
marci@646
|
316 |
};
|
marci@646
|
317 |
|
marci@646
|
318 |
///Read/write map from the edges to type \c T.
|
marci@646
|
319 |
template<typename T> class EdgeMapWrapper
|
marci@646
|
320 |
{
|
marci@646
|
321 |
leda_edge_map<T>* leda_stuff;
|
marci@646
|
322 |
public:
|
marci@646
|
323 |
typedef T ValueType;
|
marci@646
|
324 |
typedef Edge KeyType;
|
marci@646
|
325 |
|
marci@646
|
326 |
EdgeMapWrapper(leda_edge_map<T>& _leda_stuff) :
|
marci@646
|
327 |
leda_stuff(_leda_stuff) { }
|
marci@646
|
328 |
//EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}
|
marci@646
|
329 |
|
marci@646
|
330 |
void set(Edge i, T t) { (*leda_stuff)[i.l_e]=t; }
|
marci@646
|
331 |
T get(Edge i) const { return (*leda_stuff)[i.l_e]; } //FIXME: Is it necessary
|
marci@646
|
332 |
T &operator[](Edge i) { return (*leda_stuff)[i.l_e]; }
|
marci@646
|
333 |
const T &operator[](Edge i) const { return (*leda_stuff)[i.l_e]; }
|
marci@646
|
334 |
|
marci@646
|
335 |
void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
|
marci@646
|
336 |
//void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); } //FIXME: Is it necessary
|
marci@646
|
337 |
};
|
marci@646
|
338 |
|
marci@189
|
339 |
};
|
marci@189
|
340 |
|
marci@617
|
341 |
|
marci@617
|
342 |
/// \brief LEDA graph template.
|
marci@617
|
343 |
///
|
marci@617
|
344 |
/// This graph stucture uses LEDA graphs for physical storage.
|
marci@617
|
345 |
/// \ingroup graphs
|
marci@473
|
346 |
template<typename Graph>
|
marci@473
|
347 |
class LedaGraph : public LedaGraphWrapper<Graph> {
|
marci@473
|
348 |
typedef LedaGraphWrapper<Graph> Parent;
|
marci@473
|
349 |
protected:
|
marci@473
|
350 |
Graph gr;
|
marci@473
|
351 |
public:
|
marci@473
|
352 |
LedaGraph() {
|
marci@473
|
353 |
Parent::setGraph(gr);
|
marci@473
|
354 |
}
|
marci@473
|
355 |
};
|
marci@473
|
356 |
|
marci@189
|
357 |
} //namespace hugo
|
marci@189
|
358 |
|
marci@189
|
359 |
#endif // HUGO_LEDA_GRAPH_WRAPPER_H
|