|
sl@0
|
1 |
//=======================================================================
|
|
sl@0
|
2 |
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
|
|
sl@0
|
3 |
// Copyright 2004 The Trustees of Indiana University.
|
|
sl@0
|
4 |
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Douglas Gregor
|
|
sl@0
|
5 |
//
|
|
sl@0
|
6 |
// Distributed under the Boost Software License, Version 1.0. (See
|
|
sl@0
|
7 |
// accompanying file LICENSE_1_0.txt or copy at
|
|
sl@0
|
8 |
// http://www.boost.org/LICENSE_1_0.txt)
|
|
sl@0
|
9 |
//=======================================================================
|
|
sl@0
|
10 |
#ifndef BOOST_GRAPH_LEDA_HPP
|
|
sl@0
|
11 |
#define BOOST_GRAPH_LEDA_HPP
|
|
sl@0
|
12 |
|
|
sl@0
|
13 |
#include <boost/config.hpp>
|
|
sl@0
|
14 |
#include <boost/iterator/iterator_facade.hpp>
|
|
sl@0
|
15 |
#include <boost/graph/graph_traits.hpp>
|
|
sl@0
|
16 |
#include <boost/graph/properties.hpp>
|
|
sl@0
|
17 |
|
|
sl@0
|
18 |
#include <LEDA/graph.h>
|
|
sl@0
|
19 |
#include <LEDA/node_array.h>
|
|
sl@0
|
20 |
#include <LEDA/node_map.h>
|
|
sl@0
|
21 |
|
|
sl@0
|
22 |
// The functions and classes in this file allows the user to
|
|
sl@0
|
23 |
// treat a LEDA GRAPH object as a boost graph "as is". No
|
|
sl@0
|
24 |
// wrapper is needed for the GRAPH object.
|
|
sl@0
|
25 |
|
|
sl@0
|
26 |
// Remember to define LEDA_PREFIX so that LEDA types such as
|
|
sl@0
|
27 |
// leda_edge show up as "leda_edge" and not just "edge".
|
|
sl@0
|
28 |
|
|
sl@0
|
29 |
// Warning: this implementation relies on partial specialization
|
|
sl@0
|
30 |
// for the graph_traits class (so it won't compile with Visual C++)
|
|
sl@0
|
31 |
|
|
sl@0
|
32 |
// Warning: this implementation is in alpha and has not been tested
|
|
sl@0
|
33 |
|
|
sl@0
|
34 |
#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
|
|
sl@0
|
35 |
namespace boost {
|
|
sl@0
|
36 |
|
|
sl@0
|
37 |
struct leda_graph_traversal_category :
|
|
sl@0
|
38 |
public virtual bidirectional_graph_tag,
|
|
sl@0
|
39 |
public virtual adjacency_graph_tag,
|
|
sl@0
|
40 |
public virtual vertex_list_graph_tag { };
|
|
sl@0
|
41 |
|
|
sl@0
|
42 |
template <class vtype, class etype>
|
|
sl@0
|
43 |
struct graph_traits< leda::GRAPH<vtype,etype> > {
|
|
sl@0
|
44 |
typedef leda_node vertex_descriptor;
|
|
sl@0
|
45 |
typedef leda_edge edge_descriptor;
|
|
sl@0
|
46 |
|
|
sl@0
|
47 |
class adjacency_iterator
|
|
sl@0
|
48 |
: public iterator_facade<adjacency_iterator,
|
|
sl@0
|
49 |
leda_node,
|
|
sl@0
|
50 |
bidirectional_traversal_tag,
|
|
sl@0
|
51 |
leda_node,
|
|
sl@0
|
52 |
const leda_node*>
|
|
sl@0
|
53 |
{
|
|
sl@0
|
54 |
public:
|
|
sl@0
|
55 |
explicit adjacency_iterator(leda_edge edge = 0) : base(edge) {}
|
|
sl@0
|
56 |
|
|
sl@0
|
57 |
private:
|
|
sl@0
|
58 |
leda_node dereference() const { return leda::target(base); }
|
|
sl@0
|
59 |
|
|
sl@0
|
60 |
bool equal(const adjacency_iterator& other) const
|
|
sl@0
|
61 |
{ return base == other.base; }
|
|
sl@0
|
62 |
|
|
sl@0
|
63 |
void increment() { base = Succ_Adj_Edge(base, 0); }
|
|
sl@0
|
64 |
void decrement() { base = Pred_Adj_Edge(base, 0); }
|
|
sl@0
|
65 |
|
|
sl@0
|
66 |
leda_edge base;
|
|
sl@0
|
67 |
|
|
sl@0
|
68 |
friend class iterator_core_access;
|
|
sl@0
|
69 |
};
|
|
sl@0
|
70 |
|
|
sl@0
|
71 |
class out_edge_iterator
|
|
sl@0
|
72 |
: public iterator_facade<out_edge_iterator,
|
|
sl@0
|
73 |
leda_edge,
|
|
sl@0
|
74 |
bidirectional_traversal_tag,
|
|
sl@0
|
75 |
const leda_edge&,
|
|
sl@0
|
76 |
const leda_edge*>
|
|
sl@0
|
77 |
{
|
|
sl@0
|
78 |
public:
|
|
sl@0
|
79 |
explicit out_edge_iterator(leda_edge edge = 0) : base(edge) {}
|
|
sl@0
|
80 |
|
|
sl@0
|
81 |
private:
|
|
sl@0
|
82 |
const leda_edge& dereference() const { return base; }
|
|
sl@0
|
83 |
|
|
sl@0
|
84 |
bool equal(const out_edge_iterator& other) const
|
|
sl@0
|
85 |
{ return base == other.base; }
|
|
sl@0
|
86 |
|
|
sl@0
|
87 |
void increment() { base = Succ_Adj_Edge(base, 0); }
|
|
sl@0
|
88 |
void decrement() { base = Pred_Adj_Edge(base, 0); }
|
|
sl@0
|
89 |
|
|
sl@0
|
90 |
leda_edge base;
|
|
sl@0
|
91 |
|
|
sl@0
|
92 |
friend class iterator_core_access;
|
|
sl@0
|
93 |
};
|
|
sl@0
|
94 |
|
|
sl@0
|
95 |
class in_edge_iterator
|
|
sl@0
|
96 |
: public iterator_facade<in_edge_iterator,
|
|
sl@0
|
97 |
leda_edge,
|
|
sl@0
|
98 |
bidirectional_traversal_tag,
|
|
sl@0
|
99 |
const leda_edge&,
|
|
sl@0
|
100 |
const leda_edge*>
|
|
sl@0
|
101 |
{
|
|
sl@0
|
102 |
public:
|
|
sl@0
|
103 |
explicit in_edge_iterator(leda_edge edge = 0) : base(edge) {}
|
|
sl@0
|
104 |
|
|
sl@0
|
105 |
private:
|
|
sl@0
|
106 |
const leda_edge& dereference() const { return base; }
|
|
sl@0
|
107 |
|
|
sl@0
|
108 |
bool equal(const in_edge_iterator& other) const
|
|
sl@0
|
109 |
{ return base == other.base; }
|
|
sl@0
|
110 |
|
|
sl@0
|
111 |
void increment() { base = Succ_Adj_Edge(base, 1); }
|
|
sl@0
|
112 |
void decrement() { base = Pred_Adj_Edge(base, 1); }
|
|
sl@0
|
113 |
|
|
sl@0
|
114 |
leda_edge base;
|
|
sl@0
|
115 |
|
|
sl@0
|
116 |
friend class iterator_core_access;
|
|
sl@0
|
117 |
};
|
|
sl@0
|
118 |
|
|
sl@0
|
119 |
class vertex_iterator
|
|
sl@0
|
120 |
: public iterator_facade<vertex_iterator,
|
|
sl@0
|
121 |
leda_node,
|
|
sl@0
|
122 |
bidirectional_traversal_tag,
|
|
sl@0
|
123 |
const leda_node&,
|
|
sl@0
|
124 |
const leda_node*>
|
|
sl@0
|
125 |
{
|
|
sl@0
|
126 |
public:
|
|
sl@0
|
127 |
vertex_iterator(leda_node node = 0,
|
|
sl@0
|
128 |
const leda::GRAPH<vtype, etype>* g = 0)
|
|
sl@0
|
129 |
: base(node), g(g) {}
|
|
sl@0
|
130 |
|
|
sl@0
|
131 |
private:
|
|
sl@0
|
132 |
const leda_node& dereference() const { return base; }
|
|
sl@0
|
133 |
|
|
sl@0
|
134 |
bool equal(const vertex_iterator& other) const
|
|
sl@0
|
135 |
{ return base == other.base; }
|
|
sl@0
|
136 |
|
|
sl@0
|
137 |
void increment() { base = g->succ_node(base); }
|
|
sl@0
|
138 |
void decrement() { base = g->pred_node(base); }
|
|
sl@0
|
139 |
|
|
sl@0
|
140 |
leda_node base;
|
|
sl@0
|
141 |
const leda::GRAPH<vtype, etype>* g;
|
|
sl@0
|
142 |
|
|
sl@0
|
143 |
friend class iterator_core_access;
|
|
sl@0
|
144 |
};
|
|
sl@0
|
145 |
|
|
sl@0
|
146 |
typedef directed_tag directed_category;
|
|
sl@0
|
147 |
typedef allow_parallel_edge_tag edge_parallel_category; // not sure here
|
|
sl@0
|
148 |
typedef leda_graph_traversal_category traversal_category;
|
|
sl@0
|
149 |
typedef int vertices_size_type;
|
|
sl@0
|
150 |
typedef int edges_size_type;
|
|
sl@0
|
151 |
typedef int degree_size_type;
|
|
sl@0
|
152 |
};
|
|
sl@0
|
153 |
|
|
sl@0
|
154 |
template <class vtype, class etype>
|
|
sl@0
|
155 |
struct vertex_property< leda::GRAPH<vtype,etype> > {
|
|
sl@0
|
156 |
typedef vtype type;
|
|
sl@0
|
157 |
};
|
|
sl@0
|
158 |
|
|
sl@0
|
159 |
template <class vtype, class etype>
|
|
sl@0
|
160 |
struct edge_property< leda::GRAPH<vtype,etype> > {
|
|
sl@0
|
161 |
typedef etype type;
|
|
sl@0
|
162 |
};
|
|
sl@0
|
163 |
|
|
sl@0
|
164 |
} // namespace boost
|
|
sl@0
|
165 |
#endif
|
|
sl@0
|
166 |
|
|
sl@0
|
167 |
namespace boost {
|
|
sl@0
|
168 |
|
|
sl@0
|
169 |
template <class vtype, class etype>
|
|
sl@0
|
170 |
typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor
|
|
sl@0
|
171 |
source(typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor e,
|
|
sl@0
|
172 |
const leda::GRAPH<vtype,etype>& g)
|
|
sl@0
|
173 |
{
|
|
sl@0
|
174 |
return source(e);
|
|
sl@0
|
175 |
}
|
|
sl@0
|
176 |
|
|
sl@0
|
177 |
template <class vtype, class etype>
|
|
sl@0
|
178 |
typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor
|
|
sl@0
|
179 |
target(typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor e,
|
|
sl@0
|
180 |
const leda::GRAPH<vtype,etype>& g)
|
|
sl@0
|
181 |
{
|
|
sl@0
|
182 |
return target(e);
|
|
sl@0
|
183 |
}
|
|
sl@0
|
184 |
|
|
sl@0
|
185 |
template <class vtype, class etype>
|
|
sl@0
|
186 |
inline std::pair<
|
|
sl@0
|
187 |
typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator,
|
|
sl@0
|
188 |
typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator >
|
|
sl@0
|
189 |
vertices(const leda::GRAPH<vtype,etype>& g)
|
|
sl@0
|
190 |
{
|
|
sl@0
|
191 |
typedef typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator
|
|
sl@0
|
192 |
Iter;
|
|
sl@0
|
193 |
return std::make_pair( Iter(g.first_node(),&g), Iter(0,&g) );
|
|
sl@0
|
194 |
}
|
|
sl@0
|
195 |
|
|
sl@0
|
196 |
// no edges(g) function
|
|
sl@0
|
197 |
|
|
sl@0
|
198 |
template <class vtype, class etype>
|
|
sl@0
|
199 |
inline std::pair<
|
|
sl@0
|
200 |
typename graph_traits< leda::GRAPH<vtype,etype> >::out_edge_iterator,
|
|
sl@0
|
201 |
typename graph_traits< leda::GRAPH<vtype,etype> >::out_edge_iterator >
|
|
sl@0
|
202 |
out_edges(
|
|
sl@0
|
203 |
typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
|
|
sl@0
|
204 |
const leda::GRAPH<vtype,etype>& g)
|
|
sl@0
|
205 |
{
|
|
sl@0
|
206 |
typedef typename graph_traits< leda::GRAPH<vtype,etype> >
|
|
sl@0
|
207 |
::out_edge_iterator Iter;
|
|
sl@0
|
208 |
return std::make_pair( Iter(First_Adj_Edge(u,0)), Iter(0) );
|
|
sl@0
|
209 |
}
|
|
sl@0
|
210 |
|
|
sl@0
|
211 |
template <class vtype, class etype>
|
|
sl@0
|
212 |
inline std::pair<
|
|
sl@0
|
213 |
typename graph_traits< leda::GRAPH<vtype,etype> >::in_edge_iterator,
|
|
sl@0
|
214 |
typename graph_traits< leda::GRAPH<vtype,etype> >::in_edge_iterator >
|
|
sl@0
|
215 |
in_edges(
|
|
sl@0
|
216 |
typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
|
|
sl@0
|
217 |
const leda::GRAPH<vtype,etype>& g)
|
|
sl@0
|
218 |
{
|
|
sl@0
|
219 |
typedef typename graph_traits< leda::GRAPH<vtype,etype> >
|
|
sl@0
|
220 |
::in_edge_iterator Iter;
|
|
sl@0
|
221 |
return std::make_pair( Iter(First_Adj_Edge(u,1)), Iter(0) );
|
|
sl@0
|
222 |
}
|
|
sl@0
|
223 |
|
|
sl@0
|
224 |
template <class vtype, class etype>
|
|
sl@0
|
225 |
inline std::pair<
|
|
sl@0
|
226 |
typename graph_traits< leda::GRAPH<vtype,etype> >::adjacency_iterator,
|
|
sl@0
|
227 |
typename graph_traits< leda::GRAPH<vtype,etype> >::adjacency_iterator >
|
|
sl@0
|
228 |
adjacent_vertices(
|
|
sl@0
|
229 |
typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
|
|
sl@0
|
230 |
const leda::GRAPH<vtype,etype>& g)
|
|
sl@0
|
231 |
{
|
|
sl@0
|
232 |
typedef typename graph_traits< leda::GRAPH<vtype,etype> >
|
|
sl@0
|
233 |
::adjacency_iterator Iter;
|
|
sl@0
|
234 |
return std::make_pair( Iter(First_Adj_Edge(u,0)), Iter(0) );
|
|
sl@0
|
235 |
}
|
|
sl@0
|
236 |
|
|
sl@0
|
237 |
template <class vtype, class etype>
|
|
sl@0
|
238 |
typename graph_traits< leda::GRAPH<vtype,etype> >::vertices_size_type
|
|
sl@0
|
239 |
num_vertices(const leda::GRAPH<vtype,etype>& g)
|
|
sl@0
|
240 |
{
|
|
sl@0
|
241 |
return g.number_of_nodes();
|
|
sl@0
|
242 |
}
|
|
sl@0
|
243 |
|
|
sl@0
|
244 |
template <class vtype, class etype>
|
|
sl@0
|
245 |
typename graph_traits< leda::GRAPH<vtype,etype> >::edges_size_type
|
|
sl@0
|
246 |
num_edges(const leda::GRAPH<vtype,etype>& g)
|
|
sl@0
|
247 |
{
|
|
sl@0
|
248 |
return g.number_of_edges();
|
|
sl@0
|
249 |
}
|
|
sl@0
|
250 |
|
|
sl@0
|
251 |
template <class vtype, class etype>
|
|
sl@0
|
252 |
typename graph_traits< leda::GRAPH<vtype,etype> >::degree_size_type
|
|
sl@0
|
253 |
out_degree(
|
|
sl@0
|
254 |
typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
|
|
sl@0
|
255 |
const leda::GRAPH<vtype,etype>&)
|
|
sl@0
|
256 |
{
|
|
sl@0
|
257 |
return outdeg(u);
|
|
sl@0
|
258 |
}
|
|
sl@0
|
259 |
|
|
sl@0
|
260 |
template <class vtype, class etype>
|
|
sl@0
|
261 |
typename graph_traits< leda::GRAPH<vtype,etype> >::degree_size_type
|
|
sl@0
|
262 |
in_degree(
|
|
sl@0
|
263 |
typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
|
|
sl@0
|
264 |
const leda::GRAPH<vtype,etype>&)
|
|
sl@0
|
265 |
{
|
|
sl@0
|
266 |
return indeg(u);
|
|
sl@0
|
267 |
}
|
|
sl@0
|
268 |
|
|
sl@0
|
269 |
template <class vtype, class etype>
|
|
sl@0
|
270 |
typename graph_traits< leda::GRAPH<vtype,etype> >::degree_size_type
|
|
sl@0
|
271 |
degree(
|
|
sl@0
|
272 |
typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
|
|
sl@0
|
273 |
const leda::GRAPH<vtype,etype>&)
|
|
sl@0
|
274 |
{
|
|
sl@0
|
275 |
return outdeg(u) + indeg(u);
|
|
sl@0
|
276 |
}
|
|
sl@0
|
277 |
|
|
sl@0
|
278 |
template <class vtype, class etype>
|
|
sl@0
|
279 |
typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor
|
|
sl@0
|
280 |
add_vertex(leda::GRAPH<vtype,etype>& g)
|
|
sl@0
|
281 |
{
|
|
sl@0
|
282 |
return g.new_node();
|
|
sl@0
|
283 |
}
|
|
sl@0
|
284 |
|
|
sl@0
|
285 |
template <class vtype, class etype>
|
|
sl@0
|
286 |
typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor
|
|
sl@0
|
287 |
add_vertex(const vtype& vp, leda::GRAPH<vtype,etype>& g)
|
|
sl@0
|
288 |
{
|
|
sl@0
|
289 |
return g.new_node(vp);
|
|
sl@0
|
290 |
}
|
|
sl@0
|
291 |
|
|
sl@0
|
292 |
// Hmm, LEDA doesn't have the equivalent of clear_vertex() -JGS
|
|
sl@0
|
293 |
// need to write an implementation
|
|
sl@0
|
294 |
template <class vtype, class etype>
|
|
sl@0
|
295 |
void clear_vertex(
|
|
sl@0
|
296 |
typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
|
|
sl@0
|
297 |
leda::GRAPH<vtype,etype>& g)
|
|
sl@0
|
298 |
{
|
|
sl@0
|
299 |
g.del_node(u);
|
|
sl@0
|
300 |
}
|
|
sl@0
|
301 |
|
|
sl@0
|
302 |
template <class vtype, class etype>
|
|
sl@0
|
303 |
void remove_vertex(
|
|
sl@0
|
304 |
typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
|
|
sl@0
|
305 |
leda::GRAPH<vtype,etype>& g)
|
|
sl@0
|
306 |
{
|
|
sl@0
|
307 |
g.del_node(u);
|
|
sl@0
|
308 |
}
|
|
sl@0
|
309 |
|
|
sl@0
|
310 |
template <class vtype, class etype>
|
|
sl@0
|
311 |
std::pair<
|
|
sl@0
|
312 |
typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor,
|
|
sl@0
|
313 |
bool>
|
|
sl@0
|
314 |
add_edge(
|
|
sl@0
|
315 |
typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
|
|
sl@0
|
316 |
typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor v,
|
|
sl@0
|
317 |
leda::GRAPH<vtype,etype>& g)
|
|
sl@0
|
318 |
{
|
|
sl@0
|
319 |
return std::make_pair(g.new_edge(u, v), true);
|
|
sl@0
|
320 |
}
|
|
sl@0
|
321 |
|
|
sl@0
|
322 |
template <class vtype, class etype>
|
|
sl@0
|
323 |
std::pair<
|
|
sl@0
|
324 |
typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor,
|
|
sl@0
|
325 |
bool>
|
|
sl@0
|
326 |
add_edge(
|
|
sl@0
|
327 |
typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
|
|
sl@0
|
328 |
typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor v,
|
|
sl@0
|
329 |
const etype& et,
|
|
sl@0
|
330 |
leda::GRAPH<vtype,etype>& g)
|
|
sl@0
|
331 |
{
|
|
sl@0
|
332 |
return std::make_pair(g.new_edge(u, v, et), true);
|
|
sl@0
|
333 |
}
|
|
sl@0
|
334 |
|
|
sl@0
|
335 |
template <class vtype, class etype>
|
|
sl@0
|
336 |
void
|
|
sl@0
|
337 |
remove_edge(
|
|
sl@0
|
338 |
typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
|
|
sl@0
|
339 |
typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor v,
|
|
sl@0
|
340 |
leda::GRAPH<vtype,etype>& g)
|
|
sl@0
|
341 |
{
|
|
sl@0
|
342 |
typename graph_traits< leda::GRAPH<vtype,etype> >::out_edge_iterator
|
|
sl@0
|
343 |
i,iend;
|
|
sl@0
|
344 |
for (boost::tie(i,iend) = out_edges(u,g); i != iend; ++i)
|
|
sl@0
|
345 |
if (target(*i,g) == v)
|
|
sl@0
|
346 |
g.del_edge(*i);
|
|
sl@0
|
347 |
}
|
|
sl@0
|
348 |
|
|
sl@0
|
349 |
template <class vtype, class etype>
|
|
sl@0
|
350 |
void
|
|
sl@0
|
351 |
remove_edge(
|
|
sl@0
|
352 |
typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor e,
|
|
sl@0
|
353 |
leda::GRAPH<vtype,etype>& g)
|
|
sl@0
|
354 |
{
|
|
sl@0
|
355 |
g.del_edge(e);
|
|
sl@0
|
356 |
}
|
|
sl@0
|
357 |
|
|
sl@0
|
358 |
//===========================================================================
|
|
sl@0
|
359 |
// property maps
|
|
sl@0
|
360 |
|
|
sl@0
|
361 |
class leda_graph_id_map
|
|
sl@0
|
362 |
: public put_get_helper<int, leda_graph_id_map>
|
|
sl@0
|
363 |
{
|
|
sl@0
|
364 |
public:
|
|
sl@0
|
365 |
typedef readable_property_map_tag category;
|
|
sl@0
|
366 |
typedef int value_type;
|
|
sl@0
|
367 |
typedef int reference;
|
|
sl@0
|
368 |
typedef leda_node key_type;
|
|
sl@0
|
369 |
leda_graph_id_map() { }
|
|
sl@0
|
370 |
template <class T>
|
|
sl@0
|
371 |
long operator[](T x) const { return x->id(); }
|
|
sl@0
|
372 |
};
|
|
sl@0
|
373 |
template <class vtype, class etype>
|
|
sl@0
|
374 |
inline leda_graph_id_map
|
|
sl@0
|
375 |
get(vertex_index_t, const leda::GRAPH<vtype, etype>& g) {
|
|
sl@0
|
376 |
return leda_graph_id_map();
|
|
sl@0
|
377 |
}
|
|
sl@0
|
378 |
template <class vtype, class etype>
|
|
sl@0
|
379 |
inline leda_graph_id_map
|
|
sl@0
|
380 |
get(edge_index_t, const leda::GRAPH<vtype, etype>& g) {
|
|
sl@0
|
381 |
return leda_graph_id_map();
|
|
sl@0
|
382 |
}
|
|
sl@0
|
383 |
|
|
sl@0
|
384 |
template <class Tag>
|
|
sl@0
|
385 |
struct leda_property_map { };
|
|
sl@0
|
386 |
|
|
sl@0
|
387 |
template <>
|
|
sl@0
|
388 |
struct leda_property_map<vertex_index_t> {
|
|
sl@0
|
389 |
template <class vtype, class etype>
|
|
sl@0
|
390 |
struct bind_ {
|
|
sl@0
|
391 |
typedef leda_graph_id_map type;
|
|
sl@0
|
392 |
typedef leda_graph_id_map const_type;
|
|
sl@0
|
393 |
};
|
|
sl@0
|
394 |
};
|
|
sl@0
|
395 |
template <>
|
|
sl@0
|
396 |
struct leda_property_map<edge_index_t> {
|
|
sl@0
|
397 |
template <class vtype, class etype>
|
|
sl@0
|
398 |
struct bind_ {
|
|
sl@0
|
399 |
typedef leda_graph_id_map type;
|
|
sl@0
|
400 |
typedef leda_graph_id_map const_type;
|
|
sl@0
|
401 |
};
|
|
sl@0
|
402 |
};
|
|
sl@0
|
403 |
|
|
sl@0
|
404 |
|
|
sl@0
|
405 |
template <class Data, class DataRef, class GraphPtr>
|
|
sl@0
|
406 |
class leda_graph_data_map
|
|
sl@0
|
407 |
: public put_get_helper<DataRef,
|
|
sl@0
|
408 |
leda_graph_data_map<Data,DataRef,GraphPtr> >
|
|
sl@0
|
409 |
{
|
|
sl@0
|
410 |
public:
|
|
sl@0
|
411 |
typedef Data value_type;
|
|
sl@0
|
412 |
typedef DataRef reference;
|
|
sl@0
|
413 |
typedef void key_type;
|
|
sl@0
|
414 |
typedef lvalue_property_map_tag category;
|
|
sl@0
|
415 |
leda_graph_data_map(GraphPtr g) : m_g(g) { }
|
|
sl@0
|
416 |
template <class NodeOrEdge>
|
|
sl@0
|
417 |
DataRef operator[](NodeOrEdge x) const { return (*m_g)[x]; }
|
|
sl@0
|
418 |
protected:
|
|
sl@0
|
419 |
GraphPtr m_g;
|
|
sl@0
|
420 |
};
|
|
sl@0
|
421 |
|
|
sl@0
|
422 |
template <>
|
|
sl@0
|
423 |
struct leda_property_map<vertex_all_t> {
|
|
sl@0
|
424 |
template <class vtype, class etype>
|
|
sl@0
|
425 |
struct bind_ {
|
|
sl@0
|
426 |
typedef leda_graph_data_map<vtype, vtype&, leda::GRAPH<vtype, etype>*> type;
|
|
sl@0
|
427 |
typedef leda_graph_data_map<vtype, const vtype&,
|
|
sl@0
|
428 |
const leda::GRAPH<vtype, etype>*> const_type;
|
|
sl@0
|
429 |
};
|
|
sl@0
|
430 |
};
|
|
sl@0
|
431 |
template <class vtype, class etype >
|
|
sl@0
|
432 |
inline typename property_map< leda::GRAPH<vtype, etype>, vertex_all_t>::type
|
|
sl@0
|
433 |
get(vertex_all_t, leda::GRAPH<vtype, etype>& g) {
|
|
sl@0
|
434 |
typedef typename property_map< leda::GRAPH<vtype, etype>, vertex_all_t>::type
|
|
sl@0
|
435 |
pmap_type;
|
|
sl@0
|
436 |
return pmap_type(&g);
|
|
sl@0
|
437 |
}
|
|
sl@0
|
438 |
template <class vtype, class etype >
|
|
sl@0
|
439 |
inline typename property_map< leda::GRAPH<vtype, etype>, vertex_all_t>::const_type
|
|
sl@0
|
440 |
get(vertex_all_t, const leda::GRAPH<vtype, etype>& g) {
|
|
sl@0
|
441 |
typedef typename property_map< leda::GRAPH<vtype, etype>,
|
|
sl@0
|
442 |
vertex_all_t>::const_type pmap_type;
|
|
sl@0
|
443 |
return pmap_type(&g);
|
|
sl@0
|
444 |
}
|
|
sl@0
|
445 |
|
|
sl@0
|
446 |
template <>
|
|
sl@0
|
447 |
struct leda_property_map<edge_all_t> {
|
|
sl@0
|
448 |
template <class vtype, class etype>
|
|
sl@0
|
449 |
struct bind_ {
|
|
sl@0
|
450 |
typedef leda_graph_data_map<etype, etype&, leda::GRAPH<vtype, etype>*> type;
|
|
sl@0
|
451 |
typedef leda_graph_data_map<etype, const etype&,
|
|
sl@0
|
452 |
const leda::GRAPH<vtype, etype>*> const_type;
|
|
sl@0
|
453 |
};
|
|
sl@0
|
454 |
};
|
|
sl@0
|
455 |
template <class vtype, class etype >
|
|
sl@0
|
456 |
inline typename property_map< leda::GRAPH<vtype, etype>, edge_all_t>::type
|
|
sl@0
|
457 |
get(edge_all_t, leda::GRAPH<vtype, etype>& g) {
|
|
sl@0
|
458 |
typedef typename property_map< leda::GRAPH<vtype, etype>, edge_all_t>::type
|
|
sl@0
|
459 |
pmap_type;
|
|
sl@0
|
460 |
return pmap_type(&g);
|
|
sl@0
|
461 |
}
|
|
sl@0
|
462 |
template <class vtype, class etype >
|
|
sl@0
|
463 |
inline typename property_map< leda::GRAPH<vtype, etype>, edge_all_t>::const_type
|
|
sl@0
|
464 |
get(edge_all_t, const leda::GRAPH<vtype, etype>& g) {
|
|
sl@0
|
465 |
typedef typename property_map< leda::GRAPH<vtype, etype>,
|
|
sl@0
|
466 |
edge_all_t>::const_type pmap_type;
|
|
sl@0
|
467 |
return pmap_type(&g);
|
|
sl@0
|
468 |
}
|
|
sl@0
|
469 |
|
|
sl@0
|
470 |
// property map interface to the LEDA node_array class
|
|
sl@0
|
471 |
|
|
sl@0
|
472 |
template <class E, class ERef, class NodeMapPtr>
|
|
sl@0
|
473 |
class leda_node_property_map
|
|
sl@0
|
474 |
: public put_get_helper<ERef, leda_node_property_map<E, ERef, NodeMapPtr> >
|
|
sl@0
|
475 |
{
|
|
sl@0
|
476 |
public:
|
|
sl@0
|
477 |
typedef E value_type;
|
|
sl@0
|
478 |
typedef ERef reference;
|
|
sl@0
|
479 |
typedef leda_node key_type;
|
|
sl@0
|
480 |
typedef lvalue_property_map_tag category;
|
|
sl@0
|
481 |
leda_node_property_map(NodeMapPtr a) : m_array(a) { }
|
|
sl@0
|
482 |
ERef operator[](leda_node n) const { return (*m_array)[n]; }
|
|
sl@0
|
483 |
protected:
|
|
sl@0
|
484 |
NodeMapPtr m_array;
|
|
sl@0
|
485 |
};
|
|
sl@0
|
486 |
template <class E>
|
|
sl@0
|
487 |
leda_node_property_map<E, const E&, const leda_node_array<E>*>
|
|
sl@0
|
488 |
make_leda_node_property_map(const leda_node_array<E>& a)
|
|
sl@0
|
489 |
{
|
|
sl@0
|
490 |
typedef leda_node_property_map<E, const E&, const leda_node_array<E>*>
|
|
sl@0
|
491 |
pmap_type;
|
|
sl@0
|
492 |
return pmap_type(&a);
|
|
sl@0
|
493 |
}
|
|
sl@0
|
494 |
template <class E>
|
|
sl@0
|
495 |
leda_node_property_map<E, E&, leda_node_array<E>*>
|
|
sl@0
|
496 |
make_leda_node_property_map(leda_node_array<E>& a)
|
|
sl@0
|
497 |
{
|
|
sl@0
|
498 |
typedef leda_node_property_map<E, E&, leda_node_array<E>*> pmap_type;
|
|
sl@0
|
499 |
return pmap_type(&a);
|
|
sl@0
|
500 |
}
|
|
sl@0
|
501 |
|
|
sl@0
|
502 |
template <class E>
|
|
sl@0
|
503 |
leda_node_property_map<E, const E&, const leda_node_map<E>*>
|
|
sl@0
|
504 |
make_leda_node_property_map(const leda_node_map<E>& a)
|
|
sl@0
|
505 |
{
|
|
sl@0
|
506 |
typedef leda_node_property_map<E,const E&,const leda_node_map<E>*>
|
|
sl@0
|
507 |
pmap_type;
|
|
sl@0
|
508 |
return pmap_type(&a);
|
|
sl@0
|
509 |
}
|
|
sl@0
|
510 |
template <class E>
|
|
sl@0
|
511 |
leda_node_property_map<E, E&, leda_node_map<E>*>
|
|
sl@0
|
512 |
make_leda_node_property_map(leda_node_map<E>& a)
|
|
sl@0
|
513 |
{
|
|
sl@0
|
514 |
typedef leda_node_property_map<E, E&, leda_node_map<E>*> pmap_type;
|
|
sl@0
|
515 |
return pmap_type(&a);
|
|
sl@0
|
516 |
}
|
|
sl@0
|
517 |
|
|
sl@0
|
518 |
// g++ 'enumeral_type' in template unification not implemented workaround
|
|
sl@0
|
519 |
template <class vtype, class etype, class Tag>
|
|
sl@0
|
520 |
struct property_map<leda::GRAPH<vtype, etype>, Tag> {
|
|
sl@0
|
521 |
typedef typename
|
|
sl@0
|
522 |
leda_property_map<Tag>::template bind_<vtype, etype> map_gen;
|
|
sl@0
|
523 |
typedef typename map_gen::type type;
|
|
sl@0
|
524 |
typedef typename map_gen::const_type const_type;
|
|
sl@0
|
525 |
};
|
|
sl@0
|
526 |
|
|
sl@0
|
527 |
template <class vtype, class etype, class PropertyTag, class Key>
|
|
sl@0
|
528 |
inline
|
|
sl@0
|
529 |
typename boost::property_traits<
|
|
sl@0
|
530 |
typename boost::property_map<leda::GRAPH<vtype, etype>,PropertyTag>::const_type
|
|
sl@0
|
531 |
>::value_type
|
|
sl@0
|
532 |
get(PropertyTag p, const leda::GRAPH<vtype, etype>& g, const Key& key) {
|
|
sl@0
|
533 |
return get(get(p, g), key);
|
|
sl@0
|
534 |
}
|
|
sl@0
|
535 |
|
|
sl@0
|
536 |
template <class vtype, class etype, class PropertyTag, class Key,class Value>
|
|
sl@0
|
537 |
inline void
|
|
sl@0
|
538 |
put(PropertyTag p, leda::GRAPH<vtype, etype>& g,
|
|
sl@0
|
539 |
const Key& key, const Value& value)
|
|
sl@0
|
540 |
{
|
|
sl@0
|
541 |
typedef typename property_map<leda::GRAPH<vtype, etype>, PropertyTag>::type Map;
|
|
sl@0
|
542 |
Map pmap = get(p, g);
|
|
sl@0
|
543 |
put(pmap, key, value);
|
|
sl@0
|
544 |
}
|
|
sl@0
|
545 |
|
|
sl@0
|
546 |
} // namespace boost
|
|
sl@0
|
547 |
|
|
sl@0
|
548 |
|
|
sl@0
|
549 |
#endif // BOOST_GRAPH_LEDA_HPP
|