`boost::adjacency_list`

(From https://www.boost.org/doc/libs/latest/libs/graph/doc/adjacency_list.html)

The main BGL component for representing graphs is the adjacency_list. This class generalizes the traditional adjacency-list representation for a graph. The graph is represented by a collection of vertices where, with each vertex, there is stored a collection of out-edges. The actual implementation of the collection of vertices and edges can vary to meet particular needs and is set through a container selector.

Prototype:

(Also, the serialization functionality is in boost/graph/adj_list_serialize.hpp.)

boost::adjacency_list<
  OutEdgeList = boost::vecS,
  VertexList = boost::vecS,
  Directed = boost::directedS,
  VertexProperties = boost::no_property,
  EdgeProperties = boost::no_property,
  GraphProperties = boost::no_property,
  EdgeList = listS
  >

...

To use ... you need to include boost/graph/adjacency_list.hpp:

#include <boost/graph/adjacency_list.hpp>

The adjacency_list class implements a generalized adjacency list graph structure. The template parameters provide many configuration options so that you can pick a version of the class that best meets your needs. An adjacency-list is basically a two-dimensional structure, where each element of the first dimension represents a vertex, and each of the vertices contains a one-dimensional structure that is its edge list.

The VertexList template parameter of the adjacency_list class controls what kind of container is used to represent the outer two-dimensional container. The OutEdgeList template parameter controls what kind of container is used to represent the edge lists. The choices for OutEdgeList and VertexList will determine the space complexity of the graph structure, and will determine the time complexity of the various graph operations. The possible choices and tradeoffs are discussed in Choosing the Edgelist and VertexList.

The Directed template parameter controls whether the graph is directed, undirected, or directed with access to both the in-edges and out-edges (which we call bidirectional). The bidirectional graph takes up twice the space (per edge) of a directed graph since each edge will appear in both an out-edge and in-edge list.

EdgeList and VertexList specify the classes used to store the vertex list and edge lists for the graph. These parameters allow tradeoffs between traversal speed and insertion/removal speed and tradeoffs in memory consumption. In addition, the EdgeList parameter determines whether parallel edges may be inserted into the graph.
Directed specifies whether the graph is directed, undirected, or bidirectional. By convention, a directed graph provides access to out-edges only, whereas a bidirectional graph provides access to in-edges as well as out-edges. These options are selected through directedS, undirectedS, and bidirectionalS
VertexProperties, EdgeProperties, and GraphProperties specify the property types that are attached to the vertices, edges, and to the graph itself. They default to no_property.

Choosing the `Edgelist` and `VertexList`

This section focuses on how to decide which version of the adjacency_list class to use in different situations. The adjacency_list is like a swiss-army knife in that it can be configured in many ways. The parameters that we will focus on in this section are OutEdgeList and VertexList, which control the underlying data structures that will be used to represent the graph. The choice of OutEdgeList and VertexList affects the time complexity of many of the graph operations and the space complexity of the graph object.

Push and Erase for the Edge List Container

One must also tell the adjacency_list how edges can be efficiently added and removed from the edge-list container. This is accomplished by overloading the push() and erase() functions for the custom container type. The push() function must return an iterator pointing to the newly inserted element and a bool flag saying whether the edge was inserted. The following default push() and erase() functions are already supplied for all STL container types. The family of push_dispatch() and erase_dispatch() function overloads handle the various ways inserting and erasing can be done with standard containers.

template <class Container, class T>
  std::pair<typename Container::iterator, bool>
  push(Container& c, const T& v)
  {
    return push_dispatch(c, v, container_category(c));
  }

  template <class Container, class T>
  void erase(Container& c, const T& x)
  {
    erase_dispatch(c, x, container_category(c));
  }