...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
The class template compressed_sparse_row_graph
is
a graph class that uses the compact Compressed Sparse Row (CSR)
format to store directed (and bidirectional) graphs. While CSR graphs have
much less
overhead than many other graph formats (e.g., adjacency_list
), they
do not provide any mutability: one cannot add or remove vertices
or edges from a CSR graph. Use this format in high-performance
applications or for very large graphs that you do not need to
change.
The CSR format stores vertices and edges in separate arrays, with the indices into these arrays corresponding to the identifier for the vertex or edge, respectively. The edge array is sorted by the source of each edge, but contains only the targets for the edges. The vertex array stores offsets into the edge array, providing the offset of the first edge outgoing from each vertex. Iteration over the out-edges for the ith vertex in the graph is achieved by visiting edge_array[vertex_array[i]], edge_array[vertex_array[i]+1], ..., edge_array[vertex_array[i+1]]. This format minimizes memory use to O(n + m), where n and m are the number of vertices and edges, respectively. The constants multiplied by n and m are based on the size of the integers needed to represent indices into the edge and vertex arrays, respectively, which can be controlled using the template parameters. The Directed template parameter controls whether one edge direction (the default) or both directions are stored. A directed CSR graph has Directed = directedS and a bidirectional CSR graph (with a limited set of constructors) has Directed = bidirectionalS.
namespace boost { 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 { public: // Graph constructors compressed_sparse_row_graph(); // Unsorted edge list constructors 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()); 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()); 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()); 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()); // New sorted edge list constructors (directed only) 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()); 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()); // In-place unsorted edge list constructors (directed only) template<typename InputIterator> 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()); template<typename InputIterator> compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t, std::vector<vertex_descriptor>& sources, std::vector<vertex_descriptor>& targets, std::vector<EdgeProperty>& edge_props, vertices_size_type numverts, const GraphProperty& prop = GraphProperty()); // Miscellaneous constructors (directed only) template<typename Graph, typename VertexIndexMap> compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi, vertices_size_type numverts, edges_size_type numedges); template<typename Graph, typename VertexIndexMap> compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi); template<typename Graph> explicit compressed_sparse_row_graph(const Graph& g); // Graph mutators (directed only) template<typename Graph, typename VertexIndexMap> void assign(const Graph& g, const VertexIndexMap& vi, vertices_size_type numverts, edges_size_type numedges); template<typename Graph, typename VertexIndexMap> void assign(const Graph& g, const VertexIndexMap& vi); template<typename Graph> void assign(const Graph& g); // Property Access VertexProperty& operator[](vertex_descriptor v); const VertexProperty& operator[](vertex_descriptor v) const; EdgeProperty& operator[](edge_descriptor v); const EdgeProperty& operator[](edge_descriptor v) const; }; // Incidence Graph requirements vertex_descriptor source(edge_descriptor, const compressed_sparse_row_graph&); vertex_descriptor target(edge_descriptor, const compressed_sparse_row_graph&); std::pair<out_edge_iterator, out_edge_iterator> out_edges(vertex_descriptor, const compressed_sparse_row_graph&); degree_size_type out_degree(vertex_descriptor v, const compressed_sparse_row_graph&); // Bidirectional Graph requirements (bidirectional only) std::pair<in_edge_iterator, in_edge_iterator> in_edges(vertex_descriptor, const compressed_sparse_row_graph&); degree_size_type in_degree(vertex_descriptor v, const compressed_sparse_row_graph&); // Adjacency Graph requirements std::pair<adjacency_iterator, adjacency_iterator> adjacent_vertices(vertex_descriptor, const compressed_sparse_row_graph&); // Vertex List Graph requirements std::pair<vertex_iterator, vertex_iterator> vertices(const compressed_sparse_row_graph&); vertices_size_type num_vertices(const compressed_sparse_row_graph&); // Edge List Graph requirements std::pair<edge_iterator, edge_iterator> edges(const compressed_sparse_row_graph&); edges_size_type num_edges(const compressed_sparse_row_graph&); // Vertex access vertex_descriptor vertex(vertices_size_type i, const compressed_sparse_row_graph&); // Edge access std::pair<edge_descriptor, bool> edge(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&); edge_descriptor edge_from_index(edges_size_type i, const compressed_sparse_row_graph&); // Property map accessors template<typename PropertyTag> property_map<compressed_sparse_row_graph, PropertyTag>::type get(PropertyTag, compressed_sparse_row_graph& g) template<typename PropertyTag> property_map<compressed_sparse_row_graph, Tag>::const_type get(PropertyTag, const compressed_sparse_row_graph& g) template<typename PropertyTag, class X> typename property_traits<property_map<compressed_sparse_row_graph, PropertyTag>::const_type>::value_type get(PropertyTag, const compressed_sparse_row_graph& g, X x) template<typename PropertyTag, class X, class Value> void put(PropertyTag, const compressed_sparse_row_graph& g, X x, const Value& value); template<typename GraphPropertyTag> typename graph_property<compressed_sparse_row_graph, GraphPropertyTag>::type& get_property(compressed_sparse_row_graph& g, GraphPropertyTag); template<typename GraphPropertyTag> typename graph_property<compressed_sparse_row_graph, GraphPropertyTag>::type const & get_property(const compressed_sparse_row_graph& g, GraphPropertyTag); template<typename GraphPropertyTag> void set_property(const compressed_sparse_row_graph& g, GraphPropertyTag, const typename graph_property<compressed_sparse_row_graph, GraphPropertyTag>::type& value); // Incremental construction functions (directed only) template<typename InputIterator, typename Graph> void add_edges(InputIterator first, InputIterator last, compressed_sparse_row_graph& g); (directed only) template<typename InputIterator, typename EPIter, typename Graph> void add_edges(InputIterator first, InputIterator last, EPIter ep_first, EPIter ep_last, compressed_sparse_row_graph& g); (directed only) template<typename BidirectionalIterator, typename Graph> void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, compressed_sparse_row_graph& g); (directed only) template<typename BidirectionalIterator, typename EPIter, typename Graph> void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, EPIter ep_iter, compressed_sparse_row_graph& g); } // end namespace boost
<boost/graph/compressed_sparse_row_graph.hpp>
The compressed_sparse_row_graph class template models (i.e., implements the requirements of) many of the BGL graph concepts, allowing it to be used with most of the BGL algorithms. In particular, it models the following specific graph concepts:
The compressed_sparse_row_graph class has several template parameters that can customize the layout in memory and what properties are attached to the graph itself. All parameters have defaults, so users interested only in the structure of a graph can use the type compressed_sparse_row_graph<> and ignore the parameters.
ParametersDirected
A selector that determines whether the graph will be directed, bidirectional or undirected. At this time, the CSR graph type only supports directed and bidirectional graphs, so this value must be eitherboost::directedS
orboost::bidirectionalS
.
Default:boost::directedS
VertexProperty
A class type that will be attached to each vertex in the graph. If this value isvoid
, no properties will be attached to the vertices of the graph.
Default:void
EdgeProperty
A class type that will be attached to each edge in the graph. If this value isvoid
, no properties will be attached to the edges of the graph.
Default:void
GraphProperty
A nested set ofproperty
templates that describe the properties of the graph itself. If this value isno_property
, no properties will be attached to the graph.
Default:no_property
Vertex
An unsigned integral type that will be used as both the index into the array of vertices and as the vertex descriptor itself. Larger types permit the CSR graph to store more vertices; smaller types reduce the storage required per vertex.
Default:std::size_t
EdgeIndex
An unsigned integral type that will be used as the index into the array of edges. As with theVertex
parameter, larger types permit more edges whereas smaller types reduce the amount of storage needed per edge. TheEdgeIndex
type shall not be smaller than theVertex
type, but it may be larger. For instance,Vertex
may be a 16-bit integer (allowing 32,767 vertices in the graph) whereasEdgeIndex
could then be a 32-bit integer to allow a complete graph to be stored in the CSR format.
Default:Vertex
The compressed_sparse_row_graph allows properties to be attached to its vertices, edges, or to the graph itself by way of its template parameters. These properties may be accessed via the member and non-member property access functions, using the bundled properties scheme.
The CSR graph provides two kinds of built-in properties: vertex_index, which maps from vertices to values in [0, n) and edge_index, which maps from edges to values in [0, m), where n and m are the number of vertices and edges in the graph, respectively.
compressed_sparse_row_graph();
Constructs a graph with no vertices or edges.
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());
Constructs a graph with numverts
vertices whose
edges are specified by the iterator range [edge_begin,
edge_end)
. The InputIterator must be a model of
InputIterator
whose value_type
is an std::pair
of
integer values. These integer values are the source and target
vertices for the edges, and must fall within the range [0,
numverts)
. The edges in [edge_begin,
edge_end)
do not need to be sorted. This constructor uses extra
memory to save the edge information before adding it to the graph,
avoiding the requirement for the iterator to have multi-pass capability.
The value prop
will be used to initialize the graph
property.
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());
This constructor constructs a graph with numverts
vertices and the edges provided in the iterator range
[edge_begin, edge_end)
. Its semantics are identical
to the edge range constructor, except
that edge properties are also initialized. The type
EdgePropertyIterator must be a model of the InputIterator
concept whose value_type is convertible to
EdgeProperty. The iterator range [ep_iter, ep_ter +
m) will be used to initialize the properties on the edges
of the graph, where m is distance from
edge_begin to edge_end. This constructor uses extra
memory to save the edge information before adding it to the graph,
avoiding the requirement for the iterator to have multi-pass capability.
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());
Constructs a graph with numverts
vertices whose
edges are specified by the iterator range [edge_begin,
edge_end)
. The MultiPassInputIterator must be a model of
MultiPassInputIterator
whose value_type
is an std::pair
of
integer values. These integer values are the source and target
vertices for the edges, and must fall within the range [0,
numverts)
. The edges in [edge_begin,
edge_end)
do not need to be sorted. Multiple passes will be made
over the edge range.
The value prop
will be used to initialize the graph
property.
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());
This constructor constructs a graph with numverts
vertices and the edges provided in the iterator range
[edge_begin, edge_end)
. Its semantics are identical
to the edge range constructor, except
that edge properties are also initialized. The type
EdgePropertyIterator must be a model of the MultiPassInputIterator
concept whose value_type is convertible to
EdgeProperty. The iterator range [ep_iter, ep_ter +
m) will be used to initialize the properties on the edges
of the graph, where m is distance from
edge_begin to edge_end. Multiple passes will be made
over the edge and property ranges.
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());
Constructs a graph with numverts
vertices whose
edges are specified by the iterator range [edge_begin,
edge_end)
. The argument of type edges_are_sorted_t
is
a tag used to distinguish this constructor; the value
edges_are_sorted
can be used to initialize this parameter.
The InputIterator must be a model of
InputIterator
whose value_type
is an std::pair
of
integer values. These integer values are the source and target
vertices for the edges, and must fall within the range [0,
numverts)
. The edges in [edge_begin,
edge_end)
must be sorted so that all edges originating
from vertex i preceed any edges originating from all
vertices j where j > i.
The value numedges
, if provided, tells how many
edges are in the range [edge_begin, edge_end)
and
will be used to preallocate data structures to save both memory
and time during construction.
The value prop
will be used to initialize the graph
property.
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());
This constructor constructs a graph with numverts
vertices and the edges provided in the iterator range
[edge_begin, edge_end)
. Its semantics are identical
to the edge range constructor, except
that edge properties are also initialized. The type
EdgePropertyIterator must be a model of the InputIterator
concept whose value_type is convertible to
EdgeProperty. The iterator range [ep_iter, ep_ter +
m) will be used to initialize the properties on the edges
of the graph, where m is distance from
edge_begin to edge_end.
template<typename InputIterator> 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());
This constructor constructs a graph with numverts
vertices
and the edges provided in the two vectors sources
and
targets
. The two vectors are mutated in-place to sort them
by source vertex. They are returned with unspecified values, but do not
share storage with the constructed graph (and so are safe to destroy).
The parameter prop
, if provided, is used to initialize the
graph property.
template<typename InputIterator> compressed_sparse_row_graph(construct_inplace_from_sources_and_targets_t, std::vector<vertex_descriptor>& sources, std::vector<vertex_descriptor>& targets, std::vector<EdgeProperty>& edge_props, vertices_size_type numverts, const GraphProperty& prop = GraphProperty());
This constructor constructs a graph with numverts
vertices
and the edges provided in the two vectors sources
and
targets
. Edge properties are initialized from the vector
edge_props
. The three vectors are mutated in-place to sort
them by source vertex. They are returned with unspecified values, but do
not share storage with the constructed graph (and so are safe to
destroy). The parameter prop
, if provided, is used to
initialize the graph property.
template<typename Graph, typename VertexIndexMap> compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi, vertices_size_type numverts, edges_size_type numedges); template<typename Graph, typename VertexIndexMap> compressed_sparse_row_graph(const Graph& g, const VertexIndexMap& vi); template<typename Graph> explicit compressed_sparse_row_graph(const Graph& g);
Calls the assign function with all of the arguments it is given.
template<typename Graph, typename VertexIndexMap> void assign(const Graph& g, const VertexIndexMap& vi, vertices_size_type numverts, edges_size_type numedges); template<typename Graph, typename VertexIndexMap> void assign(const Graph& g, const VertexIndexMap& vi); template<typename Graph> void assign(const Graph& g);
Clears the CSR graph and builds a CSR graph in place from the
structure of another graph. The graph type Graph must
be a model of IncidenceGraph.
Parameters
VertexProperty& operator[](vertex_descriptor v); const VertexProperty& operator[](vertex_descriptor v) const;
Retrieves the property value associated with vertex v. Only valid when VertexProperty is a class type that is not no_property.
EdgeProperty& operator[](edge_descriptor v); const EdgeProperty& operator[](edge_descriptor v) const;
Retrieves the property value associated with edge v. Only valid when EdgeProperty is a class type that is not no_property.
vertex_descriptor vertex(vertices_size_type i, const compressed_sparse_row_graph&);
Retrieves the ith vertex in the graph in constant time.
std::pair<edge_descriptor, bool> edge(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&);
If there exists an edge (u, v) in the graph, returns the descriptor for that edge and true; otherwise, the second value in the pair will be false. If multiple edges exist from u to v, the first edge will be returned; use out_edges and a conditional statement to retrieve all edges to a given target. This function requires linear time in the number of edges outgoing from u.
edge_descriptor edge_from_index(edges_size_type i, const compressed_sparse_row_graph&);
Returns the ith edge in the graph. This operation requires logarithmic time in the number of vertices.
template<typename PropertyTag> property_map<compressed_sparse_row_graph, PropertyTag>::type get(PropertyTag, compressed_sparse_row_graph& g) template<typename PropertyTag> property_map<compressed_sparse_row_graph, Tag>::const_type get(PropertyTag, const compressed_sparse_row_graph& g)
Returns the property map object for the vertex property specified by PropertyTag. The PropertyTag must be a member pointer to access one of the fields in VertexProperty or EdgeProperty.
template<typename PropertyTag, class X> typename property_traits<property_map<compressed_sparse_row_graph, PropertyTag>::const_type>::value_type get(PropertyTag, const compressed_sparse_row_graph& g, X x)
This returns the property value for x, where x is either a vertex or edge descriptor.
template<typename PropertyTag, class X, class Value> void put(PropertyTag, const compressed_sparse_row_graph& g, X x, const Value& value);
This sets the property value for x to value. x is either a vertex or edge descriptor. Value must be convertible to typename property_traits<property_map<compressed_sparse_row_graph, PropertyTag>::type>::value_type
template<typename GraphPropertyTag> typename graph_property<compressed_sparse_row_graph, GraphPropertyTag>::type& get_property(compressed_sparse_row_graph& g, GraphPropertyTag); template<typename GraphPropertyTag> typename graph_property<compressed_sparse_row_graph, GraphPropertyTag>::type const & get_property(const compressed_sparse_row_graph& g, GraphPropertyTag);
Return the property specified by GraphPropertyTag that is attached to the graph object g.
template<typename GraphPropertyTag> void set_property(const compressed_sparse_row_graph& g, GraphPropertyTag, const typename graph_property<compressed_sparse_row_graph, GraphPropertyTag>::type& value);
Set the property specified by GraphPropertyTag that is attached to the graph object g.
template<typename InputIterator> void add_edges(InputIterator first, InputIterator last, compressed_sparse_row_graph& g)
Add a range of edges (from first to last) to the graph.
The InputIterator must be a model of InputIterator
whose value_type
is an std::pair
of integer
values. These integer values are the source and target vertices of the
new edges. The edges do not need to be sorted.
template<typename InputIterator, typename EPIter> void add_edges(InputIterator first, InputIterator last, EPIter ep_first, EPIter ep_last, compressed_sparse_row_graph& g)
Add a range of edges (from first to last) with
corresponding edge properties (from ep_first to
ep_last) to the graph. The InputIterator and
EPIter must be models of InputIterator;
the value_type
of InputIterator must be an
std::pair
of integer values, and the value_type
of EPIter must be the edge property type of the graph. The
integer values produced by the InputIterator are the source and
target vertices of the new edges. The edges do not need to be sorted.
template<typename BidirectionalIterator> void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, compressed_sparse_row_graph& g)
Add a range of edges (from first to last) to the graph.
The BidirectionalIterator must be a model of BidirectionalIterator
whose value_type
is an std::pair
of integer
values. These integer values are the source and target vertices of the
new edges. The edges must be sorted in increasing order by source vertex
index.
template<typename BidirectionalIterator, typename EPIter> void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, EPIter ep_iter, compressed_sparse_row_graph& g)
Add a range of edges (from first to last) to the graph.
The BidirectionalIterator and EPIter must be models of
BidirectionalIterator.
The value_type
of the BidirectionalIterator must be
an std::pair
of integer
values. These integer values are the source and target vertices of the
new edges.
The value_type
of the EPIter must be the edge
property type of the graph.
The edges must be sorted in increasing order by source vertex
index.
We will use the compressed_sparse_row_graph graph class to store a simple Web graph. In this web graph the vertices represent web pages and the edges represent links from one web page to another. With each web page we want to associate a URL, so we initially create a WebPage class that stores the URL. Then we can create our graph type by providing WebPage as a parameter to the compressed_sparse_row_graph class template.
class WebPage { public: std::string url; }; // ... typedef compressed_sparse_row_graph<directedS, WebPage> WebGraph; WebGraph g(&the_edges[0], &the_edges[0] + sizeof(the_edges)/sizeof(E), 6);
We can then set the properties on the vertices of the graph using the bundled properties syntax, and display the edges for the user.
// Set the URLs of each vertex int index = 0; BGL_FORALL_VERTICES(v, g, WebGraph) g[v].url = urls[index++]; // Output each of the links std::cout << "The web graph:" << std::endl; BGL_FORALL_EDGES(e, g, WebGraph) std::cout << " " << g[source(e, g)].url << " -> " << g[target(e, g)].url << std::endl;
See the complete example source for other operations one can perform with a compressed_sparse_row_graph.
Copyright © 2005 |
Doug Gregor, Indiana University () Jeremiah Willcock, Indiana University () Andrew Lumsdaine, Indiana University () |