williamr@2
|
1 |
// -*- c++ -*-
|
williamr@2
|
2 |
//=======================================================================
|
williamr@2
|
3 |
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
|
williamr@2
|
4 |
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
|
williamr@2
|
5 |
//
|
williamr@2
|
6 |
// Distributed under the Boost Software License, Version 1.0. (See
|
williamr@2
|
7 |
// accompanying file LICENSE_1_0.txt or copy at
|
williamr@2
|
8 |
// http://www.boost.org/LICENSE_1_0.txt)
|
williamr@2
|
9 |
//=======================================================================
|
williamr@2
|
10 |
|
williamr@2
|
11 |
#ifndef BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP
|
williamr@2
|
12 |
#define BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP
|
williamr@2
|
13 |
|
williamr@2
|
14 |
#include <map> // for vertex_map in copy_impl
|
williamr@2
|
15 |
#include <boost/config.hpp>
|
williamr@2
|
16 |
#include <boost/detail/workaround.hpp>
|
williamr@2
|
17 |
#include <boost/operators.hpp>
|
williamr@2
|
18 |
#include <boost/property_map.hpp>
|
williamr@2
|
19 |
#include <boost/pending/integer_range.hpp>
|
williamr@2
|
20 |
#include <boost/graph/graph_traits.hpp>
|
williamr@2
|
21 |
#include <memory>
|
williamr@2
|
22 |
#include <algorithm>
|
williamr@2
|
23 |
#include <boost/limits.hpp>
|
williamr@2
|
24 |
|
williamr@2
|
25 |
#include <boost/iterator/iterator_adaptor.hpp>
|
williamr@2
|
26 |
|
williamr@2
|
27 |
#include <boost/pending/ct_if.hpp>
|
williamr@2
|
28 |
#include <boost/graph/graph_concepts.hpp>
|
williamr@2
|
29 |
#include <boost/pending/container_traits.hpp>
|
williamr@2
|
30 |
#include <boost/graph/detail/adj_list_edge_iterator.hpp>
|
williamr@2
|
31 |
#include <boost/graph/properties.hpp>
|
williamr@2
|
32 |
#include <boost/pending/property.hpp>
|
williamr@2
|
33 |
#include <boost/graph/adjacency_iterator.hpp>
|
williamr@2
|
34 |
#include <boost/static_assert.hpp>
|
williamr@2
|
35 |
|
williamr@2
|
36 |
// Symbol truncation problems with MSVC, trying to shorten names.
|
williamr@2
|
37 |
#define stored_edge se_
|
williamr@2
|
38 |
#define stored_edge_property sep_
|
williamr@2
|
39 |
#define stored_edge_iter sei_
|
williamr@2
|
40 |
|
williamr@2
|
41 |
/*
|
williamr@2
|
42 |
Outline for this file:
|
williamr@2
|
43 |
|
williamr@2
|
44 |
out_edge_iterator and in_edge_iterator implementation
|
williamr@2
|
45 |
edge_iterator for undirected graph
|
williamr@2
|
46 |
stored edge types (these object live in the out-edge/in-edge lists)
|
williamr@2
|
47 |
directed edges helper class
|
williamr@2
|
48 |
directed graph helper class
|
williamr@2
|
49 |
undirected graph helper class
|
williamr@2
|
50 |
bidirectional graph helper class
|
williamr@2
|
51 |
bidirectional graph helper class (without edge properties)
|
williamr@2
|
52 |
bidirectional graph helper class (with edge properties)
|
williamr@2
|
53 |
adjacency_list helper class
|
williamr@2
|
54 |
adj_list_impl class
|
williamr@2
|
55 |
vec_adj_list_impl class
|
williamr@2
|
56 |
adj_list_gen class
|
williamr@2
|
57 |
vertex property map
|
williamr@2
|
58 |
edge property map
|
williamr@2
|
59 |
|
williamr@2
|
60 |
|
williamr@2
|
61 |
Note: it would be nice to merge some of the undirected and
|
williamr@2
|
62 |
bidirectional code... it is awful similar.
|
williamr@2
|
63 |
*/
|
williamr@2
|
64 |
|
williamr@2
|
65 |
|
williamr@2
|
66 |
namespace boost {
|
williamr@2
|
67 |
|
williamr@2
|
68 |
namespace detail {
|
williamr@2
|
69 |
|
williamr@2
|
70 |
template <typename DirectedS>
|
williamr@2
|
71 |
struct directed_category_traits {
|
williamr@2
|
72 |
typedef directed_tag directed_category;
|
williamr@2
|
73 |
};
|
williamr@2
|
74 |
|
williamr@2
|
75 |
template <>
|
williamr@2
|
76 |
struct directed_category_traits<directedS> {
|
williamr@2
|
77 |
typedef directed_tag directed_category;
|
williamr@2
|
78 |
};
|
williamr@2
|
79 |
template <>
|
williamr@2
|
80 |
struct directed_category_traits<undirectedS> {
|
williamr@2
|
81 |
typedef undirected_tag directed_category;
|
williamr@2
|
82 |
};
|
williamr@2
|
83 |
template <>
|
williamr@2
|
84 |
struct directed_category_traits<bidirectionalS> {
|
williamr@2
|
85 |
typedef bidirectional_tag directed_category;
|
williamr@2
|
86 |
};
|
williamr@2
|
87 |
|
williamr@2
|
88 |
template <class Vertex>
|
williamr@2
|
89 |
struct target_is {
|
williamr@2
|
90 |
target_is(const Vertex& v) : m_target(v) { }
|
williamr@2
|
91 |
template <class StoredEdge>
|
williamr@2
|
92 |
bool operator()(const StoredEdge& e) const {
|
williamr@2
|
93 |
return e.get_target() == m_target;
|
williamr@2
|
94 |
}
|
williamr@2
|
95 |
Vertex m_target;
|
williamr@2
|
96 |
};
|
williamr@2
|
97 |
|
williamr@2
|
98 |
// O(E/V)
|
williamr@2
|
99 |
template <class EdgeList, class vertex_descriptor>
|
williamr@2
|
100 |
void erase_from_incidence_list(EdgeList& el, vertex_descriptor v,
|
williamr@2
|
101 |
allow_parallel_edge_tag)
|
williamr@2
|
102 |
{
|
williamr@2
|
103 |
boost::graph_detail::erase_if(el, detail::target_is<vertex_descriptor>(v));
|
williamr@2
|
104 |
}
|
williamr@2
|
105 |
// O(log(E/V))
|
williamr@2
|
106 |
template <class EdgeList, class vertex_descriptor>
|
williamr@2
|
107 |
void erase_from_incidence_list(EdgeList& el, vertex_descriptor v,
|
williamr@2
|
108 |
disallow_parallel_edge_tag)
|
williamr@2
|
109 |
{
|
williamr@2
|
110 |
typedef typename EdgeList::value_type StoredEdge;
|
williamr@2
|
111 |
el.erase(StoredEdge(v));
|
williamr@2
|
112 |
}
|
williamr@2
|
113 |
|
williamr@2
|
114 |
//=========================================================================
|
williamr@2
|
115 |
// Out-Edge and In-Edge Iterator Implementation
|
williamr@2
|
116 |
|
williamr@2
|
117 |
template <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference>
|
williamr@2
|
118 |
struct out_edge_iter
|
williamr@2
|
119 |
: iterator_adaptor<
|
williamr@2
|
120 |
out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
|
williamr@2
|
121 |
, BaseIter
|
williamr@2
|
122 |
, EdgeDescriptor
|
williamr@2
|
123 |
, use_default
|
williamr@2
|
124 |
, EdgeDescriptor
|
williamr@2
|
125 |
, Difference
|
williamr@2
|
126 |
>
|
williamr@2
|
127 |
{
|
williamr@2
|
128 |
typedef iterator_adaptor<
|
williamr@2
|
129 |
out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
|
williamr@2
|
130 |
, BaseIter
|
williamr@2
|
131 |
, EdgeDescriptor
|
williamr@2
|
132 |
, use_default
|
williamr@2
|
133 |
, EdgeDescriptor
|
williamr@2
|
134 |
, Difference
|
williamr@2
|
135 |
> super_t;
|
williamr@2
|
136 |
|
williamr@2
|
137 |
inline out_edge_iter() { }
|
williamr@2
|
138 |
inline out_edge_iter(const BaseIter& i, const VertexDescriptor& src)
|
williamr@2
|
139 |
: super_t(i), m_src(src) { }
|
williamr@2
|
140 |
|
williamr@2
|
141 |
inline EdgeDescriptor
|
williamr@2
|
142 |
dereference() const
|
williamr@2
|
143 |
{
|
williamr@2
|
144 |
return EdgeDescriptor(m_src, (*this->base()).get_target(),
|
williamr@2
|
145 |
&(*this->base()).get_property());
|
williamr@2
|
146 |
}
|
williamr@2
|
147 |
VertexDescriptor m_src;
|
williamr@2
|
148 |
};
|
williamr@2
|
149 |
|
williamr@2
|
150 |
template <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference>
|
williamr@2
|
151 |
struct in_edge_iter
|
williamr@2
|
152 |
: iterator_adaptor<
|
williamr@2
|
153 |
in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
|
williamr@2
|
154 |
, BaseIter
|
williamr@2
|
155 |
, EdgeDescriptor
|
williamr@2
|
156 |
, use_default
|
williamr@2
|
157 |
, EdgeDescriptor
|
williamr@2
|
158 |
, Difference
|
williamr@2
|
159 |
>
|
williamr@2
|
160 |
{
|
williamr@2
|
161 |
typedef iterator_adaptor<
|
williamr@2
|
162 |
in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
|
williamr@2
|
163 |
, BaseIter
|
williamr@2
|
164 |
, EdgeDescriptor
|
williamr@2
|
165 |
, use_default
|
williamr@2
|
166 |
, EdgeDescriptor
|
williamr@2
|
167 |
, Difference
|
williamr@2
|
168 |
> super_t;
|
williamr@2
|
169 |
|
williamr@2
|
170 |
inline in_edge_iter() { }
|
williamr@2
|
171 |
inline in_edge_iter(const BaseIter& i, const VertexDescriptor& src)
|
williamr@2
|
172 |
: super_t(i), m_src(src) { }
|
williamr@2
|
173 |
|
williamr@2
|
174 |
inline EdgeDescriptor
|
williamr@2
|
175 |
dereference() const
|
williamr@2
|
176 |
{
|
williamr@2
|
177 |
return EdgeDescriptor((*this->base()).get_target(), m_src,
|
williamr@2
|
178 |
&this->base()->get_property());
|
williamr@2
|
179 |
}
|
williamr@2
|
180 |
VertexDescriptor m_src;
|
williamr@2
|
181 |
};
|
williamr@2
|
182 |
|
williamr@2
|
183 |
//=========================================================================
|
williamr@2
|
184 |
// Undirected Edge Iterator Implementation
|
williamr@2
|
185 |
|
williamr@2
|
186 |
template <class EdgeIter, class EdgeDescriptor, class Difference>
|
williamr@2
|
187 |
struct undirected_edge_iter
|
williamr@2
|
188 |
: iterator_adaptor<
|
williamr@2
|
189 |
undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference>
|
williamr@2
|
190 |
, EdgeIter
|
williamr@2
|
191 |
, EdgeDescriptor
|
williamr@2
|
192 |
, use_default
|
williamr@2
|
193 |
, EdgeDescriptor
|
williamr@2
|
194 |
, Difference
|
williamr@2
|
195 |
>
|
williamr@2
|
196 |
{
|
williamr@2
|
197 |
typedef iterator_adaptor<
|
williamr@2
|
198 |
undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference>
|
williamr@2
|
199 |
, EdgeIter
|
williamr@2
|
200 |
, EdgeDescriptor
|
williamr@2
|
201 |
, use_default
|
williamr@2
|
202 |
, EdgeDescriptor
|
williamr@2
|
203 |
, Difference
|
williamr@2
|
204 |
> super_t;
|
williamr@2
|
205 |
|
williamr@2
|
206 |
undirected_edge_iter() {}
|
williamr@2
|
207 |
|
williamr@2
|
208 |
explicit undirected_edge_iter(EdgeIter i)
|
williamr@2
|
209 |
: super_t(i) {}
|
williamr@2
|
210 |
|
williamr@2
|
211 |
inline EdgeDescriptor
|
williamr@2
|
212 |
dereference() const {
|
williamr@2
|
213 |
return EdgeDescriptor(
|
williamr@2
|
214 |
(*this->base()).m_source
|
williamr@2
|
215 |
, (*this->base()).m_target
|
williamr@2
|
216 |
, &this->base()->get_property());
|
williamr@2
|
217 |
}
|
williamr@2
|
218 |
};
|
williamr@2
|
219 |
|
williamr@2
|
220 |
//=========================================================================
|
williamr@2
|
221 |
// Edge Storage Types (stored in the out-edge/in-edge lists)
|
williamr@2
|
222 |
|
williamr@2
|
223 |
template <class Vertex>
|
williamr@2
|
224 |
class stored_edge
|
williamr@2
|
225 |
: public boost::equality_comparable1< stored_edge<Vertex>,
|
williamr@2
|
226 |
boost::less_than_comparable1< stored_edge<Vertex> > >
|
williamr@2
|
227 |
{
|
williamr@2
|
228 |
public:
|
williamr@2
|
229 |
typedef no_property property_type;
|
williamr@2
|
230 |
inline stored_edge() { }
|
williamr@2
|
231 |
inline stored_edge(Vertex target, const no_property& = no_property())
|
williamr@2
|
232 |
: m_target(target) { }
|
williamr@2
|
233 |
// Need to write this explicitly so stored_edge_property can
|
williamr@2
|
234 |
// invoke Base::operator= (at least, for SGI MIPSPro compiler)
|
williamr@2
|
235 |
inline stored_edge& operator=(const stored_edge& x) {
|
williamr@2
|
236 |
m_target = x.m_target;
|
williamr@2
|
237 |
return *this;
|
williamr@2
|
238 |
}
|
williamr@2
|
239 |
inline Vertex& get_target() const { return m_target; }
|
williamr@2
|
240 |
inline const no_property& get_property() const { return s_prop; }
|
williamr@2
|
241 |
inline bool operator==(const stored_edge& x) const
|
williamr@2
|
242 |
{ return m_target == x.get_target(); }
|
williamr@2
|
243 |
inline bool operator<(const stored_edge& x) const
|
williamr@2
|
244 |
{ return m_target < x.get_target(); }
|
williamr@2
|
245 |
//protected: need to add hash<> as a friend
|
williamr@2
|
246 |
static no_property s_prop;
|
williamr@2
|
247 |
// Sometimes target not used as key in the set, and in that case
|
williamr@2
|
248 |
// it is ok to change the target.
|
williamr@2
|
249 |
mutable Vertex m_target;
|
williamr@2
|
250 |
};
|
williamr@2
|
251 |
template <class Vertex>
|
williamr@2
|
252 |
no_property stored_edge<Vertex>::s_prop;
|
williamr@2
|
253 |
|
williamr@2
|
254 |
template <class Vertex, class Property>
|
williamr@2
|
255 |
class stored_edge_property : public stored_edge<Vertex> {
|
williamr@2
|
256 |
typedef stored_edge_property self;
|
williamr@2
|
257 |
typedef stored_edge<Vertex> Base;
|
williamr@2
|
258 |
public:
|
williamr@2
|
259 |
typedef Property property_type;
|
williamr@2
|
260 |
inline stored_edge_property() { }
|
williamr@2
|
261 |
inline stored_edge_property(Vertex target,
|
williamr@2
|
262 |
const Property& p = Property())
|
williamr@2
|
263 |
: stored_edge<Vertex>(target), m_property(new Property(p)) { }
|
williamr@2
|
264 |
stored_edge_property(const self& x)
|
williamr@2
|
265 |
: Base(x), m_property(const_cast<self&>(x).m_property) { }
|
williamr@2
|
266 |
self& operator=(const self& x) {
|
williamr@2
|
267 |
Base::operator=(x);
|
williamr@2
|
268 |
m_property = const_cast<self&>(x).m_property;
|
williamr@2
|
269 |
return *this;
|
williamr@2
|
270 |
}
|
williamr@2
|
271 |
inline Property& get_property() { return *m_property; }
|
williamr@2
|
272 |
inline const Property& get_property() const { return *m_property; }
|
williamr@2
|
273 |
protected:
|
williamr@2
|
274 |
// Holding the property by-value causes edge-descriptor
|
williamr@2
|
275 |
// invalidation for add_edge() with EdgeList=vecS. Instead we
|
williamr@2
|
276 |
// hold a pointer to the property. std::auto_ptr is not
|
williamr@2
|
277 |
// a perfect fit for the job, but it is darn close.
|
williamr@2
|
278 |
std::auto_ptr<Property> m_property;
|
williamr@2
|
279 |
};
|
williamr@2
|
280 |
|
williamr@2
|
281 |
|
williamr@2
|
282 |
template <class Vertex, class Iter, class Property>
|
williamr@2
|
283 |
class stored_edge_iter
|
williamr@2
|
284 |
: public stored_edge<Vertex>
|
williamr@2
|
285 |
{
|
williamr@2
|
286 |
public:
|
williamr@2
|
287 |
typedef Property property_type;
|
williamr@2
|
288 |
inline stored_edge_iter() { }
|
williamr@2
|
289 |
inline stored_edge_iter(Vertex v)
|
williamr@2
|
290 |
: stored_edge<Vertex>(v) { }
|
williamr@2
|
291 |
inline stored_edge_iter(Vertex v, Iter i, void* = 0)
|
williamr@2
|
292 |
: stored_edge<Vertex>(v), m_iter(i) { }
|
williamr@2
|
293 |
inline Property& get_property() { return m_iter->get_property(); }
|
williamr@2
|
294 |
inline const Property& get_property() const {
|
williamr@2
|
295 |
return m_iter->get_property();
|
williamr@2
|
296 |
}
|
williamr@2
|
297 |
inline Iter get_iter() const { return m_iter; }
|
williamr@2
|
298 |
protected:
|
williamr@2
|
299 |
Iter m_iter;
|
williamr@2
|
300 |
};
|
williamr@2
|
301 |
|
williamr@2
|
302 |
// For when the EdgeList is a std::vector.
|
williamr@2
|
303 |
// Want to make the iterator stable, so use an offset
|
williamr@2
|
304 |
// instead of an iterator into a std::vector
|
williamr@2
|
305 |
template <class Vertex, class EdgeVec, class Property>
|
williamr@2
|
306 |
class stored_ra_edge_iter
|
williamr@2
|
307 |
: public stored_edge<Vertex>
|
williamr@2
|
308 |
{
|
williamr@2
|
309 |
typedef typename EdgeVec::iterator Iter;
|
williamr@2
|
310 |
public:
|
williamr@2
|
311 |
typedef Property property_type;
|
williamr@2
|
312 |
inline stored_ra_edge_iter() { }
|
williamr@2
|
313 |
inline stored_ra_edge_iter(Vertex v, Iter i = Iter(),
|
williamr@2
|
314 |
EdgeVec* edge_vec = 0)
|
williamr@2
|
315 |
: stored_edge<Vertex>(v), m_i(i - edge_vec->begin()), m_vec(edge_vec){ }
|
williamr@2
|
316 |
inline Property& get_property() { return (*m_vec)[m_i].get_property(); }
|
williamr@2
|
317 |
inline const Property& get_property() const {
|
williamr@2
|
318 |
return (*m_vec)[m_i].get_property();
|
williamr@2
|
319 |
}
|
williamr@2
|
320 |
inline Iter get_iter() const { return m_vec->begin() + m_i; }
|
williamr@2
|
321 |
protected:
|
williamr@2
|
322 |
std::size_t m_i;
|
williamr@2
|
323 |
EdgeVec* m_vec;
|
williamr@2
|
324 |
};
|
williamr@2
|
325 |
|
williamr@2
|
326 |
} // namespace detail
|
williamr@2
|
327 |
|
williamr@2
|
328 |
template <class Tag, class Vertex, class Property>
|
williamr@2
|
329 |
const typename property_value<Property,Tag>::type&
|
williamr@2
|
330 |
get(Tag property_tag,
|
williamr@2
|
331 |
const detail::stored_edge_property<Vertex, Property>& e)
|
williamr@2
|
332 |
{
|
williamr@2
|
333 |
return get_property_value(e.get_property(), property_tag);
|
williamr@2
|
334 |
}
|
williamr@2
|
335 |
|
williamr@2
|
336 |
template <class Tag, class Vertex, class Iter, class Property>
|
williamr@2
|
337 |
const typename property_value<Property,Tag>::type&
|
williamr@2
|
338 |
get(Tag property_tag,
|
williamr@2
|
339 |
const detail::stored_edge_iter<Vertex, Iter, Property>& e)
|
williamr@2
|
340 |
{
|
williamr@2
|
341 |
return get_property_value(e.get_property(), property_tag);
|
williamr@2
|
342 |
}
|
williamr@2
|
343 |
|
williamr@2
|
344 |
template <class Tag, class Vertex, class EdgeVec, class Property>
|
williamr@2
|
345 |
const typename property_value<Property,Tag>::type&
|
williamr@2
|
346 |
get(Tag property_tag,
|
williamr@2
|
347 |
const detail::stored_ra_edge_iter<Vertex, EdgeVec, Property>& e)
|
williamr@2
|
348 |
{
|
williamr@2
|
349 |
return get_property_value(e.get_property(), property_tag);
|
williamr@2
|
350 |
}
|
williamr@2
|
351 |
|
williamr@2
|
352 |
//=========================================================================
|
williamr@2
|
353 |
// Directed Edges Helper Class
|
williamr@2
|
354 |
|
williamr@2
|
355 |
namespace detail {
|
williamr@2
|
356 |
|
williamr@2
|
357 |
// O(E/V)
|
williamr@2
|
358 |
template <class edge_descriptor, class EdgeList, class StoredProperty>
|
williamr@2
|
359 |
inline void
|
williamr@2
|
360 |
remove_directed_edge_dispatch(edge_descriptor, EdgeList& el,
|
williamr@2
|
361 |
StoredProperty& p)
|
williamr@2
|
362 |
{
|
williamr@2
|
363 |
for (typename EdgeList::iterator i = el.begin();
|
williamr@2
|
364 |
i != el.end(); ++i)
|
williamr@2
|
365 |
if (&(*i).get_property() == &p) {
|
williamr@2
|
366 |
el.erase(i);
|
williamr@2
|
367 |
return;
|
williamr@2
|
368 |
}
|
williamr@2
|
369 |
}
|
williamr@2
|
370 |
|
williamr@2
|
371 |
template <class incidence_iterator, class EdgeList, class Predicate>
|
williamr@2
|
372 |
inline void
|
williamr@2
|
373 |
remove_directed_edge_if_dispatch(incidence_iterator first,
|
williamr@2
|
374 |
incidence_iterator last,
|
williamr@2
|
375 |
EdgeList& el, Predicate pred,
|
williamr@2
|
376 |
boost::allow_parallel_edge_tag)
|
williamr@2
|
377 |
{
|
williamr@2
|
378 |
// remove_if
|
williamr@2
|
379 |
while (first != last && !pred(*first))
|
williamr@2
|
380 |
++first;
|
williamr@2
|
381 |
incidence_iterator i = first;
|
williamr@2
|
382 |
if (first != last)
|
williamr@2
|
383 |
for (; i != last; ++i)
|
williamr@2
|
384 |
if (!pred(*i)) {
|
williamr@2
|
385 |
*first.base() = *i.base();
|
williamr@2
|
386 |
++first;
|
williamr@2
|
387 |
}
|
williamr@2
|
388 |
el.erase(first.base(), el.end());
|
williamr@2
|
389 |
}
|
williamr@2
|
390 |
template <class incidence_iterator, class EdgeList, class Predicate>
|
williamr@2
|
391 |
inline void
|
williamr@2
|
392 |
remove_directed_edge_if_dispatch(incidence_iterator first,
|
williamr@2
|
393 |
incidence_iterator last,
|
williamr@2
|
394 |
EdgeList& el,
|
williamr@2
|
395 |
Predicate pred,
|
williamr@2
|
396 |
boost::disallow_parallel_edge_tag)
|
williamr@2
|
397 |
{
|
williamr@2
|
398 |
for (incidence_iterator next = first;
|
williamr@2
|
399 |
first != last; first = next) {
|
williamr@2
|
400 |
++next;
|
williamr@2
|
401 |
if (pred(*first))
|
williamr@2
|
402 |
el.erase( first.base() );
|
williamr@2
|
403 |
}
|
williamr@2
|
404 |
}
|
williamr@2
|
405 |
|
williamr@2
|
406 |
template <class PropT, class Graph, class incidence_iterator,
|
williamr@2
|
407 |
class EdgeList, class Predicate>
|
williamr@2
|
408 |
inline void
|
williamr@2
|
409 |
undirected_remove_out_edge_if_dispatch(Graph& g,
|
williamr@2
|
410 |
incidence_iterator first,
|
williamr@2
|
411 |
incidence_iterator last,
|
williamr@2
|
412 |
EdgeList& el, Predicate pred,
|
williamr@2
|
413 |
boost::allow_parallel_edge_tag)
|
williamr@2
|
414 |
{
|
williamr@2
|
415 |
typedef typename Graph::global_edgelist_selector EdgeListS;
|
williamr@2
|
416 |
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
williamr@2
|
417 |
|
williamr@2
|
418 |
// remove_if
|
williamr@2
|
419 |
while (first != last && !pred(*first))
|
williamr@2
|
420 |
++first;
|
williamr@2
|
421 |
incidence_iterator i = first;
|
williamr@2
|
422 |
bool self_loop_removed = false;
|
williamr@2
|
423 |
if (first != last)
|
williamr@2
|
424 |
for (; i != last; ++i) {
|
williamr@2
|
425 |
if (self_loop_removed) {
|
williamr@2
|
426 |
/* With self loops, the descriptor will show up
|
williamr@2
|
427 |
* twice. The first time it will be removed, and now it
|
williamr@2
|
428 |
* will be skipped.
|
williamr@2
|
429 |
*/
|
williamr@2
|
430 |
self_loop_removed = false;
|
williamr@2
|
431 |
}
|
williamr@2
|
432 |
else if (!pred(*i)) {
|
williamr@2
|
433 |
*first.base() = *i.base();
|
williamr@2
|
434 |
++first;
|
williamr@2
|
435 |
} else {
|
williamr@2
|
436 |
if (source(*i, g) == target(*i, g)) self_loop_removed = true;
|
williamr@2
|
437 |
else {
|
williamr@2
|
438 |
// Remove the edge from the target
|
williamr@2
|
439 |
detail::remove_directed_edge_dispatch
|
williamr@2
|
440 |
(*i,
|
williamr@2
|
441 |
g.out_edge_list(target(*i, g)),
|
williamr@2
|
442 |
*(PropT*)(*i).get_property());
|
williamr@2
|
443 |
}
|
williamr@2
|
444 |
|
williamr@2
|
445 |
// Erase the edge property
|
williamr@2
|
446 |
g.m_edges.erase( (*i.base()).get_iter() );
|
williamr@2
|
447 |
}
|
williamr@2
|
448 |
}
|
williamr@2
|
449 |
el.erase(first.base(), el.end());
|
williamr@2
|
450 |
}
|
williamr@2
|
451 |
template <class PropT, class Graph, class incidence_iterator,
|
williamr@2
|
452 |
class EdgeList, class Predicate>
|
williamr@2
|
453 |
inline void
|
williamr@2
|
454 |
undirected_remove_out_edge_if_dispatch(Graph& g,
|
williamr@2
|
455 |
incidence_iterator first,
|
williamr@2
|
456 |
incidence_iterator last,
|
williamr@2
|
457 |
EdgeList& el,
|
williamr@2
|
458 |
Predicate pred,
|
williamr@2
|
459 |
boost::disallow_parallel_edge_tag)
|
williamr@2
|
460 |
{
|
williamr@2
|
461 |
typedef typename Graph::global_edgelist_selector EdgeListS;
|
williamr@2
|
462 |
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
williamr@2
|
463 |
|
williamr@2
|
464 |
for (incidence_iterator next = first;
|
williamr@2
|
465 |
first != last; first = next) {
|
williamr@2
|
466 |
++next;
|
williamr@2
|
467 |
if (pred(*first)) {
|
williamr@2
|
468 |
if (source(*first, g) != target(*first, g)) {
|
williamr@2
|
469 |
// Remove the edge from the target
|
williamr@2
|
470 |
detail::remove_directed_edge_dispatch
|
williamr@2
|
471 |
(*first,
|
williamr@2
|
472 |
g.out_edge_list(target(*first, g)),
|
williamr@2
|
473 |
*(PropT*)(*first).get_property());
|
williamr@2
|
474 |
}
|
williamr@2
|
475 |
|
williamr@2
|
476 |
// Erase the edge property
|
williamr@2
|
477 |
g.m_edges.erase( (*first.base()).get_iter() );
|
williamr@2
|
478 |
|
williamr@2
|
479 |
// Erase the edge in the source
|
williamr@2
|
480 |
el.erase( first.base() );
|
williamr@2
|
481 |
}
|
williamr@2
|
482 |
}
|
williamr@2
|
483 |
}
|
williamr@2
|
484 |
|
williamr@2
|
485 |
// O(E/V)
|
williamr@2
|
486 |
template <class edge_descriptor, class EdgeList, class StoredProperty>
|
williamr@2
|
487 |
inline void
|
williamr@2
|
488 |
remove_directed_edge_dispatch(edge_descriptor e, EdgeList& el,
|
williamr@2
|
489 |
no_property&)
|
williamr@2
|
490 |
{
|
williamr@2
|
491 |
for (typename EdgeList::iterator i = el.begin();
|
williamr@2
|
492 |
i != el.end(); ++i)
|
williamr@2
|
493 |
if ((*i).get_target() == e.m_target) {
|
williamr@2
|
494 |
el.erase(i);
|
williamr@2
|
495 |
return;
|
williamr@2
|
496 |
}
|
williamr@2
|
497 |
}
|
williamr@2
|
498 |
|
williamr@2
|
499 |
} // namespace detail
|
williamr@2
|
500 |
|
williamr@2
|
501 |
template <class Config>
|
williamr@2
|
502 |
struct directed_edges_helper {
|
williamr@2
|
503 |
|
williamr@2
|
504 |
// Placement of these overloaded remove_edge() functions
|
williamr@2
|
505 |
// inside the class avoids a VC++ bug.
|
williamr@2
|
506 |
|
williamr@2
|
507 |
// O(E/V)
|
williamr@2
|
508 |
inline void
|
williamr@2
|
509 |
remove_edge(typename Config::edge_descriptor e)
|
williamr@2
|
510 |
{
|
williamr@2
|
511 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
512 |
graph_type& g = static_cast<graph_type&>(*this);
|
williamr@2
|
513 |
typename Config::OutEdgeList& el = g.out_edge_list(source(e, g));
|
williamr@2
|
514 |
typedef typename Config::OutEdgeList::value_type::property_type PType;
|
williamr@2
|
515 |
detail::remove_directed_edge_dispatch(e, el,
|
williamr@2
|
516 |
*(PType*)e.get_property());
|
williamr@2
|
517 |
}
|
williamr@2
|
518 |
|
williamr@2
|
519 |
// O(1)
|
williamr@2
|
520 |
inline void
|
williamr@2
|
521 |
remove_edge(typename Config::out_edge_iterator iter)
|
williamr@2
|
522 |
{
|
williamr@2
|
523 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
524 |
graph_type& g = static_cast<graph_type&>(*this);
|
williamr@2
|
525 |
typename Config::edge_descriptor e = *iter;
|
williamr@2
|
526 |
typename Config::OutEdgeList& el = g.out_edge_list(source(e, g));
|
williamr@2
|
527 |
el.erase(iter.base());
|
williamr@2
|
528 |
}
|
williamr@2
|
529 |
|
williamr@2
|
530 |
};
|
williamr@2
|
531 |
|
williamr@2
|
532 |
// O(1)
|
williamr@2
|
533 |
template <class Config>
|
williamr@2
|
534 |
inline std::pair<typename Config::edge_iterator,
|
williamr@2
|
535 |
typename Config::edge_iterator>
|
williamr@2
|
536 |
edges(const directed_edges_helper<Config>& g_)
|
williamr@2
|
537 |
{
|
williamr@2
|
538 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
539 |
typedef typename Config::edge_iterator edge_iterator;
|
williamr@2
|
540 |
const graph_type& cg = static_cast<const graph_type&>(g_);
|
williamr@2
|
541 |
graph_type& g = const_cast<graph_type&>(cg);
|
williamr@2
|
542 |
return std::make_pair( edge_iterator(g.vertex_set().begin(),
|
williamr@2
|
543 |
g.vertex_set().begin(),
|
williamr@2
|
544 |
g.vertex_set().end(), g),
|
williamr@2
|
545 |
edge_iterator(g.vertex_set().begin(),
|
williamr@2
|
546 |
g.vertex_set().end(),
|
williamr@2
|
547 |
g.vertex_set().end(), g) );
|
williamr@2
|
548 |
}
|
williamr@2
|
549 |
|
williamr@2
|
550 |
//=========================================================================
|
williamr@2
|
551 |
// Directed Graph Helper Class
|
williamr@2
|
552 |
|
williamr@2
|
553 |
struct adj_list_dir_traversal_tag :
|
williamr@2
|
554 |
public virtual vertex_list_graph_tag,
|
williamr@2
|
555 |
public virtual incidence_graph_tag,
|
williamr@2
|
556 |
public virtual adjacency_graph_tag,
|
williamr@2
|
557 |
public virtual edge_list_graph_tag { };
|
williamr@2
|
558 |
|
williamr@2
|
559 |
template <class Config>
|
williamr@2
|
560 |
struct directed_graph_helper
|
williamr@2
|
561 |
: public directed_edges_helper<Config> {
|
williamr@2
|
562 |
typedef typename Config::edge_descriptor edge_descriptor;
|
williamr@2
|
563 |
typedef adj_list_dir_traversal_tag traversal_category;
|
williamr@2
|
564 |
};
|
williamr@2
|
565 |
|
williamr@2
|
566 |
// O(E/V)
|
williamr@2
|
567 |
template <class Config>
|
williamr@2
|
568 |
inline void
|
williamr@2
|
569 |
remove_edge(typename Config::vertex_descriptor u,
|
williamr@2
|
570 |
typename Config::vertex_descriptor v,
|
williamr@2
|
571 |
directed_graph_helper<Config>& g_)
|
williamr@2
|
572 |
{
|
williamr@2
|
573 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
574 |
typedef typename Config::edge_parallel_category Cat;
|
williamr@2
|
575 |
graph_type& g = static_cast<graph_type&>(g_);
|
williamr@2
|
576 |
detail::erase_from_incidence_list(g.out_edge_list(u), v, Cat());
|
williamr@2
|
577 |
}
|
williamr@2
|
578 |
|
williamr@2
|
579 |
template <class Config, class Predicate>
|
williamr@2
|
580 |
inline void
|
williamr@2
|
581 |
remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
|
williamr@2
|
582 |
directed_graph_helper<Config>& g_)
|
williamr@2
|
583 |
{
|
williamr@2
|
584 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
585 |
graph_type& g = static_cast<graph_type&>(g_);
|
williamr@2
|
586 |
typename Config::out_edge_iterator first, last;
|
williamr@2
|
587 |
tie(first, last) = out_edges(u, g);
|
williamr@2
|
588 |
typedef typename Config::edge_parallel_category edge_parallel_category;
|
williamr@2
|
589 |
detail::remove_directed_edge_if_dispatch
|
williamr@2
|
590 |
(first, last, g.out_edge_list(u), pred, edge_parallel_category());
|
williamr@2
|
591 |
}
|
williamr@2
|
592 |
|
williamr@2
|
593 |
template <class Config, class Predicate>
|
williamr@2
|
594 |
inline void
|
williamr@2
|
595 |
remove_edge_if(Predicate pred, directed_graph_helper<Config>& g_)
|
williamr@2
|
596 |
{
|
williamr@2
|
597 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
598 |
graph_type& g = static_cast<graph_type&>(g_);
|
williamr@2
|
599 |
|
williamr@2
|
600 |
typename Config::vertex_iterator vi, vi_end;
|
williamr@2
|
601 |
for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
|
williamr@2
|
602 |
remove_out_edge_if(*vi, pred, g);
|
williamr@2
|
603 |
}
|
williamr@2
|
604 |
|
williamr@2
|
605 |
template <class EdgeOrIter, class Config>
|
williamr@2
|
606 |
inline void
|
williamr@2
|
607 |
remove_edge(EdgeOrIter e_or_iter, directed_graph_helper<Config>& g_)
|
williamr@2
|
608 |
{
|
williamr@2
|
609 |
g_.remove_edge(e_or_iter);
|
williamr@2
|
610 |
}
|
williamr@2
|
611 |
|
williamr@2
|
612 |
// O(V + E) for allow_parallel_edges
|
williamr@2
|
613 |
// O(V * log(E/V)) for disallow_parallel_edges
|
williamr@2
|
614 |
template <class Config>
|
williamr@2
|
615 |
inline void
|
williamr@2
|
616 |
clear_vertex(typename Config::vertex_descriptor u,
|
williamr@2
|
617 |
directed_graph_helper<Config>& g_)
|
williamr@2
|
618 |
{
|
williamr@2
|
619 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
620 |
typedef typename Config::edge_parallel_category Cat;
|
williamr@2
|
621 |
graph_type& g = static_cast<graph_type&>(g_);
|
williamr@2
|
622 |
typename Config::vertex_iterator vi, viend;
|
williamr@2
|
623 |
for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi)
|
williamr@2
|
624 |
detail::erase_from_incidence_list(g.out_edge_list(*vi), u, Cat());
|
williamr@2
|
625 |
g.out_edge_list(u).clear();
|
williamr@2
|
626 |
// clear() should be a req of Sequence and AssociativeContainer,
|
williamr@2
|
627 |
// or maybe just Container
|
williamr@2
|
628 |
}
|
williamr@2
|
629 |
|
williamr@2
|
630 |
template <class Config>
|
williamr@2
|
631 |
inline void
|
williamr@2
|
632 |
clear_out_edges(typename Config::vertex_descriptor u,
|
williamr@2
|
633 |
directed_graph_helper<Config>& g_)
|
williamr@2
|
634 |
{
|
williamr@2
|
635 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
636 |
typedef typename Config::edge_parallel_category Cat;
|
williamr@2
|
637 |
graph_type& g = static_cast<graph_type&>(g_);
|
williamr@2
|
638 |
g.out_edge_list(u).clear();
|
williamr@2
|
639 |
// clear() should be a req of Sequence and AssociativeContainer,
|
williamr@2
|
640 |
// or maybe just Container
|
williamr@2
|
641 |
}
|
williamr@2
|
642 |
|
williamr@2
|
643 |
// O(V), could do better...
|
williamr@2
|
644 |
template <class Config>
|
williamr@2
|
645 |
inline typename Config::edges_size_type
|
williamr@2
|
646 |
num_edges(const directed_graph_helper<Config>& g_)
|
williamr@2
|
647 |
{
|
williamr@2
|
648 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
649 |
const graph_type& g = static_cast<const graph_type&>(g_);
|
williamr@2
|
650 |
typename Config::edges_size_type num_e = 0;
|
williamr@2
|
651 |
typename Config::vertex_iterator vi, vi_end;
|
williamr@2
|
652 |
for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
|
williamr@2
|
653 |
num_e += out_degree(*vi, g);
|
williamr@2
|
654 |
return num_e;
|
williamr@2
|
655 |
}
|
williamr@2
|
656 |
// O(1) for allow_parallel_edge_tag
|
williamr@2
|
657 |
// O(log(E/V)) for disallow_parallel_edge_tag
|
williamr@2
|
658 |
template <class Config>
|
williamr@2
|
659 |
inline std::pair<typename directed_graph_helper<Config>::edge_descriptor, bool>
|
williamr@2
|
660 |
add_edge(typename Config::vertex_descriptor u,
|
williamr@2
|
661 |
typename Config::vertex_descriptor v,
|
williamr@2
|
662 |
const typename Config::edge_property_type& p,
|
williamr@2
|
663 |
directed_graph_helper<Config>& g_)
|
williamr@2
|
664 |
{
|
williamr@2
|
665 |
typedef typename Config::edge_descriptor edge_descriptor;
|
williamr@2
|
666 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
667 |
typedef typename Config::StoredEdge StoredEdge;
|
williamr@2
|
668 |
graph_type& g = static_cast<graph_type&>(g_);
|
williamr@2
|
669 |
typename Config::OutEdgeList::iterator i;
|
williamr@2
|
670 |
bool inserted;
|
williamr@2
|
671 |
boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
|
williamr@2
|
672 |
StoredEdge(v, p));
|
williamr@2
|
673 |
return std::make_pair(edge_descriptor(u, v, &(*i).get_property()),
|
williamr@2
|
674 |
inserted);
|
williamr@2
|
675 |
}
|
williamr@2
|
676 |
// Did not use default argument here because that
|
williamr@2
|
677 |
// causes Visual C++ to get confused.
|
williamr@2
|
678 |
template <class Config>
|
williamr@2
|
679 |
inline std::pair<typename Config::edge_descriptor, bool>
|
williamr@2
|
680 |
add_edge(typename Config::vertex_descriptor u,
|
williamr@2
|
681 |
typename Config::vertex_descriptor v,
|
williamr@2
|
682 |
directed_graph_helper<Config>& g_)
|
williamr@2
|
683 |
{
|
williamr@2
|
684 |
typename Config::edge_property_type p;
|
williamr@2
|
685 |
return add_edge(u, v, p, g_);
|
williamr@2
|
686 |
}
|
williamr@2
|
687 |
//=========================================================================
|
williamr@2
|
688 |
// Undirected Graph Helper Class
|
williamr@2
|
689 |
|
williamr@2
|
690 |
template <class Config>
|
williamr@2
|
691 |
struct undirected_graph_helper;
|
williamr@2
|
692 |
|
williamr@2
|
693 |
struct undir_adj_list_traversal_tag :
|
williamr@2
|
694 |
public virtual vertex_list_graph_tag,
|
williamr@2
|
695 |
public virtual incidence_graph_tag,
|
williamr@2
|
696 |
public virtual adjacency_graph_tag,
|
williamr@2
|
697 |
public virtual edge_list_graph_tag,
|
williamr@2
|
698 |
public virtual bidirectional_graph_tag { };
|
williamr@2
|
699 |
|
williamr@2
|
700 |
namespace detail {
|
williamr@2
|
701 |
|
williamr@2
|
702 |
// using class with specialization for dispatch is a VC++ workaround.
|
williamr@2
|
703 |
template <class StoredProperty>
|
williamr@2
|
704 |
struct remove_undirected_edge_dispatch {
|
williamr@2
|
705 |
|
williamr@2
|
706 |
// O(E/V)
|
williamr@2
|
707 |
template <class edge_descriptor, class Config>
|
williamr@2
|
708 |
static void
|
williamr@2
|
709 |
apply(edge_descriptor e,
|
williamr@2
|
710 |
undirected_graph_helper<Config>& g_,
|
williamr@2
|
711 |
StoredProperty& p)
|
williamr@2
|
712 |
{
|
williamr@2
|
713 |
typedef typename Config::global_edgelist_selector EdgeListS;
|
williamr@2
|
714 |
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
williamr@2
|
715 |
|
williamr@2
|
716 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
717 |
graph_type& g = static_cast<graph_type&>(g_);
|
williamr@2
|
718 |
|
williamr@2
|
719 |
typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g));
|
williamr@2
|
720 |
typename Config::OutEdgeList::iterator out_i = out_el.begin();
|
williamr@2
|
721 |
for (; out_i != out_el.end(); ++out_i)
|
williamr@2
|
722 |
if (&(*out_i).get_property() == &p) {
|
williamr@2
|
723 |
out_el.erase(out_i);
|
williamr@2
|
724 |
break;
|
williamr@2
|
725 |
}
|
williamr@2
|
726 |
typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g));
|
williamr@2
|
727 |
typename Config::OutEdgeList::iterator in_i = in_el.begin();
|
williamr@2
|
728 |
for (; in_i != in_el.end(); ++in_i)
|
williamr@2
|
729 |
if (&(*in_i).get_property() == &p) {
|
williamr@2
|
730 |
g.m_edges.erase((*in_i).get_iter());
|
williamr@2
|
731 |
in_el.erase(in_i);
|
williamr@2
|
732 |
return;
|
williamr@2
|
733 |
}
|
williamr@2
|
734 |
}
|
williamr@2
|
735 |
};
|
williamr@2
|
736 |
|
williamr@2
|
737 |
template <>
|
williamr@2
|
738 |
struct remove_undirected_edge_dispatch<no_property> {
|
williamr@2
|
739 |
// O(E/V)
|
williamr@2
|
740 |
template <class edge_descriptor, class Config>
|
williamr@2
|
741 |
static void
|
williamr@2
|
742 |
apply(edge_descriptor e,
|
williamr@2
|
743 |
undirected_graph_helper<Config>& g_,
|
williamr@2
|
744 |
no_property&)
|
williamr@2
|
745 |
{
|
williamr@2
|
746 |
typedef typename Config::global_edgelist_selector EdgeListS;
|
williamr@2
|
747 |
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
williamr@2
|
748 |
|
williamr@2
|
749 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
750 |
graph_type& g = static_cast<graph_type&>(g_);
|
williamr@2
|
751 |
no_property* p = (no_property*)e.get_property();
|
williamr@2
|
752 |
typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g));
|
williamr@2
|
753 |
typename Config::OutEdgeList::iterator out_i = out_el.begin();
|
williamr@2
|
754 |
for (; out_i != out_el.end(); ++out_i)
|
williamr@2
|
755 |
if (&(*out_i).get_property() == p) {
|
williamr@2
|
756 |
out_el.erase(out_i);
|
williamr@2
|
757 |
break;
|
williamr@2
|
758 |
}
|
williamr@2
|
759 |
typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g));
|
williamr@2
|
760 |
typename Config::OutEdgeList::iterator in_i = in_el.begin();
|
williamr@2
|
761 |
for (; in_i != in_el.end(); ++in_i)
|
williamr@2
|
762 |
if (&(*in_i).get_property() == p) {
|
williamr@2
|
763 |
g.m_edges.erase((*in_i).get_iter());
|
williamr@2
|
764 |
in_el.erase(in_i);
|
williamr@2
|
765 |
return;
|
williamr@2
|
766 |
}
|
williamr@2
|
767 |
}
|
williamr@2
|
768 |
};
|
williamr@2
|
769 |
|
williamr@2
|
770 |
// O(E/V)
|
williamr@2
|
771 |
template <class Graph, class EdgeList, class Vertex>
|
williamr@2
|
772 |
inline void
|
williamr@2
|
773 |
remove_edge_and_property(Graph& g, EdgeList& el, Vertex v,
|
williamr@2
|
774 |
boost::allow_parallel_edge_tag cat)
|
williamr@2
|
775 |
{
|
williamr@2
|
776 |
typedef typename Graph::global_edgelist_selector EdgeListS;
|
williamr@2
|
777 |
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
williamr@2
|
778 |
|
williamr@2
|
779 |
typedef typename EdgeList::value_type StoredEdge;
|
williamr@2
|
780 |
typename EdgeList::iterator i = el.begin(), end = el.end();
|
williamr@2
|
781 |
for (; i != end; ++i)
|
williamr@2
|
782 |
if ((*i).get_target() == v)
|
williamr@2
|
783 |
g.m_edges.erase((*i).get_iter());
|
williamr@2
|
784 |
detail::erase_from_incidence_list(el, v, cat);
|
williamr@2
|
785 |
}
|
williamr@2
|
786 |
// O(log(E/V))
|
williamr@2
|
787 |
template <class Graph, class EdgeList, class Vertex>
|
williamr@2
|
788 |
inline void
|
williamr@2
|
789 |
remove_edge_and_property(Graph& g, EdgeList& el, Vertex v,
|
williamr@2
|
790 |
boost::disallow_parallel_edge_tag)
|
williamr@2
|
791 |
{
|
williamr@2
|
792 |
typedef typename Graph::global_edgelist_selector EdgeListS;
|
williamr@2
|
793 |
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
williamr@2
|
794 |
|
williamr@2
|
795 |
typedef typename EdgeList::value_type StoredEdge;
|
williamr@2
|
796 |
typename EdgeList::iterator i = el.find(StoredEdge(v)), end = el.end();
|
williamr@2
|
797 |
if (i != end) {
|
williamr@2
|
798 |
g.m_edges.erase((*i).get_iter());
|
williamr@2
|
799 |
el.erase(i);
|
williamr@2
|
800 |
}
|
williamr@2
|
801 |
}
|
williamr@2
|
802 |
|
williamr@2
|
803 |
} // namespace detail
|
williamr@2
|
804 |
|
williamr@2
|
805 |
template <class Vertex, class EdgeProperty>
|
williamr@2
|
806 |
struct list_edge // short name due to VC++ truncation and linker problems
|
williamr@2
|
807 |
: public boost::detail::edge_base<boost::undirected_tag, Vertex>
|
williamr@2
|
808 |
{
|
williamr@2
|
809 |
typedef EdgeProperty property_type;
|
williamr@2
|
810 |
typedef boost::detail::edge_base<boost::undirected_tag, Vertex> Base;
|
williamr@2
|
811 |
list_edge(Vertex u, Vertex v, const EdgeProperty& p = EdgeProperty())
|
williamr@2
|
812 |
: Base(u, v), m_property(p) { }
|
williamr@2
|
813 |
EdgeProperty& get_property() { return m_property; }
|
williamr@2
|
814 |
const EdgeProperty& get_property() const { return m_property; }
|
williamr@2
|
815 |
// the following methods should never be used, but are needed
|
williamr@2
|
816 |
// to make SGI MIPSpro C++ happy
|
williamr@2
|
817 |
list_edge() { }
|
williamr@2
|
818 |
bool operator==(const list_edge&) const { return false; }
|
williamr@2
|
819 |
bool operator<(const list_edge&) const { return false; }
|
williamr@2
|
820 |
EdgeProperty m_property;
|
williamr@2
|
821 |
};
|
williamr@2
|
822 |
|
williamr@2
|
823 |
template <class Config>
|
williamr@2
|
824 |
struct undirected_graph_helper {
|
williamr@2
|
825 |
|
williamr@2
|
826 |
typedef undir_adj_list_traversal_tag traversal_category;
|
williamr@2
|
827 |
|
williamr@2
|
828 |
// Placement of these overloaded remove_edge() functions
|
williamr@2
|
829 |
// inside the class avoids a VC++ bug.
|
williamr@2
|
830 |
|
williamr@2
|
831 |
// O(E/V)
|
williamr@2
|
832 |
inline void
|
williamr@2
|
833 |
remove_edge(typename Config::edge_descriptor e)
|
williamr@2
|
834 |
{
|
williamr@2
|
835 |
typedef typename Config::global_edgelist_selector EdgeListS;
|
williamr@2
|
836 |
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
williamr@2
|
837 |
|
williamr@2
|
838 |
typedef typename Config::OutEdgeList::value_type::property_type PType;
|
williamr@2
|
839 |
detail::remove_undirected_edge_dispatch<PType>::apply
|
williamr@2
|
840 |
(e, *this, *(PType*)e.get_property());
|
williamr@2
|
841 |
}
|
williamr@2
|
842 |
// O(E/V)
|
williamr@2
|
843 |
inline void
|
williamr@2
|
844 |
remove_edge(typename Config::out_edge_iterator iter)
|
williamr@2
|
845 |
{
|
williamr@2
|
846 |
this->remove_edge(*iter);
|
williamr@2
|
847 |
}
|
williamr@2
|
848 |
};
|
williamr@2
|
849 |
|
williamr@2
|
850 |
// Had to make these non-members to avoid accidental instantiation
|
williamr@2
|
851 |
// on SGI MIPSpro C++
|
williamr@2
|
852 |
template <class C>
|
williamr@2
|
853 |
inline typename C::InEdgeList&
|
williamr@2
|
854 |
in_edge_list(undirected_graph_helper<C>&,
|
williamr@2
|
855 |
typename C::vertex_descriptor v)
|
williamr@2
|
856 |
{
|
williamr@2
|
857 |
typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
|
williamr@2
|
858 |
return sv->m_out_edges;
|
williamr@2
|
859 |
}
|
williamr@2
|
860 |
template <class C>
|
williamr@2
|
861 |
inline const typename C::InEdgeList&
|
williamr@2
|
862 |
in_edge_list(const undirected_graph_helper<C>&,
|
williamr@2
|
863 |
typename C::vertex_descriptor v) {
|
williamr@2
|
864 |
typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
|
williamr@2
|
865 |
return sv->m_out_edges;
|
williamr@2
|
866 |
}
|
williamr@2
|
867 |
|
williamr@2
|
868 |
// O(E/V)
|
williamr@2
|
869 |
template <class EdgeOrIter, class Config>
|
williamr@2
|
870 |
inline void
|
williamr@2
|
871 |
remove_edge(EdgeOrIter e, undirected_graph_helper<Config>& g_)
|
williamr@2
|
872 |
{
|
williamr@2
|
873 |
typedef typename Config::global_edgelist_selector EdgeListS;
|
williamr@2
|
874 |
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
williamr@2
|
875 |
|
williamr@2
|
876 |
g_.remove_edge(e);
|
williamr@2
|
877 |
}
|
williamr@2
|
878 |
|
williamr@2
|
879 |
// O(E/V) or O(log(E/V))
|
williamr@2
|
880 |
template <class Config>
|
williamr@2
|
881 |
void
|
williamr@2
|
882 |
remove_edge(typename Config::vertex_descriptor u,
|
williamr@2
|
883 |
typename Config::vertex_descriptor v,
|
williamr@2
|
884 |
undirected_graph_helper<Config>& g_)
|
williamr@2
|
885 |
{
|
williamr@2
|
886 |
typedef typename Config::global_edgelist_selector EdgeListS;
|
williamr@2
|
887 |
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
williamr@2
|
888 |
|
williamr@2
|
889 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
890 |
graph_type& g = static_cast<graph_type&>(g_);
|
williamr@2
|
891 |
typedef typename Config::edge_parallel_category Cat;
|
williamr@2
|
892 |
detail::remove_edge_and_property(g, g.out_edge_list(u), v, Cat());
|
williamr@2
|
893 |
detail::erase_from_incidence_list(g.out_edge_list(v), u, Cat());
|
williamr@2
|
894 |
}
|
williamr@2
|
895 |
|
williamr@2
|
896 |
template <class Config, class Predicate>
|
williamr@2
|
897 |
void
|
williamr@2
|
898 |
remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
|
williamr@2
|
899 |
undirected_graph_helper<Config>& g_)
|
williamr@2
|
900 |
{
|
williamr@2
|
901 |
typedef typename Config::global_edgelist_selector EdgeListS;
|
williamr@2
|
902 |
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
williamr@2
|
903 |
|
williamr@2
|
904 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
905 |
typedef typename Config::OutEdgeList::value_type::property_type PropT;
|
williamr@2
|
906 |
graph_type& g = static_cast<graph_type&>(g_);
|
williamr@2
|
907 |
typename Config::out_edge_iterator first, last;
|
williamr@2
|
908 |
tie(first, last) = out_edges(u, g);
|
williamr@2
|
909 |
typedef typename Config::edge_parallel_category Cat;
|
williamr@2
|
910 |
detail::undirected_remove_out_edge_if_dispatch<PropT>
|
williamr@2
|
911 |
(g, first, last, g.out_edge_list(u), pred, Cat());
|
williamr@2
|
912 |
}
|
williamr@2
|
913 |
template <class Config, class Predicate>
|
williamr@2
|
914 |
void
|
williamr@2
|
915 |
remove_in_edge_if(typename Config::vertex_descriptor u, Predicate pred,
|
williamr@2
|
916 |
undirected_graph_helper<Config>& g_)
|
williamr@2
|
917 |
{
|
williamr@2
|
918 |
typedef typename Config::global_edgelist_selector EdgeListS;
|
williamr@2
|
919 |
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
williamr@2
|
920 |
|
williamr@2
|
921 |
remove_out_edge_if(u, pred, g_);
|
williamr@2
|
922 |
}
|
williamr@2
|
923 |
|
williamr@2
|
924 |
// O(E/V * E) or O(log(E/V) * E)
|
williamr@2
|
925 |
template <class Predicate, class Config>
|
williamr@2
|
926 |
void
|
williamr@2
|
927 |
remove_edge_if(Predicate pred, undirected_graph_helper<Config>& g_)
|
williamr@2
|
928 |
{
|
williamr@2
|
929 |
typedef typename Config::global_edgelist_selector EdgeListS;
|
williamr@2
|
930 |
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
williamr@2
|
931 |
|
williamr@2
|
932 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
933 |
graph_type& g = static_cast<graph_type&>(g_);
|
williamr@2
|
934 |
typename Config::edge_iterator ei, ei_end, next;
|
williamr@2
|
935 |
tie(ei, ei_end) = edges(g);
|
williamr@2
|
936 |
for (next = ei; ei != ei_end; ei = next) {
|
williamr@2
|
937 |
++next;
|
williamr@2
|
938 |
if (pred(*ei))
|
williamr@2
|
939 |
remove_edge(*ei, g);
|
williamr@2
|
940 |
}
|
williamr@2
|
941 |
}
|
williamr@2
|
942 |
|
williamr@2
|
943 |
// O(1)
|
williamr@2
|
944 |
template <class Config>
|
williamr@2
|
945 |
inline std::pair<typename Config::edge_iterator,
|
williamr@2
|
946 |
typename Config::edge_iterator>
|
williamr@2
|
947 |
edges(const undirected_graph_helper<Config>& g_)
|
williamr@2
|
948 |
{
|
williamr@2
|
949 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
950 |
typedef typename Config::edge_iterator edge_iterator;
|
williamr@2
|
951 |
const graph_type& cg = static_cast<const graph_type&>(g_);
|
williamr@2
|
952 |
graph_type& g = const_cast<graph_type&>(cg);
|
williamr@2
|
953 |
return std::make_pair( edge_iterator(g.m_edges.begin()),
|
williamr@2
|
954 |
edge_iterator(g.m_edges.end()) );
|
williamr@2
|
955 |
}
|
williamr@2
|
956 |
// O(1)
|
williamr@2
|
957 |
template <class Config>
|
williamr@2
|
958 |
inline typename Config::edges_size_type
|
williamr@2
|
959 |
num_edges(const undirected_graph_helper<Config>& g_)
|
williamr@2
|
960 |
{
|
williamr@2
|
961 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
962 |
const graph_type& g = static_cast<const graph_type&>(g_);
|
williamr@2
|
963 |
return g.m_edges.size();
|
williamr@2
|
964 |
}
|
williamr@2
|
965 |
// O(E/V * E/V)
|
williamr@2
|
966 |
template <class Config>
|
williamr@2
|
967 |
inline void
|
williamr@2
|
968 |
clear_vertex(typename Config::vertex_descriptor u,
|
williamr@2
|
969 |
undirected_graph_helper<Config>& g_)
|
williamr@2
|
970 |
{
|
williamr@2
|
971 |
typedef typename Config::global_edgelist_selector EdgeListS;
|
williamr@2
|
972 |
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
williamr@2
|
973 |
|
williamr@2
|
974 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
975 |
typedef typename Config::edge_parallel_category Cat;
|
williamr@2
|
976 |
graph_type& g = static_cast<graph_type&>(g_);
|
williamr@2
|
977 |
typename Config::OutEdgeList& el = g.out_edge_list(u);
|
williamr@2
|
978 |
typename Config::OutEdgeList::iterator
|
williamr@2
|
979 |
ei = el.begin(), ei_end = el.end();
|
williamr@2
|
980 |
for (; ei != ei_end; ++ei) {
|
williamr@2
|
981 |
detail::erase_from_incidence_list
|
williamr@2
|
982 |
(g.out_edge_list((*ei).get_target()), u, Cat());
|
williamr@2
|
983 |
g.m_edges.erase((*ei).get_iter());
|
williamr@2
|
984 |
}
|
williamr@2
|
985 |
g.out_edge_list(u).clear();
|
williamr@2
|
986 |
}
|
williamr@2
|
987 |
// O(1) for allow_parallel_edge_tag
|
williamr@2
|
988 |
// O(log(E/V)) for disallow_parallel_edge_tag
|
williamr@2
|
989 |
template <class Config>
|
williamr@2
|
990 |
inline std::pair<typename Config::edge_descriptor, bool>
|
williamr@2
|
991 |
add_edge(typename Config::vertex_descriptor u,
|
williamr@2
|
992 |
typename Config::vertex_descriptor v,
|
williamr@2
|
993 |
const typename Config::edge_property_type& p,
|
williamr@2
|
994 |
undirected_graph_helper<Config>& g_)
|
williamr@2
|
995 |
{
|
williamr@2
|
996 |
typedef typename Config::StoredEdge StoredEdge;
|
williamr@2
|
997 |
typedef typename Config::edge_descriptor edge_descriptor;
|
williamr@2
|
998 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
999 |
graph_type& g = static_cast<graph_type&>(g_);
|
williamr@2
|
1000 |
|
williamr@2
|
1001 |
bool inserted;
|
williamr@2
|
1002 |
typename Config::EdgeContainer::value_type e(u, v, p);
|
williamr@2
|
1003 |
typename Config::EdgeContainer::iterator p_iter
|
williamr@2
|
1004 |
= graph_detail::push(g.m_edges, e).first;
|
williamr@2
|
1005 |
|
williamr@2
|
1006 |
typename Config::OutEdgeList::iterator i;
|
williamr@2
|
1007 |
boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
|
williamr@2
|
1008 |
StoredEdge(v, p_iter, &g.m_edges));
|
williamr@2
|
1009 |
if (inserted) {
|
williamr@2
|
1010 |
boost::graph_detail::push(g.out_edge_list(v), StoredEdge(u, p_iter, &g.m_edges));
|
williamr@2
|
1011 |
return std::make_pair(edge_descriptor(u, v, &p_iter->get_property()),
|
williamr@2
|
1012 |
true);
|
williamr@2
|
1013 |
} else {
|
williamr@2
|
1014 |
g.m_edges.erase(p_iter);
|
williamr@2
|
1015 |
return std::make_pair
|
williamr@2
|
1016 |
(edge_descriptor(u, v, &i->get_iter()->get_property()), false);
|
williamr@2
|
1017 |
}
|
williamr@2
|
1018 |
}
|
williamr@2
|
1019 |
template <class Config>
|
williamr@2
|
1020 |
inline std::pair<typename Config::edge_descriptor, bool>
|
williamr@2
|
1021 |
add_edge(typename Config::vertex_descriptor u,
|
williamr@2
|
1022 |
typename Config::vertex_descriptor v,
|
williamr@2
|
1023 |
undirected_graph_helper<Config>& g_)
|
williamr@2
|
1024 |
{
|
williamr@2
|
1025 |
typename Config::edge_property_type p;
|
williamr@2
|
1026 |
return add_edge(u, v, p, g_);
|
williamr@2
|
1027 |
}
|
williamr@2
|
1028 |
|
williamr@2
|
1029 |
// O(1)
|
williamr@2
|
1030 |
template <class Config>
|
williamr@2
|
1031 |
inline typename Config::degree_size_type
|
williamr@2
|
1032 |
degree(typename Config::vertex_descriptor u,
|
williamr@2
|
1033 |
const undirected_graph_helper<Config>& g_)
|
williamr@2
|
1034 |
{
|
williamr@2
|
1035 |
typedef typename Config::graph_type Graph;
|
williamr@2
|
1036 |
const Graph& g = static_cast<const Graph&>(g_);
|
williamr@2
|
1037 |
return out_degree(u, g);
|
williamr@2
|
1038 |
}
|
williamr@2
|
1039 |
|
williamr@2
|
1040 |
template <class Config>
|
williamr@2
|
1041 |
inline std::pair<typename Config::in_edge_iterator,
|
williamr@2
|
1042 |
typename Config::in_edge_iterator>
|
williamr@2
|
1043 |
in_edges(typename Config::vertex_descriptor u,
|
williamr@2
|
1044 |
const undirected_graph_helper<Config>& g_)
|
williamr@2
|
1045 |
{
|
williamr@2
|
1046 |
typedef typename Config::graph_type Graph;
|
williamr@2
|
1047 |
const Graph& cg = static_cast<const Graph&>(g_);
|
williamr@2
|
1048 |
Graph& g = const_cast<Graph&>(cg);
|
williamr@2
|
1049 |
typedef typename Config::in_edge_iterator in_edge_iterator;
|
williamr@2
|
1050 |
return
|
williamr@2
|
1051 |
std::make_pair(in_edge_iterator(g.out_edge_list(u).begin(), u),
|
williamr@2
|
1052 |
in_edge_iterator(g.out_edge_list(u).end(), u));
|
williamr@2
|
1053 |
}
|
williamr@2
|
1054 |
|
williamr@2
|
1055 |
template <class Config>
|
williamr@2
|
1056 |
inline typename Config::degree_size_type
|
williamr@2
|
1057 |
in_degree(typename Config::vertex_descriptor u,
|
williamr@2
|
1058 |
const undirected_graph_helper<Config>& g_)
|
williamr@2
|
1059 |
{ return degree(u, g_); }
|
williamr@2
|
1060 |
|
williamr@2
|
1061 |
//=========================================================================
|
williamr@2
|
1062 |
// Bidirectional Graph Helper Class
|
williamr@2
|
1063 |
|
williamr@2
|
1064 |
struct bidir_adj_list_traversal_tag :
|
williamr@2
|
1065 |
public virtual vertex_list_graph_tag,
|
williamr@2
|
1066 |
public virtual incidence_graph_tag,
|
williamr@2
|
1067 |
public virtual adjacency_graph_tag,
|
williamr@2
|
1068 |
public virtual edge_list_graph_tag,
|
williamr@2
|
1069 |
public virtual bidirectional_graph_tag { };
|
williamr@2
|
1070 |
|
williamr@2
|
1071 |
template <class Config>
|
williamr@2
|
1072 |
struct bidirectional_graph_helper
|
williamr@2
|
1073 |
: public directed_edges_helper<Config> {
|
williamr@2
|
1074 |
typedef bidir_adj_list_traversal_tag traversal_category;
|
williamr@2
|
1075 |
};
|
williamr@2
|
1076 |
|
williamr@2
|
1077 |
// Had to make these non-members to avoid accidental instantiation
|
williamr@2
|
1078 |
// on SGI MIPSpro C++
|
williamr@2
|
1079 |
template <class C>
|
williamr@2
|
1080 |
inline typename C::InEdgeList&
|
williamr@2
|
1081 |
in_edge_list(bidirectional_graph_helper<C>&,
|
williamr@2
|
1082 |
typename C::vertex_descriptor v)
|
williamr@2
|
1083 |
{
|
williamr@2
|
1084 |
typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
|
williamr@2
|
1085 |
return sv->m_in_edges;
|
williamr@2
|
1086 |
}
|
williamr@2
|
1087 |
template <class C>
|
williamr@2
|
1088 |
inline const typename C::InEdgeList&
|
williamr@2
|
1089 |
in_edge_list(const bidirectional_graph_helper<C>&,
|
williamr@2
|
1090 |
typename C::vertex_descriptor v) {
|
williamr@2
|
1091 |
typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
|
williamr@2
|
1092 |
return sv->m_in_edges;
|
williamr@2
|
1093 |
}
|
williamr@2
|
1094 |
|
williamr@2
|
1095 |
template <class Predicate, class Config>
|
williamr@2
|
1096 |
inline void
|
williamr@2
|
1097 |
remove_edge_if(Predicate pred, bidirectional_graph_helper<Config>& g_)
|
williamr@2
|
1098 |
{
|
williamr@2
|
1099 |
typedef typename Config::global_edgelist_selector EdgeListS;
|
williamr@2
|
1100 |
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
williamr@2
|
1101 |
|
williamr@2
|
1102 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
1103 |
graph_type& g = static_cast<graph_type&>(g_);
|
williamr@2
|
1104 |
typename Config::edge_iterator ei, ei_end, next;
|
williamr@2
|
1105 |
tie(ei, ei_end) = edges(g);
|
williamr@2
|
1106 |
for (next = ei; ei != ei_end; ei = next) {
|
williamr@2
|
1107 |
++next;
|
williamr@2
|
1108 |
if (pred(*ei))
|
williamr@2
|
1109 |
remove_edge(*ei, g);
|
williamr@2
|
1110 |
}
|
williamr@2
|
1111 |
}
|
williamr@2
|
1112 |
|
williamr@2
|
1113 |
template <class Config>
|
williamr@2
|
1114 |
inline std::pair<typename Config::in_edge_iterator,
|
williamr@2
|
1115 |
typename Config::in_edge_iterator>
|
williamr@2
|
1116 |
in_edges(typename Config::vertex_descriptor u,
|
williamr@2
|
1117 |
const bidirectional_graph_helper<Config>& g_)
|
williamr@2
|
1118 |
{
|
williamr@2
|
1119 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
1120 |
const graph_type& cg = static_cast<const graph_type&>(g_);
|
williamr@2
|
1121 |
graph_type& g = const_cast<graph_type&>(cg);
|
williamr@2
|
1122 |
typedef typename Config::in_edge_iterator in_edge_iterator;
|
williamr@2
|
1123 |
return
|
williamr@2
|
1124 |
std::make_pair(in_edge_iterator(in_edge_list(g, u).begin(), u),
|
williamr@2
|
1125 |
in_edge_iterator(in_edge_list(g, u).end(), u));
|
williamr@2
|
1126 |
}
|
williamr@2
|
1127 |
|
williamr@2
|
1128 |
// O(1)
|
williamr@2
|
1129 |
template <class Config>
|
williamr@2
|
1130 |
inline std::pair<typename Config::edge_iterator,
|
williamr@2
|
1131 |
typename Config::edge_iterator>
|
williamr@2
|
1132 |
edges(const bidirectional_graph_helper<Config>& g_)
|
williamr@2
|
1133 |
{
|
williamr@2
|
1134 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
1135 |
typedef typename Config::edge_iterator edge_iterator;
|
williamr@2
|
1136 |
const graph_type& cg = static_cast<const graph_type&>(g_);
|
williamr@2
|
1137 |
graph_type& g = const_cast<graph_type&>(cg);
|
williamr@2
|
1138 |
return std::make_pair( edge_iterator(g.m_edges.begin()),
|
williamr@2
|
1139 |
edge_iterator(g.m_edges.end()) );
|
williamr@2
|
1140 |
}
|
williamr@2
|
1141 |
|
williamr@2
|
1142 |
//=========================================================================
|
williamr@2
|
1143 |
// Bidirectional Graph Helper Class (with edge properties)
|
williamr@2
|
1144 |
|
williamr@2
|
1145 |
|
williamr@2
|
1146 |
template <class Config>
|
williamr@2
|
1147 |
struct bidirectional_graph_helper_with_property
|
williamr@2
|
1148 |
: public bidirectional_graph_helper<Config>
|
williamr@2
|
1149 |
{
|
williamr@2
|
1150 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
1151 |
typedef typename Config::out_edge_iterator out_edge_iterator;
|
williamr@2
|
1152 |
|
williamr@2
|
1153 |
std::pair<out_edge_iterator, out_edge_iterator>
|
williamr@2
|
1154 |
get_parallel_edge_sublist(typename Config::edge_descriptor e,
|
williamr@2
|
1155 |
const graph_type& g,
|
williamr@2
|
1156 |
void*)
|
williamr@2
|
1157 |
{ return out_edges(source(e, g), g); }
|
williamr@2
|
1158 |
|
williamr@2
|
1159 |
std::pair<out_edge_iterator, out_edge_iterator>
|
williamr@2
|
1160 |
get_parallel_edge_sublist(typename Config::edge_descriptor e,
|
williamr@2
|
1161 |
const graph_type& g,
|
williamr@2
|
1162 |
setS*)
|
williamr@2
|
1163 |
{ return edge_range(source(e, g), target(e, g), g); }
|
williamr@2
|
1164 |
|
williamr@2
|
1165 |
std::pair<out_edge_iterator, out_edge_iterator>
|
williamr@2
|
1166 |
get_parallel_edge_sublist(typename Config::edge_descriptor e,
|
williamr@2
|
1167 |
const graph_type& g,
|
williamr@2
|
1168 |
multisetS*)
|
williamr@2
|
1169 |
{ return edge_range(source(e, g), target(e, g), g); }
|
williamr@2
|
1170 |
|
williamr@2
|
1171 |
#if !defined BOOST_NO_HASH
|
williamr@2
|
1172 |
std::pair<out_edge_iterator, out_edge_iterator>
|
williamr@2
|
1173 |
get_parallel_edge_sublist(typename Config::edge_descriptor e,
|
williamr@2
|
1174 |
const graph_type& g,
|
williamr@2
|
1175 |
hash_setS*)
|
williamr@2
|
1176 |
{ return edge_range(source(e, g), target(e, g), g); }
|
williamr@2
|
1177 |
#endif
|
williamr@2
|
1178 |
|
williamr@2
|
1179 |
// Placement of these overloaded remove_edge() functions
|
williamr@2
|
1180 |
// inside the class avoids a VC++ bug.
|
williamr@2
|
1181 |
|
williamr@2
|
1182 |
// O(E/V) or O(log(E/V))
|
williamr@2
|
1183 |
void
|
williamr@2
|
1184 |
remove_edge(typename Config::edge_descriptor e)
|
williamr@2
|
1185 |
{
|
williamr@2
|
1186 |
typedef typename Config::global_edgelist_selector EdgeListS;
|
williamr@2
|
1187 |
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
williamr@2
|
1188 |
|
williamr@2
|
1189 |
graph_type& g = static_cast<graph_type&>(*this);
|
williamr@2
|
1190 |
|
williamr@2
|
1191 |
typedef typename Config::edgelist_selector OutEdgeListS;
|
williamr@2
|
1192 |
|
williamr@2
|
1193 |
std::pair<out_edge_iterator, out_edge_iterator> rng =
|
williamr@2
|
1194 |
get_parallel_edge_sublist(e, g, (OutEdgeListS*)(0));
|
williamr@2
|
1195 |
rng.first = std::find(rng.first, rng.second, e);
|
williamr@2
|
1196 |
assert(rng.first != rng.second);
|
williamr@2
|
1197 |
remove_edge(rng.first);
|
williamr@2
|
1198 |
}
|
williamr@2
|
1199 |
|
williamr@2
|
1200 |
inline void
|
williamr@2
|
1201 |
remove_edge(typename Config::out_edge_iterator iter)
|
williamr@2
|
1202 |
{
|
williamr@2
|
1203 |
typedef typename Config::global_edgelist_selector EdgeListS;
|
williamr@2
|
1204 |
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
williamr@2
|
1205 |
|
williamr@2
|
1206 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
1207 |
graph_type& g = static_cast<graph_type&>(*this);
|
williamr@2
|
1208 |
typename Config::edge_descriptor e = *iter;
|
williamr@2
|
1209 |
typename Config::OutEdgeList& oel = g.out_edge_list(source(e, g));
|
williamr@2
|
1210 |
typename Config::InEdgeList& iel = in_edge_list(g, target(e, g));
|
williamr@2
|
1211 |
typedef typename Config::OutEdgeList::value_type::property_type PType;
|
williamr@2
|
1212 |
PType& p = *(PType*)e.get_property();
|
williamr@2
|
1213 |
detail::remove_directed_edge_dispatch(*iter, iel, p);
|
williamr@2
|
1214 |
g.m_edges.erase(iter.base()->get_iter());
|
williamr@2
|
1215 |
oel.erase(iter.base());
|
williamr@2
|
1216 |
}
|
williamr@2
|
1217 |
};
|
williamr@2
|
1218 |
|
williamr@2
|
1219 |
// O(E/V) for allow_parallel_edge_tag
|
williamr@2
|
1220 |
// O(log(E/V)) for disallow_parallel_edge_tag
|
williamr@2
|
1221 |
template <class Config>
|
williamr@2
|
1222 |
inline void
|
williamr@2
|
1223 |
remove_edge(typename Config::vertex_descriptor u,
|
williamr@2
|
1224 |
typename Config::vertex_descriptor v,
|
williamr@2
|
1225 |
bidirectional_graph_helper_with_property<Config>& g_)
|
williamr@2
|
1226 |
{
|
williamr@2
|
1227 |
typedef typename Config::global_edgelist_selector EdgeListS;
|
williamr@2
|
1228 |
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
williamr@2
|
1229 |
|
williamr@2
|
1230 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
1231 |
graph_type& g = static_cast<graph_type&>(g_);
|
williamr@2
|
1232 |
typedef typename Config::edge_parallel_category Cat;
|
williamr@2
|
1233 |
detail::remove_edge_and_property(g, g.out_edge_list(u), v, Cat());
|
williamr@2
|
1234 |
detail::erase_from_incidence_list(in_edge_list(g, v), u, Cat());
|
williamr@2
|
1235 |
}
|
williamr@2
|
1236 |
|
williamr@2
|
1237 |
// O(E/V) or O(log(E/V))
|
williamr@2
|
1238 |
template <class EdgeOrIter, class Config>
|
williamr@2
|
1239 |
inline void
|
williamr@2
|
1240 |
remove_edge(EdgeOrIter e,
|
williamr@2
|
1241 |
bidirectional_graph_helper_with_property<Config>& g_)
|
williamr@2
|
1242 |
{
|
williamr@2
|
1243 |
typedef typename Config::global_edgelist_selector EdgeListS;
|
williamr@2
|
1244 |
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
williamr@2
|
1245 |
|
williamr@2
|
1246 |
g_.remove_edge(e);
|
williamr@2
|
1247 |
}
|
williamr@2
|
1248 |
|
williamr@2
|
1249 |
template <class Config, class Predicate>
|
williamr@2
|
1250 |
inline void
|
williamr@2
|
1251 |
remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
|
williamr@2
|
1252 |
bidirectional_graph_helper_with_property<Config>& g_)
|
williamr@2
|
1253 |
{
|
williamr@2
|
1254 |
typedef typename Config::global_edgelist_selector EdgeListS;
|
williamr@2
|
1255 |
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
williamr@2
|
1256 |
|
williamr@2
|
1257 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
1258 |
typedef typename Config::OutEdgeList::value_type::property_type PropT;
|
williamr@2
|
1259 |
graph_type& g = static_cast<graph_type&>(g_);
|
williamr@2
|
1260 |
|
williamr@2
|
1261 |
typedef typename Config::EdgeIter EdgeIter;
|
williamr@2
|
1262 |
typedef std::vector<EdgeIter> Garbage;
|
williamr@2
|
1263 |
Garbage garbage;
|
williamr@2
|
1264 |
|
williamr@2
|
1265 |
// First remove the edges from the targets' in-edge lists and
|
williamr@2
|
1266 |
// from the graph's edge set list.
|
williamr@2
|
1267 |
typename Config::out_edge_iterator out_i, out_end;
|
williamr@2
|
1268 |
for (tie(out_i, out_end) = out_edges(u, g); out_i != out_end; ++out_i)
|
williamr@2
|
1269 |
if (pred(*out_i)) {
|
williamr@2
|
1270 |
detail::remove_directed_edge_dispatch
|
williamr@2
|
1271 |
(*out_i, in_edge_list(g, target(*out_i, g)),
|
williamr@2
|
1272 |
*(PropT*)(*out_i).get_property());
|
williamr@2
|
1273 |
// Put in garbage to delete later. Will need the properties
|
williamr@2
|
1274 |
// for the remove_if of the out-edges.
|
williamr@2
|
1275 |
garbage.push_back((*out_i.base()).get_iter());
|
williamr@2
|
1276 |
}
|
williamr@2
|
1277 |
|
williamr@2
|
1278 |
// Now remove the edges from this out-edge list.
|
williamr@2
|
1279 |
typename Config::out_edge_iterator first, last;
|
williamr@2
|
1280 |
tie(first, last) = out_edges(u, g);
|
williamr@2
|
1281 |
typedef typename Config::edge_parallel_category Cat;
|
williamr@2
|
1282 |
detail::remove_directed_edge_if_dispatch
|
williamr@2
|
1283 |
(first, last, g.out_edge_list(u), pred, Cat());
|
williamr@2
|
1284 |
|
williamr@2
|
1285 |
// Now delete the edge properties from the g.m_edges list
|
williamr@2
|
1286 |
for (typename Garbage::iterator i = garbage.begin();
|
williamr@2
|
1287 |
i != garbage.end(); ++i)
|
williamr@2
|
1288 |
g.m_edges.erase(*i);
|
williamr@2
|
1289 |
}
|
williamr@2
|
1290 |
template <class Config, class Predicate>
|
williamr@2
|
1291 |
inline void
|
williamr@2
|
1292 |
remove_in_edge_if(typename Config::vertex_descriptor v, Predicate pred,
|
williamr@2
|
1293 |
bidirectional_graph_helper_with_property<Config>& g_)
|
williamr@2
|
1294 |
{
|
williamr@2
|
1295 |
typedef typename Config::global_edgelist_selector EdgeListS;
|
williamr@2
|
1296 |
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
williamr@2
|
1297 |
|
williamr@2
|
1298 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
1299 |
typedef typename Config::OutEdgeList::value_type::property_type PropT;
|
williamr@2
|
1300 |
graph_type& g = static_cast<graph_type&>(g_);
|
williamr@2
|
1301 |
|
williamr@2
|
1302 |
typedef typename Config::EdgeIter EdgeIter;
|
williamr@2
|
1303 |
typedef std::vector<EdgeIter> Garbage;
|
williamr@2
|
1304 |
Garbage garbage;
|
williamr@2
|
1305 |
|
williamr@2
|
1306 |
// First remove the edges from the sources' out-edge lists and
|
williamr@2
|
1307 |
// from the graph's edge set list.
|
williamr@2
|
1308 |
typename Config::in_edge_iterator in_i, in_end;
|
williamr@2
|
1309 |
for (tie(in_i, in_end) = in_edges(v, g); in_i != in_end; ++in_i)
|
williamr@2
|
1310 |
if (pred(*in_i)) {
|
williamr@2
|
1311 |
typename Config::vertex_descriptor u = source(*in_i, g);
|
williamr@2
|
1312 |
detail::remove_directed_edge_dispatch
|
williamr@2
|
1313 |
(*in_i, g.out_edge_list(u), *(PropT*)(*in_i).get_property());
|
williamr@2
|
1314 |
// Put in garbage to delete later. Will need the properties
|
williamr@2
|
1315 |
// for the remove_if of the out-edges.
|
williamr@2
|
1316 |
garbage.push_back((*in_i.base()).get_iter());
|
williamr@2
|
1317 |
}
|
williamr@2
|
1318 |
// Now remove the edges from this in-edge list.
|
williamr@2
|
1319 |
typename Config::in_edge_iterator first, last;
|
williamr@2
|
1320 |
tie(first, last) = in_edges(v, g);
|
williamr@2
|
1321 |
typedef typename Config::edge_parallel_category Cat;
|
williamr@2
|
1322 |
detail::remove_directed_edge_if_dispatch
|
williamr@2
|
1323 |
(first, last, in_edge_list(g, v), pred, Cat());
|
williamr@2
|
1324 |
|
williamr@2
|
1325 |
// Now delete the edge properties from the g.m_edges list
|
williamr@2
|
1326 |
for (typename Garbage::iterator i = garbage.begin();
|
williamr@2
|
1327 |
i != garbage.end(); ++i)
|
williamr@2
|
1328 |
g.m_edges.erase(*i);
|
williamr@2
|
1329 |
}
|
williamr@2
|
1330 |
|
williamr@2
|
1331 |
// O(1)
|
williamr@2
|
1332 |
template <class Config>
|
williamr@2
|
1333 |
inline typename Config::edges_size_type
|
williamr@2
|
1334 |
num_edges(const bidirectional_graph_helper_with_property<Config>& g_)
|
williamr@2
|
1335 |
{
|
williamr@2
|
1336 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
1337 |
const graph_type& g = static_cast<const graph_type&>(g_);
|
williamr@2
|
1338 |
return g.m_edges.size();
|
williamr@2
|
1339 |
}
|
williamr@2
|
1340 |
// O(E/V * E/V) for allow_parallel_edge_tag
|
williamr@2
|
1341 |
// O(E/V * log(E/V)) for disallow_parallel_edge_tag
|
williamr@2
|
1342 |
template <class Config>
|
williamr@2
|
1343 |
inline void
|
williamr@2
|
1344 |
clear_vertex(typename Config::vertex_descriptor u,
|
williamr@2
|
1345 |
bidirectional_graph_helper_with_property<Config>& g_)
|
williamr@2
|
1346 |
{
|
williamr@2
|
1347 |
typedef typename Config::global_edgelist_selector EdgeListS;
|
williamr@2
|
1348 |
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
williamr@2
|
1349 |
|
williamr@2
|
1350 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
1351 |
typedef typename Config::edge_parallel_category Cat;
|
williamr@2
|
1352 |
graph_type& g = static_cast<graph_type&>(g_);
|
williamr@2
|
1353 |
typename Config::OutEdgeList& el = g.out_edge_list(u);
|
williamr@2
|
1354 |
typename Config::OutEdgeList::iterator
|
williamr@2
|
1355 |
ei = el.begin(), ei_end = el.end();
|
williamr@2
|
1356 |
for (; ei != ei_end; ++ei) {
|
williamr@2
|
1357 |
detail::erase_from_incidence_list
|
williamr@2
|
1358 |
(in_edge_list(g, (*ei).get_target()), u, Cat());
|
williamr@2
|
1359 |
g.m_edges.erase((*ei).get_iter());
|
williamr@2
|
1360 |
}
|
williamr@2
|
1361 |
typename Config::InEdgeList& in_el = in_edge_list(g, u);
|
williamr@2
|
1362 |
typename Config::InEdgeList::iterator
|
williamr@2
|
1363 |
in_ei = in_el.begin(), in_ei_end = in_el.end();
|
williamr@2
|
1364 |
for (; in_ei != in_ei_end; ++in_ei) {
|
williamr@2
|
1365 |
detail::erase_from_incidence_list
|
williamr@2
|
1366 |
(g.out_edge_list((*in_ei).get_target()), u, Cat());
|
williamr@2
|
1367 |
g.m_edges.erase((*in_ei).get_iter());
|
williamr@2
|
1368 |
}
|
williamr@2
|
1369 |
g.out_edge_list(u).clear();
|
williamr@2
|
1370 |
in_edge_list(g, u).clear();
|
williamr@2
|
1371 |
}
|
williamr@2
|
1372 |
|
williamr@2
|
1373 |
template <class Config>
|
williamr@2
|
1374 |
inline void
|
williamr@2
|
1375 |
clear_out_edges(typename Config::vertex_descriptor u,
|
williamr@2
|
1376 |
bidirectional_graph_helper_with_property<Config>& g_)
|
williamr@2
|
1377 |
{
|
williamr@2
|
1378 |
typedef typename Config::global_edgelist_selector EdgeListS;
|
williamr@2
|
1379 |
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
williamr@2
|
1380 |
|
williamr@2
|
1381 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
1382 |
typedef typename Config::edge_parallel_category Cat;
|
williamr@2
|
1383 |
graph_type& g = static_cast<graph_type&>(g_);
|
williamr@2
|
1384 |
typename Config::OutEdgeList& el = g.out_edge_list(u);
|
williamr@2
|
1385 |
typename Config::OutEdgeList::iterator
|
williamr@2
|
1386 |
ei = el.begin(), ei_end = el.end();
|
williamr@2
|
1387 |
for (; ei != ei_end; ++ei) {
|
williamr@2
|
1388 |
detail::erase_from_incidence_list
|
williamr@2
|
1389 |
(in_edge_list(g, (*ei).get_target()), u, Cat());
|
williamr@2
|
1390 |
g.m_edges.erase((*ei).get_iter());
|
williamr@2
|
1391 |
}
|
williamr@2
|
1392 |
g.out_edge_list(u).clear();
|
williamr@2
|
1393 |
}
|
williamr@2
|
1394 |
|
williamr@2
|
1395 |
template <class Config>
|
williamr@2
|
1396 |
inline void
|
williamr@2
|
1397 |
clear_in_edges(typename Config::vertex_descriptor u,
|
williamr@2
|
1398 |
bidirectional_graph_helper_with_property<Config>& g_)
|
williamr@2
|
1399 |
{
|
williamr@2
|
1400 |
typedef typename Config::global_edgelist_selector EdgeListS;
|
williamr@2
|
1401 |
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
williamr@2
|
1402 |
|
williamr@2
|
1403 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
1404 |
typedef typename Config::edge_parallel_category Cat;
|
williamr@2
|
1405 |
graph_type& g = static_cast<graph_type&>(g_);
|
williamr@2
|
1406 |
typename Config::InEdgeList& in_el = in_edge_list(g, u);
|
williamr@2
|
1407 |
typename Config::InEdgeList::iterator
|
williamr@2
|
1408 |
in_ei = in_el.begin(), in_ei_end = in_el.end();
|
williamr@2
|
1409 |
for (; in_ei != in_ei_end; ++in_ei) {
|
williamr@2
|
1410 |
detail::erase_from_incidence_list
|
williamr@2
|
1411 |
(g.out_edge_list((*in_ei).get_target()), u, Cat());
|
williamr@2
|
1412 |
g.m_edges.erase((*in_ei).get_iter());
|
williamr@2
|
1413 |
}
|
williamr@2
|
1414 |
in_edge_list(g, u).clear();
|
williamr@2
|
1415 |
}
|
williamr@2
|
1416 |
|
williamr@2
|
1417 |
// O(1) for allow_parallel_edge_tag
|
williamr@2
|
1418 |
// O(log(E/V)) for disallow_parallel_edge_tag
|
williamr@2
|
1419 |
template <class Config>
|
williamr@2
|
1420 |
inline std::pair<typename Config::edge_descriptor, bool>
|
williamr@2
|
1421 |
add_edge(typename Config::vertex_descriptor u,
|
williamr@2
|
1422 |
typename Config::vertex_descriptor v,
|
williamr@2
|
1423 |
const typename Config::edge_property_type& p,
|
williamr@2
|
1424 |
bidirectional_graph_helper_with_property<Config>& g_)
|
williamr@2
|
1425 |
{
|
williamr@2
|
1426 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
1427 |
graph_type& g = static_cast<graph_type&>(g_);
|
williamr@2
|
1428 |
typedef typename Config::edge_descriptor edge_descriptor;
|
williamr@2
|
1429 |
typedef typename Config::StoredEdge StoredEdge;
|
williamr@2
|
1430 |
bool inserted;
|
williamr@2
|
1431 |
typename Config::EdgeContainer::value_type e(u, v, p);
|
williamr@2
|
1432 |
typename Config::EdgeContainer::iterator p_iter
|
williamr@2
|
1433 |
= graph_detail::push(g.m_edges, e).first;
|
williamr@2
|
1434 |
typename Config::OutEdgeList::iterator i;
|
williamr@2
|
1435 |
boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
|
williamr@2
|
1436 |
StoredEdge(v, p_iter, &g.m_edges));
|
williamr@2
|
1437 |
if (inserted) {
|
williamr@2
|
1438 |
boost::graph_detail::push(in_edge_list(g, v), StoredEdge(u, p_iter, &g.m_edges));
|
williamr@2
|
1439 |
return std::make_pair(edge_descriptor(u, v, &p_iter->m_property),
|
williamr@2
|
1440 |
true);
|
williamr@2
|
1441 |
} else {
|
williamr@2
|
1442 |
g.m_edges.erase(p_iter);
|
williamr@2
|
1443 |
return std::make_pair(edge_descriptor(u, v,
|
williamr@2
|
1444 |
&i->get_iter()->get_property()),
|
williamr@2
|
1445 |
false);
|
williamr@2
|
1446 |
}
|
williamr@2
|
1447 |
}
|
williamr@2
|
1448 |
|
williamr@2
|
1449 |
template <class Config>
|
williamr@2
|
1450 |
inline std::pair<typename Config::edge_descriptor, bool>
|
williamr@2
|
1451 |
add_edge(typename Config::vertex_descriptor u,
|
williamr@2
|
1452 |
typename Config::vertex_descriptor v,
|
williamr@2
|
1453 |
bidirectional_graph_helper_with_property<Config>& g_)
|
williamr@2
|
1454 |
{
|
williamr@2
|
1455 |
typename Config::edge_property_type p;
|
williamr@2
|
1456 |
return add_edge(u, v, p, g_);
|
williamr@2
|
1457 |
}
|
williamr@2
|
1458 |
// O(1)
|
williamr@2
|
1459 |
template <class Config>
|
williamr@2
|
1460 |
inline typename Config::degree_size_type
|
williamr@2
|
1461 |
degree(typename Config::vertex_descriptor u,
|
williamr@2
|
1462 |
const bidirectional_graph_helper_with_property<Config>& g_)
|
williamr@2
|
1463 |
{
|
williamr@2
|
1464 |
typedef typename Config::graph_type graph_type;
|
williamr@2
|
1465 |
const graph_type& g = static_cast<const graph_type&>(g_);
|
williamr@2
|
1466 |
return in_degree(u, g) + out_degree(u, g);
|
williamr@2
|
1467 |
}
|
williamr@2
|
1468 |
|
williamr@2
|
1469 |
//=========================================================================
|
williamr@2
|
1470 |
// Adjacency List Helper Class
|
williamr@2
|
1471 |
|
williamr@2
|
1472 |
template <class Config, class Base>
|
williamr@2
|
1473 |
struct adj_list_helper : public Base
|
williamr@2
|
1474 |
{
|
williamr@2
|
1475 |
typedef typename Config::graph_type AdjList;
|
williamr@2
|
1476 |
typedef typename Config::vertex_descriptor vertex_descriptor;
|
williamr@2
|
1477 |
typedef typename Config::edge_descriptor edge_descriptor;
|
williamr@2
|
1478 |
typedef typename Config::out_edge_iterator out_edge_iterator;
|
williamr@2
|
1479 |
typedef typename Config::in_edge_iterator in_edge_iterator;
|
williamr@2
|
1480 |
typedef typename Config::adjacency_iterator adjacency_iterator;
|
williamr@2
|
1481 |
typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator;
|
williamr@2
|
1482 |
typedef typename Config::vertex_iterator vertex_iterator;
|
williamr@2
|
1483 |
typedef typename Config::edge_iterator edge_iterator;
|
williamr@2
|
1484 |
typedef typename Config::directed_category directed_category;
|
williamr@2
|
1485 |
typedef typename Config::edge_parallel_category edge_parallel_category;
|
williamr@2
|
1486 |
typedef typename Config::vertices_size_type vertices_size_type;
|
williamr@2
|
1487 |
typedef typename Config::edges_size_type edges_size_type;
|
williamr@2
|
1488 |
typedef typename Config::degree_size_type degree_size_type;
|
williamr@2
|
1489 |
typedef typename Config::StoredEdge StoredEdge;
|
williamr@2
|
1490 |
typedef typename Config::edge_property_type edge_property_type;
|
williamr@2
|
1491 |
|
williamr@2
|
1492 |
typedef typename Config::global_edgelist_selector
|
williamr@2
|
1493 |
global_edgelist_selector;
|
williamr@2
|
1494 |
|
williamr@2
|
1495 |
// protected:
|
williamr@2
|
1496 |
|
williamr@2
|
1497 |
// The edge_dispatch() functions should be static, but
|
williamr@2
|
1498 |
// Borland gets confused about constness.
|
williamr@2
|
1499 |
|
williamr@2
|
1500 |
// O(E/V)
|
williamr@2
|
1501 |
inline std::pair<edge_descriptor,bool>
|
williamr@2
|
1502 |
edge_dispatch(const AdjList& g,
|
williamr@2
|
1503 |
vertex_descriptor u, vertex_descriptor v,
|
williamr@2
|
1504 |
boost::allow_parallel_edge_tag) const
|
williamr@2
|
1505 |
{
|
williamr@2
|
1506 |
bool found;
|
williamr@2
|
1507 |
const typename Config::OutEdgeList& el = g.out_edge_list(u);
|
williamr@2
|
1508 |
typename Config::OutEdgeList::const_iterator
|
williamr@2
|
1509 |
i = std::find_if(el.begin(), el.end(),
|
williamr@2
|
1510 |
detail::target_is<vertex_descriptor>(v));
|
williamr@2
|
1511 |
found = (i != g.out_edge_list(u).end());
|
williamr@2
|
1512 |
if (found)
|
williamr@2
|
1513 |
return std::make_pair(edge_descriptor(u, v, &(*i).get_property()),
|
williamr@2
|
1514 |
true);
|
williamr@2
|
1515 |
else
|
williamr@2
|
1516 |
return std::make_pair(edge_descriptor(u, v, 0), false);
|
williamr@2
|
1517 |
}
|
williamr@2
|
1518 |
// O(log(E/V))
|
williamr@2
|
1519 |
inline std::pair<edge_descriptor,bool>
|
williamr@2
|
1520 |
edge_dispatch(const AdjList& g,
|
williamr@2
|
1521 |
vertex_descriptor u, vertex_descriptor v,
|
williamr@2
|
1522 |
boost::disallow_parallel_edge_tag) const
|
williamr@2
|
1523 |
{
|
williamr@2
|
1524 |
bool found;
|
williamr@2
|
1525 |
/* According to the standard, this should be iterator, not const_iterator,
|
williamr@2
|
1526 |
but the VC++ std::set::find() const returns const_iterator.
|
williamr@2
|
1527 |
And since iterator should be convertible to const_iterator, the
|
williamr@2
|
1528 |
following should work everywhere. -Jeremy */
|
williamr@2
|
1529 |
typename Config::OutEdgeList::const_iterator
|
williamr@2
|
1530 |
i = g.out_edge_list(u).find(StoredEdge(v)),
|
williamr@2
|
1531 |
end = g.out_edge_list(u).end();
|
williamr@2
|
1532 |
found = (i != end);
|
williamr@2
|
1533 |
if (found)
|
williamr@2
|
1534 |
return std::make_pair(edge_descriptor(u, v, &(*i).get_property()),
|
williamr@2
|
1535 |
true);
|
williamr@2
|
1536 |
else
|
williamr@2
|
1537 |
return std::make_pair(edge_descriptor(u, v, 0), false);
|
williamr@2
|
1538 |
}
|
williamr@2
|
1539 |
};
|
williamr@2
|
1540 |
|
williamr@2
|
1541 |
template <class Config, class Base>
|
williamr@2
|
1542 |
inline std::pair<typename Config::adjacency_iterator,
|
williamr@2
|
1543 |
typename Config::adjacency_iterator>
|
williamr@2
|
1544 |
adjacent_vertices(typename Config::vertex_descriptor u,
|
williamr@2
|
1545 |
const adj_list_helper<Config, Base>& g_)
|
williamr@2
|
1546 |
{
|
williamr@2
|
1547 |
typedef typename Config::graph_type AdjList;
|
williamr@2
|
1548 |
const AdjList& cg = static_cast<const AdjList&>(g_);
|
williamr@2
|
1549 |
AdjList& g = const_cast<AdjList&>(cg);
|
williamr@2
|
1550 |
typedef typename Config::adjacency_iterator adjacency_iterator;
|
williamr@2
|
1551 |
typename Config::out_edge_iterator first, last;
|
williamr@2
|
1552 |
boost::tie(first, last) = out_edges(u, g);
|
williamr@2
|
1553 |
return std::make_pair(adjacency_iterator(first, &g),
|
williamr@2
|
1554 |
adjacency_iterator(last, &g));
|
williamr@2
|
1555 |
}
|
williamr@2
|
1556 |
template <class Config, class Base>
|
williamr@2
|
1557 |
inline std::pair<typename Config::inv_adjacency_iterator,
|
williamr@2
|
1558 |
typename Config::inv_adjacency_iterator>
|
williamr@2
|
1559 |
inv_adjacent_vertices(typename Config::vertex_descriptor u,
|
williamr@2
|
1560 |
const adj_list_helper<Config, Base>& g_)
|
williamr@2
|
1561 |
{
|
williamr@2
|
1562 |
typedef typename Config::graph_type AdjList;
|
williamr@2
|
1563 |
const AdjList& cg = static_cast<const AdjList&>(g_);
|
williamr@2
|
1564 |
AdjList& g = const_cast<AdjList&>(cg);
|
williamr@2
|
1565 |
typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator;
|
williamr@2
|
1566 |
typename Config::in_edge_iterator first, last;
|
williamr@2
|
1567 |
boost::tie(first, last) = in_edges(u, g);
|
williamr@2
|
1568 |
return std::make_pair(inv_adjacency_iterator(first, &g),
|
williamr@2
|
1569 |
inv_adjacency_iterator(last, &g));
|
williamr@2
|
1570 |
}
|
williamr@2
|
1571 |
template <class Config, class Base>
|
williamr@2
|
1572 |
inline std::pair<typename Config::out_edge_iterator,
|
williamr@2
|
1573 |
typename Config::out_edge_iterator>
|
williamr@2
|
1574 |
out_edges(typename Config::vertex_descriptor u,
|
williamr@2
|
1575 |
const adj_list_helper<Config, Base>& g_)
|
williamr@2
|
1576 |
{
|
williamr@2
|
1577 |
typedef typename Config::graph_type AdjList;
|
williamr@2
|
1578 |
typedef typename Config::out_edge_iterator out_edge_iterator;
|
williamr@2
|
1579 |
const AdjList& cg = static_cast<const AdjList&>(g_);
|
williamr@2
|
1580 |
AdjList& g = const_cast<AdjList&>(cg);
|
williamr@2
|
1581 |
return
|
williamr@2
|
1582 |
std::make_pair(out_edge_iterator(g.out_edge_list(u).begin(), u),
|
williamr@2
|
1583 |
out_edge_iterator(g.out_edge_list(u).end(), u));
|
williamr@2
|
1584 |
}
|
williamr@2
|
1585 |
template <class Config, class Base>
|
williamr@2
|
1586 |
inline std::pair<typename Config::vertex_iterator,
|
williamr@2
|
1587 |
typename Config::vertex_iterator>
|
williamr@2
|
1588 |
vertices(const adj_list_helper<Config, Base>& g_)
|
williamr@2
|
1589 |
{
|
williamr@2
|
1590 |
typedef typename Config::graph_type AdjList;
|
williamr@2
|
1591 |
const AdjList& cg = static_cast<const AdjList&>(g_);
|
williamr@2
|
1592 |
AdjList& g = const_cast<AdjList&>(cg);
|
williamr@2
|
1593 |
return std::make_pair( g.vertex_set().begin(), g.vertex_set().end() );
|
williamr@2
|
1594 |
}
|
williamr@2
|
1595 |
template <class Config, class Base>
|
williamr@2
|
1596 |
inline typename Config::vertices_size_type
|
williamr@2
|
1597 |
num_vertices(const adj_list_helper<Config, Base>& g_)
|
williamr@2
|
1598 |
{
|
williamr@2
|
1599 |
typedef typename Config::graph_type AdjList;
|
williamr@2
|
1600 |
const AdjList& g = static_cast<const AdjList&>(g_);
|
williamr@2
|
1601 |
return g.vertex_set().size();
|
williamr@2
|
1602 |
}
|
williamr@2
|
1603 |
template <class Config, class Base>
|
williamr@2
|
1604 |
inline typename Config::degree_size_type
|
williamr@2
|
1605 |
out_degree(typename Config::vertex_descriptor u,
|
williamr@2
|
1606 |
const adj_list_helper<Config, Base>& g_)
|
williamr@2
|
1607 |
{
|
williamr@2
|
1608 |
typedef typename Config::graph_type AdjList;
|
williamr@2
|
1609 |
const AdjList& g = static_cast<const AdjList&>(g_);
|
williamr@2
|
1610 |
return g.out_edge_list(u).size();
|
williamr@2
|
1611 |
}
|
williamr@2
|
1612 |
template <class Config, class Base>
|
williamr@2
|
1613 |
inline std::pair<typename Config::edge_descriptor, bool>
|
williamr@2
|
1614 |
edge(typename Config::vertex_descriptor u,
|
williamr@2
|
1615 |
typename Config::vertex_descriptor v,
|
williamr@2
|
1616 |
const adj_list_helper<Config, Base>& g_)
|
williamr@2
|
1617 |
{
|
williamr@2
|
1618 |
typedef typename Config::graph_type Graph;
|
williamr@2
|
1619 |
typedef typename Config::edge_parallel_category Cat;
|
williamr@2
|
1620 |
const Graph& g = static_cast<const Graph&>(g_);
|
williamr@2
|
1621 |
return g_.edge_dispatch(g, u, v, Cat());
|
williamr@2
|
1622 |
}
|
williamr@2
|
1623 |
template <class Config, class Base>
|
williamr@2
|
1624 |
inline std::pair<typename Config::out_edge_iterator,
|
williamr@2
|
1625 |
typename Config::out_edge_iterator>
|
williamr@2
|
1626 |
edge_range(typename Config::vertex_descriptor u,
|
williamr@2
|
1627 |
typename Config::vertex_descriptor v,
|
williamr@2
|
1628 |
const adj_list_helper<Config, Base>& g_)
|
williamr@2
|
1629 |
{
|
williamr@2
|
1630 |
typedef typename Config::graph_type Graph;
|
williamr@2
|
1631 |
typedef typename Config::StoredEdge StoredEdge;
|
williamr@2
|
1632 |
const Graph& cg = static_cast<const Graph&>(g_);
|
williamr@2
|
1633 |
Graph& g = const_cast<Graph&>(cg);
|
williamr@2
|
1634 |
typedef typename Config::out_edge_iterator out_edge_iterator;
|
williamr@2
|
1635 |
typename Config::OutEdgeList& el = g.out_edge_list(u);
|
williamr@2
|
1636 |
typename Config::OutEdgeList::iterator first, last;
|
williamr@2
|
1637 |
typename Config::EdgeContainer fake_edge_container;
|
williamr@2
|
1638 |
tie(first, last) =
|
williamr@2
|
1639 |
std::equal_range(el.begin(), el.end(),
|
williamr@2
|
1640 |
StoredEdge(v, fake_edge_container.end(),
|
williamr@2
|
1641 |
&fake_edge_container));
|
williamr@2
|
1642 |
return std::make_pair(out_edge_iterator(first, u),
|
williamr@2
|
1643 |
out_edge_iterator(last, u));
|
williamr@2
|
1644 |
}
|
williamr@2
|
1645 |
|
williamr@2
|
1646 |
template <class Config>
|
williamr@2
|
1647 |
inline typename Config::degree_size_type
|
williamr@2
|
1648 |
in_degree(typename Config::vertex_descriptor u,
|
williamr@2
|
1649 |
const directed_edges_helper<Config>& g_)
|
williamr@2
|
1650 |
{
|
williamr@2
|
1651 |
typedef typename Config::graph_type Graph;
|
williamr@2
|
1652 |
const Graph& cg = static_cast<const Graph&>(g_);
|
williamr@2
|
1653 |
Graph& g = const_cast<Graph&>(cg);
|
williamr@2
|
1654 |
return in_edge_list(g, u).size();
|
williamr@2
|
1655 |
}
|
williamr@2
|
1656 |
|
williamr@2
|
1657 |
namespace detail {
|
williamr@2
|
1658 |
template <class Config, class Base, class Property>
|
williamr@2
|
1659 |
inline
|
williamr@2
|
1660 |
typename boost::property_map<typename Config::graph_type,
|
williamr@2
|
1661 |
Property>::type
|
williamr@2
|
1662 |
get_dispatch(adj_list_helper<Config,Base>&, Property,
|
williamr@2
|
1663 |
boost::edge_property_tag) {
|
williamr@2
|
1664 |
typedef typename Config::graph_type Graph;
|
williamr@2
|
1665 |
typedef typename boost::property_map<Graph, Property>::type PA;
|
williamr@2
|
1666 |
return PA();
|
williamr@2
|
1667 |
}
|
williamr@2
|
1668 |
template <class Config, class Base, class Property>
|
williamr@2
|
1669 |
inline
|
williamr@2
|
1670 |
typename boost::property_map<typename Config::graph_type,
|
williamr@2
|
1671 |
Property>::const_type
|
williamr@2
|
1672 |
get_dispatch(const adj_list_helper<Config,Base>&, Property,
|
williamr@2
|
1673 |
boost::edge_property_tag) {
|
williamr@2
|
1674 |
typedef typename Config::graph_type Graph;
|
williamr@2
|
1675 |
typedef typename boost::property_map<Graph, Property>::const_type PA;
|
williamr@2
|
1676 |
return PA();
|
williamr@2
|
1677 |
}
|
williamr@2
|
1678 |
|
williamr@2
|
1679 |
template <class Config, class Base, class Property>
|
williamr@2
|
1680 |
inline
|
williamr@2
|
1681 |
typename boost::property_map<typename Config::graph_type,
|
williamr@2
|
1682 |
Property>::type
|
williamr@2
|
1683 |
get_dispatch(adj_list_helper<Config,Base>& g, Property,
|
williamr@2
|
1684 |
boost::vertex_property_tag) {
|
williamr@2
|
1685 |
typedef typename Config::graph_type Graph;
|
williamr@2
|
1686 |
typedef typename boost::property_map<Graph, Property>::type PA;
|
williamr@2
|
1687 |
return PA(&static_cast<Graph&>(g));
|
williamr@2
|
1688 |
}
|
williamr@2
|
1689 |
template <class Config, class Base, class Property>
|
williamr@2
|
1690 |
inline
|
williamr@2
|
1691 |
typename boost::property_map<typename Config::graph_type,
|
williamr@2
|
1692 |
Property>::const_type
|
williamr@2
|
1693 |
get_dispatch(const adj_list_helper<Config, Base>& g, Property,
|
williamr@2
|
1694 |
boost::vertex_property_tag) {
|
williamr@2
|
1695 |
typedef typename Config::graph_type Graph;
|
williamr@2
|
1696 |
typedef typename boost::property_map<Graph, Property>::const_type PA;
|
williamr@2
|
1697 |
const Graph& cg = static_cast<const Graph&>(g);
|
williamr@2
|
1698 |
return PA(&cg);
|
williamr@2
|
1699 |
}
|
williamr@2
|
1700 |
|
williamr@2
|
1701 |
} // namespace detail
|
williamr@2
|
1702 |
|
williamr@2
|
1703 |
// Implementation of the PropertyGraph interface
|
williamr@2
|
1704 |
template <class Config, class Base, class Property>
|
williamr@2
|
1705 |
inline
|
williamr@2
|
1706 |
typename boost::property_map<typename Config::graph_type, Property>::type
|
williamr@2
|
1707 |
get(Property p, adj_list_helper<Config, Base>& g) {
|
williamr@2
|
1708 |
typedef typename property_kind<Property>::type Kind;
|
williamr@2
|
1709 |
return detail::get_dispatch(g, p, Kind());
|
williamr@2
|
1710 |
}
|
williamr@2
|
1711 |
template <class Config, class Base, class Property>
|
williamr@2
|
1712 |
inline
|
williamr@2
|
1713 |
typename boost::property_map<typename Config::graph_type,
|
williamr@2
|
1714 |
Property>::const_type
|
williamr@2
|
1715 |
get(Property p, const adj_list_helper<Config, Base>& g) {
|
williamr@2
|
1716 |
typedef typename property_kind<Property>::type Kind;
|
williamr@2
|
1717 |
return detail::get_dispatch(g, p, Kind());
|
williamr@2
|
1718 |
}
|
williamr@2
|
1719 |
|
williamr@2
|
1720 |
template <class Config, class Base, class Property, class Key>
|
williamr@2
|
1721 |
inline
|
williamr@2
|
1722 |
typename boost::property_traits<
|
williamr@2
|
1723 |
typename boost::property_map<typename Config::graph_type,
|
williamr@2
|
1724 |
Property>::type
|
williamr@2
|
1725 |
>::reference
|
williamr@2
|
1726 |
get(Property p, adj_list_helper<Config, Base>& g, const Key& key) {
|
williamr@2
|
1727 |
return get(get(p, g), key);
|
williamr@2
|
1728 |
}
|
williamr@2
|
1729 |
|
williamr@2
|
1730 |
template <class Config, class Base, class Property, class Key>
|
williamr@2
|
1731 |
inline
|
williamr@2
|
1732 |
typename boost::property_traits<
|
williamr@2
|
1733 |
typename boost::property_map<typename Config::graph_type,
|
williamr@2
|
1734 |
Property>::const_type
|
williamr@2
|
1735 |
>::reference
|
williamr@2
|
1736 |
get(Property p, const adj_list_helper<Config, Base>& g, const Key& key) {
|
williamr@2
|
1737 |
return get(get(p, g), key);
|
williamr@2
|
1738 |
}
|
williamr@2
|
1739 |
|
williamr@2
|
1740 |
template <class Config, class Base, class Property, class Key,class Value>
|
williamr@2
|
1741 |
inline void
|
williamr@2
|
1742 |
put(Property p, adj_list_helper<Config, Base>& g,
|
williamr@2
|
1743 |
const Key& key, const Value& value)
|
williamr@2
|
1744 |
{
|
williamr@2
|
1745 |
typedef typename Config::graph_type Graph;
|
williamr@2
|
1746 |
typedef typename boost::property_map<Graph, Property>::type Map;
|
williamr@2
|
1747 |
Map pmap = get(p, static_cast<Graph&>(g));
|
williamr@2
|
1748 |
put(pmap, key, value);
|
williamr@2
|
1749 |
}
|
williamr@2
|
1750 |
|
williamr@2
|
1751 |
|
williamr@2
|
1752 |
//=========================================================================
|
williamr@2
|
1753 |
// Generalize Adjacency List Implementation
|
williamr@2
|
1754 |
|
williamr@2
|
1755 |
struct adj_list_tag { };
|
williamr@2
|
1756 |
|
williamr@2
|
1757 |
template <class Derived, class Config, class Base>
|
williamr@2
|
1758 |
class adj_list_impl
|
williamr@2
|
1759 |
: public adj_list_helper<Config, Base>
|
williamr@2
|
1760 |
{
|
williamr@2
|
1761 |
typedef typename Config::OutEdgeList OutEdgeList;
|
williamr@2
|
1762 |
typedef typename Config::InEdgeList InEdgeList;
|
williamr@2
|
1763 |
typedef typename Config::StoredVertexList StoredVertexList;
|
williamr@2
|
1764 |
public:
|
williamr@2
|
1765 |
typedef typename Config::stored_vertex stored_vertex;
|
williamr@2
|
1766 |
typedef typename Config::EdgeContainer EdgeContainer;
|
williamr@2
|
1767 |
typedef typename Config::vertex_descriptor vertex_descriptor;
|
williamr@2
|
1768 |
typedef typename Config::edge_descriptor edge_descriptor;
|
williamr@2
|
1769 |
typedef typename Config::vertex_iterator vertex_iterator;
|
williamr@2
|
1770 |
typedef typename Config::edge_iterator edge_iterator;
|
williamr@2
|
1771 |
typedef typename Config::edge_parallel_category edge_parallel_category;
|
williamr@2
|
1772 |
typedef typename Config::vertices_size_type vertices_size_type;
|
williamr@2
|
1773 |
typedef typename Config::edges_size_type edges_size_type;
|
williamr@2
|
1774 |
typedef typename Config::degree_size_type degree_size_type;
|
williamr@2
|
1775 |
typedef typename Config::edge_property_type edge_property_type;
|
williamr@2
|
1776 |
typedef adj_list_tag graph_tag;
|
williamr@2
|
1777 |
|
williamr@2
|
1778 |
static vertex_descriptor null_vertex()
|
williamr@2
|
1779 |
{
|
williamr@2
|
1780 |
return 0;
|
williamr@2
|
1781 |
}
|
williamr@2
|
1782 |
|
williamr@2
|
1783 |
inline adj_list_impl() { }
|
williamr@2
|
1784 |
|
williamr@2
|
1785 |
inline adj_list_impl(const adj_list_impl& x) {
|
williamr@2
|
1786 |
copy_impl(x);
|
williamr@2
|
1787 |
}
|
williamr@2
|
1788 |
inline adj_list_impl& operator=(const adj_list_impl& x) {
|
williamr@2
|
1789 |
this->clear();
|
williamr@2
|
1790 |
copy_impl(x);
|
williamr@2
|
1791 |
return *this;
|
williamr@2
|
1792 |
}
|
williamr@2
|
1793 |
inline void clear() {
|
williamr@2
|
1794 |
for (typename StoredVertexList::iterator i = m_vertices.begin();
|
williamr@2
|
1795 |
i != m_vertices.end(); ++i)
|
williamr@2
|
1796 |
delete (stored_vertex*)*i;
|
williamr@2
|
1797 |
m_vertices.clear();
|
williamr@2
|
1798 |
m_edges.clear();
|
williamr@2
|
1799 |
}
|
williamr@2
|
1800 |
inline adj_list_impl(vertices_size_type num_vertices) {
|
williamr@2
|
1801 |
for (vertices_size_type i = 0; i < num_vertices; ++i)
|
williamr@2
|
1802 |
add_vertex(static_cast<Derived&>(*this));
|
williamr@2
|
1803 |
}
|
williamr@2
|
1804 |
template <class EdgeIterator>
|
williamr@2
|
1805 |
inline adj_list_impl(vertices_size_type num_vertices,
|
williamr@2
|
1806 |
EdgeIterator first, EdgeIterator last)
|
williamr@2
|
1807 |
{
|
williamr@2
|
1808 |
vertex_descriptor* v = new vertex_descriptor[num_vertices];
|
williamr@2
|
1809 |
for (vertices_size_type i = 0; i < num_vertices; ++i)
|
williamr@2
|
1810 |
v[i] = add_vertex(static_cast<Derived&>(*this));
|
williamr@2
|
1811 |
|
williamr@2
|
1812 |
while (first != last) {
|
williamr@2
|
1813 |
add_edge(v[(*first).first], v[(*first).second], *this);
|
williamr@2
|
1814 |
++first;
|
williamr@2
|
1815 |
}
|
williamr@2
|
1816 |
delete [] v;
|
williamr@2
|
1817 |
}
|
williamr@2
|
1818 |
template <class EdgeIterator, class EdgePropertyIterator>
|
williamr@2
|
1819 |
inline adj_list_impl(vertices_size_type num_vertices,
|
williamr@2
|
1820 |
EdgeIterator first, EdgeIterator last,
|
williamr@2
|
1821 |
EdgePropertyIterator ep_iter)
|
williamr@2
|
1822 |
{
|
williamr@2
|
1823 |
vertex_descriptor* v = new vertex_descriptor[num_vertices];
|
williamr@2
|
1824 |
for (vertices_size_type i = 0; i < num_vertices; ++i)
|
williamr@2
|
1825 |
v[i] = add_vertex(static_cast<Derived&>(*this));
|
williamr@2
|
1826 |
|
williamr@2
|
1827 |
while (first != last) {
|
williamr@2
|
1828 |
add_edge(v[(*first).first], v[(*first).second], *ep_iter, *this);
|
williamr@2
|
1829 |
++first;
|
williamr@2
|
1830 |
++ep_iter;
|
williamr@2
|
1831 |
}
|
williamr@2
|
1832 |
delete [] v;
|
williamr@2
|
1833 |
}
|
williamr@2
|
1834 |
~adj_list_impl() {
|
williamr@2
|
1835 |
for (typename StoredVertexList::iterator i = m_vertices.begin();
|
williamr@2
|
1836 |
i != m_vertices.end(); ++i)
|
williamr@2
|
1837 |
delete (stored_vertex*)*i;
|
williamr@2
|
1838 |
}
|
williamr@2
|
1839 |
// protected:
|
williamr@2
|
1840 |
inline OutEdgeList& out_edge_list(vertex_descriptor v) {
|
williamr@2
|
1841 |
stored_vertex* sv = (stored_vertex*)v;
|
williamr@2
|
1842 |
return sv->m_out_edges;
|
williamr@2
|
1843 |
}
|
williamr@2
|
1844 |
inline const OutEdgeList& out_edge_list(vertex_descriptor v) const {
|
williamr@2
|
1845 |
stored_vertex* sv = (stored_vertex*)v;
|
williamr@2
|
1846 |
return sv->m_out_edges;
|
williamr@2
|
1847 |
}
|
williamr@2
|
1848 |
inline StoredVertexList& vertex_set() { return m_vertices; }
|
williamr@2
|
1849 |
inline const StoredVertexList& vertex_set() const { return m_vertices; }
|
williamr@2
|
1850 |
|
williamr@2
|
1851 |
inline void copy_impl(const adj_list_impl& x_)
|
williamr@2
|
1852 |
{
|
williamr@2
|
1853 |
const Derived& x = static_cast<const Derived&>(x_);
|
williamr@2
|
1854 |
|
williamr@2
|
1855 |
// Would be better to have a constant time way to get from
|
williamr@2
|
1856 |
// vertices in x to the corresponding vertices in *this.
|
williamr@2
|
1857 |
std::map<stored_vertex*,stored_vertex*> vertex_map;
|
williamr@2
|
1858 |
|
williamr@2
|
1859 |
// Copy the stored vertex objects by adding each vertex
|
williamr@2
|
1860 |
// and copying its property object.
|
williamr@2
|
1861 |
vertex_iterator vi, vi_end;
|
williamr@2
|
1862 |
for (tie(vi, vi_end) = vertices(x); vi != vi_end; ++vi) {
|
williamr@2
|
1863 |
stored_vertex* v = (stored_vertex*)add_vertex(*this);
|
williamr@2
|
1864 |
v->m_property = ((stored_vertex*)*vi)->m_property;
|
williamr@2
|
1865 |
vertex_map[(stored_vertex*)*vi] = v;
|
williamr@2
|
1866 |
}
|
williamr@2
|
1867 |
// Copy the edges by adding each edge and copying its
|
williamr@2
|
1868 |
// property object.
|
williamr@2
|
1869 |
edge_iterator ei, ei_end;
|
williamr@2
|
1870 |
for (tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) {
|
williamr@2
|
1871 |
edge_descriptor e;
|
williamr@2
|
1872 |
bool inserted;
|
williamr@2
|
1873 |
vertex_descriptor s = source(*ei,x), t = target(*ei,x);
|
williamr@2
|
1874 |
tie(e, inserted) = add_edge(vertex_map[(stored_vertex*)s],
|
williamr@2
|
1875 |
vertex_map[(stored_vertex*)t], *this);
|
williamr@2
|
1876 |
*((edge_property_type*)e.m_eproperty)
|
williamr@2
|
1877 |
= *((edge_property_type*)(*ei).m_eproperty);
|
williamr@2
|
1878 |
}
|
williamr@2
|
1879 |
}
|
williamr@2
|
1880 |
|
williamr@2
|
1881 |
|
williamr@2
|
1882 |
typename Config::EdgeContainer m_edges;
|
williamr@2
|
1883 |
StoredVertexList m_vertices;
|
williamr@2
|
1884 |
};
|
williamr@2
|
1885 |
|
williamr@2
|
1886 |
// O(1)
|
williamr@2
|
1887 |
template <class Derived, class Config, class Base>
|
williamr@2
|
1888 |
inline typename Config::vertex_descriptor
|
williamr@2
|
1889 |
add_vertex(adj_list_impl<Derived, Config, Base>& g_)
|
williamr@2
|
1890 |
{
|
williamr@2
|
1891 |
Derived& g = static_cast<Derived&>(g_);
|
williamr@2
|
1892 |
typedef typename Config::stored_vertex stored_vertex;
|
williamr@2
|
1893 |
stored_vertex* v = new stored_vertex;
|
williamr@2
|
1894 |
typename Config::StoredVertexList::iterator pos;
|
williamr@2
|
1895 |
bool inserted;
|
williamr@2
|
1896 |
boost::tie(pos,inserted) = boost::graph_detail::push(g.m_vertices, v);
|
williamr@2
|
1897 |
v->m_position = pos;
|
williamr@2
|
1898 |
return v;
|
williamr@2
|
1899 |
}
|
williamr@2
|
1900 |
// O(1)
|
williamr@2
|
1901 |
template <class Derived, class Config, class Base>
|
williamr@2
|
1902 |
inline typename Config::vertex_descriptor
|
williamr@2
|
1903 |
add_vertex(const typename Config::vertex_property_type& p,
|
williamr@2
|
1904 |
adj_list_impl<Derived, Config, Base>& g_)
|
williamr@2
|
1905 |
{
|
williamr@2
|
1906 |
Derived& g = static_cast<Derived&>(g_);
|
williamr@2
|
1907 |
typedef typename Config::stored_vertex stored_vertex;
|
williamr@2
|
1908 |
stored_vertex* v = new stored_vertex(p);
|
williamr@2
|
1909 |
typename Config::StoredVertexList::iterator pos;
|
williamr@2
|
1910 |
bool inserted;
|
williamr@2
|
1911 |
boost::tie(pos,inserted) = boost::graph_detail::push(g.m_vertices, v);
|
williamr@2
|
1912 |
v->m_position = pos;
|
williamr@2
|
1913 |
return v;
|
williamr@2
|
1914 |
}
|
williamr@2
|
1915 |
// O(1)
|
williamr@2
|
1916 |
template <class Derived, class Config, class Base>
|
williamr@2
|
1917 |
inline void remove_vertex(typename Config::vertex_descriptor u,
|
williamr@2
|
1918 |
adj_list_impl<Derived, Config, Base>& g_)
|
williamr@2
|
1919 |
{
|
williamr@2
|
1920 |
typedef typename Config::stored_vertex stored_vertex;
|
williamr@2
|
1921 |
Derived& g = static_cast<Derived&>(g_);
|
williamr@2
|
1922 |
stored_vertex* su = (stored_vertex*)u;
|
williamr@2
|
1923 |
g.m_vertices.erase(su->m_position);
|
williamr@2
|
1924 |
delete su;
|
williamr@2
|
1925 |
}
|
williamr@2
|
1926 |
// O(V)
|
williamr@2
|
1927 |
template <class Derived, class Config, class Base>
|
williamr@2
|
1928 |
inline typename Config::vertex_descriptor
|
williamr@2
|
1929 |
vertex(typename Config::vertices_size_type n,
|
williamr@2
|
1930 |
const adj_list_impl<Derived, Config, Base>& g_)
|
williamr@2
|
1931 |
{
|
williamr@2
|
1932 |
const Derived& g = static_cast<const Derived&>(g_);
|
williamr@2
|
1933 |
typename Config::vertex_iterator i = vertices(g).first;
|
williamr@2
|
1934 |
while (n--) ++i; // std::advance(i, n); (not VC++ portable)
|
williamr@2
|
1935 |
return *i;
|
williamr@2
|
1936 |
}
|
williamr@2
|
1937 |
|
williamr@2
|
1938 |
//=========================================================================
|
williamr@2
|
1939 |
// Vector-Backbone Adjacency List Implementation
|
williamr@2
|
1940 |
|
williamr@2
|
1941 |
namespace detail {
|
williamr@2
|
1942 |
|
williamr@2
|
1943 |
template <class Graph, class vertex_descriptor>
|
williamr@2
|
1944 |
inline void
|
williamr@2
|
1945 |
remove_vertex_dispatch(Graph& g, vertex_descriptor u,
|
williamr@2
|
1946 |
boost::directed_tag)
|
williamr@2
|
1947 |
{
|
williamr@2
|
1948 |
typedef typename Graph::edge_parallel_category edge_parallel_category;
|
williamr@2
|
1949 |
g.m_vertices.erase(g.m_vertices.begin() + u);
|
williamr@2
|
1950 |
vertex_descriptor V = num_vertices(g);
|
williamr@2
|
1951 |
if (u != V) {
|
williamr@2
|
1952 |
for (vertex_descriptor v = 0; v < V; ++v)
|
williamr@2
|
1953 |
reindex_edge_list(g.out_edge_list(v), u, edge_parallel_category());
|
williamr@2
|
1954 |
}
|
williamr@2
|
1955 |
}
|
williamr@2
|
1956 |
|
williamr@2
|
1957 |
template <class Graph, class vertex_descriptor>
|
williamr@2
|
1958 |
inline void
|
williamr@2
|
1959 |
remove_vertex_dispatch(Graph& g, vertex_descriptor u,
|
williamr@2
|
1960 |
boost::undirected_tag)
|
williamr@2
|
1961 |
{
|
williamr@2
|
1962 |
typedef typename Graph::global_edgelist_selector EdgeListS;
|
williamr@2
|
1963 |
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
williamr@2
|
1964 |
|
williamr@2
|
1965 |
typedef typename Graph::edge_parallel_category edge_parallel_category;
|
williamr@2
|
1966 |
g.m_vertices.erase(g.m_vertices.begin() + u);
|
williamr@2
|
1967 |
vertex_descriptor V = num_vertices(g);
|
williamr@2
|
1968 |
for (vertex_descriptor v = 0; v < V; ++v)
|
williamr@2
|
1969 |
reindex_edge_list(g.out_edge_list(v), u,
|
williamr@2
|
1970 |
edge_parallel_category());
|
williamr@2
|
1971 |
typedef typename Graph::EdgeContainer Container;
|
williamr@2
|
1972 |
typedef typename Container::iterator Iter;
|
williamr@2
|
1973 |
Iter ei = g.m_edges.begin(), ei_end = g.m_edges.end();
|
williamr@2
|
1974 |
for (; ei != ei_end; ++ei) {
|
williamr@2
|
1975 |
if (ei->m_source > u)
|
williamr@2
|
1976 |
--ei->m_source;
|
williamr@2
|
1977 |
if (ei->m_target > u)
|
williamr@2
|
1978 |
--ei->m_target;
|
williamr@2
|
1979 |
}
|
williamr@2
|
1980 |
}
|
williamr@2
|
1981 |
template <class Graph, class vertex_descriptor>
|
williamr@2
|
1982 |
inline void
|
williamr@2
|
1983 |
remove_vertex_dispatch(Graph& g, vertex_descriptor u,
|
williamr@2
|
1984 |
boost::bidirectional_tag)
|
williamr@2
|
1985 |
{
|
williamr@2
|
1986 |
typedef typename Graph::global_edgelist_selector EdgeListS;
|
williamr@2
|
1987 |
BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
|
williamr@2
|
1988 |
|
williamr@2
|
1989 |
typedef typename Graph::edge_parallel_category edge_parallel_category;
|
williamr@2
|
1990 |
g.m_vertices.erase(g.m_vertices.begin() + u);
|
williamr@2
|
1991 |
vertex_descriptor V = num_vertices(g);
|
williamr@2
|
1992 |
vertex_descriptor v;
|
williamr@2
|
1993 |
if (u != V) {
|
williamr@2
|
1994 |
for (v = 0; v < V; ++v)
|
williamr@2
|
1995 |
reindex_edge_list(g.out_edge_list(v), u,
|
williamr@2
|
1996 |
edge_parallel_category());
|
williamr@2
|
1997 |
for (v = 0; v < V; ++v)
|
williamr@2
|
1998 |
reindex_edge_list(in_edge_list(g, v), u,
|
williamr@2
|
1999 |
edge_parallel_category());
|
williamr@2
|
2000 |
|
williamr@2
|
2001 |
typedef typename Graph::EdgeContainer Container;
|
williamr@2
|
2002 |
typedef typename Container::iterator Iter;
|
williamr@2
|
2003 |
Iter ei = g.m_edges.begin(), ei_end = g.m_edges.end();
|
williamr@2
|
2004 |
for (; ei != ei_end; ++ei) {
|
williamr@2
|
2005 |
if (ei->m_source > u)
|
williamr@2
|
2006 |
--ei->m_source;
|
williamr@2
|
2007 |
if (ei->m_target > u)
|
williamr@2
|
2008 |
--ei->m_target;
|
williamr@2
|
2009 |
}
|
williamr@2
|
2010 |
}
|
williamr@2
|
2011 |
}
|
williamr@2
|
2012 |
|
williamr@2
|
2013 |
template <class EdgeList, class vertex_descriptor>
|
williamr@2
|
2014 |
inline void
|
williamr@2
|
2015 |
reindex_edge_list(EdgeList& el, vertex_descriptor u,
|
williamr@2
|
2016 |
boost::allow_parallel_edge_tag)
|
williamr@2
|
2017 |
{
|
williamr@2
|
2018 |
typename EdgeList::iterator ei = el.begin(), e_end = el.end();
|
williamr@2
|
2019 |
for (; ei != e_end; ++ei)
|
williamr@2
|
2020 |
if ((*ei).get_target() > u)
|
williamr@2
|
2021 |
--(*ei).get_target();
|
williamr@2
|
2022 |
}
|
williamr@2
|
2023 |
template <class EdgeList, class vertex_descriptor>
|
williamr@2
|
2024 |
inline void
|
williamr@2
|
2025 |
reindex_edge_list(EdgeList& el, vertex_descriptor u,
|
williamr@2
|
2026 |
boost::disallow_parallel_edge_tag)
|
williamr@2
|
2027 |
{
|
williamr@2
|
2028 |
typename EdgeList::iterator ei = el.begin(), e_end = el.end();
|
williamr@2
|
2029 |
while (ei != e_end) {
|
williamr@2
|
2030 |
typename EdgeList::value_type ce = *ei;
|
williamr@2
|
2031 |
++ei;
|
williamr@2
|
2032 |
if (ce.get_target() > u) {
|
williamr@2
|
2033 |
el.erase(ce);
|
williamr@2
|
2034 |
--ce.get_target();
|
williamr@2
|
2035 |
el.insert(ce);
|
williamr@2
|
2036 |
}
|
williamr@2
|
2037 |
}
|
williamr@2
|
2038 |
}
|
williamr@2
|
2039 |
} // namespace detail
|
williamr@2
|
2040 |
|
williamr@2
|
2041 |
struct vec_adj_list_tag { };
|
williamr@2
|
2042 |
|
williamr@2
|
2043 |
template <class Graph, class Config, class Base>
|
williamr@2
|
2044 |
class vec_adj_list_impl
|
williamr@2
|
2045 |
: public adj_list_helper<Config, Base>
|
williamr@2
|
2046 |
{
|
williamr@2
|
2047 |
typedef typename Config::OutEdgeList OutEdgeList;
|
williamr@2
|
2048 |
typedef typename Config::InEdgeList InEdgeList;
|
williamr@2
|
2049 |
typedef typename Config::StoredVertexList StoredVertexList;
|
williamr@2
|
2050 |
public:
|
williamr@2
|
2051 |
typedef typename Config::vertex_descriptor vertex_descriptor;
|
williamr@2
|
2052 |
typedef typename Config::edge_descriptor edge_descriptor;
|
williamr@2
|
2053 |
typedef typename Config::out_edge_iterator out_edge_iterator;
|
williamr@2
|
2054 |
typedef typename Config::edge_iterator edge_iterator;
|
williamr@2
|
2055 |
typedef typename Config::directed_category directed_category;
|
williamr@2
|
2056 |
typedef typename Config::vertices_size_type vertices_size_type;
|
williamr@2
|
2057 |
typedef typename Config::edges_size_type edges_size_type;
|
williamr@2
|
2058 |
typedef typename Config::degree_size_type degree_size_type;
|
williamr@2
|
2059 |
typedef typename Config::StoredEdge StoredEdge;
|
williamr@2
|
2060 |
typedef typename Config::stored_vertex stored_vertex;
|
williamr@2
|
2061 |
typedef typename Config::EdgeContainer EdgeContainer;
|
williamr@2
|
2062 |
typedef typename Config::edge_property_type edge_property_type;
|
williamr@2
|
2063 |
typedef vec_adj_list_tag graph_tag;
|
williamr@2
|
2064 |
|
williamr@2
|
2065 |
static vertex_descriptor null_vertex()
|
williamr@2
|
2066 |
{
|
williamr@2
|
2067 |
return (std::numeric_limits<vertex_descriptor>::max)();
|
williamr@2
|
2068 |
}
|
williamr@2
|
2069 |
|
williamr@2
|
2070 |
inline vec_adj_list_impl() { }
|
williamr@2
|
2071 |
|
williamr@2
|
2072 |
inline vec_adj_list_impl(const vec_adj_list_impl& x) {
|
williamr@2
|
2073 |
copy_impl(x);
|
williamr@2
|
2074 |
}
|
williamr@2
|
2075 |
inline vec_adj_list_impl& operator=(const vec_adj_list_impl& x) {
|
williamr@2
|
2076 |
this->clear();
|
williamr@2
|
2077 |
copy_impl(x);
|
williamr@2
|
2078 |
return *this;
|
williamr@2
|
2079 |
}
|
williamr@2
|
2080 |
inline void clear() {
|
williamr@2
|
2081 |
m_vertices.clear();
|
williamr@2
|
2082 |
m_edges.clear();
|
williamr@2
|
2083 |
}
|
williamr@2
|
2084 |
|
williamr@2
|
2085 |
inline vec_adj_list_impl(vertices_size_type _num_vertices)
|
williamr@2
|
2086 |
: m_vertices(_num_vertices) { }
|
williamr@2
|
2087 |
|
williamr@2
|
2088 |
template <class EdgeIterator>
|
williamr@2
|
2089 |
inline vec_adj_list_impl(vertices_size_type num_vertices,
|
williamr@2
|
2090 |
EdgeIterator first, EdgeIterator last)
|
williamr@2
|
2091 |
: m_vertices(num_vertices)
|
williamr@2
|
2092 |
{
|
williamr@2
|
2093 |
while (first != last) {
|
williamr@2
|
2094 |
add_edge((*first).first, (*first).second,
|
williamr@2
|
2095 |
static_cast<Graph&>(*this));
|
williamr@2
|
2096 |
++first;
|
williamr@2
|
2097 |
}
|
williamr@2
|
2098 |
}
|
williamr@2
|
2099 |
template <class EdgeIterator, class EdgePropertyIterator>
|
williamr@2
|
2100 |
inline vec_adj_list_impl(vertices_size_type num_vertices,
|
williamr@2
|
2101 |
EdgeIterator first, EdgeIterator last,
|
williamr@2
|
2102 |
EdgePropertyIterator ep_iter)
|
williamr@2
|
2103 |
: m_vertices(num_vertices)
|
williamr@2
|
2104 |
{
|
williamr@2
|
2105 |
while (first != last) {
|
williamr@2
|
2106 |
add_edge((*first).first, (*first).second, *ep_iter,
|
williamr@2
|
2107 |
static_cast<Graph&>(*this));
|
williamr@2
|
2108 |
++first;
|
williamr@2
|
2109 |
++ep_iter;
|
williamr@2
|
2110 |
}
|
williamr@2
|
2111 |
}
|
williamr@2
|
2112 |
|
williamr@2
|
2113 |
// protected:
|
williamr@2
|
2114 |
inline boost::integer_range<vertex_descriptor> vertex_set() const {
|
williamr@2
|
2115 |
return boost::integer_range<vertex_descriptor>(0, m_vertices.size());
|
williamr@2
|
2116 |
}
|
williamr@2
|
2117 |
inline OutEdgeList& out_edge_list(vertex_descriptor v) {
|
williamr@2
|
2118 |
return m_vertices[v].m_out_edges;
|
williamr@2
|
2119 |
}
|
williamr@2
|
2120 |
inline const OutEdgeList& out_edge_list(vertex_descriptor v) const {
|
williamr@2
|
2121 |
return m_vertices[v].m_out_edges;
|
williamr@2
|
2122 |
}
|
williamr@2
|
2123 |
inline void copy_impl(const vec_adj_list_impl& x_)
|
williamr@2
|
2124 |
{
|
williamr@2
|
2125 |
const Graph& x = static_cast<const Graph&>(x_);
|
williamr@2
|
2126 |
// Copy the stored vertex objects by adding each vertex
|
williamr@2
|
2127 |
// and copying its property object.
|
williamr@2
|
2128 |
for (vertices_size_type i = 0; i < num_vertices(x); ++i) {
|
williamr@2
|
2129 |
vertex_descriptor v = add_vertex(*this);
|
williamr@2
|
2130 |
m_vertices[v].m_property = x.m_vertices[i].m_property;
|
williamr@2
|
2131 |
}
|
williamr@2
|
2132 |
// Copy the edges by adding each edge and copying its
|
williamr@2
|
2133 |
// property object.
|
williamr@2
|
2134 |
edge_iterator ei, ei_end;
|
williamr@2
|
2135 |
for (tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) {
|
williamr@2
|
2136 |
edge_descriptor e;
|
williamr@2
|
2137 |
bool inserted;
|
williamr@2
|
2138 |
tie(e, inserted) = add_edge(source(*ei,x), target(*ei,x) , *this);
|
williamr@2
|
2139 |
*((edge_property_type*)e.m_eproperty)
|
williamr@2
|
2140 |
= *((edge_property_type*)(*ei).m_eproperty);
|
williamr@2
|
2141 |
}
|
williamr@2
|
2142 |
}
|
williamr@2
|
2143 |
typename Config::EdgeContainer m_edges;
|
williamr@2
|
2144 |
StoredVertexList m_vertices;
|
williamr@2
|
2145 |
};
|
williamr@2
|
2146 |
// Had to make these non-members to avoid accidental instantiation
|
williamr@2
|
2147 |
// on SGI MIPSpro C++
|
williamr@2
|
2148 |
template <class G, class C, class B>
|
williamr@2
|
2149 |
inline typename C::InEdgeList&
|
williamr@2
|
2150 |
in_edge_list(vec_adj_list_impl<G,C,B>& g,
|
williamr@2
|
2151 |
typename C::vertex_descriptor v) {
|
williamr@2
|
2152 |
return g.m_vertices[v].m_in_edges;
|
williamr@2
|
2153 |
}
|
williamr@2
|
2154 |
template <class G, class C, class B>
|
williamr@2
|
2155 |
inline const typename C::InEdgeList&
|
williamr@2
|
2156 |
in_edge_list(const vec_adj_list_impl<G,C,B>& g,
|
williamr@2
|
2157 |
typename C::vertex_descriptor v) {
|
williamr@2
|
2158 |
return g.m_vertices[v].m_in_edges;
|
williamr@2
|
2159 |
}
|
williamr@2
|
2160 |
|
williamr@2
|
2161 |
// O(1)
|
williamr@2
|
2162 |
template <class Graph, class Config, class Base>
|
williamr@2
|
2163 |
inline typename Config::vertex_descriptor
|
williamr@2
|
2164 |
add_vertex(vec_adj_list_impl<Graph, Config, Base>& g_) {
|
williamr@2
|
2165 |
Graph& g = static_cast<Graph&>(g_);
|
williamr@2
|
2166 |
g.m_vertices.resize(g.m_vertices.size() + 1);
|
williamr@2
|
2167 |
return g.m_vertices.size() - 1;
|
williamr@2
|
2168 |
}
|
williamr@2
|
2169 |
|
williamr@2
|
2170 |
template <class Graph, class Config, class Base>
|
williamr@2
|
2171 |
inline typename Config::vertex_descriptor
|
williamr@2
|
2172 |
add_vertex(const typename Config::vertex_property_type& p,
|
williamr@2
|
2173 |
vec_adj_list_impl<Graph, Config, Base>& g_) {
|
williamr@2
|
2174 |
Graph& g = static_cast<Graph&>(g_);
|
williamr@2
|
2175 |
typedef typename Config::stored_vertex stored_vertex;
|
williamr@2
|
2176 |
g.m_vertices.push_back(stored_vertex(p));
|
williamr@2
|
2177 |
return g.m_vertices.size() - 1;
|
williamr@2
|
2178 |
}
|
williamr@2
|
2179 |
|
williamr@2
|
2180 |
// Here we override the directed_graph_helper add_edge() function
|
williamr@2
|
2181 |
// so that the number of vertices is automatically changed if
|
williamr@2
|
2182 |
// either u or v is greater than the number of vertices.
|
williamr@2
|
2183 |
template <class Graph, class Config, class Base>
|
williamr@2
|
2184 |
inline std::pair<typename Config::edge_descriptor, bool>
|
williamr@2
|
2185 |
add_edge(typename Config::vertex_descriptor u,
|
williamr@2
|
2186 |
typename Config::vertex_descriptor v,
|
williamr@2
|
2187 |
const typename Config::edge_property_type& p,
|
williamr@2
|
2188 |
vec_adj_list_impl<Graph, Config, Base>& g_)
|
williamr@2
|
2189 |
{
|
williamr@2
|
2190 |
BOOST_USING_STD_MAX();
|
williamr@2
|
2191 |
typename Config::vertex_descriptor x = max BOOST_PREVENT_MACRO_SUBSTITUTION(u, v);
|
williamr@2
|
2192 |
if (x >= num_vertices(g_))
|
williamr@2
|
2193 |
g_.m_vertices.resize(x + 1);
|
williamr@2
|
2194 |
adj_list_helper<Config, Base>& g = g_;
|
williamr@2
|
2195 |
return add_edge(u, v, p, g);
|
williamr@2
|
2196 |
}
|
williamr@2
|
2197 |
template <class Graph, class Config, class Base>
|
williamr@2
|
2198 |
inline std::pair<typename Config::edge_descriptor, bool>
|
williamr@2
|
2199 |
add_edge(typename Config::vertex_descriptor u,
|
williamr@2
|
2200 |
typename Config::vertex_descriptor v,
|
williamr@2
|
2201 |
vec_adj_list_impl<Graph, Config, Base>& g_)
|
williamr@2
|
2202 |
{
|
williamr@2
|
2203 |
typename Config::edge_property_type p;
|
williamr@2
|
2204 |
return add_edge(u, v, p, g_);
|
williamr@2
|
2205 |
}
|
williamr@2
|
2206 |
|
williamr@2
|
2207 |
|
williamr@2
|
2208 |
// O(V + E)
|
williamr@2
|
2209 |
template <class Graph, class Config, class Base>
|
williamr@2
|
2210 |
inline void remove_vertex(typename Config::vertex_descriptor v,
|
williamr@2
|
2211 |
vec_adj_list_impl<Graph, Config, Base>& g_)
|
williamr@2
|
2212 |
{
|
williamr@2
|
2213 |
typedef typename Config::directed_category Cat;
|
williamr@2
|
2214 |
Graph& g = static_cast<Graph&>(g_);
|
williamr@2
|
2215 |
detail::remove_vertex_dispatch(g, v, Cat());
|
williamr@2
|
2216 |
}
|
williamr@2
|
2217 |
// O(1)
|
williamr@2
|
2218 |
template <class Graph, class Config, class Base>
|
williamr@2
|
2219 |
inline typename Config::vertex_descriptor
|
williamr@2
|
2220 |
vertex(typename Config::vertices_size_type n,
|
williamr@2
|
2221 |
const vec_adj_list_impl<Graph, Config, Base>&)
|
williamr@2
|
2222 |
{
|
williamr@2
|
2223 |
return n;
|
williamr@2
|
2224 |
}
|
williamr@2
|
2225 |
|
williamr@2
|
2226 |
|
williamr@2
|
2227 |
namespace detail {
|
williamr@2
|
2228 |
|
williamr@2
|
2229 |
//=========================================================================
|
williamr@2
|
2230 |
// Adjacency List Generator
|
williamr@2
|
2231 |
|
williamr@2
|
2232 |
template <class Graph, class VertexListS, class OutEdgeListS,
|
williamr@2
|
2233 |
class DirectedS, class VertexProperty, class EdgeProperty,
|
williamr@2
|
2234 |
class GraphProperty, class EdgeListS>
|
williamr@2
|
2235 |
struct adj_list_gen
|
williamr@2
|
2236 |
{
|
williamr@2
|
2237 |
typedef typename detail::is_random_access<VertexListS>::type
|
williamr@2
|
2238 |
is_rand_access;
|
williamr@2
|
2239 |
typedef typename has_property<EdgeProperty>::type has_edge_property;
|
williamr@2
|
2240 |
typedef typename DirectedS::is_directed_t DirectedT;
|
williamr@2
|
2241 |
typedef typename DirectedS::is_bidir_t BidirectionalT;
|
williamr@2
|
2242 |
|
williamr@2
|
2243 |
struct config
|
williamr@2
|
2244 |
{
|
williamr@2
|
2245 |
typedef OutEdgeListS edgelist_selector;
|
williamr@2
|
2246 |
typedef EdgeListS global_edgelist_selector;
|
williamr@2
|
2247 |
|
williamr@2
|
2248 |
typedef Graph graph_type;
|
williamr@2
|
2249 |
typedef EdgeProperty edge_property_type;
|
williamr@2
|
2250 |
typedef VertexProperty vertex_property_type;
|
williamr@2
|
2251 |
typedef GraphProperty graph_property_type;
|
williamr@2
|
2252 |
typedef std::size_t vertices_size_type;
|
williamr@2
|
2253 |
|
williamr@2
|
2254 |
typedef adjacency_list_traits<OutEdgeListS, VertexListS, DirectedS>
|
williamr@2
|
2255 |
Traits;
|
williamr@2
|
2256 |
|
williamr@2
|
2257 |
typedef typename Traits::directed_category directed_category;
|
williamr@2
|
2258 |
typedef typename Traits::edge_parallel_category edge_parallel_category;
|
williamr@2
|
2259 |
typedef typename Traits::vertex_descriptor vertex_descriptor;
|
williamr@2
|
2260 |
typedef typename Traits::edge_descriptor edge_descriptor;
|
williamr@2
|
2261 |
|
williamr@2
|
2262 |
typedef void* vertex_ptr;
|
williamr@2
|
2263 |
|
williamr@2
|
2264 |
// need to reorganize this to avoid instantiating stuff
|
williamr@2
|
2265 |
// that doesn't get used -JGS
|
williamr@2
|
2266 |
|
williamr@2
|
2267 |
// VertexList and vertex_iterator
|
williamr@2
|
2268 |
typedef typename container_gen<VertexListS,
|
williamr@2
|
2269 |
vertex_ptr>::type SeqVertexList;
|
williamr@2
|
2270 |
typedef boost::integer_range<std::size_t> RandVertexList;
|
williamr@2
|
2271 |
typedef typename boost::ct_if_t<is_rand_access,
|
williamr@2
|
2272 |
RandVertexList, SeqVertexList>::type VertexList;
|
williamr@2
|
2273 |
|
williamr@2
|
2274 |
typedef typename VertexList::iterator vertex_iterator;
|
williamr@2
|
2275 |
|
williamr@2
|
2276 |
// EdgeContainer and StoredEdge
|
williamr@2
|
2277 |
|
williamr@2
|
2278 |
typedef typename container_gen<EdgeListS,
|
williamr@2
|
2279 |
list_edge<vertex_descriptor, EdgeProperty> >::type EdgeContainer;
|
williamr@2
|
2280 |
|
williamr@2
|
2281 |
typedef typename ct_and<DirectedT,
|
williamr@2
|
2282 |
typename ct_not<BidirectionalT>::type >::type on_edge_storage;
|
williamr@2
|
2283 |
|
williamr@2
|
2284 |
typedef typename boost::ct_if_t<on_edge_storage,
|
williamr@2
|
2285 |
std::size_t, typename EdgeContainer::size_type
|
williamr@2
|
2286 |
>::type edges_size_type;
|
williamr@2
|
2287 |
|
williamr@2
|
2288 |
typedef typename EdgeContainer::iterator EdgeIter;
|
williamr@2
|
2289 |
|
williamr@2
|
2290 |
typedef typename detail::is_random_access<EdgeListS>::type is_edge_ra;
|
williamr@2
|
2291 |
|
williamr@2
|
2292 |
typedef typename boost::ct_if_t<on_edge_storage,
|
williamr@2
|
2293 |
stored_edge_property<vertex_descriptor, EdgeProperty>,
|
williamr@2
|
2294 |
typename boost::ct_if_t<is_edge_ra,
|
williamr@2
|
2295 |
stored_ra_edge_iter<vertex_descriptor, EdgeContainer, EdgeProperty>,
|
williamr@2
|
2296 |
stored_edge_iter<vertex_descriptor, EdgeIter, EdgeProperty>
|
williamr@2
|
2297 |
>::type
|
williamr@2
|
2298 |
>::type StoredEdge;
|
williamr@2
|
2299 |
|
williamr@2
|
2300 |
// Adjacency Types
|
williamr@2
|
2301 |
|
williamr@2
|
2302 |
typedef typename container_gen<OutEdgeListS, StoredEdge>::type
|
williamr@2
|
2303 |
OutEdgeList;
|
williamr@2
|
2304 |
typedef typename OutEdgeList::size_type degree_size_type;
|
williamr@2
|
2305 |
typedef typename OutEdgeList::iterator OutEdgeIter;
|
williamr@2
|
2306 |
|
williamr@2
|
2307 |
typedef boost::detail::iterator_traits<OutEdgeIter> OutEdgeIterTraits;
|
williamr@2
|
2308 |
typedef typename OutEdgeIterTraits::iterator_category OutEdgeIterCat;
|
williamr@2
|
2309 |
typedef typename OutEdgeIterTraits::difference_type OutEdgeIterDiff;
|
williamr@2
|
2310 |
|
williamr@2
|
2311 |
typedef out_edge_iter<
|
williamr@2
|
2312 |
OutEdgeIter, vertex_descriptor, edge_descriptor, OutEdgeIterDiff
|
williamr@2
|
2313 |
> out_edge_iterator;
|
williamr@2
|
2314 |
|
williamr@2
|
2315 |
typedef typename adjacency_iterator_generator<graph_type,
|
williamr@2
|
2316 |
vertex_descriptor, out_edge_iterator>::type adjacency_iterator;
|
williamr@2
|
2317 |
|
williamr@2
|
2318 |
typedef OutEdgeList InEdgeList;
|
williamr@2
|
2319 |
typedef OutEdgeIter InEdgeIter;
|
williamr@2
|
2320 |
typedef OutEdgeIterCat InEdgeIterCat;
|
williamr@2
|
2321 |
typedef OutEdgeIterDiff InEdgeIterDiff;
|
williamr@2
|
2322 |
|
williamr@2
|
2323 |
typedef in_edge_iter<
|
williamr@2
|
2324 |
InEdgeIter, vertex_descriptor, edge_descriptor, InEdgeIterDiff
|
williamr@2
|
2325 |
> in_edge_iterator;
|
williamr@2
|
2326 |
|
williamr@2
|
2327 |
typedef typename inv_adjacency_iterator_generator<graph_type,
|
williamr@2
|
2328 |
vertex_descriptor, in_edge_iterator>::type inv_adjacency_iterator;
|
williamr@2
|
2329 |
|
williamr@2
|
2330 |
// Edge Iterator
|
williamr@2
|
2331 |
|
williamr@2
|
2332 |
typedef boost::detail::iterator_traits<EdgeIter> EdgeIterTraits;
|
williamr@2
|
2333 |
typedef typename EdgeIterTraits::iterator_category EdgeIterCat;
|
williamr@2
|
2334 |
typedef typename EdgeIterTraits::difference_type EdgeIterDiff;
|
williamr@2
|
2335 |
|
williamr@2
|
2336 |
typedef undirected_edge_iter<
|
williamr@2
|
2337 |
EdgeIter
|
williamr@2
|
2338 |
, edge_descriptor
|
williamr@2
|
2339 |
, EdgeIterDiff
|
williamr@2
|
2340 |
> UndirectedEdgeIter; // also used for bidirectional
|
williamr@2
|
2341 |
|
williamr@2
|
2342 |
typedef adj_list_edge_iterator<vertex_iterator, out_edge_iterator,
|
williamr@2
|
2343 |
graph_type> DirectedEdgeIter;
|
williamr@2
|
2344 |
|
williamr@2
|
2345 |
typedef typename boost::ct_if_t<on_edge_storage,
|
williamr@2
|
2346 |
DirectedEdgeIter, UndirectedEdgeIter>::type edge_iterator;
|
williamr@2
|
2347 |
|
williamr@2
|
2348 |
// stored_vertex and StoredVertexList
|
williamr@2
|
2349 |
typedef typename container_gen<VertexListS, vertex_ptr>::type
|
williamr@2
|
2350 |
SeqStoredVertexList;
|
williamr@2
|
2351 |
struct seq_stored_vertex {
|
williamr@2
|
2352 |
seq_stored_vertex() { }
|
williamr@2
|
2353 |
seq_stored_vertex(const VertexProperty& p) : m_property(p) { }
|
williamr@2
|
2354 |
OutEdgeList m_out_edges;
|
williamr@2
|
2355 |
VertexProperty m_property;
|
williamr@2
|
2356 |
typename SeqStoredVertexList::iterator m_position;
|
williamr@2
|
2357 |
};
|
williamr@2
|
2358 |
struct bidir_seq_stored_vertex {
|
williamr@2
|
2359 |
bidir_seq_stored_vertex() { }
|
williamr@2
|
2360 |
bidir_seq_stored_vertex(const VertexProperty& p) : m_property(p) { }
|
williamr@2
|
2361 |
OutEdgeList m_out_edges;
|
williamr@2
|
2362 |
InEdgeList m_in_edges;
|
williamr@2
|
2363 |
VertexProperty m_property;
|
williamr@2
|
2364 |
typename SeqStoredVertexList::iterator m_position;
|
williamr@2
|
2365 |
};
|
williamr@2
|
2366 |
struct rand_stored_vertex {
|
williamr@2
|
2367 |
rand_stored_vertex() { }
|
williamr@2
|
2368 |
rand_stored_vertex(const VertexProperty& p) : m_property(p) { }
|
williamr@2
|
2369 |
OutEdgeList m_out_edges;
|
williamr@2
|
2370 |
VertexProperty m_property;
|
williamr@2
|
2371 |
};
|
williamr@2
|
2372 |
struct bidir_rand_stored_vertex {
|
williamr@2
|
2373 |
bidir_rand_stored_vertex() { }
|
williamr@2
|
2374 |
bidir_rand_stored_vertex(const VertexProperty& p) : m_property(p) { }
|
williamr@2
|
2375 |
OutEdgeList m_out_edges;
|
williamr@2
|
2376 |
InEdgeList m_in_edges;
|
williamr@2
|
2377 |
VertexProperty m_property;
|
williamr@2
|
2378 |
};
|
williamr@2
|
2379 |
typedef typename boost::ct_if_t<is_rand_access,
|
williamr@2
|
2380 |
typename boost::ct_if_t<BidirectionalT,
|
williamr@2
|
2381 |
bidir_rand_stored_vertex, rand_stored_vertex>::type,
|
williamr@2
|
2382 |
typename boost::ct_if_t<BidirectionalT,
|
williamr@2
|
2383 |
bidir_seq_stored_vertex, seq_stored_vertex>::type
|
williamr@2
|
2384 |
>::type StoredVertex;
|
williamr@2
|
2385 |
struct stored_vertex : public StoredVertex {
|
williamr@2
|
2386 |
stored_vertex() { }
|
williamr@2
|
2387 |
stored_vertex(const VertexProperty& p) : StoredVertex(p) { }
|
williamr@2
|
2388 |
};
|
williamr@2
|
2389 |
|
williamr@2
|
2390 |
typedef typename container_gen<VertexListS, stored_vertex>::type
|
williamr@2
|
2391 |
RandStoredVertexList;
|
williamr@2
|
2392 |
typedef typename boost::ct_if_t< is_rand_access,
|
williamr@2
|
2393 |
RandStoredVertexList, SeqStoredVertexList>::type StoredVertexList;
|
williamr@2
|
2394 |
}; // end of config
|
williamr@2
|
2395 |
|
williamr@2
|
2396 |
|
williamr@2
|
2397 |
typedef typename boost::ct_if_t<BidirectionalT,
|
williamr@2
|
2398 |
bidirectional_graph_helper_with_property<config>,
|
williamr@2
|
2399 |
typename boost::ct_if_t<DirectedT,
|
williamr@2
|
2400 |
directed_graph_helper<config>,
|
williamr@2
|
2401 |
undirected_graph_helper<config>
|
williamr@2
|
2402 |
>::type
|
williamr@2
|
2403 |
>::type DirectedHelper;
|
williamr@2
|
2404 |
|
williamr@2
|
2405 |
typedef typename boost::ct_if_t<is_rand_access,
|
williamr@2
|
2406 |
vec_adj_list_impl<Graph, config, DirectedHelper>,
|
williamr@2
|
2407 |
adj_list_impl<Graph, config, DirectedHelper>
|
williamr@2
|
2408 |
>::type type;
|
williamr@2
|
2409 |
|
williamr@2
|
2410 |
};
|
williamr@2
|
2411 |
|
williamr@2
|
2412 |
} // namespace detail
|
williamr@2
|
2413 |
|
williamr@2
|
2414 |
//=========================================================================
|
williamr@2
|
2415 |
// Vertex Property Maps
|
williamr@2
|
2416 |
|
williamr@2
|
2417 |
template <class Graph, class ValueType, class Reference, class Tag>
|
williamr@2
|
2418 |
struct adj_list_vertex_property_map
|
williamr@2
|
2419 |
: public boost::put_get_helper<
|
williamr@2
|
2420 |
Reference,
|
williamr@2
|
2421 |
adj_list_vertex_property_map<Graph, ValueType, Reference, Tag>
|
williamr@2
|
2422 |
>
|
williamr@2
|
2423 |
{
|
williamr@2
|
2424 |
typedef typename Graph::stored_vertex StoredVertex;
|
williamr@2
|
2425 |
typedef ValueType value_type;
|
williamr@2
|
2426 |
typedef Reference reference;
|
williamr@2
|
2427 |
typedef typename Graph::vertex_descriptor key_type;
|
williamr@2
|
2428 |
typedef boost::lvalue_property_map_tag category;
|
williamr@2
|
2429 |
inline adj_list_vertex_property_map() { }
|
williamr@2
|
2430 |
inline adj_list_vertex_property_map(const Graph*) { }
|
williamr@2
|
2431 |
inline Reference operator[](key_type v) const {
|
williamr@2
|
2432 |
StoredVertex* sv = (StoredVertex*)v;
|
williamr@2
|
2433 |
return get_property_value(sv->m_property, Tag());
|
williamr@2
|
2434 |
}
|
williamr@2
|
2435 |
inline Reference operator()(key_type v) const {
|
williamr@2
|
2436 |
return this->operator[](v);
|
williamr@2
|
2437 |
}
|
williamr@2
|
2438 |
};
|
williamr@2
|
2439 |
|
williamr@2
|
2440 |
template <class Graph, class Property, class PropRef>
|
williamr@2
|
2441 |
struct adj_list_vertex_all_properties_map
|
williamr@2
|
2442 |
: public boost::put_get_helper<PropRef,
|
williamr@2
|
2443 |
adj_list_vertex_all_properties_map<Graph, Property, PropRef>
|
williamr@2
|
2444 |
>
|
williamr@2
|
2445 |
{
|
williamr@2
|
2446 |
typedef typename Graph::stored_vertex StoredVertex;
|
williamr@2
|
2447 |
typedef Property value_type;
|
williamr@2
|
2448 |
typedef PropRef reference;
|
williamr@2
|
2449 |
typedef typename Graph::vertex_descriptor key_type;
|
williamr@2
|
2450 |
typedef boost::lvalue_property_map_tag category;
|
williamr@2
|
2451 |
inline adj_list_vertex_all_properties_map() { }
|
williamr@2
|
2452 |
inline adj_list_vertex_all_properties_map(const Graph*) { }
|
williamr@2
|
2453 |
inline PropRef operator[](key_type v) const {
|
williamr@2
|
2454 |
StoredVertex* sv = (StoredVertex*)v;
|
williamr@2
|
2455 |
return sv->m_property;
|
williamr@2
|
2456 |
}
|
williamr@2
|
2457 |
inline PropRef operator()(key_type v) const {
|
williamr@2
|
2458 |
return this->operator[](v);
|
williamr@2
|
2459 |
}
|
williamr@2
|
2460 |
};
|
williamr@2
|
2461 |
|
williamr@2
|
2462 |
template <class Graph, class GraphPtr, class ValueType, class Reference,
|
williamr@2
|
2463 |
class Tag>
|
williamr@2
|
2464 |
struct vec_adj_list_vertex_property_map
|
williamr@2
|
2465 |
: public boost::put_get_helper<
|
williamr@2
|
2466 |
Reference,
|
williamr@2
|
2467 |
vec_adj_list_vertex_property_map<Graph,GraphPtr,ValueType,Reference,
|
williamr@2
|
2468 |
Tag>
|
williamr@2
|
2469 |
>
|
williamr@2
|
2470 |
{
|
williamr@2
|
2471 |
typedef ValueType value_type;
|
williamr@2
|
2472 |
typedef Reference reference;
|
williamr@2
|
2473 |
typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type;
|
williamr@2
|
2474 |
typedef boost::lvalue_property_map_tag category;
|
williamr@2
|
2475 |
vec_adj_list_vertex_property_map() { }
|
williamr@2
|
2476 |
vec_adj_list_vertex_property_map(GraphPtr g) : m_g(g) { }
|
williamr@2
|
2477 |
inline Reference operator[](key_type v) const {
|
williamr@2
|
2478 |
return get_property_value(m_g->m_vertices[v].m_property, Tag());
|
williamr@2
|
2479 |
}
|
williamr@2
|
2480 |
inline Reference operator()(key_type v) const {
|
williamr@2
|
2481 |
return this->operator[](v);
|
williamr@2
|
2482 |
}
|
williamr@2
|
2483 |
GraphPtr m_g;
|
williamr@2
|
2484 |
};
|
williamr@2
|
2485 |
|
williamr@2
|
2486 |
template <class Graph, class GraphPtr, class Property, class PropertyRef>
|
williamr@2
|
2487 |
struct vec_adj_list_vertex_all_properties_map
|
williamr@2
|
2488 |
: public boost::put_get_helper<PropertyRef,
|
williamr@2
|
2489 |
vec_adj_list_vertex_all_properties_map<Graph,GraphPtr,Property,
|
williamr@2
|
2490 |
PropertyRef>
|
williamr@2
|
2491 |
>
|
williamr@2
|
2492 |
{
|
williamr@2
|
2493 |
typedef Property value_type;
|
williamr@2
|
2494 |
typedef PropertyRef reference;
|
williamr@2
|
2495 |
typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type;
|
williamr@2
|
2496 |
typedef boost::lvalue_property_map_tag category;
|
williamr@2
|
2497 |
vec_adj_list_vertex_all_properties_map() { }
|
williamr@2
|
2498 |
vec_adj_list_vertex_all_properties_map(GraphPtr g) : m_g(g) { }
|
williamr@2
|
2499 |
inline PropertyRef operator[](key_type v) const {
|
williamr@2
|
2500 |
return m_g->m_vertices[v].m_property;
|
williamr@2
|
2501 |
}
|
williamr@2
|
2502 |
inline PropertyRef operator()(key_type v) const {
|
williamr@2
|
2503 |
return this->operator[](v);
|
williamr@2
|
2504 |
}
|
williamr@2
|
2505 |
GraphPtr m_g;
|
williamr@2
|
2506 |
};
|
williamr@2
|
2507 |
|
williamr@2
|
2508 |
struct adj_list_any_vertex_pa {
|
williamr@2
|
2509 |
template <class Tag, class Graph, class Property>
|
williamr@2
|
2510 |
struct bind_ {
|
williamr@2
|
2511 |
typedef typename property_value<Property, Tag>::type value_type;
|
williamr@2
|
2512 |
typedef value_type& reference;
|
williamr@2
|
2513 |
typedef const value_type& const_reference;
|
williamr@2
|
2514 |
|
williamr@2
|
2515 |
typedef adj_list_vertex_property_map
|
williamr@2
|
2516 |
<Graph, value_type, reference, Tag> type;
|
williamr@2
|
2517 |
typedef adj_list_vertex_property_map
|
williamr@2
|
2518 |
<Graph, value_type, const_reference, Tag> const_type;
|
williamr@2
|
2519 |
};
|
williamr@2
|
2520 |
};
|
williamr@2
|
2521 |
struct adj_list_all_vertex_pa {
|
williamr@2
|
2522 |
template <class Tag, class Graph, class Property>
|
williamr@2
|
2523 |
struct bind_ {
|
williamr@2
|
2524 |
typedef typename Graph::vertex_descriptor Vertex;
|
williamr@2
|
2525 |
typedef adj_list_vertex_all_properties_map<Graph,Property,
|
williamr@2
|
2526 |
Property&> type;
|
williamr@2
|
2527 |
typedef adj_list_vertex_all_properties_map<Graph,Property,
|
williamr@2
|
2528 |
const Property&> const_type;
|
williamr@2
|
2529 |
};
|
williamr@2
|
2530 |
};
|
williamr@2
|
2531 |
|
williamr@2
|
2532 |
template <class Property, class Vertex>
|
williamr@2
|
2533 |
struct vec_adj_list_vertex_id_map
|
williamr@2
|
2534 |
: public boost::put_get_helper<
|
williamr@2
|
2535 |
Vertex, vec_adj_list_vertex_id_map<Property, Vertex>
|
williamr@2
|
2536 |
>
|
williamr@2
|
2537 |
{
|
williamr@2
|
2538 |
typedef Vertex value_type;
|
williamr@2
|
2539 |
typedef Vertex key_type;
|
williamr@2
|
2540 |
typedef Vertex reference;
|
williamr@2
|
2541 |
typedef boost::readable_property_map_tag category;
|
williamr@2
|
2542 |
inline vec_adj_list_vertex_id_map() { }
|
williamr@2
|
2543 |
template <class Graph>
|
williamr@2
|
2544 |
inline vec_adj_list_vertex_id_map(const Graph&) { }
|
williamr@2
|
2545 |
inline value_type operator[](key_type v) const { return v; }
|
williamr@2
|
2546 |
inline value_type operator()(key_type v) const { return v; }
|
williamr@2
|
2547 |
};
|
williamr@2
|
2548 |
|
williamr@2
|
2549 |
struct vec_adj_list_any_vertex_pa {
|
williamr@2
|
2550 |
template <class Tag, class Graph, class Property>
|
williamr@2
|
2551 |
struct bind_ {
|
williamr@2
|
2552 |
typedef typename property_value<Property, Tag>::type value_type;
|
williamr@2
|
2553 |
typedef value_type& reference;
|
williamr@2
|
2554 |
typedef const value_type& const_reference;
|
williamr@2
|
2555 |
|
williamr@2
|
2556 |
typedef vec_adj_list_vertex_property_map
|
williamr@2
|
2557 |
<Graph, Graph*, value_type, reference, Tag> type;
|
williamr@2
|
2558 |
typedef vec_adj_list_vertex_property_map
|
williamr@2
|
2559 |
<Graph, const Graph*, value_type, const_reference, Tag> const_type;
|
williamr@2
|
2560 |
};
|
williamr@2
|
2561 |
};
|
williamr@2
|
2562 |
struct vec_adj_list_id_vertex_pa {
|
williamr@2
|
2563 |
template <class Tag, class Graph, class Property>
|
williamr@2
|
2564 |
struct bind_ {
|
williamr@2
|
2565 |
typedef typename Graph::vertex_descriptor Vertex;
|
williamr@2
|
2566 |
typedef vec_adj_list_vertex_id_map<Property, Vertex> type;
|
williamr@2
|
2567 |
typedef vec_adj_list_vertex_id_map<Property, Vertex> const_type;
|
williamr@2
|
2568 |
};
|
williamr@2
|
2569 |
};
|
williamr@2
|
2570 |
struct vec_adj_list_all_vertex_pa {
|
williamr@2
|
2571 |
template <class Tag, class Graph, class Property>
|
williamr@2
|
2572 |
struct bind_ {
|
williamr@2
|
2573 |
typedef typename Graph::vertex_descriptor Vertex;
|
williamr@2
|
2574 |
typedef vec_adj_list_vertex_all_properties_map
|
williamr@2
|
2575 |
<Graph, Graph*, Property, Property&> type;
|
williamr@2
|
2576 |
typedef vec_adj_list_vertex_all_properties_map
|
williamr@2
|
2577 |
<Graph, const Graph*, Property, const Property&> const_type;
|
williamr@2
|
2578 |
};
|
williamr@2
|
2579 |
};
|
williamr@2
|
2580 |
namespace detail {
|
williamr@2
|
2581 |
template <class Tag>
|
williamr@2
|
2582 |
struct adj_list_choose_vertex_pa_helper {
|
williamr@2
|
2583 |
typedef adj_list_any_vertex_pa type;
|
williamr@2
|
2584 |
};
|
williamr@2
|
2585 |
template <>
|
williamr@2
|
2586 |
struct adj_list_choose_vertex_pa_helper<vertex_all_t> {
|
williamr@2
|
2587 |
typedef adj_list_all_vertex_pa type;
|
williamr@2
|
2588 |
};
|
williamr@2
|
2589 |
template <class Tag, class Graph, class Property>
|
williamr@2
|
2590 |
struct adj_list_choose_vertex_pa {
|
williamr@2
|
2591 |
typedef typename adj_list_choose_vertex_pa_helper<Tag>::type Helper;
|
williamr@2
|
2592 |
typedef typename Helper::template bind_<Tag,Graph,Property> Bind;
|
williamr@2
|
2593 |
typedef typename Bind::type type;
|
williamr@2
|
2594 |
typedef typename Bind::const_type const_type;
|
williamr@2
|
2595 |
};
|
williamr@2
|
2596 |
|
williamr@2
|
2597 |
|
williamr@2
|
2598 |
template <class Tag>
|
williamr@2
|
2599 |
struct vec_adj_list_choose_vertex_pa_helper {
|
williamr@2
|
2600 |
typedef vec_adj_list_any_vertex_pa type;
|
williamr@2
|
2601 |
};
|
williamr@2
|
2602 |
template <>
|
williamr@2
|
2603 |
struct vec_adj_list_choose_vertex_pa_helper<vertex_index_t> {
|
williamr@2
|
2604 |
typedef vec_adj_list_id_vertex_pa type;
|
williamr@2
|
2605 |
};
|
williamr@2
|
2606 |
template <>
|
williamr@2
|
2607 |
struct vec_adj_list_choose_vertex_pa_helper<vertex_all_t> {
|
williamr@2
|
2608 |
typedef vec_adj_list_all_vertex_pa type;
|
williamr@2
|
2609 |
};
|
williamr@2
|
2610 |
template <class Tag, class Graph, class Property>
|
williamr@2
|
2611 |
struct vec_adj_list_choose_vertex_pa {
|
williamr@2
|
2612 |
typedef typename vec_adj_list_choose_vertex_pa_helper<Tag>::type Helper;
|
williamr@2
|
2613 |
typedef typename Helper::template bind_<Tag,Graph,Property> Bind;
|
williamr@2
|
2614 |
typedef typename Bind::type type;
|
williamr@2
|
2615 |
typedef typename Bind::const_type const_type;
|
williamr@2
|
2616 |
};
|
williamr@2
|
2617 |
} // namespace detail
|
williamr@2
|
2618 |
|
williamr@2
|
2619 |
//=========================================================================
|
williamr@2
|
2620 |
// Edge Property Map
|
williamr@2
|
2621 |
|
williamr@2
|
2622 |
template <class Directed, class Value, class Ref, class Vertex,
|
williamr@2
|
2623 |
class Property, class Tag>
|
williamr@2
|
2624 |
struct adj_list_edge_property_map
|
williamr@2
|
2625 |
: public put_get_helper<
|
williamr@2
|
2626 |
Ref,
|
williamr@2
|
2627 |
adj_list_edge_property_map<Directed, Value, Ref, Vertex, Property,
|
williamr@2
|
2628 |
Tag>
|
williamr@2
|
2629 |
>
|
williamr@2
|
2630 |
{
|
williamr@2
|
2631 |
typedef Value value_type;
|
williamr@2
|
2632 |
typedef Ref reference;
|
williamr@2
|
2633 |
typedef detail::edge_desc_impl<Directed, Vertex> key_type;
|
williamr@2
|
2634 |
typedef boost::lvalue_property_map_tag category;
|
williamr@2
|
2635 |
inline Ref operator[](key_type e) const {
|
williamr@2
|
2636 |
Property& p = *(Property*)e.get_property();
|
williamr@2
|
2637 |
return get_property_value(p, Tag());
|
williamr@2
|
2638 |
}
|
williamr@2
|
2639 |
inline Ref operator()(key_type e) const {
|
williamr@2
|
2640 |
return this->operator[](e);
|
williamr@2
|
2641 |
}
|
williamr@2
|
2642 |
};
|
williamr@2
|
2643 |
|
williamr@2
|
2644 |
template <class Directed, class Property, class PropRef, class PropPtr,
|
williamr@2
|
2645 |
class Vertex>
|
williamr@2
|
2646 |
struct adj_list_edge_all_properties_map
|
williamr@2
|
2647 |
: public put_get_helper<PropRef,
|
williamr@2
|
2648 |
adj_list_edge_all_properties_map<Directed, Property, PropRef,
|
williamr@2
|
2649 |
PropPtr, Vertex>
|
williamr@2
|
2650 |
>
|
williamr@2
|
2651 |
{
|
williamr@2
|
2652 |
typedef Property value_type;
|
williamr@2
|
2653 |
typedef PropRef reference;
|
williamr@2
|
2654 |
typedef detail::edge_desc_impl<Directed, Vertex> key_type;
|
williamr@2
|
2655 |
typedef boost::lvalue_property_map_tag category;
|
williamr@2
|
2656 |
inline PropRef operator[](key_type e) const {
|
williamr@2
|
2657 |
return *(PropPtr)e.get_property();
|
williamr@2
|
2658 |
}
|
williamr@2
|
2659 |
inline PropRef operator()(key_type e) const {
|
williamr@2
|
2660 |
return this->operator[](e);
|
williamr@2
|
2661 |
}
|
williamr@2
|
2662 |
};
|
williamr@2
|
2663 |
|
williamr@2
|
2664 |
// Edge Property Maps
|
williamr@2
|
2665 |
|
williamr@2
|
2666 |
namespace detail {
|
williamr@2
|
2667 |
struct adj_list_any_edge_pmap {
|
williamr@2
|
2668 |
template <class Graph, class Property, class Tag>
|
williamr@2
|
2669 |
struct bind_ {
|
williamr@2
|
2670 |
typedef typename property_value<Property,Tag>::type value_type;
|
williamr@2
|
2671 |
typedef value_type& reference;
|
williamr@2
|
2672 |
typedef const value_type& const_reference;
|
williamr@2
|
2673 |
|
williamr@2
|
2674 |
typedef adj_list_edge_property_map
|
williamr@2
|
2675 |
<typename Graph::directed_category, value_type, reference,
|
williamr@2
|
2676 |
typename Graph::vertex_descriptor,Property,Tag> type;
|
williamr@2
|
2677 |
typedef adj_list_edge_property_map
|
williamr@2
|
2678 |
<typename Graph::directed_category, value_type, const_reference,
|
williamr@2
|
2679 |
typename Graph::vertex_descriptor,const Property, Tag> const_type;
|
williamr@2
|
2680 |
};
|
williamr@2
|
2681 |
};
|
williamr@2
|
2682 |
struct adj_list_all_edge_pmap {
|
williamr@2
|
2683 |
template <class Graph, class Property, class Tag>
|
williamr@2
|
2684 |
struct bind_ {
|
williamr@2
|
2685 |
typedef adj_list_edge_all_properties_map
|
williamr@2
|
2686 |
<typename Graph::directed_category, Property, Property&, Property*,
|
williamr@2
|
2687 |
typename Graph::vertex_descriptor> type;
|
williamr@2
|
2688 |
typedef adj_list_edge_all_properties_map
|
williamr@2
|
2689 |
<typename Graph::directed_category, Property, const Property&,
|
williamr@2
|
2690 |
const Property*, typename Graph::vertex_descriptor> const_type;
|
williamr@2
|
2691 |
};
|
williamr@2
|
2692 |
};
|
williamr@2
|
2693 |
|
williamr@2
|
2694 |
template <class Tag>
|
williamr@2
|
2695 |
struct adj_list_choose_edge_pmap_helper {
|
williamr@2
|
2696 |
typedef adj_list_any_edge_pmap type;
|
williamr@2
|
2697 |
};
|
williamr@2
|
2698 |
template <>
|
williamr@2
|
2699 |
struct adj_list_choose_edge_pmap_helper<edge_all_t> {
|
williamr@2
|
2700 |
typedef adj_list_all_edge_pmap type;
|
williamr@2
|
2701 |
};
|
williamr@2
|
2702 |
template <class Tag, class Graph, class Property>
|
williamr@2
|
2703 |
struct adj_list_choose_edge_pmap {
|
williamr@2
|
2704 |
typedef typename adj_list_choose_edge_pmap_helper<Tag>::type Helper;
|
williamr@2
|
2705 |
typedef typename Helper::template bind_<Graph,Property,Tag> Bind;
|
williamr@2
|
2706 |
typedef typename Bind::type type;
|
williamr@2
|
2707 |
typedef typename Bind::const_type const_type;
|
williamr@2
|
2708 |
};
|
williamr@2
|
2709 |
struct adj_list_edge_property_selector {
|
williamr@2
|
2710 |
template <class Graph, class Property, class Tag>
|
williamr@2
|
2711 |
struct bind_ {
|
williamr@2
|
2712 |
typedef adj_list_choose_edge_pmap<Tag,Graph,Property> Choice;
|
williamr@2
|
2713 |
typedef typename Choice::type type;
|
williamr@2
|
2714 |
typedef typename Choice::const_type const_type;
|
williamr@2
|
2715 |
};
|
williamr@2
|
2716 |
};
|
williamr@2
|
2717 |
} // namespace detail
|
williamr@2
|
2718 |
|
williamr@2
|
2719 |
template <>
|
williamr@2
|
2720 |
struct edge_property_selector<adj_list_tag> {
|
williamr@2
|
2721 |
typedef detail::adj_list_edge_property_selector type;
|
williamr@2
|
2722 |
};
|
williamr@2
|
2723 |
template <>
|
williamr@2
|
2724 |
struct edge_property_selector<vec_adj_list_tag> {
|
williamr@2
|
2725 |
typedef detail::adj_list_edge_property_selector type;
|
williamr@2
|
2726 |
};
|
williamr@2
|
2727 |
|
williamr@2
|
2728 |
// Vertex Property Maps
|
williamr@2
|
2729 |
|
williamr@2
|
2730 |
struct adj_list_vertex_property_selector {
|
williamr@2
|
2731 |
template <class Graph, class Property, class Tag>
|
williamr@2
|
2732 |
struct bind_ {
|
williamr@2
|
2733 |
typedef detail::adj_list_choose_vertex_pa<Tag,Graph,Property> Choice;
|
williamr@2
|
2734 |
typedef typename Choice::type type;
|
williamr@2
|
2735 |
typedef typename Choice::const_type const_type;
|
williamr@2
|
2736 |
};
|
williamr@2
|
2737 |
};
|
williamr@2
|
2738 |
template <>
|
williamr@2
|
2739 |
struct vertex_property_selector<adj_list_tag> {
|
williamr@2
|
2740 |
typedef adj_list_vertex_property_selector type;
|
williamr@2
|
2741 |
};
|
williamr@2
|
2742 |
|
williamr@2
|
2743 |
struct vec_adj_list_vertex_property_selector {
|
williamr@2
|
2744 |
template <class Graph, class Property, class Tag>
|
williamr@2
|
2745 |
struct bind_ {
|
williamr@2
|
2746 |
typedef detail::vec_adj_list_choose_vertex_pa<Tag,Graph,Property> Choice;
|
williamr@2
|
2747 |
typedef typename Choice::type type;
|
williamr@2
|
2748 |
typedef typename Choice::const_type const_type;
|
williamr@2
|
2749 |
};
|
williamr@2
|
2750 |
};
|
williamr@2
|
2751 |
template <>
|
williamr@2
|
2752 |
struct vertex_property_selector<vec_adj_list_tag> {
|
williamr@2
|
2753 |
typedef vec_adj_list_vertex_property_selector type;
|
williamr@2
|
2754 |
};
|
williamr@2
|
2755 |
|
williamr@2
|
2756 |
} // namespace boost
|
williamr@2
|
2757 |
|
williamr@2
|
2758 |
#if !defined(BOOST_NO_HASH) && !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
|
williamr@2
|
2759 |
namespace BOOST_STD_EXTENSION_NAMESPACE {
|
williamr@2
|
2760 |
|
williamr@2
|
2761 |
#if BOOST_WORKAROUND( _STLPORT_VERSION, >= 0x500 )
|
williamr@2
|
2762 |
// STLport 5 already defines a hash<void*> specialization.
|
williamr@2
|
2763 |
#else
|
williamr@2
|
2764 |
template <>
|
williamr@2
|
2765 |
struct hash< void* > // Need this when vertex_descriptor=void*
|
williamr@2
|
2766 |
{
|
williamr@2
|
2767 |
std::size_t
|
williamr@2
|
2768 |
operator()(void* v) const { return (std::size_t)v; }
|
williamr@2
|
2769 |
};
|
williamr@2
|
2770 |
#endif
|
williamr@2
|
2771 |
|
williamr@2
|
2772 |
template <typename V>
|
williamr@2
|
2773 |
struct hash< boost::detail::stored_edge<V> >
|
williamr@2
|
2774 |
{
|
williamr@2
|
2775 |
std::size_t
|
williamr@2
|
2776 |
operator()(const boost::detail::stored_edge<V>& e) const
|
williamr@2
|
2777 |
{
|
williamr@2
|
2778 |
return hash<V>()(e.m_target);
|
williamr@2
|
2779 |
}
|
williamr@2
|
2780 |
};
|
williamr@2
|
2781 |
|
williamr@2
|
2782 |
template <typename V, typename P>
|
williamr@2
|
2783 |
struct hash< boost::detail::stored_edge_property <V,P> >
|
williamr@2
|
2784 |
{
|
williamr@2
|
2785 |
std::size_t
|
williamr@2
|
2786 |
operator()(const boost::detail::stored_edge_property<V,P>& e) const
|
williamr@2
|
2787 |
{
|
williamr@2
|
2788 |
return hash<V>()(e.m_target);
|
williamr@2
|
2789 |
}
|
williamr@2
|
2790 |
};
|
williamr@2
|
2791 |
|
williamr@2
|
2792 |
template <typename V, typename I, typename P>
|
williamr@2
|
2793 |
struct hash< boost::detail::stored_edge_iter<V,I, P> >
|
williamr@2
|
2794 |
{
|
williamr@2
|
2795 |
std::size_t
|
williamr@2
|
2796 |
operator()(const boost::detail::stored_edge_iter<V,I,P>& e) const
|
williamr@2
|
2797 |
{
|
williamr@2
|
2798 |
return hash<V>()(e.m_target);
|
williamr@2
|
2799 |
}
|
williamr@2
|
2800 |
};
|
williamr@2
|
2801 |
|
williamr@2
|
2802 |
}
|
williamr@2
|
2803 |
#endif
|
williamr@2
|
2804 |
|
williamr@2
|
2805 |
|
williamr@2
|
2806 |
#undef stored_edge
|
williamr@2
|
2807 |
#undef stored_edge_property
|
williamr@2
|
2808 |
#undef stored_edge_iter
|
williamr@2
|
2809 |
|
williamr@2
|
2810 |
#endif // BOOST_GRAPH_DETAIL_DETAIL_ADJACENCY_LIST_CCT
|
williamr@2
|
2811 |
|
williamr@2
|
2812 |
/*
|
williamr@2
|
2813 |
Implementation Notes:
|
williamr@2
|
2814 |
|
williamr@2
|
2815 |
Many of the public interface functions in this file would have been
|
williamr@2
|
2816 |
more conveniently implemented as inline friend functions.
|
williamr@2
|
2817 |
However there are a few compiler bugs that make that approach
|
williamr@2
|
2818 |
non-portable.
|
williamr@2
|
2819 |
|
williamr@2
|
2820 |
1. g++ inline friend in namespace bug
|
williamr@2
|
2821 |
2. g++ using clause doesn't work with inline friends
|
williamr@2
|
2822 |
3. VC++ doesn't have Koenig lookup
|
williamr@2
|
2823 |
|
williamr@2
|
2824 |
For these reasons, the functions were all written as non-inline free
|
williamr@2
|
2825 |
functions, and static cast was used to convert from the helper
|
williamr@2
|
2826 |
class to the adjacency_list derived class.
|
williamr@2
|
2827 |
|
williamr@2
|
2828 |
Looking back, it might have been better to write out all functions
|
williamr@2
|
2829 |
in terms of the adjacency_list, and then use a tag to dispatch
|
williamr@2
|
2830 |
to the various helpers instead of using inheritance.
|
williamr@2
|
2831 |
|
williamr@2
|
2832 |
*/
|