External Properties

When data lives outside the graph.

Why external?

Not all data belongs inside the graph object. Common reasons to store properties externally:

Algorithm output. Distances, predecessors, and components are produced by algorithms and do not need to persist inside the graph.
Temporary data. Color maps and other bookkeeping exist only for the duration of one algorithm call.
Reusable storage. A single pre-allocated vector can serve multiple algorithm runs, avoiding repeated heap allocations.
Custom allocators. You control the container, so you choose the allocator, memory layout, or backing store.

Vectors with index maps

This is the core pattern for external properties.

Vertex and edge descriptors are opaque handles. They are not always integers, so you cannot use them directly as array indices. An index map bridges descriptors to contiguous offsets in a container.

auto index = get(vertex_index, g);
std::vector<int> dist(num_vertices(g));
auto dist_map = make_iterator_property_map(dist.begin(), index);

make_iterator_property_map combines an iterator (the start of the storage) with an index map (the descriptor-to-offset mapping) into a property map that algorithms can read and write through get(dist_map, v) and put(dist_map, v, value).

The vector must be sized to at least num_vertices(g) (or num_edges(g) for edge properties) before you create the property map. An undersized vector causes undefined behavior with no compile-time warning.

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

int main() {
    using namespace boost;
    using Graph = adjacency_list<vecS, vecS, directedS, no_property,
                                 property<edge_weight_t, int>>;
    using Vertex = graph_traits<Graph>::vertex_descriptor;

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

    auto index = get(vertex_index, g);
    std::vector<int> dist(num_vertices(g));
    std::vector<Vertex> pred(num_vertices(g));
    auto dist_map = make_iterator_property_map(dist.begin(), index);
    auto pred_map = make_iterator_property_map(pred.begin(), index);

    dijkstra_shortest_paths(g, vertex(0, g),
        pred_map, dist_map, get(edge_weight, g), index,
        std::less<int>(), closed_plus<int>(),
        std::numeric_limits<int>::max(), 0,
        default_dijkstra_visitor());

    for (auto v : make_iterator_range(vertices(g))) {
        std::cout << "d[" << v << "] = " << dist[v] << "\n";
    }
}

d[0] = 0
d[1] = 1
d[2] = 3
d[3] = 6

Raw arrays

When VertexList=vecS, vertex descriptors are integers starting at zero. Raw C arrays and pointers work directly as property maps with no wrapper needed.

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

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

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

    int dist[4];
    int pred[4];

    dijkstra_shortest_paths(g, vertex(0, g),
        pred, dist, get(edge_weight, g), get(vertex_index, g),
        std::less<int>(), closed_plus<int>(),
        std::numeric_limits<int>::max(), 0,
        default_dijkstra_visitor());

    for (int i = 0; i < 4; ++i) {
        std::cout << "d[" << i << "] = " << dist[i] << "\n";
    }
}

d[0] = 0
d[1] = 1
d[2] = 3
d[3] = 6

Edge-based external properties

The same pattern works for edges when you have an edge_index property. Store capacity or flow in external arrays, then wrap them with the edge index map.

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

int main() {
    using namespace boost;

    // Graph with edge_index as an internal property
    using Graph = adjacency_list<vecS, vecS, directedS,
                                 no_property,
                                 property<edge_index_t, std::size_t>>;

    Graph g(4);
    // Assign each edge an index manually
    add_edge(0, 1, 0, g);
    add_edge(0, 2, 1, g);
    add_edge(1, 2, 2, g);
    add_edge(1, 3, 3, g);
    add_edge(2, 3, 4, g);

    // External arrays indexed by edge ID
    int capacity[] = {10, 20, 30, 40, 50};
    int flow[]     = { 8, 12, 25, 32, 45};

    auto edge_id = get(edge_index, g);
    auto cap_map  = make_iterator_property_map(capacity, edge_id);
    auto flow_map = make_iterator_property_map(flow, edge_id);

    for (auto ei = edges(g).first; ei != edges(g).second; ++ei) {
        std::cout << source(*ei, g) << " -> " << target(*ei, g)
                  << "  capacity=" << get(cap_map, *ei)
                  << "  flow=" << get(flow_map, *ei) << "\n";
    }
}

0 -> 1  capacity=10  flow=8
0 -> 2  capacity=20  flow=12
1 -> 2  capacity=30  flow=25
1 -> 3  capacity=40  flow=32
2 -> 3  capacity=50  flow=45

std::map for non-integer keys

When VertexList=listS, vertex descriptors are pointers, not integers. There is no built-in vertex index map. Use std::map with make_assoc_property_map instead.

auto depth_map = make_assoc_property_map(my_map);

This wraps the map so that get(depth_map, v) and put(depth_map, v, val) call my_map[v] and my_map[v] = val respectively.

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

int main() {
    using namespace boost;
    using Graph = adjacency_list<vecS, listS, directedS>;
    using Vertex = graph_traits<Graph>::vertex_descriptor;

    Graph g;
    Vertex a = add_vertex(g), b = add_vertex(g);
    Vertex c = add_vertex(g), d = add_vertex(g);
    add_edge(a, b, g);
    add_edge(a, c, g);
    add_edge(b, d, g);
    add_edge(c, d, g);

    std::map<Vertex, int> depth;
    auto depth_map = make_assoc_property_map(depth);

    put(depth_map, a, 0);
    put(depth_map, b, 1);
    put(depth_map, c, 1);
    put(depth_map, d, 2);

    for (auto v : make_iterator_range(vertices(g))) {
        std::cout << "depth = " << get(depth_map, v) << "\n";
    }
}

depth = 0
depth = 1
depth = 1
depth = 2

Edit this Page