This documentation is being rewritten. If something looks off, please cross-check with the Boost 1.91.0 Boost.Graph docs and open an issue.

adjacency_list_traits<EdgeList, VertexList, Directed>

Pre-declares the descriptor types of an adjacency_list before the adjacency_list itself is declared. Exists to break a chicken-and-egg compile error users hit exactly once — and then want to know about forever.

Defined in: <boost/graph/adjacency_list.hpp>

Why this class exists

Suppose you want an interior edge property whose value is a vertex_descriptor — say, storing a predecessor directly on each edge instead of maintaining an external predecessor map. The naive spelling

// This does NOT compile:
using Graph = adjacency_list<
    vecS, vecS, directedS,
    no_property,
    property<edge_name_t,
             graph_traits<Graph>::vertex_descriptor>>;  // Graph not yet defined

fails because graph_traits<Graph> cannot be instantiated until Graph is a complete type, but Graph cannot be completed until its property type is known. adjacency_list_traits exposes the descriptor types computed purely from the three selectors — no property types required — so it is fine to instantiate before the full graph type exists.

Example

// Demonstrates the "mutually recursive type" problem that
// adjacency_list_traits solves.
//
// We want an interior edge property whose value is a vertex_descriptor
// (for example, a pointer-to-predecessor stored on each edge). That
// requires the vertex_descriptor type to be known BEFORE we finish
// declaring the graph — which is impossible with graph_traits because
// graph_traits needs the full graph type.
//
// adjacency_list_traits<EdgeList, VertexList, Directed> exposes just
// vertex_descriptor / edge_descriptor without instantiating the full
// adjacency_list template, breaking the cycle.

#include <boost/graph/adjacency_list.hpp>
#include <iostream>

using namespace boost;

// Step 1: pre-declare the traits. Same selectors as the final graph.
using Traits = adjacency_list_traits<vecS, vecS, directedS>;

// Step 2: use Traits::vertex_descriptor as a property value type.
using Graph = adjacency_list<
    vecS, vecS, directedS,
    no_property,
    property<edge_name_t, Traits::vertex_descriptor>>;

int main() {
    Graph g(3);
    auto e01 = add_edge(0, 1, g).first;
    auto e12 = add_edge(1, 2, g).first;

    // Store the predecessor vertex on each edge.
    put(edge_name, g, e01, vertex(0, g));
    put(edge_name, g, e12, vertex(1, g));

    for (auto e : make_iterator_range(edges(g))) {
        std::cout << source(e, g) << " -> " << target(e, g)
                  << "  predecessor=" << get(edge_name, g, e) << '\n';
    }
}
0 -> 1  predecessor=0
1 -> 2  predecessor=1

Observe that Traits and the final Graph use the same three selectors (vecS, vecS, directedS). If they diverge, the descriptor types also diverge and the program is ill-formed.

For most use cases, an external predecessor map — std::vector<vertex_descriptor> wrapped in iterator_property_map — is simpler and every BGL algorithm already accepts one. Reach for adjacency_list_traits only when you genuinely need the property to travel with the graph (serialization, subgraph adaptors, mixing with GraphML I/O that round-trips interior properties, …).

Synopsis

namespace boost {

template <class EdgeList   = vecS,
          class VertexList = vecS,
          class Directed   = directedS>
struct adjacency_list_traits {
    typedef /* implementation-defined */ vertex_descriptor;
    typedef /* implementation-defined */ edge_descriptor;
    typedef /* implementation-defined */ directed_category;
    typedef /* implementation-defined */ edge_parallel_category;
};

} // namespace boost

Template parameters

Parameter Description Default

EdgeList

Selector for per-vertex edge-list storage (vecS, listS, setS, …).

vecS

VertexList

Selector for the vertex container storage.

vecS

Directed

directedS, undirectedS, or bidirectionalS.

directedS

Members

Member Description

vertex_descriptor

Same concrete type as graph_traits<adjacency_list<EdgeList, VertexList, Directed, …>>::vertex_descriptor, but available without naming the full graph type.

edge_descriptor

Likewise for edge descriptors.

directed_category

directed_tag, undirected_tag, or bidirectional_tag.

edge_parallel_category

Whether the chosen EdgeList stores parallel edges (allow_parallel_edge_tag) or collapses them (disallow_parallel_edge_tag).

Iterator and size types are not exposed here (they depend on the full graph type, which has not been declared yet). If you need them, use graph_traits<Graph> on the completed graph.

See also

Edit this Page