boost/graph/compressed_sparse_row_graph.hpp
// 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/utility/enable_if.hpp> #include <boost/graph/graph_selectors.hpp> #include <boost/graph/detail/is_distributed_selector.hpp> #include <boost/graph/properties.hpp> #include <boost/static_assert.hpp> #include <boost/functional/hash.hpp> #include <boost/next_prior.hpp> #include <boost/property_map/transform_value_property_map.hpp> #include <boost/mpl/print.hpp> 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; // Some tests to prevent use of "void" is a property type (as was done in // some test cases): BOOST_STATIC_ASSERT((!is_same< VertexProperty, void >::value)); BOOST_STATIC_ASSERT((!is_same< EdgeProperty, void >::value)); BOOST_STATIC_ASSERT((!is_same< GraphProperty, void >::value)); public: // For Property Graph typedef GraphProperty graph_property_type; typedef typename lookup_one_property< GraphProperty, graph_bundle_t >::type 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 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 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 GraphProperty graph_property_type; typedef typename lookup_one_property< GraphProperty, graph_bundle_t >::type 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); set_up_backward_property_links(); } // 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); set_up_backward_property_links(); } // 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); set_up_backward_property_links(); } 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.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::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 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 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 tag) { return get_property_value(g.m_property, tag); } template < typename G, typename Tag, typename Kind > struct csr_property_map_helper { }; // Kind == void for invalid property tags, so we can use that to SFINAE out template < BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag > struct csr_property_map_helper< BOOST_CSR_GRAPH_TYPE, Tag, vertex_property_tag > { typedef vertex_all_t all_tag; typedef typename property_traits< typename property_map< BOOST_CSR_GRAPH_TYPE, vertex_all_t >::type >::key_type key_type; typedef VertexProperty plist_type; typedef typename property_map< BOOST_CSR_GRAPH_TYPE, vertex_all_t >::type all_type; typedef typename property_map< BOOST_CSR_GRAPH_TYPE, vertex_all_t >::const_type all_const_type; typedef transform_value_property_map< detail::lookup_one_property_f< plist_type, Tag >, all_type > type; typedef transform_value_property_map< detail::lookup_one_property_f< const plist_type, Tag >, all_const_type > const_type; }; template < BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag > struct csr_property_map_helper< BOOST_CSR_GRAPH_TYPE, Tag, edge_property_tag > { typedef edge_all_t all_tag; typedef typename property_traits< typename property_map< BOOST_CSR_GRAPH_TYPE, edge_all_t >::type >::key_type key_type; typedef EdgeProperty plist_type; typedef typename property_map< BOOST_CSR_GRAPH_TYPE, edge_all_t >::type all_type; typedef typename property_map< BOOST_CSR_GRAPH_TYPE, edge_all_t >::const_type all_const_type; typedef transform_value_property_map< detail::lookup_one_property_f< plist_type, Tag >, all_type > type; typedef transform_value_property_map< detail::lookup_one_property_f< const plist_type, Tag >, all_const_type > const_type; }; template < BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag > struct csr_property_map_helper< BOOST_CSR_GRAPH_TYPE, Tag, graph_property_tag > { typedef graph_all_t all_tag; typedef BOOST_CSR_GRAPH_TYPE* key_type; typedef GraphProperty plist_type; typedef typename property_map< BOOST_CSR_GRAPH_TYPE, graph_all_t >::type all_type; typedef typename property_map< BOOST_CSR_GRAPH_TYPE, graph_all_t >::const_type all_const_type; typedef transform_value_property_map< detail::lookup_one_property_f< plist_type, Tag >, all_type > type; typedef transform_value_property_map< detail::lookup_one_property_f< const plist_type, Tag >, all_const_type > const_type; }; // disable_if isn't truly necessary but required to avoid ambiguity with // specializations below template < BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag > struct property_map< BOOST_CSR_GRAPH_TYPE, Tag, typename disable_if< detail::is_distributed_selector< Vertex > >::type > : csr_property_map_helper< BOOST_CSR_GRAPH_TYPE, Tag, typename detail::property_kind_from_graph< BOOST_CSR_GRAPH_TYPE, Tag >::type > { }; template < BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag > typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::type get( Tag tag, BOOST_CSR_GRAPH_TYPE& g) { return typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::type(tag, get(typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::all_tag(), g)); } template < BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag > typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::const_type get( Tag tag, const BOOST_CSR_GRAPH_TYPE& g) { return typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::const_type(tag, get(typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::all_tag(), g)); } template < BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag > typename property_traits< typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::type >::reference get(Tag tag, BOOST_CSR_GRAPH_TYPE& g, typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::key_type k) { typedef typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::all_tag all_tag; typedef typename property_map< BOOST_CSR_GRAPH_TYPE, all_tag >::type outer_pm; return lookup_one_property< typename property_traits< outer_pm >::value_type, Tag >::lookup(get(all_tag(), g, k), tag); } template < BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag > typename property_traits< typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::const_type >::reference get(Tag tag, const BOOST_CSR_GRAPH_TYPE& g, typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::key_type k) { typedef typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::all_tag all_tag; typedef typename property_map< BOOST_CSR_GRAPH_TYPE, all_tag >::const_type outer_pm; return lookup_one_property< const typename property_traits< outer_pm >::value_type, Tag >::lookup(get(all_tag(), g, k), tag); } template < BOOST_CSR_GRAPH_TEMPLATE_PARMS, typename Tag > void put(Tag tag, BOOST_CSR_GRAPH_TYPE& g, typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::key_type k, typename lookup_one_property< typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::plist_type, Tag >::type val) { typedef typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::all_tag all_tag; lookup_one_property< typename property_map< BOOST_CSR_GRAPH_TYPE, Tag >::plist_type, Tag >::lookup(get(all_tag(), g, k), tag) = val; } template < BOOST_CSR_GRAPH_TEMPLATE_PARMS > struct property_map< BOOST_CSR_GRAPH_TYPE, vertex_index_t, typename disable_if< detail::is_distributed_selector< Vertex > >::type > { 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, typename disable_if< detail::is_distributed_selector< Vertex > >::type > { 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_all_t, typename disable_if< detail::is_distributed_selector< Vertex > >::type > { 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_all_t, typename disable_if< detail::is_distributed_selector< Vertex > >::type > { 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 > struct property_map< BOOST_CSR_GRAPH_TYPE, graph_all_t, typename disable_if< detail::is_distributed_selector< Vertex > >::type > { typedef boost::ref_property_map< BOOST_CSR_GRAPH_TYPE*, typename BOOST_CSR_GRAPH_TYPE::graph_property_type > type; typedef boost::ref_property_map< BOOST_CSR_GRAPH_TYPE*, const typename BOOST_CSR_GRAPH_TYPE::graph_property_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 typed_identity_property_map< Vertex > get( vertex_index_t, BOOST_CSR_GRAPH_TYPE&) { return typed_identity_property_map< Vertex >(); } template < BOOST_CSR_GRAPH_TEMPLATE_PARMS > inline Vertex get(vertex_index_t, 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, edge_index_t >::const_type get(edge_index_t, 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, 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_all_t >::type get( vertex_all_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_all_t >::const_type get(vertex_all_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_all_t, BOOST_CSR_GRAPH_TYPE& g, Vertex v) { return get(vertex_all, g)[v]; } template < BOOST_CSR_GRAPH_TEMPLATE_PARMS > inline const VertexProperty& get( vertex_all_t, const BOOST_CSR_GRAPH_TYPE& g, Vertex v) { return get(vertex_all, g)[v]; } template < BOOST_CSR_GRAPH_TEMPLATE_PARMS > inline void put( vertex_all_t, BOOST_CSR_GRAPH_TYPE& g, Vertex v, const VertexProperty& val) { put(get(vertex_all, g), v, val); } template < BOOST_CSR_GRAPH_TEMPLATE_PARMS > inline typename property_map< BOOST_CSR_GRAPH_TYPE, edge_all_t >::type get( edge_all_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_all_t >::const_type get(edge_all_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_all_t, BOOST_CSR_GRAPH_TYPE& g, const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor& e) { return get(edge_all, g)[e]; } template < BOOST_CSR_GRAPH_TEMPLATE_PARMS > inline const EdgeProperty& get(edge_all_t, const BOOST_CSR_GRAPH_TYPE& g, const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor& e) { return get(edge_all, g)[e]; } template < BOOST_CSR_GRAPH_TEMPLATE_PARMS > inline void put(edge_all_t, BOOST_CSR_GRAPH_TYPE& g, const typename BOOST_CSR_GRAPH_TYPE::edge_descriptor& e, const EdgeProperty& val) { put(get(edge_all, g), e, val); } template < BOOST_CSR_GRAPH_TEMPLATE_PARMS > inline typename property_map< BOOST_CSR_GRAPH_TYPE, graph_all_t >::type get( graph_all_t, BOOST_CSR_GRAPH_TYPE& g) { return typename property_map< BOOST_CSR_GRAPH_TYPE, graph_all_t >::type( g.m_property); } template < BOOST_CSR_GRAPH_TEMPLATE_PARMS > inline typename property_map< BOOST_CSR_GRAPH_TYPE, graph_all_t >::const_type get(graph_all_t, const BOOST_CSR_GRAPH_TYPE& g) { return typename property_map< BOOST_CSR_GRAPH_TYPE, graph_all_t >::const_type( g.m_property); } template < BOOST_CSR_GRAPH_TEMPLATE_PARMS > inline GraphProperty& get( graph_all_t, BOOST_CSR_GRAPH_TYPE& g, BOOST_CSR_GRAPH_TYPE*) { return g.m_property; } template < BOOST_CSR_GRAPH_TEMPLATE_PARMS > inline const GraphProperty& get( graph_all_t, const BOOST_CSR_GRAPH_TYPE& g, BOOST_CSR_GRAPH_TYPE*) { return g.m_property; } template < BOOST_CSR_GRAPH_TEMPLATE_PARMS > inline void put(graph_all_t, BOOST_CSR_GRAPH_TYPE& g, BOOST_CSR_GRAPH_TYPE*, const GraphProperty& val) { g.m_property = val; } #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