| File: | home/bhubbard/working/src/ceph/build/boost/src/Boost/libs/python/src/object/inheritance.cpp |
| Warning: | line 240, column 5 Address of stack memory associated with temporary object of type 'boost::param_not_found' returned to caller |
[?] Use j/k keys for keyboard navigation
| 1 | // Copyright David Abrahams 2002. | |||
| 2 | // Distributed under the Boost Software License, Version 1.0. (See | |||
| 3 | // accompanying file LICENSE_1_0.txt or copy at | |||
| 4 | // http://www.boost.org/LICENSE_1_0.txt) | |||
| 5 | #include <boost/python/object/inheritance.hpp> | |||
| 6 | #include <boost/python/type_id.hpp> | |||
| 7 | #include <boost/graph/breadth_first_search.hpp> | |||
| 8 | #if _MSC_FULL_VER >= 13102171 && _MSC_FULL_VER <= 13102179 | |||
| 9 | # include <boost/graph/reverse_graph.hpp> | |||
| 10 | #endif | |||
| 11 | #include <boost/graph/adjacency_list.hpp> | |||
| 12 | #include <boost/graph/reverse_graph.hpp> | |||
| 13 | #include <boost/property_map/property_map.hpp> | |||
| 14 | #include <boost/bind.hpp> | |||
| 15 | #include <boost/integer_traits.hpp> | |||
| 16 | #include <boost/tuple/tuple.hpp> | |||
| 17 | #include <boost/tuple/tuple_comparison.hpp> | |||
| 18 | #include <queue> | |||
| 19 | #include <vector> | |||
| 20 | #include <functional> | |||
| 21 | ||||
| 22 | // | |||
| 23 | // Procedure: | |||
| 24 | // | |||
| 25 | // The search is a BFS over the space of (type,address) pairs | |||
| 26 | // guided by the edges of the casting graph whose nodes | |||
| 27 | // correspond to classes, and whose edges are traversed by | |||
| 28 | // applying associated cast functions to an address. We use | |||
| 29 | // vertex distance to the goal node in the cast_graph to rate the | |||
| 30 | // paths. The vertex distance to any goal node is calculated on | |||
| 31 | // demand and outdated by the addition of edges to the graph. | |||
| 32 | ||||
| 33 | namespace boost { | |||
| 34 | namespace | |||
| 35 | { | |||
| 36 | enum edge_cast_t { edge_cast = 8010 }; | |||
| 37 | template <class T> inline void unused_variable(const T&) { } | |||
| 38 | } | |||
| 39 | ||||
| 40 | // Install properties | |||
| 41 | BOOST_INSTALL_PROPERTY(edge, cast)template <> struct property_kind<edge_cast_t> { typedef edge_property_tag type; }; | |||
| 42 | ||||
| 43 | namespace | |||
| 44 | { | |||
| 45 | typedef void*(*cast_function)(void*); | |||
| 46 | ||||
| 47 | // | |||
| 48 | // Here we put together the low-level data structures of the | |||
| 49 | // casting graph representation. | |||
| 50 | // | |||
| 51 | typedef python::type_info class_id; | |||
| 52 | ||||
| 53 | // represents a graph of available casts | |||
| 54 | ||||
| 55 | #if 0 | |||
| 56 | struct cast_graph | |||
| 57 | : | |||
| 58 | #else | |||
| 59 | typedef | |||
| 60 | #endif | |||
| 61 | adjacency_list<vecS,vecS, bidirectionalS, no_property | |||
| 62 | ||||
| 63 | // edge index property allows us to look up edges in the connectivity matrix | |||
| 64 | , property<edge_index_t,std::size_t | |||
| 65 | ||||
| 66 | // The function which casts a void* from the edge's source type | |||
| 67 | // to its destination type. | |||
| 68 | , property<edge_cast_t,cast_function> > > | |||
| 69 | #if 0 | |||
| 70 | {}; | |||
| 71 | #else | |||
| 72 | cast_graph; | |||
| 73 | #endif | |||
| 74 | ||||
| 75 | typedef cast_graph::vertex_descriptor vertex_t; | |||
| 76 | typedef cast_graph::edge_descriptor edge_t; | |||
| 77 | ||||
| 78 | struct smart_graph | |||
| 79 | { | |||
| 80 | typedef std::vector<std::size_t>::const_iterator node_distance_map; | |||
| 81 | ||||
| 82 | typedef std::pair<cast_graph::out_edge_iterator | |||
| 83 | , cast_graph::out_edge_iterator> out_edges_t; | |||
| 84 | ||||
| 85 | // Return a map of the distances from any node to the given | |||
| 86 | // target node | |||
| 87 | node_distance_map distances_to(vertex_t target) const | |||
| 88 | { | |||
| 89 | std::size_t n = num_vertices(m_topology); | |||
| 90 | if (m_distances.size() != n * n) | |||
| 91 | { | |||
| 92 | m_distances.clear(); | |||
| 93 | m_distances.resize(n * n, (std::numeric_limits<std::size_t>::max)()); | |||
| 94 | m_known_vertices = n; | |||
| 95 | } | |||
| 96 | ||||
| 97 | std::vector<std::size_t>::iterator to_target = m_distances.begin() + n * target; | |||
| 98 | ||||
| 99 | // this node hasn't been used as a target yet | |||
| 100 | if (to_target[target] != 0) | |||
| 101 | { | |||
| 102 | typedef reverse_graph<cast_graph> reverse_cast_graph; | |||
| 103 | reverse_cast_graph reverse_topology(m_topology); | |||
| 104 | ||||
| 105 | to_target[target] = 0; | |||
| 106 | ||||
| 107 | breadth_first_search( | |||
| 108 | reverse_topology, target | |||
| 109 | , visitor( | |||
| 110 | make_bfs_visitor( | |||
| 111 | record_distances( | |||
| 112 | make_iterator_property_map( | |||
| 113 | to_target | |||
| 114 | , get(vertex_index, reverse_topology) | |||
| 115 | # ifdef BOOST_NO_STD_ITERATOR_TRAITS | |||
| 116 | , *to_target | |||
| 117 | # endif | |||
| 118 | ) | |||
| 119 | , on_tree_edge() | |||
| 120 | )))); | |||
| 121 | } | |||
| 122 | ||||
| 123 | return to_target; | |||
| 124 | } | |||
| 125 | ||||
| 126 | cast_graph& topology() { return m_topology; } | |||
| 127 | cast_graph const& topology() const { return m_topology; } | |||
| 128 | ||||
| 129 | smart_graph() | |||
| 130 | : m_known_vertices(0) | |||
| 131 | {} | |||
| 132 | ||||
| 133 | private: | |||
| 134 | cast_graph m_topology; | |||
| 135 | mutable std::vector<std::size_t> m_distances; | |||
| 136 | mutable std::size_t m_known_vertices; | |||
| 137 | }; | |||
| 138 | ||||
| 139 | smart_graph& full_graph() | |||
| 140 | { | |||
| 141 | static smart_graph x; | |||
| 142 | return x; | |||
| 143 | } | |||
| 144 | ||||
| 145 | smart_graph& up_graph() | |||
| 146 | { | |||
| 147 | static smart_graph x; | |||
| 148 | return x; | |||
| 149 | } | |||
| 150 | ||||
| 151 | // | |||
| 152 | // Our index of class types | |||
| 153 | // | |||
| 154 | using boost::python::objects::dynamic_id_function; | |||
| 155 | typedef tuples::tuple< | |||
| 156 | class_id // static type | |||
| 157 | , vertex_t // corresponding vertex | |||
| 158 | , dynamic_id_function // dynamic_id if polymorphic, or 0 | |||
| 159 | > | |||
| 160 | index_entry_interface; | |||
| 161 | typedef index_entry_interface::inherited index_entry; | |||
| 162 | enum { ksrc_static_t, kvertex, kdynamic_id }; | |||
| 163 | ||||
| 164 | typedef std::vector<index_entry> type_index_t; | |||
| 165 | ||||
| 166 | ||||
| 167 | type_index_t& type_index() | |||
| 168 | { | |||
| 169 | static type_index_t x; | |||
| 170 | return x; | |||
| 171 | } | |||
| 172 | ||||
| 173 | template <class Tuple> | |||
| 174 | struct select1st | |||
| 175 | { | |||
| 176 | typedef typename tuples::element<0, Tuple>::type result_type; | |||
| 177 | ||||
| 178 | result_type const& operator()(Tuple const& x) const | |||
| 179 | { | |||
| 180 | return tuples::get<0>(x); | |||
| 181 | } | |||
| 182 | }; | |||
| 183 | ||||
| 184 | // map a type to a position in the index | |||
| 185 | inline type_index_t::iterator type_position(class_id type) | |||
| 186 | { | |||
| 187 | typedef index_entry entry; | |||
| 188 | ||||
| 189 | return std::lower_bound( | |||
| 190 | type_index().begin(), type_index().end() | |||
| 191 | , boost::make_tuple(type, vertex_t(), dynamic_id_function(0)) | |||
| 192 | , boost::bind<bool>(std::less<class_id>() | |||
| 193 | , boost::bind<class_id>(select1st<entry>(), _1) | |||
| 194 | , boost::bind<class_id>(select1st<entry>(), _2))); | |||
| 195 | } | |||
| 196 | ||||
| 197 | inline index_entry* seek_type(class_id type) | |||
| 198 | { | |||
| 199 | type_index_t::iterator p = type_position(type); | |||
| 200 | if (p == type_index().end() || tuples::get<ksrc_static_t>(*p) != type) | |||
| 201 | return 0; | |||
| 202 | else | |||
| 203 | return &*p; | |||
| 204 | } | |||
| 205 | ||||
| 206 | // Get the entry for a type, inserting if necessary | |||
| 207 | inline type_index_t::iterator demand_type(class_id type) | |||
| 208 | { | |||
| 209 | type_index_t::iterator p = type_position(type); | |||
| 210 | ||||
| 211 | if (p != type_index().end() && tuples::get<ksrc_static_t>(*p) == type) | |||
| 212 | return p; | |||
| 213 | ||||
| 214 | vertex_t v = add_vertex(full_graph().topology()); | |||
| 215 | vertex_t v2 = add_vertex(up_graph().topology()); | |||
| 216 | unused_variable(v2); | |||
| 217 | assert(v == v2)(static_cast<void> (0)); | |||
| 218 | return type_index().insert(p, boost::make_tuple(type, v, dynamic_id_function(0))); | |||
| 219 | } | |||
| 220 | ||||
| 221 | // Map a two types to a vertex in the graph, inserting if necessary | |||
| 222 | typedef std::pair<type_index_t::iterator, type_index_t::iterator> | |||
| 223 | type_index_iterator_pair; | |||
| 224 | ||||
| 225 | inline type_index_iterator_pair | |||
| 226 | demand_types(class_id t1, class_id t2) | |||
| 227 | { | |||
| 228 | // be sure there will be no reallocation | |||
| 229 | type_index().reserve(type_index().size() + 2); | |||
| 230 | type_index_t::iterator first = demand_type(t1); | |||
| 231 | type_index_t::iterator second = demand_type(t2); | |||
| 232 | if (first == second) | |||
| 233 | ++first; | |||
| 234 | return std::make_pair(first, second); | |||
| 235 | } | |||
| 236 | ||||
| 237 | struct q_elt | |||
| 238 | { | |||
| 239 | q_elt(std::size_t distance | |||
| 240 | , void* src_address | |||
| 241 | , vertex_t target | |||
| 242 | , cast_function cast | |||
| 243 | ) | |||
| 244 | : distance(distance) | |||
| 245 | , src_address(src_address) | |||
| 246 | , target(target) | |||
| 247 | , cast(cast) | |||
| 248 | {} | |||
| 249 | ||||
| 250 | std::size_t distance; | |||
| 251 | void* src_address; | |||
| 252 | vertex_t target; | |||
| 253 | cast_function cast; | |||
| 254 | ||||
| 255 | bool operator<(q_elt const& rhs) const | |||
| 256 | { | |||
| 257 | return distance < rhs.distance; | |||
| 258 | } | |||
| 259 | }; | |||
| 260 | ||||
| 261 | // Optimization: | |||
| 262 | // | |||
| 263 | // Given p, src_t, dst_t | |||
| 264 | // | |||
| 265 | // Get a pointer pd to the most-derived object | |||
| 266 | // if it's polymorphic, dynamic_cast to void* | |||
| 267 | // otherwise pd = p | |||
| 268 | // | |||
| 269 | // Get the most-derived typeid src_td | |||
| 270 | // | |||
| 271 | // ptrdiff_t offset = p - pd | |||
| 272 | // | |||
| 273 | // Now we can keep a cache, for [src_t, offset, src_td, dst_t] of | |||
| 274 | // the cast transformation function to use on p and the next src_t | |||
| 275 | // in the chain. src_td, dst_t don't change throughout this | |||
| 276 | // process. In order to represent unreachability, when a pair is | |||
| 277 | // found to be unreachable, we stick a 0-returning "dead-cast" | |||
| 278 | // function in the cache. | |||
| 279 | ||||
| 280 | // This is needed in a few places below | |||
| 281 | inline void* identity_cast(void* p) | |||
| 282 | { | |||
| 283 | return p; | |||
| 284 | } | |||
| 285 | ||||
| 286 | void* search(smart_graph const& g, void* p, vertex_t src, vertex_t dst) | |||
| 287 | { | |||
| 288 | // I think this test was thoroughly bogus -- dwa | |||
| 289 | // If we know there's no path; bail now. | |||
| 290 | // if (src > g.known_vertices() || dst > g.known_vertices()) | |||
| 291 | // return 0; | |||
| 292 | ||||
| 293 | smart_graph::node_distance_map d(g.distances_to(dst)); | |||
| 294 | ||||
| 295 | if (d[src] == (std::numeric_limits<std::size_t>::max)()) | |||
| 296 | return 0; | |||
| 297 | ||||
| 298 | typedef property_map<cast_graph,edge_cast_t>::const_type cast_map; | |||
| 299 | cast_map casts = get(edge_cast, g.topology()); | |||
| 300 | ||||
| 301 | typedef std::pair<vertex_t,void*> search_state; | |||
| 302 | typedef std::vector<search_state> visited_t; | |||
| 303 | visited_t visited; | |||
| 304 | std::priority_queue<q_elt> q; | |||
| 305 | ||||
| 306 | q.push(q_elt(d[src], p, src, identity_cast)); | |||
| 307 | while (!q.empty()) | |||
| 308 | { | |||
| 309 | q_elt top = q.top(); | |||
| 310 | q.pop(); | |||
| 311 | ||||
| 312 | // Check to see if we have a real state | |||
| 313 | void* dst_address = top.cast(top.src_address); | |||
| 314 | if (dst_address == 0) | |||
| 315 | continue; | |||
| 316 | ||||
| 317 | if (top.target == dst) | |||
| 318 | return dst_address; | |||
| 319 | ||||
| 320 | search_state s(top.target,dst_address); | |||
| 321 | ||||
| 322 | visited_t::iterator pos = std::lower_bound( | |||
| 323 | visited.begin(), visited.end(), s); | |||
| 324 | ||||
| 325 | // If already visited, continue | |||
| 326 | if (pos != visited.end() && *pos == s) | |||
| 327 | continue; | |||
| 328 | ||||
| 329 | visited.insert(pos, s); // mark it | |||
| 330 | ||||
| 331 | // expand it: | |||
| 332 | smart_graph::out_edges_t edges = out_edges(s.first, g.topology()); | |||
| 333 | for (cast_graph::out_edge_iterator p = edges.first | |||
| 334 | , finish = edges.second | |||
| 335 | ; p != finish | |||
| 336 | ; ++p | |||
| 337 | ) | |||
| 338 | { | |||
| 339 | edge_t e = *p; | |||
| 340 | q.push(q_elt( | |||
| 341 | d[target(e, g.topology())] | |||
| 342 | , dst_address | |||
| 343 | , target(e, g.topology()) | |||
| 344 | , boost::get(casts, e))); | |||
| 345 | } | |||
| 346 | } | |||
| 347 | return 0; | |||
| 348 | } | |||
| 349 | ||||
| 350 | struct cache_element | |||
| 351 | { | |||
| 352 | typedef tuples::tuple< | |||
| 353 | class_id // source static type | |||
| 354 | , class_id // target type | |||
| 355 | , std::ptrdiff_t // offset within source object | |||
| 356 | , class_id // source dynamic type | |||
| 357 | >::inherited key_type; | |||
| 358 | ||||
| 359 | cache_element(key_type const& k) | |||
| 360 | : key(k) | |||
| 361 | , offset(0) | |||
| 362 | {} | |||
| 363 | ||||
| 364 | key_type key; | |||
| 365 | std::ptrdiff_t offset; | |||
| 366 | ||||
| 367 | BOOST_STATIC_CONSTANT(static const std::ptrdiff_t not_found = integer_traits<std ::ptrdiff_t>::const_min | |||
| 368 | std::ptrdiff_t, not_found = integer_traits<std::ptrdiff_t>::const_min)static const std::ptrdiff_t not_found = integer_traits<std ::ptrdiff_t>::const_min; | |||
| 369 | ||||
| 370 | bool operator<(cache_element const& rhs) const | |||
| 371 | { | |||
| 372 | return this->key < rhs.key; | |||
| 373 | } | |||
| 374 | ||||
| 375 | bool unreachable() const | |||
| 376 | { | |||
| 377 | return offset == not_found; | |||
| 378 | } | |||
| 379 | }; | |||
| 380 | ||||
| 381 | enum { kdst_t = ksrc_static_t + 1, koffset, ksrc_dynamic_t }; | |||
| 382 | typedef std::vector<cache_element> cache_t; | |||
| 383 | ||||
| 384 | cache_t& cache() | |||
| 385 | { | |||
| 386 | static cache_t x; | |||
| 387 | return x; | |||
| 388 | } | |||
| 389 | ||||
| 390 | inline void* convert_type(void* const p, class_id src_t, class_id dst_t, bool polymorphic) | |||
| 391 | { | |||
| 392 | // Quickly rule out unregistered types | |||
| 393 | index_entry* src_p = seek_type(src_t); | |||
| 394 | if (src_p == 0) | |||
| 395 | return 0; | |||
| 396 | ||||
| 397 | index_entry* dst_p = seek_type(dst_t); | |||
| 398 | if (dst_p == 0) | |||
| 399 | return 0; | |||
| 400 | ||||
| 401 | // Look up the dynamic_id function and call it to get the dynamic | |||
| 402 | // info | |||
| 403 | boost::python::objects::dynamic_id_t dynamic_id = polymorphic | |||
| 404 | ? tuples::get<kdynamic_id>(*src_p)(p) | |||
| 405 | : std::make_pair(p, src_t); | |||
| 406 | ||||
| 407 | // Look in the cache first for a quickie address translation | |||
| 408 | std::ptrdiff_t offset = (char*)p - (char*)dynamic_id.first; | |||
| 409 | ||||
| 410 | cache_element seek(boost::make_tuple(src_t, dst_t, offset, dynamic_id.second)); | |||
| 411 | cache_t& c = cache(); | |||
| 412 | cache_t::iterator const cache_pos | |||
| 413 | = std::lower_bound(c.begin(), c.end(), seek); | |||
| 414 | ||||
| 415 | ||||
| 416 | // if found in the cache, we're done | |||
| 417 | if (cache_pos != c.end() && cache_pos->key == seek.key) | |||
| 418 | { | |||
| 419 | return cache_pos->offset == cache_element::not_found | |||
| 420 | ? 0 : (char*)p + cache_pos->offset; | |||
| 421 | } | |||
| 422 | ||||
| 423 | // If we are starting at the most-derived type, only look in the up graph | |||
| 424 | smart_graph const& g = polymorphic && dynamic_id.second != src_t | |||
| 425 | ? full_graph() : up_graph(); | |||
| 426 | ||||
| 427 | void* result = search( | |||
| 428 | g, p, tuples::get<kvertex>(*src_p) | |||
| 429 | , tuples::get<kvertex>(*dst_p)); | |||
| 430 | ||||
| 431 | // update the cache | |||
| 432 | c.insert(cache_pos, seek)->offset | |||
| 433 | = (result == 0) ? cache_element::not_found : (char*)result - (char*)p; | |||
| 434 | ||||
| 435 | return result; | |||
| 436 | } | |||
| 437 | } | |||
| 438 | ||||
| 439 | namespace python { namespace objects { | |||
| 440 | ||||
| 441 | BOOST_PYTHON_DECL void* find_dynamic_type(void* p, class_id src_t, class_id dst_t) | |||
| 442 | { | |||
| 443 | return convert_type(p, src_t, dst_t, true); | |||
| 444 | } | |||
| 445 | ||||
| 446 | BOOST_PYTHON_DECL void* find_static_type(void* p, class_id src_t, class_id dst_t) | |||
| 447 | { | |||
| 448 | return convert_type(p, src_t, dst_t, false); | |||
| ||||
| 449 | } | |||
| 450 | ||||
| 451 | BOOST_PYTHON_DECL void add_cast( | |||
| 452 | class_id src_t, class_id dst_t, cast_function cast, bool is_downcast) | |||
| 453 | { | |||
| 454 | // adding an edge will invalidate any record of unreachability in | |||
| 455 | // the cache. | |||
| 456 | static std::size_t expected_cache_len = 0; | |||
| 457 | cache_t& c = cache(); | |||
| 458 | if (c.size() > expected_cache_len) | |||
| 459 | { | |||
| 460 | c.erase(std::remove_if( | |||
| 461 | c.begin(), c.end(), | |||
| 462 | mem_fn(&cache_element::unreachable)) | |||
| 463 | , c.end()); | |||
| 464 | ||||
| 465 | // If any new cache entries get added, we'll have to do this | |||
| 466 | // again when the next edge is added | |||
| 467 | expected_cache_len = c.size(); | |||
| 468 | } | |||
| 469 | ||||
| 470 | type_index_iterator_pair types = demand_types(src_t, dst_t); | |||
| 471 | vertex_t src = tuples::get<kvertex>(*types.first); | |||
| 472 | vertex_t dst = tuples::get<kvertex>(*types.second); | |||
| 473 | ||||
| 474 | cast_graph* const g[2] = { &up_graph().topology(), &full_graph().topology() }; | |||
| 475 | ||||
| 476 | for (cast_graph*const* p = g + (is_downcast ? 1 : 0); p < g + 2; ++p) | |||
| 477 | { | |||
| 478 | edge_t e; | |||
| 479 | bool added; | |||
| 480 | ||||
| 481 | tie(e, added) = add_edge(src, dst, **p); | |||
| 482 | assert(added)(static_cast<void> (0)); | |||
| 483 | ||||
| 484 | put(get(edge_cast, **p), e, cast); | |||
| 485 | put(get(edge_index, **p), e, num_edges(full_graph().topology()) - 1); | |||
| 486 | } | |||
| 487 | } | |||
| 488 | ||||
| 489 | BOOST_PYTHON_DECL void register_dynamic_id_aux( | |||
| 490 | class_id static_id, dynamic_id_function get_dynamic_id) | |||
| 491 | { | |||
| 492 | tuples::get<kdynamic_id>(*demand_type(static_id)) = get_dynamic_id; | |||
| 493 | } | |||
| 494 | ||||
| 495 | }}} // namespace boost::python::objects |
| 1 | // |
| 2 | //======================================================================= |
| 3 | // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. |
| 4 | // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek |
| 5 | // |
| 6 | // Distributed under the Boost Software License, Version 1.0. (See |
| 7 | // accompanying file LICENSE_1_0.txt or copy at |
| 8 | // http://www.boost.org/LICENSE_1_0.txt) |
| 9 | //======================================================================= |
| 10 | // |
| 11 | #ifndef BOOST_GRAPH_BREADTH_FIRST_SEARCH_HPP |
| 12 | #define BOOST_GRAPH_BREADTH_FIRST_SEARCH_HPP |
| 13 | |
| 14 | /* |
| 15 | Breadth First Search Algorithm (Cormen, Leiserson, and Rivest p. 470) |
| 16 | */ |
| 17 | #include <boost/config.hpp> |
| 18 | #include <vector> |
| 19 | #include <boost/pending/queue.hpp> |
| 20 | #include <boost/graph/graph_traits.hpp> |
| 21 | #include <boost/graph/graph_concepts.hpp> |
| 22 | #include <boost/graph/visitors.hpp> |
| 23 | #include <boost/graph/named_function_params.hpp> |
| 24 | #include <boost/graph/overloading.hpp> |
| 25 | #include <boost/graph/graph_concepts.hpp> |
| 26 | #include <boost/graph/two_bit_color_map.hpp> |
| 27 | #include <boost/concept/assert.hpp> |
| 28 | |
| 29 | #ifdef BOOST_GRAPH_USE_MPI |
| 30 | #include <boost/graph/distributed/concepts.hpp> |
| 31 | #endif // BOOST_GRAPH_USE_MPI |
| 32 | |
| 33 | namespace boost { |
| 34 | |
| 35 | template <class Visitor, class Graph> |
| 36 | struct BFSVisitorConcept { |
| 37 | void constraints() { |
| 38 | BOOST_CONCEPT_ASSERT(( CopyConstructibleConcept<Visitor> ))typedef ::boost::concepts::detail::instantiate< &::boost ::concepts::requirement_<void(*)( CopyConstructibleConcept <Visitor> )>::failed> boost_concept_check38 __attribute__ ((__unused__)); |
| 39 | vis.initialize_vertex(u, g); |
| 40 | vis.discover_vertex(u, g); |
| 41 | vis.examine_vertex(u, g); |
| 42 | vis.examine_edge(e, g); |
| 43 | vis.tree_edge(e, g); |
| 44 | vis.non_tree_edge(e, g); |
| 45 | vis.gray_target(e, g); |
| 46 | vis.black_target(e, g); |
| 47 | vis.finish_vertex(u, g); |
| 48 | } |
| 49 | Visitor vis; |
| 50 | Graph g; |
| 51 | typename graph_traits<Graph>::vertex_descriptor u; |
| 52 | typename graph_traits<Graph>::edge_descriptor e; |
| 53 | }; |
| 54 | |
| 55 | |
| 56 | // Multiple-source version |
| 57 | template <class IncidenceGraph, class Buffer, class BFSVisitor, |
| 58 | class ColorMap, class SourceIterator> |
| 59 | void breadth_first_visit |
| 60 | (const IncidenceGraph& g, |
| 61 | SourceIterator sources_begin, SourceIterator sources_end, |
| 62 | Buffer& Q, BFSVisitor vis, ColorMap color) |
| 63 | { |
| 64 | BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<IncidenceGraph> ))typedef ::boost::concepts::detail::instantiate< &::boost ::concepts::requirement_<void(*)( IncidenceGraphConcept< IncidenceGraph> )>::failed> boost_concept_check64 __attribute__ ((__unused__)); |
| 65 | typedef graph_traits<IncidenceGraph> GTraits; |
| 66 | typedef typename GTraits::vertex_descriptor Vertex; |
| 67 | BOOST_CONCEPT_ASSERT(( BFSVisitorConcept<BFSVisitor, IncidenceGraph> ))typedef ::boost::concepts::detail::instantiate< &::boost ::concepts::requirement_<void(*)( BFSVisitorConcept<BFSVisitor , IncidenceGraph> )>::failed> boost_concept_check67 __attribute__ ((__unused__)); |
| 68 | BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<ColorMap, Vertex> ))typedef ::boost::concepts::detail::instantiate< &::boost ::concepts::requirement_<void(*)( ReadWritePropertyMapConcept <ColorMap, Vertex> )>::failed> boost_concept_check68 __attribute__((__unused__)); |
| 69 | typedef typename property_traits<ColorMap>::value_type ColorValue; |
| 70 | typedef color_traits<ColorValue> Color; |
| 71 | typename GTraits::out_edge_iterator ei, ei_end; |
| 72 | |
| 73 | for (; sources_begin != sources_end; ++sources_begin) { |
| 74 | Vertex s = *sources_begin; |
| 75 | put(color, s, Color::gray()); vis.discover_vertex(s, g); |
| 76 | Q.push(s); |
| 77 | } |
| 78 | while (! Q.empty()) { |
| 79 | Vertex u = Q.top(); Q.pop(); vis.examine_vertex(u, g); |
| 80 | for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) { |
| 81 | Vertex v = target(*ei, g); vis.examine_edge(*ei, g); |
| 82 | ColorValue v_color = get(color, v); |
| 83 | if (v_color == Color::white()) { vis.tree_edge(*ei, g); |
| 84 | put(color, v, Color::gray()); vis.discover_vertex(v, g); |
| 85 | Q.push(v); |
| 86 | } else { vis.non_tree_edge(*ei, g); |
| 87 | if (v_color == Color::gray()) vis.gray_target(*ei, g); |
| 88 | else vis.black_target(*ei, g); |
| 89 | } |
| 90 | } // end for |
| 91 | put(color, u, Color::black()); vis.finish_vertex(u, g); |
| 92 | } // end while |
| 93 | } // breadth_first_visit |
| 94 | |
| 95 | // Single-source version |
| 96 | template <class IncidenceGraph, class Buffer, class BFSVisitor, |
| 97 | class ColorMap> |
| 98 | void breadth_first_visit |
| 99 | (const IncidenceGraph& g, |
| 100 | typename graph_traits<IncidenceGraph>::vertex_descriptor s, |
| 101 | Buffer& Q, BFSVisitor vis, ColorMap color) |
| 102 | { |
| 103 | typename graph_traits<IncidenceGraph>::vertex_descriptor sources[1] = {s}; |
| 104 | breadth_first_visit(g, sources, sources + 1, Q, vis, color); |
| 105 | } |
| 106 | |
| 107 | |
| 108 | template <class VertexListGraph, class SourceIterator, |
| 109 | class Buffer, class BFSVisitor, |
| 110 | class ColorMap> |
| 111 | void breadth_first_search |
| 112 | (const VertexListGraph& g, |
| 113 | SourceIterator sources_begin, SourceIterator sources_end, |
| 114 | Buffer& Q, BFSVisitor vis, ColorMap color) |
| 115 | { |
| 116 | // Initialization |
| 117 | typedef typename property_traits<ColorMap>::value_type ColorValue; |
| 118 | typedef color_traits<ColorValue> Color; |
| 119 | typename boost::graph_traits<VertexListGraph>::vertex_iterator i, i_end; |
| 120 | for (boost::tie(i, i_end) = vertices(g); i != i_end; ++i) { |
| 121 | vis.initialize_vertex(*i, g); |
| 122 | put(color, *i, Color::white()); |
| 123 | } |
| 124 | breadth_first_visit(g, sources_begin, sources_end, Q, vis, color); |
| 125 | } |
| 126 | |
| 127 | template <class VertexListGraph, class Buffer, class BFSVisitor, |
| 128 | class ColorMap> |
| 129 | void breadth_first_search |
| 130 | (const VertexListGraph& g, |
| 131 | typename graph_traits<VertexListGraph>::vertex_descriptor s, |
| 132 | Buffer& Q, BFSVisitor vis, ColorMap color) |
| 133 | { |
| 134 | typename graph_traits<VertexListGraph>::vertex_descriptor sources[1] = {s}; |
| 135 | breadth_first_search(g, sources, sources + 1, Q, vis, color); |
| 136 | } |
| 137 | |
| 138 | namespace graph { struct bfs_visitor_event_not_overridden {}; } |
| 139 | |
| 140 | |
| 141 | template <class Visitors = null_visitor> |
| 142 | class bfs_visitor { |
| 143 | public: |
| 144 | bfs_visitor() { } |
| 145 | bfs_visitor(Visitors vis) : m_vis(vis) { } |
| 146 | |
| 147 | template <class Vertex, class Graph> |
| 148 | graph::bfs_visitor_event_not_overridden |
| 149 | initialize_vertex(Vertex u, Graph& g) |
| 150 | { |
| 151 | invoke_visitors(m_vis, u, g, ::boost::on_initialize_vertex()); |
| 152 | return graph::bfs_visitor_event_not_overridden(); |
| 153 | } |
| 154 | |
| 155 | template <class Vertex, class Graph> |
| 156 | graph::bfs_visitor_event_not_overridden |
| 157 | discover_vertex(Vertex u, Graph& g) |
| 158 | { |
| 159 | invoke_visitors(m_vis, u, g, ::boost::on_discover_vertex()); |
| 160 | return graph::bfs_visitor_event_not_overridden(); |
| 161 | } |
| 162 | |
| 163 | template <class Vertex, class Graph> |
| 164 | graph::bfs_visitor_event_not_overridden |
| 165 | examine_vertex(Vertex u, Graph& g) |
| 166 | { |
| 167 | invoke_visitors(m_vis, u, g, ::boost::on_examine_vertex()); |
| 168 | return graph::bfs_visitor_event_not_overridden(); |
| 169 | } |
| 170 | |
| 171 | template <class Edge, class Graph> |
| 172 | graph::bfs_visitor_event_not_overridden |
| 173 | examine_edge(Edge e, Graph& g) |
| 174 | { |
| 175 | invoke_visitors(m_vis, e, g, ::boost::on_examine_edge()); |
| 176 | return graph::bfs_visitor_event_not_overridden(); |
| 177 | } |
| 178 | |
| 179 | template <class Edge, class Graph> |
| 180 | graph::bfs_visitor_event_not_overridden |
| 181 | tree_edge(Edge e, Graph& g) |
| 182 | { |
| 183 | invoke_visitors(m_vis, e, g, ::boost::on_tree_edge()); |
| 184 | return graph::bfs_visitor_event_not_overridden(); |
| 185 | } |
| 186 | |
| 187 | template <class Edge, class Graph> |
| 188 | graph::bfs_visitor_event_not_overridden |
| 189 | non_tree_edge(Edge e, Graph& g) |
| 190 | { |
| 191 | invoke_visitors(m_vis, e, g, ::boost::on_non_tree_edge()); |
| 192 | return graph::bfs_visitor_event_not_overridden(); |
| 193 | } |
| 194 | |
| 195 | template <class Edge, class Graph> |
| 196 | graph::bfs_visitor_event_not_overridden |
| 197 | gray_target(Edge e, Graph& g) |
| 198 | { |
| 199 | invoke_visitors(m_vis, e, g, ::boost::on_gray_target()); |
| 200 | return graph::bfs_visitor_event_not_overridden(); |
| 201 | } |
| 202 | |
| 203 | template <class Edge, class Graph> |
| 204 | graph::bfs_visitor_event_not_overridden |
| 205 | black_target(Edge e, Graph& g) |
| 206 | { |
| 207 | invoke_visitors(m_vis, e, g, ::boost::on_black_target()); |
| 208 | return graph::bfs_visitor_event_not_overridden(); |
| 209 | } |
| 210 | |
| 211 | template <class Vertex, class Graph> |
| 212 | graph::bfs_visitor_event_not_overridden |
| 213 | finish_vertex(Vertex u, Graph& g) |
| 214 | { |
| 215 | invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex()); |
| 216 | return graph::bfs_visitor_event_not_overridden(); |
| 217 | } |
| 218 | |
| 219 | BOOST_GRAPH_EVENT_STUB(on_initialize_vertex,bfs)typedef ::boost::on_initialize_vertex on_initialize_vertex_type ; template<typename Visitor> bfs_visitor<std::pair< detail::functor_to_visitor<on_initialize_vertex_type, Visitor >, Visitors> > do_on_initialize_vertex(Visitor visitor ) { typedef std::pair<detail::functor_to_visitor<on_initialize_vertex_type , Visitor>, Visitors> visitor_list; typedef bfs_visitor <visitor_list> result_type; return result_type(visitor_list (visitor, m_vis)); } |
| 220 | BOOST_GRAPH_EVENT_STUB(on_discover_vertex,bfs)typedef ::boost::on_discover_vertex on_discover_vertex_type; template <typename Visitor> bfs_visitor<std::pair<detail:: functor_to_visitor<on_discover_vertex_type, Visitor>, Visitors > > do_on_discover_vertex(Visitor visitor) { typedef std ::pair<detail::functor_to_visitor<on_discover_vertex_type , Visitor>, Visitors> visitor_list; typedef bfs_visitor <visitor_list> result_type; return result_type(visitor_list (visitor, m_vis)); } |
| 221 | BOOST_GRAPH_EVENT_STUB(on_examine_vertex,bfs)typedef ::boost::on_examine_vertex on_examine_vertex_type; template <typename Visitor> bfs_visitor<std::pair<detail:: functor_to_visitor<on_examine_vertex_type, Visitor>, Visitors > > do_on_examine_vertex(Visitor visitor) { typedef std ::pair<detail::functor_to_visitor<on_examine_vertex_type , Visitor>, Visitors> visitor_list; typedef bfs_visitor <visitor_list> result_type; return result_type(visitor_list (visitor, m_vis)); } |
| 222 | BOOST_GRAPH_EVENT_STUB(on_examine_edge,bfs)typedef ::boost::on_examine_edge on_examine_edge_type; template <typename Visitor> bfs_visitor<std::pair<detail:: functor_to_visitor<on_examine_edge_type, Visitor>, Visitors > > do_on_examine_edge(Visitor visitor) { typedef std:: pair<detail::functor_to_visitor<on_examine_edge_type, Visitor >, Visitors> visitor_list; typedef bfs_visitor<visitor_list > result_type; return result_type(visitor_list(visitor, m_vis )); } |
| 223 | BOOST_GRAPH_EVENT_STUB(on_tree_edge,bfs)typedef ::boost::on_tree_edge on_tree_edge_type; template< typename Visitor> bfs_visitor<std::pair<detail::functor_to_visitor <on_tree_edge_type, Visitor>, Visitors> > do_on_tree_edge (Visitor visitor) { typedef std::pair<detail::functor_to_visitor <on_tree_edge_type, Visitor>, Visitors> visitor_list ; typedef bfs_visitor<visitor_list> result_type; return result_type(visitor_list(visitor, m_vis)); } |
| 224 | BOOST_GRAPH_EVENT_STUB(on_non_tree_edge,bfs)typedef ::boost::on_non_tree_edge on_non_tree_edge_type; template <typename Visitor> bfs_visitor<std::pair<detail:: functor_to_visitor<on_non_tree_edge_type, Visitor>, Visitors > > do_on_non_tree_edge(Visitor visitor) { typedef std:: pair<detail::functor_to_visitor<on_non_tree_edge_type, Visitor >, Visitors> visitor_list; typedef bfs_visitor<visitor_list > result_type; return result_type(visitor_list(visitor, m_vis )); } |
| 225 | BOOST_GRAPH_EVENT_STUB(on_gray_target,bfs)typedef ::boost::on_gray_target on_gray_target_type; template <typename Visitor> bfs_visitor<std::pair<detail:: functor_to_visitor<on_gray_target_type, Visitor>, Visitors > > do_on_gray_target(Visitor visitor) { typedef std::pair <detail::functor_to_visitor<on_gray_target_type, Visitor >, Visitors> visitor_list; typedef bfs_visitor<visitor_list > result_type; return result_type(visitor_list(visitor, m_vis )); } |
| 226 | BOOST_GRAPH_EVENT_STUB(on_black_target,bfs)typedef ::boost::on_black_target on_black_target_type; template <typename Visitor> bfs_visitor<std::pair<detail:: functor_to_visitor<on_black_target_type, Visitor>, Visitors > > do_on_black_target(Visitor visitor) { typedef std:: pair<detail::functor_to_visitor<on_black_target_type, Visitor >, Visitors> visitor_list; typedef bfs_visitor<visitor_list > result_type; return result_type(visitor_list(visitor, m_vis )); } |
| 227 | BOOST_GRAPH_EVENT_STUB(on_finish_vertex,bfs)typedef ::boost::on_finish_vertex on_finish_vertex_type; template <typename Visitor> bfs_visitor<std::pair<detail:: functor_to_visitor<on_finish_vertex_type, Visitor>, Visitors > > do_on_finish_vertex(Visitor visitor) { typedef std:: pair<detail::functor_to_visitor<on_finish_vertex_type, Visitor >, Visitors> visitor_list; typedef bfs_visitor<visitor_list > result_type; return result_type(visitor_list(visitor, m_vis )); } |
| 228 | |
| 229 | protected: |
| 230 | Visitors m_vis; |
| 231 | }; |
| 232 | template <class Visitors> |
| 233 | bfs_visitor<Visitors> |
| 234 | make_bfs_visitor(Visitors vis) { |
| 235 | return bfs_visitor<Visitors>(vis); |
| 236 | } |
| 237 | typedef bfs_visitor<> default_bfs_visitor; |
| 238 | |
| 239 | |
| 240 | namespace detail { |
| 241 | |
| 242 | template <class VertexListGraph, class ColorMap, class BFSVisitor, |
| 243 | class P, class T, class R> |
| 244 | void bfs_helper |
| 245 | (VertexListGraph& g, |
| 246 | typename graph_traits<VertexListGraph>::vertex_descriptor s, |
| 247 | ColorMap color, |
| 248 | BFSVisitor vis, |
| 249 | const bgl_named_params<P, T, R>& params, |
| 250 | boost::mpl::false_) |
| 251 | { |
| 252 | typedef graph_traits<VertexListGraph> Traits; |
| 253 | // Buffer default |
| 254 | typedef typename Traits::vertex_descriptor Vertex; |
| 255 | typedef boost::queue<Vertex> queue_t; |
| 256 | queue_t Q; |
| 257 | breadth_first_search |
| 258 | (g, s, |
| 259 | choose_param(get_param(params, buffer_param_t()), boost::ref(Q)).get(), |
| 260 | vis, color); |
| 261 | } |
| 262 | |
| 263 | #ifdef BOOST_GRAPH_USE_MPI |
| 264 | template <class DistributedGraph, class ColorMap, class BFSVisitor, |
| 265 | class P, class T, class R> |
| 266 | void bfs_helper |
| 267 | (DistributedGraph& g, |
| 268 | typename graph_traits<DistributedGraph>::vertex_descriptor s, |
| 269 | ColorMap color, |
| 270 | BFSVisitor vis, |
| 271 | const bgl_named_params<P, T, R>& params, |
| 272 | boost::mpl::true_); |
| 273 | #endif // BOOST_GRAPH_USE_MPI |
| 274 | |
| 275 | //------------------------------------------------------------------------- |
| 276 | // Choose between default color and color parameters. Using |
| 277 | // function dispatching so that we don't require vertex index if |
| 278 | // the color default is not being used. |
| 279 | |
| 280 | template <class ColorMap> |
| 281 | struct bfs_dispatch { |
| 282 | template <class VertexListGraph, class P, class T, class R> |
| 283 | static void apply |
| 284 | (VertexListGraph& g, |
| 285 | typename graph_traits<VertexListGraph>::vertex_descriptor s, |
| 286 | const bgl_named_params<P, T, R>& params, |
| 287 | ColorMap color) |
| 288 | { |
| 289 | bfs_helper |
| 290 | (g, s, color, |
| 291 | choose_param(get_param(params, graph_visitor), |
| 292 | make_bfs_visitor(null_visitor())), |
| 293 | params, |
| 294 | boost::mpl::bool_< |
| 295 | boost::is_base_and_derived< |
| 296 | distributed_graph_tag, |
| 297 | typename graph_traits<VertexListGraph>::traversal_category>::value>()); |
| 298 | } |
| 299 | }; |
| 300 | |
| 301 | template <> |
| 302 | struct bfs_dispatch<param_not_found> { |
| 303 | template <class VertexListGraph, class P, class T, class R> |
| 304 | static void apply |
| 305 | (VertexListGraph& g, |
| 306 | typename graph_traits<VertexListGraph>::vertex_descriptor s, |
| 307 | const bgl_named_params<P, T, R>& params, |
| 308 | param_not_found) |
| 309 | { |
| 310 | null_visitor null_vis; |
| 311 | |
| 312 | bfs_helper |
| 313 | (g, s, |
| 314 | make_two_bit_color_map |
| 315 | (num_vertices(g), |
| 316 | choose_const_pmap(get_param(params, vertex_index), |
| 317 | g, vertex_index)), |
| 318 | choose_param(get_param(params, graph_visitor), |
| 319 | make_bfs_visitor(null_vis)), |
| 320 | params, |
| 321 | boost::mpl::bool_< |
| 322 | boost::is_base_and_derived< |
| 323 | distributed_graph_tag, |
| 324 | typename graph_traits<VertexListGraph>::traversal_category>::value>()); |
| 325 | } |
| 326 | }; |
| 327 | |
| 328 | } // namespace detail |
| 329 | |
| 330 | #if 1 |
| 331 | // Named Parameter Variant |
| 332 | template <class VertexListGraph, class P, class T, class R> |
| 333 | void breadth_first_search |
| 334 | (const VertexListGraph& g, |
| 335 | typename graph_traits<VertexListGraph>::vertex_descriptor s, |
| 336 | const bgl_named_params<P, T, R>& params) |
| 337 | { |
| 338 | // The graph is passed by *const* reference so that graph adaptors |
| 339 | // (temporaries) can be passed into this function. However, the |
| 340 | // graph is not really const since we may write to property maps |
| 341 | // of the graph. |
| 342 | VertexListGraph& ng = const_cast<VertexListGraph&>(g); |
| 343 | typedef typename get_param_type< vertex_color_t, bgl_named_params<P,T,R> >::type C; |
| 344 | detail::bfs_dispatch<C>::apply(ng, s, params, |
| 345 | get_param(params, vertex_color)); |
| 346 | } |
| 347 | #endif |
| 348 | |
| 349 | |
| 350 | // This version does not initialize colors, user has to. |
| 351 | |
| 352 | template <class IncidenceGraph, class P, class T, class R> |
| 353 | void breadth_first_visit |
| 354 | (const IncidenceGraph& g, |
| 355 | typename graph_traits<IncidenceGraph>::vertex_descriptor s, |
| 356 | const bgl_named_params<P, T, R>& params) |
| 357 | { |
| 358 | // The graph is passed by *const* reference so that graph adaptors |
| 359 | // (temporaries) can be passed into this function. However, the |
| 360 | // graph is not really const since we may write to property maps |
| 361 | // of the graph. |
| 362 | IncidenceGraph& ng = const_cast<IncidenceGraph&>(g); |
| 363 | |
| 364 | typedef graph_traits<IncidenceGraph> Traits; |
| 365 | // Buffer default |
| 366 | typedef typename Traits::vertex_descriptor vertex_descriptor; |
| 367 | typedef boost::queue<vertex_descriptor> queue_t; |
| 368 | queue_t Q; |
| 369 | |
| 370 | breadth_first_visit |
| 371 | (ng, s, |
| 372 | choose_param(get_param(params, buffer_param_t()), boost::ref(Q)).get(), |
| 373 | choose_param(get_param(params, graph_visitor), |
| 374 | make_bfs_visitor(null_visitor())), |
| 375 | choose_pmap(get_param(params, vertex_color), ng, vertex_color) |
| 376 | ); |
| 377 | } |
| 378 | |
| 379 | namespace graph { |
| 380 | namespace detail { |
| 381 | template <typename Graph, typename Source> |
| 382 | struct breadth_first_search_impl { |
| 383 | typedef void result_type; |
| 384 | template <typename ArgPack> |
| 385 | void operator()(const Graph& g, const Source& source, const ArgPack& arg_pack) { |
| 386 | using namespace boost::graph::keywords; |
| 387 | typename boost::graph_traits<Graph>::vertex_descriptor sources[1] = {source}; |
| 388 | boost::queue<typename boost::graph_traits<Graph>::vertex_descriptor> Q; |
| 389 | boost::breadth_first_search(g, |
| 390 | &sources[0], |
| 391 | &sources[1], |
| 392 | boost::unwrap_ref(arg_pack[_buffer | boost::ref(Q)]), |
| 393 | arg_pack[_visitor | make_bfs_visitor(null_visitor())], |
| 394 | boost::detail::make_color_map_from_arg_pack(g, arg_pack)); |
| 395 | } |
| 396 | }; |
| 397 | } |
| 398 | BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(breadth_first_search, 2, 4)template < typename Param0 , typename Param1 , typename ArgPack > typename boost::result_of< detail::breadth_first_search_impl < Param0 , Param1>( Param0 , Param1 , const ArgPack& ) >::type breadth_first_search_with_named_params( const Param0 & param0 , const Param1 & param1 , const ArgPack& arg_pack) { return detail::breadth_first_search_impl< Param0 , Param1>()( param0 , param1 , arg_pack); } template < typename Param0 , typename Param1 > typename boost::result_of < detail::breadth_first_search_impl< Param0 , Param1> ( Param0 , Param1 , const typename boost::detail::make_arg_pack_type <void( )>::type&) >::type breadth_first_search( const Param0 & param0 , const Param1 & param1 ) { return detail ::breadth_first_search_impl< Param0 , Param1>() ( param0 , param1, (boost::parameter::aux::empty_arg_list() )); } template < typename Param0 , typename Param1 , typename Keyword0 , typename Arg0> typename boost::result_of< detail::breadth_first_search_impl < Param0 , Param1> ( Param0 , Param1 , const typename boost ::detail::make_arg_pack_type<void( Keyword0 , Arg0)>::type &) >::type breadth_first_search( const Param0 & param0 , const Param1 & param1 , const boost::parameter::aux::tagged_argument <Keyword0, Arg0>& kw0) { return detail::breadth_first_search_impl < Param0 , Param1>() ( param0 , param1, (boost::parameter ::aux::empty_arg_list() , kw0)); } template < typename Param0 , typename Param1 , typename Keyword0 , typename Keyword1 , typename Arg0 , typename Arg1> typename boost::result_of< detail ::breadth_first_search_impl< Param0 , Param1> ( Param0 , Param1 , const typename boost::detail::make_arg_pack_type< void( Keyword0 , Keyword1 , Arg0 , Arg1)>::type&) > ::type breadth_first_search( const Param0 & param0 , const Param1 & param1 , const boost::parameter::aux::tagged_argument <Keyword0, Arg0>& kw0 , const boost::parameter::aux ::tagged_argument<Keyword1, Arg1>& kw1) { return detail ::breadth_first_search_impl< Param0 , Param1>() ( param0 , param1, (boost::parameter::aux::empty_arg_list() , kw0 , kw1 )); } template < typename Param0 , typename Param1 , typename Keyword0 , typename Keyword1 , typename Keyword2 , typename Arg0 , typename Arg1 , typename Arg2> typename boost::result_of < detail::breadth_first_search_impl< Param0 , Param1> ( Param0 , Param1 , const typename boost::detail::make_arg_pack_type <void( Keyword0 , Keyword1 , Keyword2 , Arg0 , Arg1 , Arg2 )>::type&) >::type breadth_first_search( const Param0 & param0 , const Param1 & param1 , const boost::parameter ::aux::tagged_argument<Keyword0, Arg0>& kw0 , const boost::parameter::aux::tagged_argument<Keyword1, Arg1> & kw1 , const boost::parameter::aux::tagged_argument<Keyword2 , Arg2>& kw2) { return detail::breadth_first_search_impl < Param0 , Param1>() ( param0 , param1, (boost::parameter ::aux::empty_arg_list() , kw0 , kw1 , kw2)); } template < typename Param0 , typename Param1 , typename Keyword0 , typename Keyword1 , typename Keyword2 , typename Keyword3 , typename Arg0 , typename Arg1 , typename Arg2 , typename Arg3> typename boost::result_of < detail::breadth_first_search_impl< Param0 , Param1> ( Param0 , Param1 , const typename boost::detail::make_arg_pack_type <void( Keyword0 , Keyword1 , Keyword2 , Keyword3 , Arg0 , Arg1 , Arg2 , Arg3)>::type&) >::type breadth_first_search ( const Param0 & param0 , const Param1 & param1 , const boost::parameter::aux::tagged_argument<Keyword0, Arg0> & kw0 , const boost::parameter::aux::tagged_argument<Keyword1 , Arg1>& kw1 , const boost::parameter::aux::tagged_argument <Keyword2, Arg2>& kw2 , const boost::parameter::aux ::tagged_argument<Keyword3, Arg3>& kw3) { return detail ::breadth_first_search_impl< Param0 , Param1>() ( param0 , param1, (boost::parameter::aux::empty_arg_list() , kw0 , kw1 , kw2 , kw3)); } |
| 399 | } |
| 400 | |
| 401 | #if 0 |
| 402 | // Named Parameter Variant |
| 403 | BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(breadth_first_search, 2)template < typename Param0 , typename Param1 , class P, class T, class R> typename boost::result_of< ::boost::graph:: detail::breadth_first_search_impl < Param0 , Param1 > ( Param0 , Param1 , const typename boost::detail::convert_bgl_params_to_boost_parameter <boost::bgl_named_params<P, T, R> >::type &) > ::type breadth_first_search( const Param0 & param0 , const Param1 & param1 , const boost::bgl_named_params<P, T, R>& old_style_params) { typedef boost::bgl_named_params <P, T, R> old_style_params_type; typedef typename boost ::detail::convert_bgl_params_to_boost_parameter<old_style_params_type >::type arg_pack_type; arg_pack_type arg_pack = boost::detail ::convert_bgl_params_to_boost_parameter<old_style_params_type >::conv(old_style_params); return ::boost::graph::breadth_first_search_with_named_params ( param0 , param1 , arg_pack); } template < typename Param0 , typename Param1 > typename boost::result_of< ::boost ::graph::detail::breadth_first_search_impl < Param0 , Param1 > ( Param0 , Param1 , const boost::parameter::aux::empty_arg_list &) >::type breadth_first_search( const Param0 & param0 , const Param1 & param1) { typedef typename boost::detail ::convert_bgl_params_to_boost_parameter<boost::no_named_parameters >::type arg_pack_type; arg_pack_type arg_pack = boost::detail ::convert_bgl_params_to_boost_parameter<boost::no_named_parameters >::conv(boost::no_named_parameters()); return ::boost::graph ::breadth_first_search_with_named_params( param0 , param1 , arg_pack ); } |
| 404 | #endif |
| 405 | |
| 406 | } // namespace boost |
| 407 | |
| 408 | #ifdef BOOST_GRAPH_USE_MPI |
| 409 | # include <boost/graph/distributed/breadth_first_search.hpp> |
| 410 | #endif |
| 411 | |
| 412 | #endif // BOOST_GRAPH_BREADTH_FIRST_SEARCH_HPP |
| 413 |
| 1 | //======================================================================= | |||
| 2 | // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. | |||
| 3 | // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek | |||
| 4 | // | |||
| 5 | // Distributed under the Boost Software License, Version 1.0. (See | |||
| 6 | // accompanying file LICENSE_1_0.txt or copy at | |||
| 7 | // http://www.boost.org/LICENSE_1_0.txt) | |||
| 8 | //======================================================================= | |||
| 9 | ||||
| 10 | #ifndef BOOST_GRAPH_NAMED_FUNCTION_PARAMS_HPP | |||
| 11 | #define BOOST_GRAPH_NAMED_FUNCTION_PARAMS_HPP | |||
| 12 | ||||
| 13 | #include <functional> | |||
| 14 | #include <vector> | |||
| 15 | #include <boost/limits.hpp> | |||
| 16 | #include <boost/ref.hpp> | |||
| 17 | #include <boost/utility/result_of.hpp> | |||
| 18 | #include <boost/preprocessor.hpp> | |||
| 19 | #include <boost/parameter/name.hpp> | |||
| 20 | #include <boost/parameter/binding.hpp> | |||
| 21 | #include <boost/type_traits.hpp> | |||
| 22 | #include <boost/mpl/not.hpp> | |||
| 23 | #include <boost/graph/properties.hpp> | |||
| 24 | #include <boost/graph/detail/d_ary_heap.hpp> | |||
| 25 | #include <boost/property_map/property_map.hpp> | |||
| 26 | #include <boost/property_map/shared_array_property_map.hpp> | |||
| 27 | ||||
| 28 | namespace boost { | |||
| 29 | ||||
| 30 | struct parity_map_t { }; | |||
| 31 | struct vertex_assignment_map_t { }; | |||
| 32 | struct distance_compare_t { }; | |||
| 33 | struct distance_combine_t { }; | |||
| 34 | struct distance_inf_t { }; | |||
| 35 | struct distance_zero_t { }; | |||
| 36 | struct buffer_param_t { }; | |||
| 37 | struct edge_copy_t { }; | |||
| 38 | struct vertex_copy_t { }; | |||
| 39 | struct vertex_isomorphism_t { }; | |||
| 40 | struct vertex_invariant_t { }; | |||
| 41 | struct vertex_invariant1_t { }; | |||
| 42 | struct vertex_invariant2_t { }; | |||
| 43 | struct edge_compare_t { }; | |||
| 44 | struct vertex_max_invariant_t { }; | |||
| 45 | struct orig_to_copy_t { }; | |||
| 46 | struct root_vertex_t { }; | |||
| 47 | struct polling_t { }; | |||
| 48 | struct lookahead_t { }; | |||
| 49 | struct in_parallel_t { }; | |||
| 50 | struct attractive_force_t { }; | |||
| 51 | struct repulsive_force_t { }; | |||
| 52 | struct force_pairs_t { }; | |||
| 53 | struct cooling_t { }; | |||
| 54 | struct vertex_displacement_t { }; | |||
| 55 | struct iterations_t { }; | |||
| 56 | struct diameter_range_t { }; | |||
| 57 | struct learning_constant_range_t { }; | |||
| 58 | struct vertices_equivalent_t { }; | |||
| 59 | struct edges_equivalent_t { }; | |||
| 60 | struct index_in_heap_map_t { }; | |||
| 61 | struct max_priority_queue_t { }; | |||
| 62 | ||||
| 63 | #define BOOST_BGL_DECLARE_NAMED_PARAMS \ | |||
| 64 | BOOST_BGL_ONE_PARAM_CREF(weight_map, edge_weight) \ | |||
| 65 | BOOST_BGL_ONE_PARAM_CREF(weight_map2, edge_weight2) \ | |||
| 66 | BOOST_BGL_ONE_PARAM_CREF(distance_map, vertex_distance) \ | |||
| 67 | BOOST_BGL_ONE_PARAM_CREF(distance_map2, vertex_distance2) \ | |||
| 68 | BOOST_BGL_ONE_PARAM_CREF(predecessor_map, vertex_predecessor) \ | |||
| 69 | BOOST_BGL_ONE_PARAM_CREF(rank_map, vertex_rank) \ | |||
| 70 | BOOST_BGL_ONE_PARAM_CREF(root_map, vertex_root) \ | |||
| 71 | BOOST_BGL_ONE_PARAM_CREF(root_vertex, root_vertex) \ | |||
| 72 | BOOST_BGL_ONE_PARAM_CREF(edge_centrality_map, edge_centrality) \ | |||
| 73 | BOOST_BGL_ONE_PARAM_CREF(centrality_map, vertex_centrality) \ | |||
| 74 | BOOST_BGL_ONE_PARAM_CREF(parity_map, parity_map) \ | |||
| 75 | BOOST_BGL_ONE_PARAM_CREF(color_map, vertex_color) \ | |||
| 76 | BOOST_BGL_ONE_PARAM_CREF(edge_color_map, edge_color) \ | |||
| 77 | BOOST_BGL_ONE_PARAM_CREF(capacity_map, edge_capacity) \ | |||
| 78 | BOOST_BGL_ONE_PARAM_CREF(residual_capacity_map, edge_residual_capacity) \ | |||
| 79 | BOOST_BGL_ONE_PARAM_CREF(reverse_edge_map, edge_reverse) \ | |||
| 80 | BOOST_BGL_ONE_PARAM_CREF(discover_time_map, vertex_discover_time) \ | |||
| 81 | BOOST_BGL_ONE_PARAM_CREF(lowpoint_map, vertex_lowpoint) \ | |||
| 82 | BOOST_BGL_ONE_PARAM_CREF(vertex_index_map, vertex_index) \ | |||
| 83 | BOOST_BGL_ONE_PARAM_CREF(vertex_index1_map, vertex_index1) \ | |||
| 84 | BOOST_BGL_ONE_PARAM_CREF(vertex_index2_map, vertex_index2) \ | |||
| 85 | BOOST_BGL_ONE_PARAM_CREF(vertex_assignment_map, vertex_assignment_map) \ | |||
| 86 | BOOST_BGL_ONE_PARAM_CREF(visitor, graph_visitor) \ | |||
| 87 | BOOST_BGL_ONE_PARAM_CREF(distance_compare, distance_compare) \ | |||
| 88 | BOOST_BGL_ONE_PARAM_CREF(distance_combine, distance_combine) \ | |||
| 89 | BOOST_BGL_ONE_PARAM_CREF(distance_inf, distance_inf) \ | |||
| 90 | BOOST_BGL_ONE_PARAM_CREF(distance_zero, distance_zero) \ | |||
| 91 | BOOST_BGL_ONE_PARAM_CREF(edge_copy, edge_copy) \ | |||
| 92 | BOOST_BGL_ONE_PARAM_CREF(vertex_copy, vertex_copy) \ | |||
| 93 | BOOST_BGL_ONE_PARAM_REF(buffer, buffer_param) \ | |||
| 94 | BOOST_BGL_ONE_PARAM_CREF(orig_to_copy, orig_to_copy) \ | |||
| 95 | BOOST_BGL_ONE_PARAM_CREF(isomorphism_map, vertex_isomorphism) \ | |||
| 96 | BOOST_BGL_ONE_PARAM_CREF(vertex_invariant, vertex_invariant) \ | |||
| 97 | BOOST_BGL_ONE_PARAM_CREF(vertex_invariant1, vertex_invariant1) \ | |||
| 98 | BOOST_BGL_ONE_PARAM_CREF(vertex_invariant2, vertex_invariant2) \ | |||
| 99 | BOOST_BGL_ONE_PARAM_CREF(vertex_max_invariant, vertex_max_invariant) \ | |||
| 100 | BOOST_BGL_ONE_PARAM_CREF(polling, polling) \ | |||
| 101 | BOOST_BGL_ONE_PARAM_CREF(lookahead, lookahead) \ | |||
| 102 | BOOST_BGL_ONE_PARAM_CREF(in_parallel, in_parallel) \ | |||
| 103 | BOOST_BGL_ONE_PARAM_CREF(displacement_map, vertex_displacement) \ | |||
| 104 | BOOST_BGL_ONE_PARAM_CREF(attractive_force, attractive_force) \ | |||
| 105 | BOOST_BGL_ONE_PARAM_CREF(repulsive_force, repulsive_force) \ | |||
| 106 | BOOST_BGL_ONE_PARAM_CREF(force_pairs, force_pairs) \ | |||
| 107 | BOOST_BGL_ONE_PARAM_CREF(cooling, cooling) \ | |||
| 108 | BOOST_BGL_ONE_PARAM_CREF(iterations, iterations) \ | |||
| 109 | BOOST_BGL_ONE_PARAM_CREF(diameter_range, diameter_range) \ | |||
| 110 | BOOST_BGL_ONE_PARAM_CREF(learning_constant_range, learning_constant_range) \ | |||
| 111 | BOOST_BGL_ONE_PARAM_CREF(vertices_equivalent, vertices_equivalent) \ | |||
| 112 | BOOST_BGL_ONE_PARAM_CREF(edges_equivalent, edges_equivalent) \ | |||
| 113 | BOOST_BGL_ONE_PARAM_CREF(index_in_heap_map, index_in_heap_map) \ | |||
| 114 | BOOST_BGL_ONE_PARAM_REF(max_priority_queue, max_priority_queue) | |||
| 115 | ||||
| 116 | template <typename T, typename Tag, typename Base = no_property> | |||
| 117 | struct bgl_named_params | |||
| 118 | { | |||
| 119 | typedef bgl_named_params self; | |||
| 120 | typedef Base next_type; | |||
| 121 | typedef Tag tag_type; | |||
| 122 | typedef T value_type; | |||
| 123 | bgl_named_params(T v = T()) : m_value(v) { } | |||
| 124 | bgl_named_params(T v, const Base& b) : m_value(v), m_base(b) { } | |||
| 125 | T m_value; | |||
| 126 | Base m_base; | |||
| 127 | ||||
| 128 | #define BOOST_BGL_ONE_PARAM_REF(name, key) \ | |||
| 129 | template <typename PType> \ | |||
| 130 | bgl_named_params<boost::reference_wrapper<PType>, BOOST_PP_CAT(key, _t)key_t, self> \ | |||
| 131 | name(PType& p) const { \ | |||
| 132 | typedef bgl_named_params<boost::reference_wrapper<PType>, BOOST_PP_CAT(key, _t)key_t, self> Params; \ | |||
| 133 | return Params(boost::ref(p), *this); \ | |||
| 134 | } \ | |||
| 135 | ||||
| 136 | #define BOOST_BGL_ONE_PARAM_CREF(name, key) \ | |||
| 137 | template <typename PType> \ | |||
| 138 | bgl_named_params<PType, BOOST_PP_CAT(key, _t)key_t, self> \ | |||
| 139 | name(const PType& p) const { \ | |||
| 140 | typedef bgl_named_params<PType, BOOST_PP_CAT(key, _t)key_t, self> Params; \ | |||
| 141 | return Params(p, *this); \ | |||
| 142 | } \ | |||
| 143 | ||||
| 144 | BOOST_BGL_DECLARE_NAMED_PARAMS | |||
| 145 | ||||
| 146 | #undef BOOST_BGL_ONE_PARAM_REF | |||
| 147 | #undef BOOST_BGL_ONE_PARAM_CREF | |||
| 148 | ||||
| 149 | // Duplicate | |||
| 150 | template <typename PType> | |||
| 151 | bgl_named_params<PType, vertex_color_t, self> | |||
| 152 | vertex_color_map(const PType& p) const {return this->color_map(p);} | |||
| 153 | }; | |||
| 154 | ||||
| 155 | #define BOOST_BGL_ONE_PARAM_REF(name, key) \ | |||
| 156 | template <typename PType> \ | |||
| 157 | bgl_named_params<boost::reference_wrapper<PType>, BOOST_PP_CAT(key, _t)key_t> \ | |||
| 158 | name(PType& p) { \ | |||
| 159 | typedef bgl_named_params<boost::reference_wrapper<PType>, BOOST_PP_CAT(key, _t)key_t> Params; \ | |||
| 160 | return Params(boost::ref(p)); \ | |||
| 161 | } \ | |||
| 162 | ||||
| 163 | #define BOOST_BGL_ONE_PARAM_CREF(name, key) \ | |||
| 164 | template <typename PType> \ | |||
| 165 | bgl_named_params<PType, BOOST_PP_CAT(key, _t)key_t> \ | |||
| 166 | name(const PType& p) { \ | |||
| 167 | typedef bgl_named_params<PType, BOOST_PP_CAT(key, _t)key_t> Params; \ | |||
| 168 | return Params(p); \ | |||
| 169 | } \ | |||
| 170 | ||||
| 171 | BOOST_BGL_DECLARE_NAMED_PARAMS | |||
| 172 | ||||
| 173 | #undef BOOST_BGL_ONE_PARAM_REF | |||
| 174 | #undef BOOST_BGL_ONE_PARAM_CREF | |||
| 175 | ||||
| 176 | // Duplicate | |||
| 177 | template <typename PType> | |||
| 178 | bgl_named_params<PType, vertex_color_t> | |||
| 179 | vertex_color_map(const PType& p) {return color_map(p);} | |||
| 180 | ||||
| 181 | namespace detail { | |||
| 182 | struct unused_tag_type {}; | |||
| 183 | } | |||
| 184 | typedef bgl_named_params<char, detail::unused_tag_type> no_named_parameters; | |||
| 185 | ||||
| 186 | //=========================================================================== | |||
| 187 | // Functions for extracting parameters from bgl_named_params | |||
| 188 | ||||
| 189 | template <typename Tag, typename Args> | |||
| 190 | struct lookup_named_param {}; | |||
| 191 | ||||
| 192 | template <typename T, typename Tag, typename Base> | |||
| 193 | struct lookup_named_param<Tag, bgl_named_params<T, Tag, Base> > { | |||
| 194 | typedef T type; | |||
| 195 | static const T& get(const bgl_named_params<T, Tag, Base>& p) { | |||
| 196 | return p.m_value; | |||
| 197 | } | |||
| 198 | }; | |||
| 199 | ||||
| 200 | template <typename Tag1, typename T, typename Tag, typename Base> | |||
| 201 | struct lookup_named_param<Tag1, bgl_named_params<T, Tag, Base> > { | |||
| 202 | typedef typename lookup_named_param<Tag1, Base>::type type; | |||
| 203 | static const type& get(const bgl_named_params<T, Tag, Base>& p) { | |||
| 204 | return lookup_named_param<Tag1, Base>::get(p.m_base); | |||
| 205 | } | |||
| 206 | }; | |||
| 207 | ||||
| 208 | template <typename Tag, typename Args, typename Def> | |||
| 209 | struct lookup_named_param_def { | |||
| 210 | typedef Def type; | |||
| 211 | static const Def& get(const Args&, const Def& def) {return def;} | |||
| 212 | }; | |||
| 213 | ||||
| 214 | template <typename T, typename Tag, typename Base, typename Def> | |||
| 215 | struct lookup_named_param_def<Tag, bgl_named_params<T, Tag, Base>, Def> { | |||
| 216 | typedef T type; | |||
| 217 | static const type& get(const bgl_named_params<T, Tag, Base>& p, const Def&) { | |||
| 218 | return p.m_value; | |||
| 219 | } | |||
| 220 | }; | |||
| 221 | ||||
| 222 | template <typename Tag1, typename T, typename Tag, typename Base, typename Def> | |||
| 223 | struct lookup_named_param_def<Tag1, bgl_named_params<T, Tag, Base>, Def> { | |||
| 224 | typedef typename lookup_named_param_def<Tag1, Base, Def>::type type; | |||
| 225 | static const type& get(const bgl_named_params<T, Tag, Base>& p, const Def& def) { | |||
| 226 | return lookup_named_param_def<Tag1, Base, Def>::get(p.m_base, def); | |||
| 227 | } | |||
| 228 | }; | |||
| 229 | ||||
| 230 | struct param_not_found {}; | |||
| 231 | ||||
| 232 | template <typename Tag, typename Args> | |||
| 233 | struct get_param_type: | |||
| 234 | lookup_named_param_def<Tag, Args, param_not_found> {}; | |||
| 235 | ||||
| 236 | template <class Tag, typename Args> | |||
| 237 | inline | |||
| 238 | const typename lookup_named_param_def<Tag, Args, param_not_found>::type& | |||
| 239 | get_param(const Args& p, Tag) { | |||
| 240 | return lookup_named_param_def<Tag, Args, param_not_found>::get(p, param_not_found()); | |||
| ||||
| 241 | } | |||
| 242 | ||||
| 243 | template <class P, class Default> | |||
| 244 | const P& choose_param(const P& param, const Default&) { | |||
| 245 | return param; | |||
| 246 | } | |||
| 247 | ||||
| 248 | template <class Default> | |||
| 249 | Default choose_param(const param_not_found&, const Default& d) { | |||
| 250 | return d; | |||
| 251 | } | |||
| 252 | ||||
| 253 | template <typename T> | |||
| 254 | inline bool is_default_param(const T&) { return false; } | |||
| 255 | ||||
| 256 | inline bool is_default_param(const param_not_found&) | |||
| 257 | { return true; } | |||
| 258 | ||||
| 259 | namespace detail { | |||
| 260 | template <typename T> | |||
| 261 | struct const_type_as_type {typedef typename T::const_type type;}; | |||
| 262 | } // namespace detail | |||
| 263 | ||||
| 264 | ||||
| 265 | // Use this function instead of choose_param() when you want | |||
| 266 | // to avoid requiring get(tag, g) when it is not used. | |||
| 267 | namespace detail { | |||
| 268 | template <typename GraphIsConst, typename Graph, typename Param, typename Tag> | |||
| 269 | struct choose_impl_result: | |||
| 270 | boost::mpl::eval_if< | |||
| 271 | boost::is_same<Param, param_not_found>, | |||
| 272 | boost::mpl::eval_if< | |||
| 273 | GraphIsConst, | |||
| 274 | detail::const_type_as_type<property_map<Graph, Tag> >, | |||
| 275 | property_map<Graph, Tag> >, | |||
| 276 | boost::mpl::identity<Param> > {}; | |||
| 277 | ||||
| 278 | // Parameters of f are (GraphIsConst, Graph, Param, Tag) | |||
| 279 | template <bool Found> struct choose_impl_helper; | |||
| 280 | ||||
| 281 | template <> struct choose_impl_helper<false> { | |||
| 282 | template <typename Param, typename Graph, typename PropertyTag> | |||
| 283 | static typename property_map<typename boost::remove_const<Graph>::type, PropertyTag>::const_type | |||
| 284 | f(boost::mpl::true_, const Graph& g, const Param&, PropertyTag tag) { | |||
| 285 | return get(tag, g); | |||
| 286 | } | |||
| 287 | ||||
| 288 | template <typename Param, typename Graph, typename PropertyTag> | |||
| 289 | static typename property_map<typename boost::remove_const<Graph>::type, PropertyTag>::type | |||
| 290 | f(boost::mpl::false_, Graph& g, const Param&, PropertyTag tag) { | |||
| 291 | return get(tag, g); | |||
| 292 | } | |||
| 293 | }; | |||
| 294 | ||||
| 295 | template <> struct choose_impl_helper<true> { | |||
| 296 | template <typename GraphIsConst, typename Param, typename Graph, typename PropertyTag> | |||
| 297 | static Param f(GraphIsConst, const Graph&, const Param& p, PropertyTag) { | |||
| 298 | return p; | |||
| 299 | } | |||
| 300 | }; | |||
| 301 | } | |||
| 302 | ||||
| 303 | template <typename Param, typename Graph, typename PropertyTag> | |||
| 304 | typename detail::choose_impl_result<boost::mpl::true_, Graph, Param, PropertyTag>::type | |||
| 305 | choose_const_pmap(const Param& p, const Graph& g, PropertyTag tag) | |||
| 306 | { | |||
| 307 | return detail::choose_impl_helper<!boost::is_same<Param, param_not_found>::value> | |||
| 308 | ::f(boost::mpl::true_(), g, p, tag); | |||
| 309 | } | |||
| 310 | ||||
| 311 | template <typename Param, typename Graph, typename PropertyTag> | |||
| 312 | typename detail::choose_impl_result<boost::mpl::false_, Graph, Param, PropertyTag>::type | |||
| 313 | choose_pmap(const Param& p, Graph& g, PropertyTag tag) | |||
| 314 | { | |||
| 315 | return detail::choose_impl_helper<!boost::is_same<Param, param_not_found>::value> | |||
| 316 | ::f(boost::mpl::false_(), g, p, tag); | |||
| 317 | } | |||
| 318 | ||||
| 319 | namespace detail { | |||
| 320 | ||||
| 321 | // used in the max-flow algorithms | |||
| 322 | template <class Graph, class P, class T, class R> | |||
| 323 | struct edge_capacity_value | |||
| 324 | { | |||
| 325 | typedef bgl_named_params<P, T, R> Params; | |||
| 326 | typedef typename detail::choose_impl_result<boost::mpl::true_, Graph, typename get_param_type<edge_capacity_t, Params>::type, edge_capacity_t>::type CapacityEdgeMap; | |||
| 327 | typedef typename property_traits<CapacityEdgeMap>::value_type type; | |||
| 328 | }; | |||
| 329 | // used in the max-flow algorithms | |||
| 330 | template <class Graph, class P, class T, class R> | |||
| 331 | struct edge_weight_value | |||
| 332 | { | |||
| 333 | typedef bgl_named_params<P, T, R> Params; | |||
| 334 | typedef typename detail::choose_impl_result<boost::mpl::true_, Graph, typename get_param_type<edge_weight_t, Params>::type, edge_weight_t>::type WeightMap; | |||
| 335 | typedef typename property_traits<WeightMap>::value_type type; | |||
| 336 | }; | |||
| 337 | ||||
| 338 | } | |||
| 339 | ||||
| 340 | // Declare all new tags | |||
| 341 | namespace graph { | |||
| 342 | namespace keywords { | |||
| 343 | #define BOOST_BGL_ONE_PARAM_REF(name, key) BOOST_PARAMETER_NAME(name)namespace tag { struct name { static char const* keyword_name () { return "name"; } typedef boost::parameter::value_type< boost::mpl::_2, name, boost::parameter::void_ > _; typedef boost::parameter::value_type< boost::mpl::_2, name, boost ::parameter::void_ > _1; }; } namespace { ::boost::parameter ::keyword<tag::name> const& _name = ::boost::parameter ::keyword<tag::name>::instance; } | |||
| 344 | #define BOOST_BGL_ONE_PARAM_CREF(name, key) BOOST_PARAMETER_NAME(name)namespace tag { struct name { static char const* keyword_name () { return "name"; } typedef boost::parameter::value_type< boost::mpl::_2, name, boost::parameter::void_ > _; typedef boost::parameter::value_type< boost::mpl::_2, name, boost ::parameter::void_ > _1; }; } namespace { ::boost::parameter ::keyword<tag::name> const& _name = ::boost::parameter ::keyword<tag::name>::instance; } | |||
| 345 | BOOST_BGL_DECLARE_NAMED_PARAMS | |||
| 346 | #undef BOOST_BGL_ONE_PARAM_REF | |||
| 347 | #undef BOOST_BGL_ONE_PARAM_CREF | |||
| 348 | } | |||
| 349 | } | |||
| 350 | ||||
| 351 | namespace detail { | |||
| 352 | template <typename Tag> struct convert_one_keyword {}; | |||
| 353 | #define BOOST_BGL_ONE_PARAM_REF(name, key) \ | |||
| 354 | template <> \ | |||
| 355 | struct convert_one_keyword<BOOST_PP_CAT(key, _t)key_t> { \ | |||
| 356 | typedef boost::graph::keywords::tag::name type; \ | |||
| 357 | }; | |||
| 358 | #define BOOST_BGL_ONE_PARAM_CREF(name, key) BOOST_BGL_ONE_PARAM_REF(name, key) | |||
| 359 | BOOST_BGL_DECLARE_NAMED_PARAMS | |||
| 360 | #undef BOOST_BGL_ONE_PARAM_REF | |||
| 361 | #undef BOOST_BGL_ONE_PARAM_CREF | |||
| 362 | ||||
| 363 | template <typename T> | |||
| 364 | struct convert_bgl_params_to_boost_parameter { | |||
| 365 | typedef typename convert_one_keyword<typename T::tag_type>::type new_kw; | |||
| 366 | typedef boost::parameter::aux::tagged_argument<new_kw, const typename T::value_type> tagged_arg_type; | |||
| 367 | typedef convert_bgl_params_to_boost_parameter<typename T::next_type> rest_conv; | |||
| 368 | typedef boost::parameter::aux::arg_list<tagged_arg_type, typename rest_conv::type> type; | |||
| 369 | static type conv(const T& x) { | |||
| 370 | return type(tagged_arg_type(x.m_value), rest_conv::conv(x.m_base)); | |||
| 371 | } | |||
| 372 | }; | |||
| 373 | ||||
| 374 | template <typename P, typename R> | |||
| 375 | struct convert_bgl_params_to_boost_parameter<bgl_named_params<P, int, R> > { | |||
| 376 | typedef convert_bgl_params_to_boost_parameter<R> rest_conv; | |||
| 377 | typedef typename rest_conv::type type; | |||
| 378 | static type conv(const bgl_named_params<P, int, R>& x) { | |||
| 379 | return rest_conv::conv(x.m_base); | |||
| 380 | } | |||
| 381 | }; | |||
| 382 | ||||
| 383 | template <> | |||
| 384 | struct convert_bgl_params_to_boost_parameter<boost::no_property> { | |||
| 385 | typedef boost::parameter::aux::empty_arg_list type; | |||
| 386 | static type conv(const boost::no_property&) {return type();} | |||
| 387 | }; | |||
| 388 | ||||
| 389 | template <> | |||
| 390 | struct convert_bgl_params_to_boost_parameter<boost::no_named_parameters> { | |||
| 391 | typedef boost::parameter::aux::empty_arg_list type; | |||
| 392 | static type conv(const boost::no_named_parameters&) {return type();} | |||
| 393 | }; | |||
| 394 | ||||
| 395 | struct bgl_parameter_not_found_type {}; | |||
| 396 | ||||
| 397 | template <typename ArgPack, typename KeywordType> | |||
| 398 | struct parameter_exists : boost::mpl::not_<boost::is_same<typename boost::parameter::binding<ArgPack, KeywordType, bgl_parameter_not_found_type>::type, bgl_parameter_not_found_type> > {}; | |||
| 399 | } | |||
| 400 | ||||
| 401 | #define BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(old_type, old_var)typedef typename boost::detail::convert_bgl_params_to_boost_parameter <old_type>::type arg_pack_type; arg_pack_type arg_pack = boost::detail::convert_bgl_params_to_boost_parameter<old_type >::conv(old_var); \ | |||
| 402 | typedef typename boost::detail::convert_bgl_params_to_boost_parameter<old_type>::type arg_pack_type; \ | |||
| 403 | arg_pack_type arg_pack = boost::detail::convert_bgl_params_to_boost_parameter<old_type>::conv(old_var); | |||
| 404 | ||||
| 405 | namespace detail { | |||
| 406 | ||||
| 407 | template <typename ArgType, typename Prop, typename Graph, bool Exists> | |||
| 408 | struct override_const_property_t { | |||
| 409 | typedef typename boost::remove_const<ArgType>::type result_type; | |||
| 410 | result_type operator()(const Graph&, const ArgType& a) const {return a;} | |||
| 411 | }; | |||
| 412 | ||||
| 413 | template <typename ArgType, typename Prop, typename Graph> | |||
| 414 | struct override_const_property_t<ArgType, Prop, Graph, false> { | |||
| 415 | typedef typename boost::property_map<Graph, Prop>::const_type result_type; | |||
| 416 | result_type operator()(const Graph& g, const ArgType&) const {return get(Prop(), g);} | |||
| 417 | }; | |||
| 418 | ||||
| 419 | template <typename ArgPack, typename Tag, typename Prop, typename Graph> | |||
| 420 | struct override_const_property_result { | |||
| 421 | typedef | |||
| 422 | typename override_const_property_t< | |||
| 423 | typename boost::parameter::value_type<ArgPack, Tag, int>::type, | |||
| 424 | Prop, | |||
| 425 | Graph, | |||
| 426 | boost::detail::parameter_exists<ArgPack, Tag>::value | |||
| 427 | >::result_type | |||
| 428 | type; | |||
| 429 | }; | |||
| 430 | ||||
| 431 | template <typename ArgPack, typename Tag, typename Prop, typename Graph> | |||
| 432 | typename override_const_property_result<ArgPack, Tag, Prop, Graph>::type | |||
| 433 | override_const_property(const ArgPack& ap, const boost::parameter::keyword<Tag>& t, const Graph& g, Prop) { | |||
| 434 | return override_const_property_t< | |||
| 435 | typename boost::parameter::value_type<ArgPack, Tag, int>::type, | |||
| 436 | Prop, | |||
| 437 | Graph, | |||
| 438 | boost::detail::parameter_exists<ArgPack, Tag>::value | |||
| 439 | >()(g, ap[t | 0]); | |||
| 440 | } | |||
| 441 | ||||
| 442 | template <typename ArgType, typename Prop, typename Graph, bool Exists> | |||
| 443 | struct override_property_t { | |||
| 444 | typedef ArgType result_type; | |||
| 445 | result_type operator()(const Graph&, const typename boost::add_reference<ArgType>::type a) const {return a;} | |||
| 446 | }; | |||
| 447 | ||||
| 448 | template <typename ArgType, typename Prop, typename Graph> | |||
| 449 | struct override_property_t<ArgType, Prop, Graph, false> { | |||
| 450 | typedef typename boost::property_map<Graph, Prop>::type result_type; | |||
| 451 | result_type operator()(const Graph& g, const ArgType&) const {return get(Prop(), g);} | |||
| 452 | }; | |||
| 453 | ||||
| 454 | template <typename ArgPack, typename Tag, typename Prop, typename Graph> | |||
| 455 | struct override_property_result { | |||
| 456 | typedef | |||
| 457 | typename override_property_t< | |||
| 458 | typename boost::parameter::value_type<ArgPack, Tag, int>::type, | |||
| 459 | Prop, | |||
| 460 | Graph, | |||
| 461 | boost::detail::parameter_exists<ArgPack, Tag>::value | |||
| 462 | >::result_type | |||
| 463 | type; | |||
| 464 | }; | |||
| 465 | ||||
| 466 | template <typename ArgPack, typename Tag, typename Prop, typename Graph> | |||
| 467 | typename override_property_result<ArgPack, Tag, Prop, Graph>::type | |||
| 468 | override_property(const ArgPack& ap, const boost::parameter::keyword<Tag>& t, const Graph& g, Prop) { | |||
| 469 | return override_property_t< | |||
| 470 | typename boost::parameter::value_type<ArgPack, Tag, int>::type, | |||
| 471 | Prop, | |||
| 472 | Graph, | |||
| 473 | boost::detail::parameter_exists<ArgPack, Tag>::value | |||
| 474 | >()(g, ap[t | 0]); | |||
| 475 | } | |||
| 476 | ||||
| 477 | template <typename F> struct make_arg_pack_type; | |||
| 478 | template <> struct make_arg_pack_type<void()> {typedef boost::parameter::aux::empty_arg_list type;}; | |||
| 479 | template <typename K, typename A> | |||
| 480 | struct make_arg_pack_type<void(K, A)> { | |||
| 481 | typedef boost::parameter::aux::tagged_argument<K, A> type; | |||
| 482 | }; | |||
| 483 | ||||
| 484 | #define BOOST_GRAPH_OPENING_PART_OF_PAIR(z, i, n)boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument <KeywordBOOST_PP_REM BOOST_PP_IIF_BOOST_PP_BOOL_i(BOOST_PP_WHILE_2 , (n, i) BOOST_PP_TUPLE_EAT_3)(BOOST_PP_SUB_P, BOOST_PP_SUB_O , BOOST_PP_IIF_BOOST_PP_BOOL_i(BOOST_PP_SUB_O, BOOST_PP_NIL BOOST_PP_TUPLE_EAT_2 )(2, (n, i))), ArgBOOST_PP_REM BOOST_PP_IIF_BOOST_PP_BOOL_i(BOOST_PP_WHILE_2 , (n, i) BOOST_PP_TUPLE_EAT_3)(BOOST_PP_SUB_P, BOOST_PP_SUB_O , BOOST_PP_IIF_BOOST_PP_BOOL_i(BOOST_PP_SUB_O, BOOST_PP_NIL BOOST_PP_TUPLE_EAT_2 )(2, (n, i)))>, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<BOOST_PP_CAT(Keyword, BOOST_PP_SUB(n, i))KeywordBOOST_PP_REM BOOST_PP_IIF_BOOST_PP_BOOL_i(BOOST_PP_WHILE_2 , (n, i) BOOST_PP_TUPLE_EAT_3)(BOOST_PP_SUB_P, BOOST_PP_SUB_O , BOOST_PP_IIF_BOOST_PP_BOOL_i(BOOST_PP_SUB_O, BOOST_PP_NIL BOOST_PP_TUPLE_EAT_2 )(2, (n, i))), BOOST_PP_CAT(Arg, BOOST_PP_SUB(n, i))ArgBOOST_PP_REM BOOST_PP_IIF_BOOST_PP_BOOL_i(BOOST_PP_WHILE_2 , (n, i) BOOST_PP_TUPLE_EAT_3)(BOOST_PP_SUB_P, BOOST_PP_SUB_O , BOOST_PP_IIF_BOOST_PP_BOOL_i(BOOST_PP_SUB_O, BOOST_PP_NIL BOOST_PP_TUPLE_EAT_2 )(2, (n, i)))>, | |||
| 485 | #define BOOST_GRAPH_MAKE_PAIR_PARAM(z, i, _)const boost::parameter::aux::tagged_argument<Keywordi, Argi >& kwi const boost::parameter::aux::tagged_argument<BOOST_PP_CAT(Keyword, i)Keywordi, BOOST_PP_CAT(Arg, i)Argi>& BOOST_PP_CAT(kw, i)kwi | |||
| 486 | ||||
| 487 | #define BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION(z, i, _) \ | |||
| 488 | template <BOOST_PP_ENUM_PARAMS(i, typename Keyword)BOOST_PP_REPEAT_1_i(BOOST_PP_ENUM_PARAMS_M, typename Keyword), BOOST_PP_ENUM_PARAMS(i, typename Arg)BOOST_PP_REPEAT_1_i(BOOST_PP_ENUM_PARAMS_M, typename Arg)> \ | |||
| 489 | struct make_arg_pack_type<void(BOOST_PP_ENUM_PARAMS(i, Keyword)BOOST_PP_REPEAT_1_i(BOOST_PP_ENUM_PARAMS_M, Keyword), BOOST_PP_ENUM_PARAMS(i, Arg)BOOST_PP_REPEAT_1_i(BOOST_PP_ENUM_PARAMS_M, Arg))> { \ | |||
| 490 | typedef \ | |||
| 491 | BOOST_PP_REPEAT(i, BOOST_GRAPH_OPENING_PART_OF_PAIR, BOOST_PP_DEC(i))BOOST_PP_REPEAT_1_i(BOOST_GRAPH_OPENING_PART_OF_PAIR, BOOST_PP_DEC_i ) boost::parameter::aux::empty_arg_list BOOST_PP_REPEAT(i, > BOOST_PP_TUPLE_EAT(3), ~)BOOST_PP_REPEAT_1_i(> BOOST_PP_EAT, ~) \ | |||
| 492 | type; \ | |||
| 493 | }; | |||
| 494 | BOOST_PP_REPEAT_FROM_TO(2, 11, BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION, ~)BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION(2, 2, ~) BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION (2, 3, ~) BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION(2, 4, ~) BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION (2, 5, ~) BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION(2, 6, ~) BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION (2, 7, ~) BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION(2, 8, ~) BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION (2, 9, ~) BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION(2, 10, ~) | |||
| 495 | #undef BOOST_GRAPH_MAKE_AP_TYPE_SPECIALIZATION | |||
| 496 | ||||
| 497 | #define BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(name, nfixed, nnamed_max)template <BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, typename Param) BOOST_PP_IIF_BOOST_PP_BOOL_nfixed(BOOST_PP_COMMA , BOOST_PP_EMPTY)() typename ArgPack> typename boost::result_of < detail::name_impl<BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M , Param)>(BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, Param) BOOST_PP_IIF_BOOST_PP_BOOL_nfixed(BOOST_PP_COMMA, BOOST_PP_EMPTY )() const ArgPack&) >::type name_with_named_params(BOOST_PP_REPEAT_1_nfixed (BOOST_PP_ENUM_BINARY_PARAMS_M, (const Param, & param)) BOOST_PP_IIF_BOOST_PP_BOOL_nfixed (BOOST_PP_COMMA, BOOST_PP_EMPTY)() const ArgPack& arg_pack ) { return detail::name_impl<BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M , Param)>()(BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M , param) BOOST_PP_IIF_BOOST_PP_BOOL_nfixed(BOOST_PP_COMMA, BOOST_PP_EMPTY )() arg_pack); } BOOST_PP_REPEAT_1_BOOST_PP_INC_nnamed_max(BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONE , (name)(nfixed)) \ | |||
| 498 | /* Entry point for conversion from BGL-style named parameters */ \ | |||
| 499 | template <BOOST_PP_ENUM_PARAMS(nfixed, typename Param)BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, typename Param ) BOOST_PP_COMMA_IF(nfixed)BOOST_PP_IIF_BOOST_PP_BOOL_nfixed(BOOST_PP_COMMA, BOOST_PP_EMPTY )() typename ArgPack> \ | |||
| 500 | typename boost::result_of< \ | |||
| 501 | detail::BOOST_PP_CAT(name, _impl)name_impl<BOOST_PP_ENUM_PARAMS(nfixed, Param)BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, Param)>(BOOST_PP_ENUM_PARAMS(nfixed, Param)BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, Param) BOOST_PP_COMMA_IF(nfixed)BOOST_PP_IIF_BOOST_PP_BOOL_nfixed(BOOST_PP_COMMA, BOOST_PP_EMPTY )() const ArgPack&) \ | |||
| 502 | >::type \ | |||
| 503 | BOOST_PP_CAT(name, _with_named_params)name_with_named_params(BOOST_PP_ENUM_BINARY_PARAMS(nfixed, const Param, & param)BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_BINARY_PARAMS_M, (const Param, & param)) BOOST_PP_COMMA_IF(nfixed)BOOST_PP_IIF_BOOST_PP_BOOL_nfixed(BOOST_PP_COMMA, BOOST_PP_EMPTY )() const ArgPack& arg_pack) { \ | |||
| 504 | return detail::BOOST_PP_CAT(name, _impl)name_impl<BOOST_PP_ENUM_PARAMS(nfixed, Param)BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, Param)>()(BOOST_PP_ENUM_PARAMS(nfixed, param)BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, param) BOOST_PP_COMMA_IF(nfixed)BOOST_PP_IIF_BOOST_PP_BOOL_nfixed(BOOST_PP_COMMA, BOOST_PP_EMPTY )() arg_pack); \ | |||
| 505 | } \ | |||
| 506 | /* Individual functions taking Boost.Parameter-style keyword arguments */ \ | |||
| 507 | BOOST_PP_REPEAT(BOOST_PP_INC(nnamed_max), BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONE, (name)(nfixed))BOOST_PP_REPEAT_1_BOOST_PP_INC_nnamed_max(BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONE , (name)(nfixed)) | |||
| 508 | ||||
| 509 | #define BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONE(z, nnamed, seq)template <BOOST_PP_REPEAT_1_BOOST_PP_SEQ_ELEM_III(BOOST_PP_ENUM_PARAMS_M , typename Param) BOOST_PP_REPEAT_1_nnamed(BOOST_PP_ENUM_TRAILING_PARAMS_M , typename Keyword) BOOST_PP_REPEAT_1_nnamed(BOOST_PP_ENUM_TRAILING_PARAMS_M , typename Arg)> typename boost::result_of< detail::BOOST_PP_SEQ_ELEM_III_impl <BOOST_PP_REPEAT_1_BOOST_PP_SEQ_ELEM_III(BOOST_PP_ENUM_PARAMS_M , Param)> (BOOST_PP_REPEAT_1_BOOST_PP_SEQ_ELEM_III(BOOST_PP_ENUM_PARAMS_M , Param) BOOST_PP_IIF_BOOST_PP_BOOL_BOOST_PP_SEQ_ELEM_III(BOOST_PP_COMMA , BOOST_PP_EMPTY)() const typename boost::detail::make_arg_pack_type <void(BOOST_PP_REPEAT_1_nnamed(BOOST_PP_ENUM_PARAMS_M, Keyword ) BOOST_PP_IIF_BOOST_PP_BOOL_nnamed(BOOST_PP_COMMA, BOOST_PP_EMPTY )() BOOST_PP_REPEAT_1_nnamed(BOOST_PP_ENUM_PARAMS_M, Arg))> ::type&) >::type BOOST_PP_SEQ_ELEM_III { return detail ::BOOST_PP_SEQ_ELEM_III_impl<BOOST_PP_REPEAT_1_BOOST_PP_SEQ_ELEM_III (BOOST_PP_ENUM_PARAMS_M, Param)>() (BOOST_PP_REPEAT_1_BOOST_PP_SEQ_ELEM_III (BOOST_PP_ENUM_PARAMS_M, param), (boost::parameter::aux::empty_arg_list () BOOST_PP_REPEAT_1_nnamed(BOOST_PP_ENUM_TRAILING_PARAMS_M, kw ))); } \ | |||
| 510 | BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONEX(z, nnamed, BOOST_PP_SEQ_ELEM(0, seq), BOOST_PP_SEQ_ELEM(1, seq))template <BOOST_PP_REPEAT_1_BOOST_PP_SEQ_ELEM_III(BOOST_PP_ENUM_PARAMS_M , typename Param) BOOST_PP_REPEAT_1_nnamed(BOOST_PP_ENUM_TRAILING_PARAMS_M , typename Keyword) BOOST_PP_REPEAT_1_nnamed(BOOST_PP_ENUM_TRAILING_PARAMS_M , typename Arg)> typename boost::result_of< detail::BOOST_PP_SEQ_ELEM_III_impl <BOOST_PP_REPEAT_1_BOOST_PP_SEQ_ELEM_III(BOOST_PP_ENUM_PARAMS_M , Param)> (BOOST_PP_REPEAT_1_BOOST_PP_SEQ_ELEM_III(BOOST_PP_ENUM_PARAMS_M , Param) BOOST_PP_IIF_BOOST_PP_BOOL_BOOST_PP_SEQ_ELEM_III(BOOST_PP_COMMA , BOOST_PP_EMPTY)() const typename boost::detail::make_arg_pack_type <void(BOOST_PP_REPEAT_1_nnamed(BOOST_PP_ENUM_PARAMS_M, Keyword ) BOOST_PP_IIF_BOOST_PP_BOOL_nnamed(BOOST_PP_COMMA, BOOST_PP_EMPTY )() BOOST_PP_REPEAT_1_nnamed(BOOST_PP_ENUM_PARAMS_M, Arg))> ::type&) >::type BOOST_PP_SEQ_ELEM_III { return detail ::BOOST_PP_SEQ_ELEM_III_impl<BOOST_PP_REPEAT_1_BOOST_PP_SEQ_ELEM_III (BOOST_PP_ENUM_PARAMS_M, Param)>() (BOOST_PP_REPEAT_1_BOOST_PP_SEQ_ELEM_III (BOOST_PP_ENUM_PARAMS_M, param), (boost::parameter::aux::empty_arg_list () BOOST_PP_REPEAT_1_nnamed(BOOST_PP_ENUM_TRAILING_PARAMS_M, kw ))); } | |||
| 511 | ||||
| 512 | #define BOOST_GRAPH_MAKE_FORWARDING_FUNCTION_ONEX(z, nnamed, name, nfixed)template <BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, typename Param) BOOST_PP_REPEAT_1_nnamed(BOOST_PP_ENUM_TRAILING_PARAMS_M , typename Keyword) BOOST_PP_REPEAT_1_nnamed(BOOST_PP_ENUM_TRAILING_PARAMS_M , typename Arg)> typename boost::result_of< detail::name_impl <BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, Param)> (BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, Param) BOOST_PP_IIF_BOOST_PP_BOOL_nfixed (BOOST_PP_COMMA, BOOST_PP_EMPTY)() const typename boost::detail ::make_arg_pack_type<void(BOOST_PP_REPEAT_1_nnamed(BOOST_PP_ENUM_PARAMS_M , Keyword) BOOST_PP_IIF_BOOST_PP_BOOL_nnamed(BOOST_PP_COMMA, BOOST_PP_EMPTY )() BOOST_PP_REPEAT_1_nnamed(BOOST_PP_ENUM_PARAMS_M, Arg))> ::type&) >::type name(BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_BINARY_PARAMS_M , (const Param, & param)) BOOST_PP_REPEAT_1_nnamed(BOOST_PP_ENUM_TRAILING_M_1 , (BOOST_GRAPH_MAKE_PAIR_PARAM, ~))) { return detail::name_impl <BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, Param)> () (BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, param), ( boost::parameter::aux::empty_arg_list() BOOST_PP_REPEAT_1_nnamed (BOOST_PP_ENUM_TRAILING_PARAMS_M, kw))); } \ | |||
| 513 | template <BOOST_PP_ENUM_PARAMS(nfixed, typename Param)BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, typename Param ) BOOST_PP_ENUM_TRAILING_PARAMS(nnamed, typename Keyword)BOOST_PP_REPEAT_1_nnamed(BOOST_PP_ENUM_TRAILING_PARAMS_M, typename Keyword) BOOST_PP_ENUM_TRAILING_PARAMS(nnamed, typename Arg)BOOST_PP_REPEAT_1_nnamed(BOOST_PP_ENUM_TRAILING_PARAMS_M, typename Arg)> \ | |||
| 514 | typename boost::result_of< \ | |||
| 515 | detail::BOOST_PP_CAT(name, _impl)name_impl<BOOST_PP_ENUM_PARAMS(nfixed, Param)BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, Param)> \ | |||
| 516 | (BOOST_PP_ENUM_PARAMS(nfixed, Param)BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, Param) BOOST_PP_COMMA_IF(nfixed)BOOST_PP_IIF_BOOST_PP_BOOL_nfixed(BOOST_PP_COMMA, BOOST_PP_EMPTY )() \ | |||
| 517 | const typename boost::detail::make_arg_pack_type<void(BOOST_PP_ENUM_PARAMS(nnamed, Keyword)BOOST_PP_REPEAT_1_nnamed(BOOST_PP_ENUM_PARAMS_M, Keyword) BOOST_PP_COMMA_IF(nnamed)BOOST_PP_IIF_BOOST_PP_BOOL_nnamed(BOOST_PP_COMMA, BOOST_PP_EMPTY )() BOOST_PP_ENUM_PARAMS(nnamed, Arg)BOOST_PP_REPEAT_1_nnamed(BOOST_PP_ENUM_PARAMS_M, Arg))>::type&) \ | |||
| 518 | >::type \ | |||
| 519 | name(BOOST_PP_ENUM_BINARY_PARAMS(nfixed, const Param, & param)BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_BINARY_PARAMS_M, (const Param, & param)) \ | |||
| 520 | BOOST_PP_ENUM_TRAILING(nnamed, BOOST_GRAPH_MAKE_PAIR_PARAM, ~)BOOST_PP_REPEAT_1_nnamed(BOOST_PP_ENUM_TRAILING_M_1, (BOOST_GRAPH_MAKE_PAIR_PARAM , ~))) { \ | |||
| 521 | return detail::BOOST_PP_CAT(name, _impl)name_impl<BOOST_PP_ENUM_PARAMS(nfixed, Param)BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, Param)>() \ | |||
| 522 | (BOOST_PP_ENUM_PARAMS(nfixed, param)BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, param), \ | |||
| 523 | (boost::parameter::aux::empty_arg_list() BOOST_PP_ENUM_TRAILING_PARAMS(nnamed, kw)BOOST_PP_REPEAT_1_nnamed(BOOST_PP_ENUM_TRAILING_PARAMS_M, kw))); \ | |||
| 524 | } | |||
| 525 | ||||
| 526 | #define BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(name, nfixed)template <BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, typename Param) BOOST_PP_IIF_BOOST_PP_BOOL_nfixed(BOOST_PP_COMMA , BOOST_PP_EMPTY)() class P, class T, class R> typename boost ::result_of< ::boost::graph::detail::name_impl BOOST_PP_EXPR_IIF_BOOST_PP_BOOL_nfixed (<) BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, Param ) BOOST_PP_EXPR_IIF_BOOST_PP_BOOL_nfixed(>) (BOOST_PP_REPEAT_1_nfixed (BOOST_PP_ENUM_PARAMS_M, Param) BOOST_PP_IIF_BOOST_PP_BOOL_nfixed (BOOST_PP_COMMA, BOOST_PP_EMPTY)() const typename boost::detail ::convert_bgl_params_to_boost_parameter<boost::bgl_named_params <P, T, R> >::type &) >::type name(BOOST_PP_REPEAT_1_nfixed (BOOST_PP_ENUM_BINARY_PARAMS_M, (const Param, & param)) BOOST_PP_IIF_BOOST_PP_BOOL_nfixed (BOOST_PP_COMMA, BOOST_PP_EMPTY)() const boost::bgl_named_params <P, T, R>& old_style_params) { typedef boost::bgl_named_params <P, T, R> old_style_params_type; typedef typename boost ::detail::convert_bgl_params_to_boost_parameter<old_style_params_type >::type arg_pack_type; arg_pack_type arg_pack = boost::detail ::convert_bgl_params_to_boost_parameter<old_style_params_type >::conv(old_style_params); return ::boost::graph::name_with_named_params (BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, param) BOOST_PP_IIF_BOOST_PP_BOOL_nfixed (BOOST_PP_COMMA, BOOST_PP_EMPTY)() arg_pack); } BOOST_PP_EXPR_IIF_BOOST_PP_BOOL_nfixed (template <) BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M , typename Param) BOOST_PP_EXPR_IIF_BOOST_PP_BOOL_nfixed(> ) BOOST_PP_EXPR_IIF_BOOST_PP_BOOL_nfixed(typename) boost::result_of < ::boost::graph::detail::name_impl BOOST_PP_EXPR_IIF_BOOST_PP_BOOL_nfixed (<) BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, Param ) BOOST_PP_EXPR_IIF_BOOST_PP_BOOL_nfixed(>) (BOOST_PP_REPEAT_1_nfixed (BOOST_PP_ENUM_PARAMS_M, Param) BOOST_PP_IIF_BOOST_PP_BOOL_nfixed (BOOST_PP_COMMA, BOOST_PP_EMPTY)() const boost::parameter::aux ::empty_arg_list &) >::type name(BOOST_PP_REPEAT_1_nfixed (BOOST_PP_ENUM_BINARY_PARAMS_M, (const Param, & param))) { typedef typename boost::detail::convert_bgl_params_to_boost_parameter <boost::no_named_parameters>::type arg_pack_type; arg_pack_type arg_pack = boost::detail::convert_bgl_params_to_boost_parameter <boost::no_named_parameters>::conv(boost::no_named_parameters ()); return ::boost::graph::name_with_named_params(BOOST_PP_REPEAT_1_nfixed (BOOST_PP_ENUM_PARAMS_M, param) BOOST_PP_IIF_BOOST_PP_BOOL_nfixed (BOOST_PP_COMMA, BOOST_PP_EMPTY)() arg_pack); } \ | |||
| 527 | template <BOOST_PP_ENUM_PARAMS(nfixed, typename Param)BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, typename Param ) BOOST_PP_COMMA_IF(nfixed)BOOST_PP_IIF_BOOST_PP_BOOL_nfixed(BOOST_PP_COMMA, BOOST_PP_EMPTY )() class P, class T, class R> \ | |||
| 528 | typename boost::result_of< \ | |||
| 529 | ::boost::graph::detail::BOOST_PP_CAT(name, _impl)name_impl BOOST_PP_EXPR_IF(nfixed, <)BOOST_PP_EXPR_IIF_BOOST_PP_BOOL_nfixed(<) BOOST_PP_ENUM_PARAMS(nfixed, Param)BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, Param) BOOST_PP_EXPR_IF(nfixed, >)BOOST_PP_EXPR_IIF_BOOST_PP_BOOL_nfixed(>) \ | |||
| 530 | (BOOST_PP_ENUM_PARAMS(nfixed, Param)BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, Param) BOOST_PP_COMMA_IF(nfixed)BOOST_PP_IIF_BOOST_PP_BOOL_nfixed(BOOST_PP_COMMA, BOOST_PP_EMPTY )() \ | |||
| 531 | const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<P, T, R> >::type &) \ | |||
| 532 | >::type \ | |||
| 533 | name(BOOST_PP_ENUM_BINARY_PARAMS(nfixed, const Param, & param)BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_BINARY_PARAMS_M, (const Param, & param)) BOOST_PP_COMMA_IF(nfixed)BOOST_PP_IIF_BOOST_PP_BOOL_nfixed(BOOST_PP_COMMA, BOOST_PP_EMPTY )() const boost::bgl_named_params<P, T, R>& old_style_params) { \ | |||
| 534 | typedef boost::bgl_named_params<P, T, R> old_style_params_type; \ | |||
| 535 | BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(old_style_params_type, old_style_params)typedef typename boost::detail::convert_bgl_params_to_boost_parameter <old_style_params_type>::type arg_pack_type; arg_pack_type arg_pack = boost::detail::convert_bgl_params_to_boost_parameter <old_style_params_type>::conv(old_style_params); \ | |||
| 536 | return ::boost::graph::BOOST_PP_CAT(name, _with_named_params)name_with_named_params(BOOST_PP_ENUM_PARAMS(nfixed, param)BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, param) BOOST_PP_COMMA_IF(nfixed)BOOST_PP_IIF_BOOST_PP_BOOL_nfixed(BOOST_PP_COMMA, BOOST_PP_EMPTY )() arg_pack); \ | |||
| 537 | } \ | |||
| 538 | \ | |||
| 539 | BOOST_PP_EXPR_IF(nfixed, template <)BOOST_PP_EXPR_IIF_BOOST_PP_BOOL_nfixed(template <) BOOST_PP_ENUM_PARAMS(nfixed, typename Param)BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, typename Param ) BOOST_PP_EXPR_IF(nfixed, >)BOOST_PP_EXPR_IIF_BOOST_PP_BOOL_nfixed(>) \ | |||
| 540 | BOOST_PP_EXPR_IF(nfixed, typename)BOOST_PP_EXPR_IIF_BOOST_PP_BOOL_nfixed(typename) boost::result_of< \ | |||
| 541 | ::boost::graph::detail::BOOST_PP_CAT(name, _impl)name_impl BOOST_PP_EXPR_IF(nfixed, <)BOOST_PP_EXPR_IIF_BOOST_PP_BOOL_nfixed(<) BOOST_PP_ENUM_PARAMS(nfixed, Param)BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, Param) BOOST_PP_EXPR_IF(nfixed, >)BOOST_PP_EXPR_IIF_BOOST_PP_BOOL_nfixed(>) \ | |||
| 542 | (BOOST_PP_ENUM_PARAMS(nfixed, Param)BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, Param) BOOST_PP_COMMA_IF(nfixed)BOOST_PP_IIF_BOOST_PP_BOOL_nfixed(BOOST_PP_COMMA, BOOST_PP_EMPTY )() const boost::parameter::aux::empty_arg_list &) \ | |||
| 543 | >::type \ | |||
| 544 | name(BOOST_PP_ENUM_BINARY_PARAMS(nfixed, const Param, & param)BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_BINARY_PARAMS_M, (const Param, & param))) { \ | |||
| 545 | BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(boost::no_named_parameters, boost::no_named_parameters())typedef typename boost::detail::convert_bgl_params_to_boost_parameter <boost::no_named_parameters>::type arg_pack_type; arg_pack_type arg_pack = boost::detail::convert_bgl_params_to_boost_parameter <boost::no_named_parameters>::conv(boost::no_named_parameters ()); \ | |||
| 546 | return ::boost::graph::BOOST_PP_CAT(name, _with_named_params)name_with_named_params(BOOST_PP_ENUM_PARAMS(nfixed, param)BOOST_PP_REPEAT_1_nfixed(BOOST_PP_ENUM_PARAMS_M, param) BOOST_PP_COMMA_IF(nfixed)BOOST_PP_IIF_BOOST_PP_BOOL_nfixed(BOOST_PP_COMMA, BOOST_PP_EMPTY )() arg_pack); \ | |||
| 547 | } | |||
| 548 | ||||
| 549 | } | |||
| 550 | ||||
| 551 | namespace detail { | |||
| 552 | ||||
| 553 | template <bool Exists, typename Graph, typename ArgPack, typename Value, typename PM> | |||
| 554 | struct map_maker_helper { | |||
| 555 | typedef PM map_type; | |||
| 556 | static PM make_map(const Graph&, Value, const PM& pm, const ArgPack&) { | |||
| 557 | return pm; | |||
| 558 | } | |||
| 559 | }; | |||
| 560 | ||||
| 561 | template <typename Graph, typename ArgPack, typename Value, typename PM> | |||
| 562 | struct map_maker_helper<false, Graph, ArgPack, Value, PM> { | |||
| 563 | typedef typename boost::remove_const< | |||
| 564 | typename override_const_property_t< | |||
| 565 | typename boost::parameter::value_type< | |||
| 566 | ArgPack, boost::graph::keywords::tag::vertex_index_map, int>::type, | |||
| 567 | boost::vertex_index_t, | |||
| 568 | Graph, | |||
| 569 | boost::detail::parameter_exists< | |||
| 570 | ArgPack, boost::graph::keywords::tag::vertex_index_map>::value | |||
| 571 | >::result_type>::type vi_map_type; | |||
| 572 | typedef | |||
| 573 | boost::shared_array_property_map<Value, vi_map_type> | |||
| 574 | map_type; | |||
| 575 | static map_type make_map(const Graph& g, | |||
| 576 | Value v, | |||
| 577 | const PM&, | |||
| 578 | const ArgPack& ap) { | |||
| 579 | return make_shared_array_property_map( | |||
| 580 | num_vertices(g), | |||
| 581 | v, | |||
| 582 | override_const_property( | |||
| 583 | ap, | |||
| 584 | boost::graph::keywords::_vertex_index_map, | |||
| 585 | g, vertex_index)); | |||
| 586 | } | |||
| 587 | }; | |||
| 588 | ||||
| 589 | template <typename Graph, typename ArgPack, typename MapTag, typename ValueType> | |||
| 590 | struct map_maker { | |||
| 591 | BOOST_STATIC_CONSTANT(static const bool has_map = (parameter_exists<ArgPack, MapTag > ::value) | |||
| 592 | bool,static const bool has_map = (parameter_exists<ArgPack, MapTag > ::value) | |||
| 593 | has_map =static const bool has_map = (parameter_exists<ArgPack, MapTag > ::value) | |||
| 594 | (parameter_exists<ArgPack, MapTag>static const bool has_map = (parameter_exists<ArgPack, MapTag > ::value) | |||
| 595 | ::value))static const bool has_map = (parameter_exists<ArgPack, MapTag > ::value); | |||
| 596 | typedef map_maker_helper<has_map, Graph, ArgPack, ValueType, | |||
| 597 | typename boost::remove_const< | |||
| 598 | typename boost::parameter::value_type< | |||
| 599 | ArgPack, | |||
| 600 | MapTag, | |||
| 601 | int | |||
| 602 | >::type | |||
| 603 | >::type> helper; | |||
| 604 | typedef typename helper::map_type map_type; | |||
| 605 | static map_type make_map(const Graph& g, const ArgPack& ap, ValueType default_value) { | |||
| 606 | return helper::make_map(g, default_value, ap[::boost::parameter::keyword<MapTag>::instance | 0], ap); | |||
| 607 | } | |||
| 608 | }; | |||
| 609 | ||||
| 610 | template <typename MapTag, typename ValueType = void> | |||
| 611 | class make_property_map_from_arg_pack_gen { | |||
| 612 | ValueType default_value; | |||
| 613 | ||||
| 614 | public: | |||
| 615 | make_property_map_from_arg_pack_gen(ValueType default_value) | |||
| 616 | : default_value(default_value) {} | |||
| 617 | ||||
| 618 | template <typename Graph, typename ArgPack> | |||
| 619 | typename map_maker<Graph, ArgPack, MapTag, ValueType>::map_type | |||
| 620 | operator()(const Graph& g, const ArgPack& ap) const { | |||
| 621 | return map_maker<Graph, ArgPack, MapTag, ValueType>::make_map(g, ap, default_value); | |||
| 622 | } | |||
| 623 | }; | |||
| 624 | ||||
| 625 | template <typename MapTag> | |||
| 626 | class make_property_map_from_arg_pack_gen<MapTag, void> { | |||
| 627 | public: | |||
| 628 | template <typename ValueType, typename Graph, typename ArgPack> | |||
| 629 | typename map_maker<Graph, ArgPack, MapTag, ValueType>::map_type | |||
| 630 | operator()(const Graph& g, const ArgPack& ap, ValueType default_value) const { | |||
| 631 | return map_maker<Graph, ArgPack, MapTag, ValueType>::make_map(g, ap, default_value); | |||
| 632 | } | |||
| 633 | }; | |||
| 634 | ||||
| 635 | static const | |||
| 636 | make_property_map_from_arg_pack_gen< | |||
| 637 | boost::graph::keywords::tag::color_map, | |||
| 638 | default_color_type> | |||
| 639 | make_color_map_from_arg_pack(white_color); | |||
| 640 | ||||
| 641 | template <bool Exists, class Graph, class ArgPack, class KeyT, class ValueT, class KeyMapTag, class IndexInHeapMapTag, class Compare, class Q> | |||
| 642 | struct priority_queue_maker_helper { | |||
| 643 | typedef Q priority_queue_type; | |||
| 644 | ||||
| 645 | static priority_queue_type | |||
| 646 | make_queue(const Graph&, const ArgPack&, KeyT, const Q& q) { | |||
| 647 | return q; | |||
| 648 | } | |||
| 649 | }; | |||
| 650 | ||||
| 651 | template <class Graph, class ArgPack, class KeyT, class ValueT, class KeyMapTag, class IndexInHeapMapTag, class Compare, class Q> | |||
| 652 | struct priority_queue_maker_helper<false, Graph, ArgPack, KeyT, ValueT, KeyMapTag, IndexInHeapMapTag, Compare, Q> { | |||
| 653 | typedef typename std::vector<ValueT>::size_type default_index_in_heap_type; | |||
| 654 | typedef typename map_maker<Graph, ArgPack, IndexInHeapMapTag, default_index_in_heap_type>::helper::map_type index_in_heap_map; | |||
| 655 | typedef boost::d_ary_heap_indirect<ValueT, 4, index_in_heap_map, typename map_maker<Graph, ArgPack, KeyMapTag, KeyT>::helper::map_type, Compare> priority_queue_type; | |||
| 656 | ||||
| 657 | static priority_queue_type | |||
| 658 | make_queue(const Graph& g, const ArgPack& ap, KeyT defaultKey, const Q&) { | |||
| 659 | return priority_queue_type( | |||
| 660 | map_maker<Graph, ArgPack, KeyMapTag, KeyT>::make_map(g, ap, defaultKey), | |||
| 661 | map_maker<Graph, ArgPack, IndexInHeapMapTag, default_index_in_heap_type>::make_map(g, ap, typename boost::property_traits<index_in_heap_map>::value_type(-1)) | |||
| 662 | ); | |||
| 663 | } | |||
| 664 | }; | |||
| 665 | ||||
| 666 | template <class Graph, class ArgPack, class KeyT, class ValueT, class PriorityQueueTag, class KeyMapTag, class IndexInHeapMapTag, class Compare> | |||
| 667 | struct priority_queue_maker { | |||
| 668 | BOOST_STATIC_CONSTANT(static const bool g_hasQ = (parameter_exists<ArgPack, PriorityQueueTag > ::value) | |||
| 669 | bool,static const bool g_hasQ = (parameter_exists<ArgPack, PriorityQueueTag > ::value) | |||
| 670 | g_hasQ =static const bool g_hasQ = (parameter_exists<ArgPack, PriorityQueueTag > ::value) | |||
| 671 | (parameter_exists<ArgPack, PriorityQueueTag>static const bool g_hasQ = (parameter_exists<ArgPack, PriorityQueueTag > ::value) | |||
| 672 | ::value))static const bool g_hasQ = (parameter_exists<ArgPack, PriorityQueueTag > ::value); | |||
| 673 | typedef boost::reference_wrapper<int> int_refw; | |||
| 674 | typedef typename boost::parameter::value_type< | |||
| 675 | ArgPack, | |||
| 676 | PriorityQueueTag, | |||
| 677 | int_refw | |||
| 678 | >::type | |||
| 679 | param_value_type_wrapper; | |||
| 680 | typedef typename param_value_type_wrapper::type | |||
| 681 | param_value_type; | |||
| 682 | typedef typename boost::remove_const<param_value_type>::type param_value_type_no_const; | |||
| 683 | typedef priority_queue_maker_helper<g_hasQ, Graph, ArgPack, KeyT, ValueT, KeyMapTag, IndexInHeapMapTag, Compare, | |||
| 684 | param_value_type_no_const> helper; | |||
| 685 | typedef typename helper::priority_queue_type priority_queue_type; | |||
| 686 | ||||
| 687 | static priority_queue_type make_queue(const Graph& g, const ArgPack& ap, KeyT defaultKey) { | |||
| 688 | return helper::make_queue(g, ap, defaultKey, ap[::boost::parameter::keyword<PriorityQueueTag>::instance | 0]); | |||
| 689 | } | |||
| 690 | }; | |||
| 691 | ||||
| 692 | template <class PriorityQueueTag, class KeyT, class ValueT, class Compare = std::less<KeyT>, class KeyMapTag = boost::graph::keywords::tag::distance_map, class IndexInHeapMapTag = boost::graph::keywords::tag::index_in_heap_map> | |||
| 693 | struct make_priority_queue_from_arg_pack_gen { | |||
| 694 | KeyT defaultKey; | |||
| 695 | ||||
| 696 | make_priority_queue_from_arg_pack_gen(KeyT defaultKey_) : defaultKey(defaultKey_) { } | |||
| 697 | ||||
| 698 | template <class F> | |||
| 699 | struct result { | |||
| 700 | typedef typename remove_const<typename remove_reference<typename function_traits<F>::arg1_type>::type>::type graph_type; | |||
| 701 | typedef typename remove_const<typename remove_reference<typename function_traits<F>::arg2_type>::type>::type arg_pack_type; | |||
| 702 | typedef typename priority_queue_maker<graph_type, arg_pack_type, KeyT, ValueT, PriorityQueueTag, KeyMapTag, IndexInHeapMapTag, Compare>::priority_queue_type type; | |||
| 703 | }; | |||
| 704 | ||||
| 705 | template <class Graph, class ArgPack> | |||
| 706 | typename priority_queue_maker<Graph, ArgPack, KeyT, ValueT, PriorityQueueTag, KeyMapTag, IndexInHeapMapTag, Compare>::priority_queue_type | |||
| 707 | operator()(const Graph& g, const ArgPack& ap) const { | |||
| 708 | return priority_queue_maker<Graph, ArgPack, KeyT, ValueT, PriorityQueueTag, KeyMapTag, IndexInHeapMapTag, Compare>::make_queue(g, ap, defaultKey); | |||
| 709 | } | |||
| 710 | }; | |||
| 711 | ||||
| 712 | template <typename G> | |||
| 713 | typename boost::graph_traits<G>::vertex_descriptor | |||
| 714 | get_null_vertex(const G&) {return boost::graph_traits<G>::null_vertex();} | |||
| 715 | ||||
| 716 | template <typename G> | |||
| 717 | typename boost::graph_traits<G>::vertex_descriptor | |||
| 718 | get_default_starting_vertex(const G& g) { | |||
| 719 | std::pair<typename boost::graph_traits<G>::vertex_iterator, typename boost::graph_traits<G>::vertex_iterator> iters = vertices(g); | |||
| 720 | return (iters.first == iters.second) ? boost::graph_traits<G>::null_vertex() : *iters.first; | |||
| 721 | } | |||
| 722 | ||||
| 723 | template <typename G> | |||
| 724 | struct get_default_starting_vertex_t { | |||
| 725 | typedef typename boost::graph_traits<G>::vertex_descriptor result_type; | |||
| 726 | const G& g; | |||
| 727 | get_default_starting_vertex_t(const G& g): g(g) {} | |||
| 728 | result_type operator()() const {return get_default_starting_vertex(g);} | |||
| 729 | }; | |||
| 730 | ||||
| 731 | // Wrapper to avoid instantiating numeric_limits when users provide distance_inf value manually | |||
| 732 | template <typename T> | |||
| 733 | struct get_max { | |||
| 734 | T operator()() const { | |||
| 735 | return (std::numeric_limits<T>::max)(); | |||
| 736 | } | |||
| 737 | typedef T result_type; | |||
| 738 | }; | |||
| 739 | ||||
| 740 | } // namespace detail | |||
| 741 | ||||
| 742 | } // namespace boost | |||
| 743 | ||||
| 744 | #undef BOOST_BGL_DECLARE_NAMED_PARAMS | |||
| 745 | ||||
| 746 | #endif // BOOST_GRAPH_NAMED_FUNCTION_PARAMS_HPP |