boost/graph/compressed_sparse_row_graph.hpp

   1 // Copyright 2005-2009 The Trustees of Indiana University.
   2
   3 // Distributed under the Boost Software License, Version 1.0.
   4 // (See accompanying file LICENSE_1_0.txt or copy at
   5 // http://www.boost.org/LICENSE_1_0.txt)
   6
   7 //  Authors: Jeremiah Willcock
   8 //           Douglas Gregor
   9 //           Andrew Lumsdaine
  10
  11 // Compressed sparse row graph type
  12
  13 #ifndef BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP
  14 #define BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP
  15
  16 #include <vector>
  17 #include <utility>
  18 #include <algorithm>
  19 #include <climits>
  20 #include <boost/assert.hpp>
  21 #include <iterator>
  22 #if 0
  23 #include <iostream> // For some debugging code below
  24 #endif
  25 #include <boost/graph/graph_traits.hpp>
  26 #include <boost/graph/properties.hpp>
  27 #include <boost/graph/filtered_graph.hpp> // For keep_all
  28 #include <boost/graph/detail/indexed_properties.hpp>
  29 #include <boost/graph/detail/compressed_sparse_row_struct.hpp>
  30 #include <boost/graph/iteration_macros.hpp>
  31 #include <boost/iterator/counting_iterator.hpp>
  32 #include <boost/iterator/reverse_iterator.hpp>
  33 #include <boost/iterator/zip_iterator.hpp>
  34 #include <boost/iterator/transform_iterator.hpp>
  35 #include <boost/tuple/tuple.hpp>
  36 #include <boost/property_map/property_map.hpp>
  37 #include <boost/integer.hpp>
  38 #include <boost/iterator/iterator_facade.hpp>
  39 #include <boost/mpl/if.hpp>
  40 #include <boost/utility/enable_if.hpp>
  41 #include <boost/graph/graph_selectors.hpp>
  42 #include <boost/graph/detail/is_distributed_selector.hpp>
  43 #include <boost/graph/properties.hpp>
  44 #include <boost/static_assert.hpp>
  45 #include <boost/functional/hash.hpp>
  46 #include <boost/next_prior.hpp>
  47 #include <boost/property_map/transform_value_property_map.hpp>
  48 #include <boost/mpl/print.hpp>
  49
  50 namespace boost {
  51
  52 // A tag type indicating that the graph in question is a compressed
  53 // sparse row graph. This is an internal detail of the BGL.
  54 struct csr_graph_tag;
  55
  56 // A type (edges_are_sorted_t) and a value (edges_are_sorted) used to indicate
  57 // that the edge list passed into the CSR graph is already sorted by source
  58 // vertex.
  59 enum edges_are_sorted_t {edges_are_sorted};
  60
  61 // A type (edges_are_sorted_global_t) and a value (edges_are_sorted_global)
  62 // used to indicate that the edge list passed into the CSR graph is already
  63 // sorted by source vertex.
  64 enum edges_are_sorted_global_t {edges_are_sorted_global};
  65
  66 // A type (edges_are_unsorted_t) and a value (edges_are_unsorted) used to
  67 // indicate that the edge list passed into the CSR graph is not sorted by
  68 // source vertex.  This version caches the edge information in memory, and thus
  69 // requires only a single pass over the input data.
  70 enum edges_are_unsorted_t {edges_are_unsorted};
  71
  72 // A type (edges_are_unsorted_multi_pass_t) and a value
  73 // (edges_are_unsorted_multi_pass) used to indicate that the edge list passed
  74 // into the CSR graph is not sorted by source vertex.  This version uses less
  75 // memory but requires multi-pass capability on the iterators.
  76 enum edges_are_unsorted_multi_pass_t {edges_are_unsorted_multi_pass};
  77
  78 // A type (edges_are_unsorted_multi_pass_global_t) and a value
  79 // (edges_are_unsorted_multi_pass_global) used to indicate that the edge list
  80 // passed into the CSR graph is not sorted by source vertex.  This version uses
  81 // less memory but requires multi-pass capability on the iterators.  The
  82 // global mapping and filtering is done here because it is often faster and it
  83 // greatly simplifies handling of edge properties.
  84 enum edges_are_unsorted_multi_pass_global_t {edges_are_unsorted_multi_pass_global};
  85
  86 // A type (construct_inplace_from_sources_and_targets_t) and a value
  87 // (construct_inplace_from_sources_and_targets) used to indicate that mutable
  88 // vectors of sources and targets (and possibly edge properties) are being used
  89 // to construct the CSR graph.  These vectors are sorted in-place and then the
  90 // targets and properties are swapped into the graph data structure.
  91 enum construct_inplace_from_sources_and_targets_t {construct_inplace_from_sources_and_targets};
  92
  93 // A type (construct_inplace_from_sources_and_targets_global_t) and a value
  94 // (construct_inplace_from_sources_and_targets_global) used to indicate that
  95 // mutable vectors of sources and targets (and possibly edge properties) are
  96 // being used to construct the CSR graph.  These vectors are sorted in-place
  97 // and then the targets and properties are swapped into the graph data
  98 // structure.  It is assumed that global indices (for distributed CSR) are
  99 // used, and a map is required to convert those to local indices.  This
 100 // constructor is intended for internal use by the various CSR graphs
 101 // (sequential and distributed).
 102 enum construct_inplace_from_sources_and_targets_global_t {construct_inplace_from_sources_and_targets_global};
 103
 104 // A type (edges_are_unsorted_global_t) and a value (edges_are_unsorted_global)
 105 // used to indicate that the edge list passed into the CSR graph is not sorted
 106 // by source vertex.  The data is also stored using global vertex indices, and
 107 // must be filtered to choose only local vertices.  This constructor caches the
 108 // edge information in memory, and thus requires only a single pass over the
 109 // input data.  This constructor is intended for internal use by the
 110 // distributed CSR constructors.
 111 enum edges_are_unsorted_global_t {edges_are_unsorted_global};
 112
 113 /****************************************************************************
 114  * Local helper macros to reduce typing and clutter later on.               *
 115  ****************************************************************************/
 116 #define BOOST_CSR_GRAPH_TEMPLATE_PARMS                                  \
 117   typename Directed, typename VertexProperty, typename EdgeProperty,    \
 118   typename GraphProperty, typename Vertex, typename EdgeIndex
 119 #define BOOST_CSR_GRAPH_TYPE                                            \
 120    compressed_sparse_row_graph<Directed, VertexProperty, EdgeProperty,  \
 121                                GraphProperty, Vertex, EdgeIndex>
 122 #define BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS                              \
 123   typename VertexProperty, typename EdgeProperty,                       \
 124   typename GraphProperty, typename Vertex, typename EdgeIndex
 125 #define BOOST_DIR_CSR_GRAPH_TYPE                                        \
 126    compressed_sparse_row_graph<directedS, VertexProperty, EdgeProperty, \
 127                                GraphProperty, Vertex, EdgeIndex>
 128 #define BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS                            \
 129   typename VertexProperty, typename EdgeProperty,                       \
 130   typename GraphProperty, typename Vertex, typename EdgeIndex
 131 #define BOOST_BIDIR_CSR_GRAPH_TYPE                                      \
 132    compressed_sparse_row_graph<bidirectionalS, VertexProperty, EdgeProperty, \
 133                                GraphProperty, Vertex, EdgeIndex>
 134
 135 namespace detail {
 136   template <typename T>
 137   struct default_construct_iterator: public boost::iterator_facade<default_construct_iterator<T>, T, boost::random_access_traversal_tag, const T&> {
 138     typedef boost::iterator_facade<default_construct_iterator<T>, T, std::random_access_iterator_tag, const T&> base_type;
 139     T saved_value;
 140     const T& dereference() const {return saved_value;}
 141     bool equal(default_construct_iterator /*i*/) const {return true;}
 142     void increment() {}
 143     void decrement() {}
 144     void advance(typename base_type::difference_type) {}
 145     typename base_type::difference_type distance_to(default_construct_iterator) const {return 0;}
 146   };
 147
 148   template <typename Less>
 149   struct compare_first {
 150     Less less;
 151     compare_first(Less less = Less()): less(less) {}
 152     template <typename Tuple>
 153     bool operator()(const Tuple& a, const Tuple& b) const {
 154       return less(a.template get<0>(), b.template get<0>());
 155     }
 156   };
 157
 158   template <int N, typename Result>
 159   struct my_tuple_get_class {
 160     typedef const Result& result_type;
 161     template <typename Tuple>
 162     result_type operator()(const Tuple& t) const {
 163       return t.template get<N>();
 164     }
 165   };
 166 }
 167
 168 /** Compressed sparse row graph.
 169  *
 170  * Vertex and EdgeIndex should be unsigned integral types and should
 171  * specialize numeric_limits.
 172  */
 173 template<typename Directed = directedS,
 174          typename VertexProperty = no_property,
 175          typename EdgeProperty = no_property,
 176          typename GraphProperty = no_property,
 177          typename Vertex = std::size_t,
 178          typename EdgeIndex = Vertex>
 179 class compressed_sparse_row_graph; // Not defined
 180
 181 template<typename VertexProperty,
 182          typename EdgeProperty,
 183          typename GraphProperty,
 184          typename Vertex,
 185          typename EdgeIndex>
 186 class compressed_sparse_row_graph<directedS, VertexProperty, EdgeProperty, GraphProperty, Vertex, EdgeIndex>
 187    : public detail::indexed_vertex_properties<BOOST_DIR_CSR_GRAPH_TYPE,
 188                                               VertexProperty, Vertex, typed_identity_property_map<Vertex> >
 189 {
 190  public:
 191   typedef detail::indexed_vertex_properties<compressed_sparse_row_graph,
 192                                             VertexProperty, Vertex, typed_identity_property_map<Vertex> >
 193     inherited_vertex_properties;
 194
 195   // Some tests to prevent use of "void" is a property type (as was done in some test cases):
 196   BOOST_STATIC_ASSERT((!is_same<VertexProperty, void>::value));
 197   BOOST_STATIC_ASSERT((!is_same<EdgeProperty, void>::value));
 198   BOOST_STATIC_ASSERT((!is_same<GraphProperty, void>::value));
 199
 200  public:
 201   // For Property Graph
 202   typedef GraphProperty graph_property_type;
 203   typedef typename lookup_one_property<GraphProperty, graph_bundle_t>::type graph_bundled;
 204
 205   typedef detail::compressed_sparse_row_structure<EdgeProperty, Vertex, EdgeIndex> forward_type;
 206
 207  public:
 208   /* At this time, the compressed sparse row graph can only be used to
 209    * create directed and bidirectional graphs. In the future,
 210    * undirected CSR graphs will also be supported.
 211    */
 212   // BOOST_STATIC_ASSERT((is_same<Directed, directedS>::value));
 213
 214   // Concept requirements:
 215   // For Graph
 216   typedef Vertex vertex_descriptor;
 217   typedef detail::csr_edge_descriptor<Vertex, EdgeIndex> edge_descriptor;
 218   typedef directed_tag directed_category;
 219   typedef allow_parallel_edge_tag edge_parallel_category;
 220
 221   class traversal_category: public incidence_graph_tag,
 222                             public adjacency_graph_tag,
 223                             public vertex_list_graph_tag,
 224                             public edge_list_graph_tag {};
 225
 226   static vertex_descriptor null_vertex() { return vertex_descriptor(-1); }
 227
 228   // For VertexListGraph
 229   typedef counting_iterator<Vertex> vertex_iterator;
 230   typedef Vertex vertices_size_type;
 231
 232   // For EdgeListGraph
 233   typedef EdgeIndex edges_size_type;
 234
 235   // For IncidenceGraph
 236   typedef detail::csr_out_edge_iterator<compressed_sparse_row_graph> out_edge_iterator;
 237   typedef EdgeIndex degree_size_type;
 238
 239   // For AdjacencyGraph
 240   typedef typename std::vector<Vertex>::const_iterator adjacency_iterator;
 241
 242   // For EdgeListGraph
 243   typedef detail::csr_edge_iterator<compressed_sparse_row_graph> edge_iterator;
 244
 245   // For BidirectionalGraph (not implemented)
 246   typedef void in_edge_iterator;
 247
 248   // For internal use
 249   typedef csr_graph_tag graph_tag;
 250
 251   typedef typename forward_type::inherited_edge_properties::edge_bundled edge_bundled;
 252   typedef typename forward_type::inherited_edge_properties::edge_push_back_type edge_push_back_type;
 253   typedef typename forward_type::inherited_edge_properties::edge_property_type edge_property_type;
 254
 255   // Constructors
 256
 257   // Default constructor: an empty graph.
 258   compressed_sparse_row_graph(): m_property() {}
 259
 260   //  With numverts vertices
 261   compressed_sparse_row_graph(vertices_size_type numverts)
 262     : inherited_vertex_properties(numverts), m_forward(numverts) {}
 263
 264   //  From number of vertices and unsorted list of edges
 265   template <typename MultiPassInputIterator>
 266   compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
 267                               MultiPassInputIterator edge_begin,
 268                               MultiPassInputIterator edge_end,
 269                               vertices_size_type numverts,
 270                               const GraphProperty& prop = GraphProperty())
 271     : inherited_vertex_properties(numverts), m_property(prop)
 272   {
 273     m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, numverts, typed_identity_property_map<vertices_size_type>(), keep_all());
 274   }
 275
 276   //  From number of vertices and unsorted list of edges, plus edge properties
 277   template <typename MultiPassInputIterator, typename EdgePropertyIterator>
 278   compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
 279                               MultiPassInputIterator edge_begin,
 280                               MultiPassInputIterator edge_end,
 281                               EdgePropertyIterator ep_iter,
 282                               vertices_size_type numverts,
 283                               const GraphProperty& prop = GraphProperty())
 284     : inherited_vertex_properties(numverts), m_forward(), m_property(prop)
 285   {
 286     m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numverts, typed_identity_property_map<vertices_size_type>(), keep_all());
 287   }
 288
 289   //  From number of vertices and unsorted list of edges, with filter and
 290   //  global-to-local map
 291   template <typename MultiPassInputIterator, typename GlobalToLocal, typename SourcePred>
 292   compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,
 293                               MultiPassInputIterator edge_begin,
 294                               MultiPassInputIterator edge_end,
 295                               vertices_size_type numlocalverts,
 296                               const GlobalToLocal& global_to_local,
 297                               const SourcePred& source_pred,
 298                               const GraphProperty& prop = GraphProperty())
 299     : inherited_vertex_properties(numlocalverts), m_forward(), m_property(prop)
 300   {
 301     m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, numlocalverts, global_to_local, source_pred);
 302   }
 303
 304   //  From number of vertices and unsorted list of edges, plus edge properties,
 305   //  with filter and global-to-local map
 306   template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename SourcePred>
 307   compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,
 308                               MultiPassInputIterator edge_begin,
 309                               MultiPassInputIterator edge_end,
 310                               EdgePropertyIterator ep_iter,
 311                               vertices_size_type numlocalverts,
 312                               const GlobalToLocal& global_to_local,
 313                               const SourcePred& source_pred,
 314                               const GraphProperty& prop = GraphProperty())
 315     : inherited_vertex_properties(numlocalverts), m_forward(), m_property(prop)
 316   {
 317     m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numlocalverts, global_to_local, source_pred);
 318   }
 319
 320   //  From number of vertices and sorted list of edges (new interface)
 321   template<typename InputIterator>
 322   compressed_sparse_row_graph(edges_are_sorted_t,
 323                               InputIterator edge_begin, InputIterator edge_end,
 324                               vertices_size_type numverts,
 325                               edges_size_type numedges = 0,
 326                               const GraphProperty& prop = GraphProperty())
 327     : m_property(prop)
 328   {
 329     m_forward.assign_from_sorted_edges(edge_begin, edge_end, typed_identity_property_map<vertices_size_type>(), keep_all(), numverts, numedges);
 330     inherited_vertex_properties::resize(numverts);
 331   }
 332
 333   //  From number of vertices and sorted list of edges (new interface)
 334   template<typename InputIterator, typename EdgePropertyIterator>
 335   compressed_sparse_row_graph(edges_are_sorted_t,
 336                               InputIterator edge_begin, InputIterator edge_end,
 337                               EdgePropertyIterator ep_iter,
 338                               vertices_size_type numverts,
 339                               edges_size_type numedges = 0,
 340                               const GraphProperty& prop = GraphProperty())
 341     : m_property(prop)
 342   {
 343     m_forward.assign_from_sorted_edges(edge_begin, edge_end, ep_iter, typed_identity_property_map<vertices_size_type>(), keep_all(), numverts, numedges);
 344     inherited_vertex_properties::resize(numverts);
 345   }
 346
 347   //  From number of vertices and sorted list of edges, filtered and global (new interface)
 348   template<typename InputIterator, typename GlobalToLocal, typename SourcePred>
 349   compressed_sparse_row_graph(edges_are_sorted_global_t,
 350                               InputIterator edge_begin, InputIterator edge_end,
 351                               const GlobalToLocal& global_to_local,
 352                               const SourcePred& source_pred,
 353                               vertices_size_type numverts,
 354                               const GraphProperty& prop = GraphProperty())
 355     : m_property(prop)
 356   {
 357     m_forward.assign_from_sorted_edges(edge_begin, edge_end, global_to_local, source_pred, numverts, 0);
 358     inherited_vertex_properties::resize(numverts);
 359   }
 360
 361   //  From number of vertices and sorted list of edges (new interface)
 362   template<typename InputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename SourcePred>
 363   compressed_sparse_row_graph(edges_are_sorted_global_t,
 364                               InputIterator edge_begin, InputIterator edge_end,
 365                               EdgePropertyIterator ep_iter,
 366                               const GlobalToLocal& global_to_local,
 367                               const SourcePred& source_pred,
 368                               vertices_size_type numverts,
 369                               const GraphProperty& prop = GraphProperty())
 370     : m_property(prop)
 371   {
 372     m_forward.assign_from_sorted_edges(edge_begin, edge_end, ep_iter, global_to_local, source_pred, numverts, 0);
 373     inherited_vertex_properties::resize(numverts);
 374   }
 375
 376   //  From number of vertices and mutable vectors of sources and targets;
 377   //  vectors are returned with unspecified contents but are guaranteed not to
 378   //  share storage with the constructed graph.
 379   compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t,
 380                               std::vector<vertex_descriptor>& sources,
 381                               std::vector<vertex_descriptor>& targets,
 382                               vertices_size_type numverts,
 383                               const GraphProperty& prop = GraphProperty())
 384     : inherited_vertex_properties(numverts), m_property(prop)
 385   {
 386     m_forward.assign_sources_and_targets_global(sources, targets, numverts, boost::typed_identity_property_map<vertices_size_type>());
 387   }
 388
 389   //  From number of vertices and mutable vectors of sources and targets,
 390   //  expressed with global vertex indices; vectors are returned with
 391   //  unspecified contents but are guaranteed not to share storage with the
 392   //  constructed graph.  This constructor should only be used by the
 393   //  distributed CSR graph.
 394   template <typename GlobalToLocal>
 395   compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_global_t,
 396                               std::vector<vertex_descriptor>& sources,
 397                               std::vector<vertex_descriptor>& targets,
 398                               vertices_size_type numlocalverts,
 399                               GlobalToLocal global_to_local,
 400                               const GraphProperty& prop = GraphProperty())
 401     : inherited_vertex_properties(numlocalverts), m_property(prop)
 402   {
 403     m_forward.assign_sources_and_targets_global(sources, targets, numlocalverts, global_to_local);
 404   }
 405
 406   //  From number of vertices and mutable vectors of sources, targets, and edge
 407   //  properties; vectors are returned with unspecified contents but are
 408   //  guaranteed not to share storage with the constructed graph.
 409   compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t,
 410                               std::vector<vertex_descriptor>& sources,
 411                               std::vector<vertex_descriptor>& targets,
 412                               std::vector<typename forward_type::inherited_edge_properties::edge_bundled>& edge_props,
 413                               vertices_size_type numverts,
 414                               const GraphProperty& prop = GraphProperty())
 415     : inherited_vertex_properties(numverts), m_property(prop)
 416   {
 417     m_forward.assign_sources_and_targets_global(sources, targets, edge_props, numverts, boost::typed_identity_property_map<vertices_size_type>());
 418   }
 419
 420   //  From number of vertices and mutable vectors of sources and targets and
 421   //  edge properties, expressed with global vertex indices; vectors are
 422   //  returned with unspecified contents but are guaranteed not to share
 423   //  storage with the constructed graph.  This constructor should only be used
 424   //  by the distributed CSR graph.
 425   template <typename GlobalToLocal>
 426   compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_global_t,
 427                               std::vector<vertex_descriptor>& sources,
 428                               std::vector<vertex_descriptor>& targets,
 429                               std::vector<typename forward_type::inherited_edge_properties::edge_bundled>& edge_props,
 430                               vertices_size_type numlocalverts,
 431                               GlobalToLocal global_to_local,
 432                               const GraphProperty& prop = GraphProperty())
 433     : inherited_vertex_properties(numlocalverts), m_property(prop)
 434   {
 435     m_forward.assign_sources_and_targets_global(sources, targets, edge_props, numlocalverts, global_to_local);
 436   }
 437
 438   //  From number of vertices and single-pass range of unsorted edges.  Data is
 439   //  cached in coordinate form before creating the actual graph.
 440   template<typename InputIterator>
 441   compressed_sparse_row_graph(edges_are_unsorted_t,
 442                               InputIterator edge_begin, InputIterator edge_end,
 443                               vertices_size_type numverts,
 444                               const GraphProperty& prop = GraphProperty())
 445     : inherited_vertex_properties(numverts), m_property(prop)
 446   {
 447     std::vector<vertex_descriptor> sources, targets;
 448     boost::graph::detail::split_into_separate_coords
 449       (edge_begin, edge_end, sources, targets);
 450     m_forward.assign_sources_and_targets_global(sources, targets, numverts, boost::typed_identity_property_map<vertices_size_type>());
 451   }
 452
 453   //  From number of vertices and single-pass range of unsorted edges and
 454   //  single-pass range of edge properties.  Data is cached in coordinate form
 455   //  before creating the actual graph.
 456   template<typename InputIterator, typename EdgePropertyIterator>
 457   compressed_sparse_row_graph(edges_are_unsorted_t,
 458                               InputIterator edge_begin, InputIterator edge_end,
 459                               EdgePropertyIterator ep_iter,
 460                               vertices_size_type numverts,
 461                               const GraphProperty& prop = GraphProperty())
 462     : inherited_vertex_properties(numverts), m_property(prop)
 463   {
 464     std::vector<vertex_descriptor> sources, targets;
 465     boost::graph::detail::split_into_separate_coords
 466       (edge_begin, edge_end, sources, targets);
 467     size_t numedges = sources.size();
 468     std::vector<typename forward_type::inherited_edge_properties::edge_bundled> edge_props(numedges);
 469     for (size_t i = 0; i < numedges; ++i) {
 470       edge_props[i] = *ep_iter++;
 471     }
 472     m_forward.assign_sources_and_targets_global(sources, targets, edge_props, numverts, boost::typed_identity_property_map<vertices_size_type>());
 473   }
 474
 475   //  From number of vertices and single-pass range of unsorted edges.  Data is
 476   //  cached in coordinate form before creating the actual graph.  Edges are
 477   //  filtered and transformed for use in a distributed graph.
 478   template<typename InputIterator, typename GlobalToLocal, typename SourcePred>
 479   compressed_sparse_row_graph(edges_are_unsorted_global_t,
 480                               InputIterator edge_begin, InputIterator edge_end,
 481                               vertices_size_type numlocalverts,
 482                               GlobalToLocal global_to_local,
 483                               const SourcePred& source_pred,
 484                               const GraphProperty& prop = GraphProperty())
 485     : inherited_vertex_properties(numlocalverts), m_property(prop)
 486   {
 487     std::vector<vertex_descriptor> sources, targets;
 488     boost::graph::detail::split_into_separate_coords_filtered
 489       (edge_begin, edge_end, sources, targets, source_pred);
 490     m_forward.assign_sources_and_targets_global(sources, targets, numlocalverts, global_to_local);
 491   }
 492
 493   //  From number of vertices and single-pass range of unsorted edges and
 494   //  single-pass range of edge properties.  Data is cached in coordinate form
 495   //  before creating the actual graph.  Edges are filtered and transformed for
 496   //  use in a distributed graph.
 497   template<typename InputIterator, typename EdgePropertyIterator,
 498            typename GlobalToLocal, typename SourcePred>
 499   compressed_sparse_row_graph(edges_are_unsorted_global_t,
 500                               InputIterator edge_begin, InputIterator edge_end,
 501                               EdgePropertyIterator ep_iter,
 502                               vertices_size_type numlocalverts,
 503                               GlobalToLocal global_to_local,
 504                               const SourcePred& source_pred,
 505                               const GraphProperty& prop = GraphProperty())
 506     : inherited_vertex_properties(numlocalverts), m_property(prop)
 507   {
 508     std::vector<vertex_descriptor> sources, targets;
 509     std::vector<edge_bundled> edge_props;
 510     boost::graph::detail::split_into_separate_coords_filtered
 511       (edge_begin, edge_end, ep_iter, sources, targets, edge_props, source_pred);
 512     m_forward.assign_sources_and_targets_global(sources, targets, edge_props, numlocalverts, global_to_local);
 513   }
 514
 515
 516   //   Requires IncidenceGraph and a vertex index map
 517   template<typename Graph, typename VertexIndexMap>
 518   compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi,
 519                               vertices_size_type numverts,
 520                               edges_size_type numedges)
 521     : m_property()
 522   {
 523     assign(g, vi, numverts, numedges);
 524     inherited_vertex_properties::resize(numverts);
 525   }
 526
 527   //   Requires VertexListGraph and EdgeListGraph
 528   template<typename Graph, typename VertexIndexMap>
 529   compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi)
 530     : m_property()
 531   {
 532     typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
 533     if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
 534       numedges *= 2; // Double each edge (actual doubling done by out_edges function)
 535     }
 536     vertices_size_type numverts = num_vertices(g);
 537     assign(g, vi, numverts, numedges);
 538     inherited_vertex_properties::resize(numverts);
 539   }
 540
 541   // Requires vertex index map plus requirements of previous constructor
 542   template<typename Graph>
 543   explicit compressed_sparse_row_graph(const Graph& g)
 544     : m_property()
 545   {
 546     typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
 547     if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
 548       numedges *= 2; // Double each edge (actual doubling done by out_edges function)
 549     }
 550     assign(g, get(vertex_index, g), num_vertices(g), numedges);
 551   }
 552
 553   // From any graph (slow and uses a lot of memory)
 554   //   Requires IncidenceGraph and a vertex index map
 555   //   Internal helper function
 556   //   Note that numedges must be doubled for undirected source graphs
 557   template<typename Graph, typename VertexIndexMap>
 558   void
 559   assign(const Graph& g, const VertexIndexMap& vi,
 560          vertices_size_type numverts, edges_size_type numedges)
 561   {
 562     m_forward.assign(g, vi, numverts, numedges);
 563     inherited_vertex_properties::resize(numverts);
 564   }
 565
 566   // Requires the above, plus VertexListGraph and EdgeListGraph
 567   template<typename Graph, typename VertexIndexMap>
 568   void assign(const Graph& g, const VertexIndexMap& vi)
 569   {
 570     typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
 571     if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
 572       numedges *= 2; // Double each edge (actual doubling done by out_edges function)
 573     }
 574     vertices_size_type numverts = num_vertices(g);
 575     m_forward.assign(g, vi, numverts, numedges);
 576     inherited_vertex_properties::resize(numverts);
 577   }
 578
 579   // Requires the above, plus a vertex_index map.
 580   template<typename Graph>
 581   void assign(const Graph& g)
 582   {
 583     typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
 584     if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
 585       numedges *= 2; // Double each edge (actual doubling done by out_edges function)
 586     }
 587     vertices_size_type numverts = num_vertices(g);
 588     m_forward.assign(g, get(vertex_index, g), numverts, numedges);
 589     inherited_vertex_properties::resize(numverts);
 590   }
 591
 592   // Add edges from a sorted (smallest sources first) range of pairs and edge
 593   // properties
 594   template <typename BidirectionalIteratorOrig, typename EPIterOrig,
 595             typename GlobalToLocal>
 596   void
 597   add_edges_sorted_internal(
 598       BidirectionalIteratorOrig first_sorted,
 599       BidirectionalIteratorOrig last_sorted,
 600       EPIterOrig ep_iter_sorted,
 601       const GlobalToLocal& global_to_local) {
 602     m_forward.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted, global_to_local);
 603   }
 604
 605   template <typename BidirectionalIteratorOrig, typename EPIterOrig>
 606   void
 607   add_edges_sorted_internal(
 608       BidirectionalIteratorOrig first_sorted,
 609       BidirectionalIteratorOrig last_sorted,
 610       EPIterOrig ep_iter_sorted)  {
 611     m_forward.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted, typed_identity_property_map<vertices_size_type>());
 612   }
 613
 614   // Add edges from a sorted (smallest sources first) range of pairs
 615   template <typename BidirectionalIteratorOrig>
 616   void
 617   add_edges_sorted_internal(
 618       BidirectionalIteratorOrig first_sorted,
 619       BidirectionalIteratorOrig last_sorted) {
 620     m_forward.add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<edge_bundled>());
 621   }
 622
 623   template <typename BidirectionalIteratorOrig, typename GlobalToLocal>
 624   void
 625   add_edges_sorted_internal_global(
 626       BidirectionalIteratorOrig first_sorted,
 627       BidirectionalIteratorOrig last_sorted,
 628       const GlobalToLocal& global_to_local) {
 629     m_forward.add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<edge_bundled>(), global_to_local);
 630   }
 631
 632   template <typename BidirectionalIteratorOrig, typename EPIterOrig,
 633             typename GlobalToLocal>
 634   void
 635   add_edges_sorted_internal_global(
 636       BidirectionalIteratorOrig first_sorted,
 637       BidirectionalIteratorOrig last_sorted,
 638       EPIterOrig ep_iter_sorted,
 639       const GlobalToLocal& global_to_local) {
 640     m_forward.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted, global_to_local);
 641   }
 642
 643   // Add edges from a range of (source, target) pairs that are unsorted
 644   template <typename InputIterator, typename GlobalToLocal>
 645   inline void
 646   add_edges_internal(InputIterator first, InputIterator last,
 647                      const GlobalToLocal& global_to_local) {
 648     typedef compressed_sparse_row_graph Graph;
 649     typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t;
 650     typedef std::vector<std::pair<vertex_t, vertex_t> > edge_vector_t;
 651     edge_vector_t new_edges(first, last);
 652     if (new_edges.empty()) return;
 653     std::sort(new_edges.begin(), new_edges.end());
 654     this->add_edges_sorted_internal_global(new_edges.begin(), new_edges.end(), global_to_local);
 655   }
 656
 657   template <typename InputIterator>
 658   inline void
 659   add_edges_internal(InputIterator first, InputIterator last) {
 660     this->add_edges_internal(first, last, typed_identity_property_map<vertices_size_type>());
 661   }
 662
 663   // Add edges from a range of (source, target) pairs and edge properties that
 664   // are unsorted
 665   template <typename InputIterator, typename EPIterator, typename GlobalToLocal>
 666   inline void
 667   add_edges_internal(InputIterator first, InputIterator last,
 668                      EPIterator ep_iter, EPIterator ep_iter_end,
 669                      const GlobalToLocal& global_to_local) {
 670     typedef compressed_sparse_row_graph Graph;
 671     typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t;
 672     typedef std::pair<vertex_t, vertex_t> vertex_pair;
 673     typedef std::vector<
 674               boost::tuple<vertex_pair,
 675                            edge_bundled> >
 676       edge_vector_t;
 677     edge_vector_t new_edges
 678       (boost::make_zip_iterator(boost::make_tuple(first, ep_iter)),
 679        boost::make_zip_iterator(boost::make_tuple(last, ep_iter_end)));
 680     if (new_edges.empty()) return;
 681     std::sort(new_edges.begin(), new_edges.end(),
 682               boost::detail::compare_first<
 683                 std::less<vertex_pair> >());
 684     m_forward.add_edges_sorted_internal
 685       (boost::make_transform_iterator(
 686          new_edges.begin(),
 687          boost::detail::my_tuple_get_class<0, vertex_pair>()),
 688        boost::make_transform_iterator(
 689          new_edges.end(),
 690          boost::detail::my_tuple_get_class<0, vertex_pair>()),
 691        boost::make_transform_iterator(
 692          new_edges.begin(),
 693          boost::detail::my_tuple_get_class
 694            <1, edge_bundled>()),
 695        global_to_local);
 696   }
 697
 698   // Add edges from a range of (source, target) pairs and edge properties that
 699   // are unsorted
 700   template <typename InputIterator, typename EPIterator>
 701   inline void
 702   add_edges_internal(InputIterator first, InputIterator last,
 703                      EPIterator ep_iter, EPIterator ep_iter_end) {
 704     this->add_edges_internal(first, last, ep_iter, ep_iter_end, typed_identity_property_map<vertices_size_type>());
 705   }
 706
 707   using inherited_vertex_properties::operator[];
 708
 709   // Directly access a edge or edge bundle
 710   edge_push_back_type& operator[](const edge_descriptor& v)
 711   { return m_forward.m_edge_properties[get(edge_index, *this, v)]; }
 712
 713   const edge_push_back_type& operator[](const edge_descriptor& v) const
 714   { return m_forward.m_edge_properties[get(edge_index, *this, v)]; }
 715
 716   // Directly access a graph bundle
 717   graph_bundled& operator[](graph_bundle_t)
 718   { return get_property(*this); }
 719
 720   const graph_bundled& operator[](graph_bundle_t) const
 721   { return get_property(*this); }
 722
 723   // private: non-portable, requires friend templates
 724   inherited_vertex_properties&       vertex_properties()       {return *this;}
 725   const inherited_vertex_properties& vertex_properties() const {return *this;}
 726   typename forward_type::inherited_edge_properties&       edge_properties()       { return m_forward; }
 727   const typename forward_type::inherited_edge_properties& edge_properties() const { return m_forward; }
 728
 729   forward_type m_forward;
 730   GraphProperty m_property;
 731 };
 732
 733 template<typename VertexProperty,
 734          typename EdgeProperty,
 735          typename GraphProperty,
 736          typename Vertex,
 737          typename EdgeIndex>
 738 class compressed_sparse_row_graph<bidirectionalS, VertexProperty, EdgeProperty, GraphProperty, Vertex, EdgeIndex>
 739    : public detail::indexed_vertex_properties<BOOST_BIDIR_CSR_GRAPH_TYPE,
 740                                               VertexProperty, Vertex, typed_identity_property_map<Vertex> >
 741 {
 742  public:
 743   typedef detail::indexed_vertex_properties<compressed_sparse_row_graph,
 744                                             VertexProperty, Vertex, typed_identity_property_map<Vertex> >
 745     inherited_vertex_properties;
 746
 747  public:
 748   // For Property Graph
 749   typedef GraphProperty graph_property_type;
 750   typedef typename lookup_one_property<GraphProperty, graph_bundle_t>::type graph_bundled;
 751   // typedef GraphProperty graph_property_type;
 752
 753   typedef detail::compressed_sparse_row_structure<EdgeProperty, Vertex, EdgeIndex> forward_type;
 754   typedef EdgeIndex /* typename boost::mpl::if_c<boost::is_same<EdgeProperty, boost::no_property>, boost::no_property, EdgeIndex> */ backward_edge_property;
 755   typedef detail::compressed_sparse_row_structure<backward_edge_property, Vertex, EdgeIndex> backward_type;
 756
 757  public:
 758   // Concept requirements:
 759   // For Graph
 760   typedef Vertex vertex_descriptor;
 761   typedef detail::csr_edge_descriptor<Vertex, EdgeIndex> edge_descriptor;
 762   typedef bidirectional_tag directed_category;
 763   typedef allow_parallel_edge_tag edge_parallel_category;
 764
 765   class traversal_category: public bidirectional_graph_tag,
 766                             public adjacency_graph_tag,
 767                             public vertex_list_graph_tag,
 768                             public edge_list_graph_tag {};
 769
 770   static vertex_descriptor null_vertex() { return vertex_descriptor(-1); }
 771
 772   // For VertexListGraph
 773   typedef counting_iterator<Vertex> vertex_iterator;
 774   typedef Vertex vertices_size_type;
 775
 776   // For EdgeListGraph
 777   typedef EdgeIndex edges_size_type;
 778
 779   // For IncidenceGraph
 780   typedef detail::csr_out_edge_iterator<compressed_sparse_row_graph> out_edge_iterator;
 781   typedef EdgeIndex degree_size_type;
 782
 783   // For AdjacencyGraph
 784   typedef typename std::vector<Vertex>::const_iterator adjacency_iterator;
 785
 786   // For EdgeListGraph
 787   typedef detail::csr_edge_iterator<compressed_sparse_row_graph> edge_iterator;
 788
 789   // For BidirectionalGraph (not implemented)
 790   typedef detail::csr_in_edge_iterator<compressed_sparse_row_graph> in_edge_iterator;
 791
 792   // For internal use
 793   typedef csr_graph_tag graph_tag;
 794
 795   typedef typename forward_type::inherited_edge_properties::edge_bundled edge_bundled;
 796   typedef typename forward_type::inherited_edge_properties::edge_push_back_type edge_push_back_type;
 797   typedef typename forward_type::inherited_edge_properties::edge_property_type edge_property_type;
 798
 799   // Constructors
 800
 801   // Default constructor: an empty graph.
 802   compressed_sparse_row_graph(): m_property() {}
 803
 804   //  With numverts vertices
 805   compressed_sparse_row_graph(vertices_size_type numverts)
 806     : inherited_vertex_properties(numverts),
 807       m_forward(numverts), m_backward(numverts) {}
 808
 809   private:
 810
 811   void set_up_backward_property_links() {
 812     std::pair<edge_iterator, edge_iterator> e = edges(*this);
 813     m_backward.assign_unsorted_multi_pass_edges
 814       (detail::transpose_edges(
 815          detail::make_edge_to_index_pair_iter
 816            (*this, get(vertex_index, *this), e.first)),
 817        detail::transpose_edges(
 818          detail::make_edge_to_index_pair_iter
 819            (*this, get(vertex_index, *this), e.second)),
 820        boost::counting_iterator<EdgeIndex>(0),
 821        m_forward.m_rowstart.size() - 1,
 822        typed_identity_property_map<Vertex>(),
 823        keep_all());
 824   }
 825
 826   public:
 827
 828   //  From number of vertices and unsorted list of edges
 829   template <typename MultiPassInputIterator>
 830   compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
 831                               MultiPassInputIterator edge_begin,
 832                               MultiPassInputIterator edge_end,
 833                               vertices_size_type numverts,
 834                               const GraphProperty& prop = GraphProperty())
 835     : inherited_vertex_properties(numverts), m_property(prop)
 836   {
 837     m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, numverts, typed_identity_property_map<Vertex>(), keep_all());
 838     set_up_backward_property_links();
 839   }
 840
 841   //  From number of vertices and unsorted list of edges, plus edge properties
 842   template <typename MultiPassInputIterator, typename EdgePropertyIterator>
 843   compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t,
 844                               MultiPassInputIterator edge_begin,
 845                               MultiPassInputIterator edge_end,
 846                               EdgePropertyIterator ep_iter,
 847                               vertices_size_type numverts,
 848                               const GraphProperty& prop = GraphProperty())
 849     : inherited_vertex_properties(numverts), m_forward(), m_property(prop)
 850   {
 851     m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numverts, typed_identity_property_map<Vertex>(), keep_all());
 852     set_up_backward_property_links();
 853   }
 854
 855   //  From number of vertices and unsorted list of edges, with filter and
 856   //  global-to-local map
 857   template <typename MultiPassInputIterator, typename GlobalToLocal, typename SourcePred>
 858   compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,
 859                               MultiPassInputIterator edge_begin,
 860                               MultiPassInputIterator edge_end,
 861                               vertices_size_type numlocalverts,
 862                               const GlobalToLocal& global_to_local,
 863                               const SourcePred& source_pred,
 864                               const GraphProperty& prop = GraphProperty())
 865     : inherited_vertex_properties(numlocalverts), m_forward(), m_property(prop)
 866   {
 867     m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, numlocalverts, global_to_local, source_pred);
 868     set_up_backward_property_links();
 869   }
 870
 871   //  From number of vertices and unsorted list of edges, plus edge properties,
 872   //  with filter and global-to-local map
 873   template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename SourcePred>
 874   compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t,
 875                               MultiPassInputIterator edge_begin,
 876                               MultiPassInputIterator edge_end,
 877                               EdgePropertyIterator ep_iter,
 878                               vertices_size_type numlocalverts,
 879                               const GlobalToLocal& global_to_local,
 880                               const SourcePred& source_pred,
 881                               const GraphProperty& prop = GraphProperty())
 882     : inherited_vertex_properties(numlocalverts), m_forward(), m_property(prop)
 883   {
 884     m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numlocalverts, global_to_local, source_pred);
 885     set_up_backward_property_links();
 886   }
 887
 888   //   Requires IncidenceGraph and a vertex index map
 889   template<typename Graph, typename VertexIndexMap>
 890   compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi,
 891                               vertices_size_type numverts,
 892                               edges_size_type numedges)
 893     : m_property()
 894   {
 895     assign(g, vi, numverts, numedges);
 896     inherited_vertex_properties::resize(numverts);
 897   }
 898
 899   //   Requires VertexListGraph and EdgeListGraph
 900   template<typename Graph, typename VertexIndexMap>
 901   compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi)
 902     : m_property()
 903   {
 904     typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
 905     if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
 906       numedges *= 2; // Double each edge (actual doubling done by out_edges function)
 907     }
 908     vertices_size_type numverts = num_vertices(g);
 909     assign(g, vi, numverts, numedges);
 910     inherited_vertex_properties::resize(numverts);
 911   }
 912
 913   // Requires vertex index map plus requirements of previous constructor
 914   template<typename Graph>
 915   explicit compressed_sparse_row_graph(const Graph& g)
 916     : m_property()
 917   {
 918     typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
 919     if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
 920       numedges *= 2; // Double each edge (actual doubling done by out_edges function)
 921     }
 922     assign(g, get(vertex_index, g), num_vertices(g), numedges);
 923   }
 924
 925   // From any graph (slow and uses a lot of memory)
 926   //   Requires IncidenceGraph and a vertex index map
 927   //   Internal helper function
 928   //   Note that numedges must be doubled for undirected source graphs
 929   template<typename Graph, typename VertexIndexMap>
 930   void
 931   assign(const Graph& g, const VertexIndexMap& vi,
 932          vertices_size_type numverts, edges_size_type numedges)
 933   {
 934     m_forward.assign(g, vi, numverts, numedges);
 935     inherited_vertex_properties::resize(numverts);
 936     set_up_backward_property_links();
 937   }
 938
 939   // Requires the above, plus VertexListGraph and EdgeListGraph
 940   template<typename Graph, typename VertexIndexMap>
 941   void assign(const Graph& g, const VertexIndexMap& vi)
 942   {
 943     typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
 944     if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
 945       numedges *= 2; // Double each edge (actual doubling done by out_edges function)
 946     }
 947     vertices_size_type numverts = num_vertices(g);
 948     m_forward.assign(g, vi, numverts, numedges);
 949     inherited_vertex_properties::resize(numverts);
 950     set_up_backward_property_links();
 951   }
 952
 953   // Requires the above, plus a vertex_index map.
 954   template<typename Graph>
 955   void assign(const Graph& g)
 956   {
 957     typename graph_traits<Graph>::edges_size_type numedges = num_edges(g);
 958     if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) {
 959       numedges *= 2; // Double each edge (actual doubling done by out_edges function)
 960     }
 961     vertices_size_type numverts = num_vertices(g);
 962     m_forward.assign(g, get(vertex_index, g), numverts, numedges);
 963     inherited_vertex_properties::resize(numverts);
 964     set_up_backward_property_links();
 965   }
 966
 967   using inherited_vertex_properties::operator[];
 968
 969   // Directly access a edge or edge bundle
 970   edge_push_back_type& operator[](const edge_descriptor& v)
 971   { return m_forward.m_edge_properties[get(edge_index, *this, v)]; }
 972
 973   const edge_push_back_type& operator[](const edge_descriptor& v) const
 974   { return m_forward.m_edge_properties[get(edge_index, *this, v)]; }
 975
 976   // private: non-portable, requires friend templates
 977   inherited_vertex_properties&       vertex_properties()       {return *this;}
 978   const inherited_vertex_properties& vertex_properties() const {return *this;}
 979   typename forward_type::inherited_edge_properties&       edge_properties()       { return m_forward; }
 980   const typename forward_type::inherited_edge_properties& edge_properties() const { return m_forward; }
 981
 982   forward_type m_forward;
 983   backward_type m_backward;
 984   GraphProperty m_property;
 985 };
 986
 987 // Construction functions
 988 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
 989 inline Vertex
 990 add_vertex(BOOST_CSR_GRAPH_TYPE& g) {
 991   add_vertex(g, typename BOOST_CSR_GRAPH_TYPE::vertex_bundled());
 992 }
 993
 994 template<BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS>
 995 inline Vertex
 996 add_vertex(BOOST_DIR_CSR_GRAPH_TYPE& g,
 997            typename BOOST_DIR_CSR_GRAPH_TYPE::vertex_bundled const& p) {
 998   Vertex old_num_verts_plus_one = g.m_forward.m_rowstart.size();
 999   g.m_forward.m_rowstart.push_back(g.m_forward.m_rowstart.back());
1000   g.vertex_properties().push_back(p);
1001   return old_num_verts_plus_one - 1;
1002 }
1003
1004 template<BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS>
1005 inline Vertex
1006 add_vertex(BOOST_BIDIR_CSR_GRAPH_TYPE& g,
1007            typename BOOST_BIDIR_CSR_GRAPH_TYPE::vertex_bundled const& p) {
1008   Vertex old_num_verts_plus_one = g.m_forward.m_rowstart.size();
1009   g.m_forward.m_rowstart.push_back(g.m_forward.m_rowstart.back());
1010   g.m_backward.m_rowstart.push_back(g.m_backward.m_rowstart.back());
1011   g.vertex_properties().push_back(p);
1012   return old_num_verts_plus_one - 1;
1013 }
1014
1015 template<BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS>
1016 inline Vertex
1017 add_vertices(typename BOOST_DIR_CSR_GRAPH_TYPE::vertices_size_type count, BOOST_DIR_CSR_GRAPH_TYPE& g) {
1018   Vertex old_num_verts_plus_one = g.m_forward.m_rowstart.size();
1019   EdgeIndex numedges = g.m_forward.m_rowstart.back();
1020   g.m_forward.m_rowstart.resize(old_num_verts_plus_one + count, numedges);
1021   g.vertex_properties().resize(num_vertices(g));
1022   return old_num_verts_plus_one - 1;
1023 }
1024
1025   // Add edges from a sorted (smallest sources first) range of pairs and edge
1026   // properties
1027   template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig,
1028             typename EPIterOrig>
1029   void
1030   add_edges_sorted(
1031       BidirectionalIteratorOrig first_sorted,
1032       BidirectionalIteratorOrig last_sorted,
1033       EPIterOrig ep_iter_sorted,
1034       BOOST_DIR_CSR_GRAPH_TYPE& g) {
1035     g.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted);
1036   }
1037
1038   // Add edges from a sorted (smallest sources first) range of pairs
1039   template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig>
1040   void
1041   add_edges_sorted(
1042       BidirectionalIteratorOrig first_sorted,
1043       BidirectionalIteratorOrig last_sorted,
1044       BOOST_DIR_CSR_GRAPH_TYPE& g) {
1045     g.add_edges_sorted_internal(first_sorted, last_sorted);
1046   }
1047
1048   template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig,
1049             typename EPIterOrig, typename GlobalToLocal>
1050   void
1051   add_edges_sorted_global(
1052       BidirectionalIteratorOrig first_sorted,
1053       BidirectionalIteratorOrig last_sorted,
1054       EPIterOrig ep_iter_sorted,
1055       const GlobalToLocal& global_to_local,
1056       BOOST_DIR_CSR_GRAPH_TYPE& g) {
1057     g.add_edges_sorted_internal_global(first_sorted, last_sorted, ep_iter_sorted,
1058                                        global_to_local);
1059   }
1060
1061   // Add edges from a sorted (smallest sources first) range of pairs
1062   template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig,
1063             typename GlobalToLocal>
1064   void
1065   add_edges_sorted_global(
1066       BidirectionalIteratorOrig first_sorted,
1067       BidirectionalIteratorOrig last_sorted,
1068       const GlobalToLocal& global_to_local,
1069       BOOST_DIR_CSR_GRAPH_TYPE& g) {
1070     g.add_edges_sorted_internal_global(first_sorted, last_sorted, global_to_local);
1071   }
1072
1073   // Add edges from a range of (source, target) pairs that are unsorted
1074   template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator,
1075             typename GlobalToLocal>
1076   inline void
1077   add_edges_global(InputIterator first, InputIterator last,
1078                    const GlobalToLocal& global_to_local, BOOST_DIR_CSR_GRAPH_TYPE& g) {
1079     g.add_edges_internal(first, last, global_to_local);
1080   }
1081
1082   // Add edges from a range of (source, target) pairs that are unsorted
1083   template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator>
1084   inline void
1085   add_edges(InputIterator first, InputIterator last, BOOST_DIR_CSR_GRAPH_TYPE& g) {
1086     g.add_edges_internal(first, last);
1087   }
1088
1089   // Add edges from a range of (source, target) pairs and edge properties that
1090   // are unsorted
1091   template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS,
1092             typename InputIterator, typename EPIterator>
1093   inline void
1094   add_edges(InputIterator first, InputIterator last,
1095             EPIterator ep_iter, EPIterator ep_iter_end,
1096             BOOST_DIR_CSR_GRAPH_TYPE& g) {
1097     g.add_edges_internal(first, last, ep_iter, ep_iter_end);
1098   }
1099
1100   template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS,
1101             typename InputIterator, typename EPIterator, typename GlobalToLocal>
1102   inline void
1103   add_edges_global(InputIterator first, InputIterator last,
1104             EPIterator ep_iter, EPIterator ep_iter_end,
1105             const GlobalToLocal& global_to_local,
1106             BOOST_DIR_CSR_GRAPH_TYPE& g) {
1107     g.add_edges_internal(first, last, ep_iter, ep_iter_end, global_to_local);
1108   }
1109
1110 // From VertexListGraph
1111 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1112 inline Vertex
1113 num_vertices(const BOOST_CSR_GRAPH_TYPE& g) {
1114   return g.m_forward.m_rowstart.size() - 1;
1115 }
1116
1117 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1118 std::pair<counting_iterator<Vertex>, counting_iterator<Vertex> >
1119 inline vertices(const BOOST_CSR_GRAPH_TYPE& g) {
1120   return std::make_pair(counting_iterator<Vertex>(0),
1121                         counting_iterator<Vertex>(num_vertices(g)));
1122 }
1123
1124 // From IncidenceGraph
1125 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1126 inline Vertex
1127 source(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e,
1128        const BOOST_CSR_GRAPH_TYPE&)
1129 {
1130   return e.src;
1131 }
1132
1133 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1134 inline Vertex
1135 target(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e,
1136        const BOOST_CSR_GRAPH_TYPE& g)
1137 {
1138   return g.m_forward.m_column[e.idx];
1139 }
1140
1141 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1142 inline std::pair<typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator,
1143                  typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator>
1144 out_edges(Vertex v, const BOOST_CSR_GRAPH_TYPE& g)
1145 {
1146   typedef typename BOOST_CSR_GRAPH_TYPE::edge_descriptor ed;
1147   typedef typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator it;
1148   EdgeIndex v_row_start = g.m_forward.m_rowstart[v];
1149   EdgeIndex next_row_start = g.m_forward.m_rowstart[v + 1];
1150   return std::make_pair(it(ed(v, v_row_start)),
1151                         it(ed(v, next_row_start)));
1152 }
1153
1154 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1155 inline EdgeIndex
1156 out_degree(Vertex v, const BOOST_CSR_GRAPH_TYPE& g)
1157 {
1158   EdgeIndex v_row_start = g.m_forward.m_rowstart[v];
1159   EdgeIndex next_row_start = g.m_forward.m_rowstart[v + 1];
1160   return next_row_start - v_row_start;
1161 }
1162
1163 template<BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS>
1164 inline std::pair<typename BOOST_BIDIR_CSR_GRAPH_TYPE::in_edge_iterator,
1165                  typename BOOST_BIDIR_CSR_GRAPH_TYPE::in_edge_iterator>
1166 in_edges(Vertex v, const BOOST_BIDIR_CSR_GRAPH_TYPE& g)
1167 {
1168   typedef typename BOOST_BIDIR_CSR_GRAPH_TYPE::in_edge_iterator it;
1169   EdgeIndex v_row_start = g.m_backward.m_rowstart[v];
1170   EdgeIndex next_row_start = g.m_backward.m_rowstart[v + 1];
1171   return std::make_pair(it(g, v_row_start),
1172                         it(g, next_row_start));
1173 }
1174
1175 template<BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS>
1176 inline EdgeIndex
1177 in_degree(Vertex v, const BOOST_BIDIR_CSR_GRAPH_TYPE& g)
1178 {
1179   EdgeIndex v_row_start = g.m_backward.m_rowstart[v];
1180   EdgeIndex next_row_start = g.m_backward.m_rowstart[v + 1];
1181   return next_row_start - v_row_start;
1182 }
1183
1184 // From AdjacencyGraph
1185 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1186 inline std::pair<typename BOOST_CSR_GRAPH_TYPE::adjacency_iterator,
1187                  typename BOOST_CSR_GRAPH_TYPE::adjacency_iterator>
1188 adjacent_vertices(Vertex v, const BOOST_CSR_GRAPH_TYPE& g)
1189 {
1190   EdgeIndex v_row_start = g.m_forward.m_rowstart[v];
1191   EdgeIndex next_row_start = g.m_forward.m_rowstart[v + 1];
1192   return std::make_pair(g.m_forward.m_column.begin() + v_row_start,
1193                         g.m_forward.m_column.begin() + next_row_start);
1194 }
1195
1196 // Extra, common functions
1197 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1198 inline typename graph_traits<BOOST_CSR_GRAPH_TYPE>::vertex_descriptor
1199 vertex(typename graph_traits<BOOST_CSR_GRAPH_TYPE>::vertex_descriptor i,
1200        const BOOST_CSR_GRAPH_TYPE&)
1201 {
1202   return i;
1203 }
1204
1205 // edge() can be provided in linear time for the new interface
1206
1207 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1208 inline std::pair<typename BOOST_CSR_GRAPH_TYPE::edge_descriptor, bool>
1209 edge(Vertex i, Vertex j, const BOOST_CSR_GRAPH_TYPE& g)
1210 {
1211   typedef typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator out_edge_iter;
1212   std::pair<out_edge_iter, out_edge_iter> range = out_edges(i, g);
1213   for (; range.first != range.second; ++range.first) {
1214     if (target(*range.first, g) == j)
1215       return std::make_pair(*range.first, true);
1216   }
1217   return std::make_pair(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(),
1218                         false);
1219 }
1220
1221 // Find an edge given its index in the graph
1222 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1223 inline typename BOOST_CSR_GRAPH_TYPE::edge_descriptor
1224 edge_from_index(EdgeIndex idx, const BOOST_CSR_GRAPH_TYPE& g)
1225 {
1226   typedef typename std::vector<EdgeIndex>::const_iterator row_start_iter;
1227   BOOST_ASSERT (idx < num_edges(g));
1228   row_start_iter src_plus_1 =
1229     std::upper_bound(g.m_forward.m_rowstart.begin(),
1230                      g.m_forward.m_rowstart.end(),
1231                      idx);
1232     // Get last source whose rowstart is at most idx
1233     // upper_bound returns this position plus 1
1234   Vertex src = (src_plus_1 - g.m_forward.m_rowstart.begin()) - 1;
1235   return typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(src, idx);
1236 }
1237
1238 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1239 inline EdgeIndex
1240 num_edges(const BOOST_CSR_GRAPH_TYPE& g)
1241 {
1242   return g.m_forward.m_column.size();
1243 }
1244
1245 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1246 std::pair<typename BOOST_CSR_GRAPH_TYPE::edge_iterator,
1247           typename BOOST_CSR_GRAPH_TYPE::edge_iterator>
1248 edges(const BOOST_CSR_GRAPH_TYPE& g)
1249 {
1250   typedef typename BOOST_CSR_GRAPH_TYPE::edge_iterator ei;
1251   typedef typename BOOST_CSR_GRAPH_TYPE::edge_descriptor edgedesc;
1252   if (g.m_forward.m_rowstart.size() == 1 || g.m_forward.m_column.empty()) {
1253     return std::make_pair(ei(), ei());
1254   } else {
1255     // Find the first vertex that has outgoing edges
1256     Vertex src = 0;
1257     while (g.m_forward.m_rowstart[src + 1] == 0) ++src;
1258     return std::make_pair(ei(g, edgedesc(src, 0), g.m_forward.m_rowstart[src + 1]),
1259                           ei(g, edgedesc(num_vertices(g), g.m_forward.m_column.size()), 0));
1260   }
1261 }
1262
1263 // For Property Graph
1264
1265 // Graph properties
1266 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, class Tag, class Value>
1267 inline void
1268 set_property(BOOST_CSR_GRAPH_TYPE& g, Tag tag, const Value& value)
1269 {
1270   get_property_value(g.m_property, tag) = value;
1271 }
1272
1273 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, class Tag>
1274 inline
1275 typename graph_property<BOOST_CSR_GRAPH_TYPE, Tag>::type&
1276 get_property(BOOST_CSR_GRAPH_TYPE& g, Tag tag)
1277 {
1278   return get_property_value(g.m_property, tag);
1279 }
1280
1281 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, class Tag>
1282 inline
1283 const
1284 typename graph_property<BOOST_CSR_GRAPH_TYPE, Tag>::type&
1285 get_property(const BOOST_CSR_GRAPH_TYPE& g, Tag tag)
1286 {
1287   return get_property_value(g.m_property, tag);
1288 }
1289
1290 template <typename G, typename Tag, typename Kind>
1291 struct csr_property_map_helper {};
1292 // Kind == void for invalid property tags, so we can use that to SFINAE out
1293
1294 template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1295 struct csr_property_map_helper<BOOST_CSR_GRAPH_TYPE, Tag, vertex_property_tag> {
1296   typedef vertex_all_t all_tag;
1297   typedef typename property_traits<typename property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t>::type>::key_type key_type;
1298   typedef VertexProperty plist_type;
1299   typedef typename property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t>::type all_type;
1300   typedef typename property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t>::const_type all_const_type;
1301   typedef transform_value_property_map<detail::lookup_one_property_f<plist_type, Tag>, all_type> type;
1302   typedef transform_value_property_map<detail::lookup_one_property_f<const plist_type, Tag>, all_const_type> const_type;
1303 };
1304
1305 template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1306 struct csr_property_map_helper<BOOST_CSR_GRAPH_TYPE, Tag, edge_property_tag> {
1307   typedef edge_all_t all_tag;
1308   typedef typename property_traits<typename property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t>::type>::key_type key_type;
1309   typedef EdgeProperty plist_type;
1310   typedef typename property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t>::type all_type;
1311   typedef typename property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t>::const_type all_const_type;
1312   typedef transform_value_property_map<detail::lookup_one_property_f<plist_type, Tag>, all_type> type;
1313   typedef transform_value_property_map<detail::lookup_one_property_f<const plist_type, Tag>, all_const_type> const_type;
1314 };
1315
1316 template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1317 struct csr_property_map_helper<BOOST_CSR_GRAPH_TYPE, Tag, graph_property_tag> {
1318   typedef graph_all_t all_tag;
1319   typedef BOOST_CSR_GRAPH_TYPE* key_type;
1320   typedef GraphProperty plist_type;
1321   typedef typename property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>::type all_type;
1322   typedef typename property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>::const_type all_const_type;
1323   typedef transform_value_property_map<detail::lookup_one_property_f<plist_type, Tag>, all_type> type;
1324   typedef transform_value_property_map<detail::lookup_one_property_f<const plist_type, Tag>, all_const_type> const_type;
1325 };
1326
1327 // disable_if isn't truly necessary but required to avoid ambiguity with specializations below
1328 template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1329 struct property_map<BOOST_CSR_GRAPH_TYPE, Tag, typename disable_if<detail::is_distributed_selector<Vertex> >::type>:
1330   csr_property_map_helper<
1331     BOOST_CSR_GRAPH_TYPE,
1332     Tag,
1333     typename detail::property_kind_from_graph<BOOST_CSR_GRAPH_TYPE, Tag>
1334                ::type> {};
1335
1336 template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1337 typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::type
1338 get(Tag tag, BOOST_CSR_GRAPH_TYPE& g) {
1339   return typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::type(tag, get(typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::all_tag(), g));
1340 }
1341
1342 template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1343 typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::const_type
1344 get(Tag tag, const BOOST_CSR_GRAPH_TYPE& g) {
1345   return typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::const_type(tag, get(typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::all_tag(), g));
1346 }
1347
1348 template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1349 typename property_traits<typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::type>::reference
1350 get(Tag tag, BOOST_CSR_GRAPH_TYPE& g, typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::key_type k) {
1351   typedef typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::all_tag all_tag;
1352   typedef typename property_map<BOOST_CSR_GRAPH_TYPE, all_tag>::type outer_pm;
1353   return lookup_one_property<typename property_traits<outer_pm>::value_type, Tag>::lookup(get(all_tag(), g, k), tag);
1354 }
1355
1356 template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1357 typename property_traits<typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::const_type>::reference
1358 get(Tag tag, const BOOST_CSR_GRAPH_TYPE& g, typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::key_type k) {
1359   typedef typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::all_tag all_tag;
1360   typedef typename property_map<BOOST_CSR_GRAPH_TYPE, all_tag>::const_type outer_pm;
1361   return lookup_one_property<const typename property_traits<outer_pm>::value_type, Tag>::lookup(get(all_tag(), g, k), tag);
1362 }
1363
1364 template <BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag>
1365 void
1366 put(Tag tag,
1367     BOOST_CSR_GRAPH_TYPE& g,
1368     typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::key_type k,
1369     typename lookup_one_property<typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::plist_type, Tag>::type val) {
1370   typedef typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::all_tag all_tag;
1371   lookup_one_property<typename property_map<BOOST_CSR_GRAPH_TYPE, Tag>::plist_type, Tag>::lookup(get(all_tag(), g, k), tag) = val;
1372 }
1373
1374 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1375 struct property_map<BOOST_CSR_GRAPH_TYPE, vertex_index_t, typename disable_if<detail::is_distributed_selector<Vertex> >::type>
1376 {
1377   typedef typed_identity_property_map<Vertex> type;
1378   typedef type const_type;
1379 };
1380
1381 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1382 struct property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t, typename disable_if<detail::is_distributed_selector<Vertex> >::type>
1383 {
1384   typedef detail::csr_edge_index_map<Vertex, EdgeIndex> type;
1385   typedef type const_type;
1386 };
1387
1388 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1389 struct property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t, typename disable_if<detail::is_distributed_selector<Vertex> >::type>
1390 {
1391   typedef typename BOOST_CSR_GRAPH_TYPE::inherited_vertex_properties::vertex_map_type type;
1392   typedef typename BOOST_CSR_GRAPH_TYPE::inherited_vertex_properties::const_vertex_map_type const_type;
1393 };
1394
1395 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1396 struct property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t, typename disable_if<detail::is_distributed_selector<Vertex> >::type>
1397 {
1398   typedef typename BOOST_CSR_GRAPH_TYPE::forward_type::inherited_edge_properties::edge_map_type type;
1399   typedef typename BOOST_CSR_GRAPH_TYPE::forward_type::inherited_edge_properties::const_edge_map_type const_type;
1400 };
1401
1402 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1403 struct property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t, typename disable_if<detail::is_distributed_selector<Vertex> >::type>
1404 {
1405   typedef boost::ref_property_map<BOOST_CSR_GRAPH_TYPE*, typename BOOST_CSR_GRAPH_TYPE::graph_property_type> type;
1406   typedef boost::ref_property_map<BOOST_CSR_GRAPH_TYPE*, const typename BOOST_CSR_GRAPH_TYPE::graph_property_type> const_type;
1407 };
1408
1409 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1410 inline typed_identity_property_map<Vertex>
1411 get(vertex_index_t, const BOOST_CSR_GRAPH_TYPE&)
1412 {
1413   return typed_identity_property_map<Vertex>();
1414 }
1415
1416 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1417 inline Vertex
1418 get(vertex_index_t,
1419     const BOOST_CSR_GRAPH_TYPE&, Vertex v)
1420 {
1421   return v;
1422 }
1423
1424 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1425 inline typed_identity_property_map<Vertex>
1426 get(vertex_index_t, BOOST_CSR_GRAPH_TYPE&)
1427 {
1428   return typed_identity_property_map<Vertex>();
1429 }
1430
1431 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1432 inline Vertex
1433 get(vertex_index_t,
1434     BOOST_CSR_GRAPH_TYPE&, Vertex v)
1435 {
1436   return v;
1437 }
1438
1439 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1440 inline typename property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t>::const_type
1441 get(edge_index_t, const BOOST_CSR_GRAPH_TYPE&)
1442 {
1443   typedef typename property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t>::const_type
1444     result_type;
1445   return result_type();
1446 }
1447
1448 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1449 inline EdgeIndex
1450 get(edge_index_t, const BOOST_CSR_GRAPH_TYPE&,
1451     typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e)
1452 {
1453   return e.idx;
1454 }
1455
1456 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1457 inline typename property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t>::const_type
1458 get(edge_index_t, BOOST_CSR_GRAPH_TYPE&)
1459 {
1460   typedef typename property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t>::const_type
1461     result_type;
1462   return result_type();
1463 }
1464
1465 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1466 inline EdgeIndex
1467 get(edge_index_t, BOOST_CSR_GRAPH_TYPE&,
1468     typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e)
1469 {
1470   return e.idx;
1471 }
1472
1473 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1474 inline typename property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t>::type
1475 get(vertex_all_t, BOOST_CSR_GRAPH_TYPE& g)
1476 {
1477   return g.get_vertex_bundle(get(vertex_index, g));
1478 }
1479
1480 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1481 inline typename property_map<BOOST_CSR_GRAPH_TYPE, vertex_all_t>::const_type
1482 get(vertex_all_t, const BOOST_CSR_GRAPH_TYPE& g)
1483 {
1484   return g.get_vertex_bundle(get(vertex_index, g));
1485 }
1486
1487 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1488 inline VertexProperty&
1489 get(vertex_all_t,
1490     BOOST_CSR_GRAPH_TYPE& g, Vertex v)
1491 {
1492   return get(vertex_all, g)[v];
1493 }
1494
1495 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1496 inline const VertexProperty&
1497 get(vertex_all_t,
1498     const BOOST_CSR_GRAPH_TYPE& g, Vertex v)
1499 {
1500   return get(vertex_all, g)[v];
1501 }
1502
1503 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1504 inline void
1505 put(vertex_all_t,
1506     BOOST_CSR_GRAPH_TYPE& g,
1507     Vertex v,
1508     const VertexProperty& val)
1509 {
1510   put(get(vertex_all, g), v, val);
1511 }
1512
1513 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1514 inline typename property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t>::type
1515 get(edge_all_t, BOOST_CSR_GRAPH_TYPE& g)
1516 {
1517   return g.m_forward.get_edge_bundle(get(edge_index, g));
1518 }
1519
1520 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1521 inline typename property_map<BOOST_CSR_GRAPH_TYPE, edge_all_t>::const_type
1522 get(edge_all_t, const BOOST_CSR_GRAPH_TYPE& g)
1523 {
1524   return g.m_forward.get_edge_bundle(get(edge_index, g));
1525 }
1526
1527 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1528 inline EdgeProperty&
1529 get(edge_all_t,
1530     BOOST_CSR_GRAPH_TYPE& g,
1531     const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor& e)
1532 {
1533   return get(edge_all, g)[e];
1534 }
1535
1536 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1537 inline const EdgeProperty&
1538 get(edge_all_t,
1539     const BOOST_CSR_GRAPH_TYPE& g,
1540     const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor& e)
1541 {
1542   return get(edge_all, g)[e];
1543 }
1544
1545 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1546 inline void
1547 put(edge_all_t,
1548     BOOST_CSR_GRAPH_TYPE& g,
1549     const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor& e,
1550     const EdgeProperty& val)
1551 {
1552   put(get(edge_all, g), e, val);
1553 }
1554
1555 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1556 inline typename property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>::type
1557 get(graph_all_t, BOOST_CSR_GRAPH_TYPE& g)
1558 {
1559   return typename property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>::type(g.m_property);
1560 }
1561
1562 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1563 inline typename property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>::const_type
1564 get(graph_all_t, const BOOST_CSR_GRAPH_TYPE& g)
1565 {
1566   return typename property_map<BOOST_CSR_GRAPH_TYPE, graph_all_t>::const_type(g.m_property);
1567 }
1568
1569 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1570 inline GraphProperty&
1571 get(graph_all_t,
1572     BOOST_CSR_GRAPH_TYPE& g,
1573     BOOST_CSR_GRAPH_TYPE*)
1574 {
1575   return g.m_property;
1576 }
1577
1578 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1579 inline const GraphProperty&
1580 get(graph_all_t,
1581     const BOOST_CSR_GRAPH_TYPE& g,
1582     BOOST_CSR_GRAPH_TYPE*)
1583 {
1584   return g.m_property;
1585 }
1586
1587 template<BOOST_CSR_GRAPH_TEMPLATE_PARMS>
1588 inline void
1589 put(graph_all_t,
1590     BOOST_CSR_GRAPH_TYPE& g,
1591     BOOST_CSR_GRAPH_TYPE*,
1592     const GraphProperty& val)
1593 {
1594   g.m_property = val;
1595 }
1596
1597 #undef BOOST_CSR_GRAPH_TYPE
1598 #undef BOOST_CSR_GRAPH_TEMPLATE_PARMS
1599 #undef BOOST_DIR_CSR_GRAPH_TYPE
1600 #undef BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS
1601 #undef BOOST_BIDIR_CSR_GRAPH_TYPE
1602 #undef BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS
1603
1604 } // end namespace boost
1605
1606 #endif // BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP