Containers

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.

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

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