File indexing completed on 2025-01-18 09:37:24
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013 #ifndef BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP
0014 #define BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP
0015
0016 #include <vector>
0017 #include <utility>
0018 #include <algorithm>
0019 #include <climits>
0020 #include <boost/assert.hpp>
0021 #include <iterator>
0022 #if 0
0023 #include <iostream> // For some debugging code below
0024 #endif
0025 #include <boost/graph/graph_traits.hpp>
0026 #include <boost/graph/properties.hpp>
0027 #include <boost/graph/filtered_graph.hpp> // For keep_all
0028 #include <boost/graph/detail/indexed_properties.hpp>
0029 #include <boost/graph/detail/compressed_sparse_row_struct.hpp>
0030 #include <boost/graph/iteration_macros.hpp>
0031 #include <boost/iterator/counting_iterator.hpp>
0032 #include <boost/iterator/reverse_iterator.hpp>
0033 #include <boost/iterator/zip_iterator.hpp>
0034 #include <boost/iterator/transform_iterator.hpp>
0035 #include <boost/tuple/tuple.hpp>
0036 #include <boost/property_map/property_map.hpp>
0037 #include <boost/integer.hpp>
0038 #include <boost/iterator/iterator_facade.hpp>
0039 #include <boost/mpl/if.hpp>
0040 #include <boost/utility/enable_if.hpp>
0041 #include <boost/graph/graph_selectors.hpp>
0042 #include <boost/graph/detail/is_distributed_selector.hpp>
0043 #include <boost/graph/properties.hpp>
0044 #include <boost/static_assert.hpp>
0045 #include <boost/functional/hash.hpp>
0046 #include <boost/next_prior.hpp>
0047 #include <boost/property_map/transform_value_property_map.hpp>
0048 #include <boost/mpl/print.hpp>
0049
0050 namespace boost
0051 {
0052
0053
0054
0055 struct csr_graph_tag;
0056
0057
0058
0059
0060 enum edges_are_sorted_t
0061 {
0062 edges_are_sorted
0063 };
0064
0065
0066
0067
0068 enum edges_are_sorted_global_t
0069 {
0070 edges_are_sorted_global
0071 };
0072
0073
0074
0075
0076
0077 enum edges_are_unsorted_t
0078 {
0079 edges_are_unsorted
0080 };
0081
0082
0083
0084
0085
0086 enum edges_are_unsorted_multi_pass_t
0087 {
0088 edges_are_unsorted_multi_pass
0089 };
0090
0091
0092
0093
0094
0095
0096
0097 enum edges_are_unsorted_multi_pass_global_t
0098 {
0099 edges_are_unsorted_multi_pass_global
0100 };
0101
0102
0103
0104
0105
0106
0107 enum construct_inplace_from_sources_and_targets_t
0108 {
0109 construct_inplace_from_sources_and_targets
0110 };
0111
0112
0113
0114
0115
0116
0117
0118
0119
0120
0121 enum construct_inplace_from_sources_and_targets_global_t
0122 {
0123 construct_inplace_from_sources_and_targets_global
0124 };
0125
0126
0127
0128
0129
0130
0131
0132
0133 enum edges_are_unsorted_global_t
0134 {
0135 edges_are_unsorted_global
0136 };
0137
0138
0139
0140
0141 #define BOOST_CSR_GRAPH_TEMPLATE_PARMS \
0142 typename Directed, typename VertexProperty, typename EdgeProperty, \
0143 typename GraphProperty, typename Vertex, typename EdgeIndex
0144 #define BOOST_CSR_GRAPH_TYPE \
0145 compressed_sparse_row_graph< Directed, VertexProperty, EdgeProperty, \
0146 GraphProperty, Vertex, EdgeIndex >
0147 #define BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS \
0148 typename VertexProperty, typename EdgeProperty, typename GraphProperty, \
0149 typename Vertex, typename EdgeIndex
0150 #define BOOST_DIR_CSR_GRAPH_TYPE \
0151 compressed_sparse_row_graph< directedS, VertexProperty, EdgeProperty, \
0152 GraphProperty, Vertex, EdgeIndex >
0153 #define BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS \
0154 typename VertexProperty, typename EdgeProperty, typename GraphProperty, \
0155 typename Vertex, typename EdgeIndex
0156 #define BOOST_BIDIR_CSR_GRAPH_TYPE \
0157 compressed_sparse_row_graph< bidirectionalS, VertexProperty, EdgeProperty, \
0158 GraphProperty, Vertex, EdgeIndex >
0159
0160 namespace detail
0161 {
0162 template < typename T >
0163 struct default_construct_iterator
0164 : public boost::iterator_facade< default_construct_iterator< T >, T,
0165 boost::random_access_traversal_tag, const T& >
0166 {
0167 typedef boost::iterator_facade< default_construct_iterator< T >, T,
0168 std::random_access_iterator_tag, const T& >
0169 base_type;
0170 T saved_value;
0171 const T& dereference() const { return saved_value; }
0172 bool equal(default_construct_iterator ) const { return true; }
0173 void increment() {}
0174 void decrement() {}
0175 void advance(typename base_type::difference_type) {}
0176 typename base_type::difference_type distance_to(
0177 default_construct_iterator) const
0178 {
0179 return 0;
0180 }
0181 };
0182
0183 template < typename Less > struct compare_first
0184 {
0185 Less less;
0186 compare_first(Less less = Less()) : less(less) {}
0187 template < typename Tuple >
0188 bool operator()(const Tuple& a, const Tuple& b) const
0189 {
0190 return less(a.template get< 0 >(), b.template get< 0 >());
0191 }
0192 };
0193
0194 template < int N, typename Result > struct my_tuple_get_class
0195 {
0196 typedef const Result& result_type;
0197 template < typename Tuple > result_type operator()(const Tuple& t) const
0198 {
0199 return t.template get< N >();
0200 }
0201 };
0202 }
0203
0204
0205
0206
0207
0208
0209 template < typename Directed = directedS, typename VertexProperty = no_property,
0210 typename EdgeProperty = no_property, typename GraphProperty = no_property,
0211 typename Vertex = std::size_t,
0212 typename EdgeIndex = Vertex >
0213 class compressed_sparse_row_graph;
0214
0215 template < typename VertexProperty, typename EdgeProperty,
0216 typename GraphProperty, typename Vertex, typename EdgeIndex >
0217 class compressed_sparse_row_graph< directedS, VertexProperty, EdgeProperty,
0218 GraphProperty, Vertex, EdgeIndex >
0219 : public detail::indexed_vertex_properties< BOOST_DIR_CSR_GRAPH_TYPE,
0220 VertexProperty, Vertex, typed_identity_property_map< Vertex > >
0221 {
0222 public:
0223 typedef detail::indexed_vertex_properties< compressed_sparse_row_graph,
0224 VertexProperty, Vertex, typed_identity_property_map< Vertex > >
0225 inherited_vertex_properties;
0226
0227
0228
0229 BOOST_STATIC_ASSERT((!is_same< VertexProperty, void >::value));
0230 BOOST_STATIC_ASSERT((!is_same< EdgeProperty, void >::value));
0231 BOOST_STATIC_ASSERT((!is_same< GraphProperty, void >::value));
0232
0233 public:
0234
0235 typedef GraphProperty graph_property_type;
0236 typedef typename lookup_one_property< GraphProperty, graph_bundle_t >::type
0237 graph_bundled;
0238
0239 typedef detail::compressed_sparse_row_structure< EdgeProperty, Vertex,
0240 EdgeIndex >
0241 forward_type;
0242
0243 public:
0244
0245
0246
0247
0248
0249
0250
0251
0252 typedef Vertex vertex_descriptor;
0253 typedef detail::csr_edge_descriptor< Vertex, EdgeIndex > edge_descriptor;
0254 typedef directed_tag directed_category;
0255 typedef allow_parallel_edge_tag edge_parallel_category;
0256
0257 class traversal_category : public incidence_graph_tag,
0258 public adjacency_graph_tag,
0259 public vertex_list_graph_tag,
0260 public edge_list_graph_tag
0261 {
0262 };
0263
0264 static vertex_descriptor null_vertex() { return vertex_descriptor(-1); }
0265
0266
0267 typedef counting_iterator< Vertex > vertex_iterator;
0268 typedef Vertex vertices_size_type;
0269
0270
0271 typedef EdgeIndex edges_size_type;
0272
0273
0274 typedef detail::csr_out_edge_iterator< compressed_sparse_row_graph >
0275 out_edge_iterator;
0276 typedef EdgeIndex degree_size_type;
0277
0278
0279 typedef typename std::vector< Vertex >::const_iterator adjacency_iterator;
0280
0281
0282 typedef detail::csr_edge_iterator< compressed_sparse_row_graph >
0283 edge_iterator;
0284
0285
0286 typedef void in_edge_iterator;
0287
0288
0289 typedef csr_graph_tag graph_tag;
0290
0291 typedef typename forward_type::inherited_edge_properties::edge_bundled
0292 edge_bundled;
0293 typedef
0294 typename forward_type::inherited_edge_properties::edge_push_back_type
0295 edge_push_back_type;
0296 typedef typename forward_type::inherited_edge_properties::edge_property_type
0297 edge_property_type;
0298
0299
0300
0301
0302 compressed_sparse_row_graph() : m_property() {}
0303
0304
0305 compressed_sparse_row_graph(vertices_size_type numverts)
0306 : inherited_vertex_properties(numverts), m_forward(numverts)
0307 {
0308 }
0309
0310
0311 template < typename MultiPassInputIterator >
0312 compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
0313 MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
0314 vertices_size_type numverts,
0315 const GraphProperty& prop = GraphProperty())
0316 : inherited_vertex_properties(numverts), m_property(prop)
0317 {
0318 m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end,
0319 numverts, typed_identity_property_map< vertices_size_type >(),
0320 keep_all());
0321 }
0322
0323
0324 template < typename MultiPassInputIterator, typename EdgePropertyIterator >
0325 compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
0326 MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
0327 EdgePropertyIterator ep_iter, vertices_size_type numverts,
0328 const GraphProperty& prop = GraphProperty())
0329 : inherited_vertex_properties(numverts), m_forward(), m_property(prop)
0330 {
0331 m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end,
0332 ep_iter, numverts,
0333 typed_identity_property_map< vertices_size_type >(), keep_all());
0334 }
0335
0336
0337
0338 template < typename MultiPassInputIterator, typename GlobalToLocal,
0339 typename SourcePred >
0340 compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,
0341 MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
0342 vertices_size_type numlocalverts, const GlobalToLocal& global_to_local,
0343 const SourcePred& source_pred,
0344 const GraphProperty& prop = GraphProperty())
0345 : inherited_vertex_properties(numlocalverts), m_forward(), m_property(prop)
0346 {
0347 m_forward.assign_unsorted_multi_pass_edges(
0348 edge_begin, edge_end, numlocalverts, global_to_local, source_pred);
0349 }
0350
0351
0352
0353 template < typename MultiPassInputIterator, typename EdgePropertyIterator,
0354 typename GlobalToLocal, typename SourcePred >
0355 compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,
0356 MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
0357 EdgePropertyIterator ep_iter, vertices_size_type numlocalverts,
0358 const GlobalToLocal& global_to_local, const SourcePred& source_pred,
0359 const GraphProperty& prop = GraphProperty())
0360 : inherited_vertex_properties(numlocalverts), m_forward(), m_property(prop)
0361 {
0362 m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end,
0363 ep_iter, numlocalverts, global_to_local, source_pred);
0364 }
0365
0366
0367 template < typename InputIterator >
0368 compressed_sparse_row_graph(edges_are_sorted_t, InputIterator edge_begin,
0369 InputIterator edge_end, vertices_size_type numverts,
0370 edges_size_type numedges = 0,
0371 const GraphProperty& prop = GraphProperty())
0372 : m_property(prop)
0373 {
0374 m_forward.assign_from_sorted_edges(edge_begin, edge_end,
0375 typed_identity_property_map< vertices_size_type >(), keep_all(),
0376 numverts, numedges);
0377 inherited_vertex_properties::resize(numverts);
0378 }
0379
0380
0381 template < typename InputIterator, typename EdgePropertyIterator >
0382 compressed_sparse_row_graph(edges_are_sorted_t, InputIterator edge_begin,
0383 InputIterator edge_end, EdgePropertyIterator ep_iter,
0384 vertices_size_type numverts, edges_size_type numedges = 0,
0385 const GraphProperty& prop = GraphProperty())
0386 : m_property(prop)
0387 {
0388 m_forward.assign_from_sorted_edges(edge_begin, edge_end, ep_iter,
0389 typed_identity_property_map< vertices_size_type >(), keep_all(),
0390 numverts, numedges);
0391 inherited_vertex_properties::resize(numverts);
0392 }
0393
0394
0395
0396 template < typename InputIterator, typename GlobalToLocal,
0397 typename SourcePred >
0398 compressed_sparse_row_graph(edges_are_sorted_global_t,
0399 InputIterator edge_begin, InputIterator edge_end,
0400 const GlobalToLocal& global_to_local, const SourcePred& source_pred,
0401 vertices_size_type numverts,
0402 const GraphProperty& prop = GraphProperty())
0403 : m_property(prop)
0404 {
0405 m_forward.assign_from_sorted_edges(
0406 edge_begin, edge_end, global_to_local, source_pred, numverts, 0);
0407 inherited_vertex_properties::resize(numverts);
0408 }
0409
0410
0411 template < typename InputIterator, typename EdgePropertyIterator,
0412 typename GlobalToLocal, typename SourcePred >
0413 compressed_sparse_row_graph(edges_are_sorted_global_t,
0414 InputIterator edge_begin, InputIterator edge_end,
0415 EdgePropertyIterator ep_iter, const GlobalToLocal& global_to_local,
0416 const SourcePred& source_pred, vertices_size_type numverts,
0417 const GraphProperty& prop = GraphProperty())
0418 : m_property(prop)
0419 {
0420 m_forward.assign_from_sorted_edges(edge_begin, edge_end, ep_iter,
0421 global_to_local, source_pred, numverts, 0);
0422 inherited_vertex_properties::resize(numverts);
0423 }
0424
0425
0426
0427
0428 compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t,
0429 std::vector< vertex_descriptor >& sources,
0430 std::vector< vertex_descriptor >& targets, vertices_size_type numverts,
0431 const GraphProperty& prop = GraphProperty())
0432 : inherited_vertex_properties(numverts), m_property(prop)
0433 {
0434 m_forward.assign_sources_and_targets_global(sources, targets, numverts,
0435 boost::typed_identity_property_map< vertices_size_type >());
0436 }
0437
0438
0439
0440
0441
0442
0443 template < typename GlobalToLocal >
0444 compressed_sparse_row_graph(
0445 construct_inplace_from_sources_and_targets_global_t,
0446 std::vector< vertex_descriptor >& sources,
0447 std::vector< vertex_descriptor >& targets,
0448 vertices_size_type numlocalverts, GlobalToLocal global_to_local,
0449 const GraphProperty& prop = GraphProperty())
0450 : inherited_vertex_properties(numlocalverts), m_property(prop)
0451 {
0452 m_forward.assign_sources_and_targets_global(
0453 sources, targets, numlocalverts, global_to_local);
0454 }
0455
0456
0457
0458
0459 compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t,
0460 std::vector< vertex_descriptor >& sources,
0461 std::vector< vertex_descriptor >& targets,
0462 std::vector<
0463 typename forward_type::inherited_edge_properties::edge_bundled >&
0464 edge_props,
0465 vertices_size_type numverts,
0466 const GraphProperty& prop = GraphProperty())
0467 : inherited_vertex_properties(numverts), m_property(prop)
0468 {
0469 m_forward.assign_sources_and_targets_global(sources, targets,
0470 edge_props, numverts,
0471 boost::typed_identity_property_map< vertices_size_type >());
0472 }
0473
0474
0475
0476
0477
0478
0479 template < typename GlobalToLocal >
0480 compressed_sparse_row_graph(
0481 construct_inplace_from_sources_and_targets_global_t,
0482 std::vector< vertex_descriptor >& sources,
0483 std::vector< vertex_descriptor >& targets,
0484 std::vector<
0485 typename forward_type::inherited_edge_properties::edge_bundled >&
0486 edge_props,
0487 vertices_size_type numlocalverts, GlobalToLocal global_to_local,
0488 const GraphProperty& prop = GraphProperty())
0489 : inherited_vertex_properties(numlocalverts), m_property(prop)
0490 {
0491 m_forward.assign_sources_and_targets_global(
0492 sources, targets, edge_props, numlocalverts, global_to_local);
0493 }
0494
0495
0496
0497 template < typename InputIterator >
0498 compressed_sparse_row_graph(edges_are_unsorted_t, InputIterator edge_begin,
0499 InputIterator edge_end, vertices_size_type numverts,
0500 const GraphProperty& prop = GraphProperty())
0501 : inherited_vertex_properties(numverts), m_property(prop)
0502 {
0503 std::vector< vertex_descriptor > sources, targets;
0504 boost::graph::detail::split_into_separate_coords(
0505 edge_begin, edge_end, sources, targets);
0506 m_forward.assign_sources_and_targets_global(sources, targets, numverts,
0507 boost::typed_identity_property_map< vertices_size_type >());
0508 }
0509
0510
0511
0512
0513 template < typename InputIterator, typename EdgePropertyIterator >
0514 compressed_sparse_row_graph(edges_are_unsorted_t, InputIterator edge_begin,
0515 InputIterator edge_end, EdgePropertyIterator ep_iter,
0516 vertices_size_type numverts,
0517 const GraphProperty& prop = GraphProperty())
0518 : inherited_vertex_properties(numverts), m_property(prop)
0519 {
0520 std::vector< vertex_descriptor > sources, targets;
0521 boost::graph::detail::split_into_separate_coords(
0522 edge_begin, edge_end, sources, targets);
0523 size_t numedges = sources.size();
0524 std::vector<
0525 typename forward_type::inherited_edge_properties::edge_bundled >
0526 edge_props(numedges);
0527 for (size_t i = 0; i < numedges; ++i)
0528 {
0529 edge_props[i] = *ep_iter++;
0530 }
0531 m_forward.assign_sources_and_targets_global(sources, targets,
0532 edge_props, numverts,
0533 boost::typed_identity_property_map< vertices_size_type >());
0534 }
0535
0536
0537
0538
0539 template < typename InputIterator, typename GlobalToLocal,
0540 typename SourcePred >
0541 compressed_sparse_row_graph(edges_are_unsorted_global_t,
0542 InputIterator edge_begin, InputIterator edge_end,
0543 vertices_size_type numlocalverts, GlobalToLocal global_to_local,
0544 const SourcePred& source_pred,
0545 const GraphProperty& prop = GraphProperty())
0546 : inherited_vertex_properties(numlocalverts), m_property(prop)
0547 {
0548 std::vector< vertex_descriptor > sources, targets;
0549 boost::graph::detail::split_into_separate_coords_filtered(
0550 edge_begin, edge_end, sources, targets, source_pred);
0551 m_forward.assign_sources_and_targets_global(
0552 sources, targets, numlocalverts, global_to_local);
0553 }
0554
0555
0556
0557
0558
0559 template < typename InputIterator, typename EdgePropertyIterator,
0560 typename GlobalToLocal, typename SourcePred >
0561 compressed_sparse_row_graph(edges_are_unsorted_global_t,
0562 InputIterator edge_begin, InputIterator edge_end,
0563 EdgePropertyIterator ep_iter, vertices_size_type numlocalverts,
0564 GlobalToLocal global_to_local, const SourcePred& source_pred,
0565 const GraphProperty& prop = GraphProperty())
0566 : inherited_vertex_properties(numlocalverts), m_property(prop)
0567 {
0568 std::vector< vertex_descriptor > sources, targets;
0569 std::vector< edge_bundled > edge_props;
0570 boost::graph::detail::split_into_separate_coords_filtered(edge_begin,
0571 edge_end, ep_iter, sources, targets, edge_props, source_pred);
0572 m_forward.assign_sources_and_targets_global(
0573 sources, targets, edge_props, numlocalverts, global_to_local);
0574 }
0575
0576
0577 template < typename Graph, typename VertexIndexMap >
0578 compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi,
0579 vertices_size_type numverts, edges_size_type numedges)
0580 : m_property()
0581 {
0582 assign(g, vi, numverts, numedges);
0583 inherited_vertex_properties::resize(numverts);
0584 }
0585
0586
0587 template < typename Graph, typename VertexIndexMap >
0588 compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi)
0589 : m_property()
0590 {
0591 typename graph_traits< Graph >::edges_size_type numedges = num_edges(g);
0592 if (is_same< typename graph_traits< Graph >::directed_category,
0593 undirectedS >::value)
0594 {
0595 numedges *= 2;
0596
0597 }
0598 vertices_size_type numverts = num_vertices(g);
0599 assign(g, vi, numverts, numedges);
0600 inherited_vertex_properties::resize(numverts);
0601 }
0602
0603
0604 template < typename Graph >
0605 explicit compressed_sparse_row_graph(const Graph& g) : m_property()
0606 {
0607 typename graph_traits< Graph >::edges_size_type numedges = num_edges(g);
0608 if (is_same< typename graph_traits< Graph >::directed_category,
0609 undirectedS >::value)
0610 {
0611 numedges *= 2;
0612
0613 }
0614 assign(g, get(vertex_index, g), num_vertices(g), numedges);
0615 }
0616
0617
0618
0619
0620
0621 template < typename Graph, typename VertexIndexMap >
0622 void assign(const Graph& g, const VertexIndexMap& vi,
0623 vertices_size_type numverts, edges_size_type numedges)
0624 {
0625 m_forward.assign(g, vi, numverts, numedges);
0626 inherited_vertex_properties::resize(numverts);
0627 }
0628
0629
0630 template < typename Graph, typename VertexIndexMap >
0631 void assign(const Graph& g, const VertexIndexMap& vi)
0632 {
0633 typename graph_traits< Graph >::edges_size_type numedges = num_edges(g);
0634 if (is_same< typename graph_traits< Graph >::directed_category,
0635 undirectedS >::value)
0636 {
0637 numedges *= 2;
0638
0639 }
0640 vertices_size_type numverts = num_vertices(g);
0641 m_forward.assign(g, vi, numverts, numedges);
0642 inherited_vertex_properties::resize(numverts);
0643 }
0644
0645
0646 template < typename Graph > void assign(const Graph& g)
0647 {
0648 typename graph_traits< Graph >::edges_size_type numedges = num_edges(g);
0649 if (is_same< typename graph_traits< Graph >::directed_category,
0650 undirectedS >::value)
0651 {
0652 numedges *= 2;
0653
0654 }
0655 vertices_size_type numverts = num_vertices(g);
0656 m_forward.assign(g, get(vertex_index, g), numverts, numedges);
0657 inherited_vertex_properties::resize(numverts);
0658 }
0659
0660
0661
0662 template < typename BidirectionalIteratorOrig, typename EPIterOrig,
0663 typename GlobalToLocal >
0664 void add_edges_sorted_internal(BidirectionalIteratorOrig first_sorted,
0665 BidirectionalIteratorOrig last_sorted, EPIterOrig ep_iter_sorted,
0666 const GlobalToLocal& global_to_local)
0667 {
0668 m_forward.add_edges_sorted_internal(
0669 first_sorted, last_sorted, ep_iter_sorted, global_to_local);
0670 }
0671
0672 template < typename BidirectionalIteratorOrig, typename EPIterOrig >
0673 void add_edges_sorted_internal(BidirectionalIteratorOrig first_sorted,
0674 BidirectionalIteratorOrig last_sorted, EPIterOrig ep_iter_sorted)
0675 {
0676 m_forward.add_edges_sorted_internal(first_sorted, last_sorted,
0677 ep_iter_sorted,
0678 typed_identity_property_map< vertices_size_type >());
0679 }
0680
0681
0682 template < typename BidirectionalIteratorOrig >
0683 void add_edges_sorted_internal(BidirectionalIteratorOrig first_sorted,
0684 BidirectionalIteratorOrig last_sorted)
0685 {
0686 m_forward.add_edges_sorted_internal(first_sorted, last_sorted,
0687 detail::default_construct_iterator< edge_bundled >());
0688 }
0689
0690 template < typename BidirectionalIteratorOrig, typename GlobalToLocal >
0691 void add_edges_sorted_internal_global(
0692 BidirectionalIteratorOrig first_sorted,
0693 BidirectionalIteratorOrig last_sorted,
0694 const GlobalToLocal& global_to_local)
0695 {
0696 m_forward.add_edges_sorted_internal(first_sorted, last_sorted,
0697 detail::default_construct_iterator< edge_bundled >(),
0698 global_to_local);
0699 }
0700
0701 template < typename BidirectionalIteratorOrig, typename EPIterOrig,
0702 typename GlobalToLocal >
0703 void add_edges_sorted_internal_global(
0704 BidirectionalIteratorOrig first_sorted,
0705 BidirectionalIteratorOrig last_sorted, EPIterOrig ep_iter_sorted,
0706 const GlobalToLocal& global_to_local)
0707 {
0708 m_forward.add_edges_sorted_internal(
0709 first_sorted, last_sorted, ep_iter_sorted, global_to_local);
0710 }
0711
0712
0713 template < typename InputIterator, typename GlobalToLocal >
0714 inline void add_edges_internal(InputIterator first, InputIterator last,
0715 const GlobalToLocal& global_to_local)
0716 {
0717 typedef compressed_sparse_row_graph Graph;
0718 typedef
0719 typename boost::graph_traits< Graph >::vertex_descriptor vertex_t;
0720 typedef std::vector< std::pair< vertex_t, vertex_t > > edge_vector_t;
0721 edge_vector_t new_edges(first, last);
0722 if (new_edges.empty())
0723 return;
0724 std::sort(new_edges.begin(), new_edges.end());
0725 this->add_edges_sorted_internal_global(
0726 new_edges.begin(), new_edges.end(), global_to_local);
0727 }
0728
0729 template < typename InputIterator >
0730 inline void add_edges_internal(InputIterator first, InputIterator last)
0731 {
0732 this->add_edges_internal(
0733 first, last, typed_identity_property_map< vertices_size_type >());
0734 }
0735
0736
0737
0738 template < typename InputIterator, typename EPIterator,
0739 typename GlobalToLocal >
0740 inline void add_edges_internal(InputIterator first, InputIterator last,
0741 EPIterator ep_iter, EPIterator ep_iter_end,
0742 const GlobalToLocal& global_to_local)
0743 {
0744 typedef compressed_sparse_row_graph Graph;
0745 typedef
0746 typename boost::graph_traits< Graph >::vertex_descriptor vertex_t;
0747 typedef std::pair< vertex_t, vertex_t > vertex_pair;
0748 typedef std::vector< boost::tuple< vertex_pair, edge_bundled > >
0749 edge_vector_t;
0750 edge_vector_t new_edges(
0751 boost::make_zip_iterator(boost::make_tuple(first, ep_iter)),
0752 boost::make_zip_iterator(boost::make_tuple(last, ep_iter_end)));
0753 if (new_edges.empty())
0754 return;
0755 std::sort(new_edges.begin(), new_edges.end(),
0756 boost::detail::compare_first< std::less< vertex_pair > >());
0757 m_forward.add_edges_sorted_internal(
0758 boost::make_transform_iterator(new_edges.begin(),
0759 boost::detail::my_tuple_get_class< 0, vertex_pair >()),
0760 boost::make_transform_iterator(new_edges.end(),
0761 boost::detail::my_tuple_get_class< 0, vertex_pair >()),
0762 boost::make_transform_iterator(new_edges.begin(),
0763 boost::detail::my_tuple_get_class< 1, edge_bundled >()),
0764 global_to_local);
0765 }
0766
0767
0768
0769 template < typename InputIterator, typename EPIterator >
0770 inline void add_edges_internal(InputIterator first, InputIterator last,
0771 EPIterator ep_iter, EPIterator ep_iter_end)
0772 {
0773 this->add_edges_internal(first, last, ep_iter, ep_iter_end,
0774 typed_identity_property_map< vertices_size_type >());
0775 }
0776
0777 using inherited_vertex_properties::operator[];
0778
0779
0780 edge_push_back_type& operator[](const edge_descriptor& v)
0781 {
0782 return m_forward.m_edge_properties[get(edge_index, *this, v)];
0783 }
0784
0785 const edge_push_back_type& operator[](const edge_descriptor& v) const
0786 {
0787 return m_forward.m_edge_properties[get(edge_index, *this, v)];
0788 }
0789
0790
0791 graph_bundled& operator[](graph_bundle_t) { return get_property(*this); }
0792
0793 const graph_bundled& operator[](graph_bundle_t) const
0794 {
0795 return get_property(*this);
0796 }
0797
0798
0799 inherited_vertex_properties& vertex_properties() { return *this; }
0800 const inherited_vertex_properties& vertex_properties() const
0801 {
0802 return *this;
0803 }
0804 typename forward_type::inherited_edge_properties& edge_properties()
0805 {
0806 return m_forward;
0807 }
0808 const typename forward_type::inherited_edge_properties&
0809 edge_properties() const
0810 {
0811 return m_forward;
0812 }
0813
0814 forward_type m_forward;
0815 GraphProperty m_property;
0816 };
0817
0818 template < typename VertexProperty, typename EdgeProperty,
0819 typename GraphProperty, typename Vertex, typename EdgeIndex >
0820 class compressed_sparse_row_graph< bidirectionalS, VertexProperty, EdgeProperty,
0821 GraphProperty, Vertex, EdgeIndex >
0822 : public detail::indexed_vertex_properties< BOOST_BIDIR_CSR_GRAPH_TYPE,
0823 VertexProperty, Vertex, typed_identity_property_map< Vertex > >
0824 {
0825 public:
0826 typedef detail::indexed_vertex_properties< compressed_sparse_row_graph,
0827 VertexProperty, Vertex, typed_identity_property_map< Vertex > >
0828 inherited_vertex_properties;
0829
0830 public:
0831
0832 typedef GraphProperty graph_property_type;
0833 typedef typename lookup_one_property< GraphProperty, graph_bundle_t >::type
0834 graph_bundled;
0835
0836
0837 typedef detail::compressed_sparse_row_structure< EdgeProperty, Vertex,
0838 EdgeIndex >
0839 forward_type;
0840 typedef EdgeIndex
0841
0842 backward_edge_property;
0843 typedef detail::compressed_sparse_row_structure< backward_edge_property,
0844 Vertex, EdgeIndex >
0845 backward_type;
0846
0847 public:
0848
0849
0850 typedef Vertex vertex_descriptor;
0851 typedef detail::csr_edge_descriptor< Vertex, EdgeIndex > edge_descriptor;
0852 typedef bidirectional_tag directed_category;
0853 typedef allow_parallel_edge_tag edge_parallel_category;
0854
0855 class traversal_category : public bidirectional_graph_tag,
0856 public adjacency_graph_tag,
0857 public vertex_list_graph_tag,
0858 public edge_list_graph_tag
0859 {
0860 };
0861
0862 static vertex_descriptor null_vertex() { return vertex_descriptor(-1); }
0863
0864
0865 typedef counting_iterator< Vertex > vertex_iterator;
0866 typedef Vertex vertices_size_type;
0867
0868
0869 typedef EdgeIndex edges_size_type;
0870
0871
0872 typedef detail::csr_out_edge_iterator< compressed_sparse_row_graph >
0873 out_edge_iterator;
0874 typedef EdgeIndex degree_size_type;
0875
0876
0877 typedef typename std::vector< Vertex >::const_iterator adjacency_iterator;
0878
0879
0880 typedef detail::csr_edge_iterator< compressed_sparse_row_graph >
0881 edge_iterator;
0882
0883
0884 typedef detail::csr_in_edge_iterator< compressed_sparse_row_graph >
0885 in_edge_iterator;
0886
0887
0888 typedef csr_graph_tag graph_tag;
0889
0890 typedef typename forward_type::inherited_edge_properties::edge_bundled
0891 edge_bundled;
0892 typedef
0893 typename forward_type::inherited_edge_properties::edge_push_back_type
0894 edge_push_back_type;
0895 typedef typename forward_type::inherited_edge_properties::edge_property_type
0896 edge_property_type;
0897
0898
0899
0900
0901 compressed_sparse_row_graph() : m_property() {}
0902
0903
0904 compressed_sparse_row_graph(vertices_size_type numverts)
0905 : inherited_vertex_properties(numverts)
0906 , m_forward(numverts)
0907 , m_backward(numverts)
0908 {
0909 }
0910
0911 private:
0912 void set_up_backward_property_links()
0913 {
0914 std::pair< edge_iterator, edge_iterator > e = edges(*this);
0915 m_backward.assign_unsorted_multi_pass_edges(
0916 detail::transpose_edges(detail::make_edge_to_index_pair_iter(
0917 *this, get(vertex_index, *this), e.first)),
0918 detail::transpose_edges(detail::make_edge_to_index_pair_iter(
0919 *this, get(vertex_index, *this), e.second)),
0920 boost::counting_iterator< EdgeIndex >(0),
0921 m_forward.m_rowstart.size() - 1,
0922 typed_identity_property_map< Vertex >(), keep_all());
0923 }
0924
0925 public:
0926
0927 template < typename MultiPassInputIterator >
0928 compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
0929 MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
0930 vertices_size_type numverts,
0931 const GraphProperty& prop = GraphProperty())
0932 : inherited_vertex_properties(numverts), m_property(prop)
0933 {
0934 m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end,
0935 numverts, typed_identity_property_map< Vertex >(), keep_all());
0936 set_up_backward_property_links();
0937 }
0938
0939
0940 template < typename MultiPassInputIterator, typename EdgePropertyIterator >
0941 compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
0942 MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
0943 EdgePropertyIterator ep_iter, vertices_size_type numverts,
0944 const GraphProperty& prop = GraphProperty())
0945 : inherited_vertex_properties(numverts), m_forward(), m_property(prop)
0946 {
0947 m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end,
0948 ep_iter, numverts, typed_identity_property_map< Vertex >(),
0949 keep_all());
0950 set_up_backward_property_links();
0951 }
0952
0953
0954
0955 template < typename MultiPassInputIterator, typename GlobalToLocal,
0956 typename SourcePred >
0957 compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,
0958 MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
0959 vertices_size_type numlocalverts, const GlobalToLocal& global_to_local,
0960 const SourcePred& source_pred,
0961 const GraphProperty& prop = GraphProperty())
0962 : inherited_vertex_properties(numlocalverts), m_forward(), m_property(prop)
0963 {
0964 m_forward.assign_unsorted_multi_pass_edges(
0965 edge_begin, edge_end, numlocalverts, global_to_local, source_pred);
0966 set_up_backward_property_links();
0967 }
0968
0969
0970
0971 template < typename MultiPassInputIterator, typename EdgePropertyIterator,
0972 typename GlobalToLocal, typename SourcePred >
0973 compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,
0974 MultiPassInputIterator edge_begin, MultiPassInputIterator edge_end,
0975 EdgePropertyIterator ep_iter, vertices_size_type numlocalverts,
0976 const GlobalToLocal& global_to_local, const SourcePred& source_pred,
0977 const GraphProperty& prop = GraphProperty())
0978 : inherited_vertex_properties(numlocalverts), m_forward(), m_property(prop)
0979 {
0980 m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end,
0981 ep_iter, numlocalverts, global_to_local, source_pred);
0982 set_up_backward_property_links();
0983 }
0984
0985
0986 template < typename Graph, typename VertexIndexMap >
0987 compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi,
0988 vertices_size_type numverts, edges_size_type numedges)
0989 : m_property()
0990 {
0991 assign(g, vi, numverts, numedges);
0992 inherited_vertex_properties::resize(numverts);
0993 }
0994
0995
0996 template < typename Graph, typename VertexIndexMap >
0997 compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi)
0998 : m_property()
0999 {
1000 typename graph_traits< Graph >::edges_size_type numedges = num_edges(g);
1001 if (is_same< typename graph_traits< Graph >::directed_category,
1002 undirectedS >::value)
1003 {
1004 numedges *= 2;
1005
1006 }
1007 vertices_size_type numverts = num_vertices(g);
1008 assign(g, vi, numverts, numedges);
1009 inherited_vertex_properties::resize(numverts);
1010 }
1011
1012
1013 template < typename Graph >
1014 explicit compressed_sparse_row_graph(const Graph& g) : m_property()
1015 {
1016 typename graph_traits< Graph >::edges_size_type numedges = num_edges(g);
1017 if (is_same< typename graph_traits< Graph >::directed_category,
1018 undirectedS >::value)
1019 {
1020 numedges *= 2;
1021
1022 }
1023 assign(g, get(vertex_index, g), num_vertices(g), numedges);
1024 }
1025
1026
1027
1028
1029
1030 template < typename Graph, typename VertexIndexMap >
1031 void assign(const Graph& g, const VertexIndexMap& vi,
1032 vertices_size_type numverts, edges_size_type numedges)
1033 {
1034 m_forward.assign(g, vi, numverts, numedges);
1035 inherited_vertex_properties::resize(numverts);
1036 set_up_backward_property_links();
1037 }
1038
1039
1040 template < typename Graph, typename VertexIndexMap >
1041 void assign(const Graph& g, const VertexIndexMap& vi)
1042 {
1043 typename graph_traits< Graph >::edges_size_type numedges = num_edges(g);
1044 if (is_same< typename graph_traits< Graph >::directed_category,
1045 undirectedS >::value)
1046 {
1047 numedges *= 2;
1048
1049 }
1050 vertices_size_type numverts = num_vertices(g);
1051 m_forward.assign(g, vi, numverts, numedges);
1052 inherited_vertex_properties::resize(numverts);
1053 set_up_backward_property_links();
1054 }
1055
1056
1057 template < typename Graph > void assign(const Graph& g)
1058 {
1059 typename graph_traits< Graph >::edges_size_type numedges = num_edges(g);
1060 if (is_same< typename graph_traits< Graph >::directed_category,
1061 undirectedS >::value)
1062 {
1063 numedges *= 2;
1064
1065 }
1066 vertices_size_type numverts = num_vertices(g);
1067 m_forward.assign(g, get(vertex_index, g), numverts, numedges);
1068 inherited_vertex_properties::resize(numverts);
1069 set_up_backward_property_links();
1070 }
1071
1072 using inherited_vertex_properties::operator[];
1073
1074
1075 edge_push_back_type& operator[](const edge_descriptor& v)
1076 {
1077 return m_forward.m_edge_properties[get(edge_index, *this, v)];
1078 }
1079
1080 const edge_push_back_type& operator[](const edge_descriptor& v) const
1081 {
1082 return m_forward.m_edge_properties[get(edge_index, *this, v)];
1083 }
1084
1085
1086 inherited_vertex_properties& vertex_properties() { return *this; }
1087 const inherited_vertex_properties& vertex_properties() const
1088 {
1089 return *this;
1090 }
1091 typename forward_type::inherited_edge_properties& edge_properties()
1092 {
1093 return m_forward;
1094 }
1095 const typename forward_type::inherited_edge_properties&
1096 edge_properties() const
1097 {
1098 return m_forward;
1099 }
1100
1101 forward_type m_forward;
1102 backward_type m_backward;
1103 GraphProperty m_property;
1104 };
1105
1106
1107 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1108 inline Vertex add_vertex(BOOST_CSR_GRAPH_TYPE& g)
1109 {
1110 add_vertex(g, typename BOOST_CSR_GRAPH_TYPE::vertex_bundled());
1111 }
1112
1113 template < BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS >
1114 inline Vertex add_vertex(BOOST_DIR_CSR_GRAPH_TYPE& g,
1115 typename BOOST_DIR_CSR_GRAPH_TYPE::vertex_bundled const& p)
1116 {
1117 Vertex old_num_verts_plus_one = g.m_forward.m_rowstart.size();
1118 g.m_forward.m_rowstart.push_back(g.m_forward.m_rowstart.back());
1119 g.vertex_properties().push_back(p);
1120 return old_num_verts_plus_one - 1;
1121 }
1122
1123 template < BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS >
1124 inline Vertex add_vertex(BOOST_BIDIR_CSR_GRAPH_TYPE& g,
1125 typename BOOST_BIDIR_CSR_GRAPH_TYPE::vertex_bundled const& p)
1126 {
1127 Vertex old_num_verts_plus_one = g.m_forward.m_rowstart.size();
1128 g.m_forward.m_rowstart.push_back(g.m_forward.m_rowstart.back());
1129 g.m_backward.m_rowstart.push_back(g.m_backward.m_rowstart.back());
1130 g.vertex_properties().push_back(p);
1131 return old_num_verts_plus_one - 1;
1132 }
1133
1134 template < BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS >
1135 inline Vertex add_vertices(
1136 typename BOOST_DIR_CSR_GRAPH_TYPE::vertices_size_type count,
1137 BOOST_DIR_CSR_GRAPH_TYPE& g)
1138 {
1139 Vertex old_num_verts_plus_one = g.m_forward.m_rowstart.size();
1140 EdgeIndex numedges = g.m_forward.m_rowstart.back();
1141 g.m_forward.m_rowstart.resize(old_num_verts_plus_one + count, numedges);
1142 g.vertex_properties().resize(num_vertices(g));
1143 return old_num_verts_plus_one - 1;
1144 }
1145
1146
1147
1148 template < BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS,
1149 typename BidirectionalIteratorOrig, typename EPIterOrig >
1150 void add_edges_sorted(BidirectionalIteratorOrig first_sorted,
1151 BidirectionalIteratorOrig last_sorted, EPIterOrig ep_iter_sorted,
1152 BOOST_DIR_CSR_GRAPH_TYPE& g)
1153 {
1154 g.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted);
1155 }
1156
1157
1158 template < BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS,
1159 typename BidirectionalIteratorOrig >
1160 void add_edges_sorted(BidirectionalIteratorOrig first_sorted,
1161 BidirectionalIteratorOrig last_sorted, BOOST_DIR_CSR_GRAPH_TYPE& g)
1162 {
1163 g.add_edges_sorted_internal(first_sorted, last_sorted);
1164 }
1165
1166 template < BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS,
1167 typename BidirectionalIteratorOrig, typename EPIterOrig,
1168 typename GlobalToLocal >
1169 void add_edges_sorted_global(BidirectionalIteratorOrig first_sorted,
1170 BidirectionalIteratorOrig last_sorted, EPIterOrig ep_iter_sorted,
1171 const GlobalToLocal& global_to_local, BOOST_DIR_CSR_GRAPH_TYPE& g)
1172 {
1173 g.add_edges_sorted_internal_global(
1174 first_sorted, last_sorted, ep_iter_sorted, global_to_local);
1175 }
1176
1177
1178 template < BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS,
1179 typename BidirectionalIteratorOrig, typename GlobalToLocal >
1180 void add_edges_sorted_global(BidirectionalIteratorOrig first_sorted,
1181 BidirectionalIteratorOrig last_sorted, const GlobalToLocal& global_to_local,
1182 BOOST_DIR_CSR_GRAPH_TYPE& g)
1183 {
1184 g.add_edges_sorted_internal_global(
1185 first_sorted, last_sorted, global_to_local);
1186 }
1187
1188
1189 template < BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator,
1190 typename GlobalToLocal >
1191 inline void add_edges_global(InputIterator first, InputIterator last,
1192 const GlobalToLocal& global_to_local, BOOST_DIR_CSR_GRAPH_TYPE& g)
1193 {
1194 g.add_edges_internal(first, last, global_to_local);
1195 }
1196
1197
1198 template < BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator >
1199 inline void add_edges(
1200 InputIterator first, InputIterator last, BOOST_DIR_CSR_GRAPH_TYPE& g)
1201 {
1202 g.add_edges_internal(first, last);
1203 }
1204
1205
1206
1207 template < BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator,
1208 typename EPIterator >
1209 inline void add_edges(InputIterator first, InputIterator last,
1210 EPIterator ep_iter, EPIterator ep_iter_end, BOOST_DIR_CSR_GRAPH_TYPE& g)
1211 {
1212 g.add_edges_internal(first, last, ep_iter, ep_iter_end);
1213 }
1214
1215 template < BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator,
1216 typename EPIterator, typename GlobalToLocal >
1217 inline void add_edges_global(InputIterator first, InputIterator last,
1218 EPIterator ep_iter, EPIterator ep_iter_end,
1219 const GlobalToLocal& global_to_local, BOOST_DIR_CSR_GRAPH_TYPE& g)
1220 {
1221 g.add_edges_internal(first, last, ep_iter, ep_iter_end, global_to_local);
1222 }
1223
1224
1225 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1226 inline Vertex num_vertices(const BOOST_CSR_GRAPH_TYPE& g)
1227 {
1228 return g.m_forward.m_rowstart.size() - 1;
1229 }
1230
1231 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1232 std::pair< counting_iterator< Vertex >,
1233 counting_iterator< Vertex > > inline vertices(const BOOST_CSR_GRAPH_TYPE& g)
1234 {
1235 return std::make_pair(counting_iterator< Vertex >(0),
1236 counting_iterator< Vertex >(num_vertices(g)));
1237 }
1238
1239
1240 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1241 inline Vertex source(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e,
1242 const BOOST_CSR_GRAPH_TYPE&)
1243 {
1244 return e.src;
1245 }
1246
1247 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1248 inline Vertex target(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e,
1249 const BOOST_CSR_GRAPH_TYPE& g)
1250 {
1251 return g.m_forward.m_column[e.idx];
1252 }
1253
1254 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1255 inline std::pair< typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator,
1256 typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator >
1257 out_edges(Vertex v, const BOOST_CSR_GRAPH_TYPE& g)
1258 {
1259 typedef typename BOOST_CSR_GRAPH_TYPE::edge_descriptor ed;
1260 typedef typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator it;
1261 EdgeIndex v_row_start = g.m_forward.m_rowstart[v];
1262 EdgeIndex next_row_start = g.m_forward.m_rowstart[v + 1];
1263 return std::make_pair(it(ed(v, v_row_start)), it(ed(v, next_row_start)));
1264 }
1265
1266 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1267 inline EdgeIndex out_degree(Vertex v, const BOOST_CSR_GRAPH_TYPE& g)
1268 {
1269 EdgeIndex v_row_start = g.m_forward.m_rowstart[v];
1270 EdgeIndex next_row_start = g.m_forward.m_rowstart[v + 1];
1271 return next_row_start - v_row_start;
1272 }
1273
1274 template < BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS >
1275 inline std::pair< typename BOOST_BIDIR_CSR_GRAPH_TYPE::in_edge_iterator,
1276 typename BOOST_BIDIR_CSR_GRAPH_TYPE::in_edge_iterator >
1277 in_edges(Vertex v, const BOOST_BIDIR_CSR_GRAPH_TYPE& g)
1278 {
1279 typedef typename BOOST_BIDIR_CSR_GRAPH_TYPE::in_edge_iterator it;
1280 EdgeIndex v_row_start = g.m_backward.m_rowstart[v];
1281 EdgeIndex next_row_start = g.m_backward.m_rowstart[v + 1];
1282 return std::make_pair(it(g, v_row_start), it(g, next_row_start));
1283 }
1284
1285 template < BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS >
1286 inline EdgeIndex in_degree(Vertex v, const BOOST_BIDIR_CSR_GRAPH_TYPE& g)
1287 {
1288 EdgeIndex v_row_start = g.m_backward.m_rowstart[v];
1289 EdgeIndex next_row_start = g.m_backward.m_rowstart[v + 1];
1290 return next_row_start - v_row_start;
1291 }
1292
1293
1294 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1295 inline std::pair< typename BOOST_CSR_GRAPH_TYPE::adjacency_iterator,
1296 typename BOOST_CSR_GRAPH_TYPE::adjacency_iterator >
1297 adjacent_vertices(Vertex v, const BOOST_CSR_GRAPH_TYPE& g)
1298 {
1299 EdgeIndex v_row_start = g.m_forward.m_rowstart[v];
1300 EdgeIndex next_row_start = g.m_forward.m_rowstart[v + 1];
1301 return std::make_pair(g.m_forward.m_column.begin() + v_row_start,
1302 g.m_forward.m_column.begin() + next_row_start);
1303 }
1304
1305
1306 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1307 inline typename graph_traits< BOOST_CSR_GRAPH_TYPE >::vertex_descriptor vertex(
1308 typename graph_traits< BOOST_CSR_GRAPH_TYPE >::vertex_descriptor i,
1309 const BOOST_CSR_GRAPH_TYPE&)
1310 {
1311 return i;
1312 }
1313
1314
1315
1316 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1317 inline std::pair< typename BOOST_CSR_GRAPH_TYPE::edge_descriptor, bool > edge(
1318 Vertex i, Vertex j, const BOOST_CSR_GRAPH_TYPE& g)
1319 {
1320 typedef typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator out_edge_iter;
1321 std::pair< out_edge_iter, out_edge_iter > range = out_edges(i, g);
1322 for (; range.first != range.second; ++range.first)
1323 {
1324 if (target(*range.first, g) == j)
1325 return std::make_pair(*range.first, true);
1326 }
1327 return std::make_pair(
1328 typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(), false);
1329 }
1330
1331
1332 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1333 inline typename BOOST_CSR_GRAPH_TYPE::edge_descriptor edge_from_index(
1334 EdgeIndex idx, const BOOST_CSR_GRAPH_TYPE& g)
1335 {
1336 typedef typename std::vector< EdgeIndex >::const_iterator row_start_iter;
1337 BOOST_ASSERT(idx < num_edges(g));
1338 row_start_iter src_plus_1 = std::upper_bound(
1339 g.m_forward.m_rowstart.begin(), g.m_forward.m_rowstart.end(), idx);
1340
1341
1342 Vertex src = (src_plus_1 - g.m_forward.m_rowstart.begin()) - 1;
1343 return typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(src, idx);
1344 }
1345
1346 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1347 inline EdgeIndex num_edges(const BOOST_CSR_GRAPH_TYPE& g)
1348 {
1349 return g.m_forward.m_column.size();
1350 }
1351
1352 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1353 std::pair< typename BOOST_CSR_GRAPH_TYPE::edge_iterator,
1354 typename BOOST_CSR_GRAPH_TYPE::edge_iterator >
1355 edges(const BOOST_CSR_GRAPH_TYPE& g)
1356 {
1357 typedef typename BOOST_CSR_GRAPH_TYPE::edge_iterator ei;
1358 typedef typename BOOST_CSR_GRAPH_TYPE::edge_descriptor edgedesc;
1359 if (g.m_forward.m_rowstart.size() == 1 || g.m_forward.m_column.empty())
1360 {
1361 return std::make_pair(ei(), ei());
1362 }
1363 else
1364 {
1365
1366 Vertex src = 0;
1367 while (g.m_forward.m_rowstart[src + 1] == 0)
1368 ++src;
1369 return std::make_pair(
1370 ei(g, edgedesc(src, 0), g.m_forward.m_rowstart[src + 1]),
1371 ei(g, edgedesc(num_vertices(g), g.m_forward.m_column.size()), 0));
1372 }
1373 }
1374
1375
1376
1377
1378 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS, class Tag, class Value >
1379 inline void set_property(BOOST_CSR_GRAPH_TYPE& g, Tag tag, const Value& value)
1380 {
1381 get_property_value(g.m_property, tag) = value;
1382 }
1383
1384 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS, class Tag >
1385 inline typename graph_property< BOOST_CSR_GRAPH_TYPE, Tag >::type& get_property(
1386 BOOST_CSR_GRAPH_TYPE& g, Tag tag)
1387 {
1388 return get_property_value(g.m_property, tag);
1389 }
1390
1391 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS, class Tag >
1392 inline const typename graph_property< BOOST_CSR_GRAPH_TYPE, Tag >::type&
1393 get_property(const BOOST_CSR_GRAPH_TYPE& g, Tag tag)
1394 {
1395 return get_property_value(g.m_property, tag);
1396 }
1397
1398 template < typename G, typename Tag, typename Kind >
1399 struct csr_property_map_helper
1400 {
1401 };
1402
1403
1404 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag >
1405 struct csr_property_map_helper< BOOST_CSR_GRAPH_TYPE, Tag, vertex_property_tag >
1406 {
1407 typedef vertex_all_t all_tag;
1408 typedef
1409 typename property_traits< typename property_map< BOOST_CSR_GRAPH_TYPE,
1410 vertex_all_t >::type >::key_type key_type;
1411 typedef VertexProperty plist_type;
1412 typedef typename property_map< BOOST_CSR_GRAPH_TYPE, vertex_all_t >::type
1413 all_type;
1414 typedef
1415 typename property_map< BOOST_CSR_GRAPH_TYPE, vertex_all_t >::const_type
1416 all_const_type;
1417 typedef transform_value_property_map<
1418 detail::lookup_one_property_f< plist_type, Tag >, all_type >
1419 type;
1420 typedef transform_value_property_map<
1421 detail::lookup_one_property_f< const plist_type, Tag >, all_const_type >
1422 const_type;
1423 };
1424
1425 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag >
1426 struct csr_property_map_helper< BOOST_CSR_GRAPH_TYPE, Tag, edge_property_tag >
1427 {
1428 typedef edge_all_t all_tag;
1429 typedef
1430 typename property_traits< typename property_map< BOOST_CSR_GRAPH_TYPE,
1431 edge_all_t >::type >::key_type key_type;
1432 typedef EdgeProperty plist_type;
1433 typedef typename property_map< BOOST_CSR_GRAPH_TYPE, edge_all_t >::type
1434 all_type;
1435 typedef
1436 typename property_map< BOOST_CSR_GRAPH_TYPE, edge_all_t >::const_type
1437 all_const_type;
1438 typedef transform_value_property_map<
1439 detail::lookup_one_property_f< plist_type, Tag >, all_type >
1440 type;
1441 typedef transform_value_property_map<
1442 detail::lookup_one_property_f< const plist_type, Tag >, all_const_type >
1443 const_type;
1444 };
1445
1446 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag >
1447 struct csr_property_map_helper< BOOST_CSR_GRAPH_TYPE, Tag, graph_property_tag >
1448 {
1449 typedef graph_all_t all_tag;
1450 typedef BOOST_CSR_GRAPH_TYPE* key_type;
1451 typedef GraphProperty plist_type;
1452 typedef typename property_map< BOOST_CSR_GRAPH_TYPE, graph_all_t >::type
1453 all_type;
1454 typedef
1455 typename property_map< BOOST_CSR_GRAPH_TYPE, graph_all_t >::const_type
1456 all_const_type;
1457 typedef transform_value_property_map<
1458 detail::lookup_one_property_f< plist_type, Tag >, all_type >
1459 type;
1460 typedef transform_value_property_map<
1461 detail::lookup_one_property_f< const plist_type, Tag >, all_const_type >
1462 const_type;
1463 };
1464
1465
1466
1467 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag >
1468 struct property_map< BOOST_CSR_GRAPH_TYPE, Tag,
1469 typename disable_if< detail::is_distributed_selector< Vertex > >::type >
1470 : csr_property_map_helper< BOOST_CSR_GRAPH_TYPE, Tag,
1471 typename detail::property_kind_from_graph< BOOST_CSR_GRAPH_TYPE,
1472 Tag >::type >
1473 {
1474 };
1475
1476 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag >
1477 typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::type get(
1478 Tag tag, BOOST_CSR_GRAPH_TYPE& g)
1479 {
1480 return typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::type(tag,
1481 get(typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::all_tag(), g));
1482 }
1483
1484 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag >
1485 typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::const_type get(
1486 Tag tag, const BOOST_CSR_GRAPH_TYPE& g)
1487 {
1488 return typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::const_type(tag,
1489 get(typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::all_tag(), g));
1490 }
1491
1492 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag >
1493 typename property_traits<
1494 typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::type >::reference
1495 get(Tag tag, BOOST_CSR_GRAPH_TYPE& g,
1496 typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::key_type k)
1497 {
1498 typedef typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::all_tag all_tag;
1499 typedef
1500 typename property_map< BOOST_CSR_GRAPH_TYPE, all_tag >::type outer_pm;
1501 return lookup_one_property<
1502 typename property_traits< outer_pm >::value_type,
1503 Tag >::lookup(get(all_tag(), g, k), tag);
1504 }
1505
1506 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag >
1507 typename property_traits<
1508 typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::const_type >::reference
1509 get(Tag tag, const BOOST_CSR_GRAPH_TYPE& g,
1510 typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::key_type k)
1511 {
1512 typedef typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::all_tag all_tag;
1513 typedef typename property_map< BOOST_CSR_GRAPH_TYPE, all_tag >::const_type
1514 outer_pm;
1515 return lookup_one_property<
1516 const typename property_traits< outer_pm >::value_type,
1517 Tag >::lookup(get(all_tag(), g, k), tag);
1518 }
1519
1520 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag >
1521 void put(Tag tag, BOOST_CSR_GRAPH_TYPE& g,
1522 typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::key_type k,
1523 typename lookup_one_property<
1524 typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::plist_type,
1525 Tag >::type val)
1526 {
1527 typedef typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::all_tag all_tag;
1528 lookup_one_property<
1529 typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::plist_type,
1530 Tag >::lookup(get(all_tag(), g, k), tag)
1531 = val;
1532 }
1533
1534 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1535 struct property_map< BOOST_CSR_GRAPH_TYPE, vertex_index_t,
1536 typename disable_if< detail::is_distributed_selector< Vertex > >::type >
1537 {
1538 typedef typed_identity_property_map< Vertex > type;
1539 typedef type const_type;
1540 };
1541
1542 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1543 struct property_map< BOOST_CSR_GRAPH_TYPE, edge_index_t,
1544 typename disable_if< detail::is_distributed_selector< Vertex > >::type >
1545 {
1546 typedef detail::csr_edge_index_map< Vertex, EdgeIndex > type;
1547 typedef type const_type;
1548 };
1549
1550 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1551 struct property_map< BOOST_CSR_GRAPH_TYPE, vertex_all_t,
1552 typename disable_if< detail::is_distributed_selector< Vertex > >::type >
1553 {
1554 typedef typename BOOST_CSR_GRAPH_TYPE::inherited_vertex_properties::
1555 vertex_map_type type;
1556 typedef typename BOOST_CSR_GRAPH_TYPE::inherited_vertex_properties::
1557 const_vertex_map_type const_type;
1558 };
1559
1560 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1561 struct property_map< BOOST_CSR_GRAPH_TYPE, edge_all_t,
1562 typename disable_if< detail::is_distributed_selector< Vertex > >::type >
1563 {
1564 typedef typename BOOST_CSR_GRAPH_TYPE::forward_type::
1565 inherited_edge_properties::edge_map_type type;
1566 typedef typename BOOST_CSR_GRAPH_TYPE::forward_type::
1567 inherited_edge_properties::const_edge_map_type const_type;
1568 };
1569
1570 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1571 struct property_map< BOOST_CSR_GRAPH_TYPE, graph_all_t,
1572 typename disable_if< detail::is_distributed_selector< Vertex > >::type >
1573 {
1574 typedef boost::ref_property_map< BOOST_CSR_GRAPH_TYPE*,
1575 typename BOOST_CSR_GRAPH_TYPE::graph_property_type >
1576 type;
1577 typedef boost::ref_property_map< BOOST_CSR_GRAPH_TYPE*,
1578 const typename BOOST_CSR_GRAPH_TYPE::graph_property_type >
1579 const_type;
1580 };
1581
1582 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1583 inline typed_identity_property_map< Vertex > get(
1584 vertex_index_t, const BOOST_CSR_GRAPH_TYPE&)
1585 {
1586 return typed_identity_property_map< Vertex >();
1587 }
1588
1589 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1590 inline Vertex get(vertex_index_t, const BOOST_CSR_GRAPH_TYPE&, Vertex v)
1591 {
1592 return v;
1593 }
1594
1595 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1596 inline typed_identity_property_map< Vertex > get(
1597 vertex_index_t, BOOST_CSR_GRAPH_TYPE&)
1598 {
1599 return typed_identity_property_map< Vertex >();
1600 }
1601
1602 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1603 inline Vertex get(vertex_index_t, BOOST_CSR_GRAPH_TYPE&, Vertex v)
1604 {
1605 return v;
1606 }
1607
1608 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1609 inline typename property_map< BOOST_CSR_GRAPH_TYPE, edge_index_t >::const_type
1610 get(edge_index_t, const BOOST_CSR_GRAPH_TYPE&)
1611 {
1612 typedef
1613 typename property_map< BOOST_CSR_GRAPH_TYPE, edge_index_t >::const_type
1614 result_type;
1615 return result_type();
1616 }
1617
1618 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1619 inline EdgeIndex get(edge_index_t, const BOOST_CSR_GRAPH_TYPE&,
1620 typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e)
1621 {
1622 return e.idx;
1623 }
1624
1625 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1626 inline typename property_map< BOOST_CSR_GRAPH_TYPE, edge_index_t >::const_type
1627 get(edge_index_t, BOOST_CSR_GRAPH_TYPE&)
1628 {
1629 typedef
1630 typename property_map< BOOST_CSR_GRAPH_TYPE, edge_index_t >::const_type
1631 result_type;
1632 return result_type();
1633 }
1634
1635 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1636 inline EdgeIndex get(edge_index_t, BOOST_CSR_GRAPH_TYPE&,
1637 typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e)
1638 {
1639 return e.idx;
1640 }
1641
1642 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1643 inline typename property_map< BOOST_CSR_GRAPH_TYPE, vertex_all_t >::type get(
1644 vertex_all_t, BOOST_CSR_GRAPH_TYPE& g)
1645 {
1646 return g.get_vertex_bundle(get(vertex_index, g));
1647 }
1648
1649 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1650 inline typename property_map< BOOST_CSR_GRAPH_TYPE, vertex_all_t >::const_type
1651 get(vertex_all_t, const BOOST_CSR_GRAPH_TYPE& g)
1652 {
1653 return g.get_vertex_bundle(get(vertex_index, g));
1654 }
1655
1656 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1657 inline VertexProperty& get(vertex_all_t, BOOST_CSR_GRAPH_TYPE& g, Vertex v)
1658 {
1659 return get(vertex_all, g)[v];
1660 }
1661
1662 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1663 inline const VertexProperty& get(
1664 vertex_all_t, const BOOST_CSR_GRAPH_TYPE& g, Vertex v)
1665 {
1666 return get(vertex_all, g)[v];
1667 }
1668
1669 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1670 inline void put(
1671 vertex_all_t, BOOST_CSR_GRAPH_TYPE& g, Vertex v, const VertexProperty& val)
1672 {
1673 put(get(vertex_all, g), v, val);
1674 }
1675
1676 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1677 inline typename property_map< BOOST_CSR_GRAPH_TYPE, edge_all_t >::type get(
1678 edge_all_t, BOOST_CSR_GRAPH_TYPE& g)
1679 {
1680 return g.m_forward.get_edge_bundle(get(edge_index, g));
1681 }
1682
1683 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1684 inline typename property_map< BOOST_CSR_GRAPH_TYPE, edge_all_t >::const_type
1685 get(edge_all_t, const BOOST_CSR_GRAPH_TYPE& g)
1686 {
1687 return g.m_forward.get_edge_bundle(get(edge_index, g));
1688 }
1689
1690 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1691 inline EdgeProperty& get(edge_all_t, BOOST_CSR_GRAPH_TYPE& g,
1692 const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor& e)
1693 {
1694 return get(edge_all, g)[e];
1695 }
1696
1697 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1698 inline const EdgeProperty& get(edge_all_t, const BOOST_CSR_GRAPH_TYPE& g,
1699 const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor& e)
1700 {
1701 return get(edge_all, g)[e];
1702 }
1703
1704 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1705 inline void put(edge_all_t, BOOST_CSR_GRAPH_TYPE& g,
1706 const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor& e,
1707 const EdgeProperty& val)
1708 {
1709 put(get(edge_all, g), e, val);
1710 }
1711
1712 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1713 inline typename property_map< BOOST_CSR_GRAPH_TYPE, graph_all_t >::type get(
1714 graph_all_t, BOOST_CSR_GRAPH_TYPE& g)
1715 {
1716 return typename property_map< BOOST_CSR_GRAPH_TYPE, graph_all_t >::type(
1717 g.m_property);
1718 }
1719
1720 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1721 inline typename property_map< BOOST_CSR_GRAPH_TYPE, graph_all_t >::const_type
1722 get(graph_all_t, const BOOST_CSR_GRAPH_TYPE& g)
1723 {
1724 return
1725 typename property_map< BOOST_CSR_GRAPH_TYPE, graph_all_t >::const_type(
1726 g.m_property);
1727 }
1728
1729 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1730 inline GraphProperty& get(
1731 graph_all_t, BOOST_CSR_GRAPH_TYPE& g, BOOST_CSR_GRAPH_TYPE*)
1732 {
1733 return g.m_property;
1734 }
1735
1736 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1737 inline const GraphProperty& get(
1738 graph_all_t, const BOOST_CSR_GRAPH_TYPE& g, BOOST_CSR_GRAPH_TYPE*)
1739 {
1740 return g.m_property;
1741 }
1742
1743 template < BOOST_CSR_GRAPH_TEMPLATE_PARMS >
1744 inline void put(graph_all_t, BOOST_CSR_GRAPH_TYPE& g, BOOST_CSR_GRAPH_TYPE*,
1745 const GraphProperty& val)
1746 {
1747 g.m_property = val;
1748 }
1749
1750 #undef BOOST_CSR_GRAPH_TYPE
1751 #undef BOOST_CSR_GRAPH_TEMPLATE_PARMS
1752 #undef BOOST_DIR_CSR_GRAPH_TYPE
1753 #undef BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS
1754 #undef BOOST_BIDIR_CSR_GRAPH_TYPE
1755 #undef BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS
1756
1757 }
1758
1759 #endif