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.

Writing Algorithms for BGL

BGL algorithms are template functions that accept graphs and property maps as parameters. This design means your algorithm works with any graph type and any storage strategy, without knowing the concrete types at compile time.

The pattern

Every BGL algorithm follows the same structure:

  1. Accept the graph as a template parameter constrained by a graph concept (e.g., VertexListGraph, IncidenceGraph).

  2. Accept data (weights, distances, colors) as property map parameters.

  3. Access data exclusively through get(map, key) and put(map, key, value).

The algorithm never knows whether the data lives inside the graph, in a std::vector, in a std::map, or is computed on the fly. It only knows the property map interface.

Example: edge relaxation

The relax() function used inside Dijkstra’s shortest paths illustrates this pattern. It needs two properties: edge weights and vertex distances. Both are accepted as template parameters and accessed through get() and put().

template <class Edge, class Graph,
          class WeightPropertyMap,
          class DistancePropertyMap>
bool relax(Edge e, const Graph& g,
           WeightPropertyMap weight,
           DistancePropertyMap distance)
{
    auto u = source(e, g);
    auto v = target(e, g);
    if (get(distance, u) + get(weight, e) < get(distance, v)) {
        put(distance, v, get(distance, u) + get(weight, e));
        return true;
    }
    return false;
}

This function works with any combination of graph type and storage:

  • weight could be a bundled property (get(&Road::km, g)), an external vector, or a computed map.

  • distance could be a std::vector wrapped with make_iterator_property_map, or a vector_property_map.

The caller decides. The algorithm does not care.

Constraining your algorithm

Use graph concepts to document and enforce what your algorithm requires:

Your algorithm needs Require this concept

Iterate over all vertices

VertexListGraph

Traverse out-edges of a vertex

IncidenceGraph

Traverse both out-edges and in-edges

BidirectionalGraph

Check if an edge exists between two vertices

AdjacencyMatrix

Add or remove vertices and edges

MutableGraph

For property maps, use static_assert to check the category:

static_assert(
    std::is_convertible<
        typename property_traits<DistanceMap>::category,
        read_write_property_map_tag>::value,
    "distance_map must be a ReadWrite property map");

This gives the caller a clear error if they pass the wrong map type.

Writing a custom property map

Implementing your own property map requires overloading get() and put() (and optionally operator[] for Lvalue maps), plus providing property_traits typedefs. Here is a simplified iterator_property_map:

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

// A simplified iterator_property_map to show how custom property maps work.
// Wraps a random access iterator and an ID map (descriptor -> integer offset).
template <class Iterator, class IDMap>
class iterator_map {
public:
    using key_type   = typename boost::property_traits<IDMap>::key_type;
    using value_type = typename std::iterator_traits<Iterator>::value_type;
    using reference  = typename std::iterator_traits<Iterator>::reference;
    using category   = boost::lvalue_property_map_tag;

    iterator_map(Iterator i = Iterator(), const IDMap& id = IDMap())
        : m_iter(i), m_id(id) {}

    Iterator m_iter;
    IDMap    m_id;
};

// get(): read a value
template <class Iter, class ID>
typename std::iterator_traits<Iter>::value_type
get(const iterator_map<Iter, ID>& m,
    typename boost::property_traits<ID>::key_type key)
{
    return m.m_iter[get(m.m_id, key)];
}

// put(): write a value
template <class Iter, class ID>
void put(const iterator_map<Iter, ID>& m,
         typename boost::property_traits<ID>::key_type key,
         const typename std::iterator_traits<Iter>::value_type& value)
{
    m.m_iter[get(m.m_id, key)] = value;
}

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

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

    // Use our custom property map to store labels
    std::vector<std::string> labels(num_vertices(g));
    auto index = get(vertex_index, g);
    iterator_map<std::vector<std::string>::iterator,
                 decltype(index)> label_map(labels.begin(), index);

    // Write through the property map
    put(label_map, vertex(0, g), "A");
    put(label_map, vertex(1, g), "B");
    put(label_map, vertex(2, g), "C");
    put(label_map, vertex(3, g), "D");

    // Read through the property map
    for (auto vi = vertices(g).first; vi != vertices(g).second; ++vi) {
        std::cout << "vertex " << *vi << " = " << get(label_map, *vi) << "\n";
    }
}
vertex 0 = A
vertex 1 = B
vertex 2 = C
vertex 3 = D

The key insight: the IDMap converts opaque descriptors to integer offsets, and the iterator provides contiguous storage at those offsets. The three functions (get, put, and optionally a reference-returning accessor) are all that algorithms need.

How raw pointers become property maps

The same mechanism is how raw C arrays work as property maps. The library provides a property_traits specialization for pointer types:

namespace boost {
    template <class T>
    struct property_traits<T*> {
        using value_type = T;
        using key_type   = std::ptrdiff_t;
        using category   = lvalue_property_map_tag;
    };

    template <class T>
    void put(T* pa, std::ptrdiff_t key, const T& value) { pa[key] = value; }

    template <class T>
    const T& get(const T* pa, std::ptrdiff_t key) { return pa[key]; }
}

This is why int dist[N] can be passed directly as a distance map when VertexList=vecS (vertex descriptors are integers). The same pattern applies to std::vector::iterator, which may be a pointer.

See also

Edit this Page