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