| // Copyright 2005-2009 The Trustees of Indiana University. |
| |
| // Distributed under the Boost Software License, Version 1.0. |
| // (See accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| |
| // Authors: Jeremiah Willcock |
| // Douglas Gregor |
| // Andrew Lumsdaine |
| |
| // Compressed sparse row graph type |
| |
| #ifndef BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP |
| #define BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP |
| |
| #include <vector> |
| #include <utility> |
| #include <algorithm> |
| #include <climits> |
| #include <boost/assert.hpp> |
| #include <iterator> |
| #if 0 |
| #include <iostream> // For some debugging code below |
| #endif |
| #include <boost/graph/graph_traits.hpp> |
| #include <boost/graph/properties.hpp> |
| #include <boost/graph/filtered_graph.hpp> // For keep_all |
| #include <boost/graph/detail/indexed_properties.hpp> |
| #include <boost/graph/detail/compressed_sparse_row_struct.hpp> |
| #include <boost/graph/iteration_macros.hpp> |
| #include <boost/iterator/counting_iterator.hpp> |
| #include <boost/iterator/reverse_iterator.hpp> |
| #include <boost/iterator/zip_iterator.hpp> |
| #include <boost/iterator/transform_iterator.hpp> |
| #include <boost/tuple/tuple.hpp> |
| #include <boost/property_map/property_map.hpp> |
| #include <boost/integer.hpp> |
| #include <boost/iterator/iterator_facade.hpp> |
| #include <boost/mpl/if.hpp> |
| #include <boost/graph/graph_selectors.hpp> |
| #include <boost/graph/properties.hpp> |
| #include <boost/static_assert.hpp> |
| #include <boost/functional/hash.hpp> |
| #include <boost/utility.hpp> |
| |
| #ifdef BOOST_GRAPH_NO_BUNDLED_PROPERTIES |
| # error The Compressed Sparse Row graph only supports bundled properties. |
| # error You will need a compiler that conforms better to the C++ standard. |
| #endif |
| |
| namespace boost { |
| |
| // A tag type indicating that the graph in question is a compressed |
| // sparse row graph. This is an internal detail of the BGL. |
| struct csr_graph_tag; |
| |
| // A type (edges_are_sorted_t) and a value (edges_are_sorted) used to indicate |
| // that the edge list passed into the CSR graph is already sorted by source |
| // vertex. |
| enum edges_are_sorted_t {edges_are_sorted}; |
| |
| // A type (edges_are_sorted_global_t) and a value (edges_are_sorted_global) |
| // used to indicate that the edge list passed into the CSR graph is already |
| // sorted by source vertex. |
| enum edges_are_sorted_global_t {edges_are_sorted_global}; |
| |
| // A type (edges_are_unsorted_t) and a value (edges_are_unsorted) used to |
| // indicate that the edge list passed into the CSR graph is not sorted by |
| // source vertex. This version caches the edge information in memory, and thus |
| // requires only a single pass over the input data. |
| enum edges_are_unsorted_t {edges_are_unsorted}; |
| |
| // A type (edges_are_unsorted_multi_pass_t) and a value |
| // (edges_are_unsorted_multi_pass) used to indicate that the edge list passed |
| // into the CSR graph is not sorted by source vertex. This version uses less |
| // memory but requires multi-pass capability on the iterators. |
| enum edges_are_unsorted_multi_pass_t {edges_are_unsorted_multi_pass}; |
| |
| // A type (edges_are_unsorted_multi_pass_global_t) and a value |
| // (edges_are_unsorted_multi_pass_global) used to indicate that the edge list |
| // passed into the CSR graph is not sorted by source vertex. This version uses |
| // less memory but requires multi-pass capability on the iterators. The |
| // global mapping and filtering is done here because it is often faster and it |
| // greatly simplifies handling of edge properties. |
| enum edges_are_unsorted_multi_pass_global_t {edges_are_unsorted_multi_pass_global}; |
| |
| // A type (construct_inplace_from_sources_and_targets_t) and a value |
| // (construct_inplace_from_sources_and_targets) used to indicate that mutable |
| // vectors of sources and targets (and possibly edge properties) are being used |
| // to construct the CSR graph. These vectors are sorted in-place and then the |
| // targets and properties are swapped into the graph data structure. |
| enum construct_inplace_from_sources_and_targets_t {construct_inplace_from_sources_and_targets}; |
| |
| // A type (construct_inplace_from_sources_and_targets_global_t) and a value |
| // (construct_inplace_from_sources_and_targets_global) used to indicate that |
| // mutable vectors of sources and targets (and possibly edge properties) are |
| // being used to construct the CSR graph. These vectors are sorted in-place |
| // and then the targets and properties are swapped into the graph data |
| // structure. It is assumed that global indices (for distributed CSR) are |
| // used, and a map is required to convert those to local indices. This |
| // constructor is intended for internal use by the various CSR graphs |
| // (sequential and distributed). |
| enum construct_inplace_from_sources_and_targets_global_t {construct_inplace_from_sources_and_targets_global}; |
| |
| // A type (edges_are_unsorted_global_t) and a value (edges_are_unsorted_global) |
| // used to indicate that the edge list passed into the CSR graph is not sorted |
| // by source vertex. The data is also stored using global vertex indices, and |
| // must be filtered to choose only local vertices. This constructor caches the |
| // edge information in memory, and thus requires only a single pass over the |
| // input data. This constructor is intended for internal use by the |
| // distributed CSR constructors. |
| enum edges_are_unsorted_global_t {edges_are_unsorted_global}; |
| |
| /**************************************************************************** |
| * Local helper macros to reduce typing and clutter later on. * |
| ****************************************************************************/ |
| #define BOOST_CSR_GRAPH_TEMPLATE_PARMS \ |
| typename Directed, typename VertexProperty, typename EdgeProperty, \ |
| typename GraphProperty, typename Vertex, typename EdgeIndex |
| #define BOOST_CSR_GRAPH_TYPE \ |
| compressed_sparse_row_graph<Directed, VertexProperty, EdgeProperty, \ |
| GraphProperty, Vertex, EdgeIndex> |
| #define BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS \ |
| typename VertexProperty, typename EdgeProperty, \ |
| typename GraphProperty, typename Vertex, typename EdgeIndex |
| #define BOOST_DIR_CSR_GRAPH_TYPE \ |
| compressed_sparse_row_graph<directedS, VertexProperty, EdgeProperty, \ |
| GraphProperty, Vertex, EdgeIndex> |
| #define BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS \ |
| typename VertexProperty, typename EdgeProperty, \ |
| typename GraphProperty, typename Vertex, typename EdgeIndex |
| #define BOOST_BIDIR_CSR_GRAPH_TYPE \ |
| compressed_sparse_row_graph<bidirectionalS, VertexProperty, EdgeProperty, \ |
| GraphProperty, Vertex, EdgeIndex> |
| |
| namespace detail { |
| template <typename T> |
| struct default_construct_iterator: public boost::iterator_facade<default_construct_iterator<T>, T, boost::random_access_traversal_tag, const T&> { |
| typedef boost::iterator_facade<default_construct_iterator<T>, T, std::random_access_iterator_tag, const T&> base_type; |
| T saved_value; |
| const T& dereference() const {return saved_value;} |
| bool equal(default_construct_iterator i) const {return true;} |
| void increment() {} |
| void decrement() {} |
| void advance(typename base_type::difference_type) {} |
| typename base_type::difference_type distance_to(default_construct_iterator) const {return 0;} |
| }; |
| |
| template <typename Less> |
| struct compare_first { |
| Less less; |
| compare_first(Less less = Less()): less(less) {} |
| template <typename Tuple> |
| bool operator()(const Tuple& a, const Tuple& b) const { |
| return less(a.template get<0>(), b.template get<0>()); |
| } |
| }; |
| |
| template <int N, typename Result> |
| struct my_tuple_get_class { |
| typedef const Result& result_type; |
| template <typename Tuple> |
| result_type operator()(const Tuple& t) const { |
| return t.template get<N>(); |
| } |
| }; |
| } |
| |
| /** Compressed sparse row graph. |
| * |
| * Vertex and EdgeIndex should be unsigned integral types and should |
| * specialize numeric_limits. |
| */ |
| template<typename Directed = directedS, |
| typename VertexProperty = no_property, |
| typename EdgeProperty = no_property, |
| typename GraphProperty = no_property, |
| typename Vertex = std::size_t, |
| typename EdgeIndex = Vertex> |
| class compressed_sparse_row_graph; // Not defined |
| |
| template<typename VertexProperty, |
| typename EdgeProperty, |
| typename GraphProperty, |
| typename Vertex, |
| typename EdgeIndex> |
| class compressed_sparse_row_graph<directedS, VertexProperty, EdgeProperty, GraphProperty, Vertex, EdgeIndex> |
| : public detail::indexed_vertex_properties<BOOST_DIR_CSR_GRAPH_TYPE, |
| VertexProperty, Vertex, typed_identity_property_map<Vertex> > |
| { |
| public: |
| typedef detail::indexed_vertex_properties<compressed_sparse_row_graph, |
| VertexProperty, Vertex, typed_identity_property_map<Vertex> > |
| inherited_vertex_properties; |
| |
| public: |
| // For Property Graph |
| typedef typename graph_detail::graph_prop<GraphProperty>::property graph_property_type; |
| typedef typename graph_detail::graph_prop<GraphProperty>::bundle graph_bundled; |
| |
| typedef detail::compressed_sparse_row_structure<EdgeProperty, Vertex, EdgeIndex> forward_type; |
| |
| public: |
| /* At this time, the compressed sparse row graph can only be used to |
| * create directed and bidirectional graphs. In the future, |
| * undirected CSR graphs will also be supported. |
| */ |
| // BOOST_STATIC_ASSERT((is_same<Directed, directedS>::value)); |
| |
| // Concept requirements: |
| // For Graph |
| typedef Vertex vertex_descriptor; |
| typedef detail::csr_edge_descriptor<Vertex, EdgeIndex> edge_descriptor; |
| typedef directed_tag directed_category; |
| typedef allow_parallel_edge_tag edge_parallel_category; |
| |
| class traversal_category: public incidence_graph_tag, |
| public adjacency_graph_tag, |
| public vertex_list_graph_tag, |
| public edge_list_graph_tag {}; |
| |
| static vertex_descriptor null_vertex() { return vertex_descriptor(-1); } |
| |
| // For VertexListGraph |
| typedef counting_iterator<Vertex> vertex_iterator; |
| typedef Vertex vertices_size_type; |
| |
| // For EdgeListGraph |
| typedef EdgeIndex edges_size_type; |
| |
| // For IncidenceGraph |
| typedef detail::csr_out_edge_iterator<compressed_sparse_row_graph> out_edge_iterator; |
| typedef EdgeIndex degree_size_type; |
| |
| // For AdjacencyGraph |
| typedef typename std::vector<Vertex>::const_iterator adjacency_iterator; |
| |
| // For EdgeListGraph |
| typedef detail::csr_edge_iterator<compressed_sparse_row_graph> edge_iterator; |
| |
| // For BidirectionalGraph (not implemented) |
| typedef void in_edge_iterator; |
| |
| // For internal use |
| typedef csr_graph_tag graph_tag; |
| |
| typedef typename forward_type::inherited_edge_properties::edge_bundled edge_bundled; |
| typedef typename forward_type::inherited_edge_properties::edge_push_back_type edge_push_back_type; |
| typedef typename forward_type::inherited_edge_properties::edge_property_type edge_property_type; |
| |
| // Constructors |
| |
| // Default constructor: an empty graph. |
| compressed_sparse_row_graph(): m_property() {} |
| |
| // With numverts vertices |
| compressed_sparse_row_graph(vertices_size_type numverts) |
| : inherited_vertex_properties(numverts), m_forward(numverts) {} |
| |
| // From number of vertices and unsorted list of edges |
| template <typename MultiPassInputIterator> |
| compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t, |
| MultiPassInputIterator edge_begin, |
| MultiPassInputIterator edge_end, |
| vertices_size_type numverts, |
| const GraphProperty& prop = GraphProperty()) |
| : inherited_vertex_properties(numverts), m_property(prop) |
| { |
| m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, numverts, typed_identity_property_map<vertices_size_type>(), keep_all()); |
| } |
| |
| // From number of vertices and unsorted list of edges, plus edge properties |
| template <typename MultiPassInputIterator, typename EdgePropertyIterator> |
| compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t, |
| MultiPassInputIterator edge_begin, |
| MultiPassInputIterator edge_end, |
| EdgePropertyIterator ep_iter, |
| vertices_size_type numverts, |
| const GraphProperty& prop = GraphProperty()) |
| : inherited_vertex_properties(numverts), m_forward(), m_property(prop) |
| { |
| m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numverts, typed_identity_property_map<vertices_size_type>(), keep_all()); |
| } |
| |
| // From number of vertices and unsorted list of edges, with filter and |
| // global-to-local map |
| template <typename MultiPassInputIterator, typename GlobalToLocal, typename SourcePred> |
| compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t, |
| MultiPassInputIterator edge_begin, |
| MultiPassInputIterator edge_end, |
| vertices_size_type numlocalverts, |
| const GlobalToLocal& global_to_local, |
| const SourcePred& source_pred, |
| const GraphProperty& prop = GraphProperty()) |
| : inherited_vertex_properties(numlocalverts), m_forward(), m_property(prop) |
| { |
| m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, numlocalverts, global_to_local, source_pred); |
| } |
| |
| // From number of vertices and unsorted list of edges, plus edge properties, |
| // with filter and global-to-local map |
| template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename SourcePred> |
| compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t, |
| MultiPassInputIterator edge_begin, |
| MultiPassInputIterator edge_end, |
| EdgePropertyIterator ep_iter, |
| vertices_size_type numlocalverts, |
| const GlobalToLocal& global_to_local, |
| const SourcePred& source_pred, |
| const GraphProperty& prop = GraphProperty()) |
| : inherited_vertex_properties(numlocalverts), m_forward(), m_property(prop) |
| { |
| m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numlocalverts, global_to_local, source_pred); |
| } |
| |
| // From number of vertices and sorted list of edges (new interface) |
| template<typename InputIterator> |
| compressed_sparse_row_graph(edges_are_sorted_t, |
| InputIterator edge_begin, InputIterator edge_end, |
| vertices_size_type numverts, |
| edges_size_type numedges = 0, |
| const GraphProperty& prop = GraphProperty()) |
| : m_property(prop) |
| { |
| m_forward.assign_from_sorted_edges(edge_begin, edge_end, typed_identity_property_map<vertices_size_type>(), keep_all(), numverts, numedges); |
| inherited_vertex_properties::resize(numverts); |
| } |
| |
| // From number of vertices and sorted list of edges (new interface) |
| template<typename InputIterator, typename EdgePropertyIterator> |
| compressed_sparse_row_graph(edges_are_sorted_t, |
| InputIterator edge_begin, InputIterator edge_end, |
| EdgePropertyIterator ep_iter, |
| vertices_size_type numverts, |
| edges_size_type numedges = 0, |
| const GraphProperty& prop = GraphProperty()) |
| : m_property(prop) |
| { |
| m_forward.assign_from_sorted_edges(edge_begin, edge_end, ep_iter, typed_identity_property_map<vertices_size_type>(), keep_all(), numverts, numedges); |
| inherited_vertex_properties::resize(numverts); |
| } |
| |
| // From number of vertices and sorted list of edges, filtered and global (new interface) |
| template<typename InputIterator, typename GlobalToLocal, typename SourcePred> |
| compressed_sparse_row_graph(edges_are_sorted_global_t, |
| InputIterator edge_begin, InputIterator edge_end, |
| const GlobalToLocal& global_to_local, |
| const SourcePred& source_pred, |
| vertices_size_type numverts, |
| const GraphProperty& prop = GraphProperty()) |
| : m_property(prop) |
| { |
| m_forward.assign_from_sorted_edges(edge_begin, edge_end, global_to_local, source_pred, numverts, 0); |
| inherited_vertex_properties::resize(numverts); |
| } |
| |
| // From number of vertices and sorted list of edges (new interface) |
| template<typename InputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename SourcePred> |
| compressed_sparse_row_graph(edges_are_sorted_global_t, |
| InputIterator edge_begin, InputIterator edge_end, |
| EdgePropertyIterator ep_iter, |
| const GlobalToLocal& global_to_local, |
| const SourcePred& source_pred, |
| vertices_size_type numverts, |
| const GraphProperty& prop = GraphProperty()) |
| : m_property(prop) |
| { |
| m_forward.assign_from_sorted_edges(edge_begin, edge_end, ep_iter, global_to_local, source_pred, numverts, 0); |
| inherited_vertex_properties::resize(numverts); |
| } |
| |
| // From number of vertices and mutable vectors of sources and targets; |
| // vectors are returned with unspecified contents but are guaranteed not to |
| // share storage with the constructed graph. |
| compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t, |
| std::vector<vertex_descriptor>& sources, |
| std::vector<vertex_descriptor>& targets, |
| vertices_size_type numverts, |
| const GraphProperty& prop = GraphProperty()) |
| : inherited_vertex_properties(numverts), m_property(prop) |
| { |
| m_forward.assign_sources_and_targets_global(sources, targets, numverts, boost::typed_identity_property_map<vertices_size_type>()); |
| } |
| |
| // From number of vertices and mutable vectors of sources and targets, |
| // expressed with global vertex indices; vectors are returned with |
| // unspecified contents but are guaranteed not to share storage with the |
| // constructed graph. This constructor should only be used by the |
| // distributed CSR graph. |
| template <typename GlobalToLocal> |
| compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_global_t, |
| std::vector<vertex_descriptor>& sources, |
| std::vector<vertex_descriptor>& targets, |
| vertices_size_type numlocalverts, |
| GlobalToLocal global_to_local, |
| const GraphProperty& prop = GraphProperty()) |
| : inherited_vertex_properties(numlocalverts), m_property(prop) |
| { |
| m_forward.assign_sources_and_targets_global(sources, targets, numlocalverts, global_to_local); |
| } |
| |
| // From number of vertices and mutable vectors of sources, targets, and edge |
| // properties; vectors are returned with unspecified contents but are |
| // guaranteed not to share storage with the constructed graph. |
| compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t, |
| std::vector<vertex_descriptor>& sources, |
| std::vector<vertex_descriptor>& targets, |
| std::vector<typename forward_type::inherited_edge_properties::edge_bundled>& edge_props, |
| vertices_size_type numverts, |
| const GraphProperty& prop = GraphProperty()) |
| : inherited_vertex_properties(numverts), m_property(prop) |
| { |
| m_forward.assign_sources_and_targets_global(sources, targets, edge_props, numverts, boost::typed_identity_property_map<vertices_size_type>()); |
| } |
| |
| // From number of vertices and mutable vectors of sources and targets and |
| // edge properties, expressed with global vertex indices; vectors are |
| // returned with unspecified contents but are guaranteed not to share |
| // storage with the constructed graph. This constructor should only be used |
| // by the distributed CSR graph. |
| template <typename GlobalToLocal> |
| compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_global_t, |
| std::vector<vertex_descriptor>& sources, |
| std::vector<vertex_descriptor>& targets, |
| std::vector<typename forward_type::inherited_edge_properties::edge_bundled>& edge_props, |
| vertices_size_type numlocalverts, |
| GlobalToLocal global_to_local, |
| const GraphProperty& prop = GraphProperty()) |
| : inherited_vertex_properties(numlocalverts), m_property(prop) |
| { |
| m_forward.assign_sources_and_targets_global(sources, targets, edge_props, numlocalverts, global_to_local); |
| } |
| |
| // From number of vertices and single-pass range of unsorted edges. Data is |
| // cached in coordinate form before creating the actual graph. |
| template<typename InputIterator> |
| compressed_sparse_row_graph(edges_are_unsorted_t, |
| InputIterator edge_begin, InputIterator edge_end, |
| vertices_size_type numverts, |
| const GraphProperty& prop = GraphProperty()) |
| : inherited_vertex_properties(numverts), m_property(prop) |
| { |
| std::vector<vertex_descriptor> sources, targets; |
| boost::graph::detail::split_into_separate_coords |
| (edge_begin, edge_end, sources, targets); |
| m_forward.assign_sources_and_targets_global(sources, targets, numverts, boost::typed_identity_property_map<vertices_size_type>()); |
| } |
| |
| // From number of vertices and single-pass range of unsorted edges and |
| // single-pass range of edge properties. Data is cached in coordinate form |
| // before creating the actual graph. |
| template<typename InputIterator, typename EdgePropertyIterator> |
| compressed_sparse_row_graph(edges_are_unsorted_t, |
| InputIterator edge_begin, InputIterator edge_end, |
| EdgePropertyIterator ep_iter, |
| vertices_size_type numverts, |
| const GraphProperty& prop = GraphProperty()) |
| : inherited_vertex_properties(numverts), m_property(prop) |
| { |
| std::vector<vertex_descriptor> sources, targets; |
| boost::graph::detail::split_into_separate_coords |
| (edge_begin, edge_end, sources, targets); |
| size_t numedges = sources.size(); |
| std::vector<typename forward_type::inherited_edge_properties::edge_bundled> edge_props(numedges); |
| for (size_t i = 0; i < numedges; ++i) { |
| edge_props[i] = *ep_iter++; |
| } |
| m_forward.assign_sources_and_targets_global(sources, targets, edge_props, numverts, boost::typed_identity_property_map<vertices_size_type>()); |
| } |
| |
| // From number of vertices and single-pass range of unsorted edges. Data is |
| // cached in coordinate form before creating the actual graph. Edges are |
| // filtered and transformed for use in a distributed graph. |
| template<typename InputIterator, typename GlobalToLocal, typename SourcePred> |
| compressed_sparse_row_graph(edges_are_unsorted_global_t, |
| InputIterator edge_begin, InputIterator edge_end, |
| vertices_size_type numlocalverts, |
| GlobalToLocal global_to_local, |
| const SourcePred& source_pred, |
| const GraphProperty& prop = GraphProperty()) |
| : inherited_vertex_properties(numlocalverts), m_property(prop) |
| { |
| std::vector<vertex_descriptor> sources, targets; |
| boost::graph::detail::split_into_separate_coords_filtered |
| (edge_begin, edge_end, sources, targets, source_pred); |
| m_forward.assign_sources_and_targets_global(sources, targets, numlocalverts, global_to_local); |
| } |
| |
| // From number of vertices and single-pass range of unsorted edges and |
| // single-pass range of edge properties. Data is cached in coordinate form |
| // before creating the actual graph. Edges are filtered and transformed for |
| // use in a distributed graph. |
| template<typename InputIterator, typename EdgePropertyIterator, |
| typename GlobalToLocal, typename SourcePred> |
| compressed_sparse_row_graph(edges_are_unsorted_global_t, |
| InputIterator edge_begin, InputIterator edge_end, |
| EdgePropertyIterator ep_iter, |
| vertices_size_type numlocalverts, |
| GlobalToLocal global_to_local, |
| const SourcePred& source_pred, |
| const GraphProperty& prop = GraphProperty()) |
| : inherited_vertex_properties(numlocalverts), m_property(prop) |
| { |
| std::vector<vertex_descriptor> sources, targets; |
| std::vector<edge_bundled> edge_props; |
| boost::graph::detail::split_into_separate_coords_filtered |
| (edge_begin, edge_end, ep_iter, sources, targets, edge_props, source_pred); |
| m_forward.assign_sources_and_targets_global(sources, targets, edge_props, numlocalverts, global_to_local); |
| } |
| |
| |
| // Requires IncidenceGraph and a vertex index map |
| template<typename Graph, typename VertexIndexMap> |
| compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi, |
| vertices_size_type numverts, |
| edges_size_type numedges) |
| : m_property() |
| { |
| assign(g, vi, numverts, numedges); |
| inherited_vertex_properties::resize(numverts); |
| } |
| |
| // Requires VertexListGraph and EdgeListGraph |
| template<typename Graph, typename VertexIndexMap> |
| compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi) |
| : m_property() |
| { |
| typename graph_traits<Graph>::edges_size_type numedges = num_edges(g); |
| if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) { |
| numedges *= 2; // Double each edge (actual doubling done by out_edges function) |
| } |
| vertices_size_type numverts = num_vertices(g); |
| assign(g, vi, numverts, numedges); |
| inherited_vertex_properties::resize(numverts); |
| } |
| |
| // Requires vertex index map plus requirements of previous constructor |
| template<typename Graph> |
| explicit compressed_sparse_row_graph(const Graph& g) |
| : m_property() |
| { |
| typename graph_traits<Graph>::edges_size_type numedges = num_edges(g); |
| if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) { |
| numedges *= 2; // Double each edge (actual doubling done by out_edges function) |
| } |
| assign(g, get(vertex_index, g), num_vertices(g), numedges); |
| } |
| |
| // From any graph (slow and uses a lot of memory) |
| // Requires IncidenceGraph and a vertex index map |
| // Internal helper function |
| // Note that numedges must be doubled for undirected source graphs |
| template<typename Graph, typename VertexIndexMap> |
| void |
| assign(const Graph& g, const VertexIndexMap& vi, |
| vertices_size_type numverts, edges_size_type numedges) |
| { |
| m_forward.assign(g, vi, numverts, numedges); |
| inherited_vertex_properties::resize(numverts); |
| } |
| |
| // Requires the above, plus VertexListGraph and EdgeListGraph |
| template<typename Graph, typename VertexIndexMap> |
| void assign(const Graph& g, const VertexIndexMap& vi) |
| { |
| typename graph_traits<Graph>::edges_size_type numedges = num_edges(g); |
| if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) { |
| numedges *= 2; // Double each edge (actual doubling done by out_edges function) |
| } |
| vertices_size_type numverts = num_vertices(g); |
| m_forward.assign(g, vi, numverts, numedges); |
| inherited_vertex_properties::resize(numverts); |
| } |
| |
| // Requires the above, plus a vertex_index map. |
| template<typename Graph> |
| void assign(const Graph& g) |
| { |
| typename graph_traits<Graph>::edges_size_type numedges = num_edges(g); |
| if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) { |
| numedges *= 2; // Double each edge (actual doubling done by out_edges function) |
| } |
| vertices_size_type numverts = num_vertices(g); |
| m_forward.assign(g, get(vertex_index, g), numverts, numedges); |
| inherited_vertex_properties::resize(numverts); |
| } |
| |
| // Add edges from a sorted (smallest sources first) range of pairs and edge |
| // properties |
| template <typename BidirectionalIteratorOrig, typename EPIterOrig, |
| typename GlobalToLocal> |
| void |
| add_edges_sorted_internal( |
| BidirectionalIteratorOrig first_sorted, |
| BidirectionalIteratorOrig last_sorted, |
| EPIterOrig ep_iter_sorted, |
| const GlobalToLocal& global_to_local) { |
| m_forward.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted, global_to_local); |
| } |
| |
| template <typename BidirectionalIteratorOrig, typename EPIterOrig> |
| void |
| add_edges_sorted_internal( |
| BidirectionalIteratorOrig first_sorted, |
| BidirectionalIteratorOrig last_sorted, |
| EPIterOrig ep_iter_sorted) { |
| m_forward.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted, typed_identity_property_map<vertices_size_type>()); |
| } |
| |
| // Add edges from a sorted (smallest sources first) range of pairs |
| template <typename BidirectionalIteratorOrig> |
| void |
| add_edges_sorted_internal( |
| BidirectionalIteratorOrig first_sorted, |
| BidirectionalIteratorOrig last_sorted) { |
| m_forward.add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<edge_bundled>()); |
| } |
| |
| template <typename BidirectionalIteratorOrig, typename GlobalToLocal> |
| void |
| add_edges_sorted_internal_global( |
| BidirectionalIteratorOrig first_sorted, |
| BidirectionalIteratorOrig last_sorted, |
| const GlobalToLocal& global_to_local) { |
| m_forward.add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<edge_bundled>(), global_to_local); |
| } |
| |
| template <typename BidirectionalIteratorOrig, typename EPIterOrig, |
| typename GlobalToLocal> |
| void |
| add_edges_sorted_internal_global( |
| BidirectionalIteratorOrig first_sorted, |
| BidirectionalIteratorOrig last_sorted, |
| EPIterOrig ep_iter_sorted, |
| const GlobalToLocal& global_to_local) { |
| m_forward.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted, global_to_local); |
| } |
| |
| // Add edges from a range of (source, target) pairs that are unsorted |
| template <typename InputIterator, typename GlobalToLocal> |
| inline void |
| add_edges_internal(InputIterator first, InputIterator last, |
| const GlobalToLocal& global_to_local) { |
| typedef compressed_sparse_row_graph Graph; |
| typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t; |
| typedef typename boost::graph_traits<Graph>::vertices_size_type vertex_num; |
| typedef typename boost::graph_traits<Graph>::edges_size_type edge_num; |
| typedef std::vector<std::pair<vertex_t, vertex_t> > edge_vector_t; |
| edge_vector_t new_edges(first, last); |
| if (new_edges.empty()) return; |
| std::sort(new_edges.begin(), new_edges.end()); |
| this->add_edges_sorted_internal_global(new_edges.begin(), new_edges.end(), global_to_local); |
| } |
| |
| template <typename InputIterator> |
| inline void |
| add_edges_internal(InputIterator first, InputIterator last) { |
| this->add_edges_internal(first, last, typed_identity_property_map<vertices_size_type>()); |
| } |
| |
| // Add edges from a range of (source, target) pairs and edge properties that |
| // are unsorted |
| template <typename InputIterator, typename EPIterator, typename GlobalToLocal> |
| inline void |
| add_edges_internal(InputIterator first, InputIterator last, |
| EPIterator ep_iter, EPIterator ep_iter_end, |
| const GlobalToLocal& global_to_local) { |
| typedef compressed_sparse_row_graph Graph; |
| typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t; |
| typedef typename boost::graph_traits<Graph>::vertices_size_type vertex_num; |
| typedef typename boost::graph_traits<Graph>::edges_size_type edge_num; |
| typedef std::pair<vertex_t, vertex_t> vertex_pair; |
| typedef std::vector< |
| boost::tuple<vertex_pair, |
| edge_bundled> > |
| edge_vector_t; |
| edge_vector_t new_edges |
| (boost::make_zip_iterator(boost::make_tuple(first, ep_iter)), |
| boost::make_zip_iterator(boost::make_tuple(last, ep_iter_end))); |
| if (new_edges.empty()) return; |
| std::sort(new_edges.begin(), new_edges.end(), |
| boost::detail::compare_first< |
| std::less<vertex_pair> >()); |
| m_forward.add_edges_sorted_internal |
| (boost::make_transform_iterator( |
| new_edges.begin(), |
| boost::detail::my_tuple_get_class<0, vertex_pair>()), |
| boost::make_transform_iterator( |
| new_edges.end(), |
| boost::detail::my_tuple_get_class<0, vertex_pair>()), |
| boost::make_transform_iterator( |
| new_edges.begin(), |
| boost::detail::my_tuple_get_class |
| <1, edge_bundled>()), |
| global_to_local); |
| } |
| |
| // Add edges from a range of (source, target) pairs and edge properties that |
| // are unsorted |
| template <typename InputIterator, typename EPIterator> |
| inline void |
| add_edges_internal(InputIterator first, InputIterator last, |
| EPIterator ep_iter, EPIterator ep_iter_end) { |
| this->add_edges_internal(first, last, ep_iter, ep_iter_end, typed_identity_property_map<vertices_size_type>()); |
| } |
| |
| using inherited_vertex_properties::operator[]; |
| |
| // Directly access a edge or edge bundle |
| edge_push_back_type& operator[](const edge_descriptor& v) |
| { return m_forward.m_edge_properties[get(edge_index, *this, v)]; } |
| |
| const edge_push_back_type& operator[](const edge_descriptor& v) const |
| { return m_forward.m_edge_properties[get(edge_index, *this, v)]; } |
| |
| // Directly access a graph bundle |
| graph_bundled& operator[](graph_bundle_t) |
| { return get_property(*this); } |
| |
| const graph_bundled& operator[](graph_bundle_t) const |
| { return get_property(*this); } |
| |
| // private: non-portable, requires friend templates |
| inherited_vertex_properties& vertex_properties() {return *this;} |
| const inherited_vertex_properties& vertex_properties() const {return *this;} |
| typename forward_type::inherited_edge_properties& edge_properties() { return m_forward; } |
| const typename forward_type::inherited_edge_properties& edge_properties() const { return m_forward; } |
| |
| forward_type m_forward; |
| GraphProperty m_property; |
| }; |
| |
| template<typename VertexProperty, |
| typename EdgeProperty, |
| typename GraphProperty, |
| typename Vertex, |
| typename EdgeIndex> |
| class compressed_sparse_row_graph<bidirectionalS, VertexProperty, EdgeProperty, GraphProperty, Vertex, EdgeIndex> |
| : public detail::indexed_vertex_properties<BOOST_BIDIR_CSR_GRAPH_TYPE, |
| VertexProperty, Vertex, typed_identity_property_map<Vertex> > |
| { |
| public: |
| typedef detail::indexed_vertex_properties<compressed_sparse_row_graph, |
| VertexProperty, Vertex, typed_identity_property_map<Vertex> > |
| inherited_vertex_properties; |
| |
| public: |
| // For Property Graph |
| typedef typename graph_detail::graph_prop<GraphProperty>::property graph_property_type; |
| typedef typename graph_detail::graph_prop<GraphProperty>::bundle graph_bundled; |
| // typedef GraphProperty graph_property_type; |
| |
| typedef detail::compressed_sparse_row_structure<EdgeProperty, Vertex, EdgeIndex> forward_type; |
| typedef EdgeIndex /* typename boost::mpl::if_c<boost::is_same<EdgeProperty, boost::no_property>, boost::no_property, EdgeIndex> */ backward_edge_property; |
| typedef detail::compressed_sparse_row_structure<backward_edge_property, Vertex, EdgeIndex> backward_type; |
| |
| public: |
| // Concept requirements: |
| // For Graph |
| typedef Vertex vertex_descriptor; |
| typedef detail::csr_edge_descriptor<Vertex, EdgeIndex> edge_descriptor; |
| typedef bidirectional_tag directed_category; |
| typedef allow_parallel_edge_tag edge_parallel_category; |
| |
| class traversal_category: public bidirectional_graph_tag, |
| public adjacency_graph_tag, |
| public vertex_list_graph_tag, |
| public edge_list_graph_tag {}; |
| |
| static vertex_descriptor null_vertex() { return vertex_descriptor(-1); } |
| |
| // For VertexListGraph |
| typedef counting_iterator<Vertex> vertex_iterator; |
| typedef Vertex vertices_size_type; |
| |
| // For EdgeListGraph |
| typedef EdgeIndex edges_size_type; |
| |
| // For IncidenceGraph |
| typedef detail::csr_out_edge_iterator<compressed_sparse_row_graph> out_edge_iterator; |
| typedef EdgeIndex degree_size_type; |
| |
| // For AdjacencyGraph |
| typedef typename std::vector<Vertex>::const_iterator adjacency_iterator; |
| |
| // For EdgeListGraph |
| typedef detail::csr_edge_iterator<compressed_sparse_row_graph> edge_iterator; |
| |
| // For BidirectionalGraph (not implemented) |
| typedef detail::csr_in_edge_iterator<compressed_sparse_row_graph> in_edge_iterator; |
| |
| // For internal use |
| typedef csr_graph_tag graph_tag; |
| |
| typedef typename forward_type::inherited_edge_properties::edge_bundled edge_bundled; |
| typedef typename forward_type::inherited_edge_properties::edge_push_back_type edge_push_back_type; |
| typedef typename forward_type::inherited_edge_properties::edge_property_type edge_property_type; |
| |
| // Constructors |
| |
| // Default constructor: an empty graph. |
| compressed_sparse_row_graph(): m_property() {} |
| |
| // With numverts vertices |
| compressed_sparse_row_graph(vertices_size_type numverts) |
| : inherited_vertex_properties(numverts), |
| m_forward(numverts), m_backward(numverts) {} |
| |
| private: |
| |
| void set_up_backward_property_links() { |
| std::pair<edge_iterator, edge_iterator> e = edges(*this); |
| m_backward.assign_unsorted_multi_pass_edges |
| (detail::transpose_edges( |
| detail::make_edge_to_index_pair_iter |
| (*this, get(vertex_index, *this), e.first)), |
| detail::transpose_edges( |
| detail::make_edge_to_index_pair_iter |
| (*this, get(vertex_index, *this), e.second)), |
| boost::counting_iterator<EdgeIndex>(0), |
| m_forward.m_rowstart.size() - 1, |
| typed_identity_property_map<Vertex>(), |
| keep_all()); |
| } |
| |
| public: |
| |
| // From number of vertices and unsorted list of edges |
| template <typename MultiPassInputIterator> |
| compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t, |
| MultiPassInputIterator edge_begin, |
| MultiPassInputIterator edge_end, |
| vertices_size_type numverts, |
| const GraphProperty& prop = GraphProperty()) |
| : inherited_vertex_properties(numverts), m_property(prop) |
| { |
| m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, numverts, typed_identity_property_map<Vertex>(), keep_all()); |
| set_up_backward_property_links(); |
| } |
| |
| // From number of vertices and unsorted list of edges, plus edge properties |
| template <typename MultiPassInputIterator, typename EdgePropertyIterator> |
| compressed_sparse_row_graph(edges_are_unsorted_multi_pass_t, |
| MultiPassInputIterator edge_begin, |
| MultiPassInputIterator edge_end, |
| EdgePropertyIterator ep_iter, |
| vertices_size_type numverts, |
| const GraphProperty& prop = GraphProperty()) |
| : inherited_vertex_properties(numverts), m_forward(), m_property(prop) |
| { |
| m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numverts, typed_identity_property_map<Vertex>(), keep_all()); |
| set_up_backward_property_links(); |
| } |
| |
| // From number of vertices and unsorted list of edges, with filter and |
| // global-to-local map |
| template <typename MultiPassInputIterator, typename GlobalToLocal, typename SourcePred> |
| compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t, |
| MultiPassInputIterator edge_begin, |
| MultiPassInputIterator edge_end, |
| vertices_size_type numlocalverts, |
| const GlobalToLocal& global_to_local, |
| const SourcePred& source_pred, |
| const GraphProperty& prop = GraphProperty()) |
| : inherited_vertex_properties(numlocalverts), m_forward(), m_property(prop) |
| { |
| m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, numlocalverts, global_to_local, source_pred); |
| set_up_backward_property_links(); |
| } |
| |
| // From number of vertices and unsorted list of edges, plus edge properties, |
| // with filter and global-to-local map |
| template <typename MultiPassInputIterator, typename EdgePropertyIterator, typename GlobalToLocal, typename SourcePred> |
| compressed_sparse_row_graph(edges_are_unsorted_multi_pass_global_t, |
| MultiPassInputIterator edge_begin, |
| MultiPassInputIterator edge_end, |
| EdgePropertyIterator ep_iter, |
| vertices_size_type numlocalverts, |
| const GlobalToLocal& global_to_local, |
| const SourcePred& source_pred, |
| const GraphProperty& prop = GraphProperty()) |
| : inherited_vertex_properties(numlocalverts), m_forward(), m_property(prop) |
| { |
| m_forward.assign_unsorted_multi_pass_edges(edge_begin, edge_end, ep_iter, numlocalverts, global_to_local, source_pred); |
| set_up_backward_property_links(); |
| } |
| |
| // Requires IncidenceGraph and a vertex index map |
| template<typename Graph, typename VertexIndexMap> |
| compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi, |
| vertices_size_type numverts, |
| edges_size_type numedges) |
| : m_property() |
| { |
| assign(g, vi, numverts, numedges); |
| inherited_vertex_properties::resize(numverts); |
| } |
| |
| // Requires VertexListGraph and EdgeListGraph |
| template<typename Graph, typename VertexIndexMap> |
| compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi) |
| : m_property() |
| { |
| typename graph_traits<Graph>::edges_size_type numedges = num_edges(g); |
| if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) { |
| numedges *= 2; // Double each edge (actual doubling done by out_edges function) |
| } |
| vertices_size_type numverts = num_vertices(g); |
| assign(g, vi, numverts, numedges); |
| inherited_vertex_properties::resize(numverts); |
| } |
| |
| // Requires vertex index map plus requirements of previous constructor |
| template<typename Graph> |
| explicit compressed_sparse_row_graph(const Graph& g) |
| : m_property() |
| { |
| typename graph_traits<Graph>::edges_size_type numedges = num_edges(g); |
| if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) { |
| numedges *= 2; // Double each edge (actual doubling done by out_edges function) |
| } |
| assign(g, get(vertex_index, g), num_vertices(g), numedges); |
| } |
| |
| // From any graph (slow and uses a lot of memory) |
| // Requires IncidenceGraph and a vertex index map |
| // Internal helper function |
| // Note that numedges must be doubled for undirected source graphs |
| template<typename Graph, typename VertexIndexMap> |
| void |
| assign(const Graph& g, const VertexIndexMap& vi, |
| vertices_size_type numverts, edges_size_type numedges) |
| { |
| m_forward.assign(g, vi, numverts, numedges); |
| inherited_vertex_properties::resize(numverts); |
| } |
| |
| // Requires the above, plus VertexListGraph and EdgeListGraph |
| template<typename Graph, typename VertexIndexMap> |
| void assign(const Graph& g, const VertexIndexMap& vi) |
| { |
| typename graph_traits<Graph>::edges_size_type numedges = num_edges(g); |
| if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) { |
| numedges *= 2; // Double each edge (actual doubling done by out_edges function) |
| } |
| vertices_size_type numverts = num_vertices(g); |
| m_forward.assign(g, vi, numverts, numedges); |
| inherited_vertex_properties::resize(numverts); |
| } |
| |
| // Requires the above, plus a vertex_index map. |
| template<typename Graph> |
| void assign(const Graph& g) |
| { |
| typename graph_traits<Graph>::edges_size_type numedges = num_edges(g); |
| if (is_same<typename graph_traits<Graph>::directed_category, undirectedS>::value) { |
| numedges *= 2; // Double each edge (actual doubling done by out_edges function) |
| } |
| vertices_size_type numverts = num_vertices(g); |
| m_forward.assign(g, get(vertex_index, g), numverts, numedges); |
| inherited_vertex_properties::resize(numverts); |
| } |
| |
| // Add edges from a sorted (smallest sources first) range of pairs and edge |
| // properties |
| template <typename BidirectionalIteratorOrig, typename EPIterOrig, |
| typename GlobalToLocal> |
| void |
| add_edges_sorted_internal( |
| BidirectionalIteratorOrig first_sorted, |
| BidirectionalIteratorOrig last_sorted, |
| EPIterOrig ep_iter_sorted, |
| const GlobalToLocal& global_to_local) { |
| m_forward.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted, global_to_local); |
| } |
| |
| template <typename BidirectionalIteratorOrig, typename EPIterOrig> |
| void |
| add_edges_sorted_internal( |
| BidirectionalIteratorOrig first_sorted, |
| BidirectionalIteratorOrig last_sorted, |
| EPIterOrig ep_iter_sorted) { |
| m_forward.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted, typed_identity_property_map<Vertex>()); |
| } |
| |
| // Add edges from a sorted (smallest sources first) range of pairs |
| template <typename BidirectionalIteratorOrig> |
| void |
| add_edges_sorted_internal( |
| BidirectionalIteratorOrig first_sorted, |
| BidirectionalIteratorOrig last_sorted) { |
| m_forward.add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<edge_bundled>()); |
| } |
| |
| template <typename BidirectionalIteratorOrig, typename GlobalToLocal> |
| void |
| add_edges_sorted_internal_global( |
| BidirectionalIteratorOrig first_sorted, |
| BidirectionalIteratorOrig last_sorted, |
| const GlobalToLocal& global_to_local) { |
| m_forward.add_edges_sorted_internal(first_sorted, last_sorted, detail::default_construct_iterator<edge_bundled>(), global_to_local); |
| } |
| |
| template <typename BidirectionalIteratorOrig, typename EPIterOrig, |
| typename GlobalToLocal> |
| void |
| add_edges_sorted_internal_global( |
| BidirectionalIteratorOrig first_sorted, |
| BidirectionalIteratorOrig last_sorted, |
| EPIterOrig ep_iter_sorted, |
| const GlobalToLocal& global_to_local) { |
| m_forward.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted, global_to_local); |
| } |
| |
| // Add edges from a range of (source, target) pairs that are unsorted |
| template <typename InputIterator, typename GlobalToLocal> |
| inline void |
| add_edges_internal(InputIterator first, InputIterator last, |
| const GlobalToLocal& global_to_local) { |
| typedef compressed_sparse_row_graph Graph; |
| typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t; |
| typedef typename boost::graph_traits<Graph>::vertices_size_type vertex_num; |
| typedef typename boost::graph_traits<Graph>::edges_size_type edge_num; |
| typedef std::vector<std::pair<vertex_t, vertex_t> > edge_vector_t; |
| edge_vector_t new_edges(first, last); |
| if (new_edges.empty()) return; |
| std::sort(new_edges.begin(), new_edges.end()); |
| this->add_edges_sorted_internal_global(new_edges.begin(), new_edges.end(), global_to_local); |
| } |
| |
| template <typename InputIterator> |
| inline void |
| add_edges_internal(InputIterator first, InputIterator last) { |
| this->add_edges_internal(first, last, typed_identity_property_map<Vertex>()); |
| } |
| |
| // Add edges from a range of (source, target) pairs and edge properties that |
| // are unsorted |
| template <typename InputIterator, typename EPIterator, typename GlobalToLocal> |
| inline void |
| add_edges_internal(InputIterator first, InputIterator last, |
| EPIterator ep_iter, EPIterator ep_iter_end, |
| const GlobalToLocal& global_to_local) { |
| typedef compressed_sparse_row_graph Graph; |
| typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_t; |
| typedef typename boost::graph_traits<Graph>::vertices_size_type vertex_num; |
| typedef typename boost::graph_traits<Graph>::edges_size_type edge_num; |
| typedef std::pair<vertex_t, vertex_t> vertex_pair; |
| typedef std::vector< |
| boost::tuple<vertex_pair, |
| edge_bundled> > |
| edge_vector_t; |
| edge_vector_t new_edges |
| (boost::make_zip_iterator(boost::make_tuple(first, ep_iter)), |
| boost::make_zip_iterator(boost::make_tuple(last, ep_iter_end))); |
| if (new_edges.empty()) return; |
| std::sort(new_edges.begin(), new_edges.end(), |
| boost::detail::compare_first< |
| std::less<vertex_pair> >()); |
| m_forward.add_edges_sorted_internal |
| (boost::make_transform_iterator( |
| new_edges.begin(), |
| boost::detail::my_tuple_get_class<0, vertex_pair>()), |
| boost::make_transform_iterator( |
| new_edges.end(), |
| boost::detail::my_tuple_get_class<0, vertex_pair>()), |
| boost::make_transform_iterator( |
| new_edges.begin(), |
| boost::detail::my_tuple_get_class |
| <1, edge_bundled>()), |
| global_to_local); |
| } |
| |
| // Add edges from a range of (source, target) pairs and edge properties that |
| // are unsorted |
| template <typename InputIterator, typename EPIterator> |
| inline void |
| add_edges_internal(InputIterator first, InputIterator last, |
| EPIterator ep_iter, EPIterator ep_iter_end) { |
| this->add_edges_internal(first, last, ep_iter, ep_iter_end, typed_identity_property_map<Vertex>()); |
| } |
| |
| using inherited_vertex_properties::operator[]; |
| |
| // Directly access a edge or edge bundle |
| edge_push_back_type& operator[](const edge_descriptor& v) |
| { return m_forward.m_edge_properties[get(edge_index, *this, v)]; } |
| |
| const edge_push_back_type& operator[](const edge_descriptor& v) const |
| { return m_forward.m_edge_properties[get(edge_index, *this, v)]; } |
| |
| // private: non-portable, requires friend templates |
| inherited_vertex_properties& vertex_properties() {return *this;} |
| const inherited_vertex_properties& vertex_properties() const {return *this;} |
| typename forward_type::inherited_edge_properties& edge_properties() { return m_forward; } |
| const typename forward_type::inherited_edge_properties& edge_properties() const { return m_forward; } |
| |
| forward_type m_forward; |
| backward_type m_backward; |
| GraphProperty m_property; |
| }; |
| |
| // Construction functions |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| inline Vertex |
| add_vertex(BOOST_CSR_GRAPH_TYPE& g) { |
| add_vertex(g, typename BOOST_CSR_GRAPH_TYPE::vertex_bundled()); |
| } |
| |
| template<BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS> |
| inline Vertex |
| add_vertex(BOOST_DIR_CSR_GRAPH_TYPE& g, |
| typename BOOST_DIR_CSR_GRAPH_TYPE::vertex_bundled const& p) { |
| Vertex old_num_verts_plus_one = g.m_forward.m_rowstart.size(); |
| g.m_forward.m_rowstart.push_back(g.m_forward.m_rowstart.back()); |
| g.vertex_properties().push_back(p); |
| return old_num_verts_plus_one - 1; |
| } |
| |
| template<BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS> |
| inline Vertex |
| add_vertex(BOOST_BIDIR_CSR_GRAPH_TYPE& g, |
| typename BOOST_BIDIR_CSR_GRAPH_TYPE::vertex_bundled const& p) { |
| Vertex old_num_verts_plus_one = g.m_forward.m_rowstart.size(); |
| g.m_forward.m_rowstart.push_back(g.m_forward.m_rowstart.back()); |
| g.m_backward.m_rowstart.push_back(g.m_backward.m_rowstart.back()); |
| g.vertex_properties().push_back(p); |
| return old_num_verts_plus_one - 1; |
| } |
| |
| template<BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS> |
| inline Vertex |
| add_vertices(typename BOOST_DIR_CSR_GRAPH_TYPE::vertices_size_type count, BOOST_DIR_CSR_GRAPH_TYPE& g) { |
| Vertex old_num_verts_plus_one = g.m_forward.m_rowstart.size(); |
| EdgeIndex numedges = g.m_forward.m_rowstart.back(); |
| g.m_forward.m_rowstart.resize(old_num_verts_plus_one + count, numedges); |
| g.m_backward.m_rowstart.resize(old_num_verts_plus_one + count, numedges); |
| g.vertex_properties().resize(num_vertices(g)); |
| return old_num_verts_plus_one - 1; |
| } |
| |
| // Add edges from a sorted (smallest sources first) range of pairs and edge |
| // properties |
| template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig, |
| typename EPIterOrig> |
| void |
| add_edges_sorted( |
| BidirectionalIteratorOrig first_sorted, |
| BidirectionalIteratorOrig last_sorted, |
| EPIterOrig ep_iter_sorted, |
| BOOST_DIR_CSR_GRAPH_TYPE& g) { |
| g.add_edges_sorted_internal(first_sorted, last_sorted, ep_iter_sorted); |
| } |
| |
| // Add edges from a sorted (smallest sources first) range of pairs |
| template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig> |
| void |
| add_edges_sorted( |
| BidirectionalIteratorOrig first_sorted, |
| BidirectionalIteratorOrig last_sorted, |
| BOOST_DIR_CSR_GRAPH_TYPE& g) { |
| g.add_edges_sorted_internal(first_sorted, last_sorted); |
| } |
| |
| template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig, |
| typename EPIterOrig, typename GlobalToLocal> |
| void |
| add_edges_sorted_global( |
| BidirectionalIteratorOrig first_sorted, |
| BidirectionalIteratorOrig last_sorted, |
| EPIterOrig ep_iter_sorted, |
| const GlobalToLocal& global_to_local, |
| BOOST_DIR_CSR_GRAPH_TYPE& g) { |
| g.add_edges_sorted_internal_global(first_sorted, last_sorted, ep_iter_sorted, |
| global_to_local); |
| } |
| |
| // Add edges from a sorted (smallest sources first) range of pairs |
| template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename BidirectionalIteratorOrig, |
| typename GlobalToLocal> |
| void |
| add_edges_sorted_global( |
| BidirectionalIteratorOrig first_sorted, |
| BidirectionalIteratorOrig last_sorted, |
| const GlobalToLocal& global_to_local, |
| BOOST_DIR_CSR_GRAPH_TYPE& g) { |
| g.add_edges_sorted_internal_global(first_sorted, last_sorted, global_to_local); |
| } |
| |
| // Add edges from a range of (source, target) pairs that are unsorted |
| template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator, |
| typename GlobalToLocal> |
| inline void |
| add_edges_global(InputIterator first, InputIterator last, |
| const GlobalToLocal& global_to_local, BOOST_DIR_CSR_GRAPH_TYPE& g) { |
| g.add_edges_internal(first, last, global_to_local); |
| } |
| |
| // Add edges from a range of (source, target) pairs that are unsorted |
| template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, typename InputIterator> |
| inline void |
| add_edges(InputIterator first, InputIterator last, BOOST_DIR_CSR_GRAPH_TYPE& g) { |
| g.add_edges_internal(first, last); |
| } |
| |
| // Add edges from a range of (source, target) pairs and edge properties that |
| // are unsorted |
| template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, |
| typename InputIterator, typename EPIterator> |
| inline void |
| add_edges(InputIterator first, InputIterator last, |
| EPIterator ep_iter, EPIterator ep_iter_end, |
| BOOST_DIR_CSR_GRAPH_TYPE& g) { |
| g.add_edges_internal(first, last, ep_iter, ep_iter_end); |
| } |
| |
| template <BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS, |
| typename InputIterator, typename EPIterator, typename GlobalToLocal> |
| inline void |
| add_edges_global(InputIterator first, InputIterator last, |
| EPIterator ep_iter, EPIterator ep_iter_end, |
| const GlobalToLocal& global_to_local, |
| BOOST_DIR_CSR_GRAPH_TYPE& g) { |
| g.add_edges_internal(first, last, ep_iter, ep_iter_end, global_to_local); |
| } |
| |
| // From VertexListGraph |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| inline Vertex |
| num_vertices(const BOOST_CSR_GRAPH_TYPE& g) { |
| return g.m_forward.m_rowstart.size() - 1; |
| } |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| std::pair<counting_iterator<Vertex>, counting_iterator<Vertex> > |
| inline vertices(const BOOST_CSR_GRAPH_TYPE& g) { |
| return std::make_pair(counting_iterator<Vertex>(0), |
| counting_iterator<Vertex>(num_vertices(g))); |
| } |
| |
| // From IncidenceGraph |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| inline Vertex |
| source(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e, |
| const BOOST_CSR_GRAPH_TYPE&) |
| { |
| return e.src; |
| } |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| inline Vertex |
| target(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e, |
| const BOOST_CSR_GRAPH_TYPE& g) |
| { |
| return g.m_forward.m_column[e.idx]; |
| } |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| inline std::pair<typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator, |
| typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator> |
| out_edges(Vertex v, const BOOST_CSR_GRAPH_TYPE& g) |
| { |
| typedef typename BOOST_CSR_GRAPH_TYPE::edge_descriptor ed; |
| typedef typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator it; |
| EdgeIndex v_row_start = g.m_forward.m_rowstart[v]; |
| EdgeIndex next_row_start = g.m_forward.m_rowstart[v + 1]; |
| return std::make_pair(it(ed(v, v_row_start)), |
| it(ed(v, next_row_start))); |
| } |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| inline EdgeIndex |
| out_degree(Vertex v, const BOOST_CSR_GRAPH_TYPE& g) |
| { |
| EdgeIndex v_row_start = g.m_forward.m_rowstart[v]; |
| EdgeIndex next_row_start = g.m_forward.m_rowstart[v + 1]; |
| return next_row_start - v_row_start; |
| } |
| |
| template<BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS> |
| inline std::pair<typename BOOST_BIDIR_CSR_GRAPH_TYPE::in_edge_iterator, |
| typename BOOST_BIDIR_CSR_GRAPH_TYPE::in_edge_iterator> |
| in_edges(Vertex v, const BOOST_BIDIR_CSR_GRAPH_TYPE& g) |
| { |
| typedef typename BOOST_BIDIR_CSR_GRAPH_TYPE::edge_descriptor ed; |
| typedef typename BOOST_BIDIR_CSR_GRAPH_TYPE::in_edge_iterator it; |
| EdgeIndex v_row_start = g.m_backward.m_rowstart[v]; |
| EdgeIndex next_row_start = g.m_backward.m_rowstart[v + 1]; |
| return std::make_pair(it(g, v_row_start), |
| it(g, next_row_start)); |
| } |
| |
| template<BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS> |
| inline EdgeIndex |
| in_degree(Vertex v, const BOOST_BIDIR_CSR_GRAPH_TYPE& g) |
| { |
| EdgeIndex v_row_start = g.m_backward.m_rowstart[v]; |
| EdgeIndex next_row_start = g.m_backward.m_rowstart[v + 1]; |
| return next_row_start - v_row_start; |
| } |
| |
| // From AdjacencyGraph |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| inline std::pair<typename BOOST_CSR_GRAPH_TYPE::adjacency_iterator, |
| typename BOOST_CSR_GRAPH_TYPE::adjacency_iterator> |
| adjacent_vertices(Vertex v, const BOOST_CSR_GRAPH_TYPE& g) |
| { |
| EdgeIndex v_row_start = g.m_forward.m_rowstart[v]; |
| EdgeIndex next_row_start = g.m_forward.m_rowstart[v + 1]; |
| return std::make_pair(g.m_forward.m_column.begin() + v_row_start, |
| g.m_forward.m_column.begin() + next_row_start); |
| } |
| |
| // Extra, common functions |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| inline typename graph_traits<BOOST_CSR_GRAPH_TYPE>::vertex_descriptor |
| vertex(typename graph_traits<BOOST_CSR_GRAPH_TYPE>::vertex_descriptor i, |
| const BOOST_CSR_GRAPH_TYPE&) |
| { |
| return i; |
| } |
| |
| // edge() can be provided in linear time for the new interface |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| inline std::pair<typename BOOST_CSR_GRAPH_TYPE::edge_descriptor, bool> |
| edge(Vertex i, Vertex j, const BOOST_CSR_GRAPH_TYPE& g) |
| { |
| typedef typename BOOST_CSR_GRAPH_TYPE::out_edge_iterator out_edge_iter; |
| std::pair<out_edge_iter, out_edge_iter> range = out_edges(i, g); |
| for (; range.first != range.second; ++range.first) { |
| if (target(*range.first, g) == j) |
| return std::make_pair(*range.first, true); |
| } |
| return std::make_pair(typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(), |
| false); |
| } |
| |
| // Find an edge given its index in the graph |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| inline typename BOOST_CSR_GRAPH_TYPE::edge_descriptor |
| edge_from_index(EdgeIndex idx, const BOOST_CSR_GRAPH_TYPE& g) |
| { |
| typedef typename std::vector<EdgeIndex>::const_iterator row_start_iter; |
| BOOST_ASSERT (idx < num_edges(g)); |
| row_start_iter src_plus_1 = |
| std::upper_bound(g.m_forward.m_rowstart.begin(), |
| g.m_forward.m_rowstart.end(), |
| idx); |
| // Get last source whose rowstart is at most idx |
| // upper_bound returns this position plus 1 |
| Vertex src = (src_plus_1 - g.m_forward.m_rowstart.begin()) - 1; |
| return typename BOOST_CSR_GRAPH_TYPE::edge_descriptor(src, idx); |
| } |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| inline EdgeIndex |
| num_edges(const BOOST_CSR_GRAPH_TYPE& g) |
| { |
| return g.m_forward.m_column.size(); |
| } |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| std::pair<typename BOOST_CSR_GRAPH_TYPE::edge_iterator, |
| typename BOOST_CSR_GRAPH_TYPE::edge_iterator> |
| edges(const BOOST_CSR_GRAPH_TYPE& g) |
| { |
| typedef typename BOOST_CSR_GRAPH_TYPE::edge_iterator ei; |
| typedef typename BOOST_CSR_GRAPH_TYPE::edge_descriptor edgedesc; |
| if (g.m_forward.m_rowstart.size() == 1 || g.m_forward.m_column.empty()) { |
| return std::make_pair(ei(), ei()); |
| } else { |
| // Find the first vertex that has outgoing edges |
| Vertex src = 0; |
| while (g.m_forward.m_rowstart[src + 1] == 0) ++src; |
| return std::make_pair(ei(g, edgedesc(src, 0), g.m_forward.m_rowstart[src + 1]), |
| ei(g, edgedesc(num_vertices(g), g.m_forward.m_column.size()), 0)); |
| } |
| } |
| |
| // For Property Graph |
| |
| // Graph properties |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, class Tag, class Value> |
| inline void |
| set_property(BOOST_CSR_GRAPH_TYPE& g, Tag, const Value& value) |
| { |
| get_property_value(g.m_property, Tag()) = value; |
| } |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, class Tag> |
| inline |
| typename graph_property<BOOST_CSR_GRAPH_TYPE, Tag>::type& |
| get_property(BOOST_CSR_GRAPH_TYPE& g, Tag) |
| { |
| return get_property_value(g.m_property, Tag()); |
| } |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, class Tag> |
| inline |
| const |
| typename graph_property<BOOST_CSR_GRAPH_TYPE, Tag>::type& |
| get_property(const BOOST_CSR_GRAPH_TYPE& g, Tag) |
| { |
| return get_property_value(g.m_property, Tag()); |
| } |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| struct property_map<BOOST_CSR_GRAPH_TYPE, vertex_index_t> |
| { |
| typedef typed_identity_property_map<Vertex> type; |
| typedef type const_type; |
| }; |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| struct property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t> |
| { |
| typedef detail::csr_edge_index_map<Vertex, EdgeIndex> type; |
| typedef type const_type; |
| }; |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| struct property_map<BOOST_CSR_GRAPH_TYPE, vertex_bundle_t> |
| { |
| typedef typename BOOST_CSR_GRAPH_TYPE::inherited_vertex_properties::vertex_map_type type; |
| typedef typename BOOST_CSR_GRAPH_TYPE::inherited_vertex_properties::const_vertex_map_type const_type; |
| }; |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| struct property_map<BOOST_CSR_GRAPH_TYPE, edge_bundle_t> |
| { |
| typedef typename BOOST_CSR_GRAPH_TYPE::forward_type::inherited_edge_properties::edge_map_type type; |
| typedef typename BOOST_CSR_GRAPH_TYPE::forward_type::inherited_edge_properties::const_edge_map_type const_type; |
| }; |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| inline typed_identity_property_map<Vertex> |
| get(vertex_index_t, const BOOST_CSR_GRAPH_TYPE&) |
| { |
| return typed_identity_property_map<Vertex>(); |
| } |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| inline Vertex |
| get(vertex_index_t, |
| const BOOST_CSR_GRAPH_TYPE&, Vertex v) |
| { |
| return v; |
| } |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| inline typename property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t>::const_type |
| get(edge_index_t, const BOOST_CSR_GRAPH_TYPE&) |
| { |
| typedef typename property_map<BOOST_CSR_GRAPH_TYPE, edge_index_t>::const_type |
| result_type; |
| return result_type(); |
| } |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| inline EdgeIndex |
| get(edge_index_t, const BOOST_CSR_GRAPH_TYPE&, |
| typename BOOST_CSR_GRAPH_TYPE::edge_descriptor e) |
| { |
| return e.idx; |
| } |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| inline typename property_map<BOOST_CSR_GRAPH_TYPE, vertex_bundle_t>::type |
| get(vertex_bundle_t, BOOST_CSR_GRAPH_TYPE& g) |
| { |
| return g.get_vertex_bundle(get(vertex_index, g)); |
| } |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| inline typename property_map<BOOST_CSR_GRAPH_TYPE, vertex_bundle_t>::const_type |
| get(vertex_bundle_t, const BOOST_CSR_GRAPH_TYPE& g) |
| { |
| return g.get_vertex_bundle(get(vertex_index, g)); |
| } |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| inline VertexProperty& |
| get(vertex_bundle_t, |
| BOOST_CSR_GRAPH_TYPE& g, Vertex v) |
| { |
| return get(vertex_bundle, g)[v]; |
| } |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| inline const VertexProperty& |
| get(vertex_bundle_t, |
| const BOOST_CSR_GRAPH_TYPE& g, Vertex v) |
| { |
| return get(vertex_bundle, g)[v]; |
| } |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| inline void |
| put(vertex_bundle_t, |
| BOOST_CSR_GRAPH_TYPE& g, |
| Vertex v, |
| const VertexProperty& val) |
| { |
| put(get(vertex_bundle, g), v, val); |
| } |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| inline typename property_map<BOOST_CSR_GRAPH_TYPE, edge_bundle_t>::type |
| get(edge_bundle_t, BOOST_CSR_GRAPH_TYPE& g) |
| { |
| return g.m_forward.get_edge_bundle(get(edge_index, g)); |
| } |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| inline typename property_map<BOOST_CSR_GRAPH_TYPE, edge_bundle_t>::const_type |
| get(edge_bundle_t, const BOOST_CSR_GRAPH_TYPE& g) |
| { |
| return g.m_forward.get_edge_bundle(get(edge_index, g)); |
| } |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| inline EdgeProperty& |
| get(edge_bundle_t, |
| BOOST_CSR_GRAPH_TYPE& g, |
| const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor& e) |
| { |
| return get(edge_bundle, g)[e]; |
| } |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| inline const EdgeProperty& |
| get(edge_bundle_t, |
| const BOOST_CSR_GRAPH_TYPE& g, |
| const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor& e) |
| { |
| return get(edge_bundle, g)[e]; |
| } |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS> |
| inline void |
| put(edge_bundle_t, |
| BOOST_CSR_GRAPH_TYPE& g, |
| const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor& e, |
| const EdgeProperty& val) |
| { |
| put(get(edge_bundle, g), e, val); |
| } |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename T, typename Bundle> |
| inline |
| typename property_map<BOOST_CSR_GRAPH_TYPE, T Bundle::*>::type |
| get(T Bundle::* p, BOOST_CSR_GRAPH_TYPE& g) |
| { |
| typedef typename property_map<BOOST_CSR_GRAPH_TYPE, |
| T Bundle::*>::type |
| result_type; |
| return result_type(&g, p); |
| } |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename T, typename Bundle> |
| inline |
| typename property_map<BOOST_CSR_GRAPH_TYPE, T Bundle::*>::const_type |
| get(T Bundle::* p, BOOST_CSR_GRAPH_TYPE const & g) |
| { |
| typedef typename property_map<BOOST_CSR_GRAPH_TYPE, |
| T Bundle::*>::const_type |
| result_type; |
| return result_type(&g, p); |
| } |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename T, typename Bundle, |
| typename Key> |
| inline T |
| get(T Bundle::* p, BOOST_CSR_GRAPH_TYPE const & g, |
| const Key& key) |
| { |
| return get(get(p, g), key); |
| } |
| |
| template<BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename T, typename Bundle, |
| typename Key> |
| inline void |
| put(T Bundle::* p, BOOST_CSR_GRAPH_TYPE& g, |
| const Key& key, const T& value) |
| { |
| put(get(p, g), key, value); |
| } |
| |
| #undef BOOST_CSR_GRAPH_TYPE |
| #undef BOOST_CSR_GRAPH_TEMPLATE_PARMS |
| #undef BOOST_DIR_CSR_GRAPH_TYPE |
| #undef BOOST_DIR_CSR_GRAPH_TEMPLATE_PARMS |
| #undef BOOST_BIDIR_CSR_GRAPH_TYPE |
| #undef BOOST_BIDIR_CSR_GRAPH_TEMPLATE_PARMS |
| |
| } // end namespace boost |
| |
| #endif // BOOST_GRAPH_COMPRESSED_SPARSE_ROW_GRAPH_HPP |