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.