All examples in this chapter so far have used `boost::adjacency_list`

to define graphs. This section introduces the two other graph containers provided by Boost.Graph: `boost::adjacency_matrix`

and `boost::compressed_sparse_row_graph`

.

There is a missing include in `boost/graph/adjacency_matrix.hpp`

in Boost 1.56.0. To compile Example 31.15 with Boost 1.56.0, include `boost/functional/hash.hpp`

before `boost/graph/adjacency_matrix.hpp`

.

Example 31.15. Graphs with

`boost::adjacency_matrix`

```
#include <boost/graph/adjacency_matrix.hpp>
#include <array>
#include <utility>
int main()
{
enum { topLeft, topRight, bottomRight, bottomLeft };
std::array<std::pair<int, int>, 4> edges{{
std::make_pair(topLeft, topRight),
std::make_pair(topRight, bottomRight),
std::make_pair(bottomRight, bottomLeft),
std::make_pair(bottomLeft, topLeft)
}};
typedef boost::adjacency_matrix<boost::undirectedS> graph;
graph g{edges.begin(), edges.end(), 4};
}
```

`boost::adjacency_matrix`

is used like `boost::adjacency_list`

(see Example 31.15). However, the two template parameters that pass selectors don’t exist with `boost::adjacency_matrix`

. With `boost::adjacency_matrix`

, no selectors, such as `boost::vecS`

and `boost::setS`

, are used. `boost::adjacency_matrix`

stores the graph in a matrix, and the internal structure is hardcoded. You can think of the matrix as a two-dimensional table: the table is a square with as many rows and columns as the graph has points. A line is created by marking the cell where the row and column that correspond with the two end points of the line intersect.

The internal structure of `boost::adjacency_matrix`

makes it possible to add and remove lines quickly. However, memory consumption is higher. The rule of thumb is to use `boost::adjacency_list`

when there are relatively few lines compared to points. The more lines there are, the more it makes sense to use `boost::adjacency_matrix`

.

Example 31.16. Graphs with

`boost::compressed_sparse_row_graph`

```
#include <boost/graph/compressed_sparse_row_graph.hpp>
#include <array>
#include <utility>
int main()
{
enum { topLeft, topRight, bottomRight, bottomLeft };
std::array<std::pair<int, int>, 4> edges{{
std::make_pair(topLeft, topRight),
std::make_pair(topRight, bottomRight),
std::make_pair(bottomRight, bottomLeft),
std::make_pair(bottomLeft, topLeft)
}};
typedef boost::compressed_sparse_row_graph<boost::bidirectionalS> graph;
graph g{boost::edges_are_unsorted_multi_pass, edges.begin(),
edges.end(), 4};
}
```

`boost::compressed_sparse_row_graph`

is used in the same way as `boost::adjacency_list`

and `boost::adjacency_matrix`

(see Example 31.16). The most important difference is that graphs can’t be changed with `boost::compressed_sparse_row_graph`

. Once the graph has been created, points and lines can’t be added or removed. Thus, `boost::compressed_sparse_row_graph`

makes only sense when using an immutable graph.

`boost::compressed_sparse_row_graph`

only supports directed lines. You can’t instantiate `boost::compressed_sparse_row_graph`

with the template parameter `boost::undirectedS`

.

The main advantage of `boost::compressed_sparse_row_graph`

is low memory consumption. `boost::compressed_sparse_row_graph`

is especially useful if you have a huge graph and you need to keep memory consumption low.