Frequently Asked Questions

Graph construction

Which container selectors (`vecS`, `listS`, `setS`) should I pick?

Selector Storage Stable? Notes

Selector	Storage	Stable?	Notes
`vecS`	vector	No	Fast iteration; parallel edges allowed
`listS`	list	Yes	`O(E)` lookup; parallel edges allowed
`setS`	tree	Yes (edges)	`O(log E)` lookup; no parallel edges

vecS

vector

Fast iteration; parallel edges allowed

listS

list

Yes

O(E) lookup; parallel edges allowed

setS

tree

Yes (edges)

O(log E) lookup; no parallel edges

Rule of thumb: vecS on both slots unless you are actively removing vertices (then listS on the vertex slot) or need deduplicated out-edges (setS on the edge slot).

Can I use a `std::vector<std::list<…>>` as a graph?

Yes. Include <boost/graph/vector_as_graph.hpp> and the container models the BGL incidence and vertex-list concepts as-is. The vertex descriptor is the outer-vector index; each inner-list element is an integer edge target.

#include <boost/graph/vector_as_graph.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <iostream>
#include <list>
#include <vector>

int main() {
    using namespace boost;
    std::vector<std::list<int>> g(4);
    g[0].push_back(1); g[0].push_back(2);
    g[1].push_back(3);
    g[2].push_back(3);

    std::cout << "V = " << num_vertices(g) << "\n";
    for (std::size_t u = 0; u < g.size(); ++u)
        for (int v : g[u])
            std::cout << "  " << u << " -> " << v << "\n";
}

V = 4
  0 -> 1
  0 -> 2
  1 -> 3
  2 -> 3

Properties

Bundled or internal (tag-based) properties: which should I use?

Bundled. The syntax is shorter, the runtime cost is identical, and the modern algorithms accept get(&Bundle::field, g) wherever they accept a property map. Use interior tags only when an algorithm hard-codes one (for example edge_capacity_t for the DIMACS flow readers). Full comparison on the Bundled Properties page.

I get `error_property_not_found`. What does it mean?

