Back to home page

EIC code displayed by LXR

 
 

    


File indexing completed on 2025-01-18 09:37:24

0001 // Copyright 2005-2009 The Trustees of Indiana University.
0002 
0003 // Distributed under the Boost Software License, Version 1.0.
0004 // (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006 
0007 //  Authors: Jeremiah Willcock
0008 //           Douglas Gregor
0009 //           Andrew Lumsdaine
0010 
0011 // Compressed sparse row graph type
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 // A tag type indicating that the graph in question is a compressed
0054 // sparse row graph. This is an internal detail of the BGL.
0055 struct csr_graph_tag;
0056 
0057 // A type (edges_are_sorted_t) and a value (edges_are_sorted) used to indicate
0058 // that the edge list passed into the CSR graph is already sorted by source
0059 // vertex.
0060 enum edges_are_sorted_t
0061 {
0062     edges_are_sorted
0063 };
0064 
0065 // A type (edges_are_sorted_global_t) and a value (edges_are_sorted_global)
0066 // used to indicate that the edge list passed into the CSR graph is already
0067 // sorted by source vertex.
0068 enum edges_are_sorted_global_t
0069 {
0070     edges_are_sorted_global
0071 };
0072 
0073 // A type (edges_are_unsorted_t) and a value (edges_are_unsorted) used to
0074 // indicate that the edge list passed into the CSR graph is not sorted by
0075 // source vertex.  This version caches the edge information in memory, and thus
0076 // requires only a single pass over the input data.
0077 enum edges_are_unsorted_t
0078 {
0079     edges_are_unsorted
0080 };
0081 
0082 // A type (edges_are_unsorted_multi_pass_t) and a value
0083 // (edges_are_unsorted_multi_pass) used to indicate that the edge list passed
0084 // into the CSR graph is not sorted by source vertex.  This version uses less
0085 // memory but requires multi-pass capability on the iterators.
0086 enum edges_are_unsorted_multi_pass_t
0087 {
0088     edges_are_unsorted_multi_pass
0089 };
0090 
0091 // A type (edges_are_unsorted_multi_pass_global_t) and a value
0092 // (edges_are_unsorted_multi_pass_global) used to indicate that the edge list
0093 // passed into the CSR graph is not sorted by source vertex.  This version uses
0094 // less memory but requires multi-pass capability on the iterators.  The
0095 // global mapping and filtering is done here because it is often faster and it
0096 // greatly simplifies handling of edge properties.
0097 enum edges_are_unsorted_multi_pass_global_t
0098 {
0099     edges_are_unsorted_multi_pass_global
0100 };
0101 
0102 // A type (construct_inplace_from_sources_and_targets_t) and a value
0103 // (construct_inplace_from_sources_and_targets) used to indicate that mutable
0104 // vectors of sources and targets (and possibly edge properties) are being used
0105 // to construct the CSR graph.  These vectors are sorted in-place and then the
0106 // targets and properties are swapped into the graph data structure.
0107 enum construct_inplace_from_sources_and_targets_t
0108 {
0109     construct_inplace_from_sources_and_targets
0110 };
0111 
0112 // A type (construct_inplace_from_sources_and_targets_global_t) and a value
0113 // (construct_inplace_from_sources_and_targets_global) used to indicate that
0114 // mutable vectors of sources and targets (and possibly edge properties) are
0115 // being used to construct the CSR graph.  These vectors are sorted in-place
0116 // and then the targets and properties are swapped into the graph data
0117 // structure.  It is assumed that global indices (for distributed CSR) are
0118 // used, and a map is required to convert those to local indices.  This
0119 // constructor is intended for internal use by the various CSR graphs
0120 // (sequential and distributed).
0121 enum construct_inplace_from_sources_and_targets_global_t
0122 {
0123     construct_inplace_from_sources_and_targets_global
0124 };
0125 
0126 // A type (edges_are_unsorted_global_t) and a value (edges_are_unsorted_global)
0127 // used to indicate that the edge list passed into the CSR graph is not sorted
0128 // by source vertex.  The data is also stored using global vertex indices, and
0129 // must be filtered to choose only local vertices.  This constructor caches the
0130 // edge information in memory, and thus requires only a single pass over the
0131 // input data.  This constructor is intended for internal use by the
0132 // distributed CSR constructors.
0133 enum edges_are_unsorted_global_t
0134 {
0135     edges_are_unsorted_global
0136 };
0137 
0138 /****************************************************************************
0139  * Local helper macros to reduce typing and clutter later on.               *
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 /*i*/) 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 /** Compressed sparse row graph.
0205  *
0206  * Vertex and EdgeIndex should be unsigned integral types and should
0207  * specialize numeric_limits.
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; // Not defined
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     // Some tests to prevent use of "void" is a property type (as was done in
0228     // some test cases):
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     // For Property Graph
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     /* At this time, the compressed sparse row graph can only be used to
0245      * create directed and bidirectional graphs. In the future,
0246      * undirected CSR graphs will also be supported.
0247      */
0248     // BOOST_STATIC_ASSERT((is_same<Directed, directedS>::value));
0249 
0250     // Concept requirements:
0251     // For Graph
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     // For VertexListGraph
0267     typedef counting_iterator< Vertex > vertex_iterator;
0268     typedef Vertex vertices_size_type;
0269 
0270     // For EdgeListGraph
0271     typedef EdgeIndex edges_size_type;
0272 
0273     // For IncidenceGraph
0274     typedef detail::csr_out_edge_iterator< compressed_sparse_row_graph >
0275         out_edge_iterator;
0276     typedef EdgeIndex degree_size_type;
0277 
0278     // For AdjacencyGraph
0279     typedef typename std::vector< Vertex >::const_iterator adjacency_iterator;
0280 
0281     // For EdgeListGraph
0282     typedef detail::csr_edge_iterator< compressed_sparse_row_graph >
0283         edge_iterator;
0284 
0285     // For BidirectionalGraph (not implemented)
0286     typedef void in_edge_iterator;
0287 
0288     // For internal use
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     // Constructors
0300 
0301     // Default constructor: an empty graph.
0302     compressed_sparse_row_graph() : m_property() {}
0303 
0304     //  With numverts vertices
0305     compressed_sparse_row_graph(vertices_size_type numverts)
0306     : inherited_vertex_properties(numverts), m_forward(numverts)
0307     {
0308     }
0309 
0310     //  From number of vertices and unsorted list of edges
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     //  From number of vertices and unsorted list of edges, plus edge properties
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     //  From number of vertices and unsorted list of edges, with filter and
0337     //  global-to-local map
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     //  From number of vertices and unsorted list of edges, plus edge
0352     //  properties, with filter and global-to-local map
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     //  From number of vertices and sorted list of edges (new interface)
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     //  From number of vertices and sorted list of edges (new interface)
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     //  From number of vertices and sorted list of edges, filtered and global
0395     //  (new interface)
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     //  From number of vertices and sorted list of edges (new interface)
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     //  From number of vertices and mutable vectors of sources and targets;
0426     //  vectors are returned with unspecified contents but are guaranteed not to
0427     //  share storage with the constructed graph.
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     //  From number of vertices and mutable vectors of sources and targets,
0439     //  expressed with global vertex indices; vectors are returned with
0440     //  unspecified contents but are guaranteed not to share storage with the
0441     //  constructed graph.  This constructor should only be used by the
0442     //  distributed CSR graph.
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     //  From number of vertices and mutable vectors of sources, targets, and
0457     //  edge properties; vectors are returned with unspecified contents but are
0458     //  guaranteed not to share storage with the constructed graph.
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     //  From number of vertices and mutable vectors of sources and targets and
0475     //  edge properties, expressed with global vertex indices; vectors are
0476     //  returned with unspecified contents but are guaranteed not to share
0477     //  storage with the constructed graph.  This constructor should only be
0478     //  used by the distributed CSR graph.
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     //  From number of vertices and single-pass range of unsorted edges.  Data
0496     //  is cached in coordinate form before creating the actual graph.
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     //  From number of vertices and single-pass range of unsorted edges and
0511     //  single-pass range of edge properties.  Data is cached in coordinate form
0512     //  before creating the actual graph.
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     //  From number of vertices and single-pass range of unsorted edges.  Data
0537     //  is cached in coordinate form before creating the actual graph.  Edges
0538     //  are filtered and transformed for use in a distributed graph.
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     //  From number of vertices and single-pass range of unsorted edges and
0556     //  single-pass range of edge properties.  Data is cached in coordinate form
0557     //  before creating the actual graph.  Edges are filtered and transformed
0558     //  for use in a distributed graph.
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     //   Requires IncidenceGraph and a vertex index map
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     //   Requires VertexListGraph and EdgeListGraph
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; // Double each edge (actual doubling done by
0596                            // out_edges function)
0597         }
0598         vertices_size_type numverts = num_vertices(g);
0599         assign(g, vi, numverts, numedges);
0600         inherited_vertex_properties::resize(numverts);
0601     }
0602 
0603     // Requires vertex index map plus requirements of previous constructor
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; // Double each edge (actual doubling done by
0612                            // out_edges function)
0613         }
0614         assign(g, get(vertex_index, g), num_vertices(g), numedges);
0615     }
0616 
0617     // From any graph (slow and uses a lot of memory)
0618     //   Requires IncidenceGraph and a vertex index map
0619     //   Internal helper function
0620     //   Note that numedges must be doubled for undirected source graphs
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     // Requires the above, plus VertexListGraph and EdgeListGraph
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; // Double each edge (actual doubling done by
0638                            // out_edges function)
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     // Requires the above, plus a vertex_index map.
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; // Double each edge (actual doubling done by
0653                            // out_edges function)
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     // Add edges from a sorted (smallest sources first) range of pairs and edge
0661     // properties
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     // Add edges from a sorted (smallest sources first) range of pairs
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     // Add edges from a range of (source, target) pairs that are unsorted
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     // Add edges from a range of (source, target) pairs and edge properties that
0737     // are unsorted
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     // Add edges from a range of (source, target) pairs and edge properties that
0768     // are unsorted
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     // Directly access a edge or edge bundle
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     // Directly access a graph bundle
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     // private: non-portable, requires friend templates
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     // For Property Graph
0832     typedef GraphProperty graph_property_type;
0833     typedef typename lookup_one_property< GraphProperty, graph_bundle_t >::type
0834         graph_bundled;
0835     // typedef GraphProperty graph_property_type;
0836 
0837     typedef detail::compressed_sparse_row_structure< EdgeProperty, Vertex,
0838         EdgeIndex >
0839         forward_type;
0840     typedef EdgeIndex /* typename boost::mpl::if_c<boost::is_same<EdgeProperty,
0841                          boost::no_property>, boost::no_property, EdgeIndex> */
0842         backward_edge_property;
0843     typedef detail::compressed_sparse_row_structure< backward_edge_property,
0844         Vertex, EdgeIndex >
0845         backward_type;
0846 
0847 public:
0848     // Concept requirements:
0849     // For Graph
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     // For VertexListGraph
0865     typedef counting_iterator< Vertex > vertex_iterator;
0866     typedef Vertex vertices_size_type;
0867 
0868     // For EdgeListGraph
0869     typedef EdgeIndex edges_size_type;
0870 
0871     // For IncidenceGraph
0872     typedef detail::csr_out_edge_iterator< compressed_sparse_row_graph >
0873         out_edge_iterator;
0874     typedef EdgeIndex degree_size_type;
0875 
0876     // For AdjacencyGraph
0877     typedef typename std::vector< Vertex >::const_iterator adjacency_iterator;
0878 
0879     // For EdgeListGraph
0880     typedef detail::csr_edge_iterator< compressed_sparse_row_graph >
0881         edge_iterator;
0882 
0883     // For BidirectionalGraph (not implemented)
0884     typedef detail::csr_in_edge_iterator< compressed_sparse_row_graph >
0885         in_edge_iterator;
0886 
0887     // For internal use
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     // Constructors
0899 
0900     // Default constructor: an empty graph.
0901     compressed_sparse_row_graph() : m_property() {}
0902 
0903     //  With numverts vertices
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     //  From number of vertices and unsorted list of edges
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     //  From number of vertices and unsorted list of edges, plus edge properties
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     //  From number of vertices and unsorted list of edges, with filter and
0954     //  global-to-local map
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     //  From number of vertices and unsorted list of edges, plus edge
0970     //  properties, with filter and global-to-local map
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     //   Requires IncidenceGraph and a vertex index map
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     //   Requires VertexListGraph and EdgeListGraph
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; // Double each edge (actual doubling done by
1005                            // out_edges function)
1006         }
1007         vertices_size_type numverts = num_vertices(g);
1008         assign(g, vi, numverts, numedges);
1009         inherited_vertex_properties::resize(numverts);
1010     }
1011 
1012     // Requires vertex index map plus requirements of previous constructor
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; // Double each edge (actual doubling done by
1021                            // out_edges function)
1022         }
1023         assign(g, get(vertex_index, g), num_vertices(g), numedges);
1024     }
1025 
1026     // From any graph (slow and uses a lot of memory)
1027     //   Requires IncidenceGraph and a vertex index map
1028     //   Internal helper function
1029     //   Note that numedges must be doubled for undirected source graphs
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     // Requires the above, plus VertexListGraph and EdgeListGraph
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; // Double each edge (actual doubling done by
1048                            // out_edges function)
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     // Requires the above, plus a vertex_index map.
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; // Double each edge (actual doubling done by
1064                            // out_edges function)
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     // Directly access a edge or edge bundle
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     // private: non-portable, requires friend templates
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 // Construction functions
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 // Add edges from a sorted (smallest sources first) range of pairs and edge
1147 // properties
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 // Add edges from a sorted (smallest sources first) range of pairs
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 // Add edges from a sorted (smallest sources first) range of pairs
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 // Add edges from a range of (source, target) pairs that are unsorted
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 // Add edges from a range of (source, target) pairs that are unsorted
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 // Add edges from a range of (source, target) pairs and edge properties that
1206 // are unsorted
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 // From VertexListGraph
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 // From IncidenceGraph
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 // From AdjacencyGraph
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 // Extra, common functions
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 // edge() can be provided in linear time for the new interface
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 // Find an edge given its index in the graph
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     // Get last source whose rowstart is at most idx
1341     // upper_bound returns this position plus 1
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         // Find the first vertex that has outgoing edges
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 // For Property Graph
1376 
1377 // Graph properties
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 // Kind == void for invalid property tags, so we can use that to SFINAE out
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 // disable_if isn't truly necessary but required to avoid ambiguity with
1466 // specializations below
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 } // end namespace boost
1758 
1759 #endif // BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP