# Compressed Sparse Row Graph

The class template `compressed_sparse_row_graph` is a graph class that uses the compact Compressed Sparse Row (CSR) format to store directed 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.

There are two interfaces to the compressed sparse row graph. The old interface requires that all out edges from a single vertex are sorted by target, and does not support construction of the graph from unsorted arrays of sources and targets. The new interface has these new constructors, but does not support incremental construction of the graph or the `edge_range()` and `edge()` functions. The old interface is the default, but will be removed in a later version of Boost. To select the new interface, add `#define BOOST_GRAPH_USE_NEW_CSR_INTERFACE` before including `<boost/graph/compressed_sparse_row_graph.hpp>`.

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.

- Synopsis
- Where Defined
- Models
- Template parameters
- Properties
- Member functions
  - Constructors
  - Mutators
  - Property access
- Non-member functions
  - Vertex access
  - Edge access
  - Property map accessors
  - Incremental construction functions
- Example

## Synopsis

    namespace boost {

    template<typename Directed = directedS, typename VertexProperty = void,
             typename EdgeProperty = void, 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 (new interface only)
      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());

      // Old sorted edge list constructors (old interface only)
      template<typename InputIterator>
      compressed_sparse_row_graph(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(InputIterator edge_begin, InputIterator edge_end,
                                  EdgePropertyIterator ep_iter,
                                  vertices_size_type numverts,
                                  edges_size_type numedges = 0,
                                  const GraphProperty& prop = GraphProperty());

      // New sorted edge list constructors (both interfaces)
      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 (new interface 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 (both interfaces)
      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 (both interfaces)
      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 (both interfaces)
      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 (both interfaces)
    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&);

    // Adjacency Graph requirements (both interfaces)
    std::pair<adjacency_iterator, adjacency_iterator>
      adjacent_vertices(vertex_descriptor, const compressed_sparse_row_graph&);

    // Vertex List Graph requirements (both interfaces)
    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 (both interfaces)
    std::pair<edge_iterator, edge_iterator> edges(const compressed_sparse_row_graph&);
    edges_size_type num_edges(const compressed_sparse_row_graph&);

    // Vertex access (both interfaces)
    vertex_descriptor vertex(vertices_size_type i, const compressed_sparse_row_graph&);

    // Edge access
    (old interface only)
    std::pair<out_edge_iterator, out_edge_iterator>
      edge_range(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&);
    (old interface only)
    std::pair<edge_descriptor, bool>
      edge(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&);
    (both interfaces)
    edge_descriptor edge_from_index(edges_size_type i, const compressed_sparse_row_graph&);

    // Property map accessors (both interfaces)
    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
    (old interface only)
    template<typename Graph>
    vertex_descriptor add_vertex(compressed_sparse_row_graph& g);

    (old interface only)
    template<typename Graph>
    vertex_descriptor add_vertices(vertices_size_type count, compressed_sparse_row_graph& g);

    (old interface only)
    template<typename Graph>
    edge_descriptor add_edge(vertex_descriptor src, vertex_descriptor tgt, compressed_sparse_row_graph& g);

    (new interface only)
    template<typename InputIterator, typename Graph>
    void add_edges(InputIterator first, InputIterator last, compressed_sparse_row_graph& g);

    (new interface 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);

    (new interface only)
    template<typename BidirectionalIterator, typename Graph>
    void add_edges_sorted(BidirectionalIterator first, BidirectionalIterator last, compressed_sparse_row_graph& g);

    (new interface 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

## Where Defined

`<boost/graph/compressed_sparse_row_graph.hpp>`

## Models

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:

- Graph
- IncidenceGraph
- AdjacencyGraph
- VertexListGraph
- EdgeListGraph
- PropertyGraph

## Template Parameters

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.

Parameters
`Directed`

> A selector that determines whether the graph will be directed, bidirectional or undirected. At this time, the CSR graph type only supports directed graphs, so this value must be `boost::directedS`.
> Default: `boost::directedS`

`VertexProperty`

> A class type that will be attached to each vertex in the graph. If this value is `void`, 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 is `void`, no properties will be attached to the edges of the graph.
> Default: `void`

`GraphProperty`

> A nested set of `property` templates that describe the properties of the graph itself. If this value is `no_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 the `Vertex` parameter, larger types permit more edges whereas smaller types reduce the amount of storage needed per edge. The `EdgeIndex` type shall not be smaller than the `Vertex` type, but it may be larger. For instance, `Vertex` may be a 16-bit integer (allowing 32,767 vertices in the graph) whereas `EdgeIndex` could then be a 32-bit integer to allow a complete graph to be stored in the CSR format.
> Default: `Vertex`

## Interior Properties

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.

## Member Functions

### Constructors

      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. (This function is only provided by the new interface.)

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. (This function is only provided by the new interface.)

      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. (This function is only provided by the new interface.)

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. (This function is only provided by the 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());

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 version of this constructor without the `edges_are_sorted` tag is deprecated and only provided by the old interface.)

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`. (The version of this constructor without the `edges_are_sorted` tag is deprecated and only provided by the old interface.)

      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. (This function is only provided by the new interface.)

      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. (This function is only provided by the new interface.)

      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.

### Mutators

      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 and have a `vertex(i, g)` function that retrieves the ith vertex in the graph.
Parameters

- `g`: The incoming graph.
- `vi`: A map from vertices to indices. If not provided, `get(vertex_index, g)` will be used.
- `numverts`: The number of vertices in the graph `g`. If not provided, `Graph` must be a model of VertexListGraph.
- `numedges`: The number of edges in the graph `g`. If not provided, `Graph` must be a model of EdgeListGraph.

### Property Access

      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`.

## Non-member Functions

### Vertex access

      vertex_descriptor vertex(vertices_size_type i, const compressed_sparse_row_graph&);

Retrieves the ith vertex in the graph in constant time.

### Edge access

      std::pair<out_edge_iterator, out_edge_iterator>
        edge_range(vertex_descriptor u, vertex_descriptor v, const compressed_sparse_row_graph&);

Returns all edges from `u` to `v`. Requires time linear in the number of edges outgoing from `u`. (This function is only provided by the old interface.)

      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 `edge_range` to retrieve all edges. (This function is only provided by the old interface.)

      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.

### 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)

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`.

### Incremental construction functions

    vertex_descriptor add_vertex(compressed_sparse_row_graph& g)

Add a new vertex to the end of the graph `g`, and return a descriptor for that vertex. The new vertex will be greater than any of the previous vertices in `g`. (This function is only provided by the old interface.)

    vertex_descriptor add_vertices(vertices_size_type count, compressed_sparse_row_graph& g)

Add `count` new vertices to the end of the graph `g`, and return a descriptor for the smallest new vertex. The new vertices will be greater than any of the previous vertices in `g`. (This function is only provided by the old interface.)

    edge_descriptor add_edge(vertex_descriptor src, vertex_descriptor tgt, compressed_sparse_row_graph& g)

Add a new edge from `src` to `tgt` in the graph `g`, and return a descriptor for it. There must not be an edge in `g` whose source vertex is greater than `src`. If the vertex `src` has out edges before this operation is called, there must be none whose target is larger than `tgt`. (This function is only provided by the old interface.)

    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. (This function is only provided by the new interface.)

    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. (This function is only provided by the new interface.)

    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. (This function is only provided by the new interface.)

    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. (This function is only provided by the new interface.)

## Example

[libs/graph/example/csr-example.cpp]

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 ( )