error: no match for
`boost::detail::error_property_not_found & ==
 boost::detail::error_property_not_found &'

The algorithm expected a named property (weight, color, vertex_index, …) on the graph and did not find it. Add the property as a field on your bundle and pass it explicitly via the named-parameter API (weight_map(…), color_map(…), vertex_index_map(…), …).

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

using namespace boost;
struct Edge { int weight; };
using Graph = adjacency_list<vecS, vecS, directedS, no_property, Edge>;

int main() {
    Graph g(3);
    add_edge(0, 1, Edge{5}, g);
    add_edge(1, 2, Edge{3}, g);
    add_edge(0, 2, Edge{9}, g);

    std::vector<int> d(num_vertices(g));
    // Graph has no edge_weight_t tag; pass the bundled field as the weight map.
    dijkstra_shortest_paths(g, 0,
        weight_map(get(&Edge::weight, g))
            .distance_map(make_iterator_property_map(
                d.begin(), get(vertex_index, g))));

    std::cout << "shortest distance 0 -> 2 = " << d[2] << "\n";
}

shortest distance 0 -> 2 = 8

Where is `boost/property_map.hpp`?

Moved a long time ago. Include boost/property_map/property_map.hpp.

Mutating a graph

How do I remove a vertex from an `adjacency_list`?

Call clear_vertex first, then remove_vertex. remove_vertex does not touch incident edges; calling it on a vertex that still has edges leaves dangling edge descriptors and will eventually segfault.

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

int main() {
    using namespace boost;
    using Graph = adjacency_list<listS, listS, undirectedS>;
    Graph g(3);
    auto it = vertices(g).first;
    auto a = *it, b = *++it, c = *++it;
    add_edge(a, b, g);
    add_edge(b, c, g);
    add_edge(a, c, g);

    std::cout << "before: " << num_vertices(g) << " vertices, "
              << num_edges(g) << " edges\n";

    clear_vertex(b, g);    // drop all edges incident to b
    remove_vertex(b, g);   // now safe to erase

    std::cout << "after:  " << num_vertices(g) << " vertices, "
              << num_edges(g) << " edges\n";
}

before: 3 vertices, 3 edges
after:  2 vertices, 1 edges

When are my vertex or edge descriptors invalidated?

With VertexList = vecS, remove_vertex reindexes every later vertex. Any saved descriptor past the removed one is stale. With listS or setS, descriptors are pointers and survive removals. Edge descriptors follow the same rule for OutEdgeList.

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

int main() {
    using namespace boost;

    // vecS: descriptors are indices into a vector. Removing 1 shifts 2 -> 1.
    using Vec = adjacency_list<vecS, vecS, directedS>;
    Vec g(3);
    std::cout << "before remove: ";
    for (auto v : make_iterator_range(vertices(g))) std::cout << v << " ";
    remove_vertex(1, g);
    std::cout << "\nafter  remove: ";
    for (auto v : make_iterator_range(vertices(g))) std::cout << v << " ";
    std::cout << "\n";
    // What used to be vertex 2 is now vertex 1. Any saved descriptor is stale.
}

before remove: 0 1 2
after  remove: 0 1

How do I create a graph whose edges are sorted or deduplicated?

Pick setS as the OutEdgeList selector. Out-edges are kept in target-vertex order and duplicates are dropped at insertion.

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

int main() {
    using namespace boost;
    using Graph = adjacency_list<setS, vecS, directedS>;

    Graph g(1);
    add_edge(0, 3, g);
    add_edge(0, 1, g);
    add_edge(0, 2, g);
    add_edge(0, 2, g);  // duplicate; setS drops it

    std::cout << "out-edges of 0:";
    for (auto e : make_iterator_range(out_edges(0, g)))
        std::cout << " " << target(e, g);
    std::cout << "\n";
}

out-edges of 0: 1 2 3

Using algorithms

How do I stop a search early?

Throw from the visitor and catch around the algorithm call. That is the only supported mechanism. The algorithms have no "return early" hook.

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

using namespace boost;
using Graph = adjacency_list<vecS, vecS, undirectedS>;
using Vertex = graph_traits<Graph>::vertex_descriptor;

struct Found {};

struct StopAt : default_bfs_visitor {
    Vertex target;
    explicit StopAt(Vertex t) : target(t) {}
    void discover_vertex(Vertex v, const Graph&) const {
        std::cout << "visit " << v << "\n";
        if (v == target) throw Found{};
    }
};

int main() {
    Graph g(5);
    add_edge(0, 1, g); add_edge(0, 2, g);
    add_edge(1, 3, g); add_edge(2, 4, g);

    try {
        breadth_first_search(g, 0, visitor(StopAt{3}));
    } catch (const Found&) {
        std::cout << "stopped at target\n";
    }
}

visit 0
visit 1
visit 2
visit 3
stopped at target

Is there a non-throwing way to stop Dijkstra or BFS early?

Not today. Every early-exit path in the public API raises an exception from the visitor. Community feedback at the Boost.Graph 2026 workshop identified this as a pain point; a graceful-termination hook is on the library’s roadmap but not yet implemented.

Why does algorithm X work with `vecS` but not `listS`?

The algorithm needs a vertex index. With VertexList = vecS adjacency_list synthesizes one; with listS it does not, so you must supply your own. Add an index field to the bundle and pass it through the vertex_index_map named parameter.

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

using namespace boost;
struct V { std::size_t idx; };
using Graph = adjacency_list<listS, listS, undirectedS, V>;

int main() {
    Graph g;
    for (std::size_t i = 0; i < 4; ++i) add_vertex(V{i}, g);

    auto it = vertices(g).first;
    auto s = *it; auto t = *++it;
    add_edge(s, t, g);

    breadth_first_search(g, s,
        visitor(default_bfs_visitor())
            .vertex_index_map(get(&V::idx, g)));

    std::cout << "bfs ok on listS using bundled vertex_index_map\n";
}

bfs ok on listS using bundled vertex_index_map

Why is the visitor passed by value?

Because a temporary cannot bind to a non-const reference, and BGL wants to accept visitors constructed in-place at the call site. Any mutable state inside the visitor therefore lives on the internal copy and does not leak back out. Hold state by pointer or reference if you need it to.

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

using namespace boost;
using Graph = adjacency_list<vecS, vecS, undirectedS>;

struct Counter : default_bfs_visitor {
    int* n;  // indirection so mutations escape the copy
    explicit Counter(int* p) : n(p) {}
    template <typename V, typename G>
    void discover_vertex(V, const G&) const { ++*n; }
};

int main() {
    Graph g(4);
    add_edge(0, 1, g); add_edge(1, 2, g); add_edge(2, 3, g);

    int n = 0;
    breadth_first_search(g, 0, visitor(Counter{&n}));
    std::cout << "discovered " << n << " vertices\n";
}

discovered 4 vertices

Views, adaptors, I/O

`filtered_graph` or `subgraph`: which one?

filtered_graph is a non-owning view built from two predicates (vertex, edge). No copy, no heap allocation; the original graph is unchanged. Use it to run an algorithm over a subset.

subgraph owns a copy of the edges and tracks a parent-child relationship. Use it when you need a mutable independent graph that mirrors back to a parent on add_edge.

Rule of thumb: reach for filtered_graph first.

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

using namespace boost;
using Graph = adjacency_list<vecS, vecS, undirectedS>;

struct KeepEven {
    const Graph* g = nullptr;
    bool operator()(graph_traits<Graph>::vertex_descriptor v) const {
        return v % 2 == 0;
    }
    bool operator()(graph_traits<Graph>::edge_descriptor e) const {
        return (*this)(source(e, *g)) && (*this)(target(e, *g));
    }
};

int main() {
    Graph g(6);
    for (int u = 0; u < 6; ++u)
        for (int v = u + 1; v < 6; ++v)
            add_edge(u, v, g);  // K6

    KeepEven p{&g};
    filtered_graph<Graph, KeepEven, KeepEven> sub(g, p, p);

    std::cout << "filtered vertices:";
    for (auto v : make_iterator_range(vertices(sub))) std::cout << " " << v;

    // num_edges on a filtered_graph returns the underlying count; count manually.
    int kept = 0;
    for (auto e : make_iterator_range(edges(sub))) { (void)e; ++kept; }
    std::cout << "\nfiltered edges: " << kept << "\n";
}

filtered vertices: 0 2 4
filtered edges: 3

How do I read GraphML or GraphViz with custom properties?

Both readers take a boost::dynamic_properties object. Register each property map you want populated under a string name matching the attribute in the file. Full examples on the GraphML and GraphViz pages.

C++ and library design

Why doesn’t `graph_traits<Graph>::vertex_descriptor` compile inside my function template?

Graph is a template parameter, so graph_traits<Graph>::vertex_descriptor is a dependent name. C++ requires you to tell the compiler it names a type by prefixing with typename.

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

using namespace boost;

template <typename G>
typename graph_traits<G>::vertices_size_type  // note: typename required
count_vertices(const G& g) {
    return num_vertices(g);
}

int main() {
    using Graph = adjacency_list<vecS, vecS, undirectedS>;
    Graph g(5);
    std::cout << "|V| = " << count_vertices(g) << "\n";
}

|V| = 5

Why free functions instead of member functions?

Free functions can be overloaded for third-party types without modifying their source. That is how BGL adapts LEDA, Stanford GraphBase, and even a raw std::vector<std::list<…>>. A member-function-based API would have forced every integration to go through an adaptor class.

Edit this Page