// 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 